面试中一直以来有个热门问题就是：「xgboost 二阶泰勒展开为什么收敛快？」
一般来说网上的背诵答案为：「一阶导数可以找到当前最陡峭的方向，二阶导数可以掌握一阶导数未来的变化信息，等于说二阶导数有更长远的规划。」
但这个答案未免太不优雅了，过于make sense了，缺少一些数学上的严谨性。下面这篇短文来记录一下最近针对这个问题的一些思考。
gbdt 和 xgb 其实都可以用泰来展开来表示，只不过前者是一阶展开，后者是二阶展开，泰勒展开的本质在于在某一点用一堆多项式去模拟原来的函数。如果有了这个共识，那么一阶展开就是只用了一阶信息去模拟，二阶展开就是同时用到了一阶和二阶。一阶展开的公式如下：
f
(
x
+
Δ
x
)
≈
f
(
x
)
+
Δ
x
⋅
∇
f
(
x
)
f(x+\Delta x) \approx f(x)+\Delta x \cdot \nabla f(x)
f(x+Δx)≈f(x)+Δx⋅∇f(x)其中f(x) 可以看做损失函数 loss，
Δ
x
\Delta x
Δx可以看作第 N 步要学出来的那棵子树，右边是泰勒一阶展开。由于我们希望损失是不断下降的，因此有：
f
(
x
+
Δ
x
)
<
f
(
x
)
f(x+\Delta x)
Δ
x
⋅
∇
f
(
x
)
<
0
\Delta x \cdot \nabla f(x)<0
Δx⋅∇f(x)<0对于两个长度固定的向量的点积，当向量的方向完全相反的时候，他们的点积值是最小的，因此最速下降的取值即为梯度的负方向：
Δ
x
=
−
η
∇
f
(
x
)
\Delta x=-\eta \nabla f(x)
Δx=−η∇f(x)刚才说过
Δ
x
\Delta x
Δx可以看作要学的子树，所以这个结果可以理解为当前子树的学习目标为负梯度值。以上可以看出，gbdt 的优化原理其实与泰勒一阶展开后优化思路等价。
————————————————————————————————————
xgb 是二阶展开，详情请看xgboost 原论文翻译，这里不赘述其原理。其二阶展开的公式为：
L
(
t
)
≃
∑
i
=
1
n
[
l
(
y
i
,
y
^
(
t
−
1
)
)
+
g
i
f
t
(
x
i
)
+
1
2
h
i
f
t
2
(
x
i
)
]
+
Ω
(
f
t
)
\mathcal{L}^{(t)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}^{(t-1)}\right)+g_{i} f_{t}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{t}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(f_{t}\right)
L(t)≃i=1∑n[l(yi,y^(t−1))+gift(xi)+21hift2(xi)]+Ω(ft)经过一系列推到，当前子树的学习目标应该为：
w
j
∗
=
−
∑
i
∈
I
j
g
i
∑
i
∈
I
j
h
i
+
λ
w_{j}^{*}=-\frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i}+\lambda}
wj∗=−∑i∈Ijhi+λ∑i∈Ijgi看上去是不是与牛顿法不谋而合，其实其推导路径和牛顿法也是相似的。
二者的区别在于梯度下降法和牛顿法的区别，即一阶泰勒展开和二阶泰勒展开的区别。开头说过，泰勒展开的本质在于在某一点用一堆多项式去模拟原来的函数，一阶展开是用一个平面去模拟，二阶展开是用一个曲面，显然曲面模拟的更准确，所以二阶展开后求下一步优化的方向也更准确。