(57)【要約】機械翻訳（ＭＴ）システムは句ベースの結合確率モデルを利用できる。このモデルを使用して原始言語と目的言語の文を同時に作成できる。一実施態様で、このモデルは、語間統計的ＭＴシステムが作成した語間アラインメントから句間アラインメントを学習できる。このシステムは、原始言語から目的言語へ及び目的言語から原始言語へ翻訳する用途の両方に結合確率モデルを利用できる。【特許請求の範囲】
【請求項１】
２言語の並列テキストセグメントを複数含む並列コーパスで、句ベースの結合確率モデルをトレーニングすることを含んでなる方法。
【請求項２】
請求項１に記載の方法において、
ＥとＦとからなる文の対の、高頻度のｎ−グラムを決定し、
ｔ−分布テーブルを初期設定し、
ビタビベースの期待値最大化によるトレーニング手順を実行し、次いで
条件付確率モデルを導出する、
ことをさらに含んでいる方法。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
関連出願の相互参照
本願は、２００２年３月２７日付けで出願された米国仮特許願第６０/３６８，４５０号の優先権を主張するものである。なおこの特許願の開示内容は本願に援用するものである。
【０００２】
発明の起源
本願に記載されている研究と開発は、援助番号Ｎ６６００１−００−１−９８１４に基づいたＤＡＲＰＡ−ＩＴＯの援助及び援助番号０１２８３７９に基づいたＮＳＦ−ＳＴＴＲの援助によってなされたものである。米国政府は本願の発明に特定の権利をもっている。
【０００３】
背景
統計的機械翻訳（ＭＴ）に使用されるノイジーチャネル（雑音のある通信路）モデルの大部分は条件付確率モデルである。ノイジーチャネルのフレームワークにおいて、並列コーパス中の各原始文“ｅ”は、確率論的な過程によって目的文“ｆ”を“生成する”と推定され,そのパラメータは従来の期待値最大化（ＥＭ）法を利用して概算されている。その生成モデルは、原始語を目的語にマップする方法、及び目的語の順序を付け直して整合された目的文を生成する方法を説明している。各種の方法が、目的語の順序の付直しの説明に用いられていて、語ベース、テンプレートベース、及び文法ベースのモデル（少数の名称をあげるならば）を使う方法が含まれる。これらのモデルは、異なる生成過程を使用して、目的言語の翻訳された語の順序を付け直す方法を説明しているが、辞書のレベルでこれらモデルはすべて、原始語が個々に目的語に翻訳されると仮定している。
【０００４】
概要
機械翻訳（ＭＴ）システムは、１又は複数言語コーパスを使って確率的句間翻訳の辞書を作成することができる。例えば、翻訳辞書は、結合確率法、語間条件法などの方法を利用して作成できる。
【０００５】
ＭＴシステムは、翻訳辞書を使って１又は２以上の文（又は文の一部）を翻訳できる。例えばＭＴシステムは、グリーディー法（greedy method）、ビームスタックデコーダを使う方法又は文をデコードする他の方法を利用できる。
【０００６】
句ベース結合確率モデルを使って翻訳辞書を作成する実施態様では、原始言語の文と目的言語の文は同時に作成することができる。そのシステムは、原始言語から目的言語への翻訳及び目的言語から原始言語への翻訳の両方の用途に対して結合確率モデルを利用できる。
【０００７】
語間条件法を使う実施態様では、そのモデルは、語間統計的ＭＴシステムで作成した語間アラインメント（word-to-word-alignment）から句間アラインメント（phase-to-phase-alignment）を学習することができる。
【０００８】
詳細な説明
本願が開示しているシステム及び方法を使用してより効率的でかつ正確な機械翻訳（ＭＴ）を提供できる。いくつかの実施態様で、本発明のＭＴシステムは句間の確率翻訳の辞書を作成できる。その確率翻訳の辞書は、例えば結合確率モデル又は語間条件モデルを使用して二言語コーパスから自動的に学習できる。
【０００９】
次にこれらの翻訳辞書を使って新しい文を翻訳できる。すなわちその翻訳辞書を使って、ＭＴシステムをトレーニングするために使用されるコーパスには含まれていない文を翻訳できる。翻訳を行うシステムと方法としては、グリーディー法又はビームスタックデコーダを使う方法などの方法がある。
【００１０】
図１は翻訳モデル１０５とデコーダ１１０を備えた機械翻訳（ＭＴ）システム１００を示す。翻訳モデル１０５は、二言語コーパスから学習できる翻訳辞書を備えている。翻訳モデル１０５は、語レベル及び句レベルでも辞書の対応を確立できると仮定できる。デコーダ１１０は、翻訳辞書を使用して入力文に基づいた翻訳文を提供できる。
【００１１】
句間翻訳辞書の作成
いくつかの実施態様によれば、モデル１０５は結合確率モデルにしたがってトレーニングすることができる。すなわち、モデル１０５は、原始言語と目的言語の並列文字列を含む並列コーパス１１５を使って翻訳辞書を自動的に作成できる。モデル１０５は、原始文を目的文にマップできる方法を取り込もうとはしないが、原始文と目的文を同時に作成する。換言すれば、この翻訳モデルは、原始言語から目的言語へ及び目的言語から原始言語への機械翻訳の用途の両者に対する条件付確率モデルを与えるため容易にマージナライズ（marginalize）できる結合確率モデルである。
【００１２】
一実施態様で、モデル１０５は下記の確率論的な過程を使って文の対を作成できる。
１．概念Ｃのバッグを生成する。
２．各概念ｃｉ∈Ｃに対して、一対の句
【数１】
2005521952.tif 000002
を、
【数２】
2005521952.tif 000003
と
【数３】
2005521952.tif 000004
が各々少なくとも一つの語を含んでいる分布
【数４】
2005521952.tif 000005
にしたがって生成する。
３．句の二つの線形シーケンスを作り出すため、各言語に作成された句を順序付ける。なおそのシーケンスは二言語コーパスの文の対と一致している。
【００１３】
簡略化するため、概念のバッグ及び作成された句の順序付けを一様分布でモデル化する。また
【数５】
2005521952.tif 000006
と仮定される。これらの仮定に基づいて、概念ｃｉ∈Ｃを利用して文の対（Ｅ，Ｆ）を作成する確率は、文ＥとＦを得るため線形に順序付けることができる句のバッグを生成する全句間翻訳確率の積
【数６】
2005521952.tif 000007
で与えられることになる。
【００１４】
図２は一実施例を示す。文の対“ａｂｃ”――“ｘｙ”は二つの概念（“ａｂ”：“ｙ”）と（“ｃ”：”ｘ”）、又は一つの概念（“ａｂｃ”：“ｘｙ”）を使用して作成することができる。というのは、両者の場合、各言語の句は原文の対を生成するシーケンスに配列できるからである。しかしながら、同じ文の対は概念（“ａｂ”：“ｙ”）と（“ｃ”：”ｘ”）を使用して作成できない。なぜならばシーケンス“ｘｙ”は二つの句“ｙ”と“ｙ”から再現できないからである。同様に、前記文の対は概念（“ａｃ”：“ｘ”）と（“ｂ”：“ｙ”）を使用して作成できる。というのはシーケンス“ａｂｃ”は句“ａｃ”と“ｂ”を連結することによって作成できないからである。
【００１５】
ＥとＦが、全概念ｃｉ∈Ｃの特徴である句
【数７】
2005521952.tif 000008
と
【数８】
2005521952.tif 000009
の順序を変えることによって得られる場合は、概念Ｃのセットを文の対（Ｅ，Ｆ）に線形化できる。我々はこの特性を述語Ｌ（Ｅ，Ｆ，Ｃ）を使って示す。すると、このモデルに基づけば、与えられた文の対（Ｅ，Ｆ）の確率は、（Ｅ，Ｆ）に線形化できる概念ｃｉ∈Ｃのバッグを作成する可能性のあるすべての方法を合計することによって得ることができる。
【数９】
2005521952.tif 000010
【００１６】
上記モデル（“モデル１”）はかなり良好なアラインメントを生成することが分かった。しかしながら、このモデルは、与えられた概念に関連する句の順序付けに対する制約が全く無いので、初めて見る文を翻訳するのに不適である。このことを説明するため、改良モデル（“モデル２”）を開発して歪を説明した。モデル２の生成ストーリーは以下のとおりである。
１．概念Ｃのバッグを作成する。
２．ＥとＦを空シーケンスεに初期設定する。
３．概念ｃｉ∈Ｃを無作為に取り上げ、一対の句
【数１０】
2005521952.tif 000011
を、
【数１１】
2005521952.tif 000012
と
【数１２】
2005521952.tif 000013
が少なくとも一つの語を含んでいる分布
【数１３】
2005521952.tif 000014
にしたがって作成する。その後、Ｃからｃｉを除く。
４．Ｆの末端に句
【数１４】
2005521952.tif 000015
を付加する。ｋをＦ中の
【数１５】
2005521952.tif 000016
の出発位置におく。
５．他の句が１及び
【数１６】
2005521952.tif 000017
の位置を占めないならば、句
【数１７】
2005521952.tif 000018
をＥの１の位置に挿入する。ここで、
【数１８】
2005521952.tif 000019
は句
【数１９】
2005521952.tif 000020
の長さを示す。したがって、システムは、確率：
【数２０】
2005521952.tif 000021
（式中、ｄ（ｉ，ｊ）は位置ベースの歪分布である）で二つの句
【数２１】
2005521952.tif 000022
と
【数２２】
2005521952.tif 000023
の間にアラインメントを作成する。
６．Ｃが空になるまでステップ３−５を繰り返す。
【００１７】
このモデルでは、文の対（Ｅ，Ｆ）を生成する確率は下記式：
【数２３】
2005521952.tif 000024
（ここで、
【数２４】
2005521952.tif 000025
は文Ｆ中の句
【数２５】
2005521952.tif 000026
の語ｋの位置を示し、そして
【数２６】
2005521952.tif 000027
は句ｅｉの群の中心の文Ｅ内の位置を示す）で与えられる。
【００１８】
上記モデルをトレーニングする方法をコンピュータで行うのは大変である。文の対（Ｅ，Ｆ）を作成できるアラインメントの数は指数関数的な数なので、期待値最大化（ＥＭ）トレーニングアルゴリズムは完全には適用できない。図３は、上記問題を考慮している句ベースの結合確率モデルの訓練アルゴリズム３００を説明するフローチャートである。
【００１９】
システムはＥとＦ内の高頻度ｎグラム（n-gram）を決定する（ブロック３０５）。句
【数２７】
2005521952.tif 000028
及び句
【数２８】
2005521952.tif 000029
が概念ｃｉから作成できると最初から仮定すると、
【数２９】
2005521952.tif 000030
分布をモデル化するテーブルをメモリに記憶させるのにスーパーコンピューターが必要である。このシステムは、無制限のメモリのコンピュータにアクセスしないから、このシステムは、コーパス及びユニグラム（unigram）内に生ずることが多い句に対してのみｔ分布エントリーを最初に学習する。そして、平滑化によって、このシステムは、稀に存在する句に対してもｔ分布エントリーを学習する。前記アルゴリズムの次のステップで考慮されるためには、句はコーパス中に少なくとも５回存在しなくてはならない。
【００２０】
次のステップは、ｔ分布テーブルを初期設定するステップである（ブロック３１０）。ＥＭトレーニング手順が始まる前に、どの語／句の対が同じ意味を共有しているのかという考えは誰も持っていない。換言すれば、文の対（Ｅ，Ｆ）を作成できるすべてのアラインメントは同じ確率を有していると仮定できる。これらの条件下で、
【数３０】
2005521952.tif 000031
が同じ概念ｃｉで生成されるという事実に、文の対（Ｅ，Ｆ）が寄与している証拠は、文Ｅ中の句
【数３１】
2005521952.tif 000032
及び文Ｆ中の句
【数３２】
2005521952.tif 000033
に連結される概念ｃｉを有する（Ｅ，Ｆ）間に組み立てることができるアラインメントの数を、これら二つの文の間に組み立てることができるアラインメントの全数で割り算することで与えられる。これらの数はいずれも容易に近似させることができる。
【００２１】
ｌ語の文Ｅが与えられたとすると、そのｌ語をｋ個の空でないセット／概念に分割できるのはＳ（ｌ，ｋ）通りある。ここで、Ｓ（ｌ，ｋ）は第二種のスターリング数である。
【数３３】
2005521952.tif 000034
【００２２】
また、文Ｆのｍ個の語をｋ個の空でないセットに分割できるのはＳ（ｍ，ｋ）通りある。Ｅ中のどの語もＦ中のどれかの語にマップできるとした場合、長さがそれぞれｌとｍの二つの文（Ｅ，Ｆ）の間に組み立てることができる
【数３４】
2005521952.tif 000035
のアラインメントがあることになる。概念ｃｉが、長さがそれぞれａとｂの二つの句
【数３５】
2005521952.tif 000036
を作成すると、連結するために残される語はｌ−ａ個及びｍ−ｂ個の語だけである。したがって、他の情報が無いとき、句
【数３６】
2005521952.tif 000037
と
【数３７】
2005521952.tif 000038
が同じ概念ｃｉで作成される確率は下記式で与えられる。
【数３８】
2005521952.tif 000039
【００２３】
上記式により返される分数値は、前記システムが関連するｔ分布の近似値だけであることに注目すべきである。なぜなら、第二種のスターリング数は、連続している与えられた概念と関連する語に何も強制しないからである。しかしながら、上記式は分子と分母を等しく過大評価するので、近似は実際はうまくいく。
【００２４】
アルゴリズムの第二ステップにおいて、このシステムは、コーパス内の各文の対（Ｅ，Ｆ）の句について定義されるデカルト積のすべてのユニグラムの対及び高頻度のｎグラムの対に対する分数値を集めるために上記式を適用する。このシステムは、これらすべてのｔカウントを合計し正規化して初期の結合分布ｔを得る。このステップは、コーパス内のすべての可能性のあるアラインメントにわたる１ステップに対するＥＭアルゴリズムを実行することになる。
【００２５】
アルゴリズムの第三ステップで、前記システムはビタビアラインメントに対しＥＭトレーニングを実施する（ブロック３１５）。一様でないｔ分布の場合、句間アラインメントは異なる重みを有していて、多項式時間で可能性があるすべてのアラインメントの分数値を集めるために適用できる秘訣は外にはない。図３に示すアルゴリズムのブロック３１５から始まって、コーパス中の各文の対に対し、このシステムは、高いｔ確率を有する概念を生成するため、句を連結することによって初期のアラインメントをグリーディに作成する。次に、このシステムは、概念を分断及び合体し、語を概念間で交換し、そして語に概念間を移動させることによって、最高の確率を有するビタビアラインメントの方にヒルクライムする。このシステムは、ヒルクライミングプロセス中にシステムが作成したすべてのアラインメントに関連する確率を計算し、次いでこれらアラインメントのすべての概念にわたってｔカウントを収集する。
【００２６】
このシステムは、このビタビベースのＥＭトレーニング手順を数回繰り返して適用する。その最初の繰返しがモデル１を使う前記アラインメントの確率を推定する。残りの繰返しがモデル２を使う前記アラインメントの確率を推定する。
【００２７】
トレーニング中、このシステムは、平滑化法を適用して、非ゼロ値を、コーパス中に度々存在することはない句の対に連結できる。
【００２８】
トレーニング手順が終わったとき、システムは、結合確率分布tとdに限界を設ける（ブロック３２０）。こうして、システムがデコードするときに使用する条件付確率分布
【数３９】
2005521952.tif 000040
及びｄ（ｐｏｓＦ｜ｐｏｓＥ）が作成される。
【００２９】
このシステムが図２に示すコーパスに対し図３に示す訓練手順を実行するとき、モデル１を４回繰り返した後、このシステムはアラインメント２０５及び結合と条件付の確率分布２１０を得る。人間は生来、可能な最小の句の間にアラインメントを組み立てようとする傾向があるので、一見、第一の文の対に対するビタビアラインメントは間違っているように見える。しかしながら、我々のモデルによってなされる選択は全く適切な選択であることに注目すべきである。とりわけ、追加の情報が無いとき、そのモデルは、“ａ”と“ｙ”が同じことを意味するか、又は句“ａｂｃ”と“ｘｙ”が同じことを意味すると仮定できる。このモデルは第二の仮説により大きい重みを与える選択を行うが、第一の仮説にいくらかの確率の量を保存する。
【００３０】
結合分布は第二仮説が有利であるとしているが条件付分布はそうではないことにも留意すべきである。条件付分布２１０は、“ａ”を“ｙ”と翻訳することのみならず“ａｂｃ”を“ｘｙ”と翻訳することの両者が妥当であると我々に告げているという我々の直感と一致している。その条件付分布が我々の直感を反映している。
【００３１】
別の実施態様で、図１に示すシステム１００のようなシステムは、語間のアラインメントから句間の翻訳を学習できる。すなわち、モデル１０５のようなモデルは、語間のモデルによって学習された語間の翻訳辞書を作成することによって句翻訳辞書をつくることができる。その句翻訳モデルはノイジーチャネルのモデルに基づいている。このシステムは、ベイズの規則を使って、外国語の文章fを英語の文章eに翻訳する翻訳確率を下記式：
ａｒｇｍａｘｅｐ（ｅ｜ｆ）＝ａｒｇｍａｘｅｐ（ｆ｜ｅ）ｐ（ｅ）
に公式化しなおす。
【００３２】
この式は言語モデルｐ（ｅ）及び別の翻訳モデルｐ（ｅ｜ｆ）を考慮している。
【００３３】
デコード（すなわち翻訳）している間、外国語の入力文ｆはＩ個の句のシーケンス
【数４０】
2005521952.tif 000041
に区分される。システムはすべての可能な区分化にわたって一様の確率分布を仮定する。
【００３４】
【数４１】
2005521952.tif 000042
内の各外国語の句
【数４２】
2005521952.tif 000043
が英語の句
【数４３】
2005521952.tif 000044
に翻訳される。その英語の句は再度順序付けすることができる。句の翻訳は確率分布
【数４４】
2005521952.tif 000045
によってモデル化することができる。ベイズの規則によって、翻訳の方向はモデル化の観点から反転される。
【００３５】
英語の出力句の再順序付けは相対的歪の確率分布ｄ（ａｉ−ｂｉ−１）によってモデル化される。ここでａｉはｉ番目の英語の句に翻訳された外国語の句の出発位置を示し、そしてｂｉ−１はｉ−１番目の英語の句に翻訳された外国語の句の最後の位置を示す。
【００３６】
歪の確率分布ｄ（・）は、先に述べた実施態様に関連して述べたような、結合確率モデルを使ってトレーニングできる。あるいは、システムは、適当な値のパラメータαを有するより単純な歪モデル
【数４５】
2005521952.tif 000046
を使うこともできる。
【００３７】
出力の長さを校正するため、このシステムは、トリグラム（trigram）の言語モデルｐＬＭに加えて、作成した英語の各語に対して因子ωを導入する。これは性能を最適化する簡単な手段である。通常、この因子は１より大でありより長い出力をバイアスさせる。
【００３８】
要約すると、このモデルによって外国語入力文ｆに与えられる最良の英語出力文ｅｂｅｓｔは下記式で表される。
【数４６】
2005521952.tif 000047
ここでｐ（ｆ｜ｅ）は下記式に分解される。
【数４７】
2005521952.tif 000048
【００３９】
Ｇｉｚａ＋＋ツールキットが開発されたのは、並列コーパス由来の語ベースの翻訳モデルをトレーニングするためである。その副産物として、このキットは、このデータの語のアラインメントを作成する。このシステムは、このアラインメントをいくつかの発見的方法で改善することができる。このシステムは語のアラインメントに一致しているすべての整列された句の対を収集する。法律上の句の対の中の語は互いに整列しているだけで、外部の語に対して整列していない。句の対が集められると、システムは相対頻度で下記式で表される句翻訳の確率分布を推定する。
【数４８】
2005521952.tif 000049
【００４０】
いくつかの実施態様では、平滑化を行うことができる。
【００４１】
このシステムが語のアラインメントと一致するすべての句の対を集めると、これは多くの非直感的な句を含んでいる。例えば、“ｈｏｕｓｅ  ｔｈｅ”のような句の翻訳文は学習できる。このシステムは、直感的に、このような句が役に立たないと考える傾向がある。可能性のある句を構文上の動機がある句に限定すると、かような非直感的な対をフィルターして除くことができる。
【００４２】
構文上の句だけを含有する句翻訳モデルの性能を評価するための他の動機が、構文上の翻訳モデルを組み立てようとする最近の努力の結果から生まれている。これらのモデルでは、語の再順序付けは適格な構文解析ツリーの構成体の再順序付けに限定される。句の翻訳文を含むこのようなモデルを増大すると、一般に構文のサブツリー全体にまたがる句だけ翻訳が可能になる。これが役に立つ制限なのか又は有害な制限なのかを知ることが大切である。
【００４３】
このシステムは、構文上の句を、構文解析ツリー内の単一サブツリーでカバーされる語のシーケンスと定義する。我々は構文の句の対を以下のようにして収集する。このシステムは並列コーパスに先に述べたようにして語の整列を行う。次にこのシステムは、コーパスの両側を構文解析系で構文解析する。語のアラインメントと一致している句の対のすべてに対して、システムはさらに両方の句が構文解析ツリーのサブツリーなのかどうかをチェックする。これらの句だけがこのモデルに含まれている。したがって、構文上動機がある句の対であって学習される句の対は、構文の知識無しで学習される句の対のサブセットである。句の翻訳の確率分布は相対頻度によって推定できる。
【００４４】
図８は、異なる最大句長で行った実験の結果を示す。語のアラインメントと一致しているすべての句（ＡＰ）を使用した。図８に示すように、長さを１句当たり最大３語までに制限すると最高の性能が達成される。これ以上長い句を学習しても改善されない。しかしながら、その限度を２まで下げることは有害である。句をこれ以上長くすると、句の翻訳テーブルの大きさが大きくなる。この増大は最大長の限度とほとんど比例している。しかもこれらモデルの大きさのどれも、これまでメモリの問題を起こさなかった。
【００４５】
このシステムは、その語が互いにうまく翻訳されているかチェックすることによって句の翻訳対の品質を評価することができる。この場合、辞書の翻訳確率分布ｗ（ｆ｜ｅ）を使用できる。この分布は、下記のように句のモデルと同じ語のアラインメントから相対頻度によって推定できる。
【数４９】
2005521952.tif 000050
【００４６】
特定の英語の空トークン（NULL token）を、英語の各文章に付加し次いで位置合わせされていない外国語の語各々に位置合わせすることができる。
【００４７】
句の対
【数５０】
2005521952.tif 000051
と、外国語の語の位置Ｉ＝１，…，ｎと英語の語の位置Ｊ＝０，１，…，ｍの間の語のアラインメントａとが与えられると、システムは下記式：
【数５１】
2005521952.tif 000052
で字句の重みｐｗを計算する。
【００４８】
図９は一実施例を示す。
【００４９】
一つの句の対
【数５２】
2005521952.tif 000053
に対し複数のアラインメントがある場合、システムは下記式で表わされる最高の字句の重みを有するアラインメントを使用できる。
【数５３】
2005521952.tif 000054
【００５０】
このシステムは、翻訳中、この字句の重みｐｗを追加の因子として使用できる。これは、モデルｐ（ｆ｜ｅ）が下記式まで拡張されることを意味する。
【数５４】
2005521952.tif 000055
【００５１】
パラメータλは字句の重みｐｗの強さを定義する。このパラメータの適当な値は約０.２５である。
【００５２】
図１０は、機械翻訳の性能に対する字句重み付けの影響を示す。我々の実験で、システムはＢＬＥＵの得点スケールで０.０１まで改善した。
【００５３】
字句の重み付けを有する句の翻訳は、各語に対し１語のクラスを有するアラインメントテンプレートモデルの特殊ケースである。システムが実施する単純化には、字句の重みを予め句の翻訳テーブルに取り入れてデコーディングの速度を上げることができるという利点がある。前記アラインメントテンプレートモデルで使うビームサーチデコーダとは対照的に、図５と６で説明したデコーディング法は、デコードする前に入力文章の可能性のある句の区分のうちの一つを選ぶのではなくて入力文章の可能性のある句の区分のすべてをサーチできる。
【００５４】
この実験で、本発明のシステムはＧｉｚａ＋＋が作成した語のアラインメントから句の対を学習した。このツールキットが実行するＩＢＭ  Ｍｏｄｅｌは、せいぜい一つの英語の語を一つの外国語の語に位置合わせできるに過ぎない。本発明のシステムはこの問題を発見的方法で改善する。
【００５５】
第一に本発明のシステムは、並列コーパスを、双方向にすなわち外国語から英語に及び英語から外国語に位置合わせする。これはシステムが調和させようとする二つの語のアラインメントを与える。システムがこれら二つのアラインメントと交差すると、システムは信頼性の高いアラインメントポイントを有する高精度のアラインメントを得る。システムが前記二つのアラインメントを併合すると、システムは追加のアラインメントポイントを有する再現性の高いアラインメントを得る。
【００５６】
交差と併合の間のスペースは、交差で出発し次いで追加のアラインメントポイントを付加する拡張的な発見的方法である。どのポイントを付加するかの決定は、いくつかの基準によって決まる。例えば、潜在的なアラインメントポイントがどのアラインメントに存在しているか（外国語−英語又は英語−外国語），潜在的なポイントがすでに確定されたポイントに隣接しているのかどうか，“隣接している”の意味が、直接接触していることか（ブロック−ディスタンス）又は対角線方向に接触していることか，潜在的なポイントが接続している英語又は外国語の語がまだ位置合わせされていないかどうか、及び両者が位置合わせされていないとしたときは潜在的なポイントの字句確率。
【００５７】
システムは２つの語のアラインメントが交差することで始まる。システムは２つの語のアラインメントの併合体内に存在する新しいアラインメントポイントを付加するだけである。またシステムは、新しいアラインメントポイントがまだ位置合わせされていない少なくとも一つの語に接続することを常に要求する。
【００５８】
第一に、このシステムは、直接隣接するアラインメントポイントにのみ拡張する。このシステムは、アラインメントマトリックスの右上隅から始まる潜在的なポイントをチェックし、最初の英語の語に対するアラインメントポイントをチェックし、次いで第二の英語の語に対するアラインメントポイントのチェックなどを続ける。これは、それ以上のアラインメントポイントを付加できなくなるまで繰返し行われる。最終ステップで、システムは、外の点では同じ要件で、非隣接のアラインメントポイントを付加する。
【００５９】
図１１は、この発見的方法（base）の性能を二つの一方向のアラインメント（ｅ２ｆ，ｆ２）及びそれらの併合（union）と比較して示している。図１１はベースの発見的方法の二つの改良例も含んでいる。すなわち第一の改良例（diag）では、システムは、反復拡張段階で対角線方向に隣接させている。これの変形（diag-and）で、システムは最終段階で、両方の語が位置合わせされていないことを要求する。
【００６０】
これら異なる方法のランキングは、異なるトレーニングコーパスの大きさに対して変化する。例えば、アラインメントｆ２ｅは、最悪から２番目である１０,０００個の文章対のコーパスから出発するが、最終的には３２０，０００個の文章対の最良の方法と競合する。前記ベースの発見的方法は最初最良であるが、次いで徐々に低下する。最良の方法と最悪の方法の相違は、トレーニングコーパスのほとんどすべての大きさに対して非常に大きく約０.２ＢＬＥＵ（ＩＢＭの得点システム）であるが、必ずしも有意ではない。
【００６１】
デコーディング
いくつかの実施態様の句ベースのデコーダはビームサーチアルゴリズムを採用できる。その英語の入力は部分翻訳（又は仮説）の形態で左から右へ作成される。
【００６２】
このシステムは、外国語の入力語が全く翻訳されておらず英語の出力語が全く作成されていない初期状態で可能性がある翻訳のサーチを開始できる。いくつかのまだ翻訳されていない外国語の入力語をカバーする句の翻訳で英語の出力を拡大することによって、新状態をつくることができる。この新状態の現在のコストは、原状態のコストに、付加された句の翻訳における、翻訳と歪と言語モデルとのコストを掛け算したものである。
【００６３】
各サーチ空間（仮説）は、（ａ）以前の最良状態に対するバックリンク；（ｂ）これまでにカバーされた外国語の語；（ｃ）作成された最後の二つの英語の語（将来の言語モデルのコストを計算するのに必要）；（ｄ）カバーされた最後の外国語の句の末端（将来の歪のコストを計算するのに必要）；（ｅ）最後の付加された英語の句（仮説の経路から翻訳文を読み取るのに必要）；（ｆ）これまでのコスト；及び（ｇ）将来のコストの見積によって表わされる。
【００６４】
上記サーチの最終の状態は、すべての外国語の語をカバーする仮説である。これら仮説の中でコストが最低の仮説が最良の翻訳として選択される。
【００６５】
二つの仮説は、それらが（ａ）これまでにカバーされた外国語の語、（ｂ）作成された少なくとも二つの英語の語および（ｃ）カバーされた最後の外国語の句の末端で一致している場合、併合することができる。
【００６６】
これらの特性で一致している二つの仮説に到達する二つの経路があるとき、システムは、より安価な仮説例えばこれまでの仮説のなかでコストの低いものを保持する。残った仮説は最良の翻訳への経路の一部になれないので、システムはその仮説を安全に捨てることができる。下位の仮説が第二の最良翻訳の一部になれることがあることに留意すべきである。
【００６７】
図５は、一実施態様の句ベースのデコーディング操作５００を説明するフローチャートである。この操作を説明するアルゴリズムは図６に示してある。システムは初期の空の仮説で出発する。次に新しい仮説が、句を翻訳することによって既存の仮説から拡張される。未翻訳の外国語の語のシーケンスとそれらの可能性のある英語の句の翻訳を選択する（ブロック５０５）。その英語の句を既存の英語の出力シーケンスに連結する（ブロック５１０）。次に前記外国語の語に翻訳されたという印をつけ次いでその仮説の確率コストを更新する（ブロック５１５）。未翻訳の外国語の語を含まない最も安価な（最高の確率）最終仮説がサーチの出力である。（ブロック５２０）。
【００６８】
それらの仮説をスタックに記憶させる。そのスタックＳｍは、ｍ個の外国語の語が翻訳されたすべての仮説を含んでいる。システムはサーチの仮説を再結合することができる。こうすると各スタックに記憶される仮説の数は幾分減少するが、スタックの大きさは入力文の長さに対して指数関数的になる。こうなると網羅的なサーチが実行できなくなる。
【００６９】
したがって、このシステムは、仮説のこれまでにかかったコストと将来のコストの推定値に基づいて弱い仮説を除く。システムは、各スタックに、最良のｎ個の仮説のビームだけを保持する。将来のコストの推定値は、正確でないのでサーチエラーをもたらす。我々の将来のコストの推定値は、句の翻訳の推定コストを考慮しているが予想される歪のコストを考慮していない。
【００７０】
文中に存在する可能性のある句の翻訳の各々（“翻訳オプション”と呼称されている）について、このシステムは、その句の翻訳の確率に、作成された英語の句に対する言語モデルの確率を掛け算する。言語モデルの確率として、システムは、第一の語に対しユニグラムの確率、第二の語にバイグラム（bigram）の確率及び続くすべての語に対しトリグラムの確率を使用できる。
【００７１】
前記翻訳オプションのコストが与えられると、システムは、連続する外国語の語のシーケンスの将来のコストの推定値を動的計画法で計算できる。システムは歪のコストを無視するので、上記のことは単に可能であるに過ぎないことに留意すべきである。長さｎの外国語の入力文のかようなシーケンスはｎ（ｎ＋１）／２個存在しているに過ぎないので、システムはこれらのコストの推定値を予め計算してテーブルに記憶させることができる。
【００７２】
翻訳中、カバーされていない外国語の語の将来のコストは上記テーブルを調べることによって迅速に計算できる。仮説が未翻訳の外国語の語を中断した場合、システムは各シーケンスのコストを調べてそれらのコストの積を求める。
【００７３】
ビームサーチ中に作成された仮説の空間は、各々翻訳を示す経路の格子を形成し、その翻訳の翻訳得点は容易に計算できる。このような格子からｎ個の最良経路を取り出すことは十分に研究された問題である。
【００７４】
複数の新しい仮説を導出できる仮説に複数の翻訳オプションがあるとき、経路は分枝する。仮説が併合されると、経路は結合する。仮説がいくつもの同じ特性を有しコストがより小さい仮説と一致すると、このシステムは上記のようにその仮説を捨てることができる。併合経路の情報を保持するため、このシステムは、以前の仮説の識別子、よりコストの小さい仮説の識別子及び以前の仮説からよりコストの高い仮説までのコストを含むかような併合の記録を保持する。
【００７５】
図７は図に示すアークを作成する一実施例を示す。この場合、仮説２と４は、上記のように発見的サーチについては等しい。したがって仮説４は削除される。しかし、仮説３から２に至る経路に関する情報を保存するため、システムはこのアークの記録７０５を記憶する。このアークは、仮説３から４に付加されたコストも含んでいる。仮説１から仮説２に付加されたコストは、仮説のデータ構造体から再計算できるので記憶する必要がないことに注目すべきである。
【００７６】
ビームの大きさ、例えば各スタック内の仮説の最大数は、特定の数に固定できる。翻訳オプションの数は文の長さと直線の関係である。したがってビームサーチの時間複雑性は、文の長さと二次曲線の関係でありそしてビームの大きさと直線の関係である。
【００７７】
ビームの大きさはサーチ空間を限定するのでサーチの質を限定するから、システムは、速度（小さいビームの大きさ）と性能（大きいビームの大きさ）の間の適切なトレードオフを見つけなければならない。実験で、わずか１００というビームの大きさで十分であることが分かった。ビームの大きさがこれより大きいと、ごく少数の文が異なって翻訳された。そのデコーダは、２ＧＨｚのＬｉｎｕｘ（登録商標）システムに約１０分間で長さが５〜１５語の文１７５５を翻訳した。このシステムは、高品質を保証しながら迅速にデコードした。
【００７８】
いくつかの実施態様で、図１に示すデコーダ１００などのデコーダはグリーディな手順を実行する。外国語の文Ｆが与えられると、そのデコーダは第一に、Ｅ*すなわち確率ｐ（Ｅ，Ｆ）の句を選ぶことによってその文の用語集を作成する。デコーダは次に式：ｐ（Ｅ）ｐ（Ｆ｜Ｅ）を最大にするためＥ及びＥとＦの間のアラインメントを修正することによって繰返しヒルクライムする。デコーダは、与えられた時間までに組み立てられたアラインメント／翻訳を部分的に修正する一組の操作で既存のアラインメント／翻訳を修正することによってヒルクライムする。これらの操作は、アラインメントの英語の側を異なる確率の句で置換し、既存の概念を併合しそして中断し次に語を概念間で交換する。確率ｐ（Ｅ）は単純なトリグラム言語モデルを使って計算できる。その言語モデルは語のレベルで（句のレベルではない）推定される。図３は、文
【表１】
2005521952.tif 000056
の翻訳文を見つけるためデコーダがとるステップを示す。図４に示す各中間翻訳文４０５に先行してその文の確率４１０が記載され続いて文を変えてより高い確率の翻訳文を生成する操作が記載されている。
【００７９】
いくつかの実施態様を説明してきたが、本発明の精神と範囲を逸脱することなく各種の変形を実施できると理解している。例えば、フローチャートのブロックは飛び越えたり又は順序を変えて実施ししかも望ましい結果をもたらすことができる。異なる翻訳法を使用できる。したがって他の実施態様は本願の請求項の範囲内にある。
【図面の簡単な説明】
【００８０】
【図１】句ベースの結合確率翻訳モデルを含む機械翻訳（ＭＴ）システムのブロック図である。
【図２】句ベースの結合確率翻訳モデルで作成したアラインメントと確率分布を示す。
【図３】句ベースの結合確率翻訳モデルのトレーニングアルゴリズムを説明するフローチャートである。
【図４】句ベースのグリーディデコーディングの一例を示す。
【図５】一実施態様による句ベースのデコーディングアルゴリズムを説明するフローチャートである。
【図６】句ベースのデコーディングアルゴリズムを説明する擬似コードを示す。
【図７】仮説間のアークの作成を示す線図である。
【図８】性能に対する句の長さの影響を示すグラフである。
【図９】字句の重みの概算の一例を示す。
【図１０】字句の重み付けの、性能に対する影響を示すグラフである。
【図１１】異なる発見的方法の性能を比較するグラフである。
【図１】
2005521952.tif 000057
【図２】
2005521952.tif 000058
【図３】
2005521952.tif 000059
【図４】
2005521952.tif 000060
【図５】
2005521952.tif 000061
【図６】
2005521952.tif 000062
【図７】
2005521952.tif 000063
【図８】
2005521952.tif 000064
【図９】
2005521952.tif 000065
【図１０】
2005521952.tif 000066
【図１１】
2005521952.tif 000067
【手続補正書】
【提出日】平成16年11月29日(2004.11.29)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
並列コーパスから結合確率モデルを作成することを含んでなる方法。
【請求項２】
請求項１に記載の方法において、
結合確率モデルと並列コーパスから句間確率辞書を作成することをさらに含んでいる方法。
【請求項３】
請求項１に記載の方法において、
並列コーパスが、第一言語の複数の文および対応する第二言語の複数の文を含んでいる方法。
【請求項４】
請求項２に記載の方法において、
前記モデルを作成するステップが、
概念Ｃのバッグを確率的に作成し、
非表示概念ｃｉ∈Ｃの単一セットを作成して提示し、そして各概念は、一対の句
【数１】
2005521952.tif 000068
を、
【数２】
2005521952.tif 000069
と
【数３】
2005521952.tif 000070
が各々少なくとも一つの語を含んでいる分布
【数４】
2005521952.tif 000071
にしたがって作成し、次いで
各言語で作成された句を、句の二つの線形シーケンスをつくるように順序付ける、
ステップを含んでいる方法。
【請求項５】
請求項２に記載の方法において、
前記モデルを作成するステップが、
（１）概念Ｃのバッグを確率的に作成し、
（２）ＥとＦを空の文εに初期設定し、
（３）概念ｃｉ∈Ｃを無作為に取り出し、次に一対の句
【数５】
2005521952.tif 000072
を、
【数６】
2005521952.tif 000073
と
【数７】
2005521952.tif 000074
が各々少なくとも一つの語を含んでいる分布
【数８】
2005521952.tif 000075
にしたがって作成し、
（４）句
【数９】
2005521952.tif 000076
をＦの末端に付加し、
（５）他の句がｌと
【数１０】
2005521952.tif 000077
（但し
【数１１】
2005521952.tif 000078
は句
【数１２】
2005521952.tif 000079
の長さを示す）の間のどの位置も占めないならば、句
【数１３】
2005521952.tif 000080
をＥ内の位置ｌに挿入し、次いでステップ（３）−（５）をＣが空になるまで繰り返す、
ステップを含んでいる方法。
【請求項６】
請求項４又は５に記載の方法において、
ＥとＦ内に高頻度のｎ−グラムを確認し、
アラインメントを有するｔ分布テーブルを初期設定し、
ビタビベースのＥＭトレーニングを複数回繰返し実施し、次いで
結合確率モデルと条件付確率モデルを導出する、
ことによってモデルをトレーニングすることをさらに含んでいる方法。
【請求項７】
請求項１に記載の方法において、
第一言語の入力文の翻訳文を、グリーディー操作を使って決定することをさらに含んでいる方法。
【請求項８】
請求項１に記載の方法において、
第一言語の入力文の翻訳文を、ビームサーチアルゴリズムを使って決定することをさらに含んでいる方法。
【請求項９】
並列コーパス中の語間のアラインメント及び句ベースのモデルを使って、並列コーパスから句間確率辞書を作成することを含んでなる方法。
【請求項１０】
請求項９に記載の方法において、
並列コーパスが、第一言語の複数の文及び対応する第二言語の複数の文を含んでいる方法。
【請求項１１】
請求項１０に記載の方法において、
第一言語の入力文を句のシーケンスに区分し、
前記句を各々、第二言語の句に翻訳し、次いで
第二言語の出力句を再び順序付ける、
ことによって第一言語の入力文に対する最良の第二言語の出力文を決定することをさらに含んでいる方法。
【請求項１２】
請求項１１に記載の方法において、
前記再び順序付けるステップが、相対的歪確率分布を使って出力句を再び順序付けるステップを含んでいる方法。
【請求項１３】
請求項９に記載の方法において、
前記作成するステップが、
並列コーパスの両側に語間のアラインメントを実行して複数の語のアラインメントを作成し、次いで
前記複数の語のアラインメント中の語のアラインメントと一致する、複数の整列された句の対を集める、
ステップを含んでいる方法。
【請求項１４】
請求項１３に記載の方法において、
句の翻訳確率分布を、前記集めた句の対から、相対頻度によって推定する、ことをさらに含んでいる方法。
【請求項１５】
請求項１４に記載の方法において、
語を整列させた並列コーパスの両側を構文解析系で構文を解析して構文解析ツリーを作成し、次いで
整列された句の対各々について、両方の句が構文解析ツリーのサブツリーであるかどうかを検査する、
ことをさらに含んでいる方法。
【請求項１６】
請求項１４に記載の方法において、
集めた、複数のアラインメントを有する整列された句の対を識別し、次いで
前記複数のアラインメント各々に対する字句の重みを計算する、
ことをさらに含んでいる方法。
【請求項１７】
請求項９に記載の方法において、
前記作成するステップが、
並列コーパスに対して二方向の語間アラインメントを実行して２セットの語のアラインメントを作成する、
ステップを含んでいる方法。
【請求項１８】
請求項１７に記載の方法において、
前記２セットの語のアラインメントが交差するときのアラインメントポイントを識別することをさらに含んでいる方法。
【請求項１９】
請求項１７に記載の方法において、
２セットの語のアラインメントが併合するときのアラインメントポイントを識別するステップをさらに含む方法。
【請求項２０】
（１）第一言語の複数の語を含む入力文字列を第二言語の初期仮説から受け取り、
（２）前記入力文字列の複数の語かららシーケンスを選択し、
（３）前記選択されたシーケンスに対して第二言語の可能性のある句の翻訳を選択し、
（４）前記可能性のある句の翻訳を現在の仮説に連結して更新された仮説をつくり、
（５）前記選択されたシーケンスの語に翻訳されたという印をつけ、
（６）その仮説のシーケンスをスタックに記憶させ、
（７）前記更新された仮説の確率コストを更新し、
（８）スタックの大きさに基づいてステップ（２）−（７）を繰返して入力文字列にする可能性のある翻訳を１又は２以上作成し、次いで
（９）スタック内の前記可能性のある翻訳中の最高の確率を有する一つを選択する、
ことを含んでなる方法。
【請求項２１】
請求項２０に記載の方法において、
前記初期仮説が語を全く含んでいない方法。
【請求項２２】
請求項２０に記載の方法において、
可能性のある翻訳各々が、入力文字列中に対応する未翻訳語を残さない仮説を含んでいる方法。
【請求項２３】
請求項２０に記載の方法において、
前記確率コストを更新するステップが、更新された仮説に対する現在のコストを計算し次いで更新された仮説に対する将来のコストを推定するステップを含んでいる方法。
【請求項２４】
請求項２０に記載の方法において、
前記更新された仮説がスタック内のｎベスト更新仮説よりコストが高い場合は（ｎは予め定められたビームの大きさに対応している）、更新された出力シーケンスを捨てることをさらに含む方法。
【国際調査報告】
2005521952.tif 000081
2005521952.tif 000082
2005521952.tif 000083
2005521952.tif 000084
2005521952.tif 000085