提升算法 AdaBoost 算法

作者: shenghaishxt | 来源:发表于2019-03-11 15:05 被阅读0次

提升方法
Adaboost
Adaboost算法
提升算法 AdaBoost 算法
集成算法整理
第8章 Adaboost算法
Adaboost算法简介
GBDT集成算法（梯度提升树）
提升算法之Adaboost算法
AdaBoost（Adaptive Boosting）

本文来自我的个人博客 https://www.zhangshenghai.com/posts/48763/

提升算法的基本思路

提升算法是从弱学习算法出发，反复学习，得到一系列弱分类器（又称为基本分类器），然后组合这些弱分类器，构成一个强分类器。

有两个问题：

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

对于第一个问题，AdaBoost的做法是提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。
对于第二个问题，AdaBoost采取加权多数表决的方法。即加大分类误差率小的弱分类器的权值，减小分类误差率大的弱分类器的权值。

AdaBoost 算法

输入：训练数据集 $T = \left\{ \left( x_{1}, y_{1} \right), \left( x_{2}, y_{2} \right), \cdots, \left( x_{N}, y_{N} \right) \right\}$ ，其中 $x_{i} \in \mathcal{X} \subseteq R^{n}, y_{i} \in \mathcal{Y} = \left\{ +1, -1 \right\}, i = 1, 2, \cdots, N$ ；弱学习算法。

输出：最终分类器 $G(x)$ 。

初始化训练数据的权值分布
$\begin{align*} \\ & D_{1}=\left(w_{11},w_{12},\cdots,w_{1N}\right), \quad w_{1i} = \dfrac{1}{N}, \quad i=1,2,\cdots,N\end{align*}$
对 $m=1,2,\cdots,M$

（a）使用具有权值分布 $D_m$ 的训练数据集学习，得到基本分类器
$\begin{align*} \\ & G_{m}\left(x\right): \mathcal{X} \to \left\{ -1, +1\right\} \end{align*}（b）$
（b）计算 $G_m(x)$ 在训练数据集上的分类误差率
$\begin{align*} \\& e_{m} = P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right) \\ & = \sum_{i=1}^{N} w_{mi} I \left(G_{m}\left(x_{i}\right) \neq y_{i} \right) \end{align*}$
（c）计算 $G_m(x)$ 的系数
$\begin{align*} \\ & \alpha_{m} = \dfrac{1}{2} \log \dfrac{1-e_{m}}{e_{m}} \end{align*}$
（d）更新训练数据集的权值分布

$D_{m+1}=\left(w_{m+1,1},\cdots,w_{m+1,i},\cdots,w_{m+1,N}\right)$
$w_{m+1,i} = \dfrac{w_{mi}}{Z_{m}} \exp \left(- \alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right), \quad i=1,2,\cdots,N$

其中， $Z_m$ 是规范化因子
$\begin{align*} \\ & Z_{m}＝ \sum_{i=1}^{N} w_{mi} \exp \left(- \alpha_{m} y_{i}, G_{m}\left(x_{i}\right)\right)\end{align*}$
构建基本分类器的线性组合

$\begin{align} \\ & f \left( x \right) = \sum_{m=1}^{M} \alpha_{m} G_{m} \left( x \right) \end{align}$

得到最终分类器
$\begin{align*} \\ & G\left(x\right) = sign\left(f\left(x\right)\right)=sign\left(\sum_{m=1}^{M} \alpha_{m} G_{m} \left( x \right)\right) \end{align*}$

AdaBoost 算法的解释

AdaBoost 算法可以认为是模型为加法模型、损失函数为指数函数、学习算法为前向分布算法时的二类分类学习方法。

前向分布算法

前向分布算法：
输入：训练数据集 $T = \left\{ \left( x_{1}, y_{1} \right), \left( x_{2}, y_{2} \right), \cdots, \left( x_{N}, y_{N} \right) \right\}$ ，损失函数 $L\left(y,f\left(x\right)\right)$ ；基函数集 $\left\{b\left(x;\gamma\right)\right\}$
输出：加法模型 $f\left(x\right)$

初始化 $f_{0}\left(x\right)=0$
对 $m=1,2,\cdots,M$

（a）极小化损失函数
$\begin{align} \ & \left(\beta_{m},\gamma_{m}\right) = \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) \end{align}$
得到参数 $\beta_{m},\gamma_{m}$

（b）更新
$\begin{align*} \\& f_{m} \left(x\right) = f_{m-1} \left(x\right) + \beta_{m} b\left(x;\gamma_{m}\right) \end{align*}$

（c）得到加法模型
$\begin{align*} \\ & f \left( x \right) = f_{M} \left( x \right) = \sum_{m=1}^{M} \beta_{m} b \left( x; \gamma_{m} \right) \end{align*}$

前向分布算法与 AdaBoost

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

提升方法
提升方法提升方法 AdaBoost 算法 AdaBoost算法的训练误差分析 AdaBoost算法的解释提升树...
Adaboost
1.Boosting提升算法 Adaboost是典型的Boosting提升算法。Boosting算法是将弱...
Adaboost算法
AdaBoost是典型的Boosting算法。Boosting提升算法，是将“弱学习算法“提升为“强学习算法”的过...
提升算法 AdaBoost 算法
本文来自我的个人博客 https://www.zhangshenghai.com/posts/48763/ 提升算...
集成算法整理
一.AdaBoost的算法在学习adaboost算法前先要弄清楚前向分布算法，因为AdaBoost是前向分布加法...
第8章 Adaboost算法
内容一、Adaboost简介二、Adaboost算法过程三、Adaboost算法的训练误差分析四、Adab...
Adaboost算法简介
Adaboost算法 Adaboost算法是一种有监督的学习方法，是基于Adaboost算法的分类器把若干个分类器...
GBDT集成算法（梯度提升树）
一、算法思想 GBDT是集成学习Boosting算法中的一种，它与Adaboost相比，Adaboost算法利用...
提升算法之Adaboost算法
冒泡~七月的尾巴小李又上线啦! 今天叙述一个实用的算法-adaboost算法，在进入正题之前先叙述一下提升算法的...
AdaBoost（Adaptive Boosting）
AdaBoost 作为一种经典的提升方法，可以从不同维度去分析理解它。算法释义 AdaBoost 作为一种提升方...