因數分解機(Factorization Machine, 簡稱FM)是一種不錯的CTR預估模型，也是我們現在在使用的廣告點擊率預估模型，比起著名的Logistic Regression, FM能夠把握一些組合的高階特征，因此擁有更強的表現力。 在做點擊率預估時，我們的特征往往來自於用戶(user)、 ...
因數分解機(Factorization Machine, 簡稱FM)是一種不錯的CTR預估模型，也是我們現在在使用的廣告點擊率預估模型，比起著名的Logistic Regression, FM能夠把握一些組合的高階特征，因此擁有更強的表現力。
在做點擊率預估時，我們的特征往往來自於用戶(user)、廣告(item)和上下文環境(context)，線上性模型中，這些特征不進行組合的話，就會發生一個很尷尬的情況，因為：
$$score = f(w_{user} * x_{user} + w_{item} * x_{item} + w_{contex} * x_{contex})$$
所以，對所有用戶--我們將得到相同的排序。
因此我們需要引入一些組合特征作為輸入模型，然而僅二階特征組合的可能性就是原始特征的平方之多，但是由於很多特征其實是相互獨立的，他們的組合併沒有什麼價值。FM就是一種能夠自動把握一些高階特征的點擊率預估模型，可以自動幫助使用者選擇合適的高階輸入。
我們先寫出帶有所有二階組合特征的目標函數，其中矩陣W中有n^2個參數，求解非常複雜：
$$y(x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{ij} x_i x_j$$
我們都知道在矩陣分解的協同過濾中中，我們認為每個用戶可以表示成一個K維的特征向量$u_k$,每個物品也能表示成一個高維向量$i_k$，這樣用戶與物品的相關性就可以用兩個向量的點擊表示，所有用戶與所有物品的相關性就可以用兩個矩陣相乘的形式表示出來了。
FM的模型參考了矩陣分解的思想，認為每個特征 $x_i$都可以用一個K維的特征向量$v_i$表示，那麼所有特征之前的相關性就也就可以用兩個矩陣的相乘進行表示了，模型表示如下：
其中矩陣W中代表了特征的特征向量的內積，既：$w_{ij}=v_i v_j$，所以，公式可以改寫為:
$$y(x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} v_{i} v_{j} x_i x_j$$
也就是：
$$y(x) = w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{h=i}^{k} v_{i,h} v_{j,h} x_i x_j$$
可以看出，W中的參數現在只有nk個了，因為一般有k<<n，所以FM大大降低的目標函數的複雜度。推導可得梯度公式：
$δy/δw_{0}=1$
$δy/δw_{i}=x_{i},i=1...n$
$δy/δv_{i,k}=x_{i}\sum{j \neq i} v_{j,k}x_{j}$
FM的優化可以用SGD來做，不過這裡推薦帶動量（momentum）的min-batch SGD演算法，試驗中比普通的SGD效果似乎更好。帶momentum的SGD模擬了物品運動中的慣性。
在傳統的SGD中：$x\_{t+1}=x\_t+Δx\_t,Δx\_t=-ŋg\_t$ ,其中 $g\_t$代表了梯度。而在momentum的SGD中：$Δx\_t=px\_{t-1}-ŋg\_t$。
不過比起LR, FM有一個缺點--目標函數是非凸的，雖然針對這個缺點也有一些研究比如一些凸函數形式的FM，不過在實踐中似乎這並不是一個很嚴重的問題，合適的初始化方式和優化方法一般是能夠給出一個可以接受的解的。
FM的另外一個缺點是有點耗費記憶體，對於每個特征都要用一個K維的向量表示導致參數數量是LR的K倍，這方面也是有一些研究的，比如李沐針對這個問題提出的DiFacto就是一個很好的能夠降低記憶體消耗的優化方案。
最後，還有一種著名的策略是FFM模型，FFM模型被稱為FM的升級版，把同一類的特征（比如一些用01向量編碼的的離散特征）歸到一個field里去，然後要求每個特征在每個field下都有一個不同的K維表示方式，這一下把參數的數量從K變成了FK(F是field的數量)，模型複雜度變的更高了。不過這樣做的效果確實不錯。
