XGBoost
XGBoost的算法原理
设选择了使用$k$个Tree来拟合数据，XGBoost的原理是使用第一颗树来拟合原始数据，得到$\hat y_1$，然后用$\hat y_1$替换原来的$y$，再用第二颗树来拟合数据。最终的预测结果是每个数的预测结果之和。对于给定的样本点$x_i$，第$k$轮后的总预测值为
$$
\widehat {y}_i{(k)}=\sum_{j=1} f_j(x_i),f_j\in \mathcal{F}
$$
其中，$f_j(x_i)$表示第$j$个软模型的预测值。那么，模型的优化目标就可写成以下形式，
$$
Obj = \sum_{i=1}^{n} \mathcal{L}(y_i,\widehat {y}_i{(k)})+\sum_{j=1}k \Omega(f_j)
$$
其中，$\mathcal{L}(y_i,\widehat {y}_i^{(k)})$表示损失函数，$\Omega(f_j)$表示模型复杂度。模型的迭代过程如下所示
$$
\widehat y_i^{(0)}=0
$$
$$
\widehat y_i^{1}=\widehat y_i^{(0)} + f_1(x_i)
$$
$$
\vdots
$$
$$
\widehat y_i^{k}=\widehat y_i^{(k-1)} + f_k(x_i)
$$
模型的优化目标可以按照以下部分拆分。
$$
Obj=\sum_{i=1}^n \mathcal{L}(y_i,\widehat y_i^{(k-1)} +f_k(x_i)) + \sum_{j=1}^{k-1} \Omega(f_j) +\Omega(f_k)
$$
其中，$\sum_{j=1}^{k-1} \Omega(f_j) $已知，可看作常数，故优化目标可改写为以下形式。
$$
Obj=\sum_{i=1}^n \mathcal{L}(y_i,\widehat y_i^{(k-1)}+f_k(x_i))+\Omega(f_k)
$$
$$
Obj \approx \sum_{i=1}^n [\mathcal{L}(y_i,\widehat y_i^{(k-1)})+\partial_{\widehat y_i^{(k-1)}}(\mathcal{L}(y_i,\widehat y_i^{(k-1)}) \cdot f_k(x_i)+ \frac{1}{2} \partial_{\widehat y_i{(k-1)}}2\mathcal{L}(y_i,\widehat y_i^{(k-1)}) \cdot f_k(x_i)^2]+\Omega(f_k)
$$
令$g_i=\partial_{\widehat y_i^{(k-1)}}(\mathcal{L}(y_i,\widehat y_i^{(k-1)}))$，$h_i=\partial_{\widehat y_i{(k-1)}}2\mathcal{L}(y_i,\widehat y_i^{(k-1)})$
此时，
$$
Obj=\sum_{i=1}^n [g_i \cdot f_k(x_i)+ \frac{1}{2} h_i \cdot f_k(x_i)^2]+\Omega(f_k)
$$
$$
\Omega(f_k)=\gamma \cdot T + \frac{1}{2} \lambda \sum_{j=1}^T\Vert \omega_j \Vert^2
$$
其中，$T$为叶节点个数，$\lambda,\gamma$为超参数，$\omega_j$为叶节点的值。
此时
$$
Obj=\sum_{i=1}^n [g_i \cdot f_k(x_i)+ \frac{1}{2} h_i \cdot f_k(x_i)^2]+\gamma \cdot T + \frac{1}{2} \lambda \sum_{j=1}^T\Vert \omega_j \Vert^2
$$
令$\omega_j$表示叶节点的值，$q(x_i)$表示样本$x_i$所在叶节点位置，所以可以用以下方式表示软模型预测
$$
\omega_{q(x_i)}=f_k(x_i)
$$
于是，优化目标可以改写为
$$
Obj=\sum_{i=1}^n [g_i \cdot \omega_{q(x_i)}+ \frac{1}{2} h_i \cdot \omega_{q(x_i)}^2]+\gamma \cdot T + \frac{1}{2} \lambda \sum_{j=1}^T\Vert \omega_j \Vert^2
$$
$$
I_j={i|q(x_i)=j}
$$
$$
Obj = \sum_{j=1}^T [(\sum_{i \in I_j} g_i) \cdot \omega_j+ \frac{1}{2}(\sum_{i \in I_j} h_j+\lambda) \cdot \omega_j^2]+\lambda T
$$
令$G_j = \sum_{i \in I_j} g_i$，$H_j = \sum_{i \in I_j} h_i$，且均为常数，此时$Obj$可以写为
$$
Obj = \sum_{j=1}^T[G_j \cdot \omega_j+ \frac{1}{2} \cdot(H_j+\lambda) \cdot \omega_j^2]+\gamma T
$$
这是一个一元二次函数，可以求得最优解
$$
\omega_j^* = -\frac{G_j}{H_j+\lambda}
$$
带入$\omega_j^$，求得
$$
Obj^ = - \frac{1}{2} \sum_{j=1}^T \frac {G_j^2}{H_j+\lambda}+\gamma T
$$
那么，如何将这个找到对应的函数呢，也就是每一个小模型。
1、暴力搜索，找寻所有树结构，但是这是超出计算能力了
2、贪心算法
也就是类似于决策树，考虑每一步的信息增益。但这里考虑的信息增益是$Obj$的变化量。、
$$
Gain = Obj_{old}*-Obj_{new}*
$$
这里假设$model_{old}$右侧叶节点包含样本点7、8，左侧包含1、2、3、4、5、6，此时$Obj_{old}^$的值为
$$
Obj_{old}*=-\frac{1}{2}[\frac{(g_7+g_8)2}{h_7+h_8+\lambda} + \frac{(g_1+g_2+\cdots +g_6)^2}{h_1+h_2+\cdots h_6 +\lambda}]+2\gamma
$$
同时，假设根据特征$i$分成的$model_{new}$中，$L$包含1、3、5节点，$R$包含2、4、6节点，此时$Obj_{new}^$的值为
$$
Obj_{new}*=-\frac{1}{2}[\frac{(g_7+g_8)2}{h_7+h_8+\lambda} + \frac{(g_1+g_3+g_5)^2}{h_1+h_3+h_5 +\lambda}+\frac{(g_2+g_4+g_6)^2}{h_2+h_4+h_6 +\lambda}]+3\gamma
$$
$$
Gain = -\frac{1}{2}[\frac{(g_1+g_2+\cdots +g_6)^2}{h_1+h_2+\cdots h_6 +\lambda}-\frac{(g_1+g_3+g_5)^2}{h_1+h_3+h_5 +\lambda}-\frac{(g_2+g_4+g_6)^2}{h_2+h_4+h_6 +\lambda}]-\gamma
$$
$$
Gain=\frac{1}{2}[\frac{G_L^2}{H_L+\lambda} + \frac{G_R2}{H_R+\lambda}-\frac{(G_L+G_R)2}{H_L+H_R+\lambda}]-\gamma
$$
其中，$G_L=g_1+g_3+g_5$，$H_L=h_1+h_3+h_5$，$G_R=g_2+g_4+g_6$，$H_R=g_2+g_4+g_6$
选取最大的$Gain$来进行生成树。