(57)【要約】【課題】ベイジアンネットワークのネットワーク構造を学習データに基づいて構築する。【解決手段】学習部は、ベイジアンネットワークのネットワーク構造を２次元遺伝子型で表現する。すなわち、ノード間のオーダーに従って行方向に配置した複数のノードを親ノードとすると共に、同じオーダーに従って列方向に配置した複数のノードを子ノードとし、各親ノードと各子ノードとが対応する各遺伝子座における対立遺伝子により、対応するノード間のコネクションの有無を規定する。そして、学習部は、２次元遺伝子型を有する多数の個体を初期個体群とし、この初期個体群から遺伝的アルゴリズムを用いて最適な個体を探索し、その個体の表現型を準最適なネットワーク構造とする。但し、ネットワーク構造の非循環を保証するため、対角成分以下の遺伝子は形質を発現しないものとする。【選択図】図３
2007310860.tif 000002
【特許請求の範囲】
【請求項１】
複数のノード間の因果関係を有向グラフで表したベイジアンネットワークのネットワーク構造を学習データに基づいて構築する学習装置であって、
上記学習データが格納される記憶手段と、
上記学習データに基づいて上記ネットワーク構造を構築する学習手段とを備え、
上記学習手段は、それぞれ上記複数のノード間の順序と因果関係とが規定された遺伝子型を有する個体により構成された初期個体群を準備し、遺伝的アルゴリズムに基づいて上記初期個体群に対して交叉処理及び／又は突然変異処理を繰り返し行うと共に、上記学習データに基づいて各個体の評価値を計算して最適な個体を探索し、該最適な個体の表現型を上記ネットワーク構造とする
ことを特徴とする学習装置。
【請求項２】
上記遺伝子型は、規定された順序に従って第１の方向に配置した上記複数のノードを親ノードとすると共に、上記規定された順序に従って上記第１の方向と直交する第２の方向に配置した上記複数のノードを子ノードとし、各親ノードと各子ノードとが対応する各遺伝子座における対立遺伝子により、対応するノード間の因果関係の有無を規定したものであることを特徴とする請求項１記載の学習装置。
【請求項３】
子ノードの順序が親ノードの順序と同じか親ノードの順序よりも高い遺伝子座における遺伝子は形質を発現しないことを特徴とする請求項２記載の学習装置。
【請求項４】
任意の子ノードについて因果関係を有する親ノードの数が所定数を超えている場合、上記学習手段は、該子ノードについて因果関係を有する親ノードの数が所定数以下となるように、該子ノードに関連する一以上の遺伝子座における遺伝子を対立遺伝子に反転させることを特徴とする請求項２記載の学習装置。
【請求項５】
上記初期個体群は、設計者の事前知識の一部又は全部を反映したものであることを特徴とする請求項１記載の学習装置。
【請求項６】
上記初期個体群は、学習の結果得られた個体に基づくものであることを特徴とする請求項１記載の学習装置。
【請求項７】
上記評価値は、BD Metricの対数であり、
ｎ個のノードのうちｉ番目のノードを子ノードＸｉとし、該子ノードＸｉがｖｉ０からｖｉｒｉ−１までのｒｉ個の値を取り得るものとし、該子ノードＸｉについて因果関係を有する全ての親ノードが取り得る値のパターンの数をｑｉ個としたとき、
該子ノードＸｉの値がｖｉｋとなり、該子ノードＸｉについて因果関係を有する全ての親ノードの値がｊ番目のパターンとなるデータが発生すると上記学習データの取得前に予想される回数Ｎ’ｉｊｋは、以下の式に従って計算される
ことを特徴とする請求項１記載の学習装置。
【数１】
2007310860.tif 000014
【請求項８】
上記評価値は、BD Metricの対数であり、
ｎ個のノードのうちｉ番目のノードを子ノードＸｉとし、該子ノードＸｉがｖｉ０からｖｉｒｉ−１までのｒｉ個の値を取り得るものとし、該子ノードＸｉについて因果関係を有する全ての親ノードが取り得る値のパターンの数をｑｉ個としたとき、
該子ノードＸｉの値がｖｉｋとなり、該子ノードＸｉについて因果関係を有する全ての親ノードの値がｊ番目のパターンとなるデータが発生すると上記学習データの取得前に予想される回数Ｎ’ｉｊｋは、Ｎ’ｉｊｋ＝０とされる
ことを特徴とする請求項１記載の学習装置。
【請求項９】
上記ベイジアンネットワークは、複数のノード間の動的因果関係を有向グラフで表したダイナミックベイジアンネットワークであり、初期個体群における複数のノード間の因果関係を有向グラフで表す初期ネットワークと、時刻ｔ−１の個体群から時刻ｔの個体群に対する複数のノード間の因果関係を有向グラフで表すと共に時刻ｔの個体群における複数のノード間の因果関係を有向グラフで表す遷移ネットワークとから構成されることを特徴とする請求項１記載の学習装置。
【請求項１０】
上記時刻ｔ−１の個体群から時刻ｔの個体群に対する複数のノード間の遺伝子座の全ての遺伝子は形質を発現することを特徴とする請求項９記載の学習装置。
【請求項１１】
複数のノード間の因果関係を有向グラフで表したベイジアンネットワークのネットワーク構造を学習データに基づいて構築する学習方法であって、
それぞれ上記複数のノード間の順序と因果関係とが規定された遺伝子型を有する個体により構成された初期個体群を準備し、
遺伝的アルゴリズムに基づいて上記初期個体群に対して交叉処理及び／又は突然変異処理を繰り返し行うと共に、上記学習データに基づいて各個体の評価値を計算して最適な個体を探索し、
該最適な個体の表現型を上記ネットワーク構造とする
ことを特徴とする学習方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベイジアンネットワークのネットワーク構造を学習データに基づいて構築する学習装置及びその方法に関する。
【背景技術】
【０００２】
近年、情報処理技術の適用領域が拡大し、様々な状況や多様なユーザに適応して動作することができる情報処理メカニズムが重要になってきている。つまり、事前に仮定したり完全に観測したりすることができない不確実性を持つ対象を扱うことが重要になってきている。このため、不確実な情報の下でもできる限り正しく状況を理解し、適切な処理を行う知的情報処理の仕組みが必要とされている。
【０００３】
このような要請から、ネットワーク構造を用いて問題対象を記述し、観測された事象から知りたい対象を確率的に予測する確率モデルが注目されており、変数を表すノード間の因果関係（コネクション）を有向グラフで表すベイジアンネットワークが代表的な確率モデルとして知られている。
【０００４】
【非特許文献１】Cooper， G．， and Herskovits， E．，“A Bayesian method for the induction of probabilistic networks from Data”， Machine Learning， Vol．9， p．309‐347， 1992
【非特許文献２】周洪鈞、坂根茂幸，「ベイジアンネットワークの構造学習と推論を用いた移動ロボット位置決めのためのセンサプランニング」，日本ロボット学会誌，Vol．22， No．2， p．245‐255， 2004
【発明の開示】
【発明が解決しようとする課題】
【０００５】
ところで、このベイジアンネットワークを実際の問題対象に適用するには、適切なモデルを構築することが重要である。
【０００６】
これまでの実用化例の多くは、問題領域に精通したエキスパートの知識・経験を利用してモデルを構築するものであったが、ベイジアンネットワークのネットワーク構造を学習データに基づいて構築したいという要請がある。しかしながら、学習データに基づいてネットワーク構造を構築することはNP‐Hardの問題であり、且つ、ネットワーク構造の有向非循環が保証されなければならないため、最適なネットワーク構造を構築することは容易ではない。
【０００７】
そこで、現実的な時間でネットワーク構造を構築するために、ヒューリスティクスを用いたＫ２アルゴリズムが提案されている（非特許文献１を参照）。このＫ２アルゴリズムは、１）各ノードについて親ノードとなり得る候補を限定しておき、２）ある子ノードを１つ選び、親ノードの候補を１つずつ加えてネットワーク構造を作り、３）評価値が高くなったときだけ親ノードとして採用し、４）親ノードとして加えるノードがなくなるか、加えても評価値が高くならなかったら他の子ノードに移る、というものである。上記１）〜４）を全ての子ノードについて行うことにより、準最適なネットワーク構造を構築することができる。なお、上記１）において、各ノードについて親ノードとなり得る候補を限定しておくのは、予めノード間の順序（オーダー）をデザインしておくことで、ネットワーク構造の探索範囲を制約して計算量を削減すると共に、ネットワーク構造の非循環を保証するためである。
【０００８】
このＫ２アルゴリズムは、現実的な時間でネットワーク構造を構築することができるものの、上述のように、設計者の事前知識に基づいて予めノード間のオーダーをデザインしなければならないという制約がある。
【０００９】
これに対して、遺伝的アルゴリズムを用いてノード間のオーダーを決定し、Ｋ２アルゴリズムを用いてノード間のコネクションを決定する方法も提案されている（非特許文献２を参照）。
【００１０】
しかしながら、これらの従来のアルゴリズムは、設計者がデザインしたオーダー、或いは遺伝的アルゴリズムを用いて決定されたオーダーに従って、ボトムアップにノード間のコネクションを決定してネットワーク構造を構築するものであるため、ネットワーク構造の追加学習に不向きであった。また、問題領域に精通したエキスパートでなくてもコネクションに関する一部の知識を持っている場合は多いが、従来のアルゴリズムでは、コネクションに関する事前知識をネットワーク構造に反映させることができなかった。
【００１１】
本発明は、このような従来の実情に鑑みて提案されたものであり、NP‐Hardの問題に対して、ベイジアンネットワークのネットワーク構造（オーダー及びコネクション）を学習データに基づいて構築することができ、オーダー及びコネクションに関する知識の一部又は全部をネットワーク構造に反映させることも可能とし、さらに、ネットワーク構造の追加学習も可能とする学習装置及びその方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した目的を達成するために、本発明に係る学習装置は、複数のノード間の因果関係を有向グラフで表したベイジアンネットワークのネットワーク構造を学習データに基づいて構築する学習装置であって、上記学習データが格納される記憶手段と、上記学習データに基づいて上記ネットワーク構造を構築する学習手段とを備え、上記学習手段は、それぞれ上記複数のノード間の順序と因果関係とが規定された遺伝子型を有する個体により構成された初期個体群を準備し、遺伝的アルゴリズムに基づいて上記初期個体群に対して交叉及び／又は突然変異を繰り返し行うと共に、上記学習データに基づいて各個体の評価値を計算して最適な個体を探索し、該最適な個体の表現型を上記ネットワーク構造とすることを特徴とする。
【００１３】
ここで、本発明に係る学習装置において、上記遺伝子型は、規定された順序に従って第１の方向に配置した上記複数のノードを親ノードとすると共に、上記規定された順序に従って上記第１の方向と直交する第２の方向に配置した上記複数のノードを子ノードとし、各親ノードと各子ノードとが対応する各遺伝子座における対立遺伝子により、対応するノード間の因果関係の有無を規定したものとすることができる。
【００１４】
また、上述した目的を達成するために、本発明に係る学習方法は、複数のノード間の因果関係を有向グラフで表したベイジアンネットワークのネットワーク構造を学習データに基づいて構築する学習方法であって、それぞれ上記複数のノード間の順序と因果関係とが規定された遺伝子型を有する個体により構成された初期個体群を準備し、遺伝的アルゴリズムに基づいて上記初期個体群に対して交叉及び／又は突然変異を繰り返し行うと共に、上記学習データに基づいて各個体の評価値を計算して最適な個体を探索し、該最適な個体の表現型を上記ネットワーク構造とすることを特徴とする。
【発明の効果】
【００１５】
本発明に係る学習装置及びその方法によれば、NP‐Hardの問題に対して、準最適なネットワーク構造を効率的に構築することができる。また、設計者のネットワーク構造（オーダー及びコネクション）に関する知識の一部又は全部を初期個体群に反映させることも可能とされ、ネットワーク構造の追加学習も可能とされる。
【発明を実施するための最良の形態】
【００１６】
以下、本発明を適用した具体的な実施の形態について、図面を参照しながら詳細に説明する。この実施の形態は、ベイジアンネットワークのネットワーク構造を学習データに基づいて構築する学習装置に適用したものである。
【００１７】
先ず、本実施の形態における学習装置の概略構成を図１に示す。図１に示すように、本実施の形態における学習装置１は、学習データ記憶部１０と、学習部１１と、モデル記憶部１２とから構成されている。
【００１８】
学習データ記憶部１０には、ベイジアンネットワークのモデルを構築する際に用いる学習データが格納されている。Ｘ０からＸ４までの計５個のノードが存在する場合の離散完全データの一例を図２に示す。図２において、各学習データはＸｉｊｋの形式で表現されている。ここで、ｉはノードＩＤを表し、ｊはケースＩＤ、すなわち何番目に得られた学習データであるかを表し、ｋは状態ＩＤ、すなわち各ノードにおける状態を表す。つまり、Ｘｉｊｋは、ノードＸｉについてｊ番目に得られた学習データの状態が状態ＩＤ＝ｋで表されることを意味している。
【００１９】
学習部１１は、学習データ記憶部１０に格納された学習データに基づいて、ベイジアンネットワークのモデルを構築する。特に、学習部１１は、遺伝的アルゴリズムを用いることにより、ベイジアンネットワークのネットワーク構造を構成するノード間のオーダーとコネクションとを同時に決定する。このように遺伝的アルゴリズムを用いることにより、NP‐Hardの問題に対して、準最適なネットワーク構造を効率的に構築することができる。学習部１１で構築されたモデルは、モデル記憶部１２に格納される。
【００２０】
次に、学習部１１においてネットワーク構造を構築する処理について詳細に説明する。なお、以下では簡単のため、ノードはＸ０からＸ４までの計５個であるとする。
【００２１】
本実施の形態における学習部１１は、ベイジアンネットワークのネットワーク構造、すなわち遺伝的アルゴリズムに用いる個体を、図３（Ａ）に示すような２次元遺伝子型で表現する。図３（Ａ）において、行及び列におけるｘ０、ｘ１、ｘ２、ｘ３、ｘ４はノード間のオーダーを表し、行と列とのオーダーは常に一致する。また、対角成分よりも上の上三角成分の各遺伝子座における対立遺伝子である“０”及び“１”は、親ノードから子ノードへのコネクションを表す。ここで、“０”は親ノードと子ノードとの間に因果関係がないことを示し、“１”は親ノードと子ノードとの間に因果関係があることを示す。また、対角成分は自己ループに相当し、対角成分よりも下の下三角成分の各遺伝子座における対立遺伝子である“０”及び“１”は、子ノードから親ノードへのコネクションを表す。但し、ネットワーク構造の非循環を保証するため、対角成分以下の遺伝子は形質を発現しないものとする。したがって、図３（Ａ）に示すような２次元遺伝子型を有する個体の表現型は図３（Ｂ）のようになる。
【００２２】
学習部１１は、このような２次元遺伝子型を有する多数の個体を初期個体群とし、この初期個体群から遺伝的アルゴリズムを用いて最適な個体を探索し、その個体の表現型を準最適なネットワーク構造とする。
【００２３】
遺伝的アルゴリズムを用いて最適な個体を探索する手順を図４のフローチャートに示す。
【００２４】
先ずステップＳ１において、学習部１１は、初期個体群を生成する。この際、学習部１１は、ランダムに初期個体群を生成するようにしてもよく、設計者にネットワーク構造（オーダー及びコネクション）に関する知識がある場合には、その表現型を２次元遺伝子型に変換して突然変異処理を行うことにより初期個体群を生成するようにしてもよい。後者の方法により、設計者のネットワーク構造に関する知識の一部又は全部を初期個体群に反映させることができる。また、学習部１１は、学習結果の個体から初期個体群を生成するようにしてもよい。この場合には、ネットワーク構造の追加学習が可能となる。
【００２５】
次にステップＳ２において、学習部１１は、学習データ記憶部１０に格納された学習データに基づいて、各個体の評価値（遺伝的アルゴリズムにおける適応度）を計算する。具体的には、以下の式（１）に従ってBD Metric（Ｐ（Ｄ｜Ｂｓ））を計算し、その対数を評価値とする。
【００２６】
【数１】
2007310860.tif 000003
【００２７】
この式（１）において、Ｄは学習データ記憶部１０に格納された学習データであり、Ｂｓはベイジアンネットワークのネットワーク構造、すなわち遺伝的アルゴリズムに用いる個体であり、Ｐ（Ｄ｜Ｂｓ）はＢｓという条件の下でのＤの確率である。また、Γはガンマ関数であり、Γ（ｎ）＝（ｎ−１）！である。なお、（ｎ−１）！＝ｎ！／ｎから、０！＝１！／１＝１と考えられるため、便宜上０！＝１とされる。また、図５（Ａ）に示すように、ノードの数をｎとし、ｉ番目のノードをＸｉとし、Ｘｉのｋ番目の取り得る値をｖｉｋとする。ｒｉはＸｉの取り得る値の数（状態数）である。また、図５（Ｂ）に示すように、Ｘｉの親ノードリストをπｉとし、πｉのｊ番目のパターン（取り得る値）をｗｉｊとする。ｑｉはπｉのパターンの数である。また、ＮｉｊｋはＸｉの値がｖｉｋであり、πｉがｗｉｊであるような学習データＤ中のデータの数であり、Ｎｉｊは以下の式（２）に従って計算される。また、Ｎ’ｉｊｋ、Ｎ’ｉｊは設計者の予備知識（prior knowledge）に関するものであり、Ｎｉｊｋ、Ｎｉｊと同様に扱うことができるが、詳細については後述する。
【００２８】
【数２】
2007310860.tif 000004
【００２９】
なお、実際に学習データ記憶部１０に格納される学習データには欠損データが存在したり、離散データではなく連続量であったりするが、欠損データや連続量への対応方法については、例えば文献「Richard E． Neapolitan，“LEARNING BAYESIAN NETWORKS”， ISBN 0‐13‐012534‐2」に記載されている。
【００３０】
続いてステップＳ３において、学習部１１は、終了条件を満たすか否かを判別する。具体的には、世代数が閾値を超えたことや、評価値の変化率が閾値以下となったことを終了条件とすることができる。終了条件を満たしていない場合にはステップＳ４に進み、終了条件を満たしている場合には、最も評価値が高い個体を選択して終了する。
【００３１】
続いてステップＳ４において、学習部１１は、評価値に基づいて現在の個体群から次の個体群を選択する。すなわち、評価値に基づいて現在の個体群から重複を許しながら所定数の固体を選択する。選択方法としては、ルーレット選択、トーナメント選択、エリート保存など、遺伝的アルゴリズムにおける一般的な方法が使用可能である。但し、評価値であるBD Metricの対数は負の値であるため、ルーレット選択のように、評価値に比例した確率で選択する方法を直接適用することはできない。そこで、ボルツマン分布を用いて予め評価値を正の値に変換するようにしても構わない。
【００３２】
続いてステップＳ５，Ｓ６において、学習部１１は、現在の個体群に含まれる個体に対して所定の交叉確率に従って交叉処理を行うと共に、所定の突然変異率に従って突然変異処理を行う。この交叉処理では２つの親個体から２つの子個体が生成され、突然変異処理では１つの親個体から１つの子個体が生成される。この際、生成された子個体によって親個体を置き換えてもよく、子個体と親個体とを併存させてもよい。
【００３３】
ここで、特にオーダーの交叉処理及び突然変異処理では、古典的な遺伝的アルゴリズムの手法を用いた場合、図６に示すように容易に致死遺伝子が発生してしまう。例えば、図６（Ａ）に示すように、オーダーがＸ０、Ｘ１、Ｘ２、Ｘ３、Ｘ４である個体と、オーダーがＸ０、Ｘ１、Ｘ２、Ｘ３、Ｘ４である個体とを、３番目と４番目のノード間を交叉点として交叉させた場合、同一の個体内に同じノードＩＤのノードが存在することとなるため、致死遺伝子となる。また、図６（Ｂ）に示すように、オーダーがＸ０、Ｘ１、Ｘ２、Ｘ３、Ｘ４である個体のＸ２の位置で突然変異処理を行いＸ４とした場合、同一の個体内に同じノードＩＤのノードが存在することとなるため、致死遺伝子となる。このように、容易に致死遺伝子が発生してしまうと学習の効率が悪いため、致死遺伝子が発生しないような枠組みが必要である。
【００３４】
なお、遺伝的アルゴリズムを用いてベイジアンネットワークのネットワーク構造を構築する際のオーダーの交叉処理や突然変異処理は、本質的に巡回セールスマン問題と等価であり、様々な手法が提案されている（文献「P． Larranaga， C． Kuijpers， R． Murga， and Y． Yurramendi，“Learning Bayesian network structures by searching for the best ordering with genetic algorithms”， IEEE Transactions on Systems， Man and Cybernetics， 26(4)， p．487‐493， 1996」を参照）。
【００３５】
以下では先ず、ステップＳ５における交叉処理について具体例を挙げて説明する。
【００３６】
親個体のオーダーが同じ場合における交叉処理の例を図７に示す。この場合、コネクションのみの交叉処理となる。図７（Ａ）に示すように、オーダーがＸ０、Ｘ１、Ｘ２、Ｘ３、Ｘ４である２つの親個体について、それぞれ３番目と４番目のノード間を交叉点としてその後ろの遺伝子を交換すると、図７（Ｂ）のような子個体が得られる。図７（Ｂ）から分かるように、親個体のコネクションは子個体に遺伝している。
【００３７】
また、親個体のオーダーが異なる場合におけるオーダーの交叉処理の例を図８に示す。オーダーの交叉処理には例えばＰＭＸ（partially‐mapped crossover）を用いることができる。このＰＭＸは、１）ランダムに交叉点を２カ所選び、２）その交叉点間のノードを交換し、３）各ノードがその個体内で、３‐１）使用されていないならそのまま使用し、３‐２）既に使用されているなら、交換前のノードの写像となるノードと交換し、３‐３）そのノードも既に使用されているなら、そのノードの写像となるノードと交換する、というものである。この際、交換されるノードは、自身の親ノード（又は子ノード）とのコネクションも引き継ぐ。図８（Ａ）に示すように、オーダーがＸ０、Ｘ１、Ｘ２、Ｘ３、Ｘ４である親個体と、オーダーがＸ２、Ｘ０、Ｘ４、Ｘ３、Ｘ１である親個体とを、２番目と３番目のノード間、４番目と５番目のノード間を交叉点として、ＰＭＸの手法に従って交叉点間のノードを交換すると、図８（Ｂ）のような子個体が得られる。図８（Ｂ）から分かるように、親個体のオーダーとコネクションとは子個体に遺伝している。
【００３８】
なお、図７（Ａ）のように親個体のオーダーが同じ場合に、ＰＭＸの手法に従ってオーダーの交叉処理を行うと、図７（Ｂ）と同じ子個体が得られる。つまり、図７に示したコネクションの交叉処理は、オーダーの交叉処理の特殊な場合（親個体のオーダーが同じ場合）であり、オーダーの交叉処理を行うのみで結果としてコネクションの交叉処理も行われる。
【００３９】
続いて、ステップＳ６における突然変異処理について具体例を挙げて説明する。
【００４０】
コネクションの突然変異処理の例を図９に示す。このコネクションの突然変異処理は、任意の遺伝子座の遺伝子を対立遺伝子に反転させることにより実現される。図９（Ａ）に示すように、オーダーがＸ０、Ｘ１、Ｘ２、Ｘ３、Ｘ４である親個体について、親ノードがＸ３、子ノードがＸ１である遺伝子座の遺伝子“０”を対立遺伝子“１”に反転させ、親ノードがＸ４、子ノードがＸ０である遺伝子座の遺伝子“１”を対立遺伝子“０”に反転させると、図９（Ｂ）のような子個体が得られる。
【００４１】
また、オーダーの突然変異処理の例を図１０に示す。オーダーの突然変異処理には例えばＩＶＭ（inversion mutation）を用いることができる。このＩＶＭは、１）１以上の連続するノードをランダムに選択して取り除き、２）取り除いた複数のノードのオーダーを反転した後、ランダムな位置に挿入する、というものである。図１０（Ａ）に示すように、オーダーがＸ０、Ｘ１、Ｘ２、Ｘ３、Ｘ４である親個体について連続する２つのノードＸ２、Ｘ３を選択して取り除き、そのオーダーを反転した後、Ｘ４の後ろに挿入すると、図１０（Ｂ）のような子個体が得られる。
【００４２】
なお、図９に示したコネクションの突然変異処理と図１０に示したオーダーの突然変異処理とは互いに独立であるため、両者を共に行うことができる。但し、何れの処理を先に行うかによって、得られる子個体は異なる。オーダーの突然変異処理を行った後にコネクションの突然変異処理を行った例を図１１に示す。図１１（Ａ）に示すように、オーダーがＸ０、Ｘ１、Ｘ２、Ｘ３、Ｘ４である親個体について連続する２つのノードＸ２、Ｘ３を選択して取り除き、そのオーダーを反転した後、Ｘ４の後ろに挿入すると、すなわちオーダーの突然変異処理を行うと、図１１（Ｂ）のような個体が得られる。さらに、この個体について、親ノードがＸ３、子ノードがＸ１である遺伝子座の遺伝子“０”を対立遺伝子“１”に反転させ、親ノードがＸ４、子ノードがＸ０である遺伝子座の遺伝子“１”を対立遺伝子“０”に反転させると、すなわちコネクションの突然変異処理を行うと、図１１（Ｃ）のような個体が得られる。
【００４３】
図４に戻って、ステップＳ７では親ノードの数を制限し、再びステップＳ２に戻る。すなわち、予め各個体の各子ノードについて、自身と因果関係を有する親ノードの数（FanIn）に上限数（MaxFanIn）を設けておき、ステップＳ５，Ｓ６における交叉処理、突然変異処理の結果、任意の子ノードについて因果関係を有する親ノードの数が上限数を超えた場合には、FanIn≦MaxFanInとなるように遺伝子を調整する。このように親ノードの数を制限する例を図１２、図１３に示す。図１２（Ａ）に示すように、オーダーがＸ０、Ｘ１、Ｘ２、Ｘ３、Ｘ４である親個体と、オーダーがＸ２、Ｘ０、Ｘ４、Ｘ３、Ｘ１である親個体とを、２番目と３番目のノード間、４番目と５番目のノード間を交叉点として、ＰＭＸの手法に従って交叉点間のノードを交換すると、図１２（Ｂ）のような子個体が得られる。ここで、図中左側の子個体において、子ノードＸ０と因果関係を有する親ノードの数（FanIn）は“４”であり、上限数（MaxFanIn）である“３”を超えている。そこで、図１３（Ａ）に示す個体のうち、例えば親ノードがＸ３、子ノードがＸ０である遺伝子座の遺伝子“１”を対立遺伝子“０”に反転させて図１３（Ｂ）のような個体を生成することにより、FanIn≦MaxFanInとする。
【００４４】
なお、FanIn≦MaxFanInとなるように遺伝子を対立遺伝子に反転させる際には、反転させる遺伝子をランダムに選択するようにしてもよく、その個体の評価値が最も高くなるように選択するようにしてもよい。後者の場合には、親ノードの数が上限数を超えた子ノードを有する個体について評価値を計算する必要があるが、この個体についてはステップＳ２で評価値を計算する必要はなく、ステップＳ７で計算された評価値を流用することができる。
【００４５】
このように、本実施の形態における学習装置１によれば、ベイジアンネットワークのネットワーク構造（オーダー及びコネクション）、すなわち遺伝的アルゴリズムに用いる個体を２次元遺伝子型で表現し、２次元遺伝子型を有する多数の個体を初期個体群として、この初期個体群から遺伝的アルゴリズムを用いて最適な個体を探索し、その個体の表現型をベイジアンネットワークのネットワーク構造とすることにより、NP‐Hardの問題に対して、準最適なネットワーク構造を効率的に構築することができる。
【００４６】
また、学習装置１によれば、設計者にネットワーク構造（オーダー及びコネクション）に関する知識がある場合に、その表現型を２次元遺伝子型に変換して突然変異処理を行って初期個体群を生成することにより、設計者のネットワーク構造に関する知識の一部又は全部を初期個体群に反映させることができる。なお、一部のノードにおけるオーダーやコネクションを固定したい場合には、その固定したオーダーやコネクションと異なる２次元遺伝子型を有する個体を致死遺伝子と見なし、上記ステップＳ４において選択対象から除外するようにしてもよい。
【００４７】
また、学習装置１によれば、学習結果の個体から初期個体群を生成することにより、ネットワーク構造の追加学習も可能とされる。
【００４８】
なお、図４に示したフローチャートでは、学習部１１は、交叉処理及び突然変異処理の双方を行うものとして説明したが、何れか一方のみを行うようにしても構わない。
【００４９】
ところで、式（１）に示したように、BD Metricは主として、ネットワーク構造及び学習データによって決まるＮｉｊｋと、設計者の予備知識によって決まるＮ’ｉｊｋとで構成される。一般的に、あるノードＸｉとその親ノードとについて、設計者の予備知識がｐ（ｖｉｋ，ｗｉｊ）のように全てのｉ、ｊについて定義できる場合、Ｎ’ｉｊｋは以下の式（３）に従って計算される。この式（３）において、Ｎ’はequivalent sample sizeと称され、予備知識から得られた情報をどの程度のサンプル数として想定するかを設定するためのパラメータである。
【００５０】
【数３】
2007310860.tif 000005
【００５１】
設計者がネットワーク構造に関する予備知識を持っている場合には、このようにして計算されたＮ’ｉｊｋを上述した式（１）に代入することにより、設計者の予備知識を反映させることができる。
【００５２】
一方、設計者がこのような予備知識を持たない場合には、Ｎ’ｉｊｋ＝１としてBD Metricを計算するのが一般的である。Ｎ’ｉｊｋ＝１として計算されるBD Metricは、特にK2 Metricと称される。
【００５３】
しかしながら、このようにＮ’ｉｊｋ＝１とした場合には、同じマルコフ等価クラス（推論結果が同じになるクラス）に属する有向非循環グラフ（Directed Acyclic Graph；ＤＡＧ）であっても、計算されるBD Metricの値が異なることがある（“http//mikilab.doshisha.ac.jp/dia/research/report/2002/0507/009/report20020507009.html”等を参照）。
【００５４】
一例として、Cloudy、Sprinkler、Rain、WetGrassという４つのノードからなる図１４に示すようなネットワーク構造について考える。
【００５５】
図１４に示すＤＡＧのうち、Ｇ１〜Ｇ３は、同じリンクを持ち、且つ、Sprinkler→WetGrass←Rainという同じuncoupled head-to-head meetingsを持つため、同じＤＡＧパターンｇｐで表現できる。しかしながら、Ｇ４は、Ｇ１〜Ｇ３と同じリンクを持つものの、Sprinkler→Cloudy←Rainというuncoupled head‐to‐head meetingsを別途持つため、ＤＡＧパターンｇｐでは表現できない。図１４には、このような４つのＤＡＧに対してある学習データを与えたとき、Ｎ’ｉｊｋ＝１として計算される評価値（BD Metricの対数）も併せて示している。
【００５６】
なお、学習データは、図１５（Ａ）に示すような条件付き確率テーブル（Conditional Probability Table；ＣＰＴ）を有するＤＡＧを用いて、次のようにして作成した。すなわち、先ず、最も親のノードであるCloudyにおいて、条件付き確率テーブルに基づいてtrue／falseを確率的に決定する。仮にここではCloudy＝trueであったとする。次に、Cloudyの子ノードであるSprinkler及びRainにおいて、その親条件下での条件付き確率テーブルに基づいてtrue／falseを確率的に決定する。仮にここではSprinkler＝False、Rain＝trueであったとする。次に、Sprinkler及びRainの子ノードであるWetGrassにおいて、その親条件下での条件付き確率テーブルに基づいてtrue／falseを確率的に決定する。このようにして１つのケースの学習データが作成され、同様にして図１５（Ｂ）に示すように１０００ケースの学習データを作成した。
【００５７】
図１４に示すように、Ｎ’ｉｊｋ＝１とした場合には、Ｇ１、Ｇ３の評価値とＧ２の評価値とが異なっている。このように、Ｎ’ｉｊｋ＝１とした場合には、本来同じ評価値となるべき同じマルコフ等価クラスに属するＤＡＧ、すなわち同じＤＡＧパターンで表現できるＤＡＧであっても、計算されるBD Metricの値が異なることがある。
【００５８】
したがって、上述のようにBD Metricの対数を評価値とし、この評価値に基づいて最適なネットワーク構造を探索するような場合には、Ｎ’ｉｊｋ＝１とすることは適切でない。
【００５９】
そこで、本実施の形態では、同じマルコフ等価クラスに属するＤＡＧであれば計算されるBD Metricの値が同じになるように、以下のようにしてＮ’ｉｊｋを決定する。
【００６０】
先ず、第１の方法では、ノードＸｉの状態数をｒｉとしたとき、それぞれの同時確率分布ｐ（Ｘ０，Ｘ１，・・・，Ｘｎ−１）を全て以下の式（４）に従って計算する。
【００６１】
【数４】
2007310860.tif 000006
【００６２】
そして、予備知識の影響が最も小さくなるように同時発生頻度ｃ（Ｘ０，Ｘ１，・・・，Ｘｎー１）を全て１として、以下の式（５）のようにＮ’ｉｊｋを決定する。
【００６３】
【数５】
2007310860.tif 000007
【００６４】
この第１の方法では、ノード数ｎや状態数ｒｉが大きくなるとＮ’ｉｊｋの値も大きくなるため、学習データの影響Ｎｉｊｋが予備知識の影響Ｎ’ｉｊｋよりも小さくなる虞がある。そこで、第２の方法では、予備知識の影響がなくなるように、Ｎ’ｉｊｋ＝０とする。
【００６５】
図１４に示した４つのＤＡＧについて、第１の方法及び第２の方法で決定されたＮ’ｉｊｋを用いて計算された評価値を図１６に示す。図１６に示すように、第１の方法及び第２の方法でＮ’ｉｊｋを決定した場合には、Ｇ１〜Ｇ３の評価値が全て同じ値になっている。
【００６６】
以下、具体的な実施例について説明する。この実施例は、テレビジョン受信器（以下、単に「テレビ」という。）に取り付けられたカメラによってユーザを観察し、ユーザの行為を推論するためのベイジアンネットワークのモデルを想定し、そのネットワーク構造を予め準備した学習データに基づいて構築したものである。
【００６７】
学習データは、以下のようにして準備した。
【００６８】
先ず、テレビに向かって操作をするユーザをカメラで撮像し、その入力画像から、
・FaceDir（FaceDirection）：顔の方向
・FacePlace：顔の位置
・FaceSize：顔のサイズ
・OptiFlow（OpticalFlowDirection）：ユーザの動き
の４種類を図１７〜図２０に示すように認識した。すなわち、FaceDirについては、図１７に示すように入力画像を上下方向に３分割、左右方向に５分割し、ユーザの顔が中心位置にあると仮定した場合に、１５個の領域のうち何れの領域の方向を向いているか、或いは入力画像中にユーザの顔が存在しないかによって合計１６状態に分けた。また、FacePlaceについては、全ての学習データにおける顔の位置情報をベクトル量子化手法を用いて例えば図１８のようにクラス分けし、ユーザの顔が９個の領域のうち何れの領域に存在するか、或いは入力画像中にユーザの顔が存在しないかによって合計１０状態に分けた。FaceSizeについては、ユーザの顔のサイズが図１９に示す４つのサイズの何れに近いか、或いは入力画像中にユーザの顔が存在しないかによって合計５状態に分けた。OptiFlowについては、ユーザの動きの方向が図２０に示す８方向の何れに近いか、或いは入力画像中に動きが存在しないかによって合計９状態に分けた。
【００６９】
次に、その認識結果に対し、
・Channel（Communication Channel）：ユーザがテレビと対面しているか
・ComSignal（Communication Signal）：ユーザがテレビに対して操作をしているか
・UserGoalTV：ユーザがテレビを意識しているか
・UserPresence：ユーザがテレビの前に存在しているか
の４種類のラベリングを行った。なお、このラベリングは全てＹＥＳ又はＮＯの２値（２状態）とした。
【００７０】
さらに、動的事象を扱うため、上述した認識結果及びラベルの時系列を考えた。なお、ある時刻のデータに対しては“_t_0”を、１ティック前のデータに対しては“_t_1”を、２ティック前のデータに対しては“_t_2”をそれぞれ末尾に付して、例えば“FacePlace_t_0”のように表現するものとする。
【００７１】
４種類の認識結果と４種類のラベルとをそれぞれ３ティック分用いるとノード数は２４となる。約９０分間の動画（３０フレーム／秒）からティック間隔を１秒間として約１６５０００ケースの学習データを準備した。
【００７２】
この学習データに基づいて、Ｋ２アルゴリズムを用いて構築したネットワーク構造を図２１に示す。この際、ノード間のオーダーは以下の通りとした。
FacePlace_t_0、FaceSize_t_0、FaceDir_t_0、OptiFlow_t_0、Channel_t_0、ComSignal_t_0、UserGoalTV_t_0、UserPresence_t_0、FacePlace_t_1、FaceSize_t_1、FaceDir_t_1、OptiFlow_t_1、Channel_t_1、ComSignal_t_1、UserGoalTV_t_1、UserPresence_t_1、FacePlace_t_2、FaceSize_t_2、FaceDir_t_2、OptiFlow_t_2、Channel_t_2、ComSignal_t_2、UserGoalTV_t_2、UserPresence_t_2。
【００７３】
本実施例では、この図２１に示すネットワーク構造を初期構造として、上述と同じ学習データに基づいてネットワーク構造の追加学習を行った。学習過程におけるネットワーク構造の推移を図２２〜図２５に示す。この図２２〜図２５は、それぞれ２０，４０，６０，８０世代目のネットワーク構造を示したものである。図２１〜図２５から分かるように、世代交代を繰り返すことにより、エリート個体の評価値（BD Metricの対数）は大きくなっている。評価値は８０世代目以降２００世代まで変化がなかった。よって、ほぼ８０世代で収束し、準最適なネットワーク構造が構築されたと言える。なお、最終的なノード間のオーダーは以下の通りであった。
FaceDir_t_0、FaceSize_t_0、FacePlace_t_0、Channel_t_0、OptiFlow_t_0、UserPresence_t_0、FaceDir_t_1、UserGoalTV_t_0、FaceSize_t_1、FacePlace_t_1、ComSignal_t_1、Channel_t_2、Channel_t_1、ComSignal_t_0、OptiFlow_t_1、FaceSize_t_2、FaceDir_t_2、FacePlace_t_2、ComSignal_t_2、OptiFlow_t_2、UserGoalTV_t_1、UserGoalTV_t_2、UserPresence_t_1、UserPresence_t_2。
【００７４】
本発明は、上述した実施の形態とは別の実施の形態（以下、第２の実施の形態とする。）として、複数のノード間の動的因果関係を有向グラフで表したダイナミックベイジアンネットワークのネットワーク構造を学習データに基づいて構築する学習装置に適用してもよい。以下、本発明を適用した第２の実施の形態における学習装置について説明する。
【００７５】
先ず、本発明を適用した第２の実施の形態における学習装置の概略構成を図２６に示す。図２６に示すように、学習装置２は、学習データ記憶部２０と、学習部２１と、モデル記憶部２２とから構成される。なお、学習装置１と同様の構成については、詳細な説明を省略する。
【００７６】
上述した学習装置１におけるベイジアンネットワークでは、固定数のノードの確率分布を記述したが、学習装置２におけるダイナミックベイジアンネットワークでは、この固定数のノードの確率分布を時系列プロセスに拡張する。
【００７７】
この時系列プロセスは、数式（６）に示すように、確率変数Ｘにおいてマルコフ連鎖（Markovian）とする。
【００７８】
【数６】
2007310860.tif 000008
【００７９】
また、この時系列プロセスは、不変(stationary)であり、Ｐ（Ｘ［ｔ＋１］Ｘ［ｔ］）は、ｔに対して独立とする。
【００８０】
これにより、ダイナミックベイジアンネットワークにおいて、例えば、Ｘ１からＸ３までの計３個のノードが存在する個体の表現型は、図２７（Ａ）に示すようなｔ＝０の初期状態Ｘ［０］におけるノードの分布（distribution）を特定する初期ネットワークＢ０の表現型と、図２７（Ｂ）に示すような全てのｔにおいて遷移確率Ｐ（Ｘ［ｔ＋１］Ｘ［ｔ］）を特定する遷移ネットワークＢｔの表現型とで表現される。
【００８１】
この例において、初期ネットワークＢ０と遷移ネットワークＢｔとの組（Ｂ０，Ｂｔ）は、図２７（Ｃ）に示すようなＸ［０］，・・・，Ｘ［∞］の半無限大の形式、また、図２７（Ｄ）に示すようなＸ［０］，・・・，Ｘ［Ｔ］の展開した形式で表現されることが可能である。
【００８２】
このように、初期ネットワークＢ０と遷移ネットワークＢｔとの組（Ｂ０，Ｂｔ）で表現されるダイナミックベイジアンネットワークを２ＴＢＮ（２−time−slice Bayesian Network）と呼ぶ。
【００８３】
学習データ記憶部２０には、ダイナミックベイジアンネットワークのモデルを構築する際に用いる学習データが格納されている。例えば、Ｘ１からＸ３までの計３個のノードが存在する場合、学習データ記憶部２０には、ｔ＝０におけるノードであるＸ１［０］と、Ｘ２［０］と、Ｘ２［０］とが格納されている。
【００８４】
学習部２１は、学習データ記憶部２０に格納された学習データに基づいて、ダイナミックベイジアンネットワークのモデルを構築する。この学習部２１で構築されたモデルは、モデル記憶部２２に記憶される。
【００８５】
次に、学習部２１においてネットワーク構造を構築する処理について説明する。なお、以下では簡単のため、ノードはＸ１からＸ３までの計３個であるとする。
【００８６】
学習部２１は、ダイナミックベイジアンネットワークのネットワーク構造を構築、すなわち遺伝的アルゴリズムに用いる個体を図２８（Ａ）に示すような初期ネットワークＢ０の２次元遺伝子型と、図２８（Ｂ）に示すような遷移ネットワークＢｔの２次元遺伝子型とで表現する。
【００８７】
図２８（Ａ）に示す初期ネットワークＢ０の２次元遺伝子型においては、上述した実施の形態における学習装置１と同様に、行及び列におけるｘ１、ｘ２、ｘ３はノード間のオーダーを表し、行と列とのオーダーは常に一致する。また、対角成分よりも上の上三角成分の各遺伝子座における対立遺伝子である“０”及び“１”は、親ノードから子ノードへのコネクションを表す。ここで、“０”は親ノードと子ノードとの間に因果関係がないことを示し、“１”は親ノードと子ノードとの間に因果関係があることを示す。また、対角成分は自己ループに相当し、対角成分よりも下の下三角成分の各遺伝子座における対立遺伝子である“０”及び“１”は、子ノードから親ノードへのコネクションを表す。但し、ネットワーク構造の非循環を保証するため、対角成分以下の遺伝子は形質を発現しないものとする。したがって、図２８（Ａ）に示すような２次元遺伝子型を有する個体の表現型は図２７（Ａ）のようになる。
【００８８】
一方、図２８（Ｂ）に示す遷移ネットワークＢｔの２次元遺伝子型においては、時刻ｔにおけるノード間の因果関係と、時刻ｔ−１から時刻ｔへのノード間の因果関係とをそれぞれ別の２次元遺伝子型で表現する。時刻ｔにおけるノード間の因果関係を表現する２次元遺伝子型は、時刻ｔ＝０の初期ネットワークＢ０の場合と同様に、対角成分以下の遺伝子は形質を発現しないものとする。一方、時刻ｔ−１から時刻ｔへのノード間の因果関係を表す２次元遺伝子型は、対角成分以下の遺伝子も形質を発現するものとする。
【００８９】
学習部２１は、このような２次元遺伝子型を有する多数の個体を初期個体群とし、この初期個体群から遺伝的アルゴリズムを用いて最適な個体を探索し、その個体の表現型を準最適なネットワーク構造とする。
【００９０】
ここで、学習部２１が遺伝的アルゴリズムを用いて最適な個体を探索する手順について図２９のフローチャートを参照しながら説明する。なお、この処理動作は、上述した実施の形態における図４のフローチャートに示す処理動作と基本的に同様であり、同様の内容については、詳細な説明を省略する。
【００９１】
先ずステップＳ１１において、学習部２１は、初期個体群を生成する。２ＴＢＮにおける初期個体群は、初期ネットワークＢ０を表す２次元遺伝子型を有する複数の個体、遷移ネットワークＢｔにおける時刻ｔでのノード間の因果関係を表す２次元遺伝子型を有する複数の個体、及び、遷移ネットワークＢｔにおいて時刻ｔ−１から時刻ｔへのノード間の因果関係を表す２次元遺伝子型を有する複数の個体より構成されるものである。
【００９２】
次にステップＳ１２において、学習部２１は、学習データ記憶部２０に格納された学習データに基づいて、各個体の評価値（遺伝的アルゴリズムにおける適応度）を計算する。具体的には、以下の式（７）に従って２ＴＢＮにおけるBD Metric（Ｐ（Ｄ｜Ｇ））を計算し、その対数を評価値とする。
【００９３】
【数７】
2007310860.tif 000009
【００９４】
式（７）において、上述の実施の形態における学習装置１と同様に、Ｄは学習データ記憶部２０に格納された学習データであり、Ｇはダイナミックベイジアンネットワークのネットワーク構造、すなわち遺伝的アルゴリズムに用いる個体であり、Ｐ（Ｄ｜Ｇ）はＧという条件の下でのＤの確率である。また、上述の実施の形態における学習装置１と同様に、Γはガンマ関数であり、Γ（ｎ）＝（ｎ−１）！である。また、図５（Ａ）に示したように、ノードの数をｎとし、ｉ番目のノードをＸｉとし、Ｘｉのｋ番目の取り得る値をｖｉｋとする。ｒｉはＸｉの取り得る値の数（状態数）である。また、図５（Ｂ）に示したように、Ｘｉの親ノードリストをπｉとし、πｉのｊ番目のパターン（取り得る値）をｗｉｊとする。ｑｉはπｉのパターンの数である。また、ＮＧｉｊｋはＸｉの値がｖｉｋであり、πｉがｗｉｊであるような学習データＤ中のデータの数であり、ＮＧｉｊは以下の式（８）に従って計算される。また、Ｎ’Ｇｉｊｋ、Ｎ’Ｇｉｊは設計者の予備知識（prior knowledge）に関するものであり、ＮＧｉｊｋ、ＮＧｉｊと同様に扱うことができる。
【００９５】
【数８】
2007310860.tif 000010
【００９６】
式（７）は、以下の式（９）に示すように、初期ネットワークＢ０のネットワーク構造を有する個体の評価値と遷移ネットワークＢｔを有する個体の評価値との積として表される。
【００９７】
【数９】
2007310860.tif 000011
【００９８】
ここで、Ｐ（Ｄ｜Ｂ０）は、以下の式（１０）で表される。このＰ（Ｄ｜Ｂ０）は、図３０の条件付き確率テーブルに基づくｔ＝０におけるノードＸ１，Ｘ２，Ｘ３の学習データと初期ネットワークＢ０の構造とから算出されたＮＢｏ，Ｎ’Ｂｏを用いて表される。
【００９９】
【数１０】
2007310860.tif 000012
【０１００】
また、Ｐ（Ｄ｜Ｂｔ）は、以下の式（１１）で表される。このＰ（Ｄ｜Ｂｔ）は、図３１の条件付き確率テーブルに基づく学習データの内、時系列データにおいて連続する２時刻分のノードＸ１［ｔ−１］，Ｘ２［ｔ−１］，Ｘ３［ｔ−１］，Ｘ１［ｔ］，Ｘ２［ｔ］，Ｘ３［ｔ］における学習データを１セットとして適用する。また、Ｐ（Ｄ｜Ｂｔ）は、遷移ネットワークＢｔの構造から算出されたＮＢｔ，Ｎ’Ｂｔを用いて表される。
【０１０１】
【数１１】
2007310860.tif 000013
【０１０２】
続いてステップＳ１３において、学習部２１は、終了条件を満たすか否かを判別する。終了条件を満たしていない場合にはステップＳ１４に進み、終了条件を満たしている場合には、最も評価値が高い個体を選択して終了する。
【０１０３】
続いてステップＳ１４において、学習部２１は、評価値に基づいて現在の個体群から次の個体群を選択する。すなわち、評価値に基づいて現在の個体群から重複を許しながら所定数の個体を選択する。
【０１０４】
続いてステップＳ１５，Ｓ１６において、学習部２１は、現在の個体群に含まれる個体に対して所定の交叉確率にしたがって交叉処理を行うと共に、所定の突然変異率に従って突然変異処理を行う。
【０１０５】
この場合においても、上述した実施の形態における学習装置１と同様に、特にオーダーの交叉処理及び突然変異処理において古典的な遺伝的アルゴリズムの手法を用いた場合、致死遺伝子が発生しないような枠組みが必要となる。
【０１０６】
続いてステップＳ１７では、親ノードの数を制限し、再びステップＳ１２に戻る。
【０１０７】
このように、本発明を適用した第２の実施の形態における学習装置２によれば、２ＴＢＮのネットワーク構造（オーダー及びコネクション）、すなわち、遺伝的アルゴリズムに用いる個体を、初期ネットワークＢ０を表す２次元遺伝子型、遷移ネットワークＢｔにおける時刻ｔでのノード間の因果関係を表す２次元遺伝子型、及び、遷移ネットワークＢｔにおいて時刻ｔ−１から時刻ｔへのノード間の因果関係を表す２次元遺伝子型で表現し、それぞれの２次元遺伝子型を有する多数の個体を初期個体群として、この初期個体群から遺伝的アルゴリズムを用いて最適な個体を探索し、その個体の表現型をダイナミックベイジアンネットワークのネットワーク構造とすることにより、NP‐Hardの問題に対して、準最適なネットワーク構造を効率的に構築することができる。
【０１０８】
上述した実施の形態におけるベイジアンネットワークにより動的事象を表現するには、事前にtime−sliceの数を指定しなければならず、指定数以上のtime−sliceを取り扱うことは不可能である。
【０１０９】
これに対して、学習装置２によれば、初期ネットワークＢ０及び遷移ネットワークＢｔによって無限数のtime−sliceを表現することが可能となる。
【０１１０】
また、学習装置２によれば、２ＴＢＮを適用して時刻ｔ−１から時刻ｔにおける時系列データを用いてノード間の動的な因果関係のグラフィカルモデルを学習することが可能となる。
【０１１１】
また、学習装置２によれば、時系列データから動的因果関係のグラフィカルモデルを学習する際に、初期ネットワークＢ０のネットワーク構造を設計者の事前知識として用意することが可能であり、このネットワーク構造から追加学習を行うことが可能となる。
【０１１２】
以下、本発明を適用した第２の実施の形態における学習装置２の具体的な実施例について説明する。この実施例は、上述した実施の形態における学習装置１と同様に、テレビに取り付けられたカメラによってユーザを観察し、ユーザの行為を推論するためのダイナミックベイジアンネットワークのモデルを想定し、そのネットワーク構造を予め準備した学習データに基づいて構築したものである。
【０１１３】
学習データは、学習装置１と同様に、以下のようにして準備した。
【０１１４】
先ず、テレビに向かって操作をするユーザをカメラで撮像し、その入力画像から、
・FaceDir（FaceDirection）：顔の方向
・FacePlace：顔の位置
・FaceSize：顔のサイズ
・OptiFlow（OpticalFlowDirection）：ユーザの動き
の４種類を上述した実施の形態において示した図１７〜図２０のように認識した。
【０１１５】
次に、その認識結果に対し、
・Channel（Communication Channel）：ユーザがテレビと対面しているか
・ComSignal（Communication Signal）：ユーザがテレビに対して操作をしているか
・UserGoalTV：ユーザがテレビを意識しているか
・UserPresence：ユーザがテレビの前に存在しているか
の４種類のラベリングを行った。なお、このラベリングは全てＹＥＳ又はＮＯの２値（２状態）とした。
【０１１６】
約９０分間の動画からtick間隔を１［ｓ］として約１６５０００ケースの時系列データを用意して学習を行った。
【０１１７】
この学習データに基づいて、Ｋ２アルゴリズムを用いて構築したネットワーク構造を図３２に示す。
【０１１８】
この際、図３２（Ａ）に示す初期ネットワークＢ０におけるノード間のオーダーは、以下の通りとした。
FacePlace、FaceSize、FaceDir、OptiFlow、UserPresence、UserGoalTV、Channel、ComSignal。
【０１１９】
また、図３２（Ｂ）に示す遷移ネットワークＢｔにおけるノード間のオーダーは、以下の通りとした。
FacePlace_t-1、FaceSize_t-1、FaceDir_t-1、OptiFlow_t-1、UserPresence_t-1、UserGoalTV_t-1、Channel_t-1、ComSignal_t-1、FacePlace_t、FaceSize_t、FaceDir_t、OptiFlow_t、UserPresence_t、UserGoalTV_t、Channel_t、ComSignal_t。
【０１２０】
以上、本発明を実施するための最良の形態について説明したが、本発明は上述した実施の形態のみに限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能であることは勿論である。
【図面の簡単な説明】
【０１２１】
【図１】本実施の形態における学習装置の概略構成を示す図である。
【図２】ベイジアンネットワークのモデルを構築する際に用いる学習データの一例を示す図である。
【図３】２次元遺伝子型とその表現型との一例を示す図である。
【図４】遺伝的アルゴリズムを用いて最適な個体を探索する手順を示すフローチャートである。
【図５】BD Metricの計算式を説明するための図である。
【図６】古典的な遺伝的アルゴリズムにおいて、オーダーの交叉処理及び突然変異処理で発生する致死遺伝子の一例を示す図である。
【図７】親個体のオーダーが同じ場合におけるコネクションの交叉処理の例を示す図である。
【図８】親個体のオーダーが異なる場合におけるオーダーの交叉処理の例を示す図である。
【図９】コネクションの突然変異処理の例を示す図である。
【図１０】オーダーの突然変異処理の例を示す図である。
【図１１】オーダーの突然変異処理の後にコネクションの突然変異処理を行う例を示す図である。
【図１２】オーダーの交叉処理の結果、ある子ノードについて因果関係を有する親ノードの数が上限数を超える例を示す図である。
【図１３】因果関係を有する親ノードの数が上限数を超えないように遺伝子を調整する例を示す図である。
【図１４】４つの有向非循環グラフと、Ｎ'ｉｊｋ＝１として算出される評価値とを示す図である。
【図１５】図１４の評価値を算出する際に用いた学習データを作成する手法を説明する図である。
【図１６】４つの有向非循環グラフと、本実施の形態の手法によって算出される評価値とを示す図である。
【図１７】具体的な学習データを得る手法を説明する図である。
【図１８】具体的な学習データを得る手法を説明する図である。
【図１９】具体的な学習データを得る手法を説明する図である。
【図２０】具体的な学習データを得る手法を説明する図である。
【図２１】学習データに基づいてＫ２アルゴリズムで得られたネットワーク構造を示す図である。
【図２２】図２１のネットワーク構造を初期構造として追加学習を行った際の２０世代目のネットワーク構造を示す図である。
【図２３】図２１のネットワーク構造を初期構造として追加学習を行った際の４０世代目のネットワーク構造を示す図である。
【図２４】図２１のネットワーク構造を初期構造として追加学習を行った際の６０世代目のネットワーク構造を示す図である。
【図２５】図２１のネットワーク構造を初期構造として追加学習を行った際の８０世代目のネットワーク構造を示す図である。
【図２６】本発明を適用した第２の実施の形態における学習装置の概略構成を示す図である。
【図２７】２ＴＢＮにおける表現型の一例を示す図である。
【図２８】２ＴＢＮにおける２次元遺伝子型の一例を示す図である。
【図２９】遺伝的アルゴリズムを用いて最適な個体を探索する手順を示すフローチャートである。
【図３０】評価値を算出する際に用いた学習データを作成する手法を説明する図である。
【図３１】評価値を算出する際に用いた学習データを作成する手法を説明する図である。
【図３２】学習データに基づいてＫ２アルゴリズムで得られたネットワーク構造を示す図である。
【符号の説明】
【０１２２】
１  学習装置、１０  学習データ記憶部、１１  学習部、１２  モデル記憶部
【図１】
2007310860.tif 000015
【図２】
2007310860.tif 000016
【図３】
2007310860.tif 000017
【図４】
2007310860.tif 000018
【図５】
2007310860.tif 000019
【図６】
2007310860.tif 000020
【図７】
2007310860.tif 000021
【図８】
2007310860.tif 000022
【図９】
2007310860.tif 000023
【図１０】
2007310860.tif 000024
【図１１】
2007310860.tif 000025
【図１２】
2007310860.tif 000026
【図１３】
2007310860.tif 000027
【図１４】
2007310860.tif 000028
【図１５】
2007310860.tif 000029
【図１６】
2007310860.tif 000030
【図１７】
2007310860.tif 000031
【図１８】
2007310860.tif 000032
【図１９】
2007310860.tif 000033
【図２０】
2007310860.tif 000034
【図２１】
2007310860.tif 000035
【図２２】
2007310860.tif 000036
【図２３】
2007310860.tif 000037
【図２４】
2007310860.tif 000038
【図２５】
2007310860.tif 000039
【図２６】
2007310860.tif 000040
【図２７】
2007310860.tif 000041
【図２８】
2007310860.tif 000042
【図２９】
2007310860.tif 000043
【図３０】
2007310860.tif 000044
【図３１】
2007310860.tif 000045
【図３２】
2007310860.tif 000046