依存関係確率モデルを用いた統計的句アライメント
京都大学大学院情報学研究科教授

黒橋禎夫

PROFILE

1994 年京都大学大学院工学研究科電気工学第二専攻博士課程修了。博士（工学）。2006
年 4 月より京都大学大学院情報学研究科教授。自然言語処理、知識情報処理の研究に従事。

kuro@i.kyoto-u.ac.jp
京都大学大学院情報学研究科

中澤敏明

075-753-5344

PROFILE2006 年東京大学大学院情報理工学系研究科電子情報学専攻修士課程修了。現在京都大学大学院情報学研究科博士後期課程在学。機械翻訳の研究に従事。

1 はじめに
日本語と英語のように言語構造が著しく異なり、語順変化が大きな言語対において、対訳文をアライメント

１．両言語とも依存構造解析し、アライメントの最初から言語の構造情報を利用する
２．アライメントの最小単位は単語だが、モデル学習時に句となるべき部分を自動的に推定し、句アライメントを行う

する際に重要なことは二つある。一つは構文解析や依存３．各方向（原言語→目的言語と目的言語→原言語）の構造解析などの言語情報をアライメントに組み込み、語生成モデルを二つ同時に利用することにより、より順変化を克服することであり、もう一つはアライメント高精度なアライメントを行うの手法が 1 対 1 の単語対応だけでなく、1 対多や多対既存の構造情報を利用する手法において、これらの３多などの句対応を生成できることである。これは一方のつを全て満たすものは提案されておらず、我々の手法は言語では 1 語で表現されているものが、他方では 2 語この点で新規性がある。

以上で表現されることが少なくないからである。しかし本モデルは二つの依存構造木において、一方の依存ながら、既存のアライメント手法の多くは文を単純に単構造木で直接の親子関係にある一組の対応について、他語列としてしか扱っておらず [1]、句対応は単語対応を方のそれぞれの対応先の依存関係をモデル化しており、行った後にヒューリスティックなルールにより生成する単語列アライメントで扱うのが困難な距離の大きな語順といった方法を取っている [3]。Quirk ら [6] はアライ変化にも対応することができる。言い替えれば、本モデメントに構造情報を統合しようとしたが、前述の単語列ルは木構造上での reordering モデルということができアライメントを行った後に用いるに留まっている。単語る。また本モデルはヒューリスティックなルールを用い列アライメント手法そのものの精度が高くないため、こずに、句となるべき部分を自動的に推定することができのような方法では十分な精度でアライメントが行えるとる。ここでいう句とは必ずしも言語的な句である必要はは言い難い。

なく、任意の単語のまとまりである。ただし、Phrase-

一方で、アライメントの最初から構造情報を利用する

based SMT における句の定義との重要な違いは、我々手法もいくつか提案されており、我々が提案する手法もは木構造を扱っており、単語列としては連続でなくてその一つである。提案手法のポイントは以下の 3 つでも、木構造上で連続ならば句として扱っているという点ある。

である。

266

寄稿集
機械翻訳技術の向上

5

また我々のモデルは IBM モデルのような各方向の生成モデルを両方向分同時に用いてアライメントを行う。
これはアライメントの良さを両方向から判断する方が自然であり、Liang ら [4] による報告にもあるように、そうした方が精度よいアライメントが行えるからである。ただし、Liang らの手法が IBM モデルと同様に単語列を扱うものであるのに対し、提案手法は木構造を扱っているという重要な違いがある。また Liang らの手法では部分的に双方向のモデルを結合するに留まっており、アライメントの結果としては各方向それぞれ独立に生成されるが、我々の方法ではただ一つのアライメン

図1

依存構造木とそのアライメント例

トを生成するという違いもある。
最近の報告では生成モデルよりも識別モデルを用いたIBM モデル [1] では、与えられた日本語文 f と英方がより高精度なアライメントが行えるという報告がな

語文 e からなる対訳文間の最も良いアライメントされているが、学習用にアライメントの正解セットを用以下の式により獲得される：意するコストがかかってしまう。そこで我々は教師なし

は(1)でモデル学習が行える生成モデルを用いた。モデルは 2
つのステップを経て学習される。Step 1 では単語翻訳

ここで p (f｜a,e) は語彙確率 (lexicon probability) と確率を学習し、Step 2 では句翻訳確率と依存関係確率呼ばれ、各単語の翻訳確率の積である。p (a｜e) はアラが推定される。さらに Step 2 では単語対応が句対応

イメント確率 (alignment probability) と呼ばれ、前に拡張される。各 Step は EM アルゴリズムにより反後の単語との位置関係をモデル化するものである。IBM復的に実行される。

モデルは方向性があるため、アライメントに制限があ

2 提案モデル概観
以降の説明においては言語対として日本語と英語を用る。これを解消するため、両方向による結果を最後に統合して最終的なアライメントとすることが多い。しかし日英のような言語構造の違いの大きい言語対においては、このような方法では十分な精度でのアライメントは行えない。

いるが、提案モデルはこの言語対に特別に設計されたも提案モデルは IBM モデルを 3 つの点で改善する。一つのではなく、言語対によらないロバストなものである。

目は単語ではなく句を考慮すること、二つ目は文中での提案モデルは依存構造木上で定義されるものであるの単語の位置ではなく、依存関係を考慮すること、最後にで、まず対訳文を両言語とも依存構造解析し、単語の依最も良いアライメント存構造木に変換する。図 1 に依存構造木の例を示す。

ルだけでなく、両方向のモデルを同時に利用する。つま単語は上から下に順に並んでおり、文のヘッドとなる単り、式 (1) を以下のように変更する：

を求める際に、片方向のモデ語は最も左側に位置している。アライメントの最小単位はこれら各単語であるが、モデル推定時に複数単語のかたまりを句として自動的に獲得する。これについては
3.2 章で詳しく述べる。

提案モデルは EM アルゴリズムにより学習される。
なお各確率の定義は [8] を参照されたい。

267

3 モデルトレーニング

ら考慮される。つまり、Step 2 のイタレーションが進むに連れ、より大きな句の対応を発見することができる。
全体として、Step 2 の 1 回のイタレーションは、提案モデルは 2 つのステップに分けて学習される。こE-step での `` 初期アライメント '' の生成と `` 山登り法

れは IBM モデルにおいて、完全に最適解が求まる簡単'' により最適なアライメントの探索、E-step と M-stepなモデルからスタートし、徐々により複雑なモデルに移の間での新たな句候補の生成、M-step でのパラメータ行することに対応する。Step 1 では単語翻訳確率の推の更新の 4 つの要素からなる。

定が行われ、Step 2 では句翻訳確率と依存関係確率のStep 2 での一回目のイタレーションでは、パラメー推定が行われる。どちらのステップにおいてもモデルはタの初期値を以下のようにする。一回目のイタレーショ

EM アルゴリズムにより学習される。またステップ 1 にンにおいては全ての句は 1 単語からなるため (2 単語以おいて句は扱わず、全て単語単位での学習となる。複数上からなる句候補が獲得されていないため ) 句翻訳確率

単語の塊＝句は Step 2 において自動的に獲得される。

については、Step 1 で求めた単語翻訳確率をそのまま用いる。依存関係確率は、Step 1 の最後のイタレーショ

3.1

Step1

Step 1 では各方向独立に、単語翻訳確率を推定する。これは IBM Model 1 と全く同様の方法により行ンで得られた最も良いアライメント結果において依存関係の生起回数を計数し、そこから求めた確率を用いる。
初期アライメント (E-step)：

われる。Step 1 の推定の際には対応の単位は各ノード

依存関係確率は用いず、句翻訳確率のみから初期アラ単体、つまり単語のみであり、句は考慮しない。句はイメントを生成する。全ての句候補同士の対応 ( もしくStep 2 の推定から考慮し、句となるべき候補を動的に

は NULL 対応 ) に対して、各方向からの句翻訳確率を作り出すことにより実現する。これは Step 1 の段階掛け合わせた、句対応確率を計算し、句対応確率の高いで可能な句の候補全てを考慮すると、アライメント候補ものから順に、対応として採用する。この際、各単語は数が爆発し、扱えなくなるためである。

1 度しか対応付かないようにする。つまりすでに採用されている対応と重なるような対応は採用しない。なお句3.2

Step2候補の生成については後で述べる。

Step 2 では句翻訳確率と依存関係確率の両方を推初期アライメントが生成されたら、その状態でのアラ定する。また f から e、e から f の二つのモデルを同時イメント確率を計算する。このときから依存関係確率もに用いて、一つの方向性のないアライメントを得る。

用いる。

Step 1 では計算を効率化することにより、近似を用い山登り法 (E-step)：

ずにモデルの推定が完全に行えるが、Step 2 では可能初期アライメントの状態から、依存関係確率を考慮しなアライメントを全て考慮することは不可能である。そながらアライメントを修正し、徐々に確率の高いアライ

こで我々は最も良いアライメントを探索するために、まメントを探索していく。修正手段としては以下の 4 種

ず句翻訳確率のみから初期アライメントを生成し、その類を考える。

後依存関係確率も考慮しつつ、山登り法によってアライ・Swap：任意の 2 つの対応に注目し、それらの対応をメントを徐々に修正するという方法をとる。

入れ替える。例えば図２の最初の操作では、`` 光 ⇔さらに Step 2 において新たな句候補の生成を行う。

photogate'' と `` フォト ゲート ⇔ photodetector''

新たな句候補は山登り法によって求められた最も良いアの対応がそれぞれ `` 光 ⇔ photodetector'' と `` フォライメントの状態から生成され、次のイタレーションかト ゲート ⇔ photogate'' というように対応が入れ替

268

寄稿集
機械翻訳技術の向上

図2

えられている。

5

山登り法の例のを新たに句として獲得し、Step 2 の次のイタレー

・Extend：任意の 1 つの対応に注目し、そのいずれかションから探索範囲に入れる。例えば図２の最終状態の言語における句を、親または子方向に 1 ノード分において NULL 対応となっている `` 素子 '' は、その子だけ拡大する。の対応である `` 受 光 ⇔ photodetector'' に含まれ、・Add： NULL 対応となっている原言語側及び目的言語側のノード間に、新たに対応を追加する。
・Reject：すでにある対応を削除し、それぞれ NULL

新たに `` 受 光 素子 '' という句を作りだし、`` 受 光 素子 ⇔ photodetector'' という対応があるものと考える
さらに親の対応である `` に ⇔ for'' に含まれ、`` 素子 に対応とする。

'' という句もつくり出し、`` 素子 に ⇔ for'' という対応

図２に山登り法によるアライメント修正過程の例を示があるものと考える。これらの新たに考慮される対応にす。なお図２は 1 回以上イタレーションを行ったあとは、元の対応の出現期待値 ( 正規化されたアライメントの状態である。修正後のアライメント確率が修正前よりの確率 ) を分配する。

も高くなる場合にのみ修正を実行し、修正された状態か

このように、NULL 対応に注目することにより動的ら再度修正を行っていく。確率が高くなる修正箇所がなに句となるべきかたまりを獲得していき、モデルの構築くなるまで修正を繰り返し行い、最終的に得られたアラを行う。

イメントが、最も確率の高いアライメントとなる。なお

モデル推定 (M-step)：

修正の途中で得られたアライメントの状態を、確率の高

一 般 的 な EM ア ル ゴ リ ズ ム に お い て は、 得 ら れ たいものから n 個保存しておき、仮想的な n-best アライ

n-best アライメントのそれぞれのアライメント確率をメントとし、パラメータ推定の際に利用する。

正規化し、各アライメントにおけるパラメータの出現回新たな句候補の生成：数をこの正規化された確率値 ( 出現期待値 ) を用いて計山登り法により得られた最も良いアライメント結果の数する。我々もこの方法に従い、全ての対訳文での全てうち、NULL 対応となった単語に注目する。NULL 対のアライメント結果を集めてパラメータの推定を行う。

応となった語の親、または子の単語が NULL 対応でな

ただし、正確に全てのアライメントを数え上げることはければ、その単語と NULL 対応の単語とをまとめたもできないため、山登り法の途中で得られたアライメント

269

のうち、アライメントの確率の高いもの上位 n 個 ( 山登and' の 3 つである [2]。

りの回数が n に満たない場合はその全て ) を用いる。パラメータ推定は一般的な EM アルゴリズムと同様に、各パラメータの出現期待値の総和を全体の回数で正規化することにより行われる。
こ こ ま で の 処 理 に よ り、EM ア ル ゴ リ ズ ム のE-step、M-step が終了し、再び E-step に戻る。こPreRecAER

Step 1

77.5

33.92

47.20

Step 2-1

84.26

48.38

61.65

Step 2-2

84.85

57.26

68.53

Step 2-3

82.84

61.86

71.03

Step 2-480.2163.1370.88

Step 2-578.71

64.10

70.88

れを複数回繰り返すことにより、モデルのトレーニング

Step 2-6

78.02

63.38

70.76

を行う。

Step 2-776.83

64.60

70.39

4 実験

Step 2-8

71.99

67.71

69.85

intersection

90.51

45.16

60.31

grow-final-and

79.92

60.06

68.70

grow-diag-final-and

77.80

61.47

68.77

表1

アライメント実験結果

提案手法の有効性を示すためにアライメント実験を行った。トレーニングコーパスとして JST 日英抄録

一方、提案手法によるアライメント精度を表１の上コーパスを用いた。このコーパスは、科学技術振興機部に示す。まず 'Step 1' に示されているのは、Step構所有の約 200 万件の日英抄録から、内山・井佐原の1 のイタレーションを 5 回行った後に学習されたパラ

方法 [7] により、情報通信研究機構が作成したものであメータ ( 単語翻訳確率 ) を用いたアライメントの精度でり、100 万対訳文からなる。このうち 475 文に人手ある。なおここでのアライメントは、両方向のパラメーで正解のアライメントを付与し、正解データとした。

タを用いて、３．２章の初期アライメント生成手法と正解データは Sure(S ) と Possible(P ) の２段階に分け同様にアライメントを生成した結果である。'Step 2-X'てアライメントされている [5]。また評価の単位は日本

は Step 2 の各イタレーション終了時点でのアライメ語、英語とも単語とし、適合率・再現率・AER によりント精度である。'Step 2-1' は句翻訳確率は 'Step 1'精度を求めた。のものと同じだが、それに加えて 'Step 1' のアライメ

日 本 語 文 に 対 し て は 形 態 素 解 析 器 JUMAN お よ

ント結果から推定した依存関係確率を用いてアライメン

び 依 存 構 造 解 析 器 KNP を 用 い、 英 語 文 に 対 し て はトを行っている。つまり、'Step 1' と 'Step 2-1' とをCharniak の nlparser を用いて構文解析し、ルールによ比較することにより、依存関係確率を用いることにより単語の依存構造木に変換する。また Step2 のパラメー

るアライメント精度の向上が見て取れる。以後 Step 2

タ推定の際に用いるアライメントの数は n=10 とした。のイタレーションを行い、その都度アライメント精度を比較実験として、単語列アライメント手法として広計測した。結果として、提案手法では単語列アライメン

く利用されている IBM モデルを実装したアライメント

ト手法よりも AER で 2.3 ポイントのアライメント精度ツールである GIZA++[5] を用いてアライメントを行っ向上を達成した (Step 2-3 と grow-diag-final-and とた。各モデルのイタレーション回数などのオプションはの比較による )。適合率だけを見ると 'intersection' がデフォルトの設定をそのまま利用した。さらに各方向の最もよい値を示しているが再現率が極端に低くなっていアライメント結果を三つの対称化手法により統合した。

る。また再現率が最も高いのは 'grow-diag-final-and'

結果を表１の下部３行に示す。利用した対称化手法はであるが、同程度の再現率を示している提案手法の結果'intersection'、'grow-final-and'、'grow-diag-final-を見ると、適合率では大きく上回っており、総合的に見270

寄稿集
機械翻訳技術の向上て提案手法は単語列アライメント手法よりも優れているということができる。

5 まとめと今後の課題
本稿では依存関係確率モデルを用いた統計的句アラ

5[2] Koehn, P., Axelrod, A., Mayne, A. B., CallisonBurch, C., Osborne, M., and Talbot, D.
(2005). “Edinburgh System Descriptionfor the 2005 IWSLT Speech Translation
Evaluation.” In Proceedings of International
Workshop on Spoken Language Translation2005 (IWSLT'05).

イメント手法を提案した。提案モデルは木構造上での[3] Koehn, P., Och, F. J., and Marcu, D. (2003).

reordering モデルということができ、シンプルなモデ“Statistical Phrase-Based Translation.” In

ルながらも言語構造の違いを柔軟に吸収し、精度の高い

HLT-NAACL 2003: Main Proceedings, pp.

アライメントを実現できた。実験結果から、語順の大き127-133.

く異なる言語対に対しては既存の単語列アライメント手[4] Liang, P., Taskar, B., and Klein, D. (2006).

法では十分な精度を達成することは困難であり、構文解“Alignment by Agreement.” In Proceedings

析などの言語情報を利用することが自然であり、高い効of the Human Language Technology果を示すことが証明された。今回は日本語と英語間のア

Conference of the NAACL, Main Conference,

ライメント実験のみしか行わなかったが、同様に語順に

pp. 104-111 New York City, USA.

大きな違いのある日本語と中国語間での実験などを行

Association for Computational Linguistics.

い、提案手法が言語対によらずロバストな手法であるこ[5] Och, F. J. and Ney, H. (2003). “A Systematicとを示す必要がある。
考察にも述べたとおり、提案手法は依存構造解析に大きく依存しており、依存構造解析誤りが容易にアライメ

Comparison of Various Statistical Alignment
Models.” Association for ComputationalLinguistics, 29 (1), pp. 19-51.

ントの誤りにつながってしまう。両言語の解析結果を照[6] Quirk, C., Menezes, A., and Cherry, C.

らしあわせて、文構造を修正しつつアライメントするこ(2005). “Dependency Treelet Translation:とも可能なはずであり、現在検討中である。これが実現

Syntactically Informed Phrasal SMT.” In

できれば、依存構造解析とアライメント双方の精度向上

Proceedings of the 43rd Annual Meetingが可能となると考える。

of the Association for Computational

アライメントの精度のみを評価したが、この結果が翻訳の精度にどのように影響するかを調査することは今後の課題である。

Linguistics (ACL'05), pp. 271-279.
[7] Utiyama, M. and Isahara, H. (2007). “AJapanese-English Patent Parallel Corpus.”
In MT summit XI, pp. 475-482.

参考文献[8] Nakazawa, T. and Kurohashi S. (2009)[1] Brown, P. F., Pietra, S. A. D., Pietra, V.

"Statistical Phrase Alignment Model

J. D., and Mercer, R. L. (1993). “TheUsing Dependency Relation Probability."

Mathematics of Statistical Machine

In Proceedings of the third Workshop

Translation: Parameter Estimation.”on Syntax and Structure in Statistical

Association for Computational Linguistics,Translation (SSST-3), pp.10-18, Colorado,

19 (2), pp. 263-312.

U.S.A (2009.6).

271