机器学习 | 提升方法（三）

本周我们开始对于提升树的学习。

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

提升树模型

提升方法实际采用加法模型（即基函数的线性组合）与前向分布算法。以决策树为基函数的提升方法称为提升树（boosting tree）。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。提升树是迭代多棵回归树来共同决策。当采用平方误差损失函数时，每一棵回归树学习的是之前所有树的结论和残差，拟合得到一个当前的残差回归树，残差的意义如公式：残差 = 真实值 - 预测值 。提升树即是整个迭代过程生成的回归树的累加。提升树模型可以表示为决策树的加法模型 \[ f_M(x) = \sum^M_{m=1}T(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=argmin_{\Theta_m}\sum^N_{i=1}L(y_i,f_{m-1}(x_i)+T(x;\Theta_m)) \] 由于树的线性组合可以很好地拟合训练数据，即使数据中的输入与输出之间的关系很复杂也是如此，所以提升树是一个高功能的学习算法。下面来说明一下回归问题的提升树算法。

回归问题的提升树算法

输入：训练数据集\(T=\lbrace(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\rbrace\)；

输出：提升树\(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_{m=1}T(x;\Theta_m) \] 下面我们用一个例子来看看回归问题的提升树模型是如何学习的。

下表为训练数据， \(x\)的取值范围为区间 [ 0.5 , 10.5 ]，\(y\)的取值范围为区间 [ 5.0 , 10.0 ]，学习这个回归问题的提升树模型，考虑只用二叉树作为基函数：

\(x_i\)	1	2	3	4	5	6	7	8	9	10
\(y_i\)	5.56	5.70	5.91	6.40	6.80	7.05	8.90	8.70	9.00	9.05

第一步求\(f_1(x)\)即回归树\(T_1(x)\)。

首先通过以下优化问题：

捕获

求解训练数据的切分点\(s\)：

1

容易求得在\(R_1,R_2\)内部使平方误差达到最小值的\(c_1,c_2\)为

2

这里\(N_1,N_2\)是\(R_1,R_2\)的样本点数。

具体地，求解训练数据的切分点。根据所给数据，考虑如下切分点： \[ 1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5 \] 对各切分点，不难求出相应的\(R_1,R_2,c_1,c_2\)及

3

例如，当\(s=2.5\)时，

4

遍历所有的\(s\)，计算\(m(s)\)，结果列表如下：

\(s\)	1.5	2.5	3.5	4.5	5.5	6.5	7.5	8.5	9.5
\(m(s)\)	15.72	12.07	8.36	5.78	3.91	1.93	8.01	11.73	15.74

可知当\(s=6.5\)时\(m(s)\)达到最小值，此时：

5

所以回归树\(T_1(x)\)为

6

用\(f_(x)\)拟合训练数据的残差，表中\(r_{2i}=y_i-f_1(x_i)\)

\(x_i\)	1	2	3	4	5	6	7	8	9	10
\(r_{2i}\)	-0.68	-0.54	-0.33	0.16	0.56	0.81	-0.01	-0.21	0.09	0.14

平方损失误差为：

7

第二步求\(T_2(x)\)，方法与求\(T_1(x)\)一样，只是拟合的数据是上一步得到的残差，可以得到：

8

用\(f_2(x)\)拟合训练数据的平方损失误差是

9

继续迭代得到以下：

10

用\(f_6(x)\)拟合训练数据的平方损失误差是

11

假设此时已满足误差要求，那么\(f(x)=f_6(x)\)即为所求提升树。

以上就是今天的内容，谢谢大家的观看！