推薦演算法三視角：矩陣、圖、時間線

出處 | 技術人的百寶黑皮書-阿里淘系技術2020技術年貨

關於推薦系統，如果忘掉所有的公式和程式碼，忘記所有的語言描述，腦海裡就剩下幾張圖景， 會是什麼？

一張二維表格，一個拓撲圖，一條時間線。

這三幅圖景，是我看待推薦演算法的三種視角，分享給大家便於理解。

視角一：矩陣

在腦中想象一個二維的表格，每一行代表一個使用者，每一列代表一個物品，表格裡的每一個點代表使用者對物品的操作，這個操作可以是評分、點選、點贊。其中，有些格子記錄了行為，有些格子是空的。到這裡，我們就建立了基本的矩陣視角，

推薦問題轉化成了如何補上那些空格子

。

user-base/item-base 的協同過濾

：使用者對物品的評分等於相似使用者對該物品評分的加權平均值，這就是 user-base 的協同過濾了。換一個方向，使用者對物品的評分等於該使用者對其他物品的評分按物品相似加權平均值， 這就是 item-base 的協同過濾。度量使用者之間的相似度，把矩陣的一行——對物品的評分向量作為該使用者的表示向量，那麼使用者之間可以計算向量的距離，可以選擇任何距離公式， 如餘弦距離，皮爾森距離。對於物品之間的相似度，換一個方向即可。

Slope One

：對於任何兩個物品，可以計算它們的評分差值。具體來說，兩個物品有一批共同的歷史評分使用者，也就是矩陣裡兩列有交集的行，每一行可以計算一個差值，將差值平均起來，作為兩個物品的距離。和上面的距離不同的，這個差值可以想象成物理中的位移，帶著符號的。推薦時，某使用者對於某個物品的評分，等於某使用者對其他物品評分加上這個位移，再進行平均得到的平均評分。和上面的item-base 一樣的，都是列向量計算相似度，只不過相似度由距離變成了位移。這就是著名的 Slope One 演算法。

Basis of Slope-One shemes：User A&；amp；amp；amp；amp；#39；s ratings of two items and User B&；amp；amp；amp；amp；#39；s rating of a common item is used to predict User B&；amp；amp；amp；amp；#39；s unknown rating

SLIM

：物品直接的相似度，除了上面的啟發式演算法，能不能透過資料本身學習所得？這就誕生了 SLIM（Sparse Linear Methods）方法。矩陣 A 是 n x m 評分矩陣，要學習一個 m x m 維的物品相似的矩陣 W。A 的每一行是使用者的歷史評分，W 的每一列是每一個物品和該列對應物品的相似度，計算內積即為該使用者對該列物品的評分，透過梯度下降訓練來擬合真實評分。其中，W 非負體現了相似度的物理意義；對角線限制為 0 避免對角線全都學習到 1 完美過擬合；新增 L1 正則產生稀疏的 W，使得結果在大規模物品集上可用；W 的每一列的學習都可以看作一個線性迴歸模型，訓練時可以彼此相互獨立，因而可以分散式學習。

SVD

：在矩陣視角下，很自然可以進行矩陣分解。SVD 矩陣分解將 m 個使用者 n 個物品的大矩陣分解成三個矩陣相乘，中間的矩陣越靠近左上角的特徵值越大，代表矩陣分解的主要成分，也就是說保留左上角的 k x k 維矩陣 D，其餘的都置為零，將原來的等於變為約等於。將藍色和紅色的矩陣合併，得到一個 m x k 維的矩陣，每一個行代表一個 k 維的使用者向量， 對於黃色矩陣保留其前 k 行（後面的不影響計算了），每一列代表一個物品向量，使用者和物品向量的內積也就是矩陣相乘後對應矩陣的值，也就是空缺處的評分，將向量索引起來就可以推薦了。

FunkSVD

：要使用SVD 分解，待分解矩陣要是稠密的，稀疏的評分矩陣要按照統計學方法填充，如填充均值。另外，SVD 過擬合現象嚴重，泛化誤差太大。在 2006 年 Netflix Prize 的百萬推薦大獎賽上，Simon Funk 在部落格公開 FunkSVD 演算法。直接將評分矩陣分解成兩個矩陣相乘，n x k 維度的使用者矩陣，每一行是使用者的隱式向量表示，k x m 維的物品矩陣，每一列是物品的隱式向量表示，使用者和物品向量的內積即為預估的評分。那如何進行分解呢？隨機初始化矩陣，使用均方誤差作為 loss，梯度下降進行學習。這個過程中還可以加入正則項， 降低泛化誤差。由 FunkSVD 開始，基於 Matrix factor（MF）的方法大放異彩。

FM

：在 MF 的基礎上，考慮推薦中的 side information，如使用者的年齡性別，物品的類目價格。 使用者和物品自身或屬性稱作一個 field，field 之間可以兩兩進行矩陣分解，這個被稱作二階項，類似 BiasSVD 考慮每一個 field 都有一個 bias，這個被稱作一階項，再加上一個全域性的 bias 項。這就是著名的 Factorization Machines（FM）。

FISM

：如果把上面介紹的 SLIM 和 MF 解結合起來，將物品的相似度矩陣 W 分解成 P x Q 兩個低維矩陣，使用者對某物品的評分，等於他過去評分過的物品在 P 中對應的向量和 Q 中該物品向量內積的和，這就是 FISM 演算法。相比 SLIM 的稀疏處理，變為分解降維。最後再附上 一張圖，說明 MF，SLIM 和FISM 之間的關係。

視角二：圖

把使用者和物品看作頂點，使用者的評分在使用者和物品之間建立起邊，就得到了一個二部圖；在二部圖的基礎上新增更多的頂點和邊，形成一個更為複雜的圖，輔助二部圖的計算。在圖的視角下，

推薦問題轉化成了在圖上尋找高效的連結模式。

Adamic/Adar

：我們認為在同一個使用者的歷史行為中，那麼兩個物品之間有一條邊，現在要計算兩個物品之間的相似度，最樸素的思想就是數一數他們之間有多少條邊。考慮每一條邊權重不一樣，邊是透過使用者建立的，使用者的點選的物品越多，對應邊的權重就越小。這就是 Adamic/Adar 演算法的思想。

swing

：阿里著名的協同過濾推薦演算法 swing，尋找圖中更加穩固的形狀，共同評分過兩個物品的使用者集合中，每兩個使用者和這個兩個物品形成了一個四邊形（下圖紅邊為一個 swing 結構），統計有多少個這樣的結構，每一個結構的權重是不同的，這個結構裡兩個使用者共同評分過的物品的數量越多權重就越小。

Graph-Embedding

：從使用者和物品的二部圖出發進行構圖，再結合隱因子模型（Latent Factor Model），就進入了 Graph-Embedding 的領域。DeepWalk 演算法在圖上隨機遊走深度優先遍歷得到序列，然後和 word2vec 類似地使用Skip-Gram（A 和 B 序列中相鄰，用 A 的 embedding 作為特徵最大化 B 的選中機率）進行訓練。Node2Vec 演算法在 DeepWalk 的基礎上，考慮隨機遊走的方式，引入深度優先和廣度優先的權衡，能夠得到更好的更靈活的頂點隱式表示。LINE 演算法考慮頂點的二階相似，兩個頂點有邊為一階相似，兩個頂點有共同的鄰居頂點為二階相似，它雖不做隨機遊走，但可以看作是廣度優先的取樣。Graph-Embedding 取得了頂點的 embedding，計算相似度可以得到使用者物品距離，物品物品距離，用於推薦。

GraphSAGE

：GCN（圖卷積）接收拓撲圖作為網路輸入，可以計算每一個頂點更好的表示，相比 Graph-Embedding 可以有監督地為推薦目標而訓練。但 GCN 在運算時，每一層都要輸入整個圖，在推薦系統裡，物品和使用者都可以是百萬級別以上，實際中無法使用。GraphSAGE 透過 RandomWalk 取樣，解決了這個問題，用在推薦領域就是 PinSage 演算法。從某頂點出發，深度優先走k步，得到多個子圖，組成一個batch 進行訓練，然後按照取樣的反方向做前向傳播，這就是一個 k 層的圖網路，下圖是一個 k 為 2 的例子。

在使用者和物品的二部圖基礎上，使用者和使用者根據社會關係建立起邊來，這就是

社會化推薦

。

meta-path

：在使用者和物品的二部圖基礎上，增加物品的屬性作為頂點，建立新的邊，就得到了一個異質資訊網路。比如一個電影推薦系統，除了使用者和電影外，還有導演，演員，電影型別，導演拍攝電影，電影屬於某種型別，演員出演電影，導演與演員合作，諸如此類就能建立很多邊。其中一類推薦演算法叫做 meta-path，透過專家經驗人工挑選出一些圖中路徑，如使用者->演 員->電影，使用者->導演->電影，這樣的路徑稱之為 meta-path，計算每一條 meta-path 的權重，將使用者和物品間的所有 meta-path 聯合計算評分。

視角三：時間線

把使用者對物品的行為想象成一條時間線，我們已知當前時刻前使用者的物品行為序列，

推薦問題被轉化成了預測下一個時刻使用者發生行為的物品

。

FPMC

：假設序列中下一個物品只與上一個物品有關，可以使用馬爾科夫模型 MC（ MarkovChains），序列中相鄰的物品間進行矩陣分解。結合上文提到的使用者和物品間矩陣分解 MF，使用者、當前行為物品和下一個物品三者之間兩兩進行矩陣分解，將三個值加起來擬合評分，就得到了 FPMC（Factorizing Personalized Markov Chains）演算法。

Translation-based

：Translation-based 推薦在序列建模中引入 Metric Learning（把行為關係和高維空間距離對映起來），使用者 u、當前行為物品 i、下一個物品 j 三者向量化表示，訓練使得它們滿足 u+i≈j，推薦時只需拿到使用者歷史行為的物品向量加上使用者向量得到下一個物品向量，然後在推薦集合中 KNN 尋找即可完成推薦。

Session-base

：以前模型的輸入形式有限，人們透過特徵處理將資料組織成模型可以接受的形式；隨著深度學習的發展，資料越來越傾向於儲存其原有的形式，人們透過模型設計來學習有效的模式。在時間線的視角下，直接用深度模型結構建模序列，預測下一物品，形成了一個可以發揮想象力和燃燒算力的領域——Sequential/Session-base 推薦。在2016 年的時候，RNN 是處理序列問題的標配，它從 NLP 領域走來，誕生了 GRU4Rec 演算法。受到 NLP 領域 Char-CNN 啟發，CNN 的結構也逐漸用於建模序列結構，Attention 機制大火之後，RNN+Attention，CNN+Attention，RNN+CNN+ Attention 被枚舉了一遍。隨著 google 老師的 BERT 取得 NLP 領域巨大成就，SelfAttention 以及多層的 Transformer 結構開始成為序列建模的常規配置。最近的文章裡，圖神經網路（GNN）、Memory networks、變分自編碼器（VAE）也成為了序列推薦領域的深度樂高積木。在 CTR 預估領域，越來越多的模型直接將使用者歷史行為序列按照時間順序排列，使用深度模型結構直接建模。

總結

其實如果要細數，還有一個視角叫做

高維空間視角

。使用者和物品都是一個高維度空間裡的點，空間裡點之間的距離越近，代表著物品和物品越相關，使用者對物品越偏好，

推薦問題轉化成了如何將使用者和物品嵌入到高維空間裡

。典型的主題如 Metric Learning。不過這個視角的正交性不好，深度學習席捲推薦系統後，embedding 是個太常見的思路，前面很多的方法也都是最終把問題轉化成了高維空間嵌入，如 graph-embedding，Transition-base 推薦。為了避免歸類上的糾結；再加上任何一個深度網路作為 Encoder 把使用者和物品 embedding， 都可以歸在這個視角，沒有那麼多令人印象深刻的典型方法，就不做單獨梳理了。

To My Best Knowledge，我把自己認為推薦系統裡經典且令人印象深刻的方法歸在三種視角中——矩陣、圖、時間線。本來想談談認識的，寫著寫著寫多了，變成了一篇梳理文章。希望能對大家從偏演算法的角度理解推薦系統有所助益。

END

公眾號：TSGshare

歡迎留言批評指正！