SVD 實作推薦系統

Matrix Factorization and Singular Value Decomposition

為了具體了解推薦系統是一個怎麼樣的概念，先假設我們想做一個線上影音串流服務，作為經營者，對蒐集到的使用者對電影評分的資料，可能需要了解幾個問題，以提供更好的服務：

我們能從資料中知道使用者會想收看什麼電影嗎？
使用者是喜歡這些電影的什麼地方呢？
他們可能會希望被推薦什麼類型的電影呢？

這些問題，都可以由 Singular value decomposition (SVD) 解決。SVD是一種可以找出代表這些電影、使用者的重要喜好特質的方法。在影音串流業者的例子裡，利用這些特質，我們就可以根據使用者的品味推薦他們可能會喜歡的電影。

— 基本概念 —

有 m 個使用者和 n 個電影的評分矩陣 R，可以用線性代數找到對角線特徵矩陣 S(m * n)，把 rating 拆成 U (m * m) 代表使用個對每個特徵的喜好和 I (n * n)，兩個 orthogonal 矩陣使得 :

而 S 矩陣對角線上的值就代表 U 的某一行和 I 某一行相乘的重要程度。

對角線矩陣 S

因為 S 是 m * n 的長方形對角線矩陣，所以會有一部分的行或是列數都是 0。留下 S 有值的子句陣 (r * r，因為不知道是m 或 n誰較大，所以假設一個新變數 r)，並把 U、I其中會乘以 0 的行拿掉，得到新的 S、U 和 I ，如下圖：

Figure 1. matrix factorization

新的對角線矩陣 S 就是 r 個特徵的重要程度。U[u] 和 I[i]則是為長度為 r 的數值陣列，分別代表使用者 u 對第 1 ~ r 個 feature 的喜好程度和物品 i 對第 1 ~ r 個 feature 的相關程度。因為 S 矩陣還是很大，所以我們要來降維了！就可以降維了！只留下 S 中最大的 k 個值(下圖紅筐內)，對角線上的其他值都歸 0。因為 U[k+1] 和 I[k+1] 之後的行都會乘上 0 可以忽略。所以我們就可以把 U, I 壓縮乘 m * k 和 n * r，如下圖：

Figure 2. the k largest singular values, items’ features 為 I 的轉置矩陣

這就是利用 SVD 降維的方法。降維後，因為已經選出數量相對很小的 k 特徵，所以我們可以當作這 k 個特徵都相當重要，所以把對角線的k的值都設為 1。所以當要預測使用者 u 是否喜歡電影 i 的時候，我們只要把 U[u] 和 I[i] 兩個向量做內積就可以了。

Figure 3. prediction = U[u]・I[i]^T, items’ features 為 I 的轉置矩陣，預測結果就是將使用者對每個特徵的喜好程度乘上物品對每個特徵的相關程度的總和，如果使用者 u 很喜歡 feature f 而且物品 i 和 feature f 相關程度很高，將U[u], I[i] 內積就會得到很大的值，也代表使用者 u 會給物品 i 很高的評分。

在這樣的狀況下，可以大量減少預測的時間，而且也會讓模型更 robust (比較不會受到離群值分享)。在實務上，較小的 k 的表現通常會比用完整的 r 個特徵表現得更好。例如電影，其實只要十幾個特徵就能很好的代表一部電影，過多的特徵反而讓模型受到一些不重要的特徵的影響。

然而用線性代數的方法有一些困難：

1. 要處理缺失值 (如果有完整的 rating， 我們直接用就好 XD)
2. 算得非常慢

所以就有用隨機梯度下降 (stochastic gradient descent) 最小化均方根誤差 (root-mean-square error, RMSE) 來求 SVD的方法 (FunkSVD)，來改善用這些缺點。不過用這個方法要注意，因為是用 gradient descent 所以 U, I 就不能保證是 orthogonal 了。

— FunkSVD 演算法與實作—

預測使用者 u 對物品 i 的喜好程度(預測的評分)可以用下列表示 ：

score formula, Sigma的部分其實就是 U[u] 和 轉置後的 I[i] 的內積(如 Figure 3)

Funk SVD 是一種用迭代求出近似的 SVD的方法，取代原本用整個矩陣去計算 eigenvalue 的方法，因此可以較快速的計算出 U 和 I，也不用處理缺失值。然而，在這樣的情況下將 U 和 I 轉置內積就不會是原本的評分矩陣，而是近似原本評分的預測評分矩陣 R_hat (m * n)，R_hat[u][i] 代表模型預測使用者 u 對物品 i 的評分。

在訓練的時候，每次更新都是對一筆評分(使用者 u 給物品 i 的分數 r_ui)用 gradient descent 最小化預測分數(r_ui_hat)與實際分數(r_ui)的 RMSE 來更新 U[u](第 u 個 User 對每個 feature 的喜好) 和 I[i](第 i 個 Item 跟每個 feature 的相關程度)，和b[u][i] (使用者 u 對物品 i 的 bias)。不過由於：

1. the square root is monotonic
2. 一直都用同一個 dataset，所以不用取平均

我們可以改成 minimize SSE (sum of squared error)。

theta -> theta - gradient(theta)

下面以 R[u][i] (User u 對 Item i 的 rating) 更新 U[i]作為例子，首先要算 gradient：

Error 可以寫成上述的式子，其中 s(u, i) 是預測的 User u 對 Item i 的 ranking，加總每個 feature 把 User 的喜好程度和 Item 相關程度。然後我們可以開始計算對每個 feature f' 的微分 (一次 update 一個 feature)。

真實評分(r_ui)和 bias 都跟 U 無關，微分完只會剩下

其中對 feature f' 有關的那項，結果就是

所以每一次更新 U[u][f] 可以寫成：

U[u][f] -> Uif + lr * (loss * I[i][f])

完整的每次 update：

for u, i, r in rating:
    for f in features:
        U[u][f] -> Uif + lr * (loss * I[i][f])
        I[i][f] -> Iif + lr * (loss * U[u][f])

加上 L2 regularization 可以寫成： (rr 為 regularization rate)

加上 regularization 的 user 的 error

for u, i, r in rating:
    for f in features:
        U[u][f] -> Uif + lr * (loss * I[i][f] - rr * U[u][f])
        I[i][f] -> Iif + lr * (loss * U[u][f] - rr * I[i][f])

— 結果 —

Matching Results and Movie Metadata

這張圖用 Kaggle 上的 The Movies Dataset 訓練的結果。將已知 User 21 評分較高的電影 (rating ≥ 4) ，和預測 User 21 評分前五名電影中的類別拿出來比對可以發現：雖然在訓練的時候，我們只知道使用者給每部電影所評的分數，但是從結果看來，即使不知道電影本身的資訊，仍然可以利用 SVD 找到類型相似的電影推薦給使用者。

— 總結 —

利用 gradient descent 雖然無法讓 U, I 保有原本的性質(orthogonal)，但是可以剩下很多時間讓 matrix factorization 運用實際的例子上。另外也可以簡單地加進新的 User。但是現在網站上的資訊越來越複雜，不在只用 matrix factorization ，而是在加入不同 model 像是 Factorization Machines、GPMF 的 hybrid recommender。

— 完整程式—

Github: https://github.com/leafinity/gradient_dscent_svd

— 參考資料 —

[1] Coursera: Matrix Factorization and Advanced Techniques by University of Minnesota

[2] Surprise document: Matrix Factorization-based algorithms

[3] Wiki: Matrix factorization (recommender systems)