關(guān)于推薦系統(tǒng)，如果在忘掉所有的公式和代碼，忘記所有的語言描述，腦海里就剩下幾張圖景，會(huì)是什么？一張二維表格，一個(gè)拓?fù)鋱D，一條時(shí)間線。這三幅圖景，是我看待推薦算法的三種視角。
視角一：矩陣視角
在腦中想象一個(gè)二維的表格，每一行代表一個(gè)用戶，每一列代表一個(gè)物品，表格里的每一個(gè)點(diǎn)代表用戶對(duì)物品的操作，這個(gè)操作可以是評(píng)分，點(diǎn)擊，點(diǎn)贊。其中，有些格子記錄了行為，有些格子是空的。到這里，我們就建立了基本的矩陣視角，推薦問題轉(zhuǎn)化成了如何補(bǔ)上那些空格子。
用戶對(duì)物品的評(píng)分等于相似用戶對(duì)該物品評(píng)分的加權(quán)平均值，這就是user-base的協(xié)同過濾了。換一個(gè)方向，用戶對(duì)物品的評(píng)分等于該用戶對(duì)其他物品的評(píng)分按物品相似加權(quán)平均值，這就是item-base的協(xié)同過濾。度量用戶之間的相似度，把矩陣的一行——對(duì)物品的評(píng)分向量作為該用戶的表示向量，那么用戶之間可以計(jì)算向量的距離，可以選擇任何距離公式，如余弦距離，皮爾森距離。對(duì)于物品之間的相似度，換一個(gè)方向即可。
對(duì)于任何兩個(gè)物品，可以計(jì)算它們的評(píng)分差值。具體來說，兩個(gè)物品有一批共同的歷史評(píng)分用戶，也就是矩陣?yán)飪闪杏薪患男校恳恍锌梢杂?jì)算一個(gè)差值，將差值平均起來，作為兩個(gè)物品的距離。和上面的距離不同的，這個(gè)差值可以想象成物理中的位移，帶著符號(hào)的。推薦時(shí)，某用戶對(duì)于某個(gè)物品的評(píng)分，等于某用戶對(duì)其他物品評(píng)分加上這個(gè)位移，再進(jìn)行平均得到的平均評(píng)分。和上面的item-base一樣的，都是列向量計(jì)算相似度，只不過相似度由距離變成了位移。這就是著名的Slope-One算法。
物品直接的相似度，除了上面的啟發(fā)式算法，能不能通過數(shù)據(jù)本身學(xué)習(xí)所得？這就誕生了SLIM(Sparse Linear Methods)方法。矩陣A是n*m評(píng)分矩陣，要學(xué)習(xí)一個(gè)n*m維的物品相似的矩陣W。
A的每一行是用戶的歷史評(píng)分，w的每一列是每一個(gè)物品和該列對(duì)應(yīng)物品的相似度，計(jì)算內(nèi)積即為該用戶對(duì)該列物品的評(píng)分，通過梯度下降訓(xùn)練來擬合真實(shí)評(píng)分。其中，w非負(fù)體現(xiàn)了相似度的物理意義；對(duì)角線限制為0避免對(duì)角線全都學(xué)習(xí)到1完美過擬合；添加L1正則產(chǎn)生稀疏的w，使得結(jié)果在大規(guī)模物品集上可用;w的每一列的學(xué)習(xí)都可以看作一個(gè)線性回歸模型，訓(xùn)練時(shí)可以彼此相互獨(dú)立，因而可以分布式學(xué)習(xí)。
在矩陣視角下，很自然可以進(jìn)行矩陣分解。SVD矩陣分解將n個(gè)用戶m個(gè)物品的大矩陣分解成三個(gè)矩陣相乘，中間的矩陣越靠近左上角的特征值越大，代表矩陣分解的主要成分，也就是說保留左上角的
k*k維矩陣D，其余的都置為零，將原來的等于變?yōu)榧s等于。將藍(lán)色和紅色的矩陣合并，得到一個(gè)
m*k維的矩陣，每一個(gè)行代表一個(gè)k維的用戶向量，對(duì)于黃色矩陣保留其前k行（后面的不影響計(jì)算了），每一列代表一個(gè)物品向量，用戶和物品向量的內(nèi)積也就是矩陣相乘后對(duì)應(yīng)矩陣的值，也就是空缺處的評(píng)分，將向量索引起來就可以推薦了。
要使用SVD分解，待分解矩陣要是稠密的，稀疏的評(píng)分矩陣要按照統(tǒng)計(jì)學(xué)方法填充，如填充均值。另外，SVD過擬合現(xiàn)象嚴(yán)重，泛化誤差太大。在2006年Netflix Prize的百萬推薦大獎(jiǎng)賽上， Simon Funk 在博客公開FunkSVD算法。直接將評(píng)分矩陣分解成兩個(gè)矩陣相乘，n*k維度的用戶矩陣，每一行是用戶的隱式向量表示，k*m維的物品矩陣，每一列是物品的隱式向量表示，用戶和物品向量的內(nèi)積即為預(yù)估的評(píng)分。那如何進(jìn)行分解呢？隨機(jī)初始化矩陣，使用均方誤差作為loss，梯度下降進(jìn)行學(xué)習(xí)。這個(gè)過程中還可以加入正則項(xiàng)，降低泛化誤差。由FunkSVD開始，基于Matrix factor（MF）的方法大放異彩。
在MF的基礎(chǔ)上，考慮推薦中的side information，如用戶的年齡性別，物品的類目?jī)r(jià)格。用戶和物品自身或?qū)傩苑Q作一個(gè)field，field之間可以兩兩進(jìn)行矩陣分解，這個(gè)被稱作二階項(xiàng)，類似BiasSVD考慮每一個(gè)field都有一個(gè)bias，這個(gè)被稱作一階項(xiàng)，再加上一個(gè)全局的bias項(xiàng)。這就是著名的Factorization machines（FM）。
如果把上面介紹的SLIM和MF解結(jié)合起來，將物品的相似度矩陣
W分解成P*Q兩個(gè)低維矩陣，用戶對(duì)某物品的評(píng)分，等于他過去評(píng)分過的物品在P中對(duì)應(yīng)的向量和
Q中該物品向量?jī)?nèi)積的和，這就是FISM算法。相比SLIM的稀疏處理，變?yōu)榉纸饨稻S。最后再附上一張圖，說明MF，SLIM和FISM之間的關(guān)系。
視角二：圖視角
把用戶和物品看作頂點(diǎn)，用戶的評(píng)分在用戶和物品之間建立起邊，就得到了一個(gè)二部圖；在二部圖的基礎(chǔ)上添加更多的頂點(diǎn)和邊，形成一個(gè)更為復(fù)雜的圖，輔助二部圖的計(jì)算。在圖的視角下，推薦問題轉(zhuǎn)化成了在圖上尋找高效的鏈接模式。
我們認(rèn)為在同一個(gè)用戶的歷史行為中，那么兩個(gè)物品之間有一條邊，現(xiàn)在要計(jì)算兩個(gè)物品之間的相似度，最樸素的思想就是數(shù)一數(shù)他們之間有多少條邊?？紤]每一條邊權(quán)重不一樣，邊是通過用戶建立的，用戶的點(diǎn)擊的物品越多，對(duì)應(yīng)邊的權(quán)重就越小。這就是Adamic/Adar算法的思想。
阿里著名的協(xié)同過濾推薦算法swing，尋找圖中更加穩(wěn)固的形狀，共同評(píng)分過兩個(gè)物品的用戶集合中，每?jī)蓚€(gè)用戶和這個(gè)兩個(gè)物品形成了一個(gè)四邊形(下圖紅邊為一個(gè)swing結(jié)構(gòu))，統(tǒng)計(jì)有多少個(gè)這樣的結(jié)構(gòu)，每一個(gè)結(jié)構(gòu)的權(quán)重是不同的，這個(gè)結(jié)構(gòu)里兩個(gè)用戶共同評(píng)分過的物品的數(shù)量越多權(quán)重就越小。
從用戶和物品的二部圖出發(fā)進(jìn)行構(gòu)圖，再結(jié)合隱因子模型(Latent Factor Model)，就進(jìn)入了Graph-Embedding的領(lǐng)域。DeepWalk算法在圖上隨機(jī)游走深度優(yōu)先遍歷得到序列，然后和word2vec類似地使用Skip-Gram（A和B序列中相鄰，用A的embedding作為特征最大化B的選中概率）進(jìn)行訓(xùn)練。Node2Vec算法在DeepWalk的基礎(chǔ)上，考慮隨機(jī)游走的方式，引入深度優(yōu)先和廣度優(yōu)先的權(quán)衡，能夠得到更好的更靈活的頂點(diǎn)隱式表示。LINE算法考慮頂點(diǎn)的二階相似，兩個(gè)頂點(diǎn)有邊為一階相似，兩個(gè)頂點(diǎn)有共同的鄰居頂點(diǎn)為二階相似，它雖不做隨機(jī)游走，但可以看作是廣度優(yōu)先的采樣。Graph-Embedding取得了頂點(diǎn)的embedding，計(jì)算相似度可以得到用戶物品距離，物品物品距離，用于推薦。
GCN（圖卷積）接收拓?fù)鋱D作為網(wǎng)絡(luò)輸入，可以計(jì)算每一個(gè)頂點(diǎn)更好的表示，相比graph-embedding可以有監(jiān)督地為推薦目標(biāo)而訓(xùn)練。但GCN在運(yùn)算時(shí)，每一層都要輸入整個(gè)圖，在推薦系統(tǒng)里，物品和用戶都可以是百萬級(jí)別以上，實(shí)際中無法使用。GraphSAGE通過RandomWalk采樣，解決了這個(gè)問題，用在推薦領(lǐng)域就是PinSage算法。從某頂點(diǎn)出發(fā)，深度優(yōu)先走k步，得到多個(gè)子圖，組成一個(gè)batch進(jìn)行訓(xùn)練，。然后按照采樣的反方向做前向傳播，這就是一個(gè)k層的圖網(wǎng)絡(luò)，下圖是一個(gè)k為2的例子。
在用戶和物品的二部圖基礎(chǔ)上，用戶和用戶根據(jù)社會(huì)關(guān)系建立起邊來，這就是社會(huì)化推薦。
在用戶和物品的二部圖基礎(chǔ)上，增加物品的屬性作為頂點(diǎn)，建立新的邊，就得到了一個(gè)異質(zhì)信息網(wǎng)絡(luò)。比如一個(gè)電影推薦系統(tǒng)，除了用戶和電影外，還有導(dǎo)演，演員，電影類型，導(dǎo)演拍攝電影，電影屬于某種類型，演員出演電影，導(dǎo)演與演員合作，諸如此類就能建立很多邊。其中一類推薦算法叫做meta-path，通過專家經(jīng)驗(yàn)人工挑選出一些圖中路徑，如用戶->演員->電影，用戶->導(dǎo)演->電影，這樣的路徑稱之為meta-path，計(jì)算每一條meta-path的權(quán)重，將用戶和物品間的所有meta-path聯(lián)合計(jì)算評(píng)分。
視角三：時(shí)間線
把用戶對(duì)物品的行為想象成一條時(shí)間線，我們已知當(dāng)前時(shí)刻前用戶的物品行為序列，推薦問題被轉(zhuǎn)化成了預(yù)測(cè)下一個(gè)時(shí)刻用戶發(fā)生行為的物品。
假設(shè)序列中下一個(gè)物品只與上一個(gè)物品有關(guān)，可以使用馬爾科夫模型MC（Markov Chains），序列中相鄰的物品間進(jìn)行矩陣分解。結(jié)合上文提到的用戶和物品間矩陣分解MF，用戶，當(dāng)前行為物品和下一個(gè)物品三者之間兩兩進(jìn)行矩陣分解，將三個(gè)值加起來擬合評(píng)分，就得到了FPMC（Factorizing Personalized Markov Chains）算法。
Translation-based推薦在序列建模中引入Metric Learning（把行為關(guān)系和高維空間距離映射起來），用戶u，當(dāng)前行為物品i，下一個(gè)物品j三者向量化表示，訓(xùn)練使得它們滿足u+i≈j，推薦時(shí)只需拿到用戶歷史行為的物品向量加上用戶向量得到下一個(gè)物品向量，然后在推薦集合中KNN尋找即可完成推薦。
以前模型的輸入形式有限，人們通過特征處理將數(shù)據(jù)組織成模型可以接受的形式；隨著深度學(xué)習(xí)的發(fā)展，數(shù)據(jù)越來越傾向于保存其原有的形式，人們通過模型設(shè)計(jì)來學(xué)習(xí)有效的模式。在時(shí)間線的視角下，直接用深度模型結(jié)構(gòu)建模序列，預(yù)測(cè)下一物品，形成了一個(gè)可以發(fā)揮想象力和燃燒算力的領(lǐng)域——Sequential/Session-base推薦。在2016年的時(shí)候，RNN是處理序列問題的標(biāo)配，它從NLP領(lǐng)域走來，誕生了GRU4Rec算法。受到NLP領(lǐng)域Char-CNN啟發(fā)，CNN的結(jié)構(gòu)也逐漸用于建模序列結(jié)構(gòu)，Attention機(jī)制大火之后，RNN+Attention，CNN+Attention，RNN+CNN+Attention被枚舉了一遍。隨著google老師的BERT取得NLP領(lǐng)域巨大成就，Self-Attention以及多層的Transformer結(jié)構(gòu)開始成為序列建模的常規(guī)配置。最近的文章里，圖神經(jīng)網(wǎng)絡(luò)(GNN),Memory networks,變分自編碼器(VAE)也成為了序列推薦領(lǐng)域的深度樂高積木。
在CTR預(yù)估領(lǐng)域，越來越多的模型直接將用戶歷史行為序列按照時(shí)間順序排列，使用深度模型結(jié)構(gòu)直接建模。
總結(jié)
其實(shí)如果要細(xì)數(shù)，還有一個(gè)視角叫做高維空間視角。用戶和物品都是一個(gè)高維度空間里的點(diǎn)，空間里點(diǎn)之間的距離越近，代表著物品和物品越相關(guān)，用戶對(duì)物品越偏好，推薦問題轉(zhuǎn)化成了如何將用戶和物品嵌入到高維空間里。典型的主題如Metric Learning。不過這個(gè)視角的正交性不好，深度學(xué)習(xí)席卷推薦系統(tǒng)后，embedding是個(gè)太常見的思路，前面很多的方法也都是最終把問題轉(zhuǎn)化成了高維空間嵌入，如graph-embedding，Transition-base推薦。為了避免歸類上的糾結(jié)；再加上任何一個(gè)深度網(wǎng)絡(luò)作為Encoder把用戶和物品embedding，都可以歸在這個(gè)視角，沒有那么多令人印象深刻的典型方法，就不做單獨(dú)梳理了。
To My Best Knowledge，我把自己認(rèn)為推薦系統(tǒng)里經(jīng)典且令人印象深刻的方法歸在三種視角中——矩陣，圖，時(shí)間線。本來想談?wù)務(wù)J識(shí)的，寫著寫著寫多了，變成了一篇梳理文章。如果對(duì)你從偏算法的角度理解推薦系統(tǒng)有所助益，我就很開心了。后面有所學(xué)習(xí)所得，也會(huì)持續(xù)更到這篇文章，感興趣的收藏關(guān)注一下吧！
