AdaBoost 决策树
AdaBoost-DTree($\mathcal D$)
对于$t=1,2,\ldots,T$，循环执行：
- 更新数据的权重$\mathbf u^{(t)}$；
- 通过决策树算法$\mbox{DTree}\left(\tilde{\mathcal D}, \mathbf u^{(t)}\right)$得到$g_t$；
- 计算$g_t$的投票权重$\alpha_t$。
返回$G=\mbox{LinearHypo}(\{\left(g_t,\alpha_t\right)\})$。
由此可见，AdaBoost 决策树需要加权决策树算法。对于有权重的算法，需要根据权重最小化$E_{in}$，通常有两种方法：
- 一种方法是通过算法加权，在计算$E_{in}$的地方嵌入权重计算，比如AdaBoost采用的最小化加权误差；
- 另一种方法是将算法当成黑盒不变更，通过数据集加权，根据权重在bootstrap时“复制”数据，也就是加权的重采样。
AdaBoost决策树通常采用后一种方法，AdaBoost＋sampling $\propto \mathbf u^{(t)}$＋$\mbox{DTree}(\tilde{\mathcal D}_t)$。
AdaBoost 的$\alpha_t$通过错误率确定。对于所有$\mathbf x_n$不同的完全成长决策树，$E_{in}(g_t)=0$，那么$E_{in}^{\mathbf u}(g_t)=0$，因此$\epsilon_t=0$并且$\alpha_t=\infty$。合适的方法是让决策树弱些，在部分数据集上训练剪枝的决策树。即使在$\tilde{\mathcal D}_t$上得到错误率为0的决策树$g_t$，回到$\mathcal D$上$\alpha_t$可能是大于、等于或小于0。剪枝可采用常规方法或只限制决策树高度，在数据重采样阶段已经包含了只抽取部分数据的功能。因此，AdaBoost决策树＝AdaBoost＋sampling $\propto \mathbf u^{(t)}$＋剪枝的$\mbox{DTree}(\tilde{\mathcal D}_t)$。
如果C&RT的高度限制为不超过1，当用二分类的误差作为不纯度时，AdaBoost决策树就是AdaBoost-Stump，此时通常有$\epsilon_t\neq 0$，一般不再需要sampling。
AdaBoost 理论分析：最速函数梯度下降法
AdaBoost的权重更新可以合并为 \[ u_n^{(t+1)}=u_n^{(t)}\cdot\blacklozenge_t^{-y_ng_t(\mathbf x_n)}， \] 由于$\blacklozenge_t=\exp(\alpha_t)$，因此 \[ u_n^{(t+1)}=u_n^{(t)}\cdot\exp\left(-y_n\alpha_tg_t\left(\mathbf x_n\right)\right)， \] 那么 \begin{equation} u_n^{(T+1)}=u_n^{(1)}\cdot\prod_{t=1}^T\exp\left(-y_n\alpha_tg_t\left(\mathbf x_n\right)\right)={1\over N}\exp\left(-y_n\sum_{t=1}^T\alpha_tg_t\left(\mathbf x_n\right)\right)。 \label{eq:un-t-plus-1} \end{equation} AdaBoost是分类器的线性组合，$\sum_{t=1}^T\alpha_tg_t(\mathbf x)$是$\{g_t\}$在$\mathbf x$上的投票得分（voting score），也就是对AdaBoost，$u_n^{(T+1)}\propto \exp\left(-y_n\cdot\left(\mbox{voting score on }\mathbf x_n\right)\right)$。
线性混合（linear blending），可以看作线性模型和以假设作为特征转换的结合 \[ G(\mathbf x_n)=\mbox{sign}\left(\overbrace{\sum_{t=1}^T\underbrace{\alpha_t}_{w_i}\underbrace{g_t(\mathbf x_n)}_{\phi_i(\mathbf x_n)}}^{\mbox{voting score}}\right)。 \] 对比hard-margin的SVM的边界${y_n\cdot\left(\mathbf w^T\phi(\mathbf x_n)+b\right)\over\lVert\mathbf w\rVert}$，投票得分可视为某种空间中非规范化的边界（距离）的度量，“$y_n$(voting score)=signed & unnormalized margin”。期望$y_n$(voting score)是正的，且越大越好，那么$\exp(-y_n(\mbox{voting score}))$越小越好，$u_n^{(T+1)}$越小越好。AdaBoost的$\sum_{n=1}^Nu_n^{(t)}$随着$t$的增大越来越小，在最后一轮 \begin{equation} \sum_{n=1}^Nu_n^{(T+1)}={1\over N}\sum_{n=1}^N\exp\left(-y_n\sum_{t=1}^T\alpha_tg_t\left(\mathbf x_n\right)\right) \label{eq:sum-un-t-plus-1} \end{equation} 达到最小，边界$y_n\sum_{t=1}^T\alpha_tg_t\left(\mathbf x_n\right)$最大化实现large margin的效果。
令线性评分函数$s=\sum_{t=1}^T\alpha_tg_t\left(\mathbf x_n\right)$，AdaBoost的指数误差度量（exponential error measure）$\widehat{err}_{ADA}(s,y)=\exp(-ys)$是0/1误差$\widehat{err}_{0/1}(s,y)=[[ys\leq 1]]$的上界1，如上图右所示，通过0/1误差的凸上界（convex upper bound）$\widehat{err}_{ADA}$作为算法误差度量（algorithmic error measure），通过上界误差最小化使0/1误差最小化。
AdaBoost通过增加函数$h(\mathbf x)$的方式，使基于\eqref{eq:sum-un-t-plus-1}的误差$\widehat E_{ADA}=\sum_{n=1}^Nu_n^{(t+1)}$最小化， \begin{equation} \begin{aligned} \min_h\quad\widehat E_{ADA} &\overset{[1]}{=}{1\over N}\sum_{n=1}^N\exp\left(-y_n\left(\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau(\mathbf x_n)+ \eta h(\mathbf x_n)\right)\right)\\ &\overset{[2]}{=}\sum_{n=1}^Nu_n^{(t)}\exp\left(-y_n\eta h(\mathbf x_n)\right) \overset{\mbox{taylor}}{\approx}\sum_{n=1}^Nu_n^{(t)}\left(1-y_n\eta h(\mathbf x_n)\right)\\ &=\sum_{n=1}^Nu_n^{(t)}+\eta\sum_{n=1}^Nu_n^{(t)}\left(-y_nh(\mathbf x_n)\right)， \end{aligned} \label{eq:min-E-ADA} \end{equation}
- [1]：增加函数$h(\mathbf x)$，由\eqref{eq:sum-un-t-plus-1}可得$\sum_{\tau=1}^t\alpha_\tau g_\tau\left(\mathbf x_n\right)=\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau\left(\mathbf x_n\right)+\eta h(\mathbf x_n)$；
- [2]：由\eqref{eq:un-t-plus-1}可得$u_n^{(t)}={1\over N}\exp\left(-y_n\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau\left(\mathbf x_n\right)\right)$。
公式\eqref{eq:min-E-ADA}形如梯度下降法最小化$E_{in}$ \[ \min_{\lVert\mathbf v\rVert=1}E_{in}(\mathbf w_t+\eta\mathbf v) \approx \underbrace{E_{in}(\mathbf w_t)}_{\mbox{known}} +\underbrace{\eta}_{\mbox{given positive}}\mathbf v^T\underbrace{\nabla E_{in}(\mathbf w_t)}_{\mbox{known}}， \] 好的$h(\mathbf x)$能最小化$\sum_{n=1}^Nu_n^{(t)}\left(-y_nh(\mathbf x_n)\right)$。对二分类，$y_n$和$h(\mathbf x_n)$都属于$\{-1,+1\}$，那么 \[ \begin{aligned} \sum_{n=1}^Nu_n^{(t)}\left(-y_nh(\mathbf x_n)\right) &=\sum_{n=1}^Nu_n^{(t)} \left\{ \begin{aligned} -1\quad\mbox{if }y_n=h(\mathbf x_n)\\ +1\quad\mbox{if }y_n\neq h(\mathbf x_n) \end{aligned} \right.\\ &=-\sum_{n=1}^Nu_n^{(t)}+\sum_{n=1}^Nu_n^{(t)} \left\{ \begin{aligned} 0\quad\mbox{if }y_n=h(\mathbf x_n)\\ 2\quad\mbox{if }y_n\neq h(\mathbf x_n) \end{aligned} \right.\\ &\overset{[1]}{=}-\sum_{n=1}^Nu_n^{(t)}+2E_{in}^{\mathbf u^{(t)}}(h)\cdot N， \end{aligned} \]
因此，也就是要使$E_{in}^{\mathbf u^{(t)}}(h)$变小，这就是AdaBoost中算法$\mathcal A$的任务，找出一个好的函数方向$h$。
AdaBoost通过近似最小化$\min_h\widehat E_{ADA}=\sum_{n=1}^Nu_n^{(t)}\exp\left(-y_n\eta h(\mathbf x_n)\right)$，公式\eqref{eq:min-E-ADA}的$[2]$等式，找到新的分类器$g_t=h$之后，还需要找到最佳的$\eta$， \[ \min_\eta\widehat E_{ADA}=\sum_{n=1}^Nu_n^{(t)}\exp\left(-y_n\eta g_t(\mathbf x_n)\right)， \] $\eta$越大步越好。最佳的$\eta_t$会比固定的$\eta$在短期内下降更快（greedily faster），在最优化中通常称为最速（最陡）下降（steepest descent）。对于分类正确和错误两种情形，$u_n^{(t)}\exp\left(-y_n\eta g_t(\mathbf x_n)\right)$分别为$u_n^{(t)}\exp(-\eta)$和$u_n^{(t)}\exp(+\eta)$，那么有 \[ \widehat E_{ADA}=\left(\sum_{n=1}^Nu_n^{(t)}\right)\cdot \left( (1-\epsilon_t)\exp(-\eta)+\epsilon_t\exp(+\eta) \right)， \] $\epsilon_t$表示错误率。 通过${\partial\widehat E_{ADA}\over\partial\eta}=0$可得最速梯度步长$\eta_t=\ln\sqrt{1-\epsilon_t\over\epsilon_t}=\alpha_t$。当进行到$t+1$轮迭代时，误差为 \[ \widehat E_{ADA}^{(t+1)}=\widehat E_{ADA}^{(t)}\cdot\left( (1-\epsilon_t)\exp(-\eta_t)+\epsilon_t\exp(+\eta_t) \right)， \] 将$\eta_t$和$\widehat E_{ADA}^{(1)}=\sum_{n=1}^Nu_n^{(1)}=1$带入可得 \[ \widehat E_{ADA}^{(t+1)}=\prod_{\tau=1}^{t}\left(2\sqrt{\epsilon_\tau(1-\epsilon_\tau)}\right)。 \] 由此可见，最糟糕的情况是当$\epsilon_t={1\over 2}$时（错误率$\epsilon_t$始终小于正确率$1-\epsilon_t$），$\widehat E_{ADA}^{(t+1)}$不减少，否则$\widehat E_{ADA}^{(t+1)}$随着迭代增加不断减少。
因此，AdaBoost是近似的函数梯度（functional gradient）最速下降法。
任意误差函数的梯度提升
AdaBoost可以表示为最优化的形式 \begin{equation} \min_\eta\min_h{1\over N}\sum_{n=1}^N\exp\left(-y_n\left(\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau(\mathbf x_n)+ \eta h(\mathbf x_n)\right)\right)， \end{equation} 每一轮找到$h$作为$g_t$，并决定该$g_t$要前进的距离$\eta_t$。利用更一般的误差函数，将AdaBoost推广到GradientBoost \begin{equation} \min_\eta\min_h{1\over N}\sum_{n=1}^Nerr\left(\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau(\mathbf x_n)+ \eta h(\mathbf x_n),y_n\right)。 \end{equation} GradientBoost分为两步：（1）确定$h$；（2）确定$\eta$。由于要采用梯度下降法，需要平滑的误差函数$err$，$h$也不限于二分类，可以推广到实数输出。通过采用不同的误差函数$err$，GradientBoost可实现回归、soft分类等功能。
梯度提升决策树
对于回归问题，采用误差函数$err(s,y)=(s-y)^2$，令$s_n=\sum_{\tau=1}^{t-1}\alpha_\tau g_\tau(\mathbf x_n)$可得
\begin{equation}
\min_\eta\min_h{1\over N}\sum_{n=1}^N\left(s_n+
\eta h(\mathbf x_n)-y_n\right)^2，
\label{eq:min-gradientboost-regression-Ein}
\end{equation}
内层最小化
\[
\begin{aligned}
\min_h\ldots
&\overset{\mbox{taylor}}{\approx}\min_h\left({1\over N}\sum_{n=1}^N\underbrace{err(s_n,y_n)}_{\mbox{constant}}+{1\over N}\sum_{n=1}^N\eta h(\mathbf x_n)\left.{\partial err(s,y_n)\over\partial s}\right\rvert_{s=s_n}\right)\\
&\overset{\quad\quad}{=}\min_h\left(\mbox{constants}+{\eta\over N}\sum_{n=1}^N2h(\mathbf x_n)(s_n-y_n)\right)。
\end{aligned}
\]
如果对$h$无约束条件，那么$h(\mathbf x_n)=-\infty\cdot(s_n-y_n)$时取最小值。事实上，只需要$h$的方向，$h$的大小（magnitude）通过步长$\eta$控制。利用拉格朗日乘子法的思想，避免求解复杂的约束优化问题，惩罚大的$h$
\[
\begin{aligned}
&\min_h\left(\mbox{constants}+{\eta\over N}\sum_{n=1}^N\left(2h(\mathbf x_n)(s_n-y_n)+(h(\mathbf x_n))^2\right)\right)\\
\Longleftrightarrow&\min_h\left(\mbox{constants}+{\eta\over N}\sum_{n=1}^N\left(\mbox{constant}+(h(\mathbf x_n)-(y_n-s_n))^2\right)\right)。
\end{aligned}
\]
去掉常数项，带惩罚的近似函数梯度是数据集$\{(\mathbf x_n,y_n-s_n)\}$上，基于平方误差的回归。$y_n-s_n$表示期望的值与目前能达到的值之间的差异，表示尚未达到的部分，称为余数（residual）。好的$h(\mathbf x_n)$需要弥补余数的差距。
［1/2］因此，GradientBoost的回归问题就是通过余数上的回归找到$g_t=h$。
当$g_t$确定后，继续\eqref{eq:min-gradientboost-regression-Ein}的外层最小化 \[ \min_\eta{1\over N}\sum_{n=1}^N(s_n+\eta g_t(\mathbf x_n)-y_n)^2\Leftrightarrow\min_\eta{1\over N}\sum_{n=1}^N((y_n-s_n)-\eta g_t(\mathbf x_n))^2， \] 这是单变量的线性回归，非常容易求解， \begin{equation} \eta={\sum_{n=1}^Ng_t(\mathbf x_n)(y_n-s_n)\over\sum_{n=1}^Ng_t^2(\mathbf x_n)}。 \label{eq:gbdt-eta} \end{equation}
［2/2］因此，GradientBoost的回归问题通过单变量回归求解最优作为步长$\alpha_t=\eta$。
梯度提升决策树（GBDT，gradient boosted decision tree）
初始化$s_1=s_2=\ldots=s_N=0$；
对于$t=1,2,\ldots,T$，循环执行：
- 利用$\mathcal A(\{(\mathbf x_n,y_n-s_n)\})$得到$g_t$，其中$\mathcal A$是基于平方误差的回归算法（例如C&RT）；
- 利用\eqref{eq:gbdt-eta}更新步长$\alpha_t=\mbox{OneVarLinearRegression}(\{(g_t(\mathbf x_n),y_n-s_n)\})$；
- 更新$s_n\leftarrow s_n+\alpha_tg_t(\mathbf x_n)$；
返回$G(\mathbf x)=\sum_{t=1}^T\alpha_tg_t(\mathbf x)$。
GBDT就是AdaBoost决策树的回归版本。
