Skip to content

10.9 Boosting 树

原文 The Elements of Statistical Learning
翻译 szcf-weiya
发布 2018-03-01
更新 2019-08-22 15:41:45
状态 Done

回归和分类树在第 9.2 节 已经详细讨论了.它们将所有联合预测变量的空间划分为不相交的区域 $R_j,j=1,2,\ldots,J$,这些区域用树的终止结点表示.常数值 $\gamma_j$ 赋予到每个区域中,预测规则为

因此,一棵树可以正式地表达成

其中参数为 $\Theta=\{R_j,\gamma_j\}_1^J$.$J$ 通常看成是元参数.通过最小化 经验风险 (empirical risk) 来确定

这是个艰巨的组合优化问题,我们通常去寻求近似次优解.将该优化问题分成两个部分是很有用的:

  1. 给定 $R_j$ 求 $\gamma_j$: 给定 $R_j$,估计 $\gamma_j$ 是小菜一碟,而且通常有 $\hat\gamma_j=\bar y_j$,这是那些落在区域$R_j$ 的 $y_i$ 的均值.对于误分类损失,$\gamma_j$ 是落在区域 $R_j$ 的观测值的 众数 (modal class)
  2. 求 $R_j$: 对于求近似解,这是很困难的一部分.注意到寻找 $R_j$ 意味着也估计 $\gamma_j$.一个典型的策略是使用贪婪的,自上而下的递归划分算法来寻找$R_j$.另外,为了优化$R_j$,有时也需要通过一个更光滑以及更方便的准则来近似 \eqref{10.26}: 接着给定 $\hat R_j=\tilde R_j$,$\gamma_j$ 可以运用原来的准则精确估计出.

9.2 节我们讨论了用于分类树的这样一个策略.在增长树的过程(确定 $R_j$)中用 Gini 指数替换误分类损失.

Boosted 树模型是这些树的和

向前逐步(forward stagewise) 的方式导出(算法 10.2).在向前逐步过程中的每一步, 给定当前树模型 $f_{m-1}(x)$,求出下一棵树的区域和常数 $\Theta_m=\{R_{jm},\gamma_{jm}\}^{J_m}_1$ 需要求解

给定区域 $R_{jm}$,寻找每个区域的最优的常数值 $\gamma_{jm}$ 是很直接的

寻找这些区域是很困难的,甚至比寻找单棵树的区域还要困难.对于一些特殊情形,这个问题可以进行简化.

对于平方误差损失,\eqref{10.29} 的解不比单棵树复杂.此时解是当前残差 $y_i-f_{m-1}(x)$ 的最好预测的回归树,并且 $\hat\gamma_{jm}$ 是每个对应区域中的残差的均值.

对于两类别分类和指数损失,这个逐步方法给出了 Boosting 分类树的 AdaBoost 方法(算法 10.1).特别地,如果树 $T(x;\Theta_m)$ 限制为 缩放分类树 (scaled classification tree),则在 10.4 节我们已经证明 \eqref{10.29} 的解为最小化加权误差率 $\sum_{i=1}^Nw_i^{(m)}I(y_i\neq T(x_i;\Theta_m))$ 的树,其中权重 $w_i^{(m)}=e^{-y_if_{m-1}(x_i)}$.缩放分类树 是指满足限制条件 $\gamma_{jm}\in\{-1, 1\}$ 的 $\beta_mT(x;\Theta_m)$.

没有限制条件的话,\eqref{10.29} 仍然将指数损失简化为新树的加权指数损失准则:

采用加权指数损失的分割准则,应用 贪婪递归划分(greedy recursive-partitioning) 算法是很直接的.给定 $R_{jm}$,可以证明 \eqref{10.30} 的解是每个对应区域中的加权对数 log-odds(练习 10.7

Ex. 10.7

已证.详细证明过程见Issue 75: Ex. 10.7

这需要特定化的生成树算法;实际中,我们更偏好将在下文展示的采用加权最小二乘回归树的近似.

在回归中,用绝对值误差或者 Huber 损失 \eqref{10.23} 来代替平方损失,以及在分类中,用偏差 \eqref{10.22} 代替指数损失,都会得到鲁棒的 Boosting 树.

weiya 注: Recall

不幸的是,不像相对应的欠鲁棒的 (nonrobust) 准则,这些鲁棒准则不会得到简单快速的 boosting 算法.

给定 $R_{jm}$,对于更一般的损失准则,\eqref{10.30} 的解是很直接的,因为只是一个简单的局部估计.对于绝对值损失,这就是每个单独区域的残差的中位数.对于其它的准则,求解 \eqref{10.30} 存在快速的迭代算法,而且通常它们快速的单步近似就已经够了.问题在于树的生成.对于这些一般的损失准则,求解 \eqref{10.29} 不存在简单的快速算法,此时类似 \eqref{10.27} 的近似变得很重要.

Comments