双対分解を用いた組み合わせモデル型アライナ
【課題】機械翻訳において用いる、並列翻訳文中の単語を対応付けるための方法、システムおよび装置。
【解決手段】トレーニング時間中に動作するコンポーネントを備え、コンポーネントは、一対の言語の、正しく翻訳された文対よりなる並列コーパス４０２を含む。他のトレーニング時間コンポーネントは、対応付けモデルコンポーネント４０４であり、並列コーパス４０２から文対を受信し、対応付けされた並列コーパスを生成する。該並列コーパスは、句抽出コンポーネント４０６により受信され、句抽出器は、翻訳された句および対応するスコアのスニペットを含む、句テーブル４０８を生成する。翻訳時間コンポーネントは、句テーブル４０８のデータから生成される翻訳モデル４２２を含み、言語モデル４２０、および、言語モデル４２０や翻訳モデル４２２を用い、入力テキスト４２６から翻訳済み出力テキスト４２８を生成する機械翻訳コンポーネント４２４を含む。
【解決手段】トレーニング時間中に動作するコンポーネントを備え、コンポーネントは、一対の言語の、正しく翻訳された文対よりなる並列コーパス４０２を含む。他のトレーニング時間コンポーネントは、対応付けモデルコンポーネント４０４であり、並列コーパス４０２から文対を受信し、対応付けされた並列コーパスを生成する。該並列コーパスは、句抽出コンポーネント４０６により受信され、句抽出器は、翻訳された句および対応するスコアのスニペットを含む、句テーブル４０８を生成する。翻訳時間コンポーネントは、句テーブル４０８のデータから生成される翻訳モデル４２２を含み、言語モデル４２０、および、言語モデル４２０や翻訳モデル４２２を用い、入力テキスト４２６から翻訳済み出力テキスト４２８を生成する機械翻訳コンポーネント４２４を含む。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本願は、３５Ｕ．Ｓ．Ｃ．§１１９（ｅ）に基づき、２０１０年１２月１７日出願の米国出願第６１／４２４，６０８号の出願日の効果を主張する。この優先権出願の開示内容は、本願の開示内容の一部とみなされ、参照により本願に含まれる。
【背景技術】
【０００２】
本明細書は統計的機械翻訳における単語の対応付けに関する。
単語（ｗｏｒｄ）の対応付けは、文（ｓｅｎｔｅｎｃｅ）対中の対応する単語を識別する、統計的機械翻訳（ＭＴ）における主要な機械学習タスクである。ＭＴシステムの大半は、文ｆの単語を、その翻訳文ｅの単語に対応付ける有向マルコフ対応付けモデルを採用する。
【０００３】
教師なし単語対応付けは、一般的に、文ｆを、その翻訳文ｅを条件として生成するマルコフプロセスとしてモデル化される。ｆからｅを生成する同様のモデルは、異なる対応付けを予測する。
【０００４】
システムは通常２つの有向モデルによる予測を組み合わせ、このうち一方がｆをｅに対応付け、他方がｅをｆに対応付ける。統計的機械翻訳システムは、２つの有向モデルによる予測を組み合わせる。この組み合わせにより、エラーを減少させ、有向モデルの１対多の構造的制約を緩和することができる。最も一般的な組み合わせの方法は、対応（ａｌｉｇｎｍｅｎｔ）の和集合（ｕｎｉｏｎ）および積集合（ｉｎｔｅｒｓｅｃｔｉｏｎ）を形成する方法、または、ｇｒｏｗ−ｄｉａｇ−ｆｉｎａｌ等のヒューリスティック手続きを適用する方法である（これは、例えば、Ｆｒａｎｚ Ｊｏｓｅｆ Ｏｃｈ， Ｃｈｒｉｓｔｏｐｈｅｒ Ｔｉｌｌｍａｎ， ａｎｄ Ｈｅｒｍａｎｎ Ｎｅｙ， Ｉｍｐｒｏｖｅｄ ａｌｉｇｎｍｅｎｔ ｍｏｄｅｌｓ ｆｏｒ ｓｔａｔｉｓｔｉｃａｌ ｍａｃｈｉｎｅ ｔｒａｎｓｌａｔｉｏｎ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｍｐｉｒｉｃａｌ Ｍｅｔｈｏｄｓ ｉｎ Ｎａｔｕｒａｌ Ｌａｎｇｕａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， １９９９に記載されている）。
【発明の概要】
【０００５】
本明細書は、２つの有向アライナを明示的に単一の結合モデルに組み合わせる図式モデルの構成および使用方法を説明する。推論は、有向モデルの効率的な推論アルゴリズムを再利用する双対分解により行うことができる。組み合わせモデルは１対１の句（ｐｈｒａｓｅ）制約を実施し、対応付けの品質を向上させる。
【０００６】
本明細書の主題の１つまたは複数の実施例の詳細は、添付の図面および以下の説明を参照して明らかになる。また、本主題の他の特徴、態様および利点についても、明細書、図面および特許請求の範囲より明らかになる。
【図面の簡単な説明】
【０００７】
【図１】英語と中国語の単純な文対に対する双方向図式モデルのグラフ構成を示す図である。
【図２】双方向モデルをどのように２つの非循環モデルに分解するかを示す図である。
【図３】木構造を有する部分グラフＧａをどのように等価の鎖構造を有するモデルに最適化によりマッピングするかを示す図である。
【図４】機械翻訳システムにおける双方向モデルの位置を示す図である。図面中の同一の参照記号は同一の構成要素を示す。
【発明を実施するための形態】
【０００８】
（イントロダクション）
本明細書は、アライナの組み合わせに対する、モデルベースの代替案であり、２つの有向対応付けモデルの相反する予測を、これら２つの有向対応付けモデルをより大規模な図式モデル中に埋め込むことにより解消する代替案を説明する（以下「双方向モデル」と称する）。
【０００９】
双方向モデルにおける潜在変数は、２つの有向マルコフ対応付けモデルにおける潜在変数の真の上位集合である。このモデルの構成およびポテンシャルは２つの有向モデル間の不一致を許容し、一致を与える。さらに、双方向モデルは、１対１の句対応付け構造を実施し、これにより、句対応付けモデル、同期ＩＴＧ（Ｉｎｖｅｒｓｉｏｎ Ｔｒａｎｓｄｕｃｔｉｏｎ Ｇｒａｍｍａｒ）モデルおよび最新の教師ありモデルに示されるのと同様の構造的利点を得る。
【００１０】
双方向モデルでは、モデルグラフ中に辺のサイクルが多く存在するため、推論を計算することができない。しかし、近似推論法の１つとして、双対分解を用いることができる。組み合わせモデル空間を探索するため、潜在的なマルコフ対応付けモデルの効率的なシーケンスアルゴリズムを、繰り返し適用することができる。この近似が収束した場合、完全モデルによる最適性の証明を得たことになる。
【００１１】
アライナの組み合わせに対するこのモデルベースのアプローチは、対応付けおよび句抽出の品質を向上させる。
【００１２】
（モデル定義）
双方向モデルは、頂点（ｖｅｒｔｅｘ）集合Ｖおよび辺（ｅｄｇｅ）集合Ｄにより定義される図式モデルであり、文ｅおよびその翻訳文ｆの長さを条件として構築される。各頂点はモデル変数Ｖｉに対応し、各無向辺は変数の対(Ｖｉ，Ｖｊ)に対応する。各頂点は、対応する頂点ポテンシャル関数ｖｉ（ｖｊ）を有し、この関数は実数値を有するポテンシャルをＶｉの採り得る値ｖｉのそれぞれに対し割り当てる。同様に、各辺は、１対の値を有する、対応するポテンシャル関数μｉｊ（ｖｉ，ｖｊ）を有する。モデル変数に対する完全な割り当てｖのモデルによる確率はＶとインデックス付けされ、頂点および辺のポテンシャルを考慮に入れたものである。
【数１】
【００１３】
双方向モデルは、２つの有向隠れマルコフ対応付けモデル、および、これらの埋め込まれたモデルによる予測を単一の対称単語対にする追加の構成を含む。以下のパラグラフでは、まず有向モデルを説明し、それから、２つの有向モデルを結合双方向モデルに組み合わせる追加構成を説明する。
【００１４】
（隠れマルコフ対応付けモデル）
ここでは、従来の隠れマルコフ対応付けモデルを説明する（これは、例えば、Ｓｔｅｐｈａｎ Ｖｏｇｅｌ， Ｈｅｒｍａｎｎ Ｎｅｙ， ａｎｄ Ｃｈｒｉｓｔｏｐｈ Ｔｉｌｌｍａｎｎ， ＨＭＭ−Ｂａｓｅｄ Ｗｏｒｄ， Ａｌｉｇｎｍｅｎｔ ｉｎ Ｓｔａｔｉｓｔｉｃａｌ Ｔｒａｎｓｌａｔｉｏｎ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １６ｔｈ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｌｉｎｇｕｉｓｔｉｃｓ， １９９６に記載されている）。本モデルは、単語シーケンスｅを条件とする単語シーケンスｆを生成する。従来、ｅの単語はｉとインデックス付けされ、ｆはｊとインデックス付けされる。Ｐ（ｆ｜ｅ）は潜在対応ベクトルａにより定義され、ここで、ａｊ＝ｉはｅの単語位置ｉがｆの単語位置ｊに対応づけられることを示す。
【数２】
【００１５】
上式（２）において、放射モデルＭは、単語の種類による、学習済み多項分布を示す。遷移モデルＤは、遷移距離による多項式であり、ヌル対応は例外として扱われる。
【数３】
ｃ（ｉ‘−ｉ）は符号付き距離による学習済み分布であり、ｉからの、可能性のある遷移に対して正規化されている。
【００１６】
条件付き多項式Ｍのパラメータ、遷移モデルｃおよびヌル遷移パラメータｐｏはすべて、文を対応付けたコーパスから期待値最大化アルゴリズムにより学習可能である。
【００１７】
所与の文対（ｅ，ｆ）に対するモデルによる単語対応ベクトルの最大確率は、標準ビタビアルゴリズムを、時間Ｏ（｜ｅ｜２・｜ｆ｜）において、隠れマルコフモデルに対して用いることにより、正確に算出することができる。
【００１８】
対応ベクトルａは、単語対応リンクの集合Ａに明らかに変換可能である。
Ａａ＝｛（ｉ，ｊ）：ａｊ＝ｉ，ｉ≠０｝．
【００１９】
このように構築された集合Ａは常に１対多である。多数の位置ｊを同一のｉに対応付けることも可能だが、各ｊは、集合中に最大１回のみ出現する。
【００２０】
上記説明はｅからｆを生成する有向モデルを定義した。同様に構成された、ｆからｅを生成するモデルを定義することも可能である。対応のベクトルをｂとし、ｂｉ＝ｊはｆの単語位置ｊはｅの単語位置ｉに対応付けられるものとする。そして、Ｐ（ｅ，ｂ｜ｆ）も式（２）同様に定義できるが、ｅとｆとが入れ替わる。２つのモデルの遷移分布および放出分布は、モデルの生成方向ｆ→ｅまたはｅ→ｆを示すサブスクリプトにより区別される。
【数４】
【００２１】
ベクトルｂは１対多対応リンクの集合と解釈できる：各値ｉは最大１回のみ集合中に出現する。
Ａｂ＝｛（ｉ，ｊ）：ｂｉ＝ｊ，ｊ≠０｝．
【００２２】
（アライナ組み合わせのモデル）
以下に説明するように、アライナを組み合わせることにより、双方向モデルを作成することができる。これは、２つの有向アライナのすべてのランダム変数およびアライナ間の一致を促して差異を解消する追加構成を含む図式モデル中に、アライナを埋め込むことにより実現できる。
【００２３】
双方向モデルは、観測対象の単語シーケンスｅおよびｆ、ならびに上に定義された対応変数ａおよびｂの２つのベクトルを含む。
【００２４】
ｅおよびｆの単語の種類および長さは常に観測対象の文対により固定されるため、変数ａおよびｂのみを用いて同一のモデルを定義することができる。この場合、ａｊ，ｆｊおよびｅ間のエッジポテンシャルは、ａｊの頂点ポテンシャル
【数５】
にコンパイルされ、fおよびeにより定義され、いずれのｂｉについても同様である。
【数６】
【数７】
【００２５】
図１は、英語と中国語の単純な文対に対する双方向図式モデルのグラフ構成を示す図である。変数ａ、ｂおよびｃ（以下に説明）は、図中、ラベルにより示される。
【００２６】
ａおよびｂ間のエッジポテンシャルは式（２）の遷移モデルをエンコードする。
【数８】
【数９】
【００２７】
さらに、ランダムビット行列ｃは、組み合わせアライナの出力をエンコードする。
【数１０】
【００２８】
各ランダム変数
【数１１】
は、ａｊおよびｂｉに接続している。これらコヒーレンスエッジが、有向モデルの対応変数を、組み合わせ空間のブーリアン変数に接続する。これらの辺により、モデルが変数ａ、ｂおよびｃの３つの集合をエンコードし、さらに、文対のコヒーレント対応解析をエンコードすることが可能になる。図１はモデルのグラフ構成を図示する。
【００２９】
（コヒーレンスポテンシャル）
コヒーレンスエッジのポテンシャルは、学習されず、また、データセット中のいかなるパターンも表わさない。代わりに、これらは、整数値を有する有向変数ａおよびｂ、ならびにブーリアン値を有する組み合わせ変数ｃの整合性を促す固定関数である。
【００３０】
変数の割り当てａｊ＝ｉを考えると、ｉ＝０はｆｊがヌル対応であり、ｉ＞０はｆｊがｅｉに対応付けられることを示す。コヒーレンスポテンシャルは、変数割り当てａｊ＝ｉといずれかのｉ‘：０＜ｉ’ ≦｜ｅ｜の変数ｃｉ‘ｊとの間に、以下の関係性を成立させる。
・ｉ＝０（ヌル対応）の場合、すべてのｃｉ‘ｊ＝０
・ｉ＞０の場合、ｃｉｊ＝１
・
【数１２】
の場合のみ、ｃｉ’ｊ＞０
・ｉ‘≠ｉに対しｃｉ’ｊ＝１を割り当てることは、コストｅ−αを要し、αは学習済定数である（例：０．３）
【００３１】
この効果のパターンは、各辺において、ポテンシャル関数μ（ｃ）でエンコードすることができる。これらのエッジポテンシャル関数はそれぞれ変数ａｊに対して整数値ｉを採り、ｃｉ‘ｊに対してバイナリ値ｋを採る。
【数１３】
ｂおよびｃ間の辺のポテンシャル
【数１４】
も同様に定義される。
【００３２】
（モデルプロパティ）
行列ｃは、双方向モデルにより生成される最終的な対応と解釈され、ここでａおよびｂは無視する。このように、有向モデルの１対多の制約が緩和される。しかし、どのように単語が対応付けられるかについての情報はすべてａおよびｂの頂点および辺のポテンシャルにより表わされる。コヒーレンスエッジおよびリンク行列ｃは、有向モデル間の矛盾を解消し、両者間で情報のやり取りを行うのみである。
【００３３】
有向対応は双方向モデルのコンポーネントとしてそのまま維持されるため、潜在的有向マルコフ対応付けモデルに対する、レキシカライズド遷移モデル（これは、例えば、Ｘｉａｏｄｏｎｇ Ｈｅ， Ｕｓｉｎｇ ｗｏｒｄ−ｄｅｐｅｎｄｅｎｔ ｔｒａｎｓｉｔｉｏｎ ｍｏｄｅｌｓ ｉｎ ＨＭＭ ｂａｓｅｄ ｗｏｒｄ ａｌｉｇｎｍｅｎｔ ｆｏｒ ｓｔａｔｉｓｔｉｃａｌ ｍａｃｈｉｎｅ， ｉｎ ＡＣＬ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｔａｔｉｓｔｉｃａｌ Ｍａｃｈｉｎｅ Ｔｒａｎｓｌａｔｉｏｎ， ２００７に記載されている）、拡張調整コンテキスト（これは、例えば、Ｊａｍｉｅ Ｂｒｕｎｎｉｎｇ， Ａｄｒｉａ ｄｅ Ｇｉｓｐｅｒｔ， ａｎｄ Ｗｉｌｌｉａｍ Ｂｙｒｎｅ， Ｃｏｎｔｅｘｔ−ｄｅｐｅｎｄｅｎｔ ａｌｉｇｎｍｅｎｔ ｍｏｄｅｌｓ ｆｏｒ ｓｔａｔｉｓｔｉｃａｌ ｍａｃｈｉｎｅ ｔｒａｎｓｌａｔｉｏｎ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｎｏｒｔｈ Ａｍｅｒｉｃａｎ Ｃｈａｐｔｅｒ ｏｆ ｔｈｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｌｉｎｇｕｉｓｔｉｃｓ， ２００９に記載されている）、および外部情報（これは、例えば、進藤裕之、藤野昭典、永田昌明、Ｗｏｒｄ ａｌｉｇｎｍｅｎｔ ｗｉｔｈ ｓｙｎｏｎｙｍ ｒｅｇｕｌａｒｉｚａｔｉｏｎ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｌｉｎｇｕｉｓｔｉｃｓ， ２０１０に記載されている）等を含む拡張や洗練化は、容易に双方向モデルへの組み込みが可能である。
【００３４】
（ａ，ｂ，ｃ）に対するいずれの非ゼロ確率の割り当てに対しても、ｃは、最大フレーズ長を３とする１対１の句対応をエンコードする必要がある。すなわち、一方の文中の何れの単語も、他方の文中の最大３語に対し対応付けることができ、これらの語は隣接する必要がある。この制約は、式（７）のエッジポテンシャルにより、直接実施される。
【００３５】
（モデル推論）
一般的に、閉路を有さない図式モデルは、効率的かつ正確な推論アルゴリズムを実現させる。しかし、残念ながら、双方向モデルには無数の閉路が含まれる。インデックス（ｉ，ｊ）および（ｉ‘，ｊ’）の対毎に、グラフ中に以下の閉路が存在することになる:
ｃｉｊ→ｂｉ→ｃｉｊ‘→ａｊ’→
ｃｉ‘ｊ’→ｂｉ‘→ｃｉ’ｊ→ａｊ→ｃｉｊ
【００３６】
ａｊ−１およびａｊの間ならびにｂｉ−１およびｂｉの間の辺を介して、追加の閉路がグラフ中に存在する。
【００３７】
選択されたエッジポテンシャル関数のために、句の対応付けに対する非ゼロ確率割り当ての空間が制限され、双方向モデルにおける推論は、ＮＰ困難として知られる一般的な句の対応付けの問題の例である。
【００３８】
（双対分解）
図式モデル全体がループを有する一方、２つの重なり合う、閉路を有さない部分グラフが存在する。一方の部分グラフＧａが変数ａおよびｃに対応するすべての頂点を含む。他方の部分グラフＧｂは変数ｂおよびｃの頂点を含む。グラフ中の各辺は正確に２つの部分グラフのいずれか一方に属する。
【００３９】
双対分解推論アプローチにより、この部分グラフ構造の利用が実現する（例えば、Ａｌｅｘａｎｄｅｒ Ｍ． Ｒｕｓｈ， Ｄａｖｉｄ Ｓｏｎｔａｇ， Ｍｉｃｈａｅｌ Ｃｏｌｌｉｎｓ， ａｎｄ Ｔｏｍｍｉ Ｊａａｋｋｏｌａ， Ｏｎ ｄｕａｌ ｄｅｃｏｍｐｏｓｉｔｉｏｎ ａｎｄ ｌｉｎｅａｒ ｐｒｏｇｒａｍｍｉｎｇ ｒｅｌａｘａｔｉｏｎｓ ｆｏｒ ｎａｔｕｒａｌ ｌａｎｇｕａｇｅ ｐｒｏｃｅｓｓｉｎｇ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｍｐｉｒｉｃａｌ Ｍｅｔｈｏｄｓ ｉｎ Ｎａｔｕｒａｌ Ｌａｎｇｕａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， ２０１０を参照）。特に、正確な推論を、繰り返し、部分グラフ問題に適用し、部分グラフ問題のポテンシャルを調整して、完全問題の制約を反映させることができる。双対分解の技術は近年係り受け解析において最新の性能を見せている（例えば、Ｔｅｒｒｙ Ｋｏｏ， Ａｌｅｘａｎｄｅｒ Ｍ． Ｒｕｓｈ， Ｍｉｃｈａｅｌ Ｃｏｌｌｉｎｓ， Ｔｏｍｍｉ Ｊａａｋｋｏｌａ， ａｎｄ Ｄａｖｉｄ Ｓｏｎｔａｇ， Ｄｕａｌ ｄｅｃｏｍｐｏｓｉｔｉｏｎ ｆｏｒ ｐａｒｓｉｎｇ ｗｉｔｈ ｎｏｎ−ｐｒｏｊｅｃｔｉｖｅ ｈｅａｄ ａｕｔｏｍａｔａ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｍｐｉｒｉｃａｌ Ｍｅｔｈｏｄｓ ｉｎ Ｎａｔｕｒａｌ Ｌａｎｇｕａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， ２０１０を参照）。
【００４０】
（双対問題の定式化）
双方向モデルの双対分解推論手続きを説明するにあたり、まず、双方向図式モデルでの推論問題を、推論の算出を可能にする２つの重複した部分グラフを用いて再度定義する。ｃ（ａ）を、Ｇａに関連付けられたｃのコピーとし、ｃ（ｂ）を、Ｇｂに関連付けられたコピーとする。また、ｆ（ａ，ｃ（ａ））をＧａに対する割り当ての対数尤度とし、ｇ（ｂ，ｃ（ｂ））をＧｂに対する割り当ての対数尤度とする。さらに、Ｉを、ｃのすべての（ｉ，ｊ）に対する添字集合とする。そして、双方向モデルに対する最大尤度割り当てを、以下を最適化することにより決定する。
【数１５】
これにより:
【数１６】
【００４１】
この最適化問題のラングランジアン緩和はＬ（ａ，ｂ，ｃ（ａ），ｃ（ｂ），ｕ）＝
【数１７】
【００４２】
したがって、元の問題は、以下のように書き換えることができる。
【数１８】
そして、最大および最少の順番を入れ替えることにより、元の最適化問題の上解となる双対問題を形成することができる。この場合、双対問題を２項に分解され、これらはそれぞれ非循環部分グラフに対して局所的である。
【数１９】
【００４３】
図２は、双方向モデルをどのように２つの非循環モデルに分解するかを示す図である。２つのモデルはいずれもｃのコピーを含む。変数は図中にラベルとして示されている。
【００４４】
従来同様、２つの分離した最大化問題の推論を繰り返すことにより、ｕを算出することができる。
【００４５】
（部分グラフ推論）
固定のｕの式（９）の評価には、直鎖型図式モデルのビタビアルゴリズムのみが必要である。すなわち、標準ＨＭＭ（隠れマルコフモデル）アライナにより最大尤度対応を決定するのに用いるのと同様のアルゴリズムを採用することができる。
【００４６】
変数ａおよびｃ（ａ）を含む式（９）の最初の部分を検討する。
【数２０】
【００４７】
標準ＨＭＭアライナ推論では、頂点ポテンシャルはバイレキシカル確率Ｐ（ｆ｜ｅ）に相当する。これらの項は、ｆ（ａ，ｃ（ａ））に含まれている。
【００４８】
目的の追加の項を、直鎖モデルの頂点ポテンシャルに組み込むことも可能である。ａｊ＝ｉの場合、式（７）に定義されるエッジポテンシャルによると、ｃｉｊ＝１である。したがって、ａｊ＝ｉを設定することで、対応する頂点ポテンシャル
【数２１】
およびｅｘｐ（ｕ（ｉ，ｊ））が式（１０）に加えられる。ｉ‘≠ｉの場合、ａｊおよびｃｉ’ｊ間のエッジポテンシャルにより、式（１０）に対し何も寄与しないｃｉ‘ｊ＝０か、または、およびｅｘｐ（ｕ（ｉ’，ｊ）−α）を寄与するｃｉ‘ｊ＝１のいずれかとなる。したがって、ａｊの割り当ておよびのすべてのｃｉ’ｊの最適割り当ての最終的な効果を、以下の単一ポテンシャルＶｊ（ｉ）において得ることができる：
【数２２】
【００４９】
図３は、木構造を有する部分グラフＧａをどのように等価の鎖構造を有するモデルに、ａｊ＝１に対しｃｉ‘ｊを最適化することによりマッピングするかを示す図である。
【００５０】
このポテンシャルの定義により、式（１０）に定義されるソース側の部分グラフ推論問題を、ポテンシャル関数Ｖｊおよびμ（ａ）のみを含む単純な直鎖モデルに崩すことができる。したがって、一般的な木構造の図式モデルのソルバーよりも、高度に最適化された直鎖推論の実施を用いることができる。図３は、この変換を図示する。
【００５１】
等価のアプローチにより、以下の評価が可能になる。
【数２３】
【００５２】
（双対分解アルゴリズム）
固定のｕに対しての式（９）を効率的に評価する能力を備えることにより、双方向モデルの完全双対分解アルゴリズムを定義し、式（９）を最適化するｕを探索することができる。例えば、劣勾配降下により、そのようなｕを繰り返し探索することができる。また、繰り返し数とともに劣化する学習レートを用いてもよい。実際には、初期学習レートをαに設定することが好ましい。完全双対分解最適化手続きを、アルゴリズム１として以下に規定する。
【００５３】
アルゴリズム１が収束すると、式（１０）を最適化するｃ（ａ）の値と式（１１）を最適化するｃ（ｂ）の値とが同一となるｕが決定されたことになる。したがって、元の最適化問題、すなわち式（８）に対する解である。双対問題は元の問題に対する上解であるから、この解は式（８）に対して最適である。
アルゴリズム１ 双方向モデルの双対分解推論アルゴリズム
ｆｏｒ ｔ ＝ １ ｔｏ ｍａｘ ｉｔｅｒａｔｉｏｎｓ ｄｏ
【数２４】
【数２５】
【００５４】
（収束および早期停止）
双対分解アルゴリズムは、収束時に正確な推論方法を与える。（この最適性の証明は、確率伝播、サンプリングまたは擬似焼きなまし等の他の近似推論アルゴリズムからは得られない。）アルゴリズム１が収束しない場合であっても、アルゴリズムの出力は対応として解釈してよい。アルゴリズムから生成されたｕの値に基づき、ｃ（ａ）およびｃ（ｂ）の最適値を、式（１０）および式（１１）からそれぞれ求めることができる。これらの対応は異なることもあるが、完全に独立したアライナよりも、より類似する可能性が高い。これらの対応は、（和をとるなどして）手続き的に組み合わせる必要があるものの、その類似性ゆえに、組み合わせ手続きの重要性は低下する。
【００５５】
（推論プロパティ）
双対分解アルゴリズムに最大繰り返し数ｎが設定され、各繰り返しはシーケンスモデルの最適化を行うのみであるため、推論手続きは、全体で、元の有向アライナによる評価よりも定数倍のみ計算コストが高い。
【００５６】
さらに、ｕの値は文対に対して特定のものである。したがって、このアプローチは、分散アライナの実装における独立した有向モデルと比較しても、追加の通信オーバーヘッドを要さない。メモリ要件は基準値とほぼ同一である：ｕを、処理中に、文対毎に記憶する必要があるが、対応が推論されれば、直ちに破棄してよい。
【００５７】
１対１の句対応を生成する他のアプローチは、総じてコストが高い。特に、ＩＴＧモデルは時間Ｏ（｜ｅ｜３・｜ｆ｜３）を要するのに対し、アルゴリズム１はＯ（ｎ・（｜ｆ｜｜ｅ｜２＋｜ｅ｜｜ｆ｜２））のみ要する。
【００５８】
（機械翻訳システムコンテキスト）
図４は、機械翻訳システムにおける双方向モデルの位置を示す図である。
機械翻訳システムは、トレーニング時間中に動作するコンポーネントおよび翻時間中に動作するコンポーネントを備える。
【００５９】
トレーニング時間コンポーネントは、一対の言語の、正しく翻訳されたとみなされる文対よりなる並列コーパス４０２を含む。他のトレーニング時間コンポーネントは、対応付けモデルコンポーネント４０４であり、これは、並列コーパス４０２から文対を受信し、この文対から、対応付けされた並列コーパスを生成する。この並列コーパスは、句抽出コンポーネント４０６により受信される。双方向モデルは対応付けモデルコンポーネント４０４の一部であり、上記のように、文対中の単語間の対応を生成するのに用いられる。句抽出器は、翻訳された句および対応するスコアのスニペットを含むデータセットである、句テーブル４０８を生成する。
【００６０】
翻訳時間コンポーネントは、句テーブル４０８のデータから生成される翻訳モデル４２２を含む。翻訳時間コンポーネントは、さらに、言語モデル４２０、および、言語モデル４２０や翻訳モデル４２２を用いて、入力テキスト４２６から翻訳済み出力テキスト４２８を生成する機械翻訳コンポーネント４２４（例：統計的機械翻訳エンジン（コンピュータ、データおよびソフトウェアのシステム））を含む。
【００６１】
本明細書に記載の主題および機能動作の実施例は、デジタル電子回路、コンピュータソフトウェアまたはファームウェアの具体的な実施例、コンピュータハードウェア（本明細書中に開示の構造およびその構造的等価物を含む）、またはこれらの１つまたは複数を組み合わせることにより、実現できる。本明細書に記載の主題の実施例は、１つまたは複数のコンピュータプログラム、具体的には、データ処理装置により実行される、またはデータ処理装置の動作を制御する具体的なプログラムキャリア上にエンコードされた、１つまたは複数のコンピュータプログラム指示文のモジュール、として実現できる。これに代えて、またはこれに加えて、プログラム指示文を、機械的に生成され、データ処理装置により実行される情報を対応の受信装置に送信するためにエンコードする電気、光学または電磁波信号等の人工的に生成した伝播信号上にエンコードしてもよい。コンピュータ記憶媒体は、機械可読記憶装置、機械可読記憶基盤、ランダムまたはシリアルアクセスメモリ装置、またはこれらの１つまたは複数の組み合わせでよい。
【００６２】
「データ処理装置」という用語は、データを処理する装置、デバイスおよび機器のすべての種類を含み、さらに、例として、プログラマブルプロセッサ、コンピュータ、またはマルチプルプロセッサまたはコンピュータ等を含む。また、装置には、特定用途向け論理回路も含まれ、これは、例えば、ＦＰＧＡ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）やＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）である。さらに、ハードウェアに加えて、装置には、対象となるコンピュータプログラムの実行環境を作るコードが含まれ、これは、例えば、プロセッサファームウェアを構成するコード、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはこれらの１つまたは複数の組み合わせである。
【００６３】
コンピュータプログラム（「プログラム」、「ソフトウェア」、「ソフトウェアアプリケーション」、「スクリプト」、または「コード」と称する）は、コンパイラ言語、インタプリタ言語、宣言型言語、手続き型言語等、どの言語で記述してもよく、スタンドアローンのプログラムとして、または、モジュール、コンポーネント、サブルーチン、およびこれ以外の、コンピュータ環境に適したユニットの形式で用いることができる。コンピュータプログラムは、ファイルシステム中のファイルに対応することが好ましいが、これは必須ではない。プログラムは、他のプログラムまたはデータを保持するファイルの一部（例えば、マークアップ言語文書に記憶された１つまたは複数のスクリプト）、対象プログラム専用の単一ファイル、または複数の連携ファイル（例えば、１つまたは複数のモジュール、サブプログラム、コードの一部等を記憶するファイル）に記憶させることができる。また、プログラムは、１つのコンピュータまたは複数のコンピュータ上で実行して用いてよく、これらのコンピュータは、１箇所に設置しても、複数個所に分布させて通信ネットワークにより相互に接続してもよい。
【００６４】
本明細書に記載のプロセスおよび論理フローは、１つまたは複数のコンピュータプログラムを実行し、入力データにより動作し、出力を生成する機能を実行する、１つまたは複数のプログラマブルコンピュータにより実現できる。また、これらのプロセスまたは論理フローを、ＦＰＧＡ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）およびＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）等の、特定用途向け論理回路により実行してもよく、または、装置を、これら特定用途向け論理回路として実現してもよい。
【００６５】
コンピュータプログラムの実行に適したコンピュータとは、例えば、汎用または特定用途向けマイクロプロセッサ、またはこれらの両方、または他の中央処理装置を含む。通常、中央処理装置は、読み取り専用メモリまたはランダムアクセスメモリ、またはこれらの両方から、指示またはデータを受信する。コンピュータの必須要素は、指示を実現または実行する中央処理装置と、指示およびデータを記憶する１つまたは複数の記憶装置である。通常、コンピュータには、さらに、例えば、磁気、光磁気または光学ディスク等の、データを記憶するマス記憶装置を含むか、または、当該マス記憶装置に対しデータの送受信を行うことができるよう機能的に接続されているか、またはこれらの両方でもよい。しかし、コンピュータは、これらのデバイスを備える必要はない。さらに、コンピュータを、例として、携帯電話機、ＰＤＡ（Ｐｅｒｓｏｎａｌ Ｄｉｇｉｔａｌ Ａｓｓｉｓｔａｎｔ）、携帯型音声または映像再生装置、ゲームコンソール、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）受信機、または携帯型記憶装置（例：ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）フラッシュドライブ）等に埋め込んでもよい。
【００６６】
コンピュータプログラム指示文およびデータを記憶するのに適したコンピュータ読み取り可能な媒体には、すべての種類の不揮発性メモリ、メディア、およびメモリデバイスが含まれ、これには、例えば、ＥＰＲＯＭ，ＥＥＰＲＯＭおよびフラッシュ等の半導体メモリデバイス、内臓ハードディスクまたは外付けディスク等の磁気ディスク、光磁気ディスク、ならびにＣＤ−ＲＯＭおよびＤＶＤ−ＲＯＭディスクが含まれる。プロセッサ及びメモリは、特定用途向け論理回路により補強、または特定用途向け論理回路に組み込むことができる。
【００６７】
ユーザとの相互のやり取りを可能にするため、本明細書に記載の主題の実施例は、ユーザに向けて情報を表示するための表示装置（例：ＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）またはＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）モニタ）、キーボード、およびポインティングデバイス（例：ユーザがコンピュータに対し入力を行うことのできるようにするマウスまたはトラックボール）を備えるコンピュータ上で実現可能である。ユーザとの相互のやり取りを、他の種類のデバイスを用いて行うことも可能である。例えば、ユーザへのフィードバックは、視覚フィードバック、聴覚フィードバック、または触覚フィードバック等どのような形式の感覚フィードバックを用いてもよい。また、ユーザからの入力についても、楽音、音声、および触覚入力等どのような形でもよい。さらに、コンピュータは、例えば、ユーザのクライアントデバイス上のウェブブラウザから受信された要求に応じてウェブページを当該クライアントデバイスに送信する等、ユーザの使用するデバイスと文書の送受信を行うことにより、ユーザとやり取りを行うことができる。
【００６８】
本明細書は、特定の実現例の詳細を多く含んでいるが、これは保護の対象となる発明の範囲を権利範囲を限定するものと解釈されるべきものではなく、特定の発明の、特定の実施例に特化した特徴の説明と解釈されるべきである。本明細書中別々の実施例のコンテキストにおいて記載した特定の特徴は、組み合わせにより、単一の実施例として実現してもよい。一方、単一の実施例のコンテキストで記載された様々な特徴も、複数の実施例として別々に実現してもよく、また、適宜組み合わせて実現してもよい。さらに、上記の特徴は特定の組み合わせにおいて動作するように記載されその旨の主張もあるが、記載のある組み合わせから１つまたは複数の特徴を抽出し、当該記載の組み合わせを部分的な組み合わせ、または部分的な組み合わせの変更例としてもよい。
【００６９】
同様に、図面中の動作は特定の順序において描かれているが、これは、所望の結果を得るために、動作を図示の特定の順序において行うこと、または順番に行うこと、図示の動作をすべて行うことを要件とするものと理解されるべきものではない。特定の場合に、マルチタスクや並列処理が有利となることもある。さらに、上記の実施例における様々なシステムコンポーネントの分離は、すべての実施例においてそのような分離が要件であると解釈されるべきものではなく、また、記載のプログラムコンポーネントおよびシステムの全般は、単一のソフトウェア製品に統合すること、または複数のソフトウェア製品にパッケージ化することが可能であることに留意されたい。
【００７０】
本主題の特定の実施例を説明した。他の実施例も、以下の請求の範囲によりその権利範囲が定められる。例えば、請求の範囲に記載の動作を異なる順序で行って、所望の結果を得ることもできる。一例として、所望の結果を得るために、必ずしも図示の順序または順番において処理を行う必要はない。実現例によっては、マルチタスクや並列処理が有利な場合もある。
【技術分野】
【０００１】
（関連出願の相互参照）
本願は、３５Ｕ．Ｓ．Ｃ．§１１９（ｅ）に基づき、２０１０年１２月１７日出願の米国出願第６１／４２４，６０８号の出願日の効果を主張する。この優先権出願の開示内容は、本願の開示内容の一部とみなされ、参照により本願に含まれる。
【背景技術】
【０００２】
本明細書は統計的機械翻訳における単語の対応付けに関する。
単語（ｗｏｒｄ）の対応付けは、文（ｓｅｎｔｅｎｃｅ）対中の対応する単語を識別する、統計的機械翻訳（ＭＴ）における主要な機械学習タスクである。ＭＴシステムの大半は、文ｆの単語を、その翻訳文ｅの単語に対応付ける有向マルコフ対応付けモデルを採用する。
【０００３】
教師なし単語対応付けは、一般的に、文ｆを、その翻訳文ｅを条件として生成するマルコフプロセスとしてモデル化される。ｆからｅを生成する同様のモデルは、異なる対応付けを予測する。
【０００４】
システムは通常２つの有向モデルによる予測を組み合わせ、このうち一方がｆをｅに対応付け、他方がｅをｆに対応付ける。統計的機械翻訳システムは、２つの有向モデルによる予測を組み合わせる。この組み合わせにより、エラーを減少させ、有向モデルの１対多の構造的制約を緩和することができる。最も一般的な組み合わせの方法は、対応（ａｌｉｇｎｍｅｎｔ）の和集合（ｕｎｉｏｎ）および積集合（ｉｎｔｅｒｓｅｃｔｉｏｎ）を形成する方法、または、ｇｒｏｗ−ｄｉａｇ−ｆｉｎａｌ等のヒューリスティック手続きを適用する方法である（これは、例えば、Ｆｒａｎｚ Ｊｏｓｅｆ Ｏｃｈ， Ｃｈｒｉｓｔｏｐｈｅｒ Ｔｉｌｌｍａｎ， ａｎｄ Ｈｅｒｍａｎｎ Ｎｅｙ， Ｉｍｐｒｏｖｅｄ ａｌｉｇｎｍｅｎｔ ｍｏｄｅｌｓ ｆｏｒ ｓｔａｔｉｓｔｉｃａｌ ｍａｃｈｉｎｅ ｔｒａｎｓｌａｔｉｏｎ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｍｐｉｒｉｃａｌ Ｍｅｔｈｏｄｓ ｉｎ Ｎａｔｕｒａｌ Ｌａｎｇｕａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， １９９９に記載されている）。
【発明の概要】
【０００５】
本明細書は、２つの有向アライナを明示的に単一の結合モデルに組み合わせる図式モデルの構成および使用方法を説明する。推論は、有向モデルの効率的な推論アルゴリズムを再利用する双対分解により行うことができる。組み合わせモデルは１対１の句（ｐｈｒａｓｅ）制約を実施し、対応付けの品質を向上させる。
【０００６】
本明細書の主題の１つまたは複数の実施例の詳細は、添付の図面および以下の説明を参照して明らかになる。また、本主題の他の特徴、態様および利点についても、明細書、図面および特許請求の範囲より明らかになる。
【図面の簡単な説明】
【０００７】
【図１】英語と中国語の単純な文対に対する双方向図式モデルのグラフ構成を示す図である。
【図２】双方向モデルをどのように２つの非循環モデルに分解するかを示す図である。
【図３】木構造を有する部分グラフＧａをどのように等価の鎖構造を有するモデルに最適化によりマッピングするかを示す図である。
【図４】機械翻訳システムにおける双方向モデルの位置を示す図である。図面中の同一の参照記号は同一の構成要素を示す。
【発明を実施するための形態】
【０００８】
（イントロダクション）
本明細書は、アライナの組み合わせに対する、モデルベースの代替案であり、２つの有向対応付けモデルの相反する予測を、これら２つの有向対応付けモデルをより大規模な図式モデル中に埋め込むことにより解消する代替案を説明する（以下「双方向モデル」と称する）。
【０００９】
双方向モデルにおける潜在変数は、２つの有向マルコフ対応付けモデルにおける潜在変数の真の上位集合である。このモデルの構成およびポテンシャルは２つの有向モデル間の不一致を許容し、一致を与える。さらに、双方向モデルは、１対１の句対応付け構造を実施し、これにより、句対応付けモデル、同期ＩＴＧ（Ｉｎｖｅｒｓｉｏｎ Ｔｒａｎｓｄｕｃｔｉｏｎ Ｇｒａｍｍａｒ）モデルおよび最新の教師ありモデルに示されるのと同様の構造的利点を得る。
【００１０】
双方向モデルでは、モデルグラフ中に辺のサイクルが多く存在するため、推論を計算することができない。しかし、近似推論法の１つとして、双対分解を用いることができる。組み合わせモデル空間を探索するため、潜在的なマルコフ対応付けモデルの効率的なシーケンスアルゴリズムを、繰り返し適用することができる。この近似が収束した場合、完全モデルによる最適性の証明を得たことになる。
【００１１】
アライナの組み合わせに対するこのモデルベースのアプローチは、対応付けおよび句抽出の品質を向上させる。
【００１２】
（モデル定義）
双方向モデルは、頂点（ｖｅｒｔｅｘ）集合Ｖおよび辺（ｅｄｇｅ）集合Ｄにより定義される図式モデルであり、文ｅおよびその翻訳文ｆの長さを条件として構築される。各頂点はモデル変数Ｖｉに対応し、各無向辺は変数の対(Ｖｉ，Ｖｊ)に対応する。各頂点は、対応する頂点ポテンシャル関数ｖｉ（ｖｊ）を有し、この関数は実数値を有するポテンシャルをＶｉの採り得る値ｖｉのそれぞれに対し割り当てる。同様に、各辺は、１対の値を有する、対応するポテンシャル関数μｉｊ（ｖｉ，ｖｊ）を有する。モデル変数に対する完全な割り当てｖのモデルによる確率はＶとインデックス付けされ、頂点および辺のポテンシャルを考慮に入れたものである。
【数１】
【００１３】
双方向モデルは、２つの有向隠れマルコフ対応付けモデル、および、これらの埋め込まれたモデルによる予測を単一の対称単語対にする追加の構成を含む。以下のパラグラフでは、まず有向モデルを説明し、それから、２つの有向モデルを結合双方向モデルに組み合わせる追加構成を説明する。
【００１４】
（隠れマルコフ対応付けモデル）
ここでは、従来の隠れマルコフ対応付けモデルを説明する（これは、例えば、Ｓｔｅｐｈａｎ Ｖｏｇｅｌ， Ｈｅｒｍａｎｎ Ｎｅｙ， ａｎｄ Ｃｈｒｉｓｔｏｐｈ Ｔｉｌｌｍａｎｎ， ＨＭＭ−Ｂａｓｅｄ Ｗｏｒｄ， Ａｌｉｇｎｍｅｎｔ ｉｎ Ｓｔａｔｉｓｔｉｃａｌ Ｔｒａｎｓｌａｔｉｏｎ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １６ｔｈ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｌｉｎｇｕｉｓｔｉｃｓ， １９９６に記載されている）。本モデルは、単語シーケンスｅを条件とする単語シーケンスｆを生成する。従来、ｅの単語はｉとインデックス付けされ、ｆはｊとインデックス付けされる。Ｐ（ｆ｜ｅ）は潜在対応ベクトルａにより定義され、ここで、ａｊ＝ｉはｅの単語位置ｉがｆの単語位置ｊに対応づけられることを示す。
【数２】
【００１５】
上式（２）において、放射モデルＭは、単語の種類による、学習済み多項分布を示す。遷移モデルＤは、遷移距離による多項式であり、ヌル対応は例外として扱われる。
【数３】
ｃ（ｉ‘−ｉ）は符号付き距離による学習済み分布であり、ｉからの、可能性のある遷移に対して正規化されている。
【００１６】
条件付き多項式Ｍのパラメータ、遷移モデルｃおよびヌル遷移パラメータｐｏはすべて、文を対応付けたコーパスから期待値最大化アルゴリズムにより学習可能である。
【００１７】
所与の文対（ｅ，ｆ）に対するモデルによる単語対応ベクトルの最大確率は、標準ビタビアルゴリズムを、時間Ｏ（｜ｅ｜２・｜ｆ｜）において、隠れマルコフモデルに対して用いることにより、正確に算出することができる。
【００１８】
対応ベクトルａは、単語対応リンクの集合Ａに明らかに変換可能である。
Ａａ＝｛（ｉ，ｊ）：ａｊ＝ｉ，ｉ≠０｝．
【００１９】
このように構築された集合Ａは常に１対多である。多数の位置ｊを同一のｉに対応付けることも可能だが、各ｊは、集合中に最大１回のみ出現する。
【００２０】
上記説明はｅからｆを生成する有向モデルを定義した。同様に構成された、ｆからｅを生成するモデルを定義することも可能である。対応のベクトルをｂとし、ｂｉ＝ｊはｆの単語位置ｊはｅの単語位置ｉに対応付けられるものとする。そして、Ｐ（ｅ，ｂ｜ｆ）も式（２）同様に定義できるが、ｅとｆとが入れ替わる。２つのモデルの遷移分布および放出分布は、モデルの生成方向ｆ→ｅまたはｅ→ｆを示すサブスクリプトにより区別される。
【数４】
【００２１】
ベクトルｂは１対多対応リンクの集合と解釈できる：各値ｉは最大１回のみ集合中に出現する。
Ａｂ＝｛（ｉ，ｊ）：ｂｉ＝ｊ，ｊ≠０｝．
【００２２】
（アライナ組み合わせのモデル）
以下に説明するように、アライナを組み合わせることにより、双方向モデルを作成することができる。これは、２つの有向アライナのすべてのランダム変数およびアライナ間の一致を促して差異を解消する追加構成を含む図式モデル中に、アライナを埋め込むことにより実現できる。
【００２３】
双方向モデルは、観測対象の単語シーケンスｅおよびｆ、ならびに上に定義された対応変数ａおよびｂの２つのベクトルを含む。
【００２４】
ｅおよびｆの単語の種類および長さは常に観測対象の文対により固定されるため、変数ａおよびｂのみを用いて同一のモデルを定義することができる。この場合、ａｊ，ｆｊおよびｅ間のエッジポテンシャルは、ａｊの頂点ポテンシャル
【数５】
にコンパイルされ、fおよびeにより定義され、いずれのｂｉについても同様である。
【数６】
【数７】
【００２５】
図１は、英語と中国語の単純な文対に対する双方向図式モデルのグラフ構成を示す図である。変数ａ、ｂおよびｃ（以下に説明）は、図中、ラベルにより示される。
【００２６】
ａおよびｂ間のエッジポテンシャルは式（２）の遷移モデルをエンコードする。
【数８】
【数９】
【００２７】
さらに、ランダムビット行列ｃは、組み合わせアライナの出力をエンコードする。
【数１０】
【００２８】
各ランダム変数
【数１１】
は、ａｊおよびｂｉに接続している。これらコヒーレンスエッジが、有向モデルの対応変数を、組み合わせ空間のブーリアン変数に接続する。これらの辺により、モデルが変数ａ、ｂおよびｃの３つの集合をエンコードし、さらに、文対のコヒーレント対応解析をエンコードすることが可能になる。図１はモデルのグラフ構成を図示する。
【００２９】
（コヒーレンスポテンシャル）
コヒーレンスエッジのポテンシャルは、学習されず、また、データセット中のいかなるパターンも表わさない。代わりに、これらは、整数値を有する有向変数ａおよびｂ、ならびにブーリアン値を有する組み合わせ変数ｃの整合性を促す固定関数である。
【００３０】
変数の割り当てａｊ＝ｉを考えると、ｉ＝０はｆｊがヌル対応であり、ｉ＞０はｆｊがｅｉに対応付けられることを示す。コヒーレンスポテンシャルは、変数割り当てａｊ＝ｉといずれかのｉ‘：０＜ｉ’ ≦｜ｅ｜の変数ｃｉ‘ｊとの間に、以下の関係性を成立させる。
・ｉ＝０（ヌル対応）の場合、すべてのｃｉ‘ｊ＝０
・ｉ＞０の場合、ｃｉｊ＝１
・
【数１２】
の場合のみ、ｃｉ’ｊ＞０
・ｉ‘≠ｉに対しｃｉ’ｊ＝１を割り当てることは、コストｅ−αを要し、αは学習済定数である（例：０．３）
【００３１】
この効果のパターンは、各辺において、ポテンシャル関数μ（ｃ）でエンコードすることができる。これらのエッジポテンシャル関数はそれぞれ変数ａｊに対して整数値ｉを採り、ｃｉ‘ｊに対してバイナリ値ｋを採る。
【数１３】
ｂおよびｃ間の辺のポテンシャル
【数１４】
も同様に定義される。
【００３２】
（モデルプロパティ）
行列ｃは、双方向モデルにより生成される最終的な対応と解釈され、ここでａおよびｂは無視する。このように、有向モデルの１対多の制約が緩和される。しかし、どのように単語が対応付けられるかについての情報はすべてａおよびｂの頂点および辺のポテンシャルにより表わされる。コヒーレンスエッジおよびリンク行列ｃは、有向モデル間の矛盾を解消し、両者間で情報のやり取りを行うのみである。
【００３３】
有向対応は双方向モデルのコンポーネントとしてそのまま維持されるため、潜在的有向マルコフ対応付けモデルに対する、レキシカライズド遷移モデル（これは、例えば、Ｘｉａｏｄｏｎｇ Ｈｅ， Ｕｓｉｎｇ ｗｏｒｄ−ｄｅｐｅｎｄｅｎｔ ｔｒａｎｓｉｔｉｏｎ ｍｏｄｅｌｓ ｉｎ ＨＭＭ ｂａｓｅｄ ｗｏｒｄ ａｌｉｇｎｍｅｎｔ ｆｏｒ ｓｔａｔｉｓｔｉｃａｌ ｍａｃｈｉｎｅ， ｉｎ ＡＣＬ Ｗｏｒｋｓｈｏｐ ｏｎ Ｓｔａｔｉｓｔｉｃａｌ Ｍａｃｈｉｎｅ Ｔｒａｎｓｌａｔｉｏｎ， ２００７に記載されている）、拡張調整コンテキスト（これは、例えば、Ｊａｍｉｅ Ｂｒｕｎｎｉｎｇ， Ａｄｒｉａ ｄｅ Ｇｉｓｐｅｒｔ， ａｎｄ Ｗｉｌｌｉａｍ Ｂｙｒｎｅ， Ｃｏｎｔｅｘｔ−ｄｅｐｅｎｄｅｎｔ ａｌｉｇｎｍｅｎｔ ｍｏｄｅｌｓ ｆｏｒ ｓｔａｔｉｓｔｉｃａｌ ｍａｃｈｉｎｅ ｔｒａｎｓｌａｔｉｏｎ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｎｏｒｔｈ Ａｍｅｒｉｃａｎ Ｃｈａｐｔｅｒ ｏｆ ｔｈｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｌｉｎｇｕｉｓｔｉｃｓ， ２００９に記載されている）、および外部情報（これは、例えば、進藤裕之、藤野昭典、永田昌明、Ｗｏｒｄ ａｌｉｇｎｍｅｎｔ ｗｉｔｈ ｓｙｎｏｎｙｍ ｒｅｇｕｌａｒｉｚａｔｉｏｎ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ａｓｓｏｃｉａｔｉｏｎ ｆｏｒ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｌｉｎｇｕｉｓｔｉｃｓ， ２０１０に記載されている）等を含む拡張や洗練化は、容易に双方向モデルへの組み込みが可能である。
【００３４】
（ａ，ｂ，ｃ）に対するいずれの非ゼロ確率の割り当てに対しても、ｃは、最大フレーズ長を３とする１対１の句対応をエンコードする必要がある。すなわち、一方の文中の何れの単語も、他方の文中の最大３語に対し対応付けることができ、これらの語は隣接する必要がある。この制約は、式（７）のエッジポテンシャルにより、直接実施される。
【００３５】
（モデル推論）
一般的に、閉路を有さない図式モデルは、効率的かつ正確な推論アルゴリズムを実現させる。しかし、残念ながら、双方向モデルには無数の閉路が含まれる。インデックス（ｉ，ｊ）および（ｉ‘，ｊ’）の対毎に、グラフ中に以下の閉路が存在することになる:
ｃｉｊ→ｂｉ→ｃｉｊ‘→ａｊ’→
ｃｉ‘ｊ’→ｂｉ‘→ｃｉ’ｊ→ａｊ→ｃｉｊ
【００３６】
ａｊ−１およびａｊの間ならびにｂｉ−１およびｂｉの間の辺を介して、追加の閉路がグラフ中に存在する。
【００３７】
選択されたエッジポテンシャル関数のために、句の対応付けに対する非ゼロ確率割り当ての空間が制限され、双方向モデルにおける推論は、ＮＰ困難として知られる一般的な句の対応付けの問題の例である。
【００３８】
（双対分解）
図式モデル全体がループを有する一方、２つの重なり合う、閉路を有さない部分グラフが存在する。一方の部分グラフＧａが変数ａおよびｃに対応するすべての頂点を含む。他方の部分グラフＧｂは変数ｂおよびｃの頂点を含む。グラフ中の各辺は正確に２つの部分グラフのいずれか一方に属する。
【００３９】
双対分解推論アプローチにより、この部分グラフ構造の利用が実現する（例えば、Ａｌｅｘａｎｄｅｒ Ｍ． Ｒｕｓｈ， Ｄａｖｉｄ Ｓｏｎｔａｇ， Ｍｉｃｈａｅｌ Ｃｏｌｌｉｎｓ， ａｎｄ Ｔｏｍｍｉ Ｊａａｋｋｏｌａ， Ｏｎ ｄｕａｌ ｄｅｃｏｍｐｏｓｉｔｉｏｎ ａｎｄ ｌｉｎｅａｒ ｐｒｏｇｒａｍｍｉｎｇ ｒｅｌａｘａｔｉｏｎｓ ｆｏｒ ｎａｔｕｒａｌ ｌａｎｇｕａｇｅ ｐｒｏｃｅｓｓｉｎｇ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｍｐｉｒｉｃａｌ Ｍｅｔｈｏｄｓ ｉｎ Ｎａｔｕｒａｌ Ｌａｎｇｕａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， ２０１０を参照）。特に、正確な推論を、繰り返し、部分グラフ問題に適用し、部分グラフ問題のポテンシャルを調整して、完全問題の制約を反映させることができる。双対分解の技術は近年係り受け解析において最新の性能を見せている（例えば、Ｔｅｒｒｙ Ｋｏｏ， Ａｌｅｘａｎｄｅｒ Ｍ． Ｒｕｓｈ， Ｍｉｃｈａｅｌ Ｃｏｌｌｉｎｓ， Ｔｏｍｍｉ Ｊａａｋｋｏｌａ， ａｎｄ Ｄａｖｉｄ Ｓｏｎｔａｇ， Ｄｕａｌ ｄｅｃｏｍｐｏｓｉｔｉｏｎ ｆｏｒ ｐａｒｓｉｎｇ ｗｉｔｈ ｎｏｎ−ｐｒｏｊｅｃｔｉｖｅ ｈｅａｄ ａｕｔｏｍａｔａ， ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｅｍｐｉｒｉｃａｌ Ｍｅｔｈｏｄｓ ｉｎ Ｎａｔｕｒａｌ Ｌａｎｇｕａｇｅ Ｐｒｏｃｅｓｓｉｎｇ， ２０１０を参照）。
【００４０】
（双対問題の定式化）
双方向モデルの双対分解推論手続きを説明するにあたり、まず、双方向図式モデルでの推論問題を、推論の算出を可能にする２つの重複した部分グラフを用いて再度定義する。ｃ（ａ）を、Ｇａに関連付けられたｃのコピーとし、ｃ（ｂ）を、Ｇｂに関連付けられたコピーとする。また、ｆ（ａ，ｃ（ａ））をＧａに対する割り当ての対数尤度とし、ｇ（ｂ，ｃ（ｂ））をＧｂに対する割り当ての対数尤度とする。さらに、Ｉを、ｃのすべての（ｉ，ｊ）に対する添字集合とする。そして、双方向モデルに対する最大尤度割り当てを、以下を最適化することにより決定する。
【数１５】
これにより:
【数１６】
【００４１】
この最適化問題のラングランジアン緩和はＬ（ａ，ｂ，ｃ（ａ），ｃ（ｂ），ｕ）＝
【数１７】
【００４２】
したがって、元の問題は、以下のように書き換えることができる。
【数１８】
そして、最大および最少の順番を入れ替えることにより、元の最適化問題の上解となる双対問題を形成することができる。この場合、双対問題を２項に分解され、これらはそれぞれ非循環部分グラフに対して局所的である。
【数１９】
【００４３】
図２は、双方向モデルをどのように２つの非循環モデルに分解するかを示す図である。２つのモデルはいずれもｃのコピーを含む。変数は図中にラベルとして示されている。
【００４４】
従来同様、２つの分離した最大化問題の推論を繰り返すことにより、ｕを算出することができる。
【００４５】
（部分グラフ推論）
固定のｕの式（９）の評価には、直鎖型図式モデルのビタビアルゴリズムのみが必要である。すなわち、標準ＨＭＭ（隠れマルコフモデル）アライナにより最大尤度対応を決定するのに用いるのと同様のアルゴリズムを採用することができる。
【００４６】
変数ａおよびｃ（ａ）を含む式（９）の最初の部分を検討する。
【数２０】
【００４７】
標準ＨＭＭアライナ推論では、頂点ポテンシャルはバイレキシカル確率Ｐ（ｆ｜ｅ）に相当する。これらの項は、ｆ（ａ，ｃ（ａ））に含まれている。
【００４８】
目的の追加の項を、直鎖モデルの頂点ポテンシャルに組み込むことも可能である。ａｊ＝ｉの場合、式（７）に定義されるエッジポテンシャルによると、ｃｉｊ＝１である。したがって、ａｊ＝ｉを設定することで、対応する頂点ポテンシャル
【数２１】
およびｅｘｐ（ｕ（ｉ，ｊ））が式（１０）に加えられる。ｉ‘≠ｉの場合、ａｊおよびｃｉ’ｊ間のエッジポテンシャルにより、式（１０）に対し何も寄与しないｃｉ‘ｊ＝０か、または、およびｅｘｐ（ｕ（ｉ’，ｊ）−α）を寄与するｃｉ‘ｊ＝１のいずれかとなる。したがって、ａｊの割り当ておよびのすべてのｃｉ’ｊの最適割り当ての最終的な効果を、以下の単一ポテンシャルＶｊ（ｉ）において得ることができる：
【数２２】
【００４９】
図３は、木構造を有する部分グラフＧａをどのように等価の鎖構造を有するモデルに、ａｊ＝１に対しｃｉ‘ｊを最適化することによりマッピングするかを示す図である。
【００５０】
このポテンシャルの定義により、式（１０）に定義されるソース側の部分グラフ推論問題を、ポテンシャル関数Ｖｊおよびμ（ａ）のみを含む単純な直鎖モデルに崩すことができる。したがって、一般的な木構造の図式モデルのソルバーよりも、高度に最適化された直鎖推論の実施を用いることができる。図３は、この変換を図示する。
【００５１】
等価のアプローチにより、以下の評価が可能になる。
【数２３】
【００５２】
（双対分解アルゴリズム）
固定のｕに対しての式（９）を効率的に評価する能力を備えることにより、双方向モデルの完全双対分解アルゴリズムを定義し、式（９）を最適化するｕを探索することができる。例えば、劣勾配降下により、そのようなｕを繰り返し探索することができる。また、繰り返し数とともに劣化する学習レートを用いてもよい。実際には、初期学習レートをαに設定することが好ましい。完全双対分解最適化手続きを、アルゴリズム１として以下に規定する。
【００５３】
アルゴリズム１が収束すると、式（１０）を最適化するｃ（ａ）の値と式（１１）を最適化するｃ（ｂ）の値とが同一となるｕが決定されたことになる。したがって、元の最適化問題、すなわち式（８）に対する解である。双対問題は元の問題に対する上解であるから、この解は式（８）に対して最適である。
アルゴリズム１ 双方向モデルの双対分解推論アルゴリズム
ｆｏｒ ｔ ＝ １ ｔｏ ｍａｘ ｉｔｅｒａｔｉｏｎｓ ｄｏ
【数２４】
【数２５】
【００５４】
（収束および早期停止）
双対分解アルゴリズムは、収束時に正確な推論方法を与える。（この最適性の証明は、確率伝播、サンプリングまたは擬似焼きなまし等の他の近似推論アルゴリズムからは得られない。）アルゴリズム１が収束しない場合であっても、アルゴリズムの出力は対応として解釈してよい。アルゴリズムから生成されたｕの値に基づき、ｃ（ａ）およびｃ（ｂ）の最適値を、式（１０）および式（１１）からそれぞれ求めることができる。これらの対応は異なることもあるが、完全に独立したアライナよりも、より類似する可能性が高い。これらの対応は、（和をとるなどして）手続き的に組み合わせる必要があるものの、その類似性ゆえに、組み合わせ手続きの重要性は低下する。
【００５５】
（推論プロパティ）
双対分解アルゴリズムに最大繰り返し数ｎが設定され、各繰り返しはシーケンスモデルの最適化を行うのみであるため、推論手続きは、全体で、元の有向アライナによる評価よりも定数倍のみ計算コストが高い。
【００５６】
さらに、ｕの値は文対に対して特定のものである。したがって、このアプローチは、分散アライナの実装における独立した有向モデルと比較しても、追加の通信オーバーヘッドを要さない。メモリ要件は基準値とほぼ同一である：ｕを、処理中に、文対毎に記憶する必要があるが、対応が推論されれば、直ちに破棄してよい。
【００５７】
１対１の句対応を生成する他のアプローチは、総じてコストが高い。特に、ＩＴＧモデルは時間Ｏ（｜ｅ｜３・｜ｆ｜３）を要するのに対し、アルゴリズム１はＯ（ｎ・（｜ｆ｜｜ｅ｜２＋｜ｅ｜｜ｆ｜２））のみ要する。
【００５８】
（機械翻訳システムコンテキスト）
図４は、機械翻訳システムにおける双方向モデルの位置を示す図である。
機械翻訳システムは、トレーニング時間中に動作するコンポーネントおよび翻時間中に動作するコンポーネントを備える。
【００５９】
トレーニング時間コンポーネントは、一対の言語の、正しく翻訳されたとみなされる文対よりなる並列コーパス４０２を含む。他のトレーニング時間コンポーネントは、対応付けモデルコンポーネント４０４であり、これは、並列コーパス４０２から文対を受信し、この文対から、対応付けされた並列コーパスを生成する。この並列コーパスは、句抽出コンポーネント４０６により受信される。双方向モデルは対応付けモデルコンポーネント４０４の一部であり、上記のように、文対中の単語間の対応を生成するのに用いられる。句抽出器は、翻訳された句および対応するスコアのスニペットを含むデータセットである、句テーブル４０８を生成する。
【００６０】
翻訳時間コンポーネントは、句テーブル４０８のデータから生成される翻訳モデル４２２を含む。翻訳時間コンポーネントは、さらに、言語モデル４２０、および、言語モデル４２０や翻訳モデル４２２を用いて、入力テキスト４２６から翻訳済み出力テキスト４２８を生成する機械翻訳コンポーネント４２４（例：統計的機械翻訳エンジン（コンピュータ、データおよびソフトウェアのシステム））を含む。
【００６１】
本明細書に記載の主題および機能動作の実施例は、デジタル電子回路、コンピュータソフトウェアまたはファームウェアの具体的な実施例、コンピュータハードウェア（本明細書中に開示の構造およびその構造的等価物を含む）、またはこれらの１つまたは複数を組み合わせることにより、実現できる。本明細書に記載の主題の実施例は、１つまたは複数のコンピュータプログラム、具体的には、データ処理装置により実行される、またはデータ処理装置の動作を制御する具体的なプログラムキャリア上にエンコードされた、１つまたは複数のコンピュータプログラム指示文のモジュール、として実現できる。これに代えて、またはこれに加えて、プログラム指示文を、機械的に生成され、データ処理装置により実行される情報を対応の受信装置に送信するためにエンコードする電気、光学または電磁波信号等の人工的に生成した伝播信号上にエンコードしてもよい。コンピュータ記憶媒体は、機械可読記憶装置、機械可読記憶基盤、ランダムまたはシリアルアクセスメモリ装置、またはこれらの１つまたは複数の組み合わせでよい。
【００６２】
「データ処理装置」という用語は、データを処理する装置、デバイスおよび機器のすべての種類を含み、さらに、例として、プログラマブルプロセッサ、コンピュータ、またはマルチプルプロセッサまたはコンピュータ等を含む。また、装置には、特定用途向け論理回路も含まれ、これは、例えば、ＦＰＧＡ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）やＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）である。さらに、ハードウェアに加えて、装置には、対象となるコンピュータプログラムの実行環境を作るコードが含まれ、これは、例えば、プロセッサファームウェアを構成するコード、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはこれらの１つまたは複数の組み合わせである。
【００６３】
コンピュータプログラム（「プログラム」、「ソフトウェア」、「ソフトウェアアプリケーション」、「スクリプト」、または「コード」と称する）は、コンパイラ言語、インタプリタ言語、宣言型言語、手続き型言語等、どの言語で記述してもよく、スタンドアローンのプログラムとして、または、モジュール、コンポーネント、サブルーチン、およびこれ以外の、コンピュータ環境に適したユニットの形式で用いることができる。コンピュータプログラムは、ファイルシステム中のファイルに対応することが好ましいが、これは必須ではない。プログラムは、他のプログラムまたはデータを保持するファイルの一部（例えば、マークアップ言語文書に記憶された１つまたは複数のスクリプト）、対象プログラム専用の単一ファイル、または複数の連携ファイル（例えば、１つまたは複数のモジュール、サブプログラム、コードの一部等を記憶するファイル）に記憶させることができる。また、プログラムは、１つのコンピュータまたは複数のコンピュータ上で実行して用いてよく、これらのコンピュータは、１箇所に設置しても、複数個所に分布させて通信ネットワークにより相互に接続してもよい。
【００６４】
本明細書に記載のプロセスおよび論理フローは、１つまたは複数のコンピュータプログラムを実行し、入力データにより動作し、出力を生成する機能を実行する、１つまたは複数のプログラマブルコンピュータにより実現できる。また、これらのプロセスまたは論理フローを、ＦＰＧＡ（Ｆｉｅｌｄ Ｐｒｏｇｒａｍｍａｂｌｅ Ｇａｔｅ Ａｒｒａｙ）およびＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ−Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）等の、特定用途向け論理回路により実行してもよく、または、装置を、これら特定用途向け論理回路として実現してもよい。
【００６５】
コンピュータプログラムの実行に適したコンピュータとは、例えば、汎用または特定用途向けマイクロプロセッサ、またはこれらの両方、または他の中央処理装置を含む。通常、中央処理装置は、読み取り専用メモリまたはランダムアクセスメモリ、またはこれらの両方から、指示またはデータを受信する。コンピュータの必須要素は、指示を実現または実行する中央処理装置と、指示およびデータを記憶する１つまたは複数の記憶装置である。通常、コンピュータには、さらに、例えば、磁気、光磁気または光学ディスク等の、データを記憶するマス記憶装置を含むか、または、当該マス記憶装置に対しデータの送受信を行うことができるよう機能的に接続されているか、またはこれらの両方でもよい。しかし、コンピュータは、これらのデバイスを備える必要はない。さらに、コンピュータを、例として、携帯電話機、ＰＤＡ（Ｐｅｒｓｏｎａｌ Ｄｉｇｉｔａｌ Ａｓｓｉｓｔａｎｔ）、携帯型音声または映像再生装置、ゲームコンソール、ＧＰＳ（Ｇｌｏｂａｌ Ｐｏｓｉｔｉｏｎｉｎｇ Ｓｙｓｔｅｍ）受信機、または携帯型記憶装置（例：ＵＳＢ（Ｕｎｉｖｅｒｓａｌ Ｓｅｒｉａｌ Ｂｕｓ）フラッシュドライブ）等に埋め込んでもよい。
【００６６】
コンピュータプログラム指示文およびデータを記憶するのに適したコンピュータ読み取り可能な媒体には、すべての種類の不揮発性メモリ、メディア、およびメモリデバイスが含まれ、これには、例えば、ＥＰＲＯＭ，ＥＥＰＲＯＭおよびフラッシュ等の半導体メモリデバイス、内臓ハードディスクまたは外付けディスク等の磁気ディスク、光磁気ディスク、ならびにＣＤ−ＲＯＭおよびＤＶＤ−ＲＯＭディスクが含まれる。プロセッサ及びメモリは、特定用途向け論理回路により補強、または特定用途向け論理回路に組み込むことができる。
【００６７】
ユーザとの相互のやり取りを可能にするため、本明細書に記載の主題の実施例は、ユーザに向けて情報を表示するための表示装置（例：ＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）またはＬＣＤ（Ｌｉｑｕｉｄ Ｃｒｙｓｔａｌ Ｄｉｓｐｌａｙ）モニタ）、キーボード、およびポインティングデバイス（例：ユーザがコンピュータに対し入力を行うことのできるようにするマウスまたはトラックボール）を備えるコンピュータ上で実現可能である。ユーザとの相互のやり取りを、他の種類のデバイスを用いて行うことも可能である。例えば、ユーザへのフィードバックは、視覚フィードバック、聴覚フィードバック、または触覚フィードバック等どのような形式の感覚フィードバックを用いてもよい。また、ユーザからの入力についても、楽音、音声、および触覚入力等どのような形でもよい。さらに、コンピュータは、例えば、ユーザのクライアントデバイス上のウェブブラウザから受信された要求に応じてウェブページを当該クライアントデバイスに送信する等、ユーザの使用するデバイスと文書の送受信を行うことにより、ユーザとやり取りを行うことができる。
【００６８】
本明細書は、特定の実現例の詳細を多く含んでいるが、これは保護の対象となる発明の範囲を権利範囲を限定するものと解釈されるべきものではなく、特定の発明の、特定の実施例に特化した特徴の説明と解釈されるべきである。本明細書中別々の実施例のコンテキストにおいて記載した特定の特徴は、組み合わせにより、単一の実施例として実現してもよい。一方、単一の実施例のコンテキストで記載された様々な特徴も、複数の実施例として別々に実現してもよく、また、適宜組み合わせて実現してもよい。さらに、上記の特徴は特定の組み合わせにおいて動作するように記載されその旨の主張もあるが、記載のある組み合わせから１つまたは複数の特徴を抽出し、当該記載の組み合わせを部分的な組み合わせ、または部分的な組み合わせの変更例としてもよい。
【００６９】
同様に、図面中の動作は特定の順序において描かれているが、これは、所望の結果を得るために、動作を図示の特定の順序において行うこと、または順番に行うこと、図示の動作をすべて行うことを要件とするものと理解されるべきものではない。特定の場合に、マルチタスクや並列処理が有利となることもある。さらに、上記の実施例における様々なシステムコンポーネントの分離は、すべての実施例においてそのような分離が要件であると解釈されるべきものではなく、また、記載のプログラムコンポーネントおよびシステムの全般は、単一のソフトウェア製品に統合すること、または複数のソフトウェア製品にパッケージ化することが可能であることに留意されたい。
【００７０】
本主題の特定の実施例を説明した。他の実施例も、以下の請求の範囲によりその権利範囲が定められる。例えば、請求の範囲に記載の動作を異なる順序で行って、所望の結果を得ることもできる。一例として、所望の結果を得るために、必ずしも図示の順序または順番において処理を行う必要はない。実現例によっては、マルチタスクや並列処理が有利な場合もある。
【特許請求の範囲】
【請求項１】
文の対に対する２つの有向対応付けモデルを表わすデータを受信し、前記対の一方の文は第１言語であり、前記対の他方の文は異なる第２の言語であり、
前記２つの有向対応付けモデルから組み合わせ双方向対応付けモデルを導出し、
前記双方向対応付けモデルを評価し、前記双方向対応付けモデルの評価から前記文の対に対する対応を導出することを特徴とする方法。
【請求項２】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項１記載の方法。
【請求項３】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項２記載の方法。
【請求項４】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項１記載の方法。
【請求項５】
前記双方向対応付けモデルを評価して２つの対応の解を生成し、第１の解は前記第１の言語から前記第２の言語への方向である第１の方向での対応付けモデルであり、第２の解は前記第２の言語から前記第１の言語への方向である第２の方向での対応付けモデルであり、
前記文の対に対する対応は、第１の対応付けモデルと第２の対応付けモデルとを組み合わせて導出することを特徴とする請求項４記載の方法。
【請求項６】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項５記載の方法。
【請求項７】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項６記載の方法。
【請求項８】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項１記載の方法。
【請求項９】
コンピュータプログラムがエンコードされた非一時的コンピュータ記憶媒体であり、前記プログラムは、１つまたは複数のコンピュータにより実行された際に、前記１つまたは複数のコンピュータに以下の動作を行わせる：
文の対に対する２つの有向対応付けモデルを表わすデータを受信し、一方の文は第１言語であり、他方の文は異なる第２の言語であり、
前記２つの有向対応付けモデルから組み合わせ双方向対応付けモデルを導出し、
前記双方向対応付けモデルを評価し、前記双方向対応付けモデルの評価から前記文の対に対する対応を導出することを特徴とするコンピュータ記憶媒体。
【請求項１０】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項９記載のコンピュータ記憶媒体。
【請求項１１】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項１０記載のコンピュータ記憶媒体。
【請求項１２】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項９記載のコンピュータ記憶媒体。
【請求項１３】
前記双方向対応付けモデルを評価して２つの対応の解を生成し、第１の解は前記第１の言語から前記第２の言語への方向である第１の方向での対応付けモデルであり、第２の解は前記第２の言語から前記第１の言語への方向である第２の方向での対応付けモデルであり、
前記文の対に対する対応は、第１の対応付けモデルと第２の対応付けモデルとを組み合わせて導出することを特徴とする請求項１２記載のコンピュータ記憶媒体。
【請求項１４】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項１３記載のコンピュータ記憶媒体。
【請求項１５】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項１４記載のコンピュータ記憶媒体。
【請求項１６】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項９記載のコンピュータ記憶媒体。
【請求項１７】
動作可能な指示を記憶する１つまたは複数のコンピュータおよび１つまたは複数の記憶装置を有するシステムであり、前記指示は、前記１つまたは複数のコンピュータにより実行された際に、前記１つまたは複数のコンピュータに以下の動作を行わせる：
文の対に対する２つの有向対応付けモデルを表わすデータを受信し、一方の文は第１言語であり、他方の文は異なる第２の言語であり、
前記２つの有向対応付けモデルから組み合わせ双方向対応付けモデルを導出し、
前記双方向対応付けモデルを評価し、前記双方向対応付けモデルの評価から前記文の対に対する対応を導出することを特徴とするシステム。
【請求項１８】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項１７記載のシステム。
【請求項１９】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項１８記載のシステム。
【請求項２０】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項１７記載のシステム。
【請求項２１】
前記双方向対応付けモデルを評価して２つの対応の解を生成し、第１の解は前記第１の言語から前記第２の言語への方向である第１の方向での対応付けモデルであり、第２の解は前記第２の言語から前記第１の言語への方向である第２の方向での対応付けモデルであり、
前記文の対に対する対応は、第１の対応付けモデルと第２の対応付けモデルとを組み合わせて導出することを特徴とする請求項２０記載のシステム。
【請求項２２】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項２１記載のシステム。
【請求項２３】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項２２記載のシステム。
【請求項２４】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項１７記載のシステム。
【請求項１】
文の対に対する２つの有向対応付けモデルを表わすデータを受信し、前記対の一方の文は第１言語であり、前記対の他方の文は異なる第２の言語であり、
前記２つの有向対応付けモデルから組み合わせ双方向対応付けモデルを導出し、
前記双方向対応付けモデルを評価し、前記双方向対応付けモデルの評価から前記文の対に対する対応を導出することを特徴とする方法。
【請求項２】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項１記載の方法。
【請求項３】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項２記載の方法。
【請求項４】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項１記載の方法。
【請求項５】
前記双方向対応付けモデルを評価して２つの対応の解を生成し、第１の解は前記第１の言語から前記第２の言語への方向である第１の方向での対応付けモデルであり、第２の解は前記第２の言語から前記第１の言語への方向である第２の方向での対応付けモデルであり、
前記文の対に対する対応は、第１の対応付けモデルと第２の対応付けモデルとを組み合わせて導出することを特徴とする請求項４記載の方法。
【請求項６】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項５記載の方法。
【請求項７】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項６記載の方法。
【請求項８】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項１記載の方法。
【請求項９】
コンピュータプログラムがエンコードされた非一時的コンピュータ記憶媒体であり、前記プログラムは、１つまたは複数のコンピュータにより実行された際に、前記１つまたは複数のコンピュータに以下の動作を行わせる：
文の対に対する２つの有向対応付けモデルを表わすデータを受信し、一方の文は第１言語であり、他方の文は異なる第２の言語であり、
前記２つの有向対応付けモデルから組み合わせ双方向対応付けモデルを導出し、
前記双方向対応付けモデルを評価し、前記双方向対応付けモデルの評価から前記文の対に対する対応を導出することを特徴とするコンピュータ記憶媒体。
【請求項１０】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項９記載のコンピュータ記憶媒体。
【請求項１１】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項１０記載のコンピュータ記憶媒体。
【請求項１２】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項９記載のコンピュータ記憶媒体。
【請求項１３】
前記双方向対応付けモデルを評価して２つの対応の解を生成し、第１の解は前記第１の言語から前記第２の言語への方向である第１の方向での対応付けモデルであり、第２の解は前記第２の言語から前記第１の言語への方向である第２の方向での対応付けモデルであり、
前記文の対に対する対応は、第１の対応付けモデルと第２の対応付けモデルとを組み合わせて導出することを特徴とする請求項１２記載のコンピュータ記憶媒体。
【請求項１４】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項１３記載のコンピュータ記憶媒体。
【請求項１５】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項１４記載のコンピュータ記憶媒体。
【請求項１６】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項９記載のコンピュータ記憶媒体。
【請求項１７】
動作可能な指示を記憶する１つまたは複数のコンピュータおよび１つまたは複数の記憶装置を有するシステムであり、前記指示は、前記１つまたは複数のコンピュータにより実行された際に、前記１つまたは複数のコンピュータに以下の動作を行わせる：
文の対に対する２つの有向対応付けモデルを表わすデータを受信し、一方の文は第１言語であり、他方の文は異なる第２の言語であり、
前記２つの有向対応付けモデルから組み合わせ双方向対応付けモデルを導出し、
前記双方向対応付けモデルを評価し、前記双方向対応付けモデルの評価から前記文の対に対する対応を導出することを特徴とするシステム。
【請求項１８】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項１７記載のシステム。
【請求項１９】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項１８記載のシステム。
【請求項２０】
前記双方向対応付けモデルを評価して対応の解を生成することを特徴とする請求項１７記載のシステム。
【請求項２１】
前記双方向対応付けモデルを評価して２つの対応の解を生成し、第１の解は前記第１の言語から前記第２の言語への方向である第１の方向での対応付けモデルであり、第２の解は前記第２の言語から前記第１の言語への方向である第２の方向での対応付けモデルであり、
前記文の対に対する対応は、第１の対応付けモデルと第２の対応付けモデルとを組み合わせて導出することを特徴とする請求項２０記載のシステム。
【請求項２２】
前記双方向モデルは、前記２つの有向対応付けモデルと前記埋め込まれたモデルによる予測を単一の対称単語対応に変換する追加の構成とを埋め込むことを特徴とする請求項２１記載のシステム。
【請求項２３】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項２２記載のシステム。
【請求項２４】
前記２つの有向対応付けモデルはそれぞれ隠れマルコフ対応付けモデルであることを特徴とする請求項１７記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−１３８０８５（Ｐ２０１２−１３８０８５Ａ）
【公開日】平成２４年７月１９日（２０１２．７．１９）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−２７４５９８（Ｐ２０１１−２７４５９８）
【出願日】平成２３年１２月１５日（２０１１．１２．１５）
【出願人】（３０５０２９９２２）グーグル・インク (25)
【Ｆターム（参考）】
【公開日】平成２４年７月１９日（２０１２．７．１９）
【国際特許分類】
【出願番号】特願２０１１−２７４５９８（Ｐ２０１１−２７４５９８）
【出願日】平成２３年１２月１５日（２０１１．１２．１５）
【出願人】（３０５０２９９２２）グーグル・インク (25)
【Ｆターム（参考）】
[ Back to top ]