提升树 (Boosting Trees)
提升树是以分类树或回归树为基本分类器的提升方法, 模型表示为决策树的加法模型:
\[ F_M(x) = \sum_{m=0}^M f(x;\Theta_m), \]
其中 \(M\) 为树的个数, \(f(x;\Theta_m)\) 表示决策树, \(\Theta_m\) 为其参数.
1. 提升树算法提升树算法采用向前分步 (forward stagewise) 算法 (本质上是一种贪心算法). 对于训练数据集 \(D = \{(x_i, y_i) \}_{i=1}^N\), 首先确定初始提升树 \(F_0(x)=0\), 然后第 \(m\) 步的模型是
\[ F_m(x) = F_{m-1}(x) + f(x;\Theta_m), \]
其中 \(F_{m-1}\) 为当前模型, 通过经验风险最小化确定下一颗决策树的参数,
\[ \hat\Theta_m = \operatorname*{argmin}_{\Theta_m}\sum_{i=1}^N l(y_i, F_{m-1}(x_i) + f(x_i;\Theta_m)), \]
其中 \(l\) 为损失函数.
回归问题的提升树可以表示为简单函数
\[ f(x;\Theta) = \sum_{j=1}^T c_j 1_{R_j}(x), \]
其中 \(R_j\) 互不相交, \(1_{R_j}(x)\) 为示性函数, \(c_j\) 为常数, 参数 \(\Theta=\{(R_j,c_j)\}_{j=1}^T\), \(T\) 为叶节点个数.
综上,
回归问题的提升树算法
初始化 \(F_0(x) = 0\).
对 \(m = 1,\dots,M\): (a) 通过经验风险最小化学习一个回归树 \(f(x;\Theta_m)\). (b) 更新 \(F_m(x) = F_{m-1}(x) + f(x;\Theta_m)\).
输出回归问题提升树 \(F_M(x) = \sum_{m=1}^M f(x;\Theta_m)\).
2. 梯度提升树 (Gradient Boosting Decision Trees)对于一般的损失函数, 每一步经验风险最小化都不容易. GBDT 是为了便于计算而提出的方法, 它的主要想法来自于梯度下降法.
记损失函数的梯度在当前模型的值为
\[ g_{im} = \left(\frac{\partial l(y_i,F(x_i))}{\partial F(x_i)}\right)_{F = F_{m-1}}. \]
则由梯度下降法,
\[ F_m(x_i) = F_{m-1}(x_i) -\rho_m g_{im}, \]
其中步长 \(\rho_m\) 可以通过线搜索获得, 即
\[ \rho_m = \operatorname*{argmin}_{\rho} \sum_{i=1}^Nl(y_i, F_{m-1}(x_i)-\rho g_{im}). \]
梯度下降法是一个很贪心的算法, 即在当前点取函数下降最快的方向. 但如上这样做的话我们只获得了在训练数据点上的预测, 为了得到可以预测新数据的决策树, 一种可行的做法是, 用 \(f\) 逼近负梯度方向, ESL [2] p. 321 使用了平方误差来度量 \(f\) 与负梯度的距离, 即
\[ \tilde\Theta_m = \operatorname*{argmin}_{\Theta}\sum_{i=1}^N (-g_{im} - f(x_i;\Theta))^2. \]
注意到对于 \(l(x,y) = \frac12(x-y)^2\) 的情形, \(\tilde\Theta_m\) 与 \(\hat\Theta_m\) 相等.
其余操作同提升树算法, 从略.
3. XGBoost 3.1. 总体框架XGBoost 的主要想法是, 除了原有的损失函数, 在目标函数中加入正则项, 利用二阶 Taylor 近似代替目标函数再求极值 (回忆之前的梯度提升树只用了一阶导数), 其余操作同提升树算法.
记 \(F_m(x_i) = \hat y_i^{(m)}\),
\(\hat y_i^{(0)}=0\),
\(\hat y_i^{(m)} = \hat y_i^{(m-1)} + f_m(x_i)\), \(m=1,\dots,M\).
\(f_m\) 表示第 \(m\) 轮时所得的树, 是由最小化目标函数而得; \(\hat y_i^{(m)}\) 表示第 \(m\) 轮时 \(y_i\) 的预测值.
第 \(m\) 轮目标函数为
\[ \mathrm{Obj}^{(m)} = \sum_{i=1}^N l\left(y_i, \hat y_i^{(m-1)} + f_m(x_i)\right) + \Omega(f_m), \]
其中 \(l\) 为损失函数; \(\Omega\) 为正则项, 是人为定义的复杂度, 可以降低模型复杂度, 减小过拟合的风险, 在原论文 [3] 中定义为
\[ \Omega(f) = \gamma T + \frac12 \lambda\sum_{j=1}^T w_j^2, \]
其中 \(\gamma\), \(\lambda\) 为参数, \(T\) 为 \(f\) 表示的数的叶节点数, \(w_j\) 为第 \(j\) 个叶节点的预测值 (权重).
除了加入正则项外, 还可以通过 shrinkage 来降低过拟合风险, 即 \(F_m = F_{m-1} + \nu f_m\), 其中 \(0<\nu<1\), 可以看为学习率, 原来的做法相当于取 \(\nu=1\). 这么做主要的理由是减少每颗树对总模型的影响, 防止前几颗树拟合地太好 (过拟合) 以至于后面的树没有了学习空间.
3.2. 寻找分裂点对目标函数做二阶 Taylor 展开, 略去更高阶的无穷小量. 记
\[ g_i = \frac{\partial l(y_i, \hat y_i^{(m-1)})}{\partial{\hat y^{(m-1)}}},\quad h_i = \frac{\partial^2 l(y_i, \hat y_i^{(m-1)})}{\partial{\left(\hat y^{(m-1)}\right)^2}}. \]
例如对于平方损失函数 \((y_i - \hat y_i^{(m-1)})^2\) 来说, \(g_i = 2(\hat y_i^{(m-1)} - y_i)\), \(h_i = 2\).
经过简单的推导可得最优权重为
\[ w_j^* = -\frac{\sum_{i\in I_j}g_i}{\sum_{i\in I_j} h_i + \lambda}, \]
其中 \(I_j\) 表示被归到第 \(j\) 个叶节点的全体实例 (的脚标) 集合.