(57)【特許請求の範囲】
【請求項１】
複数の候補翻訳を表す翻訳ラティスにデコーダによってアクセスするステップと、
前記翻訳ラティスにおける分類の予想される誤りを最小化する翻訳仮説を得るために前記翻訳ラティス上でデコードをデコーダによって実行するステップと、
ターゲット翻訳において提案された翻訳としてユーザーが使用するために前記得られた翻訳仮説をデコーダによって提供するステップとを含み、
前記ラティス上でデコードを実行するステップは、ベイズリスク最小化(MBR)デコードを実行するステップを含み、
MBRデコードを実行するステップは、
【数１】
0005572624.tif 000055
を計算するステップを含み、
式中、wは単語であり、θwは定数であり、Eは参照翻訳であり、E’は候補翻訳であり、＃w(E’)はwがE’中に生起する回数であり、Ψは前記翻訳ラティスを表し、P(w|Ψ)は前記翻訳ラティス中のwの事後確率であるコンピュータ実施方法。
【請求項２】
ソース言語のソースサンプルをデコーダに供給するステップを含む前記翻訳ラティスを生成するステップをさらに含む請求項1に記載の方法。
【請求項３】
MBRデコードを実行するステップは、コーパスBLEU利得の近似を計算するステップを含み、
コーパスBLEU利得の近似は、
【数２】
0005572624.tif 000056
で表され、
MBRデコーダは、
【数３】
0005572624.tif 000057
で表され、
式中、wは単語であり、θwは定数であり、Eは参照翻訳であり、E’は候補翻訳であり、＃w(E’)はwがE’中に生起する回数であり、δw(E)はw∈Eであれば1、そうでなければ0である請求項1に記載の方法。
【請求項４】
式
【数４】
0005572624.tif 000058
が成り立ち、
式中、Ψw={E∈Ψ|δw(E)>0}はwを少なくとも1回含む前記翻訳ラティスの経路を表し、Z(Ψw)はΨw内の経路の重みの総和を表し、Z(Ψ)はΨ内の経路の重みの総和を表す請求項1に記載の方法。
【請求項５】
複数の候補翻訳を表す仮説空間にデコーダによってアクセスするステップと、
証拠空間に関して計算された分類の予想される誤りを最小化する翻訳仮説を得るために前記仮説空間上でデコードをデコーダによって実行するステップと、
ターゲット翻訳において提案された翻訳としてユーザーが使用するために前記得られた翻訳仮説をデコーダによって提供するステップとを含み、
前記仮説空間上でデコードを実行するステップは、ベイズリスク最小化(MBR)デコードを実行するステップを含み、
MBRデコードを実行するステップは、
【数５】
0005572624.tif 000059
を計算するステップを含み、
式中、wは単語であり、θwは定数であり、Eは参照翻訳であり、E’は候補翻訳であり、＃w(E’)はwがE’中に生起する回数であり、Ψは前記仮説空間を表し、P(w|Ψ)は前記仮説空間中のwの事後確率であるコンピュータ実施方法。
【請求項６】
前記仮説空間は、ラティスとして表される請求項5に記載の方法。
【請求項７】
前記証拠空間は、N最良リストとして表される請求項6に記載の方法。
【請求項８】
データ処理装置にオペレーションを実行させるように動作可能な、有形なプログラム担体上に符号化された、コンピュータプログラムであって、前記オペレーションは、
複数の候補翻訳を表す翻訳ラティスにデコーダによってアクセスするステップと、
前記翻訳ラティスにおける分類の予想される誤りを最小化する翻訳仮説を得るために前記翻訳ラティス上でデコードをデコーダによって実行するステップと、
ターゲット翻訳において提案された翻訳としてユーザーが使用するために前記得られた翻訳仮説をデコーダによって提供するステップとを含み、
前記ラティス上でデコードを実行するステップは、ベイズリスク最小化(MBR)デコードを実行するステップをさらに含み、
MBRデコードを実行するステップは、
【数６】
0005572624.tif 000060
を計算するステップを含み、
式中、wは単語であり、θwは定数であり、Eは参照翻訳であり、E’は候補翻訳であり、＃w(E’)はwがE’中に生起する回数であり、Ψは前記翻訳ラティスを表し、P(w|Ψ)は前記翻訳ラティス中のwの事後確率であるコンピュータプログラム。
【請求項９】
前記オペレーションは、ソース言語のソースサンプルをデコーダに供給するステップを含む前記翻訳ラティスを生成するステップをさらに含む請求項8に記載のプログラム。
【請求項１０】
MBRデコードを実行するステップは、コーパスBLEU利得の近似を計算するステップを含み、
コーパスBLEU利得の近似は、
【数７】
0005572624.tif 000061
で表され、
MBRデコーダは、
【数８】
0005572624.tif 000062
で表され、
式中、wは単語であり、θwは定数であり、Eは参照翻訳であり、E’は候補翻訳であり、＃w(E’)はwがE’中に生起する回数であり、δw(E)はw∈Eであれば1、そうでなければ0である請求項8に記載のプログラム。
【請求項１１】
式
【数９】
0005572624.tif 000063
が成り立ち、
式中、Ψw={E∈Ψ|δw(E)>0}はwを少なくとも1回含む前記翻訳ラティスの経路を表し、Z(Ψw)はΨw内の経路の重みの総和を表し、Z(Ψ)はΨ内の経路の重みの総和を表す請求項8に記載のプログラム。
【請求項１２】
データ処理装置にオペレーションを実行させるように動作可能な、有形なプログラム担体上に符号化された、コンピュータプログラムであって、前記オペレーションは、
複数の候補翻訳を表す仮説空間にデコーダによってアクセスするステップと、
証拠空間に関して計算された分類の予想される誤りを最小化する翻訳仮説を得るために前記仮説空間上でデコードをデコーダによって実行するステップと、
ターゲット翻訳において提案された翻訳としてユーザーが使用するために前記得られた翻訳仮説をデコーダによって提供するステップとを含み、
前記仮説空間上でデコードを実行するステップは、ベイズリスク最小化(MBR)デコードを実行するステップを含み、
MBRデコードを実行するステップは、
【数１０】
0005572624.tif 000064
を計算するステップを含み、
式中、wは単語であり、θwは定数であり、Eは参照翻訳であり、E’は候補翻訳であり、＃w(E’)はwがE’中に生起する回数であり、Ψは前記仮説空間を表し、P(w|Ψ)は前記仮説空間中のwの事後確率であるコンピュータプログラム。
【請求項１３】
前記仮説空間は、ラティスとして表される請求項12に記載のプログラム。
【請求項１４】
前記証拠空間は、N最良リストとして表される請求項13に記載のプログラム。
【請求項１５】
複数の候補翻訳を表す翻訳ラティスにデコーダによってアクセスするステップと、
前記翻訳ラティスにおける分類の予想される誤りを最小化する翻訳仮説を得るために前記翻訳ラティス上でデコードをデコーダによって実行するステップと、
ターゲット翻訳において提案された翻訳としてユーザーが使用するために前記得られた翻訳仮説をデコーダによって提供するステップとを含む
オペレーションを実行するように動作可能な1つまたは複数のプロセッサを備え、
前記ラティス上でデコードを実行するステップは、ベイズリスク最小化(MBR)デコードを実行するステップを含み、
MBRデコードを実行するステップは、
【数１１】
0005572624.tif 000065
を計算するステップを含み、
式中、wは単語であり、θwは定数であり、Eは参照翻訳であり、E’は候補翻訳であり、＃w(E’)はwがE’中に生起する回数であり、Ψは前記翻訳ラティスを表し、P(w|Ψ)は前記翻訳ラティス中のwの事後確率であるシステム。
【請求項１６】
複数の候補翻訳を表す仮説空間にデコーダによってアクセスするステップと、
証拠空間に関して計算された予想される誤りを最小化する翻訳仮説を得るために前記仮説空間上でデコードをデコーダによって実行するステップと、
ターゲット翻訳において提案された翻訳としてユーザーが使用するために前記得られた翻訳仮説をデコーダによって提供するステップとを含む
オペレーションを実行するように動作可能な1つまたは複数のプロセッサを備え、
前記仮説空間上でデコードを実行するステップは、ベイズリスク最小化(MBR)デコードを実行するステップを含み、
MBRデコードを実行するステップは、
【数１２】
0005572624.tif 000066
を計算するステップを含み、
式中、wは単語であり、θwは定数であり、Eは参照翻訳であり、E’は候補翻訳であり、＃w(E’)はwがE’中に生起する回数であり、Ψは前記仮説空間を表し、P(w|Ψ)は前記仮説空間中のwの事後確率であるシステム。
【請求項１７】
前記仮説空間は、ラティスとして表される請求項16に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、統計的機械翻訳(statistical machine translation)に関するものである。
【背景技術】
【０００２】
人手によるテキスト翻訳は、時間がかかり、また費用もかかる。機械翻訳の目標の1つは、ソース言語のテキストをターゲット言語の対応するテキストに自動翻訳することである。用例に基づく機械翻訳および統計的機械翻訳を含む機械翻訳に対し、いくつかの異なるアプローチがある。統計的機械翻訳は、ソース言語における特定の入力が与えられたときにターゲット言語における確度の最も高い翻訳を識別することを試みるものである。例えば、フランス語のセンテンスを英語のセンテンスに翻訳するときに、統計的機械翻訳では、フランス語のセンテンスが与えられたときに確度の最も高い英語のセンテンスを識別する。この最尤翻訳は、
【０００３】
【数１】
0005572624.tif 000002
【０００４】
と表すことができ、これは、可能なすべてのセンテンスのうちの、P(e|f)に対する最も高い値を与える英語のセンテンスeを表す。それに加えて、ベイズ規則から、
【０００５】
【数２】
0005572624.tif 000003
【０００６】
が与えられる。ベイズ規則を使用することで、この最も可能性の高いセンテンスは、
【０００７】
【数３】
0005572624.tif 000004
【０００８】
のように書き換えることができる。
【０００９】
したがって、最も可能性の高いe(つまり、最も可能性の高い英語の翻訳)は、eが生起する確率とeがfに翻訳される確率(つまり、与えられた英語のセンテンスがフランス語のセンテンスに翻訳される確率)との積を最大にするものである。
【００１０】
言語翻訳タスクの翻訳部分を実行するコンポーネントは、デコーダと呼ばれることが多い。いくつかの場合において、第1のデコーダ(第1パスデコーダ)は、可能な翻訳のリスト、例えば、N最良リストを生成することができる。次いで、第2のデコーダ(第2パスデコーダ)、例えば、ベイズリスク最小化(MBR)デコーダをそのリストに適用し、可能な翻訳のうちのどれが最も正確であるかを理想的には識別することができるが、ただし、この正確さは識別の一部である損失関数を最小化することによって測定される。典型的には、N最良リストは、100から10,000個までの候補翻訳、または仮説を含む。候補翻訳の個数を増やすと、MBRデコーダの翻訳性能が改善される。
【発明の概要】
【課題を解決するための手段】
【００１１】
本明細書では、言語翻訳に関係する技術について説明する。
【００１２】
一般に、本明細書で説明されている主題の一態様は、複数の候補翻訳を表す翻訳ラティス(lattice)にアクセスするアクションと、翻訳ラティスにおける分類の予想される誤りを最小化する翻訳仮説を得るために翻訳ラティス上でデコードを実行するアクションと、ターゲット翻訳において提案された翻訳としてユーザーが使用するための得られた翻訳仮説を提供するアクションとを含む方法で実現することができる。この態様の他の実施形態は、対応するシステム、装置、およびコンピュータプログラム製品を含む。
【００１３】
これらの態様および他の実施形態は、以下の特徴のうちの1つまたは複数を適宜含みうる。この方法は、ソース言語のソースサンプルをデコーダに供給するステップを含む翻訳ラティスを生成するステップをさらに含む。MBRデコードを実行するステップは、コーパスBLEU利得の近似を計算するステップを含む。コーパスBLEU利得の近似は、
【００１４】
【数４】
0005572624.tif 000005
【００１５】
で表され、式中、wは単語であり、θwは定数であり、Eは候補翻訳であり、E’は自動翻訳であり、＃w(E’)はwがE’中に生起する回数であり、δw(E)はw∈Eであれば1、そうでなければ0である。
【００１６】
ラティス上でデコードを実行するステップは、ベイズリスク最小化(MBR)デコードを実行するステップを含む。MBRデコードを実行するステップは、
【００１７】
【数５】
0005572624.tif 000006
【００１８】
を計算するステップを含み、式中、wは単語であり、θwは定数であり、E’は自動翻訳であり、＃w(E’)はwがE’中に生起する回数であり、Ψは翻訳ラティスを表し、P(w|Ψ)は翻訳ラティス中のwの事後確率(posterior probability)である。式
【００１９】
【数６】
0005572624.tif 000007
【００２０】
が成り立ち、式中、Ψw={E∈Ψ | δw(E)>0}はwを少なくとも1回含む翻訳ラティスの経路を表し、Z(Ψw)はΨw内の経路の重みの総和を表し、Z(Ψ)はΨ内の経路の重みの総和を表す。
【００２１】
一般に、本明細書で説明されている主題の他の態様は、複数の候補翻訳を表す仮説空間にアクセスするアクションと、証拠空間に関して計算された分類の予想される誤りを最小化する翻訳仮説を得るために仮説空間上でデコードを実行するアクションと、ターゲット翻訳において提案された翻訳としてユーザーが使用するための得られた翻訳仮説を提供するアクションとを含む方法で実現することができる。この態様の他の実施形態は、対応するシステム、装置、およびコンピュータプログラム製品を含む。
【００２２】
これらの態様および他の実施形態は、以下の特徴のうちの1つまたは複数を適宜含みうる。仮説空間は、ラティスとして表される。証拠空間は、N最良リストとして表される。
【００２３】
本明細書で説明されている主題のいくつかの特定の実施形態は、以下の利点のうちの1つまたは複数を実現するように実施されうる。ラティスのMBRデコードを行うと、仮説および証拠空間のサイズが増大し、したがって、利用可能な候補翻訳の数が増え、正確な翻訳を得る可能性が高まる。それに加えて、MBRデコードでは、コーパスBLEUスコアの近似がよくなり(以下でさらに詳しく説明される)、翻訳性能がさらに改善される。さらに、ラティスのMBRデコードは、ランタイム効率が高く、したがって、実行時にデコードを行えるため統計的機械翻訳の自由度が高まる。
【００２４】
一般に、本明細書で説明されている主題の一態様は、翻訳ラティスにおける複数の特徴関数について、翻訳ラティスで表される1つまたは複数の候補翻訳のそれぞれの対応する複数の誤り局面を決定するアクションと、学習集合内のフレーズに対する複数の誤り曲面の組み合わせをトラバースすることによって特徴関数の重みを調節するアクションと、トラバースされた組み合わせに対する誤り件数を最小化する重み値を選択するアクションと、テキストのサンプルを第1の言語から第2の言語に変換するために選択された重み値を適用するアクションとを含む方法で実現することができる。この態様の他の実施形態は、対応するシステム、装置、およびコンピュータプログラム製品を含む。
【００２５】
これらの態様および他の実施形態は、以下の特徴のうちの1つまたは複数を適宜含みうる。翻訳ラティスは、フレーズラティスを含む。フレーズラティス内のアークはフレーズ仮説を表し、フレーズラティス内のノードは部分翻訳仮説が組み換えられた状態を表す。誤り曲面は、直線最適化技術を使用して決定され、トラバースされる。直線最適化技術は、グループ内のそれぞれの特徴関数およびセンテンスについて、候補翻訳の集合上の誤り曲面を決定し、トラバースする。直線最適化技術は、パラメータ空間内のランダム点から始めて誤り曲面を決定し、トラバースする。直線最適化技術は、ランダム方向を使用して重みを調節し、誤り曲面を決定し、トラバースする。
【００２６】
重みは、制約によって制限される。重みは、重みプライア(weights priors)を使用して調節される。重みは、センテンスの1グループ内のすべてのセンテンスにわたって調節される。この方法は、複数の候補翻訳から、翻訳ラティスに対する事後確率を最大化するターゲット翻訳を選択するステップをさらに含む。翻訳ラティスは、10億個を超える候補翻訳に相当する。フレーズは複数のセンテンスを含む。フレーズはすべて、センテンスを含む。
【００２７】
一般に、本明細書で説明されている主題の他の態様は、翻訳ラティス内の特徴関数のコレクションと、それらの特徴関数にわたる、候補言語翻訳の集合に対する複数の誤り曲面と、それらの誤り曲面のトラバースに対して誤りを最小化するように選択された特徴関数に対する重み値とを含む言語モデルを備えるシステムにおいて実現することができる。この態様の他の実施形態は、対応する方法、装置、およびコンピュータプログラム製品を含む。
【００２８】
本明細書で説明されている主題のいくつかの特定の実施形態は、以下の利点のうちの1つまたは複数を実現するように実施されうる。ラティスのMBRデコードを行うと、仮説および証拠空間のサイズが増大し、したがって、利用可能な候補翻訳の数が増え、正確な翻訳を得る可能性が高まる。それに加えて、MBRデコードでは、コーパスBLEUスコアの近似がよくなり(以下でさらに詳しく説明される)、翻訳性能がさらに改善される。さらに、ラティスのMBRデコードは、ランタイム効率が高く、したがって、実行時にデコードを行えるため統計的機械翻訳の自由度が高まる。
【００２９】
ラティスベースの誤り率最小化学習(MERT)では、翻訳ラティス内のすべての翻訳に対する正確な誤り曲面を形成し、これにより、統計的機械翻訳システムの翻訳性能をさらに改善することができる。ラティスベースのMERTに対するシステムおよび技術は、空間効率およびランタイム効率も高く、このため、使用される記憶容量が低減され、例えば、必要記憶容量はラティスのサイズに(高々)比例するように制限され、翻訳性能の速度が向上する。
【００３０】
本明細書で説明されている主題の1つまたは複数の実施形態の詳細は、付属の図面および以下の説明で述べられる。主題の他の特徴、態様、および利点は、説明、図面、および請求項から明らかになるであろう。
【図面の簡単な説明】
【００３１】
【図１】入力テキストをソース言語からターゲット言語に翻訳するための例示的なプロセスを示す概念図である。
【図２Ａ】例示的な翻訳ラティスを示す図である。
【図２Ｂ】図2Aの翻訳ラティスに対する例示的なMBRオートマトンを示す図である。
【図３】例示的な翻訳ラティスの一部を示す図である。
【図４】MBRデコードの例示的なプロセスを示す図である。
【図５Ａ】ラティス上の誤り率最小化学習(MERT)の例示的なプロセスを示す図である。
【図５Ｂ】例示的な誤り率最小化学習器を示す図である。
【図６】汎用コンピュータデバイスおよび汎用モバイルコンピュータデバイスの一例を示す図である。
【発明を実施するための形態】
【００３２】
さまざまな図面内の類似の参照番号および指示記号は、類似の要素を指し示す。
【００３３】
統計的翻訳の概要
機械翻訳は、一方の言語の入力テキストを取り込んで、それを別の言語のテキストに正確に変換しようとするものである。一般に、翻訳の精度は、専門家が入力を翻訳する仕方と突き合わせて測定される。自動翻訳システムは、専門家によって実行される事前翻訳を分析して一方の言語から他方の言語への統計的翻訳モデルを形成することができる。しかし、単語の意味は文脈に依存することが多いため、このようなモデルは完全なものであるとはいえない。したがって、一方の言語から他方の言語への単語のステップ毎の逐語的変換では、許容可能な結果が得られないと思われる。例えば、「babe in the woods」(だまされやすい人)などのイディオムや、俗語は、文字通りの逐語的な変換ではうまく翻訳されない。
【００３４】
適切な言語モデルがあれば、自動翻訳プロセスに対しそのような文脈を与えやすくなると思われる。例えば、これらのモデルは、2つの単語が通常の使用法において、例えば、学習データ内で、互いに隣り合って出現する頻度、または1つの言語において複数の単語または要素(nグラム)の他のグループが出現する頻度に関する指示を与えることができる。nグラムは、n個の連続するトークン、例えば、単語もしくは文字のシーケンスである。nグラムは、nグラム内のトークンの個数である、次数またはサイズを有する。例えば、1グラム(またはユニグラム)は、1つのトークンを含み、2グラム(またバイグラム)は、2つのトークンを含む。
【００３５】
与えられたnグラムは、nグラムの異なる部分に応じて記述することができる。nグラムは、文脈および将来トークン(文脈、w)として記述することができ、文脈は長さn-1を有し、wは将来トークンを表す。例えば、c1、c2、およびc3がそれぞれ1文字を表すものとすると、3グラム「c1c2c3」はnグラムの文脈および将来トークンに関して記述することができる。nグラム左文脈は、nグラムの最後のトークンに先行するnグラムのすべてのトークンを含む。与えられた例において、「c1c2」は文脈である。文脈内の最左トークンは、左トークンと称される。将来トークンは、例では「c3」である、nグラムの最後のトークンである。nグラムは、右文脈に関して記述することもできる。右文脈は、(n-1)グラムとして表される、nグラムの第1のトークンの後に続くnグラムのすべてのトークンを含む。上記の例において、「c2c3」は右文脈である。
【００３６】
それぞれのnグラムは、学習データにおける生起数の、その学習データにおける全生起数に関する関数として計算される、関連する確率評価、例えば、対数確率を有することができる。いくつかの実施では、nグラムが入力テキストの翻訳である確率は、学習データ、例えば、ソース言語のテキストとターゲット言語の対応するテキストの集合を含む学習データ内のソース言語の対応するテキストの参照翻訳としてターゲット言語で表されるnグラムの相対度数を使用して学習される。
【００３７】
それに加えて、いくつかの実施では、大きな学習データ(例えば、数テラバイトのデータ)に対しては分散学習環境が使用される。分散学習の例示的な技術の1つは、MapReduceである。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日)において説明されている。
【００３８】
学習集合によって表される過去の使用法を用いて、一方の言語のサンプルがターゲット言語にどのように翻訳されるかを予測することができる。特に、nグラム、関連する確率評価、および各カウントした数を言語モデル内に格納し、これをデコーダ、例えば、ベイジアンデコーダで入力テキストに対する翻訳を識別するために使用することができる。入力テキストをターゲット言語の対応するテキストに翻訳できる尤度を示すスコアは、入力テキストに含まれるnグラムを特定の翻訳に対する関連する確率評価にマッピングすることによって計算されうる。
【００３９】
例示的な翻訳プロセス
図1は、入力テキストをソース言語からターゲット言語に翻訳するための例示的なプロセス100を示す概念図である。ソースサンプル102は、中国語テキストのパッセージとして示されており、第1のデコーダ104に供給される。デコーダ104は、さまざまな形態をとることができ、デコーダ104に対する学習段階においてデコーダ104に供給されたドキュメント106の学習集合が与えられたときに、パッセージに対する事後確率を最大化しようとして使用することができる。サンプル102を翻訳する際に、デコーダ104は、ドキュメント内からnグラムを選択し、そのnグラムの翻訳を試みることができる。デコーダ104は、可能な他のモデルのうち特に、並べ替えモデル、アライメントモデル、および言語モデルを備えることができる。これらのモデルは、翻訳のためサンプル102内からnグラムを選択する際にデコーダ104を導く。簡単な一例として、モデルは、区切り文字、例えば、カンマまたはピリオドなどの句読点を使用して、1つの単語を表すことができるnグラムの末尾を識別することができる。
【００４０】
デコーダ104は、さまざまな出力、例えば、可能な翻訳を含むデータ構造体を生成することができる。例えば、デコーダ104は、翻訳のN最良リストを生成することができる。いくつかの実施において、デコーダ104は、以下でさらに詳しく説明されるように、翻訳ラティス108を生成する。
【００４１】
次いで、第2のデコーダ110が、翻訳ラティス108を処理する。第1のデコーダ104は、一般的に、翻訳の事後確率を最大化すること、つまり、入力と、ドキュメント106の履歴コレクションが示しうる、他のパッセージの過去の専門家の人手による翻訳との最良一致となるものとのマッチングを目的としているが、第2のデコーダ110は、翻訳に対する品質尺度を最大化することを目的としている。したがって、第2のデコーダ110は、システム100のユーザーに対して表示することができる「最良の」翻訳を生成するように翻訳ラティス内に置かれる候補翻訳を再ランク付けすることができる。この翻訳は、中国語サンプル102の翻訳に対応する英語サンプル112によって表される。
【００４２】
第2のデコーダ110は、分類の予想される誤りを最小化する仮説(または候補翻訳)を探索する、MBRデコードと称されるプロセスを使用することができる。そこで、このプロセスは、翻訳選択を行うための決定基準に損失関数を直接組み込む。
【００４３】
ベイズリスク最小化デコード
ベイズリスク最小化(MBR)デコードでは、確率モデルの下で全く予想しない誤りを有する、翻訳仮説、例えば、候補翻訳を見つけることを目的とする。統計的機械翻訳は、ソース言語の入力テキストFからターゲット言語の翻訳済みテキストEへのマッピングであるものとして述べることができる。デコーダδ(F)、例えば、デコーダ104が、マッピングを実行することができる。参照翻訳Eが知られている場合、デコーダは、損失関数L(E,δ(F))によって測定されうる。自動翻訳E’と参照翻訳Eとの間のこのような損失関数L(E, E’)、および基礎的確率モデルP(E, F)が与えられた場合、MBRデコーダ、例えば、第2のデコーダ110は、
【００４４】
【数７】
0005572624.tif 000008
【００４５】
で表すことができ、式中、R(E)は損失関数Lの下での候補翻訳E’のベイズリスクを表し、Ψは翻訳の空間を表す。N最良MBRについては、空間Ψは、例えば、第1のデコーダ104によって生成されるN最良リストである。翻訳ラティスが使用される場合、Ψは、翻訳ラティス内にエンコードされた候補翻訳を表す。
【００４６】
2つの仮説間の損失関数が有界である、つまり、L(E, E’)≦Lmaxとすることができる場合、MBRデコーダは、利得関数G(E, E’)=Lmax - L(E, E’)に関して
【００４７】
【数８】
0005572624.tif 000009
【００４８】
のように書くことができる。
【００４９】
いくつかの実施において、MBRデコードでは、仮説選択およびリスク計算に異なる空間を使用する。例えば、仮説は、N最良リストから選択することができ、リスクは、翻訳ラティスに基づいて計算することができる。この例では、MBRデコーダは、
【００５０】
【数９】
0005572624.tif 000010
【００５１】
と書き換えることができ、式中、Ψは仮説空間を表し、Ψeはベイズリスクを計算するために使用される証拠空間を表す。
【００５２】
MBRデコードは、より大きな空間、つまり、仮説およびリスク計算空間を使用することによって改善することができる。ラティスは、N最良リストより多い候補翻訳を含むことができる。例えば、ラティスは、10億個を超える候補翻訳を含みうる。したがって、ラティスを使用して仮説およびリスク計算空間を表すことで、MBRデコードの精度が高まり、これにより、正確な翻訳がもたらされる尤度が高くなる。
【００５３】
例示的な翻訳ラティスおよびMBRデコード
図2Aは、例示的な翻訳ラティス200を示している。特に、翻訳ラティス200は、翻訳仮説の非常に大きなN最良リストおよびその尤度に対するコンパクトな表現であるとみなせる翻訳nグラムラティスである。特に、ラティスは、状態(例えば、状態0から6)と状態間の遷移を表す弧を含む非巡回重み付き有限状態受理器(acyclic weighted finite state acceptor)である。それぞれの弧は、nグラム(例えば、単語またはフレーズ)および重みに関連付けられている。例えば、翻訳ラティス200において、nグラムは、ラベル「a」、「b」、「c」、「d」、および「e」によって表される。状態0は、状態1への経路を構成する第1の弧、状態4から状態1への経路を構成する第2の弧、および状態5から状態4への経路を構成する第3の弧に接続される。第1の弧は、「a」および重み0.5を関連付けられ、第2の弧は、「b」および重み0.6を関連付けられ、第3の弧も、「d」および重み0.3を関連付けられる。
【００５４】
初期状態(例えば、状態0)から始まり、最終状態(例えば、状態6)で終わる連続する遷移を含む、翻訳ラティス200内のそれぞれの経路は、候補翻訳を表現する。1つの経路にそった重みの集合体は、モデルに従って経路の候補翻訳H(E,F)の重みを生成する。経路の候補翻訳の重みは、ソースセンテンスFが与えられたときの翻訳Eの事後確率を
【００５５】
【数１０】
0005572624.tif 000011
【００５６】
として表し、式中、α∈(0,∞)はα< 1のときに分布を平らにし、α>1のときに分布を急峻にするスケーリング係数である。
【００５７】
いくつかの実施において、利得関数Gは、局所利得関数giの総和として表される。利得関数は、重み付け有限状態変換器(WFST)合成を使用してラティス内のすべての経路に適用できる場合に局所利得関数とみなすことができ、その結果ラティス内の状態の数Nはo(N)で増大する。局所利得関数は、nグラムに重み付けすることができる。例えば、nグラムの集合N={w1,...,w|N|}が与えられたとき、w∈Nとする局所利得関数gw:ε×ε→Rは、
gw(E | E’)=θw・＃w(E’)・δw(E)
と表すことができ、式中、θwは定数であり、＃w(E’)はwがE’中に生起する回数であり、δw(E)はw∈Eであれば1、そうでなければ0である。総利得関数G(E, E’)を局所利得関数と定数θ0×仮説E’の長さとの総和として書くことができると仮定すると、総利得関数は
【００５８】
【数１１】
0005572624.tif 000012
【００５９】
として表すことができる。
【００６０】
この総利得関数を使用することで、リスク、つまり、
【００６１】
【数１２】
0005572624.tif 000013
【００６２】
は、(式1における)ラティスに対するMBRデコーダが
【００６３】
【数１３】
0005572624.tif 000014
【００６４】
で表され、式中、P(w|Ψ)はラティス中のnグラムwの事後確率、または
【００６５】
【数１４】
0005572624.tif 000015
【００６６】
である、ように書き換えることができ、そして、
【００６７】
【数１５】
0005572624.tif 000016
【００６８】
として表すことができ、式中、Ψw={E∈Ψ | δw(E)>0}はnグラムwを少なくとも1回含むラティスの経路を表し、Z(Ψw)およびZ(Ψ)はそれぞれラティスΨwおよびΨにおけるすべての経路の重みの総和を表す。
【００６９】
いくつかの実施において、MBRデコーダ(式2)は、WFSTを使用して実施される。ラティス内に含まれるnグラムの集合は、例えば、トポロジー順序でラティス内の弧をトラバースすることによって抽出される。ラティス内のそれぞれの状態は、nグラム接頭辞の対応する集合を有する。1つの状態を出るそれぞれの弧は、状態の接頭辞のそれぞれを単語1つ分だけ延長する。ラティス内の弧が後に続く状態において生起するnグラムは、この集合内に含まれる。初期化ステップとして、空の接頭辞を最初にそれぞれの状態の集合に加えることができる。
【００７０】
それぞれのnグラムwについて、nグラムを含む経路とマッチするオートマトン(例えば、他のラティス)が生成され、nグラムを含む経路の集合、つまり、Ψwを見つけるためにこのオートマトンとラティスとの共通部分がとられる。例えば、Ψが重み付けラティスを表す場合、Ψwは、
Ψw=Ψ∩(Σ*wΣ*)
のように表すことができる。
【００７１】
nグラムwの事後確率P(w|Ψ)は、Ψw内の経路の全重みと元のラティスΨ内の経路の全重みとの比として、式3において上で与えられているように計算することができる。
【００７２】
それぞれのnグラムwに対する事後確率は、上述のように計算され、次いで、それに式2に関して説明されているようにθw(nグラム係数)が乗算されうる。入力中にnグラムが生起する回数にθwを掛けた値に等しい重みを持つ入力を受理するオートマトンが生成される。オートマトンは、重み付け正規表現
【００７３】
【数１６】
0005572624.tif 000017
【００７４】
を使用して表すことができ、式中、
【００７５】
【数１７】
0005572624.tif 000018
【００７６】
はnグラムwを含まないすべての文字列を含む言語である。
【００７７】
それぞれの生成されるオートマトンと、それぞれラティスの非重み付けコピーとして始まる第2のオートマトンとの共通部分がとられる。これらの第2のオートマトンのそれぞれは、非重み付けラティスと(Σ/θ0)*を受理するオートマトンとの共通部分をとることによって生成される。その結果得られるオートマトンは、それぞれの経路の総予想利得を表す。単語列E’を表す、結果として得られるオートマトン内の経路は、費用
【００７８】
【数１８】
0005572624.tif 000019
【００７９】
を有する。
【００８０】
最小費用に関連付けられている経路、例えば、式2による経路を、結果として得られるオートマトンから抽出し、ラティスMBW候補翻訳を生成する。
【００８１】
仮説および証拠空間ラティスが異なる実施では、証拠空間ラティスは、nグラムを抽出し、関連する事後確率を計算するために使用される。MBRオートマトンは、仮説空間ラティスの非重み付けコピーから始めて構成される。nグラムオートマトンのそれぞれと仮説空間ラティスの非重み付けコピーとの共通部分を連続してとる。
【００８２】
BLEUスコアへの近似を使用して、総利得関数G(E,E’)の分解を局所利得関数の総和として計算する。BLEUスコアは、機械翻訳されたテキストの翻訳品質を示す指標である。Bleuの詳細については、K. Papineni、S. Roukes、T. Ward、およびW. Zhu. 2001. Bleu: a Method for Automatic Evaluation of Machine Translation. Technical Report RC22176 (WO109-022)、IBM Research Divisionを参照のこと。特に、システムは、コーパスにセンテンスを含めることからコーパスにそのセンテンスを含めないことまでコーパスBLEUスコアの変化に対する一次テイラー級数近似を計算する。
【００８３】
コーパスの参照長r(例えば、参照センテンスの長さ、または複数の参照センテンスの長さの総和)、候補長c0、および多数のnグラムマッチ{cn | 1≦n≦4}が与えられたときに、コーパスBLEUスコアB(r, c0, cn)は、
【００８４】
【数１９】
0005572624.tif 000020
【００８５】
で近似することができ、式中、Δnは候補の中の多数の単語の間の差であり、nグラムの個数、Δn=n-1は無視できるくらい小さいと仮定される。
【００８６】
コーパスlog(BLEU)利得は、新しいセンテンスの(E)統計がコーパス統計に含まれるときにlog(BLEU)の変化として定義され、
G=log B’-log B,
として表され、式中、B’におけるカウントは現在のセンテンスに対するカウントに加えられたBのカウントである。いくつかの実施において、c≧rであるとの仮定が使用され、cnのみが変数として取り扱われる。したがって、コーパスlog BLEU利得は、cnの初期値に関する一次ベクトルテイラー級数展開によって
【００８７】
【数２０】
0005572624.tif 000021
【００８８】
と近似することができ、式中の偏微分は
【００８９】
【数２１】
0005572624.tif 000022
【００９０】
および
【００９１】
【数２２】
0005572624.tif 000023
【００９２】
と表される。
【００９３】
したがって、コーパスlog(BLEU)利得は、
【００９４】
【数２３】
0005572624.tif 000024
【００９５】
と書き換えることができ、Δ項ではコーパス全体ではなく注目するセンテンスにおけるさまざまな統計量をカウントしている。これらの近似は、θ0およびθw(例えば、式2における)の値は、
【００９６】
【数２４】
0005572624.tif 000025
【００９７】
および
【００９８】
【数２５】
0005572624.tif 000026
【００９９】
と表すことができることを示唆している。
【０１００】
それぞれのnグラムの精度は、一定の比rに、対応する(n-1)グラムの精度を掛けた値であると仮定すると、BLEUスコアは、センテンスレベルで累計されうる。例えば、コーパス内の平均センテンス長が25語であると仮定した場合、
【０１０１】
【数２６】
0005572624.tif 000027
【０１０２】
となる。
【０１０３】
ユニグラム精度がpである場合、パラメータpおよびrおよびユニグラムトークンの数Tの関数としてのnグラム係数(n∈{1,2,3,4})は、
【０１０４】
【数２７】
0005572624.tif 000028
【０１０５】
および
【０１０６】
【数２８】
0005572624.tif 000029
【０１０７】
で表すことができる。
【０１０８】
いくつかの実施において、pおよびrは、複数の学習集合上のユニグラム精度の平均値および精度比に設定される。式2にnグラム係数を代入すると、MBRデコーダ、例えば、MBR決定規則は、Tに依存せず、Tの複数の値を使用することができるようになる。
【０１０９】
図2Bは、図2Aの翻訳ラティスに対する例示的なMBRオートマトンを示している。図2Aの翻訳ラティス200内の太い経路は、最大事後確率(MAP)仮説であり、図2BのMBRオートマトン250の太い経路は、MBR仮説である。図2Aおよび2Bに示されている例では、T=10、p=0.85、およびr=0.75である。MBR仮説(bcde)は、MAP仮説(abde)に関してより高いデコーダ費用を有することに留意されたい。しかし、bcdeは、abdeより高い予想利得を受け取るが、それは、第1のランク付けされた仮説(bcda)を持つさらに多くのnグラムを共有するからであり、これは、ラティスがMAP翻訳と異なるMBR翻訳を選択するのにどれだけ役立ちうるかを示している。
【０１１０】
誤り率最小化学習(MERT)の概要
誤り率最小化学習(MERT)では、分類に対する決定規則、例えば、0-1損失関数を使用するMBR決定規則の誤り計量を測定する。特に、MERTでは、0-1損失関数の下での決定が学習コーパス上のエンドツーエンドの性能測定を最大化するようにモデルパラメータを推定する。対数線形モデルと組み合わせることで、学習プロシージャが平滑化されていない誤り件数を最適化する。すでに述べたように、事後確率を最大化する翻訳は、
【０１１１】
【数２９】
0005572624.tif 000030
【０１１２】
に基づいて選択することができる。
【０１１３】
真の事後分布は不明なので、P(e | f)は、例えばm=1, ..., Mとして1つまたは複数の特徴関数hm(e,f)と特徴関数重みλmとを組み合わせた対数線形翻訳モデルで近似される。対数線形翻訳モデルは、
【０１１４】
【数３０】
0005572624.tif 000031
【０１１５】
として表すことができる。
【０１１６】
特徴関数重みは、モデルのパラメータであり、MERT基準により、学習センテンスの代表集合上の誤り件数を最小化するパラメータ集合
【０１１７】
【数３１】
0005572624.tif 000032
【０１１８】
を、決定規則、例えば
【０１１９】
【数３２】
0005572624.tif 000033
【０１２０】
を使用して見つける。学習コーパスのソースセンテンス
【０１２１】
【数３３】
0005572624.tif 000034
【０１２２】
、参照翻訳
【０１２３】
【数３４】
0005572624.tif 000035
【０１２４】
、およびK個の候補翻訳Cs={es,1,...es,K}が与えられたときに、翻訳
【０１２５】
【数３５】
0005572624.tif 000036
【０１２６】
に対するコーパスベースの誤り件数は、個別のセンテンスの誤り件数に加法的に分解可能であり、例えば
【０１２７】
【数３６】
0005572624.tif 000037
【０１２８】
である。MERT基準は、
【０１２９】
【数３７】
0005572624.tif 000038
【０１３０】
として表すことができ、式中、
【０１３１】
【数３８】
0005572624.tif 000039
【０１３２】
である。
【０１３３】
直線最適化技術を使用して、MERT基準の下で線形モデルを学習することができる。直線最適化技術は、それぞれの特徴関数hmおよびセンテンスfsについて、候補翻訳の集合Cs上の正確な誤り曲面を決定する。次いで、学習コーパス内のセンテンスの組み合わせ誤り曲面をトラバースし、結果として生じる誤りが最小になる点に重みを設定することによって、特徴関数重みを調節する。
【０１３４】
直線
【０１３５】
【数３９】
0005572624.tif 000040
【０１３６】
にそったCs内の最も確率の高いセンテンス仮説は、
【０１３７】
【数４０】
0005572624.tif 000041
【０１３８】
として定義されうる。
【０１３９】
候補翻訳に対する総スコアは、γを独立変数とする平面内の直線に対応する。全体として、CsはK本の直線を定義し、それぞれの直線は、他のK-1本の直線との可能な交差により高々K本の線分に分割されうる。
【０１４０】
それぞれのγについて、デコーダ(例えば、第2のデコーダ110)は、最高のスコアを生じる、したがって一番上の線分に対応する、各候補翻訳を決定する。一番上の線分の列は、Csで定義されるすべての直線上で点毎に最大となる上方包絡線を構成する。上方包絡線は、凸包であり、辺がγの区分線形関数の線分である凸多角形に内接しうる。いくつかの実施において、上方包絡線は、掃引線技術を使用して計算される。掃引線技術の詳細は、例えば、W. Macherey、F. Och、I. Thayer、およびJ. Uzskoreit、「Lattice-based Minimum Error Rate Training for Statistical Machine Translation」、Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing、725〜734頁、Honolulu、2008年10月において説明されている。
【０１４１】
ラティス上のMERT
ソースセンテンスfに対するラティス(例えば、フレーズラティス)は、頂点集合vf、一意的なソースおよびシンクノードs, t∈vf、および弧の集合
【０１４２】
【数４１】
0005572624.tif 000042
【０１４３】
を持つ連結有向非巡回グラフGf=(Vf,Ef)として定義される。それぞれの弧は、フレーズ
【０１４４】
【数４２】
0005572624.tif 000043
【０１４５】
およびこのフレーズの(局所)特徴関数値
【０１４６】
【数４３】
0005572624.tif 000044
【０１４７】
をラベル付けされる。Gf内の経路π=(v0,e0,v1,e1,...,en-1,vn)(0≦i<nに対しeiのテールおよびヘッドとしてei∈Efおよびvi,vi+1∈Vf)は、この経路にそったすべてのフレーズの連接である、部分翻訳e (fの)を定義する。関係する特徴関数値は、
【０１４８】
【数４４】
0005572624.tif 000045
【０１４９】
のように弧固有の特徴関数値の総和をとることで得られる。
【０１５０】
以下の説明では、enter(v)およびleave(v)という表記は、ノードv∈Vfに対する、それぞれ入弧と出弧の集合を指す。同様に、head(ε)およびtail(ε)は、それぞれ、弧εのヘッドとテールを表す。
【０１５１】
図3は、例示的な翻訳ラティス300の一部を示している。図3では、入弧302、304、および306は、ノードv 310に入る。それに加えて、出弧312および314は、ノードv 310を出る。
【０１５２】
ソースノードsから始まり、v(例えば、ノードv 310)で終わるそれぞれの経路は、直線で表すことができる部分翻訳仮説を定義する(式4を参照)。これらの部分翻訳仮説に対する上方包絡線が知られていると仮定し、またその包絡線を定義する直線がfi,...fNで表されていると仮定する。集合leave(v)の要素である出弧ε、例えば、弧312は、これらの部分候補翻訳の継続を表す。それぞれの出弧は、g(ε)で表される他の直線を定義する。g(ε)のパラメータを集合f1, ..., fN内のすべての直線に加えることで、f1+g(ε),...,fN+g(ε)によって定義される上方包絡線を生成する。
【０１５３】
g(ε)を加えても線分の数または包絡線内のその相対次数は変化しないので、凸包の構造は保存される。したがって、その結果得られる上方包絡線は、出弧ε上で後続ノードv’=head(ε)に伝搬することができる。v’に対する他の入弧は、異なる上方包絡線に関連付けることができる。上方包絡線は、単一の組み合わされた包絡線内に合併され、個々の包絡線を構成する直線集合上の和集合の凸包となる。それぞれの入弧v’に対する上方包絡線を組み合わせることによって、ソースノードsから始まり、v’で終わる経路に関連付けられているすべての部分候補翻訳に対する上方包絡線が生成される。
【０１５４】
他の実施も可能である。特に、MERT(ラティスに対する)の性能を改善するために、さらに精密化を施すことができる。例えば、直線最適化技術がよくない局所最適解で停止するのを防ぐために、MERTでは、パラメータ空間をサンプリングすることによってランダムに選択される追加の始点を探すことができる。他の例として、重み制約条件を定義することによって、一部または他の特徴関数重みの範囲を制限することができる。特に、特徴関数hmは、特徴関数重みλmを選択できる許容可能な領域を定義する区間
Rm=[lm,rm], lm,rm∈R∪{-∞,+∞}として指定することができる。重み制約条件の下で直線最適化が実行された場合、γは、
【０１５５】
【数４５】
0005572624.tif 000046
【０１５６】
となるように選択される。
【０１５７】
いくつかの実施において、重みプライアを使用できる。重みプライアは、新しい重みが、特定のターゲット値
【０１５８】
【数４６】
0005572624.tif 000047
【０１５９】
とマッチするように選択された場合に、目的関数上で小さな(正または負の)ブーストwを与える。
【０１６０】
【数４７】
0005572624.tif 000048
【０１６１】
0の重みプライア
【０１６２】
【数４８】
0005572624.tif 000049
【０１６３】
の場合、識別的でない特徴関数の重みは0に設定されるので、特徴選択を行うことができる。例えば、初期重みプライア
【０１６４】
【数４９】
0005572624.tif 000050
【０１６５】
を使用して、パラメータの変化を制限することができ、したがって、更新されたパラメータ集合は初期重み集合に関して差が少ない。
【０１６６】
いくつかの実施において、翻訳仮説の間隔
【０１６７】
【数５０】
0005572624.tif 000051
【０１６８】
は、0に等しい誤り件数の変化
【０１６９】
【数５１】
0005572624.tif 000052
【０１７０】
を有しており、左隣接翻訳仮説の間隔
【０１７１】
【数５２】
0005572624.tif 000053
【０１７２】
と合併される。その結果得られる間隔
【０１７３】
【数５３】
0005572624.tif 000054
【０１７４】
はより大きな範囲を有し、λの最適値の選択の信頼度は高められうる。
【０１７５】
いくつかの実施において、システムは、ランダム方向を使用して複数の特徴関数を同時に更新する。直線最適化で使用される方向が、M次元パラメータ空間の座標軸である場合、反復する毎に、単一の特徴関数の更新が結果として行われる。この更新技術では、その識別的な力に応じて特徴関数のランク付けを行い、例えば、反復毎に、対応する重みを変化させることで最高の利得が得られる特徴関数が選択されるが、この更新技術は特徴関数間の可能な相関に関わらない。その結果、最適化はよくない局所最適解で停止しうる。ランダム方向の使用により、複数の特徴関数を同時に更新することができる。ランダム方向の使用は、M次元超球の曲面上の1つまたは複数のランダム点を超球の中心(初期パラメータ集合によって定義される)と連結する直線を選択することによって実現されうる。
【０１７６】
図4は、MBRデコードの例示的なプロセス400を示している。便宜上、MBRデコードは、デコードを実行するシステムに関して説明される。システムは、仮説空間にアクセスする(410)。仮説空間は、例えば、ソース言語の対応する入力テキストのターゲット言語で複数の候補翻訳を表す。例えば、デコーダ(例えば、図1の第2のデコーダ110)が、翻訳ラティス(例えば、翻訳ラティス108)にアクセスすることができる。システムは、証拠空間に関して計算された分類の予想される誤りを最小化する翻訳仮説を得るために仮説空間上でデコードを実行する(420)。例えば、デコーダは、デコードを実行することができる。システムは、ターゲット翻訳において提案された翻訳としてユーザーが使用するための得られた翻訳仮説を提供する(430)。例えば、デコーダは、翻訳テキスト(例えば、英語サンプル112)を供給することができ、ユーザーはこれを使用することができる。
【０１７７】
図5Aは、ラティス上のMERTの例示的なプロセス500を示している。便宜上、MERTの実行は、学習を実行するシステムに関して説明される。システムは、翻訳ラティス内の複数の特徴関数について、翻訳ラティスで表される1つまたは複数の候補翻訳のそれぞれに対して対応する複数の誤り曲面を決定する(510)。例えば、図5Bの誤り率最小化学習器550の誤り曲面生成モジュール560は、対応する複数の誤り曲面を決定することができる。システムは、学習集合内のフレーズに対する複数の誤り曲面の組み合わせをトラバースすることによって特徴関数の重みを調節する(520)。例えば、誤り率最小化学習器550の更新モジュール570は、これらの重みを調節することができる。システムは、トラバースされた組み合わせに対する誤り件数を最小化する重み値を選択する(530)。例えば、誤り率最小化学習器550の誤り率最小化モジュール580は、重み値を選択することができる。システムは、テキストのサンプルを第1の言語から第2の言語に変換するために選択された重み値を適用する(540)。例えば、誤り率最小化学習器550は、選択された重み値をデコーダに適用することができる。
【０１７８】
図6は、説明されている技術(例えば、プロセス400および500)とともに使用されうる一般的なコンピュータデバイス600および一般的なモバイルコンピュータデバイス650の一例を示している。コンピューティングデバイス600は、ラップトップ、デスクトップ、ワークステーション、パーソナルデジタルアシスタント、サーバ、ブレードサーバ、メインフレーム、および他の適切なコンピュータなどのさまざまな形態のデジタルコンピュータを表すことが意図されている。コンピューティングデバイス650は、パーソナルデジタルアシスタント、携帯電話、スマートフォン、および他の類似のコンピューティングデバイスなどのさまざまな形態のモバイルデバイスを表すことが意図されている。ここに示されているコンポーネント、それらの接続および関係、ならびにそれらの機能は、例示することのみを意図されており、本明細書において説明され、および/または特許請求されているシステムおよび技術の実施を制限することを意図されていない。
【０１７９】
コンピューティングデバイス600は、プロセッサ602、メモリ604、記憶装置デバイス606、メモリ604および高速拡張ポート610に接続する高速インターフェイス608、ならびに低速バス614および記憶装置デバイス606に接続する低速インターフェイス612を備える。コンポーネント602、604、606、608、610、および612のそれぞれは、さまざまなバスを使用して相互接続され、共通マザーボード上に取り付けられるか、または適宜他の仕方で取り付けられうる。プロセッサ602は、高速インターフェイス608に結合されているディスプレイ616などの、外部入力/出力デバイス上にGUIのグラフィック情報を表示するためにメモリ604内に、または記憶装置デバイス606上に、格納されている命令を含む、コンピューティングデバイス600内で実行する命令を処理することができる。他の実施では、複数のプロセッサおよび/または複数のバスを、適宜、複数のメモリおよび複数のタイプのメモリとともに使用することができる。また、複数のコンピューティングデバイス600を、必要なオペレーションの一部を行うそれぞれのデバイスと接続することができる(例えば、サーババンク、ブレードサーバのグループ、またはマルチプロセッサシステムとして)。
【０１８０】
メモリ604は、コンピューティングデバイス600内に情報を格納する。一実施では、メモリ604は、1つまたは複数の揮発性メモリユニットである。他の実施では、メモリ604は、1つまたは複数の不揮発性メモリユニットである。メモリ604は、磁気ディスクまたは光ディスクなどのコンピュータ可読媒体の他の形態のものとすることもできる。
【０１８１】
記憶装置デバイス606は、コンピューティングデバイス600用の大容量記憶装置を構成することもできる。一実施では、記憶装置デバイス606は、ストレージエリアネットワークまたは他の構成のデバイスを含む、フロッピー（登録商標）ディスクデバイス、ハードディスクデバイス、光ディスクデバイス、またはテープデバイス、フラッシュメモリもしくは他の類似のソリッドステートメモリデバイス、またはデバイスアレイなどのコンピュータ可読媒体であるか、またはコンピュータ可読媒体を含むことができる。コンピュータプログラム製品は、情報担体で明確に具現化されうる。コンピュータプログラム製品は、実行されると上述のような1つまたは複数の方法を実行する命令も格納することができる。情報担体は、メモリ604、記憶装置デバイス606、またはプロセッサ602上のメモリなどのコンピュータもしくは機械可読媒体である。
【０１８２】
高速コントローラ608は、コンピューティングデバイス600に対する帯域幅を集中的に使用するオペレーションを管理するが、低速コントローラ612は、帯域幅を集中的に使用する程度の低いオペレーションを管理する。機能のこのような割り振りは例示的なものにすぎない。一実施では、高速コントローラ608は、メモリ604、ディスプレイ616(例えば、グラフィックスプロセッサまたはアクセラレータを通じて)、およびさまざまな拡張カード(図示せず)を受け入れることができる高速拡張ポート610に結合される。この実施では、低速コントローラ612は、記憶装置デバイス606および低速拡張ポート614に結合される。さまざまな通信ポート(例えば、USB、Bluetooth、Ethernet（登録商標）、無線Ethernet（登録商標）)を含みうる、低速拡張ポートは、キーボード、ポインティングデバイス、スキャナ、または例えば、ネットワークアダプタを通じて、スイッチまたはルーターなどネットワーキングデバイスなどの1つまたは複数の入力/出力デバイスに結合することができる。
【０１８３】
コンピューティングデバイス600は、図に示されているように、数多くの異なる形態で実施されうる。例えば、標準サーバ620として、またはそのようなサーバのグループで何倍もの数で実施されうる。これは、ラックサーバシステム624の一部としても実施することができる。それに加えて、ラップトップコンピュータ622などのパーソナルコンピューターで実施することもできる。あるいは、コンピューティングデバイス600からのコンポーネントをデバイス650などのモバイルデバイス(図示せず)内の他のコンポーネントと組み合わせることができる。このようなデバイスのそれぞれは、コンピューティングデバイス600、650のうちの1つまたは複数を含むことができ、システム全体が、互いに通信する複数のコンピューティングデバイス600、650で構成されうる。
【０１８４】
コンピューティングデバイス650は、数あるコンポーネントの中でもとりわけ、プロセッサ652、メモリ664、ディスプレイ654などの入力/出力デバイス、通信インターフェイス666、およびトランシーバ668を備える。デバイス650は、追加の記憶装置を構成するためにマイクロドライブまたは他のデバイスなどの記憶装置デバイスを備えることもできる。コンポーネント650、652、664、654、666、および668のそれぞれは、さまざまなバスを使用して相互接続され、これらのコンポーネントのうちのいくつかは、共通マザーボード上に取り付けられるか、または適宜他の仕方で取り付けられうる。
【０１８５】
プロセッサ652は、メモリ664内に格納されている命令を含む、コンピューティングデバイス650内の命令を実行することができる。プロセッサは、個別の、および複数の、アナログおよびデジタルプロセッサを備えるチップのチップセットとして実施することができる。プロセッサは、例えば、ユーザーインターフェイスの制御、デバイス650によるアプリケーション実行、デバイス650による無線通信などの、デバイス650の他のコンポーネントの調整を行うことができる。
【０１８６】
プロセッサ652は、制御インターフェイス658およびディスプレイ654に結合されているディスプレイインターフェイス656を通じてユーザーと通信することができる。ディスプレイ654は、例えば、TFT(薄膜トランジスタ液晶ディスプレイ)ディスプレイまたはOLED(有機発光ダイオード)ディスプレイまたは他の適切なディスプレイ技術とすることができる。ディスプレイインターフェイス656は、グラフィックおよび他の情報をユーザーに提示するようにディスプレイ654を駆動するための適切な回路を備えることができる。制御インターフェイス658は、ユーザーからコマンドを受け取り、それらをプロセッサ652に送るために変換することができる。それに加えて、外部インターフェイス662は、プロセッサ652と通信するように構成され、デバイス650と他のデバイスとの近距離通信を行うことを可能にする。外部インターフェイス662は、例えば、いくつかの実施における有線通信、または他の実施における無線通信を行うことができ、複数のインターフェイスも使用できる。
【０１８７】
メモリ664は、コンピューティングデバイス650内の情報を格納する。メモリ664は、1つもしくは複数のコンピュータ可読媒体、1つもしくは複数の揮発性メモリユニット、または1つもしくは複数の不揮発性メモリユニットのうちの1つまたは複数として実施することができる。拡張メモリ674も、例えば、SIMM(シングルインラインメモリモジュール)カードインターフェイスを含むものとしてよい、拡張インターフェイス672を通じて構成され、デバイス650に接続されうる。このような拡張メモリ674は、デバイス650に対する付加的な記憶領域を設けることができるか、またはデバイス650用のアプリケーションまたは他の情報を格納することもできる。特に、拡張メモリ674は、上述のプロセスを実行するか、または補助する命令を格納することができ、またセキュア情報も格納することができる。したがって、例えば、拡張メモリ674は、デバイス650に対するセキュリティモジュールとして構成することができ、デバイス650の安全な使用を可能にする命令でプログラムすることができる。それに加えて、安全なアプリケーションは、SIMMカードを介して、ハッキングできない形でSIMMカード上に識別情報を配置するなど、付加情報とともに提供することもできる。
【０１８８】
メモリとしては、例えば、後述のように、フラッシュメモリおよび/またはNVRAMが挙げられる。一実施では、コンピュータプログラム製品は、情報担体で明確に具現化される。コンピュータプログラム製品は、実行されると上述のような1つまたは複数の方法を実行する命令を格納する。情報担体は、メモリ664、拡張メモリ674、プロセッサ652上のメモリ、または例えば、トランシーバ668もしくは外部インターフェイス662上で受信されうる伝搬信号などのコンピュータもしくは機械可読媒体である。
【０１８９】
デバイス650は、必要ならば、デジタル信号処理回路を備えることができる、通信インターフェイス666を通じて無線で通信することができる。通信インターフェイス666は、とりわけ、GSM音声電話、SMS、EMS、またはMMSメッセージング、CDMA、TDMA、PDC、WCDMA、CDMA2000、またはGPRSなどの、さまざまなモードもしくはプロトコルの下で通信を行うことができる。このような通信は、例えば、無線周波トランシーバ668を通じて行うことができる。それに加えて、Bluetooth、WiFi、または他のトランシーバ(図示せず)などを使用して、短距離通信を実行することができる。それに加えて、GPS(全地球測位システム)受信機モジュール670は、追加のナビゲーションおよび位置関係無線データをデバイス650に送ることができ、これはデバイス650上で実行するアプリケーションによって適宜使用されうる。
【０１９０】
デバイス650は、オーディオコーデック660を使用して音声で通信することもでき、ユーザーから話された情報を受け取り、それを使用可能なデジタル情報に変換することができる。オーディオコーデック660は、例えば、デバイス650のハンドセットのスピーカーなどを通じて、ユーザー向けに可聴音を発生することができる。このような音声は、音声電話からの音声を含み、記録された音声を含み(例えば、音声メッセージ、音楽ファイルなど)、またデバイス650上で動作するアプリケーションによって生成される音声を含むこともできる。
【０１９１】
コンピューティングデバイス650は、図に示されているように、数多くの異なる形態で実施されうる。例えば、携帯電話680として実施することができる。また、スマートフォン682、パーソナルデジタルアシスタント、または他の類似のモバイルデバイスの一部として実施することもできる。
【０１９２】
本明細書で説明されているシステムおよび技術のさまざまな実施は、デジタル電子回路、集積回路、専用設計ASIC(特定用途向け集積回路)、コンピュータのハードウェア、ファームウェア、ソフトウェア、および/またはこれらの組み合わせで実現することが可能である。これらのさまざまな実施は、記憶装置システム、少なくとも1つの入力デバイス、および少なくとも1つの出力デバイスからデータおよび命令を受け取り、記憶装置システム、少なくとも1つの入力デバイス、および少なくとも1つの出力デバイスにデータおよび命令を送るように結合された、専用または汎用のものとしてよい、少なくとも1つのプログラム可能なプロセッサを備えるプログラム可能なシステム上で実行可能であり、および/または解釈可能である1つまたは複数のコンピュータプログラムによる実施を含むことができる。
【０１９３】
これらのコンピュータプログラム(プログラム、ソフトウェア、ソフトウェアアプリケーション、またはコードとも呼ばれる)は、プログラム可能なプロセッサ用の機械語命令を含み、高水準手続き型および/またはオブジェクト指向プログラミング言語で、および/またはアセンブリ/機械語で実施されうる。本明細書で使用されているように、「機械可読媒体」、「コンピュータ可読媒体」という用語は、機械可読信号として機械語命令を受け取る機械可読媒体を含む、機械語命令および/またはデータをプログラム可能なプロセッサに供給するために使用されるコンピュータプログラム製品、装置、および/またはデバイス(例えば、磁気ディスク、光ディスク、メモリ、プログラム可能論理デバイス(PLD))を指す。「機械可読信号」という用語は、機械語命令および/またはデータをプログラム可能なプロセッサに供給するために使用される信号を指す。
【０１９４】
ユーザーと情報のやり取りを行うために、本明細書で説明されているシステムおよび技術は、ユーザーに情報を表示するための表示デバイス(例えば、CRT(陰極線管)またはLCD(液晶ディスプレイ)モニタ)およびキーボードおよびユーザーがコンピュータに入力を送るために使用できるポインティングデバイス(例えば、マウスもしくはトラックボール)を有するコンピュータ上で実施することができる。他の種類のデバイスも、ユーザーと情報をやり取りするために使用することができ、例えば、ユーザーに返されるフィードバックは、任意の形態の感覚フィードバック(例えば、視覚フィードバック、聴覚フィードバック、または触覚フィードバック)とすることができ、ユーザーからの入力は、音響、話し声、または触覚入力を含む、任意の形態で受け取ることができる。
【０１９５】
本明細書で説明されているシステムおよび技術は、バックエンドコンポーネントを含む(例えば、データサーバとして)、またはミドルウェアコンポーネントを含む(例えば、アプリケーションサーバとして)、またはフロントエンドコンポーネントを含む(例えば、ユーザーと本明細書で説明されているシステムおよび技術の実施との情報のやり取りに使用されるグラフィカルユーザーインターフェイスまたはウェブブラウザを有するクライアントコンピュータ)コンピューティングシステム、またはそのようなバックエンド、ミドルウェア、またはフロントエンドコンポーネントの任意の組み合わせで実施することができる。システムのコンポーネントは、デジタルデータ通信の任意の形態または媒体(例えば、通信ネットワーク)によって相互接続することができる。通信ネットワークの例としては、ローカルエリアネットワーク(「LAN」)、ワイドエリアネットワーク(「WAN」)、およびインターネットが挙げられる。
【０１９６】
コンピューティングシステムは、クライアントおよびサーバを備えることができる。クライアントおよびサーバは、一般に、互いに隔てられており、典型的には、通信ネットワークを通じて情報のやり取りを行う。クライアントとサーバとの関係は、コンピュータプログラムが各コンピュータ上で実行され、互いとの間にクライアント-サーバ関係を有することによって発生する。
【０１９７】
本明細書は、多くの実施形態固有の詳細事項を含んでいるが、これらは、任意の実施の範囲または請求内容の範囲に対する制限として解釈すべきではなく、むしろ特定の実施の特定の実施形態に特有のものであると思われる特徴の説明として解釈すべきである。別々の実施形態の背景状況において本明細書で説明されているいくつかの特徴も、単一の実施形態において組み合わせて実施されうる。逆に、単一の実施形態の背景状況において説明されているさまざまな特徴は、複数の実施形態で別々に、または好適な部分的組み合わせで、実施することも可能である。さらに、上ではいくつかの特徴を特定の組み合わせで動作するものとして説明することができ、さらには最初にそのようなものとして請求されうるが、請求されている組み合わせから得られる一つまたは複数の特徴は、場合によっては、組み合わせから切り取られ、また請求された組み合わせは、部分的組み合わせまたは部分的組み合わせの変更形態を対象とするものとすることもできる。
【０１９８】
同様に、オペレーションは図面内に特定の順序で示されているが、これは、そのようなオペレーションが図示されている特定の順序で、または順番に実行されること、または例示されているオペレーションが、望ましい結果が得られるように実行されることを要求していると理解されるべきではない。いくつかの状況では、マルチタスクおよび並列処理が有利な場合もある。さらに、上述の実施形態においてさまざまなシステムコンポーネントが分離しているが、すべての実施形態においてそのような分離が必要とされていると理解されるべきではなく、また説明されているプログラムコンポーネントおよびシステムは、一般的に、単一のソフトウェア製品に一体化されうるか、または複数のソフトウェア製品にパッケージングされうることは理解されるであろう。
【０１９９】
本明細書で説明されている主題の特定の実施形態が説明された。他の実施形態も、以下の請求項の範囲内に収まる。例えば、請求項に記載のアクションは、異なる順序で実行することができ、それでも、所望の結果が得られる。一例として、付属の図面に示されているプロセスは、所望の結果を得るために、図示されている特定の順序、または順番を必ずしも必要としない。いくつかの実施において、マルチタスクおよび並列処理が有利な場合もある。
【符号の説明】
【０２００】
0-6  状態
100  プロセス
102  ソースサンプル
104  第1のデコーダ
106  ドキュメント
108  翻訳ラティス
110  第2のデコーダ
112  英語サンプル
200  翻訳ラティス
250  MBRオートマトン
300  翻訳ラティス
302，304，306  入弧
310  ノードv
312，314  出弧
550  誤り率最小化学習器
560  誤り曲面生成モジュール
570  更新モジュール
580  誤り率最小化モジュール
600  コンピュータデバイス
602  プロセッサ
604  メモリ
606  記憶装置デバイス
608  高速インターフェイス
610  高速拡張ポート
612  低速インターフェイス
614  低速バス、低速拡張ポート
616  ディスプレイ
620  標準サーバ
622  ラップトップコンピュータ
624  ラックサーバシステム
650  一般的なモバイルコンピュータデバイス
652  プロセッサ
654  ディスプレイ
656  ディスプレイインターフェイス
658  制御インターフェイス
660  オーディオコーデック
662  外部インターフェイス
664  メモリ
666  通信インターフェイス
668  トランシーバ
672  拡張インターフェイス
674  拡張メモリ
680  携帯電話
682  スマートフォン
【図１】
0005572624.tif 000067
【図２Ａ−２Ｂ】
0005572624.tif 000068
【図３】
0005572624.tif 000069
【図４】
0005572624.tif 000070
【図５Ａ】
0005572624.tif 000071
【図５Ｂ】
0005572624.tif 000072
【図６】
0005572624.tif 000073