特異値分解とLSIの意味

2012/3/24追記

わかりにくい部分や間違っている部分を修正した上でもっとちゃんとした解説エントリー書きました
潜在的意味インデキシング（LSI）徹底入門
——————

前々から特異値分解やLSI(Latent Semantic Indexing)による次元削減の意味について疑問に感じていたので自分なりに考えてみました．
誤りも多々あるかと思いますが…

特異値分解

特異値分解は Aというランクが r の m x n 行列を次のような3つの行列に分解します．

\[A = U \Sigma V^T\]

ここで，U は m x r の列直交行列，V は n x r の列直交行列，Σは対角要素に特異値を降順に並べた r x r の対角行列です．
※定義の仕方によってはU: m x m 行列，V: n x n 行列，Σ: m x n 行列とすることもあります

A のランクが r なので，A には冗長な要素があるということになります．
例えば，m 個の n 次元データを行に並べたものが A であった場合，各データは r 次元のデータで表現できることになります．
その場合は両辺に右からVを掛けて

\[AV = U\Sigma\]

とすれば m 個の r 次元データに変換することが可能です．

もっとわかりやすく書き下すと，

\[A[\bm{v}_1, \bm{v}_2, \cdots, \bm{v}_r] = [\sigma_1\mathbf{u}_1, \sigma_2\mathbf{u}_2, \cdots, \sigma_r\mathbf{u}_r]\]

となります．
※\(\bm{v}_i,\bm{u}_i\)はV, Uのi列目の列ベクトル，\(\sigma_j\)はj番目に大きな特異値を表します．

右辺を見れば，元々独立なベクトルを定数倍しているだけであることから明らかなように，各列ベクトルは独立です．

おそらくこの変換が他の変換に比べて嬉しいところは，r 次元データに変換できるだけでなく，ユークリッドノルムの大きなベクトル，つまりデータを構成するのに大きな影響を与えるベクトルから順に列ベクトルに割り当てられることです．¹
i 番目の列ベクトルのユークリッドノルムは\(\sigma_i^2\)になりますからね．
※データを構成するのに大きな影響を与えるデータというのはデータの識別に有効なデータとは限りません

LSI (Latent Semantic Indexing)

LSIは特異値分解を利用した次元圧縮方法です．
次元圧縮といっても2通りの方法があって，A のランク数を減らす方法と A の次元数を減らす方法とがあります．

ランク削減

A が特異値分解によって

\[A = U \Sigma V^T\]

のように分解されることは上述したとおりです．
ここで，分解した各行列のk+1列以降を削除した行列\(U_k, \Sigma_k, V_k\)を考えると，

\[A \simeq A_k \equiv U_k \Sigma_k V^T_k\]

と近似できます．これでランクがrからkに削減されます．
この近似行列は，ランクが k の m x n 行列の中でもフロベニウスノルムという観点で最も A に近い行列だそうです．

私の解釈として，ランク削減は機械学習でいう過学習の部分を取り除くものだと思っています．
ランクが多いあまりにデータを表現できすぎて，本来似ているデータも全然違ったものと表現されてしまう．
そこで，重要度の低い情報を削減することで，本来似ているデータの類似度を上げることができる．
そんな感じかと思います．

全然違ったデータを分けるために使われる情報というのは重要度が高い情報のはずです．
本来似ているデータを分けるために使われる情報というのはそれに比べて重要度が低くなるということでしょう．

次元削減

こちらはいたってシンプルで，

\[U^T_kA\]

とすることでデータの次元数をkまで減らします．
これは元々の特徴量と違う低次元の特徴量を用意することを意味しています．

具体例を挙げると，
A が文書・単語行列(行が文書で列が単語)の場合，各文書に関する特徴量は各単語の情報になります．単語は n 種類あります．
しかしこれらの単語は k 種類の特徴(素性)にまとめて考えることができます．
その特徴を単語の「潜在的意味」として，単語という軸を潜在的意味という軸に変換しましょう．
次元削減の意味はそんな感じかと思います．

ここで注意したいのは，特異値分解で説明したように，特徴はデータを構成するのに影響の大きいものから順に割り当てられるということです．識別に有効かどうかは別問題です．
例えば，新聞記事を政治, 経済. 芸能・スポーツに分けたいとしても，最初に割り当てられる特徴は「日常的によく使われる言葉」のような，どのジャンルでも頻繁に表れる潜在的意味になるかもしれません．
※なので単語頻度ではなくてTF-IDF値などにしてからLSIを適用するのが一般的のようです

LSIの次元削減にどうして特異値分解が使われるかですが，

• A は n 個の列ベクトルから成る．（単語という軸）
• A のランクは r → A は r 個の列ベクトルで表現できる！（それはきっと潜在的意味という軸）
• どうすれば r 個の列ベクトルで表現できるか？ → 行列を掛けて線形変換しよう
• どんな行列を掛けるといいか？ → 特異値分解で出てきたVだと重要度の高い列ベクトルから順に並ぶし，距離関係も保存されるよ！
• 次元を k まで減らしたい → 重要度の低いベクトルを削ろう！

ということかなぁと思います．