【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
1.Boosting
Boosting是一族可将弱学习器提升为强学习器的算法。这族算法的工作机制类似：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值$T$，最终将这$T$个基学习器进行加权结合。
2.AdaBoost
Boosting族算法最著名的代表是AdaBoost，其描述如下图所示，其中$y_i \in \{-1,+1\}$，$f$是真实函数。
接下来详细解释并推导算法的每一步。
2.1.算法第一步
初始化样本权值分布，即每个样本的权重均为：$\frac{1}{m}$。
2.2.算法第二步
$T$为预先设定好的基学习器的数目，即训练轮数。
2.3.算法第三步
基于分布$\mathcal{D}_t$从数据集$D$中训练出分类器$h_t$。对于二分类问题来说，$h_t$的结果为-1或+1。
2.4.算法第四步
估计$h_t$的误差$\epsilon _t$。即分类器$h_t$的预测错误率（注意：基于$\mathcal{D}_t$中的样本权重）。
2.5.算法第五步
算法在训练的每一轮都要检查当前生成的基学习器是否满足基本条件，一旦条件不满足，则当前基学习器即被抛弃，且学习过程停止。在此种情形下，初始设置的学习轮数$T$也许还远未达到，可能导致最终集成中只包含很少的基学习器而性能不佳。
2.6.算法第六步
确定分类器$h_t$的权重。
【推导过程】
AdaBoost可理解为基于“加性模型”（additive model），即基学习器的线性组合：
\[H(x)=\sum^T_{t=1} \alpha_t h_t(x) \tag{2.6.1}\]来最小化指数损失函数：
\[\ell_{exp} (H \mid \mathcal{D})=\mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H(x)}] \tag{2.6.2}\]$f(x)$为真实标签，$H(x)$为预测标签（这里没使用sign函数，所以准确的说$H(x)$的取值并不是只有-1和+1）。如果预测正确，则$f(x)H(x)>0$，否则$f(x)H(x)<0$。
指数函数图像：
式(2.6.2)可看作：
\[\begin{align} \ell _{exp}(H \mid \mathcal{D}) &= \mathbb{E}_{x \sim \mathcal{D}}[e^{-f(x)H(x)}] \\&= \sum_{x\in D} \mathcal{D}(x) e^{-f(x)H(x)} \\&= \sum^{\lvert D \rvert}_{i=1} \mathcal{D}(x_i) \left( e^{-H(x_i)} \mathbb{I} (f(x_i)=1) + e^{H(x_i)} \mathbb{I} (f(x_i)=-1) \right) \\&= \sum^{\lvert D \rvert}_{i=1} \left( e^{-H(x_i)} \mathcal{D}(x_i) \mathbb{I} (f(x_i)=1) + e^{H(x_i)} \mathcal{D}(x_i) \mathbb{I} (f(x_i)=-1) \right) \\&= \sum^{\lvert D \rvert}_{i=1} \left( e^{-H(x_i)} P(f(x_i)=1 \mid x_i) + e^{H(x_i)} P(f(x_i)=-1 \mid x_i) \right) \end{align} \tag{2.6.3}\]$\mathcal{D}(x_i) \mathbb{I} (f(x_i)=1)=P(f(x_i)=1 \mid x_i)$可以理解为：在数据集$D$中进行一次随机抽样，使得$f(x_i)=1$的样本$x_i$被抽到的概率。
若$H(x)$能令指数损失函数最小化，则考虑式(2.6.3)对$H(x)$的偏导：
\[\frac{\partial \ell _{exp} (H \mid \mathcal{D})}{\partial H(x)} = -e^{-H(x)}P(f(x)=1 \mid x)+e^{H(x)}P(f(x)=-1 \mid x) \tag{2.6.4}\]其实是对$H(x_i)$求导，求和号中只有含$x_i$项不为0。
令式(2.6.4)为零可解得：
\[H(x) =\frac{1}{2} \ln \frac{P(f(x)=1 \mid x)}{P(f(x)=-1 \mid x)} \tag{2.6.5}\]因此，有：
\[\begin{align} sign (H(x)) &= sign \left( \frac{1}{2} \ln \frac{P(f(x)=1 \mid x)}{P(f(x)=-1 \mid x)} \right) \\&= \begin{cases} 1, & P(f(x)=1 \mid x)> P(f(x)=-1 \mid x) \\ -1, & P(f(x)=1 \mid x)< P(f(x)=-1 \mid x) \end{cases} \\&= \arg\max \limits_{y\in \{-1,1\}} P(f(x)=y \mid x) \end{align} \tag{2.6.6}\]这里忽略了$P(f(x)=1 \mid x)= P(f(x)=-1 \mid x)$的情形。
这意味着$sign(H(x))$达到了贝叶斯最优错误率。换言之，若指数损失函数最小化，则分类错误率也将最小化；这说明指数损失函数是分类任务原本0/1损失函数的一致的替代损失函数。由于这个替代函数有更好的数学性质，例如它是连续可微函数，因此我们用它替代0/1损失函数作为优化目标。
在AdaBoost算法中，第一个基分类器$h_1$是通过直接将基学习算法用于初始数据分布而得；此后迭代地生成$h_t$和$\alpha_t$，当基分类器$h_t$基于分布$\mathcal{D}_t$产生后，该基分类器的权重$\alpha_t$应使得$\alpha_t h_t$最小化指数损失函数：
\[\begin{align} \ell_{exp} (\alpha_t h_t \mid \mathcal{D}_t) &= \mathbb{E}_{x\sim \mathcal{D}_t} \left[ e^{-f(x)\alpha_t h_t (x)} \right] \\&= \mathbb{E}_{x\sim \mathcal{D}_t} \left[ e^{-\alpha_t} \mathbb{I} (f(x)=h_t(x)) + e^{\alpha_t} \mathbb{I} (f(x) \neq h_t(x)) \right] \\&= e^{-\alpha_t} P_{x\sim \mathcal{D}_t} (f(x)=h_t(x)) + e^{\alpha_t} P_{x\sim \mathcal{D}_t} (f(x)\neq h_t(x)) \\&= e^{-\alpha_t} (1-\epsilon _t) + e^{\alpha_t} \epsilon_t \end{align} \tag{2.6.7}\]其中$\epsilon_t = P_{x\sim \mathcal{D}_t}(h_t(x) \neq f(x))$。考虑指数损失函数的导数：
\[\frac{\partial \ell_{exp} (\alpha_t h_t \mid \mathcal{D}_t)}{\partial \alpha_t}=-e^{-\alpha_t} (1-\epsilon _t) + e^{\alpha_t} \epsilon_t \tag{2.6.8}\]令式(2.6.8)为零可解得：
\[\alpha_t = \frac{1}{2} \ln (\frac{1-\epsilon_t}{\epsilon_t}) \tag{2.6.9}\]2.7.算法第七步
AdaBoost算法在获得$H_{t-1}$之后样本分布将进行调整，使下一轮的基学习器$h_t(x)$能纠正$H_{t-1}$的一些错误。理想的$h_t$能纠正$H_{t-1}$的全部错误，即最小化：
\[\begin{align} \ell_{exp}(H_{t-1}+h_t \mid \mathcal{D}) &= \mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)(H_{t-1}(x)+h_t(x))} \right] \\&= \mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t-1}(x)} e^{-f(x)h_t(x)} \right] \end{align} \tag{2.7.1}\]其实应为$H_{t-1}(x)+\alpha_t h_t(x)$，但因为$\alpha_t$为常数，且对后续推导没有影响，故省略。
$e^x$在0附近的泰勒展式近似为：
\[e^x=1+x+\frac{x^2}{2}+o(x^2)\]所以有：
\[e^{-f(x)h_t(x)}=1-f(x)h_t(x)+\frac{f^2(x)h^2_t(x)}{2}\]又因为$f^2(x)=h^2_t(x)=1$，上式可简化为：
\[e^{-f(x)h_t(x)}=1-f(x)h_t(x)+\frac{1}{2}\]代入式(2.7.1)可得：
\[\begin{align} \ell_{exp}(H_{t-1}+h_t \mid \mathcal{D}) &\simeq \mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t-1}(x)} \left( 1-f(x)h_t(x) + \frac{1}{2} \right) \right] \end{align} \tag{2.7.2}\]于是，理想的基学习器：
\[\begin{align} h_t(x) &= \arg\min \limits_{h} \ \ell_{exp}(H_{t-1}+h \mid \mathcal{D}) \\&= \arg \min \limits_{h} \mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t-1}(x)} \left( 1-f(x)h(x) + \frac{1}{2} \right) \right] \\&= \arg \max \limits_{h} \mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t-1}(x)} f(x)h(x) \right] \\&= \arg \max \limits_{h} \mathbb{E}_{x\sim \mathcal{D}} \left[ \frac{e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\sim \mathcal{D}} [e^{-f(x)H_{t-1}(x)}]} f(x)h(x) \right] \end{align} \tag{2.7.3}\]因为$\mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t-1}(x)} \right]$与$h(x)$无关，且是一个常数，所以可以省去或引入。
令$\mathcal{D}_t$表示一个分布：
\[\mathcal{D}_t(x)=\frac{\mathcal{D}(x) e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t-1}(x)} \right]} \tag{2.7.4}\]则根据数学期望的定义，这等价于令：
\[\begin{align} h_t(x) &= \arg \max \limits_{h} \mathbb{E}_{x\sim \mathcal{D}} \left[ \frac{e^{-f(x)H_{t-1}(x)}}{\mathbb{E}_{x\sim \mathcal{D}} [e^{-f(x)H_{t-1}(x)}]} f(x)h(x) \right] \\&= \arg \max \limits_{h} \mathbb{E}_{x\sim \mathcal{D}_t} [f(x)h(x)] \end{align} \tag{2.7.5}\]由$f(x),h(x) \in \{-1,+1 \}$，有：
\[f(x)h(x)=1-2\mathbb{I}(f(x)\neq h(x)) \tag{2.7.6}\]当$f(x)=h(x)$时，$\mathbb{I} (f(x) \neq h(x))=0$，此时$f(x)h(x)=1$。
当$f(x) \neq h(x)$时，$\mathbb{I} (f(x) \neq h(x))=1$，此时$f(x)h(x)=-1$。
则理想的基学习器：
\[h_t(x) = \arg \min \limits_{h} \mathbb{E}_{x\sim \mathcal{D}_t} [ \mathbb{I} ( f(x) \neq h(x)) ] \tag{2.7.7}\]由此可见，理想的$h_t$将在分布$\mathcal{D}_t$下最小化分类误差。因此，弱分类器将基于分布$\mathcal{D}_t$来训练，且针对$\mathcal{D}_t$的分类误差应小于0.5。这在一定程度上类似“残差逼近”的思想。考虑到$\mathcal{D}_t$和$\mathcal{D}_{t+1}$的关系，有：
\[\begin{align} \mathcal{D}_{t+1}(x) &= \frac{\mathcal{D}(x) e^{-f(x)H_{t}(x)}}{\mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t}(x)} \right]} \\&= \frac{\mathcal{D}(x) e^{-f(x)H_{t-1}(x)} e^{-f(x)\alpha_t h_t(x)}}{\mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t}(x)} \right]} \\&= \mathcal{D}_t(x) \cdot e^{-f(x)\alpha_t h_t(x)} \frac{\mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t-1}(x)} \right]}{\mathbb{E}_{x\sim \mathcal{D}} \left[ e^{-f(x)H_{t}(x)} \right]} \end{align} \tag{2.7.8}\]这便是算法第7行的样本分布更新公式。
算法第7行中$Z_t$是规范化因子，以确保$\mathcal{D}_{t+1}$是一个分布。
3.总结
Boosting算法要求基学习器能对特定的数据分布进行学习，这可通过“重赋权法”（re-weighting）实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重。
⚠️对无法接受带权样本的基学习算法，则可通过“重采样法”（re-sampling）来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。一般而言，这两种做法没有显著的优劣差别。
