JP2010522938A

JP2010522938A - 機械翻訳における大規模言語モデル

Info

Publication number: JP2010522938A
Application number: JP2010501157A
Authority: JP
Inventors: トルシュテン・ブランツ; アショク・シー・ポパット; ペン・シュ; フランツ・ジョセフ・オック; ジェフリー・ディーン
Original assignee: グーグル・インコーポレーテッド
Priority date: 2007-03-26
Filing date: 2008-03-25
Publication date: 2010-07-08
Anticipated expiration: 2028-03-25
Also published as: JP5484317B2; EP2137639A2; US8812291B2; WO2008118905A3; EP2137639B1; US20130346059A1; WO2008118905A2; KR20100015518A; US8332207B2; CN101707873A; CN101707873B; US20080243481A1

Abstract

機械翻訳のためのシステム、方法、およびコンピュータプログラム製品が提供される。いくつかの実施形態では、あるシステムが提供される。このシステムは、コーパスからのnグラムの集合体であって、各nグラムが、コーパスにおける対応する相対頻度、およびnグラムのトークン数に対応する次数nを有し、各nグラムが、次数n-1を有するバックオフnグラムに対応しているnグラムの集合体と、バックオフスコアの集合体であって、各バックオフスコアがnグラムと関連しており、バックオフスコアが、バックオフ係数、およびコーパスにおける対応するバックオフnグラムの相対頻度の関数として決定されるバックオフスコアの集合体とを含む言語モデルを含む。

Description

本明細書は、統計的機械翻訳に関するものである。

人間の作業者によって行われるテキストの手作業の翻訳は、時間がかかりコスト高になる可能性がある。機械翻訳の一目標は、ソース言語のテキストを、ターゲット言語の対応するテキストへと自動的に変換することである。機械翻訳に対する手法には、用例ベース機械翻訳および統計的機械翻訳を含めて、いくつかの異なったものがある。統計的機械翻訳は、ソース言語で特定の入力が与えられると、ターゲット言語における最も確度の高い翻訳を識別しようと試みる。例えば、ある文をフランス語から英語に翻訳する場合、統計的機械翻訳は、フランス語の文が与えられると、最も確度の高い英文を識別する。この最尤翻訳は、次のように書くことができる。

式は、すべての可能な文の中から、P(e|f)に対する最も高い値を提供する英文eを記述する。さらにベイズの法則は、

を提供する。ベイズの法則を用いると、この最も確からしい文は、次のように書き直すことができる。

その結果、最も確からしいe(すなわち、最も確からしい英語翻訳)は、eが生ずる確率と、eがfに変換されるはずの確率(すなわち、所与の英文が、フランス語の文へと変換されるはずの確率)との積を最大化するものである。

Web 1T 5-gram Version 1 corpus、LDC Catalog No.:DC2006T13、ISBN:1-58563-397-6 P.F.Brown、V.J.Della Pietra、S.A.Della Pietra、およびR.L.Mercer、「The Mathematics of Statistical Machine Translation:Parameter Estimation」、Computational Linguistics 19(2)、1993年 Franz Joseph OchおよびHermann Ney、「A Systematic Comparison of Various Statistical Alignment Models」、Computational Linguistics、29(1):9-51、2003年3月 J.DeanおよびS.Ghemawat、「MapReduce:Simplified Data Processing on Large Clusters」、Proceedings of the 6th Symposium on Operating Systems Design and Implementation、137〜150頁(2004年12月6日) Papineni,K.、Roukos,S.、Ward,T.、およびZhu,W.J.、「BLEU:a method for automatic evaluation of machine translation」in ACL-2002:40th Annual meeting of the Association for Computational Linguistics 311〜318頁(2002年) Franz Josef Och、「Minimum error rate training in statistical machine translation」、In Proc.of the 41st Annual Meeting of the Association for Computational Linguistics(ACL)、160〜167頁(2003年)

機械翻訳のためのシステム、方法、およびコンピュータプログラム製品が提供される。概して、一態様では、あるシステムが提供される。このシステムは、コーパスからのnグラムの集合体であって、各nグラムが、コーパスにおける対応する相対頻度、およびnグラムのトークン数に対応する次数nを有し、各nグラムが、次数n-1を有するバックオフnグラムに対応しているnグラムの集合体と、バックオフスコアの集合体であって、各バックオフスコアがnグラムと関連しており、バックオフスコアが、バックオフ係数、およびコーパスにおける対応するバックオフnグラムの相対頻度の関数として決定されるバックオフスコアの集合体とを含む言語モデルを含む。この態様の他の実施形態は、対応するシステム、装置、コンピュータプログラム製品、およびコンピュータ可読媒体を含む。

概して、一態様では、ある方法が提供される。この方法は、訓練データのコーパスからのnグラムの集合体を識別するステップであって、集合体の各nグラムが、コーパス中で生ずる対応する相対頻度、およびnグラムのトークン数に対応する次数nを有し、各nグラムが、次数n-1を有するバックオフnグラムに対応しているステップと、1つまたは複数のバックオフ係数を識別するステップであって、バックオフ係数が、バックオフnグラムの相対頻度の関数として、1つまたは複数のnグラムに対するバックオフスコアを識別するために使用されるステップとを含む言語モデルを生成するステップを含む。この態様の他の実施形態は、方法、装置、コンピュータプログラム製品、およびコンピュータ可読媒体を含む。

概して、他の態様では、ある方法が提供される。この方法は、1つまたは複数のnグラムへと分割される、複数のトークンを有する入力文字列を受信するステップであって、各nグラムが、nグラムのトークン数を識別する次数を有するステップと、入力文字列中の各nグラムに対する確率を識別するために言語モデルを用いるステップとを含む。入力文字列中の第1のnグラムが言語モデル中に見つからない場合、第1のnグラムの次数よりも1つ少ない次数を有するバックオフnグラムを識別し、バックオフnグラムが言語モデル中で見つかった場合には、バックオフ係数と、言語モデルにおけるバックオフnグラムの相対頻度との関数である、第1のnグラムに対するバックオフスコアを識別する。この態様の他の実施形態は、対応するシステム、装置、コンピュータプログラム製品、およびコンピュータ可読媒体を含む。

本明細書で述べられる主題の特定の実施形態は、1つまたは複数の以下の利点を実現するために実施することができる。nグラムに対するバックオフは、バックオフnグラムに対する正規化された確率を計算することなく相対頻度の関数として直接決定することができる。言語モデルは、特定のnグラムに対するnグラムバックオフ値を同じシャード上で生成できる分散環境中で生成することができる。

本明細書で述べられる主題の1つまたは複数の実施形態の詳細は、添付の図面および以下の説明に記載される。本主題の他の特徴、態様、および利点は、その記述、図面、および特許請求の範囲から明らかとなろう。

様々な図面中で、同様の参照番号および指定は同様のエレメントを示す。

例示的な機械翻訳システムのブロック図である。例示的な言語モデルのブロック図である。言語モデルを生成するための方法を示す図である。翻訳を実施するための例示的なシステムの図である。

図1は、例示的な機械翻訳システム100のブロック図である。機械翻訳システムは、ターゲットコーパス102、言語モデル104、並列コーパス106、翻訳モデル108、およびデコーダ110を含む。入力テキスト112を翻訳システム100に提供することにより、翻訳されたテキスト114が生成される。

ターゲットコーパス102は、言語モデル104を訓練するために使用されるターゲット言語(例えば、英語)のテキストの集合体を提供する。ターゲットコーパス102は、例えば、ウェブページおよび新しい記事を含む、テキストのいくつかの異なるソースを含むことができる。いくつかの実施形態では、ターゲットコーパス102は、数百億から数千億程度、またはそれ以上の単語のテキストを含む。1つのこのようなコーパスは、Google Inc.(グーグル社)により提供される、LDC(Linguistic Data Consortium:言語データコンソーシアム)のWeb 1T 5-gram Version 1 corpus、LDC Catalog No.:DC2006T13、ISBN:1-58563-397-6である。このコーパスは、公にアクセス可能なウェブページからのテキストの(個々の単語、句読点、および個々の文の始めと終わりを識別するマーカを含む)約1兆個のトークンを使用する。

言語モデル104は、ソース言語の特定の文字列(例えば、フレーズ、文、または文の集合体)が生ずる確率を識別する。したがって、英語の場合、言語モデル104は、英語の特定の文字列が生ずる確率を識別する。特定の文字列が生ずる確率を識別するために、言語モデル104は、ターゲットコーパス102中で文字列が生ずる回数を、ターゲットコーパス102中の文字列の合計数で割ったものを計算する。例えば、フレーズ「The red wheelbarrow(赤い手押し車)」が100,000,000語のコーパス中で53,000回生じた場合、確率は、

に等しい。

しかし、いくつかの可能性のある文字列は、それがターゲットコーパス102内に見つからないため確率ゼロを有することになる。したがって、いくつかの実施形態では、特定の文字列の確率は、サブの文字列コンポーネントの確率の関数として計算される。サブの文字列を表すための一技法は、nグラムを用いることによる。nグラムは、一連のn個の連続するトークンである。nグラムは、nグラムにおけるトークンの数である次数を有する。例えば、1グラム(またはユニグラム)は、1つのトークンを含み、2グラム(バイグラム)は2つのトークンを含む。

nグラム言語モデルは、文字列の確率を計算するために、nグラムのサブ文字列を使用する。所与の文字列の確率は、nグラム条件付き確率の積として計算することができる。P(y|x)で表されるバイグラムに対する条件付き確率は、単語yが単語xに続いて生ずる確率である。条件付き確率は、概して、ターゲットコーパス102中の相対頻度に従って、経験的に決定される。上記の例では、xが与えられたときの単語yの確率は次式により与えられる。

式中、f(xy)は、ターゲットコーパス102中で文字列「xy」の生ずる頻度またはカウントである。

文字列に対する確率は、条件付き確率の積として決定することができる。例えば、バイグラム言語モデルを用いて、フレーズ「The red wheelbarrow」で始まる文に対するP(The red wheelbarrow)を計算するために、nグラム言語モデルは、
P(The|<start>)P(red|The)P(wheelbarrow|red)
を計算する。式中、<start>は文の開始を表しており、したがって、P(The|<start>)は、文が「The」で始まる確率を表す。

この文字列確率は、次のように一般化することができる。

式中、(e₁,...,e_k)は、文字列中のトークンを表し、nは、言語モデル中で許容される最大のnグラムの次数である。

並列コーパス106は、ソース言語(例えば、英語)のテキスト、および1つまたは複数のターゲット言語(例えば、フランス語)の対応する翻訳の集合体を含む。並列コーパス106は、例えば、ウェブページと新しい記事のペアを含む、テキストのいくつかの異なるソースを含むことができ、その場合、各ペアは、ソース言語のテキストと、ターゲット言語の対応する翻訳されたテキストとを含む。他の例では、並列コーパス106は、多言語データを含むことができる。例えば、6言語の並列翻訳を提供する国連の議事録が利用可能である。

翻訳モデル108は、特定のソース文字列が与えられると、特定のターゲット言語文字列の条件付き確率を識別する。したがって、英語がソース言語であり、フランス語がターゲット言語である場合、翻訳モデル108は、英語の文字列eが与えられると、フランス語の文字列fの確率P(f|e)を識別する。翻訳モデルは、いくつかの異なる方法で生成することができる。いくつかの実施形態では、P(f|e)を決定するためにいくつかのパラメータが推定される。例えば、翻訳モデルは、4つのパラメータt、n、d、およびpにより定義することができる(例えば、P.F.Brown、V.J.Della Pietra、S.A.Della Pietra、およびR.L.Mercer、「The Mathematics of Statistical Machine Translation:Parameter Estimation」、Computational Linguistics 19(2)、1993年で述べられたIBM Model 3)。

翻訳パラメータtは、ソース語から翻訳語を生成する確率、例えば、t(bonjour|hello)を提供する。繁殖(fertility)パラメータnは、ソース語がn個のターゲット語を生成する確率を提供する。例えば、n(2|hello)は、ソース語「hello」が、正確に2つのフランス語を生成する確率を表す。歪み(distortion)パラメータdは、ソース文中の対応するソース語の位置に対して、ターゲット文中のターゲット語の位置に関連する確率を提供する。例えば、d(3|5)は、ある文の位置5にある英語(例えば、5番目の語)が、翻訳されたフランス文の位置3にあるフランス語(例えば、3番目の語)を提供することになる確率を表す。さらに、パラメータpは、スプリアス(spurious)語を含む翻訳の確率を提供する。スプリアス語とは、ソース文字列中のソース語に対応しないソース言語文字列のターゲット言語翻訳で出現する単語のことである。

モデルパラメータの値は、ソース文とターゲット文のペアにおける単語がすべて対応付けられる場合には、直接推定することができる。用語「対応付け(alignment)」は、1対の文において、ソース語とターゲット語の間の1語ごとの接続を表す(例えば、1つの文中でその「hello」が「bonjour」と対応付けられる)データ構造を指すために使用されることになる。いくつかの実施形態では、対応付けは、単に、様々なターゲット語が接続されるソース語の位置を特定するベクトルである。対応付けが知られた場合、パラメータ値を推定することができる。

複数の可能な対応付けが存在する可能性がある。例えば、文のペアが、2つの等しく確からしい対応付けを有する可能性もある。その結果、確率は、個々の対応付けに対して計算することができる。対応付け確率は、単語が特定の方法で対応付けされる尤度を定義する。特定の文のペアが与えられると、個々の対応付けの確率は、P(a|e,f)と記すことができ、その場合、

であり、式中、

であり、かつP(a,f|e)は、すべての対応付けaに対して加算され、またターゲット文が与えられた場合の対応付けとソース文の結合確率を表す。対応付けaが単一の文字で表されているが、それは、その次元が変化しうる行列を表している。具体的には、aは、行列確率変数であり、その特定の値は、特定のソース文と特定のペア化されたターゲット文との間の関連(例えば、リンク)の行列を指す。列がソース語の位置に対応し、行がターゲット語の位置に対応する。対応性がない場合、さらなる行と列を、ヌル語でラベル付けすることができる。行列中の要素は、ゼロと1であり、対応するソースとターゲット文の単語の間の関連が存在するかしないかを示す。使用される対応付けモデルに応じて、行列中でリンクが生ずる可能性のある(例えば、ソース語を複数のターゲット語にマップできるかどうか、単語をヌル語にマップできるかどうかなど)場所に対して制約を課すことができる。

したがって、P(a|e,f)は、P(a,f|e)によって記述することができる。しかし、P(a,f|e)はまた、パラメータ値の関数として記述することもできる。したがって、パラメータ値が知られている場合、対応付け確率は直接計算することができる。

個々の対応付けaは、特定の(f,e)ペアの間の特有の対応付けを指すが、P(a|e,f)は、再度、特有な(f,e)ペアに対して可能な対応付けに対する事後確率である。P(a|e,f)は、何らかの訓練手順により推定することのできるパラメータによって記述されるが、その訓練手順は、現在のパラメータ値を用いて、前の繰返しで達成されたものよりも各ペア間のよりよい単語対応付けを達成し、次いで、その対応付けを用いてパラメータ値を更新し、次いで、それを繰り返して、多数の(f,e)文のペアに対してループさせることにより、パラメータを繰返し学習する。対応付けに関するさらなる詳細は、例えば、Franz Joseph OchおよびHermann Ney、「A Systematic Comparison of Various Statistical Alignment Models」、Computational Linguistics、29(1):9-51、2003年3月で見出すことができる。

局所的な最適値が決定されるまで、反復プロセスを用いてパラメータ値および対応付け確率を推定するために、期待最大値化法(「EM」)アルゴリズムを使用することができる。EMアルゴリズムは、確率論的モデルにおいて、変数の最尤推定を計算する。EMアルゴリズムは、2ステップのプロセスである。期待値ステップは、変数値を、それらが観察された場合と同様に含めることにより、尤度の期待値を計算する。最大化ステップは、期待値ステップで計算された期待される尤度を最大化することによって、最尤推定を計算する。そのプロセスは、期待値ステップと最大化ステップの間で繰り返され、その場合、最大化ステップで計算された変数に対する値は、次の期待値ステップに対して使用される。用語「EMアルゴリズム」は、関連するアルゴリズムのクラスを指し、期待値ステップおよび最大化ステップは、特定のEMアルゴリズムを開発するためのロードマップを提供する。いくつかの実施形態では、最尤推定を見出すために、EMアルゴリズム以外の、例えば、勾配降下または共役勾配技法など、他の技法が使用される。

EMアルゴリズムなどの技法を用いて、翻訳モデル108は、所与のソース言語およびターゲット言語に対して、最も確からしいパラメータ値および対応付け確率を決定するように訓練される。

デコーダ110は、翻訳された文字列(例えば、翻訳されたテキスト114として)を生成するために、言語モデル104および翻訳モデル108を、(例えば、入力テキスト112からの)所与の文字列に適用する。具体的には、デコーダ110は、言語モデル104により決定されるP(e)と、翻訳モデル108により決定されるP(f|e)との積を最大化する文e(例えば、英文)を求めることにより、観察された文f(例えば、フランス語文)を翻訳する。

図2は、例示的な言語モデル200のブロック図である。言語モデル200は、nグラム202、nグラム確率204、およびバックオフスコア206を含む。nグラム202は、例えば、ターゲットコーパス102など、訓練データから導かれる。nグラム202は、特定の言語モデル200に対する各次数のnグラムを含む。例えば、5グラム言語モデルの場合、nグラム202は、訓練データから導かれた5グラム、4グラム、3グラム、2グラム、および1グラムを含む。いくつかの実施形態では、nグラムは、n個の連続するトークンの列を表しており、トークンは、句読点、および他の情報、例えば、文の開始の識別子を含むことができる。

nグラム確率204は、訓練データにおけるnグラム相対頻度の関数として計算された確率推定である。例えば、L個のトークンの文字列は、次式で表すことができる。

確率は、次式のように文字列

に割り当てることができる。

その場合、近似は、文字列中の次の単語を予測する場合、最も近い(n-1)トークンだけが関連するというマルコフ仮定に基づいており、またPに対する「^」表記は、それが確率関数の近似であることを示している。

で示される、文字列

の任意のサブ文字列(例えば、特定のnグラム)に対して、頻度

を計算することができる。サブ文字列の頻度とは、固定された長いサンプル文字列と見なすことのできる訓練データ中のそのサブ文字列の発生頻度を示している。nグラムに対する最尤確率推定は、その相対頻度により与えられる。各nグラムに対する相対頻度rは、次式のように決定することができる。

nグラムの相対頻度は、nグラムの頻度を(n-1)グラムの頻度で割ったものである。訓練データにおける各nグラムに対する確率推定が計算され、言語モデル200中に、nグラム確率204としてnグラムごとに記憶することができる。

相対頻度は、それらが訓練データ中で見つからない場合、特定のnグラムに対してゼロまたは未定義であるとすることができる。その結果、対応する確率推定は、不正確または未定義のものとなりうる。これは、疎データ問題(sparse data problem)と呼ばれる。さらに、高い次数のnグラムを使用することは、潜在的に言語モデルの正確さを高めるが、疎データ問題を悪化させる。その結果、失われたnグラムを補償するために、スムージング技法が使用される。

スムージングは、バックオフスコア206により提供することができる。バックオフスコア206は、所与のnグラムに対して、常に非ゼロの確率が存在するようにするために使用することができる。概して、バックオフは、nグラムのある部分が生ずるかどうかを考慮する。例えば、トライグラム「xyz」が見つからない場合、スムージングは、バックオフnグラム「yz」が生じるかどうかを識別するために行われる。「yz」が生じない場合、スムージングは「z」が生じるかどうかを再帰的に識別する。

いくつかの実施形態では、バックオフスコア206は、nグラムの相対頻度の関数として、直接計算される。したがって、所与のnグラムに対する確率、

は、nグラムが存在する場合、nグラムの相対頻度として表すことができる。したがって、nグラム頻度がゼロを超える場合、すなわち、

である場合、確率推定は、単に、相対頻度

となる。しかし、nグラム頻度が、ゼロを超えない場合、バックオフスコアは、次式のように計算される。

式中、αはバックオフ係数であり、またSは、計算が確率ではなく、スコアであることを示すために使用されるが、それは、nグラムの相対頻度を用いて直接計算されるからである。本質的に、バックオフ係数は、(例えば、存在していないnグラムを補正するために)バックオフnグラムの相対頻度に対してペナルティを適用する。いくつかの実施形態では、バックオフ係数αは、k(すなわち、nグラムの次数)に依存することができる。変数α値を決定するための技法の例を、以下で述べる。代替的に、nグラムの次数にかかわらず、単一の値(例えば、α=0.4)を指定することもできる。

計算は、バックオフがユニグラムに達するまで、見つからないバックオフnグラムを求めて、繰返し行われる。ユニグラムレベルにおいて、スコアは、次のようになる。

式中、Nは訓練データのサイズである。

いくつかの実施形態では、バックオフスコア206は、特定のnグラムの次数に対して1つまたは複数のα値を含む。その場合、nグラムの次数に対するα値、および識別されたバックオフnグラムの相対頻度を用いて、入力nグラムに応じて動作時に、特定のnグラムに対する特有のスコアが計算される。したがって、個々のバックオフスコアは、言語モデル200中に記憶されていないが、必要に応じて生成される。

図3は、言語モデルを生成するための方法300を示す。便宜上、方法300は、方法300を実施するシステムに関連して述べるものとする。

システムは、302で、訓練データを受け取る。訓練データは、例えば、ターゲットコーパス(例えば、ターゲットコーパス102)中のテキストの一部またはすべてとすることができる。いくつかの実施形態では、nグラム言語モデルが、識別された訓練データを用いて生成される。

さらに、いくつかの実施形態では、大規模の訓練データ(例えば、テラバイトのデータ)に対して、分散された訓練環境が使用される。分散された訓練のための1つの例示的な技法はMapReduce（マップリデュース）である。用語MapReduceは、大規模のデータセットを処理し、かつ生成するためのプログラミングモデルとそのモデルの実装とを記述する。そのモデルおよびそのライブラリ実装が共に、MapReduceと呼ばれることになる。MapReduceを用いて、プログラマは、入力(キー、値)ペアを処理して1組の中間(キー、値)ペアを生成するMap関数と、同じ中間キーに関連付けられたすべての中間値をマージするReduce関数とを指定する。この機能スタイルで記述されたプログラムは自動的に並列化され、コモディティコンピュータの大規模クラスタ上で実行することができる。ランタイムシステム、またはフレームワークを実装して入力データを区分し、1組のマシンにわたりプログラムの実行をスケジュールし、マシン障害を処理し、かつ必要なマシン間の通信を管理することができる。

MapReduceの計算は、1組の入力(キー、値)ペアを取得し、1組の出力(キー、値)ペアを生成する。ユーザは、その計算を2つの関数、MapおよびReduceとして表す。

例えば、プログラマにより記述されるMapは、入力(キー、値)ペアを取得し、1組の中間(キー、値)ペアを生成する。MapReduceライブラリは、同じ中間キーIと関連するすべての中間値を共にグループ化し、それらをReduce関数に渡す。

さらに、例えば、プログラマにより記述されるReduce関数は、中間キーIおよびそのキーに対する1組の値を受け入れる。それは、これらの値を共にマージして、おそらく、値のより小規模な組を形成する。通常、各Reduce呼出しに対して、ゼロまたは1の出力値が生成される。中間値は、イテレータを介してユーザのReduce関数に供給される。この方法では、メモリに適合するには大きすぎる値のリストを処理することができる。MapReduceのさらなる詳細は、J.DeanおよびS.Ghemawat、「MapReduce:Simplified Data Processing on Large Clusters」、Proceedings of the 6th Symposium on Operating Systems Design and Implementation、137〜150頁(2004年12月6日)で述べられている。

通常、いくつかのMapタスクは、異なるプロセッサ上で(例えば、異なるコンピューティング装置上で)、また入力データの異なる部分に対して独立して動作する。同様に、いくつかのReduceタスクは、中間データの一部に対して独立して動作する。中間データの部分は、同じレデューサ(reducer)が、所与の中間キーに対するすべての値に対して動作するように、中間キーに従って区分される。

システムは、304で、訓練データから語彙(vocabulary)を生成する。語彙は、訓練データ内の個々のトークン(例えば、単語、句読点)を識別する。MapReduceが訓練データに適用されて、語彙中の各トークンと関連する頻度カウントと共に、語彙を生成することができる。

Mapフェーズは、入力(キー、値)ペアを取得し、中間(キー、値)ペアを生成する。具体的には、Mapフェーズに対する入力(キー、値)ペアは、ノードを識別するキーと、そのノード中のテキストである値とに対応する。中間(キー、値)ペアは、個々の単語に対応するキー値、およびその単語に対応する値を有する。Reduceフェーズは、同じキーを有する中間(キー、値)ペアを、単一の出力(キー、値)へと低減する。具体的には、Reduceは、訓練データ中の単語に対する語彙およびその頻度、(単語、頻度)を出力する。

例えば、3つのシャードS1、S2、およびS3に対して、語彙および単語頻度を生成することができる。シャードS1は、訓練データテキスト「a rose(バラ)」を含む。シャードS2は、テキスト「is a rose(はバラだ)」を含む。シャードS3は、テキスト「a rose is a rose(バラはバラだ)」を含む。Mapフェーズ中、各シャードに対する入力は、キー=IDおよび値=文である。Map出力は、キー=単語、および値=1である。具体的には、S1からのMapは中間(キー、値)ペアを生成する。
(<s>,1)
(a,1)
(rose,1)
(</s>,1)。

S2からのMapは中間(キー、値)ペアとして出力される。
(<s>,1)
(is,1)
(a,1)
(rose,1)
(</s>,1)。

最後に、S3からのMapは中間(キー、値)ペアを生成する。すなわち、
(<s>,1)
(a,1)
(rose,1)
(is,1)
(a,1)
(rose,1)
(</s>,1)。

いくつかの実施形態では、中間(キー、値)ペアは、冗長なエントリを簡単化することにより、Reduceフェーズの前に最適化することができる。例えば、S3からの中間(キー、値)ペアは、次のように最適化することができる。
(<s>,1)
(a,2)
(rose,2)
(is,1)
(</s>,1)。

Reduceフェーズ中、中間(キー、値)ペアは、組み合わされて出力(キー、値)ペアを生成し、その場合、キー=単語、および値=カウントである。例で得られた出力(キー、値)ペアは、次のようになる。
(<s>,3)
(a,4)
(is,2)
(rose,4)
(</s>,3)。

Reduceフェーズの結果は、訓練データ中のテキストに対する語彙ならびに単語頻度を提供する。いくつかの実施形態では、例えば、ハッシュ関数を用いて、特定のシャードの中間(キー、値)に対する特定のReduceシャードが識別される。

語彙を生成するためのMapおよびReduce関数は、以下のように表すことができる。
Map(string key,string value){
//key=docid,ignored;value=document
array words=Tokenize(value);
for i=1..#words Emit(words[i],"1");}
int ShardForKey(string key,int nshards){return Hash(key)% nshards;
}
Reduce(string key,iterator values){
//key=term;values=counts
int sum=0;
for each v in values
sum+=Parselnt(v);
Emit(AsString(sum));
}

システムは、306で、語彙を用いてnグラムを生成する。語彙により、システムは、最大のnグラム次数まで、語彙トークンのあらゆる可能な組合せを決定することが可能になる。システムは、nグラム、および訓練データ内のその頻度を生成するために、MapReduceを用いて実施することができる。

Mapフェーズは、語彙を考慮して、訓練データシャードを処理することができる。Reduceフェーズは、出力(キー、値)ペアが(nグラム、頻度)ペアであるように、nグラムを組み合わせる。

例えば、3つの例示的なシャードが、MapReduceを用いて2グラムに対するnグラム頻度を示すために使用される。例示的なシャードは、S4、S5、およびS6である。シャードS4は、テキスト「a rose foo」を含む。シャードS5はテキスト「is a rose bar」を含み、またシャードS6はテキスト「a rose is a rose」を含む。

Mapフェーズ中、Map関数は、語彙の関数として、ノードに対する入力(キー、値)に適用される。この例の語彙は、(<s>、</s>、<UNK>、a、is、rose)であり、この場合、<UNK>は、例えば、「foo」など、訓練データ中のまれな語を表す総称的なプレースホルダを提供する。Mapフェーズで生成された中間(キー、値)ペアは、2グラムに等しいキーと、その2グラムに対する値を有する。したがって、S4の場合、中間(キー、値)ペアは次のようになる。
(<s>a,1)
(a rose,1)
(rose<UNK>,1)
(<UNK><is>,1)。

S5の場合、中間(キー、値)ペアは次のようになる。
(<s>is,1)
(is a,1)
(a rose,1)
(rose<UNK>,1)
(<UNK></s>,1)。

最後に、S6に対する中間(キー、値)ペアは次のようになる。
(<s>a,1)
(a rose,1)
(rose is,1)
(is a,1)
(a rose,1)
(rose</s>,1)。

Reduceフェーズ中、中間(キー、値)ペアは、組み合わされて出力(キー、値)ペアを生成し、その場合、キーは別個の2グラムであり、値は各nグラムに対するカウントである、すなわち、キー=2グラム、値=カウントである。例で得られた出力(キー、値)ペアは次のようになる。
(<s>a,2)
(<s>is,1)
(a rose,3)
(is a,2)
(rose is,1)
(rose<UNK>,2)
(rose</s>,1)
(<UNK></s>,2)。
したがって、Reduceフェーズの結果は、コーパス中のその頻度と共に2グラムを提供する。

nグラムを生成するためのMap関数は、以下のように表すことができる。
Map(string key,string value){
//key=docid,ignored;value=document
array ids=Tolds(Tokenize(value));
for i=1..#ids
for j=0..maxorder-1
Emit(ids[i-j..i],"1");
}

Reduce関数は、語彙生成のためのReduce関数と同様に表すことができる。

システムは、308で、nグラムに対する相対頻度を決定する。相対頻度は、上記で次のように定義されたことを思い出されたい。

コーパス中のnグラムの相対頻度もまた、MapReduceを用いて識別することができる。例えば、nグラムは、いくつかのシャードに分割することができる。nグラムおよび頻度の入力はMapおよびReduceフェーズで処理されて、上記で述べたものと同様の方法で、nグラムに対する相対頻度を生成することができる。

具体的には、同じシャード上で相対頻度を計算するために必要な分子および分母に対する値を設定するシャーディング関数を使用することができる。特に、ハッシュ関数をnグラムの最初の単語に適用することができる。その結果、必要なnグラム、

および

は、同じ最初の単語、

を共用し、(すべてユニグラムである場合を除き)同じシャード上に配置されることになる。

しかし、いくつかの実施形態では、最初の単語だけを使用するシャーディングは、不均衡なシャードになる可能性がある。例えば、いくつかの語句は、不均衡な数のnグラムの開始部(例えば、ストップワード、いくつかの句読点マーク、または文の開始マーカ)で見出される可能性がある。シャードは、nグラムの最初の2語に基づくハッシングによりさらに平均して平衡が取られるはずである。例えば、
Int ShardForKey(string key,int nshards){
String prefix=FirstTwoWords(key);
Return Hash(prefix)% nshards;
}

さらに、ユニグラムカウントが、個々のシャード内の相対頻度を計算するために、各シャード上に複製される。しかし、データ量は、nグラムの全体数と比較するとわずかなものである。

システムは、310でバックオフスコアを決定する。個々のシャードは、シャード中のnグラムに対する相対頻度を計算するために必要なすべての情報を含む。バックオフスコアは、完全なnグラムが見つからないときに計算される。したがって、完全なnグラムの相対頻度、

が見つからない場合、システムは、ユニグラムバックオフに達するまで、例えば、

などのバックオフ相対頻度を再帰的に探す。nグラムは、その最後の2語でシャーディングされ、またすべてのユニグラムは各シャード上に複製されているので、すべてのバックオフ計算は同じシャード内で行うことができる。

いくつかの実施形態では、バックオフスコアは、各シャード上に、そのシャードの各バックオフnグラムに対して記憶される。代替的には、システムは、バックオフ係数αに対する値を記憶するが、それは、(例えば、翻訳すべき入力文字列からの)入力nグラムに応じて、実行時に特定のバックオフスコアを計算するために個々のシャードにより使用される。

要約すると、コーパスから言語モデルを以下のステップで生成することができる。システムが語彙を生成する。コーパスからの入力テキストを用いて、システムは、1グラムの語彙とその頻度を出力する。次に、nグラムおよびその頻度が識別される。nグラムおよび頻度は、入力としてテキストおよび語彙を用いて識別される。nグラムに対する相対頻度が、nグラムおよびその各頻度を用いて計算される。プロセス中の各ステップは、上記で述べたMapReduceを用いて実施することができる。バックオフスコアが、次いで、nグラムの相対頻度の関数として直接決定される。

前述のように、バックオフ係数αには、nグラムの次数に依存して複数の値が存在しうる。例えば、特定のサンプルデータに対して4グラムがしばしば使用される場合、5グラムから4グラムにバックオフするためのペナルティ(すなわち、α値)は、わずかなものにすべきである。それとは反対に、サンプルデータ内で4グラムがしばしば使用される場合は、4グラムから3グラムにバックオフするためのペナルティは大きくすべきである。

heldoutデータと呼ばれる特定のサンプルデータの場合は、言語モデル中で、各次数のnグラムがどれだけ発生するかに関するカウントを取得することが可能である。nグラムの言語モデルにおける複数のバックオフ係数を決定するための一技法は、バックオフ係数を、各次数のカウントに比例するものとして決定することを含む。例えば、特定のheldoutデータセットの場合、何らかの最大の次数nまで、すなわち、k=1,...,nに対して、すべてのkグラムを調べる。次数kにおけるnグラムの割合(coverage)は、言語モデル中でも生ずるheldoutデータにおける次数kのnグラム発生の数を、heldoutデータにおける次数kのnグラム発生の合計数で割ったもの、すなわち、C_k=L_k/N_kとして計算される。ただし、L_kはN_k以下である。さらに、C_kは、次に低いnグラムの次数における割合以下、すなわち、C_kはC_k-1以下である。C_kの計算値が与えられると、各次数のバックオフ係数α_kが次のように決定される。
α_k=1-C_k k=n(最高次数)の場合、また

k=1,..,(n-1)の場合。

結果として、α_k値は、各次数におけるカウントに比例する。例えば、1組のheldoutデータ、および最大次数5の場合、以下のバックオフ係数を計算することができる。すなわち、α₅=0.7012、α₄=0.6090、α₃=0.2547、α₂=0.1052、およびα₁=0.0399である。表記α₅は、5グラムから4グラムにバックオフしたときのバックオフ係数を示す。いくつかの実施形態では、1グラムから0グラムへのバックオフはなく、したがって、そのα₁値は使用されない。

他の技法は、以下のように、バックオフ係数を計算するために公式を少し調整する。
α_k=1-C_k k=n(最高の次数)の場合、および

k=1,..,(n-1)の場合。

上記調整によると、低い次数のバックオフに対するα_k値がわずかに増加する。例えば、同じheldoutデータを用いると、バックオフ係数は次のように計算される。すなわち、
α₅=0.7012、α₄=0.6090、α₃=0.3632、およびα₂=0.1728となる。

他の技法では、バックオフ係数を計算するための公式は、高次のバックオフに対してより高いバックオフ値を提供する。
α_k=(C_k-1-C_k)/C_k k=n(最高の次数)の場合、

k=2,..,(n-1)の場合、および

k=1の場合。

上記の公式は、上記のサンプルα_k値を以下のように調整する。すなわち、α₅=0.9177、α₄=0.9916、α₃=0.4719、α₂=0.1761、およびα₁=0.1858となる。上記のように、所与の言語モデルに対しては、α₁を無視することができる。

いくつかの実施形態では、キャップ値を含めることができる。キャップ値は、バックオフ値が大きくなりすぎることを阻止するために導入することができる。したがって、バックオフ係数は、バックオフ値が、計算されたα_k値の最小、またはα_maxに等しくなるように、何らかのα_maxで上限を設けることができる。例えば、上記のサンプルα値では、α_max=0.95が使用されるとき、バックオフ係数α₄は、計算された値0.9916から、キャップ値0.95へと低減される。

バックオフ係数を計算するための他の一技法では、項M_kが導入される。M_kは、heldoutデータセットで使用される次数kの確率の和である。その場合、次数kのバックオフ分布の合計質量が次数kのheldoutセットの確率質量に比例するように、バックオフ係数が計算される。
α_k=M_k-1/M_k k=2...nの場合、および
α_k=0 k=1の場合。

さらにheldoutデータの同じサンプルセットに対して、上記の公式は、以下の例示的なバックオフ値を提供する。すなわち、α₅=0.5396、α₄=0.5138、α₃=0.1111、α₂=0.0248、およびα₁=0.0である。前の例と同様に、最大バックオフ値α_maxを、バックオフ値に上限を設けるために使用することができる。

いくつかの実施形態では、1つまたは複数のバックオフ係数に対する値を決定するために、識別(discriminative)訓練を使用することができる。機械翻訳システムは、1組の参照翻訳を利用することのできる何らかのサンプルデータに対して、翻訳品質の自動化された尺度、例えば、Bilingual Evaluation Understudy(「BLEU」)スコアを最小にするために、自由パラメータを最適化するように識別訓練技法を通常使用する。識別訓練は、数値的なスコアを直接最適化しようとはしない。そうではなくて、他のバックオフ係数値よりも優れた翻訳スコアを生成する1組のバックオフ係数値が識別される。BLEUスコアは、例えば、Papineni,K.、Roukos,S.、Ward,T.、およびZhu,W.J.、「BLEU:a method for automatic evaluation of machine translation」in ACL-2002:40th Annual meeting of the Association for Computational Linguistics 311〜318頁(2002年)に述べられている。

具体的に、バックオフ係数を識別的に訓練するために、翻訳が利用可能な文の集合体が、バックオフ係数に対して異なる値を用いて翻訳される。BLEU(または同様の)スコアの高い値が得られるバックオフ係数が使用される。統計的機械翻訳の諸機能を識別的に訓練する例示的な一方法は、Franz Josef Och、「Minimum error rate training in statistical machine translation」、In Proc.of the 41st Annual Meeting of the Association for Computational Linguistics(ACL)、160〜167頁(2003年)に述べられている。上記の方法は、バックオフ係数を訓練するために使用することができる。上記の参照において述べられている概略の方法は、翻訳中に言語モデルを各単語の位置で適用する場合に遭遇する実際のバックオフの程度を、さらなる「特徴関数」として得ることにより、バックオフ係数の決定に適用することができる。得られた特徴関数のウェートは、次いで、対数線形関係(例えば、デコード検索目的関数の対数線形公式化)を用いて、バックオフ係数に変換される。特徴関数は、特有のバックオフレベルに対する指示関数(例えば、言語モデルが、正確にk回バックオフされたときは1であり、その他の場合はゼロ)、ステップ関数(例えば、言語モデルが少なくともk回バックオフされたとき1)、または他のパラメータ化とすることができる。

本明細書は、機械翻訳システムに関して述べられてきた。しかし言語モデルと、開示された言語モデルを生成しかつ訓練するための技法とは、例えば、音声認識、光学式文字認識、文字認識を含む言語モデルを用いる他のシステムで実施することができる。

図4は、機械翻訳のための例示的なシステムである。データ処理装置410は、ハードウェア/ファームウェア、オペレーティングシステム、および翻訳プログラム420を含む1つまたは複数のプログラムを含むことができる。翻訳プログラム420は、データ処理装置410と共に動作して、本明細書で述べたオペレーションを行う。したがって、翻訳プログラム420は、1つまたは複数のプロセッサおよびコンピュータ可読媒体(例えば、メモリ)と組み合わせて、システム400における1つまたは複数の構造的コンポーネントを表す。

翻訳プログラム420は、翻訳処理アプリケーション、または部分とすることができる。本明細書で使用する場合、アプリケーションとは、ユーザにより、定義された目的のために使用される別個のコンピュータツールとして理解されるコンピュータプログラムのことである。アプリケーションは、全体的にデータ処理装置410のオペレーティングシステム(OS)中に組み込むことができるが、あるいはアプリケーションは、異なる場所(例えば、OSまたはカーネルモード中の一部、ユーザモード中の一部、および遠隔サーバ中の一部)に位置する異なるコンポーネントを有することができ、また装置410のソフトウェアプラットフォームとして働くランタイムライブラリに組み込むことができる。さらに、アプリケーション処理を、1つまたは複数のプロセッサ490を用いて、ネットワーク480を介して分散させることができる。例えば、翻訳プログラム420の言語モデルを、1つまたは複数のプロセッサ490にわたり分散的に訓練することができる。

データ処理装置410は、1つまたは複数のプロセッサ430、および少なくとも1つのコンピュータ可読媒体440(例えば、ランダムアクセスメモリ、記憶装置など)を含む。データ処理装置410はまた通信インターフェース450、1つまたは複数のユーザインターフェース装置460、および1つまたは複数の付加的装置470を含むことができる。ユーザインターフェース装置460は、表示画面、キーボード、マウス、スタイラス、またはその任意の組合せを含むことができる。

プログラムされた後、データ処理装置410は、相対的なnグラム頻度に応じてバックオフ係数を識別するように動作可能である。さらに、言語モデルを、バックオフ係数が単一のシャードから導出されうるように生成することができる。

本明細書で述べた主題および機能的なオペレーションの諸実施形態は、本明細書で開示された構造、およびその構造的に等価な形態、またはそれらの1つまたは複数のものの組合せを含む、デジタル電子回路で、またはコンピュータソフトウェア、ファームウェア、もしくはハードウェアで、あるいはそれらの1つまたは複数のものの組合せで実施することができる。本明細書で述べた諸実施形態は、1つまたは複数のコンピュータプログラム製品として、すなわち、データ処理装置により実行するための、またはそのオペレーションを制御するための有形なプログラム担持体上に符号化されたコンピュータプログラム命令の1つまたは複数のモジュールとして、実施することができる。有形なプログラム担持体は、伝播信号、またはコンピュータ可読媒体とすることができる。伝播信号は、コンピュータにより実行するために適した受信装置に送信するために、情報を符号化するように生成される、例えば、マシンで生成された電気的、光学的、もしくは電磁的信号など、人工的に生成された信号である。コンピュータ可読媒体は、マシン可読記憶装置、マシン可読記憶基板、メモリ装置、マシンで読取り可能な伝播信号を生じる組成物、あるいはそれらの1つまたは複数のものの組合せとすることができる。

用語「データ処理装置」は、例として、プログラム可能なプロセッサ、コンピュータ、または複数のプロセッサもしくはコンピュータを含む、データを処理するためのすべての装置、デバイス、およびマシンを包含する。装置は、例えば、プロセッサファームウェア、プロトコルスタック、データベース管理システム、オペレーティングシステム、またはそれらの1つまたは複数のものの組合せを構成するコードなど、問題としているコンピュータプログラムのための実行環境を作成するコードを、ハードウェアに加えて含むことができる。

コンピュータプログラム(プログラム、ソフトウェア、ソフトウェアアプリケーション、スクリプトまたはコードとしても知られている)は、コンパイルもしくは解釈される言語、または宣言もしくは手続き形言語を含む、任意の形のプログラミング言語で記述することができ、またそれは、スタンドアロンのプログラムまたはモジュールとして、コンポーネント、サブルーチン、またはコンピューティング環境で使用するのに適切な他のユニットを含む、任意の形で展開することができる。コンピュータプログラムは、必ずしもファイルシステムにおけるファイルに対応していない。プログラムは、他のプログラムまたはデータを保持するファイルの一部(例えば、マークアップ言語文書に記憶される1つまたは複数のスクリプト)に、問題のプログラムに専用の単一のファイルに、または複数の協調されたファイル(例えば、1つまたは複数のモジュール、サブプログラム、またはコードの部分を記憶するファイル)に記憶することができる。コンピュータプログラムは、1つのサイトに位置し、または複数のサイトにわたって分散され、かつ通信ネットワークで相互接続された1つまたは複数のコンピュータ上で実行されるように展開することができる。

本明細書で述べたプロセスおよび論理流れは、入力データに動作して出力を生成することにより諸機能を実施するように、1つまたは複数のコンピュータプログラムを実行する1つまたは複数のプログラム可能なプロセッサにより実施することができる。プロセスおよび論理流れはまた、例えば、FPGA(書換え可能ゲートアレイ)またはASIC(特定用途向けIC)など、専用の論理回路により実施することができ、また装置も専用の論理回路として実施することができる。

コンピュータプログラムを実行するのに適切なプロセッサは、例として、汎用および専用のマイクロプロセッサを共に含み、また任意の種類のデジタルコンピュータの任意の1つまたは複数のプロセッサを含む。一般に、プロセッサは、読取り専用メモリ、またはランダムアクセスメモリ、あるいはその両方から、命令およびデータを受け取ることになる。コンピュータの本質的なエレメントは、命令を行うためのプロセッサと、命令およびデータを記憶するための1つまたは複数のメモリ装置である。一般に、コンピュータはまた、例えば、磁気、光磁気ディスク、もしくは光ディスクなど、データを記憶するための1つまたは複数の大容量記憶装置を含む、またはそこからデータを受信し、またはそれにデータを転送し、あるいはその両方を行うように動作可能に結合される。しかし、コンピュータは、このような装置を有する必要はない。さらに、コンピュータは、他の装置に組み込むこともでき、そのいくつかを挙げると、例えば、移動電話、PDA(携帯情報端末)、携帯型オーディオもしくはビデ再生装置、ゲームコンソール、GPS(全地球測位システム)受信装置などである。

コンピュータプログラム命令およびデータを記憶するために適切なコンピュータ可読媒体は、例として、例えば、EPROM、EEPROM、およびフラッシュメモリ装置などの半導体メモリ装置と、例えば、内部ハードディスクもしくは取外し可能なディスクなどの磁気ディスクと、光磁気ディスクと、CD-ROMおよびDVD-ROMディスクとを含む、不揮発性のメモリ、媒体、およびメモリ装置のすべての形態を含む。プロセッサおよびメモリは、専用の論理回路により補強され、またはそれに組み込むことができる。

ユーザとの対話を提供するために、本明細書で述べた主題の諸実施形態は、ユーザに情報を表示するための、例えば、CRT(陰極線管)、またはLCD(液晶ディスプレイ)モニタなどの表示装置と、ユーザがコンピュータに入力を行うことのできる、キーボードおよび例えば、マウスもしくはトラックボールなどのポインティング装置とを有するコンピュータ上で実施することができる。他の種類の装置も同様に、ユーザとの対話を提供するために使用することができる。例えば、ユーザに提供されるフィードバックは、例えば、視覚フィードバック、聴覚フィードバック、または触覚フィードバックなどの任意の形の感覚的なフィードバックとすることができ、またユーザからの入力は、聴覚、音声、または触覚入力を含む任意の形で受けることができる。

本明細書で述べた主題の諸実施形態は、例えばデータサーバとしてのバックエンドコンポーネントを含む、または例えばアプリケーションサーバなどのミドルウェアコンポーネントを含む、または例えば本明細書で述べられた主題の実施形態とユーザがそれを介して対話できるグラフィカルユーザインターフェースまたはウェブブラウザを有するクライアントコンピュータなどのフロントエンドコンポーネントを含む、あるいは1つまたは複数のこのようなバックエンド、ミドルエンド、もしくはフロントエンドコンポーネントの任意の組合せを含むコンピューティングシステムで実施することができる。システムのコンポーネントは、例えば、通信ネットワークなど、デジタルデータ通信の任意の形態または媒体により、相互接続することができる。通信ネットワークの例は、ローカルエリアネットワーク(「LAN」)、および例えば、インターネットなどの広域ネットワーク(「WAN」)を含む。

コンピューティングシステムは、クライアントおよびサーバを含むことができる。クライアントおよびサーバは、概して、互いに遠隔にあり、通常、通信ネットワークを介して対話する。クライアントおよびサーバの関係は、各コンピュータ上で動作し、かつ互いにクライアント/サーバの関係を有するコンピュータプログラムによって生ずる。

本明細書は多くの仕様を含むが、それらは、いずれの発明の範囲に対する限定としても、または特許請求されうるものに関する限定としても解釈されるべきではなく、特定の発明の特定の実施形態に対して特有なものでありうる特徴を記述するものとして解釈されるべきである。別々の実施形態に関して本明細書で述べられたいくつかの特徴はまた、単一の実施形態中で組み合わせて実施することもできる。それとは反対に、単一の実施形態に関して述べられた様々な特徴はまた、複数の実施形態で別々に、または任意の適切なサブコンビネーションで実施することもできる。さらに、特徴は、いくつかの組合せで動作するものとして上記で述べられ、かつ最初はそのように特許請求されるかもしれないが、特許請求された組合せからの1つまたは複数の特徴を、いくつかの場合には、その組合せから削除することができ、また特許請求された組合せを、サブコンビネーションまたはサブコンビネーションの変形形態へと導くこともできる。

同様に、オペレーションは、図面中で特定の順序で示されているが、これは、このようなオペレーションが、望ましい結果を達成するために、示された特定の順序で、または連続的な順序で実施されることを、あるいはすべての示されたオペレーションが実施されることを要求するものとして理解されるべきではない。いくつかの状況では、多重タスク処理および並列処理が有利となりうる。さらに、上記で述べた諸実施形態において、様々なシステムコンポーネントを分離することは、すべての実施形態でこのような分離を必要とするもとと理解すべきではなく、また前述のプログラムコンポーネントおよびシステムは、概して、単一のソフトウェア製品中に共に統合され、あるいは複数のソフトウェア製品中にパッケージされうるものと理解すべきである。

本明細書に記載の主題に関する特定の諸実施形態が述べられてきた。他の実施形態も、添付の特許請求の範囲に含まれる。例えば、特許請求の範囲に記載されたアクションは、異なる順序で実施することができ、なお、所望の結果を達成することができる。一例として、添付の諸図で示されたプロセスは、所望の結果を達成するために、必ずしも、示された特定の順序、または連続的な順序を必要としない。いくつかの実施形態では、多重タスク処理および並列処理が有利となる可能性がある。

100 機械翻訳システム
102 ターゲットコーパス
104 言語モデル
106 並列コーパス
108 翻訳モデル
110 デコーダ
112 入力テキスト
114 翻訳されたテキスト
200 言語モデル
202 nグラム
204 nグラム確率
206 バックオフスコア
400 システム
410 データ処理装置
420 翻訳プログラム
430 プロセッサ(複数可)
440 コンピュータ可読媒体
450 通信インターフェース
460 ユーザインターフェース装置(複数可)
470 付加的装置(複数可)
480 ネットワーク
490 プロセッサ(複数可)

Claims

コーパスからのnグラムの集合体であって、各nグラムは、前記コーパスにおける対応する相対頻度、および前記nグラムのトークン数に対応する次数nを有し、各nグラムは、次数n-1を有するバックオフnグラムに対応しているnグラムの集合体と、
バックオフスコアの集合体であって、各バックオフスコアがnグラムと関連しており、前記バックオフスコアが、バックオフ係数、および前記コーパスにおける対応するバックオフnグラムの相対頻度の関数として決定されるバックオフスコアの集合体と
を含む言語モデルを備えるシステム。
前記バックオフ係数は、一定のペナルティ値を含む、請求項1に記載のシステム。
前記バックオフ係数は、前記nグラムの次数に依存する、請求項1に記載のシステム。
前記バックオフ係数は、サンプルデータ内で生ずる各次数のnグラムの数を用いて導出される、請求項3に記載のシステム。
前記バックオフ係数は、翻訳モデルの識別的訓練を用いて導出される、請求項1に記載のシステム。
指示特徴関数は、前記バックオフ係数を識別するために使用される、請求項5に記載のシステム。
訓練データのコーパスからのnグラムの集合体を識別するステップであって、前記集合体の各nグラムは、前記コーパス中で生ずる対応する相対頻度、および前記nグラムのトークン数に対応する次数nを有し、各nグラムは、次数n-1を有するバックオフnグラムに対応しているステップと、
1つまたは複数のバックオフ係数を識別するステップであって、前記バックオフ係数は、バックオフnグラムの相対頻度の関数として、1つまたは複数のnグラムに対するバックオフスコアを識別するために使用されるステップと
を含む言語モデルを生成するステップを含む方法。
前記1つまたは複数のバックオフ係数を識別する前記ステップは、
翻訳品質の尺度を最大化する、前記1つまたは複数のバックオフ係数に対する値を識別する識別的訓練を1組のサンプルデータに対して実施するステップを含む、請求項7に記載の方法。
指示特徴関数は、前記1つまたは複数のバックオフ係数を識別するために使用される、請求項8に記載の方法。
前記1つまたは複数のバックオフ係数を識別する前記ステップは、
サンプルデータセット中で、各次数における前記nグラムの発生数から導出されるバックオフ係数を、各nグラムの次数に対して決定するステップを含む、請求項7に記載の方法。
前記1つまたは複数のバックオフ係数を用いてnグラムに対するバックオフスコアを計算し、かつ前記バックオフスコアを記憶するステップをさらに含む、請求項7に記載の方法。
有形なプログラム担持体上で符号化され、データ処理装置にオペレーションを実施させるように動作可能なコンピュータプログラム製品であって、
訓練データのコーパスからのnグラムの集合体を識別するステップであり、前記集合体の各nグラムは、前記コーパス中で生ずる対応する相対頻度、および前記nグラムにおけるトークン数に対応する次数nを有し、各nグラムは、次数n-1を有するバックオフnグラムに対応しているステップと、
1つまたは複数のバックオフ係数を識別するステップであり、前記バックオフ係数は、バックオフnグラムの相対頻度の関数として、1つまたは複数のnグラムに対するバックオフスコアを識別するために使用されるステップと
を含む言語モデルを生成するステップを含むコンピュータプログラム製品。
前記1つまたは複数のバックオフ係数を識別する前記ステップは、
翻訳品質の尺度を最大化する、前記1つまたは複数のバックオフ係数に対する値を識別する識別的訓練を1組のサンプルデータに対して実施するステップを含む、請求項12に記載のコンピュータプログラム製品。
指示特徴関数は、前記1つまたは複数のバックオフ係数を識別するために使用される、請求項13に記載のコンピュータプログラム製品。
前記1つまたは複数のバックオフ係数を識別する前記ステップは、
サンプルデータセット中で、各次数における前記nグラムの発生数から導出されるバックオフ係数を、各nグラムの次数に対して決定するステップを含む、請求項12に記載のコンピュータプログラム製品。
前記1つまたは複数のバックオフ係数を用いてnグラムに対するバックオフスコアを計算し、かつ前記バックオフスコアを記憶するステップを含むオペレーションをさらに含む、請求項12に記載のコンピュータプログラム製品。
1つまたは複数のnグラムへと分割される、複数のトークンを有する入力文字列を受信するステップであって、各nグラムは、前記nグラムのトークン数を識別する次数を有するステップと、
前記入力文字列中の各nグラムに対する確率を識別するために言語モデルを用いるステップとを含み、
入力文字列中の第1のnグラムが前記言語モデル中で見つからない場合には、
前記第1のnグラムの前記次数よりも1つ少ない次数を有するバックオフnグラムを識別するステップを含み、
また前記バックオフnグラムが前記言語モデル中で見つかった場合には、
バックオフ係数と、前記言語モデルにおける前記バックオフnグラムの相対頻度との関数である、前記第1のnグラムに対するバックオフスコアを識別するステップを含む方法。
バックオフスコアを識別する前記ステップは、前記nグラムに対する計算されたバックオフスコアを参照するステップを含む、請求項17に記載の方法。
バックオフスコアを識別する前記ステップは、前記nグラムに対する前記バックオフ係数と、前記バックオフnグラムの前記相対頻度とを用いて前記バックオフスコアを計算するステップを含む、請求項17に記載の方法。
有形なプログラム担持体上で符号化され、データ処理装置にオペレーションを実施させるように動作可能なコンピュータプログラム製品であって、
1つまたは複数のnグラムへと分割される、複数のトークンを有する入力文字列を受信するステップであり、各nグラムが、前記nグラムのトークン数を識別する次数を有するステップと、
前記入力文字列中の各nグラムに対する確率を識別するために言語モデルを用いるステップとを含み、
入力文字列の第1のnグラムが前記言語モデル中で見つからない場合には、
前記第1のnグラムの前記次数よりも1つ少ない次数を有するバックオフnグラムを識別するステップを含み、
また前記バックオフnグラムが前記言語モデル中で見つかった場合には、
前記バックオフ係数と、前記言語モデル中の前記バックオフnグラムの相対頻度との関数である、前記第1のnグラムに対するバックオフスコアを識別するステップを含むコンピュータプログラム製品。
バックオフスコアを識別する前記ステップは、前記nグラムに対する計算されたバックオフスコアを参照するステップを含む、請求項20に記載のコンピュータプログラム製品。
バックオフスコアを識別する前記ステップは、前記nグラムに対する前記バックオフ係数と、前記バックオフnグラムの相対頻度とを用いて前記バックオフスコアを計算するステップを含む、請求項20に記載のコンピュータプログラム製品。