AdaBoost算法原理
AdaBoost的基本思想是通过不断修改训练样本的权重来训练新的基学习器，最后将所有基学习器进行加权求和从而得到一个集成模型。即，AdaBoost可以表示为基学习器的加法模型：
$$ \hat y_i = \sum_{k=1}^K \alpha_k G_k(x_i) $$其中$G_k$为第$k$个基学习器，$\alpha_k$为其系数。
以二分类模型为例，将目标变量以±1的形式表示，损失函数定义为指数损失函数，即：
$$ l(y, \hat y) = e^{-y \hat y} $$设第t个基分类器为$G_t(x)$，那么有：
$$ \hat y^{(t)}_i = \hat y^{(t-1)}_i + \alpha_t G_t(x_i) $$其目标函数可以表示为：
$$ \begin{aligned} obj^{(t)} & = \sum_{i=1}^N e^{-y_i \hat y^{(t-1)}_i -y_i\alpha_tG_t(x_i)} \\ & = \sum_{i=1}^N \omega_i^{(t)} e^{-y_i \alpha_tG_t(x_i)} \end{aligned} $$其中$\omega_i^{(t)} = e^{-y_i \hat y^{(t-1)}_i}$是一个常数可以理解为前t-1个基分类器的预测值带入损失函数得到的值。
观察上面的目标函数可以发现，对于任意的大于0的$\alpha_t$，当$y_i = G_t(x_i)$时，$\omega_i^{(t)}$会被乘上一个小于1的值（即$e^{-\alpha_t}$），当$y_i \ne G_t(x_i)$时，$\omega_i^{(t)}$会被乘上一个大于1的值（即$e^{\alpha_t}$）。
因此，第t个基分类器$G_t$的目标函数可以转换为：
$$ obj^{(t)} = \sum_{y_i \ne G_t(x_i)}\omega_i^{(t)} $$这个形式通俗的描述出来就是，对于前t-1个基分类器都预测错误的样本（$\omega_i^{(t)}$较大），在第t个基分类器中就不要再预测错了（不要再让该样本进入$y_i \ne G_t(x_i)$这个集合了）。
接下来需要对$G_t$的系数$\alpha_t$进行求解。对$obj^{(t)} = \sum_{i=1}^N \omega_i^{(t)} e^{-y_i \alpha_tG_t(x_i)}$关于$\alpha_t$求导并令其导数等于0，有：
$$ \sum_{y_i \ne G_t(x_i)} \omega^{(t)}_i e^{\alpha_t} + \sum_{y_i = G_t(x_i)} \omega^{(t)}_i e^{-\alpha_t} = 0 $$于是可以得到：
$$ \alpha_t = {1 \over 2} \log {{\sum_{y_i = G_t(x_i)} \omega^{(t)}_i} \over {\sum_{y_i \ne G_t(x_i)} \omega^{(t)}_i}} $$这里令：
$$ e_t = {\sum_{y_i \ne G_t(x_i)} \omega^{(t)}_i \over \sum_{i=1}^N \omega_i^{(t)}} $$则$\alpha_t$可以写成下面很简洁的形式：
$$ \alpha_t = {1 \over 2} \log {{ 1- e_t} \over e_t} $$这里的$e_t$我们称之为分类误差率。
关于样本权重的求解
上面描述了二分类问题下的AdaBoost算法的推导过程，可以发现在整个过程中最重要的就是$\omega_i^{(t)}$（即样本权重）的求解。它可以理解为前t-1个基分类器的集成模型的预测结果带入损失函数得到的值。
但是在实际的工程化过程中，并不需要每次生成新的基分类器时都去计算前面所有的基分类器得到的集成模型的预测值（这个很明显计算量非常之大）。可以发现：
$$ \begin{aligned} \omega_i^{(t)} & = e^{-y_i \hat y^{(t-1)}_i} \\ & = e^{-y_i (\hat y_i^{(t-2)} + \alpha_{t-1}G_{t-1}(x_i))} \\ & = \omega_i^{(t-1)} e^{-y_i\alpha_{t-1}G_{t-1}(x_i)} \end{aligned} $$即在生成第t个基分类器时使用的样本权重与前t-2个基分类器并无关系，需要做的只是根据第t-1个基分类器的预测值更新第t-1个基分类器中使用的样本权重即可。
大部分的资料在这里的右侧的式子中会加上一个作为规范化因子的分母，目的是让$\sum_{i=1}^N\omega_i^{(t)}$之和为1。同时，规范化后的样本权重在计算分类误差率$e_t$时只需要求解$\sum_{y_i \ne G_t(x_i)} \omega_i^{(t)}$即可。
回归问题下的AdaBoost
关于回归问题下的AdaBoost，找了很久也没有找到算法的推导过程的相关资料，只能通过Improving Regressors using Boosting Techniques这篇文章看到该算法最终的实现方式，总结在这里。
由于回归问题和分类问题下的AdaBoost虽然基本思想是一致的，但是在细节的处理上感觉已经不是一个东西了，所以这里延用论文中使用的数学符号，以免和上面描述的分类问题的AdaBoost混淆。
AdaBoost回归问题算法
对于$N$个样本的训练集，初始化所有样本的权重为1，即对于任意$i$，有样本权重$\omega_i = 1$，之后循环下面的步骤直到平均损失$\bar L$大于0.5（这个约束很重要）。
通过样本权重计算样本被抽样概率$p_i = {\omega_i\ /\ {\sum_{i=1}^N \omega_i}}$。这其实就是一个将样本权重规范化的步骤，$p_i$决定了在基学习器下样本的预测损失以什么样的比例计算到总的损失当中；
构建基学习器$h_t$，并得到在该学习器下的各样本的预测值$y_t^{(p)}(x_i)$；
对于每一个样本，计算其损失：
$$ L_i = L\left[ |y_i - y_t^{(p)}(x_i)| \right] $$这里我们要计算的实际是相对损失，即令$D$为所有样本中损失最大值：
$$ D = \sup |y_i - y_t^{(p)}(x_i)|,\quad i=1,2,...,N $$那么$L_i$可以有下面三种形式：
$$ \begin{aligned} & L_i = {|y_i - y_t^{(p)}(x_i)| \over D} & (linear)\\ & L_i = {(y_i - y_t^{(p)}(x_i))^2 \over D^2} & (square)\\ & L_i = 1 - \exp \left({- |y_i - y_t^{(p)}(x_i)|} \over D \right) & (exponential) \end{aligned} $$计算平均损失：
$$ \bar L = \sum_{i=1}^N L_i p_i $$令$\beta = {\bar L \over {1 - \bar L}}$。很显然，$\bar L$越大，则$\beta$越大，一个小的$\beta$意味着较小的平均损失，也就是我们对该基学习器有着更强的信心。由于我们在一开始就有了平均损失$\bar L$小于0.5的约束，所以这里的$\beta$必然是一个位于0和1之间的数字。
对于每一个样本，更新$\omega_i$为$\omega_i\beta^{1-L_i}$。可以理解为，对于基学习器下相对损失$L_i$小的样本，会通过$\beta^{1-L_i}$对权重进行一个更大的缩放，有点绕口，简单说就是权重会变得更小。
当$\bar L$无法满足一开始的约束（$\bar L<0.5$）或是循环次数达到我们设定的最大值时结束循环，假设循环进行了$T$次，那么我们得到了$T$个基学习器。回归问题下，AdaBoost通过下式得到集成模型的预测值：
$$ h_f = \inf \left\{ y \in Y:\ \sum_{t:h_t \le y} \log\left({1 \over \beta_t}\right) \ge {1\over2} \sum_t \log\left( {1 \over \beta_t} \right) \right\} $$这个式子***抽象，解释如下：
对于样本$i$，$T$个基学习器可以得到$T$个预测值，同时有对应的$T$个关于基学习器的信心的参数$\beta$。将这$T$个基学习器得到的预测值$y_i$按照从小到大排列，即：
$$ y_i^{(1)} < y_i^{(2)} < \ ...\ < y_i^{(T)} $$注意这里的$1,2,...,T$不是得到基学习器的顺序，而是其预测值从小到大排列后的顺序。
计算$\sum_{i=1}^T\log({1 \over \beta_t})$，这里个人认为可以理解为：由于$\beta$越小说明了我们对该基学习器的信心越强，那么$\log({1 \over \beta})$和我们对基学习器的信心就是一个正相关的关系，所有的基学习器的$\log({1 \over \beta})$之和则描述了我们对于集成模型的信心。
然后依次令$t = 1,2,...,T$计算$\sum_{i=1}^t\log({1 \over \beta_t})$直到$\sum_{i=1}^t\log({1 \over \beta_t}) \ge {1 \over 2}\sum_{i=1}^T\log({1 \over \beta_t})$时停止。取此时的$t$对应的基学习器的预测值$y_i^{(t)}$作为该样本的预测值。
很显然，当所有基学习器的$\beta$都相等时，$y_i^{(t)}$就是所有基学习器预测值的中位数，所以上面的求值公式也被称为加权中位数。
AdaBoost的正则化
和GDBT一样，AdaBoost也是通过在基学习器的系数中加上学习率从而达到正则化的目的。
关于AdaBoost的几点思考
纯粹个人思考，没有任何依据…
- 回归问题下的AdaBoost算法中，最后一步为什么不直接对所有基学习器的预测值取加权平均？
感觉使用加权中位数能最大降低离群值的影响。
假设现在有一个离群样本，所有的基学习器都无法对它作出较好的预测，导致该样本的样本权重会越来越大，那么最终会形成一个局面就是，某一个基学习器是为该样本量身打造的。同时，由于其它样本的样本权重几乎接近于0，导致在该基学习器下的$\bar L$会非常之小，这也就意味着集成模型会给该基学习器很强的信心（$\log({1 \over \beta})$）。
这时使用加权平均的话，该离群值会对结果产生很大的影响，但是使用加权中位数的话，就几乎没有影响了。