机器学习基石HOW BETTER部分(3)
标签：机器学习基石
第十五章
(crossly) reserve validation data to simulate testing procedure for model selection
模型选择问题
根据Ein(g)最小来选择模型也是行不通的。一方面容易造成overfitting；另一方面，假设有两个模型PK：算法A1在H1上让Ein最小；算法A2在H2上让Ein最小。最后选出来的g的效果是在H1∪H2上让EEin最小，也就说假设空间变成了H1+H2，额外增加了model complexity，容易造成bad generalization。
如果能找到一些测试数据，来看看哪一个模型的表现更好就选择哪个。如果用这样的方式，可以得到Hoeffding的理论保证如下图。看起来很棒，可是问题是我们找不到测试数据，测试数据就像考卷，不可能说考试之前就发下来的。
将这两者结合一下：把训练数据留一部分下来作为测试数据，用其他的训练数据来训练模型，然后用测试数据来测试模型的表现好坏。这是合理的作弊，这样就可以有测试资料了（测试资料一定要留着，不能收到污染。也就是说，不能参与任何选出模型的工作。）
验证（Validation）
同样，也会有Hoeffding不等式的保证。￥E_{test}就是以前的E_{in}$. 
那Validation Set的大小K应该如何选择？选择的K应该尽可能地让下面这三个Error约等式成立。
通常情况下，K取N/5。 Leave-One-Out Cross Validation
k要足够小，让Eout(g)和Eout(g−)很接近。又要很大，让Eout(g−)和Eval(g−)很接近。
考虑一个极端的情形，取非常小的K = 1。k足够小，让Eout(g)和Eout(g−)很接近。但是，这个时候，Eout(g−)和Eval(g−)就很不接近了。下面的en表示取第n笔数据作为validation data，所得到的Eval(g−)。en到底能不能告诉我们Eout(g)有多好呢？一个en当然不行，那把每笔数据都作为一次validation data然后平均起来，选择平均Error最小的作为最后的g，这样的方式叫做cross validation。
Leave-one-out Cross Validation看起来很厉害，那问题是Leave-one-out Cross Validation能不能告诉我们最在乎的事情Eout(g)有多好。 假设有一个算法和1000笔数据拿来做Leave-one-out Cross Validation，然后对各式各样的1000笔数据来做取一个平均。等一下要证明跟Eout(N−1)的平均值是可以连接的。因为Eout(g−)与Eout(g)几乎是一样的，前者是1000笔数据做出来的，后者是999笔数据做出来的。 所以，我们得到了一个几乎完全没有偏见的针对Eout(g)的衡量方式。也就是说，Leave-one-out Cross Validation在选择模型上会比Ein来的更有效。
V-fold Cross Validation
1000笔数据，你需要有1000遍，把999个数据放进去算，后面还要做平均。很明显，Leave-One-Out Cross Validation大大增加了计算的复杂度，实际应用上上可能不太行。
另一方面，对于二元分类来说，分类结果在0与1之间跳动，Leave-One-Out求一个平均值。对这个平均值来说，这些0与1的跳动是很大的，希望用平均的方式把这些很大的跳动消掉，其实还是不太容易。为了降低计算复杂度，将训练资料分为V份，取其中V-1做训练，另外1份做validation。这种方式通常叫做V-fold Cross Validation。实际上，就是把1000份资料分成100份。
实际上V通常取5或者10。Traning就像初赛，各个模型都从Hypothesis Set中选出最合适的h；Validation就像复赛，从多种模型的scheme中选出一个最优的。这两步都是在进行模型选择，之后的testing methods都只是在对模型进行estimate了。也因为Validation还是在做选择，只要做选择就会有数据的污染等等，所以Validation仍然比testing要乐观。对于模型来说，testing的表现才是真正要看重的，不是最好的validation的表现。