2011年06月28日

混合ガウス分布とEMアルゴリズムについて

前回まで確率密度関数が1個のガウス分布に従うという仮定で推定してきましたが、データによっては一つのガウス分布では推定が難しいと思います。

そこで、複数のガウス分布を重ね合わせて推定する混合ガウス分布というものが考えられています。

混合ガウス分布を使う場合、各ガウス分布の重み、平均ベクトル、共分散行列のパラメータを最尤推定する必要があるのですが、パラメータがいっぱいあって複雑なので解けないので、反復計算でパラメータを求める方法がとられています。

その方法の一つがEMアルゴリズムで、初期値を適当に与えてEステップとMステップを繰り返すと良さそうなパラメータに収束するそうです。

参考サイト
[1] http://d.hatena.ne.jp/aidiary/20100521/

今回は↑の参考サイト様にpythonのソースコードがありましたので、ほぼそのままC++に書き直させていただきました。

実行結果

270点位の2次元座標を2個のガウス分布の混合でEMアルゴリズムを使うと6〜12回ぐらいで収束しました。
緑色の点が各ガウス分布の中心です。

em_001.png

確率密度関数を適当な色で描画した結果が以下のようになりました。

em_002.png

白色化すると共分散行列が単位行列になるので使えないんでしょうか?
混合ガウス分布にするとそれぞれのガウス分布の共分散行列は単位行列にならない気もしますし前回の続きで試してみたい気がします。

↓今回のテストデータを白色化した結果
em_003.png

流れとしては白色化した教師データを混合ガウス分布で推定してテストデータに対して最大事後確率則で分類する感じですかね。
あまり結果は変わらない気もしますね。

web拍手 by FC2
posted by シンドラー at 20:02 | Comment(0) | TrackBack(0) | Pattern Recognition | このブログの読者になる | 更新情報をチェックする

2011年06月24日

特異値分解と白色化について

MNIST手書き数字データを使用して数字認識を試してみました。
http://yann.lecun.com/exdb/mnist/

以前のベイズの定理を使って尤度が一番高いものを〜のやつは、流れとして以下のようになると思います。

ポイント:
@最大事後確率則で事後確率が最大のカテゴリに分類する
A対数とっても比較結果は同じなので各カテゴリの対数事後確率を比較する
B事後確率はガウスモデルを想定する
C対数事後確率の(比較)計算に必要なのは平均ベクトルと共分散行列の逆行列と行列式

手順:
@訓練データから平均ベクトルと共分散行列を計算
A共分散行列の逆行列と行列式を計算
B未知パターンの対数事後確率を比較計算して分類

で、@は問題ないのですが、Aの共分散行列の逆行列と行列式の計算が問題になります。

28×28の画像を考えた場合、一番左上の画素などは文字の特徴と殆ど関係がない背景画素ですので、分散がほぼ0になって,共分散行列がランク落ちして行列式が0になって逆行列が存在しないのでABが計算できないということになってしまいます。

また、ランク落ちの問題以外にも、n次元対称行列の逆行列や行列式の計算は面倒ですので、共分散行列を単位行列に変換する白色化も行いたいと思います。

白色化ができれば、逆行列は単位行列、行列式は1.0になりますので、未知パターンと平均ベクトルの距離だけで対数事後確率の比較ができるようになります。

このランク落ち対策と白色化を行うための行列の計算は、特異値分解を行うことで一度に行うことができます。おそらく。

以下手順です。

MINST手書き数字データですが、特徴ベクトルが784次元,教師データが各カテゴリ約6000枚ありますので、行列Aは784×6000とします。
ちなみに行と列を逆に取ると以後のお話が色々変わってしまうと思います。共分散行列Mは784×784の対称行列になります。

N×Nの共分散行列Mの特異値分解は下記のようになります。特異値分解についてはWikipediaとか色々見てください。

white_001.png

Σは対角成分に特異値を持つ対角行列ですが、共分散行列がランク落ち(R<N)している場合、R番目までが0以上の値をとって、それ以降は0になっています。
で、特異値の寄与率?を考えて、特異値が特異値の合計の○○%となるランクR'を計算して、UをN×R'、ΣをR'×R'、V*をR'×Nの行列に削減してしまいます。

white_002.png

次に白色化ですが、白色化後の行列をBとおくと、例えばR'が200だった場合,200×6000の行列になります。

white_003.png

この白色化を行うための行列Wが、実はΣ~-1/2V~*になるのです。たぶん。

white_004.png

これで784次元が200次元に削減できて、しかもBの共分散行列は単位行列になっていてとてもお得です。

Bの平均ベクトルを再度計算し、未知パターンxに対する対数事後確率を比較すると分類ができます。
未知パターンxは、各カテゴリの白色化行列を掛けて、xiに変換しておきます(N次元→R'次元)。

white_006.PNG

white_005.png

MNISTのテストデータ10000枚に対して行ったところ、各カテゴリの平均正解率は93.8%でした。

この方法だとR'の値がカテゴリによって70と150など次元が変わってくるのでなんとなく気持ち悪いんですが、それなりの正解率が出ているのでいいのかなーと思います。
一応特異値の寄与率?を変えてみて一番正解率が高かったときの次元が大体140ぐらいで、784次元を140次元まで下げちゃっているのもどうなのかなーと思いますが0より大きいもの全てを使うより正解率が上がっているのでいいのかなーと思います。

MNISTのサイトに載っている結果はエラー率0.4%とか凄すぎですね。

おまけ

2次元の場合で適当に点を打って白色化したら重なっちゃいました。
同時対角化というものがあるようですが、それを使えばいいんでしょうかね。
whitening_001.PNG whitening_002.PNG

正規直交変換を掛ければ良さそうなんですが作り方がよくわかりませんね。
whitening_003.PNG

行列計算や特異値分解についてはEigenというライブラリを使用しました。

web拍手 by FC2
posted by シンドラー at 22:58 | Comment(0) | TrackBack(0) | Pattern Recognition | このブログの読者になる | 更新情報をチェックする