(57)【要約】【課題】この発明は、文末に語順の制約が強いという性質をもつ言語が目的言語である場合に、好適な翻訳結果が得られる統計的機械翻訳方法を提供することを目的とする。【解決手段】入力文に対して翻訳モデルと言語モデルとから出力文を発見していくために行なわれるデコーディング時において、出力文を文末から生成していく。実験の結果、英日翻訳においては、出力文を先頭から生成していくよりも、出力文を文末から生成していく方が好ましい翻訳結果が得られた。【選択図】　図３
2004086343.tif 000002
【特許請求の範囲】
【請求項１】
入力文に対して翻訳モデルと言語モデルとから出力文を発見していくために行なわれるデコーディング時において、出力文を文末から生成していくことを特徴とする統計的機械翻訳方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、統計的機械翻訳方法に関する。
【０００２】
【従来の技術】
近年、コーパスを用いた手法の一つである統計的機械翻訳システムの研究が盛んに行われるようになってきた。この統計的機械翻訳においては、原言語が与えられたときに目的言語へと翻訳する問題を、最大尤度の解を発見する問題として扱われるようになった。この問題はベーズルールにより最大事後確率の問題としてとらえられ、統計的機械翻訳システムは、翻訳モデルというチャネルソース言語をチャネルターゲット言語へと翻訳する確率、チャネルソース言語の尤度を表した言語モデル、さらに、入力文が与えられたときに出力を発見するデコーダの３つの要素で構成されるようになった（文献１参照）。
【０００３】
文献１：Ｂｒｏｗｎ，Ｐ．Ｆ．，　Ｐｉｅｔｒａ，　Ｓ．Ａ．Ｄ．，　Ｖ．Ｌ．Ｄ．　ａｎｄ　Ｍｅｒｃｅｒ，　Ｒ．Ｌ．：　Ｔｈｅ　Ｍａｔｈｅｍａｔｉｃｓ　ｏｆ　Ｓｔａｔｉｓｔｉｃａｌ　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ：　Ｐａｒａｍｅｔｅｒ　Ｅｓｔｉｍａｔｉｏｎ，　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｌｉｎｇｕｉｓｔｉｃｓ，　Ｖｏｌ．１９，　Ｎｏ．２，ｐｐ．２６３−３１１（１９９３）．
【０００４】
翻訳モデルでは、確率値を推定する効率的なアルゴリズムが知られているが、デコーディングはＮＰ＿Ｃｏｍｐｌｅｔｅであることが知られている（文献２参照）。
【０００５】
文献２：　Ｋｎｉｇｈｔ，Ｋ．：　Ｄｅｃｏｄｉｎｇ　Ｃｏｍｐｌｅｘｉｔｙ　ｉｎ　Ｗｏｒｄ−Ｒｅｐｌａｃｅｍｅｎｔ　Ｔｒａｎｓｌａｔｉｏｎ　Ｍｏｄｅｌｓ，　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｌｉｎｇｕｉｓｔｉｃｓ，　Ｖｏｌ．２５，　Ｎｏ．４，　ｐｐ．６０７−６１５（１９９９）．
【０００６】
デコーディングアルゴリズムとして、現在まで様々なアルゴリズム、例えばスタックデコーディングアルゴリズム（文献３参照）、Ａ＊　探索アルゴリズム（文献４，５参照）、ＤＰアルゴリズム（文献６，７参照）が提唱されてきた。
【０００７】
文献３：　Ｂｅｒｇｅｒ，Ａ．，　Ｂｒｏｗｎ，Ｐ．，　Ｐｉｅｔｒａ，Ｓ．，　Ｐｉｅｔｒａ，Ｖ．，　Ｇｉｌｌｅｔｔ，Ｊ．，　Ｋｅｈｌｅｒ，Ａ．　ａｎｄ　Ｍｅｒｃｅｒ，Ｒ．：　Ｌａｎｇｕａｇｅ　Ｔｌａｎｓｌａｔｉｏｎ　Ａｐｐａｒａｔｕｓ　ａｎｄ　Ｍｅｔｈｏｄ　ｏｆ　Ｕｓｉｎｇ　Ｃｏｎｔｅｘｔ−Ｂａｓｅｄ　Ｔｒａｎｓｌａｔｉｏｎ　Ｍｏｄｅｌｓ，　Ｔｅｃｈｎｉｃａｌ　ｒｅｐｏｒｔ，　Ｕｎｉｔｅｄ　Ｓｔａｔｅｓ　Ｐａｔｅｎｔ，　Ｐａｔｅｎｔ　Ｎｕｍｂｅｒ　５５１０９８１（１９９６）．
文献４：　Ｏｃｈ，Ｆ．Ｊ．，　Ｕｅｆｆｉｎｇ，Ｎ．　ａｎｄ　Ｎｅｙ，Ｈ．：　Ａｎ　Ｅｆｆｉｃｉｅｎｔ　Ａ＊　Ｓｅａｒｃｈ　Ａｌｇｏｒｉｔｈｍ　ｆｏｒ　Ｓｔａｔｉｓｔｉｃａｌ　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ，　Ｐｒｏｃ．　ｏｆ　ｔｈｅ　ＡＣＬ−２００１　Ｗｏｒｋｓｈｏｐｏｎ　　Ｄａｔａ−Ｄｒｉｖｅｎ　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ，　Ｔｏｕｌｏｕｓｅ，　Ｆｒａｎｃｅ，　ｐｐ．５５−６２（２００１）．
文献５：Ｗａｎｇ，Ｙ．−Ｙ．　ａｎｄ　Ｗａｉｂｅｌ，　Ａ．：　Ｄｅｃｏｄｉｎｇ　Ａｌｇｏｒｉｔｈｍ　ｉｎ　Ｓｔａｔｉｓｔｉｃａｌ　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ，　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３５ｔｈ　Ａｎｎｕａｌ　Ｍｅｅｔｉｎｇ　ｏｆ　ｔｈｅ　Ａｓｓｏｃｉａｔｉｏｎ　ｆｏｒ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｌｉｎｇｕｉｓｔｉｃｓ（１９９７）．
文献６：　Ｇａｒｃｉａ−Ｖａｒｅａ，　Ｉ．　ａｎｄ　Ｃａｓａｃｕｂｅｒｔａ，　Ｆ．：　Ｓｅａｃｈ　Ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　Ｓｔａｔｉｓｔｉｃａｌ　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｄｙｎａｍｉｃ　Ｐｒｏｇｒａｍｍｉｎｇ　ａｎｄ　ＰｒｕｎｉｎｇＴｅｃｈｎｉｑｕｅｓ，　ＭＴ　Ｓｕｍｍｉｔ　ＶＩＩＩ，　Ｓａｎｔｉａｇｏ　ｄｅ　Ｃｏｍｐｏｓｔｅｌａ，　Ｇａｌｉｃｉａ，　Ｓｐａｉｎ　（２００１）．
文献７：Ｔｉｌｌｍａｎｎ，Ｃ．　ａｎｄ　Ｎｅｙ，　Ｈ．：　Ｗｏｒｄ　Ｒｅ−ｏｒｄｅｒｉｎｇ　ａｎｄ　ＤＰ−ｂａｓｅｄ　Ｓｅａｒｃｈ　ｉｎ　Ｓｔａｔｉｏｎａｌ　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ，　Ｐｒｏｃ．　ｏｆ　ｔｈｅ　ＣＯＬＩＮＧ　２０００（２０００）．
【０００８】
これらは、入力文に対して出力文を文頭から生成し、原言語文と目的言語文とがほぼ線形に対応づけられることを仮定したプルーニング戦略を取り入れたものであった。このようなアルゴリズムにおいては、例えば日本語と英語のように、性質の異なる言語の翻訳には対応できなかった。
【０００９】
また、Ｇｅｒｍａｍｍ　らはヒルクライミングアルゴリズムとインテジャー解を示している（文献８参照）。前者の手法では、満足な解が得られないことが分かっており、また、後者の手法では現実的に処理速度の問題で、解を得ることができない。
【００１０】
文献８：　Ｇｅｒｍａｎ，Ｕ．，　Ｊａｈｒ，Ｍ．，　Ｋｎｉｇｈｔ，Ｋ．，　Ｍａｒｃｕ，Ｄ．　ａｎｄ　Ｙａｍａｄａ，Ｋ．：　ＦａｓｔＤｅｃｏｄｉｎｇ　ａｎｄ　Ｏｐｔｉｍａｌ　Ｄｅｃｏｄｉｎｇ　ｆｏｒ　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ，　Ｐｒｏｃ．　ｏｆ　ＡＣＬ−０１，　Ｔｏｕｌｏｕｓｅ，　Ｆｒａｎｃｅ（２００１）．
【００１１】
【発明が解決しようとする課題】
この発明は、文末に語順の制約が強いという性質をもつ言語が目的言語である場合に、好適な翻訳結果が得られる統計的機械翻訳方法を提供することを目的とする。
【００１２】
【課題を解決するための手段】
この発明による統計的機械翻訳方法は、入力文に対して翻訳モデルと言語モデルとから出力文を発見していくために行なわれるデコーディング時において、出力文を文末から生成していくことを特徴とする。
【００１３】
【発明の実施の形態】
以下、図面を参照して、この発明の実施の形態について説明する。
【００１４】
〔１〕統計的機械翻訳の概要についての説明
【００１５】
統計的機械翻訳においては、ある原言語のテキストＷＳ　が与えられているときにある目的言語のテキストＷＴ　へと翻訳する問題を、最大尤度の出力（翻訳結果）を発見する問題としてとらえられ、次式（１）のように表現される。
【００１６】
【数１】
2004086343.tif 000003
【００１７】
上記式（１）にベーズルールを適用することにより、上記の問題は、次式（２）に示すように、チャネルモデルにおける最大事後確率の解を求める問題に置き換えられる。
【００１８】
【数２】
2004086343.tif 000004
【００１９】
このため、翻訳とは、図１（ａ）に示すように「翻訳家の知識Ｐ（ＷＴ　｜ＷＳ　）を基にして原言語のテキストＷＳ　を翻訳」する問題として扱われるのではなく、図１（ｂ）に示すように「ある確率Ｐ（ＷＴ　）で起こりうる目的言語のテキストＷＴ　が、チャネルにより、（　Ｐ（ＷＴ　｜ＷＳ　）　）、ＷＳ　として出力された」と仮定して、目的言語のテキストＷＴ　を原言語のテキストＷＳ　から推測する問題として扱われるようになった（上記文献１参照）。
【００２０】
Ｐ（ＷＴ　）　は言語モデル（事前確立）であり、目的言語のテキストＷＴ　の尤度を示す。Ｐ（ＷＴ　｜ＷＳ　）は翻訳モデル（事後確立）であり、目的言語のテキストＷＴ　が原言語のテキストＷＳ　へと翻訳される確率を表す。また、翻訳モデルに、目的言語のテキストＷＴ　の各単語が原言語のテキストＷＳ　のどの単語のインデックスに対応するかを表すアライメントＡという概念が導入されることにより、翻訳モデルは、次式（３）のように表される。
【００２１】
【数３】
2004086343.tif 000005
【００２２】
図２は、目的言語のテキストＷＴ　である英語の文”Ｃｏｕｌｄ　ｙｏｕ　ｒｅｃｏｍｍｅｄ　ａｎｏｔｈｅｒ　ｈｏｔｅｌ”と、原言語のテキストＷＳ　である日本語文の「他のホテルを紹介していただけますか」とにおける、アライメントの例を示している。例えば、日本語文におけるインデックス１の「他」とインデックス２の「の」が、英語文のインデックス４の”　ａｎｏｔｈｅｒ”へと対応づけられている。
【００２３】
また、英語文のインデックス０にあるＮＵＬＬシンボルも単語の一つであり、「ます」や「か」のように、原言語のテキストＷＳ　である日本語文に対応する単語がない場合に対応づけられている。
【００２４】
〔１．１〕翻訳モデルの構成
【００２５】
アライメントを介した翻訳モデルＰ（ＷＳ　，Ａ｜ＷＴ　）はさらに分解され、例えば、次式（４）で示すように、以下のように４つのモデルから構成される（上記文献１参照）。
【００２６】
【数４】
2004086343.tif 000006
【００２７】
（１）Ｌｅｘｉｃａｌ　モデル：ｔ（ＷＳＡｉ　｜ＷＴｉ）
ある目的言語の単語ＷＴｉが原言語の単語ＷＳＡｉ　へと翻訳される確率。
【００２８】
（２）Ｆｅｒｔｉｌｉｔｙ　モデル：ｎ（φｉ　｜ＷＴｉ）
ある目的言語の単語ＷＴｉがφｉ　個の原言語の単語と対応される確率。
【００２９】
（３）Ｄｉｓｔｏｒｔｉｏｎモデル：ｄ（Ａ｜ＷＴ　，ＷＳ　）　　
ＷＴ　とＷＳ　が与えられたときのアライメントがＡである確率。歪みモデルを　　さらに分解した複雑なモデルも定義されている（上記文献１参照）。
【００３０】
（４）ＮＵＬＬモデル：上記式（４）の右辺の最後の項
ある原言語のφ０　個の単語が　ＮＵＬＬ　へと対応づけられる確率。
【００３１】
〔１．２〕探索問題
【００３２】
統計機械翻訳における探索問題は、入力文ＷＳ　が与えられたときに、翻訳モデルＰ（ＷＳ　｜ＷＴ　）＝ΣＰ（ＷＳ　，Ａ｜ＷＴ　）と言語モデルＰ（ＷＴ　）とから最大尤度の出力文ＷＴ　を発見する問題として扱われる。ただし、可能なＡの空間は、次式（５）で示されるように、非常に大きく、翻訳を決定する場合、その近似値、Ｐ（ＷＳ　｜ＷＴ　）≒Ｐ（ＷＳ　，Ａ｜ＷＴ　）　　が用いられる。
【００３３】
【数５】
2004086343.tif 000007
【００３４】
統計機械翻訳における探索問題は、単語の単位の翻訳だけでなく、並び替えの問題も含んでいることからＮＰ＿Ｃｏｍｐｌｅｔｅであることが知られている（上記文献２参照）。過去の研究においては、出力を文頭から生成する制約を加え、プルーニング（剪定）を行うことによりデコーディングアルゴリズムを実現している（上記文献３〜８参照）。ただし、プルーニングも原言語と目的言語とがほぼ線形に対応づけられていることを仮定しており、日本語と英語間の翻訳といった語順の相違が大きい言語間の翻訳を想定していない。
【００３５】
以下、出力の方向を考慮したデコーディングアルゴリズムについて説明する。
【００３６】
〔２〕デコーディングアルゴリズム
【００３７】
本発明によるデコーディングアルゴリズムは、Ｔｉｌｌｍａｎ　（上記文献７参照）やＯｃｈ　（上記文献４参照）らによるビームサーチアルゴリズムに基づいており、また、仮説に適用される操作はＢｅｒｇｅｒ（上記文献３参照）、Ｏｃｈ　（上記文献４参照）やＧｅｒｍａｎｎ　（上記文献８参照）らに基づいている。
【００３８】
まず、デコーディングアルゴリズムで用いられる仮説およびマルチスタックについて説明する。
【００３９】
仮説ｈは、（ＷＴ　，Ａ，Ｃ，ｓ，ｏｐｅｎ／ｃｌｏｓｅ）　のように表現される。仮説の各要素は次のように定義される。
【００４０】
ＷＴ　：部分出力文
Ａ　：部分的に決定されたアライメント
Ｃ　：既に処理された入力文のインデックスの集合
ｓ　：スコア
ｏｐｅｎ／ｃｌｏｓｅ：ｏｐｅｎな仮説とｃｌｏｓｅ　な仮説との識別子であり、０はｏｐｅｎな仮説を表し、１はｃｌｏｓｅ　な仮説を表す。
【００４１】
ｏｐｅｎな仮説では、入力文の単語を既に得られた部分出力文のある単語と対応づけることにより、ｆｅｒｔｉｌｉｔｙ　（出力文の１つの単語に対応付けられる入力文の単語の数）を増大させる操作が行われる。ｃｌｏｓｅ　な仮説では、既に得られた部分出力文に対して単語列ＷＴ　’を追加する操作が行われる。この単語列ＷＴ　’は、ｆｅｒｔｉｌｉｔｙ　が１以上の単語１個とｆｅｒｔｉｌｉｔｙ　がゼロの単語の列から構成される。
【００４２】
マルチスタックは、スタックの集合であり、入力文の単語のインデックスの各部分集合（各組み合わせ）に対応したスタックが存在している。例えば、入力文が、インデックス１の単語、インデックス２の単語およびインデックス３の単語の３つの単語から構成されている場合には、入力文の単語のインデックスの各部分集合に応じた、Ｃ＝｛｝、Ｃ＝｛１｝、Ｃ＝｛２｝、Ｃ＝｛３｝、Ｃ＝｛１，２｝、Ｃ＝｛１，３｝、Ｃ＝｛２，３｝、Ｃ＝｛１，２，３｝の７個のスタックが用意される。
【００４３】
各スタックには、デコーディングアルゴリズムによって生成された仮説が格納される。各スタックにおいては、スコアの高い順に、仮説がソートされる。スタックに格納されている仮説の数が所定の閾値（ｍａｘ−ｓｔａｃｋ−ｓｉｚｅ）　に達している場合に、新たな仮説を格納しようとする場合には、それらの仮説の中でスコアの最も低い仮説を捨てることにより、常にｍａｘ−ｓｔａｃｋ−ｓｉｚｅの数の仮説を格納するようにしている。
【００４４】
〔２．１〕全体フロー
【００４５】
図３は、デコーディングアルゴリズムを示している。
【００４６】
まず、入力文Ｗｓ　＝Ｗｓ１，　Ｗｓ２，　…Ｗｓ２ｍ　を入力する（ステップ１）。入力文Ｗｓ　の入力長（単語数）はｍである。
【００４７】
次に初期化処理を行う（ステップ２）。初期化処理においては、初期仮説ｈ０　が生成されて、Ｃ＝｛｝のスタックに格納される。初期仮説ｈ０　では、ＷＴ　は存在せず（ＷＴ　＝””）、アライメントＡは−１に設定され、入力分のインデックスの集合Ｃは空（｛｝）に設定され、スコアｓは１．０に設定され、ｏｐｅｎ／ｃｌｏｓｅ識別子はｃｌｏｓｅ　を表す”１”に設定される。したがって、初期仮説ｈ０　は、（ＷＴ　＝””，Ａ＝（−１，…−１），Ｃ＝｛｝，ｓ＝１．０，ｏｐｅｎ／ｃｌｏｓｅ＝１）となる。また、変数ｃが０に設定される。なお、以下の説明において、｜Ｃ｜は、入力文の単語のインデックスの各部分集合の要素数を表すものとする。
【００４８】
次に、｜Ｃ｜＝ｃであるスタック（要素数がｃ個である部分集合に対応するスタック）でまだ選択されていないスタックが存在するか否かを判別する（ステップ３）。
【００４９】
｜Ｃ｜＝ｃであるスタックでまだ選択されていないスタックが存在する場合には、そのうちの１つのスタックを選択する（ステップ４）。そして、選択したスタック内にまだ読み出されていない仮説が存在するか否かを判別する（ステップ５）。選択したスタック内にまだ読み出されてない仮説が存在する場合には、まだ読み出されてない仮説ｈを１つだけ読み出す（ステップ６）。そして、仮説生成処理を実行する（ステップ７）。そして、ステップ５に戻る。
【００５０】
上記ステップ３において、｜Ｃ｜＝ｃであるスタックでまだ選択されていないスタックが存在しない場合には、変数ｃの値を１だけインクリメント（＋１）する（ステップ８）。そして、ｃがｍに達したか否かを判定する（ステップ９）。ｃがｍに達していない場合（ｃ＜ｍ）には、ステップ３に戻る。
【００５１】
上記ステップ５において、上記ステップ４で選択したスタック内にまだ読み出されてない仮説が存在しない場合には、ステップ３に戻る。
【００５２】
上記ステップ９において、ｃがｍに達していると判別した場合（ｃ＝ｍ）には、今回の処理を終了する。この時点において、｜Ｃ｜＝ｍであるスタックの中に解が存在することになる。
【００５３】
〔２．２〕仮説生成処理手順
【００５４】
図４は、図３のステップ７の仮説生成処理手順を示している。
【００５５】
以下の説明において、ｊは入力文ＷＳ　の単語のインデックスを表す変数であり、ｉは出力文ＷＴ　の単語のインデックスを表す変数であるとする。
【００５６】
上記ステップ６で読み出された仮説ｈを入力する（ステップ１１）。変数ｊとして１を設定する（ステップ１２）。
【００５７】
そして、ｊが（ｍ＋１）に達したか否かを判定する（ステップ１３）。ｊが（ｍ＋１）に達していない場合（ｊ≦ｍ）には、ｊが入力仮説ｈ内のＣに含まれていないか否かを判定する（ステップ１４）。
【００５８】
ｊが入力仮説ｈ内のＣに含まれていない場合には、入力仮説ｈ内のｏｐｅｎ／ｃｌｏｓｅ識別子がｏｐｅｎ（　＝０）であるか、ｃｌｏｓｅ（＝１）であるかを判定する（ステップ１５）。
【００５９】
入力仮説ｈがｏｐｅｎである場合には、ｏｐｅｎに対応した仮説生成処理を行う（ステップ１６）。入力仮説ｈがｃｌｏｓｅ　である場合には、ｃｌｏｓｅ　に対応した仮説生成処理を行う（ステップ１７）。ｏｐｅｎに対応した仮説生成処理およびｃｌｏｓｅ　に対応した仮説生成処理の詳細については、後述する。
【００６０】
ステップ１６またはステップ１７によって新たな仮説が生成された場合には、生成された新たな仮説を、その仮説中のＣに対応するスタックに格納する（ステップ１８）。
【００６１】
そして、変数ｊの値を１だけインクリメント（＋１）した後（ステップ１９）、ステップ１３に移行する。
【００６２】
上記ステップ１４において、ｊがＣに含まれていると判定した場合には、ステップ１９に移行する。
【００６３】
上記ステップ１３において、ｊが（ｍ＋１）に達していると判定した場合（ｊ＝（ｍ＋１））には、今回の仮説生成処理は終了する。つまり、図３のステップ５に戻る。
【００６４】
以下、ｏｐｅｎに対応した仮説生成処理およびｃｌｏｓｅ　に対応した仮説生成処理について説明する。
【００６５】
〔２．３〕ｏｐｅｎに対応した仮説生成処理
【００６６】
ｏｐｅｎに対応した仮説生成処理では、以下のような仮説を、ｏｐｅｎとｃｌｏｓｅ　との２種類生成する。
【００６７】
入力文ＷＳ　のうちのインデックスｊにある単語を、インデックスｉにある部分出力文の単語に対応させる。
【００６８】
この実施の形態では、部分出力文を文末から生成する（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　デコーディング）　ため、インデックスｉにある出力単語は部分出力文ＷＴ　における最初の単語（ｉ＝１）となる。したがって、図５に示すように、入力文ＷＳ　のうちのインデックスｊにある単語ＷＳｊが、入力仮説ｈ内の部分出力文ＷＴ　における最初の単語ＷＴ１（ｉ＝１）に対応づけられる。
【００６９】
この場合には、仮説の要素である部分出力文ＷＴ　は変更されず、アライメントＡが変更される。つまり、Ａ［　ｊ　］　として、ｉ＝１が代入される（Ａ［　ｊ　］　←ｉ（＝１））。また、仮説の要素であるＣとして、Ｃ∪｛ｊ｝が設定される（Ｃ←Ｃ∪｛ｊ｝）。
【００７０】
なお、Ｃ∪｛ｊ｝は、例えば、Ｃが｛｝でかつｊが１であれば、｛｝∪｛１｝＝｛１｝となり、例えば、Ｃが｛１｝でかつｊが２であれば、｛１｝∪｛２｝＝｛１，２｝となり、例えば、Ｃが｛２，３｝でかつｊが１であれば、｛２，３｝∪｛１｝＝｛１，２，３｝となる。
【００７１】
仮説の要素であるスコアｓは、よく知られているように次式（６）に基づいて算出される。
【００７２】
【数６】
2004086343.tif 000008
【００７３】
ここで、ｆをＷＴ　［ｉ］　の新しいｆｅｒｒｉｌｉｔｙ　とする。また、Ｄｉｓｔｏｒｔｉｏｎモデル（　歪みモデル）　の確率を再計算する。
【００７４】
以上のような要素を持ち、かつｏｐｅｎ／ｃｌｏｓｅ識別子がｏｐｅｎ（＝０）である仮説と、ｏｐｅｎ／ｃｌｏｓｅ識別子がｃｌｏｓｅ（＝１）である仮説とが生成される。
【００７５】
なお、従来のように部分出力文を文頭から生成する（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ　デコーディング）　においては、インデックスｉにある出力単語は部分出力文ＷＴ　における最後の単語（ｉ＝｜ＷＴ　｜）となる。したがって、図６に示すように、入力文ＷＳ　のうちのインデックスｊにある単語ＷＳｊが、入力仮説内の部分出力文ＷＴ　における最後の単語ＷＴｌ（ｉ＝｜ＷＴ　｜）に対応づけられる。この結果、Ａ［　ｊ　］　として、ｉ＝｜ＷＴ　｜が代入される（Ａ［　ｊ　］　←ｉ（＝｜ＷＴ　｜）。
【００７６】
〔２．４〕ｃｌｏｓｅ　に対応した仮説生成処理
【００７７】
ｃｌｏｓｅ　に対応した仮説生成処理では、ＮＵＬＬへ対応された仮説と、文字列の挿入および挿入文字列へ対応づけられた仮説とを生成する。
【００７８】
〔２．４．１〕ＮＵＬＬへ対応された仮説
【００７９】
入力文のうち、インデックスｊにある単語を、ＮＵＬＬ（インデックス０にある出力単語）に対応させる。
【００８０】
つまり、Ａ［　ｊ　］　として、０が代入される（Ａ［　ｊ　］　←０）。また、仮説の要素であるＣとして、Ｃ∪｛ｊ｝が設定される（Ｃ←Ｃ∪｛ｊ｝）。仮説の要素であるｏｐｅｎｃｌｏｓｅ　識別子はｃｌｏｓｅ　（＝１）とする。仮説の要素であるスコアｓは、よく知られているように次式（７）に基づいて算出される。
【００８１】
【数７】
2004086343.tif 000009
【００８２】
ここで、ｆをＮＵＬＬの新しいｆｅｒｒｉｌｉｔｙ　とする。
【００８３】
〔２．４．２〕文字列の挿入および挿入文字列へ対応づけられた仮説
【００８４】
以下のような仮説を、ｏｐｅｎとｃｌｏｓｅ　との２種類生成する。
【００８５】
まず、入力仮説内の部分出力文ＷＴ　に新しい文字列ＷＴ　’を挿入する。この実施の形態では、部分出力文を文末から生成する（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　デコーディング）　ため、図７に示すように、入力仮説内の部分出力文ＷＴ　の左側に新しい文字列ＷＴ　’を挿入する（ＷＴ　←ＷＴ　’＋ＷＴ　）。
【００８６】
また、入力文ＷＳ　のうち、インデックスｊにある単語ＷＳｊを、インデックスｉにある出力単語に対応させる。この実施の形態では、部分出力文を文末から生成する（ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　デコーディング）　ため、図７に示すように、インデックスｉにある出力単語は新しいＷＴ　（図７のＷＴ　’＋ＷＴ　）における最初の単語ＷＴ１’（ｉ＝１）となる。したがって、アライメントＡ［　ｊ　］　として、ｉ＝１が代入される（Ａ［　ｊ　］　←ｉ（＝１））。
【００８７】
また、仮説の要素であるＣとして、Ｃ∪｛ｊ｝が設定される（Ｃ←Ｃ∪｛ｊ｝）。仮説の要素であるスコアｓは、よく知られているように次式（８）に基づいて算出される。
【００８８】
【数８】
2004086343.tif 000010
【００８９】
Ｐｌｍは、言語モデルによるスコアであり、もし、ＷＴ　［ｉ’］　において、ｉ　’≦０の場合、ＷＴ　［ｉ’］　＝ＢＯＳ（Ｂｅｇｇｉｎｉｎｇ　ｏｆ　Ｓｅｎｔｅｎｃｅ　Ｍａｒｋｅｒ）となる。
【００９０】
以上のような要素を持ち、かつｏｐｅｎ／ｃｌｏｓｅ識別子がｏｐｅｎ（　＝０）である仮説と、ｏｐｅｎ／ｃｌｏｓｅ識別子がｃｌｏｓｅ（＝１）である仮説とが生成される。
【００９１】
なお、新しい文字列ＷＴ　’は複数生成される。そして、新しい文字列毎に、上記のようにして、２つずつ仮説が生成される。新しい文字列ＷＴ　’の生成方法については、上記文献３，４，５に説明されている。
【００９２】
従来のように部分出力文を文頭から生成する（ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ　デコーディング）　においては、文字列ＷＴ　を挿入する場合、図８に示すように、入力仮説内の部分出力文ＷＴ　の右側に新しい文字列ＷＴ　’を挿入する（ＷＴ　←ＷＴ　＋ＷＴ　’）。また、インデックスｉにある出力単語は新しいＷＴ　（図８のＷＴ　＋ＷＴ　’）における最後の単語ＷＴｌ’（ｉ＝｜ＷＴ　｜）となる。この結果、Ａ［　ｊ　］　として、ｉ＝｜ＷＴ　｜が代入される（Ａ［　ｊ　］　←ｉ（＝｜ＷＴ　｜）。
【００９３】
〔２．５〕入力文ＷＳ　の入力長ｍが３の場合の流れについの説明
【００９４】
入力文ＷＳ　の入力長ｍが３の場合の、デコーディングアルゴリズムの流れについて簡単に説明しておく。
【００９５】
まず、Ｃ＝｛｝に対応するスタックに、初期仮説ｈ０　＝（ＷＴ　＝””，Ａ＝（−１，…−１），Ｃ＝｛｝，ｓ＝１．０，ｏｐｅｎ／ｃｌｏｓｅ＝１）が格納される（図３のステップ１〜２）。
【００９６】
そして、図３のステップ６において、Ｃ＝｛｝に対応するスタックから初期仮説ｈ０　が取り出される。そして、図４のステップ１７のｃｌｏｓｅ　に対応した仮説生成処理によって、ｊ＝１，２、３それぞれに対応した新たな仮説が生成され、Ｃ＝｛１｝、Ｃ＝｛２｝、Ｃ＝｛３｝それぞれに対応するスタックに、新たな仮説が格納される。
【００９７】
次に、Ｃ＝｛１｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝２、３それぞれに対応した新たな仮説が生成され、Ｃ＝｛１，２｝、Ｃ＝｛１，３｝それぞれに対応するスタックに、新たな仮説が格納される。
【００９８】
同様に、Ｃ＝｛２｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝１，３に対応した新たな仮説が生成され、Ｃ＝｛１，２｝、Ｃ＝｛２，３｝に対応するスタックに、新たな仮説が格納される。
【００９９】
同様に、Ｃ＝｛３｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝１，２に対応した新たな仮説が生成され、Ｃ＝｛１，３｝、Ｃ＝｛２，３｝に対応するスタックに、新たな仮説が格納される。
【０１００】
次に、Ｃ＝｛１，２｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝３に対応した新たな仮説が生成され、Ｃ＝｛１，２，３｝に対応するスタックに、新たな仮説が格納される。
【０１０１】
次に、Ｃ＝｛１，３｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝２に対応した新たな仮説が生成され、Ｃ＝｛１，２，３｝に対応するスタックに、新たな仮説が格納される。
【０１０２】
次に、Ｃ＝｛２，３｝に対応するスタックから仮説が１つずつ取り出され、各仮説に基づいて、ｊ＝１に対応した新たな仮説が生成され、Ｃ＝｛１，２，３｝に対応するスタックに、新たな仮説が格納される。
【０１０３】
この結果、Ｃ＝｛１，２，３｝に対応するスタックに、解（翻訳結果）がスコアの高い順番に格納される。
【０１０４】
〔３〕デコーディング方向による影響
【０１０５】
従来のｌｅｆｔ−ｔｏ−ｒｉｇｈｔ　デコーディングアルゴリズムにおいては、入力単語を処理し、対応する翻訳を単語単位に決定して部分出力文を文頭から生成する。このような挙動により、言語モデルや翻訳モデルは文頭からスコアリングを行うことにより、「良い仮説」と「悪い仮説」とを区別する力が大きくなることが考えられる。
【０１０６】
例えば、英語やドイツ語、フランス語のように文頭からの語順の制約が強い言語を目的言語として翻訳を行った場合、文頭からのスコアリングによる制約が強くなり、ビームサーチのプルーニングを行っても出力の質が落ちることがない。逆に、このような言語に対して本実施の形態のようにｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　デコーディング行うと、仮説間のスコアの差が小さく、仮説数が増大し、プルーニングによる影響が大きくなる。
【０１０７】
日本語のような文末に語順の制約がある場合、そのような言語を目的言語としてｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　デコーディングを行うとスコアの差が大きくなり、ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ　に行うとスコアの差が小さくなると考えられる。したがって、文末に語順の制約がある言語が目的言語である場合には、ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　にデコーディングを行うことが好ましい。
【０１０８】
〔４〕実験
【０１０９】
今回行った実験のコーパスは、大規模旅行会話集（文献９参照）から抽出した１７２，４８１　の日英の対訳文であり、その統計情報を表１に示す。コーパスから１５２，１８３　文からなるトレーニングセット、検証セットを１０，１４８文、さらにテストセット１０，１５０文を取り出した。
【０１１０】
文献９：Ｔａｋｅｚａｗａ，Ｔ．，　Ｓｕｍｉｔａ，Ｅ．，　Ｓｕｇａｙａ，Ｆ．，　Ｙａｍａｍｏｔｏ，Ｈ．　ａｎｄ　Ｙａｍａｍｏｔｏ，Ｓ．：　Ｔｏｗａｒｄ　ａ　Ｂｒｏａｄ−ｃｏｖｅｒａｇｅ　Ｂｉｌｉｎｇｕａｌ　Ｃｏｒｐｕｓ　ｆｏｒ　Ｓｐｅｅｃｈ　Ｔｒａｎｓｌａｔｉｏｎ　ｏｆ　Ｔｒａｖｅｌ　Ｃｏｎｖｅｒｓａｔｉｏｎｓ　ｉｎ　ｔｈｅ　Ｒｅａｌ　Ｗｏｒｌｄ，　Ｐｒｏｃ．　ｏｆ　ＬＲＥＣ　２００２，　Ｌａｓ　Ｐａｌｍａｓ，　ＣａｎａｒｙＩｓｌａｎｄｓ，　Ｓｐａｉｎ，　ｐｐ．１４７−１５２（２００２）．
【０１１１】
【表１】
2004086343.tif 000011
【０１１２】
翻訳モデルは日英、英日方向、どちらもＩＢＭ　Ｍｏｄｅｌ−１　からＩＢＭ　Ｍｏｄｅｌ−４　までブートストラップしてトレーニングを行い、途中にＨＭＭ　Ｍｏｄｅｌ　によるトレーニングを行っている（文献１０参照）。また、検証セットによるクロスバリデーションを行いながらトレーニングを繰り返した。ＩＢＭ　Ｍｏｄｅｌ−４　においては、品詞を単語クラスとして用いた。
【０１１３】
文献１０：　Ｏｃｈ，Ｆ．Ｊ．，　Ｔｉｌｌｍａｎｎ，Ｃ．　ａｎｄ　Ｎｅｙ，Ｈ．：　Ｉｍｐｒｏｖｅｄ　Ａｌｉｇｎｍｅｎｔ　Ｍｏｄｅｌｓｆｏｒ　Ｓｔａｔｉｓｔｉｃａｌ　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ，　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｊｏｉｎｔ　Ｃｏｎｆ．　ｏｆ　Ｅｍｐｉｒｉｃａｌ　Ｍｅｔｈｏｄｓ　ｉｎ　Ｎａｔｕｒａｌ　Ｌａｎｇｕａｇｅ　Ｐｒｏｃｅｓｓｉｎｇ　ａｎｄ　Ｖｅｒｙ　Ｌａｒｇｅ　Ｃｏｒｐｏｒａ，　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｍａｒｙｌａｎｄ，　Ｃｏｌｌｅｇｅ　Ｐａｒｋ，ＭＤ（１９９９）．
【０１１４】
トレーニングコーパスのビテルビアライメントから、ｆｅｒｔｉｌｉｔｙ　がゼロとなる単語列を取り出し、頻度が１０未満のものを取り除いた。また、テストセットから文長が６　、８　、１０である、それぞれ５０文、合計１５０　の日本語、英語の文を取り出し、上記の２つのアルゴリズムによるデコーディングの実験を行った。
【０１１５】
翻訳結果を評価するに当たって、以下の基準を用いた。
【０１１６】
・単語誤り率（ＷＥＲ）：　　挿入、削除、置換に対してペナルティを１として計算。
【０１１７】
・位置独立単語誤り率（ＰＥＲ）：　ＷＥＲ　では、実際の翻訳に起こりうる並び替えに対してペナルティが大きくなる。従って、ＰＥＲ　では位置の情報を無視し、出力単語の集合の正しさの評価を行う（上記文献４参照と文献１１参照）。
文献１１：Ｗａｔａｎａｂｅ，Ｔ．，　Ｉｍａｍｕｒａ，Ｋ．　ａｎｄ　Ｓｕｍｉｔａ，Ｅ．：　Ｓｔａｔｉｓｔｉｃａｌ　Ｍａｃｈｉｎｅ
Ｔｒａｎｓｌａｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｈｉｅｒａｒｃｈｉｃａｌ　Ｐｈｒａｓｅ　Ａｌｉｇｎｍｅｎｔ，　Ｐｒｏｃ．　ｏｆ　ＴＭＩ　２００２，Ｋｅｉｈａｎｎａ，　Ｊａｐａｎ（２００２）．
【０１１８】
・ＢＬＥＵスコア：　正解集合の全てに対してＮ−ｇｒａｍの正解率を計算するものであり、短い出力に対してペナルティを与えている（文献１２参照）。
文献１２：　Ｐａｐｉｎｅｎｉ，Ｋ．，　Ｒｏｕｋｏｓ，Ｓ．，　Ｗａｒｄ，Ｔ．　ａｎｄ　Ｚｈｕ，Ｗ．Ｊ．：　Ｂｌｅｕ：　ａ　Ｍｅｔｈｏｄ　ｆｏｒ　Ａｕｔｏｍａｔｉｃ　Ｅｖａｌｕａｔｉｏｎ　ｏｆ　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ，　Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　４０ｔｈ　Ａｎｎｕａｌ　Ｍｅｅｔｉｎｇ　ｏｆ　ｔｈｅ　Ａｓｓｏｃｉａｔｉｏｎ　ｆｏｒ　Ｃｏｍｐｕｔａｔｉｏｎａｌ　Ｌｉｎｇｕｉｓｔｉｃｓ（ＡＣＬ），ｐｐ．３１１−３１８（２００２）．
【０１１９】
・ＮＩＳＴスコア：　ＢＬＵＥと同様なスコアであるが、正解率を正解集合のＮ−ｇｒａｍに対する平均出力単語情報量として表現している（文献１３参照）。
文献１３：　Ａｕｔｏｍａｔｉｃ　Ｅｖａｌｕａｔｉｏｎ　ｏｆ　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ　Ｑｕａｌｉｔｙ　ｕｓｉｎｇ　Ｎ−ｇｒａｍ　Ｃｏ−Ｏｃｃｕｒｒｅｎｃｅ　Ｓｔａｔｉｓｔｉｃｓ，　ｈｔｔｐ：／／ｗｗｗ．ｎｉｓｔ．ｇｏｖ／ｓｐｅｅｃｈ／ｔｅｓｔｓ／ｍｔ／ｄｏｃ／ｎｇｒａｍ−ｓｔｕｄｙ．ｐｄｆ（２００２）　．
【０１２０】
・主観評価（ＳＥ）：　翻訳結果を人手でＡ、Ｂ、Ｃ、Ｄと４段階にランク付けをする（文献１４参照）。
文献１４：Ｓｕｍｉｔａ，Ｅ．，　Ｙａｍａｄａ，Ｓ．，　Ｙａｍａｍｏｔｏ，Ｋ．，　Ｐａｕｌ，Ｍ．，　Ｋａｓｈｉｏｋａ，Ｈ．，　Ｉｓｈｉｋａｗａ，Ｋ．ａｎｄ　Ｓｈｉｒａｉ，Ｓ．：　Ｓｏｌｕｔｉｏｎｓ　ｔｏ　Ｐｒｏｂｌｅｍｓ　Ｉｎｈｅｒｅｎｔ　ｉｎ　Ｓｐｏｋｅｎ−ｌａｎｇｕａｇｅＴｒａｎｓｌａｔｉｏｎ：　Ｔｈｅ　ＡＴＲ−ＭＡＴＲＩＸ　Ａｐｐｒｏｃｈ，　Ｍａｃｈｉｎｅ　Ｔｒａｎｓｌａｔｉｏｎ　Ｓｕｍｍｉｔ　ＶＩＩ，　ＰＰ．２２９−２３５（１９９９）．
【０１２１】
・探索誤り率（ＳＥＲ）：　　翻訳の正さあるいは誤り以外に、各デコーディングアルゴリズムが翻訳モデルと言語モデルから最適解を得られたかどうかを評価した。出力結果のうち、スコアが最も高い出力の集合を正解集合として、誤り率を求めた。
【０１２２】
表２は、ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ（ＬｔｏＲ）　とｒｉｇｈｔ−ｔｏ−ｌｅｆｔ（ＲｔｏＬ）　とのデコーディングアルゴリズムの翻訳結果を示す。日英、英日の翻訳例をそれぞれ図９、図１０に示す。
【０１２３】
【表２】
2004086343.tif 000012
【０１２４】
〔５〕考察
表２における探索誤り率（ＳＥＲ）　から、日英翻訳については、ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　デコーディングアルゴリズムより、ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ　デコーディングアルゴリズムが良く、また、英日翻訳ではその逆の結果が得られた。このことから、言語モデル、翻訳モデルに基づいて翻訳結果を得るに当たって、出力文の言語の特性に合わせて出力の方向を制約する手法の有効性が確認された。
【０１２５】
翻訳結果の客観評価値（ＷＥＲ／ＰＥＲ／ＢＬＥＵ／ＮＩＳＴ）では、日英翻訳でアルゴリズム間に差異が認められなかった。英日翻訳においては、ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　デコーディングアルゴリズムは、ＷＥＲ／ＰＥＲ　の点において優れていることが確認された。
【０１２６】
主観評価（ＳＥ）では、日英翻訳において、ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ　デコーディングアルゴリズムは、ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　デコーディングアルゴリズムよりＡランクの文の割合が増加している。ただし、英日翻訳では、アルゴリズム間で主観評価（ＳＥ）はほぼ変わらなかった。
【０１２７】
【発明の効果】
この発明によれば、文末に語順の制約が強いという性質をもつ言語が目的言語である場合に、好適な翻訳結果が得られるようになる。
【図面の簡単な説明】
【図１】統計的機械翻訳モデルを説明するための模式図である。
【図２】アライメントの例を示す模式図である。
【図３】デコーディングアルゴリズムを示すフローチャートである。
【図４】図３のステップ７の仮説生成処理手順を示すフローチャートである。
【図５】ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　デコーディングによる、ｏｐｅｎに対応した仮説生成処理を説明するための模式図である。
【図６】ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ　デコーディングによる、ｏｐｅｎに対応した仮説生成処理を説明するための模式図である。
【図７】ｒｉｇｈｔ−ｔｏ−ｌｅｆｔ　デコーディングによる、ｃｌｏｓｅ　に対応した仮説生成処理を説明するための模式図である。
【図８】ｌｅｆｔ−ｔｏ−ｒｉｇｈｔ　デコーディングによる、ｃｌｏｓｅ　に対応した仮説生成処理を説明するための模式図である。
【図９】実験によって得られた日英翻訳結果の例を示す模式図である。
【図１０】実験によって得られた英日翻訳結果の例を示す模式図である。
【図１】
2004086343.tif 000013
【図２】
2004086343.tif 000014
【図３】
2004086343.tif 000015
【図４】
2004086343.tif 000016
【図５】
2004086343.tif 000017
【図６】
2004086343.tif 000018
【図７】
2004086343.tif 000019
【図８】
2004086343.tif 000020
【図９】
2004086343.tif 000021
【図１０】
2004086343.tif 000022