参考资料
XGBoost: A Scalable Tree Boosting System
非常好的教学视频，在此将内容整理如下。
目标函数
Boosting是多个弱分类器叠加，每一棵树拟合前面所有树加和与目标值的残差（递归定义）。假设共K棵树，\(f_k \sim F\)
\[obj = \sum_{i=1}^{n}{l(y_i, \hat{y_i})} + \sum_{k=1}^{K}{\Omega(f_k)}\]
后一项为树的复杂度，需要参数化；前一项为损失函数累积，损失函数的形式可以是指数或Squared error等等。
假设已知树的形状，在训练第K棵树时，前面的 K-1 都已知。目标函数中去除掉先前累计的常量。
\[\begin{aligned}obj &= \sum_{i=1}^{N}{l(y_i, \sum_{j=1}^{K-1}{f_{j}(x_i)}+f_{K}(x_i))} + \Omega(f_K)\\ &= \sum_{i=1}^{N}{l(y_i, \hat{y_i}^{(k-1)}+f_{K}(x_i))} + \Omega(f_K)\end{aligned}\]
其中 \(\hat{y_i}^{(k-1)}\) 表示累计到前 K-1 棵树时的估计值。复杂度只计第 K 棵树。可以发现，损失函数中包含了前面的累积量，导致不能进一步简化。使用二阶泰勒展开。
泰勒近似
\[f(x+\Delta x) \approx f(x) + f'(x) \Delta x + \frac{f''(x)}{2} (\Delta x)^2\]
将 \(l(y_i, \hat{y_i}^{(k-1)}+f_{K}(x_i))\) 看作关于估计量 \(\hat{y_i} ^{(k-1)}\) 的函数，最后一棵树提供的 \(f_{K}(x_i)\) 看作增量， 则
\[\begin{aligned}l(y_i, \hat{y_i}^{(k-1)}+f_{K}(x_i)) &\approx l(y_i, \hat{y_i}^{(k-1)}) + l'(y_i, \hat{y_i}^{(k-1)})f_{K}(x_i) + \frac{l''(y_i, \hat{y_i}^{(k-1)})}{2}(f_{K}(x_i))^2\\ &=l(y_i, \hat{y_i}^{(k-1)}) + g_if_{K}(x_i)+ h_if_{K}^2(x_i)\end{aligned}\]
其中 \(g_i, h_i\) 分别是 \(l(y_i, \hat{y_i}^{(k-1)})\) 对 \(\hat{y_i}^{(k-1)}\) 的一阶二阶导，都是已知参数。
再对目标函数做简化，去掉常数项
\[\begin{aligned} obj &= \sum_{i=1}^{N}{l(y_i, \hat{y_i}^{(k-1)}+f_{K}(x_i))} + \Omega(f_K) \\ &= \sum_{i=1}^{N}{\bigg(l(y_i, \hat{y_i}^{(k-1)}) + g_if_{K}(x_i)+ \frac{h_i}2f_{K}^2(x_i)\bigg)} + \Omega(f_K) \\ &\to\ \sum_{i=1}^{N}{\bigg(g_if_{K}(x_i)+ \frac{h_i}2f_{K}^2(x_i)\bigg)} + \Omega(f_K) \end{aligned}\]
树的参数化
目前为止对损失函数部分进行了简化，接下来需要对树的复杂度进行研究，需要将树参数化。
这里树的复杂度用两个指标来量化，一个是叶节点的个数 \(T\), 另一个是每个叶节点的值 \(w_i\) 。
定义函数 \(q(x_i) = k\)，表示样本所在叶节点的序号。
定义函数 \(I(j) = \{i| q(x_i) = j\}\), 表示第 j 个叶节点中所有样本的序号集合。
则树的复杂度定义为
\[\Omega(f_k) = \gamma T + \frac12 \lambda \sum_{j=1}^T{w_j^2}\]
目标函数进一步表示为
\[\begin{aligned} obj &= \sum_{i=1}^{N}{\bigg(g_if_{K}(x_i)+ \frac{h_i}2f_{K}^2(x_i)\bigg)} + \Omega(f_K) \\ &=\sum_{j=1}^{T}{\bigg((\sum_{i\in I(j)}{g_i})w_j+ (\sum_{i\in I(j)}{\frac{h_i}2})w_j^2\bigg)} + \gamma T + \frac12 \lambda \sum_{j=1}^T{w_j^2}\\ &=\sum_{j=1}^{T}{\bigg((\sum_{i\in I(j)}{g_i})w_j+ \frac 1 2(\lambda + \sum_{i\in I(j)}h_i)w_j^2 + \gamma \bigg)} \end{aligned}\]
因而目标函数的每一项是关于叶节点值 \(w_j\) 的二项式。整体目标函数优化问题就变成了对各叶节点的取值\(w_j\)的优化问题。
我们知道二项式的critical point \(-\frac{b}{2a}\)。
\[w_j^* = -\frac{\sum_{i\in I(j)}{g_i}}{\lambda + \sum_{i\in I(j)}h_i} = -\frac{G_j}{H_j + \lambda}\]
\[obj^* = -\frac12 \sum_{j=1}^{T}{\frac{G_j^2}{H_j + \lambda}} + \gamma T\]
于是我们有了最优目标值的 closed-form solution。
树的结构
先前求解目标函数的最优值，基于已知树的结构这么一个前提。在不知道树的结构时如何获得全局最优值？
暴力(brute force)解法是遍历各种树结构，求出各自的最优目标函数值，并取全局最优。但遍历树复杂度过高（二叉树的组合数：卡特兰数）。
如果把 \(obj^*\) 作为 Split 的 criterion (代替 Information Gain 或 Gini Impurity)，就可以贪心求解。每次分裂节点，比较新的 \(obj^*\) 和 之前的 \(obj^*\)，最终选取的 split 使 \(obj\) 下降最快。