FM | FFM

FM与FFM分别是Factorization Machine与Field-aware Factorization Machine的简称。

LR作为广义线性模型对特征向量与label之间的非线性关系会很苦手。这时便需要进行特征组合，比如使用线性模型来预测各种近似长方形形状的面积，两个特征为长 $x_1$ 与宽 $x_2$ ，那么显然并不能学到一个很好的模型，此时增加一个新的特征 $x_3=x_1 * x_2$ ，便可以得到很好的效果。

在实际应用中，特征向量的维度是很高的，很难像上例中直接看到这种有意义的组合，考虑所有特征两两组合则线性回归方程变为：

$y(\mathbf{x})=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{i j} x_{i} x_{j}$

除了原本特征的 $i$ 个权重外还要学习各特征组合情况对应的权重，对于参数 $w_{ij}$ 的训练，需要大量 $x_i$ 和 $x_j$ 都不为0的样本，然而由于one-hot编码等原因带来的稀疏性使得这个要求无法达成，那么训练样本不足便会导致 $w_{ij}$ 的不准确，从而影响模型的质量。

解决方案是使用矩阵分解。在推荐系统中会对user_item_matrix做分解，为user及item学得一个低维的向量来代表自已。那么此处的情况可以与之类比，将特征组合的所有权重表示为一个形状为(i * i)的矩阵，那么 $w_{ij}$ 即为此矩阵第i行第j列的数值，将此高维度的矩阵进行分解，可以为每个特征得到一个关于权重的隐向量 $v_i$ ，那么 $w_{i j}$ 使用 $v_i$ 点乘 $v_j$ 即可得到。此时线性方程变为：

$y(\mathbf{x})=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n}\left\langle\mathbf{v}_{i}, \mathbf{v}_{j}\right\rangle x_{i} x_{j}$

以上模型称为因子分解机(Factorization Machine)，经过一些数学上的变换及处理，该模型可以在 $O(kn)$ 的复杂度下进行训练和预测，是一种比较高效的模型。

在FM的基础上有人提出了Field-aware Factorization Machine。比如特征向量中有200多维来代表一个user的国家，country.uk和country.us等等，那么这200多个特征可以认为是属于一个field，区别在为特征 $x_i$ 学习隐向量时要为每一个field都学到一个相应的隐向量，特征组合权重 $w_{ij}$ 根据 $x_i$ 关于 $x_j$ 所在field的隐向量乘以 $x_j$ 关于 $x_i$ 所属field的隐向量而得，线性方程变为：

$y(\mathbf{x})=w_{0}+\sum_{i=1}^{n} w_{i} x_{i}+\sum_{i=1}^{n} \sum_{j=i+1}^{n}\left\langle\mathbf{v}_{i, f_{j}}, \mathbf{v}_{j, f_{i}}\right\rangle x_{i} x_{j}$

该方法效果更好，而预测时间复杂度升至 $O(kn^2)$ 。有开源库libffm的实现以供使用。

GBDT & LR

Facebook在广告CTR预估上的做法是使用梯度提升决策树(GBDT) & LR的方案。

思路是将原本要输入LR的特征向量，先经过GBDT筛选和组合，生成新的特征向量再送到LR中。如图所示：

image

GBDT作为集成模型，会使用多棵决策树，每棵树去拟合前一棵树的残差来得到很好的拟合效果。一个样本输入到一棵树中，会根据各节点的条件往下走到某个叶子节点，将此节点值置为1，其余置为0。比如训练使用了3棵决策树，每棵决策树有5个叶子节点，样本在各树分别落到了各树从左往右的第1，2，3个节点上，则得到三个one-hot编码为[1, 0, 0, 0, 0]，[0, 1, 0, 0, 0]，[0, 0, 1, 0, 0]，拼接起来作为转换后的特征向量：[1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0]，输入到LR模型中得到分值。

此模型为Facebook的广告效果带来了明显的提升，在其发表的论文中，还讨论了各种工程上的实践与细节，包括GBDT与LR的更新频率，降采样的比例实践等，值得参考。实现GBDT可以使用开源的XGBoost包。