第 9.2 节很详细地介绍了回归和分类树模型。它们将所有自变量的联合输入变量空间分割成不相交的区域 $R_j,j=1,2,\dots,J$，也就是树模型中的终节点。
每个这样的区域会指派一个常数 $\gamma_j$，而预测的规则为
$$x \in R_j \Rightarrow f(x) = \gamma_j$$因此一个树模型可正式地表述为
$$T(x; \Theta) = \sum_{j=1}^J \gamma_j I(x \in R_j) \tag{10.25}$$其中的参数 $\Theta=\{R_j,\gamma_j\}_1^J$。$J$ 通常被当作一个超（meta）参数。这些参数1可通过最小化经验风险/损失来计算：
$$\hat{\Theta} = \arg\min_\Theta \sum_{j=1}^J \sum_{x_i \in R_j} L(y_i, \gamma_j) \tag{10.26}$$这是一个难以处理的组合最优化问题，而我们通常可以接受一个近似的次优解。一个策略是将最优化问题分解成两部分：
- 给定 $R_j$ 后寻找 $\gamma_j$：
给定了 $R_j$ 后，一般可很容易地估计出 $\gamma_j$，通常有 $\hat{\gamma}_j=\bar{y}_j$，即落入区域 $R_j$ 中的 $y_j$ 的均值。对误分类损失来说，$\hat{\gamma}_j$ 为落入区域 $R_j$ 中观测样本的众数类。 - 寻找 $R_j$：
这个部分比较困难，通常会使用某种近似的解。同时也注意到在寻找 $R_j$ 时也需要用到 $\gamma_j$ 的估计。一个通常的策略是使用贪婪的自上而下的循环分割算法来寻找 $R_j$。另外，在对 $R_j$ 最优化的过程中有时需要用一个更平滑和方便的准则替代式 10.26： $$\tilde{\Theta} = \arg\min_\Theta \sum_{i=1}^N \tilde{L}(y_i,T(x_i, \Theta)) \tag{10.27}$$ 然后对给定的 $\hat{R}_j=\tilde{R}_j$，可以用原本的准则更准确地估计出 $\gamma_j$。
第 9.2 节介绍了这个策略在分类树模型上的应用。其中在生成树模型（寻找 $R_j$）时用基尼系数（Gini index）代替了误分类损失。
提升树模型（boosted tree model）为这样的一些树模型的和：
$$f_M(x) = \sum_{m=1}^M T(x; \Theta_m) \tag{10.28}$$这个模型是由一个前向分段的形式（算法 10.2）推导出的。在这个前向分段过程中的每一步，需要求解：
$$\hat{\Theta}_m = \arg\min_{\Theta_m} \sum_{i=1}^N L(y_i, f_{m-1}(x_i) + T(x_i; \Theta_m)) \tag{10.29}$$给定了当前的模型 $f_{m-1}(x)$，其中的最小化参数为下一个树模型的区域的集合以及常数 $\Theta_m=\{R_{jm},\gamma_{jm}\}_1^{J_m}$。
给定了区域 $R_{jm}$ 后，一般很容易求出每个区域上的最优常数 $\gamma_{jm}$：
$$\hat{\gamma}_{jm} = \arg\min_{\gamma_{jm}} \sum_{x_i \in R_{jm}} L(y_i, f_{m-1}(x) + \gamma_{jm}) \tag{10.30}$$但寻找这些区域并不容易，甚至比在单一的树模型中更加困难。不过在一些特例中，可简化这个问题。
对于平方误差损失函数，求解式 10.29 的复杂度与单个树模型相符。区域的解就是可最好地预测当前残差 $y_i-f_{m-1}(x_i)$ 的回归树模型，而 $\gamma_{jm}$ 即为这些残差在每个区域上的均值。
对于两个类别的分类问题以及指数损失函数，这个分段的方法会得出作为提升分类树模型的自适应提升（AdaBoost）方法（算法 10.1）。特别是如果约束树模型 $T(x;\Theta_m)$ 在缩放（scaled）分类树模型，则第 10.4 节证明了式 10.29 的解为在权重 $w_i=e^{-y_if_{m-1}(x_i)}$ 下最小化加权误差率 $\sum_{i=1}^Nw_i^{(m)}I(y_i\ne T(x_i;\Theta_m))$ 的树模型。所谓缩放（scaled）分类树模型，指的是 $\beta_mT(x_i;\Theta_m)$ 的形式，其中约束了 $\gamma_{jm}\in\{-1,1\}$。
若没有这个约束，对于指数损失函数式 10.29 仍可简化成对一个加权指数准则求解新的树模型：
$$\hat{\Theta}_m = \arg\min_{\Theta_m} \sum_{i=1}^N w_i^{(m)} \exp[-y_i T(x_i; \Theta_m)] \tag{10.31}$$那么可以直接地利用这个加权指数损失作为分割准则，而进行一个贪婪的递归分割算法。给定 $R_{jm}$ 后，可证明（练习 10.7）表达式 10.30 的解是每个相应区域的加权对数几率：
$$\hat{\gamma}_{jm} = \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}$$这就需要一个特殊的生成树模型的算法；实践中更倾向于使用下面所述的利用加权最小二乘回归树模型的一个近似方法。
使用其他的损失准则可使提升树模型更稳健，比如在回归问题中用绝对误差或 Huber 损失（式 10.23）代替平方误差损失，或在分类问题中用诸如偏差（式 10.22）代替指数损失。不过这些稳健的准则与原来的非稳健准则不同，不再可得出简单快速的提升算法。
对于更一般的损失准则，给定了 $R_{jm}$ 后的表达式 10.30 的求解通常比较容易，因为这是一个简单的“位置”估计问题。对于绝对损失来说，这个解是残差在每个对应区域上的中位数。对于其他的损失准则来说，求解式 10.30 有快速的递归算法，但通常使用其更快速的“一步”近似算法就已经足够了。问题的难点在于推导树的结构。对于更一般的损失准则来说，并没有求解式 10.30 的简单快速的算法，所以类似于式 10.27 的近似方法就非常重要了。
本节练习
练习 10.7
Derive expression (10.32).
-
参数 $\Theta$ 可通过对损失函数在样本上的平均最小化解出。超参数 $J$ 可通过交叉验证的方法得出。 ↩︎