Validation
对于PLA, pocket, linear regression, logistic regression，这些gradient descend的方法，我们可以选择迭代的次数，学习率，也可以选择对原来的feature进行多项式的转换映射到高维空间。为了防止overfitting，regularizer可以选择l1-norm，l2-norm, symmetry regularizer，以及penalty的强度
。那么怎样选择最合适的组合才能找到最好的g呢？现在有M个Hypothesis set，以及它们对应的算法。比如线性的Hset，对应有logistic regression，树型的Hset，对应有决策树，rf等等。现在从M个Hset中，选出一个Hset，它对应的g的
最小。但是我们不知道
，那么我们可以选择最好的
吗？这样会overfitting，比如算法会prefer更高次的Hset，或者说
比
要好，那么我干脆就不regularization好了。这些都是bad generalization。
如果我们可以获得testset，我们通过选择
，即
，然后通过Hoeffding，可以得到
。但是因为无法得到测试数据，或者说这种行为是cheating，因此此路不通。因此产生一种Validation set。从手中的Dataset中选出一部分，不用做Training，而拿来做Validation。假设现在的Dataset是D，size为N，从中选出K个sample作为
，而用剩下来的N-K个sample去给A来Train model。得到的model用
表示。然后用
去validate。为了让
去表达
变得有意义，
必须独立同分布于D，这样根据Hoeffding，就有
，因此当
能够做到最小，选出了最好的
，那么
也就有了上限。根据Learning curve，随着Dataset size的增大，E逐渐减小，然后
是用了N-K大小的数据集找到的最佳模型，那么如果我们用了全部的N去训练，找到的最佳模型
，它在
上的表现会比
更好，因此有不等式
。把它们的Learning curve画出来就是
，其中，in-sample就是通过
选出来的模型，optimal是根据
选出来的模型表现，可以看到error一直很小。另外两个，红色是真的用validation选出来的还不错的
在
上的表现，差过蓝色的，也就是
的表现。我们知道，如果validation set的size K很小的话，那么几乎用手中所有的数据训练出来的g，它在
的表现，应该和
差不多，但是用这么少的validation set得到的
并不能够代表
。但是，如果当K很大时，代表留下来做validation的size很大，训练的数据集很少，此时对于训练出来的
，那些validation set在它上面的表现
，也就基本上等同于真正的
了，但是此时的
就比
差的远了。一般情况下
LOOCV:
当K取1时，由上文可知，
和
差的挺远的，这里的上标n代表作为validation set的数据是第n个。而且
要么是0要么是1。怎样才能使
变得和
差不多呢？答案是，求平均。我们有N个数据，每个数据都可以有机会当做validation set的机会，那么就可以求出N个
，因此有
，希望这个error可以和
差不多。以下是证明：
说明了
和
的期望值是有关联的。但是算LOOCV的error，需要大量的计算，例如有1000个数据，则要训练1000次的模型。而且，用一个数据去做validation，非0即1，曲线比较不稳定。
那么怎样减少计算量呢？
V-fold Cross Validationrandom-partition of D to V equal subset.然后拿V-1份subset去训练，拿剩下的一份去做validation，然后error就可以表示为
和
，依据这个交叉验证的error去选择m，方法于LOOCV中的选择m的方法一致。V常常选择10。一般上不会去选择LOOCV。同时，如果计算量允许的情况下，cross validation往往prefer过single validation，因为CV有做平均，理论依据如上证明。但是实际上
还是要比
乐观一些，就是说validation上做得很好，最后还是要看测试的结果，才算真正衡量model的表现。
