推荐系统FM & FFM算法解读与实践「建议收藏」

推荐系统FM & FFM算法解读与实践「建议收藏」在推荐系统和计算广告业务中,点击率CTR(click-throughrate)和转化率CVR(conversionrate)是衡量流量转化的两个关键指标。准确的估计CTR、CVR对于提高流量的价值,增加广告及电商收入有重要的指导作用。业界常用的方法有人工特征工程+LR(LogisticRegression)、GBDT(GradientBoostingDecisionTree)+...

在推荐系统和计算广告业务中,点击率CTR(click-through rate)和转化率CVR(conversion rate)是衡量流量转化的两个关键指标。准确的估计CTR、CVR对于提高流量的价值,增加广告及电商收入有重要的指导作用。业界常用的方法有人工特征工程 + LR(Logistic Regression)、GBDT(Gradient Boosting Decision Tree) + LR、FM模型。在这些模型中,FM近年来表现突出,分别在由Criteo和Avazu举办的CTR预测竞赛中夺得冠军。

因子分解机(Factorization Machine, FM)是由Steffen Rendle提出的一种基于矩阵分解的机器学习算法,其主要用于解决数据稀疏的业务场景(如推荐业务),特征怎样组合的问题。

paper指出FM与SVM相比,有如下优势:

  • FM可以实现非常稀疏数据参数估计,而SVM会效果很差,因为训出的SVM模型会面临较高的bias;
  • FMs拥有线性的复杂度, 可以通过 primal 来优化而不依赖于像SVM的支持向量机;

一、FM原理

1. 为什么进行特征组合?

在feed流推荐场景中,根据user和item基础信息(clicked:是否点击;userId:用户ID;userGender:用户性别;itemTag:物品类别),来预测用户是否对物品感兴趣(点击与否,二分类问题)。源数据如下:

clicked

userId userGender itemTag
1 1 篮球
0 1 化妆品
0 2 篮球
1 2 化妆品

 由于userGender和itemTag特征都是categorical类型的,需要经过独热编码(One-Hot Encoding)转换成数值型特征。

clicked userId userGender_男 userGender_女 itemTag_篮球 itemTag_化妆品
1 1 1 0 1 0
0 1 1 0 0 1
0 2 0 1 1 0
1 2 0 1 0 1

经过One-Hot编码之后,大部分样本数据特征是比较稀疏的。上面的样例中,每个样本有5维特征,但平均仅有3维特征具有非零值。实际上,这种情况并不是此例独有的,在真实应用场景中这种情况普遍存在。例如,CTR/CVR预测时,用户的性别、职业、教育水平、品类偏好,商品的品类等,经过One-Hot编码转换后都会导致样本数据的稀疏性。特别是商品品类这种类型的特征,如商品的三级品类约有1000个,采用One-Hot编码生成1000个数值特征,但每个样本的这1000个特征,有且仅有一个是有效的(非零)。由此可见,数据稀疏性是实际问题中不可避免的挑战。

One-Hot编码的另一个特点就是导致特征空间大。例如,商品三级类目有1000维特征,一个categorical特征转换为1000维数值特征,特征空间剧增。

同时通过观察大量的样本数据可以发现,某些特征经过关联之后,与label之间的相关性就会提高。例如,“男性”与“篮球”、“女性”与“化妆品”这样的关联特征,对用户的点击有着正向的影响。换句话说:男性用户很可能会在篮球有大量的浏览行为;而在化妆品却不会有。这种关联特征与label的正向相关性在实际问题中是普遍存在的。因此,引入两个特征的组合是非常有意义的。

2. 如何组合特征?

多项式模型是包含特征组合的最直观的模型。在多项式模型中,特征x_{i}x_{j}的组合采用x_{i}x_{j}表示,即x_{i}x_{j}都非零时,组合特征x_{i}x_{j}才有意义。从对比的角度,本文只讨论二阶多项式模型。模型的表达式如下:

y(X)=w_{0}+\sum_{i=1}^{n}w_{_i}x_{_i}+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}w_{ij}x_{i}x_{j}

其中, n代表样本的特征数量,x_{i}是第i个特征的值, w_{0},w_{_i}x_{_i},w_{ij}是模型参数。

从公式来看,模型前半部分就是普通的LR线性组合,后半部分的交叉项即特征的组合。单从模型表达能力上来看,FM的表达能力是强于LR的,至少不会比LR弱,当交叉项参数全为0时退化为普通的LR模型。

从上面公式可以看出,组合特征的参数一共有\frac{n(n-1)}{2}个,任意两个参数都是独立的。然而,在数据稀疏性普遍存在的实际应用场景中,二次项参数的训练是很困难的。其原因是:每个参数w_{ij}的训练需要大量x_{i}x_{j}都非零的样本;由于样本数据本来就比较稀疏,满足x_{i}x_{j}都非零的样本将会非常少。训练样本的不足,很容易导致参数w_{ij}不准确,最终将严重影响模型的性能。

3. 如何解决二次项参数的训练问题呢?

矩阵分解提供了一种解决思路。在model-based的协同过滤中,一个rating矩阵可以分解为user矩阵和item矩阵,每个user和item都可以采用一个隐向量表示。比如在下图中的例子中,我们把每个user表示成一个二维向量,同时把每个item表示成一个二维向量,两个向量的点积就是矩阵中user对item的打分。

推荐系统FM & FFM算法解读与实践「建议收藏」

任意的N\times N实对称矩阵都有N个线性无关的特征向量。并且这些特征向量都可以正交单位化而得到一组正交且模为1的向量。故实对称矩阵\vec{A}可被分解成:

\vec{A}=\vec{Q}\vec{\Lambda} \vec{Q}^{T}

其中\vec{Q}正交矩阵\vec{\Lambda}为实对角矩阵

类似地,所有二次项参数w_{ij}可以组成一个对称阵 \vec{W}(为了方便说明FM的由来,对角元素可以设置为正实数),那么这个矩阵就可以分解为 \vec{W}=\vec{V}^{T} \vec{V}, \vec{V}的第j列( v_{j})便是第j维特征(x_{j})的隐向量。换句话说,特征分量 x_{i}x_{j}的交叉项系数就等于x_{i}对应的隐向量与x_{j}对应的隐向量的内积,即每个参数w_{ij}=\left \langle v_{i}, v_{j}\right \rangle这就是FM模型的核心思想

为了求出w_{ij},我们需要求出特征分量x_{i}的辅助向量 v_{i}=\left ( v_{i1},...,v_{ik} \right )x_{j}的辅助向量v_{j}=\left ( v_{j1},...,v_{jk} \right ) , k表示隐向量长度(实际应用中k<<n),转换过程如下图所示:

\vec{W}=\vec{V}^{T}\vec{V}=\begin{bmatrix} \vec{V_{1}}\\ \vec{V_{2}}\\ ...\\ \vec{V_{n}} \end{bmatrix}\times \begin{bmatrix} \vec{V_{1}}& \vec{V_{2}} & ...& \vec{V_{n}} \end{bmatrix}=\begin{bmatrix} w_{11} &w_{12} &... &w_{1n} \\ w_{21} &w_{22} &... &w_{2n} \\ ...& ...&... &... \\ w_{n1}&w_{n2} &... &w_{nn} \end{bmatrix} \\=\begin{bmatrix} w_{11} &w_{12} &... &w_{1k} \\ w_{21} &w_{22} &... &w_{2k} \\ ...& ...&... &... \\ w_{n1}&w_{n2} &... &w_{nk} \end{bmatrix}\times \begin{bmatrix} w_{11} &w_{21} &... &w_{n1} \\ w_{12} &w_{22} &... &w_{n2} \\ ...& ...&... &... \\ w_{1k}&w_{2k} &... &w_{nk} \end{bmatrix}

 \vec{W}矩阵对角线上面的元素即为交叉项的参数。

FM的模型方程为(本文不讨论FM的高阶形式):

\hat{y}\left ( X \right ):=w_{0}+\sum_{i=1}^{n}w_{_i}x_{_i}+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n} \left \langle v_{i},v_{j} \right \rangle x_{i}x_{j}

\left \langle v_{i},v_{j} \right \rangle:=\sum_{f=1}^{k}v_{i,f}\cdot v_{j,f}

其中, v_{i}是第i维特征的隐向量,  \left \langle \cdot ,\cdot \right \rangle:代表向量点积。隐向量的长度为 k<<n,包含 k个描述特征的因子。根据公式,二次项的参数数量减少为 k\times n个,远少于多项式模型的参数数量。所有包含x_{i}的非零组合特征(存在某个j\neq i,使得 x_{i}x_{j}\neq 0)的样本都可以用来学习隐向量v_{i},这很大程度上避免了数据稀疏性造成的影响。

显而易见,上述是一个通用的拟合方程,可以采用不同的损失函数用于解决回归、二元分类等问题,比如可以采用MSE(Mean Square Error)损失函数来求解回归问题,也可以采用Hinge/Cross-Entropy 损失来求解分类问题。当然,在进行二元分类时,FM的输出需要经过sigmoid变换,这与Logistic回归是一样的。直观上看,FM的复杂度是 O(kn^{2})。但是,通过公式(3)的等式,FM的二次项可以化简,其复杂度可以优化到O(kn)。由此可见,FM可以在线性时间对新样本作出预测。

采用随机梯度下降法SGD求解参数

\frac{\partial \hat{y}(x)}{\partial x}=\left\{\begin{matrix} 1,\theta =w_{0}\\ x_{i},\theta =w_{i}\\ x_{i}\sum_{j=1}^{n} v_{i,f}x_{j} - v_{i,f}x_{i}^{2},\theta =v_{i,f} \end{matrix}\right.

由上式可知,v_{i,f}的训练只需要样本x_{i}的特征非0即可,适合于稀疏数据。

在使用SGD训练模型时,在每次迭代中,只需计算一次所有 f的 \sum_{j=1}^{n}v_{i,f}x_{j},就能够方便得到所有v_{i,f}的梯度,上述偏导结果求和公式中没有i,即与i无关,只与f有关,显然计算所有f\sum_{j=1}^{n}v_{i,f}x_{j}的复杂度是 O(kn),模型参数一共有 kn+n+1个。因此,FM参数训练的复杂度也是O(kn)。综上可知,FM可以在线性时间训练和预测,是一种非常高效的模型。

二、FFM原理

1. 特征组合为什么引入field?

同样以feed流推荐场景为例,我们多引入user维度用户年龄信息,其中性别和年龄同属于user维度特征,而tag属于item维度特征。在FM原理讲解中,“男性”与“篮球”、“男性”与“年龄”所起潜在作用是默认一样的,但实际上不一定。FM算法无法捕捉这个差异,因为它不区分更广泛类别field的概念,而会使用相同参数的点积来计算。

在FFM(Field-aware Factorization Machines )中每一维特征(feature)都归属于一个特定和field,field和feature是一对多的关系。如下表所示:

field user field(U) item field(I)
clicked userId userGender_男 userGender_女 userAge_[20.30] userAge_[30,40] itemTag_篮球 itemTag_化妆品
1 1 1 0 1 0 1 0
0 1 1 0 1 0 0 1
0 2 0 1 0 1 1 0
1 2 0 1 0 1 0 1

FFM模型认为v_{i}不仅跟x_{i}有关系,还跟与x_{i}相乘的x_{j}所属的Field有关系,即v_{i}成了一个二维向量v_{F\times K }K是隐向量长度,F是Field的总个数。设样本一共有n个特征, f个field,那么FFM的二次项有nf个隐向量。而在FM模型中,每一维特征的隐向量只有一个。FM可以看作FFM的特例,是把所有特征都归属到一个field时的FFM模型。 

y(X)=w_{0}+\sum_{i=1}^{n}w_{_i}x_{_i}+\sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left \langle V_{i,fj},V_{j,fi} \right \rangle x_{i}x_{j}

其中,f_{j}是第j的特征所属的字段。如果隐向量的长度为k,那么FFM的二次参数有nfk个,远多于FM模型的nk个。此外,由于隐向量与field相关,FFM二次项并不能够化简,时间复杂度是O\left ( kn^{2} \right )。 
需要注意的是由于FFM中的latent vector只需要学习特定的field,所以通常:

K_{FFM}<<K_{FM}

2. 如何组合特征?

还是以feed流场景为例,说明FFM是如何组合特征的。输入记录如下:

clicked

userId userGender(U) userAge(U) itemTag(I)
1 1 [20,30] 篮球

FM模型交叉项为:

 \o _{FM(V,x)} = <V_{man},V_{[20,30]} title=++">

而FFM模型特征交叉项为:

\o _{FFM(V,x)} = <V_{man},V_{[20,30]} title=++">

FFM在做latent vector的inner product的时候,必须考虑到其他特征所属的字段。例如

<V_{man},V_{[20,30]} title=">中男性和年龄[20,30]均为user field,所以不区分field;

<V_{man,I},V_{basket,U} title=">和<V_{basket,U},V_{[20,30,I]} title=">中男性、年龄[20,30]属于user field,而篮球属于item field,所以要考虑特征的latent vector。

三、xlearn实现

实现FM & FFM的最流行的python库有:LibFM、LibFFM、xlearn和tffm。其中,xLearn是一款高性能易于使用可扩展的机器学习软件包,包括FM和FFM模型,可用于大规模解决机器学习问题。xlearn比libfm和libffm库快得多,并为模型测试和调优提供了更好的功能。这里以xlearn实现FM和FFM算法。

1. FM实现

数据来自Kaggle预测泰坦尼克号的生存数据集,xlearn可以直接处理csv以及libsvm格式数据来实现FM算法,但对于FFM必须是libsvm格式数据。

1.1 python代码

import xlearn as xl

# 训练
fm_model = xl.create_fm()  # 使用xlearn自带的FM模型
fm_model.setTrain("./fm_train.txt")  # 训练数据

# 参数:
#  0. 二分类任务
#  1. learning rate: 0.2
#  2. lambda: 0.002
#  3. metric: accuracy
param = {'task':'binary', 'lr':0.2,
         'lambda':0.002, 'metric':'acc'}

# 使用交叉验证
fm_model.cv(param)
只听到从架构师办公室传来架构君的声音:
东风袅袅泛崇光,香雾空蒙月转廊。有谁来对上联或下联?

1.2 运行

[ ACTION     ] Start to train ...
[ ACTION     ] Cross-validation: 1/3:
[------------] Epoch      Train log_loss       Test log_loss       Test Accuarcy     Time cost (sec)
[   10%      ]     1            0.520567            0.519509            0.770270                0.00
[   20%      ]     2            0.462764            0.504741            0.787162                0.00
[   30%      ]     3            0.451524            0.499556            0.790541                0.00
[   40%      ]     4            0.446151            0.497348            0.787162                0.00
[   50%      ]     5            0.443402            0.494840            0.793919                0.00
[   60%      ]     6            0.440488            0.494532            0.793919                0.00
[   70%      ]     7            0.439055            0.493156            0.804054                0.00
[   80%      ]     8            0.438151            0.493404            0.800676                0.00
[   90%      ]     9            0.437012            0.492352            0.807432                0.00
[  100%      ]    10            0.436463            0.492059            0.804054                0.00
[ ACTION     ] Cross-validation: 2/3:
[------------] Epoch      Train log_loss       Test log_loss       Test Accuarcy     Time cost (sec)
[   10%      ]     1            0.529570            0.491618            0.798658                0.00
[   20%      ]     2            0.474390            0.477966            0.788591                0.00
[   30%      ]     3            0.461248            0.470482            0.785235                0.00
[   40%      ]     4            0.456666            0.469640            0.788591                0.00
[   50%      ]     5            0.452902            0.468955            0.788591                0.00
[   60%      ]     6            0.450912            0.467620            0.785235                0.00
[   70%      ]     7            0.449447            0.467692            0.785235                0.00
[   80%      ]     8            0.447781            0.466430            0.781879                0.01
[   90%      ]     9            0.447122            0.466931            0.785235                0.00
[  100%      ]    10            0.446272            0.466597            0.788591                0.00
[ ACTION     ] Cross-validation: 3/3:
[------------] Epoch      Train log_loss       Test log_loss       Test Accuarcy     Time cost (sec)
[   10%      ]     1            0.544947            0.470564            0.781145                0.00
[   20%      ]     2            0.491881            0.448169            0.794613                0.00
[   30%      ]     3            0.479801            0.442210            0.794613                0.00
[   40%      ]     4            0.475032            0.438578            0.804714                0.00
[   50%      ]     5            0.472111            0.436720            0.808081                0.00
[   60%      ]     6            0.470067            0.435224            0.811448                0.00
[   70%      ]     7            0.468599            0.434378            0.811448                0.00
[   80%      ]     8            0.466845            0.434049            0.811448                0.00
[   90%      ]     9            0.466121            0.433529            0.811448                0.00
[  100%      ]    10            0.465646            0.433083            0.814815                0.00
[------------] Average log_loss: 0.463913
[------------] Average Accuarcy: 0.802486
[ ACTION     ] Finish Cross-Validation
[ ACTION     ] Clear the xLearn environment ...
[------------] Total time cost: 0.04 (sec)

2. FFM实现

数据来自Criteo点击率预测挑战赛中CTR数据集的一个微小(1%)抽样,首先我们需要将其转换为xLearn所需的libffm格式以拟合模型。 

2.1 python代码

此代码由Java架构师必看网-架构君整理
import xlearn as xl # 训练 ffm_model = xl.create_ffm() # 使用FFM模型 ffm_model.setTrain("./FFM_train.txt") # 训练数据 ffm_model.setValidate("./FFM_test.txt") # 校验测试数据 # param: # 0. binary classification # 1. learning rate: 0.2 # 2. regular lambda: 0.002 # 3. evaluation metric: accuracy param = {'task':'binary', 'lr':0.2, 'lambda':0.002, 'metric':'acc'} # 开始训练 ffm_model.fit(param, './model.out') # 预测 ffm_model.setTest("./FFM_test.txt") # 测试数据 ffm_model.setSigmoid() # 归一化[0,1]之间 # 开始预测 ffm_model.predict("./model.out", "./output.txt")

2.2 运行

[ ACTION     ] Initialize model ...
[------------] Model size: 5.56 MB
[------------] Time cost for model initial: 0.01 (sec)
[ ACTION     ] Start to train ...
[------------] Epoch      Train log_loss       Test log_loss       Test Accuarcy     Time cost (sec)
[   10%      ]     1            0.600614            0.534322            0.770000                0.00
[   20%      ]     2            0.541555            0.536250            0.770000                0.00
[   30%      ]     3            0.521822            0.530098            0.770000                0.00
[   40%      ]     4            0.505286            0.537378            0.770000                0.00
[   50%      ]     5            0.492967            0.528159            0.770000                0.00
[   60%      ]     6            0.483819            0.533365            0.775000                0.00
[   70%      ]     7            0.472950            0.537750            0.770000                0.00
[   80%      ]     8            0.465698            0.531461            0.775000                0.00
[   90%      ]     9            0.457841            0.531676            0.770000                0.00
[  100%      ]    10            0.450092            0.531530            0.770000                0.00
[ ACTION     ] Early-stopping at epoch 8, best Accuarcy: 0.775000
[ ACTION     ] Start to save model ...
[------------] Model file: ./model.out
[------------] Time cost for saving model: 0.00 (sec)
[ ACTION     ] Finish training
[ ACTION     ] Clear the xLearn environment ...
[------------] Total time cost: 0.05 (sec)
----------------------------------------------------------------------------------------------
           _
          | |
     __  _| |     ___  __ _ _ __ _ __
     \ \/ / |    / _ \/ _` | '__| '_ \ 
      >  <| |___|  __/ (_| | |  | | | |
     /_/\_\_____/\___|\__,_|_|  |_| |_|

        xLearn   -- 0.36 Version --
----------------------------------------------------------------------------------------------

[------------] xLearn uses 4 threads for prediction task.
[ ACTION     ] Load model ...
[------------] Load model from ./model.out
[------------] Loss function: cross-entropy
[------------] Score function: ffm
[------------] Number of Feature: 9991
[------------] Number of K: 4
[------------] Number of field: 18
[------------] Time cost for loading model: 0.00 (sec)
[ ACTION     ] Read Problem ...
[------------] First check if the text file has been already converted to binary format.
[------------] Binary file (./FFM_test.txt.bin) found. Skip converting text to binary.
[------------] Time cost for reading problem: 0.00 (sec)
[ ACTION     ] Start to predict ...
[------------] The test loss is: 0.531461
[ ACTION     ] Clear the xLearn environment ...
[------------] Total time cost: 0.00 (sec)

参考资料

https://zhuanlan.zhihu.com/p/37963267

https://blog.csdn.net/hiwallace/article/details/81333604

https://blog.csdn.net/john_xyz/article/details/78933253

https://blog.csdn.net/tmb8z9vdm66wh68vx1/article/details/79091671

本文来源Mr_哲,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/209973
0

发表评论