(57)【要約】【課題】　第１のコーパスにおける文を第２のコーパスにおける文に整列させるための方法を提供する。【解決手段】　本方法は、長さをベースとする整列モデルを適用して、第１のコーパスにおける文の文境界を第２のコーパスにおける文の文境界に整列させて整列された文のペアを形成することを含む。次に、この整列された文のペアを使用して、翻訳モデルを訓練する。訓練が終わると、翻訳モデルを使用して第１のコーパスにおける文を第２のコーパスにおける文に整列させる。本発明の態様では、剪定を使用して、長さベースの整列モデルによって考慮される文境界整列の数、および翻訳モデルによって考慮される文境界の数を減らす。本発明のさらなる態様では、長さベースのモデルは、ポアソン分布を利用する。【選択図】　図２
2004086913.tif 000002
【特許請求の範囲】
【請求項１】
　第１のコーパスにおける文を第２のコーパスにおける文と整列させる方法であって、
　長さをベースとする整列モデルを前記第１のコーパスおよび前記第２のコーパスに適用して、前記第１のコーパスにおける少なくとも１つの文に関する文境界を前記第２のコーパスにおける文に関する文境界と整列させて少なくとも１つの整列された文のペアを生成するステップと、
　前記整列された文のペアを使用して翻訳モデルを訓練するステップと、
　前記翻訳モデルを前記第１のコーパスおよび前記第２のコーパスに適用して、前記第１のコーパスにおける少なくとも１つの文に関する文境界を前記第２のコーパスにおける文に関する文境界と整列させるステップと
　を含むことを特徴とする方法。
【請求項２】
　前記長さをベースとする整列モデルは、前記第２のコーパスにおける第２の長さの文を所与として、前記第１のコーパスにおける第１の長さの文の確率を示すポアソン分布によって記述される確率を含むことを特徴とする請求項１に記載の方法。
【請求項３】
　長さをベースとするモデルを適用するステップは、
　前記第１のコーパスにおける文境界と前記第２のコーパスにおける文境界の整列をそれぞれが表わすすべての可能な文境界整列のサブセットを特定するステップと、
　前記サブセットの中の各文境界整列に関するスコアを特定するステップと
　を含むことを特徴とする請求項１に記載の方法。
【請求項４】
　前記すべての可能な文境界整列のサブセットを特定するステップは、探索帯域を画定する２つの探索境界を設定するステップを含むことを特徴とする請求項３に記載の方法。
【請求項５】
　各文境界整列に関する前記スコアに基づいて推定の最良セットの文境界整列を特定するステップと、
　前記推定の最良セットの中の前記文境界整列の１つが探索境界のしきい値以内にあることを判定するステップと、
　少なくとも１つの探索境界を変更して、前記探索帯域よりも多くの可能な文境界整列を含む拡張された探索帯域を画定するステップと、
　前記拡張された探索帯域の中の各文境界整列に関するスコアを特定するステップと
　をさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
　前記探索帯域内のいくつかの文境界整列を剪定してさらなる考慮から除外するステップをさらに含むことを特徴とする請求項４に記載の方法。
【請求項７】
　前記翻訳モデルを適用するステップは、剪定されてさらなる考慮から除外されていない前記探索帯域内の文境界整列に関してだけ前記翻訳モデルを適用してスコアを判定するステップを含むことを特徴とする請求項６に記載の方法。
【請求項８】
　前記整列された文のペアを使用して翻訳モデルを訓練するステップは、しきい値を超える整列の推定の確率を有する整列された文のペアを使用するステップを含むことを特徴とする請求項１に記載の方法。
【請求項９】
　前記翻訳モデルを適用するステップは、前記翻訳モデルと前記長さをベースとする整列モデルの組合せを適用するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項１０】
　前記整列された文のペアを使用して翻訳モデルを訓練するステップは、前記第１のコーパスにおける低頻度の語を汎用トークンで置き換えるステップを含むことを特徴とする請求項１に記載の方法。
【請求項１１】
　第１のコーパスを第２のコーパスと整列させる方法であって、
　第１のコーパスにおける文の長さと第２のコーパスにおける文の長さの間の関係をポアソン分布としてモデル化するステップと、
　前記第１のコーパスからの第１の文の長さ、および前記第２のコーパスからの第２の文の長さを前記ポアソン分布に適用して、前記第１の文が前記第２の文と整列される尤度を判定するステップとを含むことを特徴とする方法。
【請求項１２】
　文の長さの間の関係をモデル化するステップは、
　前記第１のコーパスにおける文の平均の長さを判定するステップと、
　前記第２のコーパスにおける文の平均の長さを判定するステップと、
　前記第２のコーパスにおける文の前記平均の長さと前記第１のコーパスにおける文の前記平均の長さの比を判定するステップと、
　前記比を前記ポアソン分布の平均値の定義の一環として使用するステップと
　を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
　前記第１の文の長さを適用するステップは、前記第１の文の長さに前記比を掛けて前記ポアソン分布の前記平均値の定義を完成させるステップを含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
　前記第１の文が前記第２の文と整列される前記尤度を長さをベースとする整列の一環として使用するステップをさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１５】
　前記長さをベースとする整列は、すべての可能な文境界整列のサブセットを評価するステップを含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
　前記長さをベースとする整列に基づいて翻訳モデルを訓練するステップをさらに含むことを特徴とする請求項１５に記載の方法。
【請求項１７】
　前記翻訳モデルを使用して前記第１のコーパスと前記第２のコーパスの間で文境界の整列を行うステップをさらに含むことを特徴とする請求項１６に記載の方法。
【請求項１８】
　前記長さをベースとする整列は、文境界整列を剪定してさらなる考慮から除外するステップを含むことを特徴とする請求項１７に記載の方法。
【請求項１９】
　前記翻訳モデルを使用して文境界の整列を行うステップは、前記長さをベースとする整列によって剪定されてさらなる考慮から除外されていない文境界整列を評価するステップを含むことを特徴とする請求項１８に記載の方法。
【請求項２０】
　第１のセットの境界を有する第１のシーケンスの値を第２のセットの境界を有する第２のシーケンスの値と整列させる方法であって、
　前記第１のセットの境界の中の境界と前記第２のセットの境界の中の境界との整列ポイントを表わす１組の境界整列ポイントを特定するステップと、
　探索境界を設定するステップと、
　前記探索境界に対する関係に基づいて少なくとも１つの境界整列ポイントを剪定して除外して、剪定済みの１組の境界整列ポイントを形成するステップと、
　前記剪定済みの１組の境界整列ポイントの中で１組の最も可能性の高い境界整列ポイントを特定するステップと、
　前記最も可能性の高い境界整列ポイントの少なくとも１つが探索境界のしきい値以内にあることを判定するステップと、
　前記探索境界を変更してより少ない境界整列ポイントが剪定されるようにするステップと
　を含むことを特徴とする方法。
【請求項２１】
　前記第１のシーケンスの値は、シーケンスの文字であり、前記第２のシーケンスの値は、シーケンスの文字であることを特徴とする請求項２０に記載の方法。
【請求項２２】
　前記第１のシーケンスの値は、シーケンスの語であり、前記第２のシーケンスの値は、シーケンスの語であることを特徴とする請求項２０に記載の方法。
【請求項２３】
　長さをベースとする整列の方法を使用して剪定されていない境界整列ポイントにスコアを付けるステップをさらに含むことを特徴とする請求項２２に記載の方法。
【請求項２４】
　長さをベースとする整列の方法を使用して境界整列ポイントにスコアを付けるステップは、ある境界整列ポイントと別の境界整列ポイントの間の遷移の尤度を判定するステップを含むことを特徴とする請求項２３に記載の方法。
【請求項２５】
　ある境界整列ポイントから、高い尤度を有し、前記第１のシーケンスの値における１つの文と前記第２のシーケンスの値における１つの文の整列を表わす別の境界整列ポイントへの遷移を特定するステップをさらに含むことを特徴とする請求項２４に記載の方法。
【請求項２６】
　前記特定された遷移を使用して翻訳モデルを訓練するステップをさらに含むことを特徴とする請求項２５に記載の方法。
【請求項２７】
　前記翻訳モデルを使用して境界整列ポイントにスコアを付けることによって前記第１のシーケンスの値を前記第２のシーケンスの値に整列させるステップをさらに含むことを特徴とする請求項２６に記載の方法。
【請求項２８】
　前記長さをベースとするモデルを使用して境界整列ポイントにスコアを付けるステップは、低いスコアを有する境界整列ポイントを剪定するステップをさらに含むことを特徴とする請求項２７に記載の方法。
【請求項２９】
　前記翻訳モデルを使用して境界整列ポイントにスコアを付けるステップは、前記長さをベースとするモデルを使用して剪定されていない境界整列ポイントだけにスコアを付けるステップを含むことを特徴とする請求項２８に記載の方法。
【請求項３０】
　文境界に沿って２つのテキストコーパスを整列させる方法であって、
　第１の整列モデルを使用して１組の可能な整列ポイントの確率を推定するステップと、
　前記第１の整列モデルから低い推定の確率を受ける可能な整列ポイントを剪定するステップと、
　整列ポイントに関するスコアを判定するのに前記第１の整列モデルよりも１つの整列ポイント当たりより多くの計算を必要とする第２の整列モデルを使用して、剪定されていない前記可能な整列ポイントにスコアを付けるステップと、
　前記第２の整列モデルからの前記スコアを使用して前記２つのコーパスのセグメントに関する高い確率の整列を特定するステップと
　を含むことを特徴とする方法。
【請求項３１】
　前記第１の整列モデルは、長さをベースとする整列モデルであることを特徴とする請求項３０に記載の方法。
【請求項３２】
　前記第２の整列モデルは、語の対応をベースとする整列モデルであることを特徴とする請求項３１に記載の方法。
【請求項３３】
　前記語をベースとする整列モデルが、前記第１の整列モデルを使用して行われた前記スコアを付けるステップを介して特定された整列に基づいて訓練されることを特徴とする請求項３２に記載の方法。
【請求項３４】
　前記第２の整列モデルは、長さをベースとする整列モデルと語の対応をベースとする整列モデルの組合せであることを特徴とする請求項３０に記載の方法。
【請求項３５】
　前記第１の整列モデルを使用して１組の可能な整列ポイントにスコアを付けるステップの前に、より大きい１組の可能な整列ポイントから可能な整列ポイントを除去することによって前記より大きい１組の可能な整列ポイントから前記１組の可能な整列ポイントと特定するステップをさらに含むことを特徴とする請求項３０に記載の方法。
【請求項３６】
　第１の整列モデルを使用して１組の可能な整列ポイントにスコアを付けるステップは、ポアソン分布を有する整列モデルを利用するステップを含むことを特徴とする請求項３０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
　本発明は、２言語コーパスを整列させることに関する。詳細には、本発明は、長さをベースとし、語の対応をベースとする整列に関する。
【背景技術】
【０００２】
　文が整列された並列２言語（ｂｉｌｉｎｇａｌ）コーパスは、機械学習を機械翻訳およびその他のＮＬＰタスクに適用するのに非常に有用であることが分かっている。残念ながら、カナダ国会の議事録などの、ほとんどの利用可能な並列２言語コーパスは、文が整列された形態で作成されない。したがって、コーパスの文を整列させてからでないと、機械学習のためにそのコーパスを使用することができない。
【０００３】
　文を整列させることは、時々一方の言語における単一の文が、他方の言語において２つまたはそれより多くの文に翻訳されるため、些末なことではない。さらに、コーパスが不完全であるため、一方のコーパスに見られる文が、他方のコーパスに存在しない可能性がある。
【０００４】
【非特許文献１】Brown et al., The Mathematics of Statistical Machine Translation: Parameter Estimation, Computational Linguistics, 19(2): 263-311, 1993
【発明の開示】
【発明が解決しようとする課題】
【０００５】
　これまで、２言語コーパスを整列させるために２つの一般的な技法が使用されてきた。第１の手法は、語をベースとし、または文字をベースとする。この手法では、２言語語彙集を使用して各コーパスにおける個々の語を整列させる。個々の語が整列していることを判定することが複雑であるため、この手法は、不要に遅い。さらに、この手法は、２言語語彙集が存在していることを要し、したがって、そのような語彙集が存在しない場合、コーパスを整列させるのに使用することができない。
【０００６】
　２言語コーパスを整列させるための第２の一般的な方法は、一方の言語における文の長さと、他方の言語におけるその文の翻訳文の長さの間の関係を確率モデル化することを使用する。そのような長さをベースとするシステムは、語をベースとするシステムより高速であるが、正確ではない。
【０００７】
　したがって、高速で、極めて正確であり、２言語語彙集を必要としない整列システムが必要とされている。
【課題を解決するための手段】
【０００８】
　第１のコーパスにおける文を第２のコーパスにおける文に整列させるための方法を提供する。この方法は、長さをベースとする整列モデルを適用して第１のコーパスにおける文の文境界を第２のコーパスにおける文の文境界に整列させて整列された文のペアを形成することを含む。次に、整列された文のペアを使用して翻訳モデルを訓練する。訓練した後、その翻訳モデルを使用して第１のコーパスにおける文を第２のコーパスにおける文に整列させる。
【０００９】
　本発明の一態様では、長さベースの整列は、可能な文境界の整列を剪定して、長さベースの整列によって剪定されなかった文境界整列だけにスコアを付けるのに翻訳モデルが使用されるようにするステップを含む。
【００１０】
　本発明の第２の態様では、長さベースの整列が、ポアソン分布を利用して、第２のコーパスにおける第２の長さの文を所与として、第１のコーパスにおける文が第１の長さを有する尤度を記述する。
【発明を実施するための最良の形態】
【００１１】
　以下の図１の考察は、単に、本発明を使用することができる１つの例示的な環境だけを提示しており、本発明は、その他の環境においても使用することができる。
【００１２】
　図１は、本発明を実施することができる適切な計算システム環境１００の例を示している。計算システム環境１００は、適切な計算環境の一例に過ぎず、本発明の使用または機能の範囲に関して全く限定は示唆していない。また、計算環境１００が、例示的な動作環境１００に図示した構成要素のいずれか１つ、またはいずれかの組合せに関する依存性、または要件を有すると解釈してはならない。
【００１３】
　本発明は、多数の他の汎用、または特殊目的の計算システム環境または計算システム構成で機能する。本発明で使用するのに適している可能性がある周知の計算システム、計算環境、および／または計算構成の例には、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラマブル家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、前述したシステムまたはデバイスのいずれかを含む分散計算環境等が含まれるが、以上には限定されない。
【００１４】
　本発明は、コンピュータによって実行される、プログラムモジュールなどの、コンピュータ実行可能命令の一般的な文脈で説明することができる。一般に、プログラムモジュールには、特定のタスクを行う、または特定の抽象データタイプを実装するルーチン、プログラム、オブジェクト、構成要素、データ構造が含まれる。本発明は、通信網を介してリンクされた遠隔の処理デバイスによってタスクが行われる分散計算環境においても実施することが可能である。分散計算環境では、プログラムモジュールは、メモリ記憶デバイスを含むローカルのコンピュータ記憶媒体と遠隔のコンピュータ記憶媒体の両方の中に配置されることが可能である。
【００１５】
　図１を参照すると、本発明を実施するための例示的なシステムが、コンピュータ１１０の形態で汎用計算デバイスを含む。コンピュータ１１０の構成要素には、処理ユニット１２０、システムメモリ１３０、ならびにシステムメモリから処理ユニット１２０までを含む様々なシステム構成要素を結合するシステムバス１２１が含まれることが可能であるが、以上には限定されない。システムバス１２１は、様々なバスアーキテクチャの任意のアーキテクチャを使用するメモリバスまたはメモリコントローラ、周辺バス、およびローカルバスを含むいくつかのタイプのバス構造の任意の構造であることが可能である。例として、限定としてではなく、そのようなアーキテクチャには、インダストリスタンダードアーキテクチャ（Ｉｎｄｕｓｔｒｙ　Ｓｔａｎｄａｒｄ　Ａｒｃｈｉｔｅｃｔｕｒｅ）（ＩＳＡ）バス、マイクロチャネルアーキテクチャ（Ｍｉｃｒｏ　Ｃｈａｎｎｅｌ　Ａｒｃｈｉｔｅｃｔｕｒｅ）（ＭＣＡ）バス、エンハンストＩＳＡ（Ｅｎｈａｎｃｅｄ　ＩＳＡ）（ＥＩＳＡ）バス、ビデオエレクトロニクススタンダーズアソシエーション（Ｖｉｄｅｏ　Ｅｌｅｃｔｒｏｎｉｃｓ　Ｓｔａｎｄａｒｄｓ　Ａｓｓｏｃｉａｔｉｏｎ）（ＶＥＳＡ）ローカルバス、およびメザニン（Ｍｅｚｚａｎｉｎｅ）バスとしても知られるペリフェラルコンポーネントインターコネクト（Ｐｅｒｉｐｈｅｒａｌ　Ｃｏｍｐｏｎｅｎｔ　Ｉｎｔｅｒｃｏｎｎｅｃｔ）（ＰＣＩ）バスが含まれる。
【００１６】
　コンピュータ１１０は、通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータ１１０がアクセスすることができる任意の利用可能な媒体であることが可能であり、揮発性の媒体と不揮発性の媒体、取外し可能な媒体と取外し不可能な媒体をともに含む。例として、限定としてではなく、コンピュータ可読媒体は、コンピュータ記憶媒体および通信媒体を含むことが可能である。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータなどの情報を記憶するための任意の方法または技術で実装された揮発性の媒体と不揮発性の媒体、取外し可能な媒体と取外し不可能な媒体がともに含まれる。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタルバーサタイルディスク（ＤＶＤ）またはその他の光ディスクストーレッジ、磁気カセット、磁気テープ、磁気ディスクストーレッジまたはその他の磁気記憶デバイス、あるいは所望の情報を記憶するのに使用することができ、コンピュータ１１０がアクセスすることができる任意の他の媒体が含まれるが、以上には限定されない。
【００１７】
　通信媒体は、通常、搬送波などの変調されたデータ信号、または他のトランスポート機構でコンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータを実体化し、あらゆる情報配信媒体が含まれる。「変調されたデータ信号」という用語は、信号に情報を符号化するような仕方で特性の１つまたは複数が設定または変更されている信号を意味する。例として、限定としてではなく、通信媒体には、有線ネットワークまたは直接配線接続などの有線媒体、ならびに音響媒体、ＦＲ媒体、赤外線媒体、およびその他の無線媒体などの無線媒体が含まれる。また、前述した媒体のいずれかの組合せも、コンピュータ可読媒体の範囲に含まれるべきである。
【００１８】
　システムメモリ１３０は、読取り専用メモリ（ＲＯＭ）１３１およびランダムアクセスメモリ（ＲＡＭ）１３２などの揮発性メモリおよび／または不揮発性メモリの形態でコンピュータ記憶媒体を含む。始動中など、コンピュータ１１０内部の要素間で情報を転送するのを助ける基本ルーチンを含む基本入力／出力システム１３３（ＢＩＯＳ）が、通常、ＲＯＭ１３１の中に記憶されている。ＲＡＭ１３２は、通常、処理ユニット１２０によって即時にアクセス可能であり、かつ／または現在、処理されているデータおよび／またはプログラムモジュールを含む。例として、限定としてではなく、図１は、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、およびプログラムデータ１３７を示している。
【００１９】
　また、コンピュータ１１０は、他の取外し可能な／取外し不可能な、揮発性／不揮発性のコンピュータ記憶媒体を含むことも可能である。単に例として、図１は、取外し不可能な不揮発性の磁気媒体に対して読取りおよび書込みを行うハードディスクドライブ１４１、取外し可能な不揮発性の磁気ディスク１５２に対して読取りおよび書込みを行う磁気ディスクドライブ１５１、およびＣＤ−ＲＯＭまたは他の光媒体などの取外し可能な不揮発性の光ディスク１５６に対して読取りおよび書込みを行う光ディスクドライブ１５５を示している。例示的な動作環境において使用することができる他の取外し可能な／取外し不可能な揮発性／不揮発性のコンピュータ記憶媒体には、磁気テープカセット、フラッシュメモリカード、デジタルバーサタイルディスク、デジタルビデオテープ、ソリッドステートＲＡＭ、ソリッドステートＲＯＭ等が含まれるが、以上には限定されない。ハードディスクドライブ１４１は、通常、インターフェース１４０のような取外し不可能なメモリインターフェースを介してシステムバス１２１に接続され、また磁気ディスクドライブ１５１および光ディスクドライブ１５５は、通常、インターフェース１５０のような取外し可能なメモリインターフェースでシステムバス１２１に接続される。
【００２０】
　前述し、図１に示すドライブおよび関連するコンピュータ記憶媒体により、コンピュータ可読命令、データ構造、プログラムモジュール、およびその他のデータのストーレッジがコンピュータ１１０に提供される。図１では、例えば、ハードディスクドライブ１４１が、オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７を記憶しているのが示されている。以上の構成要素は、オペレーティングシステム１３４、アプリケーションプログラム１３５、他のプログラムモジュール１３６、およびプログラムデータ１３７と同じであることも、異なることも可能であることに留意されたい。オペレーティングシステム１４４、アプリケーションプログラム１４５、他のプログラムモジュール１４６、およびプログラムデータ１４７に、ここでは、少なくともそれらが異なるコピーであることを示すために異なる符号を付けている。
【００２１】
　ユーザは、キーボード１６２、マイクロホン１６３、ならびにマウス、トラックボール、またはタッチパッドなどのポインティングデバイス１６１などの入力デバイスを介してコンピュータ１１０にコマンドおよび情報を入力することができる。他の入力デバイス（図示せず）には、ジョイスティック、ゲームパッド、サテライトディッシュ、スキャナ等が含まれる可能性がある。以上の入力デバイスおよび他の入力デバイスは、しばしば、システムバスに結合されたユーザ入力インターフェース１６０を介して処理ユニット１２０に接続されるが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（Ｕｎｉｖｅｒｓａｌ　Ｓｅｒｉａｌ　Ｂｕｓ）（ＵＳＢ）などの他のインターフェースおよびバス構造で接続してもよい。また、モニタ１９１または他のタイプの表示デバイスも、ビデオインターフェース１９０などのインターフェースを介してシステムバス１２１に接続される。モニタに加えて、コンピュータは、出力周辺インターフェース１９５を介して接続することができるスピーカ１９７やプリンタ１９６などの他の周辺出力デバイスも含むことが可能である。
【００２２】
　コンピュータ１１０は、遠隔コンピュータ１８０のような１つまたは複数の遠隔コンピュータに対する論理接続を使用するネットワーク化された環境で動作することも可能である。遠隔コンピュータ１８０は、パーソナルコンピュータ、ハンドヘルドデバイス、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、または他の一般的なネットワークノードであることが可能であり、通常、コンピュータ１１０に関連して前述した要素の多く、またはすべてを含む。図１に描いた論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７１およびワイドエリアネットワーク（ＷＡＮ）１７３を含むが、他のネットワークを含むことも可能である。そのようなネットワーキング環境は、オフィス、企業全体のコンピュータ網、イントラネット、およびインターネットで一般的である。
【００２３】
　ＬＡＮネットワーキング環境で使用される場合、コンピュータ１１０は、ネットワークインターフェースまたはネットワークアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーキング環境で使用される場合、コンピュータ１１０は、通常、インターネットなどのＷＡＮ１７３を介して通信を確立するためのモデム１７２、または他の手段を含む。内部にあることも、外部にあることも可能なモデム１７２は、ユーザ入力インターフェース１６０または他の適切な機構を介してシステムバス１２１に接続することが可能である。ネットワーク化された環境では、コンピュータ１１０に関連して描いたプログラムモジュール、またはプログラムモジュールの部分を遠隔のメモリ記憶デバイスの中に記憶することができる。例として、限定としてではなく、図１は、遠隔アプリケーションプログラム１８５を遠隔コンピュータ１８０上に常駐するのを示している。図示したネットワーク接続は、例示的であり、コンピュータ間で通信リンクを確立する他の手段を使用してもよいことが認められよう。
【００２４】
　本発明では、２つのテキストコーパスが整列されて、一方のコーパスにおける観念を伝える文が、他方のコーパスにおける同じ観念を伝える文と整列されるようになる。ほとんどの実施形態では、各コーパスは、別個の言語で書かれる。以下の考察では、２つの任意の言語、言語Ｅおよび言語Ｆを使用して本発明の実施形態を例示する。
【００２５】
　図２は、文境界に沿った、言語Ｅで書かれたコーパスと言語Ｆで書かれたコーパスの整列を示す図を提供している。図２では、各コーパスは、数のストリングで表わされ、言語Ｅが、ストリング２００で表わされ、言語Ｆが、ストリング２０２で表わされている。ストリングにおける各数は、そのコーパスの単一の文の中に見られる語の数を表わしている。したがって、ストリング２００における数「１５」は、言語Ｅにおいて１５の語を有する単一の文を表わしている。
【００２６】
　２つのコーパス間の整列ポイントは、図２では、単一の境界内に整列された文をグループ化することによって示されている。例えば、境界２０４が、言語Ｅコーパスの文２０６と、言語Ｆコーパスの文２０８および２１０の周囲に広がり、文２０６が、文２０８と２１０の結合と整列されていることを示している。その他の整列が、境界２１２、２１４、２１６、および２１８で示されている。
【００２７】
　図２に示すとおり、本発明は、次のタイプの整列を含む多くのタイプの整列をサポートする。すなわち、タイプｅｆｆ整列と呼ばれ、境界２０４として示される言語Ｅの１つの文と言語Ｆの２つの文の整列、タイプｅｅｆ整列と呼ばれ、境界２１６として示される言語Ｅの２つの文と言語Ｆの１つの文の整列、タイプｅｆ整列または１対１整列と呼ばれ、境界２１２として示される言語Ｅの１つの文と言語Ｆの１つの文の整列、タイプｅ整列と呼ばれ、境界２１４として示される言語Ｅの１つの文と言語Ｆのゼロの文との整列、およびタイプｆ整列と呼ばれ、境界２１８として示される言語Ｆの１つの文と言語Ｅのゼロの文の整列である。
【００２８】
　図３は、本発明の多くの実施形態における２つのコーパスを整列させる方法の流れ図を提供している。概要を述べると、この方法は、まず、長さベースの整列モデルを構築して、可能性の高いタイプｅｆ整列を特定し、いくつかの文境界整列状態を剪定するのに使用する。タイプｅｆ整列を使用することにより、翻訳モデルが構成され、次に、その翻訳モデルが、長さベースの整列モデルと組み合わせて使用されて、２つのコーパスに関する最良の整列が特定される。
【００２９】
　図３の方法は、ステップ３００で開始し、長さベースの整列モデルのパラメータが、コーパスから決定される。このパラメータを使用して、以下のとおり定義される特定の整列の確率が計算される。
【００３０】
【数１】
2004086913.tif 000003
【００３１】
ここで、ｐ（整列）は、コーパスにわたる特定の整列の確率であり、Ｊは、コーパスにおける整列セグメントまたは整列ポイントの数であり、ｐ（整列＿タイプ）ｘは、タイプｅｅｆ整列の確率、またはタイプｅｆ整列の確率などのセグメントｘに関する整列タイプの確率であり、またｐ（長さ＿結合）ｘは、長さの特定の結合を有するセグメントｘにおける文の確率である。
【００３２】
　本発明の一実施形態では、整列タイプに関する確率は、以下のとおり推定される。
　ｐ（タイプ＿ｅ）＝．０１
　ｐ（タイプ＿ｆ）＝．０１
　ｐ（タイプ＿ｅｆ）＝．９７２
　ｐ（タイプ＿ｅｅｆ）＝．０２６
　ｐ（タイプ＿ｅｆｆ）＝．０２６
【００３３】
　文の長さの結合に関する確率は、整列タイプに基づいて判定される。整列タイプｅおよびｆの場合、長さ結合確率を判定するのに必要な確率は、それぞれ、言語Ｅの文の長さであるｐ（ｌｅ）、および言語Ｆの文の長さであるｐ（ｌｆ）だけである。一実施形態では、ｐ（ｌｅ）およびｐ（ｌｆ）は、各コーパスにおいて見られるそれぞれの長さの文の相対頻度を判定することによって判定される。例えば、言語Ｅコーパスにおける長さ８の文の確率を判定するため、言語Ｅコーパスにおいて８という長さを有する文の数を言語Ｅコーパスにおける文の総数で割る。
【００３４】
　タイプｅｆ整列（１対１整列）に関する文の長さの結合の確率は、以下のとおり定義される。
【００３５】
【数２】
2004086913.tif 000004
【００３６】
　ここで、ｐ（ｌｅ）は、言語Ｅに関する長さｌｅの文の確率であり、この確率は、タイプｅ整列に関して前述したのと同じやり方で判定され、またｐ（ｌｆ｜ｌｅ）は、言語Ｅにおける長さｌｅの文を所与とする、言語Ｆにおける長さｌｆの文の確率である。
【００３７】
　従来の長さベースの整列システムでは、ｐ（ｌｆ｜ｌｅ）は、長さｌｅと長さｌｆの比の対数に基づくガウス分布としてモデル化されている。ガウス分布は、それぞれの長さｌｅに関して、２つの隠れたパラメータ、平均値および分散を含む。ガウス分布の平均値は、各コーパスに見られる文の平均の長さに基づいて推定することが可能であるが、分散は、整列されたコーパスを有さずに推定することができない。この結果、従来技術のシステムは、期待値最大化（ＥＭ）アルゴリズムを使用して、パラメータを繰り返し推定し、次に、その推定を使用して推定の整列を形成することにより、それらのパラメータを特定しなければならなかった。詳細には、従来の技術は、まず、ガウスモデルの平均値および分散を推定し、次に、推定されたモデルを使用して可能性の高い整列を特定した。この整列に基づき、ガウスモデルの平均値および分散が更新される。次に、更新されたモデルを使用して、新しい整列が特定される。モデルが安定するまでこれが続けられ、安定した時点で、最終の平均値および最終の分散が、そのモデルに関して選択される。
【００３８】
　そのようなＥＭ訓練は、遅く、計算上の高いコストがかかる。本発明では、このＥＭ訓練が、ポアソン分布を使用する確率ｐ（ｌｆ｜ｌｅ）をモデル化することによって回避される。このような分布は、以下のとおり定義される。
【００３９】
【数３】
2004086913.tif 000005
【００４０】
　ここで、ｒは、言語Ｆにおける文の平均の長さの、言語Ｅにおける文の平均の長さに対する比である。ポアソン分布を使用してこの確率をモデル化することにより、本発明は、隠れたパラメータを全く特定しなくてもよく、したがって、ＥＭ訓練なしに確率を判定することができる。
【００４１】
　タイプｅｆｆ整列の場合、長さの結合の確率は、以下のとおり定義される。
【００４２】
【数４】
2004086913.tif 000006
【００４３】
　ここで、ｐ（ｌｅ）は、言語Ｅにおける長さｌｅの文の確率であり、ｆ１およびｆ２は、タイプｅｆｆ整列における言語Ｆの第１の文および第２の文であり、ｐ（ｌｆ１）およびｐ（ｌｆ２）は、それぞれ、言語Ｆにおける長さｌｆ１の文、および長さｌｆ２の文の確率であり、またｐ（ｌｆ１＋ｌｆ２｜ｌｅ）は、言語Ｅにおける長さｌｅの文を所与としての、言語Ｆにおける結合された長さｌｆ１＋ｌｆ２の文の確率である。数式（ＥＱ）４の右側の分母により、ｌｆ１＋ｌｆ２という結合された文の長さを有する２つの文の長さのそれぞれの可能な結合に関する確率の和が与えられる。
【００４４】
　確率ｐ（ｌｅ）、ｐ（ｌｆ１）、およびｐ（ｌｆ２）は、タイプｅ整列およびタイプｆ整列に関して前述したのと同じやり方で判定される。確率ｐ（ｌｆ１＋ｌｆ２｜ｌｅ）は、結合された長さｌｆ１＋ｌｆ２を言語Ｆにおける単一の文の長さとして扱いながら、数式（ＥＱ）３で説明したポアソン分布を使用して判定される。
【００４５】
　タイプｅｅｆ整列の場合、長さ結合確率は、以下のとおり判定される。
【００４６】
【数５】
2004086913.tif 000007
【００４７】
　ここで、ｐ（ｌｅ１）およびｐ（ｌｅ２）は、言語Ｅにおけるそれぞれの長さｌｅ１およびｌｅ２の文の確率であり、またｐ（ｌｆ｜ｌｅ１＋ｌｅ２）は、言語Ｅにおける結合された長さｌｅ１＋ｌｅ２の文を所与としての、言語Ｆにおける長さｌｆの文の確率である。
【００４８】
　確率ｐ（ｌｅ１）およびｐ（ｌｅ２）は、タイプｅ整列に関して前述したのと同じ仕方で判定される。確率ｐ（ｌｆ｜ｌｅ１＋ｌｅ２）は、結合された長さｌｅ１＋ｌｅ２を言語Ｅにおける単一の文の長さとして扱って、数式（ＥＱ）３のポアソン分布を使用して判定される。
【００４９】
　したがって、ステップ３００で、整列タイプ確率が、各整列タイプに関して推定され、言語Ｅにおけるそれぞれの文の長さに関する確率ｐ（ｌｅ）、および言語Ｆにおけるそれぞれの文の長さに関する確率ｐ（ｌｆ）が判定される。さらに、言語Ｆにおける文の平均の長さと言語Ｅにおける文の平均の長さの比ｒが、確率ｐ（ｌｆ｜ｌｅ）を計算するのに使用するために判定される。
【００５０】
　長さベースの整列モデルに関するパラメータが訓練された後、図３のプロセスは、ステップ３０２に進み、可能な整列の順方向探索が、長さベースの整列モデルを使用して行われる。この順方向探索は、整列格子を通るパスの探索として表わすことができ、格子における各ポイントは、２つのコーパス間の可能な文境界の整列のポイントを表わす。図４は、言語Ｆのコーパスに関する文境界が、水平軸４００に沿って示され、言語Ｅのコーパスに関する文境界が垂直軸４０２に沿って示されているそのような整列格子の図である。図４に示すとおり、言語Ｆのコーパスは、ｍ個の文境界を有し、言語Ｅのコーパスは、ｎ個の文境界を有している。
【００５１】
　正常な整列であるためには、整列は、各コーパスの開始を表わすポイント０，０、および各コーパスの終了を表わすポイントｍ，ｎと交差しなければならない。理論上、この２つのポイント間の任意のパスが、２つのコーパスに関する適切な整列であることが可能である。ただし、これは、多数のパスであり、最良の整列パスを探索することが、計算上のコストの高いものとなり、大きいコーパスの場合、手に負えなくなる。
【００５２】
　これを克服するため、本発明の一態様は、最良パスが見出されることを確実にしながらも、考慮されなければならないパスの数を制限する手段を提供する。本発明の以上の実施形態において、本発明者は、最良の整列が、ポイント０，０とポイントｍ，ｎの間の対角線４０４近くを通る可能性が高いことを認知している。探索されなければならない空間を小さくするため、以上の実施形態は、探索境界４０６および４０８を画定することにより、対角線４０４のまわりに探索帯域を作成する。これにより、探索は、探索境界内に留まるパスに限定される。したがって、探索は、探索エリア４１０に限定される。これは、探索境界の外側にある境界整列ポイントを剪定することと等価である。
【００５３】
　どの境界整列ポイントを考慮すべきかを決めるため、本発明の一実施形態は、まず、言語Ｅにおける文境界の数ｎを言語Ｆにおける文境界の数ｍで割ることにより、対角線４０４の傾きを判定する。言語Ｆにおける各文境界に関して、言語Ｅにおける予期される対応する文境界が、言語Ｆ境界の位置に傾きを掛けて、言語Ｅにおける対応する文境界の予期される位置を特定することによって計算される。例えば、言語Ｆの文境界が、そのセットの文境界の中の第５の文境界であった場合、言語Ｅにおける対応する文境界の予期される位置は、傾きの５倍になる。
【００５４】
　探索帯域は、言語Ｆにおける各文境界に関して、以上に定義したとおり、Ｅにおける予期される対応する文境界の何らかの距離Ｄ範囲内にある言語Ｅにおける対応する文境界だけを考慮することによって画定される。したがって、探索帯域の幅は、Ｄの値の２倍（Ｄポイントまでの予期される境界ポイントより大きい境界ポイントと、予期される境界ポイントより小さい境界ポイントを包含する）である。
【００５５】
　一実施形態では、ステップ３０２の順方向探索は、初期ポイント０，０からの何らかのパスであるポイントに到達する確率を表わす、探索エリア４１０内の各ポイントに関する順方向状態確率スコアを特定することに関わる。順方向状態確率スコアは、初期ポイント０，０からポイントにつながるすべての可能なパスの確率の和と等しくなるように計算される。多数のそのようなパスが存在するが、すべてのパスは、多くても５つの最終ステップのどれかに帰着する。例えば、図４のポイント４１２に到達することに関して５つの可能な最終ステップが存在する。この最終ステップには、タイプｆ整列を表わすポイント４１４からのステップ、タイプｅ整列を表わすポイント４１６からのステップ、タイプｅｆ整列を表わすポイント４１８からのステップ、タイプｅｆｆ整列を表わすポイント４２０からのステップ、タイプｅｅｆ整列を表わすポイント４２２からのステップが含まれる。したがって、別々のパス確率が、０，０からポイント４１４、４１６、４１８、４２０、および４２２を経由してポイント４１２に至る各セットのパスに関して判定され、この別々の確率が合計されてポイント４１２に関する順方向状態確率スコアが形成される。
【００５６】
　各パス確率は、先行するポイントに関する順方向状態確率と２つのポイント間のパスで表わされる整列の確率の積である。数式では、以下のとおりである。
【００５７】
【数６】
2004086913.tif 000008
【００５８】
　ここで、パス＿確率ｊｉは、状態ｊを通って状態ｉに至るパスのセットに関するパス確率であり、状態＿確率ｊは、状態ｊの順方向状態確率であり、ｐ（整列＿タイプ）ｊｉは、状態ｊから状態ｉまでのパスで表わされる整列のタイプに関する整列タイプ確率であり、またｐ（長さ＿結合）ｊｉは、状態ｊから状態ｉまでの遷移で表わされる整列の中の文に関する長さ結合確率である。
【００５９】
　探索エリア４１０内の各ポイントに関する順方向状態確率スコアの判定を行いながら、順方向探索は、各状態に入る推定の最良パスの記憶も行う。この推定の最良パスは、最高のパス確率を提供するパスである。推定の最良パスは、パス上で現行のポイントに先行するポイントに対するリファレンスを使用して記憶される。
【００６０】
　当分野の技術者には認識されるとおり、この順方向探索は、ポイント０，０で開始し、探索エリアを通って終了ポイントｍ，ｎに向かって外向きに進む。探索がｍ，ｎに到達したとき、推定の最良パスに沿った状態を経由して元に戻る。そのような推定の最良パスの例を図５にパス５００として示している。探索は、最良パスに沿って元に戻る際、ステップ３０４で、その最良パスに沿ったポイントの中に探索境界４０６および４０８のしきい値以内のポイントが存在するかどうかを判定する。このしきい値の例を図５でしきい値境界５０２および５０４として示している。しきい値は、図５でゼロより大きいものとして示しているが、当分野の技術者には、ゼロのしきい値を含め、本発明の範囲内で他のしきい値も可能であることが認められよう。
【００６１】
　推定の最良パスに沿ったポイントが探索境界のしきい値以内にある場合、最良パスは、探索境界によって除外されていたために、見出されていない可能性がある。これを訂正するため、図３のステップ３０６で探索帯域が拡張され、ステップ３０２で順方向探索が再実行される。図６は、拡張された探索エリア６００を形成する拡張された探索帯域を有する整列格子を示している。拡張された探索エリアのため、格子を通る最良パスの推定は、探索帯域が拡張される前の最良パスの推定とは異なる可能性があることに留意されたい。
【００６２】
　探索境界のしきい値量の範囲内を横断しない整列格子を通る推定の最良パスが見出されると、順方向探索は、完了である。
【００６３】
　探索帯域を使用して順方向探索を行うことについて、２つのテキストコーパスを整列させることの文脈で前述したが、この探索帯域の使用は、ＤＮＡ塩基配列などの他のアイテムの整列を探索することにも同様に適用できることに留意されたい。
【００６４】
　順方向探索が完了した後、ステップ３０８で逆方向探索が行われる。この逆方向探索は、何らかの可能なパスで所与のポイントから最終ポイントｍ，ｎに到達する確率を表わす、各ポイントに関する逆方向状態確率スコアを計算する。逆方向状態確率スコアは、当分野の技術者には周知のとおり、順方向状態確率スコアが計算されるのと同様の仕方で計算される。この逆方向探索中、しきい値剪定を使用して、最終の整列が占める可能性が低い整列状態が除去される。詳細には、α（Ｓｉ，ｊ）およびβ（Ｓｉ，ｊ）がそれぞれ、言語Ｆの文境界ｉおよび言語Ｅの文境界ｊにおける状態ｉ，ｊに関する順方向確率スコアおよび逆方向確率スコアであり、またα（Ｓｍ，ｎ）が、整列格子の最終状態における順方向確率スコアである場合、状態ｉ，ｊを通る整列の確率は、以下のとおり定義される。
【００６５】
【数７】
2004086913.tif 000009
【００６６】
　数式（ＥＱ）７で使用される順方向パス確率は、０，０で開始して状態ｉ，ｊを通るすべてのパスの結合された確率を表わし、数式（ＥＱ）７で使用される逆方向パス確率は、状態ｉ，ｊで開始して状態ｍ，ｎで終了するすべてのパスの結合された確率を表わす。
【００６７】
　数式（ＥＱ）７で定義される合計状態確率スコアは、所与のポイントに関する逆方向状態確率スコアβが計算されるとすぐに、逆方向探索中に計算される。というのは、必要なαの値は、順方向探索中に既に計算されているからである。合計状態確率スコアが定められたしきい値よりも小さい場合、そのポイントは剪定されて、他の状態に関する逆方向確率スコアを計算する際に使用することから除外され、またステップ３１２における後の考慮からも除外される。一実施形態では、このしきい値は、順方向探索において探索帯域が広げられるたびに毎回、低減される初期値に設定されて、最良の整列がそれほど確かでない場合に、より多くの可能性が考慮されることが可能になる。
【００６８】
　逆方向走査の一環として、確率スコアが、各タイプｅｆ整列（１対１整列）に関して、前掲の数式（ＥＱ）６に見られる整列タイプの確率と長さ結合の確率の積に、整列の終了における境界整列ポイントに関する逆方向状態確率スコアと、整列の開始における境界整列ポイントに関する順方向状態確率スコアを掛けて、最終ポイントｍ，ｎに関する順方向状態確率スコアで割ったスコアとして生成される。このスコアは、２つのコーパスを所与として、この特定の整列の確率を表わす。高い確率スコアを有する整列がメモリの中に記憶され、以下で翻訳モデルを訓練するのに使用される。
【００６９】
　逆方向走査が完了すると、剪定済みの格子が形成されている。一部の実施形態では、最初の可能な整列状態の１０パーセントだけが、剪定の後に残る。図７は、剪定済みの格子８００の例を提示している。この例は、長さベースの整列モデルを使用して予測された可能な整列の推定を表わしている。
【００７０】
　図３のプロセスは、ステップ３１０に進み、翻訳モデルが、逆方向走査中に特定された高い確率のｅｆ整列を使用して構成される。この翻訳モデルは、以下で、逆方向走査中に特定された可能な整列パスの１つを選択するのに使用される。
【００７１】
　図８は、翻訳モデルを生成するための本発明の方法の流れ図を提示している。この方法は、非特許文献１で説明されている方法を基礎にしている。詳細には、このモデルは、非特許文献１で構成されているモデル１翻訳モデルを基礎にしている。ただし、本発明の実施形態は、非特許文献１における方法を変更して効率を向上させている。
【００７２】
　ステップ９００で、各コーパスにおける各語の頻度が判定され、頻度の低い語は、「その他」トークン、つまり汎用トークンで置き換えられる。この置換により、考慮されなければならない異なる翻訳可能性の数が減少する。一実施形態では、語は、コーパスにおいて一度だけ出現する場合、またはコーパスにおける上位５０００の最も頻度の高い語より低い頻度で出現する場合、低頻度である。
【００７３】
　ステップ９０２で、長さベースの整列の逆方向走査中に特定された高い確率のｅｆ整列に関連する文のペアを使用して、可能な語翻訳に関するカウントが展開される。詳細には、所与のペアの文に関して、元の語／翻訳された語のペアが、言語Ｅの文における語と言語Ｆの文における語のそれぞれの可能なペアリング（ｐａｉｒｉｎｇ）に関して形成される。例えば、言語Ｆの文が語Ａ、Ｂ、およびＣを含み、言語Ｅの文が語Ｔ、Ｕ、Ｖ、およびＷを含む場合、語のペアＴＡ、ＵＡ、ＶＡ、ＷＡ、ＴＢ、ＵＢ、ＶＢ、ＷＢ、ＴＣ、ＵＣ、ＶＣ、およびＷＣが形成される。さらに、Ｆの文における語がＥのどの語にも対応しないことが可能であるので、元の言語Ｅの可能な語として「空」トークン「＊」が提供される。この結果、追加のペア＊Ａ、＊Ｂ、および＊Ｃが形成される。
【００７４】
　各語のペアに関して、そのペアの確率、言い換えれば、そのペアの第１の語がそのペアの第２の語を生成した確率が判定される。この確率が文の範囲内で正規化され、カウントと呼ばれる。最初は、すべてのペアの組合せに同等の可能性がある。このため、文の範囲内の各ペアの組合せは、１／ｘの確率を有し、ここで、ｘは、空トークンの１つのインスタンスを含め、言語Ｅの文における語の数である。
【００７５】
　ステップ９０４で、語のペアに関するカウントが検査されて、カウントが、特定のｅｆ整列における可能な翻訳と見なされるには低すぎるかどうかが判定される。ステップ９０４の初回の反復においては、どのカウントも低すぎるとは考えられない。初回の反復後のステップ９０４の反復において、語のペアに関するカウントが低すぎると考えられる場合、その低いカウントは、空トークンを有する対応するペアに移される。一実施形態では、カウントは、ｅｆ整列のＥの文における語からの選択がランダムであった場合に獲得されるのと同等か、それより低い場合に低すぎると考えられる。例えば、所与の文のペアにおいて、選択の対象となる言語Ｅのｘ個の語（空トークンも含め）が存在し、ＶＡに、１／ｘに等しいか、それより低いカウントが割り当てられる場合、ＶＡに関するカウントは、＊Ａに関するカウントに加算されて、ＶＡに関するカウントは、そのｅｆ整列に関してゼロに設定される。これは、語のペアに関して構成されなければならないモデルの数を減らすために行われる。語のペアが、すべてのｅｆ整列においてゼロのカウントを有する場合、その語のペアには、翻訳確率が割り当てられない。
【００７６】
　「空」トークンに低いカウント値が割り当てられた後、プロセスは、ステップ９０６に進み、様々な語のペアに関するカウントが、ｅｆ整列のすべてにわたって合計される。これにより、各語のペアに関する合計カウントがもたらされる。次に、同じ第２の語を有する語のペアに関する合計カウントが合計されて、１組の正規化値が形成される。したがって、語Ａで終わるすべての語のペアに関する合計カウントが合計されて、Ａで終わる語のペアに関する正規化値が形成される。次に、ステップ９０８で、この正規化値がそれぞれの合計カウントの各カウントに分割されて翻訳確率が生成される。数式（ＥＱ８）では、以下のとおりである。
【００７７】
【数８】
2004086913.tif 000010
【００７８】
　ただし、ｔ（ｆ｜ｅ）は、語ｆを生成する語ｅに関する翻訳確率であり、ｃ（ｆ｜ｅ）ｓは、整列された文ｓにおいて判定された語のペア「ｅｆ」に関する正規化されたカウントであり、ｃ（ｆ｜ｅｉ）ｓは、整列された文ｓにおける語のペア「ｅｉｆ」に関する正規化されたカウントであり、またｎは、言後Ｅの中の空トークンも含めた異なる語の数である。
【００７９】
　ステップ９１０で、翻訳確率が検査されて、安定した１組の値に収束したかどうかが判定される。これは、通常、現行の訓練反復の翻訳確率を１つまたは複数の以前の反復の翻訳確率と比較することによって行われる。翻訳確率が収束していない場合、プロセスは、ステップ９０２に戻り、それぞれの翻訳された語／元の語のペアに関する正規化されたカウントが、整列された文の各ペアに関して再び判定される。
【００８０】
　第２回の反復中、前回の反復で見出された翻訳された語／元の語のペアに関する翻訳確率を使用して、正規化されたカウントが判定される。詳細には、正規化されたカウントは、次のとおり計算される。
【００８１】
【数９】
2004086913.tif 000011
【００８２】
　ここで、ｃ（ｆ｜ｅ）は、正規化されたカウントであり、ｔ（ｆ｜ｅ）は、翻訳された語／元の語のペア「ｅｆ」に関する翻訳確率であり、ｔ（ｆ｜ｅｉ）は、語のペア「ｅｉｆ」に関する翻訳確率であり、またｘは、言語Ｅの文の中の空トークンを含めた語の総数である。
【００８３】
　次に、プロセスは、翻訳確率が１組の安定した値に収束するまで、ステップ９０４、９０６、９０８、９１０、および９０２を繰り返す。翻訳確率が収束すると、翻訳モデルを訓練するプロセスが、ステップ９１２で終了する。
【００８４】
　翻訳モデルが訓練されると、図３のプロセスは、ステップ３１２に進み、第２の順方向探索が、翻訳モデルに基づく語の対応をベースとする整列モデルと、長さをベースにする整列モデルの組合せを使用して行われる。詳細には、この合成モデルを使用して、図７の剪定済みの格子８００のような、長さベースの整列の逆方向走査中に形成された剪定済みの格子における高い確率の整列が特定される。
【００８５】
　格子を通る第１の順方向走査と同様に、第２の順方向走査は、現行のポイントに遷移することが可能なすべての先行するポイントからのパス確率を合計することにより、剪定済みの格子における各ポイントに関する順方向状態確率スコアを判定する。
【００８６】
　各パス確率は、先行するポイントに関する状態確率スコアと、２つのポイント間のパスで表わされる整列の確率の積である。数式では、以下のとおりである。
【００８７】
【数１０】
2004086913.tif 000012
【００８８】
　ここで、パス＿確率ｊｉは、ポイントｊからポイントｉまでのパス確率であり、状態＿確率ｊは、ポイントｊの順方向状態確率スコアであり、ｐ（整列）ｊｉは、ポイントｊからポイントｉまでのパスで表わされる整列の確率である。
【００８９】
　合成モデルでは、整列の確率は、長さベースのモデルによって提供される確率と、翻訳モデルによって提供される確率の結合である。前述した長さ結合の確率と同様に、整列の確率は、異なるタイプの整列に関して異なる仕方で計算される。
【００９０】
　言語Ｅの文が言語Ｆの文と整列されないタイプｅ整列の場合、整列確率は、次のとおり定義される。
【００９１】
【数１１】
2004086913.tif 000013
【００９２】
　ここで、ｐ（タイプ＿ｅ）およびｐ（ｌｅ）は、第１の順方向走査に関連して前述したのと同じ定義を有し、同じ仕方で判定され、またｐ（ｅ）は、言語Ｅの文で出現するシーケンスの語ｅの確率である。確率ｐ（ｅ）は、翻訳モデルの訓練中に行われた語の頻度カウントを使用して判定される。各頻度カウントが、コーパスにおけるすべての語に関する合計頻度カウントで割られて、各語に関する確率が提供される。次に、シーケンスｅの中の各語の確率が掛け合わされて、シーケンスｅの確率が提供される。
【００９３】
　言語Ｆの文が言語Ｅの文と整列されないタイプｆ整列の場合、整列確率は、次のとおり定義される。
【００９４】
【数１２】
2004086913.tif 000014
【００９５】
ここで、ｐ（タイプ＿ｆ）およびｐ（ｌｆ）は、第１の順方向走査に関連して前述したのと同じ定義を有し、同じ仕方で判定され、またｐ（ｆ）は、ｐ（ｅ）の判定と同様の仕方であるが、言後Ｅのコーパスではなく、言語Ｆのコーパスにおける語の頻度カウントを使用して判定される、言語Ｆの文においてシーケンスの語ｆが出現する確率である。
【００９６】
　言語Ｅの１つの文が言語Ｆの１つの文と整列されるタイプｅｆ整列の場合、整列確率は、次のとおり定義される。
【００９７】
【数１３】
2004086913.tif 000015
【００９８】
　ここで、ｐ（タイプ＿ｅｆ）およびｐ（ｌｅ）は、第１の順方向走査に関連して前述したのと同じ定義を有し、同じ仕方で判定され、ｐ（ｌｆ｜ｌｅ）は、前掲の数式（ＥＱ）３で述べたポアソン分布を使用して判定され、ｐ（ｅ）は、数式（ＥＱ）１１におけるのと同じ仕方で判定され、またｐ（ｆ｜ｅ）は、言語Ｅの文で出現するシーケンスの語ｅを所与とし、またｆの長さを所与として、言語Ｆの文でシーケンスの語ｆが出現する確率である。
【００９９】
　確率ｐ（ｆ｜ｅ）は、語の２つのシーケンスｆおよびｅの中の語に関する翻訳確率を使用して判定される。１つの特定の実施形態では、この確率は、以下のとおり計算される。
【０１００】
【数１４】
2004086913.tif 000016
【０１０１】
　ここで、ｌは、シーケンスｅの中の語の数であり、ｍは、シーケンスｆの中の語の数であり、またｔ（ｆｊ｜ｅｉ）は、ステップ３１０で訓練された翻訳モデルによって提供される語ｅｉを語ｆｊに翻訳することに関する翻訳確率である。
【０１０２】
　言語Ｅの１つの文が言語Ｆの２つの文と整列されるタイプｅｆｆ整列の場合、整列確率は、次のとおり定義される。
【０１０３】
【数１５】
2004086913.tif 000017
【０１０４】
　ここで、ｐ（タイプ＿ｅｆｆ）、ｐ（ｌｆ１＋ｌｆ２｜ｌｅ）、ｐ（ｌｅ）、ｐ（ｌｆ１）、およびｐ（ｌｆ２）は、第１の順方向走査に関連して前述したのと同じ定義を有し、同じ仕方で判定され、ｐ（ｅ）は、数式（ＥＱ）１１に関して前述したのと同じ仕方で判定され、またｐ（ｆ１ｆ２｜ｅ）は、言語Ｅの文で出現するシーケンスの語ｅを所与とし、またｆ１およびｆ２の長さの和を所与として、言語Ｆの文で、シーケンスｆ１とシーケンスｆ２の組合せから形成されたシーケンスの語が出現する確率である。この確率は、ｍがシーケンスｆ１とｆ２の結合された長さに設定され、シーケンスｆ１とｆ２が言語Ｆの単一の文として扱われて、前掲の数式（ＥＱ）１４を使用して判定された確率である。
【０１０５】
　言語Ｅの２つの文が言語Ｆの１つの文と整列されるタイプｅｅｆ整列の場合、整列確率は、次のとおり定義される。
【０１０６】
【数１６】
2004086913.tif 000018
【０１０７】
　ここで、ｐ（タイプ＿ｅｅｆ）、ｐ（ｌｆ｜ｌｅ１＋ｌｅ２）、ｐ（ｌｅ１）、ｐ（ｌｅ２）は、第１の順方向走査に関連した前述したのと同じ定義を有し、同じ仕方で判定され、ｐ（ｅ１ｅ２）は、言語Ｅの文で２つのシーケンスの語ｅ１およびｅ２が出現する確率であり、この確率は、２つのシーケンスを単一の文で出現するものとして扱いながら、数式（ＥＱ）１１に関して前述した頻度カウントに基づいて判定され、またｐ（ｆ｜ｅ１ｅ２）は、言語Ｅの文で出現するシーケンスｅ１とｅ２の組合せによって形成されたシーケンスの語を所与として、またｆの長さを所与として、言語Ｆの文でシーケンスの語ｆが出現する確率である。この確率は、ｌをシーケンスｅ１およびｅ２の結合された長さに設定し、シーケンスｅ１とｅ２を言語Ｅの単一の文として扱って、前掲の数式（ＥＱ）１４を使用して判定される。
【０１０８】
　この第２の順方向走査に続き、合成モデルを使用して、剪定された格子における各整列（２つのコーパスを所与として）に逆方向状態確率スコアおよび確率スコアを割り当てる第２の逆方向走査が行われる。第１の逆方向走査と同様に、合成モデルを組み込むように変更された数式（ＥＱ）７のバージョンによって計算された合計状態確率スコアを使用して、格子がさらに剪定される。第２の逆方向走査が完了したとき、所与のしきい値を超える確率スコアを有するすべての整列が生成される。一実施形態では、このしきい値は、０．５に設定され、同一の文に関して競合する整列が生成されないことが保証される。というのは、２つの競合する整列がともに、０．５を超える確率を有することは不可能だからである。
【０１０９】
　図３で説明した方法は、従来の技術に優るいくつかの利点を提供する。従来の技術のいくつかの例においてと同様に、この方法は、語の対応をベースとするモデルを探索空間全体に適用することのコストなしに、語の対応をベースとする整列の精度を有する整列を可能にする。というのは、この方法は、初期のより低コストの方法を使用して格子を剪定してから、最終モデルを適用するからである。ただし、従来の技術とは異なり、この初期探索は、初期探索空間における状態に関する実際の確率の推定を反映するスコアを生成し、これにより、従来の技術で使用されてきたより粗いヒューリスティック方法と比べて、精度を犠牲にすることなく探索空間をさらに剪定することが可能になる。
【０１１０】
　さらに、この方法により、整列前に２言語辞書の存在を必要とすることなく、語の翻訳に基づく整列が可能になる。したがって、本発明は、翻訳モデルの形成をブートストラップ（ｂｏｏｔｓｔｒａｐ）して、次に、この翻訳モデルを使用して語の対応をベースとする整列を行うことができる。
【０１１１】
　また、本発明は、探索帯域を画定することによって探索空間を小さくすること、翻訳モデルから低頻度の翻訳を除去すること、および長さをベースとする整列の逆方向走査中に整列ポイントを剪定することを含め、整列を行うのに必要とされる時間を短縮するいくつかの態様も提供する。
【０１１２】
　本発明を特定の実施形態に関連して説明してきたが、本発明の趣旨および範囲を逸脱することなく、形態および詳細の変更を行うことが可能であることが、当分野の技術者には認められよう。
【図面の簡単な説明】
【０１１３】
【図１】本発明を実施することができる一般的な計算環境を示すブロック図である。
【図２】２つのコーパスからの文の可能な整列を示す整列図である。
【図３】本発明の実施形態におけるコーパスを整列させることを示す流れ図である。
【図４】本発明で使用される探索帯域の概念を示す整列格子を示す図である。
【図５】探索境界のしきい値の範囲内を横断する推定の最良パスを示す整列格子を示す図である。
【図６】拡張された探索帯域、および再計算された推定の最良パスを有する整列格子を示す図である。
【図７】剪定された整列格子を示す図である。
【図８】本発明の多数の実施形態における翻訳モデルを訓練する方法を示す流れ図である。
【符号の説明】
【０１１４】
　１００　計算システム環境
　１１０、１８０　コンピュータ
　１２０　処理ユニット
　１２１　システムバス
　１３０　システムメモリ
　１３１　読取り専用メモリ
　１３２　ランダムアクセスメモリ
　１３３　基本入力／出力システム
　１３４、１４４　オペレーティングシステム
　１３５、１４５、１８５　アプリケーションプログラム
　１３６、１４６　プログラムモジュール
　１３７、１４７　プログラムデータ
　１４０　取外し不可能な不揮発性のメモリのインターフェース
　１４１　ハードディスクドライブ
　１５０　取外し可能な不揮発性のメモリのインターフェース
　１５１　磁気ディスクドライブ
　１５２　磁気ディスク
　１５５　光ディスクドライブ
　１５６　光ディスク
　１６０　ユーザ入力インターフェース
　１６１　ポインティングデバイス
　１６２　キーボード
　１６３　マイクロホン
　１７０　ネットワークインターフェース
　１７１　ローカルエリアネットワーク
　１７２　モデム
　１７３　ワイドエリアネットワーク
　１９０　ビデオインターフェース
　１９１　モニタ
　１９５　出力周辺インターフェース
　１９６　プリンタ
　１９７　スピーカ
【図１】
2004086913.tif 000019
【図２】
2004086913.tif 000020
【図３】
2004086913.tif 000021
【図４】
2004086913.tif 000022
【図５】
2004086913.tif 000023
【図６】
2004086913.tif 000024
【図７】
2004086913.tif 000025
【図８】
2004086913.tif 000026