GBDT原理与实践-多分类篇

摘要：

GBDT-分类
GBDT-回归
前面两篇文章已经详细介绍了在回归和分类下的GBDT算法。这一篇文章将最后介绍一个多分类任务的GBDT。其过程和二分类的GBDT类似，但是有一个地方有很大的不同，下文将详细的介绍。

正文：

下图是Friedman在论文中对GBDT多分类给出的伪代码：

从代码上看，大致和分类时候的过程一样。最大的不同点在于多了一层内部的循环For。

这里需要注意的是：
1.对于多分类任务，GDBT的做法是采用一对多的策略（详情见文章）。
也就是说，对每个类别训练M个分类器。假设有K个类别，那么训练完之后总共有M*K颗树。
2.两层循环的顺序不能改变。也就是说，K个类别都拟合完第一颗树之后才开始拟合第二颗树，不允许先把某一个类别的M颗树学习完，再学习另外一个类别。

算法6使用的是多分类常用的损失函数：
L({yk,Fk(x)}K1)=−∑Kk=1yklogpk(x)L({yk,Fk(x)}1K)=−∑k=1Kyklogpk(x)
其中pk(x)=eFk(x)∑Kl=1eFl(x)pk(x)=eFk(x)∑l=1KeFl(x)（softmax)
对损失函数求一阶导有：
y~ik=−[∂L({yil,Fl(x)}Kl=1)∂Fk(xi)]{Fl(x)=Fl,m−1(x)}K1=yik−pk,m−1(xi)y~ik=−[∂L({yil,Fl(x)}l=1K)∂Fk(xi)]{Fl(x)=Fl,m−1(x)}1K=yik−pk,m−1(xi)。
叶子节点的更新值为：
γjkm=K−1K∑xi∈Rjkmy~ik∑xi∈Rjkm|y~ik|(1−|y~ik|)γjkm=K−1K∑xi∈Rjkmy~ik∑xi∈Rjkm|y~ik|(1−|y~ik|)

下面以一个简单的数据集说明整个GBDT的流程。

由于我们需要转化3个二分类的问题，所以需要先做一步one-hot：

为了方便说明，作以下设置：
1. 树的深度为1
2. 学习率0.1

首先进行初始化Fk0(xi)=0Fk0(xi)=0，对所有的样本。
注意：在Friedman论文里全部初始化为0，但在sklearn里是初始化先验概率（就是各类别的占比）

对第一个类别（yi=0yi=0)拟合第一颗树(m=1)(m=1)。

利用pk,m(x)=eFk,m(x)∑Kl=1eFl,m(x)pk,m(x)=eFk,m(x)∑l=1KeFl,m(x)

下面计算负梯度值，以x1x1为例(k=1,i=1)(k=1,i=1)：
y~ik=yi,k−pk,m−1y~ik=yi,k−pk,m−1
=>y~11=y1,1−p1,0=1−0.3333=0.6667y~11=y1,1−p1,0=1−0.3333=0.6667
同样地，计算其他样本可以有下表：

以y~i1y~i1拟合一颗回归树，（以31为分裂点）

和前面文章类似，分别计算γjkmγjkm可得：
γ111=1.42857γ111=1.42857，γ211=−0.9999γ211=−0.9999

更新Fkm(xi)=Fk,m−1(xi)+η∗∑xi∈Rjkmγjkm∗I(xi∈Rjkm)Fkm(xi)=Fk,m−1(xi)+η∗∑xi∈Rjkmγjkm∗I(xi∈Rjkm)可得下表：

至此第一个类别（类别0）的第一颗树拟合完毕，下面开始拟合第二个类别（类别1）的第一颗树：

对第二个类别（yi=1yi=1)拟合第一颗树(m=1)(m=1)。

利用pk,m(x)=eFk,m(x)∑Kl=1eFl,m(x)pk,m(x)=eFk,m(x)∑l=1KeFl,m(x)

下面计算负梯度值，以x1x1为例(k=2,i=1)(k=2,i=1)：
y~ik=yi,k−pk,m−1y~ik=yi,k−pk,m−1
=>y~12=y1,2−p2,0=0−0.3333=−0.3333y~12=y1,2−p2,0=0−0.3333=−0.3333
同样地，计算其他样本可以有下表：

以y~i2y~i2拟合一颗回归树，（以6为分裂点）,可计算得到叶子节点：
γ121=2γ121=2，γ221=−0.2499γ221=−0.2499
更新Fkm(xi)=Fk,m−1(xi)+η∗∑xi∈Rjkmγjkm∗I(xi∈Rjkm)Fkm(xi)=Fk,m−1(xi)+η∗∑xi∈Rjkmγjkm∗I(xi∈Rjkm)可得下表：

然后再拟合第三个类别（类别2）的第一颗树，过程也是重复上述步骤，所以这里就不再重复了。在拟合完所有类别的第一颗树后就开始拟合第二颗树。反复进行，直到训练了M轮。

总结

至此，GBDT回归与分类就完整的说了一遍了。在多分类里面不打算分析Sklearn源码是因为其实现和Frieman论文里面步骤有一点不太一样。