BESOM のEMアルゴリズムを実装しました

ベイジアンネットのパラメタ学習は、
観測データがすべて与えられている場合は、
事象が起きた回数を割り算するだけでよいので簡単です。
(例えば X が起きた回数10回のうち Y も起きた回数が3回なら
P(Y|X) = 0.3 。)

BESOM のように隠れ変数(あるいは観測データの欠損値)がある場合は
EMアルゴリズムなどを使う必要があり、少し複雑になります。
とはいえ、確率伝搬アルゴリズムを使えば
比較的少ない計算量で実現可能だったみたいです。

参考にしたのは以下の本の p.195 です。

Bayesian Artificial Intelligence, Second Edition
(Chapman & Hall/CRC Computer Science & Data Analysis)
Kevin B. Korb, Ann E. Nicholson (著)
出版社: CRC Press; 2版 (2011/1/7)
ISBN-13: 978-1439815915

この本にはアルゴリズムの説明が簡単にしか書いてないですが、
それをオンライン版にして BESOM 用にアレンジして実装しました。

確率伝搬アルゴリズムはすでに実装ずみなので、
追加したコードは30行ほどですみました。
(ただし近傍学習は未実装。)

MNIST で87%くらいだった認識率が92%くらいまで
いくようになったので、たぶん正しく動いていると思います。
まだ予備実験の段階なので、ちゃんとした性能評価は、これからやります。

EMにすることで、BESOMの学習則のアドホックだったところが
ほぼなくなり、「普通」の機械学習アルゴリズムになったと思います。

その代わり、学習1ステップに必要な計算量のオーダーが、
ノード数 n に対して O(n) から O(n^2) に増えてしまいました。
ここは精度と計算量のトレードオフです。
適当なヒューリスティックスを入れることで
精度をあまり落とさずにほぼ O(n) まで落とせるかもしれません。

コメント

コメントの投稿

トラックバック


この記事にトラックバックする(FC2ブログユーザー)