AI | 推薦系統之協同過濾的前世今生

什么是協同過濾

協同過濾的分類

• 基于鄰域的方法

• 隱語義模型

• 基于圖的隨機游走方法

      PageRank

• 基于表示學習的模型

• 基于匹配方法學習的模型

傳統的協同過濾算法

基于鄰域的方法

相似度

1. Jaccard系數：用于計算兩個集合之間的相似度，比較適合隱式反饋類型的用戶行為。

2. Cosine相似度：用向量空間中兩個向量夾角的余弦值作為衡量兩個個體間差異的大小。余弦值越接近1，就表明夾角越接近0度，也就是兩個向量越相似。

3. Pearson相關性系數：是衡量向量相似度的一種方法。輸出范圍為[-1, +1]， 0代表無相關性，負值為負相關，正值為正相關。

基于用戶的協同過濾

基于用戶的協同過濾符合人們直覺上的思想，但是也存在以下缺陷：

（1）當用戶數遠大于物品數，用戶相似度矩陣的開銷會特別大。

（2）當用戶行為過于稀疏時，找到相似用戶的準確度是特別低的。

（3）解釋性不強。

基于物品的協同過濾

該算法認為：物品A和物品B具有很大的相似度是因為喜歡物品A的用戶大都也喜歡物品B。

基于物品的協同過濾的解釋性強（討論的是物品的相似性），但也存在著一些缺陷：

（1）當物品數遠大于用戶數，物品相似度矩陣的開銷會特別大。

（2）當有新物品時，沒有辦法在不離線更新物品相似度表的情況下將新物品推薦給用戶；

總結

對于基于鄰近的方法，雖然其解釋性較強，但是它并不具有較強的泛化能力。處理稀疏向量的能力弱。因此為了解決這個問題，矩陣分解技術被提出。

隱語義模型

矩陣分解

矩陣分解引入了一個隱向量（latent vector）的概念，通過從物品評分模式中推斷出的隱向量來表征物品和用戶。隱向量，類似于NLP中的Word2vec技術，也就是后來深度學習中的Embedding向量。隱向量的不同的因子可能表示不同的具體含義，對于電影來說，發現的因素可能會衡量明顯的維度，例如喜劇與戲劇，動作量或對兒童的定向；不太明確的尺寸，例如角色發展的深度或古怪程度；亦或者是完全無法解釋的尺寸。對于用戶來說，每個因素都會衡量用戶對在相應電影的喜歡程度。

適用于推薦系統的矩陣分解的主要方法有兩種：奇異值分解（Singular Value Decomposition）和梯度下降（Gradient Descent）。

• 奇異值分解（SVD）

以上等于求解一個最優化問題：

但使用SVD方法存在一些缺陷：

1. 奇異值分解要求原始的共現矩陣是稠密的。然而現實中用戶-物品矩陣非常稀疏，這與奇異值分解的應用條件相悖。如果應用，就必須對確實元素進行填充，如填充0。這樣缺失的數據和所觀測的數據具有相同的權重。
2. 無法進行正則化，容易過擬合。
3. 計算復雜度高。

因此傳統的奇異值分解也并不適合大規模稀疏矩陣的矩陣分解問題。因此梯度下降法成為了進行矩陣分解的主要方法。

• 梯度下降法

梯度下降法通常是用來求解無約束最優化問題的一種最常用方法，是一種迭代算法。

最基礎的模型為：

其中為用戶隱向量（user latent vector），為物品隱向量（item latent vector）。

損失函數為：

其中為正則化參數。

MF主要分為兩步：

1. 將用戶和物品都表示為隱向量。
2. 使用內積（inner product）作為用戶和物品之間的交互函數，結果代表為用戶對物品的偏好程度。

然后使用梯度下降法對其進行優化，同時可以加入正則化來降低模型的過擬合。

• SVD++

2008年，Korean等人[3]提出的SVD++模型。SVD++融合了MF和FISM[4]的優勢，直接將Implicit數據反饋到模型中，優化了對用戶的表示：

其中表示用戶和物品的偏置，分別表示用戶、物品的隱向量，表示用戶對所有物品的隱式偏好。

• 加入額外信息

2009年，koren對矩陣分解模型進行總的概括和擴展[5]，除了基礎的模型，主要加入了一些額外信息：

（1）添加偏置（adding biaes）：雖然基本的矩陣分解可以捕獲用戶和物品之間的交互，但是，觀察到的許多評分變化是由于與用戶或物品相關的影響（稱為偏差）所致，而與任何交互無關。

因此單純用內積的交互來解釋一個評分值是比較粗糙的。因此，使用偏置來解釋用戶/物品的自身影響：

其中被定義為總平均評分（例如單個用戶對所有電影的平均評分），參數和分別表示物品和用戶的偏置，將偏置加入最終的評分中：

評分被分解為四項：總平均得分，物品偏置，用戶偏置和物品用戶的交互。

（2）額外的輸入源（additionaL input sources）：推薦系統總會面臨一個冷啟動問題，一個緩解這個問題的方案是添加額外的用戶信息源。推薦系統可以使用隱式反饋來深入了解用戶的偏好。實際上，無論用戶是否愿意提供明確的評分，他們都可以收集行為信息。零售商除了可以提供客戶的評價外，還可以使用其客戶的購買或瀏覽歷史記錄來了解其趨勢。

簡單起見，定義一個來表示用戶隱式偏好的物品集。對于物品關聯一個向量(等于對每一個物品的隱式偏好做一個one-hot編碼）。因此，一個用戶的偏愛對于在中的物品來說可以形容為一個向量：

歸一化后，

另一個信息源是用戶屬性，定義一個布爾屬性來表示用戶相關的信息，如性別、年齡、組群、所在地的郵編、收入水平等，對于每一個屬性可以用一個向量表示，，一個用戶的所有屬性表示為：

矩陣分解模型整合輸入源，最后的評分形式為：

（3）時間的動態性（temporaL dynamics）：隨著新選擇的出現，物品的感知度和受歡迎度會不斷變化。同樣，用戶的喜好也在不斷發展，導致他們重新定義了品味。矩陣分解方法非常適合于對時間效應進行建模，從而可以顯著提高準確性。將評分分解為不同的項可以使系統分別處理不同的時間方面。

一個評分項中隨著時間的改變發生變化的有：物品偏置，用戶偏置以及用戶偏好。最終評分形式可以變為：

• 矩陣分解技術總結

矩陣分解有很多優點：

1. 泛化能力強。在一定程度上解決了數據稀疏問題。
2. 空間復雜度低。不需要存儲用戶相似或物品相似矩陣，只需存儲用戶和物品的隱向量。空間復雜度由降低到級別。
3. 更好的擴展性和靈活性。矩陣分解最后得到用戶和物品隱向量，這其實與深度學習中的Embedding思想不謀而合，因此矩陣分解的覺果非常便于與其他特征進行組合和拼接。

但矩陣分解也存在一定的局限性。總的來說應該是整個協同過濾模型的局限性，無法加入用戶、物品屬性、上下文特征等邊信息，這是的喪失了很多有效信息，無法進行有效的推薦。

基于圖的隨機游走方法

PageRank

• 二部圖

例如有一個用戶-商品矩陣，將其轉換為二部圖。

其中，未打分的地方“-”用0表示。

在推薦系統中，其最終的目的是為用戶Ui 推薦相關的商品，此時，對于用戶Ui ，需要計算商品列表{D1 ，D2 ，...，D5 }中的商品對其重要性程度，并根據重要性程度生成最終的推薦列表。PageRank算法是用于處理圖上的重要性排名的算法。

• PageRank算法概念

PageRank算法，即網頁排名算法，是由佩奇和布林在1997年提出來的鏈接分析算法。PageRank是用來標識網頁的等級、重 要性的一種方法，是衡量一個網頁的重要指標。

網頁的鏈接分析可以抽象成圖模型，如下所示。

對于某個網頁的PageRank的計算是基于以下兩個假設:

數量假設。在 Web 圖模型中，如果一個頁面節點接收到的其他網頁指向的鏈接數量越多，那么這個頁面就越重要。即: 鏈接到網頁 A 的鏈接數越多，網頁A越重要。

質量假設。指向頁面 A 的入鏈的質量不同，質量高的頁面會通過鏈接向其他的頁面傳遞更多的權重，所以越是質量高的 頁面指向頁面 A，則頁面 A 越重要。即:鏈接到網頁A的原網頁越重要，則網頁A也會越重要。

PageRank算法很好地 組合了這兩個假設，使得對網頁的重要性評價變得更加準確。

• 計算算法

利用PageRank算法計算節點的過程分別為：1.將有向圖轉換成圖的鄰接矩陣M;2.計算出鏈接概率矩陣;3.計算概率轉移矩陣;4.修改概率轉移矩陣;5.迭代求解PageRank值。

對于上述的PageRank算法，其計算公式可以表示為:

其中，PR(i)表示的是圖中i節點的PageRank值，α 表示轉移概率(通常取0.85)，N表示的是網頁的總數，in(i)表示的是指向網頁i的網 頁集合，out(j)表示的是網頁 j指向的網頁集合。

基于深度學習的協同過濾

基于表示學習的模型

用戶和物品分別通過神經網絡生成各自的Embedding向量，即表示向量。將其作為中間產物，然后再通過內積等交互函數得到匹配分數，進行排序推薦。

【注】：Embedding向量學習與得到匹配分數的學習是分開的。

AutoRec

DeepMF

基于匹配方法學習的模型

是一個端到端的模型。

NCF

ONCF

總結

參考文獻

[2]: 項亮.推薦系統實戰[M].北京：人民郵電出版社，2012.

[3]: Koren Y. Factorization meets the neighborhood: a multifaceted collaborative filtering model[C]//Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining. 2008: 426-434. 

[4]: Kabbur S, Ning X, Karypis G. Fism: factored item similarity models for top-n recommender systems[C]//Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. 2013: 659-667. 

[5]: Sedhain S, Menon A K, Sanner S, et al. Autorec: Autoencoders meet collaborative filtering[C]//Proceedings of the 24th international conference on World Wide Web. 2015: 111-112. 

[6]: Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 42(8): 30-37. 

[7]: He X, Liao L, Zhang H, et al. Neural collaborative filtering[C]//Proceedings of the 26th international conference on world wide web. 2017: 173-182. 

[8]: He X, Du X, Wang X, et al. Outer product-based neural collaborative filtering[J]. arXiv preprint arXiv:1808.03912, 2018.