大家好,又见面了,我是你们的朋友全栈君。
在推荐系统和计算广告业务中,点击率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. 如何组合特征?
多项式模型是包含特征组合的最直观的模型。在多项式模型中,特征和的组合采用表示,即和都非零时,组合特征才有意义。从对比的角度,本文只讨论二阶多项式模型。模型的表达式如下:
其中, 代表样本的特征数量,是第个特征的值, 是模型参数。
从公式来看,模型前半部分就是普通的LR线性组合,后半部分的交叉项即特征的组合。单从模型表达能力上来看,FM的表达能力是强于LR的,至少不会比LR弱,当交叉项参数全为0时退化为普通的LR模型。
从上面公式可以看出,组合特征的参数一共有个,任意两个参数都是独立的。然而,在数据稀疏性普遍存在的实际应用场景中,二次项参数的训练是很困难的。其原因是:每个参数的训练需要大量和都非零的样本;由于样本数据本来就比较稀疏,满足和都非零的样本将会非常少。训练样本的不足,很容易导致参数不准确,最终将严重影响模型的性能。
3. 如何解决二次项参数的训练问题呢?
矩阵分解提供了一种解决思路。在model-based的协同过滤中,一个rating矩阵可以分解为user矩阵和item矩阵,每个user和item都可以采用一个隐向量表示。比如在下图中的例子中,我们把每个user表示成一个二维向量,同时把每个item表示成一个二维向量,两个向量的点积就是矩阵中user对item的打分。
任意的实对称矩阵都有个线性无关的特征向量。并且这些特征向量都可以正交单位化而得到一组正交且模为1的向量。故实对称矩阵可被分解成:
类似地,所有二次项参数可以组成一个对称阵 (为了方便说明FM的由来,对角元素可以设置为正实数),那么这个矩阵就可以分解为 , 的第列( )便是第维特征()的隐向量。换句话说,特征分量 和的交叉项系数就等于对应的隐向量与对应的隐向量的内积,即每个参数,这就是FM模型的核心思想。
为了求出,我们需要求出特征分量的辅助向量 , 的辅助向量 , 表示隐向量长度(实际应用中),转换过程如下图所示:
矩阵对角线上面的元素即为交叉项的参数。
FM的模型方程为(本文不讨论FM的高阶形式):
其中, 是第维特征的隐向量, 代表向量点积。隐向量的长度为 ,包含 个描述特征的因子。根据公式,二次项的参数数量减少为 个,远少于多项式模型的参数数量。所有包含的非零组合特征(存在某个,使得 )的样本都可以用来学习隐向量,这很大程度上避免了数据稀疏性造成的影响。
显而易见,上述是一个通用的拟合方程,可以采用不同的损失函数用于解决回归、二元分类等问题,比如可以采用MSE(Mean Square Error)损失函数来求解回归问题,也可以采用Hinge/Cross-Entropy 损失来求解分类问题。当然,在进行二元分类时,FM的输出需要经过sigmoid变换,这与Logistic回归是一样的。直观上看,FM的复杂度是 。但是,通过公式(3)的等式,FM的二次项可以化简,其复杂度可以优化到。由此可见,FM可以在线性时间对新样本作出预测。
采用随机梯度下降法SGD求解参数
由上式可知,的训练只需要样本的特征非0即可,适合于稀疏数据。
在使用SGD训练模型时,在每次迭代中,只需计算一次所有 的 ,就能够方便得到所有的梯度,上述偏导结果求和公式中没有,即与无关,只与有关,显然计算所有的的复杂度是 ,模型参数一共有 个。因此,FM参数训练的复杂度也是。综上可知,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模型认为不仅跟有关系,还跟与相乘的所属的Field有关系,即成了一个二维向量,是隐向量长度,是Field的总个数。设样本一共有个特征, 个field,那么FFM的二次项有个隐向量。而在FM模型中,每一维特征的隐向量只有一个。FM可以看作FFM的特例,是把所有特征都归属到一个field时的FFM模型。
其中,是第的特征所属的字段。如果隐向量的长度为,那么FFM的二次参数有个,远多于FM模型的个。此外,由于隐向量与field相关,FFM二次项并不能够化简,时间复杂度是。
需要注意的是由于FFM中的latent vector只需要学习特定的field,所以通常:
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账号...