[1804.10959] Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates [paper-reading]

[yoheikikuta]

論文リンク

https://arxiv.org/abs/1804.10959

公開日（yyyy/mm/dd）

2018/04/29

概要

subword 分割には任意性があり（hello という文字列をどう分割するかはいくつかのパターンがある。もちろん出現頻度などでどの分割がよさそうかは一定判断できるが、そこには単語分割などと異なり言語学的な justification は存在しない）、その任意性を noise として使うことで正則化や data augmentation の効果を得る subword regularization の提案。
subword 分割の任意性を確率的に表現する unigram 言語モデルも同時に提案して、実験により subword regularization の効果が機械翻訳の文脈で効果があることを実証。
機械翻訳モデルのアーキテクチャとは独立に適用でき、source/target 文章の双方に適用できる、柔軟な手法であることが特徴。

[yoheikikuta]

SentencePiece #68 論文を読んで subword regularization が触れられているので、合わせてこちらも読んでおこうというモチベーション。

subword の分割には任意性があるが、その任意性を逆手に取ってノイズとして利用して学習をすることで、正則化効果を高めようとする手法。

[yoheikikuta]

open vocabulary 問題における subword の有効性は示されているが、この論文では subword の分割には任意性があることに注目する。
例えば Hello world は次のように様々な分割がありうる。

これは元は Hello world という曖昧さのない文字列でありながら、その分割は任意性があるので、論文では spurious ambiguity と呼んでいる。この spurious に込められた気持ちは、本質的には一通りだけあればいいはずなのに複数パターンを取りうる、というところから来ているのだろう。

さらに論文ではこの spurious ambiguity は might not be resolved in decoding process であると続くが、これはちょっと意図が掴みきれない。id sequence が与えられれば文字列に戻すのは一意なのでそういうことではないはずだし、異なる id sequence から同じ文字列になりうるということならそれは encode に任意性があるので明らかということになるので。まあここは本質的に重要になる部分ではなさそうなので置いておく。

この論文ではこの任意性を活かした正則化手法を提案していて、subword regularization と呼んでいる。
論文の貢献としては以下の 2 つ。

• 複数の分割候補を統合するためのシンプルな機械翻訳の学習アルゴリズムの提案。機械翻訳モデルのアーキテクチャに依存しない on the fly なサンプリングとして実装される。
• 言語モデルに基づいた新しい subword 分割アルゴリズムの提案。任意性ある分割を確率的に提供できるもの（BPE は学習時の merge プロセスは一意であるので一度学習すると一通りの分割しか提供しない。学習時のデータによって異なる分割になりうるが、これは確率的ではない）。

[yoheikikuta]

まずは問題のセットアップ。

• $\textbf{x} = \{ x_1, x_2, \dots, x_M \}$ : 入力の subword sequence
• $\textbf{y} = \{ y_1, y_2, \dots, y_N \}$ : 出力の subword sequence
• $\theta$ : モデルパラメタ

出力の生成は以下で実施。

機械翻訳モデルは D を corpus として s はその中のサンプルとして、以下の対数尤度最大化で学習。

subword sequence を作る際には、いくつかの分割方法がある。ここではその分割を P(x|X), P(y|Y) で与えられるとして、subword regularization 込みでの尤度関数は次で表現できる。分割が確率的に与えられるのでそれをサンプルしているだけである。

可能な分割は文字列の長さに対して指数的に増えていくので、これを exact にやることは現実的に不可能である。
サンプリング回数を k 回にすることで近似することにする。

簡単のため k = 1 を用いる。
ミニバッチ学習で何度も iteration を回すので、その度に on the fly でサンプルすることになるので、k = 1 でも良い近似になると期待できる。

[yoheikikuta]

機械翻訳の decoding (入力文章が与えられてそれから出力文章を出すこと) に関しては、分割が確率的なのでシンプルに確率最大を取るか、複数個を取り出して以下でスコアリングして最も良い y を決めるということを考えている。ここで、$|y|$ は出力 subword sequence 長であり、 $\lambda$ はパラメタである。

[yoheikikuta]

BPE は greedy でかつ deterministic なので、subword regularization を適用することは非自明である。
この論文では subword regularization を適用しやすい言語モデルとして unigram 言語モデルを提案している。

名前の通りサブワードが独立に出現するという（強い）仮定を置いて、以下のように定式化する。

ここで、$\mathcal{V}$ は事前に定めた語彙集合である。
これは subword sequence が与えられた時の確率モデリングであり、unigram にしてるのは語彙集合が大きいので n-gram (n > 1) にすると計算量的に扱いが大変になるというものだろう。
最も可能性の高い分割は分割候補からこの P(x) を最大化するような x を選べばいいことになり、これは Viterbi アルゴリズムで求めることができる。

語彙集合が与えられていれば、subword の出現確率 $p(x_i)$ は次の周辺化尤度関数を最大化するような EM アルゴリズムで求めることができる。具体的には、$p(x_i)$ を隠れ変数と見て、まずは初期化された $p(x_i)$ からスタートして P(x) を計算し、その確率分布に基づいて対数尤度を最大化する、というステップを繰り返すということである。

まず corpus $D$ から 1 つ sentence $X^{(s)}$ を持ってきて、その sentence をどのように分割するかの候補として $S(X^{(s)})$ から一つの分割 $x$ をで選んで $P(x)$ を計算する（これは (6) 式で unigram 言語モデルとして定義されている）ということになっている。
重要になるのは、我々が変えうるものとしては語彙集合をどう設定するかと各語彙にの unigram 発生確率 $p(x)$ をどう設定するか、そして分割候補 $S(X^{(s)})$ 全てで和をとっている（前述のようにこれは可能な分割全てを考えると指数的に発散するのでサンプリングする）、ということである。

これが定式化であるが、実際の状況においてはもちろん語彙集合は未知である（これこそが求めたいものである）。
語彙集合と各語彙の出現確率を同時に最適化することは intractable であるため、以下のようなアルゴリズムで探し求めていく。

• まずは heuristic に大きな語彙集合を準備
  • 自然な選び方はすべての文字とコーパス内で最も頻出する部分文字列の和集合を使用するというもので、後者の部分文字列の和集合は Enhanced Suffix Array algorithm というもので時間的には $O(|D|)$ で空間的には $O(20 |D|)$ で計算できるとのこと。
• 語彙集合の大きさが所望のものになるまで、以下のステップを繰り返して語彙集合の大きさを小さくしていく
  • p(x) を EM アルゴリズムで最適化して求める。
  • 各 subword $x_i$ に対して $loss_i$ を計算する。$loss_i$ は subword $x_i$ を語彙集合から取り除いたときに尤度がどれくらい変わるかを測るものとして設定する。
  • $loss_i$ の値に基づいて subword をソートして、上位 $\eta$ (例えば 80%) の subword は残してそれ以外は捨てる（語彙集合を小さくする）。ただし、一文字の subword は out of vocabulary を避けるために必ず保持する。

---

suffix array に関しては Wikipedia がこれ https://en.wikipedia.org/wiki/Suffix_array
efficient にしたものとしてはいくつかあるらしく、この論文で引用している SA-IS アルゴリズムや他にも SACA-K アルゴリズムなどがある。これらは純粋にアルゴリズムの話なのでここではメモを残さないが、最近の生成AIの進展により、こういうアルゴリズム系の理解を深めるためにやり取りするのはだいぶやりやすくなったね。

[yoheikikuta]

P(x∣X) からサブワード分割をサンプリングするする方法としては、まず得られている subword unigram 言語モデルに基づいて確率が大きい順に l 個の分割を取得し、その後に $P(x_i | X) \simeq P(x_i)^\alpha / \sum_i^l P(x_i)^\alpha$ に基づいてサンプルする。

$\alpha$ はパラメタで小さいほど一様分布に近いところからサンプリングし（ $\alpha = 0$ とすれば一様分布そのもの）、大きいほど Viterbi 分割からサンプリングする（確率が最も大きい分割のみを選ぶ）ことになる。

l を十分に大きくすれば全ての可能な分割を考慮することになるが、これは現実的ではない。
すべての可能な分割から正確にサンプリングするために、動的計画法の一種である Forward-Filtering and Backward-Sampling algorithm を用いている。

SentencePiece のコードで言えばこの辺りが unigram のサンプリング
https://github.com/google/sentencepiece/blob/d8f741853847553169444afc12c00f4bbff3e9ce/src/unigram_model.cc#L345

[yoheikikuta]

BPE との比較として、BPE は辞書型エンコーダー、unigram 言語モデルはエントロピーエンコーダー（任意の可逆データ圧縮方式をこのように呼ぶ）としてテキストの総コード長を最小化するものであり、分割戦略としては似ている。

unigram 言語モデルは確率的な言語モデルに基づいているため、より柔軟で確率付きで複数の分割を出力することが可能である。
これは、サブワード正則化において本質的に重要となる。

BPE はシンプルで使いやすいけど、本質的に存在する分割の任意性を扱って何かしらの改善（この論文では正則化として使う）をしたい時には柔軟性がある unigram 言語モデルの方がいいね、ということだね。これはまあそうですねという感じ。

[yoheikikuta]

関連研究の話として、noise を加えるという意味で denoising auto encoder やそれを seq2seq の文脈で取り入れたものなどが紹介されている。

subword regularization の特徴として、従来研究が noise の入れ方がヒューリティスティックで source の文章にしか適用できなかったことに対して、unigram 言語モデルをもとにして（手法自体は unigram 言語モデルじゃないと使えないわけではない）noise を取り扱い source の文章と target の文章両方に適用できることを挙げている。それと、解釈として data augmentation としても見なせると書いてある。

分割の任意性についても述べていて、先行研究はあるけどモデルアーキテクチャに依存するものになっていたりして、subword regularization の独自性が理解できる（もちろんこういう先行研究がある中での課題感を解決するために生み出された手法なんだけど）。

モデルアーキテクチャと分離しているというのは重要な点に思う。
一つの方向性として、tokenization はモデルと独立になっていて、embedding の結果は同一でもそれを様々なモデルで扱えるみたいなのはモデルが巨大になっている昨今ではよさそうに思えるし、そういう時にはアーキテクチャと分離している有効性は高い。

data augmentation 的な効果も解釈は容易。
例えば画像でいうところの回転は回転してもオブジェクトの意味は殆どの場合変わらないということで意味があり、subword regularization の場合は分割が異なっても元のテキストの意味は変わらないということで意味があると考えられる。
subword regularization は unigram 言語モデルの学習で語彙集合を削ったりするので augmentation の適用が語彙集合の中に限定されるという意味で画像における回転ほどは普遍性を感じないが、そもそも subword 分割が任意性があり恣意的ということでさもありなんではある。

[yoheikikuta]

実験をいろいろしているが、自分としては unigram 言語モデルの話と subword regularization の定式化が理解したいところだったので、全てはメモには残さず主要な結果だけを残しておく。

実験の設定として、corpus は 5 つ使っている。
IWSLT15/17およびKFTTは比較的小規模なコーパスで異なる言語学的特性を持つ多様な言語を含んでいるのでサブワード正則化の言語非依存性を評価することができる。ASPECおよびWMT14（en↔de）は中規模のコーパスであり、WMT14（en↔cs）は1,000万以上の並列文からなる大規模コーパスである。

l は subword regularization の時の分割パターンを上位何個まで扱うかを示すもので、1 であれば Viterbi 分割で subword regularization なしを示し、∞ であれば可能な全ての分割を扱うことを示す。
α は式 (5) で出てきた source, target 文章のスコアを計算するパラメタ。

主要な結果としては次の通り:

• subword regularization なしの unigram 言語モデルは BPE とほぼ同等のBLEUスコアを示している。これは、どちらもデータ圧縮アルゴリズムに基づいているため、期待通りの結果である。
• subword regularization を入れると WMT14（en→cs）データセットを除くすべての言語ペアで、BLEUスコアが向上している（+1〜2ポイント）。特にリソースが少ない設定（IWSLTおよびKFTT）では向上幅が大きく、subword regularization による data augmentation の効果がリソースが少ない状況で効果的に働いたと考えられる。
• サンプリングアルゴリズムに関しては、IWSLTコーパスにおいて、 𝑙 = ∞ , 𝛼 = 0.2 / 0.5 が 𝑙 = 64 , 𝛼 = 0.1 をわずかに上回っているが、より大きなデータセットではほぼ同等の結果を示しており、パラメタに関する鋭敏性はそこまで強くなく一定数の分割だけ考慮すれば十分であることを示している。
• 上記の結果は decoding の時に best なものを 1 つだけ取った結果であり、subword regularization は target にも適用できるのでこれを n-best decoding をすることで更なる性能の向上が見られた。

この他にも out-of-domain な状況での検証や subword regularization を source/target のどちらかもしくは両方に適用する検証などもしており、概ね期待通りの結果であることが示されている。

しっかり実験をしてきっちり結果を出しているのはいい話ですね。

[yoheikikuta]

ということで一通り読んだ。
unigram 言語モデルと subword regularization の定式化をちゃんと理解したいモチベーションだったけど、これはちゃんと達成された。