台湾国立大学（林轩田）《机器学习基石》（第15讲）Validation
课程地址：https://class.coursera.org/ntumlone-001/class
课件讲义：http://download.****.net/download/malele4th/10208897
注明：文中图片来自《机器学习基石》课程和部分博客
建议：建议读者学习林轩田老师原课程，本文对原课程有自己的改动和理解
Lecture 15 Validation
上节课我们主要讲了为了避免overfitting，可以使用regularization方法来解决。在之前的
目录
1 模型选择问题
机器学习模型建立的过程中有许多选择，例如对于简单的二元分类问题，首先是算法A的选择，有PLA，pocket，linear regression，logistic regression等等；其次是迭代次数T的选择，有100，1000,10000等等；之后是学习速率η的选择，有1，0.01,0.0001等等；接着是模型特征转换Φ的选择，有linear，quadratic，poly-10，Legendre-poly-10等等；然后是正则化regularizer的选择，有L2，L1等等；最后是正则化系数λ的选择，有0，0.01，1等等。不同的选择搭配，有不同的机器学习效果。我们的目标就是找到最合适的选择搭配，得到一个好的矩g，构建最佳的机器学习模型。
下面比较一下之前讲的两种方法，第一种方法使用Ein作为判断基准，使用的数据集就是训练集D本身；第二种方法使用Etest作为判断基准，使用的是独立于训练集D之外的测试集。前者不仅使用D来训练不同的gm，而且又使用D来选择最好的gm∗，那么gm∗对未知数据并不一定泛化能力好。举个例子，这相当于老师用学生做过的练习题再来对学生进行考试，那么即使学生得到高分，也不能说明他的学习能力强。所以最小化Ein的方法并不科学。而后者使用的是独立于D的测试集，相当于新的考试题能更好地反映学生的真实水平，所以最小化Etest更加理想。
2 validation
3 leave-one-out cross validation（留一法交叉验证）
下面用一个例子图解留一法的过程：
举一个例子，使用两个特征：Average Intensity（平均强度）和Symmetry（对称性）加上这两个特征的非线性变换（例如高阶项）来进行手写数字识别。平面特征分布如下图所示：
Error与特征数量的关系如下图所示：
很明显可以看出，使用
4 V-Fold Cross Validation
接下来我们看看Leave-One-Out可能的问题是什么。首先，第一个问题是计算量，假设N=1000，那么就需要计算1000次的Eloocv，再计算其平均值。当N很大的时候，计算量是巨大的，很耗费时间。第二个问题是稳定性，例如对于二分类问题，取值只有0和1两种，预测本身存在不稳定的因素，那么对所有的Eloocv计算平均值可能会带来很大的数值跳动，稳定性不好。所以，这两个因素决定了Leave-One-Out方法在实际中并不常用。
针对Leave-One-Out的缺点，我们对其作出了改进。Leave-One-Out是将N个数据分成N分，那么改进措施是将N个数据分成V份（例如V=10），计算过程与Leave-One-Out相似。这样可以减少总的计算量，又能进行交叉验证，得到最好的矩，这种方法称为V-折交叉验证。其实Leave-One-Out就是V-折交叉验证的一个极端例子。
所以呢，一般的Validation使用V-折交叉验证来选择最佳的模型。值得一提的是Validation的数据来源也是样本集中的，所以并不能保证交叉验证的效果好，它的模型一定好。只有样本数据越多，越广泛，那么Validation的结果越可信，其选择的模型泛化能力越强。
5 总结
本节课主要介绍了Validation验证。先从如何选择一个好的模型开始切入，例如使用Ein、Etest都是不太好的，最终使用Eval来进行模型选择。然后详细介绍了Validation的过程。最后，介绍了Leave-One-Out和V-Fold Cross两种验证方法，比较它们各自的优点和缺点，实际情况下，V-Fold Cross更加常用。