読者です 読者をやめる 読者になる 読者になる

北の大地から

北大でひっそりと研究

高速な非負値行列分解（Nonnegative Matrix Factorization:NMF)についての簡単まとめ

非負値行列分解(Nonnegative Matrix Factorization:NMF)は，非負行列を低次元な非負行列の積に分解する手法
X = UV^{T} \ \ \ \ \ \text{s.t.} X,U,V >0
この行列を見つけるために
\min_{U,V} \|X - UV^{T}\| (非負制約は省略)
を最小化することになる．
しかし，この問題はU,Vに対して同時に凸ではないために，片方を固定して最適化するを交互に行う交互最適化を行う必要がある．
この交互最適化はEMアルゴリズムのように，大域最適解の保証はされない．
実際に，非負制約もあることで，NMFの大域最適解を見つけることはNP-hardであることがVavasisらによって示されている．


この記事では，どのような手法があるのか列挙し，コメントを残すだけで，詳しい言及は避ける．（気力があれば少しずつ詳細を書いていく）
また，これらの手法の全ては近似の基準として二乗誤差を用いたものである．

  1. Multiplicative Update rule (MU)：Lee and Seungの論文で提案された更新法であり行列毎に更新を行う．拡張は容易だが，収束性の証明はなく，更新によって目的式が増加しないという単調増加性のみが保証されている．実装は容易だけど，近似が悪いので個人的にはお勧めしない．
  2. Project Gradient Descent (PGD): Linらによる手法でその名の通り，Project Gradient Descentを用いた手法．MUよりは収束速度が速いがステップサイズに強く依存．
  3. Hierarchical Alternating Least Squares (HALS): Cichockiらによって提案されたベクトル毎に更新する高速手法．各ベクトルに対して残差( X^{(j)}-u_j v^{T}_j, X^{(j)}=X -UV^{T} +u_j v^{T}_j)の近似を目的とした最小化を行う．行列全体の一回の計算量は，上記の2つよりは大きいものの，収束速度が非常にはやく，少ない更新回数で，分解できる．実装が容易で，収束が速い．追加で制約を課すことも容易．個人的にはお勧め．
  4. Active-set-like method (AS)：Kimらによって提案されたベクトル毎の更新法．有効制約法を用いる．ベクトル毎の更新が可能だが，追加で制約を課すことが難しく，収束速度も一般的にHALSより同等か遅い．また，実装も他手法と比べると，面倒．
  5. scalar Block Coordinate Descent (sBCD): Liらによって提案された手法．要素毎の更新であり二乗誤差だけでなく，Bregman Divergenceに対応している．要素毎の更新として提案されているものの実際はベクトル毎に更新を行う．実際に提案者の適用しているコードがベクトル毎の更新であり，ファイルの名前もHALSとなっている(fhals)．二乗誤差を用いた際の更新式はHALSと同じ．
  6. Greedy Coordinate Descent (GCD)： Hsiehらによって提案された手法．筆者の知る限り最速のNMF手法．要素毎に更新する手法．従来手法と異なり，各要素に対して，要素を最適化すると，どの程度近似誤差を減らすかという指標を計算し，指標が最大になる要素のみを更新，指標を更新を繰り返すことでgreedyに更新する．収束速度が，他手法と比べて明らかにはやく，2012年のACM SIGKDDでの論文だったが，この論文以降NMFの高速化の話はほぼ消えた．NMFの高速化は基本的に収束が速いかどうかの議論．そんでもって理論的ではあまりない．ってか理論的じゃない．勝負したい方はこの手法と勝負になる．
  7. Rank-one Downdate :ベクトル毎の更新手法．rank-1の分解をgreedyにに行う．特異値分解を使って，その特異ベクトルから非負成分を抽出して，次のrank-1に分解する行列を計算するを繰り返す．計算速度がよいのも売りだが，比較がなく，筆者も実装していないので，名言は避ける．（あまり深く読んでもいない) 後述といっても詳しく述べてはいないが，Separable NMFに分類したほうがいいっぽい．

ライブラリや提供されているコード(MATAB)
NMF界隈のコードは基本，MATLAB/OCTAVE．時々Python．

  1. MUやHALS,active-set-like methodは　Georgia TechのPark先生の実装を利用するのがお勧め

Professor Haesun Park - Georgia Tech

  1. sBCDは著者のページからダウンロード可能

http://www.cc.gatech.edu/grads/l/lli86/sbcd.zip

  1. GCDも同様に著者のページからダウンロード可能

Cho-Jui's Homepage
mexを使っているので，実測値は他と比べて爆速．


他について
SGDについてはまとめてない．
Online NMFも3つほど提案されている．JMLRの論文を参考にするのがといいはず．Sparse codingの話の中にNMFの話もある．
StreamingのNMFについては2015年のACM SIGKDDのERATO河原林チームの論文がある．
Separable NMF (ある理想化でのExactNMF)についてはX-rayがある．ICML 2012年だったかどっか．



とりあえず数式の書き方も込みで，テスト投稿．数式の中央寄せなどができたりできなかったり，環境を模索していく必要がありそう．
参考文献面倒くさい．．．
後日，いい書き方を探す．Mendeley等でテキスト出力して貼り付けが正解？