1. Cross-Validation on Classification Problems

Cross-Validation用于分类任务概念

在系列前文中，描述的都是$Cross-Validation$在回归任务中的应用，并使用$MSE$量化Test Error，但$Cross-Validation$同样可以应用于分类任务中。

在分类任务中，$Cross-Validation$的用法和前文一致，不一样的地方在于没有使用$MSE$来量化误差，而是使用错误分类的个数。
举个例子，在分类任务中，$LOOCV$的Error Rate计算如下：
$CV_{(n)} = \frac{1}{n}\sum_{i=1}^{n}Err_i$
这里的$Err_i = I(y_i \neq \hat{y_i})$，$I$是指示函数，但括号内条件满足时值为$1$，否则值为$0$。

Cross-Validation用于分类任务实例

首先生成模拟数据，并选定Logistic Regression作为分类模型。由于数据为生成数据，可以得到此时的True Test Error=0.201，而此时的Bayes Error Rate=0.133，这说明了当前的Logistic Regression的灵活度难以完成对该生成数据的Bayes Decision Boundary建模。
但通过采用$predictors$的多项式形式，可以将Logistic Regression扩展为非线性决策边界。举个例子，Logistic Regression的二次型如下：
- 若采用上述形式，Test Error Rate将会从0.201降低为0.197。
- 类似上面，拟合一个包含三次项形式$predictor$的Logistic Regression，Test Error Rate降低为0.160。
- 而拟合一个包含四次项形式的，Test Error Rate稍微上升，为0.162。
但在实际应用中，Bayes Decision Boundary和Test Error Rate是未知的，那么我们如何决定使用上述4中Logistic Regression的哪一种形式呢？答案是：Cross-Validation。
- 可以使用$10-fold~CV$的方式分别训练不同自由度的Logistic Regression方法（多项式的次数从1到10）
- 从图中可以发现，Training Rate随着模型自由度的提升而降低（虽然单调下降，但是随着模型自由度的增加，Training Error Rate总体上呈下降的趋势）。
- 作为对比，Test Error展现出一个$U$型，即先下降再上升。说明自由度太高，模型可能过拟合了，所以在$U$型底部的模型应该是一个维持了$bais-variance~trade-off$的模型。
- 虽然一定程度上，$10-fold~CV$ Error Rate低估了错误率，但四阶多项式时其达到了最小值，这与三阶多项式测试曲线的最小值相当接近。
同样，可以使用$KNN$方法用于对比
- 可以发现，随着$K$值的减小，Training Rate随着模型灵活度的提高而再次下降（对于$KNN$，$K$越大，模型的自由度越低）。
- 同样，Cross-Validation Error Curve低估了Test Error Rate，但对于寻找最优$K$，它还是很有帮助的。

2. BootStrap（自举法）

$BootStrap$是一个广泛适用、功能强大的统计工具，可以用来量化和估计统计学习方法的不确定性。

一个简单的例子是，$BootStrap$可以用来估计线性回归拟合系数的标准误差。
$BootStrap$的强大之处在于它可以很容易的应用于各种各样的统计学习方法。

在下面的例子中，我们将讨论如何使用$BootStrap$评估线性模型参数的变化性。

BootStrap实例

假设我们想将一笔固定的金额投资于两种分别产生$X$和$Y$回报的金额资产，其中$X$和$Y$时随机变量。
- 通过参数$\alpha$来分配投资的比例，将$\alpha$比例的钱投资$X$，$(1-\alpha)$比例的钱投资$Y$。
- 由于$X,Y$的回报会不断变化，我们想要求出令投资风险最小的$\alpha$。换句话说，我们想要最小化：
  $Var(\alpha X + (1-\alpha)Y)$
  即总回报的方差很小，偏离均值的幅度很少，那么风险就比较小。
- 为了最小化风险，可以通过下式来计算$\alpha$：
  $\alpha = \frac{\sigma_Y^2 - \sigma_{XY}}{\sigma_X^2 + \sigma_Y^2 - 2\sigma_{XY}}$
  其中 $\sigma_X^2 = Var(X)$ ， $\sigma_Y^2 = Var(Y)$ ， $\sigma_{XY} = Cov(X, Y)$
但在实际应用中， $\sigma_X^2,\sigma_Y^2, \sigma_{XY}$ 是未知的，但我们可以通过一个已有的测量$X,Y$的数据集来估计 $\hat{\sigma}_X^2,\hat{\sigma}_Y^2, \hat{\sigma}_{XY}$ ，从而带入前面的式子中求得$\alpha$。
- 为此，我们从真是分布中生成100批数据，并估计分布的$\hat{\alpha}$值。
- 重复上述操作1000次，那么就可以得到 $\hat{\alpha}_1, \hat{\alpha}_2, \hat{\alpha}_3,...,\hat{\alpha}_{1000}$ 。
- 我们设置生成分布数据的 $\sigma_X^2=1,\sigma_Y^2 = 1.25, \sigma_{XY} = 0.5$ ，故我们可以算出真实的$\alpha=0.6$。而此时1000个$\hat{\alpha}$的估计可以得到：
  $\bar{\alpha} = \frac{1}{1000}\sum_{r=1}^{1000}\hat{\alpha_r} = 0.5996$
- 这时${\bar{\alpha}}$和0.6非常接近了，这个值的标准差为：
  $\sqrt{\frac{1}{1000-1}\sum_{r=1}^{1000}(\hat{\alpha_r - \bar{\alpha}})^2} = 0.083$
但在实际中，上述估计$SE(\hat{\alpha})$的方式难以应用，因为真实数据的分布是未知的，故我们无法从分布中多次采样新的数据。但$BootStrap$允许计算机来模拟这个采样过程，这就确保无需使用额外的样本来估计$\hat{\alpha}$了。$BootStrap$不再从分布中生成随机数据，而是在原始数据集中重复采样样本。
- 假设有一个简单的数据集$Z$，从数据集$Z$中随机放回采样$n$个样本得到$bootstrap$数据集 $z^{*i}$ 。由于是放回采样，这意味着 $Z^{*i}$ 中的样本是可以重复的。
- 重复上述步骤$B$次，可以获得 $Z^{*1},Z^{*2},Z^{*3},...,Z^{*B}$ ，同样我们可以计算出相对应的$\alpha$估计： $\hat{\alpha}^{*1},\hat{\alpha}^{*2},\hat{\alpha}^{*3},...,\hat{\alpha}^{*B}$ 。
- 于是，可以计算这些$bootstrap$的标准误差如下式：
  $SE_B(\hat{\alpha}) = \sqrt{\frac{1}{B-1}\sum_{r=1}^B(\hat{\alpha}^{*r} - \frac{1}{B}\sum_{r^{'}=1}^B\hat{\alpha}^{*r})}$
  这就是对原始数据的$\hat{\alpha}$的估计
最后，简单总结一下$BootStrap$：从原始数据集中随机放回采样$n$个样本$B$次，构建$B$个$bootstrap$数据集。通过对这些数据集的计算，获取统计量的分布。