最も単純な行列分解：特異値分解（SVD）とは？
行列分解の中でも最も単純なものと言えるのがSVDです。これは、次のように対象となる行列\(R\)を特異値と特異ベクトルと呼ばれる要素に分解するアルゴリズムです。
\(R \simeq O \Sigma Q ^\mathrm{T}\)
ここで、\(O\)（左特異ベクトル）は\(U\times n \)行列、\(Q\)（右特異ベクトル）は\(I\times n \)行列、特異値\(\Sigma\)は\(n\times n \)の対角行列です（\(n\)は \(1 \le n \le \min(U, I)\)を満たす整数）。
SVDは数値計算をする上で扱いやすい性質を満たすことから、多くのライブラリにおいて最適化された実装があります。詳細な性質やアルゴリズムについては、「特異値分解」などで検索するとたくさん情報を見つけることができますので、その情報を参照してください。
SVDの模式図
SVDの結果が満たす重要な性質として、SVDによって得られた\(R\)の近似\(R \simeq O \Sigma Q ^\mathrm{T}\)は、誤差関数
\(L_{\mathrm{SVD}}\)=\( \sum_{u=1} ^ U \sum_{i=1} ^ I (R_{ui} - (O \Sigma Q\ ^ \mathrm{T})_{ui} )^2\)
が最小化されている近似になっています (これはしばしば「フロベニウスノルム」を用いて、\(|| R - O \Sigma Q ^ \mathrm{T}||_F ^2\)と書かれます。)
また、\(n\)を大きくすれば近似\(R \simeq O \Sigma Q ^\mathrm{T}\)の精度は上がります（誤差関数は小さくなる）。特に\(n\) = \(\min(U, I)\)に達すると、完全な近似となり\(R\) = \(O \Sigma Q^\mathrm{T}\)が厳密に成立します。ただし実際には、ユーザー数\(U\)、アイテム数\(I\)は非常に多いため、\(n\)はある程度の近似の精度が保たれ、計算結果をメモリなどに保持できる程度の大きさに設定することが一般的です。
このような分解\(R \simeq O \Sigma Q ^\mathrm{T}\)が得られたら、
\(P\) = \(O \Sigma\)
とします。そして、
- ユーザー\(u\)のベクトル\(\vec{p}_u\)は\(P\)の第\(u\)行
- アイテム\(i\)のベクトル\(\vec{q}_i\)は\(Q\)の第\(i\)行
と定義すれば、特異値分解を用いた行列分解の完成です。
SVDによる行列分解の図解
なぜかというと、\(P\)、\(Q\)を用いると誤差関数は
\(L_{ \mathrm{SVD}}\)=\( \sum_{u=1} ^ U \sum_{i=1} ^ I (R_{ui} - \vec{p}_{u} \cdot \vec{q}_i) ^2\)
と書くことができます。加えて、誤差関数の値がある程度小さく、\(R\)の良い近似が得られているならば
- \(R_{ui}=1\)ならば\(\vec{p}_{u} \cdot \vec{q}_i\)は1に近い
- \(R_{ui}=0\)ならば\(\vec{p}_{u} \cdot \vec{q}_i\)は0に近い
となるからです。つまり接触しそうなユーザー／アイテムの組み合わせほど、それぞれに対応するベクトルの内積の値が大きい（1に近い）性質を持っており、このベクトルを用いて推薦をすることが可能です。
