这里每个技巧都假设了未知回归函数(不同的)结构形式, 而且通过这样处理巧妙地解决了维数灾难.

广义可加模型

• 在回归的设定中，广义可加模型 $E(Y|X_1, X_2,...,X_p) = \alpha + f_{1}(X_1) + f_{2}(X_2) + ... + f_{p}(X_p),$E(Y∣X1​,X2​,...,Xp​)=α+f1​(X1​)+f2​(X2​)+...+fp​(Xp​), 其中$X_1, X_2, ... , X_p$X1​,X2​,...,Xp​ 代表预报变量，$Y$Y 表示输出变量, $f_{j}$fj​ 是未定义的(非参)光滑函数.
• 对于二分类, 通过一个线性回归模型和 logit 链接函数将预报变量与二进制响应变量的均值 $\mu(X) = {\rm Pr}(Y=1|X)$μ(X)=Pr(Y=1∣X) 关联起来: $\log\left(\frac{\mu(X)}{1-\mu(X)}\right) = \alpha + f_{1}(X_1) + f_{2}(X_2) + ... + f_{p}(X_p).$log(1−μ(X)μ(X)​)=α+f1​(X1​)+f2​(X2​)+...+fp​(Xp​). 一般地, 响应变量 $Y$Y 的条件均值 $\mu(X)$μ(X) 通过一个链接函数 $g$g 将预报变量的可加函数联系起来 $g\left[\mu(X)\right] = \alpha + f_{1}(X_1) + f_{2}(X_2) + ... + f_{p}(X_p).$g[μ(X)]=α+f1​(X1​)+f2​(X2​)+...+fp​(Xp​).
  上面的情形来自的指数族采样模型, Gamma 分布和负二项分布构成的分布族产生了著名的广义线性模型类, 它们都是以同样的方式扩展为广义可加模型.

拟合可加模型

building block 是用一种灵活的方式拟合非线性影响的散点图光滑器.

原则上, 算法 9.1 中第 2(2) 步不是必需的, 因为光滑样条对 $0$0 均值响应变量拟合均值为 $0$0.

然而可加模型对于大的数据挖掘的应用是有限制的. backfitting 算法拟合所有的预测变量, 而大部分的预测变量是不可行的也不是必需的. BRUTO 过程(Hastie and Tibshirani, 19902, 第9章)结合 backfitting 和输入选择, 但是不是为了大规模的数据挖掘的问题. 最近也有用 lasso 型惩罚来估计稀疏加性模型的工作, 对于大型问题, 向前逐步方法(如第10章的 boosting)更加地有效, 而且允许交叉项包含进模型中.

基于树????的方法（决策树）

基于树 (Tree-based) 的方法将特征空间划分成一系列的长方形, 然后对每个长方形拟合简单的模型(比如常数).

回归树

数据包含对 $N$N 个观测值中的每一个的 $p$p 个输入和 $1$1 个输出 $(x_i,y_i)$(xi​,yi​), $i = 1, 2 , ... ,N$i=1,2,...,N, 其中, $x_{i} = (x_1, x_2, ... , x_{ip})$xi​=(x1​,x2​,...,xip​). 这个算法需要根据分离变量和分类点来自动确定, 而且确定树应该有的拓扑结构(形状).

• 首先假设有一个分成 $M$M 个区域 $R_1, R_2, ... ,R_M$R1​,R2​,...,RM​ 的一个划分, 而且我们在每个区域内用常数 $c_m$cm​ 来对响应变量来建立模型 $f(x) = \sum\limits_{m=1}^{M}c_{m}I(x\in R_{m}).$f(x)=m=1∑M​cm​I(x∈Rm​).
• 采用贪婪算法寻找最优分割.
  考虑分离变量 $j$j 和分离点 $s$s, 定义半平面对 $R_{1}(j,s) = \{X|X_{j}\leq s\},\ R_{2}(j,s) = \{X|X_{j}> s\}.$R1​(j,s)={X∣Xj​≤s}, R2​(j,s)={X∣Xj​>s}. 进而寻找分离变量 $j$j 和分离点 $s$s 求解$\min\limits_{j,s}\left[\min_{c_1}\sum\limits_{x_{i}\in R_1}(y_i-c_1)^{2} + \min_{c_2}\sum\limits_{x_{i}\in R_2}(y_i-c_2)^{2}\right].$j,smin​[c1​min​xi​∈R1​∑​(yi​−c1​)2+c2​min​xi​∈R2​∑​(yi​−c2​)2]. 对于每个选定的 $j$j 和 $s$s, 内部最小化通过下式来求解 $\hat{c_1} = {\rm ave}\left(y_{i}|x_{i}\in R_{1}(j,s)\right),\ \hat{c_2} = {\rm ave}\left(y_{i}|x_{i}\in R_{2}(j,s)\right).$c1​^​=ave(yi​∣xi​∈R1​(j,s)), c2​^​=ave(yi​∣xi​∈R2​(j,s)). 找到最优的分割之后, 我们将数据分成两个区域, 然后对每个区域重复分割过程.
• 采用 cost-complexity pruning 来调整树.
  我们定义子树 $T\in T_{0}$T∈T0​ 为任何可以通过对 $T_0$T0​ 剪枝得到的树. 用 $m$m 表示终止结点, 其中结点 $m$m 表示区域 $R_m$Rm​. 令 $|T|$∣T∣ 为 $T$T 中终止结点的个数. 令
  $N_{m} = \#\{x_{i}\in R_{m}\},\ \hat{c}_{m} = \frac{1}{N_{m}}\sum\limits_{x_{i}\in R_{m}}y_{i},\ Q_{m}(T) = \frac{1}{N_{m}}\sum\limits_{x_{i}\in R_{m}}(y_i - \hat{c}_{m})^{2}.$Nm​=#{xi​∈Rm​}, c^m​=Nm​1​xi​∈Rm​∑​yi​, Qm​(T)=Nm​1​xi​∈Rm​∑​(yi​−c^m​)2.
  定义复杂度代价准则 $C_{\alpha}(T) = \sum\limits_{m=1}^{|T|}N_{m}Q_{m}(T) + \alpha|T|.$Cα​(T)=m=1∑∣T∣​Nm​Qm​(T)+α∣T∣.

对于每个 $\alpha$α, 可以找到唯一最小的子树 $T_{\alpha }$Tα​ 使得 $C_{\alpha}(T)$Cα​(T) 最小化. 为了寻找 $T_{\alpha}$Tα​ 我们采用 weakest link pruning : 逐步压缩在 $\sum_{m} N_{m}Q_{m}(T)$∑m​Nm​Qm​(T) 中单节点增长最小的中间结点, 直到我们得到单结点(根)的树. 这给出了子树的(有限)序列, 而且可以证明这条序列一定包含 $T_{\alpha}$Tα​.

分类树

针对分类问题, 令 $\hat{p}_{mk} = \frac{1}{N_{m}}\sum\limits_{x_{i}\in R_{m}}I(y_{i} = k),$p^​mk​=Nm​1​xi​∈Rm​∑​I(yi​=k),
类别 $k$k 的观测在结点 $m$m 处的比例. 我们将结点 $m$m 处的观测划分为类别 $k(m) = \arg\max_{k}\hat{p}_{mk}$k(m)=argmaxk​p^​mk​, 结点 $m$m 处最主要的类别. 不同衡量结点纯度 $Q_{m}(T)$Qm​(T) 的方法包括如下:

• 误分类误差 $\frac{1}{N_{m}}\sum\limits_{x_{i}\in R_{m}}I(y_{i} \neq k) = 1 - \hat{p}_{mk}$Nm​1​xi​∈Rm​∑​I(yi​̸​=k)=1−p^​mk​
• Gini指数 $\sum\limits_{k\neq k'}\hat{p}_{mk} \hat{p}_{mk'} = \sum\limits_{k=1}^{K}\hat{p}_{mk} (1-\hat{p}_{mk} )$k̸​=k′∑​p^​mk​p^​mk′​=k=1∑K​p^​mk​(1−p^​mk​)
• 交叉熵或者偏差$-\sum\limits^{K}_{k=1}\hat{p}_{mk}\log\hat{p}_{mk}$−k=1∑K​p^​mk​logp^​mk​

CART 算法既是分类算法, 也是回归算法, 在分类时选择的标准是Gini指数; C4.5 算法只是分类算法用的是信息增益率.

PRIM

耐心规则归纳法 (PRIM) 也在特征空间中找盒子, 但是它是寻找具有高平均响应的盒子. 因此它是在寻找目标函数的最大值, 称为bump hunting.
PRIM 中构造盒子的主要方法是自上而下, 以包含所有数据的盒子开始. 这个盒子沿着一个面被逐渐压缩, 接着观测落在盒子外的观测点被剔除(peeled) 掉. 用于压缩的面要使得压缩过后盒子均值最大. 接着重复这个过程, 直到当前的盒子包含最小数目的数据点. 计算完自上而下的序列之后, 沿着任意边进行展开, 如果这样的展开能够增大盒子均值的话, PRIM 则回溯这个过程. 这称为 pasting. 因为自上而下的过程在每一步是贪婪的, 所以这样的展开经常是可行的.

PRIM 与 CART 相比的优点是它的耐心 (patience), 在任何情形下, PRIM 的能力更加耐心, 这应该帮助自上而下的贪婪算法找到更好的解.

多变量自适应回归样条 MARS

MARS是回归的自适应过程, 非常适合高维问题. 可以从两个角度来理解它, 首先, 它可以看成是逐步线性回归的推广, 其次, 也可以看成是为了提高CART在回归中的效果而进行的改进.
MARS采用形式为 $(x-t)_{+}$(x−t)+​, $(x+t)_{+}$(x+t)+​ 的分段线性基函数的展开, 每个函数是分段线性的, 在值 $t$t 处有一个结点.

• 对于每个输入变量 $\bm X_j$Xj​, 将该输入变量的所有观测值作为结点. 基函数集合为 $\mathcal{C} = \left\{(X_j - t)_{+}, (t- X_j)_{+}\right\}_{t \in \{x_ {1j}, x_{2j}, ... , x_{Nj}\}},j=1,2,...,p.$C={(Xj​−t)+​,(t−Xj​)+​}t∈{x1j​,x2j​,...,xNj​}​,j=1,2,...,p.
• 建立模型的策略类似向前逐步线性回归, 但是不是使用原始输入, 允许使用集合 $\mathcal{C}$C 中的基函数及其基函数间的乘积. 模型有如下形式 $f(X) = \beta_{0} + \sum\limits_{m=1}^{M} \beta_{m}h_{m}(X),$f(X)=β0​+m=1∑M​βm​hm​(X), 其中每个 $h_{m}(X)$hm​(X) 是 $\mathcal{C}$C 中的基函数, 也可能是两个或者更多这样基函数的乘积. 通过标准线性回归来估计系数 $\beta_{m}$βm​.
• 为了节省计算, MARS过程采用的是广义交叉验证 ${\rm GCV}(\lambda) = \frac{\sum_{i=1}^{N}(y_i - \hat{f}_{\lambda}(x_i))^2}{(1 - M(\lambda)/N)^2}.$GCV(λ)=(1−M(λ)/N)2∑i=1N​(yi​−f^​λ​(xi​))2​. 在向后删除变量的过程中，计算 ${\rm GCV}(\lambda)$GCV(λ), 选择使得 ${\rm GCV}(\lambda)$GCV(λ) 最小的模型.

分段线性基函数的优点: 可以局部计算, 适合高维问题; 计算简便.

专家的分层混合 HME

专家的分层混合 (HME) 过程可以看成是基于树方法的变种. 主要的差异是树的分割不是硬决定 (hard decision), 而是软概率的决定 (soft probabilistic).

• 在每个结点观测往左或者往右的概率取决于输入值. 因为最后的参数优化问题是光滑的, 所以有一些计算的优势.
• 在HME中, 在每个终止结点处拟合线性(或者逻辑斯蒂回归)模型, 而不是像 CART 中那样是常值.
• 分割点可以是多重的, 而不仅仅是二值的, 并且分割点是输入的线性组合的概率函数, 而不是在标准 CART 中的单个输入.
  
  顶层的门控网络有输出
  $g_{j} = \frac{e^{\gamma_{j}^{T}x}}{\sum_{k=1}^{K}e^{\gamma_{j}^{T}x}},\ j = 1, 2, ... , K.$gj​=∑k=1K​eγjT​xeγjT​x​, j=1,2,...,K.
  这表示软的 $K$K 重分割是将特征向量为 $x$x 的观测赋给第 $j$j 个分支. 在第二层，门控网络有类似的形式.
  在每个专家(终止结点), 有如下形式的响应变量的模型
  $Y\sim {\rm Pr}(y|x, \theta_{j\ell}).$Y∼Pr(y∣x,θjℓ​).
• 回归: 使用高斯线性回归模型, 其中 $\theta_{j\ell} = (\beta_{j\ell}, \sigma_{j\ell}^2)$θjℓ​=(βjℓ​,σjℓ2​)
  $Y = \beta^{T}_{k\ell}x + \varepsilon, \ \varepsilon\sim N(0,\sigma_{j\ell}^{2}).$Y=βkℓT​x+ε, ε∼N(0,σjℓ2​).
• 分类: 使用线性逻辑斯蒂回归模型
  ${\rm Pr}(Y=1|x,\theta_{j\ell}) = \frac{1}{1+ e^{-\theta^{T}_{j\ell}x}}.$Pr(Y=1∣x,θjℓ​)=1+e−θjℓT​x1​.

专家的分层混合方式是 CART 树的一个有潜力的对手. 采用软分割 (soft splits), 而不是硬分割, 它可以捕捉到从低到高响应变量的转变是渐增的情形. 对数似然是未知系数的光滑函数, 因此更适合数值优化. 和 CART 类似, 都是线性组合的分割, 但是后者更难优化. 另一方面, 基于我们的了解, 寻找 HME 模型的一个好的树拓扑结构是没有方法的.