大家好，我是Jesse，這是我的第一篇專欄文章，以一篇經典的論文FM開始吧：

更好的觀看體驗請點選這裡

原文：《Factorization Machines》

一、問題由來

在計算廣告和推薦系統中，CTR預估（click-through rate）是非常重要的一個環節，判斷一個商品的是否進行推薦需要根據CTR預估的點選率來進行。傳統的邏輯迴歸（LR）模型是一種廣義線性模型，非常容易實現

大規模實時並行

處理，因此在工業界獲得了廣泛應用，但是線性模型的學習能力有限，不能捕獲高階特徵（非線性資訊），而在進行CTR預估時，除了單特徵外，往往要對特徵進行組合。對於特徵組合來說，業界現在通用的做法主要有兩大類：

FM系列與DNN系列

。今天，我們就來分享下FM演算法。

二、為什麼需要FM

1、一方面，特徵組合是許多機器學習建模過程中遇到的問題，如果對特徵直接建模，很有可能會忽略掉特徵與特徵之間的關聯資訊，因此，可以透過構建新的交叉特徵這一特徵組合方式提高模型的效果。

2、另一方面，高維的稀疏矩陣是實際工程中常見的問題，並且直接計算會導致計算量過大，特徵權值更新緩慢。試想一個10000*100的表，每一列都有8種元素，經過one-hot獨熱編碼之後，會產生一個10000*800的表。因此表中每行元素只有100個值為1，700個值為0。特徵空間急劇變大，以淘寶上的item為例，將item進行one-hot編碼以後，樣本空間有一個categorical變為了百萬維的數值特徵，特徵空間一下子暴增一百萬。所以大廠動不動上億維度，就是這麼來的。

而FM的優勢就在於對這兩方面問題的處理。首先是

特徵組合

，透過對兩兩特徵組合，引入交叉項特徵，提高模型得分；其次是應對

高維災難

，透過引入隱向量（且對引數矩陣進行矩陣分解），完成對特徵的引數估計。

三、原理及求解

在看FM演算法前，我們先回顧一下最常見的線性表示式：

傳統LR

其中

為初始權值，或者理解為偏置項，

為每個特徵

對應的權值。可以看到，這種線性表示式只描述了每單個特徵與輸出的關係。

而FM的表示式如下，可觀察到，只是在線性表示式後面加入了新的交叉項特徵及對應的權值。

FM數學形式

求解過程

：

從上面的式子可以很容易看出，組合部分的特徵相關引數共有n（n−1）/2個。但是如第二部分所分析，在資料很稀疏的情況下，滿足

，

都不為0的情況非常少，這樣將導致

無法透過訓練得出。

為了求出

，我們對每一個特徵分量

引入輔助向量

。然後，利用

對

進行求解（矩陣分解的思路：對於正定矩陣W，存在矩陣V，使得

）：

輔助向量Vi

那麼

組成的矩陣可以表示為：

這樣，FM的表示式就變為了：

可以看到上面這個方程的時間複雜度是

，但是透過下面的變換，會變成線性的時間複雜度O（kn）。在稀疏的情況下，大部分的x中的元素都是0，我們在計算的時候，只需要進行非0值的計算就可以了。

具體推導過程如下：（重要的

化簡

過程）

四、引數求解

利用梯度下降法，透過求損失函式對特徵（輸入項）的導數計算出梯度，從而更新權值。設m為樣本個數，θ為權值。

其中，

是和i無關的，可以事先求出來。每個梯度都可以在O（1）時間內求得，整體的引數更新的時間為O（kn）。

五、改進

在FM中，對於特徵

，

與

，

與

，都是使用

去和

、

做內積。但是對於不同的特徵組合，比如天氣與地點，天氣與性別，關聯的程度是不一樣的，都使用同樣的向量去與不同的特徵做內積，會帶來明顯的資訊損失。所以引出了FFM（本系列文章暫時未寫到）。

一個小問題：隱向量

就是embedding vector?

答案：不是，具體計算過程大家可以舉個例推導下。

結論：

我們口中的隱向量

實際上是一個向量組，其形狀為（輸入特徵One-hot後的長度，自定義長度（嵌入向量的長度如k維））；

隱向量

代表的並不是embedding vector，而是在對輸入進行embedding vector的向量組，也可理解為是一個權重矩陣；

由輸入xi*

vi得到的向量（維度為1*k

）才是真正的embedding vector。

第一篇博文就到此結束啦，之後會繼續分享計算廣告/推薦系統相關的論文和知識。

實現FM的一個Demo，感興趣的童鞋可以看下我的github。