12月13日から1月5日までの日記

MNIST 日記

きちんと書ける自信がないので日記を書く。
そのうちきちんとまとめるません。

とりあえず…

  • 2次判別 [95%]
  • IRLS (1対多) [92%]
  • IRLS (1対1) [94%]
  • IRLS (ソフトマックス) [93%]
  • 多層パーセプトロン (512HU) [97%]
  • k-NN [97%]
  • Shape Context (中途半端実装) [97%]

※ []内は記憶によるMNISTテストの正解率（大体あってる）
をCで実装して試した。

感想日記

2次判別

たぶん2次判別。クラスごとに多変量正規分布を当てはめて、入力に対して一番大きい尤度のクラスに割り当てる。思ってたより精度がよかった。学習が速いというかひたすら正規分布のパラメータを計算するだけなので速い。尤度が小さすぎて浮動少数点の闇に消えるので、分散共分散行列を固有ベクトルで対角化して式を総乗の形に変形したあとに対数をとって総和の形にしてやっと比較できる値が取れるんだけど、このときに固有値の0以上だけどかなり小さい固有値の固有ベクトルは使わないほうが精度がよかった(92%→95%)。192次元(1/4に縮小)中160くらい。あとOpenCVのCvNormalBayesClassifierはこれと同じだと思った。

IRLS

ロジスティック回帰とかこのへんの区分がよく分かってない。入力ベクトルxに対してsigmoid(x^Tφ(w))が交差エントロピー誤差を最小にするようなベクトルwをニュートン法で求める。φ(w)=wだけど思ったより精度が悪かった。ニュートン法ではHΔx=-∇fという方程式を解くんだけど(Hはヘッセ行列、∇fは誤差関数の勾配)、退化してて解けないので、特異値分解して最小ノルム解を使った。このせいか極値付近で値が飛び跳ねるので、Δxの更新に制御項をつけて、誤差が増大した場合は更新重みを下げるみたいなことをして無理やり求めた。かなり怪しい実装けど、94%だから大体あってんじゃね？　とかテキトウな感じだ。
で、このときにソフトマックス誤差関数がややこしい気がしたので、先に2クラス分類器を多クラスにする方法として、1対多と1対1とかいうのを試した。1対多は、0と1,2,3,4,5,6,7,8,9を分類する、1と..(それ以外)を分類するをクラス数分作って、入力に対して全部試したあと、一番それっぽいところに割り当てる。ただ、分類器ごとの出力値が正規化されていないので怪しいのかな。1対1は、0と1、0と2、..というクラス数の全組み合わせ（階乗）分作って、入力に対して全部試したあと多数決をとる。0に対して2と3とか関係ない分類器を試すけど、多数決で消えてくれるので気にしなくてもいいのかな。同点が出た場合は、たとえば、2と3と5が最後まで残ったとすると、2と3は比較しているので、その分類器を信じてどちらか消して（たとえば3)、2と5は比較しているので、その分類器を信じてどちらか消して、みたいなことをした。ただ同点はなかったので使えてない。
そのあと2クラス分類器の組み合わせで2次判別が抜けなかったので、泣きながらソフトマックス関数を試した。これは多クラスに対する誤差関数を定義して、ひとつの分類器を作る。ここでもソフトマックス関数の分母が浮動小数点の闇に消えててハマったので、a^20/a^40=a/a^21みたいな変換を動的に行って回避した。ヘッセ行列が(クラス数x入力次元)x(クラス数x入力次元)とかでかいので計算がかなり遅い。実際、10クラス192次元なので1920x1920のヘッセ行列を作ってこの連立方程式を繰り返し解く。学習がかなり遅いし、精度もそんなによくなかったけど、識別は速い。ニュートン法あたりの実装が悪い気がするけど、93%だから大体あってんじゃね？　とかテキトウな感じだ。

多層パーセプトロン

2-Layer-NN。内容はかなり前にやってたし、数値計算でハマるところもなかったのであまり感想はないけど、先に線形分類器をやっていたので、ちょっと理解が変った。よくあるニューラルネットワークの図は良くないんじゃないかなと思った。
f:id:ultraist:20090106174646j:image
ほんの少しだけみにくいかもしれないけどこういう図のほうが分かりやすいと思う。
オンライン版で作ったけど、バッチにしないとCUDAは無理だなーと思った。やるならデータを毎回ランダムに小分けして半バッチとかかな。
中間層素子は128、256、512を試して、512が一番よかった。それ以上は遅すぎるのでやめた。入力は01に正規化せずそのまま突っ込んだけど、バックグラウンドの輝度0を-0.5fくらいにしたほうが精度がよかった。
誤差関数はソフトマックスを試そうと思いながら平均二乗誤差しかやっていないので、そのうちやる。

k-NN

k近傍法。せっかくSOM作ったのでこれインデックスにできないかなーと思っていたのでk-NNで使った。最初、BMU(ベストマッチユニット)の近傍半径5ユニットとかでやったけど、10のほうが少しよかったのでインデックスとしては微妙なんだけど、そこそこ高速化できて精度もあまり落ちてないと思う。
多次元ベクトルのインデックスはなにがいいんだろう。VP-Treeとかか。このへんもやっておきたいと思ったけどしてない。LSHはかなり大量のデータがないとダメそうなんだけど、どうなんだろ。OpenCVのk-NNが高速化されたみたいな話を見て読もうと思っていたけど読んでない。

Shape Context

これは中途半端な実装で全部やってない。
Shape context - Wikipedia, the free encyclopedia
これのstep 4までやってて、ここからthin plate splineとかいうので片方変形して、ガウスフィルタをかけながら輝度の差をとるっぽいけど、前の段階の最小コストの割当問題を解くのが遅すぎてヤバイ。
これは2つの画像間の形状差の距離関数で、輪郭線上のN点をサンプリングしたあと、各点を中心とした雲の巣みたいなパイ状のヒストグラムを計算して、このヒストグラムのカイ２乗と接線角度の重み付き差を各点で合計した時に最小となる組み合わせを最適化問題として解くのが最初のフェーズで、
f:id:ultraist:20090106155936j:image
やってみるとこんな感じになる。これは0と0だから大体あってるんだけど、この割当が遅くてマジで人生に絶望する。ここでCUDAかーと思うけど、今、Munkres' Assignment Algorithmというのでやってて、これは条件分岐が多くてCUDAに合わないと思うので、効率悪くても行列の計算か物理シミュレーションっぽい計算だけでできればいいなーと思うけど、分からなかった。
とりあえずこの比較が遅い問題はk-NNで使ったインデックスを使って比較範囲を減らすことである程度回避できた気がするけど、距離関数が違うから不安だし、それでも遅いのでとりあえず放置してる。ただ、最初の特徴の取り方とかヒストグラムをシフトすると回転に対応できるとか、最小コストの割当問題とか、いろいろほかに応用が利きそうで勉強にはなった。
方法としてはいい気がするので、次撃沈したら頼るかもしれない。

まとめ

最初はあまりよく分かってないのを実装能力を頼って突き進んだ感じだけど、今は…も結構怪しいか。
統計は少し勉強してみて基本的なことは大体分かったと思うけど、用語の使い方がやけに難しいしフィールドによって違う言葉を使っていたりするので、正しく使える気がしない。僕的には実装やモデルのカスタマイズさえできればいいけど、本を読むのにはいるし、カッコよく説明することもできないので、調べてでも積極的に使うようにしたほうがいいのかな、と思いながら使ってない…。
実装面では、数値計算がヤバかった。逆行列が計算できなかったり、いつの間にか行列が#QNAN,#1.INFとか謎の値だらけになってたり。ただ、ほとんどは高校数学と線形代数で回避できたので、数学はとても役に立つなーと思った。
あと、参考資料は海外のサイトが多いけど、本としては、
パターン認識と機械学習 上 - ベイズ理論による統計的予測
を読んだ。この本は1ページずつじっくり読み進んで読了すると大体分かった気になったけど、あとで読み返すと「こんなの読んだっけ？」とか思うのでたぶん概要しか読めない。やばい。いいなーと思ったこともあまり使えてない。いつか撃沈したら助けを乞おうと思う。

次は……

普通はSVMとかカーネル云々だろうけど、僕はソフトを実装してナンボだし、(イメージ上の）実行速度と必要性を考えたときに、とりあえずは使わないなーと思っているので、ここまでの知識とアンサンブル学習をちょっとやってやりたい問題をいくつかやってみて、撃沈したら、2月くらいからまたやろうかなーと思ってる。