整数計画法を用いたフレーズ対応
最適化による翻訳システムの改良
システム情報工学研究科 １年
学籍番号：200820634
氏名：越川 満
指導教員：山本 幹雄
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
機械翻訳に対する需要

現在、ウェブ上には膨大なテキスト情報
が存在


様々な言語で表現
翻訳手段の一つ：機械翻訳
その他
韓国語
ポルトガル語
イタリア語
ロシア語
英語
スペイン語

機械翻訳システム

ルールベース手法




フランス語
1960年代～
excite翻訳など
性能は頭打ち状態
統計的手法



1990年代～
google翻訳
近年著しく性能向上, 未だルールベースの
性能には追いつけず
中国語
ドイツ語
日本語
2004-2006年
言語別webページ数
童芳, 平手,山名. 2008.
全世界のWebサイトの
言語分布と日本語を含む
Webサイトのリンク・地理
的位置の解析, DEWS2008.
2
統計的機械翻訳
研究の目的
提案手法
統計的機械翻訳
評価実験
まとめ
対訳コーパス：同じ意味をもつ異なる言語の文対集合

対訳コーパスから確率的翻訳規則を自動学習

原言語文fが与えられたとき、あらゆる目的言語文の中か
＾
ら翻訳として最も確率の高い目的言語文eを求める
 原言語
：翻訳元言語 foreign language
 目的言語 ：翻訳先言語 english
原言語文 f： it is rainy today .
対訳コーパス
it is fine today.
今日は天気がよい。
統計的機械翻訳システム
翻訳候補
確率
今日は雨です
0.45
今日それは雨です。 0.12
・・・
・・・
確率的
翻訳規則
＾ 今日は雨です。
目的言語文 e：
学習
fig.9 is the flowchart …
図9はフローチャート…
・
・
・
3
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
フレーズベース翻訳

フレーズを翻訳の最小単位とする
 フレーズ：連続する1単語以上の単語列
原言語文 f
it is
rainy
today
フレーズ単位に分割
f1
各原言語フレーズを
目的言語側の
フレーズに翻訳
フレーズ
f2
f3
it is
rainy
today
.
です
雨
今日 は
。
フレーズの並び替え
目的言語文 e
.
c1
今日 は
e1
c2
歪み
雨
e2
c3
f4
c4
です
。
e3
e4
4
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
フレーズベース翻訳

フレーズを翻訳の最小単位とする
 フレーズ：連続する1単語以上の単語列
原言語文 f
it is
rainy
today
フレーズ単位に分割
f1
フレーズ
f2
it is
.
f3
rainy
today
各原言語フレーズを
フレーズベースモデルでは
目的言語側の
fに対するeの翻訳確率を
フレーズに翻訳
f4
.
です
雨
今日で近似する
は 。
各フレーズごとの翻訳確率の積
フレーズの並び替え
目的言語文 e
c1
今日 は
e1
c2
歪み
雨
e2
c3
c4
です
。
e3
e4
5
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
統計的機械翻訳システム
原言語文 f
it is
語順変化 c
cc1 1
eˆ  arg max  Pe, c f 
c
 arg max max Pe, c f 
e
e
e
e ,c
today
c2
c2
c3
.
c4c4
です 。
今日 はは 雨雨 です
目的言語文 e
e
rainy
適切なフレーズ対応に確率が集中
→ Σcをmaxcで近似
c
 arg max' Pe, c f 
max’: 近似解のmax
デコーダ(ヒューリスティック探索)
与えられたfに対する翻訳としてあらゆ
るeを確率で順位付け、最も確率の高
＾
いeを出力
6
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
研究の目的

デコーダの問題点
 ヒューリスティック探索を用いているため、フレーズ区切り・
対応について確率が最大化されていない
eˆ  arg max ' P e, c f 
e ,c
e
デコーダ

本研究の目的
各翻訳候補に対してより適切なフレーズ区切り・対応
を適用し(maxc)、デコーダの探索エラーを減少させる
→ 翻訳精度の改善
max '  max ' max
e,c
e
c
7
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
提案手法

翻訳候補の再順位付け(reranking)
 デコーダの順位付けた翻訳候補上位n個につい
てフレーズ区切り・対応を最適化
max '  max ' max
e,c

e
c
整数計画法を用いたフレーズ対応最適化
 数理計画法として対訳文の最適なフレーズ対応
を求める問題を定式化
8
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
翻訳候補のreranking
デコーダの順位付けた翻訳候補上位n個
フレーズ区切り・対応を最適化し、確率を再計算
翻訳候補のrerankingを行う
確率最大の候補を翻訳結果として出力
1.
2.
3.
4.
翻訳候補上位n個
順位
1
翻訳候補
フレーズ対応最適化後
確率
順位
1
it is fine today .
翻訳候補
it is fine today .
0.21
今日 それは 晴れ だ。
2
2
it is fine today .
it is fine today .
0.35
今日 は よい天気 です 。
今日 は よい天気 です 。
・
・
・
0.21
今日 それは 晴れ だ。
0.13
・
・
・
確率
・
・
・
・
・
・
・
・
・
・
・
・9
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
フレーズ対応の最適化

フレーズ対応
対訳文：同じ意味をもつ原言語文と目的言語文のペア
 対訳文の各単語を一度ずつ被覆するフレーズ対の組合せ
f 1 f2 f3 f4
f1 f2 f3 f4
f1 f2 f3 f4
e1 e2 e3
e1 e2 e3
e1 e2 e3
フレーズ対応が成立

フレーズ対応が不成立
フレーズ対応取得問題
 対訳文およびフレーズ対とその翻訳確率が与えられたとき、
フレーズ区切り・対応の候補の中から、確率最大の候補を
求める問題
 解を求めるシステム： フレーズアライナ
10
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
整数計画法を用いた定式化(１)
フレーズ対集合
原言語側
フレーズ対kを使うか？
使う
：xk=1
使わない：xk=0
フレーズ対番号
 x1 
 
 x2 
1
0
1
1
0
0


f1 
 x 
f2 1 1 0 0 1 0  3
・  x4 


0 1 0 0 0 1
f3

  
f 4  0 1 0 0 0 1   x5 
x 
各フレーズが被覆する単語位置を
 6
1として表す0-1行列
1 2 3 4 5 6
＝
1
 
1
1
 
1
 
f1
f2
f3
f4
各単語が一度だけ被覆
されることを表す
11
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
フレーズアライナの定式化(１)

目的関数

max Σxklog pk
k∈K

制約条件
関連研究
John DeNero and Dan Klein, 2008
“The complexity of phrase alignment
problems”,
Proceedings of ACL08, pp.25-28
Fx = 1
・・・原言語側単語の被覆条件
 Ex = 1
・・・目的言語側単語の被覆条件
 xk ∈ {0,1} (∀k∈K)
・・・各フレーズ対の使用変数

12
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
フレーズアライナの定式化(１)

目的関数

max Σxklog pk
k∈K
関連研究
John DeNero and Dan Klein, 2008
“The complexity of phrase alignment
problems”,
Proceedings of ACL08, pp.25-28
 個々のフレーズ対の使用変数xでは
制約条件
(1次の項として)
 Fx = 1
・・・原言語側単語の被覆条件
フレーズ対同士の位置関係(歪み)
を表すことができない
Ex = 1
・・・目的言語側単語の被覆条件
 xk ∈ {0,1} (∀k∈K)
・・・各フレーズ対の使用変数

13
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
整数計画法を用いた定式化(２)
フレーズ対集合
フレーズ対の原言語側についてグラフ化
フレーズ対番号
有向グラフ
f1
f2
f3
f4
1
3
s
4
5
目的言語側に
ついても同様
6
2
g
14
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
フレーズ対応と有向グラフ
原言語側
フレーズ対応
フレーズ対番号
f1
フレーズ対6
e1 e2 e3
フレーズ対5
f3
f4
1
フレーズ対4
f1 f2 f3 f4
f2
3
s
5
6
4
2
g
原言語側グラフと目的言語側グラフの
どちらでも開始ノードsから終端ノードgへの
目的言語側
パスになっている場合がフレーズ対応
e1
e2
e3
4
6
1
3
s
5
2
g
15
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
有向グラフと語順変化
原言語側
フレーズ対応
フレーズ対番号
f1
フレーズ対6
3
s
e1 e2 e3
フレーズ対5
f3
f4
1
フレーズ対4
f1 f2 f3 f4
f2
5
6
4
2
目的言語側で隣接している
g
フレーズ対ペアに対する歪み(語順変化)確率は
目的言語側の枝に割り当てられる
（目的言語側で隣接しないフレーズ対ペアは考慮しない）
目的言語側
e1
e2
e3
4
6
1
3
s
5
2
g
16
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
フレーズアライナの定式化(２)

目的関数
 max Σxklog pk +Σze log de
k∈K

e∈E
歪み確率を表す項
制約条件

My = b
 x = Ny
 M’z = b’
 x = N’z



xk ∈ {0,1}
ye ∈ {0,1}
ze ∈ {0,1}
・・・原言語側でパスとなっている制約
・・・原言語側の仮変数yからxを導出
・・・目的言語側でパスとなっている制約
・・・目的言語側の仮変数zからxを導出
(∀k∈K)
(∀e∈E)
(∀e∈E)
・・・各フレーズの使用変数
・・・原言語側の枝変数
・・・目的言語側の枝変数
17
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
評価実験

実験条件
 ベースライン：Mosesデコーダ
 学習データ：

特許対訳文 180万文ペア
約10年分の特許データ
 テストデータ：
899文
 翻訳精度の評価基準：BLEU
正解例との一致率
 100[%]に近いほどよい翻訳

 reranking対象：Mosesの翻訳候補上位100個

提案手法(Solver：CPLEX11.0)を用いてrerankingを行う
18
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
実験結果
翻訳精度：良
翻訳精度：悪
19
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
翻訳例
(確率は改善されたが、BLEUは改善されなかった例)
 原言語文：
the use of a robot for deburring work is a known prior art .
 正解文：
バリ 取り 作業 に ロボット を 利用 する こと は 従来 より 公
知 の 技術 で ある 。
 ベースライン：
バリ 取り 作業 用 ロボット を 用い て 従来 技術 が 知ら れ
て いる 。
 提案手法：
従来 技術 の バリ 取り 作業 用 の ロボット が 知ら れ て い
る。
20
統計的機械翻訳
研究の目的
提案手法
評価実験
まとめ
まとめと今後の課題

本研究で提案した手法
 整数計画法を用いたフレーズ対応の最適化
 フレーズアライナを用いた翻訳候補のreranking

評価実験
 ベースラインの翻訳精度を改善することはできなかった
 翻訳候補の確率の最大化とBLEUの向上は等価とは言えない
 フレーズアライナの確率計算部分に誤りがある可能性

今後の課題
 実験結果の検証
 定式化1と定式化2の融合によるアライナの高速化
21

ベイズ的最適化に基づく能動学習の性能改善 概要 提案手法 : BO-AL

ファイルの意味情報と群知能を用いたファイルシステム

スライド 1

修士第 169号

PowerPoint プレゼンテーション

イラスト著作権保護のための HOGを用いた複製検出

扁形動物プラナリアをモデルにした.. 生殖様式転換機構の解明

ミミズの切断と再生についての実験的研究