IIR18章まとめ

18章は、行列の特異値分解とLSIについて。

LSI

クエリとドキュメントの類似度の計算は、以下のようなクエリ-ドキュメント行列が基本となっている。

通常、この行列は膨大であり、計算コストが高い。

よって、この行列をより小さな行列で近似することで計算量を下げたい。

LSI(Latent Semantic Indexing)とは、高次元の空間にある行列を射影により小さな行列で近似する手法。

近似には、SVD(行列の特異値分解)を使い、相互にに関連のありそうな索引語の次元を特定の次元に縮退させることで全体の次元を削減し、計算コストを下げられる。

また、"car" と "automobile" のような関連語を1つの次元であらわすことにより、再現率も向上させられ、一石二鳥である。

次元削減

以下の行列を考える。

ここで、固有値 λ1 = 30, λ2 = 20, λ3 = 1 である。

また、固有ベクトルを以下のように定義する。

すると、ベクトルは以下のように表せる。

このベクトルをSで写像する。

ここで、相対的に小さな固有値に対応する固有ベクトルの次元の影響が小さいので、それを無視すると、以下のようになる。

このように、相対的に影響の少ない次元を削除することができる。

SVD

以上のように次元を削減が可能である。

しかし、クエリ-ドキュメント行列は正方行列ではないので、固有値分解はできない。

SVDとは、そのように正方行列ではない場合でも、固有値絡みで行列を分解する手法である。

任意の行列 C に対して、以下の式が成立する。

• U…の固有ベクトルを列とする行列
• V…の固有ベクトルを列とする行列

ここで、σの値が小さなものを0にすることで、次元を下げることができる。