統計的機械翻訳における フレーズ対応最適化を用いた 翻訳候補のリランキング (所要時間：20秒) 統計的機械翻訳におけるフレーズ対応最適化を用いた翻訳候補のリランキングと題しまして、 システム情報工学研究科２年、越川が発表させていただきます。 システム情報工学研究科　２年 知能情報・生体工学研究室 越川 満 指導教員：山本幹雄

機械翻訳への需要 Web上のテキスト情報 統計的機械翻訳 膨大なデータ量 様々な言語 ・・・ 翻訳手段の一つ：機械翻訳 　・・・ 翻訳手段の一つ：機械翻訳 統計的機械翻訳　　　 確率的翻訳規則を自動学習 近年著しく性能向上 2004-2006年 (所要時間：1分) 現在、Web上には膨大なテキスト情報が存在しています。 そのテキスト情報は、このように様々な言語で書かれており Web上の情報を最大限に利用するには翻訳が必要不可欠です。 しかし、Webページは膨大かつ常に増加しているため、 人手による翻訳は困難です。 そこで機械翻訳が注目されています。 機械翻訳の実現方法のひとつである統計的機械翻訳では、 確率的翻訳規則をシステムが自動学習します。 この手法は近年著しく性能向上し、 従来の人手により翻訳規則を記述するルールベース手法にとって かわる存在として期待されています。 言語別webページ数 童芳, 平手,山名. 2008. 全世界のWebサイトの 言語分布と日本語を含む Webサイトのリンク・地理 的位置の解析, DEWS2008. 2019/4/9 2009年度 CSセミナー

フレーズベース翻訳 翻訳の最小単位：フレーズ フレーズ：連続する1単語以上の単語列 原言語文 f it is rainy today . ① フレーズ単位に分割 it is rainy today . フレーズ対 ② フレーズ毎に翻訳 です 雨 今日 は 。 c2 ③ フレーズの並び替え 　　(リオーダリング) (所要時間：40秒) フレーズベース手法です。 この翻訳手法では、フレーズと呼ばれる連続する１単語以上の単語列を翻訳の最小単位とします。 翻訳システムに原言語文が入力されると、 まず、確率的翻訳規則の集合であるフレーズテーブルの 翻訳対：フレーズ対を用いて、 フレーズ単位に原言語文を分割します。 そして分割されたフレーズごとにテーブルを参照して翻訳すると同時に 目的言語側の文らしくなるようにフレーズの並び替え：リオーダリングを行います。 このときリオーダリング前後の位置関係をフレーズ対応と呼びます。 c1 c3 フレーズ対応 c c4 目的言語文 e 今日 は 雨 です 。 2019/4/9 2009年度 CSセミナー

翻訳に用いる確率的規則 フレーズ翻訳モデル リオーダリング(語順並び替え)モデル 確率(スコア)が付与されている . フレーズ対のテーブル フレーズ翻訳モデル リオーダリング(語順並び替え)モデル 各フレーズ対ペアに対して３値の並べ替えパターン ただし、目的言語側フレーズ同士は隣接 英語 日本語 対訳コーパス it is です it　is 　rainy　today　. 今日は　雨　です 。 対訳文 rainy 雨 . 。 it　is　rainy　. 雨　です　。 共起回数から 推定 対訳関係にあるフレーズの対や フレーズ対同士のリオーダリングには 対訳コーパスで生起した回数をもとに 確率(スコア)が付与されている today 今日 は … … … (所要時間：1分10秒) 次にDeNeroらの定式化のもとでのリオーダリングモデルの表現について説明します。 リオーダリング確率としては目的言語側で隣接するフレーズ対ペアに対して 原言語側での位置関係をこのような3パターンで表現し確率を付与するモデルがよく用いられます。 DeNeroらの単純な定式化では各フレーズ対に対して、 フレーズ対応中で使用されているかを0-1で表現する変数をおきます。 そのため、リオーダリングモデルは二次式で表現されます。 例えば、フレーズ対P3とP2とのリオーダリング確率は、 このようにP3の変数x3とP2の変数x2とが1をとるとき有効となるように、 変数2つとリオーダリング確率d32の積で表されます。 原言語側で分離 原言語側でも同順 原言語側で逆順 it is ～ rainy rainy it is it is rainy 雨 です 雨 です 雨 です 2019/4/9 2009年度 CSセミナー

フレーズベース統計翻訳 翻訳： 入力文fに対し翻訳候補eの確率P(e|f)を最大化 デコーダの問題点 max’: maxの近似解 フレーズ対応cについて厳密な確率最大化でない 各フレーズ対のフレーズ翻訳確率とリオーダリング確率の積で近似 翻訳結果 原言語文 f it is rainy today . フレーズ対応 c 目的言語文 e 今日 は 雨 です 。 原言語文 f デコーダ・・・ヒューリスティック探索 与えられた f に対する翻訳として あらゆる e,c を考慮し、最も確率の 高い候補 e を出力 it is rainy today . max’: maxの近似解 フレーズ対応 c (所要時間：1分半) 統計翻訳では、fが与えられたときのeの確率の最大化を行うことにより翻訳結果^eを決定しますが、 フレーズベースモデルでは同じ翻訳結果eを導くフレーズ対応は様々なパターンが考えられます。 例えば、このような対応関係です。 そこで、この部分(Σc)でフレーズ対応についての総和を求めています。 このΣcは計算コストが非常に高いため、 適切なフレーズ対応に確率が集中すると仮定してmaxcで近似します。 さらに現在用いられているデコーダではヒューリスティック探索を行っており、 この部分(maxe, maxc)は近似解max’として得られます。 このようにデコーダには2段階の近似がなされており、 そのためフレーズ対応cについて厳密な確率最大化がなされていません。 目的言語文 e ＾ 今日 は 雨です 。 2019/4/9 2009年度 CSセミナー

研究の目的 デコーダの探索を厳密化 → 翻訳精度の改善 整数計画法を用いて 翻訳候補に最適なフレーズ対応を付与 → デコーダの探索エラーの低減 　→ 翻訳精度の改善 従来法： 分解 maxcを厳密化 本研究： (所要時間：1分) そこで本研究ではデコーダの探索を厳密化することを目的とします。 具体的には、整数計画法を用いて翻訳候補に最適なフレーズ対応を付与することにより、 デコーダの探索エラーの低減を図ります。 従来法ではmax’だったこの部分をeについてとcについてに分解し、 maxcを厳密化します。 これにより、翻訳精度の改善を目指します。 2019/4/9 2009年度 CSセミナー

フレーズ対応最適化を用いた翻訳候補のリランキング デコーダにより翻訳候補上位n個を獲得 フレーズ対応を最適化、確率を再計算 翻訳候補上位n 個 フレーズ対応最適化後 順位 翻訳候補 確率 順位 翻訳候補 確率 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/4/9 2009年度 CSセミナー

フレーズ対応の最適化 フレーズ対応 フレーズ対応問題 対訳文の各単語を一度ずつ被覆するフレーズ対の組合せ 入力：対訳文および「フレーズ対とその確率」のテーブル 出力：確率最大の(=最適な)フレーズ対応 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/4/9 2009年度 CSセミナー

関連研究：集合分割としてのフレーズ対応問題 [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 原言語側： (所要時間：1分40秒) DeNeroらにより提案された単純な定式化では、 フレーズ対応問題を、原言語側問題と目的言語側問題とを “同時に(すごく強調)” 解く複合問題として考えます。 (すなわち、フレーズ対応問題の解は原言語側の問題の解であると同時に目的言語側でも解となっています。) 原言語側に注目すると、これらのフレーズを部分集合として用いて原言語文の単語集合を一度ずつカバーする問題となります。 これらのフレーズはこの原言語文に適用可能なフレーズ対のテーブルから参照したものであり、 同じ数字の目的言語側フレーズと対応しています。 この例では、原言語側の解候補はF1、F4を用いる場合(上側)とF2、F3、F4を用いる場合(下側)の2通りがあります。 目的言語側についても同様な問題を定義し、解候補としてこれら(上と下の例を指す)が挙げられます。 ここに挙げたように原言語側と目的言語側とで適用したフレーズ同士がフレーズ対をなしている場合(フレーズ同士を結ぶ線を指して)、 これらは(紫色の括り)フレーズ対応問題の解候補となります。 このように解候補が複数存在する場合、 確率の高い方を解として出力します。 e1 e2 f1 f2 f3 f4 E1 E4 目的言語側： e1 e2 e3 集合 e1 e2 e3 E3 E2 E4 目的言語側の集合分割問題 2019/4/9 2009年度 CSセミナー

集合分割問題としての定式化の問題点 整数計画問題の変数： 各フレーズ対kに0-1変数xk フレーズ翻訳確率のみを最大化 リオーダリング確率を考慮しない 二次式での表現は計算コストが高いため ⇔ リオーダリング確率の使用は一般に性能向上 f1 f2 P3とP2との 　リオーダリング確率 e1 e2 x3・d32・x2 フレーズ対 (所要時間：40秒) [できれば30秒] 二次式などによる非線形問題は計算コストが高いため、 単純な定式化ではリオーダリングモデルを考慮せず、 目的関数としてフレーズ翻訳確率のみを最大化します。 しかし、リオーダリングモデルの使用は一般に性能向上することが知られています。 そこで本研究では目的関数に一次式としてリオーダリング確率を組み込み可能な、 新しい定式化を提案いたします。 P3 P2 一次式としてリオーダリング確率を 組込み可能な新たな定式化を提案 2019/4/9 2009年度 CSセミナー

提案手法：フレーズ対応の新たな考え方 フレーズ対応が満たすべき条件 原言語側 f1 f2 f3 f4 目的言語側 1 4 g s 3 2 集合 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/4/9 2009年度 CSセミナー

目的言語側の有向グラフ 変数： 枝(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/4/9 2009年度 CSセミナー

実験条件 コーパス：NTCIR-7 特許翻訳タスク コーパス(PSD1) 翻訳精度の評価基準：BLEU 翻訳方向：日→英 学習データ： 180万文ペア テストデータ： 1,371文（フォーマルラン） 翻訳精度の評価基準：BLEU 人手による正解翻訳例との一致率 100%に近いほど、よい翻訳結果 翻訳方向：日→英 ベースライン：Mosesデコーダ ビーム幅(翻訳候補数)：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/4/9 2009年度 CSセミナー

実験結果 ビーム幅と翻訳精度(BLEU)の関係 有意水準5%で有意差あり ベースラインシステム Mosesに比べて 翻訳精度：高 有意水準5%で有意差あり ベースラインシステム Mosesに比べて rerank(提案手法)は 翻訳精度が若干高い ビーム幅が大きいとき Mosesとrerankの差は ほとんどなくなる (所要時間：40秒) 実験結果です。 こちらはビーム幅とBLEUの関係を表した図で、 横軸がビーム幅、縦軸がBLEUとなっております。 この図からMosesに比べて、提案手法は翻訳精度が若干高くなっていることが分かります。 しかし、ビーム幅を大きくとると提案手法による精度改善はほとんどなくなってしまいます。 ベースラインの探索精度：良 2019/4/9 2009年度 CSセミナー

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

ご清聴ありがとうございました STSG synchronous tree-substitution grammer Shiever 2004 2019/4/9 2009年度 CSセミナー STSG synchronous tree-substitution grammer Shiever 2004

補足：フレーズ対応問題の単純な定式化 の詳細 補足：フレーズ対応問題の単純な定式化 の詳細 目的関数 max Πpkxk 制約条件 Fx = 1 ・・・原言語側単語の被覆条件 Ex = 1 ・・・目的言語側単語の被覆条件 xk ∈ {0,1} (∀k∈K) ・・・各フレーズの使用変数 k∈K フレーズ翻訳確率 2019/4/9 2009年度 CSセミナー

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

補足：フレーズ対応問題の新しい定式化 の詳細 補足：フレーズ対応問題の新しい定式化 　　の詳細 目的関数 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/4/9 2009年度 CSセミナー

補足：制約条件My=b 1 g s 4 3 2 e1 e2 e3 フレーズ対番号 1 4 6 2 5 3 枝番号 2019/4/9 2009年度 CSセミナー

補足：recombine条件による性能差 default：Mosesのデフォルトrecombine条件 recombine+ ：default + リオーダリングスコアの一致条件 2019/4/9 2009年度 CSセミナー

補足：n bestのスコア近似(Moses) 仮説3から5へ展開した場合の リオーダリングスコアが適用されている 仮説番号 2019/4/9 2009年度 CSセミナー

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

補足：処理時間とBLEUの関係 処理時間 従来法(Moses)・・・翻訳時間そのもの 提案手法(rerank)・・・翻訳時間 + フレーズ対応最適化時間 2019/4/9 2009年度 CSセミナー

補足：翻訳例 正解例の下線部が Mosesでは分離していたのに対して、 提案手法(rerank)ではリオーダリング スコアも考慮して最適化したことで 結合している 2019/4/9 2009年度 CSセミナー

補足：翻訳例(詳細) 翻訳結果にリオーダリングスコア最適化効果が見られる (上図：黒下線部) フレーズ対応がよりよくなった?(下図：赤太枠) 2019/4/9 2009年度 CSセミナー