Paper Reading - Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation

``Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation'', He et al., ACL 2020.

Transcript

1. Dynamic Programming Encoding for Subword Segmentation in Neural Machine Translation (He et al., ACL 2020) 出口 祥之 Á deguchi@ai.cs.ehime-u.ac.jp 2020/09/11 第 2 回 NLG/MT Reading Group
2.  Links  Paper https://www.aclweb.org/anthology/2020. acl-main.275/  Source Code https://github.com/xlhex/dpe 1/22
3. Introduction 動的計画法を用いた新たなサブワード分割法を提案 目的言語文の分割を潜在変数と見做し，周辺化 “Mixed character-subword Transformer”: 原言語文が与えられたときの目的言語文の分割を獲得 NMT におけるサブワード分割 貪欲法: バイトペア符号化 (BPE)¹, WordPiece² 確率的アルゴリズム: ユニグラム LM³, BPE-dropout⁴ 動的計画法: 本論文の提案手法 ¹``Neural Machine Translation of Rare Words with Subword Units'', Sennrich et al., 2016. ²``Japanese and Korean voice search'', Schuster et al., 2012. ³``Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates'', Kudo, 2018. ⁴``BPE­Dropout: Simple and Effective Subword Regularization'', Provilkov et al., 2020. 2/22
4. Related Work (Greedy Segmentation) BPE (Sennrich et al. 2016) , WordPiece (Schuster and Nakajima 2012) 隣接する頻出サブワードから順に，予め指定した 語彙数に到達するまで再帰的に結合 (BPE) 語彙数とデコード速度はトレードオフ • (語彙数を小さくするだけであれば文字単位でよい) • テキスト圧縮の技術を利用 • 語彙数の上限を制約とし，文長が短くなるような 分割を得るアルゴリズム 例: unconscious → un + conscious 3/22
5. Related Work (Stochastic Segmentation) ユニグラム LM (Kudo 2018) , BPE-dropout (Provilkov et al. 2020) 複数分割候補を得られる • ユニグラム LM: 尤度ベースでサンプリング • BPE-dropout: BPE 結合時に確率的に棄却 • NMT 訓練時に分割を確率的に得ることでデータ拡張 (Data Augumentation) の効果 モデルの頑健性向上 例: unconscious → {un + concious, uncon + scious} 4/22
6. Related Work (Dynamic Programming Algorithms) 音声認識 (Wang et al. 2017) 取り得る全ての分割や入出力間のアライメントの確率を 動的計画法により計算 非自己回帰 NMT モデル (Chan et al. 2020; Saharia et al. 2020) Imputer (Chan et al. 2020) : Connectionist Temporal Classification (CTC) を用い，定数 回のデコードで出力とその順序を予測 非自己回帰 NMT モデルに Imputer を適用 (Saharia et al. 2020) 5/22
7. Proposed Method
8. Latent Subword Segmentation - Definitions 目的言語文の分割を潜在変数とみなす M 個のサブワード: {yzi,zi+1 }M i=1 • y = (y1, . . . , yT ): 目的言語文の文字列 • z = (z1, . . . , zM+1): 境界位置系列 0 = z1 < z2 < . . . < zM < zM+1 = T (昇順) • ya,b : (a + 1)th から bth まで結合したサブワード 例: 辞書 V = {c, a, t, ca, at} 目的言語文 y = cat z サブワード列 (0, 1, 3) (c, at) (0, 2, 3) (ca, t) (0, 1, 2, 3) (c, a, t) 6/22
9. Latent Subword Segmentation - Likelihood 連鎖律を用いてサブワード列の対数尤度を表現 各サブワード位置において語彙の確率分布を生成 log p(y, z|x) = |z| ∑ i=1 log p(yzi,zi+1 |yz1,z2 , . . . , yzi−1,zi , x) ※ x : 原言語文 殆どの NMT では z を暗黙的に log p(y, z) ≈ log p(y) と仮定 7/22
10. Latent Subword Segmentation - Latent Variable z ∈ Zy (yの分割集合) を潜在表現とみなす p(y|x) = ∑ z p(y, z|x) とする log p(y|x) = log ∑ z∈Zy exp |z| ∑ i=1 log p(yzi,zi+1 |yz1,z2 , . . . , yzi−1,zi , x) ※対数周辺尤度の下限: log p(y|x) ≥ log p(y, z|x) 各サブワードの確率が条件部のコンテキストの分割 に依存するため，巨大な空間 Zy 上での厳密な周辺化 は組み合わせ爆発を起こす • コンテキストが次に来るサブワードの確率に 影響しないモデルが必要 8/22
11. A Mixed Character-Subword Transformer 文字に基づいてサブワードを生成する Transformer 条件部のコンテキストを文字のみに log p(y, z|x) = |z| ∑ i=1 log p(yzi,zi+1 |yz1 , . . . , yzi , x) y の各文字位置 t において，次に来るサブワード w ∈ V の分布を以下に基づいて生成 p(w|y1 , . . . , yt , x) = exp(f(y1 , . . . , yt ) e(w)) ∑ w ∈V exp(f(y1 , . . . , yt ) e(w )) • f(·) : Transformer により条件部の計算 • e(·) : ソフトマックス層の重み 9/22
12. A Mixed Character-Subword Transformer t ステップ目のモデル出力 (1) t ステップ目でサブワード w を 生成 (2) サブワード w の文字をデコーダ に入力 ( t + 1 から t + |w| まで) (3) t + |w| ステップ目で次のサブワ ードを生成 10/22
13. Optimization 目的関数 L(θ) を最大化 L(θ) = ∑ (x,y)∈D log Pθ (y|x) 必要な計算 周辺尤度の計算 対数周辺尤度の勾配計算 11/22
14. Exact Marginalization 動的計画法を用いて周辺尤度を計算 サブワードの出力確率が文字のみによって得られる ため動的計画法によって対数周辺尤度が計算可能 計算量: O(mT) • m : 語彙に含まれる最長の単語の文字数 12/22
15. Gradient Computation 計算量に関する問題点 通常の Transformer デコーダより 8 倍遅く，メモリ 使用量も増加 ⁵ • DP アルゴリズムと文字レベルでの演算による系列長 の増加が原因 対処法 Transformer のレイヤ数を 6 から 4 に削減 16 ステップ分勾配蓄積 (Gradient Accumulation) して からパラメタ更新 ⁵PyTorch での著者実装で比較 13/22
16. Segmenting Target Sentences Dynamic Programming Encoding (DPE): 最大事後確率を持つ目的言語文の分割を探索 14/22
17. Segmenting Target Sentences Mixed character-subword Transformer は 訓練データの目的言語文の分割のためのみに使用 分割した文で通常のサブワード Transformer を訓練 15/22
18. Experiments データセット WMT09 En-Hu, WMT14 En-De, WMT15 En-Fi, WMT16 En-Ro, WMT18 En-Et モデル NMT アーキテクチャ Transformer base 分割 (原言語側) BPE-dropout (p = 0.05) 　　 (目的言語側) DPE (提案手法) 16/22
19. Main Results 17/22
20. Segmentation Examples 他の例は論文参照 18/22
21. Conditional Subword Segmentation 原言語文を条件部に入れず，LM で分割 同一の目的言語文で原言語側を変えて違いを比較 19/22
22. Conditional Subword Segmentation 原言語文が BPE-dropout によって変化することの有効性 20/22
23. DPE vs BPE 目的言語側の分割アルゴリズムを変えて比較 21/22
24. Conclusion 新たなサブワード分割法 Dynamic Programming Encoding を提案 Mixed charcter-subword Transformer により 目的言語文を分割 • 目的言語文の分割を潜在変数と見做して周辺化 • 条件部のコンテキストを文字にすることで 動的計画法が適用可能に • 分割時は事後確率が最大となる分割を出力 BPE だけでなく BPE-dropout と比較しても 翻訳性能が向上 22/22