【机器学习】XGBoost解析1

初始化

数据集

$D=\{(x_{i}, y_{i})\}\ \ (|D|=\color{red}{n}, x_{i}\in\mathbb{R}^\color{red}{m}, y_{i}\in\mathbb{R})$

• n 代表样本标签数；
• m 代表数据特征数。

预测模型

包含k棵树的预测模型 $\hat y$

$\hat{y}_{i}=\phi(x_{i})=\sum_{k=1}^{K}f_{k}(x_{i}), f_{k}\in \color{red}{F}$

• F 代表由树构成的函数空间：$F=\{f(x)=\color{red}{w}_{\color{red}{q(x)}}\}\ \ (\color{red}{q}:\mathbb{R}^{m}\rightarrow T, \color{red}{w}\in \mathbb{R}^{T})$；
• q 代表x到叶子节点的映射函数；
• w 代表叶子节点的权值。

---

目标函数

$Obj=\sum_{i=1}^nloss(y_i, \hat y_i)+\sum_{k=1}^K\Omega(d_k)$

其中$\sum_{k=1}^K\Omega(d_k)$为模型的正则项，控制着模型的复杂度：

$\Omega(d_t)=\gamma T+\frac12\lambda\sum_{j=1}^T w_j^2$

• $T$ 代表叶子节点数目；
• $\lambda$ 代表叶子的正则系数。

---

二阶泰勒展开损失函数

对损失函数进行二阶泰勒展开

$L^{(t)}\backsimeq\sum_{i=1}^n[l(y_i, \hat y^{t-1})+g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\Omega(f_t)$

其中$g_i$和$h_i$分别为损失函数的一阶导数和二阶导数。

$g_i=\frac{\partial l(y_i, \hat y^{t-1})}{\partial \hat y^{t-1}}$

$h_i=\frac{\partial^2 l(y_i, \hat y^{t-1})}{\partial (\hat y^{t-1})^2}$

移除常数项后的损失函数为：

$\widetilde L^{(t)}=\sum_{i=1}^n[g_if_t(x_i)+\frac12h_if_t^2(x_i)]+\gamma T+\frac12\lambda\sum_{j=1}^T w_j^2$

定义叶子节点映射集合：

$I_{j}=\{i|q(x_i)=j\}$

• j 代表从1到T个叶节点

整理损失函数：

$\widetilde{L}^{(t)}=\sum_{j=1}^{T}[(\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$

最小化对损失函数

将损失函数$\widetilde{L}^{(t)}$对$w_{j}$进行求导

$\frac{\partial \widetilde{L}^{(t)}}{\partial w_{j}}=\sum_{i\in I_{j}}g_{i}+(\sum_{i\in I_{j}}h_{i}+\lambda)w_{j}$

令导数等于0，求得$w_{j}^*$使损失函数最小的最优参数

$w_{j}^*=-\frac{\sum_{i\in I_{j}}g_{i}}{\sum_{i\in I_{j}}h_{i}+\lambda}$

带入损失函数，得到在树为q的情况下损失函数最优值

$\widetilde{L}^{(t)}(q)=-\frac{1}{2}\sum_{j=1}^{T}\frac{(\sum_{i\in I_{j}}g_{i})^{2}}{\sum_{i\in I_{j}}h_{i}+\lambda}+\gamma T$

分裂节点

设

$\begin{aligned} G_j&=\sum_{i\in I_{j}}g_{i}\\ H_j&=\sum_{i\in I_{j}}h_{i} \end{aligned}$

则$\widetilde{L}^{(t)}(q)$可简化为：

$Obj=-\frac{1}{2}\sum_{j=1}^{T}\frac{G_j^{2}}{H_j+\lambda}+\gamma T$

在某个节点j下的分裂前和分裂后的函数：

$Obj_{\text{分裂前}}=-\frac12\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}-\gamma T_{\text{分裂前}}$

$Obj_{\text{分裂后}}=-\frac12[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}]-\gamma T_{\text{分裂后}}$

最后的信息增益：

$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$