(57)【要約】      （修正有）【課題】ソース言語文字列に対する最適な訳語候補を生成するフレーズベース統計翻訳モデルを提供する。【解決手段】棄却サンプリングは、フレーズベースの統計翻訳モデルｐ（ｘ）＝ｐ（ｔ，ａ｜ｓ）によるソース言語文字列ｓに対して少なくとも１つのターゲット言語の訳語を取得するよう実行され、ｔは、訳語候補であり、ａは、訳語候補ｔを生成するバイフレーズシーケンスを備える候補配列であり、ｘは、候補配列ａを表すシーケンスである。棄却サンプリングは、サンプルｘ＊の棄却に応じて提案ｑ（ｎ）（ｘ）を修正し、修正提案ｑ（ｎ＋１）を生成する。修正提案ｑ（ｎ＋１）は、基準として、全ｘ∈Ｘに対してｐ（ｘ）≦ｑ（ｎ＋１）（ｘ）≦ｑ（ｎ）（ｘ）およびｑ（ｎ＋１）（ｘ＊）＜ｑ（ｎ）（ｘ＊）を満たすよう選択され、ここで、空間Ｘは、ソース言語文字列ｓに対する訳語候補ｔを生成する候補配列ａに対応するシーケンスｘのセットである。【選択図】図１
2014146312.tif 000002
【特許請求の範囲】
【請求項１】
棄却サンプリングを実行して、フレーズベース統計翻訳モデルｐ（ｘ）＝ｐ（ｔ，ａ｜ｓ）によってソース言語文字列ｓに対する少なくとも１つの受け入れたターゲット言語の訳語を取得するための電子データ処理デバイスによって実行可能な命令を格納する非一時記憶媒体であって、
ｔは、訳語候補であり、ａは、前記訳語候補ｔを生成するソース言語−ターゲット言語バイフレーズシーケンスを備える候補配列であり、ｘは、前記候補配列ａを表すシーケンスであって、前記棄却サンプリングは、前記棄却サンプリングの現在の繰返しで取得したサンプルｘ＊の棄却に応じて修正された重み付き有限状態オートマトン（ＷＦＳＡ）ｑ（ｎ）を備える提案分布を使用して、前記棄却サンプリングの次の繰返しで使用する修正済みＷＦＳＡｑ（ｎ＋１）を生成し、前記修正済みＷＦＳＡｑ（ｎ＋１）は、基準
全ｘ∈Ｘに対してｐ（ｘ）≦ｑ（ｎ＋１）（ｘ）≦ｑ（ｎ）（ｘ）、および
ｑ（ｎ＋１）（ｘ＊）＜ｑ（ｎ）（ｘ＊）、
を満たすよう選択され、
ここで、空間Ｘは、訳語候補ｔをソース言語文字列ｓに対して生成する候補配列ａに対応するシーケンスｘのセットである、非一時記憶媒体。
【請求項２】
前記サンプルｘ＊は、前記サンプルｘ＊によって表される前記配列ａが前記ソース言語文字列ｓの各ワードを正確に１回だけ消費することを要求する非重複制約を満たさない場合に棄却され、
前記非重複制約が満たされない場合に実行される前記修正は、（ｉ）前記非重複制約に違反する前記サンプルｘ＊のサブシーケンスａｋ．．．ａｋ＋ｌを識別すること、および（ｉｉ）ＷＦＳＡｑ（ｎ＋１）がサブシーケンスａｋ．．．ａｋ＋ｌを含むいかなるシーケンスｘも受け入れないように、ＷＦＳＡｑ（ｎ）をＷＦＳＡｑ（ｎ＋１）に修正すること、を備える、請求項１に記載の非一時記憶媒体。
【請求項３】
前記シーケンスｘは、トリプルのシーケンスとしての前記配列ａを表し、前記トリプルのそれぞれは、前記訳語ｔの１ワードを正確に意味するフィールドＥと、Ｅを生成する前記バイフレーズを意味するフィールドＢと、Ｅを生成する前記バイフレーズまで、ならびにＥを生成する前記バイフレーズを含む前記配列ａの前記バイフレーズによって消費される前記ソース言語文字列ｓのワード数を意味するフィールドＮとを含む、請求項１に記載の非一時記憶媒体。
【請求項４】
前記棄却サンプリングは、前記空間Ｘの無作為サンプリングによって前記サンプルｘ＊を取得し、
前記棄却サンプリングは、比ｐ（ｘ＊）／ｑ（ｘ＊）と無作為抽出との比較に基づいてｘ＊を受け入れるか、または棄却し、
前記修正済み提案分布ｑ（ｎ＋１）は、基準
全ｘ∈Ｘに対してｐ（ｘ）≦ｑ（ｎ＋１）（ｘ）≦ｑ（ｎ）（ｘ）、
ｑ（ｎ＋１）（ｘ＊）＜ｑ（ｎ）（ｘ＊）、および
ノルム
【数１】
2014146312.tif 000053
がα＜∞の場合に最小となる、
を満たすよう選択される、請求項１に記載の非一時記憶媒体。
【請求項５】
α＝１である、請求項４に記載の非一時記憶媒体。
【請求項６】
前記棄却サンプリングは、ｑ＊＝ｑ（ｎ）（ｘ＊）が前記空間Ｘにわたってｑ（ｎ）を最大にするように前記サンプルｘ＊を取得し、
前記棄却サンプリングは、ｑ＊とｐ（ｘ＊）との間の差、もしくはそれらの比に基づいてｘ＊を受け入れるか、もしくは棄却し、
前記修正済み提案分布ｑ（ｎ＋１）は、基準
全ｘ∈Ｘに対してｐ（ｘ）≦ｑ（ｎ＋１）（ｘ）≦ｑ（ｎ）（ｘ）、
ｑ（ｎ＋１）（ｘ＊）＜ｑ（ｎ）（ｘ＊）、および
ノルム
【数２】
2014146312.tif 000054
が最小となる、
を満たすよう選択される、請求項１に記載の非一時記憶媒体。
【請求項７】
前記非一時記憶媒体は、前記棄却サンプリングの複数の繰返しにわたって受け入れたサンプルｘ＊のセットを収集することによって前記フレーズベース統計翻訳モデルｐ（ｔ，ａ｜ｓ）のサンプリングを実行するために電子データ処理デバイスによって実行可能な命令を格納し、各繰返しは、前記空間Ｘの無作為サンプリングによって前記サンプルｘ＊を取得して、比ｐ（ｘ＊）／ｑ（ｘ＊）と無作為抽出との比較に基づいてｘ＊を受け入れるか、もしくは棄却する、請求項１に記載の非一時記憶媒体。
【請求項８】
フレーズベースの統計翻訳モデルｐ（ｘ）＝ｐ（ｔ，ａ｜ｓ）によるソース言語文字列ｓに対して少なくとも１つのターゲット言語の訳語を生成する方法であって、ｔは、訳語候補であり、ａは、前記訳語候補ｔを生成するソース言語−ターゲット言語バイフレーズシーケンスを備える候補配列であり、ｘは、前記候補配列ａを表すシーケンスであって、前記方法は、
サンプルｘ＊を生成することによって、さらにｑが、重み付き有限状態オートマトンを備える提案分布であり、前記少なくとも１つのターゲット言語の訳語が、受け入れたサンプルｘ＊に対応する、ｐ（ｘ＊）とｑ（ｘ＊）との比較に基づいて前記サンプルｘ＊を受け入れるか、もしくは棄却することによって、ｐ（ｘ）の繰返し棄却サンプリングを実行することと、
前記繰返し棄却サンプリングの間、前記配列ａが、前記ソース言語文字列ｓの各ワードを正確に１回だけ消費することを要求する非重複制約に違反するサブシーケンスａｋ．．．ａｋ＋ｌを含むサンプルｘ＊を識別することと、
前記サブシーケンスａｋ．．．ａｋ＋ｌを含むいかなるシーケンスｘも受け入れないようｑを修正することとを備え、前記修正済みｑは、前記繰返し棄却サンプリングの次の繰返しで使用され、
前記識別および修正動作を含む前記繰返し棄却サンプリングは、電子データ処理デバイスによって実行される、方法。
【請求項９】
電子データ処理デバイスと、
方法を実行するために前記電子データ処理デバイスによって実行可能な命令を格納する非一時記憶媒体とを備え、前記方法は、
フレーズベース統計翻訳モデルｐ（ｘ）＝ｐ（ｔ，ａ｜ｓ）の棄却サンプリングを実行することと、ここで、ｔが訳語候補であり、ａが前記訳語候補ｔを生成するソース言語−ターゲット言語バイフレーズシーケンスを備える候補配列であり、ｘが、トリプルのシーケンスとして前記候補配列ａを表し、前記トリプルのそれぞれは、前記訳語ｔの１ワードを正確に意味するフィールドＥと、Ｅを生成する前記バイフレーズを意味するフィールドＢと、Ｅを生成する前記バイフレーズまで、およびＥを生成する前記バイフレーズを含む前記配列ａの前記バイフレーズによって消費される前記ソース言語文字列ｓのワード数を意味するフィールドＮとを含み、
前記棄却サンプリングの間、前記ソース言語文字列ｓ中のワード数が異なる前記サンプルｘ＊における最終トリプルに対するＮの前記値に基づいて、前記配列ａが前記ソース言語文字列ｓの各ワードを正確に一回だけ消費することを要求する非重複制約に違反するサブシーケンスａｋ．．．ａｋ＋ｌを含むようなサンプルｘ＊を識別することとを備える、装置。
【請求項１０】
前記方法は、前記非重複制約に違反するサブシーケンスａｋ．．．ａｋ＋ｌを含むサンプルｘ＊を識別することに応じて、
前記棄却サンプリングで使用される提案分布を修正して、前記提案分布が、前記サブシーケンスａｋ．．．ａｋ＋ｌを含むシーケンスｘをもはや含まないようにすることをさらに含む、請求項９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
以下は、機械翻訳技術、統計機械翻訳（ＳＭＴ）技術、および関連技術に関する。
【背景技術】
【０００２】
フレーズベース統計機械翻訳（ＳＭＴ）システムは、比較的短いソース言語−ターゲット言語バイフレーズのデータベースを使用する。ＳＭＴシステムは、ソース言語テキストのワードまたはフレーズを含むバイフレーズを識別し、バイフレーズの選択および配置を最適化することによって、ソース言語テキストを翻訳し、翻訳ターゲット言語テキストを生成する。最適化は、通常、特性と呼ばれる、さまざまな品質メトリクスに対応する。一般的に、これらの特性は、個々のバイフレーズに対して算出されるローカル特性、およびバイフレーズの配置を特徴づける配列特性を含む。ローカル特性の一例には、ソース言語−ターゲット言語文書のトレーニングコーパス内にバイフレーズがどれだけ含まれるかを示す頻度メトリクスがある。通常は、トレーニングコーパス内の頻度が高くなるほど、バイフレーズがＳＭＴ翻訳に対する正しい選択である可能性が高まる。この確率は、２つの条件付き確率として定式化することができ、その条件付き確率は、ソース言語テキストにおけるターゲット言語テキストの頻度、およびその逆である。
【０００３】
ターゲット言語における翻訳の言語品質を特徴づける特性は、典型的には、ターゲット言語モデル（ターゲットＬＭ）、例えば、トレーニングコーパスのターゲット言語部分全体にわたって推定されるｎグラムモデルを使用して定式化される。一例として、ｎ＝３の場合、ｎグラムモデルは、コーパス内の対応するターゲット言語シーケンスの発生頻度に基づいて、３つのバイフレーズのシーケンスに対する確率をもたらす。典型的に使用される他の特性は歪み特性であり、バイフレーズが、ソース言語テキスト内のソース言語フレーズの順序に従って指定される場合に得られるであろうものから、ターゲット言語の訳語が逸脱することについてのメトリクスである。（一般的に、歪み特性は、対応するソース言語ワードの順序から大きく逸脱するターゲット言語ワードの順序を有するターゲット言語の訳語を不利にする。）
【０００４】
翻訳を行う場合、適用される可能性がある他の制約は、ソースワード消費制約である。典型的に、この制約は、翻訳されるテキストの各ソース言語ワードが、ターゲット言語テキストを生成する場合に、正確に使用される（すなわち、消費される）ことを保証するために設計される。この制約は、（一般に）ソース言語ワードとターゲット言語ワードとの間に１対１の対応が無い場合は、適用することは困難である。例えば、フランス語から英語への翻訳の際、バイフレーズ“ｃｕｒｉｅｕｓｅ−ｑｕｉｔｅ  ｂｉｚａｒｒｅ”では、１つのソース言語ワード（“ｃｕｒｉｅｕｓｅ”）は２つのターゲット言語ワード（“ｑｕｉｔｅ  ｂｉｚａｒｒｅ”）に等しい。逆の状況、例えば、英語からフランス語への翻訳を行う際に、同じバイフレーズを、２つのソース言語ワード（“ｑｕｉｔｅ  ｂｉｚａｒｒｅ”）から単一のターゲット言語ワード（“ｃｕｒｉｅｕｓｅ”）に翻訳することも起こり得る。
【０００５】
フレーズベースのＳＭＴに対する一般的な公式は、以下の形式の対数線形モデルを使用する。
【０００６】
【数１】
2014146312.tif 000003
ここで、ｈｋは特性、すなわち、ソース文字列ｓ、ターゲット文字列ｔ、および配列ａの関数であり、配列ａは、ｔをｓから構築するために使用されたバイフレーズのシーケンスを現したものである。シーケンスの順序は、ターゲット側を参照して定義され、すなわち、ターゲット側のｂが、ターゲット言語文字列ｔにおけるターゲット側ｂ’に優先される場合にのみ、バイフレーズｂが、配列において、バイフレーズｂ’に優先される。λｋは、重みであり、Ｚｓは、ｐ（ｔ，ａ｜ｓ）が、ペア（ｔ，ａ）にわたって適切な条件付き確率分布であることを保証する正規化因子である。
【０００７】
ローカル特性は、バイフレーズにローカルである（または、他の言い方をすれば、バイフレーズのみに基づいて算出することができる）特性である。適切なローカル特性の中には、順方向および逆方向条件付き確率特性
【数２】
2014146312.tif 000004
および
【数３】
2014146312.tif 000005
を含むものがあり、そこでは、
【数４】
2014146312.tif 000006
は、バイフレーズのソース側であり、
【数５】
2014146312.tif 000007
はターゲット側である。バイフレーズに対するこれらの特性の値は、大規模バイリンガルトレーニングコーパス内のバイフレーズに対する統計に基づいて、適切に推定される。他にあり得るローカル特性は、いわゆる「フレーズペナルティ」特性であり、配列内の各バイフレーズに対して１に等しい。同様に、
【数６】
2014146312.tif 000008
内のワード数を数える「ワードペナルティ」特性が使用される可能性がある。
【０００８】
グローバル特性は、バイフレーズが配列内に表れる順序に依存し、単独のバイフレーズに基づいて算出することはできない。そのような特性の１つは、典型的に、大規模ターゲット言語コーパス全体にわたって推定されるｎグラム言語モデルによりターゲット文字列ｔが訳語候補と関連する確率を算出する言語モデル特性ｌｏｇｐ（ｔ）である。他にあり得るグローバル特性は、どれだけの訳語候補のバイフレーズのシーケンスが「単調な」順序から逸脱しているかを測定する歪み特性であり、「単調な」順序とは、すなわち、バイフレーズのターゲット側がそのソース側と同じ順序で配置された場合に決められるであろう順序である。
【０００９】
対数線形モデルｐ（ｔ，ａ｜ｓ）の特定の導入に関する設計には、バイフレーズデータベースを設けること、特性ｈｋのセットを選択すること、およびバイリンガルコーパスにおけるモデルをトレーニングして、重みλｋならびにＺｓを最適化することが含まれる。次いで、デコーダは、トレーニングされたモデルを使用して、ペア（ｔ，ａ）によって定義される、入力ソース文字列ｓに対する条件付き確率ｐ（ｔ，ａ｜ｓ）を最大にするターゲット言語の訳語を見つけ、対応するターゲット言語の訳語を出力する。本方法を使用するフレーズベースＳＭＴの一例には、Ｍｏｓｅｓ統計機械翻訳システム（ｈｔｔｐ：／／ｗｗｗ．ｓｔａｔｍｔ．ｏｒｇ／ｍｏｓｅｓ／で利用可能であり、最終アクセスは２０１２年１２月２１日）がある。
【００１０】
典型的に、既存のデコーダは、発見的前向き検索の何らかの変形物を使用し、すなわち、新しいバイフレーズを伴い各ステップで現在の部分的な訳語を、左から右へ延長して増分的に訳語候補（ｔ，ａ）を構築しようとし、２つのスコア、すなわち、これまでの部分的な訳語の既知の部分に対するスコアと、訳語を完成するために残っているコストの発見的評価とを算出する。そのような手法の１つは、ビーム検索の形式を使用し、ビーム検索では、いくつかの部分的な候補が並列に保存され、ｐ（ｔ，ａ｜ｓ）のように現在推定される可能性が非常に低い候補は切り捨てられ、より有望である候補が選ばれる。
【００１１】
これらの既存のデコーダには、ある種の欠点がある。例えば、検索ツリーが検索中に切り捨てられ、組合せ表現を見逃すため、検索の最後で見つかる解は、典型的に、最適以下である。たとえ実際にその解が最適解だとしても、そうだと判断する方法はない。部分最適性の問題は、高順序ターゲット言語モデル（ＬＭ）において増加し、それは、そのような高順序モデルが、ビーム検索中の状態を「マージする」ことをより困難にするからであり、そのため、メモリに保存する必要のある状態空間がより大規模になる。前向き処理もまた、ローカル文脈に左右されるデコーダによってなされる判断を引き起こし、全訳語候補から算出されたグローバル特性の使用を制限または妨げる。
【発明の概要】
【課題を解決するための手段】
【００１２】
本明細書で単に例示として開示されるいくつかの例示的な実施形態において、非一時記憶媒体は電子データ処理デバイスによって実行可能な命令を格納して、フレーズベースの統計翻訳モデルｐ（ｘ）＝ｐ（ｔ，ａ｜ｓ）によるソース言語文字列ｓに対して少なくとも１つの受け入れたターゲット言語の訳語を取得するために棄却サンプリングを実行し、ここで、ｔは訳語候補であり、ａは訳語候補ｔを生成するソース言語−ターゲット言語バイフレーズシーケンスを備える候補配列であり、ｘは、候補配列ａを表すシーケンスである。棄却サンプリングは、棄却サンプリングの現在の繰返しで取得したサンプルｘ＊の棄却に応じて修正された重み付き有限状態オートマトン（ＷＦＳＡ）ｑ（ｎ）を備える提案分布を使用して、棄却サンプリングの次の繰返しで使用するために、修正済みＷＦＳＡｑ（ｎ＋１）を生成する。修正済みＷＦＳＡｑ（ｎ＋１）は、基準として全ｘ∈Ｘに対してｐ（ｘ）≦ｑ（ｎ＋１）（ｘ）≦ｑ（ｎ）（ｘ）およびｑ（ｎ＋１）（ｘ＊）＜ｑ（ｎ）（ｘ＊）を満たすよう選択され、ここで、空間Ｘは、ソース言語文字列ｓに対する候補訳語ｔを生成する候補配列ａに対応するシーケンスｘのセットである。
【００１３】
本明細書で単に例示として開示されるいくつかの例示的な実施形態において、フレーズベースの統計翻訳モデルｐ（ｘ）＝ｐ（ｔ，ａ｜ｓ）によるソース言語文字列ｓに対して少なくとも１つのターゲット言語の訳語を生成する方法を開示し、ここで、ｔは訳語候補であり、ａは訳語候補ｔを生成するソース言語−ターゲット言語バイフレーズシーケンスを備える候補配列であり、ｘは、候補配列ａを表すシーケンスである。本方法は、サンプルｘ＊を生成して、ｐ（ｘ＊）とｑ（ｘ＊）との比較に基づいてサンプルｘ＊を受け入れる、もしくは棄却することによってｐ（ｘ）の繰返し棄却サンプリングを実行することを備え、ここで、ｑは、重み付き有限状態オートマトンを備える提案分布であり、少なくとも１つのターゲット言語の訳語は、受け入れたサンプルｘ＊に対応し、さらに本方法は、繰返し棄却サンプリングの間、配列ａがソース言語文字列ｓの各ワードを正確に１回だけ消費することを要求する非重複制約に違反するサブシーケンスａｋ．．．ａｋ＋ｌを含むサンプルｘ＊を識別すること、およびサブシーケンスａｋ．．．ａｋ＋ｌを含むいかなるシーケンスｘも受け入れないようｑを修正することとを備え、修正済みｑは、繰返し棄却サンプリングの次の繰返しで使用される。識別および修正動作を含む繰返し棄却サンプリングは、電子データ処理デバイスによって、適切に実行される。
【００１４】
本明細書で単に例示として開示されるいくつかの例示的な実施形態において、装置は、電子データ処理デバイスおよび非一時記憶媒体を備え、非一時記憶媒体は、フレーズベース統計翻訳モデルｐ（ｘ）＝ｐ（ｔ，ａ｜ｓ）の棄却サンプリングを実行することを含む方法を実行する、電子データ処理デバイスによって実行可能な命令を格納し、ここで、ｔは訳語候補であり、ａは訳語候補ｔを生成するソース言語−ターゲット言語バイフレーズシーケンスを備える候補配列であり、ｘはトリプルのシーケンスとして候補配列ａを表す。各トリプルは、訳語ｔの１ワードを正確に意味するフィールドＥと、Ｅを生成するバイフレーズを意味するフィールドＢと、Ｅを生成するバイフレーズまで、ならびにＥを生成するバイフレーズを含む配列ａのバイフレーズによって消費されるソース言語文字列ｓのワード数を意味するフィールドＮとを含む。本方法は、さらに、棄却サンプリングの間、ソース言語文字列ｓ中のワード数が異なるサンプルｘ＊における最終トリプルに対するＮの値に基づいて、配列ａがソース言語文字列ｓの各ワードを正確に一回だけ消費することを要求する非重複制約に違反するサブシーケンスａｋ．．．ａｋ＋ｌを含むようなサンプルｘ＊を識別することを備える。
【図面の簡単な説明】
【００１５】
【図１】図１は、動作モードにしたがって、サンプリングまたは最適化を実行するための例示的システムの図である。
【図２】図２は、図１のシステムの動作モードによって制御される設定を示す図である。
【図３】図３は、サンプリングモードで動作する、本明細書に開示するＯＳ＊アルゴリズムの動作を示す図である。
【図４】図４は、最適化モードで動作する、本明細書に開示するＯＳ＊アルゴリズムの動作を示す図である。
【図５】図５は、最適化モードで動作する、本明細書に開示するＯＳ＊アルゴリズムの動作を示す図である。
【図６】図６は、ＯＳ＊アルゴリズムを使用して、入力ソース言語文字列に対するフレーズベース統計機械翻訳（ＰＢ−ＳＭＴ）モデルをサンプリングまたは最適化するＰＢ−ＳＭＴシステムにおいて、提案分布として使用される重み付き有限状態オートマトン（ＷＦＳＡ）の用例の一部である。
【図７】図７は、ＯＳ＊アルゴリズムを使用して、入力ソース言語文字列に対するフレーズベース統計機械翻訳（ＰＢ−ＳＭＴ）モデルをサンプリングまたは最適化するＰＢ−ＳＭＴシステムにおいて、提案分布として使用される重み付き有限状態オートマトン（ＷＦＳＡ）の用例の一部である。
【図８】図８は、図１のＯＳ＊アルゴリズムを使用するＰＢ−ＳＭＴシステムを示す図である。
【発明を実施するための形態】
【００１６】
本明細書では、フレーズベース統計機械翻訳（ＰＢ−ＳＭＴ）方法および装置の改良を開示する。本方法は、サンプリングまたは最適化を行うための結合アルゴリズムである、本明細書でＯＳ＊アルゴリズムと称する技術を用いる。本明細書で開示するような統計機械翻訳を実行するために、ＯＳ＊アルゴリズムが、所与の入力ソース言語文字列ｓに対し、トレーニング済みＰＢ−ＳＭＴモデルｐ（ｘ）＝ｐ（ｔ，ａ｜ｓ）からサンプルに適用される。（本用例において、ＰＢ−ＳＭＴモデルｐ（ｔ，ａ｜ｓ）は、背景技術で述べたように対数線形形式を有するが、確率ｐ（ｔ，ａ｜ｓ）を生成するための他の形式の他のＰＢ−ＳＭＴモデルも考えられる。）所与のソース言語センテンスｓを翻訳するために、構成ｘは、ターゲット言語の訳語ｔをソース言語文字列ｓから構築するバイフレーズのシーケンスを明示する配列ａに適切に対応する。ＰＢ−ＳＭＴ問題に適用するようなＯＳ＊アルゴリズムは、ソース言語文字列ｓに対する訳語候補ｔを生成するようにＰＢ−ＳＭＴモデルｐ（ｔ，ａ｜ｓ）によって指定されたバイフレーズシーケンス、すなわち、配列ａに対応する全構成ｘに対してｑ（ｘ）≧ｐ（ｘ）であるような重み付き有限状態オートマトンｑの形式で提案分布を生成することを必要とする。サンプルｘ＊は、例えば、無作為に、またはｑ（ｘ）を最大にするようにｘ＊を選択することによって、オートマトンｑから導かれ、そのサンプルは、比ｐ（ｘ＊）／ｑ（ｘ＊）に基づいて受け入れられるか、または棄却される。サンプルｘ＊が棄却されると、提案分布、すなわちオートマトンｑ（ｘ）が、サンプルｘ＊の棄却から収集された情報に基づき修正され、全ｘに対して条件ｑ（ｘ）≧ｐ（ｘ）がまだ確実に満たされている間に、ｑ（ｘ）をｐ（ｘ）に近づける。典型的に、このことは、ｘ＊で、および（より効果的に収束するために）好ましくはｘ＊付近でｑ（ｘ）を減少させることを必要とする。本処理を繰り返すことによって、提案分布ｑ（ｘ）は次第にｐ（ｘ）に近づき、結果的に、比ｐ（ｘ＊）／ｑ（ｘ＊）に基づく所与のサンプルｘ＊を受け入れる統計的確率が増加する。サンプリング中、受け入れ率が閾値を超えると、処理は適切に終了し、一方、最適化中、
【数７】
2014146312.tif 000009
である場合、適切に終了し、ここで、εは許容閾値である。
【００１７】
開示するＳＭＴデコーディング方法は、発見的前向き検索で使用する既存のデコーダ全体に、多くの利点を有する。ＯＳ＊ベースのデコーダは、基本的モデルｐ（ｔ，ａ｜ｓ）に対して正確な（すなわち、真である）最適な訳語を生成することができ、生成した解が実際に最適な解であることを検証することが可能である。さらに、ＯＳ＊ベースのデコーダは、訳語全体を統合的に表すオートマトンｑ全体にわたってサンプリングを実行するので、当然、グローバル特性を含むモデルｐ（ｔ，ａ｜ｓ）の全特性ｈｋを使用する。またさらに、ＯＳ＊ベースのＳＭＴデコーダは、通常の意味（すなわち、基本的モデルに関する最も高いスコアの訳語候補を発見する最適化問題）でのデコーディングを実行するよう構成することができるが、このモデルから正確なサンプリングもまた（すなわち、代替として）実行することができる。ＳＭＴサンプリングへのこのような特質の追加に対する用途は、訳語候補の基本的条件付き分布についてのいくつかのモードを検出および利用する機能から、生成された訳語のサンプルへのベイズリスク最小化（ＭＢＲ）デコーディングの用途まで、多岐にわたる。この後者の技術は、単一モード辺りの“ｎｂｅｓｔ”リストにＭＢＲを適用するために、論理的に好ましい。ＳＭＴサンプリングのさらなる用途には、ＧｉｂｂｓまたはＭｅｔｒｏｐｏｌｉｓ−Ｈａｓｔｉｎｇｓなどのマルコフ連鎖モンテカルロ法（ＭＣＭＣ）サンプリング技術に近似するためのリソース無しに、ベイズ確率モデルを学習することを含む。
【００１８】
ＯＳ＊アルゴリズムを、一般的に（すなわち、フレーズベース統計機械翻訳の用途に具体的に関係することなく）、まず説明する。
【００１９】
図１を参照して、本明細書でＯＳ＊アルゴリズム１０と称する、サンプリングまたは最適化を行うための結合アルゴリズムについて説明する。ＯＳ＊アルゴリズム１０は、プロセッサ（例えば、任意選択的にマルチコアであるマイクロプロセッサ）とデータストレージとを備えて、さらに命令を実行してＯＳ＊アルゴリズム１０を実行するコンピュータまたは他の電子データ処理デバイス１２によって適切に実現される。コンピュータまたは他の電子データ処理デバイス１２によって実行されて、ＯＳ＊アルゴリズムを実行する命令は、ハードディスクや他の磁気記憶媒体、ランダムアクセスメモリ（ＲＡＭ）、読出し専用メモリ（ＲＯＭ）、または他の電子的記憶媒体、光学ディスクや他の光学記憶媒体、およびそれらの組合せなどの非一時記憶媒体（図示しない）に適切に格納される。
【００２０】
図１および図２を参照すると、ＯＳ＊アルゴリズムは、関数または分布１４をサンプリングまたは最適化するよう動作し、一次元空間または多次元空間とすることが可能な空間Ｘにわたって定義される関数または分布ｐとして本明細書では記載される。ＯＳ＊アルゴリズム１０がサンプリングまたは最適化のいずれを実行するかは、サンプリング（ｓ）または最適化（ｏ）のいずれかに設定することができる動作モード１６によって制御される。図２は、サンプリングモードと最適化モードとの違いを示す。
【００２１】
ＯＳ＊アルゴリズム１０は、棄却サンプリングを実行する。最初に、初期提案分布２０が選択される。初期提案分布は、ｑ（０）（ｘ）を意味し、サンプルｘ∈Ｘに対して定義される。動作２２において、サンプルｘ＊が取得される。サンプリングモードの場合、サンプルｘ＊は、無作為サンプリングによって取得される。最適化モードの場合、サンプルｘ＊が、（第１の繰返しに対して）ｑ（０）（ｘ）を最大にするよう選択され、より一般的には、（繰返し（ｎ）に対して）ｑ（ｎ）（ｘ）を最大にするよう選択される。動作２４において、サンプルｘ＊は、受け入れられるか、または棄却される。受け入れ基準の選択は、ＯＳ＊アルゴリズム１０が、サンプリングモードと最適化モードのどちらで動作しているかに左右される。サンプリングモードの場合、適切な選択基準は、無作為抽出を伴う比ｐ（ｘ＊）／ｑ（ｘ＊）の比較に基づく。（ここで、略記ｑ＝ｑ（ｎ）は、棄却サンプリングの現在の繰返しに対する提案分布を意味する。）例えば、無作為抽出は、０と１との間の均一な値を有し、
【数８】
2014146312.tif 000010
である、正規化された均一確率分布Ｕ［０，１］からの無作為抽出とすることができる。最適化モードの場合、適切な選択基準は、ｑ＊とｐ（ｘ＊）との差、またはｑ＊とｐ（ｘ＊）との比に基づき、ここで、略記ｑ＊＝ｑ（ｘ＊）は、空間Ｘにおけるｑの最大値を意味する。
【００２２】
動作２６において、サンプルｘ＊が（動作２４で）受け入れられると、サンプルｘ＊を含むように履歴が更新される。サンプリングモードにおいて、このことは、サンプルｘ＊を、受け入れたサンプルのセットに加えることを必要とする。最適化モードにおいて、１つのサンプルのみが最終的に受け入れられ、つまり、第１のサンプルは、ｑ＊とｐ（ｘ＊）との間の差またはｑ＊とｐ（ｘ＊）との比が最大閾値εを満たす、すなわち、（ｑ＊−ｐ（ｘ＊））＜εとなるよう生成される。（本明細書でさらに説明するように、最大閾値εは、ｐの最適化値に対するエラーメトリクスを定義する。）
【００２３】
他方で、動作３０において、サンプルｘ＊が（動作２４で）棄却された場合、提案分布ｑ（ｎ）は修正され、棄却サンプリングの次の繰返しで使用するための、修正済み提案分布ｑ（ｎ＋１）を生成する。修正済み提案分布ｑ（ｎ＋１）が、以下の基準を満たすように選択される。その基準は、すなわち、ｐ（ｘ）≦ｑ（ｎ＋１）（ｘ）≦ｑ（ｎ）（ｘ）（ここで、第１の不等式は、ｑ（ｎ＋１）がｐ（ｘ）における上限であることを保証し、第２の不等式は、修正済み提案分布ｑ（ｎ＋１）が、空間Ｘにおけるあらゆる点に対するｑ（ｎ）ほど悪くないことを保証する）、ｑ（ｎ＋１）（ｘ＊）＜ｑ（ｎ）（ｘ＊）（修正済み提案分布ｑ（ｎ＋１）が棄却されたサンプルｘ＊でのｑ（ｎ）よりも優れていることを保証する）、およびノルム
【数９】
2014146312.tif 000011
が最小となることである。この第３の基準におけるαの値は、動作モードに左右される。サンプリングに対して、α＜∞、より好ましくはα＝１である。この場合、Ｌ１ノルム
【数１０】
2014146312.tif 000012
を最小にするようｑ（ｎ＋１）を選択することで、選択したｑ（ｎ＋１）が、修正済み提案分布ｑ（ｎ＋１）全体をできる限り低くすることを保証する。サンプリングに対し、等値
【数１１】
2014146312.tif 000013
を利用して、α＝∞である。したがって、
【数１２】
2014146312.tif 000014
を最小にすることは、選択したｑ（ｎ＋１）が、修正済み提案分布ｑ（ｎ＋１）の最大値をできる限り低くすることを保証する。
【００２４】
動作２２、２４、および動作２６（受け入れ）もしくは動作３０（棄却）は、棄却サンプリングの１つの繰返しを形成する。判断３２は、停止基準が満たされたかどうかを判断する。サンプリングの場合、複数の受け入れたサンプルが、（正規化形式、すなわち、
【数１３】
2014146312.tif 000015
で）分布ｐ（ｘ）に従って判断され、最適な停止基準は、棄却サンプリングの次第に増加する受け入れ率が、閾値を超える場合である。最適化の場合、分布ｐ（ｘ）に対する単一の最大値が判断され、それにより、適切な停止基準は、第１のサンプルｘ＊が受け入れられる場合である。停止基準が満たされない場合、処理は動作２２に戻り、修正済み提案分布ｑ（ｎ＋１）などを使用して処理される次のサンプルｘ＊を取得する。停止基準が判断３２で満たされると、結果が、動作３４で出力される。サンプリングの場合、出力は、受け入れたサンプルのセットを適切に含む。サンプリング結果は、提案分布ｑの最後の修正を、任意選択的に、追加的に、または代替的に含み、ターゲット分布ｐ（ｘ）からさらに正確なサンプルを生成するために、後に使用することができる。最適化の場合、出力は、分布ｐ（ｘ）の最大値に対応する（単一の）受け入れたサンプルである。ｐ（ｘ）の真の最大値は、下限ｐ（ｘ＊）と上限ｑ＊とを有することが知られているため、最大値は、ｑ＊＝ｑ（ｘ＊）として、またはｐ（ｘ＊）として、または何らかの中間値、例えば、（ｑ＊＋ｐ（ｘ＊））／２として、良好に近似することができる。任意選択的に、最適化の場合における動作３４もまた、受け入れたサンプル分布ｘ＊に対する値ｐ（ｘ＊）およびｑ＊＝ｑ（ｘ＊）に基づいて算出されたエラーメトリクスを出力する。例えば、最適化出力は、（ｑ＊＋ｐ（ｘ＊））／２±（ｑ＊−ｐ（ｘ＊））／２とすることができ、または、上限と下限がそれほど離れていない場合、（ｑ＊＋ｐ（ｘ＊））／２±ε／２とすることができ、後者は、（ｑ＊−ｐ（ｘ＊））＜εが、最適化に対する受け入れ／停止基準である場合に従う。
【００２５】
図２は、サンプリングモードと最適化モードとの違いについて要約する。これらの違いは、（無作為サンプリングによる、または、最適化の場合、ｘ＊＝ａｒｇｍａｘｘ｛ｑ（ｘ）｝を識別することによる）動作２２でのサンプルｘ＊の取得方法、サンプルｘ＊を受け入れるための受け入れ基準、提案分布の修正で使用されるノルム、履歴（サンプリングの場合、受け入れたサンプルのセットを保持し、最適化の場合、第１の受け入れたサンプルのみを保持する）、および、停止基準（サンプリングに対して次第に増加する受け入れ率に適切に基づく、または、最適化の場合に、第１のサンプルが受け入れられた後に停止する）、を含む。有利には、同じＯＳ＊アルゴリズム１０は、選択した動作モード１６に従って、サンプリングまたは最適化のいずれかを実行することができる。
【００２６】
ＯＳ＊アルゴリズムに対して何らかの概念的基礎を含むさらなる開示を以下に記載する。
【００２７】
μが空間Ｘについてのベースメジャーであり、ｐが（Ｘ，μ）についてのＬ１非負関数、すなわち、
【数１４】
2014146312.tif 000016
であると仮定し、
【数１５】
2014146312.tif 000017
を定義する。次いで、関数ｐは、Ｘにわたる非正規化密度として考えることができ、
【数１６】
2014146312.tif 000018
は、本明細書ではターゲット分布と呼び、サンプリング（言葉の誤用により、
【数１７】
2014146312.tif 000019
からのサンプルが、ｐからのサンプルであるとも言える）をしたいと考える分布である、Ｘにわたる確率分布を定義する正規化密度と考えることができる。ターゲット分布から直接サンプリングを行うことが可能であるかもしれないし、不可能であるかもしれないが、いかなる所与のｘに対してもｐ（ｘ）を計算することが可能であると仮定する。次いで、棄却サンプリング（ＲＳ）が、次の通りに機能する。ある種の非正規化提案密度ｑは、Ｘにわたって定義され、（ｉ）そこから（より正確には、
【数１８】
2014146312.tif 000020
から）直接サンプリングする方法は既知である、（ｉｉ）全ｘ∈Ｘに対してｐ（ｘ）≦ｑ（ｘ）である。この後者の条件によると、ｑ（ｘ）がｐ（ｘ）についての上限である。次いで、以下の繰返し処理が実行される。（１）サンプルｘがｑから導かれる、（２）比
【数１９】
2014146312.tif 000021
が算出される、（３）サンプルｘが確率ｒ（ｘ）を用いて受け入れられるか、そうでなければ、サンプルｘは棄却される、（４）ステップ（１）から（３）を反復的に繰り返す。次いで、この手順では、ｐから正確なサンプルを生成することを示すことができる。受け入れられるサンプルをＲＳが生成する平均率、すなわち、受け入れ率は、Ｐ（Ｘ）／Ｑ（Ｘ）に等しく、ここで、Ｘの（測定可能な）サブセットＡに対し、パラメータ
【数２０】
2014146312.tif 000022
が定義される（Ｑも同様である）。言い換えると、受け入れ率は、ｐ曲線の下側の面と、ｑ曲線の下側の面との比に等しい。
【００２８】
受け入れ率を最大にするために、ｑ曲線は、ｐの上側にあることを保ちながら、実用可能な限り低くするべきである。この観点から、適応的棄却サンプリング（ＡＲＳ）技術が開発されてきた。Ｇｉｌｋｓらによる「Ａｄａｐｔｉｖｅ  ｒｅｊｅｃｔｉｏｎ  ｓａｍｐｌｉｎｇ  ｆｏｒ  Ｇｉｂｂｓ  ｓａｍｐｌｉｎｇ」Ａｐｐｌｉｅｄ  Ｓｔａｔｉｓｔｉｃｓ  ｐａｇｅｓ  ３３７−３４８  （１９９２）、Ｇｏｅｒｕｅｒらによる「Ｃｏｎｃａｖｅ  ｃｏｎｖｅｘ  ａｄａｐｔｉｖｅ  ｒｅｊｅｃｔｉｏｎ  ｓａｍｐｌｉｎｇ」Ｔｅｃｈｉｃａｌ  Ｒｅｐｏｒｔ、Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｎｅｕｒｏｓｃｉｅｎｃｅ  Ｕｎｉｔ、２００８を参照。ＡＲＳでは、処理のある段階において、ｑ曲線は、より良好な受け入れ率を用いて、より低い曲線ｑ’に更新される。これらの技術は、Ｘが一次元実数直線であり、ｐが凹型、対数的凹型、または区分的対数的凹型である場合に主に適用されており、そのような場合、凸型性を利用して、区分的線形エンベロープから成る上限によって、ｐを次第に良好に近似することが可能である。
【００２９】
図１を参照して説明したＯＳ＊アルゴリズムにおいて、適応的棄却サンプリングは、修正提案分布ｑが選択され、基準ｐ（ｘ）≦ｑ（ｎ＋１）（ｘ）≦ｑ（ｎ）（ｘ）ならびにｑ（ｎ＋１）（ｘ＊）＜ｑ（ｎ）（ｘ＊）、およびノルム
【数２１】
2014146312.tif 000023
の最小化を満たす場合に適用される。さらに、ＯＳ＊アルゴリズムが、本明細書で開示するような適切な構成でサンプリングまたは最適化を行うために使用することができることを開示する（例えば、図２を参照）。便宜上、ＯＳ＊は、サンプリングモードではＯＳ＊ｓと称して適用され、一方、ＯＳ＊は、最適化モードではＯＳ＊ｏと称して適用される。一般的なＯＳ＊アルゴリズムは、サンプリングモードと最適化モードとのいずれでも使用することができるが、ある実装のＯＳ＊アルゴリズムは、サンプリングのみを実行するよう構成することができ（例えば、図２に示すサンプリングモード設定をハードコーディングすることによって）、または、ある実装のＯＳ＊アルゴリズムは、最適化のみを実行するよう構成することができる（例えば、図２に示す最適化モード設定をハードコーディングすることによって）ことに留意されたい。
【００３０】
図３を参照して、サンプリングモードにおけるＯＳ＊アルゴリズムの動作（すなわち、ＯＳ＊ｓ動作）を説明する。サンプリングは、初期の提案密度ｑを用いて開始する。第１のサンプルは、サンプルｘ１であり、比ｒｑ（ｘ１）＝ｐ（ｘ１）／ｑ（ｘ１）は１に近づき、これは、サンプルｘ１の受け取りに繋がる。次の繰返しがサンプルｘ２を生成し、比ｒｑ（ｘ２）＝ｐ（ｘ２）／ｑ（ｘ２）は、１よりかなり低くなり、棄却に繋がる。それにもかかわらず、棄却は、何らかの有益な情報を生じ、すなわち、ｐ（ｘ２）はｑ（ｘ２）よりかなり低く、エビデンスは、新しい提案分布ｑ’を定義するために使用され、新しい提案分布ｑ’は、以下の特性、すなわち、Ｘについて至る所でｐ（ｘ）≦ｑ’（ｘ）≦ｑ（ｘ）であり、サンプルｘ２でｑ’（ｘ２）＜ｑ（ｘ２）であることを有する。そのようなｑ’を取得する極端な方法の１つは、ｘ２以外の至る所で、ｑ’（ｘ２）＝ｐ（ｘ２）を設定して、ｑ’（ｘ）＝ｑ（ｘ）を維持することである。空間Ｘが離散的である場合、ｑ’のこの選択は、受け取り率を向上する効果を有するが、そのようなことはわずかであるが、いかなる時点でもｑ’がｘ２を選択することを保証することによって、それを受け入れる。空間Ｘが連続的である場合、ｑ’のこの選択は、ほぼ至る所でｑ’＝ｑであるため、本質的に全く向上しない。
【００３１】
ｑ’を発見するためのより良い一般的な方法は以下である。有限セットの「１ステップ修正動作」ａｊが利用可能であると仮定し、ａｊは、ｑとｘ２とに左右され、ｑから新しいｑｊ’＝ａｊ（ｑ，ｘ２）に移動することができ、そのようなａｊのいずれに対しても、Ｘについて至る所でｐ（ｘ）≦ｑｊ，（ｘ）≦ｑ（ｘ）となり、さらにｑｊ，（ｘ２）＜ｑ（ｘ２）となる。その場合、これらの利用可能な修正動作の中から、「最高の」修正ａｊが選択される。サンプリングに対して、この「最高の」修正は、適切なものであり、ｑｊ’のＬ１ノルムが、起こり得るｊ’ｓの中で最小であり、言い換えると、
【数２２】
2014146312.tif 000024
がｊ中で最小である。この選択では、ｑ’ｊの受け入れ率
【数２３】
2014146312.tif 000025
は、可能な限り改善され、（ｉ）修正のためにあまりに大きい空間を利用する必要がない（セット｛ａｊ｝が適度に小さいと仮定する）、（ｉｉ）ｑに対する表現から、ｑに対して起こり得る修正のためにより大きな空間を利用することになるｑ’に対するさらにより複雑な表現よりも、ｑ’ｊに対するさらにもう少しだけ複雑な表現に移動する。
【００３２】
そうでなければ、図３のＯＳ＊ｓ動作において、ｘ２の棄却の後、提案分布ｑは、ｑ’（ｘ２）が厳密にｑ（ｘ２）未満であるように、ｑ’に修正される。これは、ｘ２で「狭傾斜」をとることによって行うことができ、ｑ’（ｘ２）＝ｐ（ｘ２）であり、至る所でｑ’をｑに等しくするが、図３に示すように、ｐとｑの間の面を減らすという点で、狭傾斜を減らすことはより効果的である。その場合、修正ｑ’は、ｑの１ステップ修正を可能にする小リスト間で表面減少を最大にするよう選択される。
【００３３】
図４および図５を参照して、最適化モードにおけるＯＳ＊アルゴリズムの動作（すなわち、ＯＳ＊ｏ動作）を説明する。図４は、最適化される（すなわち、本例で最大化される）関数ｐを示す。図４に（不明の）最大値ｐｍａｘをｐ曲線上に黒丸によって示し、最大値ｐｍａｘは、Ｘにおけるｘｍａｘに対応する。図４はまた、提案関数ｑを示し、サンプリングの場合と同様に、以下の基準を満たす。（１）関数ｑは、空間Ｘのすべてについてｐより高い、（２）ｑが、ｑ曲線上で黒丸で示す、その最大値ｑｍａｘに達するＸにおける点ｘ１を直接発見することができる。
【００３４】
以下が観測される。ｑ（ｘ１）とｐ（ｘ１）との間の距離が、εより小さいと仮定する。その場合、ｑ（ｘ１）とｐｍａｘとの間の距離もまた、εより小さいことになる。このことは、図４でグラフで見ることができ、さらに、このことは、一方でｐｍａｘがｐ（ｘ１）より高く（すなわち、最大で、正確にｘ１＝ｘｍａｘである場合にｐ（ｘ１）＝ｐｍａｘ）、他方でｐｍａｘがｑ（ｘｍａｘ）より下であり、ｑ（ｘ１）よりさらに下であるということのためである。言い換えると、提案関数ｑに対する最大値ｑｍａｘが座標ｘ１であり、ｑ（ｘ１）−ｐ（ｘ１）＜εである場合、ｐの最大値がエラーメトリクスεまでに発見されると結論づけることができる。
【００３５】
図４におけるｘ１の場合、差ｑ（ｘ１）−ｐ（ｘ１）は、比較的大きく、そのため、サンプルｘ１は、動作２４（図１参照）で棄却され、提案分布ｑは、サンプリングの場合と同じ方法を使用してｑ’に修正され（図１の動作３０）、しかし、ただ１つ、選択された１ステップ修正オプションａｊがここで選択され、最大値に等しい、すなわち
【数２４】
2014146312.tif 000026
である、Ｌ∞ノルムを最小にすることが異なる。言い換えると、サンプリングの場合におけるｑのＬ１ノルムの最小化は、Ｌ∞ノルムの最小化に置き換えられる。図５を参照すると、このｑ’がひとたび選択された場合、ｘ２での最大値を発見でき、次に、本処理は、ｑ（ｋ）（ｘｋ）とｐ（ｘｋ）との間の差がある定義された閾値、例えば、エラーメトリクスεよりも小さくなるまでｑ（１）＝ｑ，ｑ（２）＝ｑ’，．．．を繰り返すことが可能である。
【００３６】
最適化（ＯＳ＊ｏ）動作を要約するために、ｘｍａｘが、ｐの最大値ｐｍａｘのＸ内の場所であり、ｘ１が、ｑの最大値ｑｍａｘのＸ内の場所である場合、（不明の）距離｜ｑ（ｘ１）−ｐｍａｘ｜は、既知の量である「ギャップ」｜ｑ（ｘ１）−ｐ（ｘ１）｜以下であるとする。（これも不明である）距離｜ｐｍａｘ−ｐ（ｘ１）｜が、既知のギャップ｜ｑ（ｘ１）−ｐ（ｘ１）｜以下であると言うこともできる。そのため、ｐの最大値は、エラーメトリクス｜ｑ（ｘ１）−ｐ（ｘ１）｜でのｑｍａｘであると言うことができる。あるいは、ｐの最大値は、エラーメトリクス｜ｑ（ｘ１）−ｐ（ｘ１）｜を用いてｐ（ｘ１）であると言うことができる。差を分割することによって、ｐの最大値が（ｑｍａｘ＋ｐ（ｘ１））／２±｜ｑ（ｘ１）−ｐ（ｘ１）｜／２であると言うこともできる。エラーが受け入れられないほど大きい場合、サンプルｘ１は棄却され、修正提案ｑ’が生成され、その最大値ｘ２が計算される。ギャップ｜ｑ（ｘ２）−ｐ（ｘ２）｜が十分小さい場合、点ｘ２が受け入れられ、そうでなければ、処理は繰返し継続する。
【００３７】
サンプリングおよび最適化は、通常、２つの異なる別個のタスクと考えられるが、本明細書で開示するように、それらは、Ｌｐ空間の文脈で考える場合、連続的な範囲の２つの端であると考えることができる。概して、（Ｘ，μ）が測定空間である場合、およびｆがこの空間についての実数値関数である場合、Ｌｐノルム
【数２５】
2014146312.tif 000027
を１≦ｐ＜∞の範囲で次のように定義する。
【００３８】
【数２６】
2014146312.tif 000028
【００３９】
Ｌ∞ノルム
【数２７】
2014146312.tif 000029
は、次のように定義される。
【００４０】
【数２８】
2014146312.tif 000030
【００４１】
ここで、右項は｜ｆ｜の本質的上限と呼ばれ、関数の「最大」とほぼ考えることができる。そのため、いくらかの言葉の誤用があるが、次のように書くことができる。
【００４２】
【数２９】
2014146312.tif 000031
【００４３】
次いで、１≦ｐ≦∞の範囲で、空間Ｌｐは、
【数３０】
2014146312.tif 000032
であるすべての関数ｆの空間であるとして定義される。あるｐ＜∞の範囲で
【数３１】
2014146312.tif 000033
であるという条件のもとで、次のようになる。
【００４４】
【数３２】
2014146312.tif 000034
【００４５】
以下において、ノルムＬｐというより一般的な記号ではなく、記号Ｌαがノルムを示すために使用され、ノルム指数添字と、サンプリングまたは最適化を実行するターゲット分布ｐとの間の混同を避ける。
【００４６】
棄却サンプリングの標準概念は、Ｌ１ノルムを使用して図１のＯＳ＊アルゴリズムを実行する（すなわち、サンプリングに対してα＝１）ことによって取得される。しかしながら、以下の一般化を、本明細書では導入する。ｆ∈Ｌα（Ｘ，μ）である場合、および標準的な意味で、正規化密度分布
【数３３】
2014146312.tif 000035
の場合、１≦α＜∞の範囲でＬα（Ｘ，μ）に対する非負関数ｆのサンプリングを実行していると言えるであろう。α＝∞の場合、ｆ∈Ｌ∞（Ｘ，μ）であり、さらにｆに対して最適化を実行する場合に、より正確には、任意のε＞０に対して
【数３４】
2014146312.tif 000036
であるようなｘを発見することができる場合に、相対的にＬ∞（Ｘ，μ）をサンプリングしていると言えるであろう。
【００４７】
図１のＯＳ＊アルゴリズムを実行するための一般的な設計は、以下のように説明することができる。目的は、ｐからＯＳ−サンプリングすることであり、ここで、「ＯＳ−サンプリング」とは、サンプリングと最適化との両方をカバーする総合的な意味である。本手法では、空間（Ｘ，μ）にわたって提案密度の群Ｑを有し、全ｑ∈Ｑに対し、ｑから効率的にＯＳ−サンプリングを行うことができる。ｐ（ｘ１）＜ｑ（ｘ１）である提案ｑに対するサンプルｘ１の棄却時に、本手法では、ｐ≦ｑ’≦ｑであり、ｑ’（ｘ１）＜ｑ（ｘ１）であるような、（限定された）ある数の可能な「１ステップ」修正オプションｑ’を有する。その場合、そのようなｑ’の１つを選択する。適切な選択基準は、最小Ｌ１ノルム（サンプリングの場合）または最小ノルムＬ∞（最適化）を有するｑ’を優先させることである。ｑ’（ｘ１）を最小にするｑ’を選択するような、他の基準を使用してもよい。ＯＳ＊アルゴリズムは、適切な停止基準が満たされるまで繰り返す。サンプリングの場合、適切な停止基準の１つは、次第に増加する受け入れ率が、ある閾値を上回った場合である。最適化の場合、繰返しは、ｘ１がｑに対する最大値である場合、比ｐ（ｘ１）／ｑ（ｘ１）が、ある閾値よりも１に近づく場合に適切に停止する。次いで、閾値はエラーメトリクス（すなわち、最大エラー）を、ターゲット分布ｐの判断された最大値に対してもたらす。
【００４８】
以下のアルゴリズム１は、擬似コードを提示し、サンプリングまたは最適化のいずれかのために選択的に以下のＯＳ＊アルゴリズムを実行する。
【数３５】
2014146312.tif 000037
【００４９】
アルゴリズム１は、図１に示すＯＳ＊アルゴリズムに対応する。ＯＳ−Ｓａｍｐｌｅサブルーチンは動作２２に対応し、サブルーチンＡｃｃｅｐｔ−ｏｒ−Ｒｅｊｅｃｔは動作２４に対応し、Ｕｐｄａｔｅサブルーチンは動作２６に対応し、Ｒｅｆｉｎｅサブルーチンは動作３０に対応し、Ｓｔｏｐサブルーチンは判断動作３２に対応する。
【００５０】
アルゴリズム１へのエントリー時に、サンプルモードまたは最適化モードのいずれかであり、さらに、（１）ｐを優位とする、および（２）直接サンプリングもしくは最適化をすることができる、提案ｑから開始すると仮定する。ＯＳ−サンプルという用語を使用して、いずれの場合も表し、ここで、ＯＳ−サンプルｘ：ｑは、提案ｑに従ってｘをサンプリングすること、または状況により、ｑでｘを最適化すること（すなわち、ｑのａｒｇｍａｘであるｘを発見すること）に関する。アルゴリズム１のライン（１）では、ｈは、これまでのサンプリングの履歴に関し、すなわち、これまでに実行した試行ｘ１，ｘ２，．．．のセットに関し、それぞれが受け入れまたは棄却について記される（サンプリングの場合、これは通常の概念であり、最適化の場合、最後の提案以外のすべてが棄却として記される）。（図１のＯＳ＊アルゴリズムでは、対応する動作２６は、動作２６が、受け入れ時のみに動作して、その結果、棄却が履歴に記録されない点で、アルゴリズム１に対してわずかに変更される。あるいは、動作２６は、受け入れと棄却との両方を記録することができ、受け入れ率を算出する際に有用となり得るが、この率はまた、受け入れ数と棄却の総数とをトラッキングすることによって算出することができる。）停止基準Ｓｔｏｐ（ｈ）は次の通りに適切である。サンプリングモードでは、試行の数に対するこれまでの受け入れ数が、あるあらかじめ定義した閾値よりも大きい場合、ライン（８）で、第１に、ｐからのすでに有効なサンプルである、これまでに受け入れたｘのリストを、および、第２に、次いで、これまでに観測されたものと同様の受け入れ率を有すると期待されるような任意の数のサンプル候補を生成するために使用することができる、最終修正ｑを返す。最適化モードの場合、履歴の最終要素ｘが受け入れられた場合、ライン（８）で、第１に、このモードにおいて履歴における唯一の受け入れられた試行である値ｘを、第２に、最大値についての情報、例えば、最大値およびエラーを算出することができる受け入れられたｘに対するｐ（ｘ）およびｑ（ｘ）を返す。
【００５１】
アルゴリズム１のライン（３）では、比ｒが算出され、次いで、ライン（４）では、この比に基づいてｘを受け入れるかどうかを判断し、最適化モードにおいて、閾値によって判断したように、比が１に十分近いなら、ｘを受け入れ、サンプリングモードでは、確率ｒのベルヌーイ試行に基づいてｘを受け入れる。ライン（５）では、試行ｘを、および試行ｘが受け入れられたかを記録することによって、履歴が更新される（または、代わりに、ライン（５）は、受け入れたサンプルに対してのみ実行することができる）。ｘが棄却された場合（アルゴリズム１のライン（６））、ライン（７）では、ｑの修正が実行される。
【００５２】
結合サンプリング／最適化ＯＳ＊アルゴリズムについて概ね説明してきたが、フレーズベース統計機械翻訳（ＰＢ−ＳＭＴ）に対して開示される用途について説明する。
【００５３】
本明細書の用例では、ソース言語はフランス語であり、ターゲット言語は英語であるが、ソース言語およびターゲット言語は、実質的に任意の２つの異なる自然言語とすることが可能である。各フレーズは、特定の順序の１つまたは複数のワード（または、トークン）を含み、各ワードは、（英語などの言語では）アルファベット文字の文字列によって、もしくは（例えば、中国語などの言語では）表意文字などの他の適切な表示によって、またはそれらの何らかの組合せによって、（典型的には、コンピュータまたは他の電子データ処理デバイス１２によって処理するための電子形式で）表される。例示的なＰＢ−ＳＭＴシステムはまた、音声ワードに対応する１つまたは複数の音の断片によってフレーズが表される録音された音声言語などの他の方法で表された自然言語の翻訳での使用に応用されることもあり得る。ソース言語入力ｓは、ソース言語文字列ｓまたはソース言語センテンスｓとして本明細書にさまざまに表され、ターゲット言語文字列またはセンテンスｔに対しても同様である。本明細書での「センテンス」という用語の使用は、文法的なセンテンスごとにしばしば適用される典型的なデコーディング処理に従うが、センテンスｓは、１つのユニットとして処理される２つ以上の文法的センテンスを含むことができるか、または、完全に文法的なセンテンス未満を含むことができ、ｔに対しても同様である。
【００５４】
説明のために、ソース言語であるフランス語センテンスｃｅｔｔｅ  ｔｒａｄｕｃｔｉｏｎ  ａｕｔｏｍａｔｉｑｕｅ  ｅｓｔ  ｃｕｒｉｅｕｓｅのフランス語から英語への翻訳を考える。表１に示す英語−フランス語バイフレーズのデータベースを考える。（通常は、バイフレーズのデータベースは、表１の単純な例としてのデータベースよりもはるかに大きく、数千、数万、またはそれ以上のバイフレーズを含む。）
【００５５】
【表１】
2014146312.tif 000038
【００５６】
そのようなデータベースのために構築されたＰＢ−ＳＭＴモデルは、さまざまな可能性を有するさまざまな訳語候補を生成することができる。可能性のある訳語の１つは、ｔｈｉｓ  ｍａｃｈｉｎｅ  ｔｒａｎｓｌａｔｉｏｎ  ｉｓ  ｓｔｒａｎｇｅであり、以下の一連の判断を行うことによって取得され、各判断は、バイフレーズｈ．ｍｔ．ｉ．ｓによって表される。ここで、翻訳は、ソース言語（フランス語）ワードｃｅｔｔｅを消費するバイフレーズｈで開始し、ターゲット言語（英語）ワードｔｈｉｓを出力し、その後、フランス語ワードｔｒａｄｕｃｔｉｏｎ  ａｕｔｏｍａｔｉｑｕｅを消費するバイフレーズｍｔが続き、英語ワードｍａｃｈｉｎｅ  ｔｒａｎｓｌａｔｉｏｎを出力するなど、入力ソース言語センテンスのすべてのソース言語ワードが、繰り返されることなく消費されるまで続く。
【００５７】
他の訳語候補：ｔｈｉｓ  ｔｒａｎｓｌａｔｉｏｎ  ｑｕｉｔｅ  ｂｉｚａｒｒｅ  ｉｓ  ａｕｔｏｍａｔｉｃとしてもよく、これは、一連の判断：ｈｔ．ｑ．ｉ．ａに対応する。ここでまた、すべてのソース言語ワードが、繰り返されることなく消費される。ここで、ソースワードが、ソース言語センテンスでの順序とは異なる順序で消費されており、それが正当であることが分かる。
【００５８】
従来は、バイフレーズは、ペア
【数３６】
2014146312.tif 000039
によって表され、
【数３７】
2014146312.tif 000040
および
【数３８】
2014146312.tif 000041
は、それぞれソース言語フレーズおよびターゲット言語フレーズである。しかしながら、バイフレーズ表現
【数３９】
2014146312.tif 000042
は、ソース言語ワードの消費について、何の情報ももたらさない。
【００５９】
ＯＳ＊アルゴリズムを適用してＰＢ−ＳＭＴデコーディングを実行する際、「ワードごと」のトリプルフォーマット（Ｅ，Ｂ，Ｎ）を使用して、候補配列ａを表すことは有益であり、フィールドＥは英語のワード（正確には、１つのそのようなワード、より正確には、１つのソース言語ワード）を意味し、フィールドＢはこのワードを生成するバイフレーズを意味し、フィールドＮは、これまでに消費されたソース言語であるフランス語ワードの数（または、より正確には、バイフレーズＢ内に、および訳語候補を表すシーケンス内のＢの前にバイフレーズ内に出現するソース言語トークンの次第に増加する数）を意味する。このワードごとのトリプル記号を使用することで、第１の訳語候補（ｔｈｉｓ  ｍａｃｈｉｎｅ  ｔｒａｎｓｌａｔｉｏｎ  ｉｓ  ｓｔｒａｎｇｅ）に対応する第１の配列ｈ．ｍｔ．ｉ．ｓは、（ｔｈｉｓ，ｈ，１）．（ｍａｃｈｉｎｅ，ｍｔ，３）．（ｔｒａｎｓｌａｔｉｏｎ，ｍｔ，３）．（ｉｓ，ｉ，４）．（ｓｔｒａｎｇｅ，ｓ，５）のように書き表される。第２の訳語候補（ｔｈｉｓ  ｔｒａｎｓｌａｔｉｏｎ  ｑｕｉｔｅ  ｂｉｚａｒｒｅ  ｉｓ  ａｕｔｏｍａｔｉｃ）に対応する第２の配列ｈｔ．ｑ．ｉ．ａは、（ｔｈｉｓ，ｈｔ，２）．（ｔｒａｎｓｌａｔｉｏｎ，ｈｔ，２）．（ｑｕｉｔｅ，ｑ，３）．（ｂｉｚａｒｒｅ，ｑ，３）．（ｉｓ，ｉ，４）．（ａｕｔｏｍａｔｉｃ，ａ，５）のように書き表される。
【００６０】
有利には、トリプレット記号は、用例で使用される非重複制約と容易に適合する。この制約は、各ソース言語ワードが、訳語候補の構築の際、正確に一回だけ消費されることを要求する。非重複制約は、２つの要素に分解することができる。（１）各ソース言語ワードは消費されなければならない、（２）消費されるソース言語ワードの総数は、翻訳されるソース言語センテンス内のソース言語ワードの総数に等しくなければならない。トリプレット記号では、要素（２）は、トリプレットの最後にあるＮが、ソース言語センテンス内のソース言語ワードの総数と等しい場合にのみ満たされる。示したフランス語の例ｃｅｔｔｅ  ｔｒａｄｕｃｔｉｏｎ  ａｕｔｏｍａｔｉｑｕｅ  ｅｓｔ  ｃｕｒｉｅｕｓｅに対して、この手段Ｎ＝５は、右端のトリプレットに対して要求される。第１の要素は、訳語候補の２つのバイフレーズが、同じソース言語ワードを消費しないことを保証することによって、ペアになる形でチェックすることができる。同様に、第２の例もまた、正当であり、バイフレーズのシーケンスｈｔ．ｑ．ｉ．ａに対応する。
【００６１】
非重複ルールを評価する際、ソース言語センテンス内に含まれる各ワードは、別個のワードとして扱われる。例えば、英語のセンテンスｔｏ  ｂｅ  ｏｒ  ｎｏｔ  ｔｏ  ｂｅを他の言語に翻訳する際（ここでは、英語がソース言語である）、２回含まれるワードｔｏは、２つの別個のソース言語ワードとして扱われ、同様に、２回含まれるワードｂｅも、２つの別個のソース言語ワードとして扱われる。
【００６２】
ＰＢ−ＳＭＴモデルに対するそのような任意の訳語候補の評価またはスコアを算出するために、コストは、次の通りに、前のトリプルの文脈における各トリプルに関連づけられる。コストは、さまざまな要素を含むことができる。例えば、（語彙コストを含む）各バイフレーズの前方および反転条件付き確率コストはバイフレーズに対応するシーケンスにおける第１のトリプルに関連づけることができる（一種の「ユニグラム」コスト）。
【００６３】
前のバイフレーズに対するバイフレーズの歪みコストは、シーケンス内の正確に１つの前のトリプルを調べることによって計算することができる（一種の「バイグラム」コスト）。シーケンス内の前のトリプルに対するトリプルの正当性は、「バイグラム」コストによっても表すことができ、すなわち、後方のトリプルが前方のトリプルに続くことが可能である場合はヌルコスト、そうでない場合は無限コストである。正当性は、トリプルの第３の値Ｎに基づいて算出することができる。例えば、（ｍａｃｈｉｎｅ，ｍｔ，３）は、（ｔｈｉｓ，ｈ，１）の後に来る可能性があり、というのも、３＝１＋２であり、バイフレーズｍｔが２つのソースワードを消費するからである。（ｍａｃｈｉｎｅ，ｍｔ，３）に続くことができる唯一のトリプルは（ｔｒａｎｓｌａｔｉｏｎ，ｍｔ，３）であり、というのも、ｔｒａｎｓｌａｔｉｏｎが、バイフレーズｍｔにおけるターゲットワードｍａｃｈｉｎｅに続くターゲットワードであるためである。
【００６４】
ｎ−１前のターゲット英語ワードを与えるターゲット英語ワードの（ｎ−グラムモデルに関する）ターゲット言語モデルコストは、シーケンス内のｎ−１前のトリプルを見ることによって所与のトリプルを算出することができる（一種の「ｎ−グラム」コスト）。このことは、トリプル記号のさらなる利点であり、というのも、トリプルごとに正確に１つのターゲットワードがあり、この言語モデルコストを計算するために、ターゲット側がターゲットワードの可変数を備えるバイフレーズ間で区別する必要が無くなるからである。
【００６５】
そのような「強化」ｎ−グラム言語モデルにおいて、ラベルは、形式（Ｅ，Ｂ，Ｎ）のあらゆる可能なトリプルであり、ターゲット言語ワードＥはバイフレーズＢと適合可能であり、カウントＮはソースセンテンスの長さよりも小さい。この強化ｎ−グラムモデルにおいて、トリプルのシーケンスについての評価は、このラベルのシーケンスについての強化言語モデルの値を算出する場合の特別な場合と考えることができる。
【００６６】
したがって、バイグラムシーケンスをデコードする（すなわち、最適化する）ことが望まれ、バイグラムシーケンスでは、ソース言語文字列ｓは既知のレイヤであり、ターゲット言語訳語文字列ｔは隠れレイヤであり、ターゲット言語文字列内の各ワードｘｉは、ｘｉ＝Ｅであるトリプル（Ｅ，Ｂ，Ｎ）に等しい観測値ｏｉと関連づけられる。したがって、隠れマルコフモデル（ＨＭＭ）と類似して、隠れレイヤ内の各バイグラムｘｉ−１ｘｉは、因子
【数４０】
2014146312.tif 000043
の一因となる。次いで、次式を最大にするターゲット言語訳語文字列ｘ＝ｘ１，．．．，ｘｎの発見を試みる。
【００６７】
【数４１】
2014146312.tif 000044
【００６８】
単に
【数４２】
2014146312.tif 000045
と書き、次いで、長さｎのワード文字列にわたってｐ（ｘ）を最大にすることを試みる。ここで、以下の概念を導入する。語彙中の所与のワードｘｉに対し、次式を定義する。
【００６９】
【数４３】
2014146312.tif 000046
【００７０】
ｍａｘは、語彙中のすべての可能性のあるワードｘｉ−１全体にわたり、最後のワードがｘｉであるバイグラムのセットの「最大バックオフ」すなわち「楽観的バックオフ」と呼ぶ。ここで、本セットアップに対するＯＳ＊ｏの用途は、次の通りである。初期提案ｑ（１）を、次式として定義する。
【００７１】
【数４４】
2014146312.tif 000047
【００７２】
提案の必要に応じてｑ（１）（ｘ）≧ｐ（ｘ），∀ｘであり、文字列の空間にわたってｑ（１）がｐを支配するということを意味する。ｑ（１）は、必ずしも正規化分布に対応せず、典型的には、Σｘｑ（１）（ｘ）＞１であることに留意されたい。
【００７３】
図６を参照すると、標準ビタビデコーディング技術を、ｑ（１）を表す重み付き有限状態オートマトン（ＷＦＳＡ）に適用することによって、ｑ（１）が最大値に達する点ｘ（１）を発見することが可能である。（図６および図７において、トリプル（Ｅ，Ｂ，Ｎ）は、Ｅ−Ｂ−Ｎと書き表されることに留意されたい。）図６は、提案ｑ（１）を表す重み付きオートマトンの用例を示し、エッジでの重みはトリプルに対応する。図６のオートマトンは、６つの状態のみを有する単純例であり、確率分布（サンプリング）へのビタビデコーディング（最適化）または重み正規化のいずれかに対する通常の動的プログラミング技術が、非常に効果的である。図６では、最適化の場合のみが示され、このオートマトンに対する最適パスは、太いエッジで示され、訳語ｔｈｉｓ  ｔｒａｎｓｌａｔｉｏｎ  ｍａｃｈｉｎｅ  ｉｓ  ｓｔｒａｎｇｅに対応する。実際には、ＷＦＳＡは、典型的には、はるかに多数の状態およびパスを含む。
【００７４】
図６のオートマトンによって表されたｑ（１）と、このパスに対するＰＢ−ＳＭＴモデルによって生じた確率ｐ（ｔ，ａ｜ｓ）とを比較する際、これらの値の間に大きなギャップが観測され、これは、「トリプルバイグラム」（ｔｒａｎｓｌａｔｉｏｎ，ｔ，２）．（ｍａｃｈｉｎｅ，ｍ，３）は、Ｎが一様であるという意味で正当であるが、シーケンス「ｔｒａｎｓｌａｔｉｏｎ  ｍａｃｈｉｎｅ」という英語に対するターゲット（標準）言語モデルがありそうにもないということのために、好ましくないためである。
【００７５】
図７を参照すると、本観測の大きな違いに基づき、サンプルは棄却され、提案ｑ（１）は、図７に示すｑ（２）に修正され、文脈（ｔｒａｎｓｌａｔｉｏｎ，ｔ，２）を明確にし、（ｍａｃｈｉｎｅ，ｍ，３）にラベル付けられた状態（２’）と（３）との間のエッジの重みを下げる。この場合も、ｑ（２）に対する新しい最大パスは、太線で示す。図７において、ｑ（１）とｑ（２）との両方に対する最大パスは、非重複制約を遵守することに留意されたい。ｑに対する最大パスが（ｔｈｉｓ，ｈ，１）．（ｔｒａｎｓｌａｔｉｏｎ，ｔ，２）．（ｍａｃｈｉｎｅ，ｍ，３）．（ｔｈｉｓ，ｈ，４）．（ｓｔｒａｎｇｅ，ｓ，５）であった場合、ソースワードｃｅｔｔｅに重複が存在し、その場合、問題のパスを含まない他の修正案に導かれる。
【００７６】
通常、処理は、真の重みｐ（ｘ（ｋ））と繰返しｋでの提案重みｑ（ｋ）との比較を繰り返す。その差が閾値より大きい場合、他の修正が実行され、繰返しを継続する。これは、文脈が１ワード単位で伸び、ｘ（ｋ＋１）を形成した場合、ｑ（ｋ＋１）（ｘ（ｋ＋１））の値における最大減少に対応するｘ（ｋ）を構成するターゲット言語ワード間で識別することによって行われる。これは、１つ以上の状態をオートマトンに加えること、一部のエッジをコピーすること、および１つのエッジの重みを減らすことによって行うことができる。
【００７７】
バイグラムＰＢ−ＳＭＴに対して概説した手順は、任意のｎ−グラムＰＢ−ＳＭＴに直接適用することができる。例えば、ｐ（ｔ，ａ｜ｓ）が５−グラムモデルを使用する場合、次の最大バックオフを再帰的に導入することができる。
【００７８】
【数４５】
2014146312.tif 000048
【００７９】
この一般的な場合において、オートマトンｑ（ｋ）における現在の最適パスを修正する場合、選択は、このパスの拡張、すなわち、既存のユニグラム、バイグラム、トリグラム、または既存のクアドライグラムの文脈の間で利用可能であり、この選択は、最大の「的外れ」をもたらすパスを拡張するために行われる。
【００８０】
修正処理は、比ｐ（ｘ（ｋ））／ｑ（ｋ）（ｘ（ｋ））が任意の閾値よりも１に近づく場合に、または、任意選択的にｐ（ｘ（ｋ））／ｑ（ｋ）（ｘ（ｋ））＝１である場合に停止し、これは、ｐ（ｔ，ａ｜ｓ）に対応する真のＷＦＳＡに存在するものよりもより多くの状態をオートマトンに導入することができないため、一定の点に到達する。
【００８１】
サンプリングアルゴリズムは、最適化バージョンと類似する。最適化の場合、例えば動的プログラミング手順を介して、ｑ（ｋ）オートマトンにおける最大パスを発見することが可能である。実質的に、最終状態から開始することで、本手順は、各状態に対し、この状態から最終状態に結びつけるパスの最大の重みを算出し、最後の状態からますます離れる状態に対して本手順を繰り返す。サンプリングの場合との主な違いは、所与の状態から最終状態への最大パスを検出する代わりに、この状態を最終状態に結びつけるすべてのパスの重みについて合計が計算されることであり、さらに本処理が、最適化の場合と同様に繰り返されるということである。形式上、サンプリングは和積半環で動作し、最適化は、最大積半環で動作するが（対数バージョンは熱帯半環と呼ばれる）、それ以外は、手順は同じである。これらの合計が、ｑ（ｋ）オートマトンのすべての状態について算出されると、標準方法で前に進むことによって、これらの合計が、オートマトンからサンプリングするために直接使用される。次いで、修正は、受け入れ率が受け入れ可能になるまで、すなわち、一定の適度な閾値を超えるまで、ｑ（ｋ）を用いて棄却サンプラからの棄却について行われる。ｘが、棄却された訳語候補文字列である場合、最適化の場合では、文脈上の修正に対するｎ−グラムの１つを選択する。方法の１つはｑ（ｋ）（ｘ）に対してｑ（ｋ＋１）（ｘ）の値をこの選択がどれだけ多く減らしたかに基づきこのｎ−グラムを選択することであるが、他の方法は、ｑ（ｋ）（ｘ）の総量に対してｑ（ｋ＋１）（ｘ）の総量をその選択がどれだけ減らしたかに基づきｎ−グラムを選択することであり、サンプリングをするために最も適切であるＬ１目標と一致している。観測した受け入れ率（より正確には、現在のｑ（ｋ）まですべての修正済みオートマトンを用いて、すべての試行をこの点まで実行したために次第に増加する観測した受け入れ率）が閾値を超えるｑ（ｋ）を発見すると、修正を停止し、最終オートマトンを使用して、任意の回数のサンプリングを行う。
【００８２】
しかしながら、上記手順は、非重複条件に対するシーケンスの妥当性をチェックせず、各ソースワードが正確に１回だけ消費されることを要求する。この条件を遵守しない訳語候補文字列の例は、次の通りである。
（ｔｈｉｓ，ｈ，１）．（ｍａｃｈｉｎｅ，ｍｔ，３）．（ｔｒａｎｓｌａｔｉｏｎ，ｍｔ，３）．（ｉｓ，ｉ，４）．（ａｕｔｏｍａｔｉｃ，ａ，５）
【００８３】
非重複条件の一態様は、強化ｎ−グラムモデルに直接組む込むことができ、すなわち、Ｎカウントの進行を制御するものであり、シーケンスの１つの要素から他の要素に移動する場合に「バイグラム」コストによって説明することができる。このコストは、バイフレーズＢと次のバイフレーズＢ’との間の遷移が、Ｂ’内のソーストークンの数によってＮを増分することに対応する場合にヌルとし、そうでない場合に有限とする（すなわち、乗算用語（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｐａｒｌａｎｃｅ）で、それぞれ１および０の重みに対応する）。しかし、第２の態様は、制御することがより困難であり、すなわち、いかなるソースワードも２回は消費されないことを要求する。まとめると、２つの態様で、各ソースワードが正確に１回だけ消費されることを保証することをチェックすることは簡単であり、非重複条件に反する所与の例だけが第１の態様を遵守し、第２の態様では遵守せず、というのも、ソースワードａｕｔｏｍａｔｉｑｕｅが２回、すなわち、バイフレーズｍｔによって１回、次いで、バイフレーズａによって再び消費されるからである。
【００８４】
第２の態様を扱う適切な方法は、次の通りである。値ｐ（ｘ）は、訳語候補シーケンスが非重複制約（より詳しくは、いかなるソースワードも２回は消費されないことを要求する第２の態様）を遵守しない場合に０に等しくなるよう（乗算領域（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｄｏｍａｉｎ）で）調整され、そうでなければ、ｐ（ｘ）は、上記した強化ｎ−グラムモデルによって算出された通常値を有する。ここで、棄却は、トレーニングされたＰＢ−ＳＭＴを使用して算出されたｐ（ｘ）がｑ（ｘ）に比べて低い場合、または、非重複制約に反し、ｐ（ｘ）をゼロにセットされた場合に起こる可能性がある。
【００８５】
しかしこれは、それ自体によって、満足のいく解決策ではなく、というのも、トレーニングされたＰＢ−ＳＭＴを使用して算出されたｐ（ｘ）がその領域で高位である場合、ＯＳ＊アルゴリズムが、非重複ルールを頻繁に違反するこの領域を再サンプリングしようとする可能性があるからである。これを避けるために、ｐ（ｘ）＝０（非重複条件がサンプルｘに対して違反されたことを意味する）が、ＷＦＳＡからのサンプル（より好ましくは、サンプルを含む領域）を除去するよう構成された場合、修正が実行される。
【００８６】
シーケンスｘ＝ａ１ａ２．．．ａｍ（ａｋはトリプルである）が、非重複制約に違反すると仮定する。これは、ａｋおよびａｋ＋ｌが、共通の少なくとも１つのソース言語ワードｆを有するようなサブシーケンスａｋ．．．ａｋ＋ｌが存在するという意味である。その場合、ｑからｑ’への修正は、そのようなサブシーケンスａｋ．．．ａｋ＋ｌをｘ内に配置し、ｑをｑ’に変更することを必要とし、その結果、修正されたオートマトンｑ’は、サブシーケンスａｋ．．．ａｋ＋ｌを含むいかなるシーケンスも受け入れないが、ｑと同等である。この変更例は、ｌノードの配列を、オートマトンｑに加える。この動作を調べる他の方法は、ｑと、言語Ｖ＊ａｋ．．．ａｋ＋ｌＶ＊の補語との共通部分としてであり、Ｖは、翻訳されているソースセンテンスに関連するあらゆるトリプルの語彙である。
【００８７】
通常は、サブシーケンスａｋ．．．ａｋ＋ｌは独特なものではない。例えば、トリプルａ１３およびａ１５の両方が、非重複ルールに反するような同じソースワードｆを消費するシーケンス部分．．．ａ１２ａ１３ａ１４ａ１５ａ１６ａ１７．．．を考える。この場合、サブシーケンスａｋ．．．ａｋ＋ｌは、以下のサブシーケンスのいずれかとして選択され得、そのサブシーケンスは、ａ１２ａ１３ａ１４ａ１５ａ１６ａ１７、ａ１２ａ１３ａ１４ａ１５ａ１６、ａ１２ａ１３ａ１４ａ１５、ａ１３ａ１４ａ１５ａ１６ａ１７、ａ１３ａ１４ａ１５ａ１６、またはａ１３ａ１４ａ１５である。これらの選択では、最短サブシーケンス、この場合はａ１３ａ１４ａ１５が、一般に、好ましい選択であり、というのも、オートマトンを修正して、この最短サブシーケンスを含むすべてのシーケンスを除去することは、オートマトンから最大数の不当なシーケンス、つまり、他と比較して、より長いサブシーケンスを除去することだからである。
【００８８】
この動作は、ＯＳ＊アルゴリズムの次の繰返しで、再び現在のｘを生成せず、さらに、サブシーケンスａｋ．．．ａｋ＋ｌを含む他のいかなるパスも生成しないことを保証する。そのような修正を加えることで、いくつかのｎ−グラム文脈の配列が増えるが、修正は、（最適化では）正確な最適条件を発見する点で、または（サンプリングでは）任意のあらかじめ設定された受け入れ率を超過する点で、アルゴリズムの収束を保証する。これは、任意にＰＢ−ＳＭＴモデルｐ（ｔ，ａ｜ｓ）に近づく提案オートマトンｑを修正動作により生成することが可能であるということによる。実際には、修正は、最適化の場合に正確な最適条件を用いて、および優れた性能の正確なサンプラを用いて、早期に終了することができる。最適化の場合、これは、最適な解決策が見つかったことの証明となる。
【００８９】
場合によっては、サブシーケンスａｋ．．．ａｋ＋ｌを含むいかなるシーケンスも受け付けないようｑを修正することで、少数のシーケンスのみを除去することができ、収束を遅くさせる。しかしながら、一度により多くのシーケンスを除去することも可能である。ワードｆにすべて触れるようなトリプルのセットＺを考え、さらに、翻訳されているソースセンテンスに関係するすべてのトリプルの語彙Ｖの任意のサブセットとなるようなＡを考える。その場合、ｑを、言語Ｖ＊ＺＡ＊ＺＶ＊の補語を表すオートマトンと重なり合わせることが可能である。特に、Ａ＝｛ａｋ＋１，．．．，ａｋ＋ｌ−１｝およびＺ＝｛ａｋ，ａｋ＋ｌ｝とすることができる。このことは、ｑ’においてより多くの状態を生成するという代償を払って、サブシーケンスａｋ．．．ａｋ＋ｌを含むすべてのサンプルを単に除去するよりも、より多くの無効サンプルｘを除去しようとする。ＡがＶに等しい場合に限定すると、結果としてのｑ’は、ほぼ２倍のｑの状態を有し、というのも、本質的には、パス上に以前に存在したＺであるかどうかを各状態で記録する必要があるためである。しかしながら、ＡがＶのより小さなサブセットに限定される場合、導入される必要のある新しい状態の数は、著しく少なくすることができる。
【００９０】
さらに他の補足的な手法により、ｘにおいて、ｘによって消費されないいくつかの他のソースワード
【数４６】
2014146312.tif 000049
を識別し、実際、そのようなワードは必然的に存在し、というのも、重複ワードｆは、２つの「スロット」を占めており、ソースワードと正確に同じ数のスロットが存在するためである（最終トリプルに対するＮの値が、ソースセンテンス内のワード数に等しいと仮定する）。この条件は、ｑを言語
【数４７】
2014146312.tif 000050
と重ね合わせることによって強化することができ、ここで、
【数４８】
2014146312.tif 000051
は
【数４９】
2014146312.tif 000052
を含むすべてのトリプルの集合からなる言語である。
【００９１】
図８を参照して、図１のシステムを、ソース言語文字列ｓ１００を翻訳するために適用される例示的ＰＢ−ＳＭＴアプリケーションの文脈で、すなわち、ＯＳ＊アルゴリズム１０が、ＯＳ＊アルゴリズムを使用するＰＢ−ＳＭＴアルゴリズム１１０を実現するよう構成された場合で説明する。サンプリングされる、または最適化される関数または分布ｐ（ｘ）１４は、ここではＰＢ−ＳＭＴモデルｐ（ｔ，ａ｜ｓ）１１４であり、構成ｘは、ｓ１００に対する訳語候補を生成するすべての配列ａにわたって存在する。構成ｘは、本明細書で定義されたトリプル記号（Ｅ，Ｂ，Ｎ）を使用して適切に表される。初期の提案分布ｑ（０）（ｘ）２０は、ＰＢ−ＳＭＴモデルｐ（ｔ，ａ｜ｓ）１１４を使用して生成することができるｓ１００の可能性のあるターゲット言語の訳語を表す初期の重み付き有限状態オートマトン（ＷＦＳＡ）ｑ（０）（ｘ）１２０として構成される。オートマトンｑは、トリプル要素（Ｅ，Ｂ，Ｎ）に対応するエッジを適切に使用する（図６および図７の用例を参照）。より詳しくは、初期のオートマトンｑ（０）は、ＰＢ−ＳＭＴモデルｐ（ｔ，ａ｜ｓ）１１４によるソース言語文字列ｓ１００に対して可能性のある訳語を表すすべてのｘに対する条件ｑ（０）（ｘ）≧ｐ（ｘ）を満たす。
【００９２】
その場合、ＰＢ−ＳＭＴ用途に対するＯＳ＊アルゴリズムは、図１を参照して説明したようなサンプリング動作２２を実行し、サンプルｘ＊を取得する。受け入れ／棄却動作２４は、非重複制約がサンプルｘ＊によって満たされない場合、ｐ（ｘ＊）＝０と設定する追加動作１２５を含むことによって、受け入れ／棄却動作１２４に変更される。応答２６は、図１を参照してすでに説明したように実行される。ｘ＊が棄却された場合に実行される修正動作３０は、ｐ（ｘ＊）＝０であるかどうかをチェックして、もしそうであるなら、修正は、提案オートマトンｑを変更して、非重複制約に違反するサブシーケンスａｋ．．．ａｋ＋ｌを含むあらゆる今後のサンプルを受け入れないことを必然的に伴う追加の動作１３１を含むことによって修正動作１３０に変更される。繰返し停止動作３２は、図１を参照してすでに説明した通りであるが、出力動作３４は、提案された訳語１３４を特に出力するように変更される。
【００９３】
図８の例示的な実施形態において、非重複制約を違反することに対しては、このことにより、サンプルｘ＊が確実に棄却されるため受け入れ／棄却動作においてｐ（ｘ＊）＝０と設定することによって効果的にフラグを立てられ、その場合、同じｐ（ｘ＊）＝０が修正動作１３０におけるある種の「フラグ」として使用され、棄却が非重複条件に違反したためであったことを検出することができる。しかしながら、他の方法を使用することも可能である。代替の実装形態の一例として、さらなるフラグ要素を追加することができ、そのフラグ要素は、非重複制約が満たされると０に設定され、非重複制約が違反されると１に設定され、そして、フラグが１に設定され、さらに修正動作が、修正の判断をする際に同フラグをチェックする場合、受け入れ／棄却動作はｘ＊を適切に棄却する。
【図１】
2014146312.tif 000055
【図２】
2014146312.tif 000056
【図３】
2014146312.tif 000057
【図４】
2014146312.tif 000058
【図５】
2014146312.tif 000059
【図６】
2014146312.tif 000060
【図７】
2014146312.tif 000061
【図８】
2014146312.tif 000062