Boosting

个体学习器之间存在强依赖关系，必须串行生成基分类器的方法，提升（boosting）

常见提升算法：Adaboost、GBDT、lightBGM、XGBoost

一、Adaboost

Adaboost是英文“Adaptive Boosting（自适应增强）”的缩写，其自适应在于：前一个基本分类器被错误分类的样本权值会增大（被抽样的概率会增大），而正确分类的样本的权值会减小，并再次用来训练下一个基本分类器。同时，在每一轮迭代中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或者达到预先指定的最大迭代次数才确定最终的强分类器。

思想：将学习器的重点放在“易出错”的样本上。可以提升学习器的性能。

eg：原始训练数据集 {0，1，2，3，4，5，6，7，8，9}

Boosting采样： {7，2，6，7，5，4，8，8，1，0}

{1，3，8，4，3，5，4，0，1，4}

{4，9，4，2，4，4，3，0，1，4}

步骤：1、首先，是初始化训练数据的权值分布D1，假设有N个训练样本数据 $T= \left\{(x_{1}，y_{1}) ,(x_{2}，y_{2}),...,(x_{N}，y_{N}) \right\}$ ，则每个训练样本最开始时，都被赋予相同的权值 $W_{1} = 1/N$ 即 $D_{1} = (w_{1,1},w_{1,2},...,w_{1,i}),w_{1,i} = \frac{1}{N},i = 1,2,...,N$

2、然后，对于 m=1,2,...,M ,使用具有权值分布 $D_{m}$ 训练数据集进行学习，得到弱分类器 $G_{m} (x)$ ，具体的训练过程为：如果某个训练样本点，被弱分类器 $G_{m} (x)$ 准确地分类，那么在构造下一个训练集中，其对应的权值要减小；相反则权值增大。权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。

a、计算 $G_{m} (x)$ 在训练集上的分类误差率：

$e_{m} = \sum_{i=1}^N w_{m,i}I(G_{m}(x_{i})\neq y_{i})$

b、计算 $G_{m} (x)$ 在强分类器中所占的权重：

$\alpha _{m} = \frac{1}{2} \log \frac{1-e_{m}}{e_{m}}$

c、更新训练集的权值分布（这里 $z_{m}$ 是归一化因子，为了使样本的概率分布和为1）

$w_{m+1,i} = \frac{w_{m,i}}{z_{m}} exp(-\alpha _{m}y_{i}G_{m}(x_{i})), i = 1,2,...,10$

$z_{m} = \sum_{i=1}^Nw_{m,i}exp(-\alpha _{m}y_{i}G_{m}(x_{i}))$

3、最后，将各个训练得到的弱分类器组合成一个强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起7着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其起较小的决定作用。

$F(x) = sign(\sum_{i=1}^N \alpha _{m}G_{m}(x))$

以上步骤中的核心问题在于分类器的权重的确定，下面是证明

假设经过m-1伦迭代，得到弱分类器 $F_{m-1}(x)$ ，根据向前分布，有：

$F_{m}(x) = F_{m-1}(x) + \alpha _{m}G_{m}(x)$

Adaboost的代价函数是指数损失，则有：

$Loss = \sum_{i=1}^Nexp(-y_{i}F_{m}(x_{i})) = \sum_{i=1}^Nexp(-y_{i}(F_{m-1}(x_{i})+\alpha _{m}G_{m}(x_{i})))$

对于上式， $F_{m-1}(x)$ 是已知的，所以将其前移

$Loss = \sum_{i=1}^N \tilde{w_{m,i}} exp(-y_{i}\alpha _{m}G_{m}(x_{i}))$

其中： $\tilde{w_{m,i}}$ 是每轮迭代的样本权重，

继续化简

$Loss = \sum_{i=1}^N \tilde{w_{m,i}} exp(-y_{i}\alpha _{m}G_{m}(x_{i})) = \sum_{y_{i}=G_{m}(x_{i})} \tilde{w_{m,i}}exp(-\alpha _{m}) + \sum_{y_{i}=G_{m}(x_{i})} \tilde{w_{m,i}}exp(\alpha _{m})$

$=\sum_{i=1}^N \tilde{w_{m,i}}(\frac{\sum\nolimits_{y_{i}=G_{m}(x_{i})} \tilde{w_{m,i}}} {\sum_{i=1}^N\tilde{w_{m,i}}}exp(-\alpha _{m})+ \frac{\sum\nolimits_{y_{i}\neq G_{m}(x_{i})} \tilde{w_{m,i}}} {\sum_{i=1}^N\tilde{w_{m,i}}}exp(\alpha _{m}) )$

其中 $em= \frac{\sum\nolimits_{y_{i}\neq G_{m}(x_{i})} \tilde{w_{m,i}}} {\sum_{i=1}^N\tilde{w_{m,i}}}$ ，为分类误差率

所以 $Loss = \sum\nolimits_{N}^{i=1} \tilde{w_{m,i}} ((1-e_{m})exp(-\alpha _{m}) + e_{m}exp(\alpha _{m}))$

对 $\alpha _{m}$ 求偏导，并令其为0，则有：

$\alpha _{m} = \frac{1}{2} log\frac{1-e_{m}}{e_{m}}$

Adaboost可以看作是加法模型、代价函数为指数函数、学习算法为前向分布算法时的二分类学习方法

from sklearn.ensembleimport AdaBoostClassifier

# adaboost模型

model = AdaBoostClassifier(DecisionTreeClassifier(max_depth=3),n_estimators=10)

# 训练模型

model.fit(x_data, y_data)

二、GBDT

a、BDT（Boosting Decision Tree）提升树

提升树是以CART决策树为基学习器的集成学习方法

提升树实际上就是加法模型和向前分布算法，将其表示为：

$f_{0}(x)=0$ //初始化提升树

$f_{m}(x) = f_{m-1}+T(x,\theta_{m} )$ // $f_{m}(x)$ 为迭代m次，包含m棵决策树的提升树， $T(x,\theta_{m} )$ 为第m棵决策树

$f_{M}=\sum_{m=1}^MT(x,\theta_{m} )$ //包含M棵决策树的提升树

在前向分布算法第m步时，给定当前的模型 $f_{m-1}(x)$ ，求解：

$min(\sum_{i=1}^N L(y_{i},f_{m-1}(x)+T(x,\theta_{m})))$

$Loss= L(y_{i},f_{m-1}(x)+T(x,\theta_{m}))$

得到第m棵决策树 $T(x,\theta_{m})$ 。不同问题的提升树的区别在于损失函数的不同，比如分类用指数损失函数，回归使用平方误差损失。

当提升树采用平方损失函数时，第m次迭代时表示为：

$L(y_{i},f_{m-1}(x)+T(x,\theta_{m}))=(y-f_{m-1}(x)-T(x , \theta_{m}))^2 = (r-T(x,\theta_{m}))^2$

$r=y-f_{m-1}(x)$ 为残差，所以第m棵决策树 $T(x,\theta_{m})$ 是对该残差的拟合。要注意的是提升树算法中的基学习器CART树是回归树。

输入：训练集D={(x1,y1), (x2,y2),......,(xN,yN)}

1、初始化 $f_{0}(x)=0$

2、For m = 1,2,......,M

3、针对每一个样本 $(x_{i},y_{i})$ 计算残差 $r_{m,i}=y-f_{m-1}(x) ,i=1,2,......,N$

4、利用 $\left\{ (x_{i},r_{m,i}) \right\}_{i=1,2,......,N}$ 训练一个决策树（回归树），得 $T(x,\theta_{m})$

5、更新 $f_{m}(x) = f_{m-1}+T(x,\theta_{m} )$

6、完成以上迭代，得到提升树 $f_{M}=\sum_{m=1}^MT(x,\theta_{m} )$

b、GBDT（Gradient Boosting Decision Tree）梯度提升决策树

GBDT = 梯度提升 + 决策树

利用最速下降的近似方法，利用损失函数的负梯度拟合基学习器：

$-[\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}]_{F(x)=F_{t-1}(x)}$

以Loss为平方损失函数为例

代价函数： $L(y_{i},F(x_{i}))=\frac{1}{2} (y_{i} - F(x_{i}))^2$

对 $F(x_{i})$ 求导，则有：

$\frac {\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})} = F(x_{i}) - y_{i}$

残差r是梯度的相反数，即：

$r_{ti} = y_{i}-F_{t-1}(x)= -[\frac{\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}]_{F_{x}=F_{t-1}(x)}$

在GBDT中使用负梯度作为残差进行拟合。

过程

输入：训练集 $D=\left\{(x_1,y_1),(x_2,y_2),......,(x_N,y_N)\right\}$ , $y_i\in \left\{+1,-1\right\}$

1、初始化： $F_0(x)=arg \ min_{h_0} \sum\nolimits_{i=1}^NL(y_i,h_0(x))$

2、for t=1 to T do

计算负梯度： $\tilde{y_i}= -[\frac{\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}]_{F_{x}=F_{t-1}(x)},i=1,2,...,N$

拟合残差得到基学习器： $w_t = arg\ min_{w_t} \sum\nolimits_{i=1}^N (\tilde{y_i} - h_t(x;w_t))^2$

得到基学习器的权重： $\alpha_t = arg \ min_{\alpha_t} \sum\nolimits_{i=1}^NL(y_i,f_{t-1}(x_i) + \alpha _th_t(x;w_t))$

更新 $F_t(x) = F_{t-1}(x_i) + \alpha _th_t(x;w_t)$

GBDT与提升树的区别是残差使用梯度替代，且每个基学习器有对应的参数权重。

GBDT是使用梯度提升的决策树（CART），CART树回归将空间划分为K个不相交的区域，并确定每个区域的输出 $c_k$ ，数学表达式： $f(x) = \sum_{k=1}^Kc_kI(x\in R_k)$

GBDT的流程（回归）：

输入：训练集 $D=\left\{(x_1,y_1),(x_2,y_2),......,(x_N,y_N)\right\}$ ， $y_i\in \left\{+1,-1\right\}$

1、初始化： $F_0(x)=arg \ min_{h_0} \sum\nolimits_{i=1}^NL(y_i,h_0(x))$ $=arg \ min_{c} \sum\nolimits_{i=1}^NL(y_i,c)$

2、for t=1 to T do

计算负梯度： $\tilde{y_i}= -[\frac{\partial L(y_{i},F(x_{i}))}{\partial F(x_{i})}]_{F_{x}=F_{t-1}(x)},i=1,2,...,N$

拟合残差得到回归树，得到第t棵树的叶节点区域： $h_t(x) = \sum_{k=1}^Kc_kI(x\in R_{tk})$

更新 $F_t(x) = F_{t-1}(x_i) + h_t(x) = F_{t-1}(xi) + \sum_{k=1}^Kc_kI(x\in R_{tk})$

3、得到加法模型： $F(x) = \sum_{t=1}^Th_t(x)$

GBDT的流程（分类）：

仍然使用CART回归树，使用softmax镜进行概率的映射，然后对概率的残差进行拟合

1、针对每个类别都先训练一个回归树，如三个类别，训练三棵树。就是比如对于样本 $x_i$ 为第二类，则输入三棵树分别为 $(x_i,0),(x_i,1)$ ； $(x_i,0)$ 这其实是典型的OneVsRest的多分类训练方式。而每棵树的训练过程就是CART的训练过程。这样，对于样本 $x_i$ 就得出了三棵树的预测值 $F_1(x_i),F_2(x_i),F_3(x_i)$ ，模仿多分类的逻辑回归，用Softmax来产生概率，以类别1为例： $p_1(x_i) = \frac{exp(F_1(x_i))}{\sum\nolimits_{l=1}^3exp(F_l(x_i))}$