摘要本文为ESLII(The Element of Statistical Learning, Second Edition)第三章线性回归方法的学习总结(2)。子集选择(又称之为变量选择/特征选择)是线性回归过程中非常重要的概念，应用也十分广泛。子集选择的准则以及方法非常多，本文主要介绍了ESLII第三章提到的最优子集选择、逐步选择、分段选择等算法，并通过Python对这些算法进行了分析比较。

概述

由于以下两个原因，经典的最小二乘算法(Ordinary Least Square, OLS)通常无法满足实际的应用需求：

预测精度 (predication accuracy)：虽然在线性回归模型中，最小二乘算法是无偏估计算法中预测方差最小的一类算法，但当自变量$X$的分量(predictor, 预测变量)个数$p$较多且一些分量$X_j$对因变量$Y$没有贡献或者贡献较小时，最小二乘算法的估计方差仍然较大，无法满足预测精度需求。此时，通过对这些不重要的系数$\beta_j$进行收缩或者置零，牺牲一点估计偏差，可以换取更小的估计方差，获得更佳的估计精度。
解释能力(interpretation)：当自变量$X$的分量个数$p$较多，我们通常希望找出对大局影响最多的自变量子集，忽略一些贡献较小的自变量分量。

因此，出于以上原因，我们会进行子集选择(subset selection)。子集选择属于模型选择(model selection)的范畴。注：有些文献资料中称子集选择为变量选择(variable selection)或特征选择(feature selection)，在本文中，我们将沿用ESLII中的表示习惯。

最优子集选择

最优子集选择(best-subset selection)是以最小化残差平方和为目标使用遍历的方法计算每种子集大小下的子集选择$\mathcal{M}_k$，其中$k$为子集大小。然而，在训练数据一定的情况下，$k$越大，$\mathcal{M}_k$作用在该训练数据的残差平方和必然也是越小的，所以通常我们选用交叉验证或者AIC(Akaike Information Criterion, 赤池信息准则)或者BIC(Bayesian Information Criterion, 贝叶斯信息准则) 来选择一个最佳的$k$值，进而获得最佳的子集选择$\mathcal{M}_k$。

子集选择是在模型复杂度与模型对数据集描述能力（例如似然函数）之间寻求最佳平衡，即经验风险与结构风险的权衡。AIC、BIC以及其他的信息准则均是通过加入模型复杂度的惩罚项来避免过拟合问题(详见参考文献[1])，本质上属于正则化的范畴。
最有子集算法适用于$p<40$的线性回归场景，此时通过使用leaps and bounds procedure来提高最优子集选择的运算效率。

前向/后向逐步选择

当$p$很大时最优子集选择的运算效率很低，所以我们通过路径搜索的方法来实现子集选择。前向逐步选择(forward stepwise selection)初始状态不包含任何预测变量开始(仅含有截距$\bar{y}$)，然后依次往模型中添加预测变量，且每次添加的预测变量能够最大限度地提升模型的预测效果(最小化)的变量加入模型中。

前向逐步选择算法每一步产生了子集大小为$k$的子集选择$\mathcal{M}_k$。和最优子集选择类似，而需要先确定$k$值，才能得到最终的子集选择结果。
前向逐步选择算法属于贪婪算法，无法得到最优解。但该算法仍然会比最优子集算法受欢迎，因为：
- 运算量(computational)：运算简单，总是可以高效地得到一系列的子集选择结果$\mathcal{M}_k$，即便$p\gg N$。
- 统计意义(statistical)：相比最优子集选择，前向逐步选择算法的搜索过程具有更加严格的约束条件，所以前向逐步选择算法会有更低的估计方差，但其估计偏差可能也会增大。
前向选择算法在每一步的搜索过程中，需要遍历所有剩余的预测变量，然后依次重新进行最小二乘计算，并选择预测精度最佳的预测变量添加到预测变量子集中。

后向逐步选择(backward stepwise selection)是从包含所有的预测变量开始，然后通过$z$检验的方式，每一步丢弃一个$z$值最小的预测变量，然后重新应用最小二乘算法计算模型系数。后向逐步选择算法是前向逐步算法的逆过程，性能也极其接近，但后向逐步选择算法无法应用于$p>N$的场景。

混合逐步选择(hybrid stepwise selection)综合了前向/后向两种逐步选择算法的思想。在每一步的搜索过程中，会分别进行前向(添加最大提升模型性能的预测变量)和后向(丢弃对模型性能影响最小的预测变量)的搜索，然后同过某些准则(AIC，BIC等)来决定该步是选择前向还是后向。

前向分段回归

前向分段回归(forward stagewise regression, FS)比前向逐步回归更加严格。前向分段算法的流程如下：

初始状态，同样仅包含截距而其他的系数均为0；
在每一次的搜索步骤中，选择与残差相关性最高的预测变量$X_j$；
计算残差在该预测变量上的回归系数$\beta_j^{(n)}$(其他预测变量对应的系数不变)，并将该回归系数累加回之前的$\beta_j^{(n-1)}$ ；
更新残差，并跳转到步骤2，进行下一次的搜索步骤，直到残差与任何预测变量均无相关性。

可以看出，分段回归在每个步骤中仅仅更新了特定的一个回归系数，而不是像逐步回归算法那样重新进行所有回归系数的最小二乘计算。因此，相比前向逐步回归，该算法拟合速度慢，尤其是在高纬度的回归问题中。慢速拟合实际上是指搜索过程的每一步迈的步子都很小，避免了前向逐步回归的贪婪，在维度下可以获得更佳的性能。

几种子集选择算法的比较

ESLII Figure3.6对比了上述几种子集选择的估计精度以及收敛速度。这里，我们通过Python来还原ESLII Figure3.6。

“未完待续，代码调试ok后马上更新”

参考文献

[1]: http://blog.csdn.net/jteng/article/details/40823675 模型选择之AIC与BIC