JP4890468B2

JP4890468B2 - ベイズ・ネットワーク構造学習のデータ分割及びクリティカル・セクション

Info

Publication number: JP4890468B2
Application number: JP2007548666A
Authority: JP
Inventors: ライ，チュンロン; フ，ウェイ
Original assignee: インテルコーポレイション
Priority date: 2004-12-31
Filing date: 2004-12-31
Publication date: 2012-03-07
Anticipated expiration: 2024-12-31
Also published as: EP1846837A4; CN101095132B; US8019715B2; WO2006069495A1; EP1846837A1; JP2008525905A; CN101095132A; US20080281771A1

Description

本発明の実施例は、ネットワーク構造学習に関し、特に、ベイズ・ネットワーク構造学習のデータ分割に関する。

大量の情報（特に関連情報）をネットワーク構造に編成することができる。ベイズ・ネットワークは、前述のネットワーク構造の一般的な例である。ベイズ・ネットワークの利用は、バイオインフォマティックス、パターン認識、統計計算等において増えている。ベイズ・ネットワーク構造の学習は非常に計算集約的であり、真の「最適な」構造を求めるための解決策は、NP-完全であり得る。ベイズ・ネットワーク構造の学習が非常に計算集約的であるにもかかわらず、更にずっと大きなデータセットを有するネットワークの研究が行われている。これによって、計算負荷が増大し、潜在的には、指数関数的な増加が計算負荷にもたらされ得る。発見的手法は多くの場合、構造学習の性能効率の向上（例えば、実行時間の削減）に焦点を当てる。性能効率は、現代のネットワークに対する許容可能な実用的解決策の提供において一層重要になってきている。

構造学習アルゴリズムの実行において複数の計算マシン及び／又は処理コアの資源を含めるために並列学習手法が考えられてきている。前述の手法の並列性によって、複数の資源の間での作業の分散、及び解決策を求めるために一システムが費やす時間の削減が図られる。伝統的な並列学習によって、基本的で単純なやり方で計算タスクを分散させる。これによって通常、並列計算資源間での計算タスクの分散において、各並列計算資源に割り当てられるタスクの数のみが考慮に入れられる。

例えば、近傍スコアの計算において、一次スレッド又はマスタ・スレッドが、近傍計算を、利用可能な他のスレッド間で分散させることができる。近傍の計算において、スレッドは、スコア・キャッシュを検査して、構造のファミリ・スコアが既知であるかを判定することができる。スコア・キャッシュは伝統的には、スレッド間で共有され、ハッシュ・テーブルとしてアクセスされる、既知でかつ格納されたネットワーク・ファミリ・スコアのデータ構造である。スコアが既知である（キャッシュ・ヒットをもたらす）場合、計算資源は単に、スコアをロードし、これを用いて近傍スコア（関心の有向非循環グラフ（DAG）又は構造のスコア）を計算することができる。スコアが既知でない（キャッシュ・ミスをもたらす）場合、計算資源は、近傍スコアの計算に先行してファミリ・スコアを計算することが必要であり得る。複数のスレッドに利用可能なデータ構造として、スコア・キャッシュ・アクセスが、データのオーバランを削減するためにクリティカル・セクションにあることが必要であり得る。よって、計算資源は、その資源を非効率的に使用し、かつ／又は、別の計算資源がスコア・キャッシュをリリースするのを待ってアイドル状態に留まり得る。よって、構造学習に対する現行の、又は伝統的なマルチプロセッシング／ハイパスレッド手法は、増加するサイズ及び複雑度のネットワークの構造学習の所望の性能をもたらすことができないことがあり得る。

構造学習は、非常に一般的な意味合いでは、ノードのネットワークにおける変数間の確率的関係を発見する手法としてのベイズ・ネットワークに応用を有しており、各ノードは、条件／状態、並びに、条件／状態の原因及び／又は結果に関する情報を表す。構造学習は、個々のノード間の確率的関係に基づいてネットワーク構造表現を構成することによってネットワークを表すことができる。ヒル・クライミングは、静的及び／又は動的ベイズ・ネットワークの学習に多くの場合用いられるアルゴリズムであり、通常、ハッシュ・テーブルとして実現される多次元の疎行列であるスコア・キャッシュの利用を含み得る。行列の各要素は、ノード・ファミリ、若しくはノードのファミリ（又は本明細書では単に「ファミリ」）のスコアを格納する。ファミリは、関心の現在又は目標のノード（子ノード）、及び現在のノードの親ノード（又は本明細書では単に「親」）を含む。親ノードと目標ノードは、確率的関係によって関係していることがあり得る。スコアが計算された後、スコア・キャッシュを用いてファミリのスコアを格納することができる。

構造学習の場合、学習アルゴリズムは一般にまず訓練データ（既知の関係）をロードし、訓練データ及び特定のスコア・メトリックに基づいて、スコアを計算して構造を判定する。アルゴリズムは、始点、又は当初の現行構造（構造学習が開始する当初のユーザ定義ベイジアン・ネットワーク構造であり得る）のスコアを計算する。始点の近傍（エッジ差によって現行構造から分離された構造）を生成し、各近傍のスコアを計算することが可能である。近傍毎のスコア計算に対する伝統的な手法は、スコア・キャッシュを照会して、近傍に対応するファミリのスコアが既知であるか、又は既に計算されているかを判定することを伴う。ファミリ・スコアは変わらないものとし得る。したがって、スコアは、一算出のために計算されている場合、格納し、別の算出に再使用することができる。ファミリ・スコアが利用可能な場合、スコアを直接ロードし、近傍スコアを計算することができる。スコアが利用可能でない場合、構造全体（ファミリを含む）のスコアが概括的に計算され、スコア・キャッシュが更新される。処理は通常、近傍全てについて反復し、アルゴリズムは、次の学習反復を始めることができる新たな現行構造として、最大スコアを有する近傍を選ぶ。最適には、処理は、現行構造よりも高いスコアを有し得る近傍が存在しない間、反復する。実用的なアプリケーションは多くの場合、実現形態について判定される発見的手法を用いる。最適な解決策の達成が非実用的又は不可能であり得るからである。

構造学習に共通の課題は、計算量、及び関連した長い実行時間である。並列化によって、複数のスレッド（例えば、並列コア、算術論理演算装置（ALU）、処理コア、プロセッサ、中央処理装置（CPU）等）の間で近傍スコアリングのタスク／算出を分散させることによって構造学習が高速化され得る。単純な並列化手法では、各スレッドは、近傍をスレッド間で等しく分散させて、計算する対象の１つ又は複数の近傍を受け取ることができる。スコア・キャッシュのコンテンツ、及び／又は、スコア・キャッシュのアクセスに係わる処理は、スレッドの性能に影響を及ぼし、競合状態、遅延等をもたらし得る。伝統的には、スコア・キャッシュは、各スレッドにアクセス可能な単一のデータ構造（前述の状態と同様な状態をもたらし得る）である。現在の並列化手法には、クリティカル・セクションを作成して、一度に一スレッドにキャッシュ・アクセスを制限することが関係する。代替策は、スレッド毎に１つ、キャッシュの複数バージョンを格納することであり得るが、これは、許容可能でないオーバヘッド・ペナルティ・レベルをもたらし得る。

システム効率は、改善された局所性最適化及び負荷分散を計算タスク間で備えることによって改善することが可能である。更に、スコアリング・アルゴリズムは、スコア・キャッシュのより効率的な使用及び／又はアクセスを可能にするための実行のために再構成することができる。一実施例では、スコア・キャッシュは複数のサブ部分に区分される。例えば、スコア・キャッシュは、アレイの各要素が、ノードのスコア・キャッシュである、個々にアドレス指定可能なメモリ構造のアレイであり得る。複雑な有向非循環グラフ（DAG）（例えば、数千のノードを含むもの）では、ハッシュ索引関数の不規則なアクセス・パターンによってこうむるペナルティは、スコア・キャッシュ・アレイを設けることによって削減することができる。ハッシュ索引化のペナルティは、スコア・キャッシュ管理のより高いオーバヘッドに関連したペナルティによって置き換えることができる。大規模の複雑なDAGでは、不規則な／任意のアクセスのペナルティは、オーバヘッドのペナルティよりもずっと大きいことがあり得る。

例えば、遺伝子ネットワーク・アプリケーションでは、DAGは、数千のノードから成り得る（これは、スコア・キャッシュが数百万の要素を格納することを必要とすることを意味している）。ハッシュ索引関数は、数千ノード毎にアレイ要素を有するスコア・キャッシュ・アレイの管理よりもずっと大きなペナルティをもたらし得る。例えば、２４００個の変数（よって、２４００個のノードを有するDAGに対応する）を有する遺伝子ネットワークの任意のキャッシュ・アクセスは、２４００個の要素のアドレス指定可能なアレイを有して生成されるスコア・キャッシュをアクセスするよりも大きなペナルティをこうむり得る。一実施例では、各要素は、遺伝子ネットワークにおける対応するノードのスコアのみを格納する小さなスコア・キャッシュを表す。

更に、分割スコア・キャッシュ手法によって、スコアリングにおいて現行DAGの近傍を再編成する機会が提供される。同じノードとの間でエッジを追加又は削除する近傍を評価する場合、スコアリング・アルゴリズム（及び、よって、アルゴリズムを実行するスレッド）は、特定のノードに対応する単一のスコア・キャッシュ・アレイ要素（本明細書では分割スコア・キャッシュと表す）のみをアクセスすることによって近傍算出を完了するのに必要な情報全てを得ることができる。よって、スコアリングする対象の近傍を分散させる管理エンティティは、スコア・キャッシュのアクセスの局所性を改善するために、ノードに関する近傍をグループ化することが可能である。エッジを逆転させる近傍の場合、２つの処理（すなわち、元のエッジの削除、及び、逆方向のエッジの追加）が示唆される。この場合、各逆転によって、子ノードの一分割スコア・キャッシュ、及び親ノードの一分割スコア・キャッシュがアクセスされる。同じ子ノードにエッジ追加／削除を行う近傍と、逆転近傍をグループ化することが可能である。これによって、スコアリング／計算関数のアクセス・パターンが制御され得るものであり、したがって、局所性のアクセスが改善される。局所性の改善の結果、実行速度が向上する。最適化されたアクセスを有する分割スコア・キャッシュによって、時間的及び地理的な局所性性能拡充がもたらされる。

分離スコア・キャッシュによるデータの区分によって、データ競合又は競合状態の可能性も削減され得る。別々の終了ノードを別々のスレッドに分散させた場合、スレッド間でのデータの相互依存性の可能性が削減される。クリティカル・セクションをなお用いて逆転エッジを計算することができる。これによって、開始ノード及び終了ノードに対応する２つのスコア・キャッシュをアクセスすることができるが、さもなければ、クリティカル・セクションの使用をかなり削減することができる。

したがって、スコア・キャッシュの区分によって、データ・アクセス局所性、スコアリング・アルゴリズムの細分化された管理機能が改善され、スコアリング・アルゴリズムのマルチスレッド実現形態における多くのクリティカル・セクションがなくなるようになり得る。一実施例では、主スコア・ループが２つのループに分割される。第１のループでは、スレッドは、スコア・キャッシュの特定部分（別のスレッドに利用可能な別々の部分／サブ部分であり得る）にのみアクセスが許され得る。更に、第１のループにおけるスレッドは、他のスレッドのスコア・キャッシュを「ウォーミング」しようとし得る。スコア・キャッシュのウォーミングは、ノードに関連した１つ又は複数のファミリのファミリ・スコアをスコア・キャッシュにロードすることを含み得る。スコア・キャッシュに、第１のループの処理によって第２のループにおける使用のために予めロードされる場合、各キャッシュは読み出されるのみであり、書き込まれないのでクリティカル・セクションを必要としないことがあり得る。第１のループ上のスコア・キャッシュをロードすることによって、第２のループ上のキャッシュ・ミスがないことがもたらされ、クリティカル・セクションなしでもデータ競合の可能性が削減されるか、又はなくされ得る。その結果、マルチスレッドのスケーラビリティが、この手法によってかなり増加する。例えば、前述の手法の実現によって、デュアル・プロセッサ（DP）同時マルチプロセッサ（SMP）マシン／システム上の1.95倍の高速化がもたらされ得る。それによって、前述のデータ区分が理由で、より多くのプロセッサ又はCPU（中央処理装置）によって、SMP上、CMP（オンチップ・マルチプロセッサ）上、及び／又は、一様でないメモリ・アクセスNUMA並列処理マシン上のほぼ線形の高速化も潜在的に得られ得る。分割スコア・キャッシュの管理のための更なる、メモリ内オーバヘッド、及び実行時間のために、少数のノードを有するネットワークのスコアリングにおいて約3-11%の性能低下がみられ得る。

以下の詳細な説明は、限定ではなく、例を挙げた、図及び添付図面における種々の例証を含む。前述の図を以下に簡単に説明する。

本明細書中の、「実施例」への種々の参照は、本発明の少なくとも１つの実施例に含まれる特定の特徴、構造又は特性を表すものとする。よって、「一実施例において」や「別の実施例において」などの句が存在していることは、本発明の種々の実施例を表し得るものであり、必ずしも全てが同じ実施例を表している訳でないことがあり得る。

図１は、区分されたスコア・キャッシュを有する計算装置のブロック図の実施例である。計算装置１００は、コンピュータ、サーバ、ワークステーション、又はその他の計算デバイス／装置／マシンを表す。計算装置１００は、別々の処理の同時／並列ハンドリングを可能にするためにマルチスレッドであり得る。プロセッサ１１０は、１つ若しくは複数の処理装置及び／又は計算コアを表す。プロセッサ１１０は、中央処理装置、マイクロコントローラ、ディジタル信号プロセッサ（DSP）、ALU等を含み得る。プロセッサ１２０は同様に、１つ又は複数の処理装置及び／又は計算コアを表し、中央処理装置、マイクロコントローラ、ＤＳＰ、ＡＬＵ等を含み得る。プロセッサ１１０及び１２０は並列に動作し得る。一実施例では、プロセッサ１１０及び１２０は、計算装置１００の並列処理コアを表す。一実施例では、計算装置１００はプロセッサ１２０を含まない。計算装置１００は、同時マルチプロセッサ（SMP）システム、オンチップ・マルチプロセッサ（CMP）システム、及び／又はその他の並列処理の、一様でないメモリ・アクセス（NUMA）システムをあらわし得る。

メモリ１１２は、プロセッサ１１０によって実行するための一時的な変数及び／命令を格納し得る。メモリ１１２は、オンチップ・メモリ、例えば、プロセッサ１１０上のキャッシュ層、計算装置１００のシステム・バス上の揮発性記憶機構、システムのランダム・アクセス・メモリ（RAM）等を表し得る。メモリ１１２は、プロセッサ１１０によって直接アクセス可能であり、システム・バスによってアクセス可能であり、かつ／又はこれらの組み合わせによってアクセス可能であり得る。メモリ１２２は、プロセッサ１２０と同様に説明し得る。一実施例では、メモリ／キャッシュは一般に、プロセッサ１１０及び１２０にアクセス可能である。

一実施例では、計算装置１００は、計算装置１００が外部ソースから入力を受け取り、かつ／又は外部ソースに出力を供給することができる１つ又は複数の機構／装置を表すI／O（入力／出力）インタフェース１３０を含む。外部ソースは、別の計算システム、ユーザ等を含み得るものであり、表示装置、カーソル制御、英数字入力装置、オーディオ入力及び／又は出力装置、視覚ディスプレイ（例えば、発光ダイオード（LED））等を含み得る。I／Oインタフェース１３０は、I／O装置のドライバも含み得る。I／Oインタフェース１３０を介して受け取られる情報／データ／命令は、メモリ１１２及び／あるいはメモリ１２２並びに／あるいは大容量記憶装置１４０に記憶することができる。大容量記憶装置１４０は、１つ又は複数の種々の記憶機構（取り外し可能な記憶装置１４２（例えば、ディスク・ドライブ、メモリ・スティック／カード／スロット、ユニバーサル・シリアル・バス（USB）、接続された装置等）、及び非揮発性記憶装置１４４（例えば、ディスク・ドライブ、メモリ・スティック／カード／スロット、ハード・ディスク・ドライブ等）を含む）を表す。大容量記憶装置１４０は、メモリ１１２及び／又は１２２にロードし、プロセッサ１１０及び／又は１２０上で実行するためのプログラム／アプリケーション及び／若しくは命令、並びに／又は、プログラム若しくは命令に関する、又は関連したデータを記憶し得る。

データ、命令及び／又はプログラム情報は、マシン／電子装置／ハードウェアによって製品を介して供給し、計算装置１００によって／計算装置１００上で行うことができる。製品は、命令、データ等を供給するためにコンテンツを有する、マシンによってアクセス可能な／読み出し可能な媒体を含み得る。コンテンツは、計算装置１００が、前述の種々の動作、実行を行うことをもたらし得る。マシン・アクセス可能な媒体は、マシン（例えば、計算装置、電子装置、電子システム／サブシステム等）によってアクセス可能な形態で情報／コンテンツを供給（すなわち、記憶及び／又は伝送）する何れかの機構を含む。例えば、マシン・アクセス可能な媒体は、記録可能／非記録可能媒体（例えば、リード・オンリ・メモリ（ROM）、ランダム・アクセス・メモリ（RAM）、磁気ディスク記憶媒体、光記憶媒体、フラッシュ・メモリ装置等）、及び、伝搬信号の電気的、光学的、音響的又はその他の形式（例えば、搬送波、赤外線信号、ディジタル信号等）を含む。マシン・アクセス可能な媒体は、計算システムが動作中に計算システムが実行することができることがあり得る、計算システム上にコードをロードさせた計算システムを更に含み得る。よって、前述のコードを計算システムに備えることは、前述のコンテンツを製品に備えるものとし得る。更に、データベースやその他のメモリ場所上にコードを記憶し、伝搬信号による通信媒体を介したダウンロードにコードを供することは、製品に前述のコンテンツを備えるものとし得る。

一実施例では、計算装置１００は、有線インタフェース若しくは無線インタフェース、並びに／又は、有線インタフェース及び無線インタフェースを含み得るネットワーク・インタフェース１５０を含み得る。ネットワーク・インタフェース１５０は、計算装置１００がネットワークを介して並列計算装置とインタフェースすることができるネットワーク・カード／回路を表し得る。

一実施例では、計算装置１００は、データ・ネットワークの構造学習の値の記憶を備えるための１つ又は複数の構成部分を表し得るスコア・キャッシュ１６０を含む。スコア・キャッシュ１６０は、個々にアドレス指定可能なメモリ場所／部分であり得る複数の区分／サブ部分／要素１６１を含み得る。各場所は、スコア・キャッシュ１６０を要素アレイ（アレイの各要素が要素１６１である）として構造化することによってアドレス指定／アクセスすることができる。スコア・キャッシュ１６０は、記憶ハードウェアを管理するためのハードウェア構成部分及び／又はソフトウェア構成部分を表し得る。一実施例では、スコア・キャッシュ１６０は、プロセッサ１１０及びプロセッサ１２０にアクセス可能なデータ構造を表す。スコア・キャッシュ１６０におけるデータの記憶、及びデータへのアクセスは、データ競合を削減し、局所性を改善し、1つ又は複数のクリティカル・セクションをなくすよう構造学習処理において制御することができる。スコア・キャッシュ１６０は計算装置１００において概括的に示しており、大容量記憶装置１４０上に記憶されたデータであるものと、プロセッサ１１０又は１２０の一方又は両方において実行しているものと、かつ／又は、メモリ１１２又は１２２の一方若しくは両方に存在しているものとみなし得る。

図２は、区分されたスコア・キャッシュを有するマルチスレッド計算装置のブロック図の実施例である。計算装置２００は、プログラムの実行を行う／制御するデバイス、システム、装置及び／コンピュータである。計算装置２００は、ネットワーク構造学習の機能又はプログラムの一部若しくは全てを実行することができる。
計算装置２００は、複数のスレッド（１乃至N）を含む。ここでNは整数を表す。例えば、スレッド1乃至Nは、SMP、CMP、又はNUMAマシン上の複数の並列計算資源を表し得る。一実施例では、計算装置２００は、複数のサブ部分（サブ１乃至サブM）に区分されたスコア・キャッシュ２１０も含む。ここでMはNと同じ値であってもなくてもよい整数を表す。例えば、計算装置２００は、２つのスレッドを含み、スコア・キャッシュ２１０を1000個の要素に区分することができる。別の例では、計算装置は、１６個のスレッドを含み、スコア・キャッシュを２０個の要素に区分し得る。本明細書記載の手法の説明は、前述、又は何れかの他の特定の実現形態に限定されるものでない。上記手法は、複数の並列計算資源（スレッド）にスケーラブルであり、学習対象の小規模ネットワーク構造から大規模かつ複雑な構造までスケーラブルである。

各区分（サブ１乃至サブM）は、区分毎にエントリ数が同じであってもなくてもよい複数のエントリを含み得る。図２における表現は、例証のみとして意図されており、何れかの特定の区分に関連付けることができるいくつかのエントリを示すことを意図するものでない。一実施例では、各区分は、学習対象のネットワーク構造における別のノードと関連付けられる。エントリは、各ノードに関連付けられた別々のファミリの値を表し得るか、又は、別々のノード状態（例えば、他のノードとの関係）を表し得る。値が計算され、例えば、サブ１に記憶されると、値は一定であるとみなし得る。よって、値を一度スコアリングし、サブ１内のエントリに記憶し、将来の近傍スコアの算出に用いるための後のアクセスのために個々にアドレス指定することが可能である。

サブ１乃至サブMそれぞれはスレッド１乃至スレッドMの何れかによってアクセスすることができる。一実施例では、種々のスレッドから種々の区分へのアクセスが制御される。アクセスは、スレッドによって実行される対象の計算タスクの編成によって制御することができる。例えば、スレッドNには、サブMのエントリそれぞれを計算する連続のタスクが与えられ得る。後の計算タスクにおいてスレッド１がサブMをアクセスする場合、全ての値が算出され、スレッド１によるアクセスにおけるキャッシュ・ミスは何ら存在しない。このようにして、スレッド１及びスレッドNはクリティカル・セクションの必要性なしでサブMをアクセスすることが可能である。エントリの値が変わらないからである。

一実施例では、通信ネットワーク２２０は、ワイド・エリア・ネットワーク（WAN）（例えば、インターネット）を表し、コンピュータ間のローカル・エリア・ネットワーク（LAN）やその他の局所相互接続も表し得る。通信ネットワーク２２０は、LAN及びWANの組み合わせを表し得るものであり、有線及び／又は無線の接続／リンクを含み得る。計算装置の相互接続を表す通信ネットワーク２２０は本明細書及び特許請求の範囲において、情報の論理表現及び情報の内部関係を表し得るデータ・ネットワーク又はデータ・ネットワーク構造（例えば、ベイズ・ネットワーク）と混同すべきでない。

一実施例では、データベース（DB）２４０は計算装置２００と結合される。これは、直接リンク、又は例えば通信ネットワーク２２０を介した通信インタフェースであり得る。この例では、通信ネットワーク２２０は、計算装置２００とデータベース２４０との間の１つ又は複数の中間接続を表し得る。データベース２４０は、情報／データを記憶することができる何れかの数のデータベース・ハードウェア装置、サーバ等を表し得る。一実施例では、データベース２４０は、学習対象のネットワーク構造に関する情報を含む。例えば、データベース２４０は、１つ又は複数のファミリやその他のネットワーク構造が得られる証拠（例えば、既知データ、訓練データ）を含み得る。よって、データベース２４０は、構造を学習するデータ、近傍が判定され、近傍に関連したファミリが判定される等のデータを含み得る。データベース２４０は、ネットワーク構造自体を記憶しているとみなすこともできる。データベース２４０、及び／又は計算装置２００のスレッドの１つによって、ネットワーク構造のハンドルを生成することができる。データベース２４０の情報を用いて、スコア・キャッシュ２１０にロードされるファミリ・スコアを計算することができる。

図３は、構造学習ループを内部ループ及び外部ループに分割するフロー図の実施例である。構造学習を始めるために、構造を始点として選択することができ、近傍を判定することができる。近傍の判定、及び1つ又は複数の開始構造の選択を主スレッドによって行うことができる。主スレッドは、主スレッド自体を含む複数の並列計算スレッドに近傍算出タスクを分散させることができる。主スレッドにおいてであっても並列スレッドにおいてであっても、当初スコアが計算される（３０２）。図３の構成要素から得られるこの計算及び何れかの他の計算、処理、実行は、複数スレッドにおいて同時に又はほぼ同時に行うことができ、並列に処理されるということができる。始点は、任意に選択されるか、又は他の理由に基づいて選択される、構造学習処理における特定の基準／パラメータに基づいて選択することができる。スレッドは、DAG内の一ノードを終了ノード３０４として選択し、一ノードを開始ノード３０６として選択することができる。終了ノードはアークが向けられる子ノードである。開始ノードは親ノードである。親及び子としての２つのノード間の関係はアーク又はエッジによって表す。開始ノード及び終了ノードは、任意に、ノード・リストの最初として、又は特定のその他の基準に基づいて選択することもできる。一実施例では、選択は重要でない。

スレッドは、開始ノードから終了ノードまでのエッジが存在しているかを判定する（３１０）。例えば、スレッドは、スコア・キャッシュにアクセスして、エッジの値が計算されたかを判定することができる。分割スコア・キャッシュの場合、スコア・キャッシュへのアクセスは、ノードに関連したスコア・キャッシュ、又はスコア・キャッシュの部分又は区分へのものであり得る。エッジが存在しない場合、スレッドは、エッジ結果を加えることが有効な近傍をもたらすかを判定することができる（３２０）。有効な近傍が生じる場合、終了ノードの新たなスコアが、新たなエッジが加えられて計算される（３２２）。スレッドは、新たなエッジに基づいて近傍スコアを判定し、近傍のスコアが現在の最善の近傍よりも良いかを判定することができ、計算された近傍スコアがより良い場合に最善スコアの近傍を更新する（３２４）。

エッジが存在する場合、スレッドは、逆転エッジが、有効な近傍をもたらすかを判定することができる（３３０）。有効な近傍がもたらされる場合、開始ノード及び終了ノードの新たなスコアを計算することができる（３３２）。スレッドは、新たなエッジに基づいて近傍スコアを判定し、近傍のスコアが現在の最善の近傍よりも良いかを判定することができ、計算された近傍スコアがより良い場合に最善スコアの近傍を更新する（３２４）。最善スコアの近傍が更新されると、開始ノードから終了ノードまでのエッジが、有効な近傍をもたらさないか、又は、逆転エッジが、有効な近傍をもたらさない場合、スレッドは、スコアリングされた開始ノードが、選択された終了ノードの最後の開始ノードであるかを判定する（３４０）。この判定は、分割又は区分されたスコア・キャッシュを利用して、スコアリング・アルゴリズムの高速化実行のためのより良好な局所性を備える。例えば、分割スコア・キャッシュは、終了ノードの単一のアドレス指定メモリ場所を有し得るものであり、メモリ場所の各エントリは、開始ノードに対する、終了ノードに関連したスコアを表す。終了ノード及び開始ノードの役割を、同様な結果をともなって変えることが可能である。

開始ノードが、最後の開始ノードでない場合、次の開始ノードが選択され（３４２）、開始ノード全てが処理されるまで処理が反復される。開始ノード全てが処理されている場合、終了ノード全てが処理されているかをスレッドが判定する（３５０）。この構造は第１のループ及び第２のループを設ける。第１のループは、ノードのスコア・キャッシュにおける値を処理する。このようにして、第１のループは、第２のループによって用いるためにキャッシュにロードし、よって、スコア・キャッシュをウォーミングする。最後の終了ノードが処理されていない場合、次の終了ノードが選択され（３５２）、その終了ノードの処理が始まる。最後の終了ノードが処理されている場合、スレッドは、学習が終了したかを判定する（３６０）。学習がノード終了した場合、現行のＤＡＧが更新され、スコアリングされ（３６２）、近傍が現行構造より高いスコアを得ることが可能でない状態になるまで処理は反復される。最高のスコアの近傍が見つかった場合、最後の学習ＤＡＧが出力される（３６４）。

図４は、分離スコア・キャッシュによる構造学習のフロー図の実施例である。主スレッド又はマスタ・スレッドは、学習対象の構造の当初スコアを算出する（４０２）。当初スコアは、学習の始点を与える。マスタ・スレッドは、分割スコア・キャッシュ・アーキテクチャ（４０４）に基づいて並列スレッドへのスレッド作業ディスパッチを準備する。一実施例では、主スコア・キャッシュ・データ構造は、学習対象のネットワークのノード毎の一分割スコア・キャッシュであり得る複数の小さな、又は分割されたスコア・キャッシュに区分される。スコア計算は、処理するために並列スレッド間で分散させる（ディスパッチする）。スコア・キャッシュの分割性によって、作業分散における特定の最適化が可能になり、それによって、（並列ではなく）順次行われる作業の量がシステムにおいて削減されるようになる。

マスタ・スレッドは計算タスクを、利用可能なスレッド（スレッド1乃至スレッドN）それぞれに分散させる。計算タスクは、近傍のスコアを計算するための処理の一部又は全てを含み得る。各スレッドは、有効な近傍のスコアを計算する（４１２、４２２）。スコア・キャッシュは分割されているので、スレッドには、近傍計算の第１のループ上で競合しないスコア計算を割り当てることができる。伝統的には、並列化は、近傍全てを生成することと、算出のためにそれらをスレッドに等しく分散させることから成っている。その場合、スレッドは、割り当てられた近傍を個々に処理する。しかし、スレッドはまずスコア・キャッシュを照会して、近傍算出のスコアが計算されているかをみることができるので、データ競合（競合状態）を避け、スレッドの安全性を確保するためにクリティカル・セクションによってスコア・キャッシュ・アクセスが監視される必要があることを、大局的なスコア・キャッシュのみが伝統的に用いられていることは意味している。これは、クエリがミスした場合、スレッドがスコアを算出し、スコア・キャッシュを更新するからである。この場合、別々のスレッドは、大局的なスコア・キャッシュの同じエントリに書き込もうとしたことがあり得る。

しかし、クリティカル・セクションは並列化の利点を低減させるが、それは、マルチスレッド・プログラムの一部が順次実行され、それによってスケーラビリティがかなり低下するからである。例えば、遺伝子ネットワークの実行では、実行時間の最大６０％が、クリティカル・セクションが理由で順次行われ得る。アムダールの法則によれば、実行時間の６０％が順次の場合、デュアル・プロセッサ・システムは1((1-0.60)/2+0.60)=1.25倍以下の高速化に限定され、クアッド・プロセッサ・システムは1((1-0.60)/4+0.60)=1.43倍以下の高速化に限定される。これは、潜在的な線形高速化が0.625又は0.358それぞれに過ぎないことに相当する。プロセッサ数の増加は、線形高速化と実際の高速化との差違を悪化させる。

分割スコア・キャッシュによって、学習反復それぞれの主近傍スコアリング・ループを、より小さな２つのループに分割することが可能である。第１のループは、追加／削除エッジの近傍を処理し、対応する逆転エッジの場合、分割スコア・キャッシュをウォーム・アップする。一実施例では、これは、クリティカル・セクションなしで実現することができる。データ／処理全てが完全に区分されており、それによって、スコア・キャッシュ・データに対するスレッドの競合が阻止される。計算されるスコアが分割スコア・キャッシュに書き込まれるので、スレッドのシステムを同期化させることが可能であり、スコア・キャッシュに対する後のクエリ全てがスコア・キャッシュ・ヒットをもたらし、スコア・キャッシュにもう一度書き込む必要性がなくなり得る。よって、第２の（後者の）ループは、やはりクリティカル・セクションなしで分割スコア・キャッシュを読み出すことによって逆転エッジ近傍を処理することができる。必要な計算は全て、第１のループにおいて行われているからである。

よって、分割スコア・キャッシュのスレッド内アクセス（４１４、４２４）が、特定のスレッドのみによって処理されるスコア・キャッシュ区分（例えば、スコア・キャッシュ・アレイの要素）に対してスレッドによって行われる。スレッドは、スコア・キャッシュ区分に関連したノードの値をスコアリングし、後のスレッド間アクセスのためにスコア・キャッシュにロードすることが可能である（４１６、４２６）。これは、前述の通り、第２のループであり得る。スレッドは、最善のスコア（通常、ヒル・クライミング実現形態において最高のスコアである）を有する近傍を選択する（４１８、４２８）が、実現形態は、最低スコア、又は特定値に最も近いスコア、が最善のスコアであるように設計することが可能である。

種々の並列スレッドによって行われる処理は、通常、マスタ・スレッドによって同期化され、最善のスコアを有する現行処理近傍が選択される（４３０）。第２のループを次いで処理して、より良好なスコアの近傍が存在しているかを判定することができる。処理はもう一度種々の並列スレッドにディスパッチされ、スレッドは、スレッド間分割スコア・キャッシュ・アクセスを備えた有効な近傍のスコアを計算する（４４２，４５２）。分割スコア・キャッシュが先行して、計算されたスコアによってウォーミング又はロードされているので、スレッドはスコア計算を何ら行わなくてよいことがあり得る。よって、完全に分離されたデータ、又は他のスレッドによるアクセスから孤立させたデータをスレッドが処理しないことがあり得る場合でも、前述の処理はクリティカル・セクションなしで行うことができる。スレッドはもう一度、最善のスコアを有する近傍を選択し（４４４、４５４）、個々のスレッドの選択が同期化させられ、システムの最善の近傍が最善のスコアで更新される（４６２）。現行の最善の近傍は、主マスタ・スレッドによって制御することができる。それによって、スレッドによってスコアリングされる近傍の１つが現行の最善の近傍よりも良いかが判定される。

マスタ・スレッドは次いで、近傍をDAGに施し、スコアを更新することができる（４６４）。学習が終了した場合（４７０）、最終的に学習されたDAGが出力される（４７２）。学習が終了していない場合、学習を反復して（４７４）、より良好なスコアを備えた近傍を判定する。学習は、特定の実現形態のいくつかの基準に基づいて終了することができる。例えば、近傍が、閾値数の処理反復に対して最善の近傍であり得る、閾値数の反復に達したことがあり得る、計算の時間制限に達したことがあり得る等である。

本明細書記載のもの以外に、本発明の実施例に対する種々の修正をその範囲から逸脱することなく行うことができる。したがって、本明細書記載の例証及び実例は、限定的な意味合いでなく、例証的な意味合いで解されるべきである。本発明の範囲は、特許請求の範囲を参照することによってのみ判定すべきである。

分割されたスコア・キャッシュを有する計算装置のブロック図の実施例を示す図である。分割されたスコア・キャッシュを有するマルチスレッド計算装置のブロック図の実施例を示す図である。構造学習ループを内側ループ及び外側ループに分割するフロー図の実施例を示す図である。分離スコア・キャッシュによる構造学習のフロー図の実施例を示す図である。

Claims

構造学習の方法であって、
構造学習スコアリング処理の第１のスコア計算タスクを、第１のプロセッサ又は処理コアによって実行される第１のスレッドに、プロセッサ又は処理コアによって割り当てる工程であって、前記第１のスレッドが、前記第１のスコア計算タスクのために、共有され、区分された大局的なスコア・キャッシュの第１の区分のみをアクセスし、前記第１のスコア計算タスクにおいて用いるための第１の値を計算する工程であって、前記第１のスコア計算タスクは、構造の第１のノードを学習し、前記第１の区分は、前記第１のノードに関連した少なくとも１つのノード・ファミリのスコアを含む工程と、
前記構造学習スコアリング処理の第２のスコア計算タスクを、第２のプロセッサ又は処理コアによって実行される第２のスレッドに、プロセッサ又は処理コアによって割り当てる工程であって、前記第２のスレッドが、前記第２のスコア計算タスクのために、前記共有され、前記区分された大局的なスコア・キャッシュの第２の区分をアクセスし、前記共有され、前記区分された大局的なスコア・キャッシュの前記第１の区分へのアクセスを制限され、前記第２のスコア計算タスクは、前記構造の第２のノードを学習する工程を含み、前記第２の区分は、前記第２のノードに関連した少なくとも１つのノード・ファミリのスコアを含む工程と、
前記第１のスレッド及び前記第２のスレッドが前記第１の値、及び前記第２のスコア計算タスクにおいて使用されるために、前記第２のスレッドが並列に計算する第２の値を、前記共有され、区分された大局的なスコア・キャッシュの前記第１の区分及び前記共有され、区分された大局的なスコア・キャッシュの前記第２の区分それぞれに、プロセッサ又は処理コアによって記憶する工程と
を備える方法。
請求項１記載の方法であって、タスクを前記第１のスレッド及び前記第２のスレッドに、プロセッサ又は処理コアによって割り当てる工程が、同時マルチプロセッサ・システムの第１のプロセッサ及び第２のプロセッサにタスクを、プロセッサ又は処理コアによって割り当てる工程を備える方法。
請求項１記載の方法であって、タスクを前記第１のスレッド及び前記第２のスレッドに、プロセッサ又は処理コアによって割り当てる工程が、オンチップ・マルチプロセッサ・システムの第１の処理コア及び第２の処理コアにタスクを、プロセッサ又は処理コアによって割り当てる工程を備える方法。
請求項１記載の方法であって、前記第１の区分をアクセスするための前記第１のスレッドは、クリティカル・セクションなしで、前記共有され、区分された大局的なスコア・キャッシュの前記第１の区分をアクセスするために前記第１のスレッドを備える方法。
請求項1記載の方法であって、前記第１の区分及び前記第２の区分が、アドレス指定可能な複数の区分アレイ要素を備える方法。
請求項５記載の方法であって、前記アドレス指定可能な区分アレイ要素が、ベイズ・ネットワークのノードに関連した要素を備えており、各ノードが、アレイの要素に関連付けられる方法。
請求項１記載の方法であって、スコア計算タスクは、更なるスコア計算の構造のノードとは別のノードを有する構造の近傍の近傍スコアリングを備える方法。
装置であって、
共有され、区分された大局的なスコア・キャッシュの直接アドレス指定可能なキャッシュ区分をベイズ・ネットワークの各ノードに関連付ける手段と、
前記ベイズ・ネットワークの第１のノードに関連した近傍算出を第１の並列スレッドに分散させる手段であって、前記第１の並列スレッドが、前記第１のノードに関連した直接アドレス指定可能なキャッシュ区分をアクセスして、前記近傍算出の情報を取得し、前記第１のノードに関連した区分は、前記第１のノードに関連した少なくとも１つのノード・ファミリのスコアを含む手段と、
前記ベイズ・ネットワークの第２のノードに関連した近傍算出を第２の並列スレッドに分散させる手段であって、前記第２の並列スレッドが、前記第１のノードに関連した区分へのアクセスを制限され、前記第２のノードに関連した直接アドレス指定可能なキャッシュ区分をアクセスして、前記近傍算出の情報を取得し、前記第２のノードに関連した区分は、前記第２のノードに関連した少なくとも１つのノード・ファミリのスコアを含む手段と
を備える装置。
請求項８記載の装置であって、前記直接アドレス指定可能なキャッシュ区分を各ノードに関連付ける手段は、前記直接アドレス指定可能なキャッシュ区分のアドレスを有するデータ構造におけるメモリ場所への直接で一意のアドレス索引化を備える手段を備える装置。
請求項８記載の装置であって、前記ベイズ・ネットワークの前記第１のノードに関連した近傍算出、及び前記ベイズ・ネットワークの前記第２のノードに関連した近傍算出は、非相互依存ノードから成る別個の近傍の算出を第１の並列スレッド及び第２の並列スレッドに分散させる手段を備える装置。
請求項８記載の装置であって、前記第１のスレッド及び前記第２のスレッドが、メモリ・データ構造へのアクセスを共有する複数の並列計算資源を有するシステムの第１の計算資源及び第２の計算資源を備える装置。
請求項８記載の装置であって、前記近傍算出において前記第１のノード及び前記第２のノードについて計算されたファミリの前記第２のノードに関連したキャッシュ区分及び前記第１のノードに関連したキャッシュ区分それぞれに記憶するための前記第１の並列スレッド及び前記第２の並列スレッドを更に備える装置。
請求項１２記載の装置であって、ヒルクライミング・アルゴリズムの近傍スコアリング・ループの第１の近傍スコアリング・サブループの近傍算出をディスパッチする手段を備え、更に、前記ヒルクライミング・アルゴリズムの前記近傍スコアリング・ループの第２の近傍スコアリング・サブループの近傍算出をディスパッチする手段を備え、スレッドが、前記第１のスコアリング・サブループ中に、前記キャッシュ区分に記憶されたファミリ・スコアをアクセスする装置。