すべてがMFになる

機械学習

すべてがFになる，映像化するみたいですね．犀川創平も西之園萌絵も配役がイメージと違って一部で話題になっていました．さて，最近テンソル分解を使った論文をよく見かけるのですが，いまだにきちんと整理できずにいます．テンソルかわいいよ，テンソル．

そこで，まずは行列分解(matrix factorization, matrix decomposition)を整理してみようと思います．行列の分解手法というと線形代数的な観点からは簡単に思いつくだけでも

  • 固有値分解
  • LU分解
  • コレスキー分解

などがありますが，これらは分解前の行列と分解後の行列が一致する(たとえばA=LU)方法です．一方で，機械学習やデータマイニング界隈（特にレコメンデーション等）で出てくる行列分解というのは，大規模データや関係性データの中から低ランクの構造を抽出することや次元圧縮を目的としています．なので，正確に言うならば，行列分解というよりは低ランク行列近似と呼ぶ方が正しいように思います．

これらの低ランク行列近似の方法論は暗に低ランク性を仮定しているということがポイントです．ということで，

  • 特異値分解(Singular Value Decomposition; SVD)
  • 主成分分析(PCA)
  • CUR分解 or CMD(Compact Matrix Decomposition)
  • 非負値行列因子分解(Non-negative Matrix Factorization; NMF)

あたりを簡単にまとめてみたいと思います．ちなみに行列分解の専門家ではないので，間違いがあればご指摘ください．

特異値分解(SVD)

特異値分解は以下の式の解として得られる行列Yによる近似です．(Fはフロベニウスノルム)


その結果として，行列Xは

のように分解（近似）できます．Σは特異値を上から順にk個とって対角行列にしたものです．SVDは多くの分野で使われているものの，行列のサイズが大きくなったときには計算コストが大きくなります．

主成分分析

主成分分析は古典的な多変量解析手法ですが，やっていることはSVDと同じです．主成分分析における主成分と因子負荷量はSVDで分解した行列を用いると以下のように表すことができます．

そのため，左特異ベクトルと特異値の積が各主成分になっていて，右特異ベクトルがそれぞれの因子負荷量になっているという関係なのですね．

CUR分解 or CMD

2009年のid:mamorukさんのエントリではCUR分解と呼ばれています．（簡単に調べてみたけど）特に日本語での呼び名はないっぽいです．

CURやCMDのモチベーションはSVDによる分解では，大規模だがスパースな行列Xをに分解したときに，やが密行列になってしまうという問題を防ぎたいというものです．もちろんこれが問題かどうかはタスク依存だと思いますが，解釈しやすさなどを考えるとやが疎行列になると嬉しい訳です．また，元行列がスパース行列なので，そのスパース性を失うのももったいないというモチベーションがあります．

そこで，SVDでは密行列だったやに対し，元のスパース行列からサンプリングしてやをつくり，行列近似を行うというのがCUR分解のイメージです．

提案論文では一様分布からサンプリングをしていて，その後もう少し賢いサンプリング法(CMD)が考えられています．サンプリングするだけでいいの！というのは驚きですが，元行列がスパースな場合，よくよく考えてみるとPCA(SVD)がやっているorthogonal projectionとサンプリングがほぼほぼ変わらないというのは直感的には真であると思います．

NMF

非負値行列因子分解(NMF)も結構いろんなところで見かける行列分解手法で，非負行列Xが与えられたときに，のように二つの行列の積に分解します．その名の通り，分解した行列U, Vがそれぞれ非負のため，解釈しやすい，現象論的に負の値を取らない現象を表現できる，ということがウリです．

主成分分析(やSVD)では独立性が仮定されていたのに対し，NMFでは非負性を用いることで，独立性を仮定することなく行列分解を可能としています．

近似の評価尺度としては，XとUVのフロベニウスノルムの最小化，

一般化KLダイバージェンスの最小化

などが利用されるようです．

以前，持橋先生の資料でLDAで得られたトピック行列と混合比行列は正規化するとNMFと同じことをしているという内容があったように記憶しています．

まとめ

というわけで，非常に簡単ですが，SVD, CUR, NMFあたりを大雑把にまとめてみました．詳細は各手法の理論背景，計算方法，実装等を眺めるのが良いと思いますが，簡単なプレビューとしてお役に立てばと思います．

PFIの比戸さんが昨年まとめられているKDD2013のbest paperのmatrix sketchは行列分解ではないですが，ある巨大な行列を小さな行列に圧縮するという方法でたぶん似たような考えの方法ではないかと思います(未読)．行列分解や次元削減の界隈は圧縮センシング等のスパース性を設計原理としたモデリングにも通ずる発想ですよね．というわけで，そろそろテンソル理解したい．誰かおせーて．

参考