Nonnegative Matrix Factorization:NMFの最適化法についてのまとめ
この記事について
この記事はNMFの最適化方法についてまとめたものです。
基本的には、追加の制約なしのNMFの高速化手法についてになります。
筆者の研究サーベイは2015年ほどで止まっているのでそれ以降の研究はフォローしていません。
注意してください。
また、この記事は2015年10月に投降した記事の修正版になります。
何故、修正版を2年後に再度公開しているか？そういう気分になったためです。
Nonnegative Matrix Factorization
非負値行列分解(Nonnegative Matrix Factorization:NMF)は，非負の行列を低次元な非負行列の積に分解する手法
制約はすべての行列のすべての要素が非負
最適化問題は、以下になる。
(非負制約は省略）を最小化することになる。
しかし、この問題はU,Vに対して同時に凸ではないので、
1. 片方を固定してもう片方を最適化
2. 固定する行列を逆して同様に最適化
を交互に繰り返す。交互最適化を用いて最適化することになる。
この交互最適化はEMアルゴリズムのようなもので、残念ながら大域最適解の保証はされない。
Nonnegative Matrix Factorizationの高速な最適化手法
NMFの最適化の高速化というのは、交互最適化において、どれだけ高速に収束するか、どれだけ少ない反復回数で収束するかである。
この記事で列挙する手法は基本的には以下を考慮したNMFについて、少ない反復回数で収束するということを述べている手法になる。
1. フロベニウスノルムの二乗を誤差として扱っている。
2. 初期値は単純な乱数を用いている。初期値の設定方法は扱っていない。
以下で手法を列挙する。
Multiplicative Update rule (MU)
このMUはLee and Seungが2000年のNIPSで発表したアルゴリズムであり、機械学習やデータマイニングの分野でNMFが人気になったのはこの論文のおかげといっても過言ではない。行列毎に文字通り乗法で更新を行う。
拡張は容易だが収束性の証明はなく更新によって目的式が増加しないという単調増加性のみが保証されている。
*多分収束するって既に示されている。
実装は容易だけど近似精度が他手法と比較してよくないので個人的にはお勧めしない．
Project Gradient Descent (PGD)
Linらによる手法でその名の通りProject Gradient Descentを用いた手法．
MUよりは収束速度が速いがステップサイズに強く依存。なのでステップサイズをどう決めるかが重要。
Hierarchical Alternating Least Squares (HALS)
Cichockiらによって提案されたベクトル毎に更新する高速手法。
各ベクトルに対して残差([tex: X^{(j)}-u_j v^{T}j], [tex: X^{(j)}=X -UV^{T} +u_j v^{T}j])の近似を目的とした最小化を行う。
行列全体の一回の計算量は上記の2つよりは、やや大きいものの、収束速度が非常にはやく少ない更新回数で分解できることが経験的に知られている。
実装が容易。個人的にはお勧め。
Active-set-like method (AS)
Kimらによって提案されたベクトル毎の更新法。
有効制約法を用いてベクトル毎の更新を行う。収束は一般的にHALSと同等。
また、実装も他手法と比べるとやや面倒
Greedy Coordinate Descent (GCD)
Hsiehらによって提案された手法。
筆者の知る限り最速のNMF。
従来手法と異なり各要素に対して「要素を最適化するとどの程度近似誤差を減らすか」という指標を計算し、指標が最大の値を示す要素を選択し、更新する。
要素の更新と、その要素の「指標」の更新、そして要素を更新したことによって影響を受ける要素の「指標」の更新を繰り返す。
Greedyという名前は、この指標に対してgreedyに更新するため。
収束速度が他手法と比べて明らかにはやく2012年のACM SIGKDDでの論文だったが、この論文以降NMFの高速化の話はほぼ消えた。
Rank-one Downdate (R1D)
非負の行列のRank-1 SVDは必ずNMFになることを用いた特殊な手法。
非負の行列に対してRank-1 SVDを行って、結果をもとの行列から引いて、余った部分(残渣）をまたRank-1 SVDと繰り返していく手法。
しかし、単純にこの動作を行った場合に、１回目は非負の行列をRank-1 SVDで分解するが、２回目以降の残渣が非負であるとは限らない。
なので工夫している手法。(Rank-1 SVDをしても残渣が非負にならない 行および列のindexを探してきて、それのみでSVDするという手法）
一回の試行でRankが1ずつ増えていくことになるので、ほかの手法との比較は難しいため。どちらが高速なのかは議論されていないっぽい。
ライブラリ、提供されているコード(MATAB)
NMF界隈のコードは基本，MATLAB/OCTAVE．時々Python．
- MUやHALS,active-set-like methodは Georgia TechのPark先生の実装を利用するのがお勧め Professor Haesun Park - Georgia Tech
- sBCDは著者のページからダウンロード可能 http://www.cc.gatech.edu/grads/l/lli86/sbcd.zip
- GCDも同様に著者のページからダウンロード可能 mexを使っているので，実測値は他と比べて爆速．
MLC toolbox: MATLAB/Octave用のマルチラベル分類ライブラリ
記事を非公開にしてたけど，いま少し頑張っていることを書くことにする．
マルチラベル分類
従来の分類問題は一つのデータ点（インスタンス）は一つのクラスのいずれかに属するという設定．
マルチラベル分類は一つのインスタンスが一つ以上のクラスに属するという設定．
割り当てがラベルの組み合わせの数だけ存在するので比較的難しいよねという話．（おおざっぱにいえば
マルチラベル分類のライブラリ
色んなところで色んな人が公開している．
有名なのは
特にMulanはデータセットを公開しているので(arff形式だが)非常によく引用されている．
これらはJavaのWekaというデータマイニングライブラリをベースに実装されている．
しかし一方で，個人がいろいろと公開しているものは多くの場合がMATLABとC++(+mex function, MATLABから呼ぶため)．
例えば
- Prof. ML-Zhang http://cse.seu.edu.cn/people/zhangml/Resources.htm
- LAMDA http://lamda.nju.edu.cn/Data.ashx
- 同期 https://github.com/futuresun912
さらにeXtreme Multi-Label Classification (XML)のMSR Indiaも同様
これらはC++が基本．（大規模になるとMATLABではほとんど扱えなくなってしまうからだけど，MATLABから呼べるようになっている．
実際にSLEECはXMLでは高精度な手法で知られているがこれらはMATLAB用のコードが公開されている．
コードにはコメントがほとんどないので読むのは地獄．
自分の観測範囲ではマルチラベル分類はJava派とMATLAB派に2分されている．
MulanやMEKAを用いて実装された手法はMATLABで実装されるような手法とは比較されていないのが現状．
さらにはMATLABもコードがあちこちで提供されているので，一つのライブラリとしてまとめようってのが目的．
もう少し細かく書くと以下：
MLC-toolboxの目的
Javaは遅い（個人の経験と感想に基づく）のでMATLAB．
さらに今後公開されるコードの多くがMATLABであることを考えるとMATLAB．
Pythonも考えたけど，二つ目の理由でやはりMATLAB．
- 多様な手法の実装
MATLAB実装の多くは行列演算を頻繁に用いる手法．
これらとそうではない手法との比較を行えるようにする．
- 手法の組み合わせ
述べていないけど，これはもう一つの目的．（実はこれが一番大きな目的）
マルチラベル分類はマルチラベル分類問題を小さなもしくは簡単なマルチラベル分類問題へ変換して解くという手法が多い．
例えば，クラスタリングしてインスタンス数を減らすだったり，
特徴抽出で次元を減らすだったり．（ラベル情報を用いた教師あり手法がある）
さらにラベル数をサンプリングもしくは次元縮約で減らすということもある．
これらはマルチラベル分類問題を他のマルチラベル分類問題に変換していると見なせる．
なのでこれらの組み合わせは膨大にあって，どの組み合わせが良いのかを調べる必要がある．
例えば，実際にSLEECといった手法はクラスタリング+特徴抽出+KNNだったりする．
どの手法がどの程度，精度に影響を与えているのかはわからないので組み合わせを簡単に検証できるようなライブラリが必要だなということで
作っている
