在上一篇文章中，我們講到了使用邏輯回歸和梯度提升決策樹組合的模型融合辦法，用于CTR預估，給這個組合起了個名字，叫“輯度組合”。這對組合中，梯度提升決策樹GBDT，所起的作用就是對原始的特征做各種有效的組合，一顆樹一個葉子節點就是一種特征組合。

從特征組合說起

從邏輯回歸最樸素的特征組合就是二階笛卡爾乘積，但是這種暴力組合存在如下問題：
1.兩兩組合導致特征維度災難；
2.組合后的特征不見得都有效，事實上大部分可能無效；
3.組合后的特征樣本非常稀疏，即組合容易，但是樣本中可能不存在對應的組合，也就沒辦法在訓練時更新參數。

如果把包含了特征兩兩組合的邏輯回歸線性部分寫出來，就是：
$$\hat{y}={\omega }_0+\sum _{i=1}^n{\omega }_i{x}_i+\sum _{i=1}^n\sum _{j=j+1}^n{\omega }_{ij}{x}_i{x}_j$$

這和原始的邏輯回歸相比，多了后面的部分，特征兩兩組合，也需要去學習對應的參數權重。
問題是兩兩組合后可能沒有樣本能歐學習到$w_{ij}，在應用中，對于這些組合，也只能放棄，因為沒有學到權重。

針對這個問題，就有了一個新的算法模型：因子分解機模型，也叫FM,即Factorization Machine。因子分解機也常常用來做模型融合。

FM模型

1.原理

因子分解機模型是在2010年被提出，因為邏輯回歸在做特征組合時樣本稀疏，無法學習到很多特征組合的權重，所以因子分解機的提出者就想，能否對上面那個公式中的$w_{ij}$做解耦，讓每一個特征學習一個隱因子向量出來。

正如矩陣分解時，為每一個用戶和每一個物品各自都學習一個隱因子向量，這樣，任何兩個特征需要組合時，只需隱因子變量做向量點積，就是兩者組合特征的權重了。

針對邏輯回歸的線性部分：
$$\hat{y}={\omega }_0+\sum _{i=1}^n{\omega }_i{x}_i+\sum _{i=1}^n\sum _{j=i+1}^n<v_i,v_j>x_i{x}_j$$

這個公式和前面特征組合的公式相比，不同之處就是原來有個\omega_{ij},變成了兩個隱因子向量的點積<V_i,V_j>。

它認為兩個特征之間，即便沒有出現在一條樣本中，也是有間接聯系的。比如特征A和特征B,出現在一些樣本中，特征B和特征C也出現在一些樣本中，那么特征A和特征C無論是否出現在一些樣本中，我們有理由認為兩個特征仍然有些聯系。

如果在實際預測CTR時，特征A和特征C真的同時出現在一些樣本中，如果你用的是因子分解模型，你可以直接取特征A和特征C的隱因子向量，進行點積計算，就得到兩者組合的權重。因子分解機的先進之處就在于此。

既然二階組合特征可以學到隱因子向量，那么三階、四階、五階呢？實際上，組合越多，計算復雜度就會陡增，一般在實際使用中，因子分解機多用在二階特征組合中。

2.模型訓練

因子分解機的參數學習并無特別之處，看目標函數，這里是把他當做融合模型來看的，用來做CTR預估，因預測目標是一個二分類，因子分解機的輸出還需要經過sigmoid函數變換：
$$\sigma (\hat{y})=\frac{1}{1+e^{?\hat{y}}}$$

因此損失目標函數為：
$$loss(\theta )=?\frac{1}{m}\sum _{i=1}^m[y^{(i)}log(\sigma (\hat{y}))+(1?y^{(i)})log(1?\sigma (\hat{y})]$$

公式中$\sigma (\hat{y})$ 是因子分解機的預測輸出后經過sigma函數變換得到的預估CTR,$\hat{y}$是真實樣本的類別標記，正樣本為1，負樣本為0，m是樣本總數。

對于這個損失目標函數使用梯度下降或者隨機梯度下降，就可以得到模型的參數，注意函數實際上還需要加上正則項。

3.預測階段

因子分解機中二階特征組合那一部分，在實際計算時，復雜度有點高，如果隱因子向量的維度是k,特征維度是n,那么這個復雜度為O(kn^2),其中n方是特征要兩兩組合，k是每次組合都要對k維向量計算
點積。需稍微改造一下，改造過程如下:

loop1 begin: 循環k次，k就是隱因子向量的維度，其中，循環到第f次時做以下事情loop2 begin:循環n個特征，第i次循環時做這樣的事情1. 從第i個特征的隱因子向量中拿出第f維的值2. 計算兩個值：A是特征值和f維的值相乘，B是A的平方loop2 end把n個A累加起來，并平方得到C，把n個B也累加起來，得到D用C減D，得到Eloop1 end把k次循環得到的k個E累加起來，除以2

這就是因子分解機中，二階組合部分的實際計算方法，目前復雜度下降為O(kn)。

4.一網打盡其他模型

下面繼續帶你見識一些因子分解機的神奇之處。看下面這張圖：

下面繼續帶你見識一些因子分解機的神奇之處。看下面這張圖：

這張圖中的每一條樣本都記錄了用戶對電影的評分，最右邊的y是評分，也就是預測目標；左邊的特征有五種，用戶ID、當前評分的電影ID、曾經評過的其他分、評分時間、上一次評分的電影。

現在我們來看因子分解機如何一網打盡其他模型的，這里說的打敗是說模型可以變形成其他模型。

前面例子，因子分解機實現了帶有特征組合的邏輯回歸。

現在假設圖中的樣本特征只留下用戶ID和電影ID,因子分解機模型就變成：
$$\hat{y}={\omega }_0+{\omega }_u+{\omega }_i+<V_u,V_i>$$

用戶ID和電影ID，在一條樣本中，各自都只有一個維度1，其他都是0。所以在一階部分就沒有了求和符號，直接是$w_u$和$w_i$,二階部分乘積也只剩下了1，其他都為0，就轉變為偏置信息的SVD。

繼續，在SVD基礎上把樣本中的特征加上用戶歷史評分過的電影ID,再求隱因子向量，就轉變為SVD++;再加上時間信息，就變成了time-SVD。

因子分解機把前面講過的矩陣分解一網打盡了，順便還干起了邏輯回歸的工作。正因為如此，因子分解機常常用來做模型融合，在推薦系統的排序階段肩負起對召回結果做重排序的任務。

5.FFM

在因子分解機基礎上可以進行改進，改進思路是：不但認為特征和特征之間潛藏著一些關系，還認為特征和特征類型也有千絲萬縷的關系。

這個特征類型，就是某些特征實際上來自數據的同一個字段。比如用戶id，占據了很多維度，變成了很多特征，但他們都屬于同一個類型，都叫做用戶ID。這個特征類型就是字段，即Field.所以這種改進叫做Field-aware Factorization Machines ，簡稱FFM。

因子分解機模型如下：
KaTeX parse error: Expected group after '_' at position 42: …_{i=1}^n{\omega_?}

總結

今天，我給你介紹了另一種常用來做CTR預估的模型，因子分解機。因子分解機最早提出在2010年，在一些數據挖掘比賽中取得了不錯的成績，后來被引入到工業界做模型融合，也表現不俗。
嚴格來說，因子分解機也算是矩陣分解算法的一種，因為它的學習結果也是隱因子向量，也是用隱因子向量的乘積來代替單個權重參數。