Singular Value Decomposition / Latent semantic indexing を試す
IIR 18 章の SVD と LSI を R 言語で動かしてみた。IIR 18 章は id:sleepy_yoshi さんの日本語訳(18 Matrix decomposition and latent semantic indexing (pp.369-384) - 睡眠不足?!)にお世話になりました。ありがとうございます。
なお IIR 18 章には C_k の算出に関する間違いがあるので正しい方法は私の先生でもある id:n_shuyo さんのSVD/LSI の手触りチュートリアル - Mi manca qualche giovedi`? を参照してください。
まとめ
IIR 18 章の例 18.4 の単語文書行列に関して C_k を実際に計算しそれを利用し cosine similarity を計算した。rank k=3 が次元を減らしつつ良い結果を導くことが分かった。
準備
lsa パッケージをインストール。
> install.packages("lsa") > library(lsa)
SVD する
C を定義。
d_1 | d_2 | d_3 | d_4 | d_5 | d_6 | |
ship | 1 | 0 | 1 | 0 | 0 | 0 |
boat | 0 | 1 | 0 | 0 | 0 | 0 |
ocean | 1 | 1 | 0 | 0 | 0 | 0 |
voyage | 1 | 0 | 0 | 1 | 1 | 0 |
trip | 0 | 0 | 0 | 1 | 0 | 1 |
> (C <- matrix(c(1,0,1,1,0, 0,1,1,0,0, 1,0,0,0,0, 0,0,0,1,1, 0,0,0,1,0, 0,0,0,0,1), 5)); [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1 0 1 0 0 0 [2,] 0 1 0 0 0 0 [3,] 1 1 0 0 0 0 [4,] 1 0 0 1 1 0 [5,] 0 0 0 1 0 1
svd 関数で分解。やりたいことに集中させてくれる R は素晴らしい。
> (d <- svd(C)) $d [1] 2.1625010 1.5943824 1.2752903 1.0000000 0.3939153 $u [,1] [,2] [,3] [,4] [,5] [1,] 0.4403475 -0.2961744 -0.5694976 5.773503e-01 -0.24640214 [2,] 0.1293463 -0.3314507 0.5870217 -3.330669e-16 -0.72719701 [3,] 0.4755303 -0.5111152 0.3676900 -3.330669e-16 0.61435841 [4,] 0.7030203 0.3505724 -0.1549059 -5.773503e-01 -0.15978815 [5,] 0.2626728 0.6467468 0.4145917 5.773503e-01 0.08661399 $v [,1] [,2] [,3] [,4] [,5] [1,] 0.7486230 -0.2864540 -0.2797116 -2.220446e-16 0.5284591 [2,] 0.2797116 -0.5284591 0.7486230 -3.330669e-16 -0.2864540 [3,] 0.2036288 -0.1857612 -0.4465631 5.773503e-01 -0.6255207 [4,] 0.4465631 0.6255207 0.2036288 1.942890e-16 -0.1857612 [5,] 0.3250960 0.2198798 -0.1214672 -5.773503e-01 -0.4056409 [6,] 0.1214672 0.4056409 0.3250960 5.773503e-01 0.2198798
定義の通り掛けると元の C に戻ることを確認。
> (d$u %*% diag(d$d) %*% t(d$v)) [,1] [,2] [,3] [,4] [,5] [1,] 1.000000e+00 2.428613e-16 1.000000e+00 -5.377643e-16 -1.873501e-16 [2,] -6.661338e-16 1.000000e+00 -2.775558e-17 3.122502e-16 8.326673e-17 [3,] 1.000000e+00 1.000000e+00 -3.608225e-16 6.591949e-16 1.526557e-16 [4,] 1.000000e+00 -5.551115e-17 -1.151856e-15 1.000000e+00 1.000000e+00 [5,] -3.330669e-16 -7.285839e-17 -3.712308e-16 1.000000e+00 3.295975e-17 [,6] [1,] -1.838807e-16 [2,] 9.714451e-17 [3,] 4.787837e-16 [4,] 5.551115e-17 [5,] 1.000000e+00
LSI
C を分解した Σ の特異値を k 個残してあとは切り捨てる。k = 2, 3, 4 とする。
> new_d_2 <- diag(c(d$d[1:2], 0, 0, 0)) > new_d_3 <- diag(c(d$d[1:3], 0, 0)) > new_d_4 <- diag(c(d$d[1:4], 0))
それぞれ C_k を作る。次元が減って k 行以上は 0 になっていることに注意。
> (C_2 <- (new_d_2 %*% t(d$v))) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1.6188981 0.6048766 0.4403475 0.9656932 0.7030203 0.2626728 [2,] -0.4567172 -0.8425659 -0.2961744 0.9973192 0.3505724 0.6467468 [3,] 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 [4,] 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 [5,] 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 > (C_3 <- (new_d_3 %*% t(d$v))) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1.6188981 0.6048766 0.4403475 0.9656932 0.7030203 0.2626728 [2,] -0.4567172 -0.8425659 -0.2961744 0.9973192 0.3505724 0.6467468 [3,] -0.3567135 0.9547117 -0.5694976 0.2596858 -0.1549059 0.4145917 [4,] 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 [5,] 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 0.0000000 > (C_4 <- (new_d_4 %*% t(d$v))) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1.618898e+00 6.048766e-01 0.4403475 9.656932e-01 0.7030203 0.2626728 [2,] -4.567172e-01 -8.425659e-01 -0.2961744 9.973192e-01 0.3505724 0.6467468 [3,] -3.567135e-01 9.547117e-01 -0.5694976 2.596858e-01 -0.1549059 0.4145917 [4,] -2.220446e-16 -3.330669e-16 0.5773503 1.942890e-16 -0.5773503 0.5773503 [5,] 0.000000e+00 0.000000e+00 0.0000000 0.000000e+00 0.0000000 0.0000000
Cosine Similarity
オリジナルの C の文書同士の Cosine Similarity は cosine 関数で以下のように計算できる。
> cosine(C) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1.0000000 0.4082483 0.5773503 0.4082483 0.5773503 0.0000000 [2,] 0.4082483 1.0000000 0.0000000 0.0000000 0.0000000 0.0000000 [3,] 0.5773503 0.0000000 1.0000000 0.0000000 0.0000000 0.0000000 [4,] 0.4082483 0.0000000 0.0000000 1.0000000 0.7071068 0.7071068 [5,] 0.5773503 0.0000000 0.0000000 0.7071068 1.0000000 0.0000000 [6,] 0.0000000 0.0000000 0.0000000 0.7071068 0.0000000 1.0000000
例えば文書 1 との類似を見れば 1 と 6 は全然似てない。1 と 3 は比較的似ているなどが観察される。
さてここで C を C_k で近似したことにより Cosine Similarity がどのように変わったかを観察したい。このために文書 1 の類似度に関して以下の性質が保持されているかで判断する。
- 1 と 6 は全く似ていない
- 1 と 3、1 と 5 の似ている度合いは同じくらいである
- 1 と 2、1 と 4 の似ている度合いは同じくらいである
C_2 ~ C_4 まで Cosine Similarity を計算してみる。
C_2 では上記の性質は保持されていない。ちょっと粗すぎる印象。
> cosine(C_2) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1.0000000 0.7818374 0.9501362 0.4744320 0.7401185 0.1105958 [2,] 0.7818374 1.0000000 0.9372758 -0.1779180 0.1593750 -0.5331897 [3,] 0.9501362 0.9372758 1.0000000 0.1762690 0.4935115 -0.2048412 [4,] 0.4744320 -0.1779180 0.1762690 1.0000000 0.9431117 0.9273621 [5,] 0.7401185 0.1593750 0.4935115 0.9431117 1.0000000 0.7502052 [6,] 0.1105958 -0.5331897 -0.2048412 0.9273621 0.7502052 1.0000000
C_3 ではおおよそ性質が保たれていて良い感じ。
> cosine(C_3) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1.00000000 0.422234827 0.78542247 0.418053171 0.75047307 -0.012915290 [2,] 0.42223483 1.000000000 -0.02533697 -0.004147195 -0.01597348 0.008539267 [3,] 0.78542247 -0.025336968 1.00000000 -0.016400234 0.47162423 -0.493658248 [4,] 0.41805317 -0.004147195 -0.01640023 1.000000000 0.87394629 0.877635135 [5,] 0.75047307 -0.015973480 0.47162423 0.873946286 1.00000000 0.534041137 [6,] -0.01291529 0.008539267 -0.49365825 0.877635135 0.53404114 1.000000000
C_4 では更に良くなってる。
> cosine(C_4) [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1.00000000 0.422234827 0.63084657 0.418053171 0.60873171 -0.010525344 [2,] 0.42223483 1.000000000 -0.02035050 -0.004147195 -0.01295658 0.006959094 [3,] 0.63084657 -0.020350500 1.00000000 -0.013172569 -0.04115346 0.022103894 [4,] 0.41805317 -0.004147195 -0.01317257 1.000000000 0.70888461 0.715230692 [5,] 0.60873171 -0.012956579 -0.04115346 0.708884615 1.00000000 0.014072915 [6,] -0.01052534 0.006959094 0.02210389 0.715230692 0.01407292 1.000000000
といわけでざっと観察した結果 k=3 あたりがよさそうに見える。