如何理解Google提出的Regularized Gradient Boosting算法 ...

zt3ff3n

什么是Regularized Gradient Boosting？

Regularized Gradient Boosting（RGB）是NIPS 2019会议中Google的研究者提出的新GBDT算法。相比传统的GBDT算法，RGB直接将模型的泛化误差上界加入到优化项中，并期望通过优化该上界得到更好的GBDT模型。
如何直观理解RGB算法？

这篇文章比较硬核，里面涉及了一点坐标梯度下降、Rademacher Complexity、Lipschitz连续性的内容。当然，介绍这些内容只是为了表明作者的RGB算法有着非常强的理论依据。在实际实现中，RGB算法的实现方式非常简单。
在每一轮GBDT的构建过程中，RGB算法构建多个不同高度和正则系数的决策树，然后根据模型准确率和模型复杂度进行加权，选择一个最合适的决策树加入到最终模型中。粗略看上去，这个算法和使用了正则项之后的XGBoost很像，但是XGBoost的高度或者正则项之类的限制是全局通用的，而RGB则会随着每一轮的准确率情况调整模型复杂度上限。
泛函梯度下降

首先，RGB这篇文章的根基是泛函梯度下降（Functional Gradient Descent）这个思想。简单来说，如果将传统的梯度下降算法理解为在向量空间做梯度下降，那么就可以将GBDT的过程理解为在函数空间做梯度下降。对于一个神经网络，我们可以更新其参数，通过在向量空间做梯度下降降低最终的损失值。而对于一个决策树来说，则可以不断新增决策树，如果将所有可能生成的模型视为一个空间，那么函数空间的梯度下降就是希望以损失函数的梯度作为准则，使得我们能够尽量从整个函数空间内最快找到合适的模型。
GBDT基础

GBDT的目标是通过连续构建多个小模型，最终构建一个大模型 ，从而使得下面的损失函数最小。


具体来说，GBDT就是基于  个训练数据的每条数据在损失函数上的梯度 不断拟合新模型。
一般来说，GBDT都会限制模型  的搜索空间，例如XGBoost经常限制决策树高度不能高于一个阈值。这样的话，优化过程可以视为在模型空间 中找一个与梯度方向距离最小的模型。


进一步来说，上述过程就是找到一个模型  ，使得其预测值和负梯度方向 尽量一致。


GBDT的泛化误差上界

下面这个公式算是整个论文的点睛之笔了，对于单棵不超过 个节点的决策树，假设数据维度为 ，样本数量为  ，那么其Rademacher Complexity的上界如下所示。如果对Rademacher Complexity不甚了解的话，可以将Rademacher Complexity简单理解成对于一个标签完全随机的数据集，决策树能达到的最大准确率。这里  代表所有叶子节点预测值 范数上界 。直观理解的话，如果决策树划分的越深，叶子节点的纯度就越高，这时候 就相对比较大，从而导致Rademacher Complexity也比较大。


根据上面的Rademacher Complexity Bound，我们可以进一步推导出该决策树的泛化误差上界 。首先，第一项可以看出，这个上界跟经验 -margin loss有关，即 。这意味着如果我们的模型在训练集上能把数据分得比较开，那么 就相对较大，此时对应的 就比较小。第二项则跟上面的Rademacher Complexity相关，其中  代表了GBDT每棵决策树前面的系数。


基于随机坐标下降算法的GBDT

目标函数
有了上面的泛化误差上界以后，就可以根据这个泛化误差上界重新确定GBDT的优化目标。第一项代表了经典的GBDT误差，第二项则代表了模型的Rademacher Complexity上界。


因此，在每一轮，生成的决策树 就是所有可能的决策树中能使得上述Loss最小的决策树，而这里的 则代表了一个模型空间。


收敛性证明
在优化过程中，RGB需要同时优化GBDT的每棵决策树  和对应权重  。如果将GBDT的决策树产生视为优化过程（ ），那么对应Loss下降的Lipschitz函数为  。如果将GBDT的权重优化产生视为优化过程（ ），那么对应Loss下降的Lipschitz常数为  。由此，可以得出  和  之间的关系。


而对于随机坐标下降来说，如果选择第 个坐标下降的概率为 ，那么这个优化过程就保证收敛。

代表了样本在叶子节点上预测值的二次方，在这篇论文中，这个值的上限是一个正则化超参数  。但是有时候我们不一定将二次方作为正则化项，上面的  和  之间的关系可以进一步通过Hlder不等式进行变换（即当 时， ）， 的上界可以进一步变换为 。通过改变变换，RGB就可以使用任意的范数作为正则化项。


如果取 和 这一对组合，那么上面的公式变为 。
基于上面的Lipschitz常数，根据随机坐标下降的相关定理，可知第 轮的Loss的期望和最佳Loss之差一定小于右边的上界。这是一个非常好的性质，意味着RGB算法最终是可以收敛的。


训练方法
RGB算法训练过程如下所示。首先，RGB算法采样  个决策树拟合空间（第二行代码），每个拟合空间对应不同限制的决策树。随后，尝试基于负梯度方向 拟合这每棵决策树 （第四行代码）。在实际实现中，我们可以限制决策树的高度。但是对于给定高度的决策树，找到最近似负梯度方向的决策树依然是一个NP-Hard问题。作者并没有细讲这里是如何实现的，不过想来应该是作者直接采用了传统的贪心决策树构造方法，近似得到了一个最优解。
在训练了  棵决策树之后，就可以根据上面的目标函数，从这  棵决策树中选择一棵可以使得损失函数最小的决策树（第六行代码）。值得一提的是，每个决策树训练的时候并没有考虑优化正则项，而这时通过从  棵决策树中选一个最佳的决策树优化最终目标可以看成一个带有一定随机性的优化过程，因此RGB的作者将这个优化过程视为函数空间的随机坐标下降。
值得一提的是，这里的  个决策树空间是从从 个决策树空间中按照概率 随机进行采样得到的（第二行代码）。这个概率分布和上面的Lipschitz常数密切相关，即 。只有当按照这个比例进行采样的时候，整个算法才是随机坐标下降算法，而收敛性最终也才有保证。实际上，函数空间的Lipschitz常数我们是求不出来的，但是这里只需要一个比例，因此就还有解决该问题的希望。在上面的分析中，我们可以看到Lipschitz常数的上界为 。而分子和分母中的 项可以最终消去，因此采样比例最终可以转化为 。这意味着  上界越大的决策树空间，被采样的概率越高。更直观来说，决策树越深，  越大，这意味着RGB中更深的决策树有更大的被采样几率。
最终，将新模型 加入到模型  中，并基于随机坐标下降算法在向量空间更新  ，同时在函数空间更新  （第七行和第八行代码）。


实验结果

从最终的实验结果来看，相比XGBoost，RGB在高维数据上的效果非常不错，但是在低维数据集上没有显著优势。作者表示可能是因为高维数据集更容易出现过拟合问题，因此考虑了正则化的RGB算法可以获得效果更好的模型。

unityloverz

什么是Regularized Gradient Boosting？

Regularized Gradient Boosting（RGB）是NIPS 2019会议中Google的研究者提出的新GBDT算法。相比传统的GBDT算法，RGB直接将模型的泛化误差上界加入到优化项中，并期望通过优化该上界得到更好的GBDT模型。
如何直观理解RGB算法？

这篇文章比较硬核，里面涉及了一点坐标梯度下降、Rademacher Complexity、Lipschitz连续性的内容。当然，介绍这些内容只是为了表明作者的RGB算法有着非常强的理论依据。在实际实现中，RGB算法的实现方式非常简单。
在每一轮GBDT的构建过程中，RGB算法构建多个不同高度和正则系数的决策树，然后根据模型准确率和模型复杂度进行加权，选择一个最合适的决策树加入到最终模型中。粗略看上去，这个算法和使用了正则项之后的XGBoost很像，但是XGBoost的高度或者正则项之类的限制是全局通用的，而RGB则会随着每一轮的准确率情况调整模型复杂度上限。
泛函梯度下降

首先，RGB这篇文章的根基是泛函梯度下降（Functional Gradient Descent）这个思想。简单来说，如果将传统的梯度下降算法理解为在向量空间做梯度下降，那么就可以将GBDT的过程理解为在函数空间做梯度下降。对于一个神经网络，我们可以更新其参数，通过在向量空间做梯度下降降低最终的损失值。而对于一个决策树来说，则可以不断新增决策树，如果将所有可能生成的模型视为一个空间，那么函数空间的梯度下降就是希望以损失函数的梯度作为准则，使得我们能够尽量从整个函数空间内最快找到合适的模型。
GBDT基础

GBDT的目标是通过连续构建多个小模型，最终构建一个大模型 ，从而使得下面的损失函数最小。


具体来说，GBDT就是基于  个训练数据的每条数据在损失函数上的梯度 不断拟合新模型。
一般来说，GBDT都会限制模型  的搜索空间，例如XGBoost经常限制决策树高度不能高于一个阈值。这样的话，优化过程可以视为在模型空间 中找一个与梯度方向距离最小的模型。


进一步来说，上述过程就是找到一个模型  ，使得其预测值和负梯度方向 尽量一致。


GBDT的泛化误差上界

下面这个公式算是整个论文的点睛之笔了，对于单棵不超过 个节点的决策树，假设数据维度为 ，样本数量为  ，那么其Rademacher Complexity的上界如下所示。如果对Rademacher Complexity不甚了解的话，可以将Rademacher Complexity简单理解成对于一个标签完全随机的数据集，决策树能达到的最大准确率。这里  代表所有叶子节点预测值 范数上界 。直观理解的话，如果决策树划分的越深，叶子节点的纯度就越高，这时候 就相对比较大，从而导致Rademacher Complexity也比较大。


根据上面的Rademacher Complexity Bound，我们可以进一步推导出该决策树的泛化误差上界 。首先，第一项可以看出，这个上界跟经验 -margin loss有关，即 。这意味着如果我们的模型在训练集上能把数据分得比较开，那么 就相对较大，此时对应的 就比较小。第二项则跟上面的Rademacher Complexity相关，其中  代表了GBDT每棵决策树前面的系数。


基于随机坐标下降算法的GBDT

目标函数
有了上面的泛化误差上界以后，就可以根据这个泛化误差上界重新确定GBDT的优化目标。第一项代表了经典的GBDT误差，第二项则代表了模型的Rademacher Complexity上界。


因此，在每一轮，生成的决策树 就是所有可能的决策树中能使得上述Loss最小的决策树，而这里的 则代表了一个模型空间。


收敛性证明
在优化过程中，RGB需要同时优化GBDT的每棵决策树  和对应权重  。如果将GBDT的决策树产生视为优化过程（ ），那么对应Loss下降的Lipschitz函数为  。如果将GBDT的权重优化产生视为优化过程（ ），那么对应Loss下降的Lipschitz常数为  。由此，可以得出  和  之间的关系。


而对于随机坐标下降来说，如果选择第 个坐标下降的概率为 ，那么这个优化过程就保证收敛。
代表了样本在叶子节点上预测值的二次方，在这篇论文中，这个值的上限是一个正则化超参数  。但是有时候我们不一定将二次方作为正则化项，上面的  和  之间的关系可以进一步通过Hlder不等式进行变换（即当 时， ）， 的上界可以进一步变换为 。通过改变变换，RGB就可以使用任意的范数作为正则化项。


如果取 和 这一对组合，那么上面的公式变为 。
基于上面的Lipschitz常数，根据随机坐标下降的相关定理，可知第 轮的Loss的期望和最佳Loss之差一定小于右边的上界。这是一个非常好的性质，意味着RGB算法最终是可以收敛的。


训练方法
RGB算法训练过程如下所示。首先，RGB算法采样  个决策树拟合空间（第二行代码），每个拟合空间对应不同限制的决策树。随后，尝试基于负梯度方向 拟合这每棵决策树 <img sc="https://www.zhihu.com/equation?tex=s" alt="s" eeimg="1"/> （第四行代码）。在实际实现中，我们可以限制决策树的高度。但是对于给定高度的决策树，找到最近似负梯度方向的决策树依然是一个NP-Hard问题。作者并没有细讲这里是如何实现的，不过想来应该是作者直接采用了传统的贪心决策树构造方法，近似得到了一个最优解。
在训练了  棵决策树之后，就可以根据上面的目标函数，从这  棵决策树中选择一棵可以使得损失函数最小的决策树（第六行代码）。值得一提的是，每个决策树训练的时候并没有考虑优化正则项，而这时通过从  棵决策树中选一个最佳的决策树优化最终目标可以看成一个带有一定随机性的优化过程，因此RGB的作者将这个优化过程视为函数空间的随机坐标下降。
值得一提的是，这里的  个决策树空间是从从 个决策树空间中按照概率 随机进行采样得到的（第二行代码）。这个概率分布和上面的Lipschitz常数密切相关，即 。只有当按照这个比例进行采样的时候，整个算法才是随机坐标下降算法，而收敛性最终也才有保证。实际上，函数空间的Lipschitz常数我们是求不出来的，但是这里只需要一个比例，因此就还有解决该问题的希望。在上面的分析中，我们可以看到Lipschitz常数的上界为 。而分子和分母中的 项可以最终消去，因此采样比例最终可以转化为 。这意味着  上界越大的决策树空间，被采样的概率越高。更直观来说，决策树越深，  越大，这意味着RGB中更深的决策树有更大的被采样几率。
最终，将新模型 加入到模型  中，并基于随机坐标下降算法在向量空间更新  ，同时在函数空间更新  （第七行和第八行代码）。


实验结果

从最终的实验结果来看，相比XGBoost，RGB在高维数据上的效果非常不错，但是在低维数据集上没有显著优势。作者表示可能是因为高维数据集更容易出现过拟合问题，因此考虑了正则化的RGB算法可以获得效果更好的模型。