二、最细粒度推导AdaBoost

作者: 炼丹师_风酒 | 来源:发表于2019-05-13 12:22 被阅读0次

二、最细粒度推导AdaBoost
AdaBoost 公式推导
第8章 Adaboost算法
一、最细粒度推导支持向量机SVM
bagging和boosting及Adaboost的推导
2019-01-06[Stay Sharp] AdaBoost
提升方法
The Optimization of the Adaboost
adaboost和xgboost的区别和联系
集成学习之提升法

声明：原创文章，转载请注明或保留出处【https://www.jianshu.com/p/c6603ceb62d0】by【飞奔的野指针】

一、概念介绍

1概率分布和期望

1.1概率分布

简单理解概率分布：有一种实验是同时抛10枚硬币，统计出现正面和反面的个数，用 $X$ 表示正面个数。

进行 $n$ 次该实验，在这 $n$ 次实验中，10枚硬币全都是正面 $(X=10)$ 的次数应该最少，5正5反 $(X=5)$ 的次数应该最多。

随着 $X$ 取不同值 $X=x_i(x_i\in\{1,2,...,10\})$ ， $n$ 次实验中出现的次数也不相同，或者说出现的概率也不相同，这满足某种规律，这种规律称为概率分布。

$\begin{align} &P(X=x_i)=p(x_i) & \text{分布列}\\[2ex] \end{align}$

1.2数学预期

数学期望举例：同样抛一枚硬币，正面得到100元，反面不给钱，数学预期就是 $0.5\times 100+0.5*0=50$ 。

如果进行次数够多，多次平均，每次大约能得到50元。

$\begin{align} &E(X)=\sum_{i=0}^n x_ip(x_i) & \text{数学预期} \end{align}$

概率分布和预期，可在概率论中详细了解。

2.二项分布

就如概率分布中的例子，抛一枚硬币只会出现两种情况，正面或者反面，也就是结果只有两个值。我们抛一枚硬币 $n$ 次，每次互不影响，相互独立，这种实验称为伯努利实验。

每次实验独立且只有两种结果，正面的概率都为 $p$ ，那么表示试验反面的概率为 $1-p$ 。 $n$ 次实验出现 $k$ 次正面表示为 $B_{n,k}$ ，其概率为

$P(B_{n,k})=\begin{pmatrix}n\\k\end{pmatrix}p^k(1-p)^{n-k} \quad\quad \quad\quad \begin{pmatrix}n\\k\end{pmatrix}=C_n^m\text{表示组合}$

含参数 $n$ 和 $p$ 表示 $n$ 次独立试验的成功次数的概率分布，就是二项分布，记为 $b(n,p)$ 。 $X\sim b(n,p)$ 表示随机变量服从该二项分布。当 $n=1$ 时是二点分布，也叫 $0-1$ 分布，我们也能证明其期望为：

$E(X)=np$

具体二项分布推导可以在概率论中了解。

三、AdaBoost

Boosting：从训练集训练一个基学习器，根据基学习器对训练样本分布进行调整，使得分错的样本受到更多关注。基于调整后的样本分布来训练下一个基分类，依次训练出 $T$ 个分类器，最终将 $T$ 个分类器加权结合，AdaBoost是Boosting的一种。

我们有训练集 $S=\begin{bmatrix} [x_1,y_1]\\ [x_2,y_2]\\ ...\\ [x_n,y_n]\\ \end{bmatrix}$ 、基学习算法 $h$ 、训练轮数 $T$ （当前轮数用 $t$ 表示）。

第一轮我们给每个样本一个初始权值 $d_{1,i}=\frac1n$ 组成权值集 $D_1=\{d_{1,1},...,d_{1,n}\}$ ，此时我们对每个样本的关注度相同。

我们根据样本训练出第一轮的基学习算法为 $h_1 $ ,训练方法可以使用任何一个分类器Bayes、SVM等。

1.错误率

$\begin{align} \epsilon &=\frac{\text{未正确分类的样本数目}}{\text{所有样本数目}}\\[2ex] \epsilon_1 & =\frac{\sum_{i=1}^{n} \mathbb{I}(h_1\left(x_{i}\right)\neq y_i)}{n} & \mathbb{I}\text{为表示性函数，成立取}1\text{否则取}0\\[2ex] & =\sum_{i=1}^{n} \frac1n \mathbb{I}(h_1\left(x_{i}\right)\neq y_i)\\[2ex] & =\sum_{i=1}^{n} d_{1,i} \mathbb{I}(h_1\left(x_{i}\right)\neq y_i)\\[2ex] \end{align}$

我们知道第一轮分类错误的概率
$\begin{align} & P_1(h_1(x_i)\neq y_i) = \frac{\sum_{i=1}^n \mathbb{I}(h_1\left(x_{i}\right)\neq y_i)}{n}=\sum_{i=1}^n \frac1n\mathbb{I}(h_1\left(x_{i}\right)\neq y_i)\\[2ex] \therefore & \epsilon_1 =P_1(h_1(x_i)\neq y_i)\\[2ex] \therefore & \epsilon_t =P_t(h_t(x_i)\neq y_i)\\[2ex] \end{align}$
错误率有两种意义：

错误率 $\epsilon_t$ 是一种分布列，基于概率分布 $D_t$ ，表示为 $P_{x\sim D_t}$ 。
通过调整概率分布 $D_t$ 来让每个样本对错误率有不同的影响力。分类算法是通过降低错误率是优化分类器的，调整 $D_t$ 就是调整错误率 $\epsilon_t $ ，从而降低错误率优化分类器。

错误率可写为：
$\color{red}{\epsilon_t = \sum_{i=1}^{n} d_{ti} \mathbb{I}(h_t\left(x_{i}\right)\neq y_i)=P_{x\sim D_t}(h_t(x_i)\neq y_i)}$

2.代价函数

2.1指数代价函数

AdaBoost每一轮都训练一个基分类器 $h_t$ ，然后将每一轮的分类器组合在一起，组成一个强大的分类器 $H(x)$ ，AdaBoost采用加性模型，即及学习器的线性组合组成 $H(x)$ ，每一轮的权设为 $\alpha_t$ （注意区分 $D_t$ 和 $\alpha_t$ ）， $\alpha_t$ 的引入意味着训练出的 $T$ 个分类器的权重不同，每个分类器对最终预测结果的影响力不同。
$\begin{align} & H(x)=\sum_{t=1}^T \alpha_t h_t(x) \\[2ex] \end{align}$
支持向量机中介绍了几种基本代价函数，我们使用 $\ell_{exp}=e^{-z}$ 作为代价函数，和支持向量机类似， $y_i$ 表示实际分类， $H(x_i)$ 表示预测结果
$\begin{align} & z=-y_iH(x_i)\\[2ex] & \ell_{exp}=e^{-y_iH(x_i)} \end{align}$
简单分析下指数损失函数的性质：

1557030493674.png

预测与实际类别一致， $|H(x)|$ 越大，代价函数越趋向 $0$ 。
$\begin{align} & y_iH(x_i)\text{同号}，y_iH(x_i)>0 \implies -y_iH(x_i)<0 \implies e^{-y_iH(x_i)}<1\\[2ex] & |H(x_i)|\to +\infty \quad e^{-y_iH(x_i)}\to 0 \end{align}$
预测与实际类别不同， $|H(x)|$ 越大，代价函数越趋向 $+\infty$ 。
$\begin{align} & f(x_i)H(x_i)\text{异号}，y_iH(x_i)<0 \implies -y_iH(x_i)>0 \implies e^{-y_iH(x_i)}>1\\[2ex] & |H(x_i)|\to +\infty \quad e^{-y_iH(x_i)}\to +\infty \end{align}$
损失函数可以看基于概率分布 $D_t $ 的随机变量， $x\sim D_t $ ，我们用数学期望替代损失函数，数学期望为
$\begin{align} & \color{red}{\ell_{exp}(H|D_t)= E_{x\sim D_t}\left[e^{-y_iH(x)}\right]}\\[2ex] \end{align}$

2.2指数代价函数可行性

分类结果只有两种情况，分对和分错，这是一种 $0-1$ 分布，其预期如下
$\begin{align} E(Z=z)&=z_0p_0+z_1p_1 \quad z_0=0,z_1=1 \text{表示分对或分错}\\[2ex] \end{align}$
我们试着验证指数代价函数和原来的 $0/1$ 代价函数具有一致性。
$\begin{align} \therefore\ell_{exp}(H|D_t)&= E_{x_i\sim D_t}\left[e^{-y_iH(x_i)}\right]\\[2ex] &= e^{-H(x_i)} \times p(y_i=1)+e^{H(x_i)}\times P(y_i=-1)\\[2ex] \ell_{exp}(H|D_t)&=p(y=1) *e^{-H(x)}+P(y=-1) *e^{H(x)} \\[2ex] \end{align}$
需要最小化代价函数，由于 $p(y=1)$ 与 $p(y=-1)$ 为常数，对代价函数关于 $H(x)$ 求偏导：
$\frac{\partial \ell(H|D_t)}{\partial H(x)} =-e^{-H(x)} p(y=1)+e^{H(x)} p(y=-1)$

令其为 $0$ 可得：
$\begin{align} H(x) &=\frac{1}{2} ln\frac{P(y=1 | x)}{P(y=-1 | x)}\\[2ex] \end{align}$

$\begin{align} \operatorname{sign}(H(x)) &= \operatorname{sign}\left[\frac12 \ln \frac{P(y=1)}{P(y=-1)}\right]\\[2ex] &=\left\{\begin{array}{ll}{1,} & {P(y=1)>P(y=-1)} \\ {-1,} & {P(y=1)<P(y=-1)}\end{array}\right.\\[2ex] &=\underset{\beta \in\{-1,1\}}{\arg \max } P(y=\beta) \end{align}$
这意味着 $\operatorname{sign}H(x)$ 达到了贝叶斯最优错误率，若指数损失函数 $e^{-y_i(x_i)}$ 最小化，则分类错误率最小化，指数代价函数是原本 $0/1$ 代价函数的一致性替代函数，它有更好性质，我们采用它来替代并优化是可行的。

3.求解 $\alpha_t$

第一个分类器 $h_1$ 直接通过原始训练集得到，此后迭代生成每一轮的 $h_t $ 和 $\alpha_t$ ，当 $h_t$ 基于分布 $D_t$ ， $\alpha_t $ 应使得代价函数最小。
$\begin{align} \ell(H|D_t)& =E_{x_i\sim D_t}\left[e^{-y_i\alpha_th_t(x_i)}\right]\\[2ex] & =E_{x_i\sim D_t}\left[e^{-a_t} \mathbb{I}(h_t(x_i)=y_i)+e^{a_t} \mathbb{I}(h_t(x_i)\neq y_i) \right] \\[2ex] & =e^{-\alpha_t} P_{x \sim \mathcal{D}_t}(h_t(x_i)=y_i)+e^{\alpha_t} P_{x \sim \mathcal{D}_t}(h_t(x_i)\neq y_i) & 0-1\text{分布}\\[2ex] & =e^{-\alpha_{t}}(1-\epsilon_{t})+e^{\alpha_t} \epsilon_{t} & \epsilon_t=P_{x \sim \mathcal{D}_t}(h_t(x_i)\neq y_i)\\[2ex] \frac{\partial\ell(H|D_t)}{\partial \alpha_t}& =-e^{-\alpha_t}(1-\epsilon_t)+e^{\alpha_t} \epsilon_t=0\\[2ex] \color{red}{\alpha_t}& \color{red}{=\frac12\ln(\frac{1-\epsilon^t}{\epsilon_t})} \end{align}$
上式可知， $\alpha_t$ 只和 $t$ 轮分类器的错误率有关，错误率越高，权重 $\alpha_t$ 越小。

4.前向分布优化求解 $D_t$

$H_1=h_1\\ H_2 =H_{1}+\alpha_2h_2\\ ...\\ H_t =H_{t-1}+\alpha_th_t$

第1轮的分类器就是基分类器，第2轮只训练出 $\alpha_2,h_2$ ，在第1轮的基础上纠正 $H_1$ 的全部错误，至少逼近需要优化的目标函数。如次递推，每一轮都在上一轮的基础上学习出本轮的 $\alpha_t,h_t$ ，然后叠加，逼近优化目标（此处为最小代价函数），这种算法称为前向分布优化。

已知 $\alpha_t$ 取决于 $t$ 轮错误率 $\epsilon_t$ ，只有训练出了该轮的基学习器 $h_t$ 才能够求错误率，而训练 $h_t$ 需要 $D_t$ ，于是任务变成了从 $t-1$ 轮的各种参数中更新出 $D_t$ ，更新 $D_t$ 的限制条件为最小化代价函数。
$\text{求}D_t \quad st.\;\min\ell_{exp}(H|D_t)$
之前已经求出 $t$ 轮代价函数，我们试着将其与上一轮 $t-1$ 轮的的某些参数关联起来，试着找出两轮之间的联系。
$\begin{align} \because H_t& =H_{t-1}+\alpha_th_t\\[2ex] \color{red}{e^{-yH(x)}}& =e^{-y\left(H_{t-1}(x)+\alpha_th_t(x)\right)}\color{red}{=e^{-yH_{t-1}(x)}\cdot e^{-y\alpha_th_t(x_i)}}\\[2ex] \ell_{exp}(H_t|D_t)&= E_{x\sim D_{t}}\left[e^{-yH_{t}(x_i)}\right]\\[2ex] &=\sum_{i=1}^n d_{t,i}e^{-yH_{t}(x)} &\text{数学预期公式}E(X)=\sum_{i=1}^n x_ip(x_i)\\[2ex] &=\sum_{i=1}^n d_{t,i}e^{-yH_{t-1}(x)}e^{-y\alpha_th_t(x_i)}\\[2ex] \ell_{exp}(H_{t-1}|D_{t-1})&=\sum_{i=1}^n d_{t-1,i}e^{-yH_{t-1}(x_i)} \end{align}$

这里假设是通过 $\alpha_t,h_t$ 即可纠正 $H_{t-1}$ 的误差，也就是说
$\sum_{i=1}^n d_{t,i}e^{-yH_{t-1}(x_i)}=\sum_{i=1}^n d_{t-1,i}e^{-yH_{t-1}(x_i)}$
那么我们可以将 $t$ 轮代价函数改写
$\begin{align} \ell_{exp}(H_{t-1}+h_t|D)&=\sum_{i=1}^n d_{t-1,i}e^{-yH_{t-1}(x_i)}e^{-y\alpha_th_t(x_i)}\\[2ex] &= \text{设}\color{red}{w_{t-1}^i=e^{-yH_{t-1}(x_i)}} \\[2ex] \ell_{exp}(H_{t-1}+h_t|D)&=\sum_{i=1}^n w_{t-1}^id_{t-1,i}e^{-y\alpha_th_t(x_i)}\\[2ex] &=\sum_{i=1}^n w_{t-1}^i\sum_{i=1}^nd_{t-1,i}e^{-y\alpha_th_t(x_i)}\\[2ex] &=\sum_{i=1}^nw_{t-1}^i E_{x\sim D_{t-1}}\left[e^{-y\alpha_th_t(x)}\right]\\[2ex] \end{align}$
我们将代价函数分成了两块，前者是本轮未知参数，后者中都是上轮参数，都是已知的，也就是固定值。

后者中的 $e^{-y\alpha_t h_t(x)}$ 含有复杂的 $e$ ，设法将其去除，展开至二次方（具体见高数泰勒公式）
$\begin{align} & e^x \approx 1+x+\frac{x^2}{2} \\[2ex] \therefore & e^{-y\alpha_th_t(x)} \approx 1-y\alpha_th_t(x)+\frac{y^2\alpha_t^2h_t^2(x)}{2}\\[2ex] \because & y^2=h_t^2(x)=1\\[2ex] \therefore & e^{-y\alpha_th_t(x)} \approx 1-y\alpha_th_t(x)+\frac12=\frac32-y\alpha_th_t(x)\\[2ex] \end{align}$
将其代入原式
$\begin{align} \ell_{exp}(H_{t-1}+h_t|D) &\approx \sum_{i=1}^nw_{t-1}^iE_{x\sim D_{t-1}}\left(\frac32-y \alpha_th_t(x)\right)\\[2ex] \end{align}$
本轮基学习器 $h_t$ 依托于最小化 $\ell_{exp}(H_{t-1}+h_t|D)$ ，即 $\left(\alpha_t,h_t(x)\right)=\underset{h}{\arg\min} \ell_{exp}(H_{t-1}+h_t|D)$ ，其中arg的含义是满足后面式子时 $h$ 的取值。

$\begin{align} \left(\alpha_t,h_t(x)\right)&= \underset{h}{\arg\min}\;\sum_{i=1}^nw_{t-1}^iE_{x\sim D_{t-1}}\left(\frac32-y\alpha_th_t(x)\right)\\[2ex] &= \underset{h}{\arg\max}\;\sum_{i=1}^nw_{t-1}^iE_{x\sim D_{t-1}}y\alpha_th_t(x)\\[2ex] &=\underset{h}{\arg \max}\;\sum_{i=1}^nw_{t-1}^iE_{x \sim D_{t-1}}\left(\frac{ y \alpha_th_t(x)}{E_{x \sim D_{t-1}}\left[e^{-y H_{t-1}(x)}\right]} \right) &\text{加入规范因子} \color{red}{Z_{t-1}= E_{x \sim D_{t-1}}\left[e^{-y H_{t-1}(x)}\right]}\\[2ex] &=\underset{h}{\arg \max}\;\sum_{i=1}^nw_{t-1}^iE_{x \sim D_{t-1}}\left(\frac{ y \alpha_th_t(x)}{Z_{t-1}} \right) \\[2ex] \end{align}$

$\alpha_t>0$ ，固定 $\alpha_t$ ，求解 $h_t$ ，展开数学预期，并化简。
$\begin{align} &\because E_{x \sim D_{t-1}}\left[\frac{yh_t(x)}{Z_{t-1}}\right] = \sum_{i=1}^{n} d_{t-1,i} \frac{yh_t(x_i)}{Z_{t-1}} \\[2ex] h_t(x) &=\underset{h}{\arg \max}\;\sum_{i=1}^nw_{t-1}^i \sum_{i=1}^{n} d_{t-1,i}\frac{y h_t(x_i)}{Z_{t-1}}\\[2ex] &=\underset{h}{\arg \max}\; \sum_{i=1}^{n} yh_t(x_i)d_{t-1,i} \frac{w_{t-1}^i}{Z_{t-1}}\\[2ex] &\text{设新分布}\color{red}{\phi_{t,i} =d_{t-1,i}\frac{w_{t-1}^i}{Z_{t-1}}} \quad \Phi_t=\{\phi_{t,1},...,\phi_{t,n}\}\\[2ex] h_t(x)& = \underset{h}{\arg \max}\sum_{i=1}^{n} \phi_{t,i} y_ih_t(x_i)\\[2ex] & = \underset{h}{\arg \max}E_{x\sim \Phi_{t}}[yh_t(x)]\\[2ex] & = \underset{h}{\arg \max}E_{x\sim \Phi_{t}}[yh_t^*(x)]\\[2ex] \end{align}$
根据上式， $y$ 是定值， $h_t$ 根据分布 $\Phi$ 不断学习，直到得出最优 $h_t $ ，实质上 $\Phi $ 就是要求的本轮 $D_t $ 。
$\begin{align} \phi_{t,i}&=d_{t-1,i}\frac{w_{t-1}^i}{Z_{t-1}}\\[2ex] &=d_{t-1,i}\frac{e^{-yH_{t-1}(x_i)}}{\sum_{i=1}^n d_{t-1,i}e^{-y H_{t-1}(x)}} \end{align}$
右侧全部都是上一轮 $t-1$ 轮相关参数，右侧分母为规范因子。得出最终 $D_t $ 优化函数。
$\begin{align} d_{t,i}&=d_{t-1,i}\frac{e^{-yH_{t-1}(x_i)}}{\sum_{i=1}^n d_{t-1,i}e^{-y H_{t-1}(x)}}\\[2ex] \color{red}{D_{t,i}}&\color{red}{=D_{t-1,i} \frac{e^{-yH_{t-1}(x_i)}}{Z_{t-1}}} \end{align}$
由于 $f(x),h(x)\in\{-1,+1\}$ 则 $t$ 轮理想学习器为：
$\begin{align} & yh(x)=(1-2\mathbb{I}(h(x))\neq y)\\[2ex] & h_t=\underset{h}{\arg \min } E_{x \sim \Phi_{t}}[\mathbb{I}(h(x)\neq y)] \end{align}$

四.AdaBoost思路

adaptive boosting，自适应boosting，简称AdaBoost。

1.流程

输入：训练集 $S=\begin{bmatrix} [x_1,y_1]\\ [x_2,y_2]\\ ...\\ [x_n,y_n]\\ \end{bmatrix}$ 、基学习算法 $L$ 、训练轮数 $T$ 。
给训练集每个样本一个权重，第 $1$ 轮第 $i$ 个样本权重为 $d_{1i}$ ，初始为等值 $d_{ti} = \frac1n$ ，所有权重组成第 $t$ 轮的权重向量 $D_t=[d_{t1},d_{t2},...,d_{tn}] $ 。
循环进行T轮训练，每一轮过程如下：
1. 根据训练集 $S$ 和该轮权重 $D_t$ 训练弱分类器， $h_t=L(D, D_t)$ ，
2. 计算出错误率 $\varepsilon=\frac{\text{未正确分类的样本数目}}{\text{所有样本数目}}$ ，此时 $\epsilon_t=P_{x\sim D_t}(h_t(x)\neq y)=\sum_{i=1}^m d_i$ ，如果 $\epsilon_t >0.5$ 则跳过该轮。
3. 根据错误率 $\epsilon_t$ ，计算权重系数 $\alpha_{t}=\frac{1}{2} \ln \left(\frac{1-\epsilon_{t}}{\epsilon_{t}}\right)$ .
4. 根据 $\alpha_t$ 调整权重 $D_{t+1}(x)=\frac{D_t(x)}{Z_t} \times \left\{\begin{array}{ll}{\exp (-\alpha_{t})} & {\text{if}\quad h_t(x)=f(x)} \\ {\exp (\alpha_t),} & {\text{if}\quad h_t(x) \neq f(x)}\end{array}\right.$ ，分类错误的样本的权重增加，分对的样本权重降低，进行 $T$ 轮训练。
根据每一轮的权重，综合成一个强分类器 $H(\boldsymbol{x})=\operatorname{sign}\left(\sum_{t=1}^{T} \alpha_{t} h_{t}(\boldsymbol{x})\right)$

2.图示

1557021277829.png

如图所示， $h_1$ 的错误率 $\epsilon=0.3$ ，可以计算出 $\alpha_1=0.42$ ， $h_2$ 的错误率 $\epsilon=0.21$ ，可以计算出 $\alpha_2=0.65$ ， $h_3$ 的错误率 $\epsilon=0.14$ ，可以计算出 $\alpha_2=0.92$ ，最终可得
$H(x)=\operatorname{sign} \left[ 0.42\times h_1(x)+0.65\times h_2(x)+0.92\times h_3(x) \right]$
Adaboost 为每个分类器分配一个权重 $\alpha$ ， $\alpha$ 是基于每个弱分类器的错误率进行计算的。

参考：

周志华《机器学习》第八章集成学习
李航《统计学习方法》第8章提升方法
茆诗松《概率论与数理统计教程》第二章随机变量及其概率分布

二、最细粒度推导AdaBoost
声明：原创文章，转载请注明或保留出处【https://www.jianshu.com/p/c6603ceb62d0...
AdaBoost 公式推导
首先要知道加法模型和指数损失函数。加法模型加法模型是一个加和模型，每一列训练一个分类器，并且基于这个分类器的...
第8章 Adaboost算法
内容一、Adaboost简介二、Adaboost算法过程三、Adaboost算法的训练误差分析四、Adab...
一、最细粒度推导支持向量机SVM
声明：原创文章，转载请注明或保留出处【https://www.jianshu.com/p/dbc86a2b9760...
bagging和boosting及Adaboost的推导
bagging：对训练样本进行自助采样，产生若干个不同的子集，再从每个数据子集中训练出一个基学习器，再将这些基学...
2019-01-06[Stay Sharp] AdaBoost
What is AdaBoost? AdaBoost, short for Adaptive Boosting, ...
提升方法
提升方法提升方法 AdaBoost 算法 AdaBoost算法的训练误差分析 AdaBoost算法的解释提升树...
The Optimization of the Adaboost
The Optimization of the Adaboost 1.对于Adaboost error funct...
adaboost和xgboost的区别和联系
机器学习算法中GBDT与Adaboost的区别与联系是什么？ Adaboost Adaboost是模型为加法模型，...
集成学习之提升法
AdaBoost 定义AdaBoost最流行的提升法的一种方式之一,将几个弱学习器集合成一个强学习器的任意集成方法...