机器学习笔记17——集成学习系列——集成/提升（Boosting）方法原理以及系列算法

1、概述

$\quad \quad$Boosting是一种用来提高弱分类算法准确度的方法（集成学习方法），通过反复修改训练数据的权值分布，构建一系列基本分类器（弱分类器），并将这些基本分类器线性组合，构成一个强分类器。包括Adaboost算法、提升树、GBDT算法。

• 强学习器：根据得到的弱学习机和相应的权重给出假设（最大程度上符号实际情况）根据天气以往的预测表现及实际天气情况做出综合准确的天气预测

• 弱学习器：对一定分布的训练样本可以给出假设（仅仅好于随机猜测）例如根据天空有云彩，推测可能会下雨

2、原理

??对于提升方法来说，原理出发点关键在于两点：

• 一是在每一轮如何改变训练数据的权值或概率分布；
• 二是如何将弱分类器组合成一个强分类器。

比如:
1）提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样本的权值，使误分的样本在后续受到更多的关注。

2）加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。

??Boosting的算法原理我们可以用一张图做一个概括如下：

$\quad \quad$从图中可以看出，Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.，如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。

$\quad \quad$总的来说，提升方法使用加法模型和前向分步算法。

2.1 加法模型

$f\left(x\right)=\sum_{m=1}^M\beta_m b\left(x;\gamma_m\right) \tag{1.1}$
其中， $b\left(x;\gamma_m\right)$为基函数， $\gamma_m$为基函数的参数， $\beta_m$为基函数的系数。

??在给定训练数据 $\{\left(x_i,y_i\right)\}_{i=1}^N$及损失函数 $L\left(y,f\left(x\right)\right)$的条件下，学习加法模型 $f\left(x\right)$成为经验风险极小化问题：
$\min_{\beta_m,\gamma_m}\sum_{i=1}^N L\left(y_i,\sum_{m=1}^M\beta_m b\left(x_i;\gamma_m\right)\right)\tag{1.2}$

??前向分步算法求解这一优化问题的思路：因为学习的是加法模型，可以从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式（1.2），则可以简化优化复杂度。具体地，每步只需优化如下损失函数：
$\min_{\beta,\gamma}\sum_{i=1}^N L\left(y_i,\beta b\left(x_i;\gamma\right)\right)\tag{1.3}$

2.2 前向分布算法

算法1.1 前向分步算法
输入：训练数据集 $T=\{\left(x_1,y_1\right),\left(x_2,y_2\right),\dots,\left(x_N,y_N\right)\}$； 损失函数 $L\left(y,f\left(x\right)\right)$；基函数集合 $\{b\left(x;\gamma\right)\}$；
输出：加法模型 $f\left(x\right)$
（1）初始化 $f_0\left(x\right)=0$
（2）对 $m=1,2,\dots,M$
（a）极小化损失函数
$\left(\beta_m,\gamma_m\right)=\mathop{\arg\min}_{\beta,\gamma} \sum_{i=1}^N L\left(y_i, f_{m-1}\left(x_i\right)+\beta b\left(x_i;\gamma\right)\right) \tag{1.4}$
得到参数 $\beta_m$， $\gamma_m$
（b）更新
$f_m\left(x\right)=f_{m-1}\left(x\right)+\beta_m b\left(x;\gamma_m\right) \tag{1.5}$
（3）得到加法模型
$f\left(x\right)=f_M\left(x\right)=\sum_{m=1}^M\beta_m b\left(x;\gamma_m\right) \tag{1.6}$

??前向分步算法将同时求解从 $m=1$到 $M$所有参数 $\beta_m,\gamma_m$的优化问题简化为逐次求解各个 $\beta_m, \gamma_m$的优化问题。

3、系列算法

3.1 AdaBoost 算法

参考资料：
李航《统计学习方法》