(57)【要約】      （修正有）【課題】  削除補間言語モデルのパラメータをバックオフ言語モデルのパラメータとして記憶するための方法および装置を提供すること。【解決手段】  具体的には、削除補間言語モデルのパラメータを標準ＡＲＰＡフォーマットで記憶する。一実施形態では、前記削除補間言語モデル用のパラメータのセットを得るステップと、前記削除補間言語モデルの少なくとも１つのパラメータである単語シーケンスの補間済み確率を、バックオフ言語モデル中の単語シーケンスの確率として記憶するステップ、を含む。【選択図】  図７
2005293580.tif 000002
【特許請求の範囲】
【請求項１】
削除補間言語モデルのパラメータを記憶する方法であって、
前記削除補間言語モデル用のパラメータのセットを得るステップと、
前記削除補間言語モデル用の少なくとも１つのパラメータをバックオフ言語モデル用のパラメータとして記憶するステップと
を含むことを特徴とする方法。
【請求項２】
前記削除補間言語モデル用の少なくとも１つのパラメータを記憶するステップは、単語シーケンスの補間済み確率を前記バックオフ言語モデル中の単語シーケンスの確率として記憶するステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記補間済み確率を記憶するステップは、前記単語シーケンスの相対頻度がしきい値よりも大きいと判定した後で前記補間済み確率を確率として記憶するステップを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記相対頻度は、小数値を有する頻度カウントに基づいて決定されることを特徴とする請求項３に記載の方法。
【請求項５】
前記補間済み確率を記憶するステップは、前記単語シーケンスが前記バックオフ言語モデル中のｎグラムに対するコンテキストを形成すると判定された後で前記補間済み確率を確率として記憶するステップを含むことを特徴とする請求項２に記載の方法。
【請求項６】
前記削除補間言語モデル用の少なくとも１つのパラメータを記憶するステップは、前記削除補間モデル用の補間重みを前記バックオフ言語モデル用のバックオフ重みとして記憶するステップを含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記補間重みを記憶するステップはさらに、前記補間重みに関連する単語シーケンスを前記補間重みと同じエントリに記憶するステップを含むことを特徴とする請求項６に記載の方法。
【請求項８】
前記パラメータのセットを得るステップは、補間重みのセットを訓練するステップを含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記補間重みのセットを訓練するステップは、頻度カウント範囲のセットごとに別々の重みを訓練するステップを含むことを特徴とする請求項８に記載の方法。
【請求項１０】
前記削除補間言語モデル用の少なくとも１つのパラメータを記憶するステップは、バックオフ言語モデル用のＡＲＰＡフォーマットに準拠するデータ構造を生み出すように前記少なくとも１つのパラメータを記憶するステップを含むことを特徴とする請求項１に記載の方法。
【請求項１１】
コンピュータ実行可能命令を有するコンピュータ可読媒体であって、前記コンピュータ実行可能命令は、
削除補間言語モデル用のパラメータを識別するステップと、
前記パラメータをバックオフ言語モデル用のバックオフパラメータとしてデータ構造中に配置するステップと
を実施するための命令であることを特徴とするコンピュータ可読媒体。
【請求項１２】
前記パラメータをデータ構造中に配置するステップは、前記パラメータが前記バックオフ言語モデルの一部として含まれるべきであると判定するステップを含むことを特徴とする請求項１１に記載のコンピュータ可読媒体。
【請求項１３】
前記パラメータが前記バックオフ言語モデルの一部として含まれるべきであると判定するステップは、訓練テキスト中における単語シーケンスの頻度がしきい値を超えると判定するステップを含むことを特徴とする請求項１２に記載のコンピュータ可読媒体。
【請求項１４】
前記パラメータが前記バックオフ言語モデルの一部として含まれるべきであると判定するステップは、前記パラメータに関連する単語シーケンスが、前記データ構造に記憶されたｎグラム中のコンテキストを形成すると判定するステップを含むことを特徴とする請求項１２に記載のコンピュータ可読媒体。
【請求項１５】
前記パラメータをデータ構造中に配置するステップは、補間済み確率をｎグラムの確率として配置するステップを含むことを特徴とする請求項１１に記載のコンピュータ可読媒体。
【請求項１６】
前記パラメータをデータ構造中に配置するステップは、補間重みをコンテキストに対するバックオフ重みとして配置するステップを含むことを特徴とする請求項１１に記載のコンピュータ可読媒体。
【請求項１７】
前記データ構造はバックオフ言語モデル用のＡＲＰＡ標準に準拠することを特徴とする請求項１１に記載のコンピュータ可読媒体。
【請求項１８】
言語モデルを構築する方法であって、
削除補間を用いて言語モデル用のパラメータを訓練するステップと、
前記訓練されたパラメータの少なくともいくつかを、バックオフ言語モデル用のＡＲＰＡフォーマットに準拠するデータ構造で記憶するステップと
を含むことを特徴とする方法。
【請求項１９】
前記訓練されたパラメータの少なくともいくつかを記憶するステップは、訓練テキスト中でしきい値量よりも多く出現する単語シーケンスに関連するパラメータを記憶するステップを含むことを特徴とする請求項１８に記載の方法。
【請求項２０】
前記訓練されたパラメータの少なくともいくつかを記憶するステップは、前記データ構造に記憶されたｎグラム中のコンテキスト単語として出現する単語シーケンスに関連するパラメータを記憶するステップを含むことを特徴とする請求項１８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は言語モデルに関する。より詳細には、本発明は、言語モデルを記憶するための記憶フォーマットに関する。
【背景技術】
【０００２】
言語モデルは、単語シーケンスの確率を提供する。このようなモデルは、訓練データ（ｔｒａｉｎｉｎｇ  ｄａｔａ）中における単語シーケンスの頻度をカウントすることによって、訓練データのセットから訓練される。このようにして言語モデルを訓練する際の問題の１つは、訓練データ中で観察されない単語シーケンスは、その言語に存在するかもしれないのに、言語モデル中では確率０になることである。
【０００３】
これを克服するために、バックオフモデリング技法（ｂａｃｋ−ｏｆｆ  ｍｏｄｅｌｉｎｇ  ｔｅｃｈｎｉｑｕｅ）が開発された。バックオフ技法では、ｎ個の単語のシーケンスが訓練データ中にない場合、この単語シーケンスの確率は、ｎ−１個の単語のシーケンスの確率と、バックオフ重みとを使用して推定される。例えば、トライグラム（ｗｎ−２  ｗｎ−１  ｗｎ）が訓練データ中で観察されない場合、その確率は、バイグラム（ｗｎ−１  ｗｎ）の確率と、コンテキスト（ｗｎ−２  ｗｎ−１）に関連するバックオフ重みとを使用して推定される。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
バックオフ技法を使用したＮグラム言語モデルは、通常、ＡＲＰＡ標準フォーマットと呼ばれる標準フォーマットで記憶される。バックオフ言語モデルが普及したことにより、ＡＲＰＡフォーマットは、言語モデルを伝送するための一標準として認知されるようになった。しかし、すべての言語モデルがバックオフ重みを有するわけではない。具体的には、削除補間Ｎグラムモデルは、言語モデルに関連するデータ過疎性問題に対処するために異なる技法を使用するので、バックオフ重みを有さない。その結果、削除補間言語モデル（ｄｅｌｅｔｅｄ  ｉｎｔｅｒｐｏｌａｔｉｏｎ  Ｎ−ｇｒａｍ  ｍｏｄｅｌｓ）標準ＡＲＰＡフォーマットで記憶されてこなかった。このため、ＡＲＰＡフォーマットの言語モデルを受け取ることを予期する言語システムに削除補間言語モデルを統合するのは、容易ではなかった。
【課題を解決するための手段】
【０００５】
削除補間言語モデルのパラメータをバックオフ言語モデルのパラメータとして記憶するための方法および装置を提供する。具体的には、削除補間言語モデルのパラメータを標準ＡＲＰＡフォーマットで記憶する。一実施形態では、小数カウントを使用して、削除補間言語モデルパラメータを形成する。
【発明を実施するための最良の形態】
【０００６】
図１に、本発明を実施することのできる適したコンピューティングシステム環境の例１００を示す。コンピューティングシステム環境１００は、適したコンピューティング環境の一例にすぎず、本発明の使用または機能の範囲についてどんな制限を意味するものでもない。またコンピューティング環境１００は、この例示的な動作環境１００に示すコンポーネントのいずれか１つまたは組合せに関してどんな依存や要件を有するものとも解釈すべきではない。
【０００７】
本発明は、その他多くの汎用または専用コンピューティングシステム環境または構成でも機能する。本発明で使用するのに適するであろう周知のコンピューティングシステム、環境、および／または構成の例には、限定しないがパーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、セットトップボックス、プログラム可能な民生用電子機器、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、電話システムや、これらのシステムまたはデバイスのいずれかを含む分散コンピューティング環境などが含まれる。
【０００８】
本発明は、プログラムモジュールなど、コンピュータによって実行されるコンピュータ実行可能命令の一般的なコンテキストで述べることができる。一般に、プログラムモジュールは、特定のタスクを実施するか特定の抽象データ型を実現するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。本発明は分散コンピューティング環境で実施することもでき、その場合、タスクは通信ネットワークを介してリンクされたリモート処理デバイスによって実施される。分散コンピューティング環境では、プログラムモジュールは、メモリ記憶デバイスを含めたローカルとリモートの両方のコンピュータ記憶媒体に位置する。
【０００９】
図１を参照すると、本発明を実施するための例示的なシステムは、コンピュータシステム１１０の形の汎用コンピューティングデバイスを含む。コンピュータ１１０のコンポーネントには、限定しないが処理ユニット１２０と、システムメモリ１３０と、システムメモリを含めた様々なシステムコンポーネントを処理ユニット１２０に結合するシステムバス１２１とを含めることができる。システムバス１２１は、様々なバスアーキテクチャのいずれかを用いた、メモリバスまたはメモリコントローラ、周辺バス、ローカルバスを含めて、いくつかのタイプのバス構造のいずれかとすることができる。限定ではなく例として、このようなアーキテクチャには、ＩＳＡ（Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＭＣＡ（Ｍｉｃｒｏ  Ｃｈａｎｎｅｌ  Ａｒｃｈｉｔｅｃｔｕｒｅ）バス、ＥＩＳＡ（Ｅｎｈａｎｃｅｄ  ＩＳＡ）バス、ＶＥＳＡ（Ｖｉｄｅｏ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｓｔａｎｄａｒｄｓ  Ａｓｓｏｃｉａｔｉｏｎ）ローカルバス、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ）バス（メザニンバスとも呼ばれる）が含まれる。
【００１０】
コンピュータ１１０は通常、様々なコンピュータ可読媒体を備える。コンピュータ可読媒体は、コンピュータ１１０からアクセスできる任意の利用可能な媒体とすることができ、揮発性と不揮発性の媒体、取外し可能と取外し不可能の媒体の両方が含まれる。限定ではなく例として、コンピュータ可読媒体には、コンピュータ記憶媒体および通信媒体を含めることができる。コンピュータ記憶媒体には、コンピュータ可読命令、データ構造、プログラムモジュール、その他のデータなどの情報を記憶するための任意の方法または技術で実現された、揮発性と不揮発性、取外し可能と取外し不可能の両方の媒体が含まれる。コンピュータ記憶媒体には、限定しないがＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリまたはその他のメモリ技術、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）またはその他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置またはその他の磁気記憶デバイスが含まれ、あるいは、所望の情報を記憶するのに使用できコンピュータ１１０からアクセスできるその他の任意の媒体が含まれる。通信媒体は通常、搬送波やその他のトランスポート機構などの被変調データ信号中に、コンピュータ可読命令、データ構造、プログラムモジュール、またはその他のデータを組み入れるものであり、任意の情報送達媒体が含まれる。用語「被変調データ信号」は、信号中の情報が符号化される形で１つまたは複数の特性が設定または変更される信号を意味する。限定ではなく例として、通信媒体には、有線ネットワークや直接有線接続などの有線媒体と、音響、無線周波数、赤外線、その他の無線媒体などの無線媒体とが含まれる。以上の任意の組合せもコンピュータ可読媒体の範囲に含めるべきである。
【００１１】
システムメモリ１３０は、読取り専用メモリ（ＲＯＭ）１３１やランダムアクセスメモリ（ＲＡＭ）１３２など、揮発性および／または不揮発性メモリの形のコンピュータ記憶媒体を含む。ＲＯＭ１３１には通常、起動中などにコンピュータ１１０内の要素間で情報を転送するのを助ける基本ルーチンを含むＢＩＯＳ（ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ）１３３が記憶されている。ＲＡＭ１３２は通常、処理ユニット１２０がすぐにアクセス可能な、かつ／または処理ユニット１２０が現在作用している、データおよび／またはプログラムモジュールを含む。限定ではなく例として、図１には、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、プログラムデータ１３７を示す。
【００１２】
コンピュータ１１０は、その他の取外し可能／取外し不可能、揮発性／不揮発性コンピュータ記憶媒体を備えることもできる。例にすぎないが図１には、取外し不可能な不揮発性の磁気媒体に対して読み書きするハードディスクドライブ１４１と、取外し可能な不揮発性の磁気ディスク１５２に対して読み書きする磁気ディスクドライブ１５１と、ＣＤ  ＲＯＭやその他の光媒体など取外し可能な不揮発性の光ディスク１５６に対して読み書きする光ディスクドライブ１５５を示す。この例示的な動作環境で使用できるその他の取外し可能／取外し不可能、揮発性／不揮発性コンピュータ記憶媒体には、限定しないが磁気テープカセット、フラッシュメモリカード、ディジタル多用途ディスク、ディジタルビデオテープ、固体ＲＡＭ、固体ＲＯＭなどが含まれる。ハードディスクドライブ１４１は通常、インタフェース１４０などの取外し不可能メモリインタフェースを介してシステムバス１２１に接続され、磁気ディスクドライブ１５１および光ディスクドライブ１５５は通常、インタフェース１５０などの取外し可能メモリインタフェースでシステムバス１２１に接続される。
【００１３】
以上に論じ図１に示したドライブおよびそれらに関連するコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、その他のデータの記憶域をコンピュータ１１０に提供する。例えば図１には、ハードディスクドライブ１４１がオペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、プログラムデータ１４７を記憶しているのが示されている。これらのコンポーネントは、オペレーティングシステム１３４、アプリケーションプログラム１３５、その他のプログラムモジュール１３６、プログラムデータ１３７と同じものとすることもでき、異なるものとすることもできることに留意されたい。ここでは、オペレーティングシステム１４４、アプリケーションプログラム１４５、その他のプログラムモジュール１４６、プログラムデータ１４７が少なくとも異なるコピーであることを示すために、異なる番号を付けてある。
【００１４】
ユーザは、キーボード１６２、マイクロホン１６３、マウスやトラックボールやタッチパッド等のポインティングデバイス１６１などの入力デバイスを介して、コンピュータ１１０にコマンドおよび情報を入力することができる。その他の入力デバイス（図示せず）には、ジョイスティック、ゲームパッド、衛星受信アンテナ、スキャナなどを含めることができる。これらおよびその他の入力デバイスは、システムバスに結合されたユーザ入力インタフェース１６０を介して処理ユニット１２０に接続されることが多いが、パラレルポート、ゲームポート、ユニバーサルシリアルバス（「ＵＳＢ」）など、その他のインタフェースおよびバス構造で接続されてもよい。モニタ１９１または他のタイプの表示デバイスも、ビデオインタフェース１９０などのインタフェースを介してシステムバス１２１に接続される。モニタに加えて、コンピュータは通常、スピーカ１９７やプリンタ１９６など、その他の周辺出力デバイスも備えることができ、これらは出力周辺インタフェース１９５を介して接続することができる。
【００１５】
コンピュータ１１０は、リモートコンピュータ１８０など１つまたは複数のリモートコンピュータへの論理接続を用いて、ネットワーク化された環境で操作される。リモートコンピュータ１８０は、パーソナルコンピュータ、ハンドヘルドデバイス、サーバ、ルータ、ネットワークＰＣ、ピアデバイス、またはその他の一般的なネットワークノードとすることができ、通常はパーソナルコンピュータ１１０に関して上述した要素の多くまたはすべてを備える。図１に示す論理接続は、ローカルエリアネットワーク（ＬＡＮ）１７１およびワイドエリアネットワーク（ＷＡＮ）１７３を含むが、その他のネットワークを含むこともできる。このようなネットワーキング環境は、オフィス、企業全体のコンピュータネットワーク、イントラネット、インターネットでよく見られる。
【００１６】
ＬＡＮネットワーキング環境で使用されるときは、コンピュータ１１０は、ネットワークインタフェースまたはアダプタ１７０を介してＬＡＮ１７１に接続される。ＷＡＮネットワーキング環境で使用されるときは、コンピュータ１１０は通常、インターネットなどのＷＡＮ１７３を介した通信を確立するためのモデム１７２またはその他の手段を備える。モデム１７２は内蔵でも外付けでもよく、ユーザ入力インタフェース１６０またはその他の適切な機構を介してシステムバス１２１に接続することができる。ネットワーク化された環境では、コンピュータ１１０に関して示したプログラムモジュールまたはその一部をリモートのメモリ記憶デバイスに記憶することができる。限定ではなく例として、図１には、リモートアプリケーションプログラム１８５がリモートコンピュータ１８０上にあるのが示されている。図示のネットワーク接続は例示的なものであり、コンピュータ間で通信リンクを確立するための他の手段を使用してもよいことは理解されるであろう。
【００１７】
本発明は、削除補間で生成された言語モデルを標準ＡＲＰＡフォーマットで記憶する技法を提供する。削除補間では、Ｎグラム確率は、Ｎグラム確率の相対頻度推定値（ｒｅｌａｔｉｖｅ  ｆｒｅｑｕｅｃｙ  ｅｓｔｉｍａｔｅ）と、より低次のｎグラムの確率との線形補間として決定される。より低次のｎグラムの確率も同様に、この低次のｎグラムと、次に低次のｎグラムとの相対頻度確率推定値として定義される。これを、ユニグラム確率が決定されるまで継続する。したがって、補間は以下の式に従って再帰的に決定される。
Ｐ（ｖｋ｜ｖｋ−（ｎ−１）．．．ｖｋ−１）＝（ｌ−λｎ−１（ｖｋ−（ｎ−１）．．．ｖｋ−１））ｆ（ｖｋ｜ｖｋ−（ｎ−１）．．．ｖｋ−１）＋λｎ−１（ｖｋ−（ｎ−１）．．．ｖｋ−１）Ｐ（ｖｋ｜ｖｋ−（ｎ−２）．．．ｖｋ−１）                                式１
【００１８】
上式で、Ｐ（ｖｋ｜ｖｋ−（ｎ−１）．．．ｖｋ−１）はｎグラムの確率であり、λｎ−１（ｖｋ−（ｎ−１）．．．ｖｋ−１）は、Ｎグラムのコンテキストｖｋ−（ｎ−１）．．．ｖｋ−１に応じた補間重みである。ｆ（ｖｋ｜ｖｋ−（ｎ−１）．．．ｖｋ−１）は、Ｎグラムの相対頻度であり、この頻度は、Ｎグラムが訓練テキスト中に出現する回数を、Ｎグラムのコンテキストが訓練テキスト中に出現する回数で割った数である。Ｐ（ｖｋ｜ｖｋ−（ｎ−２）．．．ｖｋ−１）は、次に低次のｎグラムの確率であり、この確率は、次に低次のｎグラムのコンテキストに応じた重みλｎ−２（ｖｋ−（ｎ−２）．．．ｖｋ−１）を使用して式１を再帰的に用いて決定される。式１の再帰は、以下のように決定されるユニグラム確率で終了する。
【００１９】
【数１】
2005293580.tif 000003
【００２０】
上式で、Ｐ（ｖｋ）はユニグラム確率であり、λ０はユニグラム補間重みである。ｆ（ｖｋ）はユニグラムｖｋの相対頻度であり、この相対頻度は、ユニグラムが訓練テキスト中に出現する回数を、訓練テキスト中の単語数で割った比率である。｜Ｖ｜は語彙中の単語数であり、この数はデフォルトのユニグラム確率として働く。
【００２１】
式１および２の再帰を用いると、Ｎグラムの確率は、当該のＮグラムよりも低い様々な次数のｎグラム相対頻度の補間になる。例えば、トライグラムの場合、再帰的補間は以下の式を生み出す。
【００２２】
【数２】
2005293580.tif 000004
【００２３】
上式で、Ｐ（ｖｋ｜ｖｋ−２ｖｋ−１）はトライグラム確率であり、ｆ（ｖｋ｜ｖｋ−２ｖｋ−１）は訓練テキスト中のトライグラムの相対頻度であり、ｆ（ｖｋ｜ｖｋ−１）は訓練テキスト中のバイグラムの相対頻度であり、ｆ（ｖｋ）は訓練テキスト中のユニグラムの相対頻度であり、｜Ｖ｜は言語モデル中の語彙単語数であり、λ２，λ１，λ０はコンテキスト依存の補間重みである。
【００２４】
いくつかの実施形態では、相対頻度の決定に使用されるカウントは、整数値のカウントに限定されず、カウントの期待値として計算される小数値を含むこともできる。このことは、小数（実数値の）カウントに対して使用することのできないカッツ（Ｋａｔｚ）バックオフ法など他のバックオフ法に勝る、削除補間の利点の１つである。
【００２５】
図２に、削除補間を使用したＮグラム確率の計算のグラフ表現を提供する。図２で、ライン間の交差点は、ｎグラムの確率の補間を表す。例えば、ノード２００でユニグラム確率が決定され、ノード２２０でＮグラム確率が決定される。各ノードでは、より低いノードで決定された重み付き確率に、重み付き相対頻度が加えられる。
【００２６】
例えば、ノード２００で開始し、ユニグラム相対頻度２０２とデフォルトユニグラム確率２０４との重み付き和として、補間ユニグラム確率が決定される。相対頻度２０２には重み２０６（ｌ−λ０）が適用され、デフォルトユニグラム確率２０４には重み２０８（λ０）が適用される。
【００２７】
次に高いノード２１０における確率は、バイグラムの相対頻度２１２と、ノード２００のユニグラム確率との重み付き和である。ノード２００のユニグラム確率には、バイグラムのコンテキストに応じた重み２１４（λ１（ｖｋ−１））が適用され、相対頻度２１２には、重み２１６（ｌ−λ１（ｖｋ−１））が適用される。
【００２８】
この再帰的な和を、Ｎグラム確率のノード２２０に達するまで上に向かって継続する。ノード２２０について決定される確率は、次に低次のｎグラムについてノード２２２で決定された確率と、Ｎグラムの相対頻度２２４との重み付き和である。より低次の確率に適用される重み２２６はλｎ−１（ｖｋ−（ｎ−１）．．．ｖｋ−１）であり、相対頻度に適用される重み２２８はｌ−λｎ−１（ｖｋ−（ｎ−１）．．．ｖｋ−１）であり、これは両方とも、Ｎグラムのコンテキストに依存する。
【００２９】
図２からわかるように、Ｎグラムの確率を決定するには、より低次のｎグラムの相対頻度と、コンテキストに対する重みとを決定しなければならない。図３および４に、これらの値を決定するためのブロック図および流れ図を提供する。
【００３０】
図４のステップ４００で、訓練テキスト３００を主要部分３０２とチェック部分３０４に分割する。ステップ４０２で、相対頻度カウンタ３０６が、主要部分３０２をユニグラムから当該の最高Ｎグラムまでの様々な次数のｎグラムに解析する。次いで相対頻度カウンタ３０６は、各次数のｎグラムにおいて、各ｎグラムの相対頻度をカウントする。これにより、各次数のｎグラムにおける、各ｎグラムのｎグラム相対頻度カウントのセット３０８が得られる。
【００３１】
ステップ４０４で、相対頻度３０８をＥＭトレーナ３１０に適用する。ＥＭトレーナ３１０は、期待値最大化アルゴリズムを使用して、以下のように、すべての最高次数Ｎグラムの確率総計を最大化するように重みλｎ−１．．．λ０の値を設定する。
【００３２】
【数３】
2005293580.tif 000005
【００３３】
上式で、［λｎ−１．．．λ０］は、最高次数のＮグラムの確率を最大化する重みのセットであり、確率総計は、ｉ番目の各Ｎグラムの個別の確率の積であり、個別の確率は、式１および２の再帰的補間を用いて計算される。
【００３４】
前述のように、重みは、それらを使用して決定されるｎグラム確率のコンテキストに応じたものである。データ過疎性（信頼性のない推定値につながることになる）を打ち消すと同時にＥＭ訓練の計算複雑性を低減するために、これらの重みは、コンテキストの頻度カウントに基づいてバケットに分類される。一実施形態では、ある範囲の頻度カウントが、同じ重みに分類される。したがって、あるλｎ−１は、１６回と３２回の間で見られるコンテキストの場合とすることができ、あるλｎ−１は、３３回と６４回の間で見られるコンテキストの場合とすることができる。この結果、訓練する必要のある重みのセットはより小さくなり、訓練に必要な訓練テキストのセットはより小さくなる。
【００３５】
重みはチェックデータ３０４に対して最大化されるので、チェックデータ３０４中には、主要データ３０２中で観察されなかったｎグラムがあることに留意されたい。したがって、重みは未知データを予期するように設定される。
【００３６】
いくつかの実施形態では、訓練テキスト３００を異なる方式で再セグメント化することができ、この新しいテキスト分類に対して相対頻度カウントを再決定することができる。次いで、これらの新しい頻度カウントをＥＭトレーナ３１０に適用して、重みの値を再決定することができる。重みの値を再決定するとき、アルゴリズムは、前の反復で決定された重みの推定値で開始する。このような反復を、重みが安定値に達するまで繰り返すことができる。所望の数の反復が形成された後、ステップ４０６で、重みのセット３１２を、相対頻度カウントの最終的なセット３０８と共に、削除補間モデル３１４として記憶する。この削除補間モデルを使用して、新しいテキストを様々な次数のｎグラムに解析し、各コンテキストに対する適切な重みを探索し、式１および２を使用して補間済み確率の計算を実施することによって、新しいテキストの確率を決定することができる。
【００３７】
式１および２によって表される補間は、より広く受け入れられている、標準ＡＲＰＡフォーマットで通常表されるバックオフ言語モデルで使用される技法とはかなり異なる。より広く受け入れられているバックオフ言語モデルは、線形補間を使用してＮグラムの確率を決定するのではなく、モデル中で突き止めることのできない、任意のＮグラムの代用確率を使用する。この代用確率は、より低次のモデルと、この突き止めることのできない確率のコンテキストに関連するバックオフ重みとに基づく。このように、より標準的であるバックオフ言語モデルは、補間を実施するのではなく、単にＮグラム確率をより低次のｎグラム確率で置き換える。
【００３８】
図５に、従来技術のバックオフモデルを使用してＮグラムの確率を決定する方法の流れ図を示す。図５のステップ５００で、Ｎグラムの確率がバックオフ言語モデル中で突き止められるかどうかを判定するための探索を実施する。Ｎグラムの確率が存在する場合は、ステップ５０２でこの確率を返す。ステップ５００でＮグラムの確率が見つからなかった場合は、ステップ５０４で、Ｎグラムのコンテキストに関連するバックオフ重みを突き止める。ステップ５０６で、バックオフ言語モデルが次に低次のｎグラムの確率を含むかどうかを判定するための探索を実施する。例えば、最高次数のＮグラムがトライグラムであった場合、ステップ５０６でバイグラムの確率を探索することになる。ステップ５０６で次に低次のｎグラムの確率が見つからなかった場合は、プロセスはステップ５０４に戻って、次に低次のｎグラムのコンテキストに対するバックオフ重み、例えばバイグラムのコンテキストに対するバックオフ重みを突き止める。次いでプロセスはステップ５０６に戻って、次に低次のｎグラムの確率を探索する。したがって、前にステップ５０６でバイグラム確率が探索された場合、ステップ５０６に戻るとユニグラム確率を探索することになる。
【００３９】
ステップ５０６でｎグラムの確率が見つかると、ステップ５０８で、ステップ５０４から５０６までの反復で遭遇したすべてのバックオフ重みをこの確率に掛けて、Ｎグラムの確率を形成する。
【００４０】
図５でわかるように、標準的なバックオフ言語モデルを使用してＮグラムの言語モデル確率を計算するには、様々な次数のｎグラムの確率、ならびにこれらのｎグラムのコンテキストに対するバックオフ重みを探索しなければならない。バックオフ言語モデル用の標準ＡＲＰＡフォーマットは、使用されている特定のバックオフ言語モデルにかかわらず、同じ探索アルゴリズムを使用して必要な確率およびバックオフ重みを見つけることを可能にする、標準フォーマットを提供する。例えば、２つのベンダが２つの別々のバックオフ言語モデルをＡＲＰＡフォーマットで提供した場合、同じコードを使用して両方の言語モデルから確率を決定することができる。
【００４１】
図６に、バックオフ言語モデル用の標準ＡＲＰＡフォーマットのレイアウトの図を提供する。図６で、この標準フォーマットは、ヘッダタグ６００と終了タグ６０２を含む。ヘッダタグ６００の下には、各次数のｎグラムにつき別個のエントリを含むリスト６０４がある。各エントリは、その次数のｎグラムについて言語モデル中に存在するｎグラムの数を示す。例えば、エントリ６０６はｎ１個のユニグラムがあることを示し、エントリ６０８はｎＮ個のＮグラムがあることを示す。
【００４２】
リスト６０４の下にはセクションのセットがあり、各次数のｎグラムにつき１つのセクションがある。各セクションでは、ユニグラムに対するタグ６１０、バイグラムに対するタグ６１２、Ｎグラムに対するタグ６１４など、別々のタグが見出しにあり、Ｎは、言語モデル中のｎグラムの最上次数である。
【００４３】
様々な次数のｎグラムの各見出しの下には、エントリのリストがあり、その次数の各ｎグラムにつき１つのエントリがある。各エントリは、ｎグラムの確率とｎグラムとを含み、最高次数以外の次数のｎグラムの場合は、バックオフ重みも含む。例えば、ユニグラムの見出し６１０の下では、エントリ６１８が、ユニグラム６２０の確率６２２と、バックオフ重み６１６を含む。バックオフ重み６１６は、単語６２０がバイグラムにおけるコンテキストとして使用されるときに単語６２０に関連するものであることに留意されたい。同様に、バイグラム見出し６１２の下のエントリ６２４は、単語ｖ１ｖ２からなるバイグラム６２８のバイグラム確率６２６と、トライグラムのコンテキストとして使用される単語ｖ１ｖ２に関連するバックオフ重み６３０とを含む。通常、確率およびバックオフ重みは、対数の底１０のフォーマットで記憶される。
【００４４】
最高次数ｎグラムの見出し６１４の下のエントリの場合は、バックオフ重みはない。したがって、エントリ６３２では、確率６３４と、ｎグラムｖ１．．．ｖｎ６３６だけがある。
【００４５】
図２を図６と比較すると、図２に示したような補間モデルを図６の標準ＡＲＰＡフォーマットで記憶できることが明確ではない。図７に、本発明の一実施形態による、削除補間モデルを標準ＡＲＰＡフォーマットで記憶する方法の流れ図を提供する。
【００４６】
図７のステップ７００で、削除補間モデルの相対頻度および重みλを決定する。ステップ７０２で、Ｌグラムのセットの最上次数を選択する。Ｌは１とＮの間であり、Ｎは最上次数である。ステップ７０４で、選択された次数のＬグラムを選択し、ステップ７０６で、選択されたＬグラムの相対頻度が０よりも大きいかどうかを判定する。０よりも大きい場合は、式１を使用してＬグラムの補間済み確率を計算し、これをＬグラムの確率として標準フォーマットで記憶する。例えば、図６の最上次数の見出し６１４の下にあるエントリが作成され、確率６３４などの確率はＬグラムの補間済み確率に等しく設定され、Ｌグラム自体は図６のフィールド６３６などのＬグラムフィールド中に配置される。
【００４７】
Ｌグラムの相対頻度が０よりも大きくない場合は、Ｌグラムの確率は標準ＡＲＰＡフォーマットで記憶されない。
【００４８】
ステップ７０８でＬグラムの確率を記憶した後で、またはＬグラムの相対頻度が０よりも大きくないと判定された後で、ステップ７１０で、最上次数について考慮すべきＬグラムが他にもあるかどうかを判定する。考慮すべきＬグラムが他にもある場合は、ステップ７０４に戻り、次のＬグラムを選択する。次いで、この新しいＬグラムに対してステップ７０６および７０８を繰り返す。最上次数のすべてのＬグラムを処理するまで、ステップ７０４、７０６、７０８、７１０を繰り返す。
【００４９】
ステップ７１０でＬグラムの最上次数についてすべてのＬグラムを処理し終えると、ステップ７１２で、処理中のＬグラムの現在次数が０よりも大きいかどうかを判定する。現在処理中のＬグラムの次数が０よりも大きい場合は、ステップ７１４で、次数を１つ減らして次に低い次数に移る。次いでステップ７１６で、この次に低い次数におけるＬグラムを選択する。
【００５０】
ステップ７１８で、選択されたＬグラムの相対頻度を調べて、０よりも大きいかどうかを判定する。０よりも大きくない場合は、ステップ７２０に進み、前にＡＲＰＡファイルに記憶したより高次のＬグラムを調べて、現在のＬグラムがより高次のＬグラムのうちの１つのコンテキストであるかどうかを判定する。ステップ７２０でＬグラムがより高次のＬグラムにおけるコンテキストであることがわかった場合、またはステップ７１８でＬグラムの相対頻度が０よりも大きい場合は、ステップ７２２で、Ｌグラムの補間済み確率をＬグラムの確率としてＡＲＰＡファイルに記憶し、検出された補間モデル中のＬグラムに応じたλを、Ｌグラムに対するバックオフ重みとして記憶する。例えば、λがＬグラムの相対頻度に応じたものである場合、現在のＬグラムの相対頻度に関連するλをバックオフ重みとして記憶する。例えば、Ｌグラムがバイグラムｖ１ｖ２である場合、ｖ１ｖ２の相対頻度に等しい相対頻度を有するバイグラムに関連する重みを、バイグラムｖ１ｖ２に対するバックオフ重みとして使用し、補間済み確率をバイグラムｖ１ｖ２の確率として使用する。
【００５１】
このように、Ｌグラムの相対頻度が０よりも大きい場合すなわちＬグラムが訓練データ中に見られた場合と、Ｌグラムがより高次のＬグラムのコンテキストとして出現する場合には、Ｌグラムを記憶する。本発明のこの実施形態は、記憶するＬグラムをこれらの基準を満たすものだけに限定することによって、バックオフフォーマットによるコンパクトな言語モデルを生み出す。
【００５２】
最初の相対頻度がしきい値未満ならば相対頻度を０に設定することによって相対頻度が決定される場合、Ｌグラムは、訓練テキスト中での相対頻度が０でありながらもコンテキストとして出現する可能性がある。例えば、Ｌグラムの相対頻度が．０２であって、しきい値が．０２に設定されている場合、Ｌグラムの相対頻度は０に設定されることになる。これは、補間モデルのサイズを縮小するために行われる。
【００５３】
相対頻度が０であるにもかかわらずより高次のＬグラムにおけるコンテキストとして出現する場合にＬグラムを記憶する理由は、Ｌグラムがより高次のＬグラムのコンテキストとして出現するので、このコンテキストに対するバックオフ重みが言語モデル中で必要になるからである。
【００５４】
ステップ７２２の後に、またはステップ７１８で現在選択されているＬグラムの相対頻度が０よりも大きくなく、ステップ７２０でより高次のＬグラムのコンテキストして使用されない場合は、ステップ７２４で、現在次数のＬグラムが他にもあるかどうかを判定する。現在次数のＬグラムが他にもある場合は、ステップ７１６で次のＬグラムを選択し、ステップ７１８、７２０、７２２、７２４を繰り返す。選択された次数のすべてのＬグラムを処理するまで、ステップ７１６、７１８、７２０、７２２、７２４を繰り返す。
【００５５】
ステップ７２４で現在次数のＬグラムがそれ以上ないときは、ステップ７１２に戻って、次数が０よりも大きいかどうかを判定する。次数が０よりも大きい場合は、ステップ７１４で次に低い次数を選択し、この新しいより低次のＬグラムに対してステップ７１６〜７２４を繰り返す。ステップ７１２で次数がもはや０よりも大きくないときは、すべての次数のｎグラムの処理が完了しており、図７の方法はステップ７２６で終了する。
【００５６】
このように、図７の方法は、削除補間ｎグラムモデルをＡＲＰＡバックオフ標準フォーマットで表すことができる。これにより、削除補間技法によって形成された言語モデルを、標準ＡＲＰＡフォーマットを受け取ることを予期する言語システムに統合することができる。
【００５７】
本発明を特定の実施形態を参照して述べたが、本発明の趣旨および範囲を逸脱することなく形式および詳細に変更を加えることができることは、当業者なら理解するであろう。
【図面の簡単な説明】
【００５８】
【図１】本発明を実施することのできる一般的なコンピューティング環境のブロック図である。
【図２】従来技術による、削除補間ｎグラム言語モデルのグラフである。
【図３】従来技術による、削除補間ｎグラム言語モデルを訓練するための訓練システムのブロック図である。
【図４】従来技術による、削除補間ｎグラム言語モデルを訓練するための流れ図である。
【図５】従来技術による、バックオフ言語モデルを使用して確率を決定するための流れ図である。
【図６】従来技術による、バックオフ言語モデルを記憶するためのＡＲＰＡ標準フォーマットに関するレイアウトの図である。
【図７】削除補間ｎグラム言語モデルをＡＲＰＡ標準フォーマットで記憶するための流れ図である。
【符号の説明】
【００５９】
１２０  処理ユニット
１３０  システムメモリ
１３４  オペレーティングシステム
１３５  アプリケーションプログラム
１３６  その他のプログラムモジュール
１３７  プログラムデータ
１４０  取外し不可能な不揮発性メモリインタフェース
１４４  オペレーティングシステム
１４５  アプリケーションプログラム
１４６  その他のプログラムモジュール
１４７  プログラムデータ
１５０  取外し可能な不揮発性メモリインタフェース
１６０  ユーザ入力インタフェース
１６１  ポインティングデバイス
１６２  キーボード
１６３  マイクロホン
１７０  ネットワークインタフェース
１７１  ローカルエリアネットワーク
１７２  モデム
１７３  ワイドエリアネットワーク
１８０  リモートコンピュータ
１８５  リモートアプリケーションプログラム
１９０  ビデオインタフェース
１９１  モニタ
１９５  出力周辺インタフェース
１９６  プリンタ
１９７  スピーカ
【図１】
2005293580.tif 000006
【図２】
2005293580.tif 000007
【図３】
2005293580.tif 000008
【図４】
2005293580.tif 000009
【図５】
2005293580.tif 000010
【図６】
2005293580.tif 000011
【図７】
2005293580.tif 000012
【外国語明細書】
2005293580000001.pdf