統計翻訳における フレーズ対応最適化を利用した 翻訳候補のリランキング ～整数計画法の機械翻訳への応用～ 越川　 満（筑波大学） 内山将夫（情報通信機構） 梅谷俊治（大阪大学） 松井知己（中央大学） 山本幹雄（筑波大学） (所要時間：15秒) 統計的機械翻訳におけるフレーズ対応最適化を利用した翻訳候補のリランキングと題しまして、 筑波大学の越川が発表させていただきます。 SCOPE@つくば 2009

Webページの言語別割合 2002年 2004～2006年 (所要時間：1分) 私の研究分野である統計翻訳はテキスト処理です。 耳慣れない方がほとんどだと思いますので、まず研究の内容に入る前に、 機械翻訳の必要性、統計翻訳の歴史や概要について説明させていただきます。 これはWebページの言語別割合を2002年と2004～6年で比較したものです。 2002年は英語＋日本語で45％を占めていましたが、 こちら(2004～2006)では英日以外が増加し言語の多様化が進んでいます。 Webの情報を最大限に利用するには、 (2004～2006の左半球)このような言語全てを理解しなければならないですが、 さすがにそれは難しいでしょう。 そこで機械翻訳が期待されているわけです。 2002年 2004～2006年 童芳, 平手,山名. 2008.　　全世界のWebサイトの言語分布と日本語を含むWebサイトのリンク・地理的位置の解析, DEWS2008. SCOPE@つくば 2009

（Statistical） Machine Translation 翻訳とは暗号解読だ！ The letter of Warren Weaver to Nobert Wiener, March 4, 1947. When I look at an article in Russian, I say: "This is really written in English, but is has been coded in some strange symbols. I will now proceed to decode." (所要時間：1分) その機械翻訳について最初にその可能性を指摘したのがWeaverです。 彼は、知人であるサイバネティックス創始者Wienerに宛てた 手紙の中でこのようなことを言っています。 「ロシア語は、もともと英語で書かれたものを暗号化したものだ」 「だから暗号解読するんだ」 これが機械翻訳、 特に統計的機械翻訳についての初めてのアイデアです。 ちなみにこのdecodeから、 統計翻訳システムをdecoderと呼ぶようになりました。 （Statistical） Machine Translation （統計的）機械翻訳 （統計翻訳システムのことをdecoderと呼ぶ） SCOPE@つくば 2009

暗号解読ライクな翻訳 頻度を調べれば(＝統計的に) 翻訳が可能！ 翻訳規則の抽出 実際の翻訳 … 共起回数から規則を見出す ドイツ語 翻訳元言語の文（原言語文） Es ist warm heute . 今日 は 暖かい です 。 対訳文 頻度を調べれば(＝統計的に) 翻訳が可能！ Es ist sonnig　heute . Es ist　 warm　.　 暖かい です 。 翻訳規則の適用 Es ist sonnig . 晴れ　です　。 (所要時間：1分) では、Weaverの考え方を用いて翻訳をしてみましょう。 まず、このような同じ意味の文のペアである対訳文の集合での 共起回数から翻訳規則を抽出します。 この例では、この部分(青色)がよく出てきているので、かなり信用できそうです。 また、青が成り立つとすればこのような規則もありそうです。 他にも、これらの規則があるのではないかとあたりをつけます。 これらの規則を、翻訳をするときに入力文(原言語文)に対して適用します。 結果として、このような翻訳先の言語の文(目的言語文)が得られます。 つまり、暗号解読のように頻度から調べた規則で翻訳できるわけです。 これが統計的機械翻訳の基本をなすアイデアです。 翻訳先言語の文（目的言語文） 今日 は　晴れ　です 。 … 対訳データ SCOPE@つくば 2009

統計的機械翻訳の枠組み 対訳データ （数百～数千万 本発表のテーマ 対訳文） 翻訳の(確率)モデル デコーダ おおよそ 整数計画問題に落ちる 　対訳文） 本発表のテーマ おおよそ 　整数計画問題に落ちる 目的言語文 (翻訳候補) デコードの問題 モデル化の問題 翻訳結果 原言語文(入力文) 翻訳の(確率)モデル 文(の組)に対する確率は組合せが多すぎて表にできない 部分的な翻訳規則の組合せ デコーダ fに対してモデルの確率が最大となるeを探索 統計的機械翻訳は数百万という膨大な対訳文から、 確率でスコア付けされた翻訳規則を学習します。 ただし、文同士の組合せが膨大すぎるので、 実際には部分的な翻訳規則を組合わせてこれを計算します。 余談ですが、原言語文のf、目的言語文のeはそれぞれ Foreign LanguageとEnglishに由来します。 目的言語がEnglishなのは、 現在の統計翻訳の枠組みを提案した初めての論文で そう書かれていたためですw こちらはデコーダと呼ばれ、確率的翻訳規則をもとに 入力文fに対する翻訳候補eの中から確率最大の候補^eを探索します。 このように統計翻訳にはモデル化とデコード、2つの問題があります。 特にデコーダは整数計画問題に落とすことができるため、 本発表ではデコーダをテーマとします。 デコーダの話に入る前に翻訳の確率モデルについての説明を先にしたいと思います。 f: 原言語文　Source language e：目的言語　Target language SCOPE@つくば 2009

フレーズ翻訳モデルとフレーズ対応a P(e|f) → P(e,a|f ) ∝ P(e,a, f ) P(e | f) ∝ P(e, f) = ΣP(e,a, f ) a フレーズ 原言語文 f 文頭 But it is rainy today . フレーズ対応 a a3 a0 a1 a5 a2 a4 目的言語文 e 文頭 しかし 今日 は 雨 です 。 Mono. Dis. Swap. P(e,a, f )=P(e) P(a|e) P( f |e,a) 言語モデル： P(e) ≒ P(しかし)×P(今日 | しかし)×P(は | しかし, 今日)×... 　　　× 歪みモデル： P(a|e) ≒P(Mono| しかし)×P(Dis.| 今日は)×P(Swap| 雨)×... 翻訳モデル： P(f |e,a) ≒ P(But|しかし)×P(today|今日 は)×... (所要時間：2分) 現在の統計翻訳では、 フレーズと呼ばれる連続する単語列単位で翻訳する手法が主流となっています。 フレーズベース翻訳では、原言語と目的言語のフレーズ間は このようにその対応関係：フレーズ対応aにより結び付けられています。 つまり、こちらの代わりにこれ (ΣP(e,a,f))を使用します。 この部分(P(e,a,f))は、このような3つの確率モデルに分解され、 それぞれ言語モデル、歪みモデル、翻訳モデルと呼ばれます。 言語モデルは(n-1)重マルコフモデルであり、nとしては5がよく使われます。 歪みモデルは、隣接する目的言語フレーズの原言語側での位置関係を3値で分類し確率を付与します。 例えば、「しかし」と「今日は」は原言語側で離れているのでDiscontinuous(不連続)となります。 また「今日」と「雨」とは原言語側で入れ替わっているものの連続しているのでSwap(交換)となります。 「しかし」がMonotone(同順)なのは、文頭との関係からです。 翻訳モデルは単純に対応している原言語フレーズと目的言語フレーズの翻訳確率です。 言語モデルは単語単位、他の2つのモデルはフレーズ単位の確率の積によって近似されます。 SCOPE@つくば 2009 P(e|f) → P(e,a|f ) ∝ P(e,a, f )

デコーダの近似とフレーズ対応問題 フレーズ対応問題（フレーズ対応最適化） f と e が与えられた状況で、 it is rainy today . 原言語文 f it is rainy today . フレーズ対応 a フレーズ対応 a 目的言語文 e ＾ 今日 は 雨です 。 目的言語文 e 今日 は 雨 です 。 フレーズ対応問題（フレーズ対応最適化） (所要時間：1分30秒) 一方でデコーダにも近似がなされています。 文同士の間にはフレーズ対応aがあると仮定しましたが、 同じ翻訳結果を導くaには数百万以上の組合せがあり、 各翻訳候補に対してこの足しこみを行うのは現実的ではありません。 そこで、尤もらしいフレーズ対応に確率が集中するという仮定のもと、 これ(Σ)をmaxで近似します。 この部分(オレンジ)のことをフレーズ対応問題といい、 対訳文f, eに対して歪み確率と翻訳確率の積を最大化する問題となります。 しかし、現状ではこの式の2つのmaxを同時にかつ ヒューリスティック探索で近似的に求めています。 f と e が与えられた状況で、 P(a|e)P( f |e,a) を最大とする a を求める しかし、現在のデコーダは両方のmaxを同時にかつ近似的に解いている。 さらに SCOPE@つくば 2009

研究の目的 デコーダの探索を厳密化 → 翻訳精度の改善 整数計画法を用いて 翻訳候補に最適なフレーズ対応を付与 → デコーダの探索エラーの低減 　→ 翻訳精度の改善 maxaを厳密化＝フレーズ対応最適化 (所要時間：40秒) そこで本研究ではデコーダの探索を厳密化し、翻訳精度の改善を目指します。 具体的には、整数計画法を用いて翻訳候補に最適なフレーズ対応を付与することにより、 デコーダの探索エラーの低減を図ります。 すなわち、従来法では近似探索がされていたこの部分を厳密に行います。 SCOPE@つくば 2009

フレーズ対応問題 フレーズ対応問題はコスト最小化問題 歪みコストdi 翻訳コストti ～ ～ (所要時間：40分) フレーズ対応問題はデコーダの部分問題であり、 対訳文f, eに対して、歪み確率と翻訳確率でスコア付けを行い最適フレーズ対応aを求める問題です。 これらの確率は各フレーズ対の確率の積で近似され、 負の対数をとればコスト最小問題となります。 ここでこれらを歪みコスト、翻訳コストと呼びます。 なお、oiにはMono, Swap, Discontinuousが入ります。 歪みコストdi 翻訳コストti フレーズ対応問題はコスト最小化問題 SCOPE@つくば 2009

フレーズ対応問題の入出力 入力： 出力： p4 p1 p2 f = f1, f2, f3, f4 e = e1 , e2, e3 p3 フレーズ対 pi　(i=1～K(=4)) フレーズ翻訳コスト　 ti 各フレーズ対間の歪みコスト dij 出力： 全単語を一度ずつ覆うフレーズ対集合(=フレーズ対応)のうち、コスト最小のもの 対訳文 フレーズ対 p4 p1 p2 f =　　　　 　f1, 　　　　f2, 　　　　f3, 　　　　f4 e =　　　　　　e1 ,　　　 　　e2, 　　　　　e3 p3 (所要時間：30秒) フレーズ対応問題とは入力として対訳文f,e およびそれに適用可能なフレーズ対とその翻訳コスト、歪みコストを入力とします。 そして、対訳文の全単語を被覆するフレーズ対集合すなわちフレーズ対応の中から コスト最小の候補を選び出力とします。 SCOPE@つくば 2009

提案手法：フレーズ対応の制約 原言語側 f1 f2 f3 f4 目的言語側 1 4 3 2 g(文末) s(文頭) F1 F4 フレーズ対応 集合 f1 f2 f3 f4 分割 e1 e2 e3 f1 f2 F2 F3 E3 E2 E4 目的言語側 e1 e2 e3 フレーズ対番号 (所要時間：2分) では、提案手法について説明します。 フレーズ対応がこのように成り立っている場合を考えます。 このとき原言語側では、原言語文の単語集合を これらのフレーズを使って集合分割しています。 また目的言語側で各フレーズが対応する単語位置を元にして フレーズ同士の隣接関係をネットワーク状に表すと このように表現することができます。 つまりフレーズ対応は目的言語側では文頭sから文末gへのパスとなります。 目的言語側を原言語側と同じように表現しない理由は、 このようなリオーダリング確率も枝に対する重みとして表せるからです。 歪み 1 P2 P3 f1 e2 e1 f2 4 3 2 g(文末) s(文頭) SCOPE@つくば 2009

フレーズ対応問題の定式化 目的関数 制約条件 min. Σ tk xk + Σ de ye あとはCPLEXに おまかせ Fx = 1 ・・・原言語側の集合分割制約 My = b ・・・目的言語側の流量保存則(s→g) x = Ny ・・・目的言語側の変数yからxを導出 xk ∈ {0,1} (∀k∈K) ・・・フレーズ対の変数 ye ∈ {0,1} (∀e∈E) ・・・目的言語側の枝変数 あとはCPLEXに おまかせ k∈K e∈E (所要時間：1分) 以上より、フレーズ対応問題を定式化するとこのようになります。 変数は各フレーズ対におき、 また補助変数としてyを導入します。 原言語側の制約は集合分割問題そのものであり、 目的言語側の制約はネットワークのパスとなるための流量保存則です。 目的関数は、翻訳コストと歪みコストの最小化です。 実際にフレーズ対応問題を解くのはCPLEXに任せます。 SCOPE@つくば 2009 E：目的言語側 枝集合

フレーズ対応最適化を用いた翻訳候補のリランキング デコーダにより翻訳候補上位n個を獲得 フレーズ対応を最適化、確率を再計算 翻訳候補上位n 個 フレーズ対応最適化後 順位 翻訳候補 確率 順位 翻訳候補 確率 1 it is fine today . 1 it is fine today . 0.21 0.21 それは 今日 晴れ だ 。 それは 今日 晴れ だ 。 2 (所要時間：2分) それでは、提案したフレーズ対応最適化手法を翻訳に応用する方法を説明します。 本研究では、フレーズ対応最適化を用いて翻訳候補のリランキングを行います。 まずデコーダにより翻訳候補上位n個を獲得します。 この中には確率1位の候補よりも 翻訳結果としてよりよい候補が含まれていることが知られています。 しかしデコーダの近似探索のため、 この例のように確率最大でないフレーズ対が適用されている場合、 その候補の確率は不当に低く計算されていることになります。 そこでフレーズ対応最適化により確率を再計算し、 デコーダの順位付けを改善し、 新たに確率値が最も大きくなった候補をシステムの出力とします。 あえて翻訳の過程でフレーズ対応最適化を行わない理由は、 翻訳中に最適化すると目的言語文のあらゆるパターン数兆×フレーズ対応パターン数百万 となってしまうからです。 it is fine today . 2 it is fine today . 0.13 0.35 今日 は よい 天気 だ 。 今日 は よい 天気 だ 。 ・・・ ・・・ SCOPE@つくば 2009

実験条件 データセット：NTCIR-7 特許翻訳タスク コーパス 翻訳精度の評価基準：BLEU 翻訳方向：日→英 学習用対訳データ： 180万文ペア テストデータ： 1,371文（フォーマルラン） 翻訳精度の評価基準：BLEU 正解翻訳例との一致率 = 100%に近いほどよい 翻訳方向：日→英 比較：Mosesデコーダ vs. 提案手法 ビーム幅(翻訳候補数)： 10, 20, 50, 100, 200, 500, 1,000 整数計画問題のSolver： CPLEX 11.0 オープンソースの世界標準 統計翻訳システム (所要時間：1分) 以上が提案手法になりまして、ここからは実験についての報告です。 実験条件はこちらのようになっています。 データセットとしてはNTCIR-7特許翻訳タスクのものを使用しました。 このデータセットの特徴は学習データが180万文ペアと非常に大規模なことです。 翻訳精度の評価基準はBLEUという指標です。 正解との一致率を表す指標で100％に近いほど翻訳精度がよいことを表します。 また翻訳方向は日英としました。 ベースラインとしてはオープンソースのデコーダMosesを、 またビーム幅は翻訳候補数と等価とし、10から1000までこのように変化させました。 整数計画問題のSolverとしてはCPLEX11.0を利用しました。 SCOPE@つくば 2009

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

まとめ 提案手法 評価実験 フレーズ対応問題の新たな定式化 フレーズ対応最適化による翻訳候補のリランキング フレーズ対応についての厳密な確率最大化 リオーダリングモデルの考慮 フレーズ対応最適化による翻訳候補のリランキング 評価実験 フレーズ対応最適化により若干精度向上 ⇔ フレーズ対応についての探索精度は従来法で十分 そもそもデコーダはあまり多くの目的言語文のバリエーションを探索していない (所要時間：1分) まとめです。 何か変！ 本研究では、フレーズ対応最適化を翻訳に応用する手法について検討しました。 最適化を行ったにもかかわらず翻訳精度がのびないという おかしな理由の裏にはデコーダが見ている目的言語文は バリエーションに乏しいということが考えられます。 また、現在のデコーダはヒューリスティック探索をしているにもかかわらず、 翻訳速度が遅いのは私たち人工知能系の探索技術がしょぼいことが原因ではないでしょうか？ そこでみなさんOR系の最適化手法や探索技術を導入することで、 デコーダを劇的に速くすることができるのではないかと思います！ ぜひ、みなさんの技術を統計翻訳に応用してみませんか？ 私自身の今後の展望としましては、 聞きかじったところでは、タブーサーチなどが応用できそうとのことですので、 これから勉強してデコーダに組み入れたいと思います。 SCOPE@つくば 2009

大きな可能性 ～翻訳速度向上～ また、車両が一対の 後輪Ｗｒを備える 。 入力文：The vehicle has also a pair of rear wheels wr . 翻訳精度：高 (所要時間：1分) こちらの図は現在世界中で研究のベースラインとして 用いられているオープンソースのデコーダの翻訳時間と翻訳性能を表す図です。 時間をかければかけるほど、翻訳性能がよくなります。 例えばこの文を翻訳した場合、 最も速く翻訳できるこの点ではこの程度の翻訳で「車両が後輪だけ」ですが、 時間をかければこのようにおおよそ正しく翻訳できます。 ただし、翻訳時間は元の1000倍近くかかってしまします。 さすがに1文に100秒も待ってられないので、 なんとかこのあたりの精度をよくしたいわけです。 また、車両が一対の後輪Ｗｒ。 SCOPE@つくば 2009

大きな可能性 ～翻訳速度向上～ デコーダ本体へのOR系探索技法の導入 → デコーダの劇的な速度向上の可能性！ また、車両が一対の 後輪Ｗｒを備える 。 入力文：The vehicle has also a pair of rear wheels wr . 翻訳精度：高 翻訳時間をかければ翻訳精度改善 　　 ただし、1000倍の時間・・・ 私たち(AI系)の探索技術がしょぼい？ デコーダ本体へのOR系探索技法の導入 → デコーダの劇的な速度向上の可能性！ → 統計翻訳の(一般的な)実用化 タブーサーチ etc… (所要時間：1分) こちらの図は現在世界中で研究のベースラインとして 用いられているオープンソースのデコーダの翻訳時間と翻訳性能を表す図です。 時間をかければかけるほど、翻訳性能がよくなります。 例えばこの文を翻訳した場合、 最も速く翻訳できるこの点ではこの程度の翻訳で「車両が後輪だけ」ですが、 時間をかければこのようにおおよそ正しく翻訳できます。 ただし、翻訳時間は元の1000倍近くかかってしまします。 さすがに1文に100秒も待ってられないので、 なんとかこのあたりの精度をよくしたいわけです。 また、車両が一対の後輪Ｗｒ。 SCOPE@つくば 2009

ご清聴ありがとうございました SCOPE@つくば 2009

P(e | f )の近似 フレーズ対応 a a = 言語モデル 歪みモデル aiとai-1が ・モノトーンoi=M, ・スワップoi=S, f1 f2 f3 f1 f2 f3 f1 f2 f3 e1 e2 e1 e2 a = e1 e2 f1 f2 f3 f1 f2 f3 e1 e2 e1 e2 言語モデル 歪みモデル aiとai-1が 　・モノトーンoi=M, 　・スワップoi=S, 　・その他 oi=D. 翻訳モデル* フレーズ（単語列） SCOPE@つくば 2009 （*フレーズ翻訳モデル）

実行可能解の例 出力：コスト最小のフレーズ対応候補 C可能解２=t1+t4 C可能解１= t2+t3+t4 実行可能解１ 実行可能解２ p4 p4 p2 p3 p1 f =　f1, 　　f2, 　　　f3, 　f4 f =　f1, 　　f2, 　　　f3, 　f4 e = 　e1 ,　 　e2, 　 　 e3 e = 　e1 ,　 　e2, 　 　 e3 C可能解２=t1+t4 + d文頭 1+d14+d4 文末 C可能解１= t2+t3+t4 + d文頭 2+ d23+d34+d4 文末 SCOPE@つくば 2009

単純な定式化の制約条件 Fx = 1 ・ ＝ フレーズ対kを使うか？ 使う ：xk=1 原言語側 使わない：xk=0 フレーズ対集合 フレーズ対番号 ・ ＝ 各単語が一度だけ被覆 されることを表す 各フレーズが被覆する単語位置を 1として表す0-1行列 SCOPE@つくば 2009

目的言語側の有向グラフ 変数： 枝(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 SCOPE@つくば 2009

補足：制約条件My=b 1 g s 4 3 2 e1 e2 e3 フレーズ対番号 1 4 6 2 5 3 枝番号 SCOPE@つくば 2009

処理時間とBLEUの関係 同じ翻訳精度を得るなら Moses(従来法)の方が、 2倍速い Moses(従来法) ・・・翻訳時間そのもの rerank(提案手法) ・・・翻訳時間 + フレーズ対応最適化時間 SCOPE@つくば 2009

補足：翻訳例 正解例の下線部が Mosesでは分離していたのに対して、 提案手法(rerank)ではリオーダリング スコアも考慮して最適化したことで 結合している SCOPE@つくば 2009

補足：翻訳例(詳細) 翻訳結果にリオーダリングスコア最適化効果が見られる (上図：黒下線部) フレーズ対応がよりよくなった?(下図：赤太枠) SCOPE@つくば 2009

まとめ２ 統計的機械翻訳 自然言語処理で現在最もホットな研究テーマ WEBの多言語化により機械翻訳のニーズが高くなっている 自動学習で ルールベースを超える可能性 WEBの多言語化により機械翻訳のニーズが高くなっている Googleが機械翻訳を統計的なものに置き換えた 今のところ最適化の技術はあまり重要視されていない 学習データの問題 モデル化の問題 しかし、上記の問題は解決されつつある デコードの問題ではおそらく最適化技術が主役！ 今がチャンス！ SCOPE@つくば 2009