【C言語】ベイジアンネットワークの学習アルゴリズム

今回はベイジアンネットワークの学習アルゴリズムを中心に解説を行います。
■確率的因果
事象A、Bがあり、BがAの原因であるとは、Bが発生したとき、Aが発生する確率を高めることをいいます。

例)
1000人の体型を調査したところ肥満と判断される確率は0.3となりました。ただし体重が80Kg以上の人に限っては肥満であると判断される確率は0.6に高まったため、
体重80Kg以上は肥満の原因であるといいます。

事象A、B、C、...があり、いかなる事象を同時にとってもBが発生したとき、Aが発生する確率を高める場合、BはAの真の原因であるといいます。

例)
体重が80Kg以上の人が肥満と判断される確率は0.6ですが、体重が80Kg以上かつ身長が183cm以上の人が肥満であると判断される確率は元の0.3に戻ったため
体重80Kg以上は肥満の真の原因ではありません。

■ベイジアンネットワーク
ベイジアンネットワークは確率的因果関係をグラフ理論を用いてモデリングする技術です。
ベイジアンネットワークはノードとアーク(矢印)、条件付き確率表から構成されます。ノードは確率変数、各ノード間をつなぐアークは条件付き確率に対応します。
また、ベイジアンネットワークはノードをアークの方向にたどっていって同じノードに戻らないよう構築します。
■ベイジアンネットワークの学習
データからベイジアンネットワークを構築する方法をベイジアンネットワークの構造学習のアルゴリズムといいます。
構造学習のアルゴリズムには大きく分けて、厳密解と、精度を落として計算速度を高めた近似解がありますが、最近の研究のトレンドは厳密解とのことなので、厳密解について説明します。
もっとも基本的な学習アルゴリズムの手順は、考えられるすべての構造パターンのベイジアンネットワークを構築し、個々のベイジアンネットワークについてBICなどの情報量基準を学習スコアとして求め、学習スコアが最小または最大となる構造を持つベイジアンネットワークを真の構造と仮定し採択します。

[最適化する前の厳密解構造学習]
ただし、ベイジアンネットワークの学習アルゴリズムの計算量はノードの数に応じて指数倍的にふえていくため一般的なデスクトップPCではノード数が6個か7個以上の計算は難しくなってくると思います。
この問題に対してSilander and Myllymaki(2006)は動的計画法を使った最適化を提案しています。アルゴリズムの詳細は記事末で紹介している参考書に詳しく書かれているのでここではソースコードの提供のみを行います。動的計画法で最適化されたBIC基準の厳密解学習アルゴリズムと列挙法による確率推論のソースコードを下記のgithubに上げています。
https://github.com/y-mitsui/DpBayesianNet

■検証
Kaggleのタイタニックコンペで提供されているデータを使ってベイジアンネットワークを検証しました。
設定した確率変数は次のとおりです。
性別。年齢。グレード。同一のチケット番号の乗客が全員死亡:2、全員生存:0、それ以外:1。部屋の位置が左か右か。家族と同乗か否か。
予測精度は77%となりました。
全ソースはgithubに上げています。
https://github.com/y-mitsui/kaggleTitanic

参考書籍
ベイジアンネットワーク　植野真臣