グラフ構造の学習

以上で述べた条件付き確率の学習はある特定のグラフ構造のもとでのパラメータ 探索であった．一方，このグラフ構造もデータから決定したいという要求がある． データから構造を評価するときはその構造のもとでの最適なパラメータが必要であり， したがってグラフ構造の学習はパラメータの探索を含む． 最適なパラメータへの収束 が必ずしも保証できない山登り法などで探索する場合には準最適なパラメータで代用 せざるを得ない．そのため構造の評価を正確に行うことが難しくなるという問題が ある．またパラメータの探索空間はパラメータの次元のオーダーであるが，構造の探索 空間はグラフのノード数に対して指数オーダーとはるかに広大なため，データセット だけから最適な構造を発見することは容易でない． こうした様々な困難のためグラフ構造の学習は現在も未解決の多くの問題を含んで おり，今後もなお重要な課題であると認識されている[Friedman 97]．

現在，良く知られているベイジアンネットワークの構造学習アルゴリズムとしては 現実的な時間でグラフ構造を探索するためのヒューリスティクスを用いた K-2アルゴリズム[Cooper 92]がある． このアルゴリズムは (1)各ノードについて親ノードになりえる候補を限定しておく，(2)ある子ノードを一つ 選び，候補となる親ノードを一つづつ加えてグラフを作る，(3)そのグラフのもとで パラメータを決定し，評価する，(4)評価が高くなった時だけ親ノードとして採用し， (5)親ノードとして加える候補がなくなるか，加え ても評価が高くならなくなったら他の子ノードへ移る，(6)全ての子ノード について(1)-(5)を繰り返す，というものである． 始めにノードを順序づけしておくことで親ノードになれるノードの組合せを限定し， 計算量の増大と生成するグラフ構造の循環を避けているが，これにより生成できる 構造の探索範囲も制約されてしまう．他には順序づけをしないヒューリスティクスを 用いた探索アルゴリズム[Buntine 91]や遺伝的アルゴリズムを使って探索するもの [Larranaga 96]などがある．

生成したグラフ構造を評価する際には，過剰に複雑な構造を避けるために， データの尤度と構造の複雑さの両方を考慮することが本質的に重要であり， MDL基準の適用例[Suzuki 93]などがある． また単一の構造に限定するのではなく，仮説となる複数の構造の混合 [Thiesson 98]や，ある変数の値により依存関係を変化させるネットワーク[Geiger 93]もある．