传统机器学习算法复习：逻辑回归、因子分解机和梯度提升树

此时，二次项组合参数就可以被分解为：[ W=VV^T=begin{pmatrix} v1\ v2\ ...\ vn end{pmatrix}begin{pmatrix} v1^T ,v2^T, ..., vn^T end{pmatrix} ]将组合参数进行分解的优势：

• 从原先要求的(frac{n(n-1)}{2})个组合参数变成了求矩阵(V)，参数数量降低为(nk)，其中k一般远小于n
• 削弱高阶参数间的独立性。k越大，对特征分量的表征能力越强，高阶参数间独立性越强，模型越精细；k越小，模型泛化能力越强

在因子分解机中，每一维特征的隐向量只有一个，因此因子分解机可以看作是场感知因子分解机的特例，即因子分解机是把所有特征都归属到一个场时的场感知因子分解机。

• 场感知因子分解机的应用

场感知因子分解机可以自动做特征组合和处理高维稀疏特征，因此它在处理大量离散特征的问题上往往有比较好的效果。使用场感知因子分解机时要注意对连续特征做归一化或离散化。

因子分解机、场感知因子分解机和其它模型的对比关系：

• 因子分解机和场感知因子分解机。场感知因子分解机对因子分解机引入场的概念，增加了模型复杂度和模型的表达能力。
• 因子分解机和神经网络。神经网络难以直接处理高维稀疏的离散特征，因为这导致了神经元的连接参数太多，而因子分解机可以看作对高维稀疏特征的离散特征做嵌入。
• 因子分解机和梯度提升树。因子分解机与梯度提升树都可以做特征组合，当数据不是高度稀疏时，梯度提升树可以有效的学习到比较复杂的特征组合，但在高度稀疏的数据中，特征二阶组合就足以让绝大多数组合特征找不到样本。
• 因子分解机和其它模型。因子分解机是一种比较灵活的模型，通过合适的特征变换方式，因子分解机可以模拟二阶多项式核的支持向量机模型、MF模型、SVD++模型等。但SVD++与MF扩展性不如因子分解机，支持向量机核函数计算复杂度较高。(MF、SVD++均为矩阵分解模型，参见：推荐系统总结MF->PMF->CTR->CDL->CNN，矩阵分解之SVD和SVD++)
• DeepFM

因子分解机由于计算复杂度的限制，只用到了二阶特征组合。对于高阶特征组合，可以通过多层的神经网络即DNN解决。但对于稀疏高维特征，直接输入DNN中，将导致网络参数过多：


类似于场感知因子分解机的思想，将特征分为不同的“场”：


然后再加两层全连接层，那么就可以把特征组合出来了。但是这样，低阶特征和高阶特征的组合隐含地体现在隐层中，将低阶特征组合单独建模，然后融合高阶特征组合，能够更为充分的保留信息。也就是说，将DNN和因子分解机进行合理的融合：


这里有一个子问题：传统的机器学习算法和深度学习的结合。二者的融合总的来说有两种方式：一是并行结构，二是串行结构：



而DeepFM是并行结构的典型代表。

• DeepFM模型

对照上述的网络融合中的并行结构，DeepFM的模型结构：

DeepFM包含两个部分：神经网络和因子分解机，这两部分共享同样的输入。

• 神经网络

神经网络部分是一个前馈神经网络，可以学习高阶特征组合。注意：输入是高维稀疏数据，如onehot处理后的数据，因此需要引入embedding layer将输入向量压缩到低维稠密向量：

其中，(k)即是embedding size。这里神经网络做嵌入的过程，和因子分解机中二阶特征组合的过程是一致的，因此在因子分解机中得到的隐向量(v_{ij})现在作为了嵌入层的权重，参见[论文精读-DeepFM](https://blog.csdn.net/zynash2/article/details/79348540)。另外，尽管不同“场”的输入维度不同，经过嵌入后，向量长度均为(k)。

在嵌入层，因子分解机和神经网络的参数是共享的。因子分解机中的参数会参与到梯度下降中，可以理解为直接用神经网络做嵌入，无疑比因子分解机本身的嵌入能力更强。

共享嵌入带来两个好处：

• 从原始数据中同时学习到了低阶和高阶特征
• 不再需要特征工程。而Wide&Deep模型需要
• 因子分解机

和上述的因子分解机相同，可以观察到上图FM Layer中黑线表示的一阶特征组合，红线表示的二阶特征组合。

• 模型输出

DeepFM的预测结果由神经网络和因子分解机共同决定：[ y=sigmoid(y{FM}+y{DNN}) ]

另外，出现了DeepFM的升级版xDeepFM，参见：推荐系统遇上深度学习(二十二)--DeepFM升级版XDeepFM模型强势来袭！

本部分代码示例参见：CTR预估算法之FM, FFM, DeepFM及实践

DeepFM算法

梯度提升树(Gradient Boosting Decison Tree, GBDT)

梯度提升树是一种基于回归树的集成学习方法，通过构造多个弱的回归树作为基学习器，并将这些树的结果累加起来作为最终的预测输出。

• 前置知识
• 机器学习的大致流程就是确定模型集合；定义经验损失函数；利用给定的数据集({(xi,yi)})从模型集合中寻找最佳模型(一般就是寻找最佳的模型参数)。
• 决策树是一种模型，它的主要思想是将输入空间划分为不同的子区域，然后给每个子区域确定一个值，该子区域又称为树的叶子节点。如果是分类树，这个值就是类别；如果是回归树，这个值就是实数值，该值又称作叶子节点的权重值，分数等。
  [ f(x)=sum{j=1}^JcjI(xin R_j) ]
  其中，(f(x))是决策树表征的函数；(cj)是子区域对应的值；(J)为子区域的个数；(I)是指示函数，若(xin Rj)则(I(xin R_j)=1)，否则为0
• 加法模型
  [ h(x)=sum{m=1}^Mbetamf_m(x) ]
  (fm(x))称作基学习器；(betam)是基学习器的系数，一般假设大于0
• 梯度提升树中的决策树是回归树，不是分类树，也就是说，只有回归树才有所谓的梯度提升。
• 泰勒公式

二阶泰勒展开：[ f(x+Delta x)=f(x)+frac{partial f}{partial x}Delta x+frac{1}{2}frac{partial ^2f}{partial x^2}Delta x^2+o(Delta x) ]

示例：对(L(y,hm(x)+beta f(x)))进行一阶泰勒展开，令((y,hm(x)))为(x)，(beta f(x))为(Delta x)，则：[ L(y,hm(x)+beta f(x))approx L(y,hm(x))+beta f(x)frac{partial L(y,hm(x))}{partial hm(x)} ]

• 梯度提升树原理

梯度提升树是集成学习Boosting家族的一员，在训练时采用前向分步算法，首先确定第一棵树拟合的值，然后基于之前所有树的误差来更新并训练下一棵树，一步一步迭代下去直到梯度提升树构建完毕。

• 梯度提升树

简单起见，首先介绍与梯度提升树相近的提升树(

Boosting Tree)。

• 提升树算法(以回归问题为例)

输入：训练数据集(T={(x1,y1),(x2,y2),...,(xN,yN)},x_iin Xsubseteq mathbb{R}^n,yin Ysubseteq{R})

输出：提升树(f_M(x))

1.初始化(f_0(x)=0)1.对(m=1,2,...,M):

a. 计算残差：(r{mi}=yi-f{m-1}(xi),quad i=1,2,...,N)

其中，(f_{m-1}(x))为第(m-1)步时回归树加和的模型

b. 拟合残差(r{mi})学习一个回归树，获得(T(x;Thetam))

其中，(T(x;Theta_m))是第(m)步的训练获得的基学习器，通过*经验风险最小化*确定这棵树的参数：[ Thetam=mathop{argmin}sum{i=1}^NL(yi,f{m-1}(xi)+T(x;Thetam)) ]对于回归问题而言，(L(y,hat{y}))可采用平方损失误差

c. 更新(fm(x)=f{m-1}(x)+T(x;Theta_m))1.获得回归问题的提升树：[ fM(x)=sum{m=1}^MT(x;Theta_m) ]

在提升树中，每一棵树的生成采用的训练数据都是上次预测结果与真实值的残差，这个残差会不断减小。

这实际就是前置知识中

加法模型的典型应用。注意：由于这里基学习器是回归树，叶子节点的值是实数值，因此基学习器前的系数可省略。1.梯度提升树GBDT

梯度提升树的算法流程与提升树类似，只是不再使用残差作为一棵树的拟合目标，而是使用损失函数的梯度作为拟合目标。梯度提升算法利用最速下降法的近似方法，考虑经验损失函数：[ sum{i=1}^NL(yi,f{m-1}(xi)+beta f(x_i)) ]其中，(N)为样本数，(f{m-1}(xi))为第(m-1)步时所有树的累加，(beta)为基学习器的系数，(f(x_i))为本次要训练的树，即：[ f(x)=sum{j=1}^JcjI(xin R_j) ]简单起见，考虑一个样本，对损失函数进行一阶泰勒展开：[ L(yi,f{m-1}(xi)+beta f(xi))=L(yi,f{m-1}(xi))+beta f(xi)frac{partial L(yi,f{m-1}(xi))}{partial f{m-1}(x_i)} ]由于(beta)是大于0的，要使(L(yi,f{m-1}(xi)+beta f(xi))leq L(yi,f{m-1}(x_i)))，令[ f(xi)=-frac{partial L(yi,f{m-1}(xi))}{partial f{m-1}(xi)} ]每一个样本点上，上式尽可能成立的(f(x_i))就是我们本次要构建的树。

简言之，对损失函数(L(y,hat{y}))求关于(f(x))的偏导，然后带入(f_{m-1}(x))：[ r{mi}=-[frac{partial L(yi,f(xi))}{partial f(xi)}]{f(x)=f{m-1}(x)} ]就是每一步上，一棵树需要拟合的目标。

梯度提升树算法流程

输入：训练数据集(T={(x1,y1),(x2,y2),...,(xN,yN)},xiin X subseteq mathbb{R}^n,yiin Y subseteq mathbb{R})；损失函数(L(y,f(x)))

输出：回归树(hat{f(x)})

1.初始化[ f0(x)=mathop{argmin}csum{i=1}^NL(yi,c) ]1.对(m=1,2,...,M):a. 对(i=1,2,...,N)，计算[ r{mi}=-[frac{partial L(yi,f(xi))}{partial f(xi)}]{f(x)=f{m-1}(x)} ]

b. 对(r{mi})拟合一个回归树，得到第(m)棵树的叶节点区域(R{mj},j=1,2,...,J)

c. 对(j=1,2,...,J)，计算[ c{mj}=mathop{argmin}csum{xin R{mj}}L(yi,f{m-1}(x_i)+c) ]

d. 更新(fm(x)=f{m-1}(x)+sum{j=1}^Jc{mj}I(xin R_{mj}))1.获得回归树：[ hat{f(x)}=fM(x)=sum{m=1}^Msum{j=1}^Jc{mj}I(xin R_{mj}) ]

同样，梯度提升树的基学习器是回归树，加法模型中每个基学习器前的系数会内化到回归树内部，因此可省略。

注意到当使用(r_{mi})拟合出一个回归树后，2-c进一步使用整体损失函数对这棵回归树的值进行了优化。这就是”先局部，后整体“的思想，就是先通过逐步的局部优化获得一个结果，然后从全局的角度优化结果。决策树的生成和剪枝也是这样，先通过局部优化，如信息增益等指标选择特征，得出一个决策树；再从降低整体损失的角度，进行剪枝。

梯度提升树和提升树的关系：

提升树每一次提升都是用上次的预测结果和训练数据真实值的误差作为新的训练数据进行进一步学习，而梯度提升树把对误差的拟合替换为对损失函数梯度的拟合。提升树主要缺点有：在回归问题中，提升树的平方损失目标函数对于异常值特别敏感；对于一些损失函数，不易优化，如绝对值损失函数等。1.XGBoost

XGBoost是Boosting Tree的一种实现，相比于梯度提升树，XGBoost对损失函数进行了二阶泰勒展开，同时用到了一阶和二阶导数；并且引入了适用于树模型的正则化项用于控制模型的复杂度，正则化项包含树的叶子节点个数、叶子节点分数的(L_2)正则。

目标函数：[ Obj(Theta)=L(Theta)+Omega (Theta)\ Obj=sum{i=1}^nl(yi,hat{yi})+sum{k=1}^KOmega(f_k) ]可以看到，目标函数包含两个部分：训练误差和树的复杂度。其中，树的复杂度包括：a.树的深度；b.内部节点个数；c.叶子节点个数(T)；d.叶子节点分数(w)

和梯度提升树的思路一致，[ begin{split} Obj^{(t)}&=sum{i=1}^nl(yi,hat{y{i}}^{(t)})+Omega(ft(x))\ &=sum{i=1}^nl(yi,hat{y{i}}^{(t-1)}+ft(xi))+Omega(ft)+constant end{split} ]思考如何寻找一个(f_t)来优化这个目标函数。

这里和梯度提升树不同，XGBoost进行了二阶泰勒展开，令(x=(yi,hat{yi}^{(t-1)}),Delta x=ft(xi))：[ Obj^{(t)}approx sum{i=1}^n(l(yi,hat{yi}^{(t-1)})+gift(x)+frac{1}{2}hift^2(xi))+Omega(f_t)+constant ]其中，(gi​)为一阶导，(hi​)为二阶导[ gi=frac{partial l(yi,hat{y}^{(t-1)})}{partial hat{y}^{(t-1)}},\ hi=frac{partial ^2 l(yi,hat{y}^{(t-1)})}{{partial hat{y}^{(t-1)}}^2} ](l(yi,hat{yi}^{(t-1)}))为常数项；(ft(x)=W{q{(x)}})为决策树表征的函数，(win mathbb{R}^T)表示树的叶子权重，(q(x))表示树结构，这是上述对决策树(f(x)=sum{j=1}^JcjI(xin Rj))的另一种记法。

去除目标函数中的常数项：[ Obj=sum{i=1}^n(gift(xi)+frac{1}{2}hift^2(xi))+Omega(ft) ]

定义叶子(j)：[ Ij={i|q(xi)=j} ]表示第(j)个叶子中的样本，其中(q(xi))表示样本(xi)所属的叶节点[ begin{split} Obj^{(t-1)}&approx sum{i=1}^n(gift(xi)+frac{1}{2}hif^2t(xi))+Omega(ft)\ &=sum{i=1}^n(giw{q(xi)}+frac{1}{2}hiw^2{q(xi)})+gamma T+lambda frac{1}{2}sum{j=1}^Twj^2\ &=sum{j=1}^T((sum{iin Ij}gi)wj+frac{1}{2}(sum{iin Ij}hi+lambda)wj^2)+gamma T end{split} ]现在希望将(n)个样本组成的目标损失，转化为(T)个叶子节点的目标损失，令：[ Gj=sum{iin Ij}gi\ Hj=sum{iin Ij}hi ]目标损失变为：[ begin{split} Obj^{(t)}&=sum{j=1}^T((sum{iin Ij}gi)wj+frac{1}{2}(sum{iin Ij}hi+lambda)wj^2)+lambda T\ &=sum{j=1}^T(Gjwj+frac{1}{2}(Hj+lambda)wj^2)+lambda T end{split} ]求一个树结构下能够获得的目标函数的最小值

求目标函数关于(wj​)的偏导，并令该偏导(frac{partial Obj}{partial wj}=0​)，可得：[ wj^/*=-frac{Gj}{H_j+lambda} ]因此，对一个树结构而言，能够得到的目标函数的最小值：[ Obj^/*=-frac{1}{2}sum_{j=1}^Tfrac{G_j^2}{H_j+lambda}+gamma T ]其中，(Gj)为叶子节点(j)中样本的一阶导，(Hj)为叶子节点(j)中样本的二阶导，(T)为叶子节点数，(lambda)为正则化系数。

在所有可能的树结构中，(Obj^/*)越小，该树结构越好。因此，现在考虑如何寻找这个最优的树结构。


求最优树结构

最直白的方法就是列举所有的树结构，在其中选择(Obj^/)最小的作为最佳树结构，但是这实际是一个(NP)难问题。在实践中，通常使用树的精确贪婪学习*：

1. 贪婪：选分割点时，只考虑当前树结构到下一步树结构的loss变化，不考虑全局
2. 精确：当前层所有特征值中的所有可能，进行遍历，寻找最优分割点

类似于ID3的信息增益、C4.5的增益率、CART的基尼指数，定义XGBoost选择最优特征的准则：[ Gain=frac{GL^2}{HL^2+lambda}+frac{GR^2}{HR^2+lambda}-frac{(GL+GR)^2}{HL+HR+lambda}-gamma ]遍历所有的特征，计算

Gain值，选择最大的特征进行分割[ begin{split} &for k: 0to K: quad /# 对每个节点\ &quad for d:0to D:quad /# 对每个特征\ &qquad for n:0to N:quad /# 对每个实例\ &qquadquad 在0to N中，实例排序的时间复杂度为O(nlog(n)) end{split} ]因此，深度为(k)的树，总的时间复杂度为(O(ndklog(n)))

注意到，对于每个节点，也就是每一步构建子树时，寻找最佳分裂点有两层含义：a.寻找特征中最优的分裂值；b.寻找最优的特征

为了降低时间复杂度，可以采用一些近似算法：对于每个特征，只考虑分位点，

就是把一些样本捆绑在一起，形成

bin，这样就能降低最终要排序的样本数量。实际上，XGBoost不是简单的按照上图那样，按照样本个数进行分位，而是以二阶导数值作为权重：

之所以使用(h_i)加权，是因为目标函数可以被整理成下式：[ Obj=sum{i=1}^nfrac{1}{2}hi(ft(xi)-frac{gi}{hi})^2+Omega(f_t)+constant ]可以看到，(h_i​)对loss有加权的作用。

另外，观察XGBoost的最优特征准则：[ Gain=frac{GL^2}{HL^2+lambda}+frac{GR^2}{HR^2+lambda}-frac{(GL+GR)^2}{HL+HR+lambda}-gamma ]其中，等式右侧前半部分表示训练

loss的减少，(gamma)为

正则化。上式有可能是负的，也就是说，

loss的减少比正则化力度还要小时，分裂的增益会是负的。因此类似于

预剪枝和

后剪枝，有两种训练策略：

1. 提前停止：如果最佳分裂点是负的，那么提前停止分裂。这种策略过于贪婪，该分裂有可能有益于后面的分裂。
2. 后剪枝：将一棵树生成到它的最大深度，递归剪枝，剪去叶子节点分裂是负增益的。

XGBoost的其它特性：

1. 行抽样
2. 列抽样
3. 缩减学习率
4. 支持自定义损失函数。当然，该损失函数需要二阶可导
5. 增加了对稀疏数据的支持。在计算分裂增益时，只利用没有missing值的样本
6. 支持并行化。在分裂节点计算增益时，并行

XGBoost论文地址：XGBoost: A Scalable Tree Boosting System

XGBoost官网：XGBoost Documentation1.LightGBM

与XGBoost的不同：

• 直方图(Histogram)算法

把连续的浮点特征值离散化为k个整数，同时构造一个宽度为k的直方图。在遍历数据时，根据离散化后的值作为索引，在直方图中计算统计量。当遍历一次数据后，直方图计算了需要的统计量，然后根据直方图的离散值，遍历寻找最优分割点。

优势：减少了内存占用；减少了分裂点计算增益时的计算量

• 直方图加速

一个叶子的直方图可以由它的父节点的直方图与它的兄弟节点的直方图，做差而得，提升一倍速度。


• 建树方法

XGBoost是

Level-wise，LightGBM是

Leaf-wise


总而言之，LightGBM特性：

• 基于直方图的决策树算法
• 直方图差加速
• 带深度限制的Leaf-wise的叶子生长策略
• 直接支持类别特征(Categorical Feature)
• Cache命中率优化
• 基于直方图的稀疏特征优化
• 多线程优化

LightGBM论文地址：Lightgbm: A highly efficient gradient boosting decision tree

LightGBM官网：LightGBM Documentation