最终预测:
\[\hat{y}_i = \sum_{k=1}^{K}f_{k}(x_i)\]其中$x_i$为第$i$个样本，$\hat{y}_i$为预测值，$k$为树的索引，$f_k$为第$k$颗树预测，定义loss为
\[\text{obj}^{(t)} = \sum_{i=1}^n {l(y_i, \hat{y}_i^t)} + \sum_{i=1}^t{\Omega(f_i)}\]其中$\Omega$为树的复杂度，是正则化项防止过拟合。又因为对第$t$颗树来说，前面的树已经固定，因此
\[\text{obj}^{(t)} = \sum_{i=1}^n{l(y_i, \hat{y}_i^{(t-1)}+f_t(x_i))} + \Omega(f_t) + \text{constant}\]进行泰勒级数展开
\[\text{obj}^{(t)} = \sum_{i=1}^n [l(y_i, \hat{y}_i^{(t-1)}) + g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t) + \mathrm{constant}\]其中
\[\begin{aligned}g_i &= \partial_{\hat{y}_i^{(t-1)}} l(y_i, \hat{y}_i^{(t-1)})\\ h_i &= \partial_{\hat{y}_i^{(t-1)}}^2 l(y_i, \hat{y}_i^{(t-1)})\end{aligned}\]由于对第$t$颗树来说，前面的树已经固定，因此$l(y_i, \hat{y}_i^{(t-1)})$也为常数项，去掉常数项后：
\[\text{obj}^{(t)} = \sum_{i=1}^n [g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i)] + \Omega(f_t)\]由于对CART树来说，任一输入都对应一个叶子节点，因此可以定义为：
\[f_t(x) = w_{q(x)}, w \in R^T, q:R^d\rightarrow \{1,2,\cdots,T\} .\]其中$w$是树叶的权重，把$T$个叶子编码成$1,2,\cdots,𝑇$，对应的权重是$𝑤_1,𝑤_2,\cdots,𝑤_𝑇$。而函数$q(x)$是决策函数，它把输入$𝑥\in𝑅_𝑑$映射都某个叶子(的下标)。
可以定义CART树的复杂度为：
\[\Omega(f) = \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2\]根据上面的定义，树的叶子越多(从而节点也越多，因为节点个数=2*叶子数-1)，复杂度越高，此外权重越大也越复杂，参数$\lambda$用来控制这两者的比重。
带入得损失函数为：
\[\begin{aligned}\text{obj}^{(t)} &= \sum_{i=1}^n [g_i w_{q(x_i)} + \frac{1}{2} h_i w_{q(x_i)}^2] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2\\ &= \sum^T_{j=1} [(\sum_{i\in I_j} g_i) w_j + \frac{1}{2} (\sum_{i\in I_j} h_i + \lambda) w_j^2 ] + \gamma T\end{aligned}\]其中$I_j = \{i | q(x_i)=j \}$，表示落到节点$j$的样本$i$组成的集合，定义
\[G_j = \sum_{i\in I_j} g_i \\ H_j = \sum_{i\in I_j} h_i\]则$G_j$表示所有落到节点$j$的导数之和，$H_j$是二阶导数之和。$G$和$H$只依赖于树的结构$q$，而不依赖于节点的权重$w$，损失函数进一步化简为
\[\text{obj}^{(t)} = \sum^T_{j=1} [G_jw_j + \frac{1}{2} (H_j+\lambda) w_j^2] +\gamma T\]假设树的结构是固定的，则：
\[\begin{aligned}w_j^\ast &= -\frac{G_j}{H_j+\lambda}\\ \text{obj}^\ast &= -\frac{1}{2} \sum_{j=1}^T \frac{G_j^2}{H_j+\lambda} + \gamma T\end{aligned}\]理论上应该遍历所有的树结构分别算出损失，并找到对应损失最小的树的结构，实际上树的结构没法全部穷举，因此使用贪心算法，并不能保证全局最优，定义分裂的Gain为：
\[Gain = \frac{1}{2} \left[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma\]其实就是分裂前的loss减去分裂后的loss，从所有的分裂方式中选择Gain最大的那个，如果最大的Gain是小于零的，就可以停止分裂了。也就是说分裂减少的误差还不足以弥补模型变复杂带来的损失，那么就没有必要在分裂下去了。
