Gradient Boosting Decision Tree

Jun 14, 2016

1. Notations

第个训练样本，其真实的Label为，模型的预测Label为

2. Regression Tree and Ensemble

回归树与决策树一样，非叶节点有决策规则，此外，其叶节点包含一个分数

将单一一个回归树视为一个函数，也就是

将多个回归树的结果Ensemble后也就是最后的

比较常见的一种做法就是

\begin{align} \hat{y}_i=\sum_{k}f_k(x_i) \end{align}

3. Objective

首先确定Model，假设我们有个树

\begin{align} \hat{y}_i = \sum_{k=1}^Kf_k(x_i) \end{align}

设定

\begin{align} Obj=\sum_{i=1}^nl(y_i,\hat{y}_i) + \sum_{k=1}^K \Omega(f_k) \end{align}

上式中的第一项称为training loss，第二项则是complexity of the trees，也就是一般意义上的regularization

比较常见的training loss函数如

\begin{align} l(y_i,\hat{y}_i) &= (y_i - \hat{y}_i)^2 \end{align}

4. Boosting

初始时 每轮训练一颗树，加入到模型中 \begin{align} \hat{y}_i^{(1)} &= \hat{y}_i^{(0)} + f_1(x_i) \\ \hat{y}_i^{(2)} &= \hat{y}_i^{(1)} + f_2(x_i) \\ &…… \\ \hat{y}_i^{(t)} &= \hat{y}_i^{(t-1)} + f_t(x_i) = \sum_{k=1}^tf_k(x_i) \end{align}

在第轮时，我们需要确定如何构造第颗树，也就是

在第轮时，模型的预测结果为

因此

\begin{align} Obj^{(t)}= & \sum_{i=1}^nl(y_i,\hat{y}_i^{(t)}) + \sum_{i=1}^t \Omega(f_k) \\ = & \sum_{i=1}^nl(y_i,\hat{y}_i^{(t-1)} + f_t(x_i)) + \sum_{i=1}^t \Omega(f_k) \\ = & \sum_{i=1}^nl(y_i,\hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) + const \end{align}

5. Refine the Objective

回忆泰勒展开

\begin{align} f(x+\Delta x) \approx f(x) + f’(x)\Delta x + \frac{1}{2}f’'(x)\Delta x^2 \end{align}

得到

\begin{align} Obj^{(t)} &=\sum_{i=1}^nl(y_i,\hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t) + const \\ &\approx \sum_{i=1}^n \left[ l(y_i,\hat{y}_i^{(t-1)}) + \frac{\partial l(y_i,\hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}}f_t(x_i) +\frac{1}{2}\frac{\partial^2 l(y_i,\hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2}f_t^2(x_i) \right] + \Omega(f_t) + const \\ \end{align}

为了简化，令

\begin{align} g_i &= \frac{\partial l(y_i,\hat{y}_i^{(t-1)})}{\partial \hat{y}_i^{(t-1)}} \\ h_i &= \frac{\partial^2 l(y_i,\hat{y}_i^{(t-1)})}{\partial (\hat{y}_i^{(t-1)})^2} \end{align}

于是 \begin{align} Obj^{(t)} &\approx \sum_{i=1}^n\left[ l(y_i,\hat{y}_i^{(t-1)}) + g_if_t(x_i) +\frac{1}{2}h_if_t^2(x_i)\right] + \Omega(f_t) + const \\ &= \sum_{i=1}^n\left[ g_if_t(x_i) +\frac{1}{2}h_if_t^2(x_i)\right] + \Omega(f_t) + const \end{align}

回归树的每个叶节点都与一个分数相关，因此可以将定义为

\begin{align} f_t(x) = w_{q(x)},w\in R^T,q:R^d \rightarrow \{1,2,…,T\} \end{align}

为该回归树的叶节点数量，是树的叶节点对应的分数

树的复杂度，容易想到一个是叶节点数，另一个是叶节点分数的大小

因此，可以定义（非唯一定义）

\begin{align} \Omega(f_t)=\gamma T + \frac{1}{2}\lambda \sum_{j=1}^Tw_j^2 \end{align}

为了进一步化简，我们定义属于叶节点的数据集合为

\begin{align} I_j=\{i | q(x_i)=j\} \end{align}

有

\begin{align} Obj^{(t)} &\approx \sum_{i=1}^n\left[ g_if_t(x_i) +\frac{1}{2}h_if_t^2(x_i)\right] + \Omega(f_t) + const \\ &= \sum_{i=1}^n\left[ g_if_t(x_i) +\frac{1}{2}h_if_t^2(x_i)\right] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^Tw_j^2 + const \\ &= \sum_{i=1}^n\left[ g_iw_{q(x_i)} +\frac{1}{2}h_iw_{q(x_i)}^2\right] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^Tw_j^2 + const \\ &= \sum_{j=1}^T \left[ \left(\sum_{i\in I_j}g_i\right)w_j +\frac{1}{2}\left(\sum_{i \in I_j} h_i\right)w_j^2\right] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^Tw_j^2 + const \\ &= \sum_{j=1}^T \left[ \left(\sum_{i\in I_j}g_i\right)w_j +\frac{1}{2}\left(\lambda + \sum_{i \in I_j} h_i\right)w_j^2\right] + \gamma T + const \end{align}

为了符号简洁，定义

\begin{align} G_j&=\sum_{i\in I_j}g_i \\ H_j&=\sum_{i\in I_j}h_i \end{align}

有

\begin{align} Obj^{(t)} \approx \sum_{j=1}^T \left[ G_jw_j +\frac{1}{2}\left(\lambda + H_j \right)w_j^2\right] + \gamma T + const \end{align}

假设固定，那么每个叶节点对上式的贡献互相独立

由二次函数性质，可以得到最优解为

\begin{align} 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 \end{align}

6. Greedy Learning of the Tree

在说贪心之前，先说一种非常朴素的方法，流程如下

  • 遍历树的所有可能的，计算其在固定的情况下最优的
  • 得到最优的
  • 计算各个叶节点的分数

这个方法显然是不可能实现的，接下来说贪心的方法

从根节点开始，分裂出子节点，假设分出两个子节点，这个过程中Objective的变化为

\begin{align} 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 \end{align}

以此为依据选择最优的特征进行分裂

和普通的决策树相比，其分裂规则由损失函数推导得来

7. Pruning and Regularization

  • Pre-stopping
    • 如果增益为负，提前结束
  • Post-Prunning
    • 使树生长到最大高度后，迭代地剪掉负增益的叶节点

8. Recap

总结一下GBDT的流程

  • 每次迭代新增一棵树
  • 每次迭代开始时，计算所有的
  • 贪心构造新的树
  • 将新树增加到模型中
    • 通常，我们不会严格按照上式增加新树，而是，其中的通常设为。这意味着我们每轮都给下次的迭代留下优化的机会，这通常能缓解过拟合的问题