梯度提升树

GBDT主要由三个概念组成：Regression Decistion Tree（即DT)，Gradient Boosting（即GB)，Shrinkage（算法的一个重要演进分枝，目前大部分源码都按该版本实现）。搞定这三个概念后就能明白GBDT是如何工作的，要继续理解它如何用于搜索排序则需要额外理解RankNet概念，之后便功德圆满。下文将逐个碎片介绍，最终把整张图拼出来。

加法模型

对于算法模型而言，一个性能弱的算法模型可能很难得到很好的效果，加法模型的思想是将性能较弱的模型通过加权得到一个性能较强的模型。形如

$$f(x)=\sum_{m=1}^{M}\beta_m b(x;\gamma_m)\tag{1}$$

其中$b(x;y_m)$表示基函数，$\gamma_m$表示基函数系数，$\beta_m$表示基函数系数。

前向分布算法

在给定训练集的情况下以及损失函数$L(y,f(x))$的条件下，学习加法模型$f(x)$即为最小化损失函数的问题：

$$\min\limits_{\beta_m,\gamma_m}\sum_{i=1}^N L(y_i,\sum_{m=1}^M\beta_mb(x_i;\gamma_m))\tag{2}$$

前向分步算法的思想：加法模型是不同模型的组合，因此从前向后每次学习一个基函数和基函数系数来逐步优化目标函数$(1)$,从而降低复杂度。

计算流程：

(1).初始化第一个基函数$f_0(x)$

(2)对于$m=1,2,3,…,M$，极小化损失函数

$$(\beta_m,\gamma_m)=\arg \min\limits_{\beta,\gamma}+\beta_mb(x;\gamma_m)\tag{3}$$

得到参数$\beta_m,\gamma_m$

(3) 更新加法模型

$$f_m(x)=f_{m-1}(x)+\beta_mb(x;\gamma_m)\tag{4}$$

(4)得到加法模型

$$f(x)=\sum_{i=1}^M\beta_mb(x;\gamma_m)\tag{5}$$

GBDT梯度提升模型

提升树算法

提升方法可以总结为加法模型与前向分布算法，以决策树为基函数的模型成为提升树，无论是分类问题还是回归问题，都是基于回归树(这点和统计学系方法里面不一样)，提升树算法则是采用前向分步算法来更新加法模型。对于提升树，基函数变为决策树，所以加法模型为

$$f_m(x)=\sum_{i=1}^MT(x;w_m)\tag{6}$$

其中$M$为决策树的个数，$w$为决策树的参数，$T$表示决策树。

初始化第一棵决策树，第$m$部的模型为

$$f_m(x)=f_{m-1}(x)+T(x;w)\tag{7}$$

通过最小化损失函数确定下一棵决策树的参数$w_m$

$$\arg\min\limits_{w_m}\sum_{i=1}^NL(y_i,f_{m-1}+T(x_i,w_m))$$

当采用平方误差时

$$L(y,f(x))=(y-f(x))^2\tag{8}$$

损失函数变为

$$L(y)=(y-f_{m-1}(x)-T(x;w_m))^2$$ $$=[r-T(x;w_m)]^2\tag{9}$$

其中残差$r=y-f_{m-1}(x)$，所以最后的目的就是为了是$T(x;w_m)$的值更加接近残差，从而达到最小化损失函数的作用。

回归问题提升树

1.计算出第一颗树第一棵提升树

$$f_0(x)=\arg \min\limits\sum_{i=1}^NL(y_i,c)\tag{10}$$

2.得到提升树的残差

$$r_{mi}=y_i-f_{m-1}(x_i), i=1,2,3....,N\tag{11}$$

3.通过拟合残茶学习回归树，得到$T_m(x;w_m)$

4.更新提升树

$$f_m(x)=f_{m-1}(x)+T(x;w_m)\tag{12}$$

梯度提升

梯度提升本质其实是利用梯度下降算法来对前向分步算法进行优化求解的方法。其关键是利用损失函数负梯度在当前模型的值作为残差的近似值，进行一个拟合。

$$r_{mi}=-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x_i)=f_m(x_i) }\tag{13}$$

利用负梯度代替残差的原因是因为只有在损失函数为平方差的时候，梯度才等于残差，但是当损失函数比较复杂的时候，此时梯度是不等于残差的。

对于特征的选择和回归树一样，同样是遍历所有特征找到最佳切分点。

回归例子可以参见统计学习方法。

GBDT用于分类和回归的区别

前面主要将的是GBDT的思想，利用残差不断的拟合，直到最后接近目标。但是对于对于分类和回归任务的处理，主要有以下几个方面不一样。

特征选择

1、分裂节点的评价标准不同

对于回归类问题，分裂节点的时候主要评价方式为

(1)平方误差

$$L(x,c)=min \sum_{i=1}^m\sum_{j\in R_i}(x_j-c_i)^2$$

将特征划分为m个不同的区域$R_i$，然后求出每个区域的平方误差求和，平方误差和最小的特征和切分点。

(2)绝地值误差

$$L(x,c)=min \sum_{i=1}^m\sum_{j\in R_i}|x_j-c_i|$$

(3)friedman_mse：费尔德曼均方误差，改进后的均方误差，一般能够达到比较好的效果

对于分类问题，其节点分类的评价方式为

(1)信息熵(entropy)

$$H(x)=-\sum_{i=1}^np_i\log p_i$$

(2)gini,基尼系数(信息增益)

$$g(D,A)=H(D)-H(D|A)$$

详细计算过程见统计学习方法。

损失函数

在介绍分类的原理之前首先要了解一下对数损失函数

$$L(y,P(Y|X))=log P(Y|X)\tag{14}$$

对于分类任务，GBDT是结合回归加分类模型计算每种分类的概率，对于二分类，采用的是logistic进行分类

$$P(Y=1|X)=\frac{1}{1+exp(-\sum_{i=1}^Mf_i(x))}\tag{15}$$ $$P(Y=0|X)=\frac{1}{1+exp(\sum_{i=1}^Mf_i(x))}\tag{16}$$

令$h_\theta(x)=\frac{1}{1+exp(-\sum_{i=1}^Mf_i(x))}$

所以有

$$P(Y=1|X)=h_\theta(x)\tag{17}$$ $$P(Y=0|X)=1-h_\theta(x)\tag{18}$$ $$P(Y|X)=h_\theta(x)^{y_i}(1-h_\theta(x))^{1-y_i}$$

损失函数为

$$J_\theta(x)=-\sum_{i=1}^N [y_ilogh_\theta(x)+(1-y_i)log(1-h_\theta(x))]\tag{19}$$

所以经过计算有

$$\frac{\partial J}{\partial h_\theta(x)}=y-\hat y$$

对于多分类问题

损失函数为交叉熵

$$L(y,p(y|x))=-\sum_{i=1}^M y_ilog {p_i}\tag{20}$$

其中$i$表示所属类别，$M$表示分类树,$p_i$表示属于$i$的概率

并且有

$$p(y=i|x)=\frac{exp(F_i(x))}{\sum_{i=1}^Mexp(F_i(x))}\tag{21}$$

同样求梯度有

$$r_{mi}=-\frac{\partial L(y_i,F(x_i))}{\partial F(x_i)}|_{f(x_i)=f_{m-1}(x_i)}$$

回归损失函数

(1)平方损失函数

$$L(y,x)=\sum_{i=1}^n(y_i-f(x_i))^2$$

(2)绝对值损失函数

$$L(y,x)=\sum_{i=1}^n|y_i-f(x_i)|$$

(3)huber损失函数

$$L(y)=\left\{ \begin{array}{rcl} \frac{1}{2}(y-f(x))^2 & & {|y-f(x)|\leq\delta}\\ \delta*|y-f(x)-\frac{1}{2}\delta| & & {|y-f(x)|>\delta} \end{array} \right.$$

GBDT的正则化

和Adaboost一样，我们也需要对GBDT进行正则化，防止过拟合。GBDT的正则化主要有三种方式。

（1）第一种是和Adaboost类似的正则化项，即步长（learning rate）。定义为ν,对于前面的弱学习器的迭代 $f_k(x)=f_{k-1}(x)+h_k(x)$ 如果我们加上了正则化项，则有 $f_k(x)=f_{k-1}(x)+v\cdot h_k(x)$ ν的取值范围为0<ν≤10。对于同样的训练集学习效果，较小的ν意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

（2）第二种正则化的方式是通过子采样比例（subsample）。取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。

使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。（注：这一点没明白。。）

（3）第三种是对于弱学习器即CART回归树进行正则化剪枝。在决策树章节里我们已经讲过，这里就不重复了。

调参经验

分类

sklearn.ensemble.`RandomForestClassifier

Parameters

• n_estimators ：树的个数，迭代次数

  The number of trees in the forest.Changed in version 0.22: The default value of n_estimators changed from 10 to 100 in 0.22.

• criterion： 叶子结点分裂的方式，默认的是gini和entropy

• max_depth：树的深度，默认为空，会一直分裂，直到无法继续分裂

• min_samples_split： 分裂一个节点所需要的最小样本

  • int：表示样本数
  • float 表示的百分比

• min_samples_leaf：保持一颗叶子结点所需要的样本数，该参数能够对模型进行平滑，特别在回归任务中。int和float和min_samples_split一样。

• min_weight_fraction_leaf：叶子结点所有权重和的最小值，如果分布相差很大或者有很多缺失值，可以引入该参数

• max_features：当考虑最佳分割点是考虑的特征数。

  • 如果是float型，表示的是百分比
  • 如果是’auto’ or ‘log2’，表示sqrt(n_features)
  • 如果是log2, 表示log2(n_features)

• max_leaf_nodes : 最大叶子结点，用于防止过拟合

• min_impurity_split：早停的阈值，如果一个节点的不纯度高于该值，则分裂，否则为叶子结点

  Threshold for early stopping in tree growth. A node will split if its impurity is above the threshold, otherwise it is a leaf.Deprecated since version 0.19: min_impurity_split has been deprecated in favor of min_impurity_decrease in 0.19. The default value of min_impurity_split will change from 1e-7 to 0 in 0.23 and it will be removed in 0.25. Use min_impurity_decrease instead.

• bootstrap： 是否使用bootstrap采样，为否表示使用整个数据集

• oob_score：袋外精度来泛化

  Whether to use out-of-bag samples to estimate the generalization accuracy.

• class_weight：类别权重，用于样本分布不均衡时使用

  • ‘’dict, list of dicts, “balanced”, “balanced_subsample” or None, optional (default=None）
  • 格式为{class_label: weight} ，例如 {0: 1, 1: 1}
  • ’balanced‘模式下会自动调整权值，根据训练数据中类别出现频率， n_samples/(n_class *np.bincount())
  • ‘balanced_subsample’和balanced一样，区别在于才用的boostrap

• max_samples：从训练集中取出的每个样本量

  • None：表示使用所有样本
  • 如果为int 表示为该值
  • float表示 百分比

class sklearn.ensemble.``GradientBoostingRegressor

• loss ：损失函数，默认为ls

  • ‘ls’ 平方损失函数，损失函数为$L(y)=(y-f(x))^2$

  • ‘lad’，绝对值 ,损失函数 $L(y)=|y-f(x)|$

  • ‘huber’： 两者的结合

    $$L(y)=\left\{ \begin{array}{rcl} \frac{1}{2}(y-f(x))^2 & & {|y-f(x)|\leq\delta}\\ \delta*|y-f(x)-\frac{1}{2}\delta| & & {|y-f(x)|>\delta} \end{array} \right.$$

• subsample：子采样比例，子采样会减少方差，增大偏差

• criterion： 衡量节点分裂质量的指标

  • friedman_mse,
  • ‘mse’
  • ’mae‘

New in version 0.18.

• min_samples_split: 和分类一样

• tol：学习率

参考资料

[1]https://zhuanlan.zhihu.com/p/86281279

[2].统计学习方法