声明：原创文章，转载请注明或保留出处【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$ 是基于每个弱分类器的错误率进行计算的。