1
USA
26/11/15
Movie
0
China
1/7/14
Game
1
China
19/2/15
Game
“Clicked?”是label,Country、Day、Ad_type是特征。由于三种特征都是categorical类型的,需要经过独热编码(One-Hot Encoding)转换成数值型特征。
FM是一种比较灵活的模型,通过合适的特征变换方式,FM可以模拟二阶多项式核的SVM模型、MF模型、SVD++模型等[7]。相比SVM的二阶多项式核而言,FM在样本稀疏的情况下是有优势的;而且,FM的训练/预测复杂度是线性的,而二项多项式核SVM需要计算核矩阵,核矩阵复杂度就是N平方。相比MF而言,我们把MF中每一项的rating分改写为: ,
从公式(2)中可以看出,这相当于只有两类特征 u 和 i 的FM模型。对于FM而言,我们可以加任意多的特征,比如user的历史购买平均值,item的历史购买平均值等,但是MF只能局限在两类特征。SVD++与MF类似,在特征的扩展性上都不如FM,在此不再赘述。
FFM原理
FFM(Field-aware Factorization Machine)最初的概念来自Yu-Chin Juan(阮毓钦,毕业于中国台湾大学,现在美国Criteo工作)与其比赛队员,是他们借鉴了来自Michael Jahrer的论文[14]中的field概念提出了FM的升级版模型。通过引入field的概念,FFM把相同性质的特征归于同一个field。以上面的广告分类为例,“Day=26/11/15”、“Day=1/7/14”、“Day=19/2/15”这三个特征都是代表日期的,可以放到同一个field中。同理,商品的末级品类编码生成了550个特征,这550个特征都是说明商品所属的品类,因此它们也可以放到同一个field中。简单来说,同一个categorical特征经过One-Hot编码生成的数值特征都可以放到同一个field,包括用户性别、职业、品类偏好等。在FFM中,每一维特征 xi,针对其它特征的每一种field fj,都会学习一个隐向量 vi,fj。因此,隐向量不仅与特征相关,也与field相关。也就是说,“Day=26/11/15”这个特征与“Country”特征和“Ad_type”特征进行关联的时候使用不同的隐向量,这与“Country”和“Ad_type”的内在差异相符,也是FFM中“field-aware”的由来。假设样本的 n 个特征属于 f 个field,那么FFM的二次项有 nf个隐向量。而在FM模型中,每一维特征的隐向量只有一个。FM可以看作FFM的特例,是把所有特征都归属到一个field时的FFM模型。根据FFM的field敏感特性,可以导出其模型方程。
(4)
其中,fj 是第 j 个特征所属的field。如果隐向量的长度为 k,那么FFM的二次参数有 nfk 个,远多于FM模型的 nk 个。此外,由于隐向量与field相关,FFM二次项并不能够化简,其预测复杂度是 O(kn2)。下面以一个例子简单说明FFM的特征组合方式[9]。输入记录如下:
User
Movie
Genre
Price
YuChin
3Idiots
Comedy, Drama
$9.99
这条记录可以编码成5个特征,其中“Genre=Comedy”和“Genre=Drama”属于同一个field,“Price”是数值型,不用One-Hot编码转换。为了方便说明FFM的样本格式,我们将所有的特征和对应的field映射成整数编号。
在SGD寻优时,代码采用了一些小技巧,对于提升计算效率是非常有效的。第一,梯度分步计算。采用SGD训练FFM模型时,只采用单个样本的损失函数来计算模型参数的梯度。上面的公式表明,∂Lerr/∂ϕ 与具体的模型参数无关。因此,每次更新模型时,只需计算一次,之后直接调用 ∂Lerr/∂ϕ 的值即可。对于更新 nfk 个模型参数,这种方式能够极大提升运算效率。第二,自适应学习率。此版本的FFM实现没有采用常用的指数递减的学习率更新策略,而是利用 nfk 个浮点数的临时空间,自适应地更新学习率。学习率是参考AdaGrad算法计算的[11],按如下方式更新第三,OpenMP多核并行计算。OpenMP是用于共享内存并行系统的多处理器程序设计的编译方案,便于移植和多核扩展[12]。FFM的源码采用了OpenMP的API,对参数训练过程SGD进行了多线程扩展,支持多线程编译。因此,OpenMP技术极大地提高了FFM的训练效率和多核CPU的利用率。在训练模型时,输入的训练参数ns_threads指定了线程数量,一般设定为CPU的核心数,便于完全利用CPU资源。第四,SSE3指令并行编程。SSE3全称为数据流单指令多数据扩展指令集3,是CPU对数据层并行的关键指令,主要用于多媒体和游戏的应用程序中[13]。SSE3指令采用128位的寄存器,同时操作4个单精度浮点数或整数。SSE3指令的功能非常类似于向量运算。例如,a 和 b 采用SSE3指令相加(a 和 b 分别包含4个数据),其功能是 a 中的4个元素与 b 中4个元素对应相加,得到4个相加后的值。采用SSE3指令后,向量运算的速度更加快捷,这对包含大量向量运算的FFM模型是非常有利的。除了上面的技巧之外,FFM的实现中还有很多调优技巧需要探索。例如,代码是按field和特征的编号申请参数空间的,如果选取了非连续或过大的编号,就会造成大量的内存浪费;在每个样本中加入值为1的新特征,相当于引入了因子化的一次项,避免了缺少一次项带来的模型偏差等。