推荐系统-FM模型理论详解

Posted by mudux on February 6, 2020

1. 应用背景

 在计算广告和推荐系统中,CTR预估(click-through rate)和转化率CVR(conversion rate)估计是非常重要的一个环节。判断一个物品是否进行推荐需要根据CTR预估的点击率排序决定。业界常用的方法有人工特征工程+LR(Logistic Regression)、GBDT(Gradient Boosting Decision Tree) + LR、FM(Factorization Machine)和FFM(Field-aware Factorization Machine)等。
 在进行CTR预估时,除了单特征外,往往要对特征进行组合。对于特征组合来说,业界现在通用的做法主要有两大类:FM系列与Tree系列。
 2010年,日本大阪大学(Osaka University)的 Steffen Rendle 在矩阵分解(MF)、SVD++、PITF、FPMC等基础之上,归纳出针对高维稀疏数据的因子机(Factorization Machine, FM)模型。因子机模型可以将上述模型全部纳入一个统一的框架进行分析。并且,Steffen Rendle 实现了一个单机多线程版本的 libFM。在随后的KDD Cup 2012,track2 广告点击率预估(pCTR)中,国立台湾大学和 Opera Solutions两只队伍都采用了 FM,并获得大赛的冠亚军而使得 FM 名声大噪。随后,台湾大学的 Yuchin Juan 等人在总结自己在两次比赛中的经验以及 Opera Solutions 队伍中使用的 FM 模型的总结,提出了一般化的 FFM 模型,并实现了单机多线程版的libFFM,并做了深入的试验研究。事实上,Opera Solutions 在比赛中用的 FM 就是FFM。
 最近几年出现了许多基于FM改进的方法,如deepFM,FNN,PNN,DCN,xDeepFM等,这些后面介绍。这里主要讲解FM算法。

2. 预测任务

 在机器学习中,预测是一项最基本的任务,所谓的预测就是估计一个函数

 该函数将一个$n$维的实值特征向量$x \in {R^n}$映射到一个目标域$T$,例如,对于回归$T=R$,对于分类问题$T={+,-}$。在有监督学习(supervised learning)场景中,通常有一个带标签的训练数据集

 其中$x^{(i)} \in R^n$表示输入数据,对应样本的特征向量,$y^{(i)}$对应标签,$m$为样本的数目。

 在现实世界中,许多应用问题(如文本分析、推荐系统等)会产生高度稀疏的数据,即特征向量$x^{(i)}$中几乎所有的分量都为0。这里,以电影评分系统为例,给出一个关于高度稀疏数据的实例。

例1. 考虑电影评分系统中的数据,它的每一条记录都包含了那个用户$u \in U$在什么时候$t \in R$对那部电影$i \in I$打了多少分$r \in {1,2,3,4,5}$这样的信息。假定用户集$U$和电影集$I$分别为

 设观测到的数据集$S$为

 利用观测数据集$S$来进行预测任务的一个实例是:估计一个函数$\mathop y\limits^\^ $来预测某个用户在某个时刻对某部电影的打分行为。

 利用观测数据集$S$构造数据样本如下图所示:

data

  • 第一部分(对应蓝色方框)表示当前评分用户信息,其维度为 ,该部分的分量中,当前电影评分用户所在的位置为1,其他为0。例如,在第一条观测记录中,就有
  • 第二部分(对应红色方框)表示当前被评分电影信息,其维度为 ,该部分的分量中,当前被评分的电影所在的位置为1,其他为0。例如,在第一条观测记录中,就有
  • 第三部分(对应黄色方框)表示当前评分用户评分过的所有电影信息,其维度为 ,该部分的分量中,被当前用户评论过的所有电影(设个数为 )的位置为 ,其他为0。例如,Alice评价过三部电影TI,NH和SW,因此就有
  • 第四部分(对应绿色方框)表示评分日期信息,其维度为1,用来表示用户评价电影的时间,表示方法是将(记录中最早的日期)2009年1月作为基数1,以后每增加1个月就加1,如2009年5月就可以折算为5。
  • 第五部分(对应棕色方框)表示当前评分用户最近评分过的一部电影的信息,其维度为 ,该部分的分量中,如当前用户评价当前电影之前还评价过其它电影,则将当前用户评价的上一部电影的位置取为1,其他为0;若当前用户评价当前电影之前没有评价过其他的电影,则所有的评分都取为0。例如,对于第二条观测记录,Alice评价NH之前评价的是TI,因此有

 在本例中,特征向量  总的维度为 。在一个真实的电影评分系统中,用户的数目$|U|$和电影的数目$|I|$是很大的,而每个用户参与评论的电影数目则相对较小,于是,每一条记录对应的特征向量将会很稀疏。为定量刻画这种稀疏,记$N_z(x)$表示$x$中非零分量的个数,并记

 其中$X$表示由样本按行拼接成的矩阵,即

 则$\overline (X)$表示训练集$D$中所有特征向量中非零分量数的平均值。显然,对于稀疏数据,成立

$\overline {N_z} (X) \ll n$。

3. 模型方程

3.1 二阶表达式

 在介绍FM的模型方程之前,先讲一下线性回归。对于一个给定的特征向量$x=(x_1, x_2,…,x_n)^T$,线性回归建模时采用的函数是

 其中,$w_0$和$\rm w=(w_1, w_2,…,w_n)^T$为模型参数。从方程易见:各特征分量$x_i$和$x_j$($i \neq j$)之间是相互孤立的,即$\widehat y(x)$中仅考虑单个的特征分量,而没有考虑特征分量之间的相互关系(interaction)。

 为了表示特征交叉,将$\widehat y(x)$改写为

 这样任意连个互异特征分量之间的关系也考虑进来了。不过,这种直接在$x_ix_j$前面配上一个系数$w_{ij}$的方式在稀疏数据中有一个很大的缺陷,例如在上例中,观测集$S$中没有Alice评价电影Star Trek的记录,如果直接估计Alice(A)和Star Trek(ST)之间,或者说特征分量$x_A$和$x_{ST}$之间的相互关系,显然会得到系数$w_{A,ST}=0$。即对于观测样本中未出现过交互的特征分量,不能对相应的参数进行估计。注意,在高度稀疏数据场景中,由于数据量的不足,样本中出现未交互的特征分量是很普遍的。
 为克服这个缺陷,在系数$w_{ij}$上做文章,将其表示成另外的形式。为此,针对每个维度的特征分量$x_i$,引入辅助分量

 其中$k \in {N^ + }$为超参数,并将$w_{ij}$改写为


 这样就能克服上面提到的缺陷了?我们粗略地分析一下。在观测数据中,Bob(B)对Star Wars(SW)和Star Trek(ST)的评分差不多,由此可认为它们对应的辅助向量$v_{ST}$和$v_{SW}$也比较相似。从而,利用$\widehat w_{A,SW}$就可以对$\widehat w_{A,ST}$进行估计了。(当然,这里并不是说,真的要先计算出$\widehat w_{A,SW}$然后用它作为$\widehat w_{A,ST}$的近似。因为这些性质都是观测数据中内在的,我们要做的只是建好模型,让模型在训练阶段自动去学习。)
 于是,函数$\widehat y$可以进一步改写为


 从数学的角度来看,(3.2)和(3.5)的主要区别在哪呢?对于交叉项$x_ix_j$的系数,前者用的是$w_{ij}$,后者用的是$\widehat y_{ij}$。为更好地看清楚它们之间的关系,引入几个矩阵。

  • 将${v_i}_{i=1}^n$按行拼接成的矩阵$V$
  • 交互矩阵(interaction matrix)$W$
  • 交互矩阵$\widehat W$

 由此可见,(3.2)和(3.5)分别采用了交互矩阵$W$和$\widehat W$的非对角线元素作为$x_ix_j$的系数。由于$\widehat W=VV^T$是一种矩阵分解。因此将这种以(3.5)作为模型方程的方法称为Factorization Machines方法。
 那么$VV^T$的表达能力怎么样呢?即任意给定一个交互矩阵$\widehat W$,能否找到相应的分解矩阵$V$呢?答案是肯定的,这里需要用到一个结论“当$k$足够大时,对于任意对称正定的实矩阵$\widehat W \in R^{n \times n}$,均存在实矩阵$V \in R^{n \times k}$,使得成立$\widehat w = VV^T$”。
 由于(3.5)中只涉及满足$i<j$的$x_ix_j$,因此$\widehat W$的对称性没有问题,那如何保证$\widehat W$的正定性呢?注意,我们只关心互异特征分量之间的相互关系,因此$\widehat W$的对角线元素是可以任意取值的,只需将它们取得足够大(例如保证行元素满足严格对角占优),就可以保证$\widehat W$的正定性。
 理论分析中,我们要求参数$k$取得足够大,但是,在高度稀疏数据场景中,由于没有足够的样本来估计复杂的交互矩阵,因此$k$通常应取得很小。事实上,对参数$k$(亦即FM的表达能力)的限制,在一定程度上可以提高模型的泛化能力。这种能够利用$\widehat W$的低秩近似的性质也是FM的一个优势。

3.2 复杂度分析

 FM模型方程(3.5)中需要估计的参数包括

 共有$1+n+nk$个参数,其中$w_0$为整体的偏置量,$\rm w$对特征向量的各个分量的强度进行建模,$V$对特征向量中任意两个分量之间的关系进行了建模。
 那么,模型方程(3.5)的计算复杂度如何?直接从公式来看,其计算复杂度为

 其中第一个花括号对应$\sum \limits_{i=1}^n w_ix_i$的加法和乘法操作数,第二个括号对应$\sum \limits_{i=1}^{n-1}\sum \limits_{j=i+1}^{n}(\rm v_i^T v_j)x_ix_j$的加法和乘法操作数。
 如果对(3.5)进行改写,可将其计算复杂度降成线性的$O(kn)$,具体推导过程如下。

 易见,(3.9)的计算复杂度为

 注意,在高度稀疏数据场景中,特征向量$\rm x$中绝大部分分量为零,即$N_z(\rm x)$很小,而(3.9)中关于$i$的求和只需对非零元素进行,于是,计算复杂度就变成了$O(kN_z(\rm x))$。对整个数据集$D$而言,平均复杂度就是 了,所以FM可以在线性时间训练和预测

3.3 SGD求解参数

由上式可知,$v_{i,f}$的训练只需要样本的$x_i$特征非0即可,适合于稀疏数据
 在适用SGD训练模型是,在每次迭代中,只需计算一次所有的$f$的$\sum \limits_{j=1}^{n}v_{j,f}x_j$就能方便得到所有$v_{i,f}$的梯度。

3.4 推广到多阶

 前面描述的FM模型方程(3.5)包含各个特征分量,以及任意两个特征分量之间相互关系的项。我们将这种方程称为2-way(或二阶)FM方程。接下来,我们将它进一步推广位d-way(d>=2)FM方程,即方程可以同时刻画任意$\widetilde d\left( {1 \le \widetilde d \le d} \right)$个特征分量之间的相互关系。此时,方程可以定义为

 以$d=3$为例,(3.11)的第三项展开来就是

 上式中第一项刻画的是任意两个特征分量之间的相互关系,第二项刻画的是任意三个特征分量之间的相互关系。事实上,(3.11)中每一个$l$值对应一级特征分量相互关系,第$l(l \ge 2)$级关系的参数来自矩阵

 易知,公式(3.11)的计算复杂度为$O(k_dn^d)$。

3.4 总结

FM目的:旨在解决稀疏数据下的特征组合问题。
优势:

  • 适用于高度稀疏数据场景;
  • 具有线性的计算复杂度。

4. 回归和分类

 利用FM的模型方程,可以进行各种预测任务,如回归(Regression)、分类(Classification)和排名(Ranking)等。下面以回归和二分类为例,给出这两种预测任务中优化目标函数的构造。优化目标函数通常取为形如

的损失函数,优化的目标是将其最小化,其中$loss(\widehat y(\rm x^{(i)}), y^{(i)})$称为关于第$i$个样本$(x^{(i)}, y^{(i)})$的损失函数。

  • 回归问题
    对于回归问题,损失函数可取为最小平方误差(least square error),即
  • 二分类问题
    对于二分类(Binary Classification)问题(其中标签$y \in {+1, -1}$),损失函数可取为hinge loss函数logit 函数
    1. hinge loss函数

    当$y=+1$时

    当$y=-1$时

    模型训练好后,就可以利用$\widehat y(\rm x)$的正负符号来预测$\rm x$的分类了。
    2. logit loss函数

     其中$\sigma (x)=\frac {1}{1+e^{-x}}$为sigmoid函数。由定义(4.6)可见,$\widehat y$和$y$越接近,损失就越小。

    此外,为了防止过拟合,通常会在优化目标函数加入正则项

5. 其他

5.1 关于隐向量V

 这里的$v_i$是$x_i$特征的低维稠密表达,实际中隐向量的长度$k$通常远小于特征维度$n$。FM学到的隐向量可以看做是特征的一种embedding表示,把离散特征转化为Dense Feature,这种Dense Feature还可以后续和DNN结合,作为DNN的输入,事实上用于DNN的CTR也是这个思路来做的。

5.2 FM与矩阵分解

userItem  基于矩阵分解的协同过滤是推荐系统中常用的一种推荐方案,从历史数据中收集user对item的评分,可以是显式的打分,也可以是用户的隐式反馈计算的得分。由于user和item数量非常多,有过打分的user和item对通常是十分稀少的,基于矩阵分解的协同过滤是来预测那些没有过行为的user对item的打分,实际上是一个评分预测问题。矩阵分解的方法假设user对item的打分$\widehat r_{ui}$由下式决定

 其中$q_i$是第$i$个item对应的隐向量,$p_u$是第$u$个user对应的隐向量,$b_i$代表item的偏置,用于解释商品本身的热门和冷门,$b_u$代表user的偏置,用于解释用户本身的打分偏好(例如有些人喜欢打低分),$\mu$是常数。即将评分矩阵分解为user矩阵和item矩阵的乘积加上线性项和常数项,而这两个矩阵是低秩的!这些参数通过对最小化经验误差得到。

 从上面的叙述来看,FM的二阶矩阵也用了矩阵分解的技巧,那么基于矩阵分解的协同过滤和FM是什么关系呢?以user对item评分预测问题为例,基于矩阵分解的协同过滤可以看做FM的一个特殊例子,对于每一个样本,FM可以看做特征只有userid和itemid的onehot编码后的向量连接而成的向量。从FM和MFCF公式来看,MFCF的用户向量$p_u$和item向量$q_i$可以看做FM中的隐向量,user和iter的bias向量$b_u,b_i$就是FM中的一次项系数,常数$\mu$也和FM中的常数$w_0$相对应,可以看到,MFCF就是FM的一个特例!另外,FM可以采用更多的特征,学习更多的组合模式,这是单个矩阵分解的模式所做不到的!因此,FM比矩阵分解的方法更具普遍性!事实上,现在能用矩阵分解的方法做的方案都直接上FM了!

5.3 FM与决策树

 FM和决策树都可以做特征组合,Facebook就用GBDT学习特征的自动组合,决策树可以非常方便的对特征做高阶组合。一棵决策的叶子节点实际上就对应一条特征规则,例如最左边的叶子节点就代表一条特征组合规则$x_1=1,x_2=1$。通过增加树的深度,可以很方便的学习到更高级的非线性组合模式。通过增加树的棵树,可以学习到很多这样的模式,论文[10]采用GBDT来建立决策树,使得新增的决策树能够拟合损失函数的残差。
 但是,决策树和二项式模型有一个共同的问题,那就是无法学习到数据中不存在的模式。例如,对于模式$x_1=1,x_2=1$,如果这种模式在数据中不存在,或者数量特别少,那么决策树在对特征$x_1$分裂后,就不会再对$x_2$分裂了。当数据不是高度稀疏的,特征间的组合模式基本上都能够找到足够的样本,那么决策树能够有效地学习到比较复杂的特征组合;但是在高度稀疏的数据中,二阶组合的数量就足以让绝大多数模式找不到样本,这使得决策树无法学到这些简单的二阶模式,更不用说更高阶的组合了。

5.4 FM与神经网络

 神经网络天然地难以直接处理高维稀疏的离散特征,因为这将导致神经元的连接参数太多。但是低维嵌入(embedding)技巧可以解决这个问题,词的分布式表达就是一个很好的例子。事实上 FM就可以看做对高维稀疏的离散特征做 embedding。神经网络对稀疏离散特征做 embedding 后,可以做更复杂的非线性变换,具有比FM跟大的潜力学习到更深层的非线性关系!基于这个思想,2016年,Google提出 wide and deep 模型用作 Google Play的app推荐[11],它利用神经网络做离散特征和连续特征之间的交叉,神经网络的输出和人工组合较低维度的离散特征一起预测,并且采用端到端的学习,联合优化DNN和LR。

6. 后续

  • FM代码实现;
  • 相关paper阅读。

7. Reference

1.分解机(Factorization Machines)推荐算法原理-刘建平
2.因子机深入解析
3.FM(Factorization Machines)的理论与实践-知乎
4.FM-pytorch
5.深入FFM原理与实践-美团技术团队
6.FM算法解析
7.FM-github
[8] Koren Y, Bell R M, Volinsky C, et al. Matrix Factorization Techniques for Recommender Systems[J]. IEEE Computer, 2009, 42(8): 30-37.
[9] Rendle S. Factorization Machines[C]. international conference on data mining, 2010.
[10] He X, Pan J, Jin O, et al. Practical Lessons from Predicting Clicks on Ads at Facebook[C]. knowledge discovery and data mining, 2014: 1-9.
[11] Cheng H T, Koc L, Harmsen J, et al. Wide & Deep Learning for Recommender Systems[C]// The Workshop on Deep Learning for Recommender Systems. ACM, 2016:7-10.