Poly2，FM，FFM

传统的特征交叉是先手动再组合特征，再通过各种分析手段筛选特征的方法——低效。

Poly2模型

Degree-2 Polynomial Margin (Poly2)

$y=w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^nw_{ij}x_ix_j$
Poly2模型总的参数数量为 $1+n+\frac{(1+(n-1))(n-1)}{2}=1+n+\frac{n(n-1)}{2}=\frac{n(n+1)}{2}+1$

相比LR模型，新增 $\frac{(1+(n-1))(n-1)}{2}$ 个交叉特征，任意两个参数都是独立的。

我们可以把所有的 $w_{ij}$ 写成矩阵：
$\hat W=\begin{pmatrix} 1 & w_{1,2} & w_{1,3} & ... & w_{1,n}\\ w_{2,1} & 1 & w_{2,3} & ... & w_{2,n}\\ w_{3,1} & w_{3,2} & 1 & ... & w_{3,n}\\ ...&...&...&...&...\\ w_{n,1} & w_{n,2} & w_{n,3} & ... & 1\\ \end{pmatrix}$
上面的矩阵是关于对角线对称的。

Poly2模型的缺陷
1、容易发现，要训练 $w_{ij}$ 需要 $x_i$ 和 $x_j$ 同时不为0，而推荐系统中的共现矩阵是很稀疏的，因此你难以训练组合特征的参数 $w_{ij}$ 。
2、参数量由LR的 $n$ 个直接上升到 $n^2$ 个，极大的增加了模型训练的复杂度。

FM模型（因子分解机，Factorization Machine，FM）

因为 $\hat W$ 是关于对角线对称的，所以 $\hat W$ 可以分解成 $\hat W=V^TV$ ，其中 $V$ 是 $n*k,(k<<n)$ ，也就是说矩阵 $V$ 有 $n$ 行，任意两行的内积 $w_{ij}=v_{i}\cdot v_{j}$ 一共有 $\frac{n(n-1)}{2}$ 个值，那么假设函数为：
$y=w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^n\langle v_{i},v_{j}\rangle x_ix_j$
$=w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^n(v_{i}\cdot v_{j})x_ix_j$
$=w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^n(v_{i}^T v_{j})x_ix_j$

$v_{i}$ ， $v_{j}$ 是向量，对应矩阵 $V$ 的第 $i$ 行和第 $j$ 行。
此时参数量为 $1+n+nk$ 。复杂度为 $O(kn^2)$ ，但是我们可以对上面的公式进行变换，使得复杂度降低为线性的 $O(kn)$ ，具体推导过程如下：

FFM模型

Field Factorization Machine，FFM

首先要理解什么是特征域（Field）？
对于分类变量性别：[男，女，未知]
对于年龄分箱后：[x<=20，20<x<=40，40<x<=60，x>60]
对于一个33岁的女人，其one-hot编码为：0100100，前3个数字表示性别，后4个数字表示年龄，这7个特征对应两个特征域即性别和年龄。

在FM中没有特征域的概念，或者说所有的特征都属于1个特征域，即此时1个特征域对应1个矩阵 $V$ ，其大小为 $n*k$ ；

在FFM模型中，如果有 $f$ 个特征域，就有 $f$ 个矩阵 $V$ 。不同的Field变成one-hot编码后得到的sparse features数量书不同的，所以不同Field对应的矩阵 $V$ 的行长度是不同的，列长度为 $k$ 。当特征 $x_i$ 与特征 $x_j$ 交叉时，从 $x_i$ 对应的特征域矩阵（即一组向量） $V_{f_{x_i}}$ 中选择第 $i$ 行向量 $v_{i,f_{x_i}}$ ；从 $x_j$ 对应的特征域矩阵 $V_{f_{x_j}}$ 中选择第 $j$ 行向量 $v_{j,f_{x_j}}$ ，那么就有假设函数：
$y=w_0+\sum_{i=1}^nw_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^n(v_{i,f_{x_i}}^T v_{j,f_{x_j}})x_ix_j$
显然FFM模型的参数量为 $1+n+nkf$ 。