本文旨在梳理 Boosting方法相关的概念及理论推导。 在介绍Boosting方法之前，我们应该对机器学习模型的误差分析有所了解。从经典的Boosting算法—标准Adaboost的原理入手建立Boosting算法的基本理解，再来分析GBDT的原理(下文的GBDT特指(Greedy Function Approximation：A Gradient Boosting Machine )提出的算法)及其变体XGBoost和Lightgbm后续文章再讲。
机器学习中的误差，偏差与方差
误差反映的是整个模型的准确度，偏差反映的是一个模型在样本上的输出与真实值之间的误差，即模型本身的精准度，方差反映的是模型每一次输出结果与模型输出期望之间的误差，即模型的稳定性/泛化能力。 偏差和方差的概念粗略的表示为训练误差和|训练误差-测试误差|。偏差过大表现为过拟合，方差过大表现为过拟合。
集成方法是将几种机器学习技术组合成一个预测模型的元算法，以达到减小方差(过拟合)（bagging）、偏差（boosting）或改进预测（stacking）的效果。
Boosting算法
boosting算法是通过多个弱学习器串联提升成为强分类器，通常为加法模型和前向分布算法，核心为下级弱学习器修正上级学习器的偏差。
问题：为什么多个弱分类器串联在一起可以提升模型的能力减小偏差而不出现过大方差？ boosting算法要求的基分类器不是没有条件的！首先，基分类器需要一定的的可靠性，其次基分类器需要具有多样性。然而很多情况下可靠性和多样性难以兼得。
Adaboost
AdaBoost是Adaptive Boosting缩写，是由Yoav Freund和Robert Schapire提出的机器学习元算法。AdaBoost在某种意义上是适应性的，即随后的弱学习器会基于先前分类器分类错误的样本增加权重。AdaBoost对噪声数据和异常值敏感。在某些问题中，它可能比其他学习算法更不容易受到过拟合问题的影响。基学习器可能很弱，但只要每个学习者的表现好于随机猜测，最终的模型可以融合成表现优异的强分类器。
Adaboost算法有多种推导方法[1]，比较容易理解的就是基于加性模型(additive model),即基学习器的线性组合来最小化指数损失函数。 \[
l_{exp}(H|D)=E_{x-D}[e^{-f(x)H(x)}]···········(1)
\]
\[ H(x) = \sum_{t=1}^{T}\alpha_th_t(x)···········(2) \\ 其中,T表示弱学习器个数，\alpha_t表示第t个学习器的权重，h_t(x)表示第t个学习器的输出 \] Adaboost的核心思想：1. 给错误分类的样本增加权重，让随后的分类器可以有偏的输出；2. 给各个基学习器加上权重。那么怎么给，有什么依据？
Adaboost算法描述：
输入：训练集\(D={(x_1,y_1),(x_2,y_2),···,(x_m,y_m)}\),其中\(y_i\in [-1,1]\)
基学习器f；
迭代次数T；
(1) 初始化样本权重\(W_1(x)=\frac{1}{m}\)
(2)迭代T次(for)，算出每个模型的误差\(e_t = \sum_{i=1}^{M}I(y_i\ne h_t(x_i))\)
(3)if \(\epsilon >0.5\)then break
(4)更新\(\alpha_t=\frac{1}{2}ln(\frac{1-e_t}{e_t})\)
(5)更新样本新权重\(W_t(x)=\frac{W_{t-1}exp(-\alpha_{t-1}h_{t-1}y_i)}{Z_{t-1}},其中Z_{t-1}=\sum_{}^{}W_{t-1}\)
输出：\(H(x)=sign(\sum_{t=1}^{T}\alpha_th_t(x))\)
问题：显然按照这个算法流程，标准的adaboost实现的是二分类，那么多分类，回归任务需要改进。这仅仅是adaboost的一个应用。
adaboost理论推导的俩个核心：在界定了错误率\(\epsilon_t\)的情况下,求解或者估计\(\alpha_t\)和新的分布\(W_t\)使指数损失函数最小。
- \(\alpha_t\)的求解
\[ l_{exp}(H|W)=E_{x-W}[e^{-f(x)H(x)}]=p_{x-W}(f(x)=h_t(x))e^{-\alpha_t}+p_{x-W}(f(x)\ne h_t(x))e^{\alpha_t}=e^{-\alpha_t}(1-\epsilon_t)+e^{\alpha_t}\epsilon_t \]
\[ \frac{\nabla \ell_{exp}(H|W)}{\nabla\alpha_t}=-e^{-\alpha_t}(1-\epsilon_t)+e^\alpha_t\epsilon_t \]
令\(\frac{\nabla l_{exp}(H|D)}{\nabla\alpha_t}=0\)可解得： \[ \alpha_t=\frac{1}{2}ln\frac{1-\epsilon_t}{\epsilon_t} \]
- \(W_t\)的求解
Adaboost的算法核心是在上一个学习器的基础上，对错误分类的样本权重进行向上调整，使其在后面的学习中更被关注。这个地方我们就要说到模型的多样性的重要了。某个样本在一些弱分类器上的表现不好，就在其他分类器上还可能获得增强，然后加性融合时其可获得较低的偏差。然是如果他在所有弱分类器上的表现都不好，那么加性模型也难以修正其偏差，多样性是boost算法一个需要的重要的属性。
在基分类器\(h_t(x)\)时的模型损失函数表达为： \[ \ell_{exp}(H_{t-1}+h_t(x)|W_t)=E_{x-W}[e^{-f(x)(H_{t-1}(x)+h_t(x))}]=E_{x-W}[e^{-f(x)H_{t-1}(x)}e^{-f(x)h_t(x))}] \] 对二分类，将\(e^{-f(x)h_t(x)}\)的二阶泰勒展开带入损失函数近似可得： \[ \ell_{exp}(H_{t-1}+h_t{x}|W)=E_{x-W}[e^{-f(x)H_{t-1}(x)}(\frac{3}{2}-f(x)h_t(x))] \] 最理想情况在当前模型(\(H_{t}(x)\))的损失函数最小(即\(h_t(x)\)纠正了\(H_{t-1}(x)\))的条件下求解\(W_t\)。
即： \[ h_t(x)=\arg\min_{h}\ell_{exp}(H_{t-1}(x)+h_t(x)|W) = \arg\min_{h}E_{x-W}[e^{-f(x)H_{t-1}(x)}(\frac{3}{2}-f(x)h_t(x))]\\= \arg\max_{h}E_{x-W}[e^{-f(x)H_{t-1}(x)}f(x)h_t(x)] \] \(f(x)和H_{t-1}(x)\)已知。令： \[ W_t=\frac{W(x)e^{-f(x)H_{t-1}(x)}}{E_{x-W}[e^{-f(x)H_{t-1}(x)}]} \] \[ 理想的基分类器：h_t(x)=\arg\max_{h}E_{x-W}[W_tf(x)h_t(x)]=\arg\min_{h}E_{x-W_t}[I(f(x) \ne h_t(x))] \]
\(h_t(x)\)在分布\(W_t\)下仍然可以达到最小分类误差。
GDBT
吐槽：GDBT真的是太难理解了！如果只从概念上知道GDBT用不断的加基模型减小残差，那可能并没有完全理解GDBT。GDBT模型怎么加的？怎么分类的？输入是多维的构建树的过程是什么样的？
GDBT的基分类器是CART回归树，GDBT是通过不断地最小化残差来实现加法模型，其中梯度提升的本质是每一次建立模型是在之前建立模型损失函数的梯度下降方向 。梯度提升树在结构化数据上的具有优越性，如推荐系统和计算广告里面。
GDBT在处理回归问题时的残差其实就在最小平方损失函数的负梯度方向，即： \[ r_{mi}=-\frac{\partial[\frac{1}{2}(y_i-f_m(x_i))^2]}{\partial f_m(x_i)}=y_i-f_m(x_i) \] 常见的损失函数即负梯度方向：
上面的叙述说明，残差是负梯度方向的一个例子，GDBT将梯度下降法的优化概理念从参数空间的优化扩展到函数空间的优化。熟悉神经网络的同学应该知道，标准的神经网络是在一个模型上迭代的更新参数\(\theta^{*}\)以达到损失函数最小的期望；在GDBT算法中拓展到函数空间是如何优化的呢？
浓缩一下：一个变，一个不变！
一个变：基CART回归树的拟合目标\(y^*\)是在变的，它是上个CART回归树的负梯度(残差)。
一个不变： 每个样本的ground truth是不变的。
GDBT算法：
输入：\((x_i,y_i)_{i=1}^{i=N}\)，迭代次数M，损失函数$$
输出：\(F(x)=\sum_{j=1}^{j=M}f_j(x)\)
1. 学习第一棵树得到残差： \[ r_{mi}=-\left[\frac{\partial L\left(y,f\left(x_i\right)\right)}{\partial f\left(x_i\right)}\right]_{f\left(x\right)=f_{m-1}\left(x\right)} \] 注：初始化第一棵树的负梯度方向（后面的要拟合的\(y_i\)）
2. for m =2:M do:
2.1 拟合上一棵树棵树的残差，计算输出响应\(y_{mi}\):\(y_{i}=[\frac {\partial \ell(y_i,F(x_{i}))}{\partial {F(x_{i})}}]_{F_(x)=F_{m-1}(x)}\)
2.2 学习第m棵树： \(\gamma^*=\arg\min_{w} \sum_{x_i \in R_m}^{}\ell (y_i,F_{m-1}(x_i)+\gamma)\),即利用线性搜索(line search)估计叶结点区域的值，使损失函数极小化 。
2.3 更新树： \[ F_m\left(x\right)=F_{m-1}\left(x\right)+\sum_{j=1}^{J}{\gamma{mj}I\left(x\in R_{mj}\right)},其中J是叶节点 \] 3. 训练结束，输出： \[ \hat{F}\left(x\right)=F_M\left(x\right)=\sum_{m=1}^M{\sum_{j=1}^J{\gamma_{mj}I\left(x\in R_{mj}\right)}} \] ——
参考：
- 周志华,《机器学习》
- jerome H.Friedman,Greedy Function Approximation：A Gradient Boosting Machine
- 陈天奇，XGBoost 与 Boosted Tree
