統計的機械翻訳の現場 - NiCT

1
☎
✞
✝特 集 ✆
統計的機械翻訳の現場
Field of Statistical Machine Translation
渡辺 太郎
Taro Watanabe
情報通信研究機構
National Institute of Information Communications Technology
[email protected]
keywords: statistical machine translation, phrase-based translation model, syntax-based translation model
1. は じ め に
I do not know
Frederick Jelinek 先生の有名な言葉「言語学者を解雇
je ne sais
pas
する度に、音声認識器の性能が向上する」∗1 に代表され
図 1: 単語アライメント
るように、音声認識の研究開発の歴史において言語学的
な知見の貢献が極めて低かったことがわかる。では、音
声認識の基礎技術を共有することから始まった統計的機
械翻訳では、同じことが起こっているのか。
機械翻訳は従来、知識に基づく機械翻訳 (Knowledge-
based Machine Translation) とよばれ、機械翻訳システム
を新しい言語対へ対応させるため二言語の専門家により
ルールなどの知識を記述し、数年かけて開発するもので
あった。あるいは用例に基づく機械翻訳 (Example-based
Machine Translation) では、二言語の対訳データからなる
用例を検索、編集することで翻訳を生成しているが、言語
依存なスコアやヒューリスティック、編集手法を開発する
必要がある。このような言語学的な知見を集約した手法
に対し、統計的機械翻訳 (Statistical Machine Translation)
は、統計モデルに基づき、二言語の対訳データから機械翻
訳システムを自動的に構築するものであり、大量のデー
タを活用することにより新しい言語対や特定分野への適
応が短期間に低コストで実現できる。最近の評価型ワー
クショップによると、人間による主観評価の結果、中国語
から英語など、言語対あるいはタスクによっては統計的機
械翻訳は知識に基づく機械翻訳と同等、 あるいは大幅に
性能向上を果たしていることが報告されている [Callison-
Burch 11, Goto 11]。
統計的機械翻訳は、単語による統計モデルから始まり、
より多くの計算量および記憶容量を必要とする句による
モデル化によりその枠組みをほぼ完成させた。さらに、
木構造など、より豊かな言語間の対応関係を表現したモ
デルを導入することで、その翻訳精度を向上させている。
このように、言語学的な知識を取り入れることで発展し
ているかのように見える統計的機械翻訳であるが、実際
はどのように活用されてきたのか、その約 20 年の歴史
∗1 実際には技術者を増やすことで劇的に向上したらしい [Young
10]。
をたどっていく。
2. 単語モデルの挑戦
1980 年代後半から始まった統計的機械翻訳は音声認識
同様、「雑音のある通信路モデル (noisy channel model)」
に基づいている [Brown 90]。ある原言語 (例えば、フラ
ンス語) の文 f に対して、可能な様々な目的言語 (例えば、
英語) の翻訳文 e を列挙し、f が e へと翻訳される確率
P r(e|f ) を全ての文対 (e, f ) へ割り当てる。P r(e|f ) を最
ˆ を求めることにより翻訳誤りが最小な英語の
大化する e
文を生成可能である。
ˆ = arg max P r(e|f ) = arg max P r(f |e)P r(e)(1)
e
e
e
ベイズの法則により、二つの項が導入された。フランス
語の文は本来英語であった (P r(e)) が、雑音により英語
がフランス語へと歪められ、フランス語の文が観測され
た (P r(f |e)) と解釈可能である [Weaver 03]。P r(f |e) は
翻訳モデルと呼ばれ、e が与えられた時の f の条件付
き確率である。P r(e) は言語モデルと呼ばれ、事前知識
を入れることにより翻訳誤りを最小化する。また翻訳は
P r(f |e)P r(e) を最大化する問題として考えられ、英語
がフランス語へと符号化された過程を逆にたどることか
ら、復号化、あるいはデコードと呼ぶ [Brown 90]。
この古典的は枠組みに基づき、[Brown 93] はモデル 1
からモデル 5 へと徐々に複雑になっていく 5 つの翻訳モ
デルを提唱した。これは一般的に「IBM モデル」とよば
れ、図 1 に示したような対訳中の二言語間の単語単位の対
応を表現した単語アライメントという概念を導入してい
る。IBM モデルでは、単語アライメント a が導入された
人工知能学会論文誌 12 巻 1 号 a(1997 年)
2
I1
do2 not3 know4
I1 not3 not3 know4
I1 not3 not3 know4
je1 ne3 pas3
sais4
je1 ne3 sais4
pas3
ウィンドウ の 品物 を 見せ て下さい
fertility モデル
NULL モデル
in the window the one show me
語彙モデル
show me the one in the window
歪みモデル
図 3: 句に基づく機械翻訳
言語学的に異なる対では、二言語間の並び替えを正確に
図 2: IBM モデル 4 による生成過程
表現できず、そもそも日本語や中国語など単語の境界が
曖昧な言語へは直接適用するのは困難であった。
同時確率分布 P r(f , a, e) を想定し、翻訳モデル P r(f |e)
は、全ての可能な a に対して条件付き確率 P r(f , a|e) の
和と考える。
それに対し、句を最小単位とする、句に基づく機械翻
訳が提唱された [Koehn 03, Och 04b]。句とは、言語学的
な境界により決定されるものではなく、単なる単語列で
P r(f |e) =
P r(f , a|e)
(2)
a
計算量の観点から、英語の文からフランス語の文への単
語対応は一対多へと制限し、対訳データからパラメータ
を期待値最大化アルゴリズム、EM アルゴリズムにて推
定する。局所解へ収束することを防ぐために、簡単なモ
デル 1 からモデル 5 へと徐々に複雑さを増したモデルを
導入している。
ここで、特にモデル 4 について簡単に説明する。このモ
デルは P r(f , a|e) を fertility モデル、NULL モデル、語
彙モデル (lexicon model)、歪みモデル (distortion model)
へと分解しており、その生成過程を図 2 に示す。fertility
モデルは、英語の単語がフランス語の単語と対応する個
数を示しており、例えば “I” はフランス語の一単語 (“je”)
へと翻訳されやすい、あるいは “not” が単語二つ (“ne”
と “pas”) と対応しやすい、という関係を明示的に表す。
NULL モデルは英語に対応しないフランス語を挿入する
モデルである。語彙モデルにより、辞書による単語単位
の翻訳が行われ、最後に歪みモデルにより並び替えを行
う。モデル 4 では、歪みモデルは、例えば “pas” は一つ
後ろの位置へと移動する、といった相対位置で表現され
る。このようなモデル化は実際の英仏の対訳データを注
意深く観察することにより実現されており、計算量との
トレードオフ等、技術的要素を考慮に入れて統計モデル
が選択されたと予想される。
3. 単 語 か ら 句 へ
単語に基づく翻訳は Candide として実現され、非常に
限定的ではあるが、知識に基づく機械翻訳に迫る結果を
出した [Berger 94]∗2 。このような単語単位の翻訳は英語
やフランス語など、近い言語対に有効であるが、慣用句
など単語へと分解ができない表現をうまく翻訳できない。
∗2 実際には [Berger 96] のモデルにより前処理、後処理を行なっ
ている。
あり、翻訳とは、図 3 のように原言語文を I 個の句へと
¯i へと翻訳、翻訳され
分割 f = ¯
f1 , ...¯fI 、句単位で ¯fi を e
¯1 , ..., e
¯I を並び替える、という生成過程で表現され
た句 e
た。句を導入することにより、一単語だけでは表現でき
ない局所的な文脈あるは並び替えを直接表現でき、かつ
大局的な並び替えを句単位で行うことが可能となった。
句に基づく翻訳モデルは生成モデルをより一般化し、事
後確率 P r(e|f ) を直接対数線形モデル (log-linear model)
を用いて表現する。
ˆ = arg max P r(e|f )
e
e
= arg max
e
exp w⊤ h(e, φ, f )
⊤
′ ′
e′ ,φ′ exp (w h(e , φ , f ))
(3)
ここで、φ = {...(¯
ei , ¯fi ), ...} は句のペアであり、h(·) は w
により重み付けされる M 次元の素性関数である。式 (3)
により、統計的機械翻訳の研究開発は、句へのモデル化 φ
および素性関数 h(·) の開発、デコードの手法 (arg max)、
w の最適化といった問題へと帰着した。
3 ·1 句に基づく翻訳モデル
句への分割 φ および素性関数 h(·) の訓練を以下のよう
なヒューリスティックに基づいた手法で実現されている
[Koehn 03]。まず、訓練データに対して、単語アライメ
ントを計算する。2 章で述べたように、単語アライメン
トモデルは一対多で表現され、多対多のの関係を直接モ
デル化できない。そこで、[Och 04b] は両方向 P r(f , a|e)
と P r(e, a|f ) で、単語アライメントを学習、両方向の結
果を組み合わせることで単語対応の誤りを少なくしてい
る。次に、図 4 のように、単語アライメントが内部で閉
じているような句を網羅的に抽出する。最後に、句に対
応した素性を計算する。例えば句の翻訳確率 pφ (¯
f |¯
e) は
抽出された句の頻度情報 c(·) を元に計算される。
pφ (¯f |¯
e) =
¯)
c(¯f , e
′, e
¯
¯)
c(
f
¯
f′
(4)
統計的機械翻訳の現場
ィ
ド
ウ
い
の 品物 を 見せ 下さ
て
w⊤ h(·)
ウ
ン
3
show
me
(ウィンドウ, the window)
the
(の, in)
wm
(品物, one)
one
図 6: MERT における線分探索
(見せ て下さい, show)
in
(ウィンドウ の, in the window)
the
(ウィンドウ の 品物, one in the window)
(の 品物, in one)
window
となる。そこで、図 5(c) のように、探索空間の各ノード
を訪れた単語数でまとめ、その訪れた単語数に同期して
(の 品物, in one the)
(の 品物, in one the me)
図 4: 句の抽出例
他に、[Koehn 03] は、逆方向の翻訳確率 pφ (¯
e|f¯) や単語
翻訳確率、歪みペナルティー、n-gram 言語モデル、目的
言語の単語数などを素性として用いている。
幅優先探索を行い、ビーム幅などによるプルーニングが
行われる [Koehn 03]。
3 ·3 最
適
化
式 (3)(および式 (5)) における重み w は、エラー最小化
学習 (Minimum Error Rate Training、MERT) により、実
際のテストデータに近い訓練データ {(fs , es )}S
s=1 に対し
て最適化する [Och 03]。
S
3 ·2 デ コ ー ド
句に基づく翻訳モデルのデコーダは、全ての導出 Φ の
うち、素性と重みとの線形和を最大とする導出 φˆ を求
める。
φˆ = arg max w⊤ h(e, φ, f )
ℓ(arg max w⊤ h(e, φ, fs ), es )(6)
ˆ = arg min
w
(5)
φ∈Φ
デコードはまず、原言語の入力文に対して、マッチする
全ての句のペアを列挙する (図 5(a) 参照)。入力文を全て
被覆するフレーズペアの組みを目的言語側の順番にたど
ることで導出を求めることができる。この問題は、各都
市を原言語の単語、各都市を結ぶ経路を目的言語とした
巡回セールスマン問題として定式化できる [Knight 99]。
その動的計画法による解は、探索空間の各ノードを訪れ
た原言語のビット列として表現し、各ノードを結ぶエッ
w
直接最小化する学習法であり、式 (6) は凸関数でないた
めアルゴリズム 1 のように、Powell 法などの勾配を必要
としない最適化法が用いられる。Powell 法では、繰り返
し、ある方向を決定、その方向で線分探索 (line search)
にてパラメータの更新が行われる (行 5-9)。式 (6) では本
来、w の更新のたびにデコード (arg max) をしないとい
けないが、過去の n-best と結合 (行 3、4)、n-best のリラ
ンキングにより近似している。線分探索では網羅的に探
索 (grid search) を行わず、n-best の組み合わせ問題とし
てとらえ、効率よく探索する [Och 03]。具体的には、行
7 である次元 m に着目すると、式 (5) は
⊤
⊤
ˆ = arg max wm
hm (e, φ, fs )(7)
e
hm (e, φ, fs ) + wm
図 5(b) では、初期ノード “- - - - - -” から始まり、原言語
ド “- - - - • •” を訪れる。従って、長さ N の入力に対し、
2N のノードが必要であり、各ノードを N 2 の句で結
ぶため計算量は O(2N N 2 ) である。実際には n-gram 言
語モデル等、句に閉じていない素性などを組み合わせる
ため、その探索空間は非常に大きなものとなる。例えば
¯3 を計算
bigram 言語モデルを使用した場合、図 5(b) の e
¯1 の最後の一単語 “me” を記憶し、スコア
するために、e
を計算する。
e
この MERT の特徴は、翻訳誤りを評価する尺度 ℓ(·) を
ジを句のペアの目的言語側とすることで表現可能である。
¯1 のエッジにより、次のノー
の最後の 2 単語に対応する e
s=1
e
傾き
切片
となる。これは wm に対して区分的線形 (piecewise linear)
であり、ある導出 (e, φ) は、hm (e, φ, fs ) を傾き、m 以外
の素性と重みとの線形和を切片とする「線」として表現
できる。n-best 中の導出のうち、傾きが小さいものの順
に線を引き、その交点を求めることで図 6 のように wm
に対して w⊤ h(·) を最大化する凸包 (convex hull) を計算
可能である。各区間に対して ℓ(·) を求めることで、式 (6)
に関して誤りを最小化する最適な wm を求めることがで
きる。
log plm (window|me)
一般に、n-gram 言語モデルの場合、最後の n − 1 単語の履
歴が必要なため、目的言語の語彙数を |V| とすると、ノー
ドの数が 2N |V|n−1 へ増大し、計算量は O(2N |V|n−1 N 2 )
3 ·4 翻訳の自動評価:BLEU
式 (6) の翻訳誤りを評価する尺度 ℓ(·) として、BLEU
[Papineni 02] が標準的に用いられている。BLEU は、機械
人工知能学会論文誌 12 巻 1 号 a(1997 年)
4
¯3 :window
e
- - - - ••
show me
the one
the one in the window please show me
in the window
one
window on
item
ウ
ィ
ン
ド
ウ
の
品
物
show me
of
を
show please
見
せ
て
下
さ
¯1 :show me
e
¯4 :the one - - ••••
e
------
¯5 :show me
e
¯6 :of
e
¯2 :window
e
¯7 :on ••- - - e
2:
3:
(b) 探索空間
5:
6:
7:
8:
9:
10:
11:
翻訳など翻訳のスタイルを統一したい場合に有効な尺度
である。3 ·3 節の最適化の目的関数として使用すること
で、様々なモデルや素性を試すといった系統的な実験が
可能となり、機械翻訳システムの大幅な性能向上へ貢献
した。
この試行錯誤の過程で様々な言語学的な知見が試みら
れた。[Koehn 03] は、名詞句や動詞句など統語情報によ
り境界が決定される句のみを抽出したが、網羅的な手法
に勝ることはなかった。[Och 04a] は n-best のリランキン
グにより、品詞タグの言語モデルや構文解析木によるア
ライメントなど様々な言語学的な素性を試した。ところ
による翻訳 (翻訳候補) が、人間による翻訳 (参照訳) と類
似しているほど良いと考え、翻訳候補 {es }S
s=1 と複数の
S
参照訳 {{ris }R
i=1 }s=1 (R ≥ 1) との、n-gram (1 ≤ n ≤ 4)
による適合率の幾何平均で評価する。
pn × min exp 1 −
n=1
S
∗
s=1 |rs |
S
s=1 |es |
S
s=1
gn
,1
(8)
min c(gn ; es ), max{c(gn ; ris )}R
i=1
S
s=1
gn
が一番効果的だったののは、2 章の IBM モデル 1 という
一番単純なモデルのスコアによる素性であった。語彙化
木接合文法 (Lexicalied Tree Adjoining Grammar) や組み
合わせ範疇文法 (Combinatory Categorial Grammar) から
得られる高度タグ (supertag) に基づく言語モデル [Hassan
pn は翻訳候補の n-gram の適合率であり、参照訳の ngram 頻度に制限された頻度を元に計算される。
pn =
(c) プルーニング
さを捉えていると考えられ、特に新聞記事の翻訳や特許
n-best を結合
for k = 1...K do
for m = 1...M do
一つの次元 m で最適化,w を更新
end for
end for
end for
end procedure
1
4
••- - - •
••- - •- ••- - •
- •••- ••- •- - •- ••-
(1-gram) の適合率で表現、かつ長い 4-gram により流暢
procedure
for t = 1...T do
現在の w でデコード, 各 s ごとに n-best を
4
••- - - - •- - •- - •- - •
- ••- - - •- - - •
- •- •- -
続して用いられている。翻訳としての適切さを unigram
S
MERT({(es , fs )}s=1 )
生成
4:
•- - - - - •- - - -----•
- - - - •- - - •- - - •- - -
図 5: 句に基づく機械翻訳のデコード
Algorithm 1 エラー最小化学習 (MERT)
1:
•- - •- -
•- - - - -
い
(a) 句の列挙
•- - - ••
c(gn ; es )
(9)
翻訳候補の長さが参照訳に対して長い場合、適合率は低く
なる傾向がある。逆に翻訳可能な単語に絞って短い文を出
力する翻訳システムの適合率は極端に高くなる。従って、
min {·} の項で示された簡潔ペナルティー (brevity penalty)
により、翻訳候補の長さが参照訳の長さよりも短い場合、
適合率を直接調整するペナルティーを与えている。複数
の参照訳の場合、r∗s ∈ {ris }R
i=1 は、es の長さに近いもの
が選択される。
3 ·5 素性の研究開発
BLEU は人間による主観評価との相関性の問題や、統
07] や、右端 (right-corner) 変換により、構文ルールを左
側再帰なルールへと変換、階層的 HMM として統語論的
な言語モデルが実現されている [Schwartz 11]。このよう
な、統語論的に豊かな言語モデルによる精度向上は限定
的なものであったのに対し、[Brants 07] は、より単純な
5-gram 言語モデルにおいて、データを増やすことが直接
BLEU の向上に貢献することを示した。
4. 句から木構造へ
句に基づく翻訳は、文法を仮定せずに翻訳を実現する
手法であり、アラビア語やドイツ語、フランス語、英語
など比較的近い言語対などに対しては高精度な翻訳を実
現している。ところが中国語や日本語、英語など文法的
に非常に異なる言語対に対しては、語順が全く異なるた
め、非常に挑戦的な課題であった。
これに対して、単言語の構文解析木などで用いられて
いる文脈自由文法などの概念を取り入れた、同期文法を
語論的な情報を全く用いないなど様々な問題が指摘され
用いた手法が提案された [Galley 04, Chiang 07]。本稿
ているが、2000 年初頭から標準的な評価尺度として継
では二つの枠組みを解説する。まず、同期文脈自由文法
統計的機械翻訳の現場
5
X → X 1 ドア を X 2 , X 1 X 2 the door
X → X 1 X 2 開けた, X 1 opened X 2
(a) 同期文脈自由文法
ジ
ョ
ン
が ドア を け
開
た
S
S
VP
x1 :NP
X1
X1
the
VP
x2 :NP
x2 :VP
NP
X2
John
opened
x1 :NP
X 1 ドア を
door
VP
X2
the door
X2
開けた
X 1 opened X 2
(a) 同期文脈自由文法
開けた
ドア を
→ x1 x2 the door
→ x1 opened x2
S
(b) 同期木置換文法
VP
NP
図 7: 同期文法の例
ジョン が
NP
VP
ドア を 開けた
(synchronous Context Free Grammar、SCFG) は二言語で
定義される文脈自由文法である [Aho 69]。SCFG は原言
語の終端記号の集合 Σ と目的言語の終端記号の集合 ∆、
非終端記号の集合 N で定義される。SCFG の各ルール
∗
X → α, β, φ は原言語の記号列 α ∈ (N ∪ Σ) と目的言
∗
語の記号列 β ∈ (N ∪ ∆) を用いて、非終端記号 X ∈ N
を両言語同時に書き換える。φ は α と β にある非終端記
号の一対一のマッピングを表現する。図 7(a) は日本語と
英語の同期ルールの例を示しており、箱の中の数字によ
り非終端記号間の対応を表す。句に基づく翻訳と異なり、
原言語と目的言語にある非終端記号の位置により明示的
に並び替えを表現できる。
SCFG が文字列に対して書き換えを行うのに対し、同
期木置換文法 (synchronous Tree Substitution Grammar、
STSG) は木構造に対して直接置換操作を行う文法である
[Eisner 03]。STSG の各ルールは γ, δ, ϕ で表現され、γ
は原言語側の木構造であり、内部のノードは非終端記号
Xs ∈ Ns でラベル付けられ、その葉は原言語の終端記号
Σ あるいは変数 X = {x1 , x2 , ...} でラベル付けられてい
る。同様に、δ は目的言語の木構造であり、内部のノー
ドは非終端記号 Xt ∈ Nt でラベル付けされ、その葉は目
的言語の終端記号 ∆ あるいは変数 xi でラベル付けられ
ている。ϕ は一対一の対応を表現しており、X と非終端
記号 Ns と Nt との対応を示す。単純化のため、目的言
∗
語側を文字列に限定した制約 δ ∈ (X ∪ ∆) を導入する
[Galley 04]。図 7(b) にて図 7(a) に対応した同期ルール
の例を示す。このように木構造を介して、複雑な二言語
間の構造を表現可能となった。
これらの同期文法は句に基づく翻訳同様、単語アライ
メントされた二言語データから自動的に学習される。例え
ば、SCFG のルールは、階層的なルール抽出手法 [Chiang
07] により、まず句単位のアライメントを計算、その句に
含まれる句のペアを非終端記号に書き換えることで実現
John opened the door
(b) 同期木置換文法
図 8: 同期文法の抽出
語側の単語列の単語アライメントを伝搬させることによ
り、最小単位の木置換ルールを計算、その後最小ルール
を組み合わせた大きなルールを抽出することで実現され
る [Galley 06] (図 8(b) 参照)。
4 ·1 同期文法のデコード
同期文法の元での翻訳、あるいはデコードは、まず、
入力と同期文法の原言語側との交差 (intersection) を計算
し、交差した同期ルールの目的言語側を組み合わせるこ
とで、翻訳森を生成する [Chiang 07]。翻訳森は構文解
析で使用されるハイパーグラフとして表現される [Klein
01]。具体的に、ハイパーグラフは V, E という二つ組で
表現され、V 、E はそれぞれノードの集合、ハイパーエッ
ジの集合とする。V の各ノードは X @p として表現され、
X ∈ N は非終端記号であり、p は各ノードの ID を親か
らの相対的な位置として表されるアドレスとする。例え
ば、ルートノードには、ǫ(= 0) のアドレスが割り当てら
れ、p の最初の小ノードには、p.1 のアドレスが割り当て
られる。各ハイパーエッジ e ∈ E は tails(e), head(e) と
いう二つ組で表される。tails(e) ∈ (V ∪ ∆) は V のノー
∗
ドあるいは目的言語の終端記号 ∆ の子ノードのリストで
あり、head(e) ∈ V は親ノードを表す。図 9 は翻訳森を
例を示しており、例えば二つのハイパーエッジ
e1 =
[email protected] , [email protected] , the, door , [email protected]
e2 =
[email protected] , opened, [email protected] , [email protected]
される (図 8(a) 参照)。同様に、STSG のルールは GHKM
は親ノード [email protected] を共有し、図 7 にあるような同期ルール
法 [Galley 04] で、原言語の構文解析木に対して目的言
の目的言語側に対応する。
人工知能学会論文誌 12 巻 1 号 a(1997 年)
6
[Huang 07] は、cube pruning を提唱し、子ノードの導
[email protected]
e2
出の組み合わせを明示的に列挙せず、組み合わせを表現
e1
した cube と優先度付きキューを用いて効率よく列挙し
[email protected]
e3
John
ている。さらに、cube growing ではトップダウンの制約
opened
the door
[email protected]
[email protected]
e4
e6
e7
e5
opened opens
をもちいて、ボトムアップに展開する仮説を制約してい
る [Huang 07]。[Huang 09] は CNF のように、同期的に
ルールを二分化 (binarization) することで探索効率を向上
a door the door
している。[Watanabe 06] は同期ルールに制約を加える
図 9: 翻訳森の例
ことで句に基づく機械翻訳と同様にトップダウンに目的
言語を文頭から生成できることを示しており、さらに、
SCFG では、入力文を同期ルールの原言語側を用いて
CKY アルゴリズムで構文解析する。翻訳森は、交差し
たルールの目的言語側の非終端記号をハイパーグラフの
ノードに置換することにより実現される。同様に、STSG
では、二段階で構文森を生成する [Huang 06]。まず、入
力文を構文解析し、構文解析木を生成する。次に、この
構文解析木の下位の木構造に対して、トップダウン (あ
るいはボトムアップ) で STSG の原言語側でマッチング
を行い、交差を計算する。ここからは SCFG と同様に、
交差した同期ルールの目的言語側を組み合わせることで、
翻訳森を生成する。
4 ·2 探 索 の 効 率 化
翻訳森 F を生成した後、新たに素性を適用して、森の
リスコアを行い、その後、内側アルゴリズムにより全て
の導出 D から、最適な導出 dˆ を計算、翻訳を生成する。
ここで式 (5) と同様に、dˆ は以下のような素性の線形結
合による目的関数を使用する。
ルに対して文頭から生成している。
4 ·3 木 か ら そ の 先
SCFG のサブセットとして、転位伝搬文法 (Inversion
Transduction Grammar、ITG) は以下のように 3 種類の
同期ルールに限定している [Wu 97]。
X → [X X] | X X | f /e
非終端記号 X が二言語で書き換えられ、終端記号のペア
f /e を生成するか、並び替えが無い正位ルール X → [·] あ
るいは目的言語側で並び替えを行う逆位ルール X → ·
によりニ分木を構成する。ITG は文長が N の場合、多項
式時間 O(N 6 ) で二言語を解析できることが知られてお
り、そのため単語アライメント [Wu 97] や句アライメン
ト [Cherry 07] で利用されている。[Neubig 11] は 3 ·1 節
のようなヒューリスティックによらず、直接句のペアを学
習することでモデルをコンパクトに表現、かつ、従来法に
匹敵する結果を示している。[Mylonakis 11] は [Zollmann
dˆ = arg max w⊤ h(d, F )
(10)
d∈D
h(·) は句に基づく翻訳モデル同様、両方向のルール単位
の翻訳確率や n-gram 言語モデルなどの素性が用いられ
る。3 ·5 節で述べたように、オーダの大きい、かつ大量
のデータから学習された n-gram 言語モデルが翻訳を生
成する上で非常に重要である。これは文脈自由文法 (翻
訳森) と正規文法 (n-gram 言語モデル) との交差の問題で
あり、このようなルールに閉じていない、非局所的な素
性が導入されると計算量が大幅に増える。
例えば、bigram 言語モデルを使用した場合、図 9 にお
けるハイパーエッジ e1 は [email protected][email protected] から得られる単語
の履歴を用いて計算される。もし e4 が [email protected] から得られ
る導出の場合、
06] のように、構文木から得られるラベルを投影するこ
とで、統語論的な非終端記号を導入、EM アルゴリズム
で非終端記号の曖昧性を解消している。さらに、正位あ
るいは逆位、という前の非終端記号の書き換え方により
非終端記号を細分化することで ITG の曖昧性の問題を解
消している。
STSG は入力文をいったん構文解析し、その構文木か
ら翻訳を生成する必要があるが、曖昧な入力あるいは解
析誤りによる影響を大きく受けていた。そこで構文解析
器から、複数の構文解析木をコンパクトに表現した構文
解析森を出力∗3 、構文森から同期ルールの抽出 [Mi 08a]、
あるいはデコードを行う [Mi 08b]。さらに、[Zhang 11]
は構文解析木をすべての方向で二分化し、その結果得ら
れる構文森から抽出あるいはデコードを行なっている。
log plm (opened|John)plm (the|opened)plm (door|the)
のように計算される。局所的な素性のみを用いた場合、入
力文の文長 N に対して、内側アルゴリズムによるリスコ
アで O(N 3 ) で計算可能である。一般的に、n-gram 言語
モデルを適用した場合、各ノードに対して、前後の n − 1
単語の履歴を記憶するため、計算量は O(N |∆|
3
へと増大する。
[Huang 10] はスタックで仮説を表現し、任意の同期ルー
2(n−1)
)
元々の構文解析木のルールの境界を無視した二分化によ
り、翻訳が向上することを示している。
SCFG や STSG よりさらに表現力のある同期木接合文
法 (synchronous Tree Adjoining Grammar) に基づく機械
翻訳 [DeNeefe 09, Liu 11] や、依存構造に基づく機械翻訳
∗3 あるいは CKY アルゴリズムにおけるチャートをプルーニン
グし、出力する。
統計的機械翻訳の現場
7
[Ding 05, Quirk 05]、句構造および依存構造の両方を用い
た機械翻訳 [Shen 08, Mi 10, Xie 11] などの同期文法や構
困難である。用例に基づく機械翻訳のような、ヒューリ
造が提案されている。特に、木構造に基づいた翻訳モデル
データから形式言語に基づいたモデルを学習、統計量に
は同様な素性に対して親和性が高く、依存構造言語モデ
基づく素性を最適化し、膨大な探索空間から動的計画法
ル [Shen 08] や、統語論的な二値素性 [Chiang 09] が導入
に基づき最適な翻訳を導出する。この系統立てた統計モ
されている。さらに、擬似同期文法 (quasi-synchronous
デルに基づく研究開発に、人間の思いつきだけで対抗す
grammar)[Gimpel 09, Gimpel 11] や非同期文法 [Galley
10] など同期した関係では必ずしも表現しきれない複雑
るのはほぼ不可能である。統計的機械翻訳はこれらの機
な二言語間の対応を実現している。
という位置づけで今後も研究開発が続く。将来、機械翻
スティックなモデルやスコア、探索手法ではなく、大量の
械翻訳を一般化したものであり、
「機械翻訳の基礎研究」
訳の統計モデルがそのまま人間翻訳のモデルとなるのか、
5. お わ り に
統計的機械翻訳は、古典的な通信路モデルに基づいた
モデルから始まり、対数線形モデルにより様々な素性を
同時に扱えるようになった。この過程で、BLEU が標準
的な翻訳の評価尺度として導入され、複数の素性の組み
合わせを最適化するアルゴリズムにより飛躍的に研究開
発が進んだ。また、単語から句、木構造へと、より豊か
な表現を取り入れることで直接統語情報を扱えるように
なったが、同時にモデルおよび素性が複雑化している。
この問題に対し、動的計画法に基づく近似的な探索アル
ゴリズムを組み合わせることで非局所的な素性を効率よ
く適用、膨大な探索空間から最適な翻訳を生成している。
このように、動的計画法、機械学習、最適化、形式言語
論などの理論、技術を援用して統計的機械翻訳は進化を
続けてきた。
今後、さらに複雑な同期文法理論や統語論的、意味論
的知識の活用が進むと思われるが、この時、実際の対訳
データで現実的に計算可能な統計モデルへと表現するこ
とが必要となる。例えば、SCFG をより単純化した ITG
でも、十分、複雑な二言語の対応を表現でき、かつ計算
可能なモデルを実現できる。統計的機械翻訳の歴史の中
で、このようなモデル化に貢献してきたのは、言語学者
ではなくコンピュータ科学および自然言語処理の基礎ア
ルゴリズムを理解した技術者あるいは研究者であり、対
訳データを注意深く観察し、様々な現象を考慮しつつ取
捨選択してきた。例えば、BLEU は翻訳のスタイルを統
一するという点で成功した自動評価の尺度であり、実際
の翻訳業務で必要とされ作られたと考えられる。この文
法を無視した尺度に対して、同期文法に基づく翻訳モデ
ルは n-gram との効率的な交差を計算することでその尺
度の最大化へ向けて最適化させている。このような視点
は知識に基づく機械翻訳や用例に基づく機械翻訳など、
古典的な機械翻訳にはなかった。
句や木構造など、より豊かな二言語間の対応関係をモ
デル化した統計的機械翻訳の実現により、もはや、古典
的な機械翻訳と統計的機械翻訳との区別は、全く意味が
なくなったといえる。知識に基づく機械翻訳と違い、対
訳データから網羅的に同期文法を自動的に獲得する。そ
の網羅的なルールの被覆率に人間が追いつくのはもはや
その挑戦は終わらない。
♦ 参 考 文 献 ♦
[Aho 69] Aho, A. V. and Ullman, J. D.: Syntax Directed Translations
and the Pushdown Assembler, Journal of Computer and System Sciences, Vol. 3, No. 1, pp. 37–56 (1969)
[Berger 94] Berger, A. L., Brown, P. F., Della Pietra, S. A.,
Della Pietra, V. J., Gillett, J. R., Lafferty, J. D., Mercer, R. L.,
Printz, H., and Ureˇs, L.: The Candide system for machine translation,
in Proc. of HLT ’94, pp. 157–162, Stroudsburg, PA, USA (1994)
[Berger 96] Berger, A. L., Pietra, V. J. D., and Pietra, S. A. D.: A
maximum entropy approach to natural language processing, Computational Linguistics, Vol. 22, pp. 39–71 (1996)
[Brants 07] Brants, T., Popat, A. C., Xu, P., Och, F. J., and Dean, J.:
Large Language Models in Machine Translation, in Proc. of EMNLPCoNLL 2007, pp. 858–867 (2007)
[Brown 90] Brown, P. F., Cocke, J., Pietra, S. D., Pietra, V. J. D., Jelinek, F., Lafferty, J. D., Mercer, R. L., and Roossin, P. S.: A Statistical Approach to Machine Translation, Computational Linguistics,
Vol. 16, No. 2, pp. 79–85 (1990)
[Brown 93] Brown, P. F., Pietra, S. A. D., Pietra, V. J. D., and Mercer, R. L.: The Mathematics of Statistical Machine Translation: Parameter Estimation, Computational Linguistics, Vol. 19, No. 2, pp.
263–311 (1993)
[Callison-Burch 11] Callison-Burch, C., Koehn, P., Monz, C., and
Zaidan, O.: Findings of the 2011 Workshop on Statistical Machine
Translation, in Proc. of SMT 2011, pp. 22–64, Edinburgh, Scotland
(2011)
[Cherry 07] Cherry, C. and Lin, D.: Inversion Transduction Grammar
for Joint Phrasal Translation Modeling, in Proc. of SSST 2007, pp.
17–24, Rochester, New York (2007)
[Chiang 07] Chiang, D.: Hierarchical Phrase-Based Translation,
Computational Linguistics, Vol. 33, No. 2, pp. 201–228 (2007)
[Chiang 09] Chiang, D., Knight, K., and Wang, W.: 11,001 New Features for Statistical Machine Translation, in Proc. of NAACL-HLT
2009, pp. 218–226, Boulder, Colorado (2009)
[DeNeefe 09] DeNeefe, S. and Knight, K.: Synchronous Tree Adjoining Machine Translation, in Proc. of EMNLP 2009, pp. 727–736,
Singapore (2009)
[Ding 05] Ding, Y. and Palmer, M.: Machine translation using probabilistic synchronous dependency insertion grammars, in Proc. of ACL
’05, pp. 541–548, Morristown, NJ, USA (2005)
[Eisner 03] Eisner, J.: Learning Non-Isomorphic Tree Mappings for
Machine Translation, in Proc. of ACL 2003, pp. 205–208, Sapporo,
Japan (2003)
[Galley 04] Galley, M., Hopkins, M., Knight, K., and Marcu, D.:
What’s in a translation rule?, in Proc. of HLT-NAACL 2004, pp. 273–
280, Boston, Massachusetts, USA (2004)
[Galley 06] Galley, M., Graehl, J., Knight, K., Marcu, D., DeNeefe, S., Wang, W., and Thayer, I.: Scalable Inference and Training of Context-Rich Syntactic Translation Models, in Proc. of
ACL/COLING 2006, pp. 961–968, Sydney, Australia (2006)
[Galley 10] Galley, M. and Manning, C. D.: Accurate NonHierarchical Phrase-Based Translation, in Proc. of NAACL-HLT
2010, pp. 966–974, Los Angeles, California (2010)
人工知能学会論文誌 12 巻 1 号 a(1997 年)
8
[Gimpel 09] Gimpel, K. and Smith, N. A.: Feature-Rich Translation
by Quasi-Synchronous Lattice Parsing, in Proc. of EMNLP 2009, pp.
219–228, Singapore (2009)
[Gimpel 11] Gimpel, K. and Smith, N. A.: Quasi-Synchronous Phrase
Dependency Grammars for Machine Translation, in Proc. of EMNLP
2011, pp. 474–485, Edinburgh, Scotland, UK. (2011)
[Goto 11] Goto, I., Lu, B., Chow, K. P., Sumita, E., and Tsou, B. K.:
Overview of the Patent Machine Translation Task at the NTCIR-9
Workshop, in Proc. of NTCIR-9 (2011)
[Hassan 07] Hassan, H., Sima’an, K., and Way, A.: Supertagged
Phrase-Based Statistical Machine Translation, in Proc. of ACL 2007,
pp. 288–295, Prague, Czech Republic (2007)
[Huang 06] Huang, L., Knight, K., and Joshi, A.: Statistical syntaxdirected translation with extended domain of locality, in In Proc.
AMTA 2006, pp. 66–73 (2006)
[Huang 07] Huang, L. and Chiang, D.: Forest Rescoring: Faster Decoding with Integrated Language Models, in Proc. of ACL 2007, pp.
144–151, Prague, Czech Republic (2007)
[Huang 09] Huang, L., Zhang, H., Gildea, D., and Knight, K.: Binarization of synchronous context-free grammars, Computational Linguistics, Vol. 35, pp. 559–595 (2009)
[Huang 10] Huang, L. and Mi, H.: Efficient Incremental Decoding for
Tree-to-String Translation, in Proc. of EMNLP 2010, pp. 273–283,
Cambridge, MA (2010)
[Klein 01] Klein, D. and Manning, C. D.: Parsing and Hypergraphs,
in Proc. of IWPT-2001, pp. 123–134 (2001)
[Knight 99] Knight, K.: Decoding complexity in word-replacement
translation models, Computational Linguistics, Vol. 25, No. 4, pp.
607–615 (1999)
[Koehn 03] Koehn, P., Och, F. J., and Marcu, D.: Statistical PharseBased Translation, in Proc. of HLT-NAACL 2003, pp. 48–54, Edmonton (2003)
[Liu 11] Liu, Y., Liu, Q., and L¨u, Y.: Adjoining Tree-to-String Translation, in Proc. of ACL-HLT 2011, pp. 1278–1287, Portland, Oregon,
USA (2011)
[Mi 08a] Mi, H. and Huang, L.: Forest-based Translation Rule Extraction, in Proc. of EMNLP 2008, pp. 206–214, Honolulu, Hawaii
(2008)
[Mi 08b] Mi, H., Huang, L., and Liu, Q.: Forest-Based Translation,
in Proc. of ACL-08: HLT, pp. 192–199, Columbus, Ohio (2008)
[Mi 10] Mi, H. and Liu, Q.: Constituency to Dependency Translation
with Forests, in Proc. of ACL 2010, pp. 1433–1442, Uppsala, Sweden
(2010)
[Mylonakis 11] Mylonakis, M. and Sima’an, K.: Learning Hierarchical Translation Structure with Linguistic Annotations, in Proc. of
ACL-HLT 2011, pp. 642–652, Portland, Oregon, USA (2011)
[Neubig 11] Neubig, G., Watanabe, T., Sumita, E., Mori, S., and
Kawahara, T.: An Unsupervised Model for Joint Phrase Alignment
and Extraction, in Proc. of ACL-HLT 2011, pp. 632–641, Portland,
Oregon, USA (2011)
[Och 03] Och, F. J.: Minimum Error Rate Training in Statistical Machine Translation, in Proc. of ACL 2003, pp. 160–167, Sapporo,
Japan (2003)
[Och 04a] Och, F. J., Gildea, D., Khudanpur, S., Sarkar, A., Yamada, K., Fraser, A., Kumar, S., Shen, L., Smith, D., Eng, K., Jain, V.,
Jin, Z., and Radev, D.: A Smorgasbord of Features for Statistical
Machine Translation, in Proc. of HLT-NAACL 2004, pp. 161–168,
Boston, Massachusetts, USA (2004)
[Och 04b] Och, F. J. and Ney, H.: The Alignment Template Approach to Statistical Machine Translation, Computational Linguistics, Vol. 30, No. 4, pp. 417–449 (2004)
[Papineni 02] Papineni, K., Roukos, S., Ward, T., and Zhu, W.-J.:
Bleu: a Method for Automatic Evaluation of Machine Translation, in
Proc. of ACL 2002, pp. 311–318, Philadelphia, Pennsylvania, USA
(2002)
[Quirk 05] Quirk, C., Menezes, A., and Cherry, C.: Dependency
treelet translation: syntactically informed phrasal SMT, in Proc. of
ACL ’05, pp. 271–279, Morristown, NJ, USA (2005)
[Schwartz 11] Schwartz, L., Callison-Burch, C., Schuler, W., and
Wu, S.: Incremental Syntactic Language Models for Phrase-based
Translation, in Proc. of ACL-HLT 2011, pp. 620–631, Portland, Ore-
gon, USA (2011)
[Shen 08] Shen, L., Xu, J., and Weischedel, R.: A New String-toDependency Machine Translation Algorithm with a Target Dependency Language Model, in Proceedings of ACL-08: HLT, pp. 577–
585, Columbus, Ohio (2008)
[Watanabe 06] Watanabe, T., Tsukada, H., and Isozaki, H.: Left-toRight Target Generation for Hierarchical Phrase-Based Translation,
in Proc. of ACL/COLING 2006, pp. 777–784, Sydney, Australia
(2006)
[Weaver 03] Weaver, W.: Translation, in Nirenburg, S., Somers, H.,
and Wilks, Y. eds., Readings in Machine Translation, chapter 1,
pp. 13–17, MIT Press, Massachusetts Institute of Technology, Cambridge, Massachusetts (2003)
[Wu 97] Wu, D.: Stochastic inversion transduction grammars and
bilingual parsing of parallel corpora, Computational Linguistics,
Vol. 23, No. 3, pp. 377–403 (1997)
[Xie 11] Xie, J., Mi, H., and Liu, Q.: A novel dependency-to-string
model for statistical machine translation, in Proc. of EMNLP 2011,
pp. 216–226, Edinburgh, Scotland, UK. (2011)
[Young 10] Young, S.: Frederick Jelinek 19322010: The Pioneer of
Speech Recognition Technology, in Speech and Language Processing Technical Committee Newsletter, IEEE Signal Processing Society
(2010)
[Zhang 11] Zhang, H., Fang, L., Xu, P., and Wu, X.: Binarized Forest to String Translation, in Proc. of ACL-HLT 2011, pp. 835–845,
Portland, Oregon, USA (2011)
[Zollmann 06] Zollmann, A. and Venugopal, A.: Syntax augmented
machine translation via chart parsing, in Proc. of StatMT ’06, pp.
138–141, Morristown, NJ, USA (2006)
〔担当委員:××○○〕
19YY 年 MM 月 DD 日 受理
著
者 紹
介
渡辺太郎
1994 年京都大学工学部情報工学科卒業. 1997 年京都大学
大学院工学研究科情報工学専攻修士課程修了. 2000 年 Lan-
従事.
guage and Information Technologies, School of Computer
Science, Carnegie Mellon University, Master of Science 取
得. 2003 年京都大学大学院情報学研究科知能情報学専攻博
士後期課程指導認定退学. 2004 年京都大学博士 (情報学).
ATR および NTT にて研究員として務めた後、現在、情
報通信研究機構主任研究員. 主に統計的機械翻訳の研究に