Adaboost算法详解

2020-06-06 本文已影响0人 Serre对偶

一.提升方法

提升方法：

1.从弱学习算法出发，反复学习，得到一系列弱分类器（大多数提升方法都是改变训练数据

的概率分布来学习不同的弱分类器的）；

2.组合这些弱分类器，得到一个强分类器;

提升方法有两个关键点：

▶如何改变训练样本的权重学习弱分类器？

▶ 如何将弱分类器组合成强分类器？

Adaboost的做法：

▶ 提高被前一个弱分类器分类错误的样本的权重，降低被分类正确的样本权重，学习新的弱

分类器；

▶ 加大分类误差率小的弱分类器的权重，减小分类误率差大的弱分类器的权重。

二.Adaboost详解

一.Adaboost算法流程

首先，我们来理一下adaboost算法的流程：我们用 $N$ 来训练集的总数， $x_i$ 表示第 $i$ 个样本， $D_m=(w_{m, 1},\ldots, w_{m, i}, \ldots, w_{m, N})$ 表示第 $m$ 次迭代后的样本权重， $G_m$ 表示第 $m$ 次提升得到的分类器。

1:对每个 $i\in \{1, 2, \ldots, N\}$ ，初始化权重: $w_{1i}=\frac{1}{N}$ , 即

$D_1=(w_{11},\ldots, w_{1i}, \ldots, w_{1N})$

2: 对每个 $m=1, 2, \ldots, M$ , 我们用权重 $D_m$ 来训练数据集, 得到分类器：

$G_m(x):\mathcal{X}\to \{-1, +1\}$

计算 $G_m$ 的分类误差：

$e_m=\sum_{i=1}^Np(G_m(x_i)\neq y_i)=\sum_{i=1}^Nw_{mi}\mathbb{I}(G_m(x_i)\neq y_i)$

和 $G_m$ 的权重系数

$\alpha_m = \frac{1}{2}\log\frac{1-e_m}{e_m}$

更新权重分布

$D_{m+1}=(w_{m+1, 1}, w_{m+1,2}, \ldots, w_{m+1,i}, \ldots, w_{m+1, N})$

其中

$\begin{align}\label{1}w_{m+1, i}=\frac{w_{m,i}}{Z_m}\exp(-\alpha_mG_m(x_i)y_i) \end{align}$

以及规范化因子

$Z_m=\sum_{i=1}^N w_{m, i}\exp(-\alpha_mG_m(x_i)y_i)$

迭代后的组合分类器为：

$f(x)=sgn(\sum_{m=1}^M\alpha_mG_m(x))$

二.Adaboost算法收敛性

组合分类器的分类误差(分类错误率)为

$e=\frac{1}{N}\sum_{i=1}^N\mathbb{I}(y_i\neq f(x_i))$

很明显，这是被指数型损失函数控制住的：

$\frac{1}{N}\sum_{i=1}^N\mathbb{I}(y_i\neq f(x_i))\leq \frac{1}{N}\sum_{i=1}^N\exp(-y_if(x_i))=\frac{1}{N}\sum_{i=1}^N\prod_{m=1}^M\exp(-y_i\alpha_mG_m(x_i))$

而上式的最后一项可以如下化为：

$\begin{align*}&\frac{1}{N}\sum_{i=1}^N\prod_{m=1}^M\exp(-y_i\alpha_mG_m(x_i))\\=&\sum_{i=1}^Nw_{1i}\exp(-y_i\alpha_1G_1(x_i))\prod_{m=2}^M\exp(-y_i\alpha_mG_m(x_i))\\=&\sum_{i=1}^Nw_{2i}Z_1\prod_{m=2}^M\exp(-y_i\alpha_mG_m(x_i))\\=&\sum_{i=1}^Nw_{2i}\exp(-y_i\alpha_2G_2(x_i))\prod_{m=3}^M\exp(-y_i\alpha_mG_m(x_i))\\=&\ldots\\=&\sum_{i=1}^NZ_1Z_2\ldots Z_{M-1}w_{Mi}\exp(-y_i\alpha_MG_M(x_i))\\=&\prod_{m=1}^MZ_m\end{align*}$

上式第二个等号用到了权重更迭的公式，接下来我们来估计 $Z_m$ ,由于

$\begin{align}Z_m=&\sum_{i=1}^N w_{m, i}\exp(-\alpha_mG_m(x_i)y_i)\\=&\sum_{G_m(x)\neq y_i}e^{\alpha_m}+\sum_{G_m(x)=y_i}e^{-\alpha_m}\\=&e_me^{\alpha_m}+(1-e_m)e^{-\alpha_m}\\=&2\sqrt{e_m(1-e_m)}\\\end{align}$

上式最后一个等号用到了 $\alpha_m=\frac{1}{2}\log\frac{1-e_m}{e_m}\Longrightarrow e^{\alpha_m}=\sqrt{\frac{1-e_m}{e_m}}$ ,由于我们的弱分类器好于随机猜测，所以存在正数 $\delta<\frac{1}{2}$ ，使得 $e_m<\delta$ ,所以我们有

$\begin{align*}Z_m=&\sqrt{4e_m-4e_m^2}\\=&\sqrt{1-(1-2e_m)^2}\\\leq&(1-\epsilon)^{\frac{1}{2}},\epsilon=(1-2\delta)^2>0\end{align*}$

所以我们有

$\begin{align*}e=\prod_{m=1}^MZ_m\leq(1-\epsilon)^{\frac{M}{2}}\end{align*}$

即Adaboost的集成误差是指数减少的。