FM的特點：
- 針對稀疏數據也能有效估計；
- FM復雜度是線性的，計算快；
- 對數據數據沒有嚴格的要求，任意的實數向量都可以。
FM詳細介紹
FM，作為線性回歸的拓展，能夠挖掘特征與特征之間的聯(lián)系。
大家都知道，線性回歸的方程為
y=w_0+\sum_{i=1}^{n}w_ix_i
其中：n是特征維度，w是特征的權重。
度為2的FM的方程為：
y=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n}\sum_{j=i+1}^{n}\langle \textbf v_i,\textbf v_j\rangle x_ix_j
其中：
w_0 ∈\mathbb R, w∈\mathbb R^n, V∈\mathbb R^{n×k}
V=\left\{ \begin{matrix} \textbf v_1\\\textbf v_2\\\textbf v_3\\...\\\textbf v_n \end{matrix} \right\}
\langle \textbf v_i,\textbf v_j\rangle表示兩個向量的點積，結果是一個值，表示x_i與x_j的組合特征權重大小。對于n個特征，總共有n個行向量\textbf v_i，這些向量組成了V。
這里可以看見x_i與x_j的交互特征通過向量v_i與v_j來表示，這里有一個問題，為什么要用向量來表示這些交互特征而不通過一個值w_{ij}來描述呢？
這里涉及到了FM的關鍵思想：只用一個值w_{ij}來描述交互特征，如果訓練數據中針對兩個特征x_i與x_j，沒有同時非0的數據，那么x_ix_j一直等于0，導致w_{ij}一直為0，無法更新。而用向量v_i與v_j來表示交互特征的權重，這兩個向量在其他特征更新時會同時更新。v_i揭示了第i個特征的內在屬性，如果特征i與特征j在其他特征上有關聯(lián)，反映到向量v_i與v_j上，在計算兩者的關系就十分的清楚了。
時間復雜度
原始的FM時間復雜度為O(kn^2)，通過簡單的變換，能將復雜度降低到O(kn)，而且對于稀疏特征矩陣來說，復雜度可以降低到O(k\overline{m_D})，其中\overline{m_D}$是所有特征非零數量的平均數。
度為d的FM公式
公式如下：
其時間復雜度為O(kn^d)，也能化簡到線性時間。
FM的分布式計算
分布式計算與LR類似，首先按樣本求wx規(guī)約求和，然后按特征規(guī)約求梯度即可。
