(57)【特許請求の範囲】
【請求項１】
部分出力文ＷT 、出力文の各単語が入力文のどの単語のインデックスに対応するかを示すアライメントＡ、既に処理された入力文のインデックスの集合Ｃ、スコアｓ、およびopenな仮説とclose な仮説との識別子open/ close を要素とする仮説ｈ＝（ＷT ，Ａ，Ｃ，ｓ，open/ close ）と、入力文の単語のインデックスの各部分集合に対応した複数のスタックとを用いてデコーディングを行なう統計的機械翻訳装置において、
入力文を入力させる第１手段、
部分出力文ＷT が存在せずかつ識別子open/ close がclose を表す値に設定された初期仮説を生成して空集合に対応するスタックに格納するとともに、変数ｃを０に設定する第２手段、
要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在するか否かを判別する第３手段、
要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在する場合には、そのうちの１つのスタックを選択する第４手段、
第４手段によって選択したスタック内にまだ読み出されていない仮説が存在するか否かを判別する第５手段、
第５手段において、選択したスタック内にまだ読み出されていない仮説が存在すると判別した場合には、まだ読み出されていない仮説を１つ読み出して仮説生成処理を実行した後、第５手段による処理に戻る第６手段、
第５手段において、選択したスタック内にまだ読み出されていない仮説が存在しないと判別した場合には、第３手段による処理に戻る第７手段、ならびに
第３手段において、要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在しないと判別した場合には、変数ｃを１だけインクリメントし、インクリメント後のｃの値が入力文の単語数に達した場合には、今回のデコーディングを終了させ、インクリメント後のｃの値が入力文の単語数に達していない場合には、第３手段による処理に戻る第８手段を備えており、
第６手段によって実行される仮説生成処理は、
第６手段によって読み出された仮説ｈを入力するとともに、変数ｊに１を設定する第１ステップ、
変数ｊが入力文の単語数より大きいか否かを判別し、変数ｊが入力文の単語数より大きい場合には今回の仮説生成処理を終了し、変数ｊが入力文の単語数以下の場合には変数ｊが入力仮説ｈ内のＣに含まれていないか否かを判別する第２ステップ、
第２ステップにおいて、変数ｊが入力文の単語数以下であり、かつ変数ｊが入力仮説ｈ内のＣに含まれていないと判別した場合には、入力仮説ｈ内の識別子open/ close に対応した仮説生成処理を実行し、生成した仮説をその仮説中のＣに対応するスタックに格納する第３ステップ、ならびに
第２ステップにおいて、変数ｊが入力文の単語数以下であり、かつ変数ｊが入力仮説ｈ内のＣに含まれていると判別した場合および第３ステップの処理が終了した場合には、変数ｊを１だけインクリメントした後、第２ステップに戻る第４ステップを備えており、
第３ステップは、入力仮説ｈ内の識別子open/ close がclose を表す値である場合には、既に得られた部分出力文に対して単語列を追加する操作を行ってclose に対応した仮説を生成するステップ、および入力仮説ｈ内の識別子open/ close がopenを表す値である場合には、入力文の単語を既に得られた部分出力文のある単語に対応付ける操作を行なってopenに対応した仮説を生成するステップを備えており、
close に対応した仮説を生成するステップにおいては、出力文を文末から生成するために、入力仮説ｈ内の部分出力文ＷT の左側に新しい文字列を挿入することにより新しい部分出力文を生成するとともに入力文のインデックスｊにある単語を新しく生成した部分出力文における最初の単語に対応付けし、openに対応した仮説を生成するステップでは、出力文を文末から生成するために、入力文のインデックスｊにある単語を入力仮説ｈ内の部分出力文ＷT における最初の単語に対応付けることを特徴とする統計的機械翻訳装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、統計的機械翻訳装置に関する。
【０００２】
【従来の技術】
近年、コーパスを用いた手法の一つである統計的機械翻訳システムの研究が盛んに行われるようになってきた。この統計的機械翻訳においては、原言語が与えられたときに目的言語へと翻訳する問題を、最大尤度の解を発見する問題として扱われるようになった。この問題はベーズルールにより最大事後確率の問題としてとらえられ、統計的機械翻訳システムは、翻訳モデルというチャネルソース言語をチャネルターゲット言語へと翻訳する確率、チャネルソース言語の尤度を表した言語モデル、さらに、入力文が与えられたときに出力を発見するデコーダの３つの要素で構成されるようになった（文献１参照）。
【０００３】
文献１：Brown,P.F., Pietra, S.A.D., V.L.D. and Mercer, R.L.: The  Mathematics of Statistical Machine Translation: Parameter Estimation, Computational Linguistics, Vol.19, No.2,pp.263-311(1993).
【０００４】
翻訳モデルでは、確率値を推定する効率的なアルゴリズムが知られているが、デコーディングはNP＿Completeであることが知られている（文献２参照）。
【０００５】
文献２： Knight,K.: Decoding Complexity in Word-Replacement Translation Models, Computational Linguistics, Vol.25, No.4, pp.607-615(1999).
【０００６】
デコーディングアルゴリズムとして、現在まで様々なアルゴリズム、例えばスタックデコーディングアルゴリズム（文献３参照）、Ａ* 探索アルゴリズム（文献４，５参照）、ＤＰアルゴリズム（文献６，７参照）が提唱されてきた。
【０００７】
文献３： Berger,A., Brown,P., Pietra,S., Pietra,V., Gillett,J., Kehler,A. and Mercer,R.: Language Tlanslation Apparatus and Method of Using Context-Based Translation Models, Technical report, United States Patent, Patent Number 5510981(1996).
文献４： Och,F.J., Ueffing,N. and Ney,H.: An Efficient A* Search Algorithm for Statistical Machine Translation, Proc. of the ACL-2001 Workshop on  Data-Driven Machine Translation, Toulouse, France, pp.55-62(2001).
文献５：Wang,Y.-Y. and Waibel, A.: Decoding Algorithm in Statistical Machine Translation, Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics(1997).
文献６： Garcia-Varea, I. and Casacuberta, F.: Seach Algorithms for Statistical Machine Translation Based on Dynamic Programming and Pruning Techniques, MT Summit VIII, Santiago de Compostela, Galicia, Spain (2001).
文献７：Tillmann,C. and Ney, H.: Word Re-ordering and DP-based Search in Stational Machine Translation, Proc. of the COLING 2000(2000).
【０００８】
これらは、入力文に対して出力文を文頭から生成し、原言語文と目的言語文とがほぼ線形に対応づけられることを仮定したプルーニング戦略を取り入れたものであった。このようなアルゴリズムにおいては、例えば日本語と英語のように、性質の異なる言語の翻訳には対応できなかった。
【０００９】
また、Germamm らはヒルクライミングアルゴリズムとインテジャー解を示している（文献８参照）。前者の手法では、満足な解が得られないことが分かっており、また、後者の手法では現実的に処理速度の問題で、解を得ることができない。
【００１０】
文献８： German,U., Jahr,M., Knight,K., Marcu,D. and Yamada,K.: FastDecoding and Optimal Decoding for Machine Translation, Proc. of ACL-01, Toulouse, France(2001).
【００１１】
この発明は、文末に語順の制約が強いという性質をもつ言語が目的言語である場合に、好適な翻訳結果が得られる統計的機械翻訳装置を提供することを目的とする。
【００１２】
【課題を解決するための手段】
この発明による統計的機械翻訳装置は、部分出力文ＷT 、出力文の各単語が入力文のどの単語のインデックスに対応するかを示すアライメントＡ、既に処理された入力文のインデックスの集合Ｃ、スコアｓ、およびopenな仮説とclose な仮説との識別子open/ close を要素とする仮説ｈ＝（ＷT ，Ａ，Ｃ，ｓ，open/ close ）と、入力文の単語のインデックスの各部分集合に対応した複数のスタックとを用いてデコーディングを行なう統計的機械翻訳装置において、
入力文を入力させる第１手段、
部分出力文ＷT が存在せずかつ識別子open/ close がclose を表す値に設定された初期仮説を生成して空集合に対応するスタックに格納するとともに、変数ｃを０に設定する第２手段、
要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在するか否かを判別する第３手段、
要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在する場合には、そのうちの１つのスタックを選択する第４手段、
第４手段によって選択したスタック内にまだ読み出されていない仮説が存在するか否かを判別する第５手段、
第５手段において、選択したスタック内にまだ読み出されていない仮説が存在すると判別した場合には、まだ読み出されていない仮説を１つ読み出して仮説生成処理を実行した後、第５手段による処理に戻る第６手段、
第５手段において、選択したスタック内にまだ読み出されていない仮説が存在しないと判別した場合には、第３手段による処理に戻る第７手段、ならびに
第３手段において、要素数がｃ個である部分集合に対応するスタックでまだ選択されていないスタックが存在しないと判別した場合には、変数ｃを１だけインクリメントし、インクリメント後のｃの値が入力文の単語数に達した場合には、今回のデコーディングを終了させ、インクリメント後のｃの値が入力文の単語数に達していない場合には、第３手段による処理に戻る第８手段を備えており、
第６手段によって実行される仮説生成処理は、
第６手段によって読み出された仮説ｈを入力するとともに、変数ｊに１を設定する第１ステップ、
変数ｊが入力文の単語数より大きいか否かを判別し、変数ｊが入力文の単語数より大きい場合には今回の仮説生成処理を終了し、変数ｊが入力文の単語数以下の場合には変数ｊが入力仮説ｈ内のＣに含まれていないか否かを判別する第２ステップ、
第２ステップにおいて、変数ｊが入力文の単語数以下であり、かつ変数ｊが入力仮説ｈ内のＣに含まれていないと判別した場合には、入力仮説ｈ内の識別子open/ close に対応した仮説生成処理を実行し、生成した仮説をその仮説中のＣに対応するスタックに格納する第３ステップ、ならびに
第２ステップにおいて、変数ｊが入力文の単語数以下であり、かつ変数ｊが入力仮説ｈ内のＣに含まれていると判別した場合および第３ステップの処理が終了した場合には、変数ｊを１だけインクリメントした後、第２ステップに戻る第４ステップを備えており、
第３ステップは、入力仮説ｈ内の識別子open/ close がclose を表す値である場合には、既に得られた部分出力文に対して単語列を追加する操作を行ってclose に対応した仮説を生成するステップ、および入力仮説ｈ内の識別子open/ close がopenを表す値である場合には、入力文の単語を既に得られた部分出力文のある単語に対応付ける操作を行なってopenに対応した仮説を生成するステップを備えており、
close に対応した仮説を生成するステップにおいては、出力文を文末から生成するために、入力仮説ｈ内の部分出力文ＷT の左側に新しい文字列を挿入することにより新しい部分出力文を生成するとともに入力文のインデックスｊにある単語を新しく生成した部分出力文における最初の単語に対応付けし、openに対応した仮説を生成するステップでは、出力文を文末から生成するために、入力文のインデックスｊにある単語を入力仮説ｈ内の部分出力文ＷT における最初の単語に対応付けることを特徴とする。
【００１３】
【発明の実施の形態】
以下、図面を参照して、この発明の実施の形態について説明する。
【００１４】
〔１〕統計的機械翻訳の概要についての説明
【００１５】
統計的機械翻訳においては、ある原言語のテキストＷS が与えられているときにある目的言語のテキストＷT へと翻訳する問題を、最大尤度の出力（翻訳結果）を発見する問題としてとらえられ、次式（１）のように表現される。
【００１６】
【数１】
0004006297.tif 000002
【００１７】
上記式（１）にベーズルールを適用することにより、上記の問題は、次式（２）に示すように、チャネルモデルにおける最大事後確率の解を求める問題に置き換えられる。
【００１８】
【数２】
0004006297.tif 000003
【００１９】
このため、翻訳とは、図１（ａ）に示すように「翻訳家の知識Ｐ（ＷT ｜ＷS ）を基にして原言語のテキストＷS を翻訳」する問題として扱われるのではなく、図１（ｂ）に示すように「ある確率Ｐ（ＷT ）で起こりうる目的言語のテキストＷT が、チャネルにより、( Ｐ（ＷS ｜ＷT ) ）、ＷS として出力された」と仮定して、目的言語のテキストＷT を原言語のテキストＷS から推測する問題として扱われるようになった（上記文献１参照）。
【００２０】
Ｐ（ＷT ) は言語モデル（事前確立）であり、目的言語のテキストＷT の尤度を示す。Ｐ（ＷS ｜ＷT ）は翻訳モデル（事後確立）であり、目的言語のテキストＷT が原言語のテキストＷS へと翻訳される確率を表す。また、翻訳モデルに、目的言語のテキストＷT の各単語が原言語のテキストＷS のどの単語のインデックスに対応するかを表すアライメントＡという概念が導入されることにより、翻訳モデルは、次式（３）のように表される。
【００２１】
【数３】
0004006297.tif 000004
【００２２】
図２は、目的言語のテキストＷT である英語の文" Could you recommend another hotel"と、原言語のテキストＷS である日本語文の「他のホテルを紹介していただけますか」とにおける、アライメントの例を示している。例えば、日本語文におけるインデックス１の「他」とインデックス２の「の」が、英語文のインデックス４の" another"へと対応づけられている。
【００２３】
また、英語文のインデックス０にあるNULLシンボルも単語の一つであり、「ます」や「か」のように、原言語のテキストＷS である日本語文に対応する単語がない場合に対応づけられている。
【００２４】
〔１．１〕翻訳モデルの構成
【００２５】
アライメントを介した翻訳モデルＰ（ＷS ，Ａ｜ＷT ）はさらに分解され、例えば、次式（４）で示すように、以下のように４つのモデルから構成される（上記文献１参照）。
【００２６】
【数４】
0004006297.tif 000005
【００２７】
（１）Lexical モデル：t(ＷSAi ｜ＷTi)
ある目的言語の単語ＷTiが原言語の単語ＷSAi へと翻訳される確率。
【００２８】
（２）Fertility モデル：n(φi ｜ＷTi)
ある目的言語の単語ＷTiがφi 個の原言語の単語と対応される確率。
【００２９】
（３）Distortionモデル：d(Ａ｜ＷT ，ＷS ） 
ＷT とＷS が与えられたときのアライメントがＡである確率。歪みモデルを  さらに分解した複雑なモデルも定義されている（上記文献１参照）。
【００３０】
（４）NULLモデル：上記式（４）の右辺の最後の項
ある原言語のφ0 個の単語が NULL へと対応づけられる確率。
【００３１】
〔１．２〕探索問題
【００３２】
統計機械翻訳における探索問題は、入力文ＷS が与えられたときに、翻訳モデルＰ（ＷS ｜ＷT ）＝ΣＰ（ＷS ，Ａ｜ＷT ）と言語モデルＰ（ＷT ）とから最大尤度の出力文ＷT を発見する問題として扱われる。ただし、可能なＡの空間は、次式（５）で示されるように、非常に大きく、翻訳を決定する場合、その近似値、Ｐ（ＷS ｜ＷT ）≒Ｐ（ＷS ，Ａ｜ＷT ） が用いられる。
【００３３】
【数５】
0004006297.tif 000006
【００３４】
統計機械翻訳における探索問題は、単語の単位の翻訳だけでなく、並び替えの問題も含んでいることからNP＿Completeであることが知られている（上記文献２参照）。過去の研究においては、出力を文頭から生成する制約を加え、プルーニング（剪定）を行うことによりデコーディングアルゴリズムを実現している（上記文献３〜８参照）。ただし、プルーニングも原言語と目的言語とがほぼ線形に対応づけられていることを仮定しており、日本語と英語間の翻訳といった語順の相違が大きい言語間の翻訳を想定していない。
【００３５】
以下、出力の方向を考慮したデコーディングアルゴリズムについて説明する。
【００３６】
〔２〕デコーディングアルゴリズム
【００３７】
本発明によるデコーディングアルゴリズムは、Tillman （上記文献７参照）やOch （上記文献４参照）らによるビームサーチアルゴリズムに基づいており、また、仮説に適用される操作はBerger（上記文献３参照）、Och （上記文献４参照）やGermann （上記文献８参照）らに基づいている。
【００３８】
まず、デコーディングアルゴリズムで用いられる仮説およびマルチスタックについて説明する。
【００３９】
仮説ｈは、（ＷT ，Ａ，Ｃ，ｓ，open/close) のように表現される。仮説の各要素は次のように定義される。
【００４０】
ＷT ：部分出力文
Ａ  ：部分的に決定されたアライメント
Ｃ  ：既に処理された入力文のインデックスの集合
ｓ  ：スコア
open/close：openな仮説とclose な仮説との識別子であり、０はopenな仮説を表し、１はclose な仮説を表す。
【００４１】
openな仮説では、入力文の単語を既に得られた部分出力文のある単語と対応づけることにより、fertility （出力文の１つの単語に対応付けられる入力文の単語の数）を増大させる操作が行われる。close な仮説では、既に得られた部分出力文に対して単語列ＷT ’を追加する操作が行われる。この単語列ＷT ’は、fertility が１以上の単語１個とfertility がゼロの単語の列から構成される。
【００４２】
マルチスタックは、スタックの集合であり、入力文の単語のインデックスの各部分集合（各組み合わせ）に対応したスタックが存在している。例えば、入力文が、インデックス１の単語、インデックス２の単語およびインデックス３の単語の３つの単語から構成されている場合には、入力文の単語のインデックスの各部分集合に応じた、Ｃ＝｛｝、Ｃ＝｛１｝、Ｃ＝｛２｝、Ｃ＝｛３｝、Ｃ＝｛１，２｝、Ｃ＝｛１，３｝、Ｃ＝｛２，３｝、Ｃ＝｛１，２，３｝の７個のスタックが用意される。
【００４３】
各スタックには、デコーディングアルゴリズムによって生成された仮説が格納される。各スタックにおいては、スコアの高い順に、仮説がソートされる。スタックに格納されている仮説の数が所定の閾値（max-stack-size) に達している場合に、新たな仮説を格納しようとする場合には、それらの仮説の中でスコアの最も低い仮説を捨てることにより、常にmax-stack-sizeの数の仮説を格納するようにしている。
【００４４】
〔２．１〕全体フロー
【００４５】
図３は、デコーディングアルゴリズムを示している。
【００４６】
まず、入力文Ｗs ＝Ｗs1, Ｗs2, …Ｗs2m を入力する（ステップ１）。入力文Ｗs の入力長（単語数）はｍである。
【００４７】
次に初期化処理を行う（ステップ２）。初期化処理においては、初期仮説ｈ0 が生成されて、Ｃ＝｛｝のスタックに格納される。初期仮説ｈ0 では、ＷT は存在せず（ＷT ＝””）、アライメントＡは−１に設定され、入力分のインデックスの集合Ｃは空（｛｝）に設定され、スコアｓは１．０に設定され、open/close識別子はclose を表す”１”に設定される。したがって、初期仮説ｈ0 は、（ＷT ＝””，Ａ＝（−１，…−１），Ｃ＝｛｝，ｓ＝１．０，open/close＝１）となる。また、変数ｃが０に設定される。なお、以下の説明において、｜Ｃ｜は、入力文の単語のインデックスの各部分集合の要素数を表すものとする。
【００４８】
次に、｜Ｃ｜＝ｃであるスタック（要素数がｃ個である部分集合に対応するスタック）でまだ選択されていないスタックが存在するか否かを判別する（ステップ３）。
【００４９】
｜Ｃ｜＝ｃであるスタックでまだ選択されていないスタックが存在する場合には、そのうちの１つのスタックを選択する（ステップ４）。そして、選択したスタック内にまだ読み出されていない仮説が存在するか否かを判別する（ステップ５）。選択したスタック内にまだ読み出されてない仮説が存在する場合には、まだ読み出されてない仮説ｈを１つだけ読み出す（ステップ６）。そして、仮説生成処理を実行する（ステップ７）。そして、ステップ５に戻る。
【００５０】
上記ステップ３において、｜Ｃ｜＝ｃであるスタックでまだ選択されていないスタックが存在しない場合には、変数ｃの値を１だけインクリメント（＋１）する（ステップ８）。そして、ｃがｍに達したか否かを判定する（ステップ９）。ｃがｍに達していない場合（ｃ＜ｍ）には、ステップ３に戻る。
【００５１】
上記ステップ５において、上記ステップ４で選択したスタック内にまだ読み出されてない仮説が存在しない場合には、ステップ３に戻る。
【００５２】
上記ステップ９において、ｃがｍに達していると判別した場合（ｃ＝ｍ）には、今回の処理を終了する。この時点において、｜Ｃ｜＝ｍであるスタックの中に解が存在することになる。
【００５３】
〔２．２〕仮説生成処理手順
【００５４】
図４は、図３のステップ７の仮説生成処理手順を示している。
【００５５】
以下の説明において、ｊは入力文ＷS の単語のインデックスを表す変数であり、ｉは出力文ＷT の単語のインデックスを表す変数であるとする。
【００５６】
上記ステップ６で読み出された仮説ｈを入力する（ステップ１１）。変数ｊとして１を設定する（ステップ１２）。
【００５７】
そして、ｊが（ｍ＋１）に達したか否かを判定する（ステップ１３）。ｊが（ｍ＋１）に達していない場合（ｊ≦ｍ）には、ｊが入力仮説ｈ内のＣに含まれていないか否かを判定する（ステップ１４）。
【００５８】
ｊが入力仮説ｈ内のＣに含まれていない場合には、入力仮説ｈ内のopen/close識別子がopen( ＝0)であるか、close(＝1)であるかを判定する（ステップ１５）。
【００５９】
入力仮説ｈがopenである場合には、openに対応した仮説生成処理を行う（ステップ１６）。入力仮説ｈがclose である場合には、close に対応した仮説生成処理を行う（ステップ１７）。openに対応した仮説生成処理およびclose に対応した仮説生成処理の詳細については、後述する。
【００６０】
ステップ１６またはステップ１７によって新たな仮説が生成された場合には、生成された新たな仮説を、その仮説中のＣに対応するスタックに格納する（ステップ１８）。
【００６１】
そして、変数ｊの値を１だけインクリメント（＋１）した後（ステップ１９）、ステップ１３に移行する。
【００６２】
上記ステップ１４において、ｊがＣに含まれていると判定した場合には、ステップ１９に移行する。
【００６３】
上記ステップ１３において、ｊが（ｍ＋１）に達していると判定した場合（ｊ＝（ｍ＋１））には、今回の仮説生成処理は終了する。つまり、図３のステップ５に戻る。
【００６４】
以下、openに対応した仮説生成処理およびclose に対応した仮説生成処理について説明する。
【００６５】
〔２．３〕openに対応した仮説生成処理
【００６６】
openに対応した仮説生成処理では、以下のような仮説を、openとclose との２種類生成する。
【００６７】
入力文ＷS のうちのインデックスｊにある単語を、インデックスｉにある部分出力文の単語に対応させる。
【００６８】
この実施の形態では、部分出力文を文末から生成する（right-to-left デコーディング) ため、インデックスｉにある出力単語は部分出力文ＷT における最初の単語（ｉ＝１）となる。したがって、図５に示すように、入力文ＷS のうちのインデックスｊにある単語ＷSjが、入力仮説ｈ内の部分出力文ＷT における最初の単語ＷT1（ｉ＝１）に対応づけられる。
【００６９】
この場合には、仮説の要素である部分出力文ＷT は変更されず、アライメントＡが変更される。つまり、Ａ[ j ] として、ｉ＝１が代入される（Ａ[ j ] ←ｉ（＝１））。また、仮説の要素であるＣとして、Ｃ∪｛ｊ｝が設定される（Ｃ←Ｃ∪｛ｊ｝）。
【００７０】
なお、Ｃ∪｛ｊ｝は、例えば、Ｃが｛｝でかつｊが１であれば、｛｝∪｛１｝＝｛１｝となり、例えば、Ｃが｛１｝でかつｊが２であれば、｛１｝∪｛２｝＝｛１，２｝となり、例えば、Ｃが｛２，３｝でかつｊが１であれば、｛２，３｝∪｛１｝＝｛１，２，３｝となる。
【００７１】
仮説の要素であるスコアｓは、よく知られているように次式（６）に基づいて算出される。
【００７２】
【数６】
0004006297.tif 000007
【００７３】
ここで、ｆをＷT [i] の新しいferrility とする。また、Distortionモデル( 歪みモデル) の確率を再計算する。
【００７４】
以上のような要素を持ち、かつopen/close識別子がopen（＝０）である仮説と、open/close識別子がclose(＝１）である仮説とが生成される。
【００７５】
なお、従来のように部分出力文を文頭から生成する（left-to-right デコーディング) においては、インデックスｉにある出力単語は部分出力文ＷT における最後の単語（ｉ＝｜ＷT ｜）となる。したがって、図６に示すように、入力文ＷS のうちのインデックスｊにある単語ＷSjが、入力仮説内の部分出力文ＷT における最後の単語ＷTl（ｉ＝｜ＷT ｜）に対応づけられる。この結果、Ａ[ j ] として、ｉ＝｜ＷT ｜が代入される（Ａ[ j ] ←ｉ（＝｜ＷT ｜）。
【００７６】
〔２．４〕close に対応した仮説生成処理
【００７７】
close に対応した仮説生成処理では、NULLへ対応された仮説と、文字列の挿入および挿入文字列へ対応づけられた仮説とを生成する。
【００７８】
〔２．４．１〕NULLへ対応された仮説
【００７９】
入力文のうち、インデックスｊにある単語を、NULL（インデックス０にある出力単語）に対応させる。
【００８０】
つまり、Ａ[ j ] として、０が代入される（Ａ[ j ] ←０）。また、仮説の要素であるＣとして、Ｃ∪｛ｊ｝が設定される（Ｃ←Ｃ∪｛ｊ｝）。仮説の要素であるopenclose 識別子はclose （＝１）とする。仮説の要素であるスコアｓは、よく知られているように次式（７）に基づいて算出される。
【００８１】
【数７】
0004006297.tif 000008
【００８２】
ここで、ｆをNULLの新しいferrility とする。
【００８３】
〔２．４．２〕文字列の挿入および挿入文字列へ対応づけられた仮説
【００８４】
以下のような仮説を、openとclose との２種類生成する。
【００８５】
まず、入力仮説内の部分出力文ＷT に新しい文字列ＷT ’を挿入する。この実施の形態では、部分出力文を文末から生成する（right-to-left デコーディング) ため、図７に示すように、入力仮説内の部分出力文ＷT の左側に新しい文字列ＷT ’を挿入する（ＷT ←ＷT ’＋ＷT ）。
【００８６】
また、入力文ＷS のうち、インデックスｊにある単語ＷSjを、インデックスｉにある出力単語に対応させる。この実施の形態では、部分出力文を文末から生成する（right-to-left デコーディング) ため、図７に示すように、インデックスｉにある出力単語は新しいＷT （図７のＷT ’＋ＷT ）における最初の単語ＷT1’（ｉ＝１）となる。したがって、アライメントＡ[ j ] として、ｉ＝１が代入される（Ａ[ j ] ←ｉ（＝１））。
【００８７】
また、仮説の要素であるＣとして、Ｃ∪｛ｊ｝が設定される（Ｃ←Ｃ∪｛ｊ｝）。仮説の要素であるスコアｓは、よく知られているように次式（８）に基づいて算出される。
【００８８】
【数８】
0004006297.tif 000009
【００８９】
Ｐlmは、言語モデルによるスコアであり、もし、ＷT [i’] において、i ’≦０の場合、ＷT [i’] ＝ＢＯＳ(Beggining of Sentence Marker)となる。
【００９０】
以上のような要素を持ち、かつopen/close識別子がopen( ＝０）である仮説と、open/close識別子がclose(＝１）である仮説とが生成される。
【００９１】
なお、新しい文字列ＷT ’は複数生成される。そして、新しい文字列毎に、上記のようにして、２つずつ仮説が生成される。新しい文字列ＷT ’の生成方法については、上記文献３，４，５に説明されている。
【００９２】
従来のように部分出力文を文頭から生成する（left-to-right デコーディング) においては、文字列ＷT を挿入する場合、図８に示すように、入力仮説内の部分出力文ＷT の右側に新しい文字列ＷT ’を挿入する（ＷT ←ＷT ＋ＷT ’）。また、インデックスｉにある出力単語は新しいＷT （図８のＷT ＋ＷT ’）における最後の単語ＷTl’（ｉ＝｜ＷT ｜）となる。この結果、Ａ[ j ] として、ｉ＝｜ＷT ｜が代入される（Ａ[ j ] ←ｉ（＝｜ＷT ｜）。
【００９３】
〔２．５〕入力文ＷS の入力長ｍが３の場合の流れについの説明
【００９４】
入力文ＷS の入力長ｍが３の場合の、デコーディングアルゴリズムの流れについて簡単に説明しておく。
【００９５】
まず、Ｃ＝｛｝に対応するスタックに、初期仮説ｈ0 ＝（ＷT ＝””，Ａ＝（−１，…−１），Ｃ＝｛｝，ｓ＝１．０，open/close＝１）が格納される（図３のステップ１〜２）。
【００９６】
そして、図３のステップ６において、Ｃ＝｛｝に対応するスタックから初期仮説ｈ0 が取り出される。そして、図４のステップ１７のclose に対応した仮説生成処理によって、ｊ＝１，２、３それぞれに対応した新たな仮説が生成され、Ｃ＝｛１｝、Ｃ＝｛２｝、Ｃ＝｛３｝それぞれに対応するスタックに、新たな仮説が格納される。
【００９７】
次に、Ｃ＝｛１｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝２、３それぞれに対応した新たな仮説が生成され、Ｃ＝｛１，２｝、Ｃ＝｛１，３｝それぞれに対応するスタックに、新たな仮説が格納される。
【００９８】
同様に、Ｃ＝｛２｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝１，３に対応した新たな仮説が生成され、Ｃ＝｛１，２｝、Ｃ＝｛２，３｝に対応するスタックに、新たな仮説が格納される。
【００９９】
同様に、Ｃ＝｛３｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝１，２に対応した新たな仮説が生成され、Ｃ＝｛１，３｝、Ｃ＝｛２，３｝に対応するスタックに、新たな仮説が格納される。
【０１００】
次に、Ｃ＝｛１，２｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝３に対応した新たな仮説が生成され、Ｃ＝｛１，２，３｝に対応するスタックに、新たな仮説が格納される。
【０１０１】
次に、Ｃ＝｛１，３｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝２に対応した新たな仮説が生成され、Ｃ＝｛１，２，３｝に対応するスタックに、新たな仮説が格納される。
【０１０２】
次に、Ｃ＝｛２，３｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝１に対応した新たな仮説が生成され、Ｃ＝｛１，２，３｝に対応するスタックに、新たな仮説が格納される。
【０１０３】
この結果、Ｃ＝｛１，２，３｝に対応するスタックに、解（翻訳結果）がスコアの高い順番に格納される。
【０１０４】
〔３〕デコーディング方向による影響
【０１０５】
従来のleft-to-right デコーディングアルゴリズムにおいては、入力単語を処理し、対応する翻訳を単語単位に決定して部分出力文を文頭から生成する。このような挙動により、言語モデルや翻訳モデルは文頭からスコアリングを行うことにより、「良い仮説」と「悪い仮説」とを区別する力が大きくなることが考えられる。
【０１０６】
例えば、英語やドイツ語、フランス語のように文頭からの語順の制約が強い言語を目的言語として翻訳を行った場合、文頭からのスコアリングによる制約が強くなり、ビームサーチのプルーニングを行っても出力の質が落ちることがない。逆に、このような言語に対して本実施の形態のようにright-to-left デコーディング行うと、仮説間のスコアの差が小さく、仮説数が増大し、プルーニングによる影響が大きくなる。
【０１０７】
日本語のような文末に語順の制約がある場合、そのような言語を目的言語としてright-to-left デコーディングを行うとスコアの差が大きくなり、left-to-right に行うとスコアの差が小さくなると考えられる。したがって、文末に語順の制約がある言語が目的言語である場合には、right-to-left にデコーディングを行うことが好ましい。
【０１０８】
〔４〕実験
【０１０９】
今回行った実験のコーパスは、大規模旅行会話集（文献９参照）から抽出した172,481 の日英の対訳文であり、その統計情報を表１に示す。コーパスから152,183 文からなるトレーニングセット、検証セットを10,148文、さらにテストセット10,150文を取り出した。
【０１１０】
文献９：Takezawa,T., Sumita,E., Sugaya,F., Yamamoto,H. and Yamamoto,S.: Toward a Broad-coverage Bilingual Corpus for Speech Translation of Travel Conversations in the Real World, Proc. of LREC 2002, Las Palmas, CanaryIslands, Spain, pp.147-152(2002).
【０１１１】
【表１】
0004006297.tif 000010
【０１１２】
翻訳モデルは日英、英日方向、どちらもIBM Model-1 からIBM Model-4 までブートストラップしてトレーニングを行い、途中にHMM Model によるトレーニングを行っている（文献１０参照）。また、検証セットによるクロスバリデーションを行いながらトレーニングを繰り返した。IBM Model-4 においては、品詞を単語クラスとして用いた。
【０１１３】
文献１０： Och,F.J., Tillmann,C. and Ney,H.: Improved Alignment Models for Statistical Machine Translation, Proceedings of the Joint Conf. of  Empirical Methods in Natural Language Processing and Very Large Corpora, University of Maryland, College Park,MD(1999).
【０１１４】
トレーニングコーパスのビテルビアライメントから、fertility がゼロとなる単語列を取り出し、頻度が10未満のものを取り除いた。また、テストセットから文長が6 、8 、10である、それぞれ50文、合計150 の日本語、英語の文を取り出し、上記の２つのアルゴリズムによるデコーディングの実験を行った。
【０１１５】
翻訳結果を評価するに当たって、以下の基準を用いた。
【０１１６】
・単語誤り率(WER):  挿入、削除、置換に対してペナルティを１として計算。
【０１１７】
・位置独立単語誤り率(PER):  WER では、実際の翻訳に起こりうる並び替えに対してペナルティが大きくなる。従って、PER では位置の情報を無視し、出力単語の集合の正しさの評価を行う（上記文献４参照と文献１１参照）。
文献１１：Watanabe,T., Imamura,K. and Sumita,E.: Statistical MachineTranslation Based on Hierarchical Phrase Alignment, Proc. of TMI 2002,Keihanna, Japan(2002).
【０１１８】
・BLEUスコア: 正解集合の全てに対してN-gramの正解率を計算するものであり、短い出力に対してペナルティを与えている（文献１２参照）。
文献１２： Papineni,K., Roukos,S., Ward,T. and Zhu,W.J.: Bleu: a Method for Automatic Evaluation of Machine Translation, Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics(ACL),pp.311-318(2002).
【０１１９】
・NISTスコア: BLUEと同様なスコアであるが、正解率を正解集合のN-gramに対する平均出力単語情報量として表現している（文献１３参照）。
文献１３： Automatic Evaluation of Machine Translation Quality using N-gram Co-Occurrence Statistics, http://www.nist.gov/speech/tests/mt/doc/ngram-study.pdf(2002) ．
【０１２０】
・主観評価(SE): 翻訳結果を人手でＡ、Ｂ、Ｃ、Ｄと４段階にランク付けをする（文献１４参照）。
文献１４：Sumita,E., Yamada,S., Yamamoto,K., Paul,M., Kashioka,H., Ishikawa,K.and Shirai,S.: Solutions to Problems Inherent in Spoken-languageTranslation: The ATR-MATRIX Approch, Machine Translation Summit VII, PP.229-235(1999).
【０１２１】
・探索誤り率(SER):  翻訳の正さあるいは誤り以外に、各デコーディングアルゴリズムが翻訳モデルと言語モデルから最適解を得られたかどうかを評価した。出力結果のうち、スコアが最も高い出力の集合を正解集合として、誤り率を求めた。
【０１２２】
表２は、left-to-right(LtoR) とright-to-left(RtoL) とのデコーディングアルゴリズムの翻訳結果を示す。日英、英日の翻訳例をそれぞれ図９、図１０に示す。
【０１２３】
【表２】
0004006297.tif 000011
【０１２４】
〔５〕考察
表２における探索誤り率(SER) から、日英翻訳については、right-to-left デコーディングアルゴリズムより、left-to-right デコーディングアルゴリズムが良く、また、英日翻訳ではその逆の結果が得られた。このことから、言語モデル、翻訳モデルに基づいて翻訳結果を得るに当たって、出力文の言語の特性に合わせて出力の方向を制約する手法の有効性が確認された。
【０１２５】
翻訳結果の客観評価値（WER/PER/BLEU/NIST)では、日英翻訳でアルゴリズム間に差異が認められなかった。英日翻訳においては、right-to-left デコーディングアルゴリズムは、WER/PER の点において優れていることが確認された。
【０１２６】
主観評価(SE)では、日英翻訳において、left-to-right デコーディングアルゴリズムは、right-to-left デコーディングアルゴリズムよりＡランクの文の割合が増加している。ただし、英日翻訳では、アルゴリズム間で主観評価(SE)はほぼ変わらなかった。
【０１２７】
【発明の効果】
この発明によれば、文末に語順の制約が強いという性質をもつ言語が目的言語である場合に、好適な翻訳結果が得られるようになる。
【図面の簡単な説明】
【図１】統計的機械翻訳モデルを説明するための模式図である。
【図２】アライメントの例を示す模式図である。
【図３】デコーディングアルゴリズムを示すフローチャートである。
【図４】図３のステップ７の仮説生成処理手順を示すフローチャートである。
【図５】  right-to-left デコーディングによる、openに対応した仮説生成処理を説明するための模式図である。
【図６】  left-to-right デコーディングによる、openに対応した仮説生成処理を説明するための模式図である。
【図７】  right-to-left デコーディングによる、close に対応した仮説生成処理を説明するための模式図である。
【図８】  left-to-right デコーディングによる、close に対応した仮説生成処理を説明するための模式図である。
【図９】実験によって得られた日英翻訳結果の例を示す模式図である。
【図１０】実験によって得られた英日翻訳結果の例を示す模式図である。
【図１】
0004006297.tif 000012
【図２】
0004006297.tif 000013
【図３】
0004006297.tif 000014
【図４】
0004006297.tif 000015
【図５】
0004006297.tif 000016
【図６】
0004006297.tif 000017
【図７】
0004006297.tif 000018
【図８】
0004006297.tif 000019
【図９】
0004006297.tif 000020
【図１０】
0004006297.tif 000021