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二分类算法
• 深入理解GBDT多分类算法