[人工智能]集成学习 Task06 Boosting

前言

一、Boosting的基本思路

“强可学习"和"弱可学习”

在概率近似正确PAC学习的框架下：
弱学习：识别错误率小于1/2（即准确率仅比随机猜测略高的学习算法）
强学习：识别准确率很高并能在多项式时间内完成的学习算法

非常有趣的是，在PAC 学习的框架下，强可学习和弱可学习是等价的，也就是说一个概念是强可学习的充分必要条件是这个概念是弱可学习的。

弱可学习算法提升至强可学习算法

二、Adaboost算法

1.Adaboost的基本原理

对于Boosting方法来说，有两个问题需要给出答案：第一个是每一轮学习应该如何改变数据的概率分布，第二个是如何将各个弱分类器组合起来。

对于Adaboost来说，解决上述的两个问题的方式是：1. 提高那些被前一轮分类器错误分类的样本的权重，而降低那些被正确分类的样本的权重。这样一来，那些在上一轮分类器中没有得到正确分类的样本，由于其权重的增大而在后一轮的训练中“备受关注”。
2. 各个弱分类器的组合是通过采取加权多数表决的方式，具体来说，加大分类错误率低的弱分类器的权重，因为这些分类器能更好地完成分类任务，而减小分类错误率较大的弱分类器的权重，使其在表决中起较小的作用。

三、 前向分步算法

1. 加法模型

在Adaboost模型中，我们把每个基本分类器合成一个复杂分类器的方法是每个基本分类器的加权和，即：$f(x)={\sum }_{m=1}^M{\beta }_{m}b\left(x;{\gamma }_m\right)$

2. 前向分步算法

给定数据集 T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , ? ? , ( x N , y N ) } T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\} T={(x1?,y1?),(x2?,y2?),?,(xN?,yN?)}，$x_i\in \mathcal{X}?{\mathbf{R}}^n$， y i ∈ Y = { + 1 , ? 1 } y_{i} \in \mathcal{Y}=\{+1,-1\} yi?∈Y={+1,?1}。损失函数$L(y,f(x))$，基函数集合 { b ( x ; γ ) } \{b(x ; \gamma)\} {b(x;γ)}，我们需要输出加法模型$f(x)$。

• 初始化：$f_0(x)=0$
• 对m = 1,2,…,M:
  • (a) 极小化损失函数：
    $$\left({\beta }_m,{\gamma }_m\right)=\arg \underset{\beta ,\gamma }{\min }\sum _{i=1}^{N}L\left(y_i,f_{m?1}\left(x_i\right)+\beta b\left(x_i;\gamma \right)\right)$$
    得到参数${\beta }_m$与${\gamma }_m$
  • (b) 更新：
    $$f_m(x)=f_{m?1}(x)+{\beta }_{m}b\left(x;{\gamma }_m\right)$$
• 得到加法模型：
  $$f(x)=f_M(x)=\sum _{m=1}^M{\beta }_{m}b\left(x;{\gamma }_m\right)$$

这样，前向分步算法将同时求解从m=1到M的所有参数${\beta }_m$，${\gamma }_m$的优化问题简化为逐次求解各个${\beta }_m$，${\gamma }_m$的问题。

Adaboost算法是前向分步算法的特例，Adaboost算法是由基本分类器组成的加法模型，损失函数为指数损失函数。

四、梯度提升决策树(GBDT)

先学到这里，未完待续