FM

在计算广告领域，因子分解机(Factorization Machines，FM)是很经典的模型，面对量大且稀疏的数据，此算法仍然可以取得比较优秀的效果。

假设有下面的数据：

Clicked?	Country	Day	Ad_type
1	USA	26/11/15	Movie
0	China	1/7/14	Game
1	China	19/2/15	Game

其中，Clicked? 是label，Country、Day、Ad_type是特征。由于三种特征都是类别型的，需要经过独热编码（One-Hot Encoding）转换成数值型特征：

Clicked?	Country=USA	Country=China	Day=26/11/15	Day=1/7/14	Day=19/2/15	Ad_type=Movie	Ad_type=Game
1	1	0	1	0	0	1	0
0	0	1	0	1	0	0	1
1	0	1	0	0	1	0	1

经过编码之后，数据变的非常稀疏，在工业界这也是很难避免的一个问题。在这些稀疏的特征中，如果将其中一些特征加以关联，就可能得到与label管理更紧密的特征。例如对于 China 而言，19/2/15（即2015年2月19日）这天是春节，可能存在大量浏览和购买行为，广告点击率自然也会上升。

为了不错过任何有意义的特征组合，我们将所有特征两两组合起来形成新的特征，比较简单直接的实现方法是使用二阶多项式模式进行特征组合。例如将特征 $x_i,x_j$ 的组合可以用 $x_ix_j$ 表示，当且仅当 $x_i,x_j$ 都为1时得到的组合特征才有意义。需要注意的是，原本的特征在onehot编码之后已经很稀疏了，再对特征进行两两组合，那么得到的特征就更稀疏了。

在得到特征之后，假设我们用线性模型进行预测，则预测值的表达式可能是这样的：
$\hat{y}=w_0+\sum_{i=1}^n{w_ix_i}+\sum_i^n{\sum_{j=i+1}^n{w_{ij}x_ix_j}}$
式子中 n 代表特征数量， $w_0, w_{i}, w_{ij}$ 是模型的参数。其中组合特征参数 $w_{ij}$ 共有 $\frac{n(n-1)}{2}$ 个，需要大量的非零组合特征 $x_ix_j$ 才容易学习到合适的参数值。如何解决二次项参数 $w_{ij}$ 的学习问题？

矩阵分解提供了一种解决方法，由于特征组合后的系数可以构成对称矩阵 $W_{n \times n}$ ，因此可以对矩阵进行分解为 $W_{n\times n}=V_{n\times k}V_{n\times k}^T$ ，即 $w_{i,j}=<v_i,v_j>$ ，其中 $k\ll n$ 。于是，原本需要训练 $\times n$ 个特征，现在只需要训练 $\times k$ 个：
$\hat{y}=w_0+\sum_{i=1}^n{w_ix_i}+\sum_{i=1}^n{\sum_{j=i+1}^n{<v_i,v_j>x_ix_j}} \\ <v_i,v_j>=\sum_{f=1}^k{v_{if}v_{jf}}$
次数计算的时间复杂度为 $O(kn^2)$ ，能不能进一步优化一下？注意到 $\sum_{i=1}^n{\sum_{j=i+1}^n{<v_i,v_j>x_ix_j}}$ 实际上只是矩阵 $W_{n \times n}$ 中不包含对角线的上三角的部分，可以用 $W_{n \times n}$ 减去对角线元素后再除以2来得到：
$\begin{aligned} & \sum_{i=1}^n{\sum_{j=i+1}^n{<v_i,v_j>x_ix_j}} \\ & = \frac{1}{2}\sum_{i=1}^n{\sum_{j=1}^n{<v_i,v_j>x_ix_j}}-\frac{1}{2}\sum_{i=1}^n{<v_i,v_i>x_ix_i}\\ & = \frac{1}{2}\left(\sum_{i=1}^n{\sum_{j=1}^n{\sum_{f=1}^k{v_{if}v_{jf}x_ix_j}}}-\sum_{i=1}^n{\sum_{f=1}^k{v_{if}v_{if}x_ix_i}}\right) \\ & = \frac{1}{2}\left(\sum_{f=1}^k{\sum_{i=1}^n{v_{if}x_i\sum_{j=1}^n{v_{jf}x_j}}}-\sum_{i=1}^n{\sum_{f=1}^k{v_{if}v_{if}x_ix_i}}\right) \\ &= \frac{1}{2}\sum_{f=1}^k\left(\left(\sum_{i=1}^n{v_{if}x_i}\right)^2-\sum_{i=1}^n{v_{if}^2x_i^2}\right) \end{aligned}$
这样一来，是复杂度就降低为： $O (k n)$

引入二次项的FM模型，可以采用不同的损失函数用于解决回归、二元分类等问题，比如可以采用MSE（Mean Square Error）损失函数来求解回归问题，也可以采用Hinge/Cross-Entropy损失来求解分类问题。

（1）回归问题loss取最小平方误差
$loss^R(\hat y,y) = (\hat y – y)^2$
所以：
$\frac{\partial loss^R(\hat y,y)}{\partial \theta} = 2 (\hat y – y)\frac{\partial \hat y }{\partial\theta}$

（2）二分类问题loss取logit函数
$loss^C(\hat y ,y) = -\ln \sigma(\hat y y)$
所以：
$\frac{\partial loss^C(\hat y,y)}{\partial \theta} = [(\sigma(\hat y y) – 1]y \frac{\partial \hat y }{\partial\theta}$

其中：
$\frac{\partial}{\partial\theta} \hat y (\mathbf{x}) = \left\{\begin{array}{ll} 1, & \text{if}\; \theta\; \text{is}\; w_0 \\ \ x_i, & \text{if}\; \theta\; \text{is}\; w_i \\ \ x_i \sum_{j=1}^n v_{j, f} x_j – v_{i, f} x_i^2, & \text{if}\; \theta\; \text{is}\; v_{i, f} \end{array}\right.$

为了避免过拟合，也引入正则化。所以，FM的最优化问题就变成了：
$\theta ^* = \mathop{\arg\min}_{\theta} \sum_{i=1}^N\left(loss(\hat y(x_i) ,y_i)+ \sum \lambda_\theta \theta^2\right)$
注： $\lambda_\theta$ 是正则化系数。

FFM

在FFM（Field-aware Factorization Machines ）中每一维特征（feature）都归属于一个特定的field。对于进行onehot编码后的类别特征都属于同一个field。对于连续特征，一个特征就对应一个Field。例如：

在这里插入图片描述

当然也可以对连续特征离散化，一个分箱成为一个特征。例如：

在这里插入图片描述

不论是连续特征还是离散特征，它们都有一个共同点：同一个field下只有一个feature的值不是0，其他feature的值都是0。

FFM模型认为 $v_i$ 不仅跟 $x_i$ 有关系，还跟与 $x_i$ 相乘的 $x_j$ 所属的Field有关系。于是FFM模型的公式如下：
$\hat{y}=\sum_{i=1}^n{\sum_{j=i+1}^n{v_{i,f_j}\cdot v_{j,f_i}x_ix_j}}$
与FM的公式相比，它只保留了二次项。如何理解这种二次项系数的变化？可以通过下面的图片来理解 FM 与 FFM 在计算二次项系数时的区别：

FM 在计算二次项系数的时候，任意两个特征的组合都需要两个一维的隐含向量(分别对应图中上半部分棕色一维向量 $v_i$ 和蓝色的一维向量 $v_j$ )的内积来表示。

而在FFM中，计算二次项系数的时候，把一维向量扩充了F倍（F表示所有特征对应了F个field，在本例中F取值为3，即field1年龄、field2城市，field3性别），构成“field隐含矩阵”，即图中下半部分棕色的矩阵 $v_{ij}$ 和蓝色的矩阵 $v_{ji}$ 。当计算 $x_i, x_j$ 这个二次项的系数时，则需要：

1，从 $v_{ij}$ 中取出 $x_j$ 特征对应的field所在的行向量 $v_{if_j}$ ：

2，从 $v_{ji}$ 中取出 $x_i$ 特征对应的field所在的行向量 $v_{jf_i}$ ：

然后将取出的向量计算内积作为 $x_ix_j$ 系数。

总的来说，这个过程可以描述为：每个特征对应了一组隐向量，当 $x_i$ 与 $x_j$ 特征进行组合时， $x_i$ 会从 $x_i$ 那组隐向量中选择出与特征 $x_j$ 的域 $f_{j}$ 对应的隐向量 $v_{i, f_{j}}$ 进行交叉。同理， $x_j$ 也会选择与 $x_i$ 的域 $f_i$ 对应的隐向量 $v_{j, f_i}$ 进行交叉。

如果隐向量的长度为 k，那么FFM的二次参数有 $n F k$ 个，远多于FM模型的 nk 个。此外，由于隐向量与field相关，FFM二次项并不能够化简，其预测复杂度是 $O(k n^2)$ 。

以上文的第一个表格数据为例：

计算用户1的 $\hat y$ 过程为：
$\begin{aligned} \hat{y}&=\sum_{i=1}^n{\sum_{j=i+1}^n{v_{i,f_j}\cdot v_{j,f_i}x_ix_j}} \\ &=v_{1,f_2}\cdot v_{2,f_1}x_1x_2+v_{1,f_2}\cdot v_{3,f_1}x_1x_3+v_{1,f_2}\cdot v_{4,f_1}x_1x_4+\cdots \end{aligned}$
于是 $\hat y$ 对 $v_{1,f2}$ 的偏导为：
$\frac{\partial{\hat{y}}}{\partial{v_{1,f_2}}}=v_{2,f1}x_1x_2+v_{3,f1}x_1x_3+v_{4,f1}x_1x_4$
注意 $x_2,x_3,x_4$ 是同一个属性的one-hot表示，即 $x_2,x_3,x_4$ 中只有一个为1，其他都为0。在本例中 $x_3=x_4=0,x_2=1$ ，所以：
$\frac{\partial{\hat{y}}}{\partial{v_{1,f_2}}}=v_{2,f_1}x_1x_2$
推广到一般情况：
$\frac{\partial{\hat{y}}}{\partial{v_{i,f_j}}}=v_{j,f_i}x_ix_j$
实际项目中 x 是非常高维的稀疏向量，求导时只关注那些非0项即可。另外，在执行点击率预测时，会在 $\hat y$ 外面再套上一层 sigmoid 函数。接下来，我们用 z 来表示 $\hat y$ ：
$z=\hat y=\sum_{i=1}^n{\sum_{j=i+1}^n{v_{i,f_j}\cdot v_{j,f_i}x_ix_j}}$
用 α 表示对点击率的预测值：
$a=\sigma(z)=\frac{1}{1+e^{-z}}=\frac{1}{1+e^{-\phi(v,x)}}$
二分类问题常用的交叉熵损失函数：
$a=\sigma(z)$
其中，σ 为 sigmoid 函数，则有：
$\frac{\partial C}{\partial z}=\frac{\partial C}{\partial a}\sigma'(z)=-\frac{y}{a}\sigma'(z)+\frac{1-y}{1-a}\sigma'(z)=\frac{a-y}{a(1-a)}\sigma'(z)=a-y$

进而可以得到：
$\frac{\partial C}{\partial z}=a-y=\left\{\begin{matrix}-\frac{1}{1+e^z} & if\ y是正样本 \\ \frac{1}{1+e^{-z}} & if\ y是负样本\end{matrix}\right .$
结合上面求出的 $\frac{\partial{\hat{y}}}{\partial{v_{i,f_j}}}$ 和 $\frac{\partial C}{\partial z}$ ，代入下面的公式即可求得梯度值：
$\\ \frac{\partial C}{\partial{v_{i,f_j}}}=\frac{\partial C}{\partial z}\frac{\partial{z}}{\partial{v_{i,f_j}}}$
然后就可以使用梯度下降算法对参数进行优化了。