GBDT分类算法

GBDT分类算法

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

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

对数损失函数

似然函数

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

hθ(x)=11+e−F(x)h_{\theta}(x)=\frac{1}{1+e^{-F(x)}}
P(Y=1∣x;θ)=hθ(x)P(Y=0∣x;θ)=1−hθ(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∣x;θ)P(Y=y \mid x; \theta), 即模型预测样本对应标签的概率, 对于二分类任务, 可以记为:

P(Y=y∣x;θ)=(hθ(x))y(1−hθ(x))1−yP(Y=y \mid x; \theta)=\left(h_{\theta}(x)\right)^{y}\left(1-h_{\theta}(x)\right)^{1-y}

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

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

P(Y=y∣x;θ)=∑iKpθ;k(x)ykP(Y=y \mid x; \theta)=\sum_{i}^{K}p_{\theta;k}(x)^{y_k}

pθ;k(x)p_{\theta;k}(x)是模型给出的样本属于第kk类的概率. 在所有yky_k中, 只有yj=1y_j=1, 其余全部为0.

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

J(θ)=∏i=1NP(Y=yi∣xi;θ)=∏i=1N(hθ(xi))yi(1−hθ(xi))1−yiJ(\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(θ)=∑i=1N[yilogh⁡θ(xi)+(1−yi)log⁡(1−hθ(xi))]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(θ)J(\theta), 取J(θ)J(\theta)的相反数, 记为L(θ)L(\theta), 最大化J(θ)J(\theta)等价于最小化L(θ)L(\theta), 最大似然估计转为使用梯度下降法求解.

L(θ)=−1NL(θ)=−1N∑i=1N[yilogh⁡θ(xi)+(1−yi)log⁡(1−hθ(xi))]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(Y=yi∣x;θ)=∏i=1KP(yi∣x)yi=∏i=1Khθ;k(x)yiP\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(θ)=−log⁡P(Y=yi∣x;θ)=−log⁡∏i=1KP(yi∣x)yi=−∑i=1Kyilog⁡(hθ;k(x))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第MM步迭代之后, 生成MM棵树, 组成的学习器为F(x)F(x), 将其带入单个样本的二分类对数损失函数的公式, 有:

y^=hθ(x)=P(Y=1∣x)=11+e−F(x)\hat{y} = h_{\theta}(x)=P(Y=1 \mid x)=\frac{1}{1+e^{-F(x)}}
L(yi,F(xi))=yilog⁡(1+e−F(xi))+(1−yi)[F(xi)+log⁡(1+e−F(xi))]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]

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

rm,i=−∣∂L(yi,F(xi))∂F(xi)∣F(x)=Fm−1(x)=yi−11+e−F(xi)=yi−y^ir_{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}

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

cm,j=arg⁡min⁡c∑xi∈Rm,jL(yi,Fm−1(xi)+c)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)

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

cm,j=∑xi⊂Rm,jrm,i∑xi∈Rm,j(yi−rm,i)(1−yi+rm,i)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算法过程如下:

  • 初始化第一个弱学习器F0(x)=log⁡P(Y=1∣x)1−P(Y=1∣x)F_{0}(x)=\log \frac{P(Y=1 \mid x)}{1-P(Y=1 \mid x)}

  • 依次建立MM棵回归树m=1,2,⋯ ,Mm=1,2,\cdots,M

    • 对于每个样本ii, 计算当前的负梯度rm,i=−[∂L(yi,F(xi))∂F(x)]F(x)=Fm−1(x)=yi−11+e−F(xi)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)}}

    • 使用负梯度拟合出一棵回归树, 共JmJ_m个叶子结点, 第jj个叶子节点记为Rm,jR_{m,j}, 每个叶子节点的输出为cm,j=∑xi⊂Rm,jrm,i∑xi∈Rm,j(yi−rm,i)(1−yi+rm,i)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)}

    • 更新强学习器Fm(x)=Fm−1(x)+∑j=1Jmcm,jI(x∈Rm,j)F_{m}(x)=F_{m-1}(x)+\sum_{j=1}^{J_{m}} c_{m, j} I\left(x \in R_{m, j}\right)

  • 得到最终的学习器FM(x)=F0(x)+∑m=1M∑j=1Jmcm,jI(x∈Rm,j)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中的多分类, 要对每个类别都单独地建模一个回归树, 给某一个分类输出具体值. 因此, 如果是KK分类任务, 最后迭代MM轮, 那么生成的树的总数量为KMKM. 同时, 每个分类的子树独立进行提升, 分类之间相互不影响, 最终得到KK个GBDT, 用来判断样本属于该类的概率, 即第kk类GBDT的输出为Fk(x)F_k(x)

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

P(y=1∣x)=eF1(x)∑i=1keFi(x)P(y=2∣x)=eF2(x)∑i=1keFi(x)……P(y=K∣x)=eFK(x)∑k=1KeFK(x)\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=−∑k=1Kyklog⁡P(yk∣x)=−∑k=1Kyklog⁡eFk(x)∑j=1KeFj(x)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)}}

对应的负梯度为:

−∂L∂Fk=yk−eFk(x)∑j=1KeFj(x)=yk−p(yk∣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)

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

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

参考资料

上一页GBDT回归算法下一页Xgboost

最后更新于

这有帮助吗？