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 = X@1 , X@2 , the, door , X@ǫ e2 = X@1 , opened, X@3 , X@ǫ される (図 8(a) 参照)。同様に、STSG のルールは GHKM は親ノード X@1 を共有し、図 7 にあるような同期ルール法 [Galley 04] で、原言語の構文解析木に対して目的言の目的言語側に対応する。人工知能学会論文誌 12 巻 1 号 a（1997 年） 6 [Huang 07] は、cube pruning を提唱し、子ノードの導 X@ǫ e2 出の組み合わせを明示的に列挙せず、組み合わせを表現 e1 した cube と優先度付きキューを用いて効率よく列挙し X@1 e3 John ている。さらに、cube growing ではトップダウンの制約 opened the door X@3 X@2 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 は X@1 と X@2 から得られる単語の履歴を用いて計算される。もし e4 が X@2 から得られる導出の場合、 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 にて研究員として務めた後、現在、情報通信研究機構主任研究員. 主に統計的機械翻訳の研究に