第一篇:提升树

提升树

  提升树(boosting tree)是以分类树或回归树作为弱学习器的强学习器。

  提升树模型用的是加法模型,算法用的是前向分步算法,弱学习器是决策树的集成学习方法。

提升树学习目标

  1. 加法模型
  2. 前向分步算法
  3. 提升树与AdaBoost算法
  4. 回归提升树流程
  5. 提升树优缺点

提升树引入

  假设Nick的年龄是25岁。

  1. 第1棵决策树

把Nick的年龄设置成初始值0岁去学习,如果第1棵决策树预测Nick的年龄是12岁,即残差值为$25-12=13$

  1. 第2课决策树
    1. 把Nick的年龄设置成残差值13岁去学习,如果第2棵决策树能把Nick分到13岁的叶子节点,累加两棵决策树的预测值加和$12+13=25$,就是Nick的真实年龄25岁
    2. 如果第2棵决策树的得到的是10岁,残差值为$25-12-10=3$
  2. 第3课决策树

把Nick的年龄设置成残差值3岁去学习……

  1. 继续重复上述过程学习,不断逼近Nick的真实年龄

提升树详解

加法模型

  提升树模型可以表示为决策树的加法模型
$$
fM(x)=\sum{i=1}^MT(x;\theta_m)
$$
其中$T(x;\theta_m)$表示决策树;$\theta_m$表示决策树的参数;$M$为树的个数。

前向分步算法

  提升树模型使用的是前向分布算法,即假设初始提升树$f_0(x)=0$,第$m$步的模型是
$$
fm(x)=f{m-1}(x)+T(x;\thetam)
$$
其中$f
{m-1}(x)$为当前模型,通过经验风险极小化确定一下课决策树的参数$\theta_m$
$$
\hat{\thetam}=\underbrace{arg\,min}{\thetam}\sum{i=1}^mL(yi,f{m-1}(x_i)+T(x_i;\theta_m))
$$

提升树与AdaBoost算法

  AdaBoost算法使用的是前向分步算法,利用前一轮弱学习器的误差率更新训练数据的权重;提升树使用的也是前向分步算法,但是提升树如其名,他的弱学习器只能使用决策树,一般使用CART树,然后他的迭代思路也与AdaBoost算法不同

  假设提升树在$t-1$轮的强学习器为$f{t-1}(x)$,目标函数是
$$
L(y,f
{m-1}(x))
$$
  在第$t$轮的目标则是找到一个弱学习器(决策树)$h_t(x)$,最小化第$t$轮的目标函数
$$
L(y,f_m(x))=L(yi,f{m-1}(x)+T(x;\theta_m))
$$
  但是当AdaBoost算法中的弱学习器为二类分类树的时候,其实AdaBoost就是提升树,即可以说分类提升树算法是AdaBoost算法的一种特殊情况。

回归提升树

  有$m$个数据$n$个特征的训练数据集$T={(x_,y_1),(x_2,y_2),\cdots,(x_m,y_m)}$,如果将输入空间划分为$k$互不相交的区域$R_1,R_2,\cdots,R_j$,并且在每个区域上确定输出的常量$cj$,决策树可以表示为
$$
T(x;\theta)=\sum
{j=1}^Jc_jI(x\in{R_j})
$$
其中,$\theta={(R_1,c_1),(R_2,c_2),\cdots,(R_J,c_J)}表示树的区域划分和各区域上的常数,$J$是回归树的叶节点个数。

前向分步算法

$$
\begin{align}
& f_0(x)=0 \
& f_1(x)=f_0(x)+T(x;\theta_1) \
& \cdots \
& fm(x)=f{m-1}(x)+T(x,\theta_m),m=1,2,\cdots,M \
& fM(x)=\sum{m=1}^MT(x;\theta_m)
\end{align}
$$
  在第$m$步$fm(x)=f{m-1}(x)+T(x,\thetam)$的时候,给定了$f{m-1}(x)$,需要求解第$m$棵的参数$\hat{\theta_m}$
$$
\hat{\thetam} = \underbrace{arg\,min}{\thetam}\sum{i=1}^mL(yi,f{m-1}(x_i)+T(x_i;\theta_m))
$$

平方误差损失函数

  对于第$m$棵树的参数$\hat{\thetam}$,可以采用平方误差损失函数$L(y,f(x))=(y-f(x))^2$求解,树的损失变为
$$
\begin{align}
L(y,f
{m-1}(x)+T(x;\thetam)) & = [y-f{m-1}(x)-T(x;\theta_m)]^2 \
& = [r-T(x;\thetam)]^2
\end{align}
$$
其中$r=y-f
{m-1}(x)$是当前模型拟合数据的残差。

  对于回归提升树,只需简单地拟合当前模型的残差。

回归提升树流程

输入

  有$m$个数据$n$个特征的训练数据集$T={(x_,y_1),(x_2,y_2),\cdots,(x_m,y_m)}$。

输出

  回归提升树$f_M(x)$。

流程

  1. 初始化$f_0(x)=0$
  2. 对$m=1,2,\cdots,M$
    1. 计算残差$r_{mi}=yi-f{m-1}(x_i),\quad{i=1,2,\cdots,m}$
    2. 拟合残差$r_{mi}$学习一个回归树,得到$T(x;\theta_m)$
    3. 更新$fm(x)=f{m-1}(x)+T(x;\theta_m)$
  3. 得到回归提升树
    $$
    fM(x)=\sum{i=1}^MT(x;\theta_m)
    $$

提升树优缺点

优点

  1. 既可以解决分类问题,又可以解决回归问题

缺点

  1. 弱学习器之间存在依赖关系,难以并行训练
  2. 提升树只是简单的拟合模型的残差,并不准确

小结

  提升树属于Boosting系列算法,他和AdaBoost有相似之处的,并且当AdaBoost算法中的弱学习器为二类分类树的时候,梯度提升树就是一种特殊的AdaBoost算法。

  由于提升树是由简单的残差计算得到的,所以在某种程度上来说,提升树是有一定缺陷的,为了解决这个问题,一般会采用梯度提升树来弥补。

上一篇
下一篇
Copyright © 2022 Egon的技术星球 egonlin.com 版权所有 帮助IT小伙伴学到真正的技术