提升方法

提升方法是一种提升模型准确度的方法。在分类问题中，通过改变样本训练权重，着重关注预测错误的数据，数据给多个分类器学习，再对其进行线性组合，使得预测准确率高的分类器有更高的权重。

接下来主要介绍 AdaBoost 算法。

AdaBoost 算法

基本思路

弱可学习：一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随即猜测略好，那么就称这个概念是弱可学习的。

强可学习：一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率很高，那么就称这个概念是强可学习的。

一个概念是强可学习的充要条件是其为弱可学习。原因是可以集成学习，具体的证明可以找一找，这里就不证明了。

AdaBoost 算法

输入：训练数据集 $T = {(x_1,y_1),…,(X_N,y_N)}$,其中 $x_i \in X,y \in Y = {-1,1}$, 弱学习算法
输出:最终分类器$G(x)$

• 初始化训练数据的权值分布:
  $$D_1 = (w_{11},…,w_{1N}),w_{1i} = \frac{1}{N}$$
• 对 $m = 1,…,N$
• • 使用具有权值分布 $D_m$ 的训练数据集学习,得到基本分类器
    $$G_m(x):X \rightarrow {-1,1}$$
• • 计算 $G_m(x)$ 在训练数据集上的分类误差率
    $$e_m = \sum P( G_m(x_i) \ne y_i ) = \displaystyle \sum_{i=1}^N w_{mi} I(G_m(x_i) \ne y_i)$$
• • 计算 $G_m(x)$ 的系数
    $$\alpha_m = \frac{1}{2}log\frac{1-e_m}{e_m}$$
• • 更新训练数据集的权值分布
    $$\begin{aligned}
    D_{m+1} = (w_{m+1,1},…,w_{m+1,N}) \\
    w_{m+1,i} = \frac{w_{m,i}}{Z_m}exp(-\alpha_m y_i G_m(x_i)) \\
    Z_m = \sum w_{m,i} exp(-\alpha_m y_i G_m(x_i)) 目的是为了让 D_{m+1} 成为概率分布
    \end{aligned}$$
• 构建基本分类器的线性组合
  $$f(x) = \sum \alpha_m G_m(x)$$
  得到最终分类器:
  $$G(x) = sign(f(x)) = sign(\sum \alpha_m G_m(x))$$

AdaBoost 算法的解释

可认为 AdaBoost 算法是模型为假发模型,损失函数为指数函数,学习算法为前向分布算法时的二类分类学习方法

前向分布算法

考虑加法模型:

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

其中,$b(x;\gamma_m)$ 为基函数,$\gamma_m$ 为基函数的系数

在给定训练数据及损失函数 $L(y,f(x))$ 的条件下,学习加法模型$f(x)$成为经验风险极小化即损失函数极小化问题:

$$\underset{\beta_m,\gamma_m}{min}\displaystyle \sum_{i=1}^N L(y_i, \displaystyle \sum_{m=1}^M \beta_m b(x_i;\gamma_m)) $$

前向分布算法求解这一优化问题的想法是:因为学习的是加法模型,如果能从前向后,每一步都只学习一个基函数及其系数,逐步逼近优化目标函数式,那么就可以简化优化的复杂度.

具体的,每步只需优化如下损失函数:

$$\underset{\beta, \gamma}{min} \displaystyle \sum_{i=1}^N L(y_i,\beta b(x_i;\gamma_m))$$

算法整体如下:

输入:训练数据集 $T = {(x_1,y_1),…,(x_N,y_N)}$;损失函数$L(y,f(x))$;基函数集${b(x;y)}$

输出:加法模型$f(x)$

• 初始化 $f_0(x) = 0$
• 对 $m = 1,…,M$
• • 极小化损失函数
    $$(\beta_m,\gamma_m) = arg \underset{\beta, \gamma}{min} \displaystyle \sum_{i=1}^N L(y_i,f_{m-1}(x_i) + \beta b(x_i;\gamma_m))$$
• • 更新
    $$f_m(x) = f_{m-1}(x) + \beta_m b(x;y_m)$$
• 得到加法模型
  $$f(x) = f_M(x) = \sum \beta_m b(x;\gamma_m)$$

前向分布算法与 AdaBoost

AdaBoost 算法是前向分布算法的特例,此时模型是由基本分类器组成的加法模型,损失函数是指数函数

提升树

提示树是以分类树活回归树为基本分类器的提升方法。

提升树模型

提升方法实际采用加法模型与前向分布算法.以决策树为基函数的提升方法称为提升树

提升树算法

提升树算法采用前向分布算法.首先确定初始提升树$f_0(x) = 0$,第 m 步模型为
$$f_m(x) = f_{m_1}(x) + T(x;\Theta_m)$$

其中$f_{m_1}(x)$为当前步的模型,通过经验风险极小化确定下一课决策树的参数$\Theta_m$:
$$\Theta_m = arg \underset{\Theta_m}{min}\displaystyle \sum_{i=1}^N L(y_i,f_{m-1}(x_i) + T(x_i;\Theta_m))$$

对于回归树的提升树算法如下:

输入:训练数据集 $T = {(x_1,y_1),…,(x_N,y_N)}$

输出:提升树$f_m(x)$

• 初始化 $f_0(x) = 0$
• 对 $m = 1,..,M$
• • 计算残差：
    $$r_{mi} = y_i - f_{m-1}(x_i)$$
• • 拟合残差 $r_{mi}$ 学习一个回归树,得到$T(x;\Theta_m)$
• • 更新 $f_m(x) = f_{m-1}(x) + T(x;\Theta_m)$
• 得到回归问题提升树
  $$f_M(x) = \sum T(x;\Theta_m)$$

梯度提升算法

提升树利用加法模型与前向分布算法实现学习的优化过程,当损失函数是平方损失和指数损失函数的时候,每一步的优化比较简单,但对一般损失函数而言,每一步的优化不是那么容易.

于是,梯度提升算法出现,使用了最速下降法的近似方法.其关键是利用损失函数的负梯度在当前模型的值:

$$-[\frac{\delta L(y,f(x_i))}{\delta f(x_i)}]{f(x) = f{m-1}(x)}$$

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

算法如下:

输入:训练数据集$T={(x_1,y_1),…,(x_N,y_N)}$

输出:回归树$f(x)$

• 初始化
  $$f_0(x) = arg \underset{c}{min} \sum L(y_i,c)$$
• 对$m = 1,…,M$
• • 对 $i = 1,…,N$,计算
    $$r_{mi} = - [\frac{\delta L(y_i,f(x_i))}{\delta f(x_i)}]{f(x) = f{m-1}(x)}$$
• • 对$r_{mi}$拟合一个回归树,得到第 m 棵树的叶结点区域 $R_{mj}$
• • 对 $j = 1,..,J$,计算
    $$c_mj = arg min \displaystyle \sum_{x_i \in R_{mj}} L(y_i,f_{m-1}(x_i)+c)$$
• • 更新 $f_m(x) = f_{m-1}(x) + \sum c_{mj}I(x \in R_mj)$
• 得到回归树