(57)【要約】  言語の語彙の単語がツリーの葉のところに位置する言語モデル先読みツリーの各ノードにおける先読み確率を計算するシステムであって、第１の低次言語モデルを使用して語彙の単語それぞれに言語モデル確率を割り当てる手段と、第１の言語モデルを使用してツリーのすべてのノードの言語先読み確率を計算する手段と、語彙の１つまたは複数の単語の言語モデル確率を、より高次の言語モデルを使用して計算することができるかどうか判定し、単語をより高次の言語モデルを用いて更新する手段と、言語モデルが更新されている単語による影響を受けるノードにおいてのみ先読み確率を更新する手段とを備えるシステム。
2010540976.tif 000002
【特許請求の範囲】
【請求項１】
言語の語彙の単語がツリーの葉のところに位置する言語モデル先読みツリーのノードにおける先読み確率を計算するシステムであって、
第１の低次言語モデルを使用して前記語彙の前記単語それぞれに言語モデル確率を割り当てる手段と、
前記第１の低次言語モデルを使用して前記ツリーのすべてのノードの前記言語先読み確率を計算する手段と、
前記語彙の１つまたは複数の単語の前記言語モデル確率を、より高次の言語モデルを使用して計算することができるかどうか判定し、前記単語を前記より高次の言語モデルで更新する手段と、
前記言語モデルが更新されている前記単語による影響を受ける前記ノードにおいてのみ前記先読み確率を更新する手段と
を備えるシステム。
【請求項２】
前記より低次の言語モデルを使用して言語モデル確率を割り当てる前記手段は、バックオフパラメータを使用するように構成されている請求項１に記載のシステム。
【請求項３】
前記語彙の１つまたは複数の単語の前記言語モデル確率を、より高次の言語モデルを使用して計算することができるかどうか判定する前記手段は、単語が前に認識された単語と組み合わさって発生しているかどうか判定するように構成されている請求項１に記載のシステム。
【請求項４】
前記より高次のモデルは、バイグラム、トライグラム、フォーグラム、またはより高次のｎグラムモデルである請求項１に記載のシステム。
【請求項５】
マルチキャッシュ構造を有するメモリであり、キャッシュの数がシステムで使用されるｎグラムモデルの次数に等しい前記メモリをさらに備える請求項４に記載のシステム。
【請求項６】
音声を受け取る手段と、
前記音声から音響信号を抽出し、前記音声に含まれる単語の第１の確率を求める手段と、
前記請求項のいずれか１項に記載の言語モデル先読みツリーのノードにおける先読み確率を計算するシステムを備える、前記音声に含まれる前記単語の第２の確率を求めるための言語モデルを提供する手段と、
前記第１の確率と前記第２の確率を組み合わせ、前記受取り音声から認識される前記単語を出力する手段と
を備える自動音声認識システム。
【請求項７】
請求項６に記載の自動音声認識システムと、前記出力される単語を翻訳すべき目的言語に変換する手段とを備える音声−音声翻訳システム。
【請求項８】
スキャンテキストを受け取る手段と、
前記テキストに含まれる単語の第１の確率を求める手段と、
請求項１から５のいずれか１項に記載の言語モデル先読みツリーのノードにおける先読み確率を計算するシステムを備える、前記テキストに含まれる前記単語の第２の確率を求めるための言語モデルを提供する手段と、
前記第１の確率と前記第２の確率を組み合わせ、前記スキャンテキストから認識される前記単語を、コンピュータが読み取ることのできる書式で出力する手段と
を備えるＯＣＲシステム。
【請求項９】
手書きテキストを受け取る手段と、
前記テキストに含まれる単語の第１の確率を求める手段と、
請求項１から５のいずれか１項に記載の言語モデル先読みツリーのノードにおける先読み確率を計算するシステムを備える、前記テキストに含まれる前記単語の第２の確率を求めるための言語モデルを提供する手段と、
前記第１の確率と前記第２の確率を組み合わせ、前記手書きテキストから認識される前記単語を、コンピュータが読み取ることのできる書式で出力する手段と
を備える手書き文字認識システム。
【請求項１０】
言語の語彙の単語がツリーの葉のところに位置する言語モデル先読みツリーのノードにおける先読み確率を計算する方法であって、
第１の低次言語モデルを使用して前記語彙の前記単語それぞれに言語モデル確率を割り当てることと、
前記第１の言語モデルを使用して前記ツリーのすべてのノードの言語先読み確率を計算することと、
前記語彙の１つまたは複数の単語の前記言語モデル確率を、より高次の言語モデルを使用して計算することができるかどうか判定し、前記単語を前記より高次の言語モデルで更新することと、
前記言語モデルが更新されている前記単語による影響を受ける前記ノードにおいてのみ前記先読み確率を更新することと
を備える方法。
【請求項１１】
前記より低次の言語モデル確率を求めることは、バックオフパラメータを使用する請求項１０に記載の方法。
【請求項１２】
前記語彙の１つまたは複数の単語の前記言語モデル確率を、より高次の言語モデルを使用して計算することができるかどうか判定することは、単語が前に認識された単語と組み合わさって発生しているかどうか判定する請求項１０に記載の方法。
【請求項１３】
前記より高次のモデルは、バイグラム、トライグラム、フォーグラムまたはより高次のｎグラムモデルである請求項１０に記載の方法。
【請求項１４】
前記言語モデル先読み確率を前記より低次の言語モデルにリセットすることによって後続の信号を復号することと、
前記語彙の１つまたは複数の単語の前記言語モデル確率を、より高次の言語モデルを使用して計算することができるかどうか判定し、前記単語を前記より高次の言語モデル確率で更新することと、
前記言語モデルが更新されている前記単語による影響を受ける前記ノードにおいてのみ前記先読み確率を更新することと
をさらに備える請求項１０に記載の方法。
【請求項１５】
音声を受け取ることと、
前記音声から音響信号を抽出し、前記音響信号に基づいて前記音声に含まれる単語の確率を求めることと、
請求項１０から１４のいずれか１項に記載の言語モデル先読みツリーのノードにおける先読み確率を計算することを備える言語モデルを提供することと、
前記受取り音声から認識される前記単語を出力することと
を備える自動音声認識の方法。
【請求項１６】
請求項１５に記載の自動音声認識の方法と、前記出力される単語を翻訳すべき目的言語に変換することとを備える音声−音声翻訳の方法。
【請求項１７】
スキャンテキストを受け取ることと、
前記テキストに含まれる単語の第１の確率を求めることと、
請求項１０から１４のいずれか１項に記載の言語モデル先読みツリーのノードにおける先読み確率を計算する方法を備える、前記テキストに含まれる前記単語の第２の確率を求めるための言語モデルを提供することと、
前記第１の確率と前記第２の確率を組み合わせ、前記スキャンテキストから認識される前記単語を、コンピュータが読み取ることのできる書式で出力することと
を備えるＯＣＲの方法。
【請求項１８】
手書きテキストを受け取ることと、
前記テキストに含まれる単語の第１の確率を求めることと、
請求項１０から１４のいずれか１項に記載の言語モデル先読みツリーのノードにおける先読み確率を計算する方法を備える、前記テキストに含まれる前記単語の第２の確率を求めるための言語モデルを提供することと、
前記第１の確率と前記第２の確率を組み合わせ、前記手書きテキストから認識される前記単語を出力することと
を備える手書き文字認識の方法。
【請求項１９】
請求項１０から１８のいずれか１項に記載の方法を実行するようにコンピュータを制御するプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は自動音声認識（automatic speech recognition：ＡＳＲ）の分野に関する。より詳細には、本発明は言語モデル先読み確率を計算する方法および装置に関する。
【背景技術】
【０００２】
言語モデル（language model）ＬＭは、音響的観測から独立したものであり、ＡＳＲにおいて、ある言語における単語が文を構成するためにどのようにして連結されるべきかに関する制約条件を組み込むのに使用される。一般には、ｎ−１個の履歴単語を考慮するｎグラム（n-gram）に基づく言語モデルが使用される。言語モデルを適用するためには完全な単語が必要とされるため、単語が完成される前に言語モデルを適用し始めることを可能にする言語モデル先読み（language model look ahead：ＬＭＬＡ）確率が導入された。
【０００３】
言語モデル先読み（ＬＭＬＡ）は、ｎグラム復号プロセスを加速させることができる。ＬＭＬＡの基本的な考えは、現在の単語ＩＤが未知であるときにＬＭＬＡ確率を言語スコアとして使用するというものである。この技術は、復号プロセスにおけるより効率のよい枝刈り（pruning）につながる。しかし、ＬＭＬＡ確率を生成する計算コストは、従来の方法においては高い。高次のＬＭＬＡ、例えば、トライグラム（trigram）ＬＭＬＡが用いられるとき、探索空間において発生する異なるトライグラムコンテキストの数は、バイグラム（bigram）コンテキストの数と比べて劇的に増大する。この結果、トライグラムＬＭＬＡの計算コストはバイグラムＬＭＬＡよりずっと高くなり、このコストは、この技術の使用による探索空間の縮小によってさえも埋め合わせることができない。この問題を克服するために、ノードベースのＬＭＬＡ確率キャッシュ、ＬＭ確率および完全なハッシングを事前に計算することを含む、いくつかの優れた方法が提示されている。これらの方法の大部分は、どのようにしてＬＭＬＡ確率を効率よくキャッシュに入れ、探索するかに注目したものである。しかし、ＬＭＬＡを生成すること自体が時間のかかるプロセスである。
【発明の概要】
【０００４】
本発明はこの問題に対処するものであり、第１の態様においては、言語の語彙の単語がツリーの葉に位置する言語モデル先読みツリーの各ノードにおける先読み確率を計算するシステムであり、
第１の低次言語モデルを使用して語彙の単語それぞれに言語モデル確率を割り当てる手段と、
第１の言語モデルを使用してツリーのすべてのノードの言語先読み確率を計算する手段と、
語彙の１つまたは複数の単語の言語モデル確率が、より高次の言語モデルを使用して計算することができるかどうか判定し、単語をより高次の言語モデルを用いて更新する手段と、
言語モデルが更新されている単語によって影響を受けるノードにおいてのみ先読み確率を更新する手段と
を備えるシステムを提供する。
【０００５】
本発明では、より低次のＬＭＬＡツリーからより高次のＬＭＬＡ確率を生成する。この方法は、ｎグラムのＬＭの疎性（sparseness）に基づくものである。バックオフベースのＬＭにおいては、単語コンテキスト情報が与えられると、ｎグラム確率のごくわずかな部分だけが明示的に推定され、ｎグラム確率の残りの部分は、バックオフ推定値によって計算される。このことに基づいて、本明細書では、ｎグラムＬＭＬＡツリーの計算を、（ｎ−１）グラムＬＭＬＡツリーから開始する。ｎグラムＬＭＬＡツリーのノードが、計算できなかったために、ｎグラム値が割り当てられていない場合、このノードのＬＭＬＡ確率は、（ｎ−１）グラムＬＭＬＡツリーから直接取得することができる。
【０００６】
この方法を使用すると、バイグラムＬＭＬＡツリーを生成するプロセスを３倍加速させることができ、トライグラムＬＭＬＡツリー生成するプロセスを１２倍加速させることができる。
【０００７】
従来の方法は、ＬＭ確率とＬＭＬＡ確率の計算を２つの独立したプロセスとして扱う。しかし、ＬＭＬＡ確率の計算はＬＭ確率の計算と強い関連性を有する。この関係を利用すれば、ＬＭＬＡ確率の計算を大幅に加速させることができる。
【０００８】
本発明は、統計的言語モデルおよび言語モデル先読みを用いて実行される復号器における言語モデル（ＬＭ）先読み確率の計算回数を低減する。さらに本発明は、ＬＭ先読みのメモリコストも低減する。
【０００９】
ｎグラム言語モデルを考えるときには、単語と先行する単語の出現回数に関する統計情報を照合する必要がある。しかし、このデータは必ずしも利用できるとは限らない。この問題に対処するために、例えば、ある特定の単語について、この単語に利用できるバイグラムデータがないときに、ユニグラム（unigram）モデルからバイグラム確率を推定することを可能にする、バックオフパラメータの概念が導入された。システムは、好ましくは、バックオフパラメータをより低次の言語モデルと共に使用する。システムは、このバックオフパラメータを記憶し、または計算するように構成され得る。
【００１０】
語彙の１つまたは複数の単語の言語モデル確率をより高次の言語モデルを使用して計算することができるかどうか判定するために、システムは、好ましくは、単語が前に認識された単語と組み合わさって出現しているかどうか判定するように構成されている。
【００１１】
より高次のモデルは、好ましくは、バイグラム、トライグラム、フォーグラム（4-gram）、またはより高次のｎグラムモデルである。
【００１２】
好ましい実施形態において、システムは、マルチキャッシュ構造を有するメモリをさらに備え、このメモリのキャッシュの数は、システムにおいて使用されるｎグラムモデルの次数に等しい。
【００１３】
第２の態様において、本発明は、
音声を受け取る手段と、
音声から音響信号を抽出し、音声に含まれる単語の第１の確率を求める手段と、
前述のような言語モデル先読みツリーの各ノードにおける先読み確率を計算するシステムを備える、音声に含まれる単語の第２の確率を求めるための言語モデルを提供する手段と、
第１の確率と第２の確率を組み合わせ、受取り音声から認識される単語を出力する手段と
を備える自動音声認識システムを提供する。
【００１４】
音声を受け取る手段は、マイクロホン、音声の記録などとすることができる。
【００１５】
第３の態様において、本発明は、言語の語彙の単語がツリーの葉に位置する言語モデル先読みツリーの各ノードにおける言語モデル先読み確率を計算する方法であって、
第１の低次言語モデルを使用して語彙の単語それぞれに言語モデル確率を割り当てることと、
第１の言語モデルを使用してツリーのすべてのノードの言語先読み確率を計算することと、
語彙の１つまたは複数の単語の言語モデル確率が、より高次の言語モデルを使用して計算することができるかどうか判定し、単語をより高次の言語モデルを用いて更新することと、
言語モデルが更新されている単語による影響を受けるノードにおいてのみ先読み確率を更新することと
を備える方法を提供する。
【００１６】
好ましくは、より低次の言語モデル確率を求めることは、バックオフパラメータを使用する。
【００１７】
この方法は動的な方法であり、単語を構成するために新しい音響信号が絶えず復号されることが必要になる。新しいＬＭＬＡツリーが必要とされる場合、このツリーは、
言語モデル先読み確率をより低次の言語モデルにリセットし、
語彙の１つまたは複数の単語の言語モデル確率を、より高次の言語モデルを使用して計算することができるかどうか判定し、単語をより高次の言語モデル確率を用いて更新し、
言語モデルが更新されている単語により影響を受けるノードにおいてのみ先読み確率を更新する
ことによって構築することができる。
【００１８】
ＬＭＬＡツリーは、受け取られる音響ベクトルごとに更新される必要はない。例えば、新しいＬＭコンテキストを生じることにならない新しいベクトルが求められ、またはこのコンテキストのＬＭＬＡツリーがキャッシュ内で見つけることができる場合には、ＬＭＬＡを更新する必要は生じない。
【００１９】
第４の態様において、本発明は、
音声を受け取ることと、
音声から音響信号を抽出し、音響信号に基づいて音声に含まれる単語の確率を求めることと、
前述のように言語モデル先読みツリーの各ノードにおける先読み確率を計算することを備える言語モデルを提供することと、
受取り音声から認識される単語を出力することと
を備える自動音声認識方法を提供する。
【００２０】
この説明は音声認識を中心としたものになるが、本発明は、音声−音声翻訳、ＯＣＲ、手書き文字認識、または統計的言語モデル情報を使用した他の動的プログラミング探索にも適用され得ることが、当業者には理解されるであろう。システムはＤＮＡゲノム配列決定にさえも適用され得る。
【００２１】
本発明は、ハードウェアとしても、汎用コンピュータ内のソフトウェア上でも実施することができる。さらに本発明は、ハードウェアとソフトウェアの組み合わせとして実施することもできる。また本発明は、単一の処理装置によって実施することもでき、処理装置の分散ネットワークによって実施することもできる。
【００２２】
本発明はソフトウェアによって実施され得るため、本発明は、任意の適切な搬送媒体で汎用コンピュータ提供されるコンピュータコードを包含するものである。搬送媒体には、フロッピー（登録商標）ディスク、ＣＤ−ＲＯＭ、磁気装置、プログラマブル・メモリ・デバイスといった任意の記憶媒体、または、電気的信号、光学的信号、マイクロ波信号などの任意の信号といった任意の過渡的媒体が含まれ得る。
【図面の簡単な説明】
【００２３】
【図１】図１は、ＡＳＲの探索空間を示す概略図である。
【図２】図２は、単語ネットワークを示す概略図である。
【図３】図３は、単語ネットワークとバイグラムＬＭとに基づく探索空間を示す概略図である。
【図４】図４は、ＬＭ先読み確率ツリーを示す概略図である。
【図５】図５は、従来技術の方法に従って言語モデル先読み確率を計算する際の各ステップを示す図である。
【図６】図６は、本発明の一実施形態に従って言語モデル先読み確率を計算する際の各ステップを示す図である。
【図７】図７は、マルチキャッシュ構造に基づくトライグラムＬＭＬＡを示す図である。
【図８】図８は、ＬＭＬＡを使用する信号処理のための一般的なシステムを示す概略図である。
【発明を実施するための形態】
【００２４】
次に本発明を、以下の非限定的な好ましい実施形態を参照して、より詳細に説明する。
【００２５】
自動音声認識（ＡＳＲ）の間、認識されるべき音声は、まずディジタル化され、次に、音声のスペクトル領域内容を表す特徴が計算される。これらの特徴を認識システムの語彙内の単語と照合するためには、２種類の確率分布が使用される。これらの一方は、上記特徴から導出される音響ベクトルを発話されている単語と一致させる確率を表す音響−音声または音響モデルであり、他方は言語モデルである。言語モデルは、音響的観測から完全に独立したものであり、文全体を構成するために語彙の単語をどのようにして連結するべきかに関する制約条件を組み込むのに使用される。
【００２６】
本発明は言語モデルに関連するものである。しかし、本発明の背景として、まず、ＡＳＲの一般的説明を行う。
【００２７】
本明細書で使用する場合、「単語」という語は統計的言語モデルの基本単位を表す。「単語」に関連して、単語列、サブワード列、および辞書の概念は以下のとおりである。
【００２８】
ａ．単語列
ｉ．復号の一般的問題は、入力信号に含まれる「単語」の列を見つけることである。「単語」は、言語モデル（ＬＭ）における統計的単位の列である。
【００２９】
ｉｉ．単語の列は、ｎグラムモデルと呼ばれる統計的ＬＭによってモデル化することができ、ｎグラムモデルは、最も新しいｎ−１個の履歴単語を使用して現在の単語の確率を計算する。単語の列ｗ１ｗ２…ｗＫがあるものと仮定すると、ｎグラムモデルに基づいて、ｗ１ｗ２…ｗＫの確率は以下のように計算することができる。
【数１】
2010540976.tif 000003
【００３０】
式１において、単語履歴ｗｉ−ｎ＋１…ｗｉ−１は、ｉ＝１のときはＰ（ｗ１）とし、ｉ≧２かつｉ−ｎ＋１＜１である場合、Ｐ（ｗｉ｜ｗ１…ｗｉ−１）とする。
【００３１】
ｂ．サブワード列
本特許において考慮される復号タスクでは、各単語は１つまたは複数のサブワード単位、例えば、音声における単音、ＯＣＲなどにおける文字、「ｓａｔ／ｓ  Ａ  ｔ／，ｓａｎｇ／ｓ  Ａ  ｎ  ｇ／」などとして表すことができる。
【００３２】
ｃ．辞書
発音辞書は、探索空間における単語集合の一般的表現であり、多くの場合、単語ネットワークによって表され、単語ネットワーク内の各パスは単語のサブワード列を表す。広く使用されている単語木は、単語ネットワークの特殊例である。
【００３３】
復号の主要タスクは、膨大な探索空間の中から最も高い尤度を有する単語列を選択することである。隠れマルコフモデル（Hidden Markov Model：ＨＭＭ）ベースの大語彙連続音声認識（Large Vocabulary continuous speech recognition：ＬＶＣＳＲ）では、復号問題は、音響特徴列が与えられたとすると、辞書、音響モデルおよび言語モデル情報を組み合わせること、ならびに、（最大事後尤度を有する）最善のパスを、すなわち、各ノードがＨＭＭ状態を所与の時刻と対応付ける格子探索空間（trellis search space）から最善のＨＭＭ状態列を見つけることである。図１に、ＡＳＲの探索空間の一例（ＮｅｙおよびＯｒｔｍａｎｎｓ、２０００年）を示す。
【００３４】
図２に単語ネットワークを示す。効率よくするために、ＡＳＲの発音辞書は普通、各弧（ａｒｃ）が音素モデルを表す単語ネットワークとして編成される。音素モデルは、コンテキスト依存とすることも、コンテキスト独立とすることもできる。広く使用されている発音プレフィックスツリーは、単語ネットワークの特殊例である。
【００３５】
図３に、Ｈ．ＮｅｙおよびＳ．Ｏｒｔｍａｎｎｓ著、「ＬＶＣＳＲのための動的プログラミング探索の進展」、ＩＥＥＥ会報、２０００年８月、１２２４〜１２４０頁（H. Ney and S. Ortmanns, "Progress in Dynamic Programming Search for LVCSR", Proceedings of the IEEE, August 2000, pp1224-pp1240）に記載されているＡＳＲの探索空間の概略図を示す。図３において、単語ネットワークは３つの単語Ａ、Ｂ、Ｃと無音を含む。各フレームｔにおいて、同じ単語で終わるすべての仮説が再結合され、対応する単語履歴と共に新しい単語ネットワークに伝播される。
【００３６】
音響特徴列が与えられたとすると、復号の原理は、
【数２】
2010540976.tif 000004
【００３７】
で表すことができ、式中、ｗ１Ｋは探索空間内の単語列であり、ｘ１Ｔはフレーム１からフレームＴまでの音響特徴列であり、ｓ１Ｔはフレーム１からフレームＴまでのＨＭＭ状態列である。ＳＬＭ情報を用いた時間同期ビタビ復号では、フレームｔごとに、動的プログラミングプロセスを、単語内のプロセスと、この単語の境界におけるプロセスの２つの部分に分割することができる。バイグラム復号が用いられる場合、単語内のプロセスは以下のように表すことができる。
【数３】
2010540976.tif 000005
【００３８】
式中、Ｑｖ（ｔ，ｓ）は、先行要素ｖを有する単語ネットワークの状態ｓにおいて時刻ｔに終わる最善の部分パスのスコアであり、システムはＱｖ（ｔ，ｓ）を使用して仮説を伝播する。Ｂｖ（ｔ，ｓ）は、先行要素ｖを有する単語ネットワークの状態ｓにおいて時刻ｔに終わる最善の部分パスにおける最後の履歴単語の終了時刻であり、システムは、Ｂｖ（ｔ，ｓ）を使用してトレースバック情報を記憶する。ｓｖｍａｘ（ｔ，ｓ）は、仮説（ｔ，ｓ）および先行要素ｖについての最適先行要素状態である。
【００３９】
単語の境界においては、部分パスの総スコアにＬＭスコアが加えられる必要があり、次いで、時刻ｔに単語ｗとして終わるすべての仮説が再結合される必要がある。すなわち、以下のとおりである。
【数４】
2010540976.tif 000006
【００４０】
式中、Ｓｗは単語ネットワークにおける単語ｗの最後の状態である。ＬＭスコアが加えられた後、新しいスコアを使用して、次のステップの動的プログラミングプロセスが実行される。すなわち、以下のとおりである。
【数５】
2010540976.tif 000007
【００４１】
スコアの小さい仮説は枝刈りによって除去される。枝刈りの手法には、音響ビーム枝刈り、言語モデルビーム枝刈りおよびヒストグラム枝刈りなどが含まれる。フレームｔごとに、音響ビーム枝刈りでは、最善の状態仮説を選択し、最善のスコアに近いスコアを有する仮説だけが保持され、すなわち、
【数６】
2010540976.tif 000008
【００４２】
であり、状態仮説（ｔ，ｓ，ｖ）は、
【数７】
2010540976.tif 000009
【００４３】
の場合除去され、式中、ｆＡＣは枝刈り閾値である。
【００４４】
言語モデル枝刈りは、現在のフレームｔにおいて単語境界に到達する仮説にだけ適用される。これは以下のように示すことができる。
【数８】
2010540976.tif 000010
【００４５】
単語境界における仮説（ｔ，ｓ＝０，ｖ）は、
【数９】
2010540976.tif 000011
【００４６】
の場合除去される。
【００４７】
前述のように、本発明は言語モデル、より具体的には、ＬＭ先読み技術に関連するものである。
【００４８】
前述の復号アルゴリズムは辞書単語ネットワークに基づくものであり、辞書単語ネットワークでは、他の単語と共用されない最初の弧に到達するまでシステムが単語ＩＤを取得することができない。したがって、単語ＩＤは普通、辞書単語ネットワークの末尾の近くに位置する。言語モデルは、単語をどのようにして連結すべきかに関する制約条件を提供するものであるため、単語ＩＤが検出されるとき、ごく後の方で言語モデルを復号プロセスに組み込むことができる。
【００４９】
しかし、ＬＭスコアを可能な限り早く導入するために、Ｓ．Ｏｒｔｍａｎｎｓ、Ｈ．ＮｅｙおよびＡ．Ｅｉｄｅｎ著、「大語彙音声認識のための言語モデル先読み」、音声言語処理国際会議会議録、米国ペンシルバニア州フィラデルフィア、１９９６年１０月、２０９５〜２０９８頁（S. Ortmanns, H. Ney and a. Eiden, "Language-Model Look-ahead for Large Vocabulary Speech Recognition ", in Proc. Int. Conf. Spoken Language Processing, Philadelphia, PA, Oct. 1996, pp2095-pp2098）には、ＬＭ先読み技術が記載されている。
【００５０】
ＬＭコンテキストが与えられたとすると、ＬＭ先読みネットワーク内のノードごとに、ＬＭ先読み確率は、この特定のノードから到達することのできるすべての単語にわたる最大ＬＭ確率として定義される。すなわち、
【数１０】
2010540976.tif 000012
【００５１】
であり、式中、Ｗ（ｎ）はノードｎから到達することのできる単語の集合を表す。
【００５２】
ＬＭ先読みの基本的な考え方は、ＬＭ先読み確率を動的プログラミング手順に組み込んでより効率のよい枝刈りを実現するというものである。ＬＭ先読み技術を用いない場合、ある単語内の仮説のスコアは、現在の単語ＩＤが知られていないため、現在の単語のＬＭスコアを含まない。ＬＭ先読みが使用されるときには、ＬＭ先読み確率が仮説の本来のスコアに組み込まれ、これらの新しいスコアに基づいて枝刈りが実行される。
【００５３】
図４はＬＭ先読み確率ツリーの図である。ＬＭ先読みネットワークは、例えば、図２に示す種類などの単語ネットワークのコピーである。図４のＬＭ先読みツリーでは、特定のＬＭコンテキストが与えられた場合、あらゆるノードはこれのＬＭ先読み確率を含む。ＬＭ先読みネットワークは、ただ１つの後続ノードしかないすべてのノードを除去することによって圧縮することができる。
【００５４】
ＬＭ先読み確率を計算する従来の方法は、動的プログラミング手順を用いる。最初に、ＬＭ先読みネットワークにおける葉ノードのＬＭ先読み確率が、異なる単語の実際のＬＭ確率として割り当てられる。というのは、ＬＭ先読みネットワーク内のあらゆる葉ノードが１つの個別の単語に対応するからである。次いで、個別ノードごとに、ＬＭ先読み確率が、このノードの後続ノードの最大ＬＭ先読み確率によって決まる。ＬＭ先読みネットワーク全体のＬＭ先読み確率は、下から上まで再帰的に計算することができる。すなわち以下のとおりである。
【数１１】
2010540976.tif 000013
【００５５】
式中、ｓ（ｎ）はノードｎの後続ノードの集合である。
【００５６】
通常、ＬＭ先読み確率は、復号プロセスの間にオンラインで生成される必要がある。したがって、ＬＭ先読み確率を計算する際の効率は、復号速度に大きく影響する。動的プログラミング手順は、ＬＭ先読み確率を計算する効率のよいやり方を提供するが、過大な計算回数が生じる。
【００５７】
図５に、ＬＭ先読み確率の計算を示す。この計算は２つの部分に分かれており、第１の部分が図５ａに、第２の部分が図５ｂに示されている。第１の部分は、単語のｎグラムモデル確率など、ＬＭコンテキストに基づく語彙内のあらゆる単語のＬＭ確率を計算することである。第２の部分は、ＬＭ先読みネットワーク内の各ノードに、各ノードごとに特定のノードから到達することのできるすべての単語のＬＭ確率を合計することによってＬＭ先読み確率を割り当てることである。
【００５８】
ＬＭ先読み確率は、動的プログラミング手順によって割り当てられる。語彙がＶ個の単語を含み、ＬＭ先読みネットワークはＭ個のノードを含むと仮定する。これは、探索空間において発生する各ＬＭ履歴に、ＬＶＣＳＲシステムは、ステップ１においてＶ個の確率を探索し、ステップ２においてＭ個の先読み確率を生成する必要があることを意味する。ＶおよびＭの値は、ＬＶＣＳＲシステムにおいてはきわめて大きい。通常、１つの文の認識プロセスの間に、探索空間においては数百個のバイグラムコンテキストおよび数千個のトライグラムコンテキストが発生する。より高次のｎグラム、例えば、フォーグラムでは、探索空間内のＬＭコンテキストの数は一層大きくなる。ＬＭコンテキストごとに、前述のＬＭ確率計算が実行される必要がある。したがって、従来の方法を使用してＬＭ先読み確率を計算するとＣＰＵコストが高い。
【００５９】
一方、探索空間において発生するＬＭ先読み確率がキャッシュされる場合、ＬＭ先読みネットワークがＭ個のノードを含み、探索空間においてＮ個の異なるＬＭコンテキストが発生するものと仮定すると、合計で、Ｍ×Ｎ個のＬＭ確率を記憶させる必要が生じる。ＬＶＣＳＲシステムにおいて、高次のｎグラム復号が使用されるときには、ＭもＮも大きくなり、したがって、ＬＭ先読みを実行するメモリコストも高い。
【００６０】
図６に、本発明の一実施形態によるＬＭ先読み確率を計算する方法を概略的に示す。
【００６１】
この実施形態では、低次のＬＭ先読み情報を使用して、より高次のＬＭ先読みの計算が低減される。図５を参照して示した方法は、低次のＬＭ先読み情報を利用せず、ＬＭ先読みネットワーク内の各ノードにＬＭ先読み確率を割り当てる必要がある。
【００６２】
本発明の一実施形態による方法では、ノードの小部分集合におけるＬＭ先読み確率を更新しさえすれはよく、ＬＭ先読みネットワーク内のノードの大部分については、これらのノードのＬＭ先読み確率を低次のＬＭ先読みネットワークから直接コピーすることができる。
【００６３】
このバックオフベースのｎグラムモデルは、以下のように表すことができる。
【数１２】
2010540976.tif 000014
【００６４】
式中、ｆ（・）は、ｎグラムファイルから読み取られる割り引かれたＬＭ確率であり、Ｃ（・）は、学習コーパスにおいて発生する事象の頻度であり、Ｂａｃｋｏｆｆ（ｈ）は、全てのｗについてＰ（ｗ｜ｈ）の和が１になるように定められる、履歴ｈに対するバックオフパラメータであり、ｈ’はｈのより低次の履歴を表す。
【００６５】
式１２は、ｎグラムデータにおいて履歴単語対が見つからないときに、より低次のモデルがバックオフ推定値として使用されることを示している。実際には、大語彙の適用例では、履歴ｈが与えられた場合、訓練データにおいて見つかる異なる履歴単語対の数が語彙Ｖのサイズよりずっと小さくなる。これは、単語履歴ｈごとに、ｎグラム確率の大部分がバックオフ推定値によって与えられることを意味する。この現象を使用して、言語モデル化における計算を加速させることができる。
【００６６】
ｎグラム言語モデルを考えるときには、ある単語と先行する単語の出現回数に関する統計情報を照合する必要がある。しかし、このデータは必ずしも利用できるとは限らない。この問題に対処するために、例えば、ある特定の単語に利用できるバイグラムデータがないときに、この単語のユニグラムモデルからバイグラム確率を推定することを可能にする、バックオフパラメータの概念が導出された。例えば、図６の実施形態において、バックオフパラメータは以下のように計算される。
【００６７】
ｎグラムのＬＭは以下のように計算することができる。
【数１３】
2010540976.tif 000015
【００６８】
これは、確率として、
【数１４】
2010540976.tif 000016
【００６９】
を満たさなければならない。
【００７０】
式ａによれば、式ｂは、
【数１５】
2010540976.tif 000017
【００７１】
と書き換えることができる。
【００７２】
よって、バックオフパラメータは次式から計算することができる。
【数１６】
2010540976.tif 000018
【００７３】
バックオフパラメータは、事前に計算し、記憶させることができる。
【００７４】
ノードｎにおけるＬＭ先読みの定義は、ｎから到達することのできるすべての単語にわたる最大ＬＭ確率であり、これは以下のように表すことができる。
【数１７】
2010540976.tif 000019
【００７５】
式中、Ｗ（ｎ）は、ノードｎから到達することのできる単語の集合をあらわす。
【００７６】
式（１２）によれば、ＬＭ先読みの定義は以下のように書き換えることができる。
【数１８】
2010540976.tif 000020
【００７７】
式中、
【数１９】
2010540976.tif 000021
【００７８】
であり、
【数２０】
2010540976.tif 000022
【００７９】
である。
【００８０】
したがって、ＬＭＬＡツリー内の各ノードは２つの部分に分割することができる。すなわち以下のとおりである。
【数２１】
2010540976.tif 000023
【００８１】
単語履歴ｈが与えられたとすると、明示的なｎグラム推定値を使用して、Ｎ１に関連するＬＭＬＡ確率だけが計算されればよく、Ｎ２に関連するＬＭＬＡ確率の残りの部分は、バックオフ推定値を使用して計算される。
【００８２】
上記分析に基づき、ＬＭＬＡ確率を計算する新しい方法が提示される。
【００８３】
上記分析によれば、ＬＭ先読みの計算を４つのステップに分割することができる。
【００８４】
ステップ１：低次のＬＭ先読みネットワークＴを生成する。Ｔにおける各ノードｎに、
【数２２】
2010540976.tif 000024
【００８５】
とする。
【００８６】
ステップ２：低次のＬＭ先読み確率に履歴ｈのバックオフパラメータを掛けて、新しいＬＭ先読みネットワーク（ツリー）、
【数２３】
2010540976.tif 000025
【００８７】
を生成する。
【数２４】
2010540976.tif 000026
【００８８】
における各ノードｎに、
【数２５】
2010540976.tif 000027
【００８９】
とする。
【００９０】
ステップ３：学習コーパスにおいてＬＭコンテキストｈと共に発生した各単語ｗに、
【数２６】
2010540976.tif 000028
【００９１】
の葉ノードにおけるバックオフＬＭ確率を、ｎグラムモデルにおける割り引されたＬＭ確率で置き換える。すなわち、Ｃ（ｈ，ｗ）＞０の場合、ｆ（ｗ｜ｈ）を使用して、
【数２７】
2010540976.tif 000029
【００９２】
におけるｆ（ｗ｜ｈ’）＊ｂａｃｋｏｆｆ（ｈ）を置き換える。
【００９３】
ステップ４：Ｗ＝｛ｗ｜Ｃ（ｈ，ｗ）＞０｝内の各単語ｗに、動的プログラミング手順を使用して、そこからｗに到達することのできるノードにおけるＬＭ先読み確率を更新する。
【００９４】
図６には、この新しい方法に基づくＬＭＬＡ確率の計算が示されている。図６ａにはステップ１および２が示され、図６ｂにはステップ３および４が示されている。ＬＭＬＡ確率を計算する新しい方法は、バックオフＬＭＬＡツリーから開始する。図６のＬＭＬＡツリーは、８枚の葉、すなわち８個の個別単語を含む。ＬＭコンテキストｈが与えられた場合、ただ２つの単語ｗ１およびｗ３だけが明示的なＬＭ確率を有するものと仮定すると、この新しい方法では、そこからｗ１およびｗ３に到達することのできるノード、すなわち図６の黒いノードにおけるＬＭＬＡ確率を計算しさえすればよく、ＬＭＬＡ確率の残りの部分、すなわち、グレーのノードにおけるＬＭＬＡ確率は、バックオフＬＭＬＡツリーから直接コピーすることができる。
【００９５】
この実施形態の方法は、旧い方法のようにあらゆるノードを更新するのではなく、ＬＭ先読みツリーにおけるノードの部分集合、すなわち、式１７のＮ１に属するノードだけを計算することによって、ＣＰＵコストを著しく低減する。個々のＬＭコンテキストｈについて、単語集合Ｗ＝｛ｗ｜Ｃ（ｈ，ｗ）＞０｝は、全認識語彙よりずっと小さい。したがって、Ｎ１内のノードは、ＬＭ先読みツリー内のノードの小部分集合にすぎない。
【００９６】
よって、トライグラム先読み確率などの高次のＬＭ先読み確率をきわめて効率よく計算することができる。従来の方法では、探索空間において発生したＬＭ先読みネットワークをキャッシュするのに１つのバッファを保持し、このため、これらのＬＭ先読みネットワークを後で再利用することができる。提案の方法では、ｎグラムＬＭ先読み確率を計算するために、ｎグラム先読みネットワークのみならず、（ｎ−１）グラム先読みネットワークもキャッシュに入れる必要がある。ｎグラム先読み確率が計算される前に、必要とされるｎグラム先読みネットワークがすでにｎグラム先読みバッファにキャッシュされているかどうかがチェックされる。キャッシュされていない場合、対応する（ｎ−１）グラムの先読みネットワークが（ｎ−１）グラム先読みバッファにおいて探索される。次いで、提案の方法を使用して、（ｎ−１）グラム先読みネットワークからｎグラム先読みネットワークが生成される。（ｎ−１）グラム先読みネットワークが計算されるときにも類似の動作が実行される。すなわち、（ｎ−１）グラム先読みネットワークを生成するには（ｎ−２）グラム先読みネットワークがキャッシュされる必要がある。この動作は反復して実行され、より高次の先読みネットワークを生成するために、より低次の先読みネットワークが常にキャッシュに入れられる
この実施形態の方法を使用すれば、ＬＭ先読み確率を計算するＣＰＵコストを著しく低減することができる。
【００９７】
従来の方法では、ＬＭ先読みツリーにおける各ノードに、対応するＬＭ先読み確率が計算される必要がある。
【００９８】
提案の方法では、ＬＭ先読み確率が更新される必要のあるノードは、ＬＭ先読みツリーのノードのごく一部でしかない。Ｎｏｄｅ（ｗ）を、そこから単語ｗに到達することのできるノードの集合として定義すると、ＬＭ先読み確率が更新される必要のあるＬＭ先読みネットワーク内のすべてのノードは、以下のように表すことができる。
【数２８】
2010540976.tif 000030
【００９９】
個々のＬＭコンテキストｈについて、単語集合Ｗ＝｛ｗ｜Ｃ（ｈ，ｗ）＞０｝
は全認識語彙よりずっと小さい。したがって、集合Ｎ内のノードの数は、ＬＭ先読みネットワーク内のノードの総数よりずっと少ない。
【０１００】
また、この実施形態の方法は、メモリコストも低減することができる。一見したところ、提案の方法は、より高次の先読みネットワークとより提示の先読みネットワークの両方をキャッシュに入れる必要があり、メモリコストが高い。しかし、より低次の先読みネットワークをキャッシュするためのバッファのサイズは、より高次の先読みネットワークをキャッシュするためのバッファのサイズよりずっと小さい。他方、提案の方法は、従来の方法よりずっと高速であり、したがって、最の頻度の高い先読みネットワークをキャッシュしさえすればよく、残りのより頻度の低い先読みネットワークは、要求に応じて、余り大きなＣＰＵコストをかけずに生成することができる。最の頻度の高い先読みネットワークは、探索空間において発生するすべての先読みネットワークと比べて、メモリのわずかな部分しか占めないため、提案の方法は、実際には、メモリコストを低減する。
【０１０１】
さらに、従来の方法は、探索空間内のすべてのＬＭ先読みネットワークをキャッシュに入れる。提案の方法では、ｎグラムコンテキストごとに、システムは、このコンテキストに基づくｎグラム確率が実際にモデルに存在するかどうかチェックすることができる。特定のｎグラムコンテキストのｎグラム確率が記憶されていない場合、このコンテキストに関連するｎグラム先読みネットワークは記憶される必要がなく、（ｎ−１）グラム先読みネットワークが直接使用される。したがって、本発明の実施形態による方法では、記憶されるｎグラム先読みネットワークをさらに低減することができる。
【０１０２】
１．この実施形態の方法は、ＬＭ先読み確率の計算を著しく加速させる。
【０１０３】
２．この実施形態の方法は、トライグラムまたはより高次のｎグラム先読みのメモリコストを低減することができる。
【０１０４】
この実施形態の方法では、より高次のＬＭＬＡ確率の計算はより低次のＬＭＬＡ確率の値に依存し、高次のＬＭＬＡを実施するためのマルチキャッシュ構造が設計されている。システムによって保持されるキャッシュの数は、復号器によって用いられるＬＭの次数と同じである。各次数のＬＭＬＡ確率のキャッシュがある。要求されるＬＭＬＡツリーは、これがキャッシュに存在しない場合、低次のＬＭＬＡキャッシュからの対応するバックオフツリーを使用して生成される。
【０１０５】
図７に、マルチキャッシュに基づくトライグラムＬＭＬＡの枠組みを示す。マルチキャッシュ構造に基づき、トライグラムＬＭＬＡは５つのステップに分割することができる。
【０１０６】
ステップ１：復号器は、ＬＭＬＡスコアリングモジュールにノードｎのＬＭＬＡスコアおよび単語履歴ｗｊｗｉを要求し、ＬＭＬＡスコアリングモジュールは、要求されたＬＭＬＡ確率がすでにトライグラムＬＭＬＡキャッシュにあるかどうかチェックし、キャッシュにある場合、ＬＭＬＡ確率が返され、そうでない場合、ステップ２に進む。
【０１０７】
ステップ２：バイグラム単語履歴ｗｉを使用して、バイグラムＬＭＬＡバイグラムＬＭＬＡキャッシュが探索され、ｗｉのＬＭＬＡバッファがすでにキャッシュにある場合、ステップ４に進み、そうでない場合、ステップ３に進む。
【０１０８】
ステップ３：ユニグラムＬＭＬＡバッファを使用して、ｗｉのバイグラムＬＭＬＡが生成され、キャッシュされる。
【０１０９】
ステップ４：ｗｉのバイグラムＬＭＬＡバッファを使用して、ｗｊｗｉのトライグラムＬＭＬＡバッファが生成され、キャッシュされる。
【０１１０】
ステップ５：要求されたＬＭＬＡ確率が復号器に返される。
【０１１１】
図６の方法が、ＷＳＪ（Ｗａｌｌ  Ｓｔｒｅｅｔ  Ｊｏｕｒｎａｌ）の２万単語を語彙とするシステムを有するトライグラムＬＭＬＡと共に使用された。訓練音声はＷＳＪ０およびＷＳＪ１コーパス、ＳＩ２８４訓練集合である。この語彙は、言語データコンソーシアム（Linguistic Data Consortium：ＬＤＣ）によって提供される約２０ｋの単語を有する閉じた語彙である。音響モデルは、１状態当たり１０個のガウス混合成分を有する６０００個の連結ＨＭＭ状態を含む。音声特徴ベクトルは３３次元であり、１０次元Ｃ−ＭＦＣＫＬ、１次元の対数エネルギー、ならびにこれらの１次および２次の時間微分を含む。ＬＭは、約４千万語を有するＷＳＪ８７〜８９テキストコーパスによって訓練されたトライグラム言語モデルである。
【表１】
2010540976.tif 000031
【０１１２】
表１には、同じビーム幅に基づく異なる構成でのＬＭＬＡのＣＰＵコストが示されている。本明細書で提案する方法は、ＬＭＬＡ確率の計算コストを大幅に低減したことが示されている。バイグラムＬＭＬＡツリーを生成する処理は３倍加速され、トライグラムＬＭＬＡツリーを生成する処理は１２倍加速される。トライグラムＬＭＬＡが使用されるとき、探索空間において発生する異なるトライグラムコンテキストの数は、バイグラムコンテキストの数よりずっと多くなる。旧来の方法では、トライグラムＬＭＬＡの利益はＬＭＬＡによってもたらされる余分の計算を埋め合わせることができず、システムはバイグラムＬＭＬＡシステムよりいっそう低速になる。他方、新しい方法は従来の方法よりＬＭＬＡ確率をずっと高速に計算するため、新しい方法が使用されるとき、トライグラムＬＭＬＡは、バイグラムＬＭＬＡと比べて、システムをさらに加速させる。
【０１１３】
表２に、新しい方法に基づくトライグラムＬＭＬＡおよびバイグラムＬＭＬＡの性能を示す。同じＷＥＲを達成する際に、トライグラムＬＭＬＡに基づく復号は常に、バイグラムＬＭＬＡを用いた復号より高速である。トライグラムは高速復号に際してより効率がよく、ビーム幅が１６０であるとき、トライグラムＬＭＬＡのＷＥＲはバイグラムＬＭＬＡより１％優れ、ビーム幅が２００に増大されると、この差は０．３％まで下がる。
【０１１４】
第４項で述べたように、新しい方法でのトライグラムＬＭＬＡは、トライグラムＬＭＬＡ確率がバイグラムＬＭＬＡ確率から生成され、バイグラムＬＭＬＡ確率がユニグラムＬＭＬＡ確率から生成されるマルチキャッシュ構造に基づくものである。表３に、ＷＳＪ２０ｋタスクにおける評価データの１つに基づく異なる次数のＬＭＬＡの計算量を示す。３倍多いトライグラムＬＭＬＡツリーが生成される場合でさえも、トライグラムＬＭＬＡは１．２６％のＣＵＰコストしか占めず、他方バイグラムＬＭＬＡは、７．６３％のＣＰＵコストを占めることが示されている。これは主に、トライグラムデータの疎性によるものである。トライグラムデータは、バイグラムデータと比べて非常に疎であり、トライグラムＬＭＬＡにおいて更新されるべきノードはバイグラムＬＭＬＡにおいて更新されるべきノードよりずっと少ない。したがって、計算コストの大部分は、呼び出される頻度が低くても、バイグラムＬＭＬＡによるものである。
【表２】
2010540976.tif 000032
【０１１５】
【表３】
2010540976.tif 000033
【０１１６】
前述のように、本発明は、言語モデルと併せた入力信号の動的処理が必要とされる同類のシステムにも適用され得る。図８に、入力信号が入力ユニット１において提供される基本システムを示す。ユニット１からの出力は次いでユニット３に供給され、そこで、入力信号における可能性の高い単語の第１の確率分布を生成することのできる音響モデルまたは他のモデルが決定される。例えば、音声認識に際して、このユニットは、音響−音声モデルを提供するはずである。ユニット５は、言語において各単語がどのようにして連結され得るかに関する制約条件を組み込んだ言語モデルを提供する。言語モデルと音響モデルユニット３の間にはやり取りが生じ得る。最後に、復号器７は出力を生成し、この出力は、音声認識の場合には、単語になる。
【０１１７】
システムは、音声−音声翻訳システムの一部とすることができ、音声−音声翻訳システムにおいて、出力は、さらに変換され、ＴＴＳシステムなどを使用して音声として出力される。
【０１１８】
また、システムはＯＣＲに使用することもでき、ＯＣＲでは、入力１における入力が音声ではなくスキャンテキストになり、ユニット３は、音響モデルを提供するのではなく、スキャンテキスト内に位置する単語の確率を出力する。言語モデル５は、前述のやり方と同様に動作する。復号器７は、コンピュータが、単語処理などにおいて使用するために読み取り、操作することのできるテキストを出力する。同様にシステムは、入力が手書きテキストであり、ユニット３が手書きテキストを復号する手書き入力分析にも適用することができる。この場合もやはり、言語モデルは、前述のやり方と同様に動作する。
【０１１９】
最後に、このシステムは、例えばＤＮＡゲノム配列決定などにおける、特殊な言語モデルにも使用され得る。
【図１】
2010540976.tif 000034
【図２】
2010540976.tif 000035
【図３】
2010540976.tif 000036
【図４】
2010540976.tif 000037
【図５】
2010540976.tif 000038
【図６】
2010540976.tif 000039
【図７】
2010540976.tif 000040
【図８】
2010540976.tif 000041
【国際調査報告】
2010540976.tif 000042
2010540976.tif 000043
2010540976.tif 000044