梯度提升决策树（Gradient Boosting Decision Tree, GBDT）是一种基于boosting集成学习思想的加法模型，训练时采用前向分布算法进行贪婪学习，每次迭代都学习一棵CART树来拟合之前 t ? 1 t-1 t?1棵树的训练样本真实值的残差。
最小二乘回归算法
输入：训练数据集
D
D
D。
输出：回归树
f
(
x
)
f(x)
f(x)。
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域的输出值，构建二叉决策树：
假设GBDT里有k个CART。其中第k个CART记为
T
k
(
X
)
T_k(X)
Tk?(X)，前k个CART的预测值记为
f
k
(
x
)
=
∑
i
=
1
k
T
i
(
x
)
f_k(x)=\sum_{i=1}^{k}T_i(x)
fk?(x)=i=1∑k?Ti?(x)
GBDT是一种加法模型，它把所有基础模型的预测值累加起来作为最终的预测值，可把前K个CART的预测值表示为一个递归的形式：
f
k
(
x
)
=
f
k
?
1
(
x
)
+
T
k
(
x
)
f_k(x)=f_{k-1}(x)+T_k(x)
fk?(x)=fk?1?(x)+Tk?(x)
训练第k个CART时，最小化目标函数：
J
=
∑
n
=
1
N
L
(
y
n
,
f
k
(
x
n
)
)
=
∑
n
=
1
N
L
(
y
n
,
f
k
?
1
(
x
)
+
T
k
(
x
)
)
J=\sum_{n=1}^{N}L(y_n,f_k(x_n))=\sum_{n=1}^{N}L(y_n,f_{k-1}(x)+T_k(x))
J=n=1∑N?L(yn?,fk?(xn?))=n=1∑N?L(yn?,fk?1?(x)+Tk?(x))
利用梯度下降法：
f
k
(
x
n
)
=
f
k
?
1
(
x
n
)
?
α
?
J
?
f
k
?
1
(
x
n
)
f_k(x_n)=f_{k-1}(x_n)-\alpha \frac{\partial J}{\partial f_{k-1}(x_n)}
fk?(xn?)=fk?1?(xn?)?α?fk?1?(xn?)?J?
T
k
(
x
n
)
=
?
α
?
J
?
f
k
?
1
(
x
n
)
T_k(x_n)=-\alpha \frac{\partial J}{\partial f_{k-1}(x_n)}
Tk?(xn?)=?α?fk?1?(xn?)?J?
通常回归任务中用残差平方和作为目标函数
J
=
∑
n
=
1
N
L
(
y
n
,
f
k
(
x
n
)
)
=
∑
n
?
1
N
1
2
(
y
n
?
f
k
(
x
n
)
)
2
J=\sum_{n=1}^{N}L(y_n,f_k(x_n))=\sum_{n-1}^{N}\frac{1}{2}{(y_n-f_k(x_n))}^2
J=n=1∑N?L(yn?,fk?(xn?))=n?1∑N?21?(yn??fk?(xn?))2
因此有
T
k
(
x
n
)
=
?
α
?
J
?
f
k
?
1
(
x
n
)
=
y
n
?
f
k
?
1
(
x
n
)
T_k(x_n)=-\alpha \frac{\partial J}{\partial f_{k-1}(x_n)}=y_n-f_{k-1}(x_n)
Tk?(xn?)=?α?fk?1?(xn?)?J?=yn??fk?1?(xn?)
也就是说，GBDT的每一颗CART树的任务，是拟合之前所有CART留下的残差。