Statistic Learning 4

1. Resampling Methods

重采样方法是现代统计学习中不可缺失的一环。它们包括：

• 重复的从训练集中采样
• 重复的拟合模型以获得额外的信息

重采样方法会耗费计算机资源，因为需要从训练集中采集不同的子集来多次拟合同一个模型。下面，我们将要讨论两个较为常用的重采样方法：

• $Cross-Validation$（交叉验证）
• $BootStrap$

其中交叉验证估计测试误差以灵活的选择模型；$BootStrap$衡量了给定方法参数估计的准确性。

2. Cross Validation

Test Error Rate, Train Error Rate

• Test Error Rate得到了一个方法预测新样本的平均误差；而Train Error Rate得到了一个方法在训练过程中Response和Label的误差。
• 然而，Test Error Rate往往高于Train Error Rate

当缺少一个较大的测试集来估计Test Error Rate的时候，还有很多其他的替代方案如通过训练集得到Test Error Rate。在交叉验证中，训练样本中一个假冒的子集会扮演测试集。

The validation set approach

• 假设我们要估计一个模型的Test Error Rate，Validation set approach是个非常简单的策略。它将所有样本随机分成2份，一份作为Training Set，另一份作为Validation Set(Hold-out Set)。模型在Training Set上进行训练，并通过Validation Set来验证模型的能力。尝试用$MSE$来评价模型的验证效果，它是一种对Test Error Rate的评估。
• 现在使用Auto数据集来验证Validation Set Approach方法
  • 在Auto dataset中，mpg和horsepower有着非线性的关系，所以在线性回归模型中加入$horsepower^2$这一项，将会使得模型获得更好的效果。那么，我们很自然的想知道，三次拟合或者更高次的拟合会不会有更好的效果呢？在前文中，我们采用$p-value$来检测这一点，但现在可以使用验证方法如$MSE$来回答这个问题。
  • 我们将392个样本随机分为2份，即Training Set和Validation Set各196个样本。我们使用Training Set拟合不同的回归模型（从1次到高次），并在Validation Set上使用$MSE$作为验证误差的度量，以评估各模型的性能。
  • 从实验结果上，我们可以发现：二次拟合明显优于线性拟合；然而三次和之后的高次拟合MSE不减反增，这证明了它们并没有很好的提升模型的性能。当整个数据集被重复的随机分成不同的Training Set和Validation Set，并训练模型后，会发现各个MSE曲线各不相同，它们对于哪个模型能够获得最好的性能并没有统一的意见。我们仅能得到的结论是：二次项的加入大大提升了模型的性能，表现在MSE普遍降低，故线性回归不适合该数据集。
• Validation Set Approach很简单但有两个潜在的问题
  • 对所有数据集，不同的拆分发，训练出来的模型在验证集上$MSE$各不相同，过于依赖特定的Training Set和Validation Set。
  • 在验证方法中，只用训练集中的样本拟合模型，故当训练样本较小时，验证集的Test Error Rate将被过高的估计。

3. Leave-One-Out Cross-Validation

• 简称$LOOCV$。假设有样本$\{(x_1, y_1), (x_2, y_2) …. (x_n, y_n)\}$，$LOOCV$每次从样本中挑选出一个样本作为Validation Set，剩下的$(n-1)$个样本当作Training Set。模型将会用$(n-1)$个样本来拟合模型，并用1个样本计算$MSE$值。

  $$MSE = (y_1 - \hat{y_1})^2$$

• 根据上述选择Test Set的方法，可将过程重复$n$次得到$n$个$MSE$的值。$LOOCV$估计Test MSE的方法为，求$n$个Test Error估计的均值：

  $$CV(n) = \frac{1}{n}\sum_{i=1}^nMSE_i$$

• $LOOCV$相对于Validation Set Approach方法有以下两个优点

  • 偏差低（far less bias）。bias高会导致过高估计Test Error Rate，因为浮动性太大，而造成这个问题的主要原因是训练样本不充足。而$LOOCV$每次都选取$n-1$个样本，相对于Validation Set Approach的$\frac{n}{2}$，Training Set大得多。故偏差高的问题得到缓解。
  • Validation Set Approach中的Training Set中的样本随机性太强，导致各个MSE曲线各不相同，无法得出有用的结论。而$LOOCV$总会得出相似的MSE曲线，故在拆分训练集/测试集时没有随机性。

• 然而，使用$LOOCV$对算力要求较高，因为要测试$n$次模型。当$n$过大时，会耗费大量的时间拟合最小二乘线性或者多项式回归中，但是可通过一个捷径减小$LOOCV$的开销至训练一个模型相当。公式如下：

  $$CV(n) = \frac{1}{n}\sum_{i=1}^n(\frac{y_i-\hat{y_i}}{1-h_i})^2$$
  • 其中，$\hat{y_i}$未原始最小二乘的第$i$个拟合值；$h_i$是高杠杆点。这个值和原始的$MSE$相似，但第$i$个残差除以了$(1-h_i)$。$leverage$值位于$(\frac{1}{n}, 1)$之间，反应了一个样本对于拟合自身的影响。因此，高杠杆点的残差被正确的计算，从而使得等式成立。
  • 也就是说，影响Test Error Rate往往是异常点：离群点、高杠杆点。其中，高杠杆点的影响尤为明显，拟合$n$次模型就是为了消除这些异常点的影响。而通过上述捷径公式可直接消除异常点的影响，无需进行多次的拟合，但该方法并不一直使用。

4. K-Fold Cross-Validation

• $LOOCV$的一个替代品就是K-Fold CV，其步骤如下

  • 首先将训练集分成等大小的$k$组

  • 每次选择其中一组作为验证集，模型拟合剩余的$(k-1)$组，MSE计算均方差。

  • 重复$k$次后，K-Fold CV可用于计算下式的估计

    $$CV(k) = \frac{1}{k}\sum_i^kMSE_i$$

  不难发现，当$k=n$时，$LOOCV$是K-Fold CV的一个特殊形式。

• 在实践中，往往设置$k=5$或者$k=10$，那么K-Fold相对于$LOOCV$的优势在哪里呢？

  • 首先肯定是降低了计算量。$LOOCV$需要拟合$n$次模型，当$n$很大的时候，这几乎是场灾难。
  • $Bias-Variance-Trade-Off$。通过将训练集随机分成10个，并使用9个进行训练得到的Error Curve（误差曲线）的变化明显没有Validation Set Approach强烈。

• 我们再详细的看一下$Bias-Variance-Trade-Off$。

  • 当$k<n$时，K-Fold CV相对于$LOOCV$有着计算上的优势。我们将该优势放在一边，可以发现K-Fold CV一个不太明显但却更加重要的优点是：它相较于$LOOCV$对于Test Error Rate的估计会更加的精确，这和$Bias-Variance-Trade-Off$相关。
  • 在上文中，我们提到Validation Set Approach会对Test Error Rate估计过高，因为这个方法中的训练集仅为数据集的一半。在这个逻辑下，不难看出$LOOCV$给出的测试误差近似无偏估计（因为每个训练集包含$(n-1)$个样本，接近整体了，求的就是每个整体数据集训练出来的模型的MSE的均值）。
  • 而K-Fold CV，当$k=5$或$k=10$的时候，将会找到偏差较为中间的部分，因为每个训练集包含$\frac{n(k-1)}{k}$个样本，比$LOOCV$的方法少得多，但比Validation Approach多得多。所以，从减少偏差的角度，$LOOCV$优于K-Fold CV。
  • 但在估计的过程中，偏差（Bias）并不是唯一需要关心的，我们必须要同时考虑$Variance$。事实证明，当$k<n$时，$LOOCV$的$Variance$明显高于K-Fold CV。为什么？当我们进行$LOOCV$的时候，我们实际上室对$n$个拟合模型的输出进行平均，每个模型几乎都在相同的训练集上进行训练，因为这些输出高度相关。相比之下，K-Fold CV的输出相关性较小，因为每个模型的训练集的重叠度较小。
  • 因为许多高度相关量的均值比低相关量的均值，有更高的方差；因此，$LOOCV$产生的测试误差估计往往比K-Fold CV有更高的方差。