在線性迴歸中，是假設每個特徵之間獨立的，也即是線性迴歸模型是無法捕獲特徵之間的關係。為了捕捉特徵之間的關係，便有了FM分解機的出現了。FM分解機是在線性迴歸的基礎上加上了交叉特徵，通過學習交叉特徵的權重從而得到每個交叉特徵的重要性。這個模型也經常用於點擊率預估。
因為線性迴歸中特徵都是獨立存在的，不存在特徵組合項，除非事先人工添加。如果要在線性迴歸上加入二特徵組合，可以如下：
其中，n代表樣本的特徵數量，x_i是第i個特徵的值，w_0，w_i，w_ij是模型參數。
從上面公式可以看出組合特徵一共有n(n-1)/2個，任意兩個參數之間都是獨立，這在數據稀疏的場景中，二次項參數的訓練會很困難，因為訓練w_ij需要大量非零的x_i和x_j，而樣本稀疏的話很難滿足x_i和x_j都非零。訓練樣本不足就很容易導致w_ij不準確，影響模型的性能
為了解決這個問題，可以引進矩陣分解的技術，這也是為什麼叫做分解機的原因。
根據矩陣分解的知識可以知道，一個實對稱矩陣W，可以進行如下分解：
類似的，所有的二次項參數w_ij可以組成一個對稱陣W，然後進行分解成以上形式，其中V的第j列便是第j維特徵的隱向量，也就是說每個w_ij =
其中<>表示兩個向量的點積
為了降低參數訓練的時間複雜度，我們將二次項進行化簡，如下：
由上式可知，v_if的訓練只需要樣本的x_i特徵非0即可，適合於稀疏數據。
同時，我們可以看到對於每個v_if的梯度中求和公式中沒有i，所以對i=1,..,N求和項都是一樣的，只需要計算一次就可以了，所以要更新所有v_if(共有nk個)的是時間複雜度為O(nk)，則FM可以在線性時間訓練和預測，是一種非常高效的模型。
對於上述的式子，我們可以使用隨機梯度下降的方法求解每個參數，即：
通過求解參數我們就可以得到最終的模型了。另外補充說明一點，對於隱向量V，每個v_i都是x_i特徵的一個低維的稠密表示，在實際應用中，數據一般都是很稀疏的Onehot類別特徵，通過FM就可以學習到特徵的一種Embedding表示，把離散特徵轉化為Dense Feature。同時這種Dense Feature還可以後續和DNN來結合，作為DNN的輸入，事實上用於DNN的CTR也是這個思路來做的。
閱讀更多 人工智能遇見磐創 的文章
