- GBDT回归算法的基本思路
- 为什么是梯度下降
- 三种损失函数
- GBDT回归算法的一般步骤
- GBDT二分类算法
- 损失函数推导
- GBDT二分类算法步骤
1、给定数据集
D
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
.
.
.
,
(
x
n
,
y
n
)
}
D=lbrace(x_1,y_1),(x_2,y_2),...,(x_n,y_n)rbrace
D={(x1,y1),(x2,y2),...,(xn,yn)}，任务是拟合一个模型
F
(
x
)
F(x)
F(x)来最小化平方误差
1
2
(
y
i
−
F
(
x
i
)
)
2
frac{1}{2}(y_i-F(x_i))^2
21(yi−F(xi))2；
2、当前的
F
(
x
)
F(x)
F(x)还不够好，采用加法模型的策略，叠加上一个新的弱学习器
h
(
x
)
h(x)
h(x)（树回归模型），新模型的拟合结果变为
F
(
x
)
+
h
(
x
)
F(x)+h(x)
F(x)+h(x)；
3、我们期望的是
F
(
x
i
)
+
h
(
x
i
)
=
y
i
F(x_i)+h(x_i)=y_i
F(xi)+h(xi)=yi，等价于
h
(
x
i
)
=
y
i
−
F
(
x
)
h(x_i)=y_i-F(x)
h(xi)=yi−F(x)；当前问题等价于在新的数据集
D
=
{
(
x
1
,
y
1
−
F
(
x
1
)
)
,
(
x
2
,
y
2
−
F
(
x
2
)
)
,
.
.
.
,
(
x
n
,
y
n
−
F
(
x
n
)
)
}
D=lbrace(x_1,y_1-F(x_1)),(x_2,y_2-F(x_2)),...,(x_n,y_n-F(x_n))rbrace
D={(x1,y1−F(x1)),(x2,y2−F(x2)),...,(xn,yn−F(xn))}上拟合一个新模型
h
(
x
)
h(x)
h(x)；
4、
y
i
−
F
(
x
i
)
y_i-F(x_i)
yi−F(xi)就是当前模型的残差，即当前问题等价于用残差作为新的y来拟合一个新的回归树模型
h
(
x
)
h(x)
h(x).
加法模型的表达式：
F m ( x i ) = F m − 1 ( x i ) + h ( x i ) F_m(x_i)=F_{m-1}(x_i)+h(x_i) Fm(xi)=Fm−1(xi)+h(xi)
平方误差损失函数：
J = 1 2 ∑ i = 1 n ( y i − F ( x i ) ) 2 J=frac{1}{2}sum_{i=1}^n(y_i-F(x_i))^2 J=21∑i=1n(yi−F(xi))2
梯度为：
∂ J ∂ F ( x i ) = − ( y i − F ( x i ) ) frac{partial J}{partial F(x_i)}=-(y_i-F(x_i)) ∂F(xi)∂J=−(yi−F(xi))
GB回归树模型的表达式变为：
F m ( x i ) = F m − 1 ( x i ) − ∂ J ∂ F ( x i ) F_m(x_i)=F_{m-1}(x_i)-frac{partial J}{partial F(x_i)} Fm(xi)=Fm−1(xi)−∂F(xi)∂J
一般表达式为：
F m ( x i ) = F m − 1 ( x i ) − ρ ∂ J ∂ F ( x i ) F_m(x_i)=F_{m-1}(x_i)-rhofrac{partial J}{partial F(x_i)} Fm(xi)=Fm−1(xi)−ρ∂F(xi)∂J
一般情况下，使用损失函数负梯度作为新加模型的拟合目标。
三种损失函数1、平方误差损失函数在数学上可以很好地求导处理，但是，平方误差会把误差平方放大，导致一些异常点在新的训练中会被重点关注，可能影响最终模型的性能；下面介绍两个处理异常点时更加鲁棒的损失函数；
2、绝对误差损失函数：
L ( y i , F ( x i ) ) = ∣ y i − F ( x i ) ∣ L(y_i,F(x_i))=|y_i-F(x_i)| L(yi,F(xi))=∣yi−F(xi)∣
负梯度为：
− g ( x i ) = s i g n ( y i − F ( x i ) ) -g(x_i)=sign(y_i-F(x_i)) −g(xi)=sign(yi−F(xi))
3、Huber损失函数：
L ( y i , F ( x i ) ) = { 1 2 ( y i − F ( x i ) ) 2 , ∣ y i − F ( x i ) ∣ ≤ δ δ ( ∣ y i − F ( x i ) ∣ − δ 2 ) , ∣ y i − F ( x i ) ∣ > δ L(y_i,F(x_i))= begin{cases} frac{1}{2}(y_i-F(x_i))^2,|y_i-F(x_i)|leqdelta \ \ delta(|y_i-F(x_i)|-frac{delta}{2}),|y_i-F(x_i)|>delta\ end{cases} L(yi,F(xi))=⎩⎪⎨⎪⎧21(yi−F(xi))2,∣yi−F(xi)∣≤δδ(∣yi−F(xi)∣−2δ),∣yi−F(xi)∣>δ
负梯度为：
− g ( x i ) = { y i − F ( x i ) , ∣ y i − F ( x i ) ∣ ≤ δ δ s i g n ( y i − F ( x i ) ) , ∣ y i − F ( x i ) ∣ > δ -g(x_i)= begin{cases} y_i-F(x_i),|y_i-F(x_i)|leqdelta \ \ delta sign(y_i-F(x_i)),|y_i-F(x_i)|>delta\ end{cases} −g(xi)=⎩⎪⎨⎪⎧yi−F(xi),∣yi−F(xi)∣≤δδsign(yi−F(xi)),∣yi−F(xi)∣>δ
GBDT回归算法的一般步骤Step1: 初始化一个弱学习器
F
0
=
a
r
g
m
i
n
⏟
F
∑
i
=
1
n
L
(
y
i
,
F
)
F_0=underbrace{argmin}_F sum_{i=1}^nL(y_i,F)
F0=F
argmin∑i=1nL(yi,F)，得到各个样本的初始预测值；
Step2：开始迭代计算，from 1 to M do:
-
在第m步中，使用m-1步的预测值，计算每个样本损失函数负梯度值,
− g m ( x i ) = − ∂ L ∂ F ∣ ( m − 1 ) -g_m(x_i)=-frac{partial L}{partial F}|_{(m-1)} −gm(xi)=−∂F∂L∣(m−1) -
训练一棵新的回归树 h m h_m hm来拟合 − g m ( x i ) -g_m(x_i) −gm(xi)
-
计算 h m h_m hm的每个叶子节点的最佳拟合值，
c m j = a r g m i n ⏟ c ∑ i = 1 n L ( y i , F m − 1 + c ) c_{mj}=underbrace{argmin}_csum _{i=1}^nL(y_i,F_{m-1}+c) cmj=c argmin∑i=1nL(yi,Fm−1+c) -
直至满足迭代停止条件，则停止迭代
Step3：最终学习器为M棵树以及每棵树叶子节点的预测值，实施预测时，只需要判断样本在每一棵树里落在哪个叶子节点里，然后将对应每棵树的叶子节点预测值加和，即为最终预测值。
GBDT二分类算法 损失函数推导-
设0/1二分类问题中，预测样本为1类的概率为 y i ^ = 1 1 + e x p ( − F ( x i ) ) hat{y_i}=frac{1}{1+exp(-F(x_i))} yi^=1+exp(−F(xi))1
-
{ P ( y = 1 ∣ x ) = y i ^ P ( y = 0 ∣ x ) = 1 − y i ^ begin{cases}P(y=1|x)=hat{y_i}\ \P(y=0|x)=1-hat{y_i}end{cases} ⎩⎪⎨⎪⎧P(y=1∣x)=yi^P(y=0∣x)=1−yi^
-
P ( y ∣ x i ) = y i ^ y ( 1 − y i ^ ) 1 − y P(y|x_i)=hat{y_i}^{y}(1-hat{y_i})^{1-y} P(y∣xi)=yi^y(1−yi^)1−y
-
似然函数 l = ∏ i = 1 n P ( Y = y i ∣ x i ) = ∏ i = 1 n y i ^ y i ( 1 − y i ^ ) 1 − y i l=prod_{i=1}^nP(Y=y_i|x_i)=prod_{i=1}^nhat{y_i}^{y_i}(1-hat{y_i})^{1-y_i} l=∏i=1nP(Y=yi∣xi)=∏i=1nyi^yi(1−yi^)1−yi
-
对数似然函数 L = ln l = ∑ i = 1 n [ y i ln y i ^ + ( 1 − y i ) ln ( 1 − y i ^ ) ] L=ln l=sum_{i=1}^n[y_iln hat{y_i}+(1-y_i)ln(1-hat{y_i})] L=lnl=∑i=1n[yilnyi^+(1−yi)ln(1−yi^)]
-
设损失函数为 J = − 1 n L J=-frac{1}{n}L J=−n1L，即可使用梯度下降法求似然函数最大值。
-
GBDT的二分类任务实际上就是求F(x)，使J最小
-
损失函数 J = − 1 n ∑ i = 1 n [ y i ln y i ^ + ( 1 − y i ) ln ( 1 − y i ^ ) ] J=-frac{1}{n}sum_{i=1}^n[y_iln hat{y_i}+(1-y_i)ln(1-hat{y_i})] J=−n1∑i=1n[yilnyi^+(1−yi)ln(1−yi^)]
-
假设迭代了m-1步以后，当前学习器为 F m − 1 = ∑ i = 1 m − 1 h i ( x ) F_{m-1}=sum_{i=1}^{m-1} h_i(x) Fm−1=∑i=1m−1hi(x)
-
将 y i ^ = 1 1 + e − F hat{y_i}=frac{1}{1+e^{-F}} yi^=1+e−F1带入损失函数得
J i = − y i ln 1 1 + e x p ( − F ) − ( 1 − y i ) ln e x p ( − F ) 1 + e x p ( − F ) = y i ln ( 1 + e x p ( − F ) ) + ( 1 − y i ) [ F + ln ( 1 + e x p ( − F ) ) ] = ln ( 1 + e − F ) + ( 1 − y i ) F begin{aligned} J_i&=-y_ilnfrac{1}{1+exp(-F)}-(1-y_i)lnfrac{exp(-F)}{1+exp(-F)} \ &= y_iln(1+exp(-F))+(1-y_i)[F+ln(1+exp(-F))]\ &=ln(1+e^{-F})+(1-y_i)F end{aligned} Ji=−yiln1+exp(−F)1−(1−yi)ln1+exp(−F)exp(−F)=yiln(1+exp(−F))+(1−yi)[F+ln(1+exp(−F))]=ln(1+e−F)+(1−yi)F -
当前负梯度（伪残差） r m i = − ∂ J i ∂ F ∣ m − 1 = y i − 1 1 + e − F = y i − y i ^ r_{mi}=-frac{partial J_i}{partial F}|_{m-1}=y_i-frac{1}{1+e^{-F}}=y_i-hat{y_i} rmi=−∂F∂Ji∣m−1=yi−1+e−F1=yi−yi^
-
训练第m棵回归树 h m h_m hm来拟合 r m i r_{mi} rmi
-
给第m棵树的第j个叶子节点确定最佳残差拟合值
c m j = a r g m i n ⏟ c ∑ i J ( y i , F m − 1 ( x i ) + c ) c_{mj}=underbrace{argmin}_c sum_i J(y_i, F_{m-1}(x_i)+c) cmj=c argmin∑iJ(yi,Fm−1(xi)+c) -
求解过程，损失函数的二阶泰勒展开式为：
J ( y i , F m − 1 + c ) = J ( y i , F m − 1 ) + ∂ J ∂ F c + 1 2 ∂ 2 J ∂ F 2 c 2 = c o n s t a n t + [ 1 1 + e − F − y i ] c + 1 2 e − F ( 1 + e − F ) 2 c 2 begin{aligned} J(y_i,F_{m-1}+c)&=J(y_i,F_{m-1})+frac{partial J}{partial F}c+frac{1}{2}frac{partial^2J}{partial F^2}c^2 \ &=constant+[frac{1}{1+e^{-F}}-y_i]c+frac{1}{2}frac{e^{-F}}{(1+e^{-F})^2}c^2 end{aligned} J(yi,Fm−1+c)=J(yi,Fm−1)+∂F∂Jc+21∂F2∂2Jc2=constant+[1+e−F1−yi]c+21(1+e−F)2e−Fc2 -
上式取得极值时，c的取值为
c ∗ = − b 2 a = y i ( 1 + e − F ) 2 − ( 1 + e − F ) e − F = y i − y i ^ y i ^ ( 1 − y i ^ ) = r m i ( y i − r m i ) ( 1 − y i + r m i ) c^*=-frac{b}{2a}=frac{y_i(1+e^{-F})^2-(1+e^{-F})}{e^{-F}}=frac{y_i-hat{y_i}}{hat{y_i}(1-hat{y_i})}=frac{r_{mi}}{(y_i-r_{mi})(1-y_i+r_{mi})} c∗=−2ab=e−Fyi(1+e−F)2−(1+e−F)=yi^(1−yi^)yi−yi^=(yi−rmi)(1−yi+rmi)rmi -
对于第m棵树的第j个叶子节点
c m j = ∑ x i ∈ R m j r m i ∑ x i ∈ R m j ( y i − r m i ) ( 1 − y i + r m i ) c_{mj}=frac{sum_{x_iin R_{mj}}r_{mi}}{sum_{x_iin R_{mj}}(y_i-r_{mi})(1-y_i+r_{mi})} cmj=∑xi∈Rmj(yi−rmi)(1−yi+rmi)∑xi∈Rmjrmi -
最终强学习器为
F M ( x i ) = F 0 ( x i ) + ∑ m = 1 M ∑ j = 1 J m c m j I ( x i ∈ R m j ) F_M(x_i)=F_0(x_i)+sum_{m=1}^Msum_{j=1}^{J_m}c_{mj}I(x_iin R_{mj}) FM(xi)=F0(xi)+∑m=1M∑j=1JmcmjI(xi∈Rmj) -
一般初始学习器 F 0 ( x i ) = ln P ( Y = 1 ∣ x ) 1 − P ( Y = 1 ∣ x ) F_0(x_i)=lnfrac{P(Y=1|x)}{1-P(Y=1|x)} F0(xi)=ln1−P(Y=1∣x)P(Y=1∣x)
