> 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/gbdt-fen-lei-suan-fa.md).

# GBDT分类算法

## GBDT分类算法

GBDT无论用于分类还是回归, 使用的都是CART回归树. 原因是**GBDT每轮的训练是在上一轮训练模型的负梯度值基础之上训练的**, 这就要求每轮迭代的时候, 弱分类器叶子节点的输出是要拟合负梯度的, 从而达到梯度下降的模拟. 如果直接输出类别, 类别的值没有意义.

而分类任务的真实值就是真实标签, 对于二分类任务, 就是$${0, 1}$$, 而叶子节点的输出是没有限制的, 如果将这两个值通过损失函数联系在一起呢?

### 对数损失函数

#### 似然函数

假设模型的输出为$$F(x)$$, 我们从**概率**的角度, 计算损失. 假设$$h\_{\theta}(x)$$表示二分类结果为1的概率, 因此分类结果为0的概率为$$1 - h\_{\theta}(x)$$:

$$
h\_{\theta}(x)=\frac{1}{1+e^{-F(x)}}
$$

$$
\begin{array}{l}
P(Y=1 \mid x ; \theta)=h\_{\theta}(x) \\
P(Y=0 \mid x ; \theta)=1-h\_{\theta}(x)
\end{array}
$$

**似然函数**为$$P(Y=y \mid x; \theta)$$, 即模型预测样本对应标签的概率, 对于二分类任务, 可以记为:

$$P(Y=y \mid x; \theta)=\left(h\_{\theta}(x)\right)^{y}\left(1-h\_{\theta}(x)\right)^{1-y}$$

$$y$$的取值为$${0, 1}$$, 因此右侧的前面一项对应的是标签为1时的概率, 后面一项是标签为0是对应的概率.

对于多分类任务, 假设有$$k=1,2,\cdots,K$$类, 使用$$y\_k$$表示当前样本的是不是属于第$$k$$类, 假设真是样本是第$$j$$类, 则似然函数为:

$$P(Y=y \mid x; \theta)=\sum\_{i}^{K}p\_{\theta;k}(x)^{y\_k}$$

$$p\_{\theta;k}(x)$$是模型给出的样本属于第$$k$$类的概率. 在所有$$y\_k$$中, 只有$$y\_j=1$$, 其余全部为0.

**对于二分类**, 单个样本的二分类似然函数如上, 将所有样本的概率相乘, 就得到了整个训练集的似然函数:

$$
J(\theta)=\prod\_{i=1}^{N} P\left(Y=y\_{i} \mid x\_{i} ; \theta\right)=\prod\_{i=1}^{N}\left(h\_{\theta}\left(x\_{i}\right)\right)^{y\_{i}}\left(1-h\_{\theta}\left(x\_{i}\right)\right)^{1-y\_{i}}
$$

并处理成对数似然函数:

$$
J(\theta)=\sum\_{i=1}^{N}\left\[y\_{i} \operatorname{logh}*{\theta}\left(x*{i}\right)+\left(1-y\_{i}\right) \log \left(1-h\_{\theta}\left(x\_{i}\right)\right)\right]
$$

使用**最大似然估计**方法优化参数, 想要最大化$$J(\theta)$$, 取$$J(\theta)$$的相反数, 记为$$L(\theta)$$, 最大化$$J(\theta)$$等价于最小化$$L(\theta)$$, 最大似然估计转为使用梯度下降法求解.

$$
L(\theta)=-\frac{1}{N} L(\theta)=-\frac{1}{N} \sum\_{i=1}^{N}\left\[y\_{i} \operatorname{logh}*{\theta}\left(x*{i}\right)+\left(1-y\_{i}\right) \log \left(1-h\_{\theta}\left(x\_{i}\right)\right)\right]
$$

**对于多分类**, 仍然是所有样本相乘, 得到整个训练集的似然函数:

$$
P\left(Y=y\_{i} \mid x ; \theta\right)=\prod\_{i=1}^{K} P\left(y\_{i} \mid x\right)^{y\_{i}}=\prod\_{i=1}^{K} h\_{\theta;k}(x)^{y\_{i}}
$$

并求对数, 再去相反数, 得到多分类情况下的对数损失函数:

$$
L(\theta) = -\log P\left(Y=y\_{i} \mid x ; \theta\right)=-\log \prod\_{i=1}^{K} P\left(y\_{i} \mid x\right)^{y\_{i}}=-\sum\_{i=1}^{K} y\_{i} \log \left(h\_{\theta;k}(x)\right)
$$

### GBDT二分类原理

假设GBDT第$$M$$步迭代之后, 生成$$M$$棵树, 组成的学习器为$$F(x)$$, 将其带入单个样本的二分类对数损失函数的公式, 有:

$$
\hat{y} = h\_{\theta}(x)=P(Y=1 \mid x)=\frac{1}{1+e^{-F(x)}}
$$

$$
L\left(y\_{i}, F\left(x\_{i}\right)\right)=y\_{i} \log \left(1+e^{-F\left(x\_{i}\right)}\right)+\left(1-y\_{i}\right)\left\[F\left(x\_{i}\right)+\log \left(1+e^{-F\left(x\_{i}\right)}\right)\right]
$$

依旧对损失函数求负梯度, 得到:

$$
r\_{m, i}=-\left|\frac{\partial L\left(y\_{i}, F\left(x\_{i}\right)\right)}{\partial F\left(x\_{i}\right)}\right|*{F(x)=F*{m-1}(x)}=y\_{i}-\frac{1}{1+e^{-F\left(x\_{i}\right)}}=y\_{i}-\hat{y}\_{i}
$$

求得每个样本的负梯度后, 决策树拟合的叶子结点的输出值应为:

$$
c\_{m, j}=\underset{c}{\arg \min } \sum\_{x\_{i} \in R\_{m, j}} L\left(y\_{i}, F\_{m-1}\left(x\_{i}\right)+c\right)
$$

在使用对数损失函数的情况下, 解使用近似值:

$$
c\_{m, j}=\frac{\sum\_{x\_{i} \subset R\_{m, j}} r\_{m, i}}{\sum\_{x\_{i} \in R\_{m, j}}\left(y\_{i}-r\_{m, i}\right)\left(1-y\_{i}+r\_{m, i}\right)}
$$

因此完整的二分类GBDT算法过程如下:

* 初始化第一个弱学习器$$F\_{0}(x)=\log \frac{P(Y=1 \mid x)}{1-P(Y=1 \mid x)}$$
* 依次建立$$M$$棵回归树$$m=1,2,\cdots,M$$
  * 对于每个样本$$i$$, 计算当前的负梯度$$r\_{m, i}=-\left\[\frac{\partial L\left(y\_{i}, F\left(x\_{i}\right)\right)}{\partial F(x)}\right]*{F(x)=F*{m-1}(x)}=y\_{i}-\frac{1}{1+e^{-F\left(x\_{i}\right)}}$$
  * 使用负梯度拟合出一棵回归树, 共$$J\_m$$个叶子结点, 第$$j$$个叶子节点记为$$R\_{m,j}$$, 每个叶子节点的输出为$$c\_{m, j}=\frac{\sum\_{x\_{i} \subset R\_{m, j}} r\_{m, i}}{\sum\_{x\_{i} \in R\_{m, j}}\left(y\_{i}-r\_{m, i}\right)\left(1-y\_{i}+r\_{m, i}\right)}$$
  * 更新强学习器$$F\_{m}(x)=F\_{m-1}(x)+\sum\_{j=1}^{J\_{m}} c\_{m, j} I\left(x \in R\_{m, j}\right)$$
* 得到最终的学习器$$F\_{M}(x)=F\_{0}(x)+\sum\_{m=1}^{M} \sum\_{j=1}^{J\_{m}} c\_{m, j} I\left(x \in R\_{m, j}\right)$$

### GBDT多分类原理

GBDT中的多分类, 要对每个类别都单独地建模一个回归树, 给某一个分类输出具体值. 因此, 如果是$$K$$分类任务, 最后迭代$$M$$轮, 那么生成的树的总数量为$$KM$$. 同时, 每个分类的子树独立进行提升, 分类之间相互不影响, 最终得到$$K$$个GBDT, 用来判断样本属于该类的概率, 即第$$k$$类GBDT的输出为$$F\_k(x)$$

对于输出, 使用softmax的逻辑, 每个类别的概率为:

$$
\begin{array}{l}
P(y=1 \mid x)=\frac{e^{F\_{1}(x)}}{\sum\_{i=1}^{k} e^{F\_{i}(x)}} \\
P(y=2 \mid x)=\frac{e^{F\_{2}(x)}}{\sum\_{i=1}^{k} e^{F\_{i}(x)}} \\
\ldots \ldots \\
P(y=K \mid x)=\frac{e^{F\_{K}(x)}}{\sum\_{k=1}^{K} e^{F\_{K}(x)}}
\end{array}
$$

多分类依然使用对数损失函数, 将所有类别的输出进行综合, 单个样本的损失函数为:

$$
L=-\sum\_{k=1}^{K} y\_{k} \log P\left(y\_{k} \mid x\right)= -\sum\_{k=1}^{K} y\_{k} \log \frac{e^{F\_{k}(x)}}{\sum\_{j=1}^{K} e^{F\_{j}(x)}}
$$

对应的负梯度为:

$$
-\frac{\partial L}{\partial F\_{k}}=y\_{k}-\frac{e^{F\_{k}(x)}}{\sum\_{j=1}^{K} e^{F\_{j}(x)}}=y\_{k}-p\left(y\_{k} \mid x\right)
$$

这里样本$$x$$的真实标签为第$$k$$类, 只有这棵树上有负梯度. 考虑整个训练集, 第$$k$$类对应的GBDT, 只使用标签为$$k$$的样本进行更新.

每类个GBDT对应一个二分类, 迭代生成的方法见上.

## 参考资料

* [深入理解GBDT二分类算法](https://zhuanlan.zhihu.com/p/89549390)
* [深入理解GBDT多分类算法](https://zhuanlan.zhihu.com/p/91652813)