FM 模型理论基础

1. 背景介绍

假设一个广告分类的问题，根据用户和广告位相关的特征，预测用户是否点击了广告。数据如下：

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

由上表可知，3维特征和点击标签，对类别特征进行One-hot编码转化为数值特征，转化为数据如下：

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

特征空间还是比较稀疏的，并且在类别空间很大时，特征则越稀疏。并且根据不同的特征组合来看，两两组合的特征是十分必要的。原因如下：

通过观察大量的样本数据可以发现，某些特征经过关联之后，与label之间的相关性就会提高。例如，“USA”与“Thanksgiving”、“China”与“Chinese New Year”这样的关联特征，对用户的点击有着正向的影响。换句话说，来自“China”的用户很可能会在“Chinese New Year”有大量的浏览、购买行为，而在“Thanksgiving”却不会有特别的消费行为。这种关联特征与label的正向相关性在实际问题中是普遍存在的，如“化妆品”类商品与“女”性，“球类运动配件”的商品与“男”性，“电影票”的商品与“电影”品类偏好等。

如何表示两个特征的组合呢？一种方法是采用多项式模型表示两个特征的组合， $x_i$ 为第 i 个特征的取值， $x_ix_j$ 表示特征组合，其参数 $w_{ij}$ 即为学习参数，也是 $x_ix_j$ 组合的重要程度：
$g(x)=w_{0}+\sum_{i} w_{i} x_{i}+\sum_{i} \sum_{j=i+1} w_{i j} x_{i} x_{j}$

上式称为 Poly2 模型，参数个数：一次项有 d+1 个，二次项共有 $d(d-1)/2$ 个，而参数与参数之间彼此独立，在稀疏场景下，二次项的训练是很困难的。因为要训练 $w_{ij}$ ，需要有大量的 $x_i$ 和 $x_j$ 都非零的样本，样本少则难以估计。

2. FM 模型

Poly2 模型认为参数 $w_{ij}$ 是彼此独立的，所以必须进行单独训练。但是实践上不同的特征之间进行组合并非完全独立。参考矩阵分解，rating 矩阵可以分解为 user 矩阵和 item 矩阵的矩阵乘，如下图所示：

user 和 item 矩阵的维度分别为 (n, k) 和 (k, m)，相比原来的rating矩阵，空间占用得到降低，并且分解后的user矩阵暗含着user偏好，Item矩阵暗含着item的属性，而user矩阵乘上item矩阵就是rating矩阵中用户对item的评分。

参考矩阵分解的过程，FM 模型将二次项参数 $w_{ij}$ 进行分解：
$g(x)=w_{0}+\sum_{i} w_{i} x_{i}+\sum_{i} \sum_{j=i+1}\left\langle v_{i}, v_{j}\right\rangle x_{i} x_{j}$

其中 $v_i$ 是第 i 维特征的隐向量，长度为k， $(v_i, v_j)$ 为内积，值为原来的 $w_{ij}$ 。

上式的复杂度可以从 $O(kd^2)$ 优化到 $O(kd)$ ：
$\begin{aligned} & \sum_{i=1}^{d} \sum_{j=i+1}^{d}\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle x_{i} x_{j} \\ = & \frac{1}{2} \sum_{i=1}^{d} \sum_{j=1}^{d}\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle x_{i} x_{j}-\frac{1}{2} \sum_{i=1}^{d}\left\langle\mathbf{v}_{i}, \mathbf{v}_{i}\right\rangle x_{i} x_{i} \\ = & \frac{1}{2} \sum_{i=1}^{d} \sum_{j=1}^{d} \sum_{f=1}^{k} v_{i, f} v_{j, f} x_{i} x_{j}-\frac{1}{2} \sum_{i=1}^{d} \sum_{f=1}^{k} v_{i, f} v_{i, f} x_{i} x_{i} \\ = & \frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{d} v_{i, f} x_{i}\right)\left(\sum_{j=1}^{d} v_{j, f} x_{j}\right)-\sum_{i=1}^{d} v_{i, f}^{2} x_{i}^{2}\right) \\ = & \frac{1}{2} \sum_{f=1}^{k}\left(\left(\sum_{i=1}^{d} v_{i, f} x_{i}\right)^{2}-\sum_{i=1}^{d} v_{i, f}^{2} x_{i}^{2}\right) \end{aligned}$

3. FFM 模型

FM模型中，所有特征共享同一个隐空间，每一维特征对应为唯一的隐向量进行特征交互。存在的问题在于：不同特征是按照不同的 filed 划分，比如 “EPSN、NBC” 属于广告商、“Nike、Adidas”属于广告主、“Male、Female”属于性别。描述（EPSN，Nike）和（EPSN，Male）特征组合，FM模型都用同一 $w_{EPSN}$ ，而实际上，ESPN作为广告商，其对广告主和用户性别的潜在影响可能是不同的。

表示的不同点为：
FM： $<v_{EPSN}, v_{Nike}> * 1 * 1 + <v_{EPSN}, v_{Male}> * 1 * 1 + <v_{Nike}, v_{Male}> * 1 * 1$
FFM： $<v_{EPSN,广告主}, v_{Nike, 广告商}> * 1 * 1 + <v_{EPSN,性别}, v_{Male,广告商}> * 1 * 1 + <v_{Nike,性别}, v_{Male,广告主}> * 1 * 1$

FFM的数学公式表示为：
$g(x)=w_{0}+\sum_{i} w_{i} x_{i}+\sum_{i} \sum_{j>i}\left\langle v_{i, f_{j}}, v_{j, f_{i}}\right\rangle x_{i} x_{j}$

其中 $f_i$ 和 $f_j$ 分别代表第 i 个特征和第 j 个特征所属的 field，若field有 $f$ 个，隐向量的长度为 $k$ ，则二次项系数共有 $dfk$ 个，远多于FM模型的 $dk$ 个。此外，隐向量和field相关，并不能像FM模型一样将二次项化简，计算的复杂度是 $d^2k$ 。通常情况下，每个隐向量只需要学习特定field的表示，所以有 $k_{FFM} << k_{FM}$ 。