机器学习 学习笔记（18） 提升树

提升树是以分类树或回归树为基本分类器的提升方法，提升树被认为是统计学习中性能最好的方法之一。

提升方法实际采用加法模型（即基函数的线性组合）与前向分步算法。以决策树为基函数的提升方法称为提升树（boosting tree）。对分类问题决策树时二叉分类树，对回归问题是二叉回归树。提升树模型可以表示为决策树的加法模型：

f_M(x)=\sum_{m=1}^MT(x;\Theta _m)

，其中

T(x;\Theta _m)

表示决策树，

\Theta _m

为决策树的参数，M个树的个数。

提升树算法采用前向分步算法，首先确定初始提升树

f_0(x)=0

，第m步的模型是

f_m(x)=f_{m-1}(x)+T(x;\Theta _m)

其中

f_{m-1}(x)

为当前模型，通过经验风险极小化确定下一颗决策树的参数

\Theta _m

，

\hat{\Theta }_m=\arg \min \limits_{\Theta _m} L(y_i,f_{m-1}(x_i)+T(x_i;\Theta _m))

由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。

下面叙述回归问题的提升树。

一直一个训练数据集

T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}

，

\chi

为输入空间，Y为输出空间。如果将输入空间

\chi

划分为J个互不相交的区域

R_1,R_2,...,R_J

，并且在每个区域上确定输出的常量

c_j

，那么树可以表示为：

T(x;\Theta )=\sum_{j=1}^Jc_j\mathbb{I}(x\in R_j)

，其中参数

\Theta =\{(R_1,c_1),(R_2,c_2),...,(R_J,c_J)\}

表示树的区域划分和各区域上的常数，J是回归树的复杂度即叶结点个数。

回归问题的提升树使用以下前向分步算法：

f_0(x)=0

f_m(x)=f_{m-1}(x)+T(x;\Theta _m),m=1,2,...,M

f_M(x)=\sum_{m=1}^MT(x;\Theta _m)

在前向分步算法的第m步，给定当前模型

f_{m-1}(x)

，需求解

\hat{\Theta }_m=\arg \min \limits_{\Theta _m}\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\Theta _m))

得到

\hat{\Theta }_m

，即第m棵树的参数。

当采用平方误差损失函数时，

L(y,f(x))=(y-f(x))^2

，其损失变为

L(y,f_{m-1}(x)+T(x;\Theta _m))=[y-f_{m-1}(x)-T(x;\Theta _m)]^2=[r-T(x;\Theta _m)]^2

这里

r=y-f_{m-1}(x)

是当前模型拟合数据的残差，所说义，对回归问题提升树算法来说，只需简单地拟合当前模型的残差。

回归问题提升树算法描述如下：

输入：训练数据集

T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}

输出：提升树

f_M(x)

（1）初始化

f_0(x)=0

（2）对m=1,2,...,M

        (a)计算残差

r_{mi}=y_i-f_{m-1}(x_i),i=1,2,...,N

        (b)拟合残差

r_{mi}

学习一个回归树，得到

T(x;\Theta _m)

        (c)更新

f_m(x)=f_{m-1}(x)+T(x;\Theta _m)

（3）得到回归问题提升树

f_M(x)=\sum_{m=1}^MT(x;\Theta _m)

提升树利用加法模型和前向分步算法实现学习的优化过程，当损失函数是平方损失和指数损失函数时，每一步优化使很简单的，但对一般损失函数而言，往往每一步优化并不那么容易，针对这一问题，梯度提升（gradient boosting）算法被提出，这是利用最速下降的近似方法，其关键是利用损失函数的负梯度在当前模型的值

-[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}

作为回归问题提升树算法中的残差的近似值，拟合一个回归树。

梯度提升算法描述如下：

输入：训练数据集

T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}

，损失函数

L(y,f(x))

输出：回归树

\hat{f}(x)

（1）初始化

f_0(x)=\arg \min \limits_{c} \sum_{i=1}^NL(y_i,c)

（2）对m=1,2,...,M

   （a）对i=1,2,...,N，计算

r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}

   （b）对

r_{mi}

拟合一个回归树，得到第m棵树的叶结点区域

R_{mj},j=1,2,...,J

   （c）对j=1,2,...,J，计算

c_{mj}=\arg \min \limits_{c} \sum_{x_i\in R_{mj}} L(y_i,f_{m-1}(x_i)+c)

   （d）更新

f_m(x)=f_{m-1}(x)+\sum_{j=1}^Jc_{mj}\mathbb{I}(x\in R_{mj})

（3）得到回归树

\hat{f}(x)=f_M(x)=\sum_{m=1}^M\sum_{j=1}^J c_{mj}\mathbb{I}(x\in R_{mj})

算法第一步初始化，估计使损失函数极小化的常数值，它是一个只有一个根节点的树。第二步（a）步计算损失函数的负梯度在当前模型的值，将它作为残差的估计，对于平方损失函数，它就是所说的残差；对于一般损失函数，它就是残差的近似值，（b）步估计回归树叶结点区域，以拟合残差的近似值，（c）步利用线性搜索估计叶结点区域的值，使损失函数极小化。（d）更新回归树。第三步得到输出的最终模型

\hat{f}(x)

Gradient boosting Decision Tree(GBDT)

GB算法中最典型的基学习器是决策树，尤其是CART，正如名字的含义，GBDT是GB和DT的结合。要注意的是这里的决策树是回归树，GBDT中的决策树是个弱模型，深度较小一般不会超过5，叶子节点的数量也不会超过10，对于生成的每棵决策树乘上比较小的缩减系数（学习率<0.1），有些GBDT的实现加入了随机抽样（subsample 0.5<=f <=0.8）提高模型的泛化能力。通过交叉验证的方法选择最优的参数。因此GBDT实际的核心问题变成怎么基于

\{(x_i, r_{im})\}_{i=1}^n

使用CART回归树生成

\! h_m(x)

？

　　CART分类树在很多书籍和资料中介绍比较多，但是再次强调GDBT中使用的是回归树。作为对比，先说分类树，我们知道CART是二叉树，CART分类树在每次分枝时，是穷举每一个feature的每一个阈值，根据GINI系数找到使不纯性降低最大的的feature以及其阀值，然后按照feature<=阈值，和feature>阈值分成的两个分枝，每个分支包含符合分支条件的样本。用同样方法继续分枝直到该分支下的所有样本都属于统一类别，或达到预设的终止条件，若最终叶子节点中的类别不唯一，则以多数人的类别作为该叶子节点的性别。回归树总体流程也是类似，不过在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是GINI系数，而是最小化均方差--即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和 除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

Xgboost

　　Xgboost是GB算法的高效实现，xgboost中的基学习器除了可以是CART（gbtree）也可以是线性分类器（gblinear）。下面所有的内容来自原始paper，包括公式。

　　(1). xgboost在目标函数中显示的加上了正则化项，基学习为CART时，正则化项与树的叶子节点的数量T和叶子节点的值有关。

　　(2). GB中使用Loss Function对f(x)的一阶导数计算出伪残差用于学习生成fm(x)，xgboost不仅使用到了一阶导数，还使用二阶导数。

　　　　第t次的loss：

　　　　对上式做二阶泰勒展开：g为一阶导数，h为二阶导数

　　(3). 上面提到CART回归树中寻找最佳分割点的衡量标准是最小化均方差，xgboost寻找分割点的标准是最大化，lamda，gama与正则化项相关

 　　xgboost算法的步骤和GB基本相同，都是首先初始化为一个常数，gb是根据一阶导数ri，xgboost是根据一阶导数gi和二阶导数hi，迭代生成基学习器，相加更新学习器。

xgboost与gdbt除了上述三点的不同，xgboost在实现时还做了许多优化：

• 在寻找最佳分割点时，考虑传统的枚举每个特征的所有可能分割点的贪心法效率太低，xgboost实现了一种近似的算法。大致的思想是根据百分位法列举几个可能成为分割点的候选者，然后从候选者中根据上面求分割点的公式计算找出最佳的分割点。
• xgboost考虑了训练数据为稀疏值的情况，可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率，paper提到50倍。
• 特征列排序后以块的形式存储在内存中，在迭代中可以重复使用；虽然boosting算法迭代必须串行，但是在处理每个特征列时可以做到并行。
• 按照特征列方式存储能优化寻找最佳的分割点，但是当以行计算梯度数据时会导致内存的不连续访问，严重时会导致cache miss，降低算法效率。paper中提到，可先将数据收集到线程内部的buffer，然后再计算，提高算法的效率。
• xgboost 还考虑了当数据量比较大，内存不够时怎么有效的使用磁盘，主要是结合多线程、数据压缩、分片的方法，尽可能的提高算法的效率。

gbdt 无论用于分类还是回归一直都是使用的CART 回归树

参考

1. 《统计学习方法》
2. https://www.cnblogs.com/wxquare/p/5541414.html
3. GBDT详解
4. 机器学习算法GBDT的面试要点总结-上篇