(57)【要約】【課題】ベイジアンネットワークを別のベイジアンネットワークへ変換する。【解決手段】ネットワーク蓄積部１００に蓄積されたベイジアンネットワークと、ノード管理部２００の残ノード管理部２２０及び値保持ノード管理部２４０において管理されている情報とに基づき、ネットワーク構造決定部３００が変換アルゴリズムを決定する。ネットワーク構造決定部３００において決定された変換アルゴリズムに従い、条件付き確率表計算部４００がネットワーク蓄積部１００に蓄積されたベイジアンネットワークを変換処理し変換後ベイジアンネットワークを生成する。【効果】変換前ベイジアンネットワークと、任意に指定された、残すべきノード識別子情報とに基づき、変換後のベイジアンネットワーク構造を決定し、新たな条件付き確率表を求めることで、残すべきノードのみから構成される変換後ベイジアンネットワークを生成できる。【選択図】      図１
2007066260.tif 000002
【特許請求の範囲】
【請求項１】
複数ノードの情報間のリンクが因果関係の方向に向きを持ち、このリンクをたどったパスが循環しない、非循環有向グラフで表される確率ネットワークモデルであるベイジアンネットワークを変換するネットワーク変換方法であって、
変換対象となる変換前ベイジアンネットワークを蓄積するネットワーク蓄積ステップと、
前記変換前ベイジアンネットワークを構成するノードのうち、変換処理後に残される残ノードを示す残ノード情報、並びに、既に変換前に値を有しているノードを示す値保持ノード情報及びその値を管理するノード管理ステップと、
前記ネットワーク蓄積ステップにおいて蓄積された前記ベイジアンネットワークと、前記ノード管理ステップにおいて管理された情報とに基づいて、変換アルゴリズムを決定するネットワーク構造決定ステップと、
前記ネットワーク構造決定ステップにおいて決定された前記変換アルゴリズムに従って、前記ネットワーク蓄積ステップにおいて蓄積された前記ベイジアンネットワークを変換処理し変換後ベイジアンネットワークを生成する変換処理ステップとを含むことを特徴とするネットワーク変換方法。
【請求項２】
前記ネットワーク蓄積ステップにおいては、
前記変換前ベイジアンネットワークを構成する、一意に識別可能な情報が付与された構成ノードと、各ノード間のリンク情報と、各ノード間の条件付き確率表とを管理することを特徴とする請求項１記載のネットワーク変換方法。
【請求項３】
前記ノード管理ステップにおいて管理される残ノード情報は、前記変換前ベイジアンネットワークを構成する構成ノードに付与された情報と一致した情報を有することを特徴とする請求項１記載のネットワーク変換方法。
【請求項４】
前記ネットワーク構造決定ステップにおいては、
前記ネットワーク蓄積ステップにおいて蓄積された変換前ベイジアンネットワークを用いて、前記ノード管理ステップにおいて管理された残ノード情報に対応する残ノードの内、ある特定の対象残ノードに因果関係の影響を有するノード群を影響ノード群として抽出することを特徴とする請求項１記載のネットワーク変換方法。
【請求項５】
前記ネットワーク構造決定ステップにおいては、
前記影響ノード群の抽出にあたり、残ノードへ入力される全リンクパスについて、所定基準の下で条件付き独立が成り立つ分離ノードを求め、その分離ノードを群の境界ノードとし、その分離ノードから前記対象残ノードまでの間のすべてのノードで構成される影響ノード群を抽出することを特徴とする請求項１記載のネットワーク変換方法。
【請求項６】
前記変換処理ステップにおいては、
前記残ノード情報と、前記影響ノード群に含まれる残ノードの残ノード情報と、前記値保持ノード情報とに基づいて、前記残ノードに対する条件付き確率表を確率推論計算により導出することを特徴とする請求項１記載のネットワーク変換方法。
【請求項７】
複数ノードの情報間のリンクが因果関係の方向に向きを持ち、このリンクをたどったパスが循環しない、非循環有向グラフで表される確率ネットワークモデルであるベイジアンネットワークを変換するネットワーク変換システムであって、
変換対象となる変換前ベイジアンネットワークを蓄積するネットワーク蓄積手段と、
前記変換前ベイジアンネットワークを構成するノードのうち、変換処理後に残される残ノードを示す残ノード情報、並びに、既に変換前に値を有しているノードを示す値保持ノード情報及びその値を管理するノード管理手段と、
前記ネットワーク蓄積手段に蓄積されている前記ベイジアンネットワークと、前記ノード管理手段において管理されている情報とに基づいて、変換アルゴリズムを決定するネットワーク構造決定手段と、
前記ネットワーク構造決定手段において決定された前記変換アルゴリズムに従って、前記ネットワーク蓄積手段に蓄積されている前記ベイジアンネットワークを変換処理し変換後ベイジアンネットワークを生成する変換処理手段とを含むことを特徴とするネットワーク変換システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はネットワーク変換システム、ネットワーク変換方法に関し、特に、ベイジアンネットワークを構成するノードの内、任意に指定されたノードから構成されるベイジアンネットワークへ変換するネットワーク変換システム、ネットワーク変換方法に関する。
【背景技術】
【０００２】
不確実性を伴う意思決定やモデル表現を行うことに適したベイジアンネットワークにおいては、ネットワークを構成するノード情報の観測情報からネットワークを学習・構築する技術（例えば、特許文献１）や、構築されたネットワークを用いた推論技術の研究が行われている。さらに、ベイジアンネットワークを用いた意思決定方式を用いて最適な情報を提供するシステムの研究が行われている（例えば、特許文献２）。
【特許文献１】特開２００５−１０７７４７号公報
【特許文献２】特開２００５−８４７５２号公報
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかし、上記ベイジアンネットワークの利用の仕方では、ネットワークの学習処理や、構築されたネットワークにより推論処理によるシステム利用が主な利用方法であり、ネットワークそのものを何らかの理由により変換する技術については検討されていない。
ところで、ある広範囲の目的のために構築されたベイジアンネットワークを他の限定された目的で利用することや、ネットワークに情報を入力しながら、そのネットワークを他の装置や端末に送信するような目的で利用することも想定される。例えば、商品情報や販売時間・場所、顧客情報から構成される商品推奨サービス用ベイジアンネットワークについては、顧客情報を入手できない環境において同様のサービスを利用する場合、その顧客情報を省いたコンパクトなベイジアンネットワークを利用することが想定される。この場合、元のベイジアンネットワークの変換処理によりコンパクトなベイジアンネットワークを生成でき、以後、これを用いることができる。従って、このような変換処理方式が重要である。
【０００４】
本発明は上述した従来技術の問題点を解決するためになされたものであり、その目的は、変換対象であるベイジアンネットワークを構成するノードの内、任意に指定されたノードから構成されるベイジアンネットワークへ変換するネットワーク変換システム、ネットワーク変換方法を提供することである。
【課題を解決するための手段】
【０００５】
本発明の請求項１によるネットワーク変換方法は、
複数ノードの情報間のリンクが因果関係の方向に向きを持ち、このリンクをたどったパスが循環しない、非循環有向グラフで表される確率ネットワークモデルであるベイジアンネットワークを変換するネットワーク変換方法であって、
変換対象となる変換前ベイジアンネットワークを蓄積するネットワーク蓄積ステップと、
前記変換前ベイジアンネットワークを構成するノードのうち、変換処理後に残される残ノードを示す残ノード情報、並びに、既に変換前に値を有しているノードを示す値保持ノード情報及びその値を管理するノード管理ステップと、
前記ネットワーク蓄積ステップにおいて蓄積された前記ベイジアンネットワークと、前記ノード管理ステップにおいて管理された情報とに基づいて、変換アルゴリズムを決定するネットワーク構造決定ステップと、
前記ネットワーク構造決定ステップにおいて決定された前記変換アルゴリズムに従って、前記ネットワーク蓄積ステップにおいて蓄積された前記ベイジアンネットワークを変換処理し変換後ベイジアンネットワークを生成する変換処理ステップとを含むことを特徴とする。このようにすれば、変換前ベイジアンネットワークと、任意に指定された、残すべきノード識別子情報に基づいて、変換後のベイジアンネットワーク構造を決定し、新たな条件付き確率表を求めることで、残すべきノードのみから構成される変換後ベイジアンネットワークを生成することができる。なお、ベイジアンネットワークは、複数ノードの情報間のリンクが因果関係の方向に向きを持ち、このリンクをたどったパスが循環しない、非循環有向グラフで表される確率ネットワークモデルである。
【０００６】
本発明の請求項２によるネットワーク変換方法は、請求項１において、前記ネットワーク蓄積ステップにおいては、
前記変換前ベイジアンネットワークを構成する、一意に識別可能な情報が付与された構成ノードと、各ノード間のリンク情報と、各ノード間の条件付き確率表と(CPT：Conditional Probability Tables)を管理することを特徴とする。これにより、変換対象のベイジアンネットワークの構造情報および条件付き確率表を保有し、変換後のベイジアンネットワークに残すべきノード情報を利用することで、変換後の構造を決定でき、また新たな条件付き確率表を計算するための確率情報を与えることができる。
【０００７】
本発明の請求項３によるネットワーク変換方法は、請求項１において、前記ノード管理ステップにおいて管理される残ノード情報は、前記変換前ベイジアンネットワークを構成する構成ノードに付与された情報と一致した情報を有することを特徴とする。これにより、変換後ベイジアンネットワークに残すべきノード情報と、変換前に既に値を有するノード情報およびその値を管理でき、変換対象のベイジアンネットワークの構造情報を利用することで、変換前の変換後の構造を決定することができる。
【０００８】
本発明の請求項４によるネットワーク変換方法は、請求項１において、前記ネットワーク構造決定ステップにおいては、
前記ネットワーク蓄積ステップにおいて蓄積された変換前ベイジアンネットワークを用いて、前記ノード管理ステップにおいて管理された残ノード情報に対応する残ノードの内、ある特定の対象残ノードに因果関係の影響を有するノード群を影響ノード群として抽出することを特徴とする。これにより、変換後ベイジアンネットワーク内の残ノード間の因果関係を決定することでネットワーク全体の構造を決定することができるとともに、新たな条件付き確率表を計算するための条件付き確率表計算用情報ノード情報を決定することができる。
【０００９】
本発明の請求項５によるネットワーク変換方法は、請求項１において、前記ネットワーク構造決定ステップにおいては、
前記影響ノード群の抽出にあたり、残ノードへ入力される全リンクパスについて、所定基準の下で条件付き独立が成り立つ分離ノードを求め、その分離ノードを群の境界ノードとし、その分離ノードから前記対象残ノードまでの間のすべてのノードで構成される影響ノード群を抽出することを特徴とする。“Ｄ−分離判断基準”の下で“条件付き独立”が成り立つ分離ノードを求めることにより、変換後ベイジアンネットワーク内の残ノード間の無駄なノード関係を削除でき、また新たな条件付き確率表を計算する際においても必要なノードのみ考慮に入れて計算することで計算コストを削減できる。さらに値保持ノードを考慮することで、さらに不要なリンクや、残すノードの内、実際には不必要なノードを排除でき、さらなる構造の簡略化や計算コストの削減を実現できる。
【００１０】
本発明の請求項６によるネットワーク変換方法は、請求項１において、前記変換処理ステップにおいては、
前記残ノード情報と、前記影響ノード群に含まれる残ノードの残ノード情報と、前記値保持ノード情報とに基づいて、前記残ノードに対する条件付き確率表を確率推論計算により導出することを特徴とする。これにより、変換後ベイジアンネットワークを構成する残ノード間の新たな条件付き確率表を、従来の推論エンジンを用いて効率的に計算することができる。
【００１１】
本発明の請求項７によるネットワーク変換システムは、複数ノードの情報間のリンクが因果関係の方向に向きを持ち、このリンクをたどったパスが循環しない、非循環有向グラフで表される確率ネットワークモデルであるベイジアンネットワークを変換するネットワーク変換システムであって、
変換対象となる変換前ベイジアンネットワークを蓄積するネットワーク蓄積手段と、
前記変換前ベイジアンネットワークを構成するノードのうち、変換処理後に残される残ノードを示す残ノード情報、並びに、既に変換前に値を有しているノードを示す値保持ノード情報及びその値を管理するノード管理手段と、
前記ネットワーク蓄積手段に蓄積されている前記ベイジアンネットワークと、前記ノード管理手段において管理されている情報とに基づいて、変換アルゴリズムを決定するネットワーク構造決定手段と、
前記ネットワーク構造決定手段において決定された前記変換アルゴリズムに従って、前記ネットワーク蓄積手段に蓄積されている前記ベイジアンネットワークを変換処理し変換後ベイジアンネットワークを生成する変換処理手段とを含むことを特徴とする。このようにすれば、変換前ベイジアンネットワークと、任意に指定された、残すべきノード識別子情報に基づいて、変換後のベイジアンネットワーク構造を決定し、新たな条件付き確率表を求めることで、残すべきノードのみから構成される変換後ベイジアンネットワークを生成することができる。
【発明の効果】
【００１２】
本発明によれば、変換後のベイジアンネットワークに含まれる残ノード間の関係の内、条件付き依存関係にあるノード間のみのリンクから構成される構造へと変換し、それらの依存関係を記載する条件付き確率表を従来の推論方式を利用して導出することで、新たなベイジアンネットワークへと変換できるという効果がある。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施の形態を、図面を参照して説明する。なお、以下の説明において参照する各図では、他の図と同等部分は同一符号によって示されており、繰り返しの説明は省略する。
（実施の形態の説明）
まず、本実施形態にかかるネットワーク変換システムの構成例について説明する。図１は、本実施形態にかかるネットワーク変換システムの構成例を示すブロック図である。
同図において、本実施形態にかかるネットワーク変換システム１０は、変換前ベイジアンネットワークを保有するネットワーク蓄積部１００と、変換後ベイジアンネットワークに残るノードの識別子を管理するノード管理部２００と、変換後ベイジアンネットワークの構造を決定するネットワーク構造決定部３００と、変換後ベイジアンネットワークの新たな条件付き確率表を計算する条件付き確率表計算部４００とを含んで構成されている。これらの各構成要素は、同一の装置内に備えられていても良いし、全部又は一部が別の装置内に備えられていても良い。以下、各構成要素について詳細に説明する。
【００１４】
（ネットワーク蓄積部１００）
ネットワーク蓄積部１００は、変換前ベイジアンネットワークを構成する、一意に識別可能な識別子が付与された構成ノードの識別子と、各ノード間のリンク情報と、各ノード間の条件付き確率表（ＣＰＴ：Ｃｏｎｄｉｔｉｏｎａｌ  Ｐｒｏｂａｂｉｌｉｔｙ  Ｔａｂｌｅ）とを管理し、これらをネットワーク構造決定部３００へ出力する。
ここで、変換前ベイジアンネットワークの例が図２に示されている。同図に示されている変換前ベイジアンネットワークは、ノードＡからノードＫまでの１１個のノードによって構成されている。
【００１５】
また、図３には、図２中のノードＧに対する条件付き確率表の例が示されている。図３の確率表では、ノードＣ，Ｄ，Ｇの全てが２値（“Ｔｒｕｅ”、“Ｆａｌｓｅ”）の離散値を示す場合を示している。例えば、ノードＣが“Ｔｒｕｅ”、ノードＤが“Ｆａｌｓｅ”を示す場合、ノードＧが“Ｔｒｕｅ”を示すのは「０．６」の確率であることを示している。
このように、図２に示されている変換前ベイジアンネットワークにおいて、親ノードを有する全てのノードが条件付き確率表を有しており、これとノード間のリンク構造情報により、ベイジアンネットワークが特徴付けられる。
【００１６】
（ノード管理部２００）
ノード管理部２００は、変換前ベイジアンネットワークを構成するノードのうち、変換処理後に残される残ノードの識別子と、既に変換前に値を有している値保持ノード識別子とその値を管理し、ネットワーク構造決定部３００へ出力する。
このノード管理部２００は、残ノード識別子を管理する残ノード管理部２２０と、値保持ノード識別子を管理する値保持ノード管理部２４０とから構成されている。
（残ノード管理部２２０）
残ノード管理部２２０は、変換後ベイジアンネットワークで残るべきノード情報の識別子である残ノード識別子を管理する。これらの情報は、ネットワーク構造決定部３００内の影響ノード群抽出部３２０へ出力される。
【００１７】
（値保持ノード管理部２４０）
一方、値保持ノード管理部２４０は、変換前にノードの示す値情報を既に保持しているノードの識別子とその値情報とを対で管理する。
図４は、残ノード識別子情報、値保持ノード識別子およびその値についての例を示す図である。同図の例では、残ノードのノード識別子は、ノードＡ，Ｃ，Ｅ，Ｆ，Ｋである。また、値保持ノードのノード識別子は、ノードＤ、ノードＨであり、その値はノードＤについて“Ｔｒｕｅ”、ノードＨについて“Ｆａｌｓｅ”である。
これらの情報は、ネットワーク構造決定部３００内の影響ノード群抽出部３２０へ出力される。
【００１８】
（ネットワーク構造決定部３００）
図１に戻り、ネットワーク構造決定部３００は、ネットワーク蓄積部１００から変換前ベイジアンネットワークを入力し、ノード管理部２００から残ノード識別子と値保持ノード識別子とを入力する。そして、ネットワーク構造決定部３００は、変換後ベイジアンネットワークにおけるネットワーク構造を決定するとともに、変換後ベイジアンネットワークにおける条件付き確率表を計算するための条件付き確率表計算用情報ノード情報を生成する。
このネットワーク構造決定部３００は、残ノードに対して因果関係を有する、すなわち条件付き依存関係を有するノード群である影響ノード群を抽出する影響ノード群抽出部３２０と、影響ノード群から後述の条件付き確率表を計算するための親ノード、値保持ノードおよびその値を決定する計算用ノード決定部３４０とから構成されている。
【００１９】
（影響ノード群抽出部３２０）
影響ノード群抽出部３２０は、ネットワーク蓄積部１００から変換前ベイジアンネットワークを入力し、ノード管理部２００から残ノード識別子と値保持ノード識別子およびその値とを入力する。そして、影響ノード群抽出部３２０は、変換前ベイジアンネットワークを用いて、ノード管理ステップで管理された残ノード識別子に相当する残ノードに因果関係の影響を有するノード群を影響ノード群として抽出し、残ノードの親ノードとなるノード群を抽出することで、変換後ベイジアンネットワークのネットワーク構造を決定する。
影響ノード群抽出部３２０は、影響ノード群の境界ノードの決定に対しては“Ｄ−分離判断基準”を利用する。抽出された影響ノード群情報は、計算用ノード決定部３４０へと出力される。なお、“Ｄ−分離判断基準”による境界ノードの決定のアルゴリズムについての詳細は後述する。
【００２０】
（計算用ノード決定部３４０）
計算用ノード決定部３４０は、影響ノード群抽出部３２０から影響ノード群を入力し、後続する条件付き確率表計算部４００で実施される条件付き確率表の計算を行うための条件付き確率表計算用情報ノード情報を生成し、これを条件付き確率表計算部４００へ出力する。
計算用ノード決定部３４０は、影響ノード群の中から残ノードの親ノードとなるノード群を決定する。これらの情報は、条件付き確率表の各要素を計算するための親ノードとして利用されるが、条件付き確率表の計算にあたっては、変換前に値を有する値保持ノードの影響を考慮する必要があり、計算に必要な値保持ノード群も決定する。計算用ノード決定部３４０は、これら親ノード群の識別子情報と値保持ノード群の識別子情報およびその値とを、計算対象となる残ノードの識別子情報とともに条件付き確率表計算用情報ノード情報として、条件付き確率表計算部４００へ出力する。
【００２１】
（条件付き確率表計算部４００）
条件付き確率表計算部４００は、ネットワーク構造決定部３００から条件付き確率表計算用情報ノード情報を入力し、これに基づいて条件付き確率表の各値を計算し、最終的に変換後ベイジアンネットワークを出力する。具体的には、条件付き確率表計算部４００は、条件付き確率表計算用情報ノード情報に含まれる親ノード識別子から、親ノードを事前条件とする計算対象ノードの確率値を計算する。条件付き確率表計算部４００は、最終的に、変換後ベイジアンネットワークを出力する。つまり、条件付き確率表計算部４００は、蓄積されたベイジアンネットワークを変換処理し、変換後ベイジアンネットワークを生成する変換処理機能を有している。
【００２２】
（動作説明）
図５は、本実施形態によるネットワーク変換システムの動作を示すシーケンス図である。同図を参照して、本ネットワーク変換システムの動作について説明する。
本実施形態にかかるネットワーク変換システムにおいて、ネットワークを変換するにあたっては、最初に、ネットワーク蓄積部１００が予め保持している変換前ベイジアンネットワークに関する情報が蓄積される（ステップＳ１０１）。この情報は出力され、ネットワーク構造決定部３００内の影響ノード群抽出部３２０へ入力される（ステップＳ１０２）。
【００２３】
一方、ノード管理部２００内の残ノード管理部２２０には残ノード識別子、値保持ノード管理部２４０には値保持ノード識別子およびその値がそれぞれ蓄積される（ステップＳ１０３、Ｓ１０５）。これらはそれぞれ出力され、ネットワーク構造決定部３００内の影響ノード群抽出部３２０へ入力される（ステップＳ１０４、Ｓ１０６）。
【００２４】
次に、ネットワーク構造決定部３００内の影響ノード群抽出部３２０は、変換後ベイジアンネットワークのネットワーク構造を決定する（ステップＳ１０７）。この場合、入力された変換前ベイジアンネットワーク、残ノード識別子と値保持ノード識別子およびその値を用いて、ノード管理ステップで管理された残ノード識別子に相当する残ノードに因果関係の影響を有するノード群を影響ノード群として抽出し、残ノードの親ノードとなるノード群を抽出することで、変換後ベイジアンネットワークのネットワーク構造を決定する。抽出された影響ノード群情報は出力され、計算用ノード決定部３４０へ入力される（ステップＳ１０８）。
【００２５】
次に、ネットワーク構造決定部３００内の計算用ノード決定部３４０は、入力した影響ノード群に基づき、後続する条件付き確率表計算部４００で実施される条件付き確率表の計算を行うための条件付き確率表計算用情報ノード情報を作成する（ステップＳ１０９）。この条件付き確率表計算用情報ノード情報は出力され、条件付き確率表計算部４００へ入力される（ステップＳ１１０）。
条件付き確率表計算部４００は、入力された条件付き確率表計算用情報ノード情報に基づいて条件付き確率表の各値を計算し、最終的に変換後ベイジアンネットワークを出力する（ステップＳ１１１）。
【００２６】
（アルゴリズム詳細説明）
次に、ネットワーク変換システム１０を構成する各部の処理アルゴリズムについて詳細に説明する。
（ベイジアンネットワーク）
ベイジアンネットワークは、複数の確率変数間の定性的な依存関係を有向非循環グラフ構造によって表現し、個々の変数間の定量的な関係を定量的に示す条件付き確率で表したモデルである。ネットワークは、確率変数を示すノード、並びに、確率変数間の条件付き依存関係、及び、その条件付き確率、３つによって提示される確率モデルである。特に、確率変数が離散変数の場合は、条件付確率は条件付き確率テーブルＣＰＴ(Conditional Probability Tables)により表現される。
【００２７】
ベイジアンネットワークは、モデル表現による可視化の容易性だけでなく、各問題領域に関する事前知識を用いて確率変数間の順序関係としてモデル構造に反映することが可能である。このように、各問題領域に適合したベイジアンネットワークを用いることで、一部の変数を観測した際のその他の変数の確率や、対象確率変数が最大となる状態を予測することが可能である点が、従来のグラフィカルモデリングとの大きな差異といえる。
【００２８】
なお、ベイジアンネットワークについては、Heckerman,D.による文献“A tutorial on learning with Bayesian networks”,[1995],Microsoft Research MSR-TR-95-06, Revised June 1996.に記載されている。
ベイジアンネットワークは、ネットワークを構成する「構成ノード情報」、ノード間の「条件付き確率テーブル」、「ネットワーク構造情報」、および親ノードを持たない「ルートノードの事前確率」により定義される。
【００２９】
（ネットワーク構造決定・条件付き確率表計算用情報ノード情報生成）
次に、影響ノード群抽出部３２０によるネットワーク構造決定と、計算用ノード決定部３４０による条件付き確率表計算用情報ノード情報の生成について説明する。
本実施例では、ネットワーク構造決定するための影響ノード群の抽出にあたり、対象残ノードへ入力される全リンクパスについて、“Ｄ−分離判断基準”の下で“条件付き独立”が成り立つ分離ノードを求め、分離ノードを群の境界ノードとし、分離ノードから対象残ノード間のすべてのノードで構成される影響ノード群を抽出する。
ここで“Ｄ−分離判断基準”とは、有向グラフネットワークと証拠ノードｅとが与えられる時、ノード集合ｘ中のあるノードからノード集合ｙ中のノードへの全ての無向経路がノードｅで遮断されているとき“Ｄ−分離”と言い、ノードｅの下でノード集合ｘとノード集合ｙは“条件付き独立”である、という基準である。
【００３０】
（Ｄ−分離）
ここで、“Ｄ−分離”について、図６を参照し、例をあげて説明する。同図において、ある経路がノード集合ｅによって遮断されている時は、以下の３つの場合が想定される。すなわち、
（ア）ノードｚがノード集合ｅに含まれ、経路上の１つのインリンクと１つのアウトリンクを持つ場合、
（イ）ノードｚがノード集合ｅに含まれ、経路上の２つのアウトリングを持つ場合、
（ウ）ノードｚおよびノードｚの子孫がノード集合ｅに含まれず、かつ、経路上の２つのインリンクがある場合、
が想定される。
【００３１】
以上の“Ｄ−分離判断基準”に基づくと、残ノード識別子および値保持ノード識別子がＤ−分離を与えるノードｚに相当する。そこで、これらの残ノードおよび値保持ノードを分離ノードとして影響ノード群の境界ノードとし、分離ノードから対象残ノード間のすべてのノードで構成される影響ノード群を抽出する。
ここで、図４に示されているネットワークの場合について、図７、図８を参照して説明する。図４において、対象残ノードＫについて考えると、対象残ノードＫへ入力する上流ノード群はノードＡからノードＪまでの１０個のノードとなる。すなわち、図７において、実線Ｊ１で囲まれた“上流ノード群”である。
【００３２】
次に、その上流ノード群を構成する各パスについて、そのパス上で残ノードもしくは値保持ノードがある場合には“Ｄ−分離判断基準”に基づき、それより対象残ノードＫから見て遠いノードについては、対象残ノードＫに影響が無いものとして、そのノードを分離ノードとし、それらの分離ノードを最も外側とする影響ノード群を求めることができる。例えば、ノードＫへ入力されるノードＫ→ノードＩ→ノードＨ→ノードＥのパス（パスα）については、ノードＨが値保持ノードのため、ノードＫに対する影響ノード群にはノードＥは含まれない。一方、ノードＫ→ノードＩ→ノードＦ→ノードＡのパス（パスβ）については、ノードＦが残ノードのためノードＫに対する影響ノード群にはノードＡは含まれない。以上より、影響ノード群として上流影響ノード群が得られる。他のパスについても同様である。図７において、破線Ｈ１で囲まれたノードが“影響ノード群”である。
【００３３】
以上を考慮して得られる変換後ベイジアンネットワークが、図８に示されている。同図を参照すると、図２においてネットワークを構成しているノードＡ〜ノードＫのうち、ノードＢ、ノードＤ、ノードＥ、ノードＧ〜ノードＪが消去され、ノードＡ、ノードＣ、ノードＦ、及び、ノードＫからなるネットワークが得られる。さらに、このように、ノードＥは残ノードであったが、結果的にはネットワークに影響を及ぼすノードではなかったため、変換後ベイジアンネットワークには含まれていないことが分かる。
【００３４】
以上より、ノードＫに対する条件付き確率表を構成する親ノードは、上流影響ノード群のうちノードＦ、ノードＣの２ノードとなり、それら親ノードとノードＫとの条件付き確率表を構成する各確率値は上流影響ノードに含まれる値保持ノードＨとノードＤとを用いて計算されることになる。以上を条件付き確率表計算用情報ノード情報として条件付き確率表計算部４００へ出力する。
【００３５】
図９には、図４に示されているネットワークの場合の、条件付き確率表計算用情報ノード情報の例が示されている。同図を参照すると、対象ノードＦについての親ノード識別子は“Ａ”、対象ノードＫについての親ノード識別子は“Ｃ”及び“Ｆ”である。そして、値保持ノード識別子とその値は、（Ｄ、Ｔｒｕｅ）、（Ｈ、Ｆａｌｓｅ）である。
【００３６】
（条件付き確率表計算部における計算方法）
次に、条件付き確率表計算部４００における計算方法について説明する。
この計算にあたっては、条件付き確率表計算用情報ノード情報に含まれる親ノード識別子から、親ノードを事前条件とする計算対象ノードの確率値を計算する。具体的には、計算対象ノードをＸt＝（ｘt0，…，ｘtk，…，ｘtKt-1）とする。ここで離散値の状態インデックスをｋ（０＜＝ｋ＜Ｋt）とする。一方、親ノード群をＸp＝（Ｘp,0，…，Ｘp,j，…，Ｘp,J-1）とし、親ノード数をｊ（０＜＝ｊ＜Ｊp）とする。各親ノードはＸp,jは同様にしてＸp,j＝（ｘp,j0，…，ｘp,jlj，…，ｘp,jLj-1）とする。ただし、離散値の状態インデックスをｌ（０＜＝ｌj＜Ｌj）とする。
【００３７】
ここで、Ｘp,jの全ての取りうる状態の組み合わせのインデックスをｍとすると、ｍの最大値はＬ0×…×Ｌj×…×Ｌpとなる。例えば、親ノード数Ｊpが３で、各親ノードの離散状態値Ｌjが２の場合、ｍ＝２×２×２＝８となる。以上より、各状態の組み合わせインデックスがｍとなる親ノードをＸpmとした場合の、状態ｋを有する計算対象ノードをＸt、即ちｘtkの確率値は以下のように計算できる。
【００３８】
【数１】
2007066260.tif 000003
【００３９】
ただし、ここでＸｖは、値保持ノード情報である。
次に、ネットワーク構造決定部３００及び条件付き確率表計算部４００の処理フローについて、図１０を参照して説明する。
同図において、変換前ベイジアンネットワークのうち、残ノードを見つけた場合（ステップＳ１４０）、これを対象ノードと当該対象ノードに対する影響ノード群の中身の要素を０にリセットする（ステップＳ１４１→Ｓ１４２）。ただし、残ノードを見つけられない場合には処理を終了する（ステップＳ１４１→Ｓ１５０）。
【００４０】
次に、対象ノードに入力されるパスを見つけた場合（ステップＳ１４３）、全てのパスについて、対象ノードからパス先端に対して残ノード又は値保持ノードを検索する（ステップＳ１４４）。ノードが見つかった場合（ステップＳ１４６）、それらが残ノードである場合には影響ノード群のＸpとして，値保持ノードである場合にはＸvとして影響ノードに追加登録し（ステップＳ１４７）、対象ノードに入力される別のパスを見つける処理へ戻る（ステップＳ１４７→Ｓ１４３）。ただし、それらのノードが見つからなかった場合には、そのパスは無視する（ステップＳ１４６→Ｓ１４８）。
【００４１】
対象ノードに入力されるパスを見つけられない場合（ステップＳ１４３）には、影響ノード群に登録ノードがあるかどうかを確かめ（ステップＳ１４５）、ある場合には、ＸpとＸvとを用いて、Ｘpの全ての組み合わせと対象ノードの全ての離散状態値に対して、確率計算する（ステップＳ１４９）。その後、残ノードを見つける処理に戻る（ステップＳ１４９→Ｓ１４０）。ただし、影響ノード群に登録ノードが無い場合には、残ノードを見つける処理に戻る（ステップＳ１４９→Ｓ１４０）。
【００４２】
（計算数値例）
本装置における計算数値例について、図１１〜図１４を参照して説明する。
図１１は、変換前のネットワークの構成例を示す図である。同図には、ノードＡからノードＩまでの９個のノードが示されている。同図において、ノードＤが値保持ノード、ノードＢ、ノードＣ、ノードＥ、ノードＨ、ノードＩが残ノードである。
図１２（ａ）は図１１中のノードＥについてのＣＰＴの例を示す図、図１２（ｂ）は図１１中のノードＦについてのＣＰＴの例を示す図、図１２（ｃ）は図１１中のノードＧについてのＣＰＴの例を示す図、図１２（ｄ）は図１１中のノードＨについてのＣＰＴの例を示す図、図１２（ｅ）は図１１中のノードＩについてのＣＰＴの例を示す図、である。
【００４３】
図１３は、変換後のネットワークの構成例を示す図である。同図には、ノードＢ、ノードＣ、ノードＥ、ノードＨ、及び、ノードＩの５個のノードが示されている。
図１４（ａ）は図１３中のノードＩについてのＣＰＴの例を示す図、図１４（ｂ）は図１３中のノードＨについてのＣＰＴの例を示す図、である。
これらの図においては、ノードＩが残ノードであり、ノードＣとノードＥが影響ノード群内の境界ノードに起因する親ノード、ノードＤが影響ノード群内の値保持ノードである。この例では、全てのノードが２つの離散状態値（Ｙｅｓ、Ｎｏ）を有しており、ノードＤは“Ｙｅｓ”の値を有している場合を示している。
このような条件において、図１４（ｃ）には、同図（ａ）においてノードＩが“Ｙｅｓ”となる場合で、ノードＣとノードＥがともに“Ｙｅｓ”の場合の計算結果が示されている。
【００４４】
（ネットワーク変換方法）
以上の動作を行うネットワーク変換システムにおいては、以下のようなネットワーク変換方法が実現されている。すなわち、複数ノードの情報間のリンクが因果関係の方向に向きを持ち、このリンクをたどったパスが循環しない、非循環有向グラフで表される確率ネットワークモデルであるベイジアンネットワークを変換するネットワーク変換方法であって、
変換対象となる変換前ベイジアンネットワークを蓄積するネットワーク蓄積ステップ（図５中のステップＳ１０１に対応）と、
上記変換前ベイジアンネットワークを構成するノードのうち、変換処理後に残される残ノードを示す残ノード情報、並びに、既に変換前に値を有しているノードを示す値保持ノード情報及びその値を管理するノード管理ステップ（図５中のステップＳ１０３、Ｓ１０５に対応）と、
上記ネットワーク蓄積ステップにおいて蓄積された上記ベイジアンネットワークと、上記ノード管理ステップにおいて管理された情報とに基づいて、変換アルゴリズムを決定するネットワーク構造決定ステップ（図５中のステップＳ１０７に対応）と、
上記ネットワーク構造決定ステップにおいて決定された上記変換アルゴリズムに従って、上記ネットワーク蓄積ステップにおいて蓄積された上記ベイジアンネットワークを変換処理し変換後ベイジアンネットワークを生成する変換処理ステップ（図５中のステップＳ１０９、Ｓ１１１に対応）とを含むネットワーク変換方法が実現されている。
【００４５】
このような方法によれば、変換前ベイジアンネットワークと、任意に指定された、残すべきノード識別子情報に基づいて、変換後のベイジアンネットワーク構造を決定し、新たな条件付き確率表を求めることで、残すべきノードのみから構成される変換後ベイジアンネットワークを生成することができる。
また、上記ネットワーク蓄積ステップにおいては、
上記変換前ベイジアンネットワークを構成する、一意に識別可能な情報が付与された構成ノードと、各ノード間のリンク情報と、各ノード間の条件付き確率表と(CPT：Conditional Probability Table)を管理する。これにより、変換対象のベイジアンネットワークの構造情報および条件付き確率表を保有し、変換後のベイジアンネットワークに残すべきノード情報を利用することで、変換後の構造を決定でき、また新たな条件付き確率表を計算するための確率情報を与えることができる。
【００４６】
さらに、上記ノード管理ステップにおいて管理される残ノード情報は、上記変換前ベイジアンネットワークを構成する構成ノードに付与された情報と一致した情報を有する。これにより、変換後ベイジアンネットワークに残すべきノード情報と、変換前に既に値を有するノード情報およびその値を管理でき、変換対象のベイジアンネットワークの構造情報を利用することで、変換前の変換後の構造を決定することができる。
【００４７】
そして、上記ネットワーク構造決定ステップにおいては、
上記ネットワーク蓄積ステップにおいて蓄積された変換前ベイジアンネットワークを用いて、上記ノード管理ステップにおいて管理された残ノード情報に対応する残ノードの内、ある特定の対象残ノードに因果関係の影響を有するノード群を影響ノード群として抽出する。これにより、変換後ベイジアンネットワーク内の残ノード間の因果関係を決定することでネットワーク全体の構造を決定することができるとともに、新たな条件付き確率表を計算するための条件付き確率表計算用情報ノード情報を決定することができる。
【００４８】
さらに、上記ネットワーク構造決定ステップにおいては、上記影響ノード群の抽出にあたり、残ノードへ入力される全リンクパスについて、所定基準の下で条件付き独立が成り立つ分離ノードを求め、その分離ノードを群の境界ノードとし、その分離ノードから上記対象残ノードまでの間のすべてのノードで構成される影響ノード群を抽出する。“Ｄ−分離判断基準”の下で“条件付き独立”が成り立つ分離ノードを求めることにより、変換後ベイジアンネットワーク内の残ノード間の無駄なノード関係を削除でき、また新たな条件付き確率表を計算する際においても必要なノードのみ考慮に入れて計算することで計算コストを削減できる。さらに値保持ノードを考慮することで、さらに不要なリンクや、残すノードの内、実際には不必要なノードを排除でき、さらなる構造の簡略化や計算コストの削減を実現できる。
【００４９】
なお、上記変換処理ステップにおいては、上記残ノード情報と、上記影響ノード群に含まれる残ノードの残ノード情報と、上記値保持ノード情報とに基づいて、上記残ノードに対する条件付き確率表を確率推論計算により導出する。これにより、変換後ベイジアンネットワークを構成する残ノード間の新たな条件付き確率表を、従来の推論エンジンを用いて効率的に計算することができる。
（変形例）
上述の実施例では、ノード管理部２００において残ノード識別子と値保持ノード識別子が管理されている場合について述べたが、値保持ノード識別子が指定されない場合もある。
【００５０】
（まとめ）
続いて、本実施形態にかかるネットワーク変換システムの作用および効果について説明する。本実施形態にかかるネットワーク変換システム１０においては、ノード管理部２００で管理される残ノード識別子と値保持ノード識別子に基づいて、ネットワーク蓄積部１００で管理される変換前ベイジアンネットワークを変換することができる。特に、変換に際しては、ネットワーク構造決定部３００で、変換後ベイジアンネットワークに含まれる予定の残ノードに基づいてネットワーク構造を決定し、その情報を基に条件付き確率表計算部４００では、従来の計算方法を用いて確率計算することで実現することができる。これにより、変換後のネットワーク構造は簡易な構造となり、必要な条件付き確率表のみ生成することで、コンパクトなネットワークへと変換することが可能となる。
【００５１】
このようなネットワーク変換技術は、広範囲な目的のために生成されたベイジアンネットワークから、各個別の目的で使用するための特化したベイジアンネットワークを生成することに利用可能である。これにより、様々な要因や情報を考慮した比較的大きなベイジアンネットワークを生成しておくことで、各個別の事例毎にベイジアンネットワークを生成することが不要となり、ベイジアンネットワークの構築、ベイジアンネットワークの更新等の、管理処理が簡易に行える。例えば、あるベイジアンネットワークが情報推奨サービスに利用される場合、ここの事例やサービス提供環境に基づいて個別のベイジアンネットワークへ変換して利用することにより、サービス提供のためのベイジアンネットワークの新たな構築に対する負荷が軽減され、サービスの増加につながる。
【００５２】
また、一方、このようなベイジアンネットワークを分散的に利用しながらサービス提供をする場合においても、各箇所で必要なベイジアンネットワークへと分離・変換することで、各箇所では最小のベイジアンネットワークのみを管理することで、管理コストを軽減できる。
さらに、情報推奨サービスがこのようなベイジアンネットワークにより記載されており、構成情報が、サービス提供者が所有する情報と、ユーザが所有する情報により構成されている場合、サービス提供者の情報をベイジアンネットワークに入力してネットワークを変換・送出し、ユーザ側でユーザ所有情報を入力することで、分散的なサービス実行が可能となる。この場合、ネットワークをサービス提供者側で変換することで、ネットワーク全体をユーザ側に提供することなく情報推奨サービスが実行できるため、サービスロジックをユーザに非公開にするといったプライバシー制御方式および装置・システムにも応用できる。
【００５３】
（請求項に関する追記）
請求項の記載に関し、本発明はさらに以下の態様をとりうる。
（１）前記ネットワーク蓄積手段は、
前記変換前ベイジアンネットワークを構成する、一意に識別可能な情報が付与された構成ノードと、各ノード間のリンク情報と、各ノード間の条件付き確率表とを管理することを特徴とするネットワーク変換システム。これにより、変換対象のベイジアンネットワークの構造情報および条件付き確率表（ＣＰＴ：Ｃｏｎｄｉｔｉｏｎａｌ  Ｐｒｏｂａｂｉｌｉｔｙ  Ｔａｂｌｅ）を保有し、変換後のベイジアンネットワークに残すべきノード情報を利用することで、変換後の構造を決定でき、また新たな条件付き確率表を計算するための確率情報を与えることができる。
【００５４】
（２）ノード管理手段が管理する残ノード情報は、前記変換前ベイジアンネットワークを構成する構成ノードに付与された情報と一致した情報を有することを特徴とするネットワーク変換システム。これにより、変換後ベイジアンネットワークに残すべきノードと、変換前に既に値を有するノード情報およびその値を管理でき、変換対象のベイジアンネットワークの構造情報を利用することで、変換前の変換後の構造を決定することができる。
【００５５】
（３）前記ネットワーク構造決定手段は、
前記ネットワーク蓄積手段に蓄積された変換前ベイジアンネットワークを用いて、前記ノード管理手段で管理された残ノード情報に対応する残ノードの内、ある特定の対象残ノードに因果関係の影響を有するノード群を影響ノード群として抽出することを特徴とするネットワーク変換システム。これにより、変換後ベイジアンネットワーク内の残ノード間の因果関係を決定することでネットワーク全体の構造を決定することができるとともに、新たな条件付き確率表を計算するための条件付き確率表計算用情報ノード情報を決定することができる。
【００５６】
（４）前記ネットワーク構造決定手段は、
前記影響ノード群の抽出にあたり、残ノードへ入力される全リンクパスについて、所定基準の下で条件付き独立が成り立つ分離ノードを求め、その分離ノードを群の境界ノードとし、その分離ノードから前記対象残ノードまでの間のすべてのノードで構成される影響ノード群を抽出することを特徴とするネットワーク変換システム。これにより、変換後ベイジアンネットワーク内の残ノード間の無駄なノード関係を削除でき、また新たな条件付き確率表を計算する際においても必要なノードのみ考慮に入れて計算することで計算コストを削減できる。さらに値保持ノードを考慮することで、さらに不要なリンクや、残すノードの内、実際には不必要なノードを排除でき、さらなる構造の簡略化や計算コストの削減を実現できる。
【００５７】
（５）前記変換処理手段は、
前記残ノード情報と、前記影響ノード群に含まれる残ノードの残ノード情報と、前記値保持ノード情報とに基づいて、前記残ノードに対する条件付き確率表を確率推論計算により導出することを特徴とするネットワーク変換システム。これにより、変換後ベイジアンネットワークを構成する残ノード間の新たな条件付き確率表を、従来の推論エンジンを用いて効率的に計算することができる。
【産業上の利用可能性】
【００５８】
本発明は、ベイジアンネットワークを変換する場合に利用することができる。
【図面の簡単な説明】
【００５９】
【図１】本発明の実施形態にかかるネットワーク変換システムの構成例を示す図である。
【図２】本発明の実施形態にかかる変換前ベイジアンネットワークの構成例を示す図である。
【図３】本発明の実施形態にかかる変換前ベイジアンネットワークの条件付き確率表である。
【図４】本発明の実施形態にかかるノード識別子の構成例を示す図である。
【図５】本実施形態によるネットワーク変換システムの動作を示すシーケンス図である。
【図６】本発明の実施形態にかかるＤ−分離概念を示す図である。
【図７】本発明の実施形態にかかる影響ノード群の構成図である。
【図８】本発明の実施形態にかかる条件付き確率表計算用情報ノード情報表である。
【図９】本発明の実施形態にかかる条件付き確率表計算例である。
【図１０】ネットワーク構造決定部及び条件付き確率表計算部の処理を示すフローチャートである。
【図１１】本発明の実施形態にかかるベイジアンネットワークの構成例を示す図である。
【図１２】（ａ）は図１１中のノードＥについてのＣＰＴの例を示す図、（ｂ）は図１１中のノードＦについてのＣＰＴの例を示す図、（ｃ）は図１１中のノードＧについてのＣＰＴの例を示す図、（ｄ）は図１１中のノードＨについてのＣＰＴの例を示す図、（ｅ）は図１１中のノードＩについてのＣＰＴの例を示す図、である。
【図１３】変換後のネットワークの構成例を示す図である。
【図１４】（ａ）は図１３中のノードＩについてのＣＰＴの例を示す図、（ｂ）は図１３中のノードＨについてのＣＰＴの例を示す図、（ｃ）は、同図（ａ）においてノードＩが“Ｙｅｓ”となる場合で、ノードＣとノードＥがともに“Ｙｅｓ”の場合の計算結果を示す図である。
【符号の説明】
【００６０】
１０  ネットワーク変換システム
１００  ネットワーク蓄積部
２００  ノード管理部
２２０  残ノード管理部
２４０  値保持ノード管理部
３００  ネットワーク構造決定部
３２０  影響ノード群抽出部
３４０  計算用ノード決定部
４００  確率表計算部
Ａ〜Ｋ  ノード
α、β  パス
【図１】
2007066260.tif 000004
【図２】
2007066260.tif 000005
【図３】
2007066260.tif 000006
【図４】
2007066260.tif 000007
【図５】
2007066260.tif 000008
【図６】
2007066260.tif 000009
【図７】
2007066260.tif 000010
【図８】
2007066260.tif 000011
【図９】
2007066260.tif 000012
【図１０】
2007066260.tif 000013
【図１１】
2007066260.tif 000014
【図１２】
2007066260.tif 000015
【図１３】
2007066260.tif 000016
【図１４】
2007066260.tif 000017