Linear Model Selection and Regularization

在回归方法中，标准的线性模型如下：

$Y = \beta_0 + \beta_1x_1 + ... + \beta_px_p + \epsilon$

用来描述Response Y和一系列变量$x_1, x_2, … ,x_p$之间的关系。在前文中，我们使用最小二乘来拟合模型，的确线性模型在推理方面有自己的明确方式，在实际应用中也和非线性方法有得一拼。所以，在进入非线性世界之前，我们先讨论一些线性模型改进的方法，使用可选的方法来替代普通最小二乘。为什么要用其他的拟合方式取代最小二乘？正如下文大家将看到的，替代的方案可以产生更好的预测精度和模型的可解释性。

Prediction Accuracy

假设Response和Predictors之间的关系的确是线性的，最小二乘估计的bias（偏差）将会较低。

当$n >> p$，即样本数量远大于变量个数的时候，最小二乘估计趋向于有较低的方法。因此，在测试样本上会表现较好。
当$n$仅小幅度大于$p$时，那在最小二乘拟合的过程中将会出现很多变化（相对于大样本来说，小样本变化更多），这会导致过拟合从而使得在测试集上预测效果很差。
当$n < p$时，就不存在唯一的最小二乘系数估计（方程个数比未知数还要少，那么未知数的结果应该有多个解，类似于线代中的奇异矩阵？）因此，最小二乘不适合。

针对$n$仅小幅度大于$p$时，可以通过约束方法；针对$n < p$，而可通过缩小估计稀疏的方法；以上两个方法通常可以在偏差几乎不增加的情况下大幅度减少方差。这可以让模型在测试集上的准确性得到显著的提高。

Model interpretability

通常来说，大部分回归模型中的变量实际上和Response并无太大关联。若包含这些变量，还会增加模型不必要的复杂度。那么，通过消除这些变量，或使得相应的系数估计值为0，我们就可以得到一个更容易解释的模型。但最小二乘很难产生值为0的系数估计，所以在下文中，我们会见到一些Feature Selection（特征选择）和Variable Selection（变量选择）的方法，从而在多元回归的模型中排除不相关的变量。
除最小二乘外，还有很多其他的选择，包括经典的和先进的方法，后文将主要讨论三种重要方法
- Subset Selection
  
  该方法首先确定了$p$个Predictors中，与Response最相关的Predictor所构成的子集。我们再用该子集去应用最小二乘法
- Shrinkage（特征缩减技术）
  
  该方法使用所有$p$个Predictors来拟合一个模型。然而相对于最小二乘估计，估计系数可缩小到接近于零。该Shrinkage（Regularization）可以达到减少方差的效果，根据不同的Shrinkage方法，有些系数可能恰好为零。因此，Shrinkage方法可以进行变量选择（Variable Selection）。
- Dimension Reduction
  
  该方法先将$p$个Predictors投影到M维的子空间上（M < P），再通过计算M个不同的线性组合投影来实现。然后使用该M作为Predictors，用最小二乘法拟合线性回归模型。

在下文中，我们将更详细的描述这些方法，以及它们的优缺点。虽然所举的例子仅用于回归，但同样的概念也会适用于分类。

Subset Selection

Best Subset Selection

为了使用Best Subset Selection，我们需要对$p$个Predictors所有可能的组合，拟合最小二乘回归。比如说：
- p个只包含一个Predictor的模型
- 所有$\left(\begin{matrix}p \\ 2\end{matrix}\right) = p(p-1)/2$个包含2个Predictors的模型
- 依此类推…
最后从上述训练好的模型中挑选出效果最好的那一个
但从通过Best Subset Selection得到的$2^p$个模型中，挑选出最佳模型并不简单，这通常分为3个阶段
- 定义$M_0$为空模型（Null Model），$M_0$包含0个Predictors。这个模型仅能简单预测每个观测值的样本均值。
- 对于$k = 1,2,…,p$
  - 拟合所有$\left(\begin{matrix}p \\ k\end{matrix}\right)$个包含k个Predictors的模型
  - 从这$\left(\begin{matrix}p \\ k\end{matrix}\right)$个模型中选择最好的那个，称之为$M_k$。这里最好的定义是有着最小的RSS值，或者最大的$R^2$。
- 使用Cross-validate Prediction Error，$C_p$，AIC，BIC，或者adjusted $R^2$从$M_0, M_1, …, M_p$中选择最好的那个模型。
在上述过程中，步骤2定义了训练集上每个子集中最好的那个模型，把最优模型的可选个数从$2^p$降低为$(p+1)$个。所以问题转化为从剩下的$(p+1)$个模型中选择最优模型。然而问题在于，随着Predictors个数的增加，RSS指标逐渐下降，同时$R^2$指标逐渐上升，这会导致选择最优模型永远是Predictors最多的那一个，不符合我们的目的：排除对Response结果无关的Predictors。
故问题得根源在于评价指标：RSS越低，$R^2$越高，都表明模型有着低Train Error，但我们希望选择测试误差较低的模型。（根据前系列文章，Train Error往往低于Test Error，低Train Error并不能保证低Test Error）。所以在步骤3中，需要使用Cross-validate Prediction Error，$C_p$，AIC，BIC，或者adjusted $R^2$指标选择最优模型。
同样的方法也适用于其他的统计方法，如Logistic Regression。在Logistic Regression的情况下，上述算法的步骤2将不会使用RSS对模型排序，而是使用偏差，一种类似于RSS但作用范围更广的度量方法。偏差是最大对数似然的负两倍；偏差越小，模型越好。
虽然Best Subset Selection很简单且有效果，但对算力要求过高。一般来说，p个Predictors有$2^p$种可选模型；当p=10，$2^p = 1024$；当p=20，这简直是一场灾难；当p>40时，再好的计算机也很难保证方法的可行性。为了排除某些选择，有一些称之为“分支界限技术”的方法可排除某些选项。但随着p的增大，这些技术也会出现局限性。故需要有更高效的子集选择方法。

Forward Stepwise Selection

相比于Best Subset Selection, Forward Stepwise Selection的计算效率很高，其考虑的模型个数远小于$2^p$个。

Forward Stepwise Selection从不包括Predictors的空模型开始，然后逐渐的往模型中加入Predictors，一次加一个，直到所有的Predictors都在模型中。具体来说，每一步中，提升模型拟合能力最大的Predictors被置入模型中，具体算法如下：
- 定义$M_0$为NULL Model，不包含任意一个Predictor
- 对于$k=0, 1, …, p-1$
  - 考虑所有$(p-k)$个往$M_k$中增加一个额外的Predictor的模型
  - 从$(p-k)$各模型中选择最好的那个，称之为$M_{k+1}$。同样，最好模型的定义为有着最小的RSS或者最高的$R^2$
- 从$M_0,M_1,…,M_p$中采用Cross-validate Prediction Error，$C_p$，AIC，BIC，或者adjusted $R^2$，挑选出最优的那个模型。
相比于Best Subset Selection需要拟合$2^p$个模型，Forward Stepwise Selection仅需要拟合一个Null Model，以及第$k$轮中的$(p-k)$个模型。所以Forward Stepwise Selection需要拟合的模型个数为$1 + \sum_{k=0}^{p-1}(p-k) = 1 + p(p+1)/2$。这是个实质性的差别，当$p=20$的时候，Best Subset Selection需要拟合1048576个模型，而Forward Stepwise Selection仅需要拟合211个模型。
Forward Stepwise Selection相较于Best Subset Selection的计算优势很明显，但其选择的模型并非是全局最优。举个例子，一个有3个Predictors的数据集$p=3$，当$p=1$时，best model为$X_1$；当p=2时，best model为$X_2, X_3$。对于Best Subset Selection，在$p=1,p=2$时都能挑选出最优的模型。但对于Forward Stepwise Selection，当$p=1$时，best model为$X_1$；当$p=2$时，它只能从$X_2,X_3$中挑选出一个最优的加进去，从而错过了Best Model $X_2, X_3$。

Backｗard Stepwise Selection

和Forward Stepwise Selection类似，Backward Stepwise Selection相较于Best Subset Selection提供了更高效的计算。与Forward Stepwise Selection不同的是，它从包含了所有p个Predictors的模型开始，并逐渐对模型帮助最小的Predictor。
Backward Stepwise Selection的具体算法如下：
- 定义$M_p$为Full Model，即包含所有p个predictors
- For $k=p, p-1, …, 1$：
  - 考虑所有的从$M_k$中去除一个Predictor从而剩下$(k-1)$个predictors的模型
  - 从这$k$个模型中，选择最优的模型称之为$M_{k-1}$。同样，最好模型的定义为有着最小的RSS或者最高的$R^2$
- 从$M_0,M_1,…,M_p$中采用Cross-validate Prediction Error，$C_p$，AIC，BIC，或者adjusted $R^2$，挑选出最优的那个模型。
和Forward Stepwise Selection类似，Backward Stepwise Selection只需要搜索$1 + p(p+1)/2$个模型，所以可以应用于$p$过大从而难以采用Best Subset Selection的方法。同理，Backward Stepwise Selection也无法保证获取最优模型。

Hybrid Approaches（混合方法）

Best Subset Selection，Forward Stepwise Selection，Backward Stepwise Selection这三个方法往往得到相似但不完全相同的模型。作为可选项，Forward和Backward是可以混合在一起使用的。

首先，Predictor根据顺序加入模型中，类似于Forward
再去除对模型帮助不大的变量

这种方法近似于做Best Subset Selection，但又保证了Forward和Backward的计算优势。

Choosing the Optimal Model

Best Subset Selection，Forward Stepwise Selection，Backward Stepwise Selection都会得到一系列包含p个Predictors的模型，我们需要判断哪个模型是最好的。

前文提到了，一个包含所有p个Predictors的模型将会有最小的RSS和最大的$R^2$，这就导致包含了所有Predictors的模型会被选中，不符合筛选无用Predictors的目的。且RSS，$R^2$都和Training Error相关，往往Training Error难以估计Test Error，所以$R^2$，RSS并不适合作为挑选最佳模型的指标
为了选择和测试误差相关的最优模型，我们得估计Test Error，总体来说有两种常见的方式：
- 通过调整Training Error解释过拟合带来的偏差，从而间接地估计Test Error。
- 使用Validation Set Approach，Cross-Validation Approach来直接估计Test Error

$C_p$, AIC, BIC, 以及 Adjusted $R^2$的引入

在前文中，我们提到Training Set得MSE往往低估了Test MSE（$MSE = \frac{RSS}{n}$）。因为当拟合一个模型得时候，我们使用的是训练集，让模型拟合训练集时Training RSS（Not Test RSS）越来越小。尤其当变量越来越多得时候，Training Error将会降低，但Test Error不会。
所以，Training Set RSS，Training Set $R^2$并不能用从包含不同个数变量的模型中挑选出一个最优模型。但可以使用一些技术来调整模型的训练误差，从而从包含不同变量个数的模型中寻找最优模型。一共有4种方法，它们分别为：$C_p$, AIC, BIC, 以及 Adjusted $R^2$。

$C_p$