算法拾遗：XGBoost

本文介绍XGBoost的基本思想。

一个包含KKK树棵的集成模型中，每棵树的预测结果是一个实数值（回归树），如果我们把每棵树看作是一个函数fkf_kfk​，则对于样本xix_ixi​的预测结果为这些树的输出之和： y^i=ϕ(xi)=∑k=1Kfk(xi)\hat y_i=\phi(x_i)=\sum_{k=1}^K f_k(x_i)y^​i​=ϕ(xi​)=k=1∑K​fk​(xi​) 我们的目标就是求解最优的KKK棵树。

对于树模型来说，假设有TTT个叶子结点，每棵树会把输入xxx映射到某一个叶子结点q(x)q(x)q(x)上，并输出该叶子节点上预设的值wq(x)w_{q(x)}wq(x)​。上面用qqq来表示一棵树形成的独特映射（将输入映射到叶子结点），而www表示叶子结点上的值向量，这二者实际上就代表了一棵树。

现在我们考虑这样一个模型的损失函数： L(ϕ)=∑il(y^i,yi)+∑k=1KΩ(fk)L(\phi)=\sum_il(\hat y_i,y_i) + \sum_{k=1}^K \Omega(f_k)L(ϕ)=i∑​l(y^​i​,yi​)+k=1∑K​Ω(fk​) 其中第一项为所有样本上的误差之和，比如平方误差；后一项为正则项，用于限制每棵树的复杂度，复杂度越大惩罚越大，其定义为： Ω(fk)=γT+12λ∣∣w∣∣2\Omega(f_k)=\gamma T+\frac{1}{2} \lambda ||w||^2Ω(fk​)=γT+21​λ∣∣w∣∣2 可以看到其实际上为叶子节点数量TTT与权重www的平方和的加权和。

我们使用迭代的策略来一棵一棵计算上面的树模型，假设在第ttt轮添加的树对应函数为ftf_tft​，则在前t−1t-1t−1棵树已经确定的情况下，损失函数为： L(ϕt)=∑il(y^i(t−1)+ft(xi),yi)+Ω(ft)L(\phi_t)=\sum_i l(\hat y_i^{(t-1)}+f_t(x_i),y_i)+\Omega(f_t)L(ϕt​)=i∑​l(y^​i(t−1)​+ft​(xi​),yi​)+Ω(ft​) 其中y^i(t−1)\hat y_i^{(t-1)}y^​i(t−1)​为前t−1t-1t−1棵树的预测结果。我们需要在第ttt轮计算一棵最小化L(ϕt)L(\phi_t)L(ϕt​)的树，贪心地加入到模型中。

上面式中，变量为ft(xi)f_t(x_i)ft​(xi​)，我们将函数l(y^i(t−1)+ft(xi),yi)l(\hat y_i^{(t-1)}+f_t(x_i),y_i)l(y^​i(t−1)​+ft​(xi​),yi​)在y^i(t−1)\hat y_i^{(t-1)}y^​i(t−1)​处展开到二阶泰勒来近似： l(y^i(t−1)+ft(xi),yi)≈l(y^i(t−1),yi)+gift(xi)+12hift2(xi)l(\hat y_i^{(t-1)}+f_t(x_i),y_i)\approx l(\hat y_i^{(t-1)},y_i)+g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)l(y^​i(t−1)​+ft​(xi​),yi​)≈l(y^​i(t−1)​,yi​)+gi​ft​(xi​)+21​hi​ft2​(xi​) 其中gig_igi​和hih_ihi​分别是损失函数l(a,yi)l(a, y_i)l(a,yi​)在a=y^i(t−1)a=\hat y_i^{(t-1)}a=y^​i(t−1)​处的一阶和二阶导数。

经过近似，我们去掉式中的常量部分，即l(y^i(t−1),yi)l(\hat y_i^{(t-1)},y_i)l(y^​i(t−1)​,yi​)，将需最小化的损失函数修改为： L(ϕt)≈∑i=1n[gift(xi)+12hift2(xi)]+γT+12λ∑j=1Twj2L(\phi_t)\approx \sum_{i=1}^n[g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i)]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^Tw_j^2L(ϕt​)≈i=1∑n​[gi​ft​(xi​)+21​hi​ft2​(xi​)]+γT+21​λj=1∑T​wj2​ 现在我们已经将ftf_tft​单独拿了出来，现在考虑∑ift(xi)\sum_i f_t(x_i)∑i​ft​(xi​)是什么？

如果q(xi)=jq(x_i)=jq(xi​)=j，那么ft(xi)=wjf_t(x_i)=w_jft​(xi​)=wj​，因此假如集合IjI_jIj​是所有被树映射到叶子节点jjj的样本集合，即Ij=i∣q(xi)=jI_j={i| q(x_i)=j}Ij​=i∣q(xi​)=j，那么： ∑ift(xi)=∑j=1Twj∣Ij∣\sum_if_t(x_i)=\sum_{j=1}^T w_j|I_j|i∑​ft​(xi​)=j=1∑T​wj​∣Ij​∣ 因此损失函数可以变化为： L(ϕt)=∑j=1T[(∑i∈Ijgi)wj+12(λ+∑i∈Ijhi)wj2]+γTL(\phi_t)=\sum_{j=1}^T \big[(\sum_{i\in I_j} g_i)w_j+\frac{1}{2}(\lambda+\sum_{i\in I_j}h_i)w_j^2\big]+\gamma TL(ϕt​)=j=1∑T​[(i∈Ij​∑​gi​)wj​+21​(λ+i∈Ij​∑​hi​)wj2​]+γT 上面的式子中，我们可以很快看出每个叶子结点的权值wjw_jwj​的最优取值为： wj∗=−∑i∈Ijgiλ+∑i∈Ijhiw_j^*=-\frac{\sum_{i\in I_j} g_i}{\lambda+\sum_{i\in I_j}h_i}wj∗​=−λ+∑i∈Ij​​hi​∑i∈Ij​​gi​​ 上式中，IjI_jIj​取决于当前树的结构，而其余部分均为已知的常值，也就是说，如果第ttt棵树的结构确定下来了，那么叶子节点的输出也可以按照上式直接计算出来。

我们将www代入损失函数： L(ϕt)=−12∑j=1T(∑i∈Ijgi)2λ+∑i∈Ijhi+γTL(\phi_t)=-\frac{1}{2}\sum_{j=1}^T \frac{(\sum_{i\in I_j} g_i)^2}{\lambda+\sum_{i\in I_j}h_i}+\gamma TL(ϕt​)=−21​j=1∑T​λ+∑i∈Ij​​hi​(∑i∈Ij​​gi​)2​+γT 上式给出了一个确定结构的回归树加入后整个模型的损失函数，我们需要构造一棵最小化上式的树。

我们考虑迭代方式构造树，从根节点开始尝试对叶子结点增加分支，假如对叶子结点jjj增加分支，对映射到该结点的样本再进行划分，将IjI_jIj​划分为IlI_lIl​和IrI_rIr​，作为新的两个叶子结点，而其余结点没有变化，那么新树的损失函数为： Lnew=γ+L+12((∑i∈Ijgi)2λ+∑i∈Ijhi−(∑i∈Ilgi)2λ+∑i∈Ilhi−(∑i∈Irgi)2λ+∑i∈Irhi)L_{new}=\gamma + L +\frac{1}{2}\Big(\frac{(\sum_{i\in I_j} g_i)^2}{\lambda+\sum_{i\in I_j}h_i}-\frac{(\sum_{i\in I_l} g_i)^2}{\lambda+\sum_{i\in I_l}h_i}-\frac{(\sum_{i\in I_r} g_i)^2}{\lambda+\sum_{i\in I_r}h_i}\Big)Lnew​=γ+L+21​(λ+∑i∈Ij​​hi​(∑i∈Ij​​gi​)2​−λ+∑i∈Il​​hi​(∑i∈Il​​gi​)2​−λ+∑i∈Ir​​hi​(∑i∈Ir​​gi​)2​) 显然，我们希望划分后产生的新树的损失函数最小，实际上就是要找到一个最优的划分，使得上式最小化，如果把对应结点的式子看作该结点的score，那么就是需要新结点的score之和最大。如果上式最小化后，Lnew>=LL_{new}>=LLnew​>=L，则显然在结点jjj处不可再划分了。

一种简单的划分办法就是遍历所有可能的划分点，假设输入的样本xxx具有ddd维的特征，一共有nnn个样本，那么对每一种特征，首先对其进行排序，而后遍历这nnn个样本的n−1n-1n−1种划分，计算新树的score，确定最优划分点。时间复杂度为O(dnlgn)O(dnlgn)O(dnlgn)。这种算法比较精确，当然比较慢，有一些近似算法可以给出一些划分点的proposal以减少遍历的次数，不过比较复杂这里就不阐述了。

以上是xgboost（实际上是gradient boosting tree）的基本思想，通过上述算法即可针对样本集构造出一个集成树模型，后续就是系统实现的问题了，本文不涉及。