推荐系统与CTR预估,基于深度学习(二):FM系列模型串讲

Posted by nickiwei on May 2, 2018

这个系列介绍了在深度学习的大背景下, 推荐系统领域所发生的翻天覆地的变化。 从召回和排序模型串讲开始, 结合论文分析与工程实践, 并充分记录了作者在实际工作中所总结的各种经验总结。

欢迎转载, 转载请注明出处及链接。

为什么需要FM

在召回模型一文中, 我们已经介绍了推荐系统的整体工作流程。 具体到排序模型来看, 我们要解决的核心问题是, 将各个召回通道(如DSSM用户相关性召回, 热度召回, 同类召回等)召回内容根据预估CTR进行混排, 将内容依序展现给用户。

排序模型与广告系统中CTR预估部分的原理是基本一致的, 在具体实践中, 二者的模型也是互相借鉴。唯一的区别是, 广告预估通常只考虑筛选出CTR较高的一个或几个广告,而推荐系统排序模型通常需要将绝大多数召回内容进行全排序。

在传统的机器学习领域, SVM由于无法处理稀疏数据及在规模以上数据下性能表现不足, 完全不适合推荐系统下的CTR预估模型实现。 基于人工特征工程/GBDT+LR的方法仍是工业界的常用标准手段之一。

FM在2010年被提出, 其主要优势在于:

1, FM在稀疏数据下表现出了良好的性能。 这一点对于FM的广泛应用起到了至关重要的作用。

2, FM具有线性复杂度(时间性能), 且不像SVM一样依赖支持向量(空间性能)。 因此,非常适合超大规模的数据训练。

3, FM可以适用于任何输入数据形式, 具有良好的泛用性。 事实上, 一些先于FM产生的其他类FM模型, 如SVD++, PITF等, 均可以由FM+特殊的数据输入形式实现。

基于以上几点, FM在推荐系统及CTR预估领域, 表现出了非常良好的性能。但归根结底, FM的广泛应用还是取决于其对稀疏数据处理的良好性能。

为什么稀疏性的问题如此重要?

原因在于, 在推荐系统等领域, 输入往往采用多个离散特征, 为了对这些特征进行拟合, 需要采用one_hot编码。 而one hot编码自然会产生极大的稀疏性。

One hot编码如下图:

one hot

在实践中, 平均每个特征都会有大约3-5个选项, 因此综合而言, 输入样本的稀疏率达到了惊人的70% - 80%. 因此, 处理推荐系统等的模型, 对于稀疏性处理的良好性能是绝对必要的。

FM模型

FM的基本原理

FM模型的一大基本假设是:

某些特征经过关联之后,与label之间的相关性就会提高。

举例而言, “USA”与“Thanksgiving”、“China”与“Chinese New Year”, 当这些特征同时出现时, 实践证明, CTR会有着显著的提升。

因此, 一个最自然的想法就是, 我们在线性拟合的基础上, 增加交叉项拟合, 最终公式如下:

one hot

直接训练这样的一个模型会遇到训练不充分的欠拟合问题。 原因在于由于样本的稀疏性, Xi和Xj同时不为0的概率是非常非常低的, 因此, Wij参数被梯度更新了极少的次数, 很容易产生不充分训练的问题。

我们采用隐向量内积分解法来处理该问题。

所有交叉项参数Wij可以组成一个对称矩阵(理论上, 由于交叉项度量的是两件事同时发生后的相关性权重, 因此应该有Wij==Wji)。 根据线性代数, 一定有:

one hot

如下图可见, 这样的对称分解之后我们可以把向量vi的维度做到很小, 远小于矩阵W的向量维度.

one hot

这样, 在实际训练时, 我们只需要训练零阶项W0, 一阶项Wi, 以及分解因子Vi(低纬度向量)即可。这样就大大简化了模型的训练难度。

FM的目标方程

如上所述, FM的目标方程是:

one hot

我们还可以进一步简化该方程右端:

one hot

这个方程有着非常重要的意义, 具体来说:

1, 在训练阶段, 不仅仅是需要更新的参数变少(二阶参数从n*n个, 减少到n*k个, k « n). 更重要的是, 只要Xi不为0, Vi向量就会被更新, 相比于只有Xi和Xj同时不为0时, Wij才会被更新而言。 参数被更新的次数指数级增长。

2, 在测试阶段, 由于二阶项被剔除, 因此, 我们实际上能在线性时间内就计算完所有的特征。 效率大大提升。

在Cost方程方面, FM可以灵活的使用MSE来处理回归问题, 用Softmax Crossentropy/ Hinge Loss 来处理分类问题。 这一点与LR是一致的。

最后, 在训练复杂度方面, FM的梯度更新策略如下:

one hot

可以看出, FM的梯度更新也可以在线性时间内完成。 训练也是非常高效的。 稍加注意的是, 第三类梯度中的求和可以提前完成后复用, 是循环后再循环, 而不是循环套循环。 因此, 训练复杂度是线性的。

FM的优势

FM的优势前述已经很清楚了, 我们整理如下:

1, 能够很好的表征组合特征相关性。

2,能够在线性时间内的处理稀疏样本输入的相关性处理。 在训练和测试阶段都体现出了线性复杂度的高效性。

3,能够充分利用稀疏样本对参数进行训练, 对样本规模要求低。

4, 对输入要求低, 可以灵活处理各种输入问题。

FFM

在FFM模型中, 有一个地方奇怪的很明显, 就是one hot编码时, 明明同一个特征的不同选择项和不同特征之间地位完全一致, 并没有体现出他们的紧密性, 这显然是很奇怪的, FFM模型就是基于这一点对FM进行了直接的优化, 取得了相当不错的效果。

FFM的基本原理

在FFM中,每一维特征 xi,针对其它特征的每一种field fj,都会学习一个隐向量 vi,fj。因此,隐向量不仅与特征相关,也与field相关。这么说比较抽象, 我们直接看目标方程:

one hot

可以看出, 隐向量矩阵从一个二维矩阵变成了三维矩阵, 每一个矩阵面Vfi上, 只有该域的特征有值, 其余全部为0.

FFM的问题在于:

1, FFM的二次参数有 nfk 个,远多于FM模型的 nk 个。

2, 由于隐向量与field相关,FFM二次项并不能够化简,其预测复杂度是 O(kn2)。

因此, FFM对于训练数据的规模和训练机器的性能提出了更高的要求。

FFM的训练

首先, 我们来看FFM的cost function, 在原论文中, 作者采用了hinge loss + L2 正则惩罚, 具体如下:

one hot

在模型训练中, 有以下几点需要注意:

1, 归一化。 在数据预处理时, 一定要进行特征和样本的归一化。 一般取值控制在0-1之间即可。

2, FFM的梯度更新策略如下, 可以看出, Lerr梯度 这一项 与具体的模型参数无关。因此,每次更新模型时,只需计算一次,之后直接调用 Lerr梯度 的值即可。对于更新 nfk 个模型参数,这种方式能够极大提升运算效率。

one hot

FFM实践

在我们的实验中, 受限于样本特征,算力等原因, 我们在实验中所取得的FFM和FM CTR差距很小。 考虑到模型的简便, 训练的快速等原因, 我们没有采用FFM.

更多应用

事实上, 比起FFM, FM与深度学习结合形成的Deep FM模型和FNN(Factorialized Machine based Neural Network)是FM在工业界更常见的应用, 我们将在下一节中详细介绍这两个模型。