講義目的と内容• 目的

統計的機械翻訳入門– 実習で用いるシステムの仕組みを理解する• 特にMosesという統計的機械翻訳システムについて理解する

統計的機械翻訳に関する講習会

• 内容
午前

2008.8.28-29

午後

講習会後修正版(2008.9)

1• フレーズペアの抽出

この入門よりもう少し詳しいチュートリアル： Philipp Koehn. Statistical Machine Translation: the basic, the novel, and the speculative.
Tutorial at EACL 2006. http://www.iccs.informatics.ed.ac.uk/~pkoehn/
2

対訳コーパスの例：Hansards• Corpus-based NLP → データ ＋ 人間の知識
経験主義–– 自動翻訳性能評価– チューニング： Minimum Error Rate Training

統計的機械翻訳重視の度合い：• 訓練データの準備• 言語モデルの構築• 翻訳モデル： フレーズ翻訳モデル• フレーズ翻訳モデルの構築と確認• デコーダ： Multistack & Beam-search• Moses設定ファイルの作成
フレーズ翻訳モデルの推定• チューニング• 方向のある単語対応（IBMモデル,GIZA++） • 翻訳実験と評価
講義では省略• 最終課題• 対称化単語対応• 言語モデル： ngramモデル

山本幹雄 筑波大学
Patent Translation Task Group,
Cluster of Focused Domains,
NTCIR (NII Test Collection for IR Systems) Project

午後の実習の流れ– 統計的機械翻訳の概要（カナダの国会議事録）

1980年代から１００万文ペア以上存在

英語

合理主義

フランス語

The 35th Parliament having been
dissolved by proclamation on
Sunday, April 27, 1997, and writs
having been issued and returned,
a new Parliament was summoned tomeet for the dispatch of business on
Monday, September 22, 1997, anddid accordingly meet on that day.

• 経験主義の最も極端な立場： 統計的機械翻訳

大量の言語データ・プレーンテキスト（新聞・WEBなど）
・対訳テキスト（議事録・特許文など）

La trente-cinquième législature ayant été
prorogée et les Chambres dissoutes par
proclamation le dimanche 27 avril 1997,
puis les brefs ayant été émis et rapportés, lesnouvelles Chambres ont été convoquées
pour l'expédition des affaires le lundi 22
septembre 1997 et, en conséquence, se sontréunies le jour dit.

Monday, September 22, 1997. Le lundi 22 septembre 1997.
This being the day on which Parliament
was convoked by proclamation of His
Excellency the Governor General of
Canada for the dispatch of business,andthe members of the House being
assembled:

パラメータの自動推定（数理統計学）
翻訳辞書

Le Parlement ayant été convoqué pouraujourd'hui, par proclamation de Son
Excellence le Gouverneur général du
Canada pour l'expédition des affaires, et lesdéputés étant réunis:

翻訳の（確率）モデル 単語の並び替え
3

対訳コーパスの例： NTCIR-7 （日米特許）

何故、いま統計的機械翻訳なのか？

約180万文ペア

英語• 性能の目覚しい向上（ここ５年）• 性能向上の原因

日本語

The lock flag is outputted to the controller 2 また、このロックフラグは、レジスタ６からコントfrom the register 6. ローラ２に出力される。

– 翻訳モデルの発展• IBMモデル（単語）→フレーズモデル

A plurality of clients are connected to the server. サーバには複数のクライアントが接続する。

– デコーダ等の仕組みが公開

Next, the server application program issues a 次にサーバアプリケーションプログラムはデータ
recv command 2116 by designating a data 受信バッファ２１６１を指定してｒｅｃｖコマンド２１１
receiving buffer 2161. ６を発行する。

• １０年前は職人技• ツールの普及

As shown in FIG. 2, a counter 5 and a flip-flop 6 図２を参照すると、カウンタ５およびフリップフ
generate a pulse having a width proportional ロップ６は、信号処理回路４によって計算された
to the value (Tf) calculated by signal 値(Ｔｆ)に比例した幅を持つパルスを発生するた
processing circuit 4. めのものである。

– 自動評価手法の開発と普及

A gate electrode 61 is formed on the periphery of ゲート電極６１はトレンチ５３内に位置し、ゲート
gate insulating film 63 in trench 53. 絶縁膜６３の周囲に形成されている。

– チューニング手法（＋識別モデル）

The process for translating the input sentence is 入力文を翻訳する過程は、上記した例と同様で
the same as in the above-mentioned example. ある。

– 対訳データの拡充

ACL Best Paper Award
ACL2001: デコーダ
ACL2002: 識別モデルとチューニング
ACL2005: 翻訳モデル– GIZA++, SRILM, Pharaoh, Moses• BLEU• MERT : Minimum Error Rate Training... ...
5

http://www.isi.edu/natural-language/download/hansard/

4

6• Hansards（英仏） → Europarl（11ヶ国語100万文以上並記）• 特許対訳データ（NTCIR-7） : 日英180万文

機械翻訳

モ l. 1
IBM n et aro
（B

（Wu 1997）

ルデル

Inversion Transduction Grammar）
993

Syntax（Yamada&Night 2001）

Phrase&JointProb.
（Marcu&Wong 2002）

Alignment-Template（Och&Ney 2003）

w

ル
・ツー
ーダ EGYPT project
デコ

Phrase（Koehn et al. 2003）（Al-Onaizan et al. 1999）

Hierarchical Phrase（*Chiang 2005）

GIZA++

ISI-rewrite デコーダ
（Och&Ney 2003）（*Germann et al. 2001）

WER
PER
NIST

BLEU

Discriminative
Training

Pharaoh（Koehn et al. 2004）

グ
ニン

7

４０年

ー
チュ

we
The latest releases
In autumn 2007, will meet government leaders
at United Nations Headquarters in New Yorkto find solutions and make recommendations
to protect children in war.
Will these(S)MTのアイデア（Weaver 1947）

自動評価‫أﺣﺪث اﻟﻨﺸﺮات‬‫ ﺳﻴﺠﺘﻤﻊ ﻗﺎدة اﻟﺤﻜﻮﻣﺎت ﻓﻲ ﻣﻘﺮ اﻷﻣﻢ اﻟﻤﺘﺤﺪة ﻓﻲ ﻧﻴﻮﻳﻮرك ﻟﻠﺘﻮﺻّﻞ إﻟﻰ ﺣﻠﻮل‬،2007 ‫ﻓﻲ ﺧﺮﻳﻒ ﻋﺎم‬‫ ﺳﻴﻨﻈﺮ هﺆﻻء اﻟﻘﺎدة ﻓﻴﻤﺎ ﺗﻢ إﺣﺮازﻩ ﻣﻦ ﺗﻘﺪّم ﻣﻨﺬ ﺗﻘﺮﻳﺮ ﻋﺎم‬.‫وﺗﻘﺪﻳﻢ ﺗﻮﺻﻴﺎت ﻟﺤﻤﺎﻳﺔ اﻷﻃﻔﺎل ﻓﻲ اﻟﺤﺮب‬‫ ﻗﺪّم اﻟﺘﻘﺮﻳﺮ ﺗﻮﺻﻴﺎت ﻣﺒﺘﻜﺮة ﺣﻮل ﻣﺎ‬.‫ اﻟﺬي أﻋﺪّﺗﻪ اﻣﺮأة ﻣﻦ اﻟﻤﻮزﻣﺒﻴﻖ اﺳﻤﻬﺎ ﻏﺮاﺳﺎ ﻣﺎﺷﻴﻞ‬1996‫ أﺟﺮى ﻣﻮﻗﻊ أﺻﻮات اﻟﺸﺒﺎب ﻣﺴﺤًﺎ‬،‫ وﻓﻲ ﺳﻌﻴﻪ ﻹﻳﺼﺎل أﺻﻮات اﻟﺸﺒﺎب‬.‫ﻳﻤﻜﻦ – وﻣﺎ ﻳﺠﺐ – اﻟﻘﻴﺎم ﺑﻪ‬‫ﻟﻠﺸﺒﺎب ﻳﺴﺘﻄﻠﻊ ﺁراءهﻢ ﺣﻮل ﻣﺎ ﻳﺠﺐ اﻟﻘﻴﺎم ﺑﻪ ﻻﺣﺘﺮام ﺣﻘﻮق اﻷﻃﻔﺎل اﻟﻤﺘﺄﺛﺮﻳﻦ ﺑﺎﻟﻨﺰاع اﻟﻤﺴﻠّﺢ‬‫ ﻓﻲ اﻟﺘﻘﺮﻳﺮ‬- ‫ ﻣﻦ ﺧﻼل اﻟﻤﺴﺢ واﻟﻤﺠﻤﻮﻋﺎت اﻟﺒﺆرﻳﺔ‬- ‫ وﺳﻴﺘﻢ إدراج إﺟﺎﺑﺎت اﻟﺸﺒﺎب‬.‫وﺣﻤﺎﻳﺘﻬﺎ وﺗﻠﺒﻴﺘﻬﺎ‬‫ وﺗﻘﺪّم اﻟﻨﺸﺮة اﻹﺧﺒﺎرﻳﺔ ﻟﻬﺬا اﻟﺸﻬﺮ‬.‫اﻟﺬي ﺳﻴﻜﻮن وﺛﻴﻘﺔ رﺋﻴﺴﻴﺔ ﻓﻲ اﻟﻨﻘﺎﺷﺎت اﻟﻘﺎدﻣﺔ ﻓﻲ اﻷﻣﻢ اﻟﻤﺘﺤﺪة‬‫ وﺗﻮﺻﻴﺎﺗﻬﻢ ﻟﻘﺎدة‬،‫ وآﻴﻔﻴﺔ اﻟﺘﺄﻗﻠﻢ ﻣﻌﻬﺎ‬،‫ﻟﻤﺤﺔ أوﻟﻰ ﺣﻮل رأي اﻟﺸﺒﺎب ﻓﻲ أﺳﺒﺎب اﻟﺤﺮب وﺗﺒﻌﺎﺗﻬﺎ‬‫اﻟﺤﻜﻮﻣﺎت‬.

ユニセフのあるページ

統計的機械翻訳の発展

アラビア⇔英語
2006.5よりサービス開始

翻訳モデ（NIST 2006 MT Evaluationで１位）

Hiero（Papineni
et al. 2002）（Chiang 2007）（*Och&Ney 2002）

Moses

MERT
（Och 2003）（Koehn et al. 2006）

8*=ACL Best Paper Award

参考文献* = ACL Best Paper Award
Brown, P.F. et al. 1993. The mathematics of statistical machine translation: parameter estimation.
Computational Linguistics 19(2):263-311.
*Chiang, D. 2007. Hierarchical phrase-based traslation. Computational Linguistics 33(2):201-228.
*Germann, U. et al. 2001. Fast decoding and optimal decoding for machine translation. In Proc. of ACL 2001.
Koehn, P. et al. 2003. Statistical phrase-based translation. In Proc. of HLT-NAACL 2003.
Koehn, P. et al. 2007. Moses: open source toolkit for statistical machine translation. In Proc. of ACL 2007.
Marcu, D. and W. Wong. 2002. A phrase-based, joint probability model for statistical machine translation. In
Proc. of EMNLP-2002.
Och, F.J. and H. Ney. 2003. A systematic comparison of various statistical alignment models. Computational
Linguistics 29(1):19-51.
Och, F.J. 2003. Minimum error rate training in statistical machine translation. In Proc. of ACL 2003.
*Och, F.J. and H. Ney. 2002. Discriminative training and maximum entropy models for statistical machinetranslation. In Proc. of ACL 2002.
Papineni, K, et al. 2002. Bleu: a method for automatic evaluation of machine translation. In Proc. of ACL
2002.
Weaver, W. 1947. The letter of W. Weaver appears in his paper "Translation" which was published in thebook of "Machine Translation of Languages: Fourteen Essays" edited by W.N. Locke and A.D. Booth,
1955. (Also the paper is reprinted in "Readings in Machine Translation" edited by S Nirenburg et al.,2003.)Wu, D. 1997. Stochastic inversion transduciton grammars and bilingual parsing of parallel corpora.
Computational Linguistics 23(3):377-404.
Yamada, K., and K. Knight. 2001. A syntax-based statistical translation model. In Proc. of ACL 2001.
9

統計的機械翻訳の概要•言語モデル： ngramモデル•翻訳モデル： フレーズ翻訳モデル•デコーダ： Multistack & Beam-search

10

基本モデル： Noisy Channel Modeleˆ = arg max P (e | f )e

P ( f | e ) P (e )eP( f )= arg max P ( f | e ) P(e )= arg max
e

デコーダ

翻訳モデル

（原言語に対して （意味的等価性の意味的に等価で モデル）
流暢な目的言語を探す）
11

確率論の復習• P(a)： 確率

f: 原言語文
Source language（foreign language
or French）
e：目的言語
Target language（English）– aという事象が起きる確率– 例： P(曇り) = 1/3• P(a, b): 同時確率
– aとbという事象が同時に起きる確率– 例： P(今日曇り, 明日曇り) = 1/6• P(a | b): 条件付確率

言語モデル– bという事象が起こった状況で、aという事象が起きる確率– 例： P(明日曇り | 今日曇り) = 1/2– 定理（定義）： P(a | b) = P(a, b)/ P(b) = P(b | a) P(a) / P(b)（（目的）言語らしさのモデル）

f = f1m = f1 , f 2 ,..., f me = e1l = e1 , e2 ,..., el• P(a) = ΣP(a, b) : 周辺確率b12

ベイズの定理デコーダ： 翻訳システム本体

２つのモデル英日方向

f = He ate soup with a spoon.

f e

e1 = ヘリウム食べたスープとスプーン
e2 = 彼は食べたスープでスプーン
e3 = ヘリウム飲んだスプーンとスープ

e: 翻訳候補
デコーダ

eˆ = arg max P ( f | e ) P (e )e

彼はスプーンでスープを飲んだ …

e28459 = ヘリウムはスプーンでスープを飲んだ
e28460 = 彼はスプーンでスープを飲んだ
e28461 = ...
2020×20!
...

位置

...

確からしさ

ヘリウム スープ スプーン
彼 食べた
と
…
は飲んだ を で
ヘリウムはスプーンでスープを飲んだ…
がにヘリウム食べたスープとスプーン
彼は飲んだスープでスプーン

言語モデル

翻訳モデル

翻訳候補数 = M | f | × | f |!
e＾ =彼はスプーンでスープを飲んだ

P(e)P( f |e)典
型例f = He ate soup with a spoon.

単語ごとの翻訳候補数 f の文長「同じ意味で かつ 日本語らしい」

13

14

以降のスライド• 午前– 統計的機械翻訳の概要• 言語モデル• 翻訳モデル• デコーダ全体概要

統計的機械翻訳の概要•言語モデル： ngramモデル•翻訳モデル： フレーズ翻訳モデル•デコーダ： Multistack & Beam-search• 午後– フレーズ翻訳モデルの推定

モデル推定• 方向のある単語対応（IBMモデル＆GIZA++）• 対称化単語対応• フレーズペア抽出

講義では省略– 評価指標（BLEU）– Minimum Error Rate Training （MERT）

その他

15

16

ngramモデル

ngramモデルのパワー• ngramモデル ＝ n-1重マルコフモデル

スライドに文字化け• Bag translationP(e ) = P(e1 , e2 ,..., eN )– 文の単語（文字）を乱数ででたらめに入れ換える– ngramモデルで元に戻す= P(e1 ) P(e2 | e1 ) P (e3 | e1 , e2 ) L P(eN | e1 , e2 ,..., eN −1 )• 最も高い確率を与える並びを出力とする

N= ∏ P(ei | e1 , e2 ,..., ei −1 )
i =1

• 例：

n-1個前までの単語にのみ依存するとする

N≈ ∏ P(ei | ei − n +1 , ei − n + 2 ,..., ei −1 )i =1

N

例： Bigram = 2gram : P(e ) ≈ ∏ P (ei | ei −1 )– 「彼はスプーンでスープを飲んだ。」

n=1 : Unigramモデル
n=2 : Bigramモデル
n=3 : Trigramモデル– 「飲んだ, 。, を, は, スープ, 彼, スプーン,」

i =1

P(e = “I think so”) ≈ P(I | w0)×P(think | I) × P(so | think)
文頭単語

7億回

10万回

– 「彼はスプーンでスープを飲んだ。」？？

Googleヒット数

P(e= “My think so”) ≈ P(My | w0)×P(think | My) × P(so | think)
17

18

Bag translationの実験結果 1/2

Bag translationの実験結果 2/2• 使用モデル

入力例：
を, て, その, 、 , た, うかがっ, 。, い, 絶対, で, チャンス, 斉藤, は, の, 自信– 単語Trigram (Back-off Smoothing)– 訓練データ：毎日新聞5年分
最尤推定の改良• 完全に正しい復元 （14～15単語の文で６０％強）– 元の文：斉藤 は 絶対 の 自信 で 、 その チャンス を うかがっ て い た 。
– 復元文： 同上

100

正解率

• おしい！

80– 元の文：その後 結婚 し た 妻 や ２ 人 の 子ども も 失っ た 。
– 復元文：その後 結婚 し た ２ 人 の 妻 や 子ども も 失っ た 。

6040• 誤った復元– 元の文：更新 に は 警視庁 の 担当 者 が 皇居 に 出張 し て くる 。
– 復元文：警視庁 の 担当 者 に は 更新 が 皇居 に 出張 し て くる 。

20
0
6～7

19

8～9

10～11

12～13

14～15

単語数

20

言語モデルの研究は終わっている？

言語モデルの性能は重要• 言語モデルの性能 ＝ Perplexity（小さいほどよい）• 翻訳システムの性能 ＝ BLEU（大きいほどよい）• ngramモデルの推定– 問題： データのスパースネス• trigramモデル＆語彙１０万単語 → 100,0003=1[Peta]

英日特許翻訳, フレーズ翻訳モデル＝180万文ペア（NTCIR7）, Reorderingモデルなし– 最尤推定の改良• 工学的な手法としてはほぼ確立している– back-off smoothing や Interpolation• 研究– 音声認識の言語モデル• 約１０年ほど前に研究は下火– 言語モデルの性能改善が音声認識率の改善に結びつかない– SMTの場合

ngramの次数• 言語モデルの性能改善は音声認識よりもはるかに翻訳性能の改善に効果がある（？）
21（学習データ量＝180万文固定）

22

言語モデルの訓練データ量（ngramは5gramに固定）

PerplexityとBLEUはきれいに反比例する

Google ngram
T.Brants et al. 2007. Large language models in machine translation. EMNLP-CoNLL2007. より・アラビア語→英語方向（言語モデルは英語）

・5-gramモデル

統計的機械翻訳の概要•言語モデル： ngramモデル•翻訳モデル： フレーズ翻訳モデル•デコーダ： Multistack & Beam-search
P.Koehn, F.Och and D. Marcu. 2003. Statistical phrase-based translation, NAACL-2003, pp.48-54.
D. Marcu and W.Wong. 2002. A phrase-based, joint probability model for SMT, EMNLP-2002, pp.133-139.

をベースに厳密かつ分かりやすく（?）改変

ベースシステム：
NIST 2006 Machine Translation Evaluationで１位だったGoogleのシステム
23• Phrase Alignment（アラインメント or 対応）• フレーズ翻訳モデル• 歪モデル24

小さい単位への分解

Alignment 1/3• フレーズの翻訳確率 t ( f | e ) が与えられていて、• P( f | e) : e が f に翻訳される確率t(the remains | それ以外は) = 0.08, t(the same as in | と同様) = 0.3, ...

f = the remains are the same as in fig. 12.
e = それ以外は図１２と同様である。

• かつ、あるフレーズ対応a（Alignment）が与えられれば、

f = the remains are the same as in fig. 12P( f |e) ??

a• 文や単語のように順序関係がない離散確率変数に対する確率分布は表で与えるしか方法がない• 文（の組）は、表にするには多すぎる

e =それ以外は 図１２ と同様 である「単語または単語列の対訳対の翻訳確率」を組み合わせるP( f |e,a) ≒ P(the remains|それ以外は)P(are|である)
P(the same as in|と同様)P(fig. 12|図12)「フレーズ」と呼ぶ
25

26

Alignment 2/3

Alignment 3/3• Alignment a の表現• P( f |e,a) からP( f |e)はどうやって求める？

e = e1m = 4 =

a

a

m

P( f | e , a = a1m ) ≈ ∏ P ( fi | eai )i =1

f = the remains are the same as in fig. 12

e1
e2
e3
e4
それ以外は 図１２ と同様 である

a1

a = a1m = a1 , a2 ,..., am と表現し、 aj は f j ↔ ea を意味する。

a2

上記の例： a = a : a1=1, a2=4, a3=3, a4=2

e =それ以外は 図１２ と同様 である

f 2 ↔ ea2 = 4

a3

と書ける

e =それ以外は 図１２と 同様である

…

28

…

i =1

27

P(f, a2|e)

合計がP(f |e)P(f, a3|e)…

P ( f | e, a = a ) ≈ ∏ P( f i | eai )P(f, a1|e)

f = the remains are the same as in fig. 12mm1

e =それ以外は 図１２ と同様 である
f = the remains are the same as in fig. 12

j

4
1

前ページは

reorderingモデル

P ( f | e ) = ∑ P ( f , a | e ) = ∑ P ( f | e, a ) P (a | e )the remains are the same as in fig. 12
f = f1m = 4 =
f1
f2
f3
f4

MosesのReorderingモデル
P ( f | e ) = ∑ P ( f , a | e ) = ∑ P ( f | e , a ) P (a | e )aamf = the remains are the same as in fig. 12

P(a | e ) = ∏ P(ai | e, a1i −1 )統計的機械翻訳の概要

i =1

m

e =それ以外は 図１２ と同様 である
a1=1
a4=2 a3=3 a2=4(m)(d) (s)(s)（a0= 0と考える）

i =1•言語モデル： ngramモデル•翻訳モデル： フレーズ翻訳モデル•デコーダ： Multistack & Beam-searchm≈ ∏ P (orientation | eai )i =1orientation =実習のときのオプション＝ msd-bidirectional-fe≈ ∏ P (ai | eai , ai −1 )monotone(m) ,ifswap(s) ,if

Pharaoh, Moses（フレーズベースの代表的decoder）

discontinuous(d), otherwise.
lexicalised msd モデル

C.Tillman. 2004. A Unigram Orientation Model for Statistical Machine Translation. HLT-NAACL2004.
29 P.Koehn et al. 2005. Edinburgh System Description for the 2005 IWSLT Speech Translation Evaluation. IWSLT2005.

30

デコーダ： 翻訳システム本体

２つの近似eˆ = arg max P ( f | e ) P(e )f = He ate soup with a spoon.
デコーダ

ae28459 = ヘリウムはスプーンでスープをe

飲んだ∑ P ( f | e , a ) P (a | e )(1) aに対する近似

e28460 = 彼はスプーンでスープを飲んだ
e28461 = ...
1020×20!

a...

P( f | e ) = ∑ P( f | e , a ) P(a | e ) ≈ max P( f | e, a ) P (a | e )
a

典
型
例

a

eˆ ≈ arg max P ( f | e, a ) P(a | e ) P (e )e＾ =彼はスプーンでスープを飲んだ

翻訳候補数 = M | f | × | f |!

なんらかの近似解法が必要

単語ごとの翻訳候補数 f の文長

e

31

e ,a

(2) e,aに対する近似
全探索をあきらめる

AIにおける探索問題

32

フレーズ・ラティス （オプション）

デコーダの技英日翻訳：（原言語=英語, 目的言語=日本語）• 職人技– １０年くらい前までは、文献はIBMの特許だけ– 今はかなり公開されているが、ノウハウの部分もいまだ多い• 基本技– 整数計画法
単語ベース– 局所探索– 動的計画法:DP
フレーズベース– Ａ*探索– Beam-search（or/& Multistack）
階層フレーズベース– ＣＫＹパージング– キュービック・プルーニング
フレーズベースモデルの主流（?）
・Multistack & Beam-search

33

f：

He

デコーダの選択肢：

f：

He

ate

ヘリウム

・フレーズの選択
・訳語の位置

彼は

彼は

系統的な全翻訳候補の列挙
・システマティックな選択肢の選択
左から右

食べた

e：

cake

を食べた

ケーキ

.
。

ケーキ

食べた

食べた

は

デコーダの選択肢：・フレーズの選択
・訳語の位置
系統的に全翻訳候補を列挙する方法は？

フレーズ翻訳モデル

He ⇔ ヘリウムHe ⇔ 彼は
He ate ⇔ 食べたate ⇔ 食べた
ate a ⇔ を食べた
...

0.01
0.08
0.02
0.21
0.17

<e,a>
34

cake

.

を食べた

ケーキ

。

• 探索木
Left-to-right展開：
・まったく翻訳されていない仮説からスタート
・まだ翻訳されていないf側フレーズを選択
・翻訳フレーズを仮説のe部分の右端に接続（言語モデルの計算をするため）・仮説の部分翻訳確率を計算する

ケーキ
は

スタート

f: He ate a cake .
e:
確率： 1.0...

アルゴリズム１（直感的）：（1）フレーズを左から順に選択 。。。 いろいろあってダメ
アルゴリズム２（主流）（Left-to-right展開）：（1）訳語の位置を左から順に選択（2）その位置に入れるフレーズを選択

a

デコーダの問題 ＝ AIの探索問題
a

食べた

ate

ヘリウム

系統的な翻訳候補の列挙

35∑ P ( f | e , a ) P (a | e )

膨大

...

eˆ = arg max P( f | e ) P(e )膨大ee1 = ヘリウム食べたスープとスプーン
e2 = 彼は食べたスープでスプーン
e3 = ヘリウム飲んだスプーンとスープ

f : He ate a cake .
e: ケーキ
確率： 0.069
36

f : He ate a cake .
e: 彼は
確率： 0.08
f : He ate a cake .
e: 食べた確率： 0.007
f : He ate a cake .
e: ケーキ
確率： 0.07

仮説：
f: すでに翻訳した部分
e: 翻訳候補（先頭から途中まで）
確率： 翻訳した部分の確率 f(h)f : He ate a cake .
e: 彼は 食べた
確率: 0.00076
f : He ate a cake .
e: 彼は ケーキ
確率： 0.0031
f : He ate a cake .
e: 彼は ケーキ
確率： 0.0029

基本探索手法

Best-first search• 知識なし探索手法： Depth-first, Breadth-first• 知識あり探索手法： Best-first

Stack decoderと呼ばれることもある

f: すでに翻訳した部分• 仮説： e: 翻訳候補（先頭から途中まで）
確率： 翻訳した部分の確率 f(h)Best-first• 探索：
Breadth-first

f: He ate a cake .
e:
確率： 1.0

Depth-firstf : He ate a cake .
e: ケーキ
確率： 0.069
37

f : He ate a cake .
e: 彼は 食べた
確率: 0.00076

f : He ate a cake . ②
e: 彼は
確率： 0.08①

f : He ate a cake .
e: 彼は ケーキ
確率： 0.0031

f : He ate a cake .
e: 食べた確率： 0.007

f : He ate a cake .
e: 彼は ケーキ
確率： 0.0029

f : He ate a cake .
e: ケーキ③
確率： 0.07

38

Future cost•

Best-first + Future cost
動的計画法（DP or Viterbi）で高速計算できる• Future costの例（Moses）

f(h)の問題– 未翻訳部分のフレーズ翻訳確率– 言語モデルはフレーズ内部のみ– reorderingモデルは無視– f(h)は部分翻訳確率の*積*なので、翻訳が進むほどf(h)が小さくなる– 全体で見たとき、翻訳が進んだ仮説は展開されない傾向にある①
f : He ate a cake .
e:
確率： 1.0– Breadth-first searchになってしまう

f : He ate a cake .
e: 彼は 食べた
確率: 0.00076×0.1=0.000076②

f : He ate a cake .
e: 彼は ケーキ
確率： 0.0031×0.25=0.00078

f : He ate a cake .
e: 食べた確率： 0.007×0.02=0.00014
f : He ate a cake .
e: ケーキ
確率： 0.07×0.01=0.0007

評価値を翻訳された部分の長さに依存しないようにする
未翻訳部分の翻訳コスト（確率）を推測して加える（積）Future cost = g(h)f : He ate a cake .
e: 彼は ケーキ
確率： 0.0029×0.3=0.00087

f : He ate a cake .
e: ケーキ
確率： 0.069×0.01=0.00069

g(h)がある条件を満たせば A* search になる
39

f : He ate a cake .
e: 彼は
g(h)
確率： 0.08×0.01=0.0008

未翻訳部分の確率を最大とする組合せ

40

Beam-searchMultistack & Beam-search• Best-first searchの問題• 枝刈りつきBest-first serarch の問題– すべての展開仮説を保持するのは困難– Future cost が真のcostより小さめの場合• 翻訳が進んでいない仮説を切りすぎる– 枝刈り– Future cost が真のcostより大きめの場合：（a）全体で、上位b個（beam幅と呼ばれる）しか仮説を保持しない（b）仮説の展開毎に、〃①
f : He ate a cake .
e:
確率： 1.0

f : He ate a cake .
e: ケーキ
確率： 0.00069

41

f : He ate a cake .
e: 彼は
確率： 0.0008
f : He ate a cake .
e: 食べた確率： 0.00014

f: He ate a cake .
e: ケーキ
確率： 0.0007②• 翻訳が進んだ仮説を切りすぎる

f : He ate a cake .
e: 彼は 食べた
確率: 0.000076

結局、未翻訳部分の長さが異なる仮説の優劣を比較すること自体に無理がある

f : He ate a cake .
e: 彼は ケーキ
確率： 0.00078

未翻訳部分の長さごとに分けて枝刈りを行う

f : He ate a cake .
e: 彼は ケーキ
確率： 0.00087

例えば、全体で上位３個しか保持しない場合（a）.

Multistack & Beam-search
42

現在の主流

Multistack & Beam-search 例１

Multistack & Beam-search 例２b=2とした場合

f: He ate a cake .
e:
確率： 1.0

f : He ate a cake .
e: 彼は
確率： 0.08
f : He ate a cake .
e: ケーキ
確率： 0.069

Sort & Pruningf : He ate a cake .
e: 彼は 食べた
確率: 0.00076

Sort & Pruningf : He ate a cake .
e: 彼は ケーキ
確率： 0.0029
Sort & Pruningf : He ate a cake .
e: 食べた確率： 0.07

f : He ate a cake .
e : ケーキ
確率： 0.002

f : He ate a cake .
e : 彼は ケーキ
確率： 0.0031

翻訳単語＝１

翻訳単語＝２

翻訳単語＝３

彼はケーキを食べた。

...

43

He ate a cake .

翻訳部分の長さ毎に異なるスタックを持つ

44... 最後にここの一番上の仮説をとる

フレーズ翻訳モデル推定の手順• 手順（１）方向のある単語対応• GIZA++（Och&Ney 2003）

フレーズ翻訳モデルの推定– P( f | e)に対してIBMモデルを推定しながら、– 対訳データの各ペアに対して、IBMモデルによる最尤の単語alignment（ aˆ = arg max P ( f , a | e ) ）を計算する。
a• 逆方向P(e | f )に対しても同じことをする• フレーズ翻訳モデル推定の手順（２）対称化単語対応： Symmetricalized word alignment• ヒューリスティックス• 方向のある単語対応• 対称化単語対応• フレーズペア抽出– 各ペアに対して、両方向の単語alignmentを用いて対称単語対応を得る– 例えば： Grow-diag-final-and（Koehn et al. 2005）（３）フレーズ抽出• 一貫した対訳フレーズ < f , e > を抽出する• フレーズ翻訳確率 t ( f | e ) を計算する

46

45

フレーズ翻訳モデル推定の手順： 例（１）方向のある単語対応：P(f=日|e=英)（１）方向のある単語対応：P(f=英|e=日)

それ 以外 は 図 １２ と 同様 で ある

e0 それ 以外 は 図 １２ と 同様 で ある

e0 the remains are the same as in fig. 12

the remains are the same as in fig. 12

フレーズ翻訳モデルの推定

それ 以外 は 図 １２ と 同様 で ある
（２）対称化単語対応

the remains are the same as in fig. 12（３）フレーズ抽出• フレーズ翻訳モデル推定の手順

積： のみ
和： と
その他

• 方向のある単語対応（IBMモデル&GIZA++）• 対称化単語対応• フレーズペア抽出

それ 以外 は 図 １２ と 同様 で ある
the remains are the same as in fig. 12

4748

翻訳モデル：P( f | e)

Alignment 1/4• IBMモデル （単語に基づく翻訳モデル）• P( f | e) : e が f に翻訳される確率– P.F.Brown et. al. 1993. The mathematics of statistical machinetranslation: Parameter estimation. Computational Linguistics,
19(2), pages 263-311.
（ http://acl.ldc.upenn.edu/J/J93/J93-2003.pdf ）f = CE NE EST PAS CLAIR
e = It is not clear– Model １ ～ ５P( f |e) ??

• P( f | e)の近似方法の違い• だんだん精巧なモデルとなる• 文や単語のように順序関係がない離散確率変数に対する確率分布は表で与えるしか方法がない• 文（の組）は、表にするには多すぎる– パラメータ推定• データ： 文対応の対訳コーパス• 推定手法: 最尤推定（EMアルゴリズム）「単語対の翻訳確率」を組み合わせる
49

50

Alignment 2/4

Alignment 3/4• IBM model におけるAlignmentの条件• 単語の翻訳確率 t( f | e) が与えられていて、（f と eは単語）– f 側の各単語はe側に対応する単語をそれぞれ１つもつt(CE | it) = 0.8, t(NE | it) = 0.00001, ...

• e側の各単語は f 側の0～m単語に対応する可能性がある• かつ、ある単語対応a（Alignment）が与えられれば、– e側には空単語e0が存在すると仮定する• f 側のある単語に対応するe側単語がない場合は、e0に対応させる

f = CE NE EST PAS CLAIRa

CE NE EST PAS CLAIR

e = It is not

a1

clear

e0 It is not

CE NE EST PAS CLAIR

P( f |e,a) ≒ P(CE|it)P(NE|not)P(EST|is)P(PAS|not)P(CLAIR|clear)a2

e0 It is not• P( f |e,a) からP( f |e)はどうやって求める？
P ( f | e ) = ∑ P ( f , a | e ) = ∑ P ( f | e , a ) P (a | e )

a3

51

52

e0 It is not

Alignment 4/4

f2

f3

f4



e = e = e0

e1

e2

e3

e4

e0

It

is

not

clear

特長： EMアルゴリズムで大域的に最適なモデル推定が可能

P( f | e ) = ∑ P( f , a | e )
a
m

e0
It
a
j =1
is
m
l
l
= ε ∑ L ∑ ∏ t ( f j | ea j ) not
a1 = 0am = 0 j =1
clear

a = a15 : a1=1, a2=3, a3=2, a4=3, a5=4
f 2 ↔ ea2 =3

CE NE EST PAS CLAIR≈ ∑ ε ∏ t ( f j | ea j )aj は f j ↔ ea j を意味する。

53

Model 1では一様分布とする= ∑ P (a | e ) P ( f | e , a )a = a1m = a1 , a2 ,..., am と表現する。
上記の例：(1+l)m種類（最尤推定）f5al
0

P(f, a3|e)• IBM Model 1 は、t( f |e)だけを用いた翻訳モデル

CE NE EST PAS CLAIR
f1

P(f |e)IBM Model 1• Alignment a の表現

f = f1m =

clear

…

これを一様分布とおくのがModel1

…

a

合計が

P(f, a2|e)clear

CE NE EST PAS CLAIR…

aP(f, a1|e)clear

a1 a2 a3
54

a4

a5

翻訳モデルの推定: 最尤推定

IBM Model 1の推定
• 対数尤度• 対訳コーパス: D = 対訳ペア<f,e>の集合

L( D | θ = {t ( f | e)}) = ∑ log P( f | e )• 尤度＝ ∏ P( f | e)

< f ,e >< f ,e >– 各対訳ペアが独立に生起したと仮定する

l• 最尤推定< f ,e >ただし、全対訳ペアで共起しない単語ペアを確率ゼロと仮定すると計算する必要はない。
この場合パラメータは数百万。

– 尤度を最大とするパラメータを求める– 対数尤度 L( D | θ ) = log ∏ P ( f | e )< f ,e >= ∑ log P( f | e )a1 = 0l< f ,e >a1 = 0am = 0 j =1l

< f ,e >t ( f | e)
最低でも10万×10万＝100億のパラメータ55ml

a1 = 0f

IBM Model 1の推定l

• EMアルゴリズム– 現在の θ old を L(θ old ) ≤ L(θ new ) を満たすような θ new に更新

ml

L(θ new ) = ∑ log ∑ L ∑ ∏ t new ( f j | ea j )< f ,e >a1 = 0am = 0 j =1m

– ポイント： lower boundの最大化を繰り返すl= ∑ log ∏ ∑ t new ( f j | ei )< f ,e >当たり前？（説明は次ページ）

j =1 i = 0ml< f ,e > j =1

i =0

= ∑ ∑ log ∑ t new ( f j | ei )L (θ )ml= ∑ ∑ log ∑ p ji (θ old )< f ,e > j =1

θEMアルゴリズムは ∑ pk rk ≥ ∏ rk
k

pk

l

m

l

m

m

l

j

am = 0 j =1

m

l

aj

l

am = 0 j =1

jaj

a1 = 0Lower bound, これを最大化するj

IBM Model 1の推定iam = 0 j =1

• 等式制約条件： ∑ t ( f | e) = 1 for ∀e.

j ,a jf• ラグランジュ関数• 上式は、以下の図で「パス（ j=1～m ）上のtj,iの積」をあらゆるパス
について和をとったものである。
j=1
0
i= 1
2
3
l

2

3

...

t2,0

t1,0
t1,1
t1,2

e
m

m

= ∑ ∑∑ p ji (θ ) log t new ( f j | ei ) + ∑ λe (∑ P( f | e) − 1)
< f ,e > j =1 i = 0t∂h(θ new )=0∂t ( f | e)t new ( f | e) ∝ ∑< f ,e >(t1,0+ t1,1 + t1,2 + t1,3 )× (t2,0+ t2,1 + t2,2 + t2,3 )×...
m

l

m

f

クロネッカーのδ（f=fjのとき１、他は０）mlt old ( f | e)
δ (e, ei )∑ δ ( f , f j )∑t old ( f | e0 ) + L + t old ( f | el ) j =1
i =0l

= ∏ ∑ t j ,i = ∏ ∑ t ( f j | ei )j =1 i = 0

e

• 最大化

• 同じことは以下の式でもできる。

59

f

l

old

... j,i ...

t2,2
t2,3

t1,3

h(θ new ) = L′(θ new ) + ∑ λe (∑ P( f | e) − 1)

tm,0

t2,1

= L′(θ new )58m∑ L ∑ ∏ t( f | e ) ≡ ∑ L ∑ ∏ t

a1 = 0p ji ( θ old )lj =1 i = 0lt old ( f j | ek )l

参考： ∑ L ∑ ∏ t ( f | e ) = ∏ ∑ t ( f | e )
a1 =0

k =0

p ji (θ )

new

l

∑

old

< f ,e > j =1 i = 0k（幾何平均は算術平均より小さいか等しい）57( f j | ei )t old ( f j | ei )l= ∑ ∑∑ p ji (θ old ) log t new ( f j | ei ) + const.

を使う （ ∑ pk = 1 ）kp ji (θ old ) =⎛ t ( f j | ei ) ⎞≥ ∑ ∑ log∏ ⎜
⎟
old
⎜
) ⎟⎠
< f ,e > j =1
i = 0 ⎝ p ji (θθθ t + 2θ t +θ3 t + 4

t

new

i =0

m

θ

am = 0 j =1

56

T. Minka. 1998. Expectation-Maximization as lower bound maximization.
http://research.microsoft.com/~minka/papers/em.html

t +1

m

∑ t ( f | e) = 1 for ∀e.

制約条件

IBM Model 1の推定tl

目的関数（最大化） L(θ ) = ∑ log ∑ L ∑ ∏ t ( f j | ea j )Model1の場合

θ

am = 0 j =1

= const. + ∑ log ∑ L ∑ ∏ t ( f j | ea j )< f ,e >θˆ = arg max L( D | θ )ml= ∑ log ε ∑ L ∑ ∏ t ( f j | ea j )j =1 i = 0

目的関数はもともと上に凸なので、最適解が求まる。
60

IBM Model 1 推定の解釈

IBM Model 1～5• IBM Model 1～5• Alignmentが与えられていたら？
CE NE EST PAS CLAIR票投t) に がI|
E
t(C たのっだ１e0 It is nott(CE|It) =clear

Model 1 : translation prob. t(f|e)
Model 2 : Model 1 + permutation prob.（絶対位置）
Model 3 : Model 2 + fertility prob. n(φ|e)
Model 4 : Model 3 の permutation prob. を改良（相対位置）
Model 5 : Model 4 の permutation prob. をさらに改良

It⇔CEの出現回数
It⇔*の出現回数

Alignmentの数（例では５）だけ投票• Model 4 : P(f, a|e) = fertility × translation × permutation• Alignmentが与えられていない場合

単語対応数

CE NE EST PAS CLAIR– fertility probability

e0 It is not– translation probability

単語対応

交換

• 目的言語のある単語eiが原言語の何単語（φi）に対応するか

clear• 目的言語のある単語eiが原言語の単語fikに対応する（訳される）確率t(CE|e0), t(CE|It), t(CE|is), t(CE|not), t(CE|clear)に分配して投票– permutation probabilitymlt old ( f | e)
δ ( f , f j )∑ δ (e, ei )∑old
( f | e0 ) + L + t ( f | el ) j =1
< f ,e > t
i =0t new ( f | e) ∝ ∑61• 目的言語のある単語eiに対応する原言語の単語fikの原言語文中での位
置jの確率（直前の目的言語単語ei-1に対応する原言語単語からの相対位置：πik）

old

62

推定実験 1/2

IBM Model 4• 実験条件• P(f, a | e) = fertility × translation × permutation
単語対応数

単語対応

– コーパス：Hansards corpus 1,778,620英仏文ペア– 語彙： 英 42,005単語＋１, 仏 58,016単語– モデルパラメータ：（Model 5）

交換

CE NE EST PAS CLAIR
It is not
目的言語単語 ei : e0 e1 e2 e3

clear
e4

fertilityφi : 0 1 1

1

2• t(f|e): 42,006×58,016 = 2,437,020,096
文ペア内に共起した単語だけを考慮 → 25,427,016• n(φ|e): 5(?)×42,006• d(π|...):→ n(φi | ei)translation fik : - ce est ne,pas clair → t (fik | ei)
permutation πik : - 1

notの場合の例
2→ d(πik|c(ei-1, fik))

2 -1,2

63

P.F.Brown et. al. 1993. The mathematics of statistical machine translation:
Parameter estimation. Computational Linguistics, 19(2), pages 263-311.

64

推定実験 2/2

フレーズ翻訳モデルの最尤推定
単語翻訳モデル

not…

t(ne|not)=0.497 n(2|not)=0.735t(pas|not)=0.442 n(0|not)=0.154
t(non|not)=0.029 n(1|not)=0.107

the

65

a

a

= ∑ P (a | e ) P ( f | e , a )= ∑ P (a | e ) P ( f | e , a )oil

P.F.Brown et. al. 1993. The mathematics of statistical machine translation:
Parameter estimation. Computational Linguistics, 19(2), pages 263-311.

a

計算量:

a

t(petrole|oil)=0.442t(petrolieres|oil)=0.138t(petroliere|oil)=0.109t(le | oil)=0.054m≈ ε ∑∏ P( fi | eai )m≈ ε ∑∏ t ( fi | eai )
a

i =1

m

l

= ε ∏ ∑ t ( fi | e j )(l+1)ma=(l+1) mi =1 j = 0…

n(1|the)=0.746
n(0|the)=0.254

フレーズ翻訳モデル
P( f | e ) = ∑ P( f , a | e )P( f | e ) = ∑ P( f , a | e )•…

t(le|the)=0.497
t(la|the)=0.207t(les|the)=0.155（IBM Model 1）

現実な計算量かつ大域的最適化を行える美しいアルゴリズム単語モデルと最尤推定は相性がよい
66

i =1

aが単語の
ときよりも
複雑

計算量を下げられない•••近似が必要となる
Alignmentの可能性が単語のときより膨大フレーズの階層性の問題

ヒューリスティックス

最尤単語アラインメント： GIZA++• GIZA++– IBM Model （+ HMM） モデルの推定– 訓練用対訳文ペアに対して最尤単語アライメント

フレーズ翻訳モデルの推定

Viterbiアラインメントaˆ = arg max P( f , a | e )a• フレーズ翻訳モデル推定の手順

最尤単語アラインメントの計算方法• シンプルなモデルのViterbiアラインメント（厳密解）を求める- f 側単語に同期させてViterbiアルゴリズムを適用- Model1, Model2, HMM• 上のViterbiアラインメントを初期値として局所探索でよりよいアラインメントを探す- Model3以上（Fertilityが難点）• 方向のある単語対応• 対称化単語対応• フレーズペア抽出

Och, F.J. and H. Ney. 2003. A systematic comparison of various statistical alignment models.
Computational Linguistics 29(1):19-51.
67

68

対称化単語対応

最尤単語対応：P(f=日|e=英)

最尤単語対応：P(f=英|e=日)

それ 以外 は 図 １２ と 同様 で ある

多 e0 それ 以外 は 図 １２ と 同様 で ある

多 e0 the remains are the same as in fig. 12

対
1 the remains are the same as in fig. 121対対称化単語対応

それ 以外 は 図 １２ と 同様 で ある積：
和：

対称化単語対応のみとthe remains are the same as in fig. 12※「は69

ある ・・■・・・・・・
で ・・・・・・・・・
同様 ・・・・■・・・・と ・・・・・■■・・
１２ ・・・・・・・・■
図 ・・・・・・・■・
は ・・・■・・・・・
以外 ・■・・・・・・・
それ ■・・・・・・・・

e0
theremains
are
the
same
as
in
fig.
12

（２）IBMモデルのalignmentにも誤りは多い
正しそうな対応だけを残したい

最尤単語対応：P(f=英|e=日)

ある ・・・■・・・・・・
で ・・・■・・・・・・
同様 ・・・・・■・・・・と ■・・・・・・・・・
１２ ・・・・・・・・・■
図 ・・・・・・・・■・
は ■・・・・・・・・・
以外 ・・■・・・・・・・
それ ・■・・・・・・・・

the」以外の対応は正しそう

theremains
are
the
same
as
in
fig.
12

（１）IBMモデルは方向のある1対多のalignment
両方向の1対多のalignmentにしたい70

ある ・・■・・・・・・
で ・・□・・・・・・
同様 ・・・・■・・・・と ・・・・・□□・・
１２ ・・・・・・・・■
図 ・・・・・・・■・
は ・・・□・・・・・
以外 ・■・・・・・・・
それ ■・・・・・・・・
theremains
are
the
same
as
in
fig.
12

目的

対称化単語対応
最尤単語対応：P(f=日|e=英)

積：■のみ
和：■と□
grow-diag:

対称化単語対応：ヒューリスティックス• 基本３種– 積（intersection）：両方向共にある対応点のみを用いる• 高precision, 低recall

alignment point

フレーズ翻訳モデルの推定– 和（union)：両方向の対応点をすべて使う• 低precision, 高recall– 成長（grow）: 積と和の中間• フレーズ翻訳モデル推定の手順• 積からスタート（和の対応点）• すでに採用した対応点の周りに候補の対応点を加えていく• 周り： grow → 縦・横,
grow-diag → 縦・横・対角• 最終処理（追加）３種• 方向のある単語対応• 対称化単語対応• フレーズペア抽出（和の対応点）– 対応がついてない単語に関する候補対応点を加える• final : 少なくとも片方の言語の単語の単語対応がない場合• final-and : 両側言語の単語に単語対応がない場合– 最終処理を行わない
71

72

を除く■と□

P.Koehn et al. 2005. Edinburgh systemdescription for the 2005 IWSLT speechtranslation evaluation. IWSLT2005.

一貫しないフレーズペア

定義：
フレーズ＝連続する単語列
フレーズペア＝英日のフレーズの対応

対称化単語対応（grow-diag）
ある・・■・・・・・・
で・・■・・・・・・
同様・・・・■・・・・と・・・・・■■・・
１２・・・・・・・・■
図・・・・・・・■・
は・・・・・・・・・
以外・■・・・・・・・
それ■・・・・・・・・

73

theremains
are
the
same
as
in
fig.
12

the
remains
are
the
same
as
in
fig.
12

ある ・・■・・・・・・
で ・・■・・・・・・
同様 ・・・・■・・・・
左の図のalignmentポイントをと ・・・・・■■・・ 囲む四角で任意のフレーズペア
１２ ・・・・・・・・■ を表現できる。
図 ・・・・・・・■・ 例：左の は「と同様」と“the same as in”のペア
は ・・・・・・・・・
以外 ・■・・・・・・・ 一貫したフレーズペア＝
それ ■・・・・・・・・ 灰色部分にAlignment
ポイントがないフレーズ

一貫したフレーズペア＝灰色部分にAlignment
ポイントがないフレーズ

一貫したフレーズペアをすべて取り出す

74

一貫したフレーズペア （別の図）フレーズペア抽出
対称化単語対応（grow-diag）

対称化単語対応（grow-diag）

the remains are the same as in fig. 12

それ 以外 は 図 １２ と 同様 で ある
the remains are the same as in fig. 12

と 同様

と 同様

the same as in

the same as in

一貫している

一貫しないある ・・■・・・・・・
で ・・■・・・・・・
同様 ・・・・■・・・・と ・・・・・■■・・
１２ ・・・・・・・・■
図 ・・・・・・・■・
は ・・・・・・・・・
以外 ・■・・・・・・・
それ ■・・・・・・・・

一貫したフレーズペア＝
フレーズペア内の単語対応から外に出て行く対応がない
75

76

the
remains
are
the
same
as
in
fig.
12

対称化単語対応（grow-diag）
それ 以外 は 図 １２ と 同様 で ある

対称化単語対応（grow-diag）
ある・・■・・・・・・
で・・■・・・・・・
同様・・・・■・・・・と・・・・・■■・・
１２・・・・・・・・■
図・・・・・・・■・
は・・・・・・・・・
以外・■・・・・・・・
それ■・・・・・・・・
theremains
are
the
same
as
in
fig.
12

一貫したフレーズペア
対称化単語対応（grow-diag）

抽出されるフレーズペア（それ, the）（以外,remains）（図, fig.）（１２,12）（同様,same）（と, as in）（同様, the same）（である,are）（は図, fig.）（以外は, reamins）（図１２, fig. 12）（である, are the）
（それ以外,the remains）（と同様,same as in）（それ以外は, the remains）（は図１２, fig. 12）（図１２と, as in fig. 12）（と同様, the same as in）（同様である, are the same）（は図１２と, as in fig. 12）（と同様である,are the same as in）（図１２と同様, same as in fig. 12）（図１２と同様, the same as in fig. 12）（は図１２と同様, same as in fig. 12）（は図１２と同様, the same as in fig. 12）

評価方法の種類• 人手評価（manual evaluation）– 翻訳結果は最終的に人が読む（ことが多い）– 「翻訳性能」を測る場合は人手評価が基本– 欠点： 高コスト（労力＆時間）

翻訳性能評価• 自動評価（intrinsic evaluation）
・人手評価
・自動評価
- BLEU, WER, NIST

– 人手をかけない評価• 主に、正解翻訳例との一致率（様々）で定義されることが多い– 問題： 人手評価と正確に同じではない– 利点： 正解翻訳例さえあればあとは低労力・少時間

・人手評価と自動評価の相関• 自動評価（extrinsic evaluation）– 人手をかけない評価• 翻訳システムを利用したより大きなタスクの達成率で評価– 例： NTCIR-7のPatent Translation TaskにおけるCLIR評価
77

78

人手評価

自動評価（intrinsic evaluation）• Adequacy & Fluency （代表的）• BLEU: BiLingual Evaluation Understudy– Adequacy： 翻訳結果は正しく意味を伝えているか？
– Fluency : 翻訳結果は言葉として自然か？
– 複数の人間によるそれぞれ５段階評価の平均– 翻訳結果とreferenceとの1～4gramの一致率の幾何平均– 短い文にはペナルティ
4
BLEU = BP ⋅ 4 ∏ pn
– 0.0～1.0で、大きいほどよい
i =1
ペナルティ

• WER : Word Error Rate
– 例（HLT-NAACL2006のSMT Workshop）

Adequacy
5: All meaning
4: Most meaning
3: Much meaning
2: Little meaning
1: None– 翻訳結果とreferenceの編集距離を正規化• 置換・挿入・削除誤りの割合• 音声認識におけるいわゆる「認識率」

Fluency
5: Flawless English
4: Good English
3: Non-native English
2: Disfluent English
1: Incomprehensible

79– 0.0～1.0で、小さいほどよい

ngramの一致率

n=1

PER=語順を無視したWER（Position-independent word Error Rate）• NIST metric : NIST（米国標準技術局）のBLEU– BLEUの幾何平均を重み付き幾何平均にする• 語順よりも単語訳の正しさ（特に内容語）を重視– 0.0～無限大で、大きいほどよい
NIST: National Institute of Standards & Technology

80

人手評価とBLEUの相関

参考文献などP.Koehn and C.Monz. 2006. Manual and automatic evaluation of machine translation
between European languages. Proc. of the workshop on SMT, pages 102-121.

• BLEU– オリジナルが以下ドイツ語→英語• K.Papineni et al. 2002. Bleu: a method for automatic evaluation of machinetranslation. Proc. of ACL2002, pages 311-318.

（標準化されている）（標準化されている）• WER– Wikipedia（英語版）の``word error rate’’の項

SMT– 最初に定義（使用）したオリジナルな論文は不明– 比較的正確に書いてある論文は例えば以下

ルールベース
ルールベース• McCowan et al. 2005. On the use of information retrieval measures for speech
recognition evaluation. IDIAP Research Report, IDIAP-RR 04-73.

SMT• NIST metric– Wikipedia（英語版）の``NIST (metric)’’の項– オリジナルは以下らしいがインターネット上にない（?）ので見たことがない• G.Doddington. 2002. Automatic evaluation of machine translation quality using ngram co-occurrence statistics. HLT2002.
（ACL AnthologyからHLT2002だけ全部欠落している）

SMTシステム同士の比較では高い相関
異種システム（SMT以外?）の比較には使わない方がよい
81

82

MERT : Minimum Error Rate Training• log-linearモデルeˆ ≈ arg max P1 (e ) P1 ( f | e, a ) P1 (a | e )チューニング
Minimum Error Rate Training

e

e ,a

eˆ ≈ arg max P λLM (e ) P λTM ( f | e, a ) P λRM (a | e )ee ,aeˆ ≈ arg max ∏ f k ( f , e, a )λk
e ,a

e

k

eˆ ≈ arg max log ∏ f k ( f , e, a )λk
e

e ,a

k

= arg max ∑ λk log f k ( f , e, a )
e

83

e ,a

本当は、基本モデルが、Noisy Channel ModelからDiscriminative Modelへとドラスティックに変化しているが、本講義ではそこには立ち入らない。
詳しくは[Och&Ney2002]など

k

Minimum Error Rate Training（ＭＥＲＴ）: ê がよくなるように λk を決める

84

MERT : Minimum Error Rate Training

MERT : Minimum Error Rate Training

Minimum Error Rate Training（ＭＥＲＴ）: ê がよくなるように λk を決める

λˆ = λ1n = arg max eval ( smt ( λ), eref )λê のよさ＝翻訳性能評価関数： BLEU, NIST, WER, ...
いずれも正解例 eref との一致率

smt ( λ) = eˆ = arg max ∑ λk log f k (e, a )eeval (eˆ, eref ) とおく（大きいほどよい）λˆ = λ1n = arg max eval ( smt ( λ), eref )λsmt ( λ) = eˆ = arg max ∑ λk log f k (e, a )e ,akmaxが２段階適用されているので最適化は簡単ではない（→近似：次ページ）

85※BLEUは文の集合に対して定義されるので、 ê や eref は文集合となる

86（２）の最適化：• Downhill simplex• 各次元で順番に最適化（N-bestで離散化できる [Och 2003]）• Powell法

まとめ：午後の実習 （英日方向のシステム）

MERTの図解

λ を更新して繰He ate a cake.
データ（原言語） She ate a soup.
...
development• 前半（2時間強）
り返す– 訓練データの準備• 英日データの分離と前処理– 言語モデルの構築

decoder∑ λ log f ( f , e, a)kTotal Cost
-4.04
-4.11
-3.99
BLEUや
WERの改善λLM = 0.4, λTM = 0.3, λRM = 0.2– Moses設定ファイルの作成

参照と比較すると、N-bestの中でどの候補がよいのかが分かる（BLEUやWER）

おまけ: SMTの研究テーマ• 言語モデル– 音声認識と様子が違う＆あまり研究されていないので穴場？

• 翻訳モデル2nd Workshop on SMT 2007:
Topics of interest include, but are not limited to:• word-based, phrase-based, syntax-based SMT• using comparable corpora for SMT• using morphological and POS information for SMT• integration of rule-based MT and statistical MT• decoding• error analysis• evaluation techniques for MT– フレーズモデル推定の脱ヒューリスティックス– フレーズモデルの次： 構文情報をいかに取り込むか– Reordering Model（特に日英）• デコーダ– Multistack & Beam-search がベスト？
• 普通に考えると局所探索がよいに決まっているのだが．．．

• 自動評価– ルールベースとSMTが比較できる指標• チューニング• 対訳データ– 方向のある単語アラインメント（IBMモデルの結果）– 対称化単語アラインメント– 抽出されたフレーズテーブル...

Total Cost
-4.47
-4.56
-4.59

...

...
...

...

...

LM TM RM
-3.8 -3.0 -8.1
-3.2 -4.3 -7.7
-2.9 -3.5 -8.9

彼はケーキを食べた。 development
彼女はスープを飲んだ。
データ（参照訳）...

89– フレーズ翻訳モデルの構築と確認• Mosesのスクリプトでフレーズ
翻訳モデルを作成• 途中ファイルを確認kkf = He ate a cake.
１位 彼はケーキを食べ。
２位 ヘリウムがケーキ。
３位 彼がケーキを食べた。

87• 50万文の日本語テキストとSRILMで5-gramモデルを作る

λLM = 0.3, λTM = 0.3, λRM = 0.3

各モデルの確率（対数）付N-best出力k

具体的な手続き（０）λを初期値に設定する（１）現在のλでデコーダを走らせ、N-bestを出力する（２）N-bestの中でrerankingした評価が最大になるようにλを最適化する（３）（１）～（２）を収束するまで繰り返す

MERT:

e

e ,a

しかし、いずれを研究するとしても大規模な
日英対訳データがないことには面白くない？
→ NTCIR-7のデータを使いましょう！

88– チューニング• MERTの実行– 翻訳実験と評価• Mosesでテスト文（30文）の翻訳• BLEU値の計算• 後半（1時間強）– 最終課題• 指定された条件で全体を繰り返す