統計的機械翻訳における フレーズ対応最適化を用いた 翻訳候補のリランキング 越川 満*　内山 将夫† 梅谷 俊治‡ 松井 知己§ 山本 幹雄* (所要時間：20秒) 統計的機械翻訳におけるフレーズ対応最適化を用いた翻訳候補のリランキングと題しまして、 筑波大学 越川が発表させていただきます。 * 筑波大学 大学院 システム情報工学研究科 † 情報通信研究機構 MASTAR プロジェクト ‡ 大阪大学 大学院 情報科学研究科 §中央大学 理工学部 情報工学科

予稿の図の訂正 予稿 ２ページ目；図２ 正しくはフレーズ3が左、フレーズ2が右 逆 2019/1/1 言語処理学会 第15回 年次大会

フレーズベース統計翻訳 以下の式に基づいて翻訳 デコーダの問題点 フレーズ対応cについて厳密な確率最大化でない max’: maxの近似解 研究の目的 　　　関連研究 　　提案手法 　　評価実験 　　まとめ フレーズベース統計翻訳 以下の式に基づいて翻訳 デコーダの問題点 フレーズ対応cについて厳密な確率最大化でない 原言語文 f it is rainy today . フレーズ対応 c 目的言語文 e 今日 は 雨 です 。 デコーダ・・・ヒューリスティック探索 与えられた f に対する翻訳として あらゆる e,c を考慮し、最も確率の 高い候補 e を出力 max’: maxの近似解 ＾ (所要時間：1分半) まず、背景としてフレーズベース翻訳について説明します。 現在、統計翻訳で最も広く用いられているフレーズベース翻訳では、 原言語文fをフレーズ単位に分割し、フレーズ毎に翻訳を行い目的言語文を得ます。 ここで、原言語－目的言語間のフレーズの対応関係をフレーズ対応といいます。 統計翻訳では、fが与えられたときのeの確率の最大化を行うことにより翻訳結果^eを決定しますが、 フレーズベースモデルでは同じ翻訳結果eを導くフレーズ対応は様々なパターンが考えられます。 そこで、この部分(Σc)でフレーズ対応についての周辺確率を求めています。 このΣcは計算コストが非常に高いため、 適切なフレーズ対応に確率が集中すると仮定してmaxcで近似します。 さらに現在用いられているデコーダではヒューリスティック探索を行っており、 この部分(maxe, maxc)は近似解max’として得られます。 このようにデコーダには2段階の近似がなされており、 そのためフレーズ対応cについて厳密な確率最大化がなされていません。 2019/1/1 言語処理学会 第15回 年次大会 it is rainy today . フレーズ ① フレーズ単位に分割 it is rainy today . c2 c1 c3 フレーズ対応 c ② フレーズ毎に翻訳 c4 目的言語文 e 今日 は 雨 です 。

研究の目的 デコーダの探索を厳密化 → 翻訳精度の改善 整数計画法を用いて 翻訳候補に最適なフレーズ対応を付与 　　　関連研究 　　提案手法 　　評価実験 　　まとめ 研究の目的 デコーダの探索を厳密化 整数計画法を用いて 翻訳候補に最適なフレーズ対応を付与 → デコーダの探索エラーの低減 　→ 翻訳精度の改善 従来法： 分解 maxcを厳密化 本研究： (所要時間：1分) そこで本研究ではデコーダの探索を厳密化することを目的とします。 具体的には、整数計画法を用いて翻訳候補に最適なフレーズ対応を付与することにより、 デコーダの探索エラーの低減を図ります。 従来法ではmax’だったこの部分をeについてとcについてに分解し、 maxcを厳密化します。 これにより、翻訳精度の改善を目指します。 2019/1/1 言語処理学会 第15回 年次大会

フレーズ対応の最適化 フレーズ対応 フレーズ対応問題 対訳文の各単語を一度ずつ被覆するフレーズ対の組合せ 研究の目的 　　　関連研究 　　提案手法 　　評価実験 　　まとめ フレーズ対応の最適化 フレーズ対応 対訳文の各単語を一度ずつ被覆するフレーズ対の組合せ フレーズ対応問題 入力：対訳文および「フレーズ対とその確率」のテーブル 出力：確率最大の(=最適な)フレーズ対応 f1　 f2　 f3　 f4 f1　 f2　 f3　 f4 f1　 f2　 f3　 f4 フレーズ対 e1　 e2　 e3 e1　 e2　 e3 e1　 e2　 e3 フレーズ対応が成立 フレーズ対応が不成立 (所要時間：1分) ここでフレーズ対応の最適化について説明します。 フレーズ対応とは、このように対訳文の各単語を一度ずつカバーする フレーズ対(枠をポインタでなぞりながら)の組合せのことを言います。 ここでf1~f4は原言語文の単語列, e1~e3は目的言語文の単語列です。 こちら(左)のふたつはフレーズ対応が成立しているのに対して、 こちらの例では、カバーされていない単語や重複してカバーされている単語があり フレーズ対応が成立しているとはいえません。 フレーズ対応問題とは、入力として対訳文およびフレーズ対とその確率のテーブルが与えられたとき、 出力として確率最大のフレーズ対応を求める問題です。 2019/1/1 言語処理学会 第15回 年次大会

フレーズ対応問題の単純な定式化 f1 f2 f3 f4 e1 e2 e3 原言語側の集合分割問題 解候補 ① 集合 分割 原言語側： 研究の目的 　　　関連研究 　　提案手法 　　評価実験 　　まとめ [DeNero and Klein 2008] 原言語側の集合分割問題 解候補 ① 集合 f1 f2 f3 f4 F1 F4 分割 原言語側： f1 f2 f3 f4 フレーズ F1 F4 f1 f2 目的言語側： e1 e2 e3 f3 f4 フレーズ対 テーブル f1 f2 E1 E4 F2 F3 より確率の高い候補が 解として選ばれる E2 解候補 ② E3 e1 e2 F2 F3 F4 e3 原言語側： e1 e2 f1 f2 f3 f4 (所要時間：1分40秒) DeNeroらにより提案された単純な定式化では、 フレーズ対応問題を、原言語側問題と目的言語側問題とを “同時に(すごく強調)” 解く複合問題として考えます。 (すなわち、フレーズ対応問題の解は原言語側の問題の解であると同時に目的言語側でも解となっています。) 原言語側に注目すると、これらのフレーズを部分集合として用いて原言語文の単語集合を一度ずつカバーする問題となります。 これらのフレーズはこの原言語文に適用可能なフレーズ対のテーブルから参照したものであり、 同じ数字の目的言語側フレーズと対応しています。 この例では、原言語側の解候補はF1、F4を用いる場合(上側)とF2、F3、F4を用いる場合(下側)の2通りがあります。 目的言語側についても同様な問題を定義し、解候補としてこれら(上と下の例を指す)が挙げられます。 ここに挙げたように原言語側と目的言語側とで適用したフレーズ同士がフレーズ対をなしている場合(フレーズ同士を結ぶ線を指して)、 これらは(紫色の括り)フレーズ対応問題の解候補となります。 このように解候補が複数存在する場合、 確率の高い方を解として出力します。 E1 E4 目的言語側： e1 e2 e3 集合 e1 e2 e3 分割 E3 E2 E4 目的言語側の集合分割問題 2019/1/1 言語処理学会 第15回 年次大会

単純な定式化とリオーダリングモデル リオーダリング確率 単純な定式化でのリオーダリング確率の表現 目的言語側で隣接のフレーズ対ペアに対し付与 研究の目的 　　　関連研究 　　提案手法 　　評価実験 　　まとめ 単純な定式化とリオーダリングモデル リオーダリング確率 目的言語側で隣接のフレーズ対ペアに対し付与 単純な定式化でのリオーダリング確率の表現 整数計画問題の変数： 各フレーズ対kに0-1変数xk フレーズ対が対応に含まれるか否かを表す リオーダリング確率は二次式で表現 [Tillmann and Zhang 2005] 原言語側で分離 原言語側でも同順 原言語側で逆順 f1 f3 f4 f1 f2 f3 f4 f1 f2 e2 e3 e1 e2 e3 e1 e2 フレーズ対 P2 P4 P1 P4 P3 P2 (所要時間：1分10秒) 次にDeNeroらの定式化のもとでのリオーダリングモデルの表現について説明します。 リオーダリング確率としては目的言語側で隣接するフレーズ対ペアに対して 原言語側での位置関係をこのような3パターンで表現し確率を付与するモデルがよく用いられます。 DeNeroらの単純な定式化では各フレーズ対に対して、 フレーズ対応中で使用されているかを0-1で表現する変数をおきます。 そのため、リオーダリングモデルは二次式で表現されます。 例えば、フレーズ対P3とP2とのリオーダリング確率は、 このようにP3の変数x3とP2の変数x2とが1をとるとき有効となるように、 変数2つとリオーダリング確率d32の積で表されます。 P3とP2との 　リオーダリング確率 x3・d32・x2 2019/1/1 言語処理学会 第15回 年次大会

単純な定式化の問題点 目的関数：フレーズ翻訳確率のみを最大化 リオーダリング確率を考慮しない ⇔ リオーダリング確率の使用は一般に性能向上 研究の目的 　　　関連研究 　　提案手法 　　評価実験 　　まとめ 単純な定式化の問題点 [DeNero and Klein 2008] 目的関数：フレーズ翻訳確率のみを最大化 リオーダリング確率を考慮しない 二次式での表現は計算コストが高いため ⇔ リオーダリング確率の使用は一般に性能向上 フレーズ対iとjとのリオーダリング確率 xi・dij・xj (所要時間：40秒) [できれば30秒] 二次式などによる非線形問題は計算コストが高いため、 単純な定式化ではリオーダリングモデルを考慮せず、 目的関数としてフレーズ翻訳確率のみを最大化します。 しかし、リオーダリングモデルの使用は一般に性能向上することが知られています。 そこで本研究では目的関数に一次式としてリオーダリング確率を組み込み可能な、 新しい定式化を提案いたします。 目的関数に一次式としてリオーダリング確率を 組込み可能な新たな定式化を提案 2019/1/1 言語処理学会 第15回 年次大会

フレーズ対応問題の新たな定式化 目的言語側についてグラフ化 変数： 枝(i, j)の使用有無を表す0-1変数 yij y32・d32 1 4 研究の目的 　　　関連研究 　　提案手法 　　評価実験 　　まとめ フレーズ対応問題の新たな定式化 目的言語側についてグラフ化 変数： 枝(i, j)の使用有無を表す0-1変数 yij yijが1 ・・・ 枝(i,j)の両端のフレーズ対iとjが使用される リオーダリング確率は枝に対する重み P3とP2との 　リオーダリング確率 e1 e2 e3 フレーズ対番号 y32・d32 1 4 g s 3 2 リオーダリング確率 (所要時間：1分) 本研究で提案する新しい定式化では、 原言語側の制約条件は単純な定式化と同様とし、 目的言語側についてフレーズ同士の位置関係をグラフ化します。 この例では(中央以下の図全体を指して)、目的言語側に注目するとフレーズ対P3はe1、P2はe2をカバーするため、 それぞれ対応する単語にまたがるノードとしてこのように(ノード3と2を指して)表現できます。 整数計画問題の変数はノード同士を結ぶ有向枝に0－1変数として置きます。 枝に置いた変数が1をとるとき、その両端のフレーズ対がフレーズ対応に含まれることを表します。 この定式化では、リオーダリング確率は有向枝に対する重みとして扱うことができるため(P3、P2の例を指しながら) 、 このように枝変数とリオーダリング確率の積として一次式で表現可能です。 フレーズ対 P3 フレーズ対 P2 P2 P3 f1 e2 e1 f2 f1 f2 f3 f4 f1 f2 f3 f4 e1 e2 e3 e1 e2 e3 2019/1/1 言語処理学会 第15回 年次大会

フレーズ対応が満たす制約条件 フレーズ対応が満たすべき条件 原言語側 f1 f2 f3 f4 目的言語側 1 4 g s 3 2 研究の目的 フレーズ対応が満たす制約条件 　　　関連研究 　　提案手法 　　評価実験 　　まとめ 原言語側 F1 F4 フレーズ対応 f1 f2 f3 f4 F2 F3 F4 F2 F3 F4 f1 f2 f3 f4 f1 f2 f3 f4 集合 f1 f2 f3 f4 フレーズ対応が満たすべき条件 　　　　　　　　　　 ・・・線形整数計画問題として定式化可能 （１）原言語側 ：集合分割問題の解 （２）目的言語側 ：開始ノードsから終端ノードgへのパス 分割 e1 e2 e3 f1 f2 F2 F3 E3 E2 E4 目的言語側 e1 e2 e3 フレーズ対番号 (所要時間：1分) では、提案した定式化において フレーズ対応が満たすべき制約条件について説明します。 このようにフレーズ対応が成立している場合を考えます。 このとき原言語側では、DeNeroらの定式化と同様に集合分割問題の解となっています。 また目的言語側では、開始ノードsから3、2、4を通り、終端ノードgへのパスとなっています。 フレーズ対応が満たすべき条件をまとめるとこのようになります。 これらの条件は線形整数計画問題として定式化可能です。 時間の都合上、詳しい定式化方法は割愛させていただきますので、 興味のある方は論文をご覧下さい。 1 4 g s 3 2 2019/1/1 言語処理学会 第15回 年次大会

フレーズ対応最適化を用いた翻訳候補のリランキング 研究の目的 　　　関連研究 　　提案手法 　　評価実験 　　まとめ フレーズ対応最適化を用いた翻訳候補のリランキング デコーダによりn best翻訳を獲得 フレーズ対応を最適化、確率を再計算 n best翻訳 フレーズ対応最適化後 順位 翻訳候補 確率 順位 翻訳候補 確率 1 it is fine today . 1 it is fine today . 0.21 0.21 それは 今日 晴れ だ 。 それは 今日 晴れ だ 。 2 (所要時間：50秒) それでは、提案したフレーズ対応最適化手法を翻訳に応用する方法を説明します。 本研究では、フレーズ対応最適化を用いて翻訳候補のリランキングを行います。 まずデコーダによりn best翻訳を獲得します。 n bestの中には確率1位の候補よりも 翻訳結果としてよりよい候補が含まれていることが知られています。 しかしデコーダの近似探索のため、 この例のように確率最大でないフレーズ対が適用されている場合、 その候補の確率は不当に低く計算されていることになります。 そこでフレーズ対応最適化により確率を再計算し、 デコーダの順位付けを改善し、 新たに確率値が最も大きくなった候補をシステムの出力とします。 it is fine today . 2 it is fine today . 0.13 0.35 今日 は よい 天気 だ 。 今日 は よい 天気 だ 。 ・・・ ・・・ 2019/1/1 言語処理学会 第15回 年次大会

実験条件 コーパス：NTCIR-7 特許翻訳タスク コーパス(PSD1) 翻訳精度の評価基準：BLEU 翻訳方向：日→英 研究の目的 　　　関連研究 　　提案手法 　　評価実験 　　まとめ 実験条件 コーパス：NTCIR-7 特許翻訳タスク コーパス(PSD1) 学習データ： 180万文ペア テストデータ： 1,371文（フォーマルラン） 翻訳精度の評価基準：BLEU 翻訳方向：日→英 ベースライン：Mosesデコーダ リオーダリングモデル：msd-bidirectional-fe ビーム幅(n best数)：10, 20, 50, 100, 200, 500, 1,000 整数計画問題のSolver： CPLEX 11.0 (所要時間：1分) 以上が提案手法になりまして、ここからは実験についての報告です。 実験条件はこちらのようになっています。 コーパスとしてはNTCIR-7特許翻訳タスクのものを、 翻訳精度の評価基準はBLEUです。 また翻訳方向は日英としました。 ベースラインとしてはMosesデコーダを、 そのリオーダリングモデルはこちらに示したものを使用しました。 またビーム幅はn best数と等価とし、10から1000までこのように変化させました。 整数計画問題のSolverとしてはCPLEX11.0を利用しました。 2019/1/1 言語処理学会 第15回 年次大会

実験結果 ビーム幅とBLEUの関係 有意水準5%で有意差あり Mosesに比べて rerank(提案手法)は 翻訳精度が若干高い 研究の目的 　　　関連研究 　　提案手法 　　評価実験 　　まとめ 実験結果 ビーム幅とBLEUの関係 有意水準5%で有意差あり Mosesに比べて rerank(提案手法)は 翻訳精度が若干高い ビーム幅が大きいとき Mosesとrerankの差は ほとんどなくなる (所要時間：40秒) 実験結果です。 こちらはビーム幅とBLEUの関係を表した図で、 横軸がビーム幅、縦軸がBLEUとなっております。 この図からMosesに比べて、提案手法は翻訳精度が若干高くなっていることが分かります。 しかし、ビーム幅を大きくとると提案手法による精度改善はほとんどなくなってしまいます。 2019/1/1 言語処理学会 第15回 年次大会

実験結果 ビーム幅と平均スコア改善幅の関係 平均スコア（対数尤度）改善幅： 提案手法とベースラインとの探索精度の差を表す指標 研究の目的 　　　関連研究 　　提案手法 　　評価実験 　　まとめ 実験結果 ビーム幅と平均スコア改善幅の関係 平均スコア（対数尤度）改善幅： 提案手法とベースラインとの探索精度の差を表す指標 各翻訳候補のフレーズ対応最適化前後におけるスコアの差の平均 ビーム幅を大きくとるほど、 スコア改善幅が小さくなる ビーム幅を大きくとると Mosesの探索精度がよくなり、 提案手法の効果が小さくなる (所要時間：1分) [場合によっては省略] 先程の実験結果を裏付けるのがこのグラフです。 これはビーム幅と平均スコア改善幅について表したものです。 ここで平均スコア改善幅とは、提案手法とベースラインとの探索精度の差を表す指標であり、 各翻訳最適化前後のフレーズ対応最適化前後におけるスコアの差の平均です。 横軸はビーム幅、縦軸はスコア改善幅です。 ビーム幅を大きくとるほどスコア改善幅が小さくなっています。 これはMosesの探索精度がよくなるためであり、 そのため提案手法はビーム幅が大きいとき、 BLEU改善が小さくなると考えられます。 参考：翻訳候補のスコアの大きさ＝－10～－100 2019/1/1 言語処理学会 第15回 年次大会

まとめ 提案手法 評価実験 フレーズ対応問題の新たな定式化 フレーズ対応最適化による翻訳候補のリランキング 提案手法により翻訳精度が若干改善 研究の目的 まとめ 　　　関連研究 　　提案手法 　　評価実験 　　まとめ 提案手法 フレーズ対応問題の新たな定式化 フレーズ対応についての厳密な確率最大化 リオーダリングモデルの考慮 フレーズ対応最適化による翻訳候補のリランキング 評価実験 提案手法により翻訳精度が若干改善 従来法でもフレーズ対応についての精度は十分 　→ 目的言語文についての探索精度向上が必要 (所要時間：30秒) 本研究では、 フレーズ対応問題の新たな定式化および それを応用した翻訳候補のリランキング手法ついて提案しました。 評価実験の結果、 提案手法により翻訳精度の改善が見られましたが、 その改善は最適解を求めているにもかかわらず小さく、 従来法でもフレーズ対応についての探索精度は十分であると考えられます。 従ってデコーダは目的言語文についての探索精度向上が必要であるといえます。 以上です。ご清聴ありがとうございました。 2019/1/1 言語処理学会 第15回 年次大会

補足：フレーズ対応問題の単純な定式化 の詳細 補足：フレーズ対応問題の単純な定式化 の詳細 目的関数 max Πpkxk 制約条件 Fx = 1 ・・・原言語側単語の被覆条件 Ex = 1 ・・・目的言語側単語の被覆条件 xk ∈ {0,1} (∀k∈K) ・・・各フレーズの使用変数 k∈K フレーズ翻訳確率 2019/1/1 言語処理学会 第15回 年次大会

補足：単純な定式化の制約条件 Fx = 1 ・ ＝ フレーズ対kを使うか？ 使う ：xk=1 原言語側 使わない：xk=0 フレーズ対集合 フレーズ対番号 ・ ＝ 各単語が一度だけ被覆 されることを表す 各フレーズが被覆する単語位置を 1として表す0-1行列 2019/1/1 言語処理学会 第15回 年次大会

補足：フレーズ対応問題の新しい定式化 の詳細 補足：フレーズ対応問題の新しい定式化 　　の詳細 目的関数 max Πpkxk・ Πdeye 制約条件 Fx = b ・・・原言語側が My = b ・・・目的言語側でパスとなっている制約 x = Ny ・・・目的言語側の仮変数yからxを導出 xk ∈ {0,1} (∀k∈K) ・・・各フレーズの使用変数 ye ∈ {0,1} (∀e∈E) ・・・目的言語側の枝変数 k∈K y∈Y フレーズ翻訳確率 リオーダリング確率 2019/1/1 言語処理学会 第15回 年次大会

補足：制約条件My=b 1 g s 4 3 2 e1 e2 e3 フレーズ対番号 1 4 6 2 5 3 枝番号 2019/1/1 言語処理学会 第15回 年次大会

補足：recombine条件による性能差 default：Mosesのデフォルトrecombine条件 recombine+ ：default + リオーダリングスコアの一致条件 2019/1/1 言語処理学会 第15回 年次大会

補足：n bestのスコア近似(Moses) 仮説3から5へ展開した場合の リオーダリングスコアが適用されている 仮説番号 2019/1/1 言語処理学会 第15回 年次大会

補足：ビーム幅と平均スコア改善幅 平均スコア（対数尤度）改善幅： 提案手法とベースラインとの探索精度の差を表す 各翻訳候補の対応最適化前後におけるスコアの差の平均 ビーム幅を大きくとるほど、 スコア改善幅が小さくなる ビーム幅を大きくとると Mosesの探索精度がよくなり、 提案手法の効果が小さくなる (所要時間：1分) [場合によっては省略] 先程の実験結果を裏付けるのがこのグラフです。 これはビーム幅と平均スコア改善幅について表したものです。 ここで平均スコア改善幅とは、提案手法とベースラインとの探索精度の差を表す指標であり、 各翻訳最適化前後のフレーズ対応最適化前後におけるスコアの差の平均です。 横軸はビーム幅、縦軸はスコア改善幅です。 ビーム幅を大きくとるほどスコア改善幅が小さくなっています。 これはMosesの探索精度がよくなるためであり、 そのため提案手法はビーム幅が大きいとき、 BLEU改善が小さくなると考えられます。 参考：翻訳候補のスコアの大きさ＝－10～－100 2019/1/1 言語処理学会 第15回 年次大会

補足：処理時間とBLEUの関係 処理時間 従来法(Moses)・・・翻訳時間そのもの 提案手法・・・・・・・・翻訳時間 + フレーズ対応最適化時間 2019/1/1 言語処理学会 第15回 年次大会

補足：翻訳例 正解例の下線部が Mosesでは分離していたのに対して、 提案手法(rerank)ではリオーダリング スコアも考慮して最適化したことで 結合している 2019/1/1 言語処理学会 第15回 年次大会

補足：翻訳例(詳細) 翻訳結果にリオーダリングスコア最適化効果が見られる (上図：黒下線部) フレーズ対応がよりよくなった?(下図：赤太枠) 2019/1/1 言語処理学会 第15回 年次大会