楡楡

備忘録とまとめと

Nonnegative Matrix Factorization:NMFの最適化法についてのまとめ

この記事について

この記事はNMFの最適化方法についてまとめたものです。
基本的には、追加の制約なしのNMFの高速化手法についてになります。 筆者の研究サーベイは2015年ほどで止まっているのでそれ以降の研究はフォローしていません。
注意してください。
また、この記事は2015年10月に投降した記事の修正版になります。
何故、修正版を2年後に再度公開しているか？そういう気分になったためです。

Nonnegative Matrix Factorization

非負値行列分解(Nonnegative Matrix Factorization:NMF)は，非負の行列を低次元な非負行列の積に分解する手法
\begin{equation} X = UV^{T} \end{equation}
制約はすべての行列のすべての要素が非負 \begin{equation} X,U,V \geq 0 \end{equation}

最適化問題は、以下になる。
\min_{U,V} ||X - UV^{T}||^{2}_{F}
(非負制約は省略）を最小化することになる。 しかし、この問題は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．

  1. MUやHALS,active-set-like methodは　Georgia TechのPark先生の実装を利用するのがお勧め Professor Haesun Park - Georgia Tech
  2. sBCDは著者のページからダウンロード可能 http://www.cc.gatech.edu/grads/l/lli86/sbcd.zip
  3. GCDも同様に著者のページからダウンロード可能 mexを使っているので，実測値は他と比べて爆速．