(57)【特許請求の範囲】
【請求項１】
複数のＢＢＮモデル処理要求を処理するＢＢＮモデル処理システムであって、
少なくとも１つのクライアント手段からＢＢＮモデル処理要求を受け取る管理サーバ手段と、
前記管理サーバ手段に接続され、前記ＢＢＮモデル処理要求に関連したＢＢＮモデルを計算することによって、クライアントの要求を処理する複数のＢＢＮサーバ手段と、を備え、
前記管理サーバ手段は、前記ＢＢＮモデル処理要求に関連したＢＢＮモデルを実行するための、計算リソース必要量を推定する負荷推定器と、
前記複数のＢＢＮサーバ手段の各々にかかる負荷および推定された計算リソース必要量にしたがって前記ＢＢＮモデル処理要求の各々を、前記複数のＢＢＮサーバ手段の内の選択されたＢＢＮサーバ手段へ分配する負荷分配器と、を含むＢＢＮモデル処理システム。
【請求項２】
前記負荷推定器は、前記計算リソース必要量としてＣＰＵ時間を計算する請求項１に記載のＢＢＮモデル処理システム。
【請求項３】
前記負荷推定器は、前記計算リソース必要量として記憶領域サイズを計算する請求項１に記載のＢＢＮモデル処理システム。
【請求項４】
ＢＢＮモデルの、診断される問題についての原因の数、対応する問題を解決するために取り得る行動の数および診断する問題に制約を付するためにクライアントに提出できる質問の数を含むデータベースをさらに備え、前記負荷推定器は、前記データベースに含まれる、対応するＢＢＮモデルの前記原因の数、前記行動の数および前記質問の数を使用して、前記ＢＢＮモデル処理要求の各々を処理するための、計算リソース必要量を推定する請求項１から３のいずれかに記載のＢＢＮモデル処理システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は確率的診断及び手順に関し、より詳細には、診断システムに適用されるベイジアン信念ネットワークの必要とするリソースを推定する方法及びシステムに関する。
【０００２】
【従来の技術】
一般に、様々な問題領域に適用される診断手法は、特定の確定値（evidence）または制約条件を評価し、その特定の確定値や制約条件に関連する確率に基づいて、プロセスにおける適当な次のステップを決定する。種々の問題を解くとき、人間はこのような診断を規則的に行う。コンピューティング・システムが同様の問題を解くときには、収集した確定値や制約条件に基づいた同様の確率的手法を利用することが多い。
【０００３】
トラブル・シューティングと診断「ウィザード」は、よく使われる自動診断システムの例である。コンピューティング・システムのこのようなウィザードは、ユーザから解決すべき問題の性質を表す入力を受け取るのが普通である。ユーザとの多数の質疑応答の対話を通じて、ウィザードはその問題に対し取り得る解決策の範囲を狭める。言い換えると、ユーザにより提供される一組の制約条件に確率的分析を適用することによって、問題を診断している。トラブル・シューティングと診断ウィザードは、コンピューティング・システムのエンド・ユーザを補助する自動トラブル・シューティングに使用されることが多く、これによってエンド・ユーザは、コンピューティング・システムと提携している顧客サポートサービスとの対話に頼らずに、未解決の問題を迅速に診断することができる。
【０００４】
このような問題診断に使用するコンピューティング・システムの診断能力を向上させるために、種々の数学的モデルが適用されている。良く知られているモデルの１つは、ベイジアン信念ネットワーク（Bayesian belief network、以下「ＢＢＮ」ともいう）と呼ばれることが多い。ベイジアン信念ネットワークは、ベイズ則を繰り返し適用し、確定値や制約条件及び関連する確率に基づいて、問題診断において起こり得る事象や次のステップを推論する。従って、ベイジアン信念ネットワークは、収集した確定値と関連付けられる特定の事象あるいは状態を表すノードと、ノードによって表された種々の事象の間の確率的依存関係を表しているノード間を接続する弧（arc）の集合として数学的に表現されることが多い。ステップのコスト、ステップについての説明等の情報でベイジアン信念ネットワークの表現を拡張することによって、ユーザ問題のトラブルシューティングにベイジアン信念ネットワークを有効に適用することができる。
【０００５】
このようなＢＢＮ手法や自動（コンピュータ化）問題診断システムを使用すると、ＢＢＮの確率的決定の計算が複雑であることに起因する数々の困難が生じる。ＢＢＮ手法を使用するには、取り得る状態や関連する確率を計算するために、ＣＰＵの処理サイクルやメモリを含むかなりの計算リソースが必要となる。利用可能な計算リソースが予測できないと、ベイジアン信念ネットワーク手法を実行するにあたって問題となる。ＢＢＮ手法の適用に消費される計算リソースは、これまで予測不可能と考えられていた。所定の制約条件下で、特定の問題解決にＢＢＮ手法を利用するために必要なリソースを推定する正確なモデルは提案されていない。このため、実用的な問題として、既知のＢＢＮ診断ツールは専用の計算サーバ上で演算するものに限られている。言い換えると、単一のユーザ/クライアントのために単一の問題を解決する演算を行う単一のＢＢＮ診断ツールは、単一の専用計算サーバ上の全ての利用可能なリソースを消費することが許容されている。
【０００６】
この複雑性及び関連する専用計算リソースの必要性は、ＢＢＮ診断ツールシステムの有用性を低下させている。なぜなら、単一のＢＢＮ診断サーバが複数のクライアントからの要求にサービスを提供するクライアント/サーバコンピュータ・アーキテクチャでは、ＢＢＮ診断ツールシステムの管理は容易ではないからである。１つのＢＢＮネットワークの計算に単一の計算サーバを割り当てなければならない場合、ＢＢＮ診断ツールをクライアント/サーバモデルに展開してより多数のクライアントにサービスさせることは簡単ではない。
【０００７】
【発明が解決しようとする課題】
従って、ＢＢＮ診断システムに必要な計算リソースの特徴をより適切に調べ、クライアント/サーバ・アプリケーション・アーキテクチャにおけるＢＢＮ診断ツールの計算リソースの管理を改善する必要がある。
【０００８】
【課題を解決するための手段】
本発明は、特定の制約付き問題を解決するためにＢＢＮ診断ツールが必要とする計算リソースの多項式モデルを提供することによって、上述の及び他の問題を解決する。ＢＢＮの計算の複雑性を特徴付ける改善した方法を用いることで、管理手法（本発明の範囲外）は、複数の要求クライアントのために動作する１つ以上の計算サーバに対するＢＢＮ診断計算の分布を適切に管理することができる。言い換えると、本発明によるＢＢＮ計算リソースの改善された推定方法により、計算リソースを効率的に管理し、ＢＢＮサーバリソースをより適切に展開して複数のクライアントにサービスすることができる。
【０００９】
実験データから、ＢＢＮ診断計算は、メモリ集約的及びＣＰＵ集約的であることが分かる。ＣＰＵの利用は周知の管理可能な問題である一方、記憶領域の利用については注意深く管理して、ＢＢＮ計算モデルの演算での致命的なエラーを回避しなければならない。さらに、実験データから、ＢＢＮの記憶領域の要件は、多項式による計算複雑性（polynomial computational complexity）によって正確に推定することができることが分かる。必要なリソースを計算によって簡単に推定できると、周知の管理手法によって、ＢＢＮサービスの負荷を１つ以上のサーバに正確に分配して複数のクライアントにサービスすることができる。
【００１０】
本発明のさらなる利点は、複数のＢＢＮサービスの管理を１つ以上のサーバノードで動作可能とすることによって、単一のクライアント要求のために複数のＢＢＮモデルを並列で実行することができる点である。このように複数のモデルを並列に演算することで、モデルマッチング処理が可能となる。本明細書において、モデル・マッチングとはユーザの問題を最も良く扱えるモデルを探索するプロセスのことを指す。例えば、最も適切なモデルが明らかになるまで多数の競合モデルを並列に実行することによって、これを達成することができる。このようにモデル・マッチングのために複数のモデルを実行することは、サーバのネットワーク上で分散された複数のＢＢＮモデル実行の演算を管理するという別の利点である。
【００１１】
【発明の実施の形態】
図１は、本発明のＢＢＮリソース推定を有効に適用することができるシステム100のブロック図である。複数のクライアント102は、ネットワーク104を介して、問題を解決または診断するためにサーバからのサービスを要求する。クライアント102は、トラブル・シューティング・ガイドやウィザード等の問題解決機能を含む、任意のアプリケーションまたはユーザ・プロセスである。ネットワーク104は、例えばイントラネットやインターネットを含む任意の分散処理型通信ネットワークである。より一般的には、任意のプロセス間通信を当技術分野で周知のクライアント/サーバ相互動作に用いることができる。従って、図１に示した種々のプロセスを相互接続された複数の計算システムに渡って物理的に分散して、またはクライアント/サーバ・アーキテクチャを用いた単一の計算システム内で動作して、プロセス間通信を達成することができる。このような設計の選択は当業者にとって周知であり、これ以上の説明は行わない。
【００１２】
このような要求はサーバプロセス106に向かう。具体的には、サーバプロセス106は本発明に従ってこのような診断要求を管理し、この要求を計算サーバ112から116の何れかに分配してＢＢＮを処理し、クライアント102により要求された問題を解決または診断する。
【００１３】
ＢＢＮ管理サーバプロセス106は、クライアントの質問に関連してＢＢＮを処理するのに必要な計算リソースを推定する負荷推定器108を含む。負荷推定器108は、ＢＢＮデータベース130から、クライアントの要求に関連したＢＢＮのパラメータ及び属性を探す。発見されたパラメータ及び属性は、負荷推定器108によってＢＢＮに必要な推定計算リソースを計算するのに用いられる。データベース130はサーバ106の知る各ＢＢＮモデルのパラメータ及び/または属性を含む任意の構造である。データベースという用語は、特定の複雑な構造を意味しているわけではない。メモリ内のテーブルのような単純な構造からインデックス付けされたデータベースのような複雑な構造までの任意の構造を、要素130の意図する目的のために使用することができる。このような設計の選択は当技術分野において周知である。
【００１４】
ＢＢＮ管理サーバプロセス106は、負荷分配器110を含むのが好ましい。負荷分配器110は、負荷推定器108に応答して、クライアントの要求に関連するＢＢＮモデルを実行するのに必要な推定計算リソースに基づいて、適当なＢＢＮサーバプロセス112〜116にクライアントの要求を分配する。ＢＢＮを処理するために十分な利用可能な計算リソースを有するサーバプロセス112〜116は、ＢＢＮ管理サーバプロセス106からクライアントの要求を受け取り、その要求に関連したＢＢＮモデルを計算することによってクライアントの要求を実際に処理する。図１に示すように、ＢＢＮサーバプロセス112は、現在２つのＢＢＮモデル、すなわちＢＢＮ＃１(118)とＢＢＮ＃２(120)を処理している。ＢＢＮサーバプロセス114は、クライアントのために１つのＢＢＮモデル、すなわちＢＢＮ＃３(  122)を処理している。ＢＢＮサーバプロセス116は、現在ＢＢＮモデルを処理していない。ＢＢＮモデル118、120、122を表す四角形の大きさによってあらわされているように、各ＢＢＮモデルは、ＢＢＮモデルを処理するのに必要な推定計算リソースを提供することができるＢＢＮサーバプロセス112〜116に与えられる。ある時間で、ＢＢＮサーバプロセス112は、２つのＢＢＮモデル118、120を処理することができる十分な計算リソースを有していた。ＢＢＮモデル122はより多くのリソースを必要としたので、このモデルを処理するのに十分なリソースを有していたＢＢＮサーバプロセス114に送られた。負荷推定器108は、クライアント要求に対応する各ＢＢＮモデルに必要な計算リソースを推定する。この推定により、負荷分配器110は、複数のクライアント102のために処理するＢＢＮモデルを適当なＢＢＮサーバプロセス112〜116に分配することができる。
【００１５】
問題の重要クラスは有界（bounded）ＢＢＮモデルによって表すことができると判断されてきた。このようなＢＢＮにおける境界や制約条件の観点より、本発明は、ＢＢＮの計算リソース要件（計算リソース必要量、特にメモリの利用）はＢＢＮの種々の属性及びパラメータによる簡単な多項式として推定できることを示す。従って、図１の負荷推定器108は、このような多項式計算を利用して、任意の選択された問題分析（すなわち、任意の特定のトラブルシューティング過程）に対応するＢＢＮの処理の計算リソース要件を推定する。
【００１６】
図２は図１の負荷推定器108の動作を説明するフローチャートであり、特定の要求クライアントプロセスのために所定のＢＢＮを処理するのに必要な計算リソースを推定する。最初にステップ200で、ユーザにより選択された有界ＢＢＮ（選択された診断するべき問題）の属性とパラメータを収集する。上述のように、これらのパラメータと属性とは、クライアント/ユーザの要求に従って解決すべき特定の問題に対して、パラメータと属性とをＢＢＮと関連付けるテーブルまたはデータベース構造から検索される。ステップ202で、選択されたＢＢＮに関して検索されたパラメータと属性とに従って、選択されたＢＢＮを処理するために必要な推定計算リソースを計算する。好ましい多項式による推定については後述する。ステップ204で、計算した推定結果を返して、複数のクライアント要求のために複数のＢＢＮモデルを処理する負荷を分配するときにこれを利用する。
【００１７】
図１１は、ベイジアンネットワークの負荷要件を推定し、ＢＢＮの推定計算リソース負荷のバランスに基づいて複数のサーバに複数のＢＢＮ要求を分配するためのＢＢＮ管理サーバの全体的な動作の詳細を説明するフローチャートである。ステップ1110で、管理サーバシステムの知るすべてのＢＢＮモデルについての確率を前もって計算する。後に詳細に説明するように、これらの確率を前もって計算することで、ＢＢＮモデル計算の最初のスタートアップ時間が改善されるので、ユーザの応答性についての印象が改善する。ステップ1112で、システムの知る各ＢＢＮについて推定ＣＰＵ時間と推定記憶領域サイズ要件を計算する。ステップ1114で、ＢＢＮ計算に使用されるシステムの各サーバ上で利用可能なＣＰＵと記憶領域リソースを決定する。ステップ1116で、ステップ1110〜1112の演算により決定した全てのパラメータを管理サーバの構成ファイルに格納する。ステップ1118で、クライアントプロセスから受け取る各ＢＢＮ要求を繰り返し処理する。
【００１８】
要求の処理には、指定されたＢＢＮの推定負荷要件及び各サーバにおける現在の負荷とに基づいて適当なサーバを選択することが含まれる。新しい要求の処理には、クライアントから要求を非同期的に受信することを含む。サーバが要求の処理を完了すると、非同期的な事象が管理サーバに送られて、処理すべき他の要求を許可する。管理サーバは各サーバのローディングを追跡し、指定したＢＢＮの現在の負荷及び負荷要件に基づいて、新しい要求を分配する。
【００１９】
ステップ1100〜1108は、クライアントからの新しいＢＢＮ要求の非同期的受信に応答した管理サーバの処理を表す。ステップ1100で、まずクライアントの指定したＢＢＮモデルを処理するための最適のサーバを選択する。最適のサーバは、各サーバにかかる負荷及びクライアントの指定したＢＢＮモデルの推定負荷要件とに従って選択される。指定されたモデルの処理に十分なリソースを複数のサーバが有していた場合、単純ラウンドロビンまたは他のスケジューリング手法を用いて複数のサーバ間でモデル計算を分配することができる。
【００２０】
ステップ1102で、任意のサーバがステップ1100の演算によって選択されたか否かを判定する。新しいクライアント要求を処理する十分なリソースが利用可能であるサーバが無いときのように、全てのサーバがＢＢＮモデルの計算に現在ビジーであるときは、新しい要求の分配は延期される。このような要求の延期は、単純にサーバが処理を完了するのを待ち、その後該サーバを選択することによって実施できる。または、図１１に示すように、先行する要求が最終的に完了した後の処理のために、このような延期された要求を待ち行列に入れておくこともできる。新しいクライアント要求を処理するための容量を持つサーバが現在ない場合は、ステップ1104でその要求を後の処理のために待ち行列に入れ、サーバがその要求を処理することができるようになるまで、方法は終了する。
【００２１】
サーバがステップ1102で現在利用可能であると決定された場合、ステップ1106で、そのクライアントＢＢＮを選択されたサーバに転送する。ステップ1108で、構成ファイル内の現在の負荷戦略（statistics）を増加させて、新しいクライアント要求の処理によって増加した新しい負荷を選択したサーバに反映させる。
【００２２】
ステップ1120〜1126は、クライアントのＢＢＮモデル要求の計算が完了したことを示す非同期的事象の受信に応答した管理サーバの処理を表す。ステップ1120で、まず構成ファイル内のサーバの現在の負荷戦略を減らし、ＢＢＮモデル処理負荷の完了を反映させる。特定のクライアントのＢＢＮモデルの処理を完了したサーバは、新しいクライアントＢＢＮモデル要求の処理のために利用可能なリソースを有している。ステップ1122で、適当なサーバが利用可能となるのを待機していた任意の先行するクライアント要求が待ち行列にあるか否かを判断する。待ち行列に要求があれば、ステップ1126で、次に待機している要求を待ち行列から出して、ステップ1100に進み（ラベルＡ）、適当なサーバを見つける。
【００２３】
当業者は、図１１のフローチャートは、ＢＢＮモデルの負荷要件を推定し、サーバ間でＢＢＮ要求を処理する負荷が均衡するようにＢＢＮモデル要求を複数のサーバに分配するようプログラムされている、管理サーバの一実施形態に過ぎないことを認めるであろう。このような負荷推定及び負荷分配を利用する多数の等価な構造及び方法は、当業者にとっては明らかであろう。
【００２４】
実験データと数学的証明（図示せず）により、有界ＢＢＮについてサイズが測定された計算リソースは多項式の複雑性で計算可能であることが分かる。図３は、特定の関連する問題を解決するための実際のＢＢＮの例（「ネットワーク」列）及びこのネットワークの関係するパラメータと属性を表すテーブルである。第２（「＃原因」）は、診断される問題について既知の起こり得る原因の数を示す。第３列（「＃行動」）は、対応する問題を解決するために（より一般的に言うと、対応する問題をさらに診断するために）取り得る行動の数を示す。第４列は、診断する問題に制約を付すためにクライアントに提出できる質問の数を表す。第５列及び第６列は、この問題を診断するためのＢＢＮ構造のジャンクションツリー（junction tree: ＪＴ）サイズ及びクリーク（clique）サイズを示す。当分野において周知のように、推論に適用されるベイジアンネットワークは、より効率の良い計算を行うためにジャンクションツリーと呼ばれる構造に変換される。ジャンクションツリーは、クリークがベイジアンネットワークからの全て接続されている変数のセットであるクリークの木である。従って、本明細書において、クリークサイズはクリークの変数の結合確率密度として格納されるクリークの記憶サイズのことを指し、言い換えると、クリーク内の全ての変数についての状態の数の積である。計算はこれらの構造を用いる。なぜなら、基礎となるベイジアンネットワークにはループが存在し得るが、ネットワークのジャンクションツリー表現には存在しないからである。最後の列（Ｄエンジンデータ構造サイズ）は、この特定の問題のＢＢＮを表現するためのＢＢＮ処理エンジンの特定の実施形態に用いられるデータ構造のサイズ（キロバイト）である。当業者は、ＢＢＮのデータ構造表現が構造に関連するメモリオーバヘッドの多少を有するという点で、各実施形態は異なることがあるということを認めるであろう。しかし、構造のサイズの支配的要因は、ＢＢＮのパラメータと属性、すなわち、原因と行動と質問の数に残る。
【００２５】
図３のテーブルの特定のデータは、通常のレーザプリンタの動作において解決すべき典型的問題の選択を表している。例えば、解決すべき紙詰まり問題は、テーブルの第５行の「13_2pjam」と名付けられた関連するＢＢＮを有する。この特定の例示ＢＢＮは、解決する問題の定義をさらに洗練するために、１７の原因、１９の行動、及び２つの質問を有する。これらのパラメータ/属性から、ＢＢＮは、２９キロバイトのジャンクションテーブルサイズと、８２６浮動少数点数（すなわち、８２６×典型的な３２ビットプロセッサの浮動小数点数あたりの４バイトで約３３０４バイト）のクリークサイズとを有する。特定の実施に関する全てのオーバーヘッド情報を含む、この例示ＢＢＮを表す合計データ構造は、２４８キロバイトである。図３のテーブル内の全てのエントリは、特定の問題を解決するための実際のＢＢＮの実施であるが、このようなエントリの典型として例示しているに過ぎない。当業者は、図３のテーブル内の特定のデータは、本発明の範囲をこれらの特定の構造や特定の問題に限定するものではないことを理解するであろう。
【００２６】
図３のデータから、ＢＢＮのサイズは（最後の列でデータ構造サイズによって測定されるように）多項式の複雑性またはこれ以下を有するものとして計算によって推定することができる。図４は、図３のデータのグラフであり、ＢＢＮモデルのサイズを原因の数（Ｎ_Ｃ）とステップの数（Ｎ_Ｓ）の積（Ｎ_Ｃ×Ｎ_Ｓ）の関数として示している。ステップの数は、アクションの数（Ｎ_Ａ）と質問の数の和である（Ｎ_Ｓ＝Ｎ_Ａ＋Ｎ_Ｑ）。データポイントのグラフは、モデルの複雑性（モデルのサイズで測定される）が多項式より少ないことを示している。図５は、図３のデータの別のグラフであり、ＢＢＮモデルの複雑性が多項式より小さいことをさらに確認している。具体的には、図５は同一データポイントの対数グラフである。
【００２７】
特に、図３、４、５のデータとグラフは、ＢＢＮモデルの複雑性が以下の式で計算できることを示している。
【００２８】
ｙ＝２×ｘ0.8
ここで、ｙはＢＢＮモデルのサイズであり、ｘは（Ｎ_Ｃ×Ｎ_Ｓ）である。
【００２９】
図６は、図３のデータのグラフであり、（Ｎ_Ｃ×Ｎ_Ｓ）の関数と同じクリークサイズで測定されたＢＢＮモデルの複雑性を示している。このグラフは、モデルの複雑性が多項式の複雑性以上ではない（すなわち、Ｏ(Ｎ_Ｃ×Ｎ_Ｓ)）ことを確認している。
【００３０】
同様のデータ分析は、時間で測定されたＢＢＮモデルの複雑性を決定するのに適用できる。例えば、モデルの複雑性は、問題解決における最良の最初のステップを発見するのに必要な時間で測定することができる。ＢＢＮモデルの時間の複雑性の別の測定は、開始時間である。本明細書において、ＢＢＮモデルの開始時間とは、モデルが最初のステップを計算する準備ができるようにベイジアンネットワークが初期化するのに要する時間を意味する。この開始時間は、ベイジアンネットワーク定義のローディング、実施の関連データ構造の初期化、及び全ての変数について正しい確率を得るための最初の信念伝搬（belief propagation）の１つを実行することを含む。
【００３１】
図７は、図３に示すＢＢＮモデルの同一セットの時間ベースの測定を示すデータのテーブルである。図７のテーブルの最初の４列は、図３と同一であり、モデルの名前（問題の名前）、原因の数、行動の数、及び質問の数である。第５列は、対応する問題を解決するときに最良の最初のステップを見つけるための時間（秒）を示す。第６列は、予め計算された確率を持つモデルに対する「開始時間」を示し、第７列は、予め計算された確率を持たないモデルの「開始時間」である。参照された確率は、ＢＢＮのスタートアップ計算の間に必要な確率であり、後続するステップの迅速な処理を確実にする。一旦ＢＢＮが定義されると、これらの確率は予め計算され、ＢＢＮデータ構造の属性として格納（編集）されることができる。このように事前に計算した確率をＢＢＮデータ構造に編集することで、ＢＢＮモデルの開始段階を処理する時間は、図７のテーブルに示すように劇的に削減される。この削減された時間は、ＢＢＮ計算サービスを要求するクライアントプロセスによってより高速な応答と認識される。
【００３２】
図７のテーブル及び図８から図１０の関連するグラフは、計算時間で測定されたＢＢＮモデルの複雑性が、複数のＢＢＮ計算の負荷を複数のサーバに渡って管理し分配する目的のために決定できることを実証している。実際、予め編集された確率を持つ開始時間（図７のテーブルの第６列）の決定は、図１０のグラフで示すように、多項式の複雑性かそれ以下で計算できる。図８及び図９のグラフもまた、図７の第５列及び第７列の測定が多項式の複雑性かそれ以下で計算できることを示している。
【００３３】
このような時間の測定は、複数のＢＢＮ計算の負荷の分配の管理においても有用である。例えば、トラブルシューティングのユーザの要求に応答するための最大時間が５秒であり、単一のＢＢＮモデル計算が特定のサーバシステムにおいて１秒かかると推定されるとしきい値パラメータが提案したならば、５だけの並列計算をその特定のサーバシステムに割り当てるべきである。このような負荷管理計算は、上述の記憶領域サイズ関連の負荷管理構造及び方法と共に、あるいは別の負荷管理関数として、使用することができる。
【００３４】
当業者は、図７〜図１０のデータにおいて、重要な変数が考慮されていないことに気づくであろう。すなわち、負荷管理のための推定計算についてと同様、ＢＢＮ計算について、特定のシステムの速度が使用されている。この意味で、図７〜図１０のデータは、システム性能の特定の例示的基準に正規化されていると考えることができる。測定の関係は、対象となる特定のシステムのシステム性能で線形に計算できるであろう。
【００３５】
クロック周波数５００ｍＨｚのインテル・ペンティアム（登録商標）IIプロセッサにこのような方法で正規化すると、ＢＢＮモデル（図７のテーブル及び図８のグラフに示す）における最良の最初のステップを決定するための時間は、以下の式のように推定できる。
【００３６】
Ｔ＝0.000036ｘ＋0.046
ここで、Ｔは時間(秒)であり、ｘ＝Ｎ_Ｑ×Ｎ_Ａ２である。
【００３７】
予め計算した確率を持つＢＢＮモデルの計算を開始する時間（図７のテーブル及び図１０のグラフに示す）は、以下の式のように推定できる。
【００３８】
Ｔ＝0.000027ｘ＋0.016
ここで、Ｔは時間(秒)であり、ｘ＝Ｎ_Ｃ×Ｎ_Ａである。
【００３９】
最後に、予め計算した確率を持たないＢＢＮモデルの計算を開始する時間（図７のテーブル及び図９のグラフに示す）は、以下の式のように推定できる。
【００４０】
Ｔ＝0.0000084ｘ＋0.19
ここで、Ｔは時間(秒)であり、ｘ＝Ｎ_Ａ×Ｎ_Ｃ２である。
【００４１】
図１２は、図１１のステップ1112に係る処理の詳細を示すフローチャートであり、特定のＢＢＮモデルの負荷を推定している。ステップ1200で、まず処理するべきＢＢＮモデルの量的な属性を決定する。診断する問題のＢＢＮモデルにおける量的な属性の例は、Ｎ_Ｃ（原因の数）、Ｎ_Ａ（行動の数）、Ｎ_Ｑ（質問の数）、及びＮ_Ｓ（上述したステップの数）である。好ましい実施形態では、このような属性は予め決定され、特定のＢＢＮ問題モデルに関連した構造に格納される。データベースまたは他のインデックス付けされたファイル構造は、ＢＢＮモデルの数が大きい場合に使用することができ、より簡単な記憶構造は、ＢＢＮモデルの数が小さい場合に使用することができる。従って、このような量的な属性を決定するステップは、計算するべき指定されたＢＢＮモデルと関連付けて格納されるこのような属性を探すための構造化ファイルの探索ステップを含むことが好ましい。
【００４２】
ステップ1202では、ステップ1200で決定された量的属性に基づいて、指定されたＢＢＮモデルを計算するための推定記憶領域負荷を計算する。好ましくは、記憶領域負荷は、推定記憶領域として ｙ＝２×(Ｎ_Ｃ×Ｎ_Ｓ)0.8（キロバイト）で計算される。本明細書において、ＢＢＮモデルの記憶領域負荷を推定するのに他の等価な計算（例えば、記憶領域負荷の推定としてのクリークサイズの計算を含む）を使用することができる。
【００４３】
最後に、ステップ1204で、指定されたＢＢＮモデルの計算のためのＣＰＵ負荷の推定を計算する。ＣＰＵ負荷は、上述の多項式の何れかまたはこのような推定の組み合わせを用いて計算され、利用可能な計算リソースを選択したＢＢＮモデルに最適に割り当てる。しかし、推定ＣＰＵ負荷は正規化された値として使用するのが好ましく、ＢＢＮモデルを処理することができる特定の計算サーバの性能にその値を拡張することによって適用する。
【００４４】
以上、本発明を詳細に説明してきたが、これらは例示に過ぎず、特定の実施形態に本発明を限定するものではない。
【００４５】
本発明には以下の実施形態が含まれる。
【００４６】
（１）問題を診断するためのＢＢＮモデルの計算リソース要件を推定する方法であって、
前記ＢＢＮモデルの複雑性の少なくとも１つの量的属性を決定するステップ(1112)と、
多項式の複雑性に従って、前記少なくとも１つの量的属性の関数として前記計算リソース要件を推定するステップ(1112)と、
を含むことを特徴とする方法。
【００４７】
（２）前記決定ステップは、
前記ＢＢＮモデルにおける原因の数（Ｎ_Ｃ）を決定するステップ(1200)と、
前記ＢＢＮモデルにおけるステップの数（Ｎ_Ｓ）を決定するステップ(1200)と、
を含む、上記（１）に記載の方法。
【００４８】
（３）前記Ｎ_Ｓを決定するステップは、Ｎ_ＡをＢＢＮにおいて取り得る行動の数、Ｎ_ＱをＢＢＮにおける質問の数としたとき、Ｎ_Ｓを（Ｎ_Ａ＋Ｎ_Ｑ）として決定するステップからなる、上記（２）に記載の方法。
【００４９】
（４）前記推定ステップは、前記計算リソース要件をＮ_ＣとＮ_Ｓの多項式関数として計算するステップを含む、上記（３）に記載の方法。
【００５０】
（５）前記計算ステップは、推定された記憶空間における前記計算リソース要件（ｙ）をｙ＝２×(Ｎ_Ｃ×Ｎ_Ｓ)0.8として計算するステップを含む、上記（４）に記載の方法。
【００５１】
（６）問題を診断するためのＢＢＮモデルの計算リソース要件を推定するシステム(106)であって、
前記ＢＢＮモデル(106、108、130)の複雑性の少なくとも１つの量的属性を決定する手段と、
多項式の複雑性(106、108)に従って、前記少なくとも１つの量的属性の関数として前記計算リソース要件を推定する手段と、
を含むことを特徴とするシステム。
【００５２】
（７）前記決定手段は、
前記ＢＢＮモデル(106、108、130)における原因の数（Ｎ_Ｃ）を決定する手段と、
前記ＢＢＮモデル(106、108、130)におけるステップの数（Ｎ_Ｓ）を決定する手段と、
を含む、上記（６）に記載の方法。
【００５３】
（８）前記Ｎ_Ｓを決定する手段は、Ｎ_ＡをＢＢＮ(106、108、130)において取り得る行動の数、Ｎ_ＱをＢＢＮにおける質問の数としたとき、Ｎ_Ｓを（Ｎ_Ａ＋Ｎ_Ｑ）として決定する手段からなる、上記（７）に記載の方法。
【００５４】
（９）前記推定手段は、前記計算リソース要件をＮ_ＣとＮ_Ｓの多項式関数として計算する手段を含む、上記（８）に記載の方法。
【００５５】
（１０）前記計算手段は、推定された記憶空間における前記計算リソース要件（ｙ）をｙ＝２×(Ｎ_Ｃ×Ｎ_Ｓ)0.8として計算することを含む、上記（９）に記載の方法。
【００５６】
【発明の効果】
本発明によれば、ＢＢＮ計算リソースを推定することで、計算リソースを効率的に管理し、ＢＢＮサーバリソースをより適切に展開して複数のクライアントにサービスすることができる。
【図面の簡単な説明】
【図１】複数のＢＢＮ要求を処理するための計算リソース負荷を推定するＢＢＮ管理サーバを含む本発明のシステムのブロック図である。
【図２】図１のＢＢＮ管理サーバの負荷推定要素の動作の詳細を説明するフローチャートである。
【図３】例示的な多数のベイズネットワークの複数のパラメータと、記憶領域のサイズ要件の観点による各ネットワークの推定複雑性についての実験データを表すテーブルである。
【図４】ＢＢＮ記憶領域サイズ要件を推定する、多項式による複雑性を表す、図３のテーブルのデータのグラフである。
【図５】ＢＢＮ記憶領域サイズ要件を推定する、多項式による複雑性を表す、図３のテーブルのデータのグラフである。
【図６】ＢＢＮ記憶領域サイズ要件を推定する、多項式による複雑性を表す図３のテーブルのデータのグラフである。
【図７】図３の例示的なベイズネットワークの複数のパラメータと、計算時間の要件の観点による各ネットワークの推定複雑性を示す実験データを表すテーブルである。
【図８】図７のテーブルのデータのグラフである。
【図９】図７のテーブルのデータのグラフである。
【図１０】図７のテーブルのデータのグラフである。
【図１１】図１のＢＢＮ管理サーバの動作の全体を説明するフローチャートである。
【図１２】特定のＢＢＮモデルを計算するための負荷を推定するステップの詳細を説明するフローチャートである。
【符号の説明】
102        クライアント
104        ネットワーク
106        ＢＢＮ管理サーバ
108        負荷推定器
110        負荷分配器
112、114、116        ＢＢＮサーバ
118、120、122        ＢＢＮ
130        ＢＢＮデータベース
【図１】
0004059682.tif 000002
【図２】
0004059682.tif 000003
【図３】
0004059682.tif 000004
【図４】
0004059682.tif 000005
【図５】
0004059682.tif 000006
【図６】
0004059682.tif 000007
【図７】
0004059682.tif 000008
【図８】
0004059682.tif 000009
【図９】
0004059682.tif 000010
【図１０】
0004059682.tif 000011
【図１１】
0004059682.tif 000012
【図１２】
0004059682.tif 000013