整数計画法を用いたフレーズ対応最適化による翻訳システムの改良 システム情報工学研究科　１年 学籍番号：200820634 氏名：越川 満 指導教員：山本 幹雄

機械翻訳に対する需要 現在、ウェブ上には膨大なテキスト情報が存在 機械翻訳システム 言語別webページ数 様々な言語で表現 統計的機械翻訳 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 機械翻訳に対する需要 現在、ウェブ上には膨大なテキスト情報が存在 様々な言語で表現 翻訳手段の一つ：機械翻訳 機械翻訳システム ルールベース手法 　　 1960年代～ excite翻訳など 性能は頭打ち状態 統計的手法　　　　　　 1990年代～ google翻訳 近年著しく性能向上,　未だルールベースの性能には追いつけず 2004-2006年 言語別webページ数 童芳, 平手,山名. 2008. 全世界のWebサイトの 言語分布と日本語を含む Webサイトのリンク・地理 的位置の解析, DEWS2008.

統計的機械翻訳 対訳コーパスから確率的翻訳規則を自動学習 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 対訳コーパス：同じ意味をもつ異なる言語の文対集合 対訳コーパスから確率的翻訳規則を自動学習 原言語文fが与えられたとき、あらゆる目的言語文の中から翻訳として最も確率の高い目的言語文eを求める 原言語　 ：翻訳元言語　 foreign language 目的言語 ：翻訳先言語 english ＾ 原言語文 f：　it is rainy today . 対訳コーパス it is fine today. 今日は天気がよい。 fig.9 is the flowchart … 図9はフローチャート… ・ 統計的機械翻訳システム 翻訳候補　　　 確率 今日は雨です　 0.45 今日それは雨です。 0.12 　　　・・・　　　　　　　　 ・・・ 確率的 翻訳規則 学習 目的言語文 e：　今日は雨です。 ＾

フレーズベース翻訳 フレーズを翻訳の最小単位とする 原言語文 f it is rainy today . it is rainy today 統計的機械翻訳 フレーズベース翻訳 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ フレーズを翻訳の最小単位とする フレーズ：連続する1単語以上の単語列 原言語文 f it is rainy today . フレーズ単位に分割 フレーズ f2 f3 f1 f4 it is rainy today . 各原言語フレーズを 目的言語側の フレーズに翻訳 です 雨 今日 は 。 c2 c1 c3 歪み c4 フレーズの並び替え 目的言語文 e 今日 は 雨 です 。 e1 e2 e3 e4

フレーズベース翻訳 フレーズを翻訳の最小単位とする 原言語文 f it is rainy today . 統計的機械翻訳 フレーズベース翻訳 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ フレーズを翻訳の最小単位とする フレーズ：連続する1単語以上の単語列 原言語文 f it is rainy today . フレーズ単位に分割 フレーズ f2 f3 f1 フレーズベースモデルでは fに対するeの翻訳確率を 各フレーズごとの翻訳確率の積で近似する f4 it is rainy today . 各原言語フレーズを 目的言語側の フレーズに翻訳 です 雨 今日 は 。 c2 c1 c3 歪み c4 フレーズの並び替え 目的言語文 e 今日 は 雨 です 。 e1 e2 e3 e4

統計的機械翻訳システム it is rainy today . 今日 は 雨 です 。 it is rainy today . 今日 は 雨 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 統計的機械翻訳システム 目的言語文 e 語順変化 c 原言語文 f it is rainy today . 今日 は 雨 です 。 c1 c3 c2 c4 原言語文 f it is rainy today . c1 c3 語順変化 c c4 c2 今日 は 雨 です　。 目的言語文 e 適切なフレーズ対応に確率が集中 → Σcをmaxcで近似 デコーダ(ヒューリスティック探索) 与えられたfに対する翻訳としてあらゆるeを確率で順位付け、最も確率の高いeを出力 ＾ max’: 近似解のmax

統計的機械翻訳 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 研究の目的 デコーダの問題点 ヒューリスティック探索を用いているため、フレーズ区切り・対応について確率が最大化されていない 本研究の目的 各翻訳候補に対してより適切なフレーズ区切り・対応を適用し(maxc)、デコーダの探索エラーを減少させる 　→ 翻訳精度の改善 デコーダ

提案手法 翻訳候補の再順位付け(reranking) 整数計画法を用いたフレーズ対応最適化 統計的機械翻訳 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 提案手法 翻訳候補の再順位付け(reranking) デコーダの順位付けた翻訳候補上位n個についてフレーズ区切り・対応を最適化 整数計画法を用いたフレーズ対応最適化 数理計画法として対訳文の最適なフレーズ対応を求める問題を定式化

翻訳候補のreranking 1 1 2 2 0.35 デコーダの順位付けた翻訳候補上位n個 フレーズ区切り・対応を最適化し、確率を再計算 統計的機械翻訳 翻訳候補のreranking 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ デコーダの順位付けた翻訳候補上位n個 フレーズ区切り・対応を最適化し、確率を再計算 翻訳候補のrerankingを行う 確率最大の候補を翻訳結果として出力 翻訳候補上位n個 フレーズ対応最適化後 順位 翻訳候補 確率 順位 翻訳候補 確率 1 1 it is fine today . it is fine today . 0.21 0.21 今日 それは 晴れ だ。 今日 それは 晴れ だ。 2 2 it is fine today . it is fine today . 0.35 0.13 今日 は よい天気 です 。 今日 は よい天気 です 。 ・・・ ・・・ ・・・ ・・・ ・・・ ・・・

フレーズ対応の最適化 フレーズ対応 フレーズ対応取得問題 対訳文の各単語を一度ずつ被覆するフレーズ対の組合せ 統計的機械翻訳 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ フレーズ対応の最適化 フレーズ対応 対訳文の各単語を一度ずつ被覆するフレーズ対の組合せ フレーズ対応取得問題 対訳文およびフレーズ対とその翻訳確率が与えられたとき、フレーズ区切り・対応の候補の中から、確率最大の候補を求める問題 解を求めるシステム： フレーズアライナ 対訳文：同じ意味をもつ原言語文と目的言語文のペア f1　 f2　 f3　 f4 f1　 f2　 f3　 f4 f1　 f2　 f3　 f4 e1　 e2　 e3 e1　 e2　 e3 e1　 e2　 e3 フレーズ対応が成立 フレーズ対応が不成立

整数計画法を用いた定式化(１) ・ ＝ フレーズ対kを使うか？ 使う ：xk=1 原言語側 使わない：xk=0 フレーズ対集合 統計的機械翻訳 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 整数計画法を用いた定式化(１) フレーズ対集合 フレーズ対kを使うか？ 　 使う 　 ：xk=1 　使わない：xk=0 原言語側 フレーズ対番号 ・ ＝ 各単語が一度だけ被覆 されることを表す 各フレーズが被覆する単語位置を 1として表す0-1行列

フレーズアライナの定式化(１) 目的関数 制約条件 max Σxklog pk Fx = 1 ・・・原言語側単語の被覆条件 統計的機械翻訳 フレーズアライナの定式化(１) 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 関連研究 　John DeNero and Dan Klein, 2008 　“The complexity of phrase alignment 　 problems”, 　Proceedings of ACL08, pp.25-28 目的関数 max Σxklog pk 制約条件 Fx = 1 ・・・原言語側単語の被覆条件 Ex = 1 ・・・目的言語側単語の被覆条件 xk ∈ {0,1} (∀k∈K) ・・・各フレーズ対の使用変数 k∈K

フレーズアライナの定式化(１) 目的関数 制約条件 max Σxklog pk Fx = 1 ・・・原言語側単語の被覆条件 統計的機械翻訳 フレーズアライナの定式化(１) 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 関連研究 　John DeNero and Dan Klein, 2008 　“The complexity of phrase alignment 　 problems”, 　Proceedings of ACL08, pp.25-28 目的関数 max Σxklog pk 制約条件 Fx = 1 ・・・原言語側単語の被覆条件 Ex = 1 ・・・目的言語側単語の被覆条件 xk ∈ {0,1} (∀k∈K) ・・・各フレーズ対の使用変数 k∈K 個々のフレーズ対の使用変数xでは (1次の項として) フレーズ対同士の位置関係(歪み)を表すことができない

整数計画法を用いた定式化(２) 有向グラフ フレーズ対集合 フレーズ対の原言語側についてグラフ化 フレーズ対番号 f1 f2 f3 f4 統計的機械翻訳 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 整数計画法を用いた定式化(２) フレーズ対集合 フレーズ対の原言語側についてグラフ化 有向グラフ フレーズ対番号 f1 f2 f3 f4 1 目的言語側に 　ついても同様 3 5 6 s 4 2 g

フレーズ対応と有向グラフ 原言語側 目的言語側 原言語側グラフと目的言語側グラフの どちらでも開始ノードsから終端ノードgへの 統計的機械翻訳 フレーズ対応と有向グラフ 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 原言語側 フレーズ対番号 フレーズ対応 f1 f2 f3 f4 1 フレーズ対4 フレーズ対6 3 5 6 f1 f2 f3 f4 e1 e2 e3 s 4 2 g 原言語側グラフと目的言語側グラフの どちらでも開始ノードsから終端ノードgへの パスになっている場合がフレーズ対応 フレーズ対5 目的言語側 e1 e2 e3 1 3 4 6 s 5 2 g

有向グラフと語順変化 原言語側 目的言語側 目的言語側で隣接している 統計的機械翻訳 有向グラフと語順変化 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 原言語側 フレーズ対番号 フレーズ対応 f1 f2 f3 f4 1 フレーズ対4 フレーズ対6 3 5 6 f1 f2 f3 f4 e1 e2 e3 s 目的言語側で隣接している フレーズ対ペアに対する歪み(語順変化)確率は目的言語側の枝に割り当てられる （目的言語側で隣接しないフレーズ対ペアは考慮しない） 4 2 g フレーズ対5 目的言語側 e1 e2 e3 1 3 4 6 s 5 2 g

フレーズアライナの定式化(２) 目的関数 制約条件 max Σxklog pk +Σze log de 統計的機械翻訳 フレーズアライナの定式化(２) 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 目的関数 max Σxklog pk +Σze log de 制約条件 My = b ・・・原言語側でパスとなっている制約 x = Ny ・・・原言語側の仮変数yからxを導出 M’z = b’ ・・・目的言語側でパスとなっている制約 x = N’z ・・・目的言語側の仮変数zからxを導出 xk ∈ {0,1} (∀k∈K) ・・・各フレーズの使用変数 ye ∈ {0,1} (∀e∈E) ・・・原言語側の枝変数 ze ∈ {0,1} (∀e∈E) ・・・目的言語側の枝変数 k∈K e∈E 歪み確率を表す項

評価実験 実験条件 ベースライン：Mosesデコーダ 学習データ： 特許対訳文 180万文ペア テストデータ： 899文 統計的機械翻訳 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 評価実験 実験条件 ベースライン：Mosesデコーダ 学習データ： 特許対訳文 180万文ペア 約10年分の特許データ テストデータ： 899文 翻訳精度の評価基準：BLEU 正解例との一致率 100[%]に近いほどよい翻訳 reranking対象：Mosesの翻訳候補上位100個 提案手法(Solver：CPLEX11.0)を用いてrerankingを行う

統計的機械翻訳 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 実験結果 翻訳精度：良 翻訳精度：悪

翻訳例 (確率は改善されたが、BLEUは改善されなかった例) 原言語文： 統計的機械翻訳 翻訳例 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 　 (確率は改善されたが、BLEUは改善されなかった例) 原言語文： 　 the use of a robot for deburring work is a known prior art . 正解文： 　 バリ 取り 作業 に ロボット を 利用 する こと は 従来 より 公知 の 技術 で ある 。 ベースライン： 　 バリ 取り 作業 用 ロボット を 用い て 従来 技術 が 知ら れ て いる 。 提案手法： 　 従来 技術 の バリ 取り 作業 用 の ロボット が 知ら れ て いる 。

まとめと今後の課題 本研究で提案した手法 評価実験 今後の課題 整数計画法を用いたフレーズ対応の最適化 統計的機械翻訳 まとめと今後の課題 　　　研究の目的 　　提案手法 　　評価実験 　　まとめ 本研究で提案した手法 整数計画法を用いたフレーズ対応の最適化 フレーズアライナを用いた翻訳候補のreranking 評価実験 ベースラインの翻訳精度を改善することはできなかった 翻訳候補の確率の最大化とBLEUの向上は等価とは言えない フレーズアライナの確率計算部分に誤りがある可能性 今後の課題 実験結果の検証 定式化1と定式化2の融合によるアライナの高速化