Coursera机器学习基石笔记week15

Validation

Model Selection Problem

针对模型建立的过程，如上图所示，不仅需要考虑算法的选择，还要考虑迭代次数，学习速率，特征转换，正则化，正则化系数的选择等等，不同的搭配，都有不同的机器学习效果。那么我们应该如何找一个最合适的搭配呢？

首先我们考虑通过找一个最好$E_{in}$Ein​来选择模型。

但是相对来说，$E_{in}$Ein​小的模型总是偏向于使用较大指数的特征以及尽量小的正则化，但是这又容易导致过拟合。而且假如每一种模型选择+训练会使模型复杂度变得比较高，从而使泛化能力变得比较差。

另外一种方法，如果有这样一个独立于训练样本的测试集，将M个模型在测试集上进行测试，看一下$E_{test}$Etest​的大小，则选取$E_{test}$Etest​最小的模型作为最佳模型：

但是，我们拿到的都是训练集D，测试集是拿不到的。所以，寻找一种折中的办法，我们可以使用已有的训练集D来创造一个验证集validation set，即从D中划出一部分$D_{val}$Dval​作为验证集。D另外的部分作为训练模型使用，$D_{val}$Dval​独立开来，用来测试各个模型的好坏，最小化$E_{val}$Eval​，从而选择最佳的$g_{m^∗}$gm∗​。

Validation

从训练集D中抽出一部分K个数据作为验证集$D_{val}$Dval​，$D_{val}$Dval​对应的error记为$E_{val}$Eval​。这样做的一个前提是保证$D_{val}$Dval​独立同分布（iid）于P(x,y)，也就是说$D_{val}$Dval​的选择是从D中平均随机抽样得到的，这样能够把$E_{val}$Eval​与$E_{out}$Eout​联系起来。D中去除$D_{val}$Dval​后的数据就是供模型选择的训练数据$D_{train}$Dtrain​，其大小为N-k。从$D_{train}$Dtrain​中选择最好的g，记为$g^−_m$gm−​。

假如D共有1000个样本，那么可以选择其中900个$D_{train}$Dtrain​，剩下的100个作为$D_{val}$Dval​。使用$D_{train}$Dtrain​训练模型，得到最佳的$g^−_m$gm−​，使用$g^−_m$gm−​对$D_{val}$Dval​进行验证，得到如下Hoffding不等式：

$E_{out}(g^-_m)\leq E_{val}(g^-_m)+O(\sqrt\frac{logM}{K})$Eout​(gm−​)≤Eval​(gm−​)+O(KlogM​​)

假设有M种模型hypothesis set，$D_{val}$Dval​的数量为K，那么从每种模型m中得到一个在$D_{val}$Dval​上表现最好的g，再横向比较，从M个g中选择一个最好的$m^∗$m∗作为我们最终得到的模型。

根据之前的leraning curve很容易知道，训练样本越多，得到的模型越准确，其hypothesis越接近target function，即D的$E_{out}$Eout​比$D_{train}$Dtrain​的$E_{out}$Eout​要小.

所以，我们通常的做法是通过$D_{val}$Dval​来选择最好的矩$g^−_{m^∗}$gm∗−​对应的模型$m^∗$m∗，再对整体样本集D使用该模型进行训练，最终得到最好的矩$g_{m^∗}$gm∗​。

如上图所示，我们先把数据集分为$D_{train}$Dtrain​，$D_{val}$Dval​。如果有M个模型，就分别让M个模型在$D_{train}$Dtrain​上跑，得到$g^-_m$gm−​,再分别让$g^-_m$gm−​在验证集上进行验证，选择表现最好的$g^-_m$gm−​。将对应的模型在整个数据集D上进行训练，得到最终的$g_{m^*}$gm∗​。

然后我们就可以得出下列不等式：

然后我们来感受下验证集在实际操作中的效果。

in-sample的曲线是不使用验证集的曲线，因此$E_{out}$Eout​与验证集数量没有关系，永远保持定值。
黑色虚线表示测试集非常接近实际数据，这是一种理想的情况，其$E_{out}$Eout​很小，同样也与K无关，实际中很难得到这条虚线。
红色曲线表示使用验证集，但是最终选取的矩是$g^−_{m^∗}$gm∗−​，其趋势是随着K的增加，它对应的$E_{out}$Eout​先减小再增大，当K大于一定值的时候，甚至会超过黑色水平线。
蓝色曲线表示也使用验证集，最终选取的是$g_{m^*}$gm∗​，其趋势是随着K的增加，它对应的$E_{out}$Eout​先缓慢减小再缓慢增大，且一直位于红色曲线和黑色直线之下。从此可见，蓝色曲线对应的方法最好，符合我们之前讨论的使用验证集进行模型选择效果最好。

这里提一点，当K大于一定的值时，红色曲线会超过黑色直线。这是因为随着K的增大，$D_{val}$Dval​增大，但可供模型训练的$D_{train}$Dtrain​在减小，那得到的$g^−_{m^∗}$gm∗−​不具有很好的泛化能力，即对应的$E_{out}$Eout​会增大，甚至当K增大到一定值时，比$E_{in}$Ein​模型更差。

根据之前的分析：

想要左边这个等式成立，k需要足够小，想要右边这个等式成立，k需要足够大。这就导致了矛盾，因此折中的办法是，一般设置k=$\frac{N}{5}$5N​。

Leave-One-Out Cross Validation

假如考虑一个极端的例子，k=1，也就是说验证集大小为1，即每次只用一组数据对$g_m$gm​进行验证。这样做的优点是$g^−_m≈g_m$gm−​≈gm​，但是$E_{val}$Eval​与$E_{out}$Eout​可能相差很大。为了避免$E_{val}$Eval​与$E_{out}$Eout​相差很大，每次从D中取一组作为验证集，直到所有样本都作过验证集，共计算N次，最后对验证误差求平均，得到$E_{loocv}(H,A)$Eloocv​(H,A)，这种方法称之为留一法交叉验证，表达式为：

这样求平均的目的就是为了让$E_{loocv}(H,A)$Eloocv​(H,A)尽可能地接近$E_{out}(g)$Eout​(g)。

接下来，我们从理论上分析Leave-One-Out方法的可行性，即$E_{loocv}(H,A)$Eloocv​(H,A)是否能保证$E_{out}$Eout​的矩足够好？假设有不同的数据集D，它的期望分布记为$ε_D$εD​，则其$E_{loocv}(H,A)$Eloocv​(H,A)可以通过推导，等于$E_{out}(N−1)$Eout​(N−1)的平均值。由于N-1近似为N，$E_{out}(N−1)$Eout​(N−1)的平均值也近似等于$E_{out}(N)$Eout​(N)。具体推导过程如下：

这就证明了留一交叉验证的可行性。

上图也可以证明在实际中，$E_{cv}$Ecv​比$E_{in}$Ein​来的更有用，更加接近$E_{out}$Eout​曲线的趋势。

V-Fold Cross Validation

接下来我们看看Leave-One-Out可能的问题是什么。首先，第一个问题是计算量，假设N=1000，那么就需要计算1000次的$E_{loocv}$Eloocv​，再计算其平均值。当N很大的时候，计算量是巨大的，很耗费时间。第二个问题是稳定性，例如对于二分类问题，取值只有0和1两种，预测本身存在不稳定的因素，那么对所有的$E_{loocv}$Eloocv​计算平均值可能会带来很大的数值跳动，稳定性不好。所以，这两个因素决定了Leave-One-Out方法在实际中并不常用。

因此我们引入了V-折交叉验证。

所以呢，一般的Validation使用V-折交叉验证来选择最佳的模型。值得一提的是Validation的数据来源也是样本集中的，所以并不能保证交叉验证的效果好，它的模型一定好。只有样本数据越多，越广泛，那么Validation的结果越可信，其选择的模型泛化能力越强。

总结

本节从使用$E_{in}$Ein​,$E_{test}$Etest​无法得出较好的$E_{out}$Eout​来引出使用$E_{val}$Eval​来进行模型选择。然后讲诉了使用validation set的过程。最后，又引出了Leave-One-Out和V-Fold Cross两种验证方法，比较它们各自的优点和缺点。