Boosting(AdaBoost、DBT、GBDT)

Boost算法在我的黑白判项目，动态项目都有用到，而且在实际中也非常常用，是一种非常有效的算法

Boosting

思想：对于一个训练集，弱分类器可以比较容易地学习到比较粗糙的分类问题，而一个复杂的分类问题很难学习。于是我们想到将复杂的分类问题分而治之，由每个弱分类器负责学习一个相对比较简单的分类问题，于是每个弱分类器各有所长，将多个弱分类器组合成一个强分类器，就可以解决复杂分类问题。

具体地，我们在训练集上迭代学习多个弱分类器，每一次迭代学习出一个弱分类器，这个弱分类器对部分样本有较好的分类作用，而对有些样本分类效果很差。于是我们加大分类效果差的样本的权值，降低分类效果好的样本的权值，以学习一个新的弱分类器来分开它们（在整个训练集上学习），它能够较好的分出这些效果较差的样本中的一部分样本。于是为了分开那一部分类效果差的样本，继续迭代$\cdots\cdots$最后以每一个分类器的分类效果为依据，设计弱分类器之间的组合，最终得到强分类器

根据这个思想，Boost方法要考虑两个问题：

①每一轮训练数据的权值（广义的权值，即每个样本重要性）如何改变

②如何将弱分类器组合成一个强分类器

AdaBoost

Adaptive Boost 适应性提升算法

①每一轮训练数据的权值如何改变：根据分类器效果，样本权值直接改变

②如何将弱分类器组合成一个强分类器：分类器加权相加

AdaBoost Algorithm

$T=\{(x_1,y_1),(x_2,y_2),\cdots,(x_N,y_N)\}$，$y_i∈\{-1,1\}$

开始进行第一轮迭代，$m$为迭代轮数

①初始训练集每个样本的权值平均分布，学得第一个弱分类器$G_1$

$D_1=(w_{11},\cdots,w_{1i},\cdots,w_{1N})\quad,w_{1i}=\frac{1}{N}\quad,i=1,2,\cdots,N$

$G_1(x):\mathbb X\to\{-1,+1\}$

②计算分类误差率$e_1$

$$e_1=\sum_{i=1}^N P(G_1(x_i)≠y_i)=\sum_{i=1}^N w_{1i}I(G_1(x_i)≠y_i)$$

③通过$e_1$计算弱分类器$G_1$的权值$\alpha_1$

这个系数既用来作为分类器权重，也用来计算训练集权值

$$\alpha_1=\frac{1}{2}\log\frac{1-e_1}{e_1}$$

这个公式恰好使得在$e=\frac{1}{2}$的时候，$\alpha=0$；$e$越大，则误差越大，就让权值$\alpha$越小。

由于二分类问题的最差情况就是正确率$e≥50\%$，所以这个式子实际上就是使得$\alpha$的值域为$[0,1)$

④通过$\alpha_1$计算新的训练集每个样本的权值，每个样本用$w_{2i}$表示，在权值为$w_2$的训练集（依然是在整个训练集上学习）上学得第二个弱分类器$G_2$

$$w_{2i}=\frac{1}{Z_1}w_{1i}e^{-\alpha_1y_iG_1(x_i)}$$

权值为概率，之和必为1，要归一化

其中$y_iG_1(x_i)=c(u)=\begin{cases} 1\quad,y_i=G_1(x_i)\\ -1\quad,y_i≠G_1(x_i) \end{cases}$。也就是说，[A]如果预测准确，指数部分为负，新的权值减小；如果预测[B]如果预测不准确，指数部分为正，新的权值增加。增加和减少都是$e^{\alpha_1}$倍

⑤进入第二轮迭代，计算$e_2,\alpha_2,G_{3}$

⑥$\cdots$，进入第$m$轮迭代，迭代计算$e_m,\alpha_m,G_{m+1}$

⑦迭代结束后，得到强分类器

$$G(x)=sign(\sum_m\alpha_mG_m(x))$$

---

AdaBoost算法的训练误差分析：略

前向分步算法

具体算法与公式略

思想：因为学习的是加法模型，如果能够从前往后，每一步只学习一个基函数及其系数，逐步逼近优化目标函数式，那么就可以简化优化的复杂度。

AdaBoost算法的前向分布算法解释：AdaBoost算法是前向分步算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数就是指数函数（证略）

Boost方法实质上是使用了加法模型与前向分步算法。

前向分步算法每一步相当于AdaBoost中的每一轮（但具体细节会有差别）

前向分步算法的求解本质是贪心方法

更多地可以通过提升树来理解，提升树就是直接用的前向分布算法。

BDT 提升树

学习DBT需要对CART有深刻掌握

提升树是以决策树为基函数的提升方法。表示为决策树的加法模型：

$$f_{M(x)}=\sum_{m=1}^MT(x;\Theta_m)$$

$T(x;\Theta_m)$表决策树，$\Theta_m$为决策树的参数，$M$为树的个数

树的线性组合可以很好地拟合训练数据，即使输入与输出之间的关系很复杂也如此，于是提升树是一个很高功能的学习算法

于是根据前向分步算法，拟合初始训练数据集学得初始分类器$f_0(x)=T(x;\Theta_0)$，

第$m+1$步的模型为：$f_{m+1}(x)=f_{m}(x)+T(x;\Theta_{m+1})$$\quad ,f_{m}(x)$即为当前第$m$步的已有模型，由上一步第$m-1$步学到

于是通过ERM确定下一个决策树的最优参数：$\hat \Theta_{m+1}=\arg\min_{\Theta_{m+1}}\sum_{i=1}^NL(y_i,f_{m}(x_i)+T(x_i,\Theta_{m+1}))$

根据不同的问题，使用不同的损失函数；回归问题用平方误差，分类问题用指数损失函数；一般决策问题用一般损失函数

①二分类问题：线性分类器为二类分类树（CART分类树）的AdaBoost

②回归问题：基函数是CART回归树

对第$m$步

采用平方误差损失，则$L(y_i,f_{m}(x_i)+T(x,\Theta_{m+1}))=(y_i-f_{m}(x_i)-T(x_i;\Theta_{m+1}))^2$

则第$m$步（轮）第$i$样本的残差$r_{mi}=y_i-f_{m}(x_i)$，这个残差算的当前已有模型（由上一步计算出的当前步）的残差，于是我们要求出下一个新的决策树$T(x;\Theta_{m+1})$，就是去拟合这个残差，以使得损失函数最小化，求得最优参数的决策树$T(x;\hat\Theta_{m+1})$，也可以求出其输出值（回归值，具体怎么求出参考决策树章节）

然后更新分类器$f_{m+1}(x)=f_{m}(x)+T(x;\Theta_{m+1})$ ，完成一次迭代

然后计算下一步$m+1$的残差，拟合下下步$m+2$的模型，更新线性模型$\cdots\cdots$

最后得到的回归问题提升树就为$f_{M(x)}=\sum_{m=1}^MT(x;\Theta_m)$

具体算法略

注意：

①分类器$f_m(x)$函数是用于迭代作用的，最后组合强分类器的时候和它无关，是将每一步迭代得到的决策树$T(x;\Theta_m)$拿来组合。

②为什么要每轮都要累加分类器，计算$f_m(x)$而不像AdaBoost一样每步直接用新学得的弱分类器进行分类？因为除了第一步求得的决策树是拟合训练数据集本身以外，以后每一步求得的决策树拟合的都是残差！而不是训练数据本身！举例：原始训练集 $(2,3,4,5)$，假设拟合得初始决策树：$\begin{cases} 2.5\quad,y_i＜3.5\\ 4.5\quad,y_i≥3.5 \end{cases}$，于是求得第一步的残差$r$为$(-0.5,0.5,-0.5,0.5)$，然后拟合这个残差求得下一步的决策树。所以用$f_m(x)$累加后才是分类器，因为其包含了初始训练集的完整数据，而不是仅是根据残差求得的那个决策树。（这个决策树只对当前步的残差起决策作用）

所谓A拟合B就是让A更接近B

总结（回归问题）：

①每一轮训练数据的权值如何改变：不直接设置权值，而是计算残差

②如何将弱分类器组合成一个强分类器：拟合残差得到的决策树相加

BDT的求解过程一般化就是前向分步算法的求解过程，需要理解，以便后面变形方便使用

GBDT 梯度提升决策树（回归）

GDBT Algorithm

依然基于CART分类器，是回归问题提升树的改进

像前面的平方，指数损失函数都很容易最优化，但对于一般损失函数，如huber损失、quantile损失，每一步求最优化都不容易。于是使用梯度提升（不是梯度上升！梯度依然是下降以求最小损失函数）算法来求解损失函数最优化问题，其是最速下降法（搜索最佳步长的梯度下降法）的近似方法。

在提升树基础上修改：利用损失函数的[负梯度在当前模型的值]替代回归问题提升树算法中的残差

GBRT 几乎可用于所有的回归问题（线性/非线性） 问题O

---

过程：

$m$代表步（轮）数

①初始化：

$$f_0(x)=\arg\min_c\sum_{i=1}^NL(y_i,c)$$

②对该步（轮）每个样本计算[负梯度在当前模型的值=残差的估计]为：（②其实为③的一个步骤）

$$r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m}(x)}$$

推导见下面【②中残差的推导】

③拟合上面计算出的每个样本的[残差]，得到下一步用的新决策树的[结构]：

用这个新决策树对残差学习得到叶结点区域（划分）$R_{mj}\quad,j=1,2,\cdots,J$

这里其实就是极小化损失函数$L(y_{i+1},f_{m+1}(x_i))=L(r_{mi},T(x=特征点与切割点;\Theta_{m+1}))$（中间推导就是残差的推导那儿），以选取新决策树的最优特征和最优划分

[此时只是确定了树的结构，但是还未确定叶子节点中的最优输出值，下一步④中通过最小化损失函数:

$L(y_i,f_{m}(x_i)+c)$，求得每个叶子节点中的输出值，和CART中的算法一样，不同的就在于下面求最优输出值的时候是让输出而不是残差去拟合$y_i$ ，也就是损失函数不一样] 。更多细节见下面的【注意理解】

④对每个划分用线性搜索叶结点区域的最优值（最速下降法），使得损失函数最小化：

$$c_{mj}=\arg\min_c\sum_{x_i∈R_{mj}}L(y_i,f_{m}(x_i)+c)$$ $$更新：f_{m+1}(x)=f_{m}(x)+\sum_{j=1}^Jc_{mj}I(x∈R_{mj})$$

注意这里的表示方法。$I(x∈R_{mj})$就表示了新学得的决策树输出的结构，乘上该区域结点输出值$c_{mj}$，此即在当前步下最终学到的下一步用的新决策树$\sum_{j=1}^Jc_{mj}I(x∈R_{mj})$

⑤最终的强分类器为：

$$\hat f(x)=f_M(x)=\sum_{m=1}^M\sum_{j=1}^Jc_{mj}I(x∈R_{mj})$$

于是新的决策树就去拟合这个残差，其它不变。

---

【注意理解】：这里需要好好回想生成CART回归树的步骤。将CART回归树表达式中是损失函数扩展为任意，则：

$\min_{j,s}[\min_{c_1}\sum_{x_i∈R_1(j,s)}L(y_i,c_1)+\min_{c_2}\sum_{x_i∈R_2(j,s)}L(y_i,c_2)]$

③中就相当于通过拟合残差（也就是该式子损失函数中的拟合$y_i$替换为拟合$r_i$）先求了CART回归树的外围参数最小值$j,s$，即特征选择和划分（回看CART回归生成，遍历选择$j,s$最小化损失函数选最优特征和划分）

④中就是求在划分下，使得损失函数最小的$c$，而这个$c$就是对应划分的残差的回归输出（通过求该划分下的平均值求得，为CART中损失函数中的模型输出值），也就是上面所提到的叶结点区域的值。（回看CART回归生成，在一个划分（结点）内最小化损失函数选择一个最优的输出，使得该划分每个样本的损失最小）

由于前面求得决策树拟合的是残差（除了第一步决策树是拟合的训练集）以得到最优划分结构；下面要去拟合训练集的真实输出还要让新决策树的输出加上从第一颗决策树输出与中间决策树拟合残差输出迭代而来的前$m$步模型输出$f_{m}(x_i)$（第$m$轮），所以某划分的模型实际回归输出为$f_{m}(x_i)+c$。（前向分步算法的基本求法。）所以我们在每轮（第一轮除外）拟合决策树求划分的时候，是拟合残差（③）；但是在求划分得到的叶结点区域的输出值的时候，我们是要去拟合[真实输出值$y_i$]而不是残差，所以是用$f_{m}(x_i)+c$去拟合！得损失函数极值及极值的时候的$c$（④）可以看出③和④损失函数目标不一样。（但是同一个损失函数）

---

【②中残差的推导】：损失函数为（这里是单个样本的损失函数，多个样本加个求和符号即可，求出的每个样本的残差结论不变）

$L(y_{i+1},f_{m+1}(x_i))=L(y_{i+1},f_{m}(x_i)+T(x,\Theta_{m+1}))$，$y$为常数（样本真实输出）

令$x’=\hat f_{m}(x_i)+T(x,\Theta_{m+1})$，对于在$x_0$的泰勒展开：

$f(x)=f(x_0)+\cdots+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R_n(x)$

(此$x’$即为泰勒展开式形式的自变量，为了区分损失函数中的$x$)

则该损失函数在当前模型$\hat f_{m}(x_i)$处进行一阶泰勒展开：

$L(y_{i+1},f_{m+1}(x_i))=L(y_{i+1},f_{m}(x_i)+T(x,\Theta_{m+1}))≈L(y_{i+1},\hat f_{m}(x_i))+\frac{\partial L(y_{i+1},\hat f_{m}(x_i))}{\partial f_{m}(x_i)}(x’-\hat f_{m}(x_i))$

$=L(y_{i+1},\hat f_{m}(x_i))+\frac{\partial L(y_{i+1},\hat f_{m}(x_i))}{\partial f_{m}(x_i)}T(x,\Theta_{m+1})$

所以要使损失函数最低，那么按照梯度下降思想，我们求出梯度，然后只需要令损失函数向梯度反方向增加即可。所以我们让损失函数对要优化的变量$T(x,\Theta_{m+1})$求导（$L(y_{i+1},\hat f_{m}(x_i))$显然为无关项）：

$\nabla L(y_{i+1},f_{m+1}(x_i))=\frac{\partial L(y_{i+1},f_{m+1}(x_i))}{\partial T(x,\Theta_{m+1})}=\frac{\partial L(y_{i+1},\hat f_{m}(x_i))}{\partial f_{m}(x_i)}$，于是我们就要让函数在：

$r_{mi}=-[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m}(x)}$上梯度下降，该负梯度的在当前模型的值即为残差的估计。

---

残差其实是梯度提升中负梯度的一种特例，就是导数的近似值，将损失函数换为平方差损失可以推导出

具体算法略

GDBT分类算法O

如果样本输出类别为$k$，则$y_k=1$；$p_k(x)$表示模型$f(x)$判定$x$属于第$k$类的概率：$p_k(x)=\frac{e^{f_k(x)}}{\sum_{l=1}^Ke^{f_l(x)}}$

注意，对于多分类问题，回归树训练时，会为每一个类别训练一个决策树。

GDBT的正则化

1. 与AdaBoost一样，每个决策树乘上一个弱化系数
2. 对CART树剪枝，降低CART树复杂度
3. 采用子采样，每次随机抽取部分样本（SGBT）

GDBT 损失函数选择

OReason

1. 分类问题

   指数损失函数、对数损失函数

2. 回归问题

   均方差损失函数、绝对损失函数

3. huber损失函数和分位数（quantile）损失函数，也用于回归问题，可以增加回归问题的健壮性，减少异常点对损失函数的影响

GDBT的优缺点

可以处理各种类型的数据，预测准确率高，使用huber和分位数损失函数可以增加回归问题的健壮性（Huber函数 在值为0时也是可微分的 ）

但是由于基学习器存在依赖关系，难以并行化处理，不过通过子采样的SGBT来实现部分并行

后记

1. $I(True)=1,I(False)=0$
2. 更多资料可以看此文 https://blog.csdn.net/zhang15953709913/article/details/84586592
3. 梯度下降法/最速下降法中用的就是加上负梯度（相当于减去梯度）以缩小损失函数，加梯度就越来越大了
4. 这里有一个GDBT回归问题求解的一个例子： https://blog.csdn.net/zpalyq110/article/details/79527653 ，也可以作为自己练习O
5. 表记轮数/步数下标的时候我都是观测的$m,m+1$，可以各自减一改为观测$m-1,m$