台湾大学林轩田《机器学习基石》学习笔记第15讲—— Validation

上节课我们引入了augmented error，并学习如何通过加入regularizer来限制model complexity，并求得augmented error的最小值。从开始到现在我们已经学习到很多模型，但究竟哪些模型能得到更好的泛化能力呢？这节课我们将来探讨一下这个问题。
一、Model Selection Problem
台湾大学林轩田《机器学习基石》学习笔记第15讲—— Validation

对于一个简单的binary classification问题，模型上，我们就有多维的选择：

算法A的选择（PLA、pocket、linear regression…）
迭代次数T的选择
学习速率η的选择
特征转换feature transform φ的选择
正则化regularizer的选择
正则化系数λ的选择

不同的选择搭配，有不同的机器学习效果。
台湾大学林轩田《机器学习基石》学习笔记第15讲—— Validation

我们的目标是找到一个g使得Eout最小，但实际情况是Eout我们并不知道，我们并没有办法去衡量Eout究竟是多少。
那究竟如何来选择这个g呢，或者说是模型？
我们首先想到可以通过Ein来做选择，只要Ein越小越好，这样是否可行呢？
我们知道 $\phi_{1126}$ 找到的Ein往往会比 $\phi_{1}$ 要小，但这个代价会导致严重的overfitting，即bad generalization；
那假设我们在几个不同的Hypothesis set中分别找出最小的Ein再做比较呢？也不行，因为等效的Hypothesis set变大了， $d_{vc}$ 变大，同样容易导致overfitting，获得很差的generalization；
所以通过Ein来选择是不可行的！
那么通过一个另外的测试数据集 $D_{test}$ 可行么？
根据finite-bin Hoffding不等式，只要我们的模型个数M越小， $D_{test}$ 数目越大，那么 $E_{test}$ 就会越接近 $E_{out}$ ;
但是问题是这样的 $D_{test}$ 我们并不好获得。
既然使用 $E_{in}$ 和 $E_{test}$ 都有自己的局限性，但其优点分别是找到一个小的 $E_{in}$ 和使用 $E_{test}$ 来检验generalization，那么折中一下：
找到一个 $E_{val}$ ，它是通过数据集 $D_{val}\subset D$ ，一来 $D_{val}$ 是我们方便获取的，二来 $E_{val}$ 可以用来替代 $E_{test}$ ；
验证集 $D_{val}$ 是从训练集D中抽取并独立出来的，模型的训练使用除了 $D_{val}$ 之外的数据，模型的验证则使用验证集 $D_{val}$ 。

二、Validation
台湾大学林轩田《机器学习基石》学习笔记第15讲—— Validation

D= $D_{train}$ + $D_{val}$
关于验证集 $D_{val}$ ，有如下几点特征：
$D_{val}\subset D$ ， $D_{val}$ 用来充当测试集；
$D_{val}$ 独立同分布（iid）于P(x,y)，即 $D_{val}$ 是从D随机抽样出来的K个sample组成的集合；
为了保证 $D_{val}$ 是"干净"的，只能使用 $D_{train}$ 用于模型训练；
假设有M种模型hypothesis set， $D_{val}$ 的数量为K，那么从每种模型m中得到一个在Dval上表现最好的矩，再横向比较，从M个矩中选择一个最好的 $m^*$ 作为我们最终得到的模型；
$g_m^-$ 从 $D_{train}$ 中得到最好的g，而总样本D对应的最好的矩为 $g_m$ 。根据之前的leraning curve很容易知道，训练样本越多，得到的模型越准确，其hypothesis越接近target function，即D的 $E_{out}$ 比 $D_{train}$ 的 $E_{out}$ 要小：

上图总结一下整个学习的过程：
首先把数据集D分为两部分：一部分用于训练为 $D_{train}$ ，另一部分用于验证为 $D_{val}$ ；
假设共有M个模型，那么每个模型在 $g_m^-$ 上进行训练，并分别得到最好的 $g_m^-$ ；
再用 $D_{val}$ 对 $g_m^-$ 进行验证，选出一个最佳的叫做 $g_{m^*}^-$ ，那么该 $g_{m^*}^-$ 所对应的那个模型 $H_{m^*}$ 被选择；
最后使用该模型对整个D进行训练，得到最终的 $g_{m^*}$ 。

那么这么做有什么好处呢，下面我们通过一个例子来解释一下：
台湾大学林轩田《机器学习基石》学习笔记第15讲—— Validation
图标中横轴代表验证集的大小K，纵轴是Eout的大小：

黑色实线：这是完全通过Ein来选择，即没用使用 $D_{val}$ ，因此是与K无关的直线，但它这种方法通常Eout比较大；
黑色虚线：这是通过 $D_{test}$ 获得的，由于 $D_{test}$ 与实际数据很接近，因此Eout比较低，但实际上很难实现；
红色实线：表示使用 $D_{val}$ ，但是最终选取的矩是 $g_m^-$ ，其趋势是随着K的增加，它对应的Eout先减小再增大，当K大于一定值的时候，甚至会超过黑色水平线，这是因为随着K的增大，相对应的用于训练的 $D_{train}$ 会减小，Eout(train)本身就比较大；
蓝色实线：表示也使用 $D_{val}$ ，最终选取的矩是 $g_{m^*}$ ，其趋势是随着K的增加，它对应的Eout先缓慢减小再缓慢增大，且一直位于红色曲线和黑色直线之下。因此次方法最好。
当K值很大时， $E_{val}\approx E_{out}$ ，但是 $g_m^-$ 与 $g_m$ 相差很大；
当K值很小是， $g_m^-\approx g_m$ ，但是 $E_{val}$ 与 $E_{out}$ 可能相差很大；
所以有个折中的办法，通常设置 $k=\frac N5$ 。

三、Leave-One-Out Cross Validation
台湾大学林轩田《机器学习基石》学习笔记第15讲—— Validation

考虑一个极端的例子，我们取 $D_{val}$ 的数量为K=1，这时候 $D_{train}$ 和D就很接近了，这样 $g_m^-$ 与 $g_m$ 也会很接近，这样有个缺陷是 $E_{val}$ （这里我们称之为 $e_n$ ）与 $E_{out}$ 可能相差很大；
那么如果我们针对D所有N个数据都重复上一步骤，把得到的 $e_n$ 做个加权平均，得到leave-one-out cross validation estimate $E_{loocv}$ ；
那么这个 $E_{loocv}$ 是否接近于Eout(g)呢？
举个栗子：
有两种模型用来做linear regression问题，每次将一个点作为验证集，其他两个点作为训练集，最终将得到的验证误差求平均值，就得到了 $E_{loocv}(linear)$ 和 $E_{loocv}(constant)$ ；
比较两个值的大小，取值小对应的模型即为最佳模型。
以上推导得出 $E_{loocv}(H,A)$ 的期望值和 $E_{out}(g^-)$ 的期望值是相近的，这说明leave-one-out这种方法是可行的。
再举个之前识别手写字的例子：
蓝色曲线是采用 $E_{in}$ 进行模型选择，当使用多项式越高阶的话 $E_{in}$ 就会越小，但同时 $E_{out}$ 会很大，这就是之前提到的overfitting；
黑色曲线是采用leave-one-out方法，曲线和 $E_{out}$ 很接近，经过 $E_{loocv}$ 选择的模型在实际应用中表现比 $E_{in}$ 好太多了。

四、V-Fold Cross Validation
台湾大学林轩田《机器学习基石》学习笔记第15讲—— Validation

虽然leave-one-out能够很好地帮我们做模型选择，但计算量太大；
那么退一步，我们不再每次选出一个数据做validation，而是把总的数据样本D随机分成V份，取1份做validation，而剩下的V-1份对模型进行训练，我们把这种方法叫做V-fold cross validation；
一般的实际应用中我们取V=10。

总结一下：
training model：针对每个model对hypothesis进行选择
validation schemes：对不同模型选出的hypothesis进行验证并选出最好的
test method：hypothesis的好坏最终还是需要测试集来最终测试得到
validation一般来讲还是比较有用的，但是由于其数据也是来源于数据集，所以并不能保证交叉验证的效果好，它的模型一定好。只有样本数据越多，越广泛，那么Validation的结果越可信，其选择的模型泛化能力越强。

五、总结
本节课主要介绍了Validation验证。先从如何选择一个好的模型开始切入，例如使用 $inE_{in}、E_{test}$ 都是不太好的，最终使用 $E_{val}$ 来进行模型选择。然后详细介绍了Validation的过程。最后，介绍了Leave-One-Out和V-Fold Cross两种验证方法，比较它们各自的优点和缺点，实际情况下，V-Fold Cross更加常用。

台湾大学林轩田《机器学习基石》学习笔记第15讲—— Validation

相关推荐