推荐系统-重排序-CTR-FM模型及FFM等

作者: 莱昂纳多91 | 来源:发表于2019-05-30 19:35 被阅读0次

1 概述

重排序模型中，特征主要使用离散one-hot编码的特征。这是由任务本身特点与历史发展以及模型特点决定的。
首先就任务本身来说，主要涉及到的特征分为用户特征-物品特征-行为特征。这些特征往往都是离散的如用户性别，用户爱好，物品分类等
就历史发展来说，是从人工规则--LR--GBDT+LR--FM--... 发展而来，这里都倾向于离散特征
而就整个发展过程中最关键以及工业应用中最常用的模型LR来讲，离散特征更有优势
而one-hot编码的离散特征，更容易引入非线性以及容易后续的特征组合，所以独热(one-hot)编码的离散特征在推荐系统重排序以及CTR预测中都十分普遍。

1.1 特征与特征域(feature field)

例如我们有数据：用户性别，年龄，物品品牌，物品价格等特征，则可以做如下转化
性别：[男，女]：[1,0] 表示男
年龄：[0-15岁，15-25岁，25-35岁，35-50岁，大于50岁]：[0,0,1,0,0] 表示用户年龄在25-35之间
物品品牌：[李宁，特步，Nike，Adidas，匡威] ： [0,0,0,1,0]表示Adidas
物品价格：[0-500元，500-1000元，1000-2000元，大2000元]：[0,1,0,0]则表示物品价格500-1000元

域	性别		年龄					品牌					价格
特征	男	女	15	25	35	50	>50	ln	tb	nike	adi	kw	500	1000	2000	>2000
样本	1	0	0	0	1	0	0	0	0	0	1	0	0	1	0	0

则 $x=[1,0,0,0,1,0,0,0,0,0,1,0,0,1,0,0]$ 表示一个样本
y=1可以表示一个年龄25-35岁的男性购买或点击了一个adi品牌价格500-1000之间的商品或其广告
所以男女分别变成了特征通过01表示是否是该特征，而性别作为男女的抽象则变成了特征域。
这里其实对于域，并没有严格的规定，从常识来讲倾向于把域如此来分，但同样，也可以根据具体样本特征做分组。
其主旨是：相同类型的特征组成一个域

2 FM(Factorization Machine)

2.1 模型推导

一般线性模型
$f_{line}(x)=w_0+\sum_{i=1}^{n}w_ix_i \tag{2.1}$
注意此处 $x_i$ 表示样本的第i个特征，而不是第i个样本。n表示每个样本共n维特征。

LR
$f_{LR}(x)=\frac{1}{1+exp(-f_{line}(x))}=\frac{1}{1+exp(-w_0-\sum_{i=1}^{n}w_ix_i)} \tag{2.2}$
LR是线性模型的一个转换。
但是从线性模型公式我们可以看出，线性模型只是使用了单个特征，没有考虑不同特征之间交叉的因素。例如性别和品牌的交叉，组成新特征“男-Nike”，“女-Nike”，“男-李宁”，“女-李宁”等，这些同样也是能够提供信息的。
所以，可以设计一个新模型
$f(x)=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}w_{ij}x_ix_j \tag{2.3}$
这相比于一般线性模型，就多了二元特征交叉的信息。当然，也可以继续添加三元交叉，四元交叉等等
但是，这里又要考虑计算量的问题。首先要注意，对于CTR任务，n是很大的，因为独热编码之后，域的展开就非常大。而当我们考虑二元交叉特征时，组合特征是 $n^2$ 数量级的
这会造成参数数量呈指数增长，而样本量m基本固定。这就导致添加三元等更高的特征交叉后，特征维度很容易超过样本量m
当特征维度远大于样本量m时，每个参数就难以得到足够的训练，造成欠拟合
所以暂时只考虑二元特征交叉
而仅仅是二元特征交叉，其参数 $w_{ij}$ 是 $n^2$ 级别的。而又由于 $x$ 本身就稀疏，所以 $x_ix_j$ 更加稀疏，在总体样本上，很容易出现某个组合 $x_ix_j$ 总为0的情况，这样对应的 $w_{ij}$ 就得不到训练。
为了应对这个问题，就需要把参数数量降下来。

通过线性代数知识我们知道可以使用矩阵分解技术把矩阵Ｗ分解
$W=VV^T$
W是 $n*n$ 维，V是 $n*k$ 维，当令 $k<<n$ 时，就可以把计算量从 $o(n^2)$ 降到 $nk\approx o(n)$
所以根据这样的思想，我们可以对每个特征 $x_i$ 构建一个向量 $v_i=(v_1,v_2...v_k)$ ,则 $w_{ij}=<v_i·v_j>$
则式(2.3)可以转换成
$f(x)=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}<v_i·v_j>x_ix_j \tag{2.4}$
进一步转化得
$f(x)=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(\sum_{l=1}^{k}v_{il}v_{jl})x_ix_j \tag{2.5}$
式(2.4)(2.5)就是FM模型，我们称 $v_{i}$ 为隐向量或者 $x_i$ 的隐向量

2.2 优化算法

我们对式(5)的最后一部分做进一步转换 $^1$ (详情见最后注释)
$\begin{alignedat}{2} \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(\sum_{l=1}^{k}v_{il}v_{jl})x_ix_j&=\sum_{l=1}^{k}\bigg[\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(v_{il}v_{jl})x_ix_j \bigg]\\ &=\sum_{l=1}^{k}\bigg[\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(v_{il}x_i)(v_{jl}x_j) \bigg]\\ &=\sum_{l=1}^{k}\frac{1}{2}\bigg[(\sum_{i=1}^{n}v_{il}x_i)^2-\sum_{i=1}^{n}(v_{il}x_i)^2 \bigg] \end{alignedat}$

对于此模型，设有损失函数
$L(f(x),y)$
可以是MAE，也可以是交叉熵损失函数
其根据链式法则梯度
$\frac{\partial L}{\partial \theta}=\frac{\partial L}{\partial f(x)}·\frac{\partial f(x)}{\partial \theta}$
即表示为损失函数对模型的导乘以模型对参数的导。
模型对参数的求导：
$f(x)=w_0+\sum_{i=1}^{n}w_ix_i+\sum_{l=1}^{k}\frac{1}{2}\bigg[(\sum_{i=1}^{n}v_{il}x_i)^2-\sum_{i=1}^{n}(v_{il}x_i)^2\bigg]$

$\frac{\partial f(x)}{\partial \theta}= \begin{cases}1,&\text{ if }\theta=w_0 \\ x_i, &\text{ if }\theta=w_i \\ x_i\sum_{j=1}^{n}v_{jl}x_j-v_{il}x_i^2, &\text{ if }\theta=v_{il} \end{cases}$

面对这样的情况，我们可以使用如下几种优化算法求解参数

随机梯度下降法(SGD)
交替最小二乘法(ALS)
马尔科夫链蒙特卡罗法(MCMC)

随机梯度下降法(SGD)

很容易理解，根据上述式子可以得出损失函数的梯度，得知梯度后就很方便的可以应用SGD

交替最小二乘法(ALS)

又称坐标下降法
即每次只优化一个参数。令导数=0，求解当前这个参数的最优值。

马尔科夫链蒙特卡罗法(MCMC)

不会不想查 :)

以上三种方法具体可移步参考链接

3 FFM(Field Factorization Machine)

3.1 模型推导

FM的核心是特征交叉，这里面最重要的就是隐向量。FM中，每个特征 $x_i$ 都有且只有一个隐向量 $v_i$
在特征交叉时，对应的隐向量点乘得到这个交叉特征的权重 $w_{ij}$
然而，每个特征所代表的意义是不一样的，例如在计算交叉特征：“男性-20到30岁”，“男性-Nike”时，用同一个男性隐向量v点乘20-30岁和nike的隐向量结果的区别度低。FFM认为，每个特征 $x_i$ 的隐向量应该有多个，当该特征与不同类型(域field)的特征做交叉时，应该使用对应的隐向量，这样可以做到更精细地刻画交叉特征的权重。所以每个特征应该有和field数量相同的隐向量个数。
假设样本共有l个域 $(f_1,f_2,..f_l)$
特征 $x_i,x_j$ 分别属于域 $f_I,f_J$
$x_i$ 有l个隐向量 $(v_{i1},v_{i2}...v_{il})$ 分别对应l个域，v是一个k维向量
$x_j$ 有l个隐向量 $(v_{j1},v_{j2}...v_{jl})$ 分别对应l个域，v是一个k维向量
则当 $x_i,x_j$ 做交叉时，
$x_i$ 应该选取 $x_j$ 所在域对应的隐向量 $v_{iJ}$
$x_j$ 应该选取 $x_i$ 所在域对应的隐向量 $v_{jI}$
即
$<v_{iJ}·v_{jI}>x_ix_j$
这样更精准了，但是参数量多了l倍。所以实际应用中，FFM设置的隐向量长度k会比FM的k小很多以尽可能降低计算量。

3.2 优化算法

同FM

4 总结

FM模型相比传统LR模型，多了二元交叉特征组合。提高了模型表征能力。
从根本上来说，FM之所以可以这么容易的拓展与组合，是因为任务使用的是独热编码的离散化特征
FM全称Factorization Machine。其中Factorization是因式分解的意思。通过上面的介绍，我想很容易理解这个因式分解的意思。当出现特征交叉如 $x_i,x_j$ ，必然会有这个交叉特征的参数 $w_{ij}$ ，而FM把这个参数分解成了两个向量的点乘 $<v_i·v_j>$ 。而这两个向量可以看成是特征 $x_i,x_j$ 的一种编码。
对隐向量的进一步探讨
对于onehot编码来说，
$x_i$ 特征对应着向量 $[0,0...1...0...0]$ 其中第i位=1，其他=0；
$x_i$ 特征对应着向量 $[0,0...0...1...0]$ 其中第j位=1，其他=0；
所以 $x_i$ 的隐向量= $v_i$ 等价于 $[0,0...1...0...0]$ 被编码成 $v_i$ ：
$v_i=transform([0,0...1...0...0])$
而 $x_i*x_j$ 表示两特征交叉，其权重 $w_{ij}$ 则被FM表示成了两隐向量的內积 $<v_i·v_j>$
则 $<v_i·v_j>x_i*x_j=transform([0,0...1...0...0])·transform([0,0...0...1...0])$
注意式子
$\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}<v_i·v_j>x_ix_j \tag{4.1}$
虽然看似有 $o(n^2)$ 的复杂度，但实际上 $x_ix_j$ 绝大多数时候都=0，这表示对于每一个样本，式(4.1)计算量远达不到 $o(n^2)$ 。对于一个特定的样本，式(4.1)退化成
$\sum_{i=1}^{\overline{n} -1}\sum_{j=i+1}^{\overline{n}}<v_i·v_j>x_ix_j \tag{4.2}$
$\overline{n}$ 表示该样本的稀疏特征中1的数量。
即
$\begin{alignedat}{2} \sum_{i=1}^{\overline{n} -1}\sum_{j=i+1}^{\overline{n}}<v_i·v_j>x_ix_j = \sum_{i=1}^{\overline{n} -1}\sum_{j=i+1}^{\overline{n}}transform([0,0...1...0...0])·transform([0,0...0...1...0]) \end{alignedat}$
请理解这段，这段在理解DeepFM中有用。
参加过一个会议，会上有人说对于CTR预测或推荐系统重排序来说，最根本的是做特征组合。
因为独热编码的特征，每一维表征的信息太少，需要通过组合来提高每一维的表征能力。
同时，特征组合引入了非线性，可以提高拟合能力。
其实GBDT+LR模型，也是一种特征组合。
FM实际上做了一个Embedding 工作，把稀疏的独热特征转换成了稠密特征，这对于深度学习是友好的，所以后续有很多FM和神经网络结合的工作。

未完待续。。。

5 注释

[1].此处应用平方和公式
$(x_1+x_2+x_3)^2=x_1^2+x_2^2+x_3^2+2x_1x_2+2x_1x_3+2x_2x_3$
$x_1x_2+x_1x_3+x_2x_3=\frac{1}{2}((x_1+x_2+x_3)^2-(x_1^2+x_2^2+x_3^2))$
即
$\sum_{i=1}^{2}\sum_{j=i+1}^{3}x_ix_j=\frac{1}{2}\bigg[(\sum_{i=1}^{3}x_i)^2-\sum_{i=1}^{3}(x_i)^2\bigg]$

参考

https://www.cnblogs.com/pinard/p/6370127.html
https://tracholar.github.io/machine-learning/2017/03/10/factorization-machine.html
https://www.cnblogs.com/wkang/p/9788012.html