機械学習
MachineLearning
Julia
JuliaDay 22

スパースコーディングのための辞書生成アルゴリズム,K-SVDをJuliaで実装した

More than 1 year has passed since last update.

スパースコーディングのための辞書を生成してくれるアルゴリズム,K-SVDをJuliaで実装しました.

スパースコーディングとは

ひとことで言うと,「ある信号をできるだけ少数の基底で表現する手法」のことを言います.


引用元: Andrew Ng, Unsupervised Feature Learning and Deep Learning, 2015

例えばこの図では Natural Images が表現したい信号,Learned bases が信号を表現するための基底となっています.
Test example は画像から得られたパッチ(Natural Images内の赤枠の部分)です.

信号の基底を辞書と呼びます.スパースコーディングは,信号を辞書中のできるだけ少ない数の要素で表現することを目標とします.
この図では Test example を3つの要素の組み合わせで表現しています.

K-SVDとは

K-SVDはスパースコーディングにおける辞書を生成してくれるアルゴリズムです.
表現したい信号を与えると,その信号を効率よく表現するための辞書を生成してくます.

KSVD.jl

KSVD.jlK-SVDのオリジナルの論文のアルゴリズムをJuliaのパッケージとして実装したものです.
使い方はREADMEに書いてあるので,結果だけここに載せます.

この文字画像をK-SVDに入力します.
digit_images.png

するとこのように文字画像の基底が得られます.
digits256.png

問題点

オリジナルのK-SVDには欠点があります.それは入力信号のサイズが大きくなると基底の計算が一気に重くなることです.
物体認識のデータセットなど,大きなデータにK-SVDを適用するとなかなか計算が終わりません.

解決策

信号の基底を効率よく計算する方法が既に論文になっています.オリジナルのK-SVDよりも複雑ですが,どうやら高速に辞書を求めることができるようです.