关于Boosting算法

Boosting意为提升或增强，是一类应用广泛且非常有效的统计学习（statistical learning）方法，属于集成学习(Ensembling)算法。其基本思想非常简单，就是要将影响结果的多个因素综合考虑。而最终结果可以表示为各个因素分别乘以他们影响结果的权重之和。换句话讲，即单个因素无法决定结果，或者说影响结果有限，但多个因素综合起来，便可以有效地决定结果。

可以认为，单个因素就是一个弱的分类器，多个因素综合考虑便是一个强分类器。，通俗来讲“三个臭皮匠顶个诸葛亮”。Boost的核心过程也就是由弱学习算法转变为强学习算法的过程。

背景知识

在机器学习领域，Boosting算法是一种通用的学习算法，这一算法可以提升任意给定的学习算法的性能。其思想源于1984年Valiant提出的”可能近似正确”-PAC(Probably Approximately Correct)学习模型，在PAC模型中定义了两个概念-强学习算法和弱学习算法。其概念是: 如果一个学习算法通过学习一组样本，识别率很高，则称其为强学习算法;如果识别率仅比随机猜测略高，其猜测准确率大于50，则称其为弱学习算法。

Boosting表达

Boosting是一个加法过程，它是由若干个基函数及其权值乘积之和的累加。可以使用数学表示如下：

$$ f(x)= \beta_1·w_1 + \beta_2·w_2+ \dots + \beta_n·w_n $$ 即：

\begin{equation} f(x)= \sum_{k=1}^{n} \beta_k·w_k \end{equation}

其中，$w$ 是 $x$ 的函数，有时也称为基函数，而 $\beta$ 则是基函数的系数。

Boosting算法思路

  1. 知难而退：对于一个学习问题来说（以分类问题为例），假如给定训练数据集，求一个弱学习算法要比求一个强学习算法要容易的多。

  2. 弱弱得强:Boosting方法就是从弱学习算法出发，反复学习，得到一系列弱分类器，然后组合弱分类器，得到一个强分类器。强分类器一般是弱分类器的线性组合

  3. 抓主要矛盾：Boosting方法在学习过程中通过改变训练数据的权值分布，针对不同的数据分布调用弱学习算法得到一系列弱分类器。在分类问题中，通常会减小一轮中分类正确训练数据权值，增大前一轮中分类错误训练数据权值，使得分类器更加注重误分类数据。

AdaBoost算法

Boosting学习算法拥有众多算法，其中最著名的有3个，分别是：

  • Adaboost(Adaptive Boosting) 自适应提升

  • GBDT(Gradient Boost Decision Tree) 梯度上升决策树

  • XGBoost（eXtreme Gradient Boost）

    AdaBoost来龙去脉

    接下来重点介绍AdaBoosting算法： 1995年，Freund and Schapire改进了Boosting算法，取名为Adaboost算法，该算法不需要提前知道所有关于弱学习算法的先验知识，同时运算效率与Freund在1991年提出的Boosting算法几乎相同。Adaboost即Adaptive Boosting，它能

  • 自适应的调整弱学习算法的错误率，经过若干次迭代后错误率能达到预期的效果。

  • 它不需要精确知道样本空间分布，在每次弱学习后调整样本空间分布，更新所有训练样本的权重，把样本空间中被正确分类的样本权重降低，被错误分类的样本权重将会提高，这样下次弱学习时就更能更关注这些被错误分类的样本。该算法可以很容易地应用到实际问题中，因此，已成为目前最流行的Boosting算法。 AdaBoost算法的核心思想是针对同一个训练集训练出不同的分类器（弱分类器），然后把这些弱分类器集合起来，构成一个性能更加强大的分类器（强分类器）

AdaBoost详细算法

假设有训练数据集 X: $$ X = \{ (x_1,y_1),(x_2,y_2),\dots,(x_i,y_i),\dots,(x_N,y_N) \} , x_i\in R^N, y_i\in\{-1,1\} $$ 通过弱分类器构建强分类器（模型） $G(x)$

(1). 初始化权值w分布，即$W_m,m=1$时：

$$ W_1 = (w_{11} , w_{12},\dots,w_{1i} ,\dots w_{1n} ), 其中 i=1,2,\dots, N. $$

其中首次权重都是相等的，可表示为 $ w_{ 1i }= \frac{ 1 }{ N } $

(2). 当 $W_m,m=1,2,3,4,\dots，M$时,

  • 在使用权重$W_m$基础上来训练数据集，以分类误差率最小化为目标，得到模型$G_{m}(x)$。

  • 计算$G_{m}(x)$在训练数据集上的分类误差率

$$ e_m =P(G_{m}(x_i)\neq y_i) $$

  • 计算$G_{m}(x)$系数

$$ \alpha_m = \frac{ 1 }{ 2 } log{\frac{ 1-e_m }{ e_m }} = \frac{ 1 }{ 2 } log{(\frac{ 1 }{ e_m }-1)}$$ 这是个递减函数，当分类错误率越低，那么对应的分类器最终占得权重系数越大。

  • 更新分类器权重 $$W_{m+1,i} = \frac{ 1 }{ Z_m } * (W_{mi} * exp(-\alpha_m y_i G_m(x_i))),其中 i=1,2,\dots, N. $$

其中$Z_m$是规范化因子，它使得$W_{m+1}$是一个概率分布。

$$Z_m = \sum_{i=1}^{N}(W_{mi} * exp(-\alpha_m y_i G_m(x_i))) $$

(3). 构建分类器的线性组合

$$f(x)=\sum_{m=1}^{M} \alpha_m G_m(x)$$

因此，

$$G(x) = sign(f(x)) = sign\Big(\sum_{m=1}^{M} \alpha_m G_m(x)\Big)$$

总结

  • python生态中，scikit-learn对Adaboost做了较好的实现。

  • 如果地震前兆信号能够和地震事件对应起来，那么该算法会有很好的表现。