この記事は@sakanazensenさん主催のコンピュータビジョンアドベントカレンダーの12月24日分の記事です。
本日のお題はSparse CodingとDictionary Learningをscikit-LearnというPythonの機械学習ライブラリを使ってやってみよう！というお話。
こちらのテーマを選んだ理由ですが、先日コンピュータビジョン勉強会＠関東で「Sparselet Models for Efficient Multiclass Object Detection」という論文を紹介した際、資料を作る時間がなくてSparse Codingの話を割愛してしまったので、その補足の意味もこめました。
とは言えSparse Codingもscikit-Learn(というよりPython自体)も勉強を始めたばかりのため、解説はあくまでツールを使う上での基本的な知識に留めたいと思います。もし誤り等あれば御指摘下さい。
Sparse CodingとDictionary Learningについては、例えばこんなチュートリアル資料が参考になります。
http://lear.inrialpes.fr/people/mairal/tutorial_iccv09/
また、圧縮センシングに関する以下のチュートリアルビデオも参考になります。
http://research.microsoft.com/apps/video/default.aspx?id=103660
では、Sparse Coding、Dictionary Learningの順に解説をしていきます。
Sparse Coding
Sparse Codingの目的は、できるだけ少ない基底の線形和で信号を復元することです。
つまり下図のように観測さた信号をy、基底の集合（=辞書）をAとした時、スパース（ほとんどの要素が0）なxを求めます。
(1)
ここで、行列Aの列ベクトルが基底となります。例えばJPEGで使用される離散コサイン変換であれば、基底はある周波数の余弦関数数列ですし、主成分分析であれば主成分だと思って下さい。mが信号の次元数、nが基底の数です。
さて、xがスパースなので、信号yを復元するには以下のように、xの要素が0以外の基底を重みをつけて足しあわせれば済みます。
上記の例であれば信号yを復元するために、わずか３つの値とそれぞれに対応する基底のIDさえわかれば良いことがわかります。そのためデータ圧縮などに使用することが可能です。また、基底を例えば様々な人の顔としておき、観測信号yとして誰かの顔が与えられた時、Sparse Codingによって最も大きな係数を持つ基底をその個人であるとみなすことで顔認識にも応用することができます[1]。他にもノイズ除去などに応用が可能です。
では、Sparse Codingによってどうやってスパースなxを求めるかについて解説していきます。
この問題を式で表すと以下のようになります。
(2)
つまりAx=yの条件のもと、xのL0ノルム（0でない要素の数）を最小化するという問題になります。尚、ここではAの列ベクトル（基底）のL2ノルムが1であるとしています。
しかし、この式を解くのは簡単ではありません（＝NP困難）。そもそもxがスパースになるほどAx=yは誤差により成立しなくなります。
そこで、この条件を以下のようにもう少し緩めてやります。
(3)
上の式ではxのL0ノルムがε以下という条件のもとで、観測信号yと復元した信号Axの二乗和誤差を最小化することになります。この条件であれば、誤差を最も減らすような基底とその係数を順次ε個まで求めていけば最適化できます。ただしこの条件だと、xの非ゼロ要素の数がほぼεと決まっているので、できるだけxのL0ノルムを小さくしたいという要望からは外れます。
そこで、以下のような式で表すことで、誤差とスパース性とのトレードオフを表すことができます。
(4)
argmin内の第一項が二乗和誤差、第二項がスパース性を表しています。λは誤差とスパース性のバランスを調整するためのパラメータです。このように二乗和誤差＋L1正則化の形をLassoと言います。
実はこのようにL0ノルムの代わりにL1ノルムを使って上記の最適化問題を解いても、スパースな解が得られます。それをイメージで表したのが以下の図です。
このようにL1ノルムがある値t以下となるような領域は、各次元の要素を表す軸上で尖った形状を取るため、スパースな解が得られやすいという性質があります。
scikit-Learnには、上記(3)(4)式を最適化するために以下のアルゴリズムが実装されています（Ver0.12で確認）。
- OMP(Orthogonal Matching Pursuit)[2]
- LARS(Least Angle Regression)[3]
- Lasso-LARS
- Lasso-CD(Coordinate Descent)
- Threshold
１つめと２つめが(3)式を、３つめと４つめが(4)式を最適化するためのアルゴリズムです。デフォルトではOMPが選択されます。OMPは復元信号の残差が最小となるように順次基底と係数を選択していくアルゴリズム、LARSは復元信号ベクトルと観測信号ベクトルとのなす角度が小さくなるように基底と係数を調整していくアルゴリズムです。Coordinate Descentは、m次元のうちどれか１つを順番に選んでいって、順次その次元での最小値を探索していくアルゴリズムです。Thresholdは単純に規定に対する小さい係数を閾値処理によってゼロとすることでスパースにしています（もちろん精度は悪い）。
Dictionary Learning
実は(1)式の辞書Aはランダムに生成されたものであっても（というよりランダムな方が）Sparse Codingによって高い精度の信号の復元が可能です。ただし一方で、ノイズに対して弱くなってしまいます（ノイズを含んだ観測信号も正確に再現しようとするため）。
そこで、データから辞書を学習によって求めることによって、基底のパターンを学習しノイズに対して頑健な辞書を作成することができます。
辞書の作成は以下の式を満たす、A（とX）を求めることです。
(5)
ここでYとXは学習データの集合とそれに対応するスパースな係数行列です。
この最適化は
- Aを固定して、Sparse CodingによってXを求める。
- Xを固定して(5)を最小化するAを求める。
という処理を繰り返しながら収束させることになります。
Scikit-learnでは前者の最適化では同様に、
- OMP
- LARS
- Lasso-LARS
- Lasso-CD
- Threshold
の５つが、選択可能です。また、後者の最適化では、
- Lasso-LARS
- Lasso-CD
のどちらかを選びます。（デフォルトはLARS）
さて、ここまででscikit-learnでSparse CodingとDictionary Learningを使うための最低限の準備は整いました。
というわけで、明日の実践編（機械学習アドベントカレンダー12/25日分）に続きます。
参考文献
[1]J.Wright, A.Y.Yang, A.Ganesh, S.S.Sastry, and Y.Ma, "Robust Face Recognition via Sparse Representation", IEEE Transaction on Pattern Analysis Machine Intelligence, VOL. 31, NO. 2, (Feb 2009)
[2]J.A.Tropp, and A.C.Gilbert, "Signal recovery from random measurements via Orthogonal Matching Pursuit", IEEE Transaction on Information Theory, vol.53, pp.4655-4666 (2007)
[3]B.Efron, T.Hastie, I.Johnstone, and R.Tibshirani, "Least Angle Regression", Annals of Statistics, Vol.32, Number. 2, pp.407-499 (2004)
