三種算法的對比
| FM | FFM | AFM | |
|---|---|---|---|
| 交叉項 |  |  | |
| 待學習的參數個數 | （1）LR部分： 1 + n 1+n 1+n （2）embedding 部分： n ∗ k n * k n∗k | （1）LR部分： 1 + n 1+n 1+n （2）embedding 部分： n ∗ f ∗ k n * f * k n∗f∗k | （1）FM部分參數： 1 + n 1+n 1+n（2）Embedding部分參數: n ∗ k n * k n∗k（3）Attention Network部分參數: k ∗ t + t ∗ 2 k * t + t * 2 k∗t+t∗2（4）MLP部分參數： k ∗ 1 k*1 k∗1 |
| 優點 | 使用隐向量相乘模拟特征交叉，适用于稀疏場景 | 提出field的概念，細化隐向量的表示 | 通過attention network學習不同特征互動的重要性，性能更好，可解釋性強 |
| 缺點 | 一個特征隻對應一個向量 | 慢 | 未考慮高階組合特征 |
1 FM
1.1 模型方程
1.2 論文連結
Factorization Machines
分解機(Factorization Machines)推薦算法原理
1.3 特點
FM模型對稀疏資料有更好的學習能力，通過互動項可以學習特征之間的關聯關系，并且保證了學習效率和預估能力，具有線性的計算複雜度。
1.4 原理
對于categorical(類别)類型特征，需要經過One-Hot Encoding轉換成數值型特征，而大部分樣本資料特征經過One-Hot編碼之後是比較稀疏的(即特定樣本的特征向量很多元度為0)，同時導緻特征空間大。
通過觀察大量的樣本資料可以發現，某些特征經過關聯之後，與label之間的相關性就會提高。例如，“USA”與“Thanksgiving”、“China”與“Chinese New Year”這樣的關聯特征，對使用者的點選有着正向的影響。是以，引入兩個特征的組合是非常有意義的。
一般的線性模型為：
從上面的式子很容易看出，一般的線性模型壓根沒有考慮特征間的關聯(組合)。為了表述特征間的相關性，我們采用多項式模型。在多項式模型中，特征xi與xj的組合用xixj表示。為了簡單起見，我們讨論二階多項式模型。具體的模型表達式如下：
然而，每個參數 wij 的訓練需要大量 xi 和xj都非零的樣本，由于樣本資料本來就比較稀疏，滿足“xi 和 xj 都非零”的樣本将會非常少。訓練樣本的不足，很容易導緻參數 wij 不準确，最終将嚴重影響模型的性能。
如何解決二次項參數的訓練問題呢？矩陣分解提供了一種解決思路。FM借鑒了矩陣分解的方式，将Wij拆解成vi與vj的向量點積，此時就不必要求xi與xj一定要同時非零的樣本出現了，因為即使沒有這種樣本，假設有xh與xj的同時非零的樣本存在，xk與xi同時非零的樣本的存在，我們可以學到vh、vj、vk、vi。這樣獲得了vi與vj，就獲得了曾經的wij。(此處用曾經的wij并不準确，隻是友善了解這個曲線救國的過程。)
對輔助向量的次元k值的限定，反映了FM模型的表達能力。
由此得到FM的模型方程：
通過改寫模型方程，可以将其複雜度降成線性的O(kn)，具體過程如下：
FFM（Field-aware FM）
1.1 模型方程
1.2 論文連結
Field-aware Factorization Machines for CTR Prediction
1.3 特點
FFM引入了field的概念。從論文中，可以看出：
- 對于包含分類特征并且轉換為二進制特征的資料集，FFM表現很好
- 如果轉換後的集合不夠稀疏，FFM表現不是特别突出
- 将FFM應用于數值資料集會比較困難
- FFMs在logloss方面優于其他模型，但它也比LMs和FMs需要更長的訓練時間
1.4 原理
FM中一個特征隻對應一個向量，而在實際場景中特征和不同field的特征互動時應該使用不同的向量，這就是Field-aware FM（FFM）的提出動機。通過引入field的概念，FFM把相同性質的特征歸于同一個field， 每個特征的隐向量不再是隻有一個，而是針對每個field學習一個獨立的隐向量，防止互相影響。
說白了，就是将幾個Field進行組合後，再在組合而成的Field的基礎之上進行FM，實際上是增加了訓練樣本，使得結果更精确，但是它的訓練時間比較尴尬：O(kn^2)，而FM是線性的：O(kn)。
對比FM與FFM的交叉項，對于特征xi，它的隐向量不再是隻有一個Vi，而是針對每個field學習一個獨立的隐向量Vi，fj。
FM的交叉項：
FFM的交叉項：
FM可以看作FFM的特例，是把所有特征都歸屬到一個field時的FFM模型。
AFM（Attentional FM）
1.1 模型方程
1.2 論文連結
論文連結：Attentional Factorization Machines:Learning the Weight of Feature Interactions via Attention Networks∗
1.3 特點
AFM區分不同特征互相作用的方式不再像ffm那麼笨重，而且用一個神經網絡學習得到參數 a i j a_{ij} aij ，總體參數量增加也不明顯。從論文中可以看出，AFM可以更好地拟合資料，進而使預測更加準确，對未知資料的泛化效果也更好。
1.4 原理
AFM也是FM的一種改進，它通過一個attention network來學習不同特征互動的重要性。
顯然，不是所有的二階特征互動的重要性都是一樣的，例如：在句子"US continues taking a leading role on foreign payment transparency"中，除了"foreign payment transparency"，其它句子明顯與财經新聞無關，它們之間的交叉作用可認為對主題預測是一種噪音。如何通過機器自動的學習到這些重要性是這篇論文解決的最重要的問題。
FM模型中的兩兩交叉層可以表示為：
這裡
表示element-wise product。然後通過全連接配接層映射至目标，有：
在上式的兩兩交叉的前面引入權重的話，即在FM的兩兩交叉層增加Attention-based pooling Layer， 則變為下式：
這裡aij是特征交叉wij的注意力分（attention score），以說明wij的重要程度。
下面是訓練 aij了。一種直接的做法是通過最小化損失函數而訓練得到，但是在樣本中，如果兩個做交叉的兩特征并不一起出現，訓練就不容易了。為此，作者引入了多層感覺機（multi-layer perceptron ）來做訓練。
attention network 可定義為：
那麼最後AFM模型可表示為：
大量的實驗表明，在FM上使用attention有兩個好處:它不僅能帶來更好的性能，而且還能觀察哪些二階特征互動對預測的貢獻更大。
總結
在計算廣告中使用邏輯回歸等算法進行CTR（廣告點選率）、CVR（轉化率）等預估時，有三個重要的問題：
1） 特征稀疏問題。
2） 特征空間非常大的問題。
3） 沒有考慮特征之間的互相關系。
由于以上三個問題的存在，FM應運而生。
FFM是基于FM的，它改進的地方在于添加了field， 每個特征的隐向量不再是隻有一個，而是針對每個field學習一個獨立的隐向量。
AFM也是FM的一種改進，它通過一個attention network來學習不同特征互動的重要性。在FM上使用attention不僅能帶來更好的性能，而且還能觀察哪些二階特征互動對預測的貢獻更大。
參考文獻
邏輯回歸、FM、FFM比較總結
FM和FFM算法精髓
FM與FFM
FM算法及FFM算法
FM及FFM算法
FM系列算法解讀（FM+FFM+DeepFM）
FFM
AFM（Attention+FM）-----Attentional Factorization Machines:Learning the Weight of Feature Interactions via Attention Network
深度學習在CTR預估中的應用