(57)【要約】第一言語の原始ストリング内の構文チャンクを検出し、その原始ストリング内の検出された構文チャンクに構文ラベルを割り当て、その原始ストリング内の検出された構文チャンクを第二言語の目的ストリング内の構文チャンクにマップし、そのマッピングが前記割り当てられた構文ラベルに基づいており、次いで前記原始ストリングを第二言語の可能な翻訳に翻訳することを含む方法。
2005527894.tif 000002
【特許請求の範囲】
【請求項１】
第一言語の原始ストリング内の構文チャンクを検出し、
その原始ストリング内の検出された構文チャンクに構文ラベルを割り当て、
その原始ストリング内の検出された構文チャンクを第二言語の目的ストリング内の構文チャンクにマップし、そのマッピングは前記割り当てられた構文ラベルに基づいており、次いで
前記原始ストリングを第二言語の可能な翻訳に翻訳する、
ことを含んでなる方法。
【請求項２】
構文ラベルを割り当てるステップが、原始ストリング内の単語にタグされた品詞識別子の部分に基づいて割り当てるステップを含んでいる請求項１に記載の方法。
【請求項３】
前記原始ストリング内の検出された構文チャンクと目的ストリング内のチャンクとの間の接続を定義するステップをさらに含んでいる請求項１に記載の方法。
【請求項４】
接続を定義するステップが、チャンクマッピングテーブルに基づいて接続を決定するステップを含み、そのチャンクマッピングテーブルが構文チャンクラベルに基づいて予め定義された接続を利用する請求項３に記載の方法。
【請求項５】
接続を定義するステップが、原始ストリングから検出されたチャンクと目的ストリング内の少なくとも二つの非接触チャンクとの間の接続を定義するステップを含んでいる請求項３に記載の方法。
【請求項６】
接続を定義するステップが、原始ストリングから検出された少なくとも二つのチャンクと目的ストリング内の単一チャンクとの接続を定義するステップを含んでいる請求項３に記載の方法。
【請求項７】
翻訳するステップが、原始ストリング内の単一の単語に対応する少なくとも二つの単語を目的ストリング内に含ませるステップを含んでいる請求項１に記載の方法。
【請求項８】
翻訳するステップが、語句を翻訳するステップを含んでいる請求項１に記載の方法。
【請求項９】
言語モデルを原始ストリングに適用するステップをさらに含み、その言語モデルが目的ストリングの言語に基づいている請求項１に記載の方法。
【請求項１０】
前記マッピングの確率を決定するステップをさらに含んでいる請求項１に記載の方法。
【請求項１１】
翻訳するステップが、少なくとも一つのＮＵＬＬ単語を目的ストリングに挿入するステップを含んでいる請求項１に記載の方法。
【請求項１２】
機械が実行できる命令、すなわち機械に
第一言語の原始ストリング内の構文チャンクを検出させ；
その原始ストリング内の検出された構文チャンクに構文ラベルを割り当て；
その原始ストリング内の検出された構文チャンクを第二言語ストリング内の構文ストリングにマップさせ、その整列は前記割り当てられた構文ラベルに基づいており；次いで
原始ストリングからの各単語を、第二言語の可能な翻訳に相当する第二単語に翻訳させる；
ように作用する命令を含む機械可読媒体を備えている物品。
【請求項１３】
機械に構文ラベルを割り当てるように作用する命令が、機械に、原始ストリング内の単語にタグされた品詞識別子の部分に基づいて構文ラベルを割り当てるように作用する命令を含んでいる請求項１２に記載の物品。
【請求項１４】
原始ストリング内の検出された構文チャンクと目的ストリング内のチャンクとの間の接続を機械に定義させるように作用する命令をさらに含んでいる請求項１２に記載の物品。
【請求項１５】
機械に接続を定義させるように作用する命令が、機械にチャンクマッピングテーブルに基づいて接続を決定させるように作用する命令を含み、そのチャンクマッピングテーブルが構文チャンクラベルに基づいて予め定義された接続を使用する請求項１４に記載の物品。
【請求項１６】
機械に接続を定義させるように作用する命令が、原始ストリングから検出されたチャンクと目的ストリング内の少なくとも二つの非接触チャンクとの間の接続を機械に定義させるように作用する命令を含んでいる請求項１４に記載の物品。
【請求項１７】
機械に接続を定義させるように作用する命令が、原始ストリングから検出された少なくとも二つのチャンクと目的ストリング内の単一チャンクとの接続を機械に定義させるように作用する命令を含んでいる請求項１３に記載の物品。
【請求項１８】
機械に翻訳させるように作用する命令が、機械に、原始ストリング内の単一の単語に対応する少なくとも二つの単語を目的ストリング内に含ませるように作用する命令を含んでいる請求項１２に記載の物品。
【請求項１９】
機械に翻訳させるように作用する命令が、機械に語句を翻訳させるように作用する命令を含んでいる請求項１２に記載の物品。
【請求項２０】
機械に、言語モデルを原始ストリングに適用させるように作用する命令をさらに含み、その言語モデルが目的ストリングの言語に基づいている請求項１２に記載の物品。
【請求項２１】
機械に、前記マッピングの確率を決定させるように作用する命令をさらに含んでいる請求項１２に記載の物品。
【請求項２２】
機械に翻訳させるように作用する命令が、機械に、少なくとも一つのＮＵＬＬ単語を目的ストリング内に挿入させるように作用する命令を含んでいる請求項１２に記載の物品。
【発明の詳細な説明】
【発明の詳細な説明】
【０００１】
関連出願の相互参照
本願は２００２年３月２８日付けで出願された米国仮特許願第６０／３６８，８５１号の優先権を主張するものである。なおこの特許願は本願に援用するものである。
【０００２】
本発明の起源
本願に記載されている研究と開発は、援助番号Ｎ６６００１−００−１−８９１４に基づいてＤＡＲＰＡ−ＩＴＯの援助を受けてなされたものである。米国政府は本願発明に特定の権利を有している。
【０００３】
背景
機械翻訳（ＭＴ）とは、例えばコンピュータシステムを使って第一言語（原始言語）から別の言語（目的言語）へ自動翻訳することである。ＭＴプロセスを実行するシステムは原始言語を目的言語に「デコードする］といわれている。エンドユーザの眼からみてＭＴプロセスは比較的簡明である。ＭＴプロセスは、原始文（又は単語のストリング）を入力として受け取り、次にその入力した文を処理したのち目的言語の翻訳文を出力する。
【０００４】
ＭＴプロセスの一形態は統計的ＭＴデコーダと呼称されている。従来の統計的ＭＴデコーダは言語モデル（ＬＭ）と翻訳モデル（ＴＭ）を備えている。
【０００５】
概要
本発明の一側面の方法は、第一言語の第一ストリング内の構文チャンクを検出し、その第一ストリング内の検出された構文チャンクに構文ラベルを割り当て、その第一ストリング内の検出された構文チャンクを第二言語のストリングと整列させ、その整列は前記割り当てられた構文ラベルに基づいており、次いで前記第一ストリングからの各単語を第二言語の可能な翻訳に対応する第二単語に翻訳するステップを含んでいる。
【０００６】
下記特徴のうちの１又は２以上が含まれてもよい。第一ストリングからの少なくとも二つの単語をそれら少なくとも二つの単語にタグ付けされた品詞識別子の部分に基づいてグループ化すること。原始ストリング内の検出された構文チャンクと第二ストリング内のチャンクとの間の接続を定義すること。チャンクマッピングテーブルすなわち構造チャンクラベルに基づいて予め定義された接続を利用するチャンクマッピングテーブルに基づいて接続を決定すること。第一ストリングから検出されたチャンクと目的言語の少なくとも二つの非接触チャンクとの間の接続を定義すること。原始ストリングから検出された少なくとも二つのチャンクと目的ストリングの単一チャンクとの接続を定義すること。
【０００７】
詳細な説明
本願に記載されている統計的ＭＴシステムは、下記の別個の三つの部分：（１）確率Ｐ（ｅ）を任意の単語の目的ストリングに割り当てる言語モデル（ＬＭ）、（２）確率Ｐ（ｆ｜ｅ）を目的ストリングと原始ストリングの任意の対に割り当てる翻訳モデル（ＴＭ）及び（３）そのＬＭとＴＭの割り当てられた確率に基づいて翻訳を決定するデコーダとしてモデル化することができる。
【０００８】
従来のＭＴシステムは、一連の単語ベースの決定を行うことによって原始文を目的文に翻訳することができる。その単語ベースの決定は、各原始単語が目的単語に翻訳される翻訳決定を含んでいる。マッピング（整列）の決定も翻訳された各単語について行うことができ、例えば複数の原始単語を、翻訳された原始単語の決定された稔性（fertility）に基づいて単一の目的単語にマップすることができる。再配列（ひずみ）の決定も行うことができ、例えば原始文からの単語の順序を対応する目的文の翻訳された単語の順序に再配列できる。これらの翻訳、マッピング及びひずみの決定は、翻訳の過程で決定される重み付けされた確率に基づいている。
【０００９】
いくつかの原始文は、従来の単語ベースのＭＴシステムによって十分に処理されていない翻訳上の課題を提起する。例えば、翻訳上の課題としては、語句の翻訳、構文上の理由による文の再構成、及び目的文の単一の単語又は語句への隣接していない単語の翻訳がある。
【００１０】
図１は、翻訳すべき原始文を受け取り（１５）、「品詞（part of speech）」（ＰＯＳ）の単一又は複数のタグを原始文の各原始単語に割り当て（２０）、次いでその原始文に含まれている構文「チャンク」を検出する（３０）ステップを含む言語の統計的翻訳モデル（ＬＳＴ）のプロセス１０を示す。ＬＳＴプロセス１０は、単一もしくは複数の割り当てられたＰＯＳタグ及び/又は単一もしくは複数の検出された構文チャンクに部分的に基づいている動作（４０）、（５０）及び（６０）も含んでいる。プロセス１０で単一もしくは複数のＰＯＳタグ及び/又は構文チャンクを使用すると、原始文から目的文への翻訳を改善することができ、特に先に挙げた翻訳上の課題のストリングの翻訳を改善することができる。
【００１１】
ＰＯＳタグは、単語のタイプを示す識別記号を指示し、例えば「VVFIN」記号は定形動詞にタグすることができる。プロセス１０に使用できるＰＯＳタグの代表的なセットは、「Penn Treebank tag set」と呼称されそしてMitchell P. Marcus、Beatricce Santorini及びMary Ann Marcinkiewicz著「Building a Large Anno-lated Corpus of English：The Penn Treebannk」、１９巻、２号（１９９３年６月）、３１３−３３０頁（Special
Issue on Using Large Corpora）に記載されている。なおこの文献は本願に援用するものである。
【００１２】
チャンキングは文中の非再帰動詞、名詞、前置詞又は他の語句をグループ化することを意味する。チャンキングには、原始文のグループ化の検出及び目的文のチャンク結合の出力が含まれている。チャンキングの概念は、Robert Berwick、Steven Abney及びCarol Tenny著「Principle-Based Parsing」（Kluwer Academic publishers）中のAbeny S．の論文（１９９１年）「Parsing by chunks」で考察されている。
【００１３】
さらに図１を参照すると、ＬＳＴプロセス１０は、入力された翻訳すべき原始文を受け取り（１５）、その原始文の各単語にＰＯＳタグをつけ（２０）、各原始文の構文チャンク(例えば語句)を検出し（３０）、文レベルでチャンクの再順序付けを行い（４０）、検出された原始チャンクを目的文の目的チャンクにマップし（５０）、次いで原始文からの各単語を目的文に翻訳する（６０）ステップを含んでいる。動作（６０）で作成された単語の翻訳は、任意の目的言語のモデルを使ってさらに改善できる（７０）。
【００１４】
図２は、動作（２０）中に作成された関連ＰＯＳタグ１１０−１１６を有する各単語、及び動作（３０）中に生成して検出された構文チャンク１０１−１０５を有する典型的な原始文１００を示す。検出されたチャンク１０１−１０５はそれぞれ、構文ラベル例えば「Ｎ、Ｖ、Ｎ、Ｖ及び！」も有している。構文ラベルは、検出されたチャンクに対する文の構文部分を意味し、例えば「Ｎ」は基本名詞句を意味し、「Ｖ」は動詞の複合語を意味し、「Ｐ」は基本前置詞句を意味し、「Ａ」は形容詞を意味し、「Ｆ」は機能語を意味し、そして「！」は句読点を意味する。
【００１５】
チャンクを文レベルで再順序付けすると（４０）、各原始チャンク１０１−１０６と目的文１５０に含まれている対応する目的チャンク１３０−１３４との間の接続１２０−１２５が定義される。多くの場合、目的チャンクが原始チャンクに対して再順序付けされる。この再順序付けは、検出された構文チャンクと目的文内の対応する構文チャンクとの間の可能性のある接続を定義するテンプレートに基づいている。接続は、単一値又は多値（例えば１対１、多数対多数又は１対多数など）である。図３は、図２に示した接続に相当する原始チャンク１０１−１０５と目的チャンク１３０−１３４との間の接続１２０−１２５を示すチャンク接続テーブル１６０を示す。
【００１６】
図４は代表的な文１００に適用したようなプロセス１０の動作（５０）によって作成されるチャンクマッピングを示すチャンクマッピングテーブル１７０、１８０、１９０及び２００を示す。チャンクマッピングは、各原始チャンクを目的チャンクに対し整列させることを意味しそして原始チャンク内の単語及び目的チャンク内の単語のＰＯＳタグで表すことができる。例えば、テーブル１７０に示されているように、原始ＰＯＳタグ１１０（ＡＲＴ）及び１１１（ＮＮ）は、目的ＰＯＳタグ１４０（ＤＴ）及び１４１（ＮＮＰ）に対して整列させられている。チャンクマッピングは多重チャンク（複合チャンク）を単一チャンク又は他の複合チャンクに対して整列させる。例えばテーブル１９０に示すように、原始チャンク１０３は、目的チャンク１３０及び１３１を含む複合チャンクに対して整列させられる。原始文１００からの非隣接チャンクは単一チャンクに結合することができ、例えばテーブル１８０に示すようにチャンク１０２及び１０４は目的チャンク１３２に結合できる。
【００１７】
先に述べたように、各複合チャンクは割り当てられた構文チャンクのラベルで「ラベル付け」することができる。このラベル付けは、その構文ラベルが文中でのそれらの構文の役割を識別できるので、文レベルでのチャンクの再順序付けを改善できる。
【００１８】
プロセス１０は、次に原始言語の文からの原始単語を目的言語の文の単語に翻訳する（６０）。単語の翻訳は、対応する原始単語（チャンクマッピングによって選択される）に割り当てられた品詞に基づいて、例えば割り当てられるＰＯＳタグに対応する単語の選択を制限することで、部分的に決定できる。図５は、プロセス１０の動作（６０）の実行を示し、例えば図１−４に示す実施例に相当する単語の翻訳を示す。
【００１９】
一実施態様では、個々の単語を翻訳することによって目的言語の単語を作成する代わりに、正確に語句を探索することによって複合チャンクを翻訳できる。より詳細に述べれば、原始チャンク全体が既知の語句であることが確認されると、その原始チャンク全体を既知の語句として翻訳できる。例えば図２に示すように,原始チャンク１０３に含まれている単語「der Agrarausschuss」が既知の語句である場合、この単語は目的チャンク１３０−１３１内の単語「the sub-committee for agriculture」に直接翻訳することができる。正確に語句を探索すると、単語ベースの翻訳では容易に翻訳されない慣用語句を翻訳できる。
【００２０】
プロセス１０は、目的文の流暢さのさらなる改善をもたらすために実行される任意の目的言語モデルを含んでいる（７０）。
【００２１】
プロセス１０の数学的公式化
ＬＳＴプロセス１０の操作は数学的にモデル化することができ、例えば、一組の確率決定（probability determinations）でモデル化できる。以下に述べるプロセス１０の数学的モデルは、ノイズがあるチャネルモデルをたどる公式を含んでいる。より詳細に述べると、このことは、Ｐ（ｅ｜ｆ）を直接推定すること（例えば入力ストリングfに対する最良の翻訳ｅ）の代わりに、ベイズ（Bayes）の規則を適用してＰ（ｆ｜ｅ）ｘＰ（ｅ）を最大にすることを意味する。したがって、これによって前記モデルは、二つの部分：翻訳部分Ｐ（ｆ｜ｅ）と言語モデルＰ（ｅ）に分裂する。その言語部分に対して、トリグラム言語モデルを利用できる。
【００２２】
上記翻訳部分は、文レベルの再順序付け（ＳＬＲ）、チャンクのマッピング（ＣＭ）及び単語の翻訳（Ｗ）に分解されて下記の確率式でモデル化できる。
【数１】
2005527894.tif 000003
【００２３】
ＰＯＳタグ付け及びチャンキングは決定的であるから、ｅは目的ストリングの単語のみならずそれらのＰＯＳ及びチャンクへのグループ化を示す。文レベルのチャンクの再順序付け（ＳＬＲ）とチャンク内の単語の再順序付け（ＣＭ）は、テンプレートを使って、例えば、図３と４に示すテーブルからの情報を示すテンプレートを使って実施できる。単語の翻訳（Ｗ）は１単語ごとの翻訳テーブルを使用して達成できる。
【００２４】
上記三つの確率式を直接適用することは、まばらなデータのため問題がある。したがって、上記三つの条件付き確率分布は下記のように簡略化できる。
ｐ（ＳＬＲ）は各目的チャンクのラベルシーケンスだけを条件としており；
ｐ（ＣＭｉ）は関連する原始チャンクラベルと目的チャンクラベル及び目的ＰＯＳタグだけを条件としており；
ｐ（Ｗｉｊ）は関連する目的ＰＯＳタグと単語だけを条件としている。
【００２５】
チャンクマッピングにおける各単語の整列は単語翻訳の確率を要因とする。整列していない原始単語は確率ｐ（ｆｋ｜ＺＦＥＲＴ，ｆｐｏｓｋ）を要因とする。整列していない目的単語は確率ｐ（ＮＵＬＬ｜ｅｋ，ｆｐｏｓｋ）を要因とする。
【００２６】
チャンクマッピングを単語の翻訳に分解する代わりに、下記式によってモデル化される直接の語句探索を実施できる。
【数２】
2005527894.tif 000004
【００２７】
単語整列に対するパラメータは、原始言語ストリングのテキスト(第一コーパス）を目的言語ストリングの翻訳されたテキスト(第二コーパス)に対し整列させるいわゆる並列コーパス法を用いて決定できる。これらの整列は、原始ストリングの原始単語と目的ストリングとの間の対応を確立する。その並列コーパスの両側にもＰＯＳをタグしチャンクすることができる。
【００２８】
チャンクのマッピングは並列コーパス法を使って決定できる。例えば、原始チャンクと目的チャンクが互いに整列している原始単語と目的単語を含んでいる場合、これら二つのチャンクは接続される。整列していない単語を含んでいるチャンクは、一組の規則、例えば、副詞は、整列していない場合、続く動詞チャンクに連結され、又はコンマは、整列していない場合、次の機能単語に連結される、などに基づいて他のチャンクに連結できる。
【００２９】
次に、推移閉包をいずれのチャンク整列に対しても、例えば、下記の規則セットを使って実施できる。すなわち、チャンクｆｉがｅｘと整列したならば、ｆｊはｅｘと整列し、そしてチャンクｆｉがｅｙと整列したならば、チャンクｆｊはたとえ互いに整列した単語を含んでいなくてもｅｙと整列すると考えられるという規則セットである。上記推移閉包は、原始文と目的文内の複合チャンク間の１対１のマッピングを保証する。
【００３０】
並列コーパスを前記式に基づいて整列させると、単語の翻訳［ｐ（ｆｋ｜ＺＦＥＲＴ，ｆｐｏｓｋ）とｐ（ＮＵＬＬ｜ｅｋ，ｆｐｏｓｋ）を含む］、複合チャンクのマッピング及び文レベルの再順序付けに関する統計資料を収集することができる。次に条件付き確率分布を最尤推定法で収集できる。正確な語句探索をおこなうためのデータはノイズが多いのでその確率は平滑化される。
【００３１】
一実施態様のモデル（例えば「デコーディング」）の翻訳部分は以下の二つのステップで実施できる。第一に、各文レベルのチャンクを再順序付けするための文レベルのテンプレート（ＳＬＴ）を作成する。第二に、目的翻訳が、左から右へ一回に一単語ずつ構築される。これは、与えられた原始チャンクシーケンス各々に対するトップｎのＳＬＴについて繰り返される。最終的に、全スコアが最良の翻訳がシステムの出力として選択される。
【００３２】
与えられた文レベルテンプレート（ＳＬＴ）に対する目的文は、動的プログラミングを使用してビタビ（Viterbi）サーチ法によって構築できる。この場合、必要に応じてチャンクマッピングのテンプレートが選択される。次に、単語スロットが、一語ずつの翻訳テーブルと言語モデルを使って満たされる。各複合チャンクを終了したとき、どのチャンクマッピングのテンプレートが使用されたかに関する情報を破棄できる。いくつかの実施態様では、目的ストリングの構築にＮＵＬＬ単語の挿入が含まれている。
【００３３】
しかし、各部分翻訳（又は仮定）に対しては下記の情報が維持される。
−作成された最後の二つの単語（言語モデルが要求する）；
−完全でないにしても現行のチャンクマッピングテンプレート；
−現在のスコア（「スコア」は部分翻訳の決定、チャンクマッピングの決定などの組合わせ確率の積を意味する）；
−最良経路に対するバックポインタ；
−最終チャンクの位置；
−チャンク内に作成された最終単語の位置；
−「スタック化チャンクマッピングテンプレート」。
【００３４】
スタック化チャンクマッピングテンプレートは、切断された複合チャンクが目的翻訳で埋められているとき、例えば、ＳＬＴが、「Ｖ＋Ｐ」チャンクを「Ｖ」と「Ｐ」の間の追加のマテリアルで作成することを要求しているときに要求される情報を参照する。この場合、選択されたチャンクマッピングテンプレートに関する情報は、完全に埋められるまで「Ｖ」と「Ｐ」の間を通じて伝達されねばならない。
【００３５】
目的文内の与えられた位置の仮定スペースの計算量（complexity）は式：Ｏ（Ｖ２Ｃ１＋Ｓ）で表すことができ、式中Ｖは語彙の大きさであり、Ｃは適用可能なチャンクマッピングテンプレートの数であり、そしてｓはスタック化チャンクマッピングテンプレートの数である。
【００３６】
このモデルは、翻訳を、目的言語の連続複合チャンクに限定することによって簡略にすることができ、こうすることによってスタック化チャンクマッピングテンプレートに対する要求がなくなる。こうして、与えられた位置における計算量の式が簡略化されてＯ（Ｖ２Ｃ）になる。こうしてまた文の長さについてデコーディングが線形計算量を有するようになる。
【００３７】
図６は、先に考察した式と公式化でモデル化されたＬＳＴプロセス１００の一実施態様を示す。この実施例で、ＬＳＴプルセス１００は、ｎ個の異なる文レベルのテンプレートに対しｎ回繰り返されるループ（１３５、１４０、１５０、１６０及び１７０）を含んでいる。
【００３８】
多くの実施態様を説明してきたが、本発明の精神と範囲を逸脱することなく各種の変形を行えることは分かるであろう。例えば、チャンクマッピングの誤差は、複数の目的言語に翻訳する原始単語によって起こることがある。この種の誤差は、稔性の特徴を付加するか又は複合名詞をさらに前処理することによって避けたり減らすことができる。別の例として、単語の翻訳は確率的単語翻訳法、例えば「Ｔ−Ｔａｂｌｅ」翻訳法を利用して実施できる。別の例として、文レベルテンプレート（ＳＬＴ）を高い信頼性で推定するのに十分な統計量が無いときがある。したがって、他の推定法、例えば節レベルテンプレートを使用してもよく、又は文レベルチャンク翻訳ステップをいくつものチャンク分割及び翻訳決定に分解する方法を使ってもよい。
【００３９】
したがって、他の実施態様は本願の請求項の範囲内に入っている。
【図面の簡単な説明】
【００４０】
【図１】言語の統計的翻訳（ＬＳＴ）法のフローチャートである。
【図２】典型的な原始文と目的文を示す。
【図３】図２の文に対応する文レベルチャンクの再順序付けテーブルを示す。
【図４】図２−３に対応するチャンクマッピング整列テーブルを示す。
【図５】図１−４に対応する単語翻訳を示す。
【図６】ＬＳＴプロセスの第二実施態様を示す。
【図１】
2005527894.tif 000005
【図２】
2005527894.tif 000006
【図３】
2005527894.tif 000007
【図４】
2005527894.tif 000008
【図５】
2005527894.tif 000009
【図６】
2005527894.tif 000010
【国際調査報告】
2005527894.tif 000011
2005527894.tif 000012
2005527894.tif 000013
2005527894.tif 000014
2005527894.tif 000015