推薦系統之矩陣分解家族

07-13

推薦系統之矩陣分解家族

來自專欄社會化推薦那些事26 人贊了文章

摘要

本文主要圍繞推薦系統中經典的矩陣分解技術展開討論，先闡述推薦系統的必要性以及主流分類，隨後介紹推薦系統的兩大場景以及矩陣分解原理，最後開始介紹矩陣分解大家族，從最經典的FunkSVD開始講起，隨後介紹一些對於它的經典擴展（模型方面和數據層面），或者從另一個概率角度來解釋矩陣分解，或者提出一些其他的經典假設，以期給讀者一個更加清晰的認識，即矩陣分解作為推薦系統的經典，可以在此基礎上延伸出許多經典模型，只要讀者能夠對其足夠了解，相信有朝一日，你也可以創造出屬於自己滴經典！

前言

隨著大數據時代的飛速發展，信息逐漸呈現出過載狀態，推薦系統（Recommender System）作為近年來實現信息生產者與消費者之間利益均衡化的有效手段之一，越來越發揮著舉足輕重的作用。再者這是一個張揚個性的時代，人們對於個性化的追求、千人千面的嚮往愈來愈突出，誰能捕捉住用戶的個性化需求，誰就能在這個時代站住腳跟。現在人們不再單單依靠隨大流式的熱門推薦，而是基於每個用戶的行為記錄來細粒度的個性化的生成推薦內容。像今日頭條、抖音這樣的APP之所以如此之火，讓人們欲罷不能，無非是抓住了用戶想看什麼的心理，那麼如何才能抓住用戶的心理，那就需要推薦系統的幫助了。

眾所周知，推薦系統中最為主流與經典的技術之一是協同過濾技術（Collaborative Filtering），它是基於這樣的假設：用戶如果在過去對某些項目產生過興趣，那麼將來他很可能依然對其保持熱忱。其中協同過濾技術又可根據是否採用了機器學習思想建模的不同劃分為基於內存的協同過濾（Memory-based CF）與基於模型的協同過濾技術（Model-based CF）。其中基於模型的協同過濾技術中尤為矩陣分解（Matrix Factorization）技術最為普遍和流行，因為它的可擴展性極好並且易於實現，因此接下來我們將梳理下推薦系統中出現過的經典的矩陣分解方法。

矩陣分解家族

在介紹矩陣分解大家族之前，先讓我們明確下推薦系統的場景以及矩陣分解的原理。對於推薦系統來說存在兩大場景即評分預測（rating prediction）與Top-N推薦（item recommendation，item ranking）。評分預測場景主要用於評價網站，比如用戶給自己看過的電影評多少分（MovieLens），或者用戶給自己看過的書籍評價多少分（Douban）。其中矩陣分解技術主要應用於該場景。Top-N推薦場景主要用於購物網站或者一般拿不到顯式評分信息的網站，即通過用戶的隱式反饋信息來給用戶推薦一個可能感興趣的列表以供其參考。其中該場景為排序任務，因此需要排序模型來對其建模。因此，我們接下來更關心評分預測任務。

對於評分預測任務來說，我們通常將用戶和項目（以電影為例）表示為二維矩陣的形式，其中矩陣中的某個元素表示對應用戶對於相應項目的評分，1-5分表示喜歡的程度逐漸增加，？表示沒有過評分記錄。推薦系統評分預測任務可看做是一個矩陣補全（Matrix Completion）的任務，即基於矩陣中已有的數據（observed data）來填補矩陣中沒有產生過記錄的元素（unobserved data）。值得注意的是，這個矩陣是非常稀疏的（Sparse），稀疏度一般能達到90%以上，因此如何根據極少的觀測數據來較準確的預測未觀測數據一直以來都是推薦系統領域的關鍵問題。

其中，推薦系統的評分預測場景可看做是一個矩陣補全的遊戲，矩陣補全是推薦系統的任務，矩陣分解是其達到目的的手段。因此，矩陣分解是為了更好的完成矩陣補全任務（欲其補全，先其分解之）。之所以可以利用矩陣分解來完成矩陣補全的操作，那是因為基於這樣的假設：假設UI矩陣是低秩的，即在大千世界中，總會存在相似的人或物，即物以類聚，人以群分，然後我們可以利用兩個小矩陣相乘來還原它。

1、PureSVD

當然提到矩陣分解，人們首先想到的是數學中經典的SVD（奇異值）分解，在這我命名為PureSVD（傳統並經典著），直接上公式：

當然SVD分解的形式為3個矩陣相乘，左右兩個矩陣分別表示用戶/項目隱含因子矩陣，中間矩陣為奇異值矩陣並且是對角矩陣，每個元素滿足非負性，並且逐漸減小。因此我們可以只需要前 $k$ 個因子來表示它。

如果想運用SVD分解的話，有一個前提是要求矩陣是稠密的，即矩陣里的元素要非空，否則就不能運用SVD分解。很顯然我們的任務還不能用SVD，所以一般的做法是先用均值或者其他統計學方法來填充矩陣，然後再運用SVD分解降維。

2、FunkSVD

http://sifter.org/~simon/journal/20061211.html

剛才提到的PureSVD首先需要填充矩陣，然後再進行分解降維，同時由於需要求逆操作（複雜度O(n^3)），存在計算複雜度高的問題，所以後來Simon Funk提出了FunkSVD的方法，它不在將矩陣分解為3個矩陣，而是分解為2個低秩的用戶項目矩陣，同時降低了計算複雜度：

它借鑒線性回歸的思想，通過最小化觀察數據的平方來尋求最優的用戶和項目的隱含向量表示。同時為了避免過度擬合（Overfitting）觀測數據，又提出了帶有L2正則項的FunkSVD：

以上兩種最優化函數都可以通過梯度下降或者隨機梯度下降法來尋求最優解。

3、PMF

Salakhutdinov et al. Probabilistic matrix factorization. NIPS(2008): 1257-1264.

PMF是對於FunkSVD的概率解釋版本，它假設評分矩陣中的元素 $mathbf{R}_{ij}$ 是由用戶潛在偏好向量 $mathbf{U}_i$ 和物品潛在屬性向量 $mathbf{V}_j$ 的內積決定的，並且服從均值為 $mathbf{U}_i^Tmathbf{V}_j$ ，方差為 $sigma^2$ 的正態分布：

則觀測到的評分矩陣條件概率為：

同時，假設用戶偏好向量與物品偏好向量服從於均值都為0，方差分別為 $sigma^2_Umathbf{I}$ , $sigma^2_Vmathbf{I}$ 的正態分布：

根據貝葉斯公式，可以得出潛變數U,V的後驗概率為：

接著，等式兩邊取對數 $ln$ 後得到：

最後，經過推導，我們可以發現PMF確實是FunkSVD的概率解釋版本，它兩個的形式一樣一樣的。

註：為了方便讀者理解，在此舉例推導中間項 $N(U_i|0,sigma^2mathbf{I})$ ，將此項展開，帶入多維正態分布即可得到 $-frac{D}{2}ln(sigma^2_U)-frac{U_i^TU_i}{2sigma^2_U}+C$ 。推導如下：

4、BiasSVD

Koren et al. Matrix factorization techniques for recommender systems.Computer 42.8 (2009).

在FunkSVD提出來之後，陸續又提出了許多變形版本，其中相對流行的方法是BiasSVD，它是基於這樣的假設：某些用戶會自帶一些特質，比如天生願意給別人好評，心慈手軟，比較好說話，有的人就比較苛刻，總是評分不超過3分（5分滿分）；同時也有一些這樣的項目，一被生產便決定了它的地位，有的比較受人們歡迎，有的則被人嫌棄，這也正是提出用戶和項目偏置項的原因；項亮給出的解釋是：對於一個評分系統有些固有屬性和用戶物品無關，而用戶也有些屬性和物品無關，物品也有些屬性與用戶無關，具體的預測公式如下：

其中， $mu$ 為整個網站的平均評分，是真箇網站的基調； $b_u$ 為用戶的評分偏置，代表某個用戶的評分基調， $b_i$ 為項目的被評分偏置，代表某個項目的屬性基調。

5、SVD++

Koren Y. Factor in the neighbors: Scalable and accurate collaborative filtering[J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2010, 4(1): 1.

在用戶除了顯式評分外，隱式反饋信息同樣有助於用戶的偏好建模，因此隨後提出了SVD++。它是基於這樣的假設：用戶除了對於項目的顯式歷史評分記錄外，瀏覽記錄或者收藏列表等隱反饋信息同樣可以從側面一定程度上反映用戶的偏好，比如用戶對某個項目進行了收藏，可以從側面反映他對於這個項目感興趣，具體反映到預測公式為：

其中 $N(i)$ 為用戶 $i$ 所產生隱反饋行為的物品集合； $y_s$ 為隱藏的對於項目 $s$ 的個人喜好偏置，是一個我們所要學習的參數；至於 $|N(i)|^{-frac{1}{2}}$ 是一個經驗公式。

6、timeSVD

Koren et al. Collaborative filtering with temporal dynamics. Communications of the ACM 53.4 (2010): 89-97.

它是基於這樣的假設：用戶的興趣或者偏好不是一成不變的，而是隨著時間而動態演化。於是提出了timeSVD，其中用戶的和物品的偏置隨著時間而變化，同時用戶的隱含因子也隨著時間而動態改變，在此物品的隱含表示並未隨時間而變化（假設物品的屬性不會隨著時間而改變）。

其中， $t$ 為時間因子，表示不同的時間狀態。

7、NMF

Lee et al. Learning the parts of objects by non-negative matrix factorization. Nature 401.6755 (1999): 788.

這是一篇發表在Nature上的經典論文，谷歌學術顯示引用將近9k，它提出了一個假設：分解出來的小矩陣應該滿足非負約束。

因為在大部分方法中，原始矩陣 $mathbf{R}$ 被近似分解為兩個低秩矩陣 $mathbf{R}=mathbf{P}^Tmathbf{Q}$ 相乘的形式，這些方法的共同之處是，即使原始矩陣的元素都是非負的，也不能保證分解出的小矩陣都為非負，這就導致了推薦系統中經典的矩陣分解方法可以達到很好的預測性能，但不能做出像User-based CF那樣符合人們習慣的推薦解釋（即跟你品味相似的人也購買了此商品）。在數學意義上，分解出的結果是正是負都沒關係，只要保證還原後的矩陣元素非負並且誤差儘可能小即可，但負值元素往往在現實世界中是沒有任何意義的。比如圖像數據中不可能存在是負數的像素值，因為取值在0~255之間；在統計文檔的詞頻時，負值也是無法進行解釋的。因此提出帶有非負約束的矩陣分解是對於傳統的矩陣分解無法進行科學解釋做出的一個嘗試。它的公式如下：

其中， $mathbf{P}$ , $mathbf{Q}$ 兩個矩陣中的元素滿足非負約束。

8、WMF

Pan et al. One-class collaborative filtering. ICDM, 2008.
Hu et al. Collaborative filtering for implicit feedback datasets. ICDM, 2008.

對於矩陣分解來說，我們一般是處理的推薦系統中的評分預測任務，但同樣矩陣分解也可以用來進行Top-N的推薦，即根據隱式信息來預測用戶是否點擊某項目。你可以把他看做是二分類問題，即點或者不點。但這不是普通的二分類問題，因為在模型訓練的過程中負樣本並非都為真正的負樣本，可能是用戶根本沒見過該項目，何來喜不喜歡,沒準他看到後喜歡呢，即正樣本告訴我們作者喜歡的信息，但負樣本並不能告訴我們該用戶不喜歡。由於只存在正樣本，所以我們把只有正反饋的問題定義為one-class問題，即單類問題。對於單類問題，該作者提出了兩種解決策略，一種是加權的矩陣分解，另一種是負採樣技術。雖然只是加了一下權重，看起來比較naive，但在於當時的研究背景下，這一小步其實是推薦系統中的一大步。

對於單類問題的研究一直沒有停止過，雖然負採樣技術是啟發式的，即不用通過數據建模的方式來進行預測，但效果還是很好用的。最近幾年人們提出了基於模型的方法來處理這種單類問題，即從缺失數據中來進行建模，具體可參見這兩篇論文【Hernández-Lobato et al 2014，Liang et al 2016】。

10、LLORMA

Lee et al. Local low-rank matrix approximation.ICML. 2013.

經典的矩陣分解模型是假設整個用戶-項目矩陣（即UI矩陣）滿足低秩假設（即全局低秩假設），即在整個系統當中，用戶和項目總是滿足存在相似的某種模式，即物以類聚，人以群分。

這種假設固然有道理，但在當今大數據時代下，全局意義上的低秩假設似乎太強了，尤其是在數據量巨大的情況下（即用戶數與項目數都很多的系統當中），因此該論文推翻了全局意義上經典的全局低秩假設，它認為大千世界，林林總總，我們應該去尋找局部的低秩假設（即局部低秩假設）。首先根據某種相似測度來將整個大矩陣分為若干個小矩陣，每個小矩陣當中滿足某種相似度閾值，然後再在局部的小矩陣當中做低秩假設。這樣，全局的大矩陣可以由多個局部的小矩陣來加權組合構成，具體可參見該論文。

11、SRui

Ma Hao. An experimental study on implicit social recommendation. SIGIR, 2013.

雖然經典的矩陣分解方法已經可以到達比較好的預測性能了，但它固有的弊病仍然是躲不開的，即數據稀疏與冷啟動問題。為了緩解數據稀疏我們可以引入豐富的社交信息。即如果兩個用戶是朋友關係，那麼我們假設他們有相同的偏好，同時他們學得的用戶隱表示在向量空間應該有相近的距離。用戶維度如此，同理，項目維度亦可以利用此思路來約束項目隱表示。即如果兩個項目之間的關係較近，那麼在低維向量空間中的距離同樣也應該較小。這裡的項目關係是從UI矩陣中抽取出來的，論文中成為項目隱社交關係（其實項目維度跟社交沒啥關係）。具體公式如下：

其中， $s_{if}$ 表示用戶 $i$ 和用戶 $f$ 的社交相似度， $s_{jq}$ 表示項目 $j$ 與項目 $q$ 的隱社交相似度，在用戶維度和項目維度分別增加了平滑項約束，使得學得的隱特徵表示更加符合現實意義。

12、ConvMF

Kim et al. Convolutional matrix factorization for document context-aware recommendation. RecSys 2016.

當然矩陣分解的優點之一是可擴展性好，這當然不是吹的，比如16年的這篇文章就是將矩陣分解（MF）與圖像處理領域很火的卷積神經網路（CNN）做了完美結合。

矩陣分解作為協同過濾模型中經典的方法，性能當然沒的說。但它存在的數據稀疏與冷啟動問題一直以來都是它的痛點，因此結合外部豐富的信息成為了緩解上述問題的有效途徑。其中文本數據作為web中主流的數據形式成為了首選，並且對於文本的處理，大部分還是基於one-hot的表示，因此無法捕捉文檔中上下文的關鍵信息，於是作者將兩者做了結合，具體細節請參見論文，該公式如下：