Improved Lexically Constrained Decoding for Translation and Monolingual Rewriting
https://scrapbox.io/files/630701271301d5001d782d3f.png
著者情報
Matt Post: sacreBLEU, 先行研究 DMA の作者 現在は Microsoft Translator チーム所属
論文を選んだ理由
現在の要約は精度的には高いものの、結局は人のチェックや修正が必要
人が手を入れるなら、生成してから修正するより作成時に指示するほうが楽なはず
文生成に条件をつける方法として有名な手法をサーベイ
この論文の偉いところ
現在も使われている語彙制約の効率的な手法を提案
アルゴリズム単体での評価だけではなく、アプリケーションで効果を測っている
イントロ
対話生成における名前や、要約における事実など生成されるテキストに含めたほうが良いものは経験的によく知られている
特定の語を使わないネガティブ制約にくらべると、特定の語を使うポジティブ制約は少し単純ではない
実用上や、大規模なデータを扱うときには少しでも早い方がよい
例えば、MT では data augmentation のために大量に back-translation(翻訳→逆翻訳)を行うことがある
制約の定義
ポジティブ制約:複数の、トークンもしくはトークン列が出力に必ず含まれるようデコーディングを制約する
ネガティブ制約:特定のトークンやトークン列が必ず出力に含まれないようにデコーディングを制約する
手法
デコーディングでは与えられた単語列に1トークンずつ追加していき、文を生成する。生成済みのトークン列に対して、次に追加するトークンごとにスコアが与えられる、木構造のような空間を探索して、トータルのスコアがもっとも高いトークン列を探索する問題として定式化される(が、実際はスコアさえ高ければよいわけでもない場合がある)
https://scrapbox.io/files/6307012c641a5f002392c1c5.png
イメージを掴んでもらうための、seq2seq でのデコーディングの概要図 (下図は翻訳の例)
https://scrapbox.io/files/630703f01074090020d25729.png
従来の手法 (DBA: Dynamic Beam Allocation) とその問題点
https://scrapbox.io/files/630701308b051a001dea850c.png
縦がビーム(探索の過程で保持する途中の状態)横が語彙を表している。t =そこまでで生成されたトークンの数
色のついた図形はポジティブ制約を表している(四角は左側と右側で2語、三角と丸は1語)
記号の意味は次の通り(重複しているところは省略されている)
★は全体でスコアの高い k-best
→は制約を追加で満たせることを指す
◇はそのビームで最もスコアの高い語
↺は制約の巻き戻しが発生していることを表している
制約を満たしている度合いごとに次のビーム幅をきめて、allocate で候補(グレーのマス)から残す候補を選ぶ
自然な文を生成するために、制約を満たしているものだけではなく満たしていないものも幅広く残すことが必要
https://scrapbox.io/files/630702c35ea556001db50d78.png
問題点
Post and Vilar の手法 (DBA) はコーナーケースでうまく行っていなかった https://scrapbox.io/files/630701330d3749001d762e9f.png
複数のトークン列の制約があり、かつそのトークン列同士で同じトークンを共有している場合に、どちらか1つの制約しか、制約が満たされている状態のトラッキングができない(ただのバグでは?)
DBA はバッチで実行できなかった
制約を満たしている度合いごとにビームに割り当てする部分がバッチに対してまとめて実行できないため、バッチで実行するメリットが薄い
バッチで実行できない=行列の操作で結果がでる形で表せなかった
提案手法 Vectorized DBA の Vectorized はバッチに対応するの意
MST (Multi-state tries)
コーナーケースの対策として、制約を木構造(trie) で表現することにした。https://scrapbox.io/files/6307013622d5380023824d1f.png
ノード横の数字はそのノードを何回通る必要があるかを表しており、0 になるとそのノードは削除される
ネガティブ制約も同じく trie で表され、制約されるトークン列の末尾が禁止ノードとしてマークされる
VDBA (vectorized Dynamic Beam Allocation)
行列のソートの形で DBA の機能を実装する
https://scrapbox.io/files/630701385ea556001db4ecf5.png
同じバッチ内で扱われている全ての候補を1つの行列で表している
次のビームに生き残る(Allocationされる)のはグレーになっている列
各行の意味
sentno: バッチ内の何文目かを表す番号
unmet: 満たされていない制約の数
score: 候補の持っているスコア
hypo#: どのビームから出てきたかを表す番号
vocab ID: 選択したトークンのID
step: 同じsentnoとunmet を持つ候補内で、スコアが高い順に0,1,2 と割り振られる
step が小さい順に選ぶことで、unmet の値が同じ列の中からスコアの高いものを一つずつラウンドロビンで選べるようになっている
第1キー: sentno, 第2キー: unmet, 第3キー: step で列をソートしてk-ベストを選択する、と書かれているがそのとおりにソートすると上の表の左からk個選ぶことになってしまうので、sentnoごとに (step, unmet) をキーとしてk-ベストを選択しているものと思われる
実験結果
https://scrapbox.io/files/6307013c46137d001dab5e6e.png
機械翻訳タスクで生成速度と生成された文を評価(ビーム幅 10)
none 制約なし
phr4 リファレンスから連続する4語をランダムに選択し、ポジティブ制約として追加
rand3 リファレンスから3語をランダムに選択し、ポジティブ制約として利用
Baseline は Post and Vilar (2018) の手法、VDBAの Vectorize の無いバージョン
制約を部分的に満たしている度合いごとにビーム幅を均等に割り当てる
バッチサイズが大きい場合に速度が改善、BLEUスコアも良くなっている
BLEUが良くなるのは、VDBAにより制約の元でより自然な文を選べているから
従来手法では均等に割付できないビームを一番制約を満たせているグループに割り振ってしまっていたため、不自然な文が生き残りやすかった
パラフレーズ(言い換え)文生成器とそれを利用したData augmentation の実験結果は割愛
要約とはほとんど関係がないのと、BERT 以前の手法で実験しているためあまり参考にならない
結論
制約付きの生成が速く、かつより自然な生成になるところが嬉しい
今回は紹介していないが、パラフレーズによる Data augmentation もデータが少ない時には特に有効
とはいえ、大量のデータで事前学習されている現在も有効かは不明
コメント
思ったよりも実装よりのアルゴリズムの話だったので興味から外れていないか心配
このアルゴリズムを元にしたものが Transformers で実装されているので、引数指定するだけですぐに使えます
コーナーケースへの対処を評価できる実験がなかったのは少し残念
参考文献
分かりやすい制約付きビームサーチの解説、Transformers での実装について
先行研究: Fast Lexically Constrained Decoding with Dynamic Beam Allocation for
今日紹介できなかった、seq2seq のデコーディングの詳しい説明