推荐算法学习（十）：CTR预估算法

CTR预估问题是竞价广告核心问题之一。针对CTR预估样本数量大，LR模型学习能力有限，人工特征工程成本高等问题，提出了GBDT+LR、Wide & Deep等算法，能够自动发现有效的特征及特征组合，弥补人工经验不足，得到更好的预估结果。

CTR模型回顾

（1）对输入进行特征编码

在推荐系统，个性化信息检索中，需要对用户行为进行预测，比如用户的行为特征[weekday=Tuesday, Gender=Male, City=London]，需要通过OneHot编码进行转换 => 高维稀疏特征，然后进行Concatenate。

（2）模型选择

LR模型：，W为权重，X为特征，b为偏差。

Poly2模型（Degree-2 Polynomial）：，LR模型可解释性强，但是需要人工交叉特征，Poly2在LR的基础上考虑特征自动交叉。

FM模型：Poly2可以自动交叉特征，但是当特征维度高且稀疏时，权重W很难收敛，FM模型通过MF完成了二阶特征交叉的矩阵补全。

FFM模型：考虑了特征所属的Field场。

FNN模型：CTR中大部分特征是离散、高维且稀疏的，需要embedding后才能进行深度学习，使用FM对embedding层进行初始化，即每个特征对应一个偏置项${w_i}$和一个k维向量${y_i}$。FNN实际上是wide & deep模型中的deep模型。

GBDT+LR算法

GBDT+LR出自Facebook经典CTR预估论文（Practical Lessons from Predicting Clicks on Ads at Facebook,2014 ），是一种具有stacking思想的二分类器模型，GBDT+LR通过GBDT将特征进行组合，然后传给线性分类器，LR对GBDT产生的输入数据进行分类。

Gradient Boosting Decision Tree

GBDT（梯度提升决策树）是一种常用的非线性模型，基于集成学习中的boosting思想。GBDT由多棵CART回归树组成，将累加所有树的结果作为最终结果。GBDT拟合的目标是一个梯度值（连续值，实数），所以在GBDT里，都是回归树。GBDT可用来做回归预测，调整后也可以用于分类。

CART（分类与回归树）

CART树是二叉树，不像多叉树那样形成过多的数据碎片，CART决策树算法是一种分类及回归树算法。若目标变量是离散变量，则是Classification Tree，分类树是使用树结构算法将数据分成离散类的方法，其采用基尼系数的大小度量特征各个划分点的优劣；若目标是连续变量，则是Regression Tree，回归树使用平方误差最小准则。作为分类决策树时，待预测样本落至某一叶子节点，则输出该叶子节点中所有样本所属类别最多的那一类（即叶子节点中的样本可能不是属于同一个类别，则多数为主）；作为回归决策树时，待预测样本落至某一叶子节点，则输出该叶子节点中所有样本的均值。

CART算法由以下两步组成：（1）决策树生成，基于训练数据集生成决策树，生成的决策树要尽量大；（2）决策树剪枝，用验证集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝标准。

梯度迭代 Gradient Boosting

Boosting（迭代），即通过迭代多棵树来共同决策。损失函数用于评价模型性能（一般为拟合程度+正则项）。最好的方法就是让损失函数沿着梯度方向下降。Gradient Boosting，每一次建立模型是在之前模型损失函数的梯度下降方向。

GBDT是将所有树的结果累加起来，最为最终的结果为每一棵树学的是之前所有树结果和的残差。例如，A的真实年龄是24岁，第一棵树预测出来18岁，残差为6 => 第二棵树将A的年龄设置为6，继续学习，第二棵树预测出来是5，残差为1 => 第三棵树将残差1作为预测目标

GBDT在每一轮迭代中，先计算出当前模型在所有样本上的负梯度，然后以该值为目标训练一个新的弱分类器进行拟合并计算出该弱分类器的权重，最终实现对模型的更新。第t次迭代后的函数 = 第t-1次迭代后的函数 + 第t次迭代函数的增量：

拟合负梯度，最终结果为每次迭代增量的累加，$f_0(x)$为初始值:

使用GBDT进行新特征构造

当GBDT训练好做预测的时候，输出的并不是最终的二分类概率值，而是要把模型中的每棵树计算得到的预测概率值所属的叶子结点位置记为1 ，从而构造新的训练数据。

GBDT是一堆树的组合，假设有k棵树(T1,T2…Tk)，每棵树的节点数分别为$N_i$, GBDT会输出一个维的由0,1构成的向量$x_{gbdt}$.

GBDT+LR

使用GBDT+LR，相比单纯的LR和GBDT，在Loss上减少了3%，提升作用明显。前500棵决策树，会让NE（Normalized Cross-Entropy，）下降，而后1000棵决策树对NE下降不明显，不超过0.1%。实验中，boosting tree数量从1到2000，叶节点个数被限制为最大12个。所有特征的重要度总和是1，TOP10个特征，贡献了50%的重要程度，而后面300个特征，贡献了1%的重要度。大量弱特征的累积也很重要，不能都去掉。但如去掉部分不重要的特征，对模型的影响比较小。

常见评价指标有：（1）NE，Normalized Cross-Entropy，（2）Calibration，预估CTR除以真实CTR，即预测的点击数与真实点击数的比值。数值越接近1，预测效果越好，（3）AUC，衡量排序质量的良好指标，但是无法进行校准，也就是如果我们希望得到预估准确的比值，而不是最优的排序结果，那么需要使用NE或者Calibration（ROC曲线，横轴是FPRate，纵轴是TPRate，AUC=ROC曲线下的面积）。

*集成学习方法（RF与GBDT的区别）

Boosting，通过将弱学习器提升为强学习器的集成方法来提高预测精度（如AdaBoost，GBDT）
Bagging，通过自助采样的方法生成众多并行式的分类器，通过“少数服从多数”的原则来确定最终的结果（如Random Forest）

Wide & Deep算法

推荐系统的挑战是 memorization与generalization。memorization（记忆能力），学习items或者features之间的相关频率，在历史数据中探索相关性的可行性；generalization（泛化/推理能力），基于相关性的传递，去探索一些在过去没有出现过的特征组合。Google于2016 年提出的Wide & Deep模型核心思想是结合线性模型的记忆能力和 DNN 模型的泛化能力，在训练过程中同时优化 2 个模型的参数，从而达到整体模型的预测能力最优。

Wide推荐，系统通过获得用户的购物日志数据，包括用户点击哪些商品，购买过哪些商品，然后通过OneHot编码转换为离散特征，好处是可解释性强，不足在于特征组合需要人为操作。

wide模型是线性模型，输入特征可以是连续特征，也可以是稀疏的离散特征。离散特征通过交叉可以组成更高维的离散特征。一个有d个特征的样本，模型的参数，线性回归，实际中往往需要交叉特征，第k个特征交叉为，最终的wide模型：

Deep推荐，通过深度学习出一些向量，这些向量是隐性特征，往往没有可解释性的。

Deep模型使用的特征包括连续特征和Embedding后的离散特征，使用前馈网络模型，特征首先转换为低维稠密向量，作为第一个隐藏层的输入，解决维度爆炸问题。根据最终的loss反向训练更新。向量进行随机初始化，隐藏层的激活函数通常使用ReLU：

Wide join Deep，融合模型的方法有：（1）ensemble，两个模型分别对全量数据进行预测，然后根据权重组合最终的预测结果；（2）joint training，wide和deep的特征合一，构成一个模型进行预测。

Wide & Deep模型：，其中$\phi(x)$代表X的Cross Product Transformation,$W_{wide}$代表Wide模型的权重向量，$W_{deep}$代表Deep模型的权重向量，${\alpha}^{(lf)}$代表最终的神经网络数结果，b为偏差。Wide & Deep模型不论在线下还是线上相比于单独的Wide模型和单独的Deep模型，效果都有明显提升。

NFM算法

FNN, Wide & Deep, DeepFM都是在DNN部分，对embedding之后的特征进行concatenate，没有充分进行特征交叉计算。NFM算法是对embedding直接采用对位相乘（element-wise）后相加起来作为交叉特征，然后通过DNN直接将特征压缩，最后concatenate linear部分和deep部分的特征。

DeepFM和NFM都是FM和DNN的结合，但DeepFM是并行结构，FM和DNN分开计算；而NFM是串行架构，将FM的结果作为DNN的输入。

对于输入X的预测公式：

Embedding层：全连接层，将稀疏输入映射到一个密集向量，得到

BI层: 池化操作，将一系列的Embedding向量转换为一个向量

隐藏层：神经网络的全连接层

预测层：将隐藏层输出到n*1的全连接层，得到预测结果

FM 通过隐向量完成特征组合工作，同时解决了稀疏的问题。但是 FM 对于 non-linear 和 higher-order 特征交叉能力不足，因此可以使用FM和DNN来弥补这个不足，如NFM模型。NFM的BI层，将每个特征embedding进行两两做元素积， BI层的输出是一个 k维向量（隐向量的大小），BI层负责了二阶特征组合可以将FM看成是NFM模型 Hidden Layer层数为0的一种特殊情况。

实例：使用Wide&Deep模型对movielens进行评分预测

数据集：movielens
进行数据准备（数据读取，特征标签编码，计算每个特征不同特征值个数，训练测试数据集切分）；使用deepctr工具中的Wide&Deep模型进行训练；使用Wide&Deep进行预测并计算RMSE/MSE

代码：https://github.com/Alice1214/RS/tree/master/RS08/wide%26deep