推荐系统学习笔记之四 Factorization Machines 因子分解机 + Field-aware Factorization Machine(FFM) 场感知分解机-白红宇

推荐系统学习笔记之四 Factorization Machines 因子分解机 + Field-aware Factorization Machine(FFM) 场感知分解机

阅读量：2288 次

发布时间：2019-05-09

本文共 4156 字，大约阅读时间需要 13 分钟。

前言

Factorization Machines(FM) 因子分解机是Steffen Rendle于2010年提出，而Field-aware Factorization Machine (FFM) 场感知分解机最初的概念来自于Yu-Chin Juan与其比赛队员，它们借鉴了辣子Michael Jahrer的论文中field概念，提出了FM的升级版模型。

FM的paper中主要对比对象是SVM支持向量机，与SVM相比，有如下几个优势

FM可以实现对于输入数据是非常稀疏（比如自动推荐系统），而SVM会效果很差，因为训出的SVM模型会面临较高的bias。

FMs拥有线性的复杂度, 可以通过 primal 来优化而不依赖于像SVM的支持向量机。

在推荐系统和计算广告领域，点击率CTR（click-through rate）和转化率CVR（conversion rate）是衡量广告流量的两个关键指标。准确的估计CTR、CVR对于提高流量的价值，增加广告收入有重要的指导作用。FM和FFM近年来表现突出，分别在由Criteo和Avazu举办的CTR预测竞赛中夺得冠军。

Factorization Machines 因子分解机

假如在某个电影播放网站有这么一组实时数据：

MoviesClass	Actor	Director	MoviesIsPlay?
Action	A	AA	1
Romantic	B	BB	0
Action	A	BB	1

其中MoviesIsPlay?是label，MoviesClass 、UserType、Actor、Director是特征。以上这四种特征都是categorical类型的，需要经过独热编码（One-Hot Encoding）转换成数值型特征。

MoviesClass = Action	MoviesClass = Romantic	Actor = A	Actor = B	Director = AA	Director = BB	MoviesIsPlay = 1	MoviesIsPlay = 0
1	0	1	0	1	0	1	0
0	1	0	1	0	1	0	1
1	0	1	0	0	1	1	0

从该独热编码表可以看出矩阵许多值都为0，数据十分稀疏，而且会导致数据维度增大，数量级从 $n$ 增大到

$n^2$ 。

而我们的目的是从该矩阵中获取到特征的某些关联，比如MovieClass=action 与 actor=A 关联比较大，电影播放量可很客观，从而对用户进行推荐。

先从线性回归和多项式回归开始建模，这里我们以二阶多项式模型（degree = 2时）为例：

xixj $x_ix_j$ 表示特征xi和xj的组合，当

xi $x_i$ 和

xj $x_j$ 都非零时，组合特征

xixj $x_ix_j$ 才有意义。

y^(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                  交 叉 项 （ 组 合 特 征 ）

$\hat{y}(x) := \underbrace {w_0 + \sum_{i=1}^{n} w_i x_i }_{\text{线性回归}} + \underbrace {\sum_{i=1}^{n} \sum_{j=i+1}^{n} w_{ij} x_i x_j}_{\text{交叉项（组合特征）}}$

其中，n 代表样本的特征数量，

$x_i$ 是第 i 个特征的值，

w0、wi、wij

$w_0、w_i、w_{ij}$ 是模型参数。

从此公式可以看出组合特征一共有n(n-1)/2个，如果特征n上百个，组合特征上万个，就是任意两个 $w_{ij}$ 相互独立，样本数据很稀疏， $x_ix_j$ 为非零的项会非常的少，导致训练样本的不足，很容易导致参数 $w_{ij}$ 不准确，最终将严重影响模型的性能和稳定性。

那么如何解决这些问题呢？上一篇的矩阵分解提供了思路。在一个rating矩阵可以分解为user矩阵和item矩阵，每个user和item都可以采用一个隐向量表示，两个向量的点积就是矩阵中user对item的打分。

类似地，所有二次项参数 $w_{ij}$ 可以组成一个对称阵 $W$ ，可以分解为

W=VTV

$\mathbf{W} = \mathbf{V}^T \mathbf{V}$ ，

V $V$ 的第 j 列便是第 j 维特征的隐向量，也就是说每个参数 $w_{ij}=⟨v_i,v_j⟩$ ，这就是FM模型的核心思想（不讨论高阶形式）。所以可以得到：

y^(x) : = w 0 + \sum i = 1 n w i x i + \sum i = 1 n \sum j = i + 1 n ⟨ v i, v j ⟩ x i x j

$\hat{y}(\mathbf{x}) := w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j$

其中<>表示两个向量的点积
$⟨ v i, v j ⟩ : = \sum f = 1 k v i, f \cdot v j, f$ $\langle \mathbf{v}_i, \mathbf{v}_j \rangle := \sum_{f=1}^{k} v_{i,f} \cdot v_{j,f}$
直观上看，FM的复杂度是 $O(kn^2)$ 。但是，通过下列等式，FM的二次项可以化简，其复杂度可以优化到 $O(kn)$ 。由此可见，FM可以在线性时间对新样本作出预测。

$\sum i = 1 n \sum j = i + 1 n ⟨ v i, v j ⟩ x i x j = 1 2 \sum f = 1 k ⎛ ⎝ (\sum i = 1 n v i, f x i) 2 - \sum i = 1 n v 2 i, f x 2 i ⎞ ⎠$ $\sum_{i=1}^n \sum_{j=i+1}^n \langle \mathbf{v}_i, \mathbf{v}_j \rangle x_i x_j = \frac{1}{2} \sum_{f=1}^k \left(\left( \sum_{i=1}^n v_{i, f} x_i \right)^2 - \sum_{i=1}^n v_{i, f}^2 x_i^2 \right)$
下面给出详细证明过程：

$= = = = \sum i = 1 n \sum j = i + 1 n ⟨ v i, v j ⟩ x i x j (1) 1 2 \sum i = 1 n \sum j = 1 n ⟨ v i, v j ⟩ x i x j - 1 2 \sum i = 1 n ⟨ v i, v i ⟩ x i x i (2) 1 2 ⎛ ⎝ \sum i = 1 n \sum j = 1 n \sum f = 1 k v i, f v j, f x i x j - \sum i = 1 n \sum f = 1 k v i, f v i, f x i x i ⎞ ⎠ (3) 1 2 \sum f = 1 k ⎧ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ (\sum i = 1 n v i, f x i) \cdot ⎛ ⎝ \sum j = 1 n v j, f x j ⎞ ⎠ - \sum i = 1 n v 2 i, f x 2 i ⎫ ⎭ ⎪ ⎪ ⎪ ⎪ ⎪ (4) 1 2 \sum f = 1 k ⎧ ⎩ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ (\sum i = 1 n v i, f x i) 2 - \sum i = 1 n v 2 i, f x 2 i ⎫ ⎭ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ (5)$
$\begin{align} & \sum_{i=1}^{n} \sum_{j=i+1}^{n} {\langle \mathbf{v}_i, \mathbf{v}_j \rangle} x_i x_j \qquad\qquad\qquad\qquad\qquad\qquad(1)\\ = & \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} {\langle \mathbf{v}_i, \mathbf{v}_j \rangle} x_i x_j - \frac{1}{2} \sum_{i=1}^{n} {\langle \mathbf{v}_i, \mathbf{v}_i \rangle} x_i x_i \qquad\qquad\;\;(2)\\ = & \frac{1}{2} \left(\sum_{i=1}^{n} \sum_{j=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{j,f} x_i x_j - \sum_{i=1}^{n} \sum_{f=1}^{k} v_{i,f} v_{i,f} x_i x_i \right) \qquad\,(3) \\ = & \frac{1}{2} \sum_{f=1}^{k} {\left \lgroup \left(\sum_{i=1}^{n} v_{i,f} x_i \right) \cdot \left(\sum_{j=1}^{n} v_{j,f} x_j \right) - \sum_{i=1}^{n} v_{i,f}^2 x_i^2 \right \rgroup} \quad\;\;\,(4) \\ = & \frac{1}{2} \sum_{f=1}^{k} {\left \lgroup \left(\sum_{i=1}^{n} v_{i,f} x_i \right)^2 - \sum_{i=1}^{n} v_{i,f}^2 x_i^2\right \rgroup} \qquad\qquad\qquad\;\;(5) \end{align}$

其中第（1）步到第（2）步，这里用AA表示系数矩阵VV的上三角元素，BB表示对角线上的交叉项系数。由于系数矩阵VV是一个对称阵，所以下三角与上三角相等，有下式成立：

$A = 1 2 (2 A + B) - 1 2 B . A = \sum i = 1 n \sum j = i + 1 n ⟨ v i, v j ⟩ x i x j - - - - - - - - - - - - - - - - - - -; B = 1 2 \sum i = 1 n ⟨ v i, v i ⟩ x i x i - - - - - - - - - - - - - - - - -$
$A = \frac{1}{2} (2A+B) - \frac{1}{2} B. \quad \underline{ A=\sum_{i=1}^{n} \sum_{j=i+1}^{n} {\langle \mathbf{v}_i, \mathbf{v}_j \rangle} x_i x_j } ; \quad \underline{ B = \frac{1}{2} \sum_{i=1}^{n} {\langle \mathbf{v}_i, \mathbf{v}_i \rangle} x_i x_i }$

之后采用随机梯度下降SGD（Stochastic Gradient Descent）训练模型参数。那么，模型各个参数的梯度如下:

$\partial \partial θ y (x) = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ 1, x i x i \sum j = 1 n v j, f x j - v i, f x 2 i, if θ is w 0 (常数项) if θ is w i (线性项) if θ is v i, f (交叉项)$ $\frac{\partial}{\partial \theta} y(\mathbf{x}) = \left \{ \begin{array}{ll} 1, & \text{if}\; \theta\; \text{is}\; w_0 \qquad \text{(常数项)} \\ x_i & \text{if}\; \theta\; \text{is}\; w_i \;\qquad \text{(线性项)} \\ x_i \sum_{j=1}^{n} v_{j,f} x_j - v_{i,f} x_i^2, & \text{if}\; \theta\; \text{is}\; v_{i,f} \qquad \text{(交叉项)} \end{array} \right.$
其中， $v_{j,f}$ 是隐向量 $v_j$ 的第 f 个元素。由于 $\sum_{j=1}^n v_{j, f} x_j$ 只与 f 有关，而与 i 无关，在每次迭代过程中，只需计算一次所有 f 的 $\sum_{j=1}^n v_{j, f} x_j$ 就能够方便地得到所有 $v_{i,f}$ 的梯度。因此，FM参数训练的复杂度也是 O(kn)。

FM总结

首先是为什么使用向量的点积可以解决以上问题呢？

参数的数量大幅度缩减，从n×(n−1)/2降低到nk

隐向量的点积可以表示原本两个毫无相关的参数之间的关系

而稀疏数据下学习不充分的问题也能得到充分解决。比如原本的多项式回归的参数 $w_{12}$ 的学习只能依赖于特征 $x_1$ 和 $x_2$ ；而对参数 $⟨v_1,v_2⟩$ 而言就完全不一样了，它由 $v_1$ 和 $v_2$ 组成。而对于每个向量可以通过多个交叉组合特征学习得到，比如可以由 $x_1x_2,x_1x_3,..$ 学习获得，这样可供学习的非零样本就大大增加了。

其次FM与矩阵分解MF与SVM有什么差别呢？

FM是一种比较灵活的模型，通过合适的特征变换方式，FM可以模拟二阶多项式核的SVM模型、MF模型、SVD++模型等。

相比SVM的二阶多项式核而言，FM在样本稀疏的情况下是有优势的；而且，FM的训练/预测复杂度是线性的，而二项多项式核SVM需要计算核矩阵，核矩阵复杂度就是N平方。

相比MF而言，我们把MF中每一项的rating分改写为 $r_{ui} \sim \beta_u + \gamma_i + x_u^T y_i$ ，从此公式中可以看出，这相当于只有两类特征 $\beta$ 和 $\gamma$ 的FM模型。对于FM而言，我们可以加任意多的特征，比如user的历史购买平均值，item的历史购买平均值等，但是MF只能局限在两类特征。SVD++与MF类似，在特征的扩展性上都不如FM。

Field-aware Factorization Machine(FFM) 场感知分解机

场感知说白了可以理解为分类。通过引入field的概念，FFM把相同性质的特征归于同一个field。比如， “MovieClass = romantic”、“MovieClass = action”这2个特征值都是代表电影分类的，可以放到同一个field中。简单来说，同一个类别的特征经过One-Hot编码生成的数值特征都可以放到同一个field。在FFM中，每一维特征 $x_i$ ，针对其它特征的每一种field $f_j$ ，都会学习一个隐向量 $v_{i,f_j}$ 。因此，隐向量不仅与特征相关，也与field相关。也就是说，“MovieClass”这个特征与“UserRate”特征和“PlayTimes”特征进行关联的时候使用不同的隐向量，也是FFM中“field-aware”的由来。
通过修改FM的公式，我们可以得出：

$y^(x) : = w 0 + \sum i = 1 n w i x i + \sum i = 1 n \sum j = i + 1 n ⟨ v i, f j, v j, f i ⟩ x i x j$ $\hat{y}(\mathbf{x}) := w_0 + \sum_{i=1}^{n} w_i x_i + \sum_{i=1}^{n} \sum_{j=i+1}^{n} \langle \mathbf{v}_{i,\,f_j}, \mathbf{v}_{j,\,f_i} \rangle x_i x_j$
其中， $f_j$ 是第j个特征所属的field。如果隐向量的长度为k，那么FFM的二交叉项参数就有 $nfk$ 个，远多于FM模型的 $nk$ 个。此外，由于隐向量与field相关，FFM的交叉项并不能够像FM那样做化简，其预测复杂度为 $O(kn^2)$ 。

为了使用FFM方法，所有的特征必须转换成“field_id:feat_id:value”格式，field_id代表特征所属field的编号，feat_id是特征编号，value是特征的值。数值型的特征比较容易处理，只需分配单独的field编号，如用户评论得分、商品的历史CTR/CVR等。categorical特征需要经过One-Hot编码成数值型，编码产生的所有特征同属于一个field，而特征的值只能是0或1，如用户的性别、年龄段，商品的品类id等。
除此之外，还有第三类特征，如用户浏览/购买品类，有多个品类id且用一个数值衡量用户浏览或购买每个品类商品的数量。这类特征按照categorical特征处理，不同的只是特征的值不是0或1，而是代表用户浏览或购买数量的数值。按前述方法得到field_id之后，再对转换后特征顺序编号，得到feat_id，特征的值也可以按照之前的方法获得。

参考文献

FFM C++实现

转载地址：http://pcfnb.baihongyu.com/

你可能感兴趣的文章

一线互联网大厂面经分享：阿里三面+头条四面+腾讯二面+美团四面