グラフベースのネットワークを横断するための方法及びシステム
【課題】ネットワークの状態のシーケンスに対応するネットワークのアークの入力ラベルを文法要素のシーケンスに対応するアークの出力文法要素のリストに変換する方法及びシステムを提供する。
【解決手段】ネットワークは、重み付き有限状態変換器（ＷＦＳＴ）と組み合わされた複数の音声認識モデルを含む。トラバーサルは、アクティブアーク横断を含むことができ、また、アクティブアーク伝播を含むことができる。アークは、複数のソース状態を起源とし且つ共通の目的状態に向けられるアークを含め、並列に処理され得る。状態に関連するセルフループは状態の退出アーク内でモデル化されてもよく、それにより同期化処理が削減され得る。タスクを、対応するデータオブジェクトに関する別のタスクが以前にスレッドに割り当てられていたかに少なくとも部分的に基づいて、処理スレッドに関連付けるように、タスクはキャッシュデータ位置との関係で順序付けられ得る。
【解決手段】ネットワークは、重み付き有限状態変換器（ＷＦＳＴ）と組み合わされた複数の音声認識モデルを含む。トラバーサルは、アクティブアーク横断を含むことができ、また、アクティブアーク伝播を含むことができる。アークは、複数のソース状態を起源とし且つ共通の目的状態に向けられるアークを含め、並列に処理され得る。状態に関連するセルフループは状態の退出アーク内でモデル化されてもよく、それにより同期化処理が削減され得る。タスクを、対応するデータオブジェクトに関する別のタスクが以前にスレッドに割り当てられていたかに少なくとも部分的に基づいて、処理スレッドに関連付けるように、タスクはキャッシュデータ位置との関係で順序付けられ得る。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、グラフベースのネットワークを横断（トラバース）するための方法及びシステムに関する。
【背景技術】
【０００２】
音声ストリームを表す特徴ベクトルのストリームを生成するために、音声特徴抽出器が開発されている。
【０００３】
音声ベースの特徴ベクトルを書き言葉の単語シーケンスに関連付けるために、グラフベースの音声認識ネットワークが開発されている。
【０００４】
対応する単語シーケンスを特定するために、音声ベースの特徴ベクトルのストリームに応答して、グラフベースの音声認識ネットワークの複数の状態間を繰り返し行き来するように、推論（インファレンス）エンジンが開発されている。
【０００５】
音声認識システムは、大語彙連続音声認識（large vocabulary continuous speech recognition；ＬＶＣＳＲ）システムを含む重み付き有限状態変換器（Weighted Finite State Transducer；ＷＦＳＴ）を用いて開発されてきた。
【０００６】
状態ベースのネットワーク横断（トラバーサル）技術は、マルチスレッド的且つ単一命令複数データ（single instruction，multiple data；ＳＩＭＤ）的に実装されてきた。音声認識ネットワークの状態は、対応する状態への追加の到来ループとして従来から取り扱われているセルフループを含み得る。マルチスレッドＳＩＭＤ処理環境においては、故に、状態がセルフループに加えて唯一の到来アークを含む場合であっても、同期化が必要となり得る。さらに、状態ベースのＳＩＭＤ横断技術は、ＳＩＭＤ処理レーンを完全に利用することができないことがあり、それにより、ベクトル非効率性がもたらされ得る。これは、ＳＩＭＤ処理の利益を相殺してしまい得る。
【０００７】
包括的な動的タスクスケジューリング技術がマルチプロセッサシステム用に開発されている。そのような包括的な技術は、例えば音声認識ネットワークの横断などの一部の用途では最適でないことがある。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の実施形態は、グラフベースのネットワークを横断するための方法及びシステムを提供する。
【課題を解決するための手段】
【０００９】
一態様に従って、ネットワークのアークの入力ラベルを、前記アークの出力文法要素のリストに変換する方法及びシステムが提供される。当該方法及びシステムは、特徴ベクトルのストリームに応答してネットワークを繰り返し横断することを含む。ネットワークの状態のシーケンスに対応するネットワークのアークの入力ラベルが、文法要素のシーケンスに対応する前記アークの出力文法要素のリストに変換される。当該方法及びシステムは更に、データオブジェクトに関するタスクを、該データオブジェクトに関する先行タスクが割り当てられた処理スレッドに基づいて順序付けることを含む。
【図面の簡単な説明】
【００１０】
【図１】グラフベースネットワーク及び推論エンジンを示すブロック図である。
【図２】グラフベースネットワークを横断する方法を示す処理フローチャートである。
【図３】推論エンジンがアクティブアーク横断システムを含む図１のシステムを示すブロック図である。
【図４】アクティブアークを処理する方法を示す処理フローチャートである。
【図５】グラフベースネットワークの目的状態を更新する方法を示す処理フローチャートである。
【図６】対応する状態の退出アーク内でセルフループ情報がモデル化される別のグラフベースネットワーク及び推論エンジンを示すブロック図である。
【図７】ネットワークのアークの少なくとも一部内でセルフループ情報がモデル化されるときの、ネットワークを横断する方法を示す処理フローチャートである。
【図８】セルフループ固有尤度情報を含むようにネットワークのアークの一部の固有尤度情報が変更されるときの、ネットワークを横断する方法を示す処理フローチャートである。
【図９】セルフループ固有尤度情報とセルフループ固有尤度情報の存在を指し示すものとを保持するようにネットワークのアークが複数のフィールドを含むときの、ネットワークを横断する方法を示す処理フローチャートである。
【図１０】タスク待ち行列内のタスク群を順序付けるキューマネジャと、複数の処理スレッド間でタスク待ち行列からのタスク群をスケジューリングする動的タスクマネジャとを含む、黙示的なキャッシュ認識環境を示すブロック図である。
【図１１】データ局所情報をデータオブジェクトと関連付けるキャッシュ認識システムと、少なくとも部分的にデータ局所情報に基づいて、タスクを処理スレッドに割り当てる動的タスクマネジャとを含む、明示的なキャッシュ認識環境を示すブロック図である。
【図１２】データ局所情報に基づいてタスク群を順序付ける方法を示す処理フローチャートである。
【図１３】少なくとも部分的にデータ局所情報に基づいてタスクを処理スレッドに割り当てる方法を示す処理フローチャートである。
【図１４】グラフベースネットワークを横断するように構成されたコンピュータシステムを示すブロック図である。 図面において、参照符号の１桁目は、その参照符号が最初に現れる図を指し示す。
【発明を実施するための形態】
【００１１】
図１は、グラフベースネットワーク１０２と推論エンジン１０４とを含むシステム１００のブロック図である。
【００１２】
ネットワーク１０２は、複数の状態１０６と、状態１０６間のアーク１０８とを含んでおり、ネットワークの一連の状態に対応するアーク１０８の入力ラベルを、一連の文法要素に対応するアーク１０８の出力文法要素のリストに変換する。
【００１３】
推論エンジン１０４は、特徴ベクトル１１０のストリームに応答して、ネットワーク１０２を繰り返し横断するように構成されている。
【００１４】
特徴ベクトル１１０は、連続音声、例えばビデオフレームのシーケンス又はビデオクリップなどの画像シーケンス、並びに連続テキストのうちの１つ以上を表し得る。特徴ベクトル１１０は、音響信号内に埋め込まれた音声、ビデオ信号内に埋め込まれた視覚映像、及びコンピュータ読み取り可能な信号内に埋め込まれたテキスト文字及びフォーマット情報のうちの１つ以上を含み得る１つ以上の連続信号及び／又は不連続信号から生成され得る。オーディオベースの特徴ベクトル１１０は、言葉、単語の一部又は音波を表し得る。ビデオベースの特徴ベクトル１１０は、動き、色、物体、及び／又はフレーム間でのそれらの変化のうちの１つ以上を表し得る。各特徴ベクトル１１０は、信号の対応する部分又はフレームに付随する情報を保持するために複数のフィールド（場）を含み得る。
【００１５】
文法は、ヒトが読み取り可能な言語又はコンピュータが読み取り可能な言語のうちの１つ以上を含み得る書き言葉に相当し得る。
【００１６】
システム１００は、オーディオ及び／又はビデオを書き言葉に変換する音声及び／又は映像認識システムに相当し得る。それに代えて、あるいは加えて、システム１００は、第１の書き言葉を第２の書き言葉へと変換する言語翻訳システムに相当してもよい。第１及び第２の書き言葉のうちの１つ以上は、話された言葉及び／又はコンピュータ読み取り可能言語に相当してもよい。
【００１７】
推論エンジン１０４は、特徴ベクトル１１０のストリームに応答して、状態１０６の１つ以上のシーケンスと、ここではパスとも称する対応するアーク１０８とを特定し、それらを繰り返しリファインするように構成され得る。特徴ベクトルストリーム１１０に潜在的に対応するとして所与の繰り返し中に特定された状態１０６及び／又はアーク１０８のことを、ここでは、その繰り返しのアクティブ状態１０６及びアクティブアーク１０８と呼ぶ。
【００１８】
所与の繰り返しにおいて、複数組のアクティブアーク１０８を介して到達可能なアクティブ状態１０６の組が特定されてもよい。換言すれば、複数のパスが、同一でない組のアーク１０８に沿って横断される１つの共通する組の状態１０６を含み得る。
【００１９】
推論エンジン１０４は、状態１０６及びアーク１０８が特徴ベクトルストリーム１１０に対応する尤度を表す可能性指標を、状態１０６及びアーク１０８に関連付けるように構成され得る。
【００２０】
推論エンジン１０４は、１つ以上のデータオブジェクトを用いて状態１０６及び／又はアーク１０８を表すように構成されることができ、また、ネットワーク１０２が横断されるときに対応するデータオブジェクトを更新するように構成され得る。状態１０６及び／又はアーク１０８の処理は、対応するデータオブジェクトを処理することを含み得る。
【００２１】
アーク１０８の起源となる状態１０６のことを、ここでは、起源状態１０６と称する。アーク１０８が向けられる状態１０６のことを、ここでは、目的状態１０６と称する。
【００２２】
システム１００は、指数関数的な順列及び単語間の未知の境界セグメンテーションを含み得る比較的大きい語彙から単語を認識する大語彙連続音声認識（ＬＶＣＳＲ）に相当し得る。
【００２３】
一組の可能性ある単語シーケンスＷが与えられるとき、観測されたオーディオ特徴Ｏに関して最も可能性の高い単語シーケンス：
【００２４】
【数１】
は、数学的に：
【００２５】
【数２】
として表され得る。
【００２６】
オーディオ特徴と単語シーケンスＷの従前の尤度との積であるＰ（Ｏ｜Ｗ）Ｐ（Ｗ）は、例えばビタビ（Ｖｉｔｅｒｂｉ）探索アルゴリズムを用いるなど、動的プログラミング再帰を用いて計算され得る。
【００２７】
時間ｔに単語シーケンスｗｔｊを有する状態ｊにある横断プロセスの尤度は、先行状態での尤度から：
【００２８】
【数３】
として導出され得る。ここで、ａｔｊは状態ｉ（ｓｉ）から状態ｊ（ｓｊ）への遷移確率であり、ｂ（Ｏｔ；ｍｋ）は状態ｉ（ｓｉ）から状態ｊ（ｓｊ）への遷移時のコンテキスト依存状態ｋ（ｍｋ）の観測確率である。
【００２９】
推論エンジン１０４は、一連の時間ステップにわたってアルゴリズムを繰り返し処理することができ、各時間ステップにおける単語又は文法要素シーケンスの尤度は、先行する時間ステップで計算された尤度に依存する。各繰り返しにおいて、特徴ベクトル１１０の最も可能性ある選択すべき解釈を表す多数の、恐らくは何千もの、アクティブ状態１０６が存在し得る。最も可能性ある状態１０６の組が、特徴ベクトル１１０のストリームの最後で選択され得る。
【００３０】
ネットワーク１０２は、重み付き有限状態変換器（ＷＦＳＴ）に従って生成され得る。ＷＦＳＴは、各々が例えば後述するもののような複数の特性を含むアーク群１０８のリストによって表されるＭｅａｌｙの有限状態マシン（ＦＳＭ）である。
【００３１】
ネットワーク１０２は、隠れマルコフモデル（Hidden Markov Model；ＨＭＭ）音響モデルＨ、コンテキストモデルＣ、単語の発音辞書Ｌ、及びここではＨレベルネットワークと称するＨ−Ｃ−Ｌ−Ｇ型ＷＦＳＴに構成され得る言語モデルＧのうちの１つ以上を含み得る複数の階層的な知識源又はモデルを含み得る。結合されたＷＦＳＴが、ＦＳＭ最小化技術を用いて最適化されて、認識ネットワークのフラット化されたＦＳＭ表現として用いられてもよい。ＷＦＳＴは、ランタイムにて横断すべく、階層的な知識源をオフラインで単一階層のＦＳＭへとフラット化することによって、認識処理を単純化し得る。
【００３２】
ＨレベルＷＦＳＴにおいて、個々のアーク１０８は、対応する文法要素に関連付けられ得る。推論エンジン１０４は、アーク上の入力ラベルのリストとしてのＨＭＭ状態のシーケンスを、アーク上の出力ワードのリストとしての単語のシーケンスに変換し得る。
【００３３】
ＨレベルＷＦＳＴにおいて、１つ以上のアーク１０８は：
アーク１０８が横断されるときに消費される入力ラベル又はシンボル；
入力ラベルが変換された結果の出力ラベル又は単語；
ソース状態；
目的状態；及び
ソース状態からのアークに従う固有尤度；
を含み得る。
【００３４】
１つ以上の状態１０６は：
状態１０６からの第１の退出アーク１０８へのポインタ；
状態１０６からの退出アークの数を指し示すもの；及び
状態１０６からの退出イプシロンアークの数を指し示すもの；
を含み得る。
【００３５】
イプシロンアークについては図２に関連して後述する。
【００３６】
アーク群１０８は、配列にて管理され、起源状態１０６によってグループ分けされ得る。
【００３７】
ＷＦＳＴに基づく探索において、入力シンボル又は特徴ベクトル１１０の組に対して、ネットワーク１０２を通り抜ける最も可能性あるパスの組が辿られる。各パスの情報は、該パスの先頭に結合され得る。この情報は、例えば潜在的に特徴ベクトル１１０に一致するとして特定された単語などの、そのパスに沿った出力シンボルの組と、そのパスの対応する累積尤度とを含み得る。
【００３８】
この情報は、出力シンボルの組へのポインタ及び累積尤度の値を含み得るデータ構造内で管理され得る。データ構造は、例えば１つ以上の状態１０６がセルフループ１１４を含む場合など、状態１０６に関連付けられ得る。他の例では、データ構造は、例えば図６−９に関連して後述するようにセルフループ情報が１つ以上のアーク１０８内でモデル化される場合など、対応するアーク１０８に関連付けられ得る。
【００３９】
ＷＦＳＴベースの推論エンジンは、用途にとらわれるものではなく、例えばテキスト処理や画像処理などのその他のドメインでも採用され得る。
【００４０】
アーク１０８は、図１にそれぞれ破線及び実線で示すイプシロンアーク及び非イプシロンアークを含み得る。イプシロンアークは、如何なる入力シンボルをも消費することなく横断される。非イプシロンアークは、状態遷移を実行するために１つの入力シンボルを消費する。ＨレベルＷＦＳＴ認識ネットワークでは、ネットワーク１０２の入力ラベルは、コンテキスト依存のＨＭＭ状態を表す。
【００４１】
図２は、或る１つの繰り返し中に入力フレーム又は特徴ベクトル１１０に応答してネットワーク１０２を横断する方法２００の処理フローチャートである。
【００４２】
ステップ２０２にて、ネットワーク１０２の入力シンボルに関して観測確率が決定される。観測確率は、例えば距離関数を計算することによる、音響入力シンボルに合致する入力特徴ベクトルの尤度指標を含み得る。観測確率は、コンテキスト依存状態のガウシアン混合モデルに従って決定され得る。ステップ２０２での観測確率の決定は、アクティブ状態の退出アーク上で入力シンボルを計算することを含むことができ、本質的あるいは専ら該計算で構成され得る。観測確率の決定は、ネットワーク１０２の音響モデルを参照することを含んでいてもよい。
【００４３】
ステップ２０４にて、非イプシロンアークが処理される。非イプシロンアークの処理は：
ステップ２０２で計算された現入力ｂ（Ｏｔ；ｍｋ）の観測確率；
ネットワーク１０２から参照される横断されているアークａｉｊの遷移確率又は重み；及び
時間ｔ−１での先行する繰り返しにて計算された先行シーケンスの尤度、すなわち、ソース状態コスト：
【００４４】
【数４】
の同時確率を計算することを含み得る。
【００４５】
同時確率はステップ２０４において、観測確率、遷移確率、及び尤度の積として決定され得る。同時確率はステップ２０４において、対数で表された値の加算として決定されてもよい。
【００４６】
ステップ２０６にて、イプシロンアークが処理される。イプシロンアークは入力シンボルを有しないため、確率は、遷移確率及び先行シーケンスの尤度の積として計算され得る。
【００４７】
ステップ２０４及び／又は２０６において、目的状態のコストは、その状態に関して最も可能性の高い、対応する到来非イプシロン及びイプシロンアークのコストを用いて更新され得る。コストはビタビ近似に従って決定され得る。
【００４８】
ネットワーク１０２は、例えば図１のイプシロンアーク１０８−７及び１０８−１０などの、連続したイプシロンアークの連鎖を含み得る。ステップ２０６でのイプシロンアークの処理は、退出イプシロンアークを伴わない状態に到達するまで、各目的状態から全ての退出イプシロンアークを横断することを含み得る。
【００４９】
ステップ２０２では、観測確率を計算するために、例えば何千もの入力シンボルといった多数の入力シンボルが用いられ得る。ステップ２０４での非イプシロンアークの処理及びステップ２０６でのイプシロンアークの処理においては、ネットワーク全体で、例えば何万ものアーク遷移といった多数のアーク遷移が横断され得る。
【００５０】
方法２００は、更なる入力フレーム又は特徴ベクトル１１０に対して繰り返され得る。
【００５１】
横断技術
推論エンジン１０４は、アクティブ状態及び／又はアクティブアークに関してネットワーク１０２を横断するように構成され得る。
【００５２】
アクティブ状態横断は、状態毎を基本にして動作する。アクティブ状態の横断は、ここではアクティブ状態伝播と称するように、アクティブ状態１０６の退出アーク１０８に関して実行され得る。それに代えて、あるいは加えて、アクティブ状態の横断は、ここではアクティブ状態集約と称するように、次の繰り返しの候補アクティブ状態１０６の到来アーク１０８に関して実行され得る。状態１０６は、その状態への到来アーク１０８が現在の繰り返しのアクティブ状態１０６を起源とするとき、次の繰り返しの候補アクティブ状態として定められ得る。
【００５３】
アクティブ状態伝播の場合、アクティブ状態１０６ごとに、退出アーク１０８が評価され、対応する目的状態１０６に結果が伝播される。
【００５４】
アクティブ状態集約の場合、候補アクティブ状態１０６の到来アーク１０８が評価され、対応する候補アクティブ状態１０６が評価結果に従って更新される。
【００５５】
アクティブアーク横断は、アーク毎を基本にして動作し、アクティブアーク１０８が、対応する起源状態から取り出されたパラメータを用いて更新され、更新されたアクティブアーク１０８が、対応する目的状態１０６を更新するために用いられる。アクティブアーク横断は、ここではアクティブアーク伝播と称するようにアクティブ状態の退出アークに関して、あるいは、ここではアクティブアーク集約と称するように候補アクティブ状態の到来アークに関して実行され得る。アクティブアーク横断を実行する方法及びシステムについては、図３−５に関連して後述する。
【００５６】
並列処理技術
推論エンジン１０４は、例えば単一命令複数データ（ＳＩＭＤ）環境においてのようなデータレベルの並列化、及び／又は例えばマルチプロセッサ若しくはマルチコア環境においてのようなスレッドレベルの並列化を用いて、ネットワーク１０２を繰り返し横断するように構成され得る。
【００５７】
ＳＩＭＤ環境におけるアクティブ状態横断では、状態１０６に関連付けられたアーク１０８は、ＳＩＭＤ作業単位又はベクトルに関連付けられることができ、アーク１０８は並列ＳＩＭＤ処理レーンで処理され得る。ＷＦＳＴベースの探索グラフにおいては、一部の状態は、その他の状態が比較的少数の退出アークを有しながら、比較的多数の退出アークを有し得る。これは、比較的低い、且つ／或いは一貫性のない、ＳＩＭＤ利用をもたらし得る。
【００５８】
ＳＩＭＤ環境におけるアクティブアーク横断では、複数のアーク１０８が、対応するソース状態又は目的状態１０６とは関係なく、ＳＩＭＤ作業単位又はベクトルに関連付けられ得る。これは、比較的一貫性のあるＳＩＭＤベクトル単位の効率性を提供し得る。
【００５９】
マルチスレッド環境におけるアクティブ状態横断では、第１のアクティブ状態１０６に関連付けられたアーク１０８は、複数の処理スレッドのうちの第１のスレッドに割り当てられることができ、第２のアクティブ状態１０６に関連付けられたアーク１０８は、複数の処理スレッドのうちの第２のスレッドに割り当てられることができ、これら第１及び第２のスレッドが並列に処理され得る。
【００６０】
マルチスレッド環境におけるアクティブアーク横断では、アクティブアーク１０８は、対応する状態１０６とは関係なく、処理スレッドに割り当てられ得る。
【００６１】
スレッドレベルの並列化の場合、タスクはランタイムに先立って特定のスレッドに事前割当てされ得る。それに代えて、あるいは加えて、図９−１２を参照して後述するように、少なくとも部分的にデータ位置情報に基づいて、実行時にタスクをスレッドに割り当てるように動的タスクマネジャが構成されてもよい。
【００６２】
同期化
ＳＩＭＤ環境及び／又はマルチスレッド環境においてのようにアクティブ状態又はアクティブアークが並列に伝播される場合、及び複数のアークが共通の目的状態に向けられる場合、例えばアトミックアップデートなどの、書込競合の解消が、基礎となるプラットフォームから提供され得る。同期化が必要とされ得る場合を削減する方法及びシステムについては、図６−８に関連して後述する。
【００６３】
アクティブ状態１０６の到来アーク１０８が並列に集約される場合、該アクティブ状態の対応する更新は、到来アーク１０８の評価結果の削減を含み得る。この削減は、基礎となるプラットフォームからの書込競合の解消支援が不要となるよう、更なるアルゴリズム的ステップを用いて、潜在的な書込競合を明示的に管理し得る。
【００６４】
アクティブアーク横断
図３は、ネットワーク１０２のアクティブアーク１０８上を横断あるいは反復するアクティブアーク横断システム３０２を推論エンジン１０４が含む場合のシステム１００のブロック図である。更に後述するように、アクティブアーク横断システム３０２は、複数のアクティブ状態からのアーク群にわたるＳＩＭＤ計算を用いてアクティブアークを横断するように構成されることができ、それにより、非常に広いベクトルユニットであっても、該ユニットの実質的に完全な使用を可能にし得る。
【００６５】
図４は、アクティブアークを処理する方法４００の処理フローチャートである。ここでは、方法４００は、図３に示したシステム１００に関連して説明される。しかしながら、方法４００は図３の例に限定されるものではない。
【００６６】
ステップ４０２にて、特徴ベクトル１１０が推論エンジン１０４で受信される。
【００６７】
ステップ４０４にて、ネットワーク１０２のアクティブアーク１０８が、アクティブアーク横断システム３０２によって特定される。アクティブアークは、アクティブ状態の退出アーク、又はアクティブアーク伝播として、且つ／或いは、候補アクティブ状態の到来アーク、又はアクティブアーク集約として特定され得る。
【００６８】
ステップ４０６にて、特定されたアクティブアーク１０８の目的状態１０６が、ステップ４０２で受信された特徴ベクトル１１０に応答して、アクティブアーク横断システム３０２によって更新される。
【００６９】
ステップ４０８にて、１つ以上の更なる特徴ベクトル１１０を受信するため、処理はステップ４０２へと戻る。
【００７０】
ステップ４１０にて、特徴ベクトル１１０の処理が完了したとき、最も高い尤度のネットワーク１０２を通り抜けるパスに対応する文法要素のシーケンスが、推論エンジン１０４によって出力される。
【００７１】
図５は、ステップ４０６に関連して上述したような目的状態１０６を更新する方法５００の処理フローチャートである。
【００７２】
ステップ５０２にて、アクティブアーク１０８の起源状態１０６から、起源状態１０６に関する尤度の指標を含む情報が取り出される。
【００７３】
ステップ５０４にて、ステップ５０２で取り出された対応する情報と、ステップ４０２で受信された１つ以上の特徴ベクトルとを用いて、アクティブアークが更新される。
【００７４】
推論エンジン１０４は、アクティブアーク１０８をＳＩＭＤ的に処理するように構成され得る。例えば、ステップ５０２での情報の取り出し、及びステップ５０４でのアクティブアークの更新は、複数のアークに関してＳＩＭＤ的に実行され得る。複数のアーク１０８を、一組のＳＩＭＤ処理レーンにて処理される作業の単位として関連付けるように、作業単位マネジャが構成され得る。複数のソース状態１０６から共通の目的状態に向けられた複数のアーク１０８がＳＩＭＤ的に処理され得る。
【００７５】
ＳＩＭＤ的なアクティブアークの処理は、対応するベクトルユニットの実質的に完全なる使用を可能にし、ＳＩＭＤ的なアクティブ状態の処理より高いベクトル効率を提供し得る。
【００７６】
退出アーク内でのセルフループのモデル化
図１においては、複数のアクティブ状態１０６及び／又はアクティブアーク１０８は、横断の一度の繰り返し中に、共通の目的状態１０６に情報を伝播し得る。複数のアクティブ状態１０６及び／又はアクティブアーク１０８が、例えばスレッドレベル及び／又はデータレベルの並列処理などにて、同時あるいは並列に処理されるとき、対応する目的状態の更新の同期化が必要となり得る。
【００７７】
ネットワーク１０２の１つ以上の状態１０６はセルフループ１１４を含み得る。ＷＦＳＴ探索グラフは、例えば基礎となる隠れマルコフモデル（ＨＭＭ）の特徴のために、セルフループ１１４を含むことがある。
【００７８】
セルフループ１１４は、状態１０６が唯一の到来アクティブアーク１０８を有する場合にも状態１０６の更新の同期化を必要とさせ得る対応する状態の到来アークとして処理され得る。
【００７９】
同期化は、アトミックアップデートハードウェアと協働して実行され得る。それに代えて、あるいは加えて、プライベート化スキームが採用されてもよい。プライベート化スキームは、プライベートな結果を融合するための追加処理を伴い得る。同期化及びプライベート化の処理は、処理資源及び処理時間を消費し得る。
【００８０】
一実施形態において、セルフループ１１４は、１つ以上の状態１０６から削除あるいは除去され、１つ以上の対応する退出アーク１０８内でモデル化され得る。
【００８１】
セルフループ１１４は、例えば唯一の到来アーク１０８を有する状態１０６からなど、セルフループ１１４を有する全ての状態１０６、又はその部分集合（サブセット）から削除あるいは除去されてもよい。セルフループ１１４は、非イプシロンアーク１０８内でのみモデル化され得る。唯一の到来アーク１０８を有する状態１０６からのセルフループ１１４の除去又は削除は、状態１０６の更新を同期化する必要性を低減あるいは排除し得る。
【００８２】
退出アーク１０８内でのセルフループ１１４のモデル化は、セルフループ情報を格納するように、アーク１０８に関連付けられたデータ構造を変更することを含み得る。
【００８３】
セルフループ情報は、固有の尤度又は確率の情報を含み得る。セルフループ固有尤度情報は、例えば退出アーク１０８の固有尤度情報をセルフループ固有尤度情報で変更することによって等、退出アーク１０８内で黙示的にモデル化され得る。他の例では、セルフループ固有尤度情報は、例えばアーク１０８がセルフループ情報を含むかを指し示すものを格納するためのフィールドと、セルフループ情報を格納するための１つ以上の更なるフィールドとを含むように退出アーク１０８を変更することによって等、退出アーク１０８内で明示的にモデル化されてもよい。
【００８４】
対応するネットワークの横断は、退出アーク１０８内のセルフループ情報を処理するために、各繰り返し中に１つ以上の追加計算を含み得る。追加計算は、例えば図６−９に関連して後述するようにして、対応する退出アーク１０８を処理するときに実行され得る。
【００８５】
先ず、複数のセルフループ１１４を有するネットワーク１０２が生成され、複数のセルフループ１１４のうちの１つ以上が除去されて、対応する退出アーク１０８内で再モデル化され得る。ネットワーク１０２は、セルフループ情報の除去及び退出アーク１０８内でのセルフループ情報の再モデル化の後に最適化されてもよい。この後の最適化は比較的多数の状態１０６を融合することができ、それにより横断効率が向上され得る。最適化は、上述のような１つ以上のＦＳＭ最小化技術を含み得る。
【００８６】
他の例では、明示的なセルフループ１１４を用いずに、退出アーク１０８内でモデル化されたセルフループ情報を用いて、手始めにＨ変換器が生成されてもよい。そして、ＷＦＳＴネットワーク１０２を提供するように、組み立て手順及び／又はその他の最適化手順が実行され得る。最適化は比較的多数の状態１０６を融合し得る。
【００８７】
図６は、対応する状態６０６の退出非イプシロンアーク６０８−１乃至６０８−５、６０８−８及び６０８−１１内でセルフループ情報がモデル化されたネットワーク６０２を含む、グラフベースネットワーク及び推論エンジン６００のブロック図である。図１のセルフループ１１４は対応する状態６０６から削除されている。
【００８８】
推論エンジン１０４は、例えば図７−９のうちの１つ以上に関連して後述するようにしてネットワーク６０２のアーク内でモデル化されたセルフループ情報を更新するアークベースのセルフループ更新システム６０４を含み得る。
【００８９】
図７は、ネットワークのアークの少なくとも一部内でセルフループ情報がモデル化されるときの、ネットワークを横断する方法７００の処理フローチャートである。
【００９０】
ステップ７０２にて、少なくとも、内部にモデル化されたセルフループ固有尤度情報を有するアークに関して、累積尤度情報が更新される。故に、図９に関連して後述するように、例えば図６のイプシロンアーク６０８−６、６０８−７及び６０８−８など一部のアーク１０８は、ステップ７０２での更新から省略され得る。
【００９１】
ステップ７０４にて、更新されたアークの目的状態が、対応する更新後のアークに従って更新される。ステップ７０４での目的状態の更新は、ステップ７０２での更新の後に実行され得る。ステップ７０４で目的状態が複数の到来アークに応答して更新されるべき場合、ステップ７０４での更新は、更新の同期化を含み得る。
【００９２】
ステップ７０６にて、イプシロンアークが更新され得る。
【００９３】
ステップ７０８にて、ステップ７０４で更新された目的状態を起源とするアークが、更新後の目的状態に従って更新される。ステップ７０８でのアークの更新は、ステップ７０４での全ての目的状態の更新の後に実行され得る。
【００９４】
図８は、セルフループ固有尤度情報を含むようにアークの少なくとも一部の固有尤度情報が変更されるときの、ネットワークを横断する方法８００の処理フローチャートである。
【００９５】
ステップ８０２にて、現在の繰り返しのアクティブアークが特定される。
【００９６】
ステップ８０４にて、全てのアクティブアークの累積尤度情報、又は全てのアクティブな非イプシロンアークの累積尤度情報が、対応する固有尤度情報に基づいて更新される。これは基本的に、セルフループ固有尤度情報を含むアークに関してセルフループ更新を実行する。
【００９７】
ステップ８０６にて、アクティブアークの目的状態の累積尤度情報が、対応するアクティブアークの更新後の累積尤度情報を用いて更新される。
【００９８】
方法８００が、例えばスレッドレベル及び／又はデータレベルの並列処理環境などの並列処理環境で実行される場合、また、状態が複数の到来アクティブアークに応答して更新される場合、ステップ８０６での目的状態の更新は、複数の到来アークに関する更新を同期化することを含み得る。セルフループ情報は状態ではなくアーク内でモデル化されているので、同期化は、単一の到来アークに応答して更新される状態に関しては省略され得る。
【００９９】
ステップ８０８にて、イプシロンアークが更新される。
【０１００】
ステップ８０６での累積尤度情報の更新は、更新された目的状態の１つ以上の退出アークをアクティブにし得る。そのようなアークにことを、ここでは、新たにアクティブにされたアークと称する。ステップ８１０にて、新たにアクティブにされたアークの累積尤度情報が、ステップ８０６で更新された対応する目的状態の更新後の累積情報を用いて更新される。ステップ８１０での新たにアクティブにされたアークの更新は、ステップ８０６での全てのアクティブアークの処理の後に実行され得る。
【０１０１】
方法８００又はその一部は、全てのアクティブアーク及び対応する目的状態が更新されるまで、反復的に繰り返され得る。その後の繰り返しにおいて、ステップ８０４及び８０６でのアクティブアークの処理は、ステップ８１２での先行の繰り返しにて特定された、新たにアクティブにされたアークを含み得る。
【０１０２】
１つ以上のアクティブアークは、新たにアクティブにされたアークを含めて、例えば対応する累積尤度の値が閾値未満であるとき等には、その後の繰り返しにおける更なる処理から省略されてもよい。
【０１０３】
図９は、セルフループ固有尤度情報とセルフループ固有尤度情報の存在を指し示すもの（インジケーション）とを保持するようにネットワークのアークが複数のフィールドを含むときの、ネットワークを横断する方法９００の処理フローチャートである。
【０１０４】
ステップ９０２にて、現繰り返しのアクティブアークが特定される。
【０１０５】
ステップ９０４にて、セルフループ固有尤度情報の存在のインジケーションを含むアクティブアークの累積尤度情報が、該アーク内の対応するセルフループ固有尤度情報に基づいて更新される。これは基本的に、セルフループ固有尤度情報の存在のインジケーションを含むアークに関してのみセルフループ更新を実行する。
【０１０６】
ステップ９０６にて、全てのアクティブアーク、又は少なくとも全てのアクティブ非イプシロンアークの目的状態の累積尤度情報が、対応するアクティブアークの更新後の累積尤度情報を用いて更新される。
【０１０７】
方法８００に関して上述したように、ステップ９０６での目的状態の更新は、複数の到来アークに関する更新を同期化することを含み得る。
【０１０８】
ステップ９０８にて、イプシロンアークが更新され得る。
【０１０９】
ステップ９１０にて、ステップ８１０に関して上述したようにして、新たにアクティブにされたアークの累積尤度情報が、ステップ９０６で更新された対応する目的状態の更新後の累積情報を用いて更新される。
【０１１０】
方法９００又はその一部は、方法８００に関して上述したように、全てのアクティブアーク及び対応する目的状態が更新されるまで、反復的に繰り返され得る。
【０１１１】
キャッシュ認識動的タスクオーダリング
マルチプロセッサ環境においては、複数の処理スレッド間で作業負荷を平衡させるために、動的タスクスケジューリングが利用され得る。
【０１１２】
従来のタスクスケジューラ発見的問題解決法（ヒューリスティックス）は、例えばＷＦＳＴに基づく探索などの一部の環境では最適でないことがある。例えば、アクティブ状態又はアクティブアークなどのデータオブジェクトが現在の繰り返し又はフレームで処理されるべきで、該データオブジェクトが先行の繰り返しで処理されていた場合、該データオブジェクトに付随するデータは、該データオブジェクトが以前に処理されたスレッドに関連付けられた位置にキャッシュされたままとなり得る。このデータオブジェクトを現繰り返しの同一スレッドにて処理することは有用である。既存のキャッシュデータが、キャッシュデータの再取出し又は再計算の必要性を低減あるいは排除し得るためである。しかしながら、従来の動的スケジューラ発見的問題解決法は、データオブジェクトを、該データオブジェクトが以前に割り当てられていたのと同一のスレッドに割り当てようとはしていない。
【０１１３】
ここでは、データの場所に基づいてタスクを順序付ける方法及びシステムを開示する。ここでは、これを動的キャッシュ認識タスクオーダリングと称する。動的キャッシュ認識タスクオーダリングは、対応するデータオブジェクトのデータキャッシュ位置に少なくとも部分的に基づいて、タスクをスレッドに関連付ける。
【０１１４】
ここではまた、ここで開示する動的キャッシュ認識タスクオーダリングを用いてＷＦＳＴベースネットワークを探索する方法及びシステムを開示する。
【０１１５】
キャッシュ認識動的タスクオーダリングは、黙示的なキャッシュ認識タスクスケジューリング、又は明示的なキャッシュ認識タスクスケジューリングを含み得る。
【０１１６】
黙示的なキャッシュ認識タスクスケジューリングは、黙示的あるいは間接的に動的タスクマネジャに特定のスレッドへのタスクの割り当てを行わせるように、待ち行列内のタスクを順序付け得る。待ち行列の順序付けは、例えば図１０及び１２に関連して後述するように、タスクマネジャの発見的問題解決に基づき得る。
【０１１７】
明示的なキャッシュ認識タスクスケジューリングは、例えば図１１及び１３に関連して後述するように、データオブジェクトが以前に処理されたスレッドを特定し、該データオブジェクトに関する新たなタスクを同一のスレッドに明示的に割り当て得る。
【０１１８】
図１０は、タスク待ち行列１００６内のタスク１００２を順序付けるキューマネジャ１００４と、複数の処理スレッド１０１０間でタスク待ち行列１００６からのタスク１００２をスケジューリングする動的タスクマネジャ１００８とを含む、黙示的なキャッシュ認識環境１０００のブロック図である。
【０１１９】
タスク１００２はアクティブ状態１０６及び／又はアクティブアーク１０８と関連付けられ得る。タスク１００２の処理中、スレッド１０１０は次の繰り返しのアクティブ状態１０６及び／又はアクティブアーク１０８のリスト１０１２を生成し得る。対応する新たなタスク１００２が、リスト１０１２内で特定されたアクティブ状態１０６及び／又はアクティブアーク１０８に関して定義される。
【０１２０】
リスト１０１２内で特定された次の繰り返しのアクティブ状態１０６及び／又はアクティブアーク１０８のうちの少なくとも一部は、対応するスレッド１０１０を用いて現繰り返しにおいて既にアクティブになっている。
【０１２１】
キューマネジャ１００４は、対応する状態１０６及び／又はアーク１０８が特定されたリスト１０１２に基づいて、動的タスクマネジャ１００８にタスク１００２を、該タスク１００２を開始したスレッド１０１０に割り当てさせるように、待ち行列１００６内のタスク１００２を配列するように構成され得る。故に、状態１０６及び／又はアーク１０８が連続した繰り返し内でアクティブである場合、対応するタスク１００２は同一のスレッド１０１０に割り当てられ得る。
【０１２２】
例えば、アーク１０８に関連付けられたタスク１００２が、現繰り返しにおいてスレッド１０１０−１に割り当てられ得る。現繰り返しにおいてタスク１００２を処理する際、スレッド１０１０−１は、該アーク１０８が次の繰り返しにおいてアクティブであるべきことを指し示すようにリスト１０１２−１を生成し得る。該アーク１０８に対応する新たなタスク１００２が次の繰り返しで呼び出され、キューマネジャ１００４は、動的タスクスケジューラに該新たなタスク１００２をスレッド１０１０−１に割り当てさせるように、待ち行列１００６内の該新たなタスク１００２を配置し得る。
【０１２３】
キューマネジャ１００４は、動的タスクマネジャ１００８のスレッド割当てに影響を及ぼすために、動的タスクマネジャ１００８によって使用される経験則に従って待ち行列１００６内のタスク１００２を順序付ける経験則（ヒューリスティック）システム１０１４を含み得る。
【０１２４】
例えば、タスクマネジャ１００８は、タスク１００２をスレッド１０１０に総当たり的に割り当てるように構成されることができ、循環的に、第１のタスク１００２がスレッド１０１０−１に割り当てられ、第２のタスク１００２がスレッド１０１０−２に割り当てられ、後続のタスク１００２が後続のスレッド１０１０に割り当てられる。同様に、キューマネジャ１００４は、待ち行列１００６内のタスク群１００２を、リスト１０１２に従って総当たり的に配置するように構成され得る。例えば、リスト１０１２−１からの１つのタスク１００２が最初に待ち行列１００６に割り当てられ、リスト１０１２−２からの１つのタスク１００２が続けられ、後続のリスト１０１２からの後続のタスク１００２が続けられ得る。
【０１２５】
他の一例として、動的タスクマネジャ１００８は、待ち行列１００６からタスク群１００２を取り出し、該タスク群１００２を複数組の連続タスク群１００２に分離し、且つ各組の連続タスク群１００２を順次、総当たり的にスレッド群１０１０に割り当てるように構成されてもよい。例えば、待ち行列１００６が８個のタスク１００２（Ａ乃至Ｈ）を含み、且つスレッド１０１０が４個のスレッド１０１０−１乃至１０１０−４を含む場合、動的タスクマネジャ１００８は、タスクＡ及びＢをスレッド１０１０−１に、タスクＣ及びＤをスレッド１０１０−２に、タスクＥ及びＦをスレッド１０１０−３に、そしてタスクＧ及びＨをスレッド１０１０−４に割り当て得る。キューマネジャ１００４は、待ち行列１００６内のタスクＡ乃至Ｈを、タスクＡ乃至Ｈを開始する元となったリスト１０１２を考慮して配列するように構成され得る。
【０１２６】
図１１は、データ局所情報を管理するキャッシュ認識システム１１０４と、少なくとも部分的にデータ局所情報に基づいて、タスク１１０２を処理スレッド１１１０に割り当てる動的タスクマネジャ１１０８とを含む、明示的なキャッシュ認識環境１１００のブロック図である。
【０１２７】
キャッシュ認識システム１１０４は、タスク１１０２がスレッド１１１０に割り当てられるときに動的タスクマネジャ１１０８からデータ局所情報１１０８を受信する記録システム１１０６を含み得る。データ局所情報１１０８は、タスク１１０２が割り当てられたスレッド１１１０を特定し得る。これは、対応するデータオブジェクト１１１６に付随するデータがキャッシュされたキャッシュ位置に相当し得る。
【０１２８】
記録システム１１０６は、タスク１１０２が対象とするデータオブジェクト１１１６にデータ局所情報１１０８を関連付けるように構成され得る。データオブジェクト１１１６は、状態１０６及び／又はアーク１０８を表すことができ、対応するデータ局所情報１１０８を記録するフィールドを含み得る。
【０１２９】
キャッシュ認識システム１１０４は、データオブジェクト１１１６に関するタスク１１０２がスレッド１１１０に割り当てられるべきときに、該データオブジェクト１１１６に関連付けられたデータ局所情報１１０８を取り出す検索システム１１１２を含み得る。
【０１３０】
動的タスクマネジャ１１０８は、取り出されたデータ局所情報１１１４に少なくとも部分的に基づいてタスク１１０２をスレッド１１１０に割り当てるように構成され得る。
【０１３１】
動的タスクマネジャ１１０８は、タスク１１０２をスレッド１１１０に割り当てるに際して、例えばスレッド１１１０間で処理負荷を平衡化することなど、１つ以上のその他の因子を考慮に入れるように構成されてもよい。
【０１３２】
キャッシュ認識システム１１０４及び動的タスクマネジャ１１０８は、別々に実装されてもよいし、ともに一体化されて実装されてもよい。
【０１３３】
図１２は、データ局所情報に少なくとも部分的に基づいてタスクを順序付ける方法１２００の処理フローチャートである。方法１２００は、図１０に関連して上述したようにして実行され得る。しかしながら、方法１２００は図１０の例に限定されるものではない。
【０１３４】
ステップ１２０２にて、次の繰り返しのアクティブデータオブジェクトのリストが、複数の処理スレッドの各々から受信される。データオブジェクトはグラフベースネットワークのアーク及び／又は状態を表し得る。
【０１３５】
ステップ１２０４にて、次の繰り返しのアクティブデータオブジェクトに関するタスクが受信される。
【０１３６】
ステップ１２０６にて、タスクが、対応するデータオブジェクトが特定された上記リストに基づいて、処理スレッドに関連付けられる。
【０１３７】
ステップ１２０８にて、タスクを関連付けられた処理スレッドへと向けるために、タスクがタスクマネジャ経験則に従って順序付けられる。タスクは、タスクマネジャがタスクをスレッドに割り当てる元となったタスク待ち行列内で順序付けられてもよい。
【０１３８】
図１３は、少なくとも部分的にデータ局所情報に基づいてタスクを処理スレッドに割り当てる方法１３００の処理フローチャートである。方法１３００は、図１１に関連して上述したようにして実行され得る。しかしながら、方法１３００は図１１の例に限定されるものではない。
【０１３９】
ステップ１３０２にてタスクが受信される。タスクは、グラフベースネットワークの状態及び／又はアークを表すデータオブジェクトに関連付けられ得る。
【０１４０】
ステップ１３０４にて、データオブジェクトがスレッドに関連付けられているかについて決定が為される。これは、例えばスレッド識別子などのキャッシュデータ局所情報がデータオブジェクトに関連付けられているかを決定することを含み得る。
【０１４１】
データオブジェクトがスレッドに関連付けられていない場合、後述するように、処理はステップ１３０６へと進む。
【０１４２】
タスクがスレッドに関連付けられている場合、ステップ１３０８にて更なる決定が為される。
【０１４３】
ステップ１３０８にてスレッドがそのタスクを受け入れることができる場合、ステップ１３１０にてタスクはそのスレッドに割り当てられる。スレッドがそのタスクを受け入れることができない場合、又は１つ以上のその他の考慮に基づいて別のスレッドの方がそのタスクに適している場合には、処理はステップ１３０６へと進む。
【０１４４】
ステップ１３０６にて、１つ以上のその他の因子に基づいて、データオブジェクトがスレッドに割り当てられ、対応するキャッシュデータ局所情報が該データオブジェクトに関連付けられる。キャッシュデータ局所情報は、該タスクが割り当てられるスレッドの識別子を含み得る。
【０１４５】
その後、そのデータオブジェクトがステップ１３０２での別のタスクの対象となるとき、そのタスクはステップ１３１０にて同一のスレッドに割り当てられ得る。
【０１４６】
アクティブアークに基づく横断、アーク内でモデル化されたセルフループ情報の処理、キャッシュ認識動的タスクオーダリングは、単独で実行されてもよいし、且つ／或いは相互に様々に組み合わされて実行されてもよい。
【０１４７】
ここで説明した１つ以上の機能は、ディスクリートロジック及び集積回路ロジック、特定用途向け集積回路（ＡＳＩＣ）ロジック、並びにマイクロコントローラを含むハードウェア、ソフトウェア、ファームウェア及びそれらの組み合わせにて実装されてもよいし、特定ドメイン向けの集積回路パッケージ又は複数の集積回路パッケージの組み合わせの一部として実装されてもよい。ここでは、ソフトウェアという用語は、ここで開示した１つ以上の機能及び／又はそれらの組み合わせをコンピュータシステムに実行させるコンピュータプログラムロジックを格納したコンピュータ読み取り可能媒体を含むコンピュータプログラムの製造物を意味する。
【０１４８】
図１４は、グラフベースネットワークを横断するように構成されたコンピュータシステム１４００のブロック図である。
【０１４９】
コンピュータシステム１４００は、コンピュータプログラムロジックを実行する１つ以上のコンピュータ命令処理ユニット（ここではプロセッサ又はコア１４０２として示す）を含み得る。
【０１５０】
コンピュータシステム１４００は更に、プロセッサ１４０２に１つ以上の機能を実行させるコンピュータプログラムロジック又は命令１４０６を格納したコンピュータ読み取り可能媒体を含め、キャッシュ、メモリ及び／又はストレージ（以下、“メモリ”）１４０４を含み得る。
【０１５１】
メモリ１４０４は更に、命令１４０６を実行する際にプロセッサ１４０２によって使用される、且つ／或いは命令１４０６の実行に応答してプロセッサ１４０２によって生成される、データ１４０８を含んでいる。
【０１５２】
図１４の例において、ロジック１４０６は、上述の１つ以上の例にて説明したようにプロセッサ１４０２にグラフベースネットワーク１４１２を横断させる推論エンジンロジック１４１０を含んでいる。ネットワーク１４１２は、図１のネットワーク１０２又は図６のネットワーク６０２に相当し得る。ネットワーク１４１２は、当該ネットワーク１４１２の状態及びアークのうちの１つ以上を表すデータオブジェクト１４１４を含み得る。
【０１５３】
推論エンジンロジック１４１０は、図１−５のうちの１つ以上に関連して上述したようにプロセッサ１４０２にネットワーク１４１２のアクティブアークを横断させるアクティブアーク横断ロジック１４１６を含み得る。
【０１５４】
セルフループ情報がネットワーク１４１２のアーク内でモデル化される場合、推論エンジンロジック１４１０は、図６−９のうちの１つ以上に関連して上述したようにプロセッサ１４０２にセルフループ情報を更新させるアークベースのセルフループ更新ロジック１４１８を含み得る。
【０１５５】
コンピュータシステム１４００は、実行時にタスクのスケジューリング又はタスクの処理スレッドへの割り当てを行う動的タスクマネジャ１４２２を含み得る。動的タスクマネジャ１４２２は、図１０の動的タスクマネジャ１００８及び図１１の動的タスクマネジャ１１０８のうちの１つ以上に対応し得る。
【０１５６】
コンピュータシステム１４００が動的タスクマネジャ１４２２を含む場合、推論エンジンロジック１４１０は、データオブジェクトに関連するタスクを、該データオブジェクトに関する先行タスクが割り当てられた処理ロジックに基づいて順序付けることをプロセッサ１４０２に行わせるキャッシュ認識オーダリングロジック１４２０を含み得る。キャッシュ認識オーダリングロジック１４２０は、図１０及び１２のうちの１つ以上に関連して上述したようにタスクマネジャ１４２２の経験則に従ってスレッドを順序付け且つタスクマネジャ１４２２にタスクの対応するスレッドへの割当てを行わせるロジックを含み得る。キャッシュ認識オーダリングロジック１４２０は、図１０のキューマネジャ１００４に対応し得る。キャッシュ認識オーダリングロジック１４２０は、推論エンジンロジック１４１０の外部に実装されてもよいし、推論エンジンロジック１４１０とは独立に実装されてもよい。
【０１５７】
他の例では、図１１及び１３のうちの１つ以上に関連して上述したように、動的タスクマネジャ１４２２は明示的に、データオブジェクト１４１４に関連付けられたデータ局所情報に基づいてタスクをスレッドに割り当てるように構成されてもよく、コンピュータシステム１４００は更に、データ局所情報をデータオブジェクト１４１４に関連付け且つデータ局所情報を取り出して動的タスクマネジャ１４２２に提供するデータ位置管理システム１４２４を含んでいてもよい。データ位置管理システム１４２４は、図１１のキャッシュ認識システム１１０４に対応し得る。データ位置管理システム１４２４は、ハードウェア、ソフトウェア、ファームウェア、ロジック１４０６及びこれらの組み合わせにて実装され得る。
【０１５８】
コンピュータシステム１４００は、当該コンピュータシステム１４００内に１つ以上の通信パスを提供する情報通信基盤１４２６を含み得る。
【０１５９】
コンピュータシステム１４００は、当該コンピュータシステム１４００と１つ以上のその他のシステムとの間に１つ以上の通信パスを提供する入力／出力コントローラ１４２８を含み得る。
【０１６０】
ここでは、機能、特徴及びそれらの関係を示す機能構築ブロックの助けを借りて方法及びシステムを開示した。これらの機能構築ブロックの境界のうちの少なくとも一部は、説明の便宜のためにここで自由に定めたものである。代替的な境界が定められてもよい。
【０１６１】
ここでは様々な実施形態を説明したが、理解されるように、これらの実施形態は、限定としてではなく単に例として提示したものである。当業者に明らかなように、ここで開示した方法及びシステムの精神及び範囲を逸脱することなく、形態及び細部の様々な変更が為され得る。故に、請求項の広さ及び範囲は、ここで開示した実施形態例の何れにも限定されるべきでない。
【符号の説明】
【０１６２】
１００、６００ システム
１０２、６０２ グラフベースネットワーク
１０４ 推論エンジン
１０６、６０６ 状態
１０８、６０８ アーク（パス）
１１０ 特徴ベクトル
１１２ 文法要素
１１４ セルフループ
３０２ アクティブアーク横断システム
６０４ アークベースセルフループ更新システム
１０００、１１００ キャッシュ認識環境
１００２、１１０２ タスク
１００４ キューマネジャ
１００６ 待ち行列
１００８ 動的タスクマネジャ
１０１０ スレッド
１０１２ アクティブオブジェクトのリスト
１０１０、１１１０ スレッド
１０１４ 経験則システム
１１０４ キャッシュ認識システム
１１０６ 記録システム
１１０８ 動的タスクマネジャ
１１０８、１１１４ データ局所性情報
１１１２ 検索システム
１１１６ データオブジェクト
１４００ コンピュータシステム
１４０２ プロセッサ
１４０４ キャッシュ／メモリ／ストレージ
１４０６ コンピュータプログラムロジック／命令
１４０８ データ
１４１０ 推論エンジンロジック
１４１２ グラフベースネットワーク
１４１４ データオブジェクト
１４１６ アクティブアーク横断ロジック
１４１８ アークベースセルフループ更新ロジック
１４２０ キャッシュ認識タスクオーダリングロジック
１４２２ タスクマネジャ
１４２４ キャッシュ認識システム
１４２６ 通信基盤
１４２８ 入力／出力コントローラ
【技術分野】
【０００１】
本発明の実施形態は、グラフベースのネットワークを横断（トラバース）するための方法及びシステムに関する。
【背景技術】
【０００２】
音声ストリームを表す特徴ベクトルのストリームを生成するために、音声特徴抽出器が開発されている。
【０００３】
音声ベースの特徴ベクトルを書き言葉の単語シーケンスに関連付けるために、グラフベースの音声認識ネットワークが開発されている。
【０００４】
対応する単語シーケンスを特定するために、音声ベースの特徴ベクトルのストリームに応答して、グラフベースの音声認識ネットワークの複数の状態間を繰り返し行き来するように、推論（インファレンス）エンジンが開発されている。
【０００５】
音声認識システムは、大語彙連続音声認識（large vocabulary continuous speech recognition；ＬＶＣＳＲ）システムを含む重み付き有限状態変換器（Weighted Finite State Transducer；ＷＦＳＴ）を用いて開発されてきた。
【０００６】
状態ベースのネットワーク横断（トラバーサル）技術は、マルチスレッド的且つ単一命令複数データ（single instruction，multiple data；ＳＩＭＤ）的に実装されてきた。音声認識ネットワークの状態は、対応する状態への追加の到来ループとして従来から取り扱われているセルフループを含み得る。マルチスレッドＳＩＭＤ処理環境においては、故に、状態がセルフループに加えて唯一の到来アークを含む場合であっても、同期化が必要となり得る。さらに、状態ベースのＳＩＭＤ横断技術は、ＳＩＭＤ処理レーンを完全に利用することができないことがあり、それにより、ベクトル非効率性がもたらされ得る。これは、ＳＩＭＤ処理の利益を相殺してしまい得る。
【０００７】
包括的な動的タスクスケジューリング技術がマルチプロセッサシステム用に開発されている。そのような包括的な技術は、例えば音声認識ネットワークの横断などの一部の用途では最適でないことがある。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の実施形態は、グラフベースのネットワークを横断するための方法及びシステムを提供する。
【課題を解決するための手段】
【０００９】
一態様に従って、ネットワークのアークの入力ラベルを、前記アークの出力文法要素のリストに変換する方法及びシステムが提供される。当該方法及びシステムは、特徴ベクトルのストリームに応答してネットワークを繰り返し横断することを含む。ネットワークの状態のシーケンスに対応するネットワークのアークの入力ラベルが、文法要素のシーケンスに対応する前記アークの出力文法要素のリストに変換される。当該方法及びシステムは更に、データオブジェクトに関するタスクを、該データオブジェクトに関する先行タスクが割り当てられた処理スレッドに基づいて順序付けることを含む。
【図面の簡単な説明】
【００１０】
【図１】グラフベースネットワーク及び推論エンジンを示すブロック図である。
【図２】グラフベースネットワークを横断する方法を示す処理フローチャートである。
【図３】推論エンジンがアクティブアーク横断システムを含む図１のシステムを示すブロック図である。
【図４】アクティブアークを処理する方法を示す処理フローチャートである。
【図５】グラフベースネットワークの目的状態を更新する方法を示す処理フローチャートである。
【図６】対応する状態の退出アーク内でセルフループ情報がモデル化される別のグラフベースネットワーク及び推論エンジンを示すブロック図である。
【図７】ネットワークのアークの少なくとも一部内でセルフループ情報がモデル化されるときの、ネットワークを横断する方法を示す処理フローチャートである。
【図８】セルフループ固有尤度情報を含むようにネットワークのアークの一部の固有尤度情報が変更されるときの、ネットワークを横断する方法を示す処理フローチャートである。
【図９】セルフループ固有尤度情報とセルフループ固有尤度情報の存在を指し示すものとを保持するようにネットワークのアークが複数のフィールドを含むときの、ネットワークを横断する方法を示す処理フローチャートである。
【図１０】タスク待ち行列内のタスク群を順序付けるキューマネジャと、複数の処理スレッド間でタスク待ち行列からのタスク群をスケジューリングする動的タスクマネジャとを含む、黙示的なキャッシュ認識環境を示すブロック図である。
【図１１】データ局所情報をデータオブジェクトと関連付けるキャッシュ認識システムと、少なくとも部分的にデータ局所情報に基づいて、タスクを処理スレッドに割り当てる動的タスクマネジャとを含む、明示的なキャッシュ認識環境を示すブロック図である。
【図１２】データ局所情報に基づいてタスク群を順序付ける方法を示す処理フローチャートである。
【図１３】少なくとも部分的にデータ局所情報に基づいてタスクを処理スレッドに割り当てる方法を示す処理フローチャートである。
【図１４】グラフベースネットワークを横断するように構成されたコンピュータシステムを示すブロック図である。 図面において、参照符号の１桁目は、その参照符号が最初に現れる図を指し示す。
【発明を実施するための形態】
【００１１】
図１は、グラフベースネットワーク１０２と推論エンジン１０４とを含むシステム１００のブロック図である。
【００１２】
ネットワーク１０２は、複数の状態１０６と、状態１０６間のアーク１０８とを含んでおり、ネットワークの一連の状態に対応するアーク１０８の入力ラベルを、一連の文法要素に対応するアーク１０８の出力文法要素のリストに変換する。
【００１３】
推論エンジン１０４は、特徴ベクトル１１０のストリームに応答して、ネットワーク１０２を繰り返し横断するように構成されている。
【００１４】
特徴ベクトル１１０は、連続音声、例えばビデオフレームのシーケンス又はビデオクリップなどの画像シーケンス、並びに連続テキストのうちの１つ以上を表し得る。特徴ベクトル１１０は、音響信号内に埋め込まれた音声、ビデオ信号内に埋め込まれた視覚映像、及びコンピュータ読み取り可能な信号内に埋め込まれたテキスト文字及びフォーマット情報のうちの１つ以上を含み得る１つ以上の連続信号及び／又は不連続信号から生成され得る。オーディオベースの特徴ベクトル１１０は、言葉、単語の一部又は音波を表し得る。ビデオベースの特徴ベクトル１１０は、動き、色、物体、及び／又はフレーム間でのそれらの変化のうちの１つ以上を表し得る。各特徴ベクトル１１０は、信号の対応する部分又はフレームに付随する情報を保持するために複数のフィールド（場）を含み得る。
【００１５】
文法は、ヒトが読み取り可能な言語又はコンピュータが読み取り可能な言語のうちの１つ以上を含み得る書き言葉に相当し得る。
【００１６】
システム１００は、オーディオ及び／又はビデオを書き言葉に変換する音声及び／又は映像認識システムに相当し得る。それに代えて、あるいは加えて、システム１００は、第１の書き言葉を第２の書き言葉へと変換する言語翻訳システムに相当してもよい。第１及び第２の書き言葉のうちの１つ以上は、話された言葉及び／又はコンピュータ読み取り可能言語に相当してもよい。
【００１７】
推論エンジン１０４は、特徴ベクトル１１０のストリームに応答して、状態１０６の１つ以上のシーケンスと、ここではパスとも称する対応するアーク１０８とを特定し、それらを繰り返しリファインするように構成され得る。特徴ベクトルストリーム１１０に潜在的に対応するとして所与の繰り返し中に特定された状態１０６及び／又はアーク１０８のことを、ここでは、その繰り返しのアクティブ状態１０６及びアクティブアーク１０８と呼ぶ。
【００１８】
所与の繰り返しにおいて、複数組のアクティブアーク１０８を介して到達可能なアクティブ状態１０６の組が特定されてもよい。換言すれば、複数のパスが、同一でない組のアーク１０８に沿って横断される１つの共通する組の状態１０６を含み得る。
【００１９】
推論エンジン１０４は、状態１０６及びアーク１０８が特徴ベクトルストリーム１１０に対応する尤度を表す可能性指標を、状態１０６及びアーク１０８に関連付けるように構成され得る。
【００２０】
推論エンジン１０４は、１つ以上のデータオブジェクトを用いて状態１０６及び／又はアーク１０８を表すように構成されることができ、また、ネットワーク１０２が横断されるときに対応するデータオブジェクトを更新するように構成され得る。状態１０６及び／又はアーク１０８の処理は、対応するデータオブジェクトを処理することを含み得る。
【００２１】
アーク１０８の起源となる状態１０６のことを、ここでは、起源状態１０６と称する。アーク１０８が向けられる状態１０６のことを、ここでは、目的状態１０６と称する。
【００２２】
システム１００は、指数関数的な順列及び単語間の未知の境界セグメンテーションを含み得る比較的大きい語彙から単語を認識する大語彙連続音声認識（ＬＶＣＳＲ）に相当し得る。
【００２３】
一組の可能性ある単語シーケンスＷが与えられるとき、観測されたオーディオ特徴Ｏに関して最も可能性の高い単語シーケンス：
【００２４】
【数１】
は、数学的に：
【００２５】
【数２】
として表され得る。
【００２６】
オーディオ特徴と単語シーケンスＷの従前の尤度との積であるＰ（Ｏ｜Ｗ）Ｐ（Ｗ）は、例えばビタビ（Ｖｉｔｅｒｂｉ）探索アルゴリズムを用いるなど、動的プログラミング再帰を用いて計算され得る。
【００２７】
時間ｔに単語シーケンスｗｔｊを有する状態ｊにある横断プロセスの尤度は、先行状態での尤度から：
【００２８】
【数３】
として導出され得る。ここで、ａｔｊは状態ｉ（ｓｉ）から状態ｊ（ｓｊ）への遷移確率であり、ｂ（Ｏｔ；ｍｋ）は状態ｉ（ｓｉ）から状態ｊ（ｓｊ）への遷移時のコンテキスト依存状態ｋ（ｍｋ）の観測確率である。
【００２９】
推論エンジン１０４は、一連の時間ステップにわたってアルゴリズムを繰り返し処理することができ、各時間ステップにおける単語又は文法要素シーケンスの尤度は、先行する時間ステップで計算された尤度に依存する。各繰り返しにおいて、特徴ベクトル１１０の最も可能性ある選択すべき解釈を表す多数の、恐らくは何千もの、アクティブ状態１０６が存在し得る。最も可能性ある状態１０６の組が、特徴ベクトル１１０のストリームの最後で選択され得る。
【００３０】
ネットワーク１０２は、重み付き有限状態変換器（ＷＦＳＴ）に従って生成され得る。ＷＦＳＴは、各々が例えば後述するもののような複数の特性を含むアーク群１０８のリストによって表されるＭｅａｌｙの有限状態マシン（ＦＳＭ）である。
【００３１】
ネットワーク１０２は、隠れマルコフモデル（Hidden Markov Model；ＨＭＭ）音響モデルＨ、コンテキストモデルＣ、単語の発音辞書Ｌ、及びここではＨレベルネットワークと称するＨ−Ｃ−Ｌ−Ｇ型ＷＦＳＴに構成され得る言語モデルＧのうちの１つ以上を含み得る複数の階層的な知識源又はモデルを含み得る。結合されたＷＦＳＴが、ＦＳＭ最小化技術を用いて最適化されて、認識ネットワークのフラット化されたＦＳＭ表現として用いられてもよい。ＷＦＳＴは、ランタイムにて横断すべく、階層的な知識源をオフラインで単一階層のＦＳＭへとフラット化することによって、認識処理を単純化し得る。
【００３２】
ＨレベルＷＦＳＴにおいて、個々のアーク１０８は、対応する文法要素に関連付けられ得る。推論エンジン１０４は、アーク上の入力ラベルのリストとしてのＨＭＭ状態のシーケンスを、アーク上の出力ワードのリストとしての単語のシーケンスに変換し得る。
【００３３】
ＨレベルＷＦＳＴにおいて、１つ以上のアーク１０８は：
アーク１０８が横断されるときに消費される入力ラベル又はシンボル；
入力ラベルが変換された結果の出力ラベル又は単語；
ソース状態；
目的状態；及び
ソース状態からのアークに従う固有尤度；
を含み得る。
【００３４】
１つ以上の状態１０６は：
状態１０６からの第１の退出アーク１０８へのポインタ；
状態１０６からの退出アークの数を指し示すもの；及び
状態１０６からの退出イプシロンアークの数を指し示すもの；
を含み得る。
【００３５】
イプシロンアークについては図２に関連して後述する。
【００３６】
アーク群１０８は、配列にて管理され、起源状態１０６によってグループ分けされ得る。
【００３７】
ＷＦＳＴに基づく探索において、入力シンボル又は特徴ベクトル１１０の組に対して、ネットワーク１０２を通り抜ける最も可能性あるパスの組が辿られる。各パスの情報は、該パスの先頭に結合され得る。この情報は、例えば潜在的に特徴ベクトル１１０に一致するとして特定された単語などの、そのパスに沿った出力シンボルの組と、そのパスの対応する累積尤度とを含み得る。
【００３８】
この情報は、出力シンボルの組へのポインタ及び累積尤度の値を含み得るデータ構造内で管理され得る。データ構造は、例えば１つ以上の状態１０６がセルフループ１１４を含む場合など、状態１０６に関連付けられ得る。他の例では、データ構造は、例えば図６−９に関連して後述するようにセルフループ情報が１つ以上のアーク１０８内でモデル化される場合など、対応するアーク１０８に関連付けられ得る。
【００３９】
ＷＦＳＴベースの推論エンジンは、用途にとらわれるものではなく、例えばテキスト処理や画像処理などのその他のドメインでも採用され得る。
【００４０】
アーク１０８は、図１にそれぞれ破線及び実線で示すイプシロンアーク及び非イプシロンアークを含み得る。イプシロンアークは、如何なる入力シンボルをも消費することなく横断される。非イプシロンアークは、状態遷移を実行するために１つの入力シンボルを消費する。ＨレベルＷＦＳＴ認識ネットワークでは、ネットワーク１０２の入力ラベルは、コンテキスト依存のＨＭＭ状態を表す。
【００４１】
図２は、或る１つの繰り返し中に入力フレーム又は特徴ベクトル１１０に応答してネットワーク１０２を横断する方法２００の処理フローチャートである。
【００４２】
ステップ２０２にて、ネットワーク１０２の入力シンボルに関して観測確率が決定される。観測確率は、例えば距離関数を計算することによる、音響入力シンボルに合致する入力特徴ベクトルの尤度指標を含み得る。観測確率は、コンテキスト依存状態のガウシアン混合モデルに従って決定され得る。ステップ２０２での観測確率の決定は、アクティブ状態の退出アーク上で入力シンボルを計算することを含むことができ、本質的あるいは専ら該計算で構成され得る。観測確率の決定は、ネットワーク１０２の音響モデルを参照することを含んでいてもよい。
【００４３】
ステップ２０４にて、非イプシロンアークが処理される。非イプシロンアークの処理は：
ステップ２０２で計算された現入力ｂ（Ｏｔ；ｍｋ）の観測確率；
ネットワーク１０２から参照される横断されているアークａｉｊの遷移確率又は重み；及び
時間ｔ−１での先行する繰り返しにて計算された先行シーケンスの尤度、すなわち、ソース状態コスト：
【００４４】
【数４】
の同時確率を計算することを含み得る。
【００４５】
同時確率はステップ２０４において、観測確率、遷移確率、及び尤度の積として決定され得る。同時確率はステップ２０４において、対数で表された値の加算として決定されてもよい。
【００４６】
ステップ２０６にて、イプシロンアークが処理される。イプシロンアークは入力シンボルを有しないため、確率は、遷移確率及び先行シーケンスの尤度の積として計算され得る。
【００４７】
ステップ２０４及び／又は２０６において、目的状態のコストは、その状態に関して最も可能性の高い、対応する到来非イプシロン及びイプシロンアークのコストを用いて更新され得る。コストはビタビ近似に従って決定され得る。
【００４８】
ネットワーク１０２は、例えば図１のイプシロンアーク１０８−７及び１０８−１０などの、連続したイプシロンアークの連鎖を含み得る。ステップ２０６でのイプシロンアークの処理は、退出イプシロンアークを伴わない状態に到達するまで、各目的状態から全ての退出イプシロンアークを横断することを含み得る。
【００４９】
ステップ２０２では、観測確率を計算するために、例えば何千もの入力シンボルといった多数の入力シンボルが用いられ得る。ステップ２０４での非イプシロンアークの処理及びステップ２０６でのイプシロンアークの処理においては、ネットワーク全体で、例えば何万ものアーク遷移といった多数のアーク遷移が横断され得る。
【００５０】
方法２００は、更なる入力フレーム又は特徴ベクトル１１０に対して繰り返され得る。
【００５１】
横断技術
推論エンジン１０４は、アクティブ状態及び／又はアクティブアークに関してネットワーク１０２を横断するように構成され得る。
【００５２】
アクティブ状態横断は、状態毎を基本にして動作する。アクティブ状態の横断は、ここではアクティブ状態伝播と称するように、アクティブ状態１０６の退出アーク１０８に関して実行され得る。それに代えて、あるいは加えて、アクティブ状態の横断は、ここではアクティブ状態集約と称するように、次の繰り返しの候補アクティブ状態１０６の到来アーク１０８に関して実行され得る。状態１０６は、その状態への到来アーク１０８が現在の繰り返しのアクティブ状態１０６を起源とするとき、次の繰り返しの候補アクティブ状態として定められ得る。
【００５３】
アクティブ状態伝播の場合、アクティブ状態１０６ごとに、退出アーク１０８が評価され、対応する目的状態１０６に結果が伝播される。
【００５４】
アクティブ状態集約の場合、候補アクティブ状態１０６の到来アーク１０８が評価され、対応する候補アクティブ状態１０６が評価結果に従って更新される。
【００５５】
アクティブアーク横断は、アーク毎を基本にして動作し、アクティブアーク１０８が、対応する起源状態から取り出されたパラメータを用いて更新され、更新されたアクティブアーク１０８が、対応する目的状態１０６を更新するために用いられる。アクティブアーク横断は、ここではアクティブアーク伝播と称するようにアクティブ状態の退出アークに関して、あるいは、ここではアクティブアーク集約と称するように候補アクティブ状態の到来アークに関して実行され得る。アクティブアーク横断を実行する方法及びシステムについては、図３−５に関連して後述する。
【００５６】
並列処理技術
推論エンジン１０４は、例えば単一命令複数データ（ＳＩＭＤ）環境においてのようなデータレベルの並列化、及び／又は例えばマルチプロセッサ若しくはマルチコア環境においてのようなスレッドレベルの並列化を用いて、ネットワーク１０２を繰り返し横断するように構成され得る。
【００５７】
ＳＩＭＤ環境におけるアクティブ状態横断では、状態１０６に関連付けられたアーク１０８は、ＳＩＭＤ作業単位又はベクトルに関連付けられることができ、アーク１０８は並列ＳＩＭＤ処理レーンで処理され得る。ＷＦＳＴベースの探索グラフにおいては、一部の状態は、その他の状態が比較的少数の退出アークを有しながら、比較的多数の退出アークを有し得る。これは、比較的低い、且つ／或いは一貫性のない、ＳＩＭＤ利用をもたらし得る。
【００５８】
ＳＩＭＤ環境におけるアクティブアーク横断では、複数のアーク１０８が、対応するソース状態又は目的状態１０６とは関係なく、ＳＩＭＤ作業単位又はベクトルに関連付けられ得る。これは、比較的一貫性のあるＳＩＭＤベクトル単位の効率性を提供し得る。
【００５９】
マルチスレッド環境におけるアクティブ状態横断では、第１のアクティブ状態１０６に関連付けられたアーク１０８は、複数の処理スレッドのうちの第１のスレッドに割り当てられることができ、第２のアクティブ状態１０６に関連付けられたアーク１０８は、複数の処理スレッドのうちの第２のスレッドに割り当てられることができ、これら第１及び第２のスレッドが並列に処理され得る。
【００６０】
マルチスレッド環境におけるアクティブアーク横断では、アクティブアーク１０８は、対応する状態１０６とは関係なく、処理スレッドに割り当てられ得る。
【００６１】
スレッドレベルの並列化の場合、タスクはランタイムに先立って特定のスレッドに事前割当てされ得る。それに代えて、あるいは加えて、図９−１２を参照して後述するように、少なくとも部分的にデータ位置情報に基づいて、実行時にタスクをスレッドに割り当てるように動的タスクマネジャが構成されてもよい。
【００６２】
同期化
ＳＩＭＤ環境及び／又はマルチスレッド環境においてのようにアクティブ状態又はアクティブアークが並列に伝播される場合、及び複数のアークが共通の目的状態に向けられる場合、例えばアトミックアップデートなどの、書込競合の解消が、基礎となるプラットフォームから提供され得る。同期化が必要とされ得る場合を削減する方法及びシステムについては、図６−８に関連して後述する。
【００６３】
アクティブ状態１０６の到来アーク１０８が並列に集約される場合、該アクティブ状態の対応する更新は、到来アーク１０８の評価結果の削減を含み得る。この削減は、基礎となるプラットフォームからの書込競合の解消支援が不要となるよう、更なるアルゴリズム的ステップを用いて、潜在的な書込競合を明示的に管理し得る。
【００６４】
アクティブアーク横断
図３は、ネットワーク１０２のアクティブアーク１０８上を横断あるいは反復するアクティブアーク横断システム３０２を推論エンジン１０４が含む場合のシステム１００のブロック図である。更に後述するように、アクティブアーク横断システム３０２は、複数のアクティブ状態からのアーク群にわたるＳＩＭＤ計算を用いてアクティブアークを横断するように構成されることができ、それにより、非常に広いベクトルユニットであっても、該ユニットの実質的に完全な使用を可能にし得る。
【００６５】
図４は、アクティブアークを処理する方法４００の処理フローチャートである。ここでは、方法４００は、図３に示したシステム１００に関連して説明される。しかしながら、方法４００は図３の例に限定されるものではない。
【００６６】
ステップ４０２にて、特徴ベクトル１１０が推論エンジン１０４で受信される。
【００６７】
ステップ４０４にて、ネットワーク１０２のアクティブアーク１０８が、アクティブアーク横断システム３０２によって特定される。アクティブアークは、アクティブ状態の退出アーク、又はアクティブアーク伝播として、且つ／或いは、候補アクティブ状態の到来アーク、又はアクティブアーク集約として特定され得る。
【００６８】
ステップ４０６にて、特定されたアクティブアーク１０８の目的状態１０６が、ステップ４０２で受信された特徴ベクトル１１０に応答して、アクティブアーク横断システム３０２によって更新される。
【００６９】
ステップ４０８にて、１つ以上の更なる特徴ベクトル１１０を受信するため、処理はステップ４０２へと戻る。
【００７０】
ステップ４１０にて、特徴ベクトル１１０の処理が完了したとき、最も高い尤度のネットワーク１０２を通り抜けるパスに対応する文法要素のシーケンスが、推論エンジン１０４によって出力される。
【００７１】
図５は、ステップ４０６に関連して上述したような目的状態１０６を更新する方法５００の処理フローチャートである。
【００７２】
ステップ５０２にて、アクティブアーク１０８の起源状態１０６から、起源状態１０６に関する尤度の指標を含む情報が取り出される。
【００７３】
ステップ５０４にて、ステップ５０２で取り出された対応する情報と、ステップ４０２で受信された１つ以上の特徴ベクトルとを用いて、アクティブアークが更新される。
【００７４】
推論エンジン１０４は、アクティブアーク１０８をＳＩＭＤ的に処理するように構成され得る。例えば、ステップ５０２での情報の取り出し、及びステップ５０４でのアクティブアークの更新は、複数のアークに関してＳＩＭＤ的に実行され得る。複数のアーク１０８を、一組のＳＩＭＤ処理レーンにて処理される作業の単位として関連付けるように、作業単位マネジャが構成され得る。複数のソース状態１０６から共通の目的状態に向けられた複数のアーク１０８がＳＩＭＤ的に処理され得る。
【００７５】
ＳＩＭＤ的なアクティブアークの処理は、対応するベクトルユニットの実質的に完全なる使用を可能にし、ＳＩＭＤ的なアクティブ状態の処理より高いベクトル効率を提供し得る。
【００７６】
退出アーク内でのセルフループのモデル化
図１においては、複数のアクティブ状態１０６及び／又はアクティブアーク１０８は、横断の一度の繰り返し中に、共通の目的状態１０６に情報を伝播し得る。複数のアクティブ状態１０６及び／又はアクティブアーク１０８が、例えばスレッドレベル及び／又はデータレベルの並列処理などにて、同時あるいは並列に処理されるとき、対応する目的状態の更新の同期化が必要となり得る。
【００７７】
ネットワーク１０２の１つ以上の状態１０６はセルフループ１１４を含み得る。ＷＦＳＴ探索グラフは、例えば基礎となる隠れマルコフモデル（ＨＭＭ）の特徴のために、セルフループ１１４を含むことがある。
【００７８】
セルフループ１１４は、状態１０６が唯一の到来アクティブアーク１０８を有する場合にも状態１０６の更新の同期化を必要とさせ得る対応する状態の到来アークとして処理され得る。
【００７９】
同期化は、アトミックアップデートハードウェアと協働して実行され得る。それに代えて、あるいは加えて、プライベート化スキームが採用されてもよい。プライベート化スキームは、プライベートな結果を融合するための追加処理を伴い得る。同期化及びプライベート化の処理は、処理資源及び処理時間を消費し得る。
【００８０】
一実施形態において、セルフループ１１４は、１つ以上の状態１０６から削除あるいは除去され、１つ以上の対応する退出アーク１０８内でモデル化され得る。
【００８１】
セルフループ１１４は、例えば唯一の到来アーク１０８を有する状態１０６からなど、セルフループ１１４を有する全ての状態１０６、又はその部分集合（サブセット）から削除あるいは除去されてもよい。セルフループ１１４は、非イプシロンアーク１０８内でのみモデル化され得る。唯一の到来アーク１０８を有する状態１０６からのセルフループ１１４の除去又は削除は、状態１０６の更新を同期化する必要性を低減あるいは排除し得る。
【００８２】
退出アーク１０８内でのセルフループ１１４のモデル化は、セルフループ情報を格納するように、アーク１０８に関連付けられたデータ構造を変更することを含み得る。
【００８３】
セルフループ情報は、固有の尤度又は確率の情報を含み得る。セルフループ固有尤度情報は、例えば退出アーク１０８の固有尤度情報をセルフループ固有尤度情報で変更することによって等、退出アーク１０８内で黙示的にモデル化され得る。他の例では、セルフループ固有尤度情報は、例えばアーク１０８がセルフループ情報を含むかを指し示すものを格納するためのフィールドと、セルフループ情報を格納するための１つ以上の更なるフィールドとを含むように退出アーク１０８を変更することによって等、退出アーク１０８内で明示的にモデル化されてもよい。
【００８４】
対応するネットワークの横断は、退出アーク１０８内のセルフループ情報を処理するために、各繰り返し中に１つ以上の追加計算を含み得る。追加計算は、例えば図６−９に関連して後述するようにして、対応する退出アーク１０８を処理するときに実行され得る。
【００８５】
先ず、複数のセルフループ１１４を有するネットワーク１０２が生成され、複数のセルフループ１１４のうちの１つ以上が除去されて、対応する退出アーク１０８内で再モデル化され得る。ネットワーク１０２は、セルフループ情報の除去及び退出アーク１０８内でのセルフループ情報の再モデル化の後に最適化されてもよい。この後の最適化は比較的多数の状態１０６を融合することができ、それにより横断効率が向上され得る。最適化は、上述のような１つ以上のＦＳＭ最小化技術を含み得る。
【００８６】
他の例では、明示的なセルフループ１１４を用いずに、退出アーク１０８内でモデル化されたセルフループ情報を用いて、手始めにＨ変換器が生成されてもよい。そして、ＷＦＳＴネットワーク１０２を提供するように、組み立て手順及び／又はその他の最適化手順が実行され得る。最適化は比較的多数の状態１０６を融合し得る。
【００８７】
図６は、対応する状態６０６の退出非イプシロンアーク６０８−１乃至６０８−５、６０８−８及び６０８−１１内でセルフループ情報がモデル化されたネットワーク６０２を含む、グラフベースネットワーク及び推論エンジン６００のブロック図である。図１のセルフループ１１４は対応する状態６０６から削除されている。
【００８８】
推論エンジン１０４は、例えば図７−９のうちの１つ以上に関連して後述するようにしてネットワーク６０２のアーク内でモデル化されたセルフループ情報を更新するアークベースのセルフループ更新システム６０４を含み得る。
【００８９】
図７は、ネットワークのアークの少なくとも一部内でセルフループ情報がモデル化されるときの、ネットワークを横断する方法７００の処理フローチャートである。
【００９０】
ステップ７０２にて、少なくとも、内部にモデル化されたセルフループ固有尤度情報を有するアークに関して、累積尤度情報が更新される。故に、図９に関連して後述するように、例えば図６のイプシロンアーク６０８−６、６０８−７及び６０８−８など一部のアーク１０８は、ステップ７０２での更新から省略され得る。
【００９１】
ステップ７０４にて、更新されたアークの目的状態が、対応する更新後のアークに従って更新される。ステップ７０４での目的状態の更新は、ステップ７０２での更新の後に実行され得る。ステップ７０４で目的状態が複数の到来アークに応答して更新されるべき場合、ステップ７０４での更新は、更新の同期化を含み得る。
【００９２】
ステップ７０６にて、イプシロンアークが更新され得る。
【００９３】
ステップ７０８にて、ステップ７０４で更新された目的状態を起源とするアークが、更新後の目的状態に従って更新される。ステップ７０８でのアークの更新は、ステップ７０４での全ての目的状態の更新の後に実行され得る。
【００９４】
図８は、セルフループ固有尤度情報を含むようにアークの少なくとも一部の固有尤度情報が変更されるときの、ネットワークを横断する方法８００の処理フローチャートである。
【００９５】
ステップ８０２にて、現在の繰り返しのアクティブアークが特定される。
【００９６】
ステップ８０４にて、全てのアクティブアークの累積尤度情報、又は全てのアクティブな非イプシロンアークの累積尤度情報が、対応する固有尤度情報に基づいて更新される。これは基本的に、セルフループ固有尤度情報を含むアークに関してセルフループ更新を実行する。
【００９７】
ステップ８０６にて、アクティブアークの目的状態の累積尤度情報が、対応するアクティブアークの更新後の累積尤度情報を用いて更新される。
【００９８】
方法８００が、例えばスレッドレベル及び／又はデータレベルの並列処理環境などの並列処理環境で実行される場合、また、状態が複数の到来アクティブアークに応答して更新される場合、ステップ８０６での目的状態の更新は、複数の到来アークに関する更新を同期化することを含み得る。セルフループ情報は状態ではなくアーク内でモデル化されているので、同期化は、単一の到来アークに応答して更新される状態に関しては省略され得る。
【００９９】
ステップ８０８にて、イプシロンアークが更新される。
【０１００】
ステップ８０６での累積尤度情報の更新は、更新された目的状態の１つ以上の退出アークをアクティブにし得る。そのようなアークにことを、ここでは、新たにアクティブにされたアークと称する。ステップ８１０にて、新たにアクティブにされたアークの累積尤度情報が、ステップ８０６で更新された対応する目的状態の更新後の累積情報を用いて更新される。ステップ８１０での新たにアクティブにされたアークの更新は、ステップ８０６での全てのアクティブアークの処理の後に実行され得る。
【０１０１】
方法８００又はその一部は、全てのアクティブアーク及び対応する目的状態が更新されるまで、反復的に繰り返され得る。その後の繰り返しにおいて、ステップ８０４及び８０６でのアクティブアークの処理は、ステップ８１２での先行の繰り返しにて特定された、新たにアクティブにされたアークを含み得る。
【０１０２】
１つ以上のアクティブアークは、新たにアクティブにされたアークを含めて、例えば対応する累積尤度の値が閾値未満であるとき等には、その後の繰り返しにおける更なる処理から省略されてもよい。
【０１０３】
図９は、セルフループ固有尤度情報とセルフループ固有尤度情報の存在を指し示すもの（インジケーション）とを保持するようにネットワークのアークが複数のフィールドを含むときの、ネットワークを横断する方法９００の処理フローチャートである。
【０１０４】
ステップ９０２にて、現繰り返しのアクティブアークが特定される。
【０１０５】
ステップ９０４にて、セルフループ固有尤度情報の存在のインジケーションを含むアクティブアークの累積尤度情報が、該アーク内の対応するセルフループ固有尤度情報に基づいて更新される。これは基本的に、セルフループ固有尤度情報の存在のインジケーションを含むアークに関してのみセルフループ更新を実行する。
【０１０６】
ステップ９０６にて、全てのアクティブアーク、又は少なくとも全てのアクティブ非イプシロンアークの目的状態の累積尤度情報が、対応するアクティブアークの更新後の累積尤度情報を用いて更新される。
【０１０７】
方法８００に関して上述したように、ステップ９０６での目的状態の更新は、複数の到来アークに関する更新を同期化することを含み得る。
【０１０８】
ステップ９０８にて、イプシロンアークが更新され得る。
【０１０９】
ステップ９１０にて、ステップ８１０に関して上述したようにして、新たにアクティブにされたアークの累積尤度情報が、ステップ９０６で更新された対応する目的状態の更新後の累積情報を用いて更新される。
【０１１０】
方法９００又はその一部は、方法８００に関して上述したように、全てのアクティブアーク及び対応する目的状態が更新されるまで、反復的に繰り返され得る。
【０１１１】
キャッシュ認識動的タスクオーダリング
マルチプロセッサ環境においては、複数の処理スレッド間で作業負荷を平衡させるために、動的タスクスケジューリングが利用され得る。
【０１１２】
従来のタスクスケジューラ発見的問題解決法（ヒューリスティックス）は、例えばＷＦＳＴに基づく探索などの一部の環境では最適でないことがある。例えば、アクティブ状態又はアクティブアークなどのデータオブジェクトが現在の繰り返し又はフレームで処理されるべきで、該データオブジェクトが先行の繰り返しで処理されていた場合、該データオブジェクトに付随するデータは、該データオブジェクトが以前に処理されたスレッドに関連付けられた位置にキャッシュされたままとなり得る。このデータオブジェクトを現繰り返しの同一スレッドにて処理することは有用である。既存のキャッシュデータが、キャッシュデータの再取出し又は再計算の必要性を低減あるいは排除し得るためである。しかしながら、従来の動的スケジューラ発見的問題解決法は、データオブジェクトを、該データオブジェクトが以前に割り当てられていたのと同一のスレッドに割り当てようとはしていない。
【０１１３】
ここでは、データの場所に基づいてタスクを順序付ける方法及びシステムを開示する。ここでは、これを動的キャッシュ認識タスクオーダリングと称する。動的キャッシュ認識タスクオーダリングは、対応するデータオブジェクトのデータキャッシュ位置に少なくとも部分的に基づいて、タスクをスレッドに関連付ける。
【０１１４】
ここではまた、ここで開示する動的キャッシュ認識タスクオーダリングを用いてＷＦＳＴベースネットワークを探索する方法及びシステムを開示する。
【０１１５】
キャッシュ認識動的タスクオーダリングは、黙示的なキャッシュ認識タスクスケジューリング、又は明示的なキャッシュ認識タスクスケジューリングを含み得る。
【０１１６】
黙示的なキャッシュ認識タスクスケジューリングは、黙示的あるいは間接的に動的タスクマネジャに特定のスレッドへのタスクの割り当てを行わせるように、待ち行列内のタスクを順序付け得る。待ち行列の順序付けは、例えば図１０及び１２に関連して後述するように、タスクマネジャの発見的問題解決に基づき得る。
【０１１７】
明示的なキャッシュ認識タスクスケジューリングは、例えば図１１及び１３に関連して後述するように、データオブジェクトが以前に処理されたスレッドを特定し、該データオブジェクトに関する新たなタスクを同一のスレッドに明示的に割り当て得る。
【０１１８】
図１０は、タスク待ち行列１００６内のタスク１００２を順序付けるキューマネジャ１００４と、複数の処理スレッド１０１０間でタスク待ち行列１００６からのタスク１００２をスケジューリングする動的タスクマネジャ１００８とを含む、黙示的なキャッシュ認識環境１０００のブロック図である。
【０１１９】
タスク１００２はアクティブ状態１０６及び／又はアクティブアーク１０８と関連付けられ得る。タスク１００２の処理中、スレッド１０１０は次の繰り返しのアクティブ状態１０６及び／又はアクティブアーク１０８のリスト１０１２を生成し得る。対応する新たなタスク１００２が、リスト１０１２内で特定されたアクティブ状態１０６及び／又はアクティブアーク１０８に関して定義される。
【０１２０】
リスト１０１２内で特定された次の繰り返しのアクティブ状態１０６及び／又はアクティブアーク１０８のうちの少なくとも一部は、対応するスレッド１０１０を用いて現繰り返しにおいて既にアクティブになっている。
【０１２１】
キューマネジャ１００４は、対応する状態１０６及び／又はアーク１０８が特定されたリスト１０１２に基づいて、動的タスクマネジャ１００８にタスク１００２を、該タスク１００２を開始したスレッド１０１０に割り当てさせるように、待ち行列１００６内のタスク１００２を配列するように構成され得る。故に、状態１０６及び／又はアーク１０８が連続した繰り返し内でアクティブである場合、対応するタスク１００２は同一のスレッド１０１０に割り当てられ得る。
【０１２２】
例えば、アーク１０８に関連付けられたタスク１００２が、現繰り返しにおいてスレッド１０１０−１に割り当てられ得る。現繰り返しにおいてタスク１００２を処理する際、スレッド１０１０−１は、該アーク１０８が次の繰り返しにおいてアクティブであるべきことを指し示すようにリスト１０１２−１を生成し得る。該アーク１０８に対応する新たなタスク１００２が次の繰り返しで呼び出され、キューマネジャ１００４は、動的タスクスケジューラに該新たなタスク１００２をスレッド１０１０−１に割り当てさせるように、待ち行列１００６内の該新たなタスク１００２を配置し得る。
【０１２３】
キューマネジャ１００４は、動的タスクマネジャ１００８のスレッド割当てに影響を及ぼすために、動的タスクマネジャ１００８によって使用される経験則に従って待ち行列１００６内のタスク１００２を順序付ける経験則（ヒューリスティック）システム１０１４を含み得る。
【０１２４】
例えば、タスクマネジャ１００８は、タスク１００２をスレッド１０１０に総当たり的に割り当てるように構成されることができ、循環的に、第１のタスク１００２がスレッド１０１０−１に割り当てられ、第２のタスク１００２がスレッド１０１０−２に割り当てられ、後続のタスク１００２が後続のスレッド１０１０に割り当てられる。同様に、キューマネジャ１００４は、待ち行列１００６内のタスク群１００２を、リスト１０１２に従って総当たり的に配置するように構成され得る。例えば、リスト１０１２−１からの１つのタスク１００２が最初に待ち行列１００６に割り当てられ、リスト１０１２−２からの１つのタスク１００２が続けられ、後続のリスト１０１２からの後続のタスク１００２が続けられ得る。
【０１２５】
他の一例として、動的タスクマネジャ１００８は、待ち行列１００６からタスク群１００２を取り出し、該タスク群１００２を複数組の連続タスク群１００２に分離し、且つ各組の連続タスク群１００２を順次、総当たり的にスレッド群１０１０に割り当てるように構成されてもよい。例えば、待ち行列１００６が８個のタスク１００２（Ａ乃至Ｈ）を含み、且つスレッド１０１０が４個のスレッド１０１０−１乃至１０１０−４を含む場合、動的タスクマネジャ１００８は、タスクＡ及びＢをスレッド１０１０−１に、タスクＣ及びＤをスレッド１０１０−２に、タスクＥ及びＦをスレッド１０１０−３に、そしてタスクＧ及びＨをスレッド１０１０−４に割り当て得る。キューマネジャ１００４は、待ち行列１００６内のタスクＡ乃至Ｈを、タスクＡ乃至Ｈを開始する元となったリスト１０１２を考慮して配列するように構成され得る。
【０１２６】
図１１は、データ局所情報を管理するキャッシュ認識システム１１０４と、少なくとも部分的にデータ局所情報に基づいて、タスク１１０２を処理スレッド１１１０に割り当てる動的タスクマネジャ１１０８とを含む、明示的なキャッシュ認識環境１１００のブロック図である。
【０１２７】
キャッシュ認識システム１１０４は、タスク１１０２がスレッド１１１０に割り当てられるときに動的タスクマネジャ１１０８からデータ局所情報１１０８を受信する記録システム１１０６を含み得る。データ局所情報１１０８は、タスク１１０２が割り当てられたスレッド１１１０を特定し得る。これは、対応するデータオブジェクト１１１６に付随するデータがキャッシュされたキャッシュ位置に相当し得る。
【０１２８】
記録システム１１０６は、タスク１１０２が対象とするデータオブジェクト１１１６にデータ局所情報１１０８を関連付けるように構成され得る。データオブジェクト１１１６は、状態１０６及び／又はアーク１０８を表すことができ、対応するデータ局所情報１１０８を記録するフィールドを含み得る。
【０１２９】
キャッシュ認識システム１１０４は、データオブジェクト１１１６に関するタスク１１０２がスレッド１１１０に割り当てられるべきときに、該データオブジェクト１１１６に関連付けられたデータ局所情報１１０８を取り出す検索システム１１１２を含み得る。
【０１３０】
動的タスクマネジャ１１０８は、取り出されたデータ局所情報１１１４に少なくとも部分的に基づいてタスク１１０２をスレッド１１１０に割り当てるように構成され得る。
【０１３１】
動的タスクマネジャ１１０８は、タスク１１０２をスレッド１１１０に割り当てるに際して、例えばスレッド１１１０間で処理負荷を平衡化することなど、１つ以上のその他の因子を考慮に入れるように構成されてもよい。
【０１３２】
キャッシュ認識システム１１０４及び動的タスクマネジャ１１０８は、別々に実装されてもよいし、ともに一体化されて実装されてもよい。
【０１３３】
図１２は、データ局所情報に少なくとも部分的に基づいてタスクを順序付ける方法１２００の処理フローチャートである。方法１２００は、図１０に関連して上述したようにして実行され得る。しかしながら、方法１２００は図１０の例に限定されるものではない。
【０１３４】
ステップ１２０２にて、次の繰り返しのアクティブデータオブジェクトのリストが、複数の処理スレッドの各々から受信される。データオブジェクトはグラフベースネットワークのアーク及び／又は状態を表し得る。
【０１３５】
ステップ１２０４にて、次の繰り返しのアクティブデータオブジェクトに関するタスクが受信される。
【０１３６】
ステップ１２０６にて、タスクが、対応するデータオブジェクトが特定された上記リストに基づいて、処理スレッドに関連付けられる。
【０１３７】
ステップ１２０８にて、タスクを関連付けられた処理スレッドへと向けるために、タスクがタスクマネジャ経験則に従って順序付けられる。タスクは、タスクマネジャがタスクをスレッドに割り当てる元となったタスク待ち行列内で順序付けられてもよい。
【０１３８】
図１３は、少なくとも部分的にデータ局所情報に基づいてタスクを処理スレッドに割り当てる方法１３００の処理フローチャートである。方法１３００は、図１１に関連して上述したようにして実行され得る。しかしながら、方法１３００は図１１の例に限定されるものではない。
【０１３９】
ステップ１３０２にてタスクが受信される。タスクは、グラフベースネットワークの状態及び／又はアークを表すデータオブジェクトに関連付けられ得る。
【０１４０】
ステップ１３０４にて、データオブジェクトがスレッドに関連付けられているかについて決定が為される。これは、例えばスレッド識別子などのキャッシュデータ局所情報がデータオブジェクトに関連付けられているかを決定することを含み得る。
【０１４１】
データオブジェクトがスレッドに関連付けられていない場合、後述するように、処理はステップ１３０６へと進む。
【０１４２】
タスクがスレッドに関連付けられている場合、ステップ１３０８にて更なる決定が為される。
【０１４３】
ステップ１３０８にてスレッドがそのタスクを受け入れることができる場合、ステップ１３１０にてタスクはそのスレッドに割り当てられる。スレッドがそのタスクを受け入れることができない場合、又は１つ以上のその他の考慮に基づいて別のスレッドの方がそのタスクに適している場合には、処理はステップ１３０６へと進む。
【０１４４】
ステップ１３０６にて、１つ以上のその他の因子に基づいて、データオブジェクトがスレッドに割り当てられ、対応するキャッシュデータ局所情報が該データオブジェクトに関連付けられる。キャッシュデータ局所情報は、該タスクが割り当てられるスレッドの識別子を含み得る。
【０１４５】
その後、そのデータオブジェクトがステップ１３０２での別のタスクの対象となるとき、そのタスクはステップ１３１０にて同一のスレッドに割り当てられ得る。
【０１４６】
アクティブアークに基づく横断、アーク内でモデル化されたセルフループ情報の処理、キャッシュ認識動的タスクオーダリングは、単独で実行されてもよいし、且つ／或いは相互に様々に組み合わされて実行されてもよい。
【０１４７】
ここで説明した１つ以上の機能は、ディスクリートロジック及び集積回路ロジック、特定用途向け集積回路（ＡＳＩＣ）ロジック、並びにマイクロコントローラを含むハードウェア、ソフトウェア、ファームウェア及びそれらの組み合わせにて実装されてもよいし、特定ドメイン向けの集積回路パッケージ又は複数の集積回路パッケージの組み合わせの一部として実装されてもよい。ここでは、ソフトウェアという用語は、ここで開示した１つ以上の機能及び／又はそれらの組み合わせをコンピュータシステムに実行させるコンピュータプログラムロジックを格納したコンピュータ読み取り可能媒体を含むコンピュータプログラムの製造物を意味する。
【０１４８】
図１４は、グラフベースネットワークを横断するように構成されたコンピュータシステム１４００のブロック図である。
【０１４９】
コンピュータシステム１４００は、コンピュータプログラムロジックを実行する１つ以上のコンピュータ命令処理ユニット（ここではプロセッサ又はコア１４０２として示す）を含み得る。
【０１５０】
コンピュータシステム１４００は更に、プロセッサ１４０２に１つ以上の機能を実行させるコンピュータプログラムロジック又は命令１４０６を格納したコンピュータ読み取り可能媒体を含め、キャッシュ、メモリ及び／又はストレージ（以下、“メモリ”）１４０４を含み得る。
【０１５１】
メモリ１４０４は更に、命令１４０６を実行する際にプロセッサ１４０２によって使用される、且つ／或いは命令１４０６の実行に応答してプロセッサ１４０２によって生成される、データ１４０８を含んでいる。
【０１５２】
図１４の例において、ロジック１４０６は、上述の１つ以上の例にて説明したようにプロセッサ１４０２にグラフベースネットワーク１４１２を横断させる推論エンジンロジック１４１０を含んでいる。ネットワーク１４１２は、図１のネットワーク１０２又は図６のネットワーク６０２に相当し得る。ネットワーク１４１２は、当該ネットワーク１４１２の状態及びアークのうちの１つ以上を表すデータオブジェクト１４１４を含み得る。
【０１５３】
推論エンジンロジック１４１０は、図１−５のうちの１つ以上に関連して上述したようにプロセッサ１４０２にネットワーク１４１２のアクティブアークを横断させるアクティブアーク横断ロジック１４１６を含み得る。
【０１５４】
セルフループ情報がネットワーク１４１２のアーク内でモデル化される場合、推論エンジンロジック１４１０は、図６−９のうちの１つ以上に関連して上述したようにプロセッサ１４０２にセルフループ情報を更新させるアークベースのセルフループ更新ロジック１４１８を含み得る。
【０１５５】
コンピュータシステム１４００は、実行時にタスクのスケジューリング又はタスクの処理スレッドへの割り当てを行う動的タスクマネジャ１４２２を含み得る。動的タスクマネジャ１４２２は、図１０の動的タスクマネジャ１００８及び図１１の動的タスクマネジャ１１０８のうちの１つ以上に対応し得る。
【０１５６】
コンピュータシステム１４００が動的タスクマネジャ１４２２を含む場合、推論エンジンロジック１４１０は、データオブジェクトに関連するタスクを、該データオブジェクトに関する先行タスクが割り当てられた処理ロジックに基づいて順序付けることをプロセッサ１４０２に行わせるキャッシュ認識オーダリングロジック１４２０を含み得る。キャッシュ認識オーダリングロジック１４２０は、図１０及び１２のうちの１つ以上に関連して上述したようにタスクマネジャ１４２２の経験則に従ってスレッドを順序付け且つタスクマネジャ１４２２にタスクの対応するスレッドへの割当てを行わせるロジックを含み得る。キャッシュ認識オーダリングロジック１４２０は、図１０のキューマネジャ１００４に対応し得る。キャッシュ認識オーダリングロジック１４２０は、推論エンジンロジック１４１０の外部に実装されてもよいし、推論エンジンロジック１４１０とは独立に実装されてもよい。
【０１５７】
他の例では、図１１及び１３のうちの１つ以上に関連して上述したように、動的タスクマネジャ１４２２は明示的に、データオブジェクト１４１４に関連付けられたデータ局所情報に基づいてタスクをスレッドに割り当てるように構成されてもよく、コンピュータシステム１４００は更に、データ局所情報をデータオブジェクト１４１４に関連付け且つデータ局所情報を取り出して動的タスクマネジャ１４２２に提供するデータ位置管理システム１４２４を含んでいてもよい。データ位置管理システム１４２４は、図１１のキャッシュ認識システム１１０４に対応し得る。データ位置管理システム１４２４は、ハードウェア、ソフトウェア、ファームウェア、ロジック１４０６及びこれらの組み合わせにて実装され得る。
【０１５８】
コンピュータシステム１４００は、当該コンピュータシステム１４００内に１つ以上の通信パスを提供する情報通信基盤１４２６を含み得る。
【０１５９】
コンピュータシステム１４００は、当該コンピュータシステム１４００と１つ以上のその他のシステムとの間に１つ以上の通信パスを提供する入力／出力コントローラ１４２８を含み得る。
【０１６０】
ここでは、機能、特徴及びそれらの関係を示す機能構築ブロックの助けを借りて方法及びシステムを開示した。これらの機能構築ブロックの境界のうちの少なくとも一部は、説明の便宜のためにここで自由に定めたものである。代替的な境界が定められてもよい。
【０１６１】
ここでは様々な実施形態を説明したが、理解されるように、これらの実施形態は、限定としてではなく単に例として提示したものである。当業者に明らかなように、ここで開示した方法及びシステムの精神及び範囲を逸脱することなく、形態及び細部の様々な変更が為され得る。故に、請求項の広さ及び範囲は、ここで開示した実施形態例の何れにも限定されるべきでない。
【符号の説明】
【０１６２】
１００、６００ システム
１０２、６０２ グラフベースネットワーク
１０４ 推論エンジン
１０６、６０６ 状態
１０８、６０８ アーク（パス）
１１０ 特徴ベクトル
１１２ 文法要素
１１４ セルフループ
３０２ アクティブアーク横断システム
６０４ アークベースセルフループ更新システム
１０００、１１００ キャッシュ認識環境
１００２、１１０２ タスク
１００４ キューマネジャ
１００６ 待ち行列
１００８ 動的タスクマネジャ
１０１０ スレッド
１０１２ アクティブオブジェクトのリスト
１０１０、１１１０ スレッド
１０１４ 経験則システム
１１０４ キャッシュ認識システム
１１０６ 記録システム
１１０８ 動的タスクマネジャ
１１０８、１１１４ データ局所性情報
１１１２ 検索システム
１１１６ データオブジェクト
１４００ コンピュータシステム
１４０２ プロセッサ
１４０４ キャッシュ／メモリ／ストレージ
１４０６ コンピュータプログラムロジック／命令
１４０８ データ
１４１０ 推論エンジンロジック
１４１２ グラフベースネットワーク
１４１４ データオブジェクト
１４１６ アクティブアーク横断ロジック
１４１８ アークベースセルフループ更新ロジック
１４２０ キャッシュ認識タスクオーダリングロジック
１４２２ タスクマネジャ
１４２４ キャッシュ認識システム
１４２６ 通信基盤
１４２８ 入力／出力コントローラ
【特許請求の範囲】
【請求項１】
ネットワークのアークの入力ラベルを、前記アークの出力文法要素のリストに変換する方法であって：
特徴ベクトルのストリームに応答してネットワークを繰り返し横断するステップであり、前記ネットワークの状態のシーケンスに対応する前記ネットワークのアークの入力ラベルを、文法要素のシーケンスに対応する前記アークの出力文法要素のリストに変換する、横断するステップ；及び
データオブジェクトに関するタスクを、該データオブジェクトに関する先行タスクが割り当てられた処理スレッドに基づいて順序付けるステップ；
を有する方法。
【請求項２】
前記順序付けるステップは：
前記処理スレッドの各々から、次の繰り返しのアクティブデータオブジェクトのリストを受信するステップ；
前記次の繰り返しの前記アクティブデータオブジェクトに関するタスクの識別子を受信するステップ；
前記タスクの各々を、対応するデータオブジェクトが特定された前記リストに基づいて、前記処理スレッドのうちの１つに関連付けるステップ；及び
前記タスクを関連付けられた処理スレッドに向けるため、タスクマネジャの経験則に従って前記タスクを順序付けるステップ；
を含む、請求項１に記載の方法。
【請求項３】
前記順序付けるステップは：
現在の繰り返しにて、データオブジェクトに関する第１のタスクを、前記処理スレッドのうちの第１の処理スレッドに割り当てるステップ；
前記第１の処理スレッドの識別子を前記データオブジェクトに関連付けるステップ；
前記データオブジェクトに関する第２のタスクを受信するステップ；及び
前記データオブジェクトに関連付けられた前記第１の処理スレッドの前記識別子に少なくとも部分的に基づいて、前記第２のタスクを前記第１の処理スレッドに割り当てるステップ；
を含む、請求項１に記載の方法。
【請求項４】
前記繰り返し横断するステップは：
前記ネットワークのアクティブアークを伝播するステップであり、特徴ベクトルに応答して前記アクティブアークの目的状態を更新することを含む、アクティブアークを伝播するステップ；
を含む、請求項１に記載の方法。
【請求項５】
前記アクティブアークを伝播するステップは：
前記アクティブアークの起源状態に関する情報であり、前記起源状態に関する尤度指標を含む情報、を取り出すステップ；
前記アクティブアークを、対応する起源状態の前記尤度指標と前記特徴ベクトルとを用いて更新するステップ；及び
更新されたアクティブアークに従って、対応する目的状態を更新するステップ；
を含む、請求項４に記載の方法。
【請求項６】
複数の前記状態の各々に対応するセルフループ情報を、対応する状態の１つ以上の退出アーク内でモデル化するステップ；
を更に含む、請求項１に記載の方法。
【請求項７】
前記セルフループ情報は固有の尤度情報を含み、前記モデル化するステップは：
前記セルフループ固有の尤度情報を用いて退出アークの固有尤度情報を変更するステップ
を含む、請求項６に記載の方法。
【請求項８】
前記セルフループ情報は固有の尤度情報を含み、前記モデル化するステップは：
前記セルフループの尤度情報と、前記セルフループの尤度情報の存在のインジケーションとを保持するための複数のフィールドを含むように、退出アークを表すデータオブジェクトを変更するステップ
を含む、請求項６に記載の方法。
【請求項９】
前記アークは固有の尤度情報を含み、前記アークの少なくとも一部は更にセルフループ固有の尤度情報を含み、前記横断するステップは：
一組のアクティブアークを特定するステップ；
前記セルフループ固有の尤度情報を含む前記一組のアクティブアークのうちの少なくともサブセットの累積尤度情報を、少なくとも対応するセルフループ固有の尤度情報に基づいて更新するステップ；
前記累積尤度情報の更新の後に、第１の伝播段階において、前記一組のアクティブアークの累積尤度情報を伝播するステップ；
前記第１の伝播段階の後の第２の伝播段階において、新たにアクティブにされたアークに累積尤度情報を伝播するステップであり、前記新たにアクティブにされたアークは、前記第１の伝播段階において更新された１つ以上の状態の１つ以上の退出アークを含む、ステップ；
前記新たにアクティブにされたアークを含むように、且つ閾値未満の累積尤度の値を有するアークを削除するように、前記一組のアクティブアークを組み直すステップ；及び
組み直されたアクティブアークの組に関して、前記更新するステップ、前記第１の伝播段階及び前記第２の伝播段階を繰り返すステップ；
を含む、請求項１に記載の方法。
【請求項１０】
前記アークの前記一部の固有の尤度情報は、対応するセルフループ固有の尤度情報を含むように変更され、前記更新するステップは：
前記一組のアクティブアーク内の全てのアクティブアークの累積尤度情報を、対応するアークの固有の尤度情報に基づいて更新するステップ
を含む、請求項９に記載の方法。
【請求項１１】
前記ネットワークの少なくとも非イプシロンアークの各々は、該アーク固有の尤度情報を保持する１つ以上のフィールドの第１の組と、セルフループ固有の尤度情報を保持する１つ以上のフィールドの第２の組と、前記１つ以上のフィールドの第２の組にセルフループ固有の尤度情報が存在するときにセルフループインジケーションを保持するセルフループインジケータフィールドとを含み、前記更新するステップは：
現在の前記一組のアクティブアーク内の前記サブセットのアークを、前記セルフループインジケーションを含むアークとして特定するステップ；及び
特定された前記サブセットのアクティブアークに関してのみ、累積セルフループ尤度情報を更新するステップ；
を含む、請求項９に記載の方法。
【請求項１２】
ネットワークのアークの入力ラベルを、前記アークの出力文法要素のリストに変換するシステムであって：
ネットワークの状態のシーケンスに対応する前記ネットワークのアークの入力ラベルを、文法要素のシーケンスに対応する前記アークの出力文法要素のリストに変換するネットワーク；及び
特徴ベクトルのストリームに応答して前記ネットワークのアクティブアークを繰り返し伝播する推論エンジンであり、前記特徴ベクトルに応答して前記アクティブアークの目的状態を更新することを含む推論エンジン；
を有するシステム。
【請求項１３】
前記推論エンジンは：
前記アクティブアークの起源状態に関する情報であり、前記起源状態に関する尤度指標を含む情報、を取り出し；
前記アクティブアークを、対応する起源状態の前記尤度指標と前記特徴ベクトルとを用いて更新し；且つ
更新されたアクティブアークに従って、対応する目的状態を更新する；
ように構成されている、請求項１２に記載のシステム。
【請求項１４】
データオブジェクトに関するタスクを、該データオブジェクトに関する先行タスクが割り当てられた処理スレッドに基づいて順序付ける順序付けシステム；
を更に含む請求項１２に記載のシステム。
【請求項１５】
前記アークは固有の尤度情報を含み、前記アークの少なくとも一部は更にセルフループ固有の尤度情報を含み、前記推論エンジンは：
一組のアクティブアークを特定し；
前記セルフループ固有の尤度情報を含む前記一組のアクティブアークのうちの少なくともサブセットの累積尤度情報を、少なくとも対応するセルフループ固有の尤度情報に基づいて更新し；
前記累積尤度情報の更新の後に、第１の伝播段階において、前記一組のアクティブアークの累積尤度情報を伝播し；
前記第１の伝播段階の後の第２の伝播段階において、新たにアクティブにされたアークに累積尤度情報を伝播し、ただし、前記新たにアクティブにされたアークは、前記第１の伝播段階において更新された１つ以上の状態の１つ以上の退出アークを含み；
前記新たにアクティブにされたアークを含むように、且つ閾値未満の累積尤度の値を有するアークを削除するように、前記一組のアクティブアークを組み直し；且つ
組み直されたアクティブアークの組に関して、前記更新、前記第１の伝播段階及び前記第２の伝播段階を繰り返す；
ように構成されている、請求項１２に記載のシステム。
【請求項１６】
ネットワークの状態のシーケンスに対応する前記ネットワークのアークの入力ラベルを、文法要素のシーケンスに対応する前記アークの出力文法要素のリストに変換するシステムであって、前記アークは固有の尤度情報を含み、前記アークの少なくとも一部は更にセルフループ固有の尤度情報を含み、当該システムは：
一組のアクティブアークを特定する手段；
前記セルフループ固有の尤度情報を含む前記一組のアクティブアークのうちの少なくともサブセットの累積尤度情報を、少なくとも対応するセルフループ固有の尤度情報に基づいて更新する手段；
前記累積尤度情報の更新の後に、第１の伝播段階において、前記一組のアクティブアークの累積尤度情報を伝播する手段；
前記第１の伝播段階の後の第２の伝播段階において、新たにアクティブにされたアークに累積尤度情報を伝播する手段であり、前記新たにアクティブにされたアークは、前記第１の伝播段階において更新された１つ以上の状態の１つ以上の退出アークを含む、手段；
前記新たにアクティブにされたアークを含むように、且つ閾値未満の累積尤度の値を有するアークを削除するように、前記一組のアクティブアークを組み直す手段；及び
組み直されたアクティブアークの組に関して、前記更新するステップ、前記第１の伝播段階及び前記第２の伝播段階を繰り返す手段；
を有する、システム。
【請求項１７】
前記アークの前記一部の固有の尤度情報は、対応するセルフループ固有の尤度情報を含むように変更され、前記更新する手段は：
前記一組のアクティブアーク内の全てのアクティブアークの累積尤度情報を、対応するアークの固有の尤度情報に基づいて更新する手段
を含む、請求項１６に記載のシステム。
【請求項１８】
前記ネットワークの少なくとも非イプシロンアークの各々は、該アーク固有の尤度情報を保持する１つ以上のフィールドの第１の組と、セルフループ固有の尤度情報を保持する１つ以上のフィールドの第２の組と、前記１つ以上のフィールドの第２の組にセルフループ固有の尤度情報が存在するときにセルフループインジケーションを保持するセルフループインジケータフィールドとを含み、前記更新する手段は：
現在の前記一組のアクティブアーク内の前記サブセットのアークを、前記セルフループインジケーションを含むアークとして特定する手段；及び
特定された前記サブセットのアクティブアークに関してのみ、累積セルフループ尤度情報を更新する手段；
を含む、請求項１６に記載のシステム。
【請求項１９】
データオブジェクトに関するタスクを、該データオブジェクトに関する先行タスクが割り当てられた処理スレッドに基づいて順序付ける手段；
を更に含む請求項１６に記載のシステム。
【請求項２０】
前記ネットワークのアクティブアークを伝播する手段であり、特徴ベクトルに応答して前記アクティブアークの目的状態を更新する手段を含む、伝播する手段；
を更に含む請求項１６に記載のシステム。
【請求項１】
ネットワークのアークの入力ラベルを、前記アークの出力文法要素のリストに変換する方法であって：
特徴ベクトルのストリームに応答してネットワークを繰り返し横断するステップであり、前記ネットワークの状態のシーケンスに対応する前記ネットワークのアークの入力ラベルを、文法要素のシーケンスに対応する前記アークの出力文法要素のリストに変換する、横断するステップ；及び
データオブジェクトに関するタスクを、該データオブジェクトに関する先行タスクが割り当てられた処理スレッドに基づいて順序付けるステップ；
を有する方法。
【請求項２】
前記順序付けるステップは：
前記処理スレッドの各々から、次の繰り返しのアクティブデータオブジェクトのリストを受信するステップ；
前記次の繰り返しの前記アクティブデータオブジェクトに関するタスクの識別子を受信するステップ；
前記タスクの各々を、対応するデータオブジェクトが特定された前記リストに基づいて、前記処理スレッドのうちの１つに関連付けるステップ；及び
前記タスクを関連付けられた処理スレッドに向けるため、タスクマネジャの経験則に従って前記タスクを順序付けるステップ；
を含む、請求項１に記載の方法。
【請求項３】
前記順序付けるステップは：
現在の繰り返しにて、データオブジェクトに関する第１のタスクを、前記処理スレッドのうちの第１の処理スレッドに割り当てるステップ；
前記第１の処理スレッドの識別子を前記データオブジェクトに関連付けるステップ；
前記データオブジェクトに関する第２のタスクを受信するステップ；及び
前記データオブジェクトに関連付けられた前記第１の処理スレッドの前記識別子に少なくとも部分的に基づいて、前記第２のタスクを前記第１の処理スレッドに割り当てるステップ；
を含む、請求項１に記載の方法。
【請求項４】
前記繰り返し横断するステップは：
前記ネットワークのアクティブアークを伝播するステップであり、特徴ベクトルに応答して前記アクティブアークの目的状態を更新することを含む、アクティブアークを伝播するステップ；
を含む、請求項１に記載の方法。
【請求項５】
前記アクティブアークを伝播するステップは：
前記アクティブアークの起源状態に関する情報であり、前記起源状態に関する尤度指標を含む情報、を取り出すステップ；
前記アクティブアークを、対応する起源状態の前記尤度指標と前記特徴ベクトルとを用いて更新するステップ；及び
更新されたアクティブアークに従って、対応する目的状態を更新するステップ；
を含む、請求項４に記載の方法。
【請求項６】
複数の前記状態の各々に対応するセルフループ情報を、対応する状態の１つ以上の退出アーク内でモデル化するステップ；
を更に含む、請求項１に記載の方法。
【請求項７】
前記セルフループ情報は固有の尤度情報を含み、前記モデル化するステップは：
前記セルフループ固有の尤度情報を用いて退出アークの固有尤度情報を変更するステップ
を含む、請求項６に記載の方法。
【請求項８】
前記セルフループ情報は固有の尤度情報を含み、前記モデル化するステップは：
前記セルフループの尤度情報と、前記セルフループの尤度情報の存在のインジケーションとを保持するための複数のフィールドを含むように、退出アークを表すデータオブジェクトを変更するステップ
を含む、請求項６に記載の方法。
【請求項９】
前記アークは固有の尤度情報を含み、前記アークの少なくとも一部は更にセルフループ固有の尤度情報を含み、前記横断するステップは：
一組のアクティブアークを特定するステップ；
前記セルフループ固有の尤度情報を含む前記一組のアクティブアークのうちの少なくともサブセットの累積尤度情報を、少なくとも対応するセルフループ固有の尤度情報に基づいて更新するステップ；
前記累積尤度情報の更新の後に、第１の伝播段階において、前記一組のアクティブアークの累積尤度情報を伝播するステップ；
前記第１の伝播段階の後の第２の伝播段階において、新たにアクティブにされたアークに累積尤度情報を伝播するステップであり、前記新たにアクティブにされたアークは、前記第１の伝播段階において更新された１つ以上の状態の１つ以上の退出アークを含む、ステップ；
前記新たにアクティブにされたアークを含むように、且つ閾値未満の累積尤度の値を有するアークを削除するように、前記一組のアクティブアークを組み直すステップ；及び
組み直されたアクティブアークの組に関して、前記更新するステップ、前記第１の伝播段階及び前記第２の伝播段階を繰り返すステップ；
を含む、請求項１に記載の方法。
【請求項１０】
前記アークの前記一部の固有の尤度情報は、対応するセルフループ固有の尤度情報を含むように変更され、前記更新するステップは：
前記一組のアクティブアーク内の全てのアクティブアークの累積尤度情報を、対応するアークの固有の尤度情報に基づいて更新するステップ
を含む、請求項９に記載の方法。
【請求項１１】
前記ネットワークの少なくとも非イプシロンアークの各々は、該アーク固有の尤度情報を保持する１つ以上のフィールドの第１の組と、セルフループ固有の尤度情報を保持する１つ以上のフィールドの第２の組と、前記１つ以上のフィールドの第２の組にセルフループ固有の尤度情報が存在するときにセルフループインジケーションを保持するセルフループインジケータフィールドとを含み、前記更新するステップは：
現在の前記一組のアクティブアーク内の前記サブセットのアークを、前記セルフループインジケーションを含むアークとして特定するステップ；及び
特定された前記サブセットのアクティブアークに関してのみ、累積セルフループ尤度情報を更新するステップ；
を含む、請求項９に記載の方法。
【請求項１２】
ネットワークのアークの入力ラベルを、前記アークの出力文法要素のリストに変換するシステムであって：
ネットワークの状態のシーケンスに対応する前記ネットワークのアークの入力ラベルを、文法要素のシーケンスに対応する前記アークの出力文法要素のリストに変換するネットワーク；及び
特徴ベクトルのストリームに応答して前記ネットワークのアクティブアークを繰り返し伝播する推論エンジンであり、前記特徴ベクトルに応答して前記アクティブアークの目的状態を更新することを含む推論エンジン；
を有するシステム。
【請求項１３】
前記推論エンジンは：
前記アクティブアークの起源状態に関する情報であり、前記起源状態に関する尤度指標を含む情報、を取り出し；
前記アクティブアークを、対応する起源状態の前記尤度指標と前記特徴ベクトルとを用いて更新し；且つ
更新されたアクティブアークに従って、対応する目的状態を更新する；
ように構成されている、請求項１２に記載のシステム。
【請求項１４】
データオブジェクトに関するタスクを、該データオブジェクトに関する先行タスクが割り当てられた処理スレッドに基づいて順序付ける順序付けシステム；
を更に含む請求項１２に記載のシステム。
【請求項１５】
前記アークは固有の尤度情報を含み、前記アークの少なくとも一部は更にセルフループ固有の尤度情報を含み、前記推論エンジンは：
一組のアクティブアークを特定し；
前記セルフループ固有の尤度情報を含む前記一組のアクティブアークのうちの少なくともサブセットの累積尤度情報を、少なくとも対応するセルフループ固有の尤度情報に基づいて更新し；
前記累積尤度情報の更新の後に、第１の伝播段階において、前記一組のアクティブアークの累積尤度情報を伝播し；
前記第１の伝播段階の後の第２の伝播段階において、新たにアクティブにされたアークに累積尤度情報を伝播し、ただし、前記新たにアクティブにされたアークは、前記第１の伝播段階において更新された１つ以上の状態の１つ以上の退出アークを含み；
前記新たにアクティブにされたアークを含むように、且つ閾値未満の累積尤度の値を有するアークを削除するように、前記一組のアクティブアークを組み直し；且つ
組み直されたアクティブアークの組に関して、前記更新、前記第１の伝播段階及び前記第２の伝播段階を繰り返す；
ように構成されている、請求項１２に記載のシステム。
【請求項１６】
ネットワークの状態のシーケンスに対応する前記ネットワークのアークの入力ラベルを、文法要素のシーケンスに対応する前記アークの出力文法要素のリストに変換するシステムであって、前記アークは固有の尤度情報を含み、前記アークの少なくとも一部は更にセルフループ固有の尤度情報を含み、当該システムは：
一組のアクティブアークを特定する手段；
前記セルフループ固有の尤度情報を含む前記一組のアクティブアークのうちの少なくともサブセットの累積尤度情報を、少なくとも対応するセルフループ固有の尤度情報に基づいて更新する手段；
前記累積尤度情報の更新の後に、第１の伝播段階において、前記一組のアクティブアークの累積尤度情報を伝播する手段；
前記第１の伝播段階の後の第２の伝播段階において、新たにアクティブにされたアークに累積尤度情報を伝播する手段であり、前記新たにアクティブにされたアークは、前記第１の伝播段階において更新された１つ以上の状態の１つ以上の退出アークを含む、手段；
前記新たにアクティブにされたアークを含むように、且つ閾値未満の累積尤度の値を有するアークを削除するように、前記一組のアクティブアークを組み直す手段；及び
組み直されたアクティブアークの組に関して、前記更新するステップ、前記第１の伝播段階及び前記第２の伝播段階を繰り返す手段；
を有する、システム。
【請求項１７】
前記アークの前記一部の固有の尤度情報は、対応するセルフループ固有の尤度情報を含むように変更され、前記更新する手段は：
前記一組のアクティブアーク内の全てのアクティブアークの累積尤度情報を、対応するアークの固有の尤度情報に基づいて更新する手段
を含む、請求項１６に記載のシステム。
【請求項１８】
前記ネットワークの少なくとも非イプシロンアークの各々は、該アーク固有の尤度情報を保持する１つ以上のフィールドの第１の組と、セルフループ固有の尤度情報を保持する１つ以上のフィールドの第２の組と、前記１つ以上のフィールドの第２の組にセルフループ固有の尤度情報が存在するときにセルフループインジケーションを保持するセルフループインジケータフィールドとを含み、前記更新する手段は：
現在の前記一組のアクティブアーク内の前記サブセットのアークを、前記セルフループインジケーションを含むアークとして特定する手段；及び
特定された前記サブセットのアクティブアークに関してのみ、累積セルフループ尤度情報を更新する手段；
を含む、請求項１６に記載のシステム。
【請求項１９】
データオブジェクトに関するタスクを、該データオブジェクトに関する先行タスクが割り当てられた処理スレッドに基づいて順序付ける手段；
を更に含む請求項１６に記載のシステム。
【請求項２０】
前記ネットワークのアクティブアークを伝播する手段であり、特徴ベクトルに応答して前記アクティブアークの目的状態を更新する手段を含む、伝播する手段；
を更に含む請求項１６に記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１１−１２３４９４（Ｐ２０１１−１２３４９４Ａ）
【公開日】平成２３年６月２３日（２０１１．６．２３）
【国際特許分類】
【出願番号】特願２０１０−２７６０６７（Ｐ２０１０−２７６０６７）
【出願日】平成２２年１２月１０日（２０１０．１２．１０）
【出願人】（５９３０９６７１２）インテル コーポレイション (931)
【Ｆターム（参考）】
【公開日】平成２３年６月２３日（２０１１．６．２３）
【国際特許分類】
【出願日】平成２２年１２月１０日（２０１０．１２．１０）
【出願人】（５９３０９６７１２）インテル コーポレイション (931)
【Ｆターム（参考）】
[ Back to top ]