『壹』 推薦系統論文閱讀（二十三)-神經圖協同過濾NGCF
論文：
論文題目：《Neural Graph Collaborative Filtering》
論文地址： https://arxiv.org/pdf/1905.08108.pdf
本論文是關於圖結構的協同過濾演算法，在原始的矩陣分解和基於深度學習的方法中，通常是通過映射描述用戶（或物品）的現有特徵（例如ID和屬性）來獲得用戶（或物品）的嵌入。從而利用user和item的embedding進行協同召回。但是作者認為這種方法的固有缺點是：在user與item的interaction數據中潛伏的 協作信號（collaborative signal） 未在嵌入過程中進行編碼。這樣，所得的嵌入可能不足以捕獲協同過濾效果。
讓我們一起來看一下本論文是怎麼利用數據中潛伏的協作信號的吧。
推薦演算法被廣泛的運用在各個領域中，在電商領域，社交媒體，廣告等領域都發揮著至關重要的作用。推薦系統的核心內容就是根據用戶以前的購買和點擊行為來評估用戶對一個物品的喜愛程度，從而針對每個用戶進行個性化推薦。協同過濾演算法認為歷史行為相似的用戶之間的興趣是相同的，所以給用戶推薦的是同類型用戶的愛好，也就是UserCF，而ItemCF給用戶推薦的是跟歷史行為相近的物品。
傳統的協同過濾方法要麼是基於矩陣分解，要麼是基於深度學習的，這兩種方法都忽略了一個非常關鍵的信息---user和item交互的協作信號，該信號隱藏在user和item的交互過程中。原始的協同過濾方法忽略了這種信息，所以在進行user 和 item representation時就不足以較好的進行embedding。
本論文通過將用戶項交互（更具體地說是二分圖結構）集成到embedding過程中，開發了一個新的推薦框架神經圖協同過濾（NGCF），該框架通過在其上傳播embedding來利用user-item圖結構。這種方法在用戶項目圖中進行高階連通性的表達建模，從而以顯式方式將協作信號有效地注入到embedding過程中。
在介紹模型之前先來講解一下什麼是useritem interaction以及什麼是高階的useritem interaction。
我們先看左邊的圖，這個圖就是useritem interaction，u1是我們待推薦的用戶，用雙圓圈表示，他交互過的物品有i1，i2，i3。在看右邊這個樹形結構的圖，這個圖是u1的高階interaction圖，注意只有l > 1的才是u1的高階連接。觀察到，這么一條路徑，u1 ← i2 ← u2，指示u1和u2之間的行為相似性，因為兩個用戶都已與i2進行了交互。而另一條更長的路徑，u1←i2←u2←i4暗示u1可能會點擊i4，因為他的相似用戶u2之前已經購買過i4。另一方面，用戶u1在l = 3這一層會更傾向於i4而不是i5，理由是i4到u1有兩條路徑而i5隻有一條。
當然這種樹結構是不可能通過構建真正的樹節點來表示的，因為樹模型比較復雜，而且結構很大，沒法對每個用戶構建一個樹，這樣工作量太大了。那麼怎麼設計模型結構可以達到跟這個high-order connectivity的效果呢，這個就要運用到神經網路了。通過設計一個embedding propagation layer來表示這種embedding 在每個層之間的傳遞。
還是拿上面那張圖舉例子，堆疊兩層可捕獲u1←i2←u2的行為相似性，堆疊三層可捕獲u1←i2←u2←i4的潛在推薦以及信息流的強度（由層之間的可訓練權重來評估），並確定i4和i5的推薦優先順序。
這個跟傳統的embedding是一樣的，都是對原始的userID和itemID做embedding，跟傳統embedding不同的地方是，在我們的NGCF框架中，我們通過在用戶-項目交互圖上傳播embedding來優化embedding。 由於embedding優化步驟將協作信號顯式注入到embedding中，因此可以為推薦提供更有效的embedding。
這一層是本文的核心內容，下面我們來進行詳細的解讀。
從直觀上來看，用戶交互過的item會給用戶的偏好帶來最直接的依據。類似地，交互過某個item的用戶可以視為該item的特徵，並可以用來衡量兩個item的協同相似性。 我們以此為基礎在連接的用戶和項目之間執行embedding propogation，並通過兩個主要操作來制定流程：消息構建和消息聚合。
Message Construction(消息構建)
對於連接的user-item對(u,i)，我們定義從i到u的消息為：
其中ei是i的embedding，eu是u的embedding，pui是用於控制每次傳播的衰減因子，函數f是消息構建函數，f的定義為：
其中W1和W2用來提取有用的embedding信息，可以看到W2控制的i和u直接的交互性，這使得消息取決於ei和eu之間的親和力，比如，傳遞更多來自相似項的消息。
另一個重要的地方是Nu和Ni，pui = 1/ 。Nu和Ni表示用戶u和item i的第一跳鄰居。 從表示學習的角度來看，pui反映了歷史item對用戶偏好的貢獻程度。 從消息傳遞的角度來看，考慮到正在傳播的消息應隨路徑長度衰減，因此pui可以解釋為折扣因子。
Message Aggregation
聚合方法如下 ：
其中 表示在第一嵌入傳播層之後獲得的用戶u的表示。激活函數採用的是leakyrelu，這個函數適合對pos和neg信號進行編碼。
另一個重要的信息是 ,它的定義如下：
這個信息的主要作用是保留原始的特徵信息。
至此，我們得到了 ，同樣的方法，我們也能獲得 ，這個都是first order connectivoty的信息。
根據前面的計算方式，我們如果將多個Embedding Propagation Layers進行堆疊，我們就可以得到high order connectivity信息了：
計算方式如下：
當我看到這里的時候，我的腦子里產生了一個大大的疑惑，我們在計算第l層的eu和ei時都需要第l-1層的信息，那麼我們怎麼知道ei和eu在第l層是否存在呢？也就是說出現u側的總層數l大於i側總層數的時候，我們如何根據第l-1層的ei來計算第l層的e呢？經過思考，我感覺應該是這樣的，訓練樣本應該是一條path，也就是這個例子是u1 ← i2 ← u2 ← i4這條path，所以可以保證u1跟i4的層數l是一樣的，所以不存在上面那個層數不匹配的問題。
ps:看到後面的實驗結果才知道L是固定的所以每一層都不會缺失。
還有一個就是，不同層之間的W是不一樣的，每一層都有著自己的參數，這個看公式就知道，理由就是我們在提取不同層信息的時候需要不同的W進行信息提取。
另一個疑惑是pui到底是不是每一個l層都一樣？這里看公式好像就是指的是第一跳的Nu和Ni進行就計算的結果。
這部分內容是為了在進行batch訓練的時候進行矩陣運算所推導的數學過程，其實跟之前我們講的那個過程在數學上的計算是完全一樣的，你想像一下，如果不用矩陣進行運算，在訓練過程中要如何進行這么復雜的交互運算。
當進行了l層的embedding propagation後，我們就擁有了l個eu和l個ei，我們將他們進行concate操作：
這樣，我們不僅可以通過嵌入傳播層豐富初始嵌入，還可以通過調整L來控制傳播范圍。
最後，我們進行內積計算，以評估用戶對目標商品的偏好：
採用的是pair-wise方式中的bpr loss：
『貳』 協同過濾，矩陣分解有感
這個概念經常在機器學習的文章中看到，但由於接觸不久，所以一直都是一知半解，沒有好好了解過。
首先從字面上理解，「協同」需要一個「集體「，「過濾」就應該是曬選的意思，那麼協同過濾總的來說就是通過「集體」來「篩選」，以評分推薦系統為例子，這里的「協同」我個人理解就是集合」眾多人的評價」，這里的「評價」，就是「對集體都接觸過的事物進行打分」，這樣大概就能通過一些共同的事物反應出用戶不同的」價值觀「，然後通過這樣的價值觀來」篩選「出價值觀高度相似的人，再相互推薦共同都喜愛的東西。那麼這樣的推薦就很有可能是大家都需要的。
經過資料洗禮過後，得知cf現在的兩大方向，一種是以記憶為基礎（Memory-base）,另一種是基於模型（Model-based Collaborative Filtering）。
普及的比較多的前者，它基於關注的目標，又分為基於用戶的協同過濾和基於項目的協同過濾，上面舉的一個簡單的評分推薦系統的例子就可以說是基於用戶的協同過濾，它是通過用戶對共同物品的「主觀價值」來篩選相似用戶，再互補評分高的商品，從而達到推薦商品的目的；那麼基於項目的意思就是通過這個用戶集體對商品集的評價，在物品的角度上去尋找相似度高的物品，達到推薦商品的效果。雖然針對的目標不通，但以我個人理解，大體上都是依賴這個用戶集營造的「價值觀」，只不過區別在於，基於用戶的CF是「關心」各個用戶的「主觀價值」上的「區別」，而基於項目的CF則是要基於這整個用戶集對項目集的「普世價值觀」，來甄別出「物品」上的差異。不知道這么比喻恰不恰當哈，「普世」我這邊理解就是「大多數」，是一種整體趨勢的意思。價值觀比較「抽象」的話，再直接點這里的「價值觀」就相當於物理中的「參考系」。
但是以上兩種方法在面對，不是每個用戶對大多數商品都做出過評價（數據稀疏）時就無能為力，所以基於這個問題就引導出了基於模型（Model-based ）的CF，我在最近的論文中接觸到的就是一個「矩陣分解」的協同過濾，它能夠基於現有的數據得到一個模型，再用此模型進行推薦。那麼是如何做到的呢？接下來看看矩陣分解。
假設我先在有一個關於用戶對音樂評分的矩陣如下圖：
只有上述的數據是很難使用戶相互推薦音樂的，因為可以看出用戶本身聽過的歌就不夠多，那麼如何使數據更加「飽滿」呢？這時正是需要矩陣分解的時候，矩陣分解演算法的數學理論基礎是矩陣的行列變換。行列變換中又有以下規則，我們知道矩陣A進行行變換相當於A左乘一個矩陣，矩陣A進行列變換等價於矩陣A右乘一個矩陣，因此矩陣A可以表示為A=PEQ=PQ（E是標准陣）。
形象的表示如下圖：
矩陣分解的目的就是把一個稀疏的用戶評分矩陣分解成用戶因子矩陣和項目因子矩陣相乘的形式R=U(轉置)*I，我們的目的就是最後再讓兩個因子矩陣反乘回去得到飽滿的用戶評分矩陣。那麼這個用戶,項目因子是個什麼東西呢？我們接著上面的音樂評分的形式說，一首歌可能包含多種音樂風格，我們可以量化風格，體現各種風格在一首歌中的比重，那麼這里的「潛在因子」我們就可以當作「音樂風格」，K個因子就可以看作K種風格。譬如下圖：
可以說，這些因子就是我們的模型中的重要參數，個人理解分解出來的這兩個因子矩陣就可以說是基於模型的CF中的，「模型」的了，其實我覺得可以類比線性模型中的參數，我們的回歸模型最終重要的不就是公式中的各項參數嗎，這兩個因子矩陣其實就是我們這個模型中的重要參數，參數知道了模型也就求出來了。如果不了解線性模型可以參考吳恩達大大的機器學習課程，裡面介紹的很詳細，不像我這邊一知半哈。
那麼這些個值具體是怎麼得出來的呢？過程和求線性回歸也很像，接下來就是相關的簡單推倒，首先，我們假設，真實的用戶評分和我們預測評分的差遵循高斯分布
R用是評分矩陣 U是用戶因子矩陣，V是項目因子矩陣
接下來就是極大似然估計，使，在現有數據下概率最大化
類比求線性模型，就能夠了解思想很相似，所以應該同樣是運用了似然估計的思想，要使值最大，式子兩邊同時取對數，可以看到，如果要使概率最大，那麼公式的第一項就要最小，是不是想到了什麼，沒錯接下來就可以看到最小二乘法的式子。
線性模型我們遇到這個情況一般怎麼做，沒錯，就是梯度下降。首先求偏導數
最後就是梯度下降的矩陣因子更新公式：
接下來迭代到自己設置的閾值收斂就能得到局部最優解了。
下面是我根據上述矩陣分解的思想隨機的模擬實踐，可以自行感受一下準度，可能寫搓了點～
注釋：以上諸多圖片材料來自網上多篇博客文章
https://www.hu.com/question/26743347
http://blog.csdn.net/dream_angel_z/article/details/46288167
還有方便實用sklearn的中文API文檔
http://cwiki.apachecn.org/pages/viewpage.action?pageId=10030193
『叄』 基於用戶協同過濾(User-CF)的推薦演算法
1. 數學必備知識(向量)
2. 構建矩陣模型
3. User-CF的思想和計算
在一個個性化推薦系統中，當一個用戶A需要個性化推薦時，可以先找和他有相似興趣的其他用戶，然後把那些用戶喜歡的、而用戶A沒有聽說過的物品推薦給A。這種方法成為基於用戶的協同過濾演算法(User-CF)
根據問題域中構建出來的用戶-行為評分矩陣(圖1-1),我們可以構建出用戶的向量.首先,把每一個用戶用一個向量表示,每個向量里有6個數字,分別代表該用戶對6本書喜愛程度的評分.0代表用戶沒看過這本書.圖示:
接下來,計算倆個用戶的相似性,這里使用的指標叫作餘弦相似度,計算公式如下:
其中,分子部分a·b表示兩個向量的點積,計算方法就是兩個向量對應元素先相乘再求和,比如:
用戶a=[4 3 0 0 5 0]和用戶b=[5 0 4 0 4 0]
a·b=4x5+3x0+0x4+0x0+5x4+0x0=40
分母部分的 代表向量a的模長, 就是a,b兩個向量模長的乘積.向量模長的計算方法就是把向量
中的每個元素平方後再求和最後再開根號.
於是,第一個用戶和第二個用戶的相似度就可以進行如下計算:
餘弦相似度的值在[0,1]閉區間內,值越大說明越相似,值越小說明越不相似.根據上面的計算公式,分別計算小白和其他5個同事的相似度,然後根據從大到小的順序排列.可以看到小白和前倆個同事相似度高而和最後一個同事完全不相似.
比如,和小白最相似的兩個同事的閱讀列表編號有1,3,4,5共4本書.其中1,5這兩本書小白已經看過,3,4這兩本書哪本可能更適合小白的口味呢?
可以計算這兩個同事對這兩本書的加權評分並作為小白的可能評分,權重就是他們之間的相似度,具體計算如
下圖.通過計算可以看出編號為3的書可能更適合小白的口味.
計算步驟:
1. 先確定第一個同事擁有的閱讀列表的圖書編號為1,3,5
2. 再確定第二個同事擁有的閱讀列表的圖書編號為1,3,4,5
3. 小白自己已經擁有的閱讀的圖書列表是1,2,5[這也是打叉的意義,自己已經有的,不需要再推薦給自己了]
4. 最後剩餘的只有編號為3和編號為4的兩本書了
5. 計算公式說明,0.75和0.63代表權重,也就是相似值.4,3,5代表的是該用戶對這本書的評分.
1. 性能:適用於用戶較少的場合，如果用戶過多，計算用戶相似度矩陣的代價較大
2. 領域:實效性要求高，用戶個性化興趣要求不高
3. 實時性:用戶有新行為，不一定需要推薦結果立即變化
4. 冷啟動:在新用戶對少的物品產生行為後，不能立即對他進行個性化推薦，因為用戶相似度是離線計算的
新物品上線後一段時間，一旦有用戶對物品產生行為，就可以將新物品推薦給其他用戶