> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/ji-qi-xue-xi/ensemble-model/boosting-ji-ben-gai-nian/ti-sheng-shu-mo-xing.md).

# 提升树模型

## 提升树

在介绍梯度提升模型之前, 首先引入提升树模型. 顾名思义, 提升树模型就是以分类树或回归树为基本分类器的提升方法.

具体来说, 采用**加法模型**(即基函数的线性组合)与**前向分步算法**作为提升手段, 以**决策树为基函数**的提升方法称为提升树.

### 加法模型

加法模型(Additive Model)即基函数的线性组合, 假设$$b(x;\gamma\_{m})$$为基函数, $$\gamma\_{m}$$为基函数的参数, $$\beta\_{m}$$为基函数的加权系数, 加法模型表达如下:

$$f(x) = \sum\_{m=1}^{M} \beta\_{m} b(x;\gamma\_{m})$$

### 前向分布算法

给定训练数据和损失函数$$L(Y, f(x))$$, 学习加法模型$$f(x)$$, 就是一个损失函数极小化的问题:

$$\min *{\left(\beta*{m}, \gamma\_{m}\right)} \sum\_{i=1}^{N} L\left(y\_{i}, \sum\_{m=1}^{M} \beta\_{m} b\left(x\_{i} ; \gamma\_{m}\right)\right)$$

使用**前向分布算法**求解这一优化问题. 思路是: 由于学习的是加法模型, 如果能够从前向后, 每步只学习一个基函数及其系数, 逐步减小损失函数的大小, 解决优化问题. 即**每步**只需要优化如下的损失函数:

$$\min *{(\beta, \gamma)} \sum*{i=1}^{N} L\left(y\_{i}, \beta b\left(x\_{i} ; \gamma\right)\right)$$

给定训练集$$T=\left{\left(x\_{1}, y\_{1}\right),\left(x\_{2}, y\_{2}\right), \ldots,\left(x\_{N}, y\_{N}\right)\right}, x\_{i} \in X \subseteq R^{n}, y\_{i} \in Y={-1,+1}$$, 损失函数为$$L(Y, f(x))$$, 基函数的集合为$${b(X;\gamma)}$$, 学习加法模型$$f(x)$$的前向分布算法步骤如下:

* 初始化加法模型$$f\_{0}(x)$$
* 依次生成$$M$$个基函数, 对$$m=1,2,\cdots,M$$
  * 极小化损失函数: $$\left(\beta\_{m}, \gamma\_{m}\right)=\operatorname{argmin}*{\beta, \gamma} \sum*{i=1}^{N} L\left(y\_{i}, f\_{m-1}\left(x\_{i}\right)+\beta b\left(x\_{i} ; \gamma\right)\right)$$, 得到参数$$\beta\_{m}$$和$$\gamma\_{m}$$
  * 更新加法模型: $$f\_{m}(x)=f\_{m-1}(x)+\beta\_{m} b\left(x ; \gamma\_{m}\right)$$
* 得到最终的加法模型: $$f(x)=f\_{M}(x)=\sum\_{m=1}^{M} \beta\_{m} b\left(x ; \gamma\_{m}\right)$$

因此, 前向分布算法, 将寻找整体的加法模型, 拆分为依次寻找每个基模型参数$$\gamma\_{m}$$和其加权参数$$\beta\_{m}$$的问题. 而前向分布算法的关键点在于如何**极小化损失函数**, 从而得到一个新的基函数这一步.

### 提升树模型

以决策树为基函数加法模型称为提升树. 记决策树为$$T\left(x ; \Theta\_{m}\right)$$, 提升树记为:

$$f\_{M}(x)=\sum\_{m=1}^{M} T\left(x ; \Theta\_{m}\right)$$

在前向分布算法的第$$m$$步, 给定当前模型$$f\_{m-1}(x)$$, 需求解第$$m$$棵树的参数$$\hat{\Theta}\_{m}$$:

$$\hat{\Theta}*{m}=\operatorname{argmin}*{\left(\Theta\_{m}\right)} \sum\_{i=1}^{N} L\left(y\_{i}, f\_{m-1}\left(x\_{i}\right)+T\left(x\_{i} ; \Theta\_{m}\right)\right)$$

**对于回归问题**:

如果使用的损失函数是**平方误差函数**$$L(y,f(x))=(y-f(x))^2$$时, 损失函数变为:

$$L\left(y, f\_{m-1}(x)+T\left(x ; \Theta\_{m}\right)\right)=\left\[y-f\_{m-1}(x)-T\left(x ; \Theta\_{m}\right)\right]^{2}=\left\[r-T\left(x ; \Theta\_{m}\right)\right]^{2}$$

其中的$$r=y-f\_{m-1}(x)$$, 是当前模型拟合结果的**残差**(residual). 因此, 当前基模型只需要拟合之前累积得到的加法模型预测的残差, 就可以最小化损失函数.

**对于分类问题**

如果使用的损失函数是**指数损失函数**$$L(y,f(x))=e^{-yf(x)}$$. 那么损失函数就变为:

$$
\begin{aligned}
\Theta\_{m} &= \arg \min *{\Theta*{m}} \sum\_{i=1}^{N} e^{\left.-y\_{i}\left(f\_{m-1}\left(x\_{i}\right)+T\left(x\_i ; \Theta\_{m}\right)\right)\right)} \\
&= \arg \min *{\Theta*{m}} \sum\_{i=1}^{N} w\_{mi} e^{-y\_{i}T\left(x\_i ; \Theta\_{m}\right)}
\end{aligned}
$$

在求最小对应的参数过程中, 将常数部分化为$$w\_{mi}=e^{-y\_{i}f\_{m-1}(x\_i)}$$.

在$$\sum\_{i=1}^{N} w\_{mi} e^{-y\_{i}T\left(x\_i ; \Theta\_{m}\right)}$$中, $$T\left(x\_i ; \Theta\_{m}\right)$$此时是分类树, 因此有$$y\_i$$与$$T\left(x\_i ; \Theta\_{m}\right)$$的值域都为$${-1,+1}$$, 只要两者同号相等, 损失就越小.

因此根据上式, 第$$m$$步的基函数, 就是以$$w\_{mi}$$为每个样本的权重, 拟合一个分类决策树.

而如果给这里的分类提升树中, 每个基函数都加上一个系数$$\alpha\_{m}$$, 这就是**Adaboost**算法. 因此可以说Adaboost算法就是以**指数损失函数**为目标损失函数的提升树.

## 参考资料

* [深入理解提升树（Boosting tree）算法](https://zhuanlan.zhihu.com/p/84139957)
* [一文弄懂AdaBoost、提升树、残差树、GDBT](https://zhuanlan.zhihu.com/p/59751960)