大規模データ処理のための行列の低ランク近似 -- SVD から用例ベースの行列分解まで --

id:naoya さんのLatent Semantic Indexing の記事に触発されて、ここ1週間ほどちょくちょく見ている行列の近似計算手法について書いてみる。ここでやりたいのは単語-文書行列(どの単語がどの文書に出てきたかの共起行列)や購入者-アイテム行列(どの人がどの本を買ったかとか、推薦エンジンで使う行列)、ページ-リンク行列(どのページからどのページにリンクが出ているか、もしくはリンクをもらっているか。PageRank などページのランキングの計算に使う)、といったような行列を計算するとき、大規模行列だと計算量・記憶スペースともに膨大なので、事前にある程度計算しておけるのであれば、できるだけ小さくしておきたい(そして可能ならば精度も上げたい)、という手法である。

行列の圧縮には元の行列を A (m行n列)とすると A = USV^T というように3つに分解することが多いが、もっともよく知られているのは naoya さんが書かれているように、行列の特異値分解(Singular Value Decomposition: SVD)を行い、U と S と V を求める手法で、S は A の特異値が順に入っている対角行列となる。行列の情報量を圧縮したければ、上位 k 個の特異値を用いたりすると、情報は落ちるものの元の行列を近似することができる(情報が落ちたらマイナスかというと、ノイズを減らすスムージング効果もあったりするので、完全にマイナスとは言い切れない)。

これはたとえば検索だとクエリによらず事前に計算しておくことができるという利点があり、また数学的にもきれい(主成分分析、PCA も本質的には SVD しているのと一緒)なので、割と広く知られている、と思う(使われているかどうかは分からない。理由は以下に述べる)。ただこの手法には三つの問題点がある。

第一に、SVD は基本的に O(min(n^2 * m, n * m^2))かかる計算(対称行列だと O(m^3))で、数万エントリくらいまでならなんとかなるのだが、それを超えるとナイーブには計算できなくなる。まあ、こういうタスクの場合行列が疎行列であることが多いので、Lanczos method などを使って効率的に k 個の固有値を求めることもできなくはない(ただ、実際に計算するとなると、いつ計算が終了するのかの見積もりがしにくいという欠点はある)。また、Jacobi 法を用いると割と楽に分割して並列計算ができるようで、並列して計算することも可能であるが、数百万x数百万が普通だったりする(たとえば Mixi でもアカウント数は1,000万超えたそうだ)大規模行列の処理をしたいので、本質的にはこういう計算は避けたい。もちろん、LSI が目的であれば、LSI の確率版 pLSI は並列計算可能(実際 Google では並列計算しているようだ)なので、pLSI でいい、とも言える(せっかく元の行列が疎行列なのだから、疎行列である特徴をうまく利用したい、ということは言えると思うが)。

第二に、SVD をすると重要な次元から圧縮されていくのだが、これ圧縮された次元を人間が見ても、なんだろうこれ、と思うものがあったりする(クラスタリングでも人間がクラスタリングしたらまず考えつかないようなクラスタができることがあるのと同じ)。つまり、圧縮された結果の解釈が難しい。圧縮した状態のデータでも、人間が見て意味が分かると嬉しい。(こういうふうに、人間が見て分かると嬉しい、というのは、このタスクに限らず、機械学習の設定でよくある。生成されたモデルを見てもなんだか分からないけど精度がいいアルゴリズムよりは、中でなにをやっているのか分かって速度や精度もそこそこ、スケールするようなアルゴリズムのほうがいい)

第三に、SVD をすると確かに分解された U と S と V それぞれに意味があり、分解された U と V はそれぞれ巨大な密行列、S は小さい疎行列になるのだが、元々の A が疎行列の場合、U と V が密行列になるのは嬉しくない(スペースも取る)。U と V は疎行列のままでいてほしい(S はそもそも小さいので密行列でもいい)。

で、最近提案されているのが CUR 分解という分解法で、行列を3つに分解するのは SVD と同じなのだが、元々の行列 A から列をサンプリングして C を作る(そして R も同様に作る)ことで、上記3つの問題点を全てクリアする。サンプリングするので O(m^3) はかからないし、元々の A から列を抜き出してくるだけなので、人間が見たらどう圧縮されたのかが一目瞭然。そして、C と R は元々の行列 A が疎行列なら疎行列のまま扱うことができる。

直感的には、たとえば購買者-アイテム行列を例に取ると、全購買者の中からモニターになってくれる購買者を一定数選び、さらに全アイテムの中から消費行動を特徴付ける商品を一定数選び、全体の購買者とアイテムを近似する、という具合である。

サンプリングは一様にサンプリングする方法から、重みづけしてサンプリングする方法もあり、同じ列を何回もサンプリングして C を作るのは無駄なので同じ列は1回しか使わないようにする方法(CMD)、そして列の中には他の事例の線形結合で表すことができる事例があるのでそれはまとめて圧縮する方法(Colibri)もあり、一番最後の手法がいまのところの state-of-the-art (KDD 2008)らしい(近似することによってどれくらい性能が低下するかも下記の論文に書かれている)。

まとめると、用例ベースで行列を分解する、という手法が最近提案され、大規模な行列を近似で扱う際に役に立ちますよ、というお話。やっぱり SVD はかなり重たい処理なので、SVD が必要な計算をするときは全体の行列を扱えるサイズ(現在の PC だとせいぜい数万x数万が限界)に分割し、えいやと計算して結合する、といった近似手法が一般的なのかなと思うのだが、できるだけ SVD を使わないで行列の計算ができないか、と思って調べてみると、いろいろな手法があるのだなぁ、と知ったわけ。(行列の近似手法としては random projection というキーワードで検索するといろいろ出てくる)

2月下旬発売の

WEB+DB PRESS Vol.49

WEB+DB PRESS Vol.49

に id:kzk くんや id:tkng さん、O 野原くんが速習レコメンドエンジンという特集で SVD や LSH、pLSI について書いていると聞いたので、こういう方面に興味ある方はどうぞ。大規模データを扱う際のテクニック、研究の方ではこういうモデルがあるよ、という紹介まであるそうで、自分も大いに期待。

参考