BDT- Gradient Boosted Decision Tables for High Accuracy and Scoring Efficiency

这篇文章是Airbnb的一篇文章,发在KDD2017上,介绍了一篇叫梯度提升决策表(Gradient Boosted Decision Tables)的方法。本文的motivation idea有以下几点:

  • 可以更好的理解梯度提升bias和variance的权衡,在降低bias的同时,会造成variance的增加,正则化可以在一定程度上解决这些问题,如shrinkage、subsampling等等,传统的限制树模型的复杂度的方式是限制其深度,然而树模型仍然可以自由地划分特征空间,决策表模型可以通过限制切割的位置来控制模型复杂度,在切割位置划分特征空间;
  • 对于回归树而言,做梯度提升时通常需要控制每一棵树的复杂度,往往需要在很大的参数空间中去搜索最优解,因此模型选择变得非常“昂贵”,然而由于受限于结构,维数是调整决策表模型的主要参数,因此在梯度提升时,模型选择就变得相对容易;
  • 在部署一个集成模型时,往往需要权衡打分效率和模型准确度,决策表模型可以用紧凑的数据结构所表示,大大节约了内存空间,使得我们可以训练更大的模型,同时达到较高的精度,而不用担心打分的延迟。

一个通用的梯度提升框架如下所示:

1

一个\(d\) 维的决策表用一个\(d\) 维的数组来存储特征下标,另一个\(d\) 维数组来存储划分,一个\(2^d\) 的数组来存储存储预测值(\(d\) 的取值通常较小),预测值通过一个bit的向量来表示,用例子来说明

2

输入\(x_i=(0,3,4,2,1,0)\) ,经过\(d=3\) 个test:\(x_3\leq 5,x_6\leq0,x_2\leq1\)并且产生一个bit向量\([110]_2=[6]_{10}\) ,然后将它的值作为下标值存储。对于每次划分\(k\) ,用\(\mathcal{D}_k\) 表示划分点的子集,\(\mathcal{D}_k^L\)\(\mathcal{D}_k^R\) 分别表示划分后的两个集合,大于临界值\(c\) 的和小于等于的,用\(\mathcal{I}_k^L=\{i|x_i\in\mathcal{D}_k^L\}\)\(\mathcal{I}_k^R=\{i|x_i\in\mathcal{D}_k^R\}\) 表示划分点的下标,定义均方误差为\(\text{SE}_{\mathcal{D}_k}=\sum_{i\in\mathcal{I}_k}(y_i-\overline{y}_k)^2\) 其中\(\overline{y}_k=\frac{1}{|\mathcal{I}_k|}\sum_{i\in\mathcal{I}_k}y_i\) ,根据基尼系数来划分 \[ \begin{aligned} \text{Gain}(x_j,c)&= \text{SE}_{\mathcal{D}}-\sum_k(\text{SE}_{\mathcal{D}_k^L}+\text{SE}_{\mathcal{D}_k^R})\\ &=\sum_k(\frac{(\sum_{i\in\mathcal{I}_k^L}y_i)^2}{|\mathcal{I}_k^L|}-\frac{(\sum_{i\in\mathcal{I}_k^R}y_i)^2}{|\mathcal{I}_k^R|})-N\overline{y}^2 \end{aligned} \]

\[ \text{Gain}(x_j)=\max_{c\in dom(x_j)}\text{Gain}(x_j,c) \]

很容易看出,寻找最有决策是一个NP问题,所以作者提出了一个反向拟合(backfitting)的方法

3

首先用贪婪策略去寻找\(d\) 次划分,这样可能不会得到最优解,因此,一旦我们完成\(d\) 次划分的据侧标,用\(n\) 次检验的反向拟合算法来矫正一些次优的划分,每次检验时执行\(d\) 次划分,每次选择\(d\) 次划分之一时来优化划分临界值,并且从当前决策表中去除,计算当前最优化分,更新划分方式。最后,我们计算每次划分的均值来作为预测值。反向拟合主要有以下三种策略:

  • 循环反向拟合,cyclic backfitting,从头开始进行划分和优化所有划分序列;
  • 随机反向拟合,random backfitting,随机选择一次划分并优化;
  • 贪婪反向拟合,gredy backfiting,贪婪策略,选择能最大程度降低variance的划分点。