(57)【特許請求の範囲】
【請求項１】
少なくとも１つの中央処理装置（ＣＰＵ）及び少なくとも１つのグラフィック処理装置（ＧＰＵ）を備える演算プラットホームを用いて、音声認識に利用されるグラフ探索についてコンピュータで実施される統計的推測方法において、
尤度を初期化する工程と、
入力信号について、一まとまりの音声を含んでいるサンプルをキャプチャする工程と、
サンプルからサンプル特徴を演算する工程と、
ＧＰＵを用いて、音声モデル及び言語モデルの少なくとも一方に基づいてサンプル特徴の各々について観測尤度を演算する工程と、
ＧＰＵを用いて、過去のタイムステップにおけるサンプル特徴及び尤度の各々について、観測尤度に基づいて尤度をアップデートして、一組の部分的仮説を作成する工程であって、一組の部分的仮説の各々の部分的仮説は、一まとまりの音声とマッチする可能性のある、音声モデル又は言語モデルからのトークンのシーケンスを含んでいる、工程と、
ＣＰＵを用いて、一組の部分的仮説の各々の部分的仮説について尤度補正を演算する工程と、
ＧＰＵを用いて、一組の部分的仮説の各々の部分的仮説について尤度補正をアップデートする工程と、
ＧＰＵ上の第２バックトラックテーブルとマッチするようにＣＰＵ上の第１バックトラックテーブルを同期する工程と、
アップデートされた一組の部分的仮説でバックトラックを実行して、アップデートされた一組の部分的仮説における最も起こり得る部分的仮説を決定する工程と、
を含む方法。
【請求項２】
サンプル特徴の各々について観測尤度を演算する工程は、ガウス混合モデルを用いてサンプル特徴の各々について観測尤度を演算する工程を含む、請求項１に記載の方法。
【請求項３】
サンプル特徴の各々について観測尤度を演算する工程は、ニューラルネットワークを用いてサンプル特徴の各々について観測尤度を演算する工程を含む、請求項１に記載の方法。
【請求項４】
一組の部分的仮説の各々の部分的仮説について尤度補正を演算する工程は、ｎ−ｇｒａｍ言語モデルを用いて一組の部分的仮説の各々の部分的仮説について尤度補正を演算する工程を含む、請求項１に記載の方法。
【請求項５】
一組の部分的仮説の各々の部分的仮説について尤度補正を演算する工程は、ニューラルネットワークを用いて一組の部分的仮説の各々の部分的仮説について尤度補正を演算する工程を含む、請求項１に記載の方法。
【請求項６】
一組の部分的仮説の各々の部分的仮説をソートする工程と、
ランキング閾値未満の部分的仮説を除外する工程と、
を更に含む、請求項１に記載の方法。
【請求項７】
出力アークとして、トークンシーケンスを示す履歴の確率を格納するデータ構造を作成する工程を更に含んでおり、当該データ構造は、出力アークの組を格納するのに使用されており、状態を出るアークの数に基づいて変化する、請求項１に記載の方法。
【請求項８】
出力アークの組を第１データベースに格納する工程と、
出力アークの組に基づいて探索モデルを作成する工程と、
探索モデルの状態に基づいて探索モデルを変更する工程と、
変更された探索モデルを第２データベースに保存する工程と、
を更に含む、請求項７に記載の方法。
【請求項９】
アップデートされた一組の部分的仮説でバックトラックを実行して、アップデートされた一組の部分的仮説における最も起こり得る部分的仮説を決定する工程は、アトミックコンペアアンドスワップ処理を用いて、アップデートされた一組の部分的仮説をマージする工程を含む、請求項１に記載の方法。
【請求項１０】
第１処理ユニット及び第２処理ユニットを備える並列プロセッサ演算プラットホームを用いてグラフ探索についてコンピュータで実施される統計的推測方法において、
尤度を初期化する工程と、
入力信号について、一まとまりの音声を含んでいるサンプルをキャプチャする工程と、
サンプルからサンプル特徴を演算する工程と、
第２処理ユニットを用いて、音声モデル及び言語モデルの少なくとも一方に基づいてサンプル特徴の各々について観測尤度を演算する工程と、
第２処理ユニットを用いて、過去のタイムステップにおけるサンプル特徴及び尤度の各々について、観測尤度に基づいて尤度をアップデートして、一組の部分的仮説を作成する工程であって、一組の部分的仮説の各々の部分的仮説は、一まとまりの音声とマッチする可能性のある、音声モデル又は言語モデルからのトークンのシーケンスを含んでいる、工程と、
第１処理ユニットを用いて、一組の部分的仮説の各々の部分的仮説について尤度補正を演算する工程と、
第２処理ユニットを用いて、一組の部分的仮説の各々の部分的仮説について尤度補正をアップデートする工程と、
第２処理ユニット上の第２バックトラックテーブルとマッチするように第１処理ユニット上の第１バックトラックテーブルを同期する工程と、
アップデートされた一組の部分的仮説でバックトラックを実行して、アップデートされた一組の部分的仮説における最も起こり得る部分的仮説を決定する工程と、
を含む方法。
【請求項１１】
一組の部分的仮説の各々の部分的仮説をソートする工程と、
ランキング閾値未満の部分的仮説を除外する工程と、
を更に含む、請求項１０に記載の方法。
【請求項１２】
出力アークとして、トークンシーケンスを示す履歴の確率を格納するデータ構造を作成する工程を更に含んでおり、当該データ構造は、出力アークの組を格納するのに使用されており、状態を出るアークの数に基づいて変化する、請求項１０に記載の方法。
【請求項１３】
出力アークの組を第１データベースに格納する工程と、
出力アークの組に基づいて探索モデルを作成する工程と、
探索モデルの状態に基づいて探索モデルを変更する工程と、
変更された探索モデルを第２データベースに保存する工程と、
を更に含む、請求項１２に記載の方法。
【請求項１４】
アップデートされた一組の部分的仮説でバックトラックを実行して、アップデートされた一組の部分的仮説における最も起こり得る部分的仮説を決定する工程は、アトミックコンペアアンドスワップ処理を用いて、アップデートされた一組の部分的仮説をマージする工程を含む、請求項１０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
[関連出願の相互参照]
本願は、２０１２年９月７日に出願された米国仮出願第６１／７４３，７５８号、発明の名称「METHODS FOR HYBRID GPU/CPU DATA PROCESSING」の優先権を主張するＰＣＴ国際出願であり前記米国仮出願は、引用を以て本明細書の一部となる。
【０００２】
本発明は、データ処理分野に関する。より詳細には、本発明は、並列処理プラットホームにて大規模グラフ探索（large-scale graph traversal）を実行するための方法に関する。
【背景技術】
【０００３】
近年、マルチコア処理とメニーコア処理をするコンピュータがより一般的になってきており、これにより、複雑な演算タスクが実行される速度は、このようなタスクが多数の処理コアで並列式に実行されることで顕著に増大する。ある種の複雑な演算タスクでは、しかしながら、このようなプロセッサは、そのメモリ容量によって制限される。例えば、メニーコアグラフィック処理装置（ＧＰＵ）では、メモリは、２乃至８ギガバイト（ＧＢ）に制限されている。このようなメモリは、グラフ構造が数百万のアーク（arc）を含んでおり、モデルのサイズが約１００ＧＢのオーダー又はそれより大きい大規模グラフ探索を演算するようなタスクに限界をもたらす。
【０００４】
それ故に、ヘテロジニアス並列演算コアを効率的に活用することで、並列処理プラットホームで大規模グラフ探索を効率的に実行する方法が必要とされている、
【０００５】
このような改善された方法が必要とされる分野の一つは、大語彙連続音声認識（large vocabulary continuous speech recognition）（ＬＶＣＳＲ）の分野である。必要性の一例としては、音声ユーザインターフェイスは、次世代のスマートデバイスのコアテクノロジとして成長していることがある。魅惑的な（captivating）ユーザー・エクスペリエンスを確実にするためには、これらシステム内で使用される音声認識エンジンが、ロバストで、速く、低遅延であって、システムが出くわすであろう極めて多数の語彙にわたって十分な適用範囲をもたらすことが重要である。高い認識精度を得るために、放送ニュースの転写［１，２］又は音声検索［３，４］のようなタスク用の音声最新式の音声認識システムは、大語彙（＞１００万語）、大音声モデル（数百万のモデルパラメータ）、及び非常に大きな言語モデル（数十億のｎ−ｇｒａｍエントリ）を用いて認識を実行することがある。これらのモデルは、オフラインの音声認識タスクに適用され得るが、デコード中に要求される演算コストが大きいので、リアルタイム音声認識には実用的ではない。
【０００６】
Ｈ−レベルＷＦＳＴとして一般に知られているように、ＷＦＳＴが、一つの単一ネットワークとして合成された、隠れマルコフモデル（ＨＭＭ）音声モデルＨ、コンテキストモデルＣ、発音辞書Ｌ、及び言語モデルＧを体現するような、静的コンパイルされる重み付き有限状態トランスデューサ（ＷＦＳＴ）ネットワークの使用は、音声認識を非常に効率的に実行することを可能にする［５］。しかしながら、このような音声ネットワークの合成と最適化は、大きなモデルが使用される場合には、実行不可能となる。
【０００７】
オンザフライ合成（On-the-fly composition）は、十分に合成された単一のＷＦＳＴを用いて音声認識を実行することに現実的に代わるものである。オンザフライ合成は、２又は３以上のサブＷＦＳＴのグループを順番に用いることを含んでおり、デコード中に必要に応じてそれらを合成する。一般的なアプローチの一つでは、デコード前にＨｏＣｏＬをプレ合成し、その後、これを文法ネットワークＧとオンザフライで合成する。オンザフライ合成は、メモリの観点からすると経済的であるとされてきたが、静的コンパイルされるＷＦＳＴよりも、デコードが極めて遅い［６］。
【０００８】
効率的なＷＦＳＴデコードの代替的なアプローチは、サーチ中に、合成ではなく、仮説リスコアリング（hypothesis rescoring）［３］を実行することである。このアプローチでは、ビタビ探索が、ＨｏＣｏＧｕｎｉを用いて実行されて、別のネットワークＧｕｎｉ／ｔｒｉが単に、オンザフライ式で、ビタビ探索プロセスから生成された仮説をリスコアリングために使用される。このアルゴリズムは、サーチの最初から全ての知識ソースを利用可能とすることから、これは、正しい経路を選択することと、仮説を削減する（pruning）ことの両方に効果的である。
【０００９】
メニーコアグラフィック処理装置（ＧＰＵ）は、現在有用なリソースであり、ハイブリッドＧＰＵ／ＣＰＵ演算アーキテクチャは、多数の演算タスクの現実的なソリューションである。演算サブタスクの各々に最も適切なアーキテクチャを活用することで、何れのプラットホームを単独で用いる場合よりも、顕著に高いスループットが得られる。従前の研究［７，８］は、音声認識にＧＰＵプロセッサを用いる有効性を明らかにして、限定された語彙タスク（vocabulary tasks）について、スループットを顕著に改善した。しかしながら、これらのアーキテクチャにおけるメモリの制限は、大きな音声及び言語モデルが認識中に適用される場合と、その他の大規模グラフ探索演算とについては、顕著なボトルネックになる。このような演算の最も大きな課題は、現代の幅広い領域の音声認識システムに使用される非常に大きな言語モデルを処理することである［１，２，４］。これらのモデルは、数百万のユニークな語彙エントリと、数十億のｎ−ｇｒａｍコンテキストとを含むことができ、メモリへの２０ＧＢ以上の格納をたちまち必要とする。顕著に削減される場合でさえも、これらのモデルは、ＧＰＵプラットホームで利用可能な制限されたメモリには収まらない。大きな音声モデル及び言語モデルを用いて音声認識を効率的に実行するために、我々は、ＧＰＵアーキテクチャの演算スループットを用いて、ＣＰＵの大きなメモリとローカルキャッシュとを活用するハイブリッドＧＰＵ／ＣＰＵアーキテクチャを開発した。
【発明の概要】
【００１０】
本発明は、並列処理プラットホームで、大規模グラフ探索計算を実行する方法を示す。本発明は、演算デバイスの中央演算処理装置（ＣＰＵ）を用いることと組み合わせて、グラフィック処理装置（ＧＰＵ）を用いるオンザフライ仮説リスコアリングの方法を示す。本発明は、大語彙連続音声認識のタスクに適用されるものとして、ある実施形態について説明される。当該分野における通常の知識を有する者であれば、本発明の方法は、その他の大規模グラフ探索演算に適用可能であることは分かるであろう。
【図面の簡単な説明】
【００１１】
【図１】図１は、大規模グラフ探索のタスクに適用された場合における本発明の実施構造の模式図である。
【００１２】
【図２】図２は、重み付き有限状態トランスデューサ（ＷＦＳＴ）合成中に適用されるであろう小さいモデルに含めるために、大きなモデルからエントリ（つまり、トークンシーケンスのマルコフモデルからの確率）をサブセレクト（sub-select）する実施アプローチの模式図である。その結果である十分に合成されたＷＦＳＴサーチグラフは、グラフィック処理装置（ＧＰＵ）でサーチを実行するのに十分に小さくなる。
【００１３】
【図３】図３は、グラフィック処理装置（ＧＰＵ）でサーチを実行するのに適した小さいＷＦＳＴサーチグラフを構成するのに使用される実施アプローチの模式図である。
【００１４】
【図４】図４は、ＷＦＳＴサーチグラフにおける状態と隣接するアークに含まれる情報の模式図である。それらは、状態ＩＤ（stateID）と、入力アークのリストと、出力アークのリストと、入力シンボルと、出力シンボルとを含んでいる。各アークは、アーク固有の重みを含んでいる。入力シンボルは、「観測モデル（observation model）」で生成された確率にマッチする。出力シンボルは、サーチプロセスで生成されたトークンにマッチする。例えば、音声認識タスクでは、これらのトークンが、語にマップするであろう。
【００１５】
【図５】図５は、グラフィック処理装置（ＧＰＵ）でのサーチに適した、小さいＷＦＳＴのサーチグラフの例を示す。この例は、任意の順序で起こる３つの語（「ｎｉｃｅ」、「ｒｅｃｏｇｎｉｚｅ」、及び「ｓｐｅｅｃｈ」）を含む非常に簡単なタスクの音声認識に適用される場合のサーチグラフを示す。
【００１６】
【図６】図６は、例示の言語モデルを示しており、既知の語履歴（word history）を仮定した場合において、言語モデル確率が、現在の語について掲載されている。
【００１７】
【図７】図７は、グラフィック処理装置（ＧＰＵ）で使用されるＷＦＳＴベースのサーチグラフをコンパイルする場合に合成中に使用するのに適した、小さい言語モデルの例を示す。この小さい言語モデルは、言語モデル確率と共に、０．０５の言語モデル閾値（ＴＬＭ）を使用して、図６の大きな言語モデルからサブセレクトされたものである。
【００１８】
【図８】図８は、図６及び図７に夫々示された大きな言語モデルと小さな言語モデルを用いて、自動音声認識のタスクについて部分的仮説（partial hypothesis）のスコアリングをした例を示す。リスコアリングの前にて、フレーズ「ｒｅｃｏｇｎｉｚｅ ａ ｂｅａｃｈ …」は、最も高い確率を有しているが、大きな言語モデルを用いてリスコアリングした後では、最も確率が高い部分的仮説は、「ｒｅｃｏｇｎｉｚｅ ｓｐｅｅｃｈ」である。
【００１９】
【図９】図９は、仮説の組合せと仮説の削減とを例示する、本発明の模式図である。
【００２０】
【図１０】図１０は、語彙サイズが５０００語である大語彙連続音声認識のタスクに適用された場合の、従来技術のアプローチと本発明のアプローチとを用いた精度とデコード速度を比較したデータを示している（評価設定（Ｅｖａｌ．ｓｅｔ）：ＷＳＪ ５Ｋ ｎｏｖ’９２（３３０センテンス））、ｎ１．３＝９、ｍ１．３＝１、ｎ２．３＝３、ｍ２．３＝４、ｌｂｗ２．３＝７）。
【００２１】
【図１１】図１１は、語彙サイズが１００万語である大語彙連続音声認識のタスクに適用された場合の、従来技術のアプローチと本発明のアプローチとを用いた精度とデコード速度を比較したデータを示している（評価設定：ＷＳＪ  ５Ｋ  ｎｏｖ’９２  ＋  ＷＳＪ  ２０ｋ  ｎｏｖ’９３（５４３センテンス）、ｎ２．３＝ｎ３．４＝３、ｍ２．３＝ｍ３．４＝２４））。
【００２２】
【図１２】図１２は、大語彙連続音声認識のタスクに適用された場合の、本発明を用いた実験における演算フェーズ当たりの処理時間の比のデータを示す（１００万語彙、ｎ３．４＝３、  ｍ３．４＝２４）。
【００２３】
【図１３】図１３は、本発明で用いた場合における「並列アトミックマージソート（parallel atomic merge-and-sort）」法の入出力を示す。入力は、Ｌ個のソートリスト（Ｓ１，…，ＳＬ）からなり、出力は、単一のソートリスト（Ｔ）である。
【００２４】
【図１４】図１４は、本発明で用いた場合における「アトミックマージソート」法における部分的仮説情報を格納するのに使用されるデータ構造を示す。
【００２５】
【図１５】図１５は、本発明で用いた場合における「アトミックマージソート」法で使用されるデータ構造及び関数の概略を示す。関数「ｍｅｒｇｅ−ａｎｄ−ｓｏｒｔ（＜ソースリスト＞，  ＜ターゲットリスト＞）」は、マージされる必要があるＬ個のソートリストの全て（Ｓ１，…，ＳＬ）について呼び出される。
【００２６】
【図１６】図１６は、本発明で用いた場合における「アトミックマージソート」法の概略図である。
【００２７】
【図１７】図１７は、本発明で用いた場合における「高速メモリ効率的ルックアップ（Fast and memory efficient look-up）」アーキテクチャに変換される言語モデルの例を示す。
【００２８】
【図１８】図１８は、本発明で用いた場合における「高速メモリ効率的ルックアップ」アーキテクチャによって（与えられた履歴と出力トークンについて）確率を抽出する手順の概略図である。
【００２９】
【図１９】図１９は、本発明で用いた場合における「高速メモリ効率的ルックアップ」アーキテクチャにて最も適切なデータ構造 (（ハッシュマップ（HASH-MAP）、静的配列（STATIC ARRAY）、バイナリサーチツリー（BINARY SEARCH TREE）、単精度整数（single INTEGER）) を選択することで、メモリ効率的モデルを生成する手順の概略図である。
【００３０】
【図２０】図２０は、語彙サイズが１００万である大規模連続音声認識のタスクに用いた場合における「高速メモリ効率的ルックアップ」アーキテクチャでのメモリ最適化の前で、出力アークの数と状態数とを比較するデータを示す。
【００３１】
【図２１】図２１は、大規模連続音声認識のタスクに用いた場合における高速メモリ効率的ルックアップ」アーキテクチャにて、バイナリサーチツリーを使うための出力アークに対してメモリフットプリント（footprint）を比較したデータを示す。
【００３２】
【図２２】図２２は、大規模連続音声認識のタスクに用いた場合にて、従来のアプローチ（ＫｅｎＬＭと呼ばれる）と、実施された「高速メモリ効率的ルックアップ」アーキテクチャについて、速度（つまり、実時間係数（ＲＴＦ））を比較したデータを示す。
【００３３】
【図２３】図２３は、大規模連続音声認識のタスクに用いた場合にて、従来のアプローチ（ＫｅｎＬＭと呼ばれる）と、実施された「高速メモリ効率的ルックアップ」アーキテクチャについて、メモリフットプリント（ギガバイト）を比較したデータを示す。
【発明を実施するための形態】
【００３４】
本発明は、並列処理プラットホームで、大規模グラフ探索計算を実行する方法を示す。本発明は、演算デバイスの１又は複数の中央演算処理装置（ＣＰＵ）を用いることと組み合わせて、グラフィック処理装置（ＧＰＵ）を用いる「オンザフライ仮説リスコアリング」の方法を示す。本発明は、大語彙連続音声認識（ＬＶＣＳＲ）のタスクに適用されるものとして、ある実施形態について説明される。当該分野における通常の知識を有する者であれば、本発明の方法が、手書き認識、画像ベースのジェスチャー認識や画像理解のような、大規模グラフ探索演算が必要とされるその他の統計的推測タスクに適用可能であることは分かるであろう。
【００３５】
本発明について、ハイブリッドＧＰＵ／ＣＰＵアーキテクチャ用の新規なオンザフライ仮説リスコアリングアルゴリズムを説明する。本発明のアプローチの概略は、図１に示されている。
【００３６】
与えられた入力信号（符号１）と１組の統計モデル（符号１５、１６及び１８）について、サーチが実行されて、入力信号に最も良くマッチするモデルを共同的に介して、ベストなトークンシーケンス（符号２）が見つけられる。
【００３７】
本発明のある実施例では、つまり、大語彙連続音声認識（ＬＶＣＳＲ）のタスクにおいて、入力信号（符号１）は、マイクロホンからキャプチャされたデジタルオーディオであってよく、出力（符号２）は、ユーザが発音したものに最も良くマッチする語系列であってよい。大語彙連続音声認識（ＬＶＣＳＲ）のタスクでは、符号１５は、音声モデル（例えば、ガウス混合モデル又は多層ニューラルネットワークベースの確率モデル（Deep Neural Network-based Stochastic Model））にマッピングし（map to）、符号１６は、十分に合成されたＨレベル重み付き有限状態トランスデューサ（ＷＦＳＴ）ベースのサーチグラフであり（このようなグラフの例示的な具体例は、図５に示されている）、符号１８は、言語モデル（例えば、言語モデルの確率は、静的なルックアップテーブル、又は代替的には、多層ニューラルネットワークベースの統計モデルに格納される）であろう。
【００３８】
本発明では、サーチは、以下の要領で実行される。初期化（図１、ステップ３）で、どの一時作業メモリ（符号１７及び１９）もクリアされて、状態尤度（state likelihood）が、サーチネットワークについて初期化される。具体的には、ネットワークの初期状態（状態０）について、尤度は、１．０に設定され、その他全ての状態について、尤度は、０に設定される。例示した具合例では、符号３７は、図５にてサーチグラフの初期状態を示している。
【００３９】
入力信号が最初に受信されると、サンプルが最初にキャプチャされて（符号４）、 一組の表現特徴（representative features）が、サンプルから計算又は抽出される（符号５）。得られた「特徴ベクトル」は、キャプチャされた信号の最も有益な様相の低次の表現である。１又は複数の特徴ベクトルは、アプリケーションのタスクに応じて、サンプル毎に演算されてよい。
【００４０】
本発明のある実施形態、つまりＬＶＣＳＲでは、入力信号（符号１）はデジタルオーディオである。このタスクでは、２５ｍＳのオーディオサンプルが１０ｍＳ毎にキャプチャされて（ステップ４及び１３）、入力信号がオーバーラップしてよい。音声特徴は、その後、各２５ｍＳのオーディオサンプルについて計算されてよい。このタスクに使用され得る典型的な音声特徴は、ｌｏｇ−Ｍｅｌフィルタバンドエネルギとメル周波数ケプストラム係数（ＭＦＣＣ）の特徴を含んでいてよい。同様なアプローチは、画像又はオーディオビジュアル信号が入力信号である場合にも使用できる。サンプルキャプチャ（ステップ４及び１３）と特徴計算（ステップ５）は、ＣＰＵ又はＧＰＵの演算アーキテクチャの何れかを用いて、任意の演算デバイスで計算される。それらは、本発明では、その他のステップとして、同じ演算デバイス上で実行される必要は必ずしもない。
【００４１】
特徴ベクトルが生成されると（ステップ５）、Ｎ−ｂｅｓｔサーチがその後、ＧＰＵで実行され（ステップ６、７、８、１１及び１２）、ＣＰＵを活用して、ＣＰＵのメインメモリに格納されたトークンシーケンスモデル（ステップ1８）を利用して、組み込まれたモデルの尤度の補正が演算される（ステップ９及び１０）。サーチ中、最初の観測尤度（observation likelihoods）は、ガウス混合モデル又は多層ニューラルネットワークベースモデルなどの統計的観測モデル（符号１５）を用いて、新しい特徴ベクトルの各々について演算される（ステップ６）。ステップ７では、状態尤度は、式（１）を用いており、ステップ６で演算された観測尤度と先の時間のステップの観測尤度とに基づいている。新しい部分的仮説ｇ′の状態尤度α［ｇ′］は、以下のように計算される。
【００４２】
【数１】
0006346893.tif 000002
【００４３】
ここで、β［ｅ］は、（符号１５を用いて演算された）入力シンボルｉ［ｅ］の観測尤度であり、ｗ［ｅ］は、（符号１６からの）状態遷移確率であり、ａ［ｇ］は、先の時間同期（previous time-synchronous）からの状態尤度である（ステップ６）。
【００４４】
本発明では、モデル尤度補正、ｃ［ｅ，ｈ［ｇ］］が導入されて、非常に大きなモデルにオンザフライを適用可能にする。
【００４５】
【数２】
0006346893.tif 000003
【００４６】
モデル尤度補正係数、ｃ［ｅ，ｈ［ｇ］］は、小さなモデルＰｕｎｉ（ｏ［ｅ］）（即ち、ＷＦＳＴ合成中に適用された言語モデル）のモデル尤度と、サーチ中に適用される非常に大きいモデルＰｎｇｍ（ｏ［ｅ］｜ｈ［ｇ］）（符号１８）のモデル尤度の差である。
【００４７】
【数３】
0006346893.tif 000004
【００４８】
ｈ［ｇ］は、仮説ｇの出力シンボルシーケンスである。
【００４９】
ここで、ＣＰＵメモリに格納されている大きなモデル（符号１８）は、Ｐｎｇｍ（ｏ［ｅ］｜ｈ［ｇ］）を演算するのに使用される。次に、状態尤度［ｇ′］が、式２として記載したモデル尤度補正係数を用いて、アップデートされる（ステップ１０）。
【００５０】
リスコアリングが実行された後、部分的仮説が、それらの状態尤度a［ｇ′］に基づいてランク分けされて、ランキング閾値未満のものが、考慮から除外される（ステップ１１）。
【００５１】
このサーチプロセス（ステップ６、７、８、９、１０、１１、１２、１３）は、最後のサンプルに出くわすまで（ステップ１２）、繰り返される。そのポイントにて、バックトラック（back-track）が、ＣＰＵで実行されて（ステップ１４）、最後の１−ｂｅｓｔ仮説出力（符号２）を生成する。バックトラックテーブル（アクティブな部分的仮説のリストと、部分的仮説が変更されたより前のフレームへのバックポインタとを格納するテーブル）が、ＧＰＵ（符号１７）とＣＰＵ（符号１９）の間で作業メモリにて共有される。このテーブルの同期を維持するために、ＣＰＵは、各サンプルが処理された後に、ＧＰＵからＣＰＵへとバックトラック情報にわたってコピーする（符号２０）。
【００５２】
ある実施例では、バックトラックを実行する前に出くわす最後のサンプルを待っている（符号１２）のではなく、２０個のサンプル毎にて、又は、単一−ベスト出力が将来にて変換しないであろうポイントにて、バックトラックがＣＰＵで実行される（符号１４）。
【００５３】
本発明では、ｎ−ｂｅｓｔビタビ探索が、ｎ−ｂｅｓｔ仮説リストを各アーク及び状態に割り当てることで実行される。複数のアークが同じ状態で出くわす場合、ｎ−ｂｅｓｔ仮説リストはマージされて、ビタビ探索は、全てのｎ−ｂｅｓｔ仮説リストにわたってｎ個の最小重み仮説（minimally weighted hypotheses）を選択する。図９では、状態ｓ２からのｆ４と状態ｓ３からのｆ２とは、それらの全重みに基づいてソートされた順序で維持される。加えて、仮説が同じ高次の履歴を有している場合、重みがより小さい仮説のみが維持されるだろう。例えば、ｆ”１は削除される。なぜならば、ｓ５にて出くわす場合にｆ”４と比較して、この仮説は、同じ高次の履歴「ｂａ」を有しているが、重みが高いからである。ｎ−ｂｅｓｔリストを維持することは、比較に値する精度を得るのに重要である［７］。２．１にて説明されたようなベストの仮説を選択する場合、最終的なベストの仮説の部分的仮説は、仮説がリスコアされ得る非イプシロン（non-epsilon）出力でトランジションｅに至る前に、削除される。このシナリオは、図９に図示されており、仮説ｆ１は、一般的なデコードアプローチを用いた場合のオリジナルのベスト経路であり、ｆ４は、リスコアされたベスト経路である。ベストの仮説のみを維持するのであれば、全体的なベストの仮説ｆ４は、リスコアリングが適用され得るｓ３とｓ４の間のアークに達することはできない。ｎ−ｂｅｓｔリストの最大サイズは、語彙のサイズと言語モデルの次数とに基づいて注意深く決定されるべきである。与えられた語彙のサイズにおいて、低次の言語モデルと合成されるＷＦＳＴは、比較可能な精度を得るためには、高次の言語モデルと合成されるものと比較してより大きいｎを必要とする。これは、同じ行き先の状態へとアークを集めるのが厳しいことによる。同様に、より語彙が多いＷＦＳＴは、リスコアリングポイントまで達するまでに最終的なベストとを維持するのに、より大きいｎ−ｂｅｓｔリストを必要とする。
【００５４】
本発明は、幾つかの例示的な実施形態に基づいて説明されている。それらは、全ての点において、限定ではなく、説明を目的としている。特に、本発明は、大語彙連続音声認識演算に適用されるものとして、ある実施形態について説明されてきた。当該分野における通常の知識を有する者であれば、本発明は、大規模グラフ探索演算のその他の５つのタイプに適用できることが分かるであろう。故に、本発明は、具体的な実施において様々に変更でき、それらは、当業者であれば本明細書の記載から導き出せるであろう。このような変更とその他の変更の全ては、本発明の範囲と精神に含まれると考えられる。
【００５５】
［実証例］
【００５６】
図６、図７及び図８に、提案した「オンザフライ」リスコアリング方法の効果を実証するための音声認識タスク用の一組の例示のモデルを示す。
【００５７】
最初に、サーチグラフ（図１、符号１６）を準備するために、大きな言語モデルからエントリをサブセレクトし（図７）、モデルのコンパイル中に使用する必要がある。この実証例では、確率が０．０５よりも大きいモデルエントリをサブセレクトした。これにより、図６に示す小さな言語モデルが得られた。その結果のサーチグラフは、図５に示したものと同様な構造であろう。
【００５８】
大きなモデルから最適なモデルエントリを選択して、小さいモデル及びサーチを生成する方法は、図２及び図３に夫々示されている。
【００５９】
図８は、図６及び図７に掲載された言語モデルを用いる前と後の双方について、６つの部分的仮説に関する確率を示している。図８は、「ｒｅｃｏｇｎｉｚｅ ａ ｂｅａｃｈ …」は、リスコアリング前にて最も高い確率を有していることを示している。しかしながら、リスコアリング後では、より妥当な仮説「ｒｅｃｏｇｎｉｚｅ ｓｐｅｅｃｈ」が最も高い確率を有している。語系列（「＜ｓ＞ ｒｅｃｏｇｎｉｚｅ ｓｐｅｅｃｈ ＜／ｓ＞」）の確率は、オリジナルのモデルで比較的高いが、これらのエントリは、ＧＰＵ上でサーチを実行するための小さい言語モデルとサーチグラフを生成するために廃棄される必要があった。
【００６０】
［実験の評価］
【００６１】
ＷＳＪタスクの大語彙バージョンを用いて、大語彙連続音声認識（ＬＶＣＳＲ）のタスクについて本発明の効果を評価した。１９９２年１１月のＡＲＰＡ ＷＳＪ ５ｋ評価セット（３３０センテンス）と、１９９３年１１月のＡＲＰＡ ＷＳＪ ２０ｋ評価セット（２１３センテンス、語彙制約無し（open vocabulary））とからなる複合評価セットを使用した。
【００６２】
我々の音声モデルは、ＬＤＡ変換を用いた３９次元のＭＦＣＣのフィート（feat）を有するＷＳＪデータセットでＫａｌｄｉツールキット［２２］を用いて、トレーニングされた。得られた音声モデルは、２４０Ｋガウシアンと２，９４６個の音声状態（phonetic state）とを含んでいた。
【００６３】
【表１】
0006346893.tif 000005
【００６４】
ＷＦＳＴは、［５，６］に説明されているようにして、ＧＰＵ加速プラットホームの効率的並列時間同期グラフ探索について、オフラインで合成及び最適化された。表１は、５ｋ及び１０００ｋの語彙の言語モデルについて、最終的な完全に合成されたＷＦＳＴのサイズを示す。２つのＩｎｔｅｌ Ｘｅｏｎ Ｅ５−２６４０ ６−ｃｏｒｅ ＣＰＵを有する４−ｗａｙ ＮＶＩＤＩＡ Ｔｅｓｌａ Ｋ２０ ＧＰＵサーバの単一のＧＰＵを用いて、提案したアルゴリズムを評価した。ＮＶＩＤＩＡ Ｔｅｓｌａ Ｋ２０ ＧＰＵは、２，４９６個のＣＵＤＡコアと５ＧＢのＧＤＤＲ５メモリを有する１３個のストリーミングマルチプロセッサ（ＳＭＸ）を含んでいる。オペレーティングシステムは、Ｕｂｕｎｔｕ １２．０４  ＬＴＳ（６４ビット）であり、デコーダは、ｇ＋＋４．６とｎｖｃｃ５．０でコンパイルされた［２３］。以下のセクションでは、以下の合成スキームを比較する:３−ｇｒａｍの言語モデルで構成されたＷＦＳＴを用いた従来のアプローチ（ＳＴＤ−３）、ｌｂｗ２．３としてラティスビームを用いた、ラティス生成リスコア２−ｇｒａｍ／３−ｇｒａｍ言語モデルの組合せ（ＬＡＴＲ−２．３）、ｍ２．３スレッドを用いてｎ２．３−ｂｅｓｔサーチを実行する、提案のオンザフライリスコア２−ｇｒａｍ／３−ｇｒａｍの組合せ（ＯＴＦＲ−２．３）。
【００６５】
精度性能：最初の評価では、小語彙５Ｋテストセットを用いて提案のリスコアリングアプローチ（ＯＴＦＲ）の精度を評価する試みをした。言語モデルは異なるが、同じ知識ソースを用いて完全に合成された３つのＷＦＳＴを生成した。１−ｇｒａｍと２−ｇｒａｍのケースでは、提案したオンザフライ仮説リスコアリングアプローチを適用した。３−ｇｒａｍ言語モデルを用いて、Ｎ１、Ｎ２とリスコアされたオンザフライでデコードすることで、ｎ１．３が９、ｎ２．３が９である場合に、ＳＴＤ−３ケースとＬＡＴＲ−２．３とに対して同様なワードエラーレート（ＷＥＲ）を得た。ｎ１．３はｎ２．３よりも大きく、３に説明されているように、ｎ２．３と比較して同程度のＷＥＲ、５．４％を得た。同様に、ＬＡＴＲ−２．３は、全てのデコードアプローチにわたって、与えられたグローバルビームについて比較可能な精度を得るために、より広いｌｂｗ２．３を必要とする。大語彙（１００万語彙）では、ｎ２．４、ｎ３．４が３である場合に、ＯＴＦＲ−２．４は、ＯＴＦＲ−３．４のケースと比較して０．３％の絶対精度の低下を示した。これは、低次の言語モデルに加えて大語彙は、従来及びラティスリストアリングアルゴリズムを用いて比較可能な精度を得るためには、より大きなｎを必要とすることを明らかにしている。
【００６６】
速度性能：第２の評価では、シングルコア実行例とＧＰＵ加速マルチコア実行例の両方を用いてデコード速度を評価した。ベースラインの実行例は、自動チューニング線形代数ソフトウェア（Automatically Tuned Linear Algebra Software）（ＡＴＬＡＳ）を用いて最適化されて、音声重み演算処理を加速している。図１０及び図１１のＧＰＵ／ＣＰＵ評価では、言語モデルのルックアップが、ＧＰＵでの音声モデル演算と同時に、多数のＣＰＵコアにわたって並列に実行された。これらのステップの内訳は、図１２に示されている。図１２は、最適化なしの、ベースラインである従来のＧＰＵデコードアプローチを示す。言語モデルのルックアップは、デコード時間の大半を消費した。ＯｐｅｎＭｐを用いて言語モデルのルックアップをすることで（ｂ）、ルックアップに要する時間は、０．７１から０．０６ＲＴＦへと１１．６×の因子で低減される。最後に、ＧＰＵでの音声重み演算と同時に言語モデルのルックアップを実行することで、全体的なデコード時間は、０．２０ＲＴＦから０．１２ＲＴＦへと更に低減される。図１０は、ＧＰＵとコアＣＰＵを効率的に用いることで、ＷＥＲが６．５％である場合に、ＯＴＲＦ−３．４は、デコード速度がリアル−タイムよりも１０倍速くなることを示している。高度に最適化された単一ＣＰＵの実行例と比較して、２４×速い。その結果は、高次の言語モデルと合成されたＷＦＳＴは、デコード速度の点でより適切であることを示している。図１１では、ＯＴＦＲ２．３は、ＷＥＲが５．４％である場合にＯＴＦＲ−１．３よりも、相対的に４０％速い。また、図１１にて、ＯＴＦＲ２．３は、ＯＴＦＲ−２．４よりも相対的に速いことが観測される。
【００６７】
［高並列演算アーキテクチャでソートリストをマージする方法：アトミックマージソート］
【００６８】
ビタビ検索中のｎ−ｂｅｓｔ仮説の維持は、多数の並列化課題を有する。最も重要な課題は、再収束（reconvergent）経路上でのｎ−ｂｅｓｔリストのマージである。我々は、最小重みの仮説を用いてソートしたｎ−ｂｅｓｔリストを最上に維持することを選択する。これによって、「マージソート」プロセスへとｎ−ｂｅｓｔ仮説リストをマージする処理が簡単になる。ＣＰＵでは、この処理は、非常に効率的に実行できる。
【００６９】
ＧＰＵでは、しかしながら、数百のアークがあって、各々がｎ−ｂｅｓｔリストを伴っており、同じ時間にて行先の状態にてｎ−ｂｅｓｔリストに書き込もうと試みることがあり得る。我々は、図１６に示すように、アトミックコンペアアンドスワップ（Compare-And-Swap）処理を用いて、高並列プラットホーム上で自動的にｎ−ｂｅｓｔリストをマージする新規な方法を開発した。ＧＰＵは、効率的に実行されるハードウェアサポートアトミック処理をもたらし、この能力を活用して、このプラットホーム上で「アトミックマージソート」方法を実施する。図１３、１４、１５及び１６を参照。
【００７０】
［マルコフモデル確率の高速メモリ効率的ルックアップのアーキテクチャ］
【００７１】
オンザフライ仮説リスコアリングアプローチは、上述したように、大きなモデル（典型的には、マルコフモデルであり、トークンシーケンスの確率を与える）を、ＧＰＵ上でのＷＦＳＴサーチに導入することを可能とする。ＧＰＵでのサーチ中にトークン境界に出くわすと、（履歴状態ＩＤ、ＷＦＳＴ重み及び現在のトークンからなる）部分的仮説は、ＣＰＵに格納されたより大きいモデルを用いて、リスコアされる。（図１のステップ９の「リスコアリング重みを演算」に示された）モデルのリックアップ効率は、高速な認識にとって重要である。
【００７２】
このステップに必要とされる時間を低減するために、迅速な仮説リスコアリングに最適化された新規なグラフベースのモデル構造を開発した。このモデルの概要は、図１７に示されている。このモデルは、グラフ構造内の状態として履歴（トークンシーケンス）を示している。履歴の確率（Probabilities of histories）は、これらの状態からの出力アークとして格納される。履歴とトークンの両方は、このフレームワーク内にて整数として表現されており、直接に使用されるトークンＩＤは、ＧＰＵでのサーチ中に適用される、完全に合成されたＷＦＳＴのものにマッチする。仮説リスコアリング中、特定の＜状態ＩＤ（ｈ），トークンＩＤ（ｔ）＞対についての確率の演算は、（アレイの直接インデックスルックアップ（direct index lookup）である）状態ＩＤを見つけることと、対象であるトークンＩＤについて出力アークを探索することと、その後、確率ｐ（トークンＩＤ（ｔ）｜状態ＩＤ（ｈ））とアップデートされた状態ＩＤの何れかを返すこととを含んでいる。
【００７３】
図１７は、提案したグラフベースの構造に表現された小さい言語モデルを示している。各ノードは、固有の履歴（固有のトークンシーケンス）を示している。実線のアークには、トークンとその確率とが付されており、これらのアークは、新しい履歴に通じている。点線のアークは、バックオフ（back-off）アークを表している。それらには、バックオフ重みが付されており、それらは、履歴が低減された状態に通じている。
【００７４】
図１８は、このアプローチを用いて、特定の＜状態ＩＤ（ｈ），トークンＩＤ（ｔ）＞対について確率を得るために必要なプロセスを示している。
【００７５】
このモデルに必要とされるメモリフットプリントを低減するために、新規な方法が使用され、当該方法では、出力アークの組を格納するのに使用されるデータ構造が、状態に存在するアークの数に応じて変化する。我々は、４つのデータ構造、つまり、ハッシュマップ（HASH-MAP） (デフォルト)、静的アレイ（STATIC ARRAY）、バイナリサーチツリー（BINARY-SEARCH TREE）、又は単精度整数（single INTEGER）を用いたプロトタイプを実施した。しかしながら、この目的のために、その他のデータ構造も使用されてよい。 
【００７６】
図１９に記載された方法は、データを格納するのに要求されるメモリフットプリントをできるだけ小さくするのに使用される。最初に、全ての出力アークがハッシュマップを用いて格納されている初期モデルをロードし（符号９）、モデルの最初の状態（Ｓ）を選択する [ステップ]。モデルの各状態にて、その後、出力アークの数が比較される。
【００７７】
［実験的評価］
【００７８】
プロトタイプでは、非常に大きな言語モデル（１００万語、４８８万個の確率）からの確率を格納するために上述したようなヘテロジニアスなデータ構造を用いて評価した。最初に、単一のエントリのみを有するハッシュマップを単精度整数に置き換えた。これによって、２８．６４ギガバイトから２２．５０ギガバイトへと、要求されるメモリフットプリントが２１．４％低減した。
【００７９】
次に、出力アークにおいて語彙の９０％以上を有するハッシュマップを、総語彙のサイズに合う静的アレイデータ構造に置き換えた。このケースでは、出力アークの組では起こらなかったトークンが、このアレイ内にて（１ルックアップで）特定される。メモリ使用は、このアプローチを用いて２２．５０から２２．４７ギガバイトへと低減された。
【００８０】
最後に、より多くのＴａｒｃの出力アークを有するハッシュマップを、バイナリサーチツリーで置き換えた。Ｔａｒｃの値を２から１０，０００（＜総語彙サイズの１％）に変化させることで、メモリ使用を１０．５ギガバイトに低減できた。これは、オリジナルのハッシュマップベースでの実施と比較して、メモリ使用の６３．４％の低減になる。Ｔａｒｃは、特定のプラットホーム又はデータセット、メモリフットプリント対ルックアップ速度について最適化できる。実験結果は、図２０、図２１、図２２、及び図２３に示されている。
【００８１】
本発明は、詳細に、且つ特定の実施形態について説明されたが、当該分野における通常の知識を有する者には、それら実施形態の精神と範囲から逸脱することなく、様々な変更及び修正を行うことができることが明らかであろう。故に、本発明は、添付の請求項とそれらの均等物の範囲内において本発明の変更と変形を含んでいる。
【図１】
0006346893.tif 000006
【図２】
0006346893.tif 000007
【図３】
0006346893.tif 000008
【図４】
0006346893.tif 000009
【図５】
0006346893.tif 000010
【図６】
0006346893.tif 000011
【図７】
0006346893.tif 000012
【図８】
0006346893.tif 000013
【図９】
0006346893.tif 000014
【図１０】
0006346893.tif 000015
【図１１】
0006346893.tif 000016
【図１２】
0006346893.tif 000017
【図１３】
0006346893.tif 000018
【図１４】
0006346893.tif 000019
【図１５】
0006346893.tif 000020
【図１６】
0006346893.tif 000021
【図１７】
0006346893.tif 000022
【図１８】
0006346893.tif 000023
【図１９】
0006346893.tif 000024
【図２０】
0006346893.tif 000025
【図２１】
0006346893.tif 000026
【図２２】
0006346893.tif 000027
【図２３】
0006346893.tif 000028