网站营销设计,免费域名申请 tk,公司名字查询,雄安免费网站建设公司在推荐系统和计算广告业务中#xff0c;点击率CTR#xff08;click-through rate#xff09;和转化率CVR#xff08;conversion rate#xff09;是衡量流量转化的两个关键指标。准确的估计CTR、CVR对于提高流量的价值#xff0c;增加广告及电商收入有重要的指导作用。业界… 在推荐系统和计算广告业务中点击率CTRclick-through rate和转化率CVRconversion rate是衡量流量转化的两个关键指标。准确的估计CTR、CVR对于提高流量的价值增加广告及电商收入有重要的指导作用。业界常用的方法有人工特征工程 LRLogistic Regression、GBDTGradient Boosting Decision Tree LR、FM模型。在这些模型中FM近年来表现突出分别在由Criteo和Avazu举办的CTR预测竞赛中夺得冠军。 因子分解机Factorization Machine, FM是由Steffen Rendle提出的一种基于矩阵分解的机器学习算法其主要用于解决数据稀疏的业务场景如推荐业务特征怎样组合的问题。
paper指出FM与SVM相比有如下优势
FM可以实现非常稀疏数据参数估计而SVM会效果很差因为训出的SVM模型会面临较高的biasFMs拥有线性的复杂度, 可以通过 primal 来优化而不依赖于像SVM的支持向量机
一、FM原理
1. 为什么进行特征组合
在feed流推荐场景中根据user和item基础信息clicked是否点击userId用户IDuserGender用户性别itemTag物品类别来预测用户是否对物品感兴趣点击与否二分类问题。源数据如下 clicked userIduserGenderitemTag11男篮球01男化妆品02女篮球12女化妆品由于userGender和itemTag特征都是categorical类型的需要经过独热编码One-Hot Encoding转换成数值型特征。
clickeduserIduserGender_男userGender_女itemTag_篮球itemTag_化妆品111010011001020110120101经过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的高阶形式 其中 是第维特征的隐向量 代表向量点积。隐向量的长度为 包含 个描述特征的因子。根据公式二次项的参数数量减少为 个远少于多项式模型的参数数量。所有包含的非零组合特征存在某个使得 的样本都可以用来学习隐向量这很大程度上避免了数据稀疏性造成的影响。
显而易见上述是一个通用的拟合方程可以采用不同的损失函数用于解决回归、二元分类等问题比如可以采用MSEMean 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的概念而会使用相同参数的点积来计算。
在FFMField-aware Factorization Machines 中每一维特征feature都归属于一个特定和fieldfield和feature是一对多的关系。如下表所示
fielduser field(U)item field(I)clickeduserIduserGender_男userGender_女userAge_[20.30]userAge_[30,40]itemTag_篮球itemTag_化妆品11101010011010010201011012010101FFM模型认为不仅跟有关系还跟与相乘的所属的Field有关系即成了一个二维向量是隐向量长度是Field的总个数。设样本一共有个特征, 个field那么FFM的二次项有个隐向量。而在FM模型中每一维特征的隐向量只有一个。FM可以看作FFM的特例是把所有特征都归属到一个field时的FFM模型。 其中是第的特征所属的字段。如果隐向量的长度为那么FFM的二次参数有个远多于FM模型的个。此外由于隐向量与field相关FFM二次项并不能够化简时间复杂度是。 需要注意的是由于FFM中的latent vector只需要学习特定的field所以通常 2. 如何组合特征
还是以feed流场景为例说明FFM是如何组合特征的。输入记录如下 clicked userIduserGender(U)userAge(U)itemTag(I)11男[20,30]篮球FM模型交叉项为 而FFM模型特征交叉项为 FFM在做latent vector的inner product的时候必须考虑到其他特征所属的字段。例如
中男性和年龄[20,30]均为user field所以不区分field
和中男性、年龄[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: accuracyparam {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: accuracyparam {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
