（作者：陳玓玏）
1. 為什麼要用FM
在計算廣告中使用邏輯回歸等算法進行CTR（廣告點選率）、CVR（轉化率）等預估時，有三個重要的問題：
1） 特征稀疏問題。關于客戶的特征和關于廣告的特征都有很多的标稱型特征，如客戶所在地區、職業、性别，以及廣告的主題等，這些屬性無法比較大小，是以需要經過one-hot編碼處理才能進入模型。但one-hot編碼後會産生大量的0值特征，這對于邏輯回歸、SVM等模型的求解都是非常不友好的，會造成預測性能差。
2） 特征空間非常大的問題。如果原來的标稱特征有500個可選值，那麼這個特征經過one-hot編碼就會衍生成500個特征，那麼對于電影、電商等品類标稱特征非常多的場景來說，求解會變得困難。
3） 沒有考慮特征之間的互相關系。但考慮這些是有必要的，因為點選率本身是屬于預測客戶的特征與廣告特征之間的一個比對度，是以必須關注客戶特征和廣告特征的關系（比如女性關注美妝），這一點和分類問題是不一樣的。在這種情況下，适合使用的傳統機器學習算法隻有SVM，因為SVM的核方法能夠學習它的交叉特征，但是SVM不适合稀疏場景。
由于以上三個問題的存在，FM應運而生，那麼FM的特點也很明顯了：适用于特征稀疏的場景，并且能夠學習特征之間的關系。
2. FM模型公式
傳統的線性模型的公式如下：
y ( x ) = ω 0 + ∑ i = 1 n ω i x i y(x) = \omega_0+\sum_{i=1}^{n}\omega_ix_i y(x)=ω0+i=1∑nωixi
這個公式中還未包含交叉特征，那麼現在把所有特征都做交叉：
y ( x ) = ω 0 + ∑ i = 1 n ω i x i + ∑ i = 1 n ∑ j = i + 1 n ω i j x i x j y(x) = \omega_0+\sum_{i=1}^{n}\omega_ix_i+\sum_{i=1}^{n}\sum_{j=i+1}^{n}\omega_{ij}x_ix_j y(x)=ω0+i=1∑nωixi+i=1∑nj=i+1∑nωijxixj
最後一項即交叉特征和它們的權值的乘積和，即 ω 12 x 1 x 2 + ω 13 x 1 x 3 + … + ω ( n − 1 ) n x n − 1 x n \omega_{12}x_1x_2+\omega_{13}x_1x_3+…+\omega_{(n-1)n}x_{n-1}x_n ω12x1x2+ω13x1x3+…+ω(n−1)nxn−1xn。接下來的問題是， ω i \omega_i ωi的求解是很簡單的，那怎麼求解 ω i j \omega_{ij} ωij呢？在SVM中我們是用核方法來求解的，但這裡不行，這裡是借鑒的矩陣分解的思想。
我們首先把交叉特征的權值矩陣寫出來：
( ω 11 ω 12 ω 13 ⋯ ω 1 n ω 21 ω 22 ω 23 ⋯ ω 2 n ⋮ ⋮ ⋮ ⋱ ⋮ ω n 1 ω n 2 ω n 3 ⋯ ω n n ) \begin{pmatrix} \omega_{11} & \omega_{12} & \omega_{13} & \cdots & \omega_{1n} \\ \omega_{21} & \omega_{22} & \omega_{23} & \cdots & \omega_{2n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \omega_{n1} & \omega_{n2} & \omega_{n3} & \cdots & \omega_{nn} \\ \end{pmatrix} ⎝⎜⎜⎜⎛ω11ω21⋮ωn1ω12ω22⋮ωn2ω13ω23⋮ωn3⋯⋯⋱⋯ω1nω2n⋮ωnn⎠⎟⎟⎟⎞
因為我們在實際的模型公式是隻需要計算不重複的值，是以雖然現在寫出來的矩陣中有 n 2 n^2 n2個值，模型公式中隻用到了矩陣中 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n−1)個值。實際上這個矩陣是一個對稱矩陣，因為本身交叉特征 x 1 x 2 x_1x_2 x1x2和 x 2 x 1 x_2x_1 x2x1就是一樣的，系數自然也一樣。至于對角矩陣，隻要它的值能保證矩陣正定，也就是滿足可分解條件即可。那麼 ω \omega ω矩陣可以分解為 V T V V^TV VTV的形式，如下所示：
ω = V T V = ( v 11 v 12 v 13 ⋯ v 1 k v 21 v 22 v 23 ⋯ v 2 k ⋮ ⋮ ⋮ ⋱ ⋮ v n 1 v n 2 v n 3 ⋯ v n k ) ( v 11 v 21 v 31 ⋯ v n 1 v 12 v 22 v 32 ⋯ v n 2 ⋮ ⋮ ⋮ ⋱ ⋮ v 1 k v 2 k v 3 k ⋯ v n k ) \omega = V^TV = \begin{pmatrix} v_{11} & v_{12} & v_{13} & \cdots & v_{1k} \\ v_{21} & v_{22} & v_{23} & \cdots & v_{2k} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ v_{n1} & v_{n2} & v_{n3} & \cdots & v_{nk} \\ \end{pmatrix} \begin{pmatrix} v_{11} & v_{21} & v_{31} & \cdots & v_{n1} \\ v_{12} & v_{22} & v_{32} & \cdots & v_{n2} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ v_{1k} & v_{2k} & v_{3k} & \cdots & v_{nk} \end{pmatrix} ω=VTV=⎝⎜⎜⎜⎛v11v21⋮vn1v12v22⋮vn2v13v23⋮vn3⋯⋯⋱⋯v1kv2k⋮vnk⎠⎟⎟⎟⎞⎝⎜⎜⎜⎛v11v12⋮v1kv21v22⋮v2kv31v32⋮v3k⋯⋯⋱⋯vn1vn2⋮vnk⎠⎟⎟⎟⎞
也就是将大小為 n ∗ n n*n n∗n的 ω \omega ω矩陣分解成了 n ∗ k n*k n∗k的 V V V矩陣的乘積。一般 k k k是要遠小于 n n n的，至于 k k k具體是多少，為什麼會遠小于 n n n，這個這篇算法寫完了再研究一下。
為了友善推導，把上面的公式再簡化一下：
y ( x ) = ω 0 + ∑ i = 1 n ω i x i + ∑ i = 1 n ∑ j = i + 1 n < v i ⃗ , v j ⃗ > x i x j y(x) = \omega_0+\sum_{i=1}^{n}\omega_ix_i+\sum_{i=1}^{n}\sum_{j=i+1}^{n}<\vec{v_i},\vec{v_j}>x_ix_j y(x)=ω0+i=1∑nωixi+i=1∑nj=i+1∑n<vi
,vj
>xixj
< v i , v j > <v_i,v_j> <vi,vj>表示向量點乘，直接這麼看仍然是看不出什麼名堂的，接下來推導一下：
∑ i = 1 n ∑ j = i + 1 n < v i ⃗ , v j ⃗ > x i x j = 1 2 ∑ i = 1 n ∑ j = 1 n < v i ⃗ , v j ⃗ > x i x j − 1 2 ∑ i = 1 n < v i ⃗ , v i ⃗ > x i x i \sum_{i=1}^{n}\sum_{j=i+1}^{n}<\vec {v_i},\vec {v_j}>x_ix_j = \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}<\vec{v_i},\vec{v_j}>x_ix_j-\frac{1}{2}\sum_{i=1}^{n}<\vec{v_i},\vec{v_i}>x_ix_i i=1∑nj=i+1∑n<vi
,vj
>xixj=21i=1∑nj=1∑n<vi
,vj
>xixj−21i=1∑n<vi
,vi
>xixi
可以這樣做的原因是，兩項相減，減去的是 ω \omega ω矩陣對角線上的元素，剩下的是對稱元素， 1 2 \frac{1}{2} 21合并後就是原來的模型公式。接着往下展開：
∑ i = 1 n ∑ j = i + 1 n < v i ⃗ , v j ⃗ > x i x j = 1 2 ∑ i = 1 n ∑ j = 1 n ∑ f = 1 k v i f v j f x i x j − 1 2 ∑ i = 1 n ∑ f = 1 k v i f v i f x i x i \sum_{i=1}^{n}\sum_{j=i+1}^{n}<\vec{v_i},\vec{v_j}>x_ix_j = \frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{f=1}^{k}v_{if}v_{jf}x_ix_j-\frac{1}{2}\sum_{i=1}^{n}\sum_{f=1}^{k}v_{if}v_{if}x_ix_i i=1∑nj=i+1∑n<vi
,vj
>xixj=21i=1∑nj=1∑nf=1∑kvifvjfxixj−21i=1∑nf=1∑kvifvifxixi
把求和符号放到式子裡面，得到：
∑ i = 1 n ∑ j = i + 1 n < v i , v j > x i x j = 1 2 ∑ f = 1 k ( ( ∑ i = 1 n v i f x i ) ( ∑ j = 1 n v j f x j ) − ∑ i = 1 n v i f 2 x i 2 ) = 1 2 ∑ f = 1 k ( ( ∑ i = 1 n v i f x i ) 2 − ∑ i = 1 n v i f 2 x i 2 ) \sum_{i=1}^{n}\sum_{j=i+1}^{n}<v_i,v_j>x_ix_j = \frac{1}{2}\sum_{f=1}^{k}((\sum_{i=1}^{n} v_{if}x_i)(\sum_{j=1}^{n}v_{jf}x_j)-\sum_{i=1}^{n}v_{if}^2x_i^2) \\ = \frac{1}{2}\sum_{f=1}^{k}((\sum_{i=1}^{n} v_{if}x_i)^2-\sum_{i=1}^{n}v_{if}^2x_i^2) i=1∑nj=i+1∑n<vi,vj>xixj=21f=1∑k((i=1∑nvifxi)(j=1∑nvjfxj)−i=1∑nvif2xi2)=21f=1∑k((i=1∑nvifxi)2−i=1∑nvif2xi2)
把這個結果帶入到模型公式中，我們就可以通過梯度下降法來求解 ω \omega ω和 v v v參數了，具體的求解其實還得看你想要什麼樣的結果，如果想要作為一個二分類問題來考慮，預測其點選的機率值，可以在 y ( x ) y(x) y(x)上加上sigmoid激活函數，那麼在使用梯度下降法求導時，也可以采用邏輯回歸的交叉熵損失函數來求解參數。但不管是用哪種損失函數來求解，都是要求 ∂ y ^ ∂ θ \frac{\partial \hat y}{\partial \theta} ∂θ∂y^的，其結果如下：
具體的公式就是把這個公式裡面的結果代入到損失函數求導的結果中，逐漸更新梯度直到收斂即可。
FM是一種比較靈活的模型，通過合适的特征變換方式，FM可以模拟二階多項式核的SVM模型、MF模型、SVD++模型等[1]。參數因子化使得 x h x i x_hx_i xhxi的參數和 x i x j x_ix_j xixj 的參數不再是互相獨立的，是以我們可以在樣本稀疏的情況下相對合理地估計FM的二次項參數。具體來說， x h x i x_hx_i xhxi的參數和 x i x j x_ix_j xixj 的系數分别為 < v h ⃗ , v i ⃗ > <\vec{v_h},\vec{v_i}> <vh
,vi
>和 < v i ⃗ , v j ⃗ > <\vec{v_i},\vec{v_j}> <vi
,vj
>，它們之間有共同項 v i ⃗ \vec{v_i} vi
。也就是說，所有包含“ x i x_i xi的非零組合特征”（存在某個 j ≠ i j\neq i j̸=i，使得 x i x j ≠ 0 x_ix_j\neq 0 xixj̸=0）的樣本都可以用來學習隐向量 v i ⃗ \vec{v_i} vi
，這很大程度上避免了資料稀疏性造成的影響。而在多項式模型中， ω h i \omega_{hi} ωhi 和 ω i j \omega_{ij} ωij 是互相獨立的[1]。
3. FFM算法
FFM是基于FM的，它改進的地方在于添加了field。之前在FM中，原始特征通過one-hot編碼新生成的特征，我們是沒有同一個标稱屬性one-hot編碼後延伸出的所有變量間原本的關系保留下來的，但在FFM中，這種關系得到了保留，那就是同一個原始特征延伸出的新特征屬于同一個Field。那麼FM是對每一個新特征學習一個長度為 k k k的隐式向量 v i ⃗ \vec{v_i} vi
，共有 n k nk nk個參數，而FFM是對每一個新特征學習 f f f個長度為 k k k的隐式向量 v i , f j ⃗ \vec{v_{i,f_j}} vi,fj
，共有 n k f nkf nkf個參數，也就是說，FFM有 f f f個FM中的參數矩陣，針對每個field都有一個。從這個角度看，FM是FFM的 f = 1 f=1 f=1的特例。
y ( x ) = ω 0 + ∑ i = 1 n ω i x i + ∑ i = 1 n ∑ j = i + 1 n < v i , f j ⃗ , v j , f i ⃗ > x i x j y(x) = \omega_0+\sum_{i=1}^{n}\omega_i x_i+\sum_{i=1}^{n}\sum_{j=i+1}^{n}<\vec{v_{i,f_j}},\vec{v_{j,f_i}}>x_ix_j y(x)=ω0+i=1∑nωixi+i=1∑nj=i+1∑n<vi,fj
,vj,fi
>xixj
3.1 FFM例子
考慮以下一個樣本：
将它轉換成FFM算法需要的形式：
那麼這個樣本的模型公式最後一個部分的計算結果為：
< v 1 , 2 ⃗ , v 2 , 1 ⃗ > <\vec{v_{1,2}},\vec{v_{2,1}}> <v1,2
,v2,1
>索引産生的邏輯是：第1個特征的feature index=1，第2個特征的field index=2，第2個特征的feature index=2，第1個特征的field index=1。後面依此類推。總之，紅色是field編号，藍色是特征編号，綠色是此樣本的特征取值，同一項的特征編号和field編号總是交叉的。
也就是說，一對向量v的第一個參數仍然和FM算法一樣的邏輯，隻不過不僅學習了特征之間的關系，還 在特征之間的關系中隐藏了各特征所代表的Field之間的關系，但這些field的關系并非通過兩兩配對來展現的，而是附加在特征上展現的。
FFM損失函數
網絡上實作的版本裡，模型公式沒有考慮非交叉特征，是以，其模型公式如下：
其損失函數如下：
3.2 一個想要讨論的問題
其實我不是很懂為什麼要交叉着來？想讓特征交叉得更充分？：
我自己關于FFM一個非常拙劣的了解就是，FM是把特征與特征之間的關系表現出來了，但是沒有表現客戶與品牌、客戶與主題這類filed與filed之間的關系，也就是說，把原始的特征的業務含義給稀釋掉了，但是通過加入field概念，計算不同特征與不同field的隐式向量（同一個field的特征與另一個field的隐式向量一起應該就能說明兩個field之間的互相關系了？），可能交叉也是這個含義吧，如果不交叉，以上說的這些其實就都沒有意義了。
參考文章：
1. https://blog.csdn.net/happytofly/article/details/80122160（這個原文是美團的人寫的，但連結失效了，這個也是一樣的内容）
2. https://blog.csdn.net/hiwallace/article/details/81333604
3. https://blog.csdn.net/hualinchangfeng/article/details/78606658