推荐系统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模型交叉项为:

 

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代码

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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/131749.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 中国历年出生人口性别比统计_2000年男女比例

    中国历年出生人口性别比统计_2000年男女比例年份比例总数男女1976年出生50.92%20,491,79710,435,19610,056,6011977年出生50.86%17,931,1559,119,6858,811,4701978年出生50.5

  • 全局平均池化层替代全连接层(最大池化和平均池化的区别)

    最近看了两张图,我对第一张图有些不同的见解。首先全连接层和softmax层是不同的两个部分,其次计算参数时候可以理解为,假设最后一个卷积层是4个4*4的特征图,类别为4,则计算量为4*4*4*4。同样去理解GAP,为4*4,而这里与softmax还没有关系。下面是第二张图,GAP最早来源于NIN…

  • 从机械硬盘和固态硬盘的结构来看IO

    从机械硬盘和固态硬盘的结构来看IO“磁盘”这个词,对于程序员来说并不陌生,我们知道它是一种存储介质,主要用来存储数据的,可以说常用的中间件基本上都离不开它,比如我们常用的MySQL数据库、kafka消息引擎,甚至redis缓存都离不开磁盘。我们在优化某个业务逻辑的时候,经常需要用到缓存,尽量让热数据都从缓存里读取,因为我们知道磁盘是缓慢的,特别在高并发的场景下,我们要保证极少的请求走磁盘IO。不知道你有没有思考过以下问题: 机械硬盘为什么慢? 机械硬盘有多慢? kafka也是写磁盘的,它却挺快的,为什么?..

  • WinForm 界面美化

    WinForm 界面美化主界面的扁平化更改winform自带的MainForm窗体属性将主窗体FormBorderStyle更改为None,这样就得到了一个无边框的窗体调节背景色,找到自己喜欢的颜色,输入到BackColor属性中在主窗体的Mouse_Down中添加如下事件,实现窗体随意拖动:[DllImport(“user32.dll”)]publicstaticexternboolReleaseCapture();[DllImport(“user32.dll”)]publicstatic

  • 开心网外挂之争车位之发起比赛

    开心网外挂之争车位之发起比赛       publicvoidlalisai_KaiShiBiSai(stringid)       {           AccessHelperAH=newAccessHelper();           KaiXinHelperKH=newKaiXinHelper();           DataTabledt=AH.GetDataTable(“

  • 在线作图|在线做完整的Lefse分析

    在线作图|在线做完整的Lefse分析前言今天小编给大家介绍的是TUTU(https://www.cloudtutu.com/)网站上新添的Lefse分析,即LDAEffectSize分析。咱之前有上过这个分析(lefse),但是只能画出LDA值柱状图,今天新添的工具lefse2基本可以实现完整的分析内容,包括LDA值柱状图、物种分类分支图、组间丰度柱状图等等。Lefse分析文献应用举例:Fig.7ThemaintaxaofbacteriathatweredifferentinHMGvs.SMGvs.F

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号