FM工程实现细节
关于FM算法网上已经介绍了很多，这里介绍一下FM算法的实现细节。
FM的模型方程为:
$$
y(x)=w_0 + \sum^n_{i=1}w_ix_i + \sum^n_{i=1}\sum^n_{j=i+1}v_iv_j^Tx_ix_j
$$
$$
\begin{aligned}
\sum_{i=1}^{n}{\sum_{j=i+1}^{n}{<v_i,v_j^{T}>x_ix_j}} &= \frac{1}{2}\sum_{i=1}^{n}{\sum_{j=1}^{n}{<v_i,v_j^{T}>x_ix_j}} - \frac{1}{2} {\sum_{i=1}^{n}{<v_i,v_j^{T}>x_ix_i}} \\
&= \frac{1}{2} \left( \sum_{i=1}^{n}{\sum_{j=1}^{n}{\sum_{f=1}^{k}{v_{i,f}v_{j,f}x_ix_j}}} - \sum_{i=1}^{n}{\sum_{f=1}^{k}{v_{i,f}v_{i,f}x_ix_i}} \right) \\
&= \frac{1}{2}\sum_{f=1}^{k}{\left[ \left( \sum_{i=1}^{n}{v_{i,f}x_i} \right) \cdot \left( \sum_{j=1}^{n}{v_{j,f}x_j} \right) - \sum_{i=1}^{n}{v_{i,f}^2 x_i^2} \right]} \\
&= \frac{1}{2}\sum_{f=1}^{k}{\left[ \left( \sum_{i=1}^{n}{v_{i,f}x_i} \right)^2 - \sum_{i=1}^{n}{v_{i,f}^2 x_i^2} \right]}
\end{aligned}
$$
在上式中，$<v_i,v_j^{T}>$可以看做一个常数，其中$v_i=[v_{i,1},v_{i,2}, .. ,v_{i,f}], i\in \lbrace1,2,..,n\rbrace$；$<v_i,v_j^{T}>=\sum_{f=1}^{k}{v_{i,f}v_{j,f}}$。
实现时，$\sum_{i=1}^{n}{v_{i,f}x_i}$ 式子可以直接将每行样本$X$和一个$n*k$的隐向量矩阵相乘($n$是特征数，$k$是隐向量长度）。
如果要用 FM 做二分类，需要在上面模型外面套上一层sigmoid函数，即：
$$
output=sigmoid(y(x))=\frac{1}{1+e^{-y(x)}}
$$
损失函数
- 回归问题 通常使用平方损失，即$1/2(y-y(x))^2$。
- 分类问题（此处指的是二分类问题）通常使用逻辑损失函数（也叫交叉熵损失函数），即$ln(1+e^{-yy(x)})，y\in{-1,1}$。
所以对于二分类问题，FM 算法的损失函数如下：
$$
loss(x) = ln(1+e^{-yy(x)})
$$
加上 L2正则化之后，损失函数如下：
$$
\begin{aligned}
loss(x) &= ln(1+e^{-yy(x)}) + \frac{\beta}{2}{\theta}^2 \\
&= ln(1+e^{-yy(x)}) + \frac{\beta}{2}{w_0}^2 + \frac{\beta}{2}{w_i}^2 + \frac{\beta}{2}{v_{i,f}v_{i,f}^T} \\
&= ln(1+e^{yy(x)})-ln(e^{yy(x)}) + \frac{\beta}{2}{w_0}^2 + \frac{\beta}{2}{w_i}^2 + \frac{\beta}{2}{v_{i,f}v_{i,f}^T} \\
&= ln(1+e^{yy(x)})-yy(x) + \frac{\beta}{2}{w_0}^2 + \frac{\beta}{2}{w_i}^2 + \frac{\beta}{2}{v_{i,f}v_{i,f}^T}
\end{aligned}
$$
梯度求导，以$w_0$为例：
$$
\begin{aligned}
\frac{\partial loss(x)}{\partial w_0} &= \frac{1}{1+e^{yy(x)}}\cdot e^{yy(x)} \cdot y \cdot \frac{\partial y(x)}{\partial w_0} - y\frac{\partial y(x)}{\partial w_0} + \beta w_0 \\
&= sigmoid(yy(x)) \cdot y \cdot \frac{\partial y(x)}{\partial w_0} - y\frac{\partial y(x)}{\partial w_0} + \beta w_0 \\
&= (sigmoid(yy(x)) - 1 )\cdot y\frac{\partial y(x)}{\partial w_0} + \beta w_0 \qquad (1) \\
&= (sigmoid(yy(x)) - 1 )\cdot y + \beta
\end{aligned}
$$
在实现的时候通常可以将(1)处的$(sigmoid(yy(x)) - 1 )\cdot y$计算保存，不同参数的梯度求导在于其它项的不同。
