2013年07月24日

最小二乗法による関数の多項式近似

最近たまに使用している疑似逆行列についてのメモです。

最小二乗法のちゃんとした説明(二乗誤差を最小化するために係数の偏微分を計算して…)というのはWikipedia[1]などにお任せして、とりあえず疑似逆行列を使って未知数<方程式となる連立一次方程式を解くということをします。

lsm_001.png

[1]を見ると、疑似逆行列は効率が悪いので余り使われないって書かれてますね…。

実行結果

sin関数+ノイズで生成した赤点から、5次の多項式近似を行った結果(青線)です。
lsm_002.png
5+1=6個の未知数に対して、512個のサンプル点を使用しています。
n≫m+1なので、正則っぽいです。
5次の係数が0だったので実質4次になってます。

[1] 最小二乗法
web拍手 by FC2
posted by シンドラー at 00:05 | Comment(0) | TrackBack(0) | Pattern Recognition | このブログの読者になる | 更新情報をチェックする

2012年10月29日

Parzen推定による動的背景モデルについて

気分転換?にパターン認識ネタをひとつ試してみました。

統計的パターン認識の手法として、パラメトリック法とノンパラメトリック法があります。

・パラメトリック法
−モデルがある分布(ガウス分布等)に従っていると仮定して推定
使用例:特異値分解と白色化について
・セミパラメトリック法
−モデルが複数のある分布の重ね合わせでできていると仮定して推定
使用例:混合ガウス分布とEMアルゴリズムについて
・ノンパラメトリック法
−モデルの分布は仮定せずに与えられた訓練データからモデルを推定
使用例:今回の背景モデル推定

パラメトリック法とセミパラメトリック法はこれまでに試しているので、今回はノンパラメトリック法で背景モデルの推定を試してみます。

動画像から動く物体を検出するために、背景モデルをノンパラメトリック推定する手法が提案されています。
今回は、ノンパラメトリック推定のひとつであるParzen推定を用いて、物体検出を行います。

Parzen推定の参考文献としては、以下のようなものがあります。
[1] http://sunak2.cs.shinshu-u.ac.jp/~maruyama/course/learning/2002/slides/parzen.pdf
[2] http://nlp.dse.ibaraki.ac.jp/~shinnou/zemi2010/staml/staml-okazaki-0713.pdf
[3] http://ci.nii.ac.jp/naid/110006991102

このParzen推定で背景モデルを構築する場合には、訓練データとして過去Nフレームの画像データを使用して、各画素の色や輝度値を入力とした場合に、そこが背景かどうかの確率を出力とするような確率密度関数を求めることになります。

parzen_001.png

今回、サンプル動画として、PRMUアルゴリズムコンテスト2010の画像を使用させていただいております。
オクルージョンの有無などLV1〜3に分かれており、各レベルに5つの各101枚サンプル画像があります。

通常は過去N枚使って求めた確率密度関数から、現在のフレームの画素値が背景か前景かを閾値により判定することで前景の検出を行うのですが、今回は全部で101枚に固定されているため、この101枚の画像で確率密度関数を推定した後、もう一度101枚の画像で動物体検出を行います。

実行結果

ttp://www.murase.m.is.nagoya-u.ac.jp/alcon2010/?page=download
上記ページのLv3の3(自転車に乗っている)画像で試した結果です。
上がParzen推定による結果で、下が輝度値の差分の絶対値を10倍した結果です。
赤い矩形がアルコンのデータについている正解矩形データです。




差分の絶対値をとった場合、フレームの前後の像が現れるので、二人乗りをしているように見えます。
Parzen推定だと画素毎に背景か前景かを判定するので、こういったことは起こりませんが、今回高速化の手法を全く行っていないので、処理時間的にはお話になりません。
また、Parzen推定は平滑化パラメータや閾値で結果が変わるのですが、2,3種類試しただけで特に最適化は行っていません。
精度的にもこれぐらいの問題であればフレーム間差分で十分な気がしますね。



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

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 | このブログの読者になる | 更新情報をチェックする

2011年05月07日

修正トンプソン−τ法について

学習に使うデータを正規分布と仮定した場合、異常値が混じっているとそれが影響して精度が下がることがあります。
この異常値を取り除くための手法として修正トンプソン−τ法というものがあるようです。

参考サイト:
http://applied.bpe.agr.hokudai.ac.jp/education/measurement/02.pdf

参考サイトでは1次元データでしたので、ノルムや内積に置き換えて一応n次元にしてみましたが、合っているのかどうかは分かりません。

実行結果

2次元の場合ですが、適当にマウスで点を打って異常値を除去してみました。


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

2011年05月04日

ベイズの定理を使った識別のテスト

ベイズの定理を使って格闘ゲームのプレイヤーの次の攻撃を予測するというお話が「ゲーム開発者のためのAI入門」に載っていました。

ベイズの定理の説明は、「フリーソフトでつくる音声認識システム」がわかりやすかったです。
以下一部本の引用があるので問題があればお知らせください。

条件付確率
P(A|B):Bという条件下でAが起こる確率

ベイズの定理

P(ωi|x)=P(x|ωi)P(ωi)/P(x)

xという未知パターンがあった場合、そのパターンがωiというカテゴリに属している確率は、
ωiというカテゴリの中でxが起こる確率と、ωi自体が起こる確率を掛けたものを、
xが起こる確率で割ると求まります。というお話です。

xがどこに所属するかということは、N個(i=1,2,...,N)のカテゴリのP(ωi|x)を計算して、一番起こる確率が高いカテゴリに分類するということになります。

数式で表すと、P(ωi|x)が最大になるiを求めるということで、
arg max {P(ωi|x)} = arg max {P(x|ωi)P(ωi)/P(x)}
となります。

つまり、arg max {P(x|ωi)P(ωi)/P(x)}が計算できれば、ベイズの定理を使って識別ができることになります。

1. 厄介者のP(x)を消そう

xが起こる確率は無限にある未知パターンのひとつが起こる確率ということでわかるわけがありません。

幸い、arg max {P(x|ωi)P(ωi)/P(x)}でP(x)はiに依存していませんので、消すことができます。

arg max {P(x|ωi)P(ωi)/P(x)} = arg max P(x|ωi)P(ωi)

2. 事前確率の計算

事前確率(カテゴリωiが起こる確率)は、教師データの数から推定することにします。
各カテゴリの教師データがTni個、教師データ全体がTN個あった場合、各カテゴリが発生する確率は以下の式で計算できます。

P(ωi)=Tni/TN

3. 最後の難敵「尤度」

P(x|ωi)は、確率密度関数というもので、教師データから推定します。ここで、確率密度関数は正規分布と仮定して、教師データから正規分布を生成するための計算をしておきます。

正規分布の式は下記サイトを参照してください。
http://www.orsj.or.jp/~wiki/wiki/index.php/%E5%A4%9A%E6%AC%A1%E5%85%83%E6%AD%A3%E8%A6%8F%E5%88%86%E5%B8%83

ここから、教師データから共分散行列を作って、行列式と逆行列、平均ベクトルが分かれば正規分布の式で計算できることが分かります。

で、共分散行列を作成し、LU分解で行列式と逆行列と平均ベクトルを計算しておきます。

後は未知パターンxを分類するとき、正規分布の式に当てはめて計算すれば、P(ωi|x)が計算できます。

4. 識別

P(ωi|x)P(ωi)は小さい値になってしまいますので、logをとって計算した方が良いようです。

arg max {log(P(ωi|x))+log(P(ωi))}

そういうわけでマウスで適当に打った座標を教師データとして、残りの座標がどのカテゴリに所属するかを識別するサンプルを作ってみました。

実行結果




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

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。