

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$ 赋予到每个区域中，预测规则为

$$x\in R_j\Rightarrow f(x) = \gamma_j$$

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

$$T(x;\Theta)=\sum\limits_{j=1}^J\gamma_jI(x\in R_j)\tag{10.25}$$

其中参数为 $\Theta=\{R_j,\gamma_j\}_1^J$．$J$ 通常看成是元参数．通过最小化 经验风险 (empirical risk) 来确定 $$\hat\Theta = \text{arg }\underset{\Theta}{\text{min}}\sum\limits_{j=1}^J\sum\limits_{x_i\in R_j}L(y_i,\gamma_j)\tag{10.26}\label{10.26}$$

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

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\Theta = \text{arg }\underset{\Theta}{\text{min}}\sum\limits_{i=1}^N\tilde L(y_i,T(x_i,\Theta))\tag{10.27}\label{10.27}$$ 接着给定 $\hat R_j=\tilde R_j$，$\gamma_j$ 可以运用原来的准则精确估计出．

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

Boosted 树模型是这些树的和

$$f_M(x)=\sum\limits_{m=1}^MT(x;\Theta_m)\tag{10.28}\label{10.28}$$

由 向前逐步(forward stagewise) 的方式导出（算法 10.2）．在向前逐步过程中的每一步, 给定当前树模型 $f_{m-1}(x)$，求出下一棵树的区域和常数 $\Theta_m=\{R_{jm},\gamma_{jm}\}^{J_m}_1$ 需要求解 $$\hat\Theta_m = \text{arg }\underset{\Theta_m}{\text{min}}\sum\limits_{i=1}^NL(y_i,f_{m-1}(x_i)+T(x_i;\Theta_m))\tag{10.29}\label{10.29}$$

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

$$\hat \gamma_{jm}=\text{arg }\underset{\gamma_{jm}}{\text{min}}\sum\limits_{x_i\in R_{jm}}L(y_i,f_{m-1}(x_i)+\gamma_{jm})\tag{10.30}\label{10.30}$$

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

对于平方误差损失，\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} 仍然将指数损失简化为新树的加权指数损失准则：

$$\hat\Theta_m = \text{arg }\underset{\Theta_m}{\text{min}}\sum\limits_{i=1}^Nw_i^{(m)}\exp[-y_iT(x_i;\Theta_m)]\tag{10.31}$$

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

$$\hat \gamma_{jm}=\frac 12\log \frac{\sum_{x_i\in R_{jm}}w_i^{(m)}I(y_i=1)}{\sum_{x_i\in R_{jm}}w_i^{(m)}I(y_i=-1)}\tag{10.32}$$

Ex. 10.7

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

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

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

weiya 注: Recall

$$\begin{align} L(y,p(x))&=-\sum\limits_{k=1}^KI(y=\cal G_k)\log p_k(x)\notag\\ &=-\sum\limits_{k=1}^KI(y={\cal G_k})f_k(x)+\log (\sum\limits_{\ell=1}^Ke^{f_\ell(x)})\tag{10.22}\label{10.22} \end{align}$$ $$L(y,f(x))= \left\{ \begin{array}{ll} [y-f(x)]^2&\text{for }\vert y-f(x)\vert \le\delta\\ 2\delta\vert y-f(x)\vert-\delta^2&\text{otherwise} \end{array} \right. \tag{10.23}\label{10.23}$$

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

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

Comments