1. 協同過濾(CF)
1. 裡程碑
2003年，Amazon發表論文《Amazon.com recommendations: item-to-item collaborative filtering》，不僅讓Amazon的推薦系統廣為人知，更讓協同過濾成為今後很長時間的研究熱點和業界主流的推薦模型。
2. 算法過程
（1）一種完全依賴使用者和物品之間行為關系的推薦算法，利用所有使用者與所有商品的關系建立共現矩陣。
（2）計算使用者相似度：在共現矩陣中，每個使用者對應的行向量其實就可以當作一個使用者的 Embedding 向量，可以使用餘弦相似度計算。
（3）使用者評分預測：利用使用者相似度與相似使用者評價的權重平均值，來獲得目标使用者的評價預測
3. 缺點
共現矩陣往往非常稀疏
2. 矩陣分解
1. 裡程碑
2006年，在Netflix Prize Challenge中，以矩陣分解為主的推薦算法大放異彩，拉開了矩陣分解在業界流行的序幕。
2. 協同過濾與矩陣分解差別
（1）協同過濾算法(圖左)找到使用者可能喜歡的視訊的方式很直覺，就是利用使用者的觀看曆史，找到跟目标使用者 Joe 看過同樣視訊的相似使用者，然後找到這些相似使用者喜歡看的其他視訊，推薦給目标使用者 Joe
（2）矩陣分解算法(圖右)是期望為每一個使用者和視訊生成一個隐向量，将使用者和視訊定位到隐向量的表示空間上，距離相近的使用者和視訊表明興趣特點接近，在推薦過程中，我們就應該把距離相近的視訊推薦給目标使用者
3. 矩陣分解過程
先分解協同過濾生成的共現矩陣，生成使用者和物品的隐向量，再通過使用者和物品隐向量間的相似性進行推薦。把一個 M ∗ N M * N M∗N的共現矩陣，分解成一個 M ∗ K M*K M∗K的使用者矩陣和 K ∗ N K*N K∗N 的物品矩陣相乘的形式。
4. 分解方法
（1）特征值分解（ED）：隻能作用于方針，不适用于分解使用者-物品矩陣
（2）奇異值分解（SVD）：要求原始的共現矩陣是稠密的，而且計算複雜度達到了 O ( m n 2 ) O(mn^2) O(mn2)，是以不滿足實時性要求
（3）梯度下降法（GD）：主要方法，為了減少過拟合現象，通常加入正則化項。
5. 矩陣分解優點：
（1）泛化能力強，在一定程度上解決了資料稀疏的問題
（2）空間複雜度低，不需要存儲大量的使用者和物品相似性矩陣，隻需要存儲使用者和物品隐向量即可。
（3）更好的擴充性和靈活性：矩陣分解結果是使用者和物品隐向量，與Embedding思想不謀而合，是以其結果易于與其他特征交叉組合，也能夠與深度學習網絡無縫結合。
6. 矩陣分解局限性
不友善加入使用者、物品和上下文相關的特征，喪失了利用很多有效資訊的機會。同時在缺乏使用者曆史行為時無法進行有效推薦。
7. 問答經典
-
評分标準不一緻，有人喜歡打高分，有人喜歡打低分，如何處理？
（1）在生成共現矩陣的時候對使用者的評分進行使用者級别的校正或者歸一化，用目前得分減去使用者平均得分作為共現矩陣裡面的值
（2）可以嘗試餘弦相似度消除影響。
-
正負樣本不平衡問題怎麼處理？
（1）負樣本欠采樣，和正樣本過采樣，或者增大正樣本學習的權重。
（2）SMOTE，大緻意思是通過合成的方式過采樣正樣本，可以嘗試但有一定風險。
3. 邏輯回歸（LR）
1. 簡介
LR模型可以綜合利用使用者、物品、上下文等多種不同的特征。另外LR的另外一種表現形式“感覺機”是神經網絡中最基礎的單一神經元結構，是深度學習的基礎結構。LR把推薦問題看作分類問題，通過預測正樣本的機率對物品進行排序，是以轉化成了點選率（CTR）預估問題。
2. 推薦流程
（1）将使用者屬性資訊、物品屬性資訊、上下文屬性資訊等特征展開并轉換成數值型特征向量。
（2）确定LR模型的優化目标，利用已有樣本資料對LR模型進行訓練。
（3）模型服務階段，将特征向量輸入LR模型，推斷得到目标機率。
（4）利用機率對所有候選物品進行排序，得到推薦清單。
3. 具體LR模型數學表達及訓練方法，請參考：
深度學習(DL)與卷積神經網絡(CNN)學習筆記随筆-03-基于Python的LeNet之LR
4. LR模型的優勢
（1）可解釋性強。LR模型數學形式是各特征的權重和，在經過Sigmoid函數計算出0~1之間的機率，符合人類對預估過程的直覺人知。
（2）工程化需要。在網際網路公司每天資料量是TB級别，模型的訓練和線上推斷效率非常重要。在尚未流行GPU訓練（2012年）之前，LR模型憑借易于并行化、模型簡單、訓練開銷小等優勢占據着工程領域的主流。
5. LR模型局限性
表達能力不強，無法進行多特征交叉、特征篩選等複雜操作；
4. 因子分解機(FM)
1. 為什麼需要多特征交叉？
辛普森悖論 – 交叉與不交叉的結論完全相悖
2. 特征交叉發展裡程碑
POLY2–>FM–>FFM
3. POLY2模型
原始的特征交叉方法是人工組合特征，再通過各種分析手段篩選有效的組合特征。是以首先發展出了POLY2（Degree-2 Polynomial Margin，論文連結）模型進行特征的“暴力”組合。數學形式如下：
P O L Y 2 ( w , x ) = w 0 + ∑ i = 1 n w i x i + ∑ j 1 = 1 n ∑ j 2 = j 1 + 1 n w h ( j 1 , j 2 ) x j 1 x j 2 POLY2(w, x) = w_0 + \sum^{n}_{i=1} w_i x_i + \sum^{n}_{j_1 = 1} \sum^{n}_{j_2 = j_1 + 1} w_{h(j_1, j_2)} x_{j_1} x_{j_2} POLY2(w,x)=w0+i=1∑nwixi+j1=1∑nj2=j1+1∑nwh(j1,j2)xj1xj2
其中 n n n表示特征數量， x i x_i xi表示one-hot編碼中第 i i i個特征的值， w w w等是模型參數。
當 x j 1 x_{j_1} xj1和 x j 2 x_{j_2} xj2兩者都非零時，交叉特征 x j 1 x j 2 x_{j_1} x_{j_2} xj1xj2才有效。上式對特征進行了兩兩交叉（特征 x j 1 x_{j_1} xj1和 x j 2 x_{j_2} xj2），并對所有的交叉特征賦予權重 w h ( j 1 , j 2 ) w_{h(j_1, j_2)} wh(j1,j2)。
在一定程度上解決了特征交叉的問題，但本質上還是線性模型，其訓練方法與LR無差別。同時存在2個較大缺陷：
（1）one-hot編碼處理類别型資料導緻特征向量稀疏，POLY2進行無選擇的特征交叉會導緻特征向量更加稀疏。
（2）權重參數數量由 n n n上升到了 n n n，極大的增加了訓練複雜度。
4. FM模型
2010年，Rendle提出了FM模型（Factorization Machines），FM為每個特征學習一個隐權重向量，在特征交叉的時候，使用兩個特征隐向量的内積作為交叉特征的權重，而不是PLOY2中為每個交叉特征設定一個權重參數，數學形式如下：
F M ( w , x ) = w 0 + ∑ i = 1 n w i x i + ∑ j 1 = 1 n ∑ j 2 = j 1 + 1 n ( w j 1 ⃗ ⋅ w j 2 ⃗ ) x j 1 x j 2 FM(w, x) = w_0 + \sum^{n}_{i=1} w_i x_i + \sum^{n}_{j_1 = 1} \sum^{n}_{j_2 = j_1 + 1} (\vec{w_{j_1}} \cdot \vec{w_{j_2}}) x_{j_1} x_{j_2} FM(w,x)=w0+i=1∑nwixi+j1=1∑nj2=j1+1∑n(wj1
⋅wj2
)xj1xj2
與POLY2的主要差別是：用兩個向量的内積 ( w j 1 ⃗ ⋅ w j 2 ⃗ ) (\vec{w_{j_1}} \cdot \vec{w_{j_2}}) (wj1
⋅wj2
)取代了單一的權重系數 w h ( j 1 , j 2 ) w_{h(j_1, j_2)} wh(j1,j2)。FM引入隐向量的思路與矩陣分解出使用者隐向量和物品隐向量思路一緻，但是做了進一步的拓展，即從單純的使用者、物品兩特征拓展到了所有的特征。
優點：
（1）把POLY2的 n n n級别參數量降低到了 n k ( k 是 隐 向 量 維 度 ， n > > k ) nk(k是隐向量次元，n>>k) nk(k是隐向量次元，n>>k)級别，大大降低了訓練開銷。
（2）引入隐向量，可以更好的解決稀疏資料問題。可以把兩種特征的向量内積作為交叉特征的權重，而不需要樣本中必須含有這種交叉特征。
（3）一定程度上丢失了某些具體交叉特征的精确記憶表示能力，但是大大提高了泛化能力。
由于FM同樣可以用梯度下降方法進行訓練，其二階表達式經過化簡之後，預測複雜度可從 O ( k n 2 ) O(kn^2) O(kn2)優化到 O ( k n ) O(kn) O(kn)，即可以線上性時間内完成線上預測。同時計算完梯度後的表達式複雜度是 O ( k n ) O(kn) O(kn)，是以其訓練也非常高效。是以憑借着易于訓練和預測，是以在2012~2014年前後成為業界主流的推薦模型之一。
5. FFM
2015年，基于FM提出的FFM（Field-aware Factorization Machines for CTR Prediction）在多項CTR預估大賽中奪冠，并被Criteo、美團等公司深度應用在推薦系統、CTR預估等領域。FFM引入了特征域概念，使模型的表達能力更強。那怎麼了解特征域呢？
《深度學習推薦系統》中的示例：
使用者的性别分為男、女、未知三類，那麼對一個女性使用者來說，采用one-hot方式編碼的特征向量為[0, 1, 0]，這個三維的特征向量就是一個“性别”特征域。
《深入FFM原理與實踐》中的解釋：
以上面的廣告分類為例，“Day=26/11/15”、“Day=1/7/14”、“Day=19/2/15”這三個特征都是代表日期的，可以放到同一個field中。同理，商品的末級品類編碼生成了550個特征，這550個特征都是說明商品所屬的品類，是以它們也可以放到同一個field中。簡單來說，同一個categorical特征經過One-Hot編碼生成的數值特征都可以放到同一個field，包括使用者性别、職業、品類偏好等。
我的個人了解是：經過one-hot編碼的某類特征的特征值的集合稱為特征域。
FFM的數學形式如下：
F F M ( w , x ) = w 0 + ∑ i = 1 n w i x i + ∑ j 1 = 1 n ∑ j 2 = j 1 + 1 n ( w j 1 , f j 2 ⃗ ⋅ w j 2 , f j 1 ⃗ ) x j 1 x j 2 FFM(w, x) = w_0 + \sum^{n}_{i=1} w_i x_i + \sum^{n}_{j_1 = 1} \sum^{n}_{j_2 = j_1 + 1} (\vec{w_{j_1, f_{j_2}}} \cdot \vec{w_{j_2, f_{j_1}}}) x_{j_1} x_{j_2} FFM(w,x)=w0+i=1∑nwixi+j1=1∑nj2=j1+1∑n(wj1,fj2
⋅wj2,fj1
)xj1xj2
其中：
（1） f j f_j fj表示第 j j j個特征所屬的特征域；
（2） w j 1 , f j 2 ⃗ \vec{w_{j_1, f_{j_2}}} wj1,fj2
表示特征 x j 1 x_{j_1} xj1與特征域 f j 2 f_{j_2} fj2對應的隐向量，同理 w j 2 , f j 1 ⃗ \vec{w_{j_2, f_{j_1}}} wj2,fj1
表示特征 x j 2 x_{j_2} xj2與特征域 f j 1 f_{j_1} fj1對應的隐向量。
是以FFM與FM的差別是隐特征向量由 w j 1 ⃗ \vec{w_{j_1}} wj1
變成了 w j 1 , f j 2 ⃗ \vec{w_{j_1, f_{j_2}}} wj1,fj2
，意味着每種特征都會針對其他特征域學習一個隐向量。當 x j 1 x_{j_1} xj1和 x j 2 x_{j_2} xj2兩種特征進行交叉時， x j 1 x_{j_1} xj1挑出與 x j 2 x_{j_2} xj2所屬特征域 f j 2 f_{j_2} fj2的隐向量 w j 1 , f j 2 ⃗ \vec{w_{j_1, f_{j_2}}} wj1,fj2
與 x j 2 x_{j_2} xj2挑出與 x j 1 x_{j_1} xj1所屬特征域 f j 1 f_{j_1} fj1的隐向量 w j 2 , f j 1 ⃗ \vec{w_{j_2, f_{j_1}}} wj2,fj1
進行交叉計算。
FFM模型在訓練時，需要學習 n n n個特征在 f f f個域上的 k k k維隐向量，則二階參數量有 n ⋅ f ⋅ k n \cdot f \cdot k n⋅f⋅k個，且由于隐向量和域相關，FFM的二階部分不能化簡，是以預測複雜度是 O ( k n 2 ) O(kn^2) O(kn2)。
FFM實際特征交叉舉例：
5. GBDT+LR
1. 簡介
FFM模型增加了特征交叉能力，但是隻能做二階特征交叉，若提高特征交叉的次元，則會産生組合爆炸和計算複雜度過高的問題。2014年，Facebook提出了基于GBDT+LR組合模型的解決方案，其中用GBDT自動進行特征篩選群組合，再把特征向量輸入LR模型，這兩步是獨立訓練的，是以不需要把LR的梯度回傳到GBDT。
2. GBDT是什麼
基本結構：決策樹組成的樹林，通過逐一生成決策子樹生成整個樹林。
生成新子樹過程：利用樣本标簽值與目前樹林預測值之間的殘差。
學習方式：梯度提升。
預測方式：把所有子樹結果加起來。
理論上，若可以無限生成決策樹，則GBDT可以無限逼近目标拟合函數，進而達到減小預測誤差的目的。
3. GBDT的特征轉換過程
GBDT模型訓練好之後，輸入一個樣本，根據每個節點的規則最終落入某一葉子節點，則該節點置為1，其他葉子節點置為0。所有葉子節點組成的向量即形成了該棵樹的特征向量。把GBDT所有子樹的特征向量連接配接起來，即形成了該樣本的離散型特征向量。
以上圖為例，若輸入一個樣本，分别落在了三顆子樹的3，1，4葉節點，則最終的樣本特征向量是：[0,0,1,0, 1,0,0,0, 0,0,0,1]。
4. 特點總結
（1）決策樹的深度決定了特征交叉的階數，比FM具有更強的特征交叉能力。
（2）GBDT容易産生過拟合，且容易丢失特征的數值資訊。
（3）是以特征交叉能力強不意味着效果就一定會好。
（4）組合模型的提出意味着特征工程可以完全交由一個獨立的模型來完成，模型的輸入是原始的特征向量，不需要投入過多人工篩選和模型設計的精力，真正的實作端到端訓練。
6. 大規模分段線性模型(LS-PLM）
1. 簡介
LS-PLM（Large Scale Piece-wise Linear Model），早在2012年就成為了阿裡巴巴主流的推薦模型，主要應用于各類廣告推薦場景，在2017年公之于衆。
2. 模型結構
LS-PLM，結構與三層神經網絡相似，在LR的基礎上采用分而治之的思想，先對樣本進行聚類分類，再對分類的樣本使用LR進行CTR預估。是以本質上可以看成是對LR的推廣，是以又被稱為MLR（Mixed Logistic Regression，混合邏輯回歸）模型。比如女裝廣告的CTR預估不希望把男性使用者點選數位類産品的樣本資料納入訓練集。
3. 原理
LS-PLM的數學形式如下：
f ( x ) = ∑ i = 1 m π i ( x ) ⋅ η i ( x ) = ∑ i = 1 m e μ i ⋅ x ∑ j = 1 m e μ j ⋅ x ⋅ 1 1 + e − w j ⋅ x f(x) = \sum^{m}_{i=1} \pi_{i}(x) \cdot \eta_{i}(x) = \sum^{m}_{i=1}{\frac{e^{\mu_i \cdot x}}{\sum^{m}_{j=1} e^{\mu_j \cdot x}} \cdot \frac{1}{1 + e^{-w_j \cdot x}}} f(x)=i=1∑mπi(x)⋅ηi(x)=i=1∑m∑j=1meμj⋅xeμi⋅x⋅1+e−wj⋅x1
其中 π \pi π為聚類函數，采用了 s o f t m a x softmax softmax函數對樣本進行多分類。 m m m為超參數，表示分類數，可以較好的平衡模型的拟合與推廣能力。當 m = 1 m=1 m=1時，LS-PLM退化為LR。 m m m越大，表示能力越精确，拟合能力越強，但是參數量越大。
在每個分類内部構件LR模型，将每個樣本的各個分類機率與LR的得分進行權重平均，得到最終的預估值。
4. 模型優點
（1）端到端的非線性學習能力。LS-PLM的分類能力使得模型可以提取樣本中的非線性特征，省去了大量的人工樣本處理和特征工程的過程，可以完成端到端的訓練。
（2）模型的稀疏性強。LS-PLM模組化時引入了L1和L2範數，使得最終訓練完的模型具有較高的稀疏性，是以部署時更加輕量級。
參考資料
《深度學習推薦系統實戰》 – 極客時間，王喆
《深度學習推薦系統》 – 王喆
深入FFM原理與實踐 – 美團技術團隊
本文首發于個人小站：NotLate.net，歡迎關注。