其中的$L(\Theta)$表示训练误差，衡量当前机器学习模型与训练数据的拟合程度，训练误差越低表示模型拟合得越好，但并不一定代表模型的泛化能力就强，因为很有可能是因为模型在训练数据集上过拟合导致的。$\Omega(\Theta)$表示模型正则化项，衡量了模型本身的复杂程度。在“以简为美”的理念下，一般更倾向于选择简单的模型，认为越简单的模型越可能是数据真正的规律。同时优化这两项，就可以找到模型复杂度和模型对训练数据拟合程度之间的一个tradeoff。
对于有$K$棵树的GBDT模型来说，可以定义模型的损失函数如下：
$$Obj(\Theta)=\sum_{i=1}^{N}l(y_i,\hat{y_i})+\sum_{k=1}^{K}\Omega(f_k)$$
其中$\hat{y_i}=\sum_{k=1}^{K}f_k(x_i)$表示模型对样例$i$的预测值，$y_i$则表示样例$i$的标签。$\Omega(f_k)$表示第$i$棵树的复杂度。可以说以上的定义合乎情理，同时考虑了模型的拟合程度和树模型的总复杂度。
如何定义每棵树的拟合函数$f_k$呢？我们以陈天奇PPT里的图为例：
$f_k(x)=w_{q(x)}$，$w \in \mathbb{R}^T$，$T$为叶子节点个数，$q(x)$将样例映射到叶子节点。$f_k(x)$将每个样例映射到叶子节点，并且赋予一定的权重，但并没有定义树形结构，所以在后面优化时只能采取启发式的方法构建树。
在XGBoost中，定义单棵树的正则化项为：
$$\Omega(f_k)=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2}$$
第一项为树的叶子节点个数，第二项为所有叶子节点分数的$L2$正则化项。
很明显，以上定义的损失函数并不能直接求导，所以也就不能直接使用SGD等梯度下降算法进行求解，GBDT是一种可行的解法。
实际上，可以将GBDT看成是一种加法训练模型，在第$k$轮时，模型函数由第$k-1$轮和当前轮的拟合函数相加构成，也即:
$$\hat{y_i}^{(k)}=\hat{y_i}^{(k-1)}+f_k(x_i)$$
所以，可以改成损失函数为：
$$Obj^{(k)}=\sum_{i=1}^{N}l\left(y_i,\hat{y_i}^{(k)}\right)+\sum_{i=1}^{k}\Omega(f_i)=\sum_{i=1}^{N}l\left(y_i,\hat{y_i}^{(k-1)}+f_k(x_i)\right)+\Omega(f_k)+const$$
考虑最简单的平方误差，损失函数改写为：
$$Obj^{(k)}=\sum_{i=1}^{N}\left[y_i-(\hat{y_i}^{(k-1)}+f_k(x_i))\right]^2+\Omega(f_k)+const=\sum_{i=1}^{N}\left[2(\hat{y_i}^{(k-1)}-y_i)f_k(x_i)+f_k(x_i)^2\right]+\Omega(f_k)+const$$
回忆一下泰勒展开公式，二阶泰勒展开式为：
$$f(x+\Delta{x})\simeq f(x)+f'(x)\Delta{x}+\frac{1}{2}f''(x)\Delta{x}^2$$
那么目标损失函数可以改写为：
$$Obj^{(k)}\simeq \sum_{i=1}^{N}\left[l(y_i,\hat{y_i}^{(k-1)})+g_if_k(x_i)+\frac{1}{2}h_if_k^2(x_i)\right]+\Omega(f_k)+const$$
其中，
$$g_i=\frac{\partial l(y_i,\hat{y_i}^{(k-1)})}{\partial \hat{y_i}^{(k-1)}}$$
$$h_i=\frac{\partial^2 l(y_i,\hat{y_i}^{(k-1)})}{\partial (\hat{y_i}^{(k-1)})^2}$$
移除常数项，得到:
$$Obj^{(k)}=\sum_{i=1}^{N}\left[g_if_k(x_i)+\frac{1}{2}h_if_k^2(x_i)\right]+\Omega(f_k)$$
如果叶子节点$j$里的样例集合用$I_j$表示，可以改成损失函数如下所示：
$$Obj^{(k)}=\sum_{i=1}^{N}\left[g_if_k(x_i)+\frac{1}{2}h_if_k^2(x_i)\right]+\Omega(f_k)=\sum_{i=1}^{N}\left[g_iw_{q(x_i)}+\frac{1}{2}h_iw_{q(x_i)}^2\right]+\gamma T+\lambda \frac{1}{2}\sum_{j=1}^{T}w_j^2=\sum_{j=1}^{T}\left[(\sum_{i\in I_j}g_i)w_j+\frac{1}{2}(\sum_{i \in I_j}h_i+\lambda)w_j^2\right]+\gamma T$$
令$G_j=\sum_{i\in I_j}g_i, H_j=\sum_{i \in I_j}h_i$，则：
$$Obj^{(k)}=\sum_{j=1}^{T}\left[G_jw_j+\frac{1}{2}(H_j+\lambda)w_j^2\right]+\gamma T$$
如果上式中当前树形结构已经确定，那么可以在每个叶子节点优化权重，可以得到：
$$w_j^*=-\frac{G_j}{H_j+\lambda}$$
$$Obj=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^2}{H_j+\lambda}+\gamma T$$
$Obj$评价了一棵树的好坏，值越小树模型越好。但是问题来了，如果构建这棵树呢？构建树的方式似乎可以有很多很多种，遍历所有的树形结构肯定是不可取的。回想一下在我们最开始学二叉树的时候，知道树是一层一层地构建出来的，这里其实也可以定义一个切分规则，采用一种启发式的方法，从上到下，一层层地将树结构构建出来。
决策树ID3采用信息增益划分节点，回归树使用基尼指数划分节点，这里可以根据损失函数来定义节点划分标准：
$$Gain=\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}-\gamma$$