行列(画像)分解アルゴリズムGoDec (Zhou+, ICML2011)の実装を公開しました

つい2週間ほど前,機械学習のトップカンファレンスICMLが開催されました.その中のGoDecという行列分解アルゴリズムを実装したので公開します.このアルゴリズムは,簡単にいえば「外れ値抜き特異値分解」で,昨日のICML読み会で発表しました.論文はこれです.

厳密な版(Nai:ve GoDec)は遅いですが実装は非常に簡単です.遅い版でも,数百x数百ピクセルの小さな画像であれば,十分実用的な速度で動くので,実装して試してみた次第です.GoDecの論文では,この厳密な版(Nai:ve GoDec)が線形収束することを証明した上で,さらに,実用的に早くなるように(証明はないようですが)乱択化低ランク近似で高速化したFast GoDecも提案されています.僕のソースコードはNew BSDライセンスにしておきましたが,GoDec自体の特許関係は全く調べておりません.もしかしたら,特許が取られているかもしれませんので,商用にGoDecを用いることには注意が必要です.

ソースコードと使い方

コンパイルには,Eigenが必要です.C++0xを使っているので,gcc 4.6.0以上奨励です.

git clone git@github.com:niam/godec.git
cd godec
./waf configure
./waf build
build/src/godec -r 8 -k 762 hogehoge.png

これは,簡単にいえば,「762個までの外れ値を許容して,hogehoge.pngを行列だと思ってランク8で低ランク近似しろ」ということです.

例えば,以下の画像をhogehoge.pngとして入力したとします.

すると,X.png, L,png, S.png, LpS.pngがカレントディレクトリに出来ます.X.pngは,元の画像をグレイスケールに変換したもので,これが,分解対象の行列になります.

これをランク8の行列Lと,要素数762の行列Sに分解し,L+Sを実行したものがLpSです.

GoDecは,特異値分解に加えて外れ値の数kの自由度を持つので,特異値分解と比較するためには,自由度の数を合わせないとフェアではありません.200x180行列において,1ランク分の情報を保存するには200次元の特異ベクトルu+180次元の特異ベクトルv+特異値σの381個の自由度が必要になります.従って,2ランク分の情報がちょうど762自由度なので,単純な特異値分解で上位8+2=10で低ランク近似した場合と自由度がおなじになります.元の画像を特異値分解で上位10で低ランク近似したものが,下の画像です.

GoDecでは,頭の上の木漏れ日による光の点が外れ値として処理されハッキリ表示できているのに対し,特異値分解(SVD)では周りの色に紛れてしまっていることが分かります.

SVDと比較する場合,この自由度を合わせる作業は面倒くさいので,自動的に自由度を合わせてくれるモードも作りました.

build/src/godec -r 10 --rdiff=2 --comparesvdmode hogehoge.png

とやると,上の実験設定と同じ実験設定になります.つまり,特異値分解の方のランクが10で,それと2ランク差がつくようにGoDecのランクと,許容する外れ値の数kを自動的に設定してくれます.comparesvdmodeでは,10ランクで近似したsvd.pngも作られます.

アルゴリズムの解説

行列を,小さいランクの行列で近似することを低ランク近似と言います.低ランク近似の代表的な方法が特異値分解です.しかし,特異値分解は,行列内に,外れ値のような他の要素よりずっと大きい/小さい要素があったりすると,その要素を上手く再現出来なかったり,また,その要素に引きずられて,その要素の周りがにじむように近似誤差が大きくなってしまったりすることが知られています.

このアルゴリズムは,簡単に言えば「外れ値抜きの特異値分解」です.

  1. 外れ値を抜いて特異値分解でランクrで低ランク近似する
  2. もとの行列と低ランク近似した行列を見比べて,要素の差(の絶対値)が大きい「外れ値」要素を差の大きい方からk個見つけてきて新しい外れ値にする

を繰り返したものが,線形収束することを示しているのがこの論文です.

僕の発表資料はこちらです.解釈に間違いがある可能性がありますので,詳細は論文本体を参照されることをお勧めします.