机器学习-Validation（验证）2019-12-17

在过拟合和正则化学习过，当使用特征变换或者使用更高维度的dvc后，Ein就会变的非常小。但是真的会选择Ein=0的这些函数么？

如果按照Ein比较小的来选择函数：

1. 特征变换后的，要比变换前的要好

2. dvc大的要比dvc小的要好

3. $\lambda$ =0的要比 $\lambda$ =0.1的要好

4. 若有2个hyposis set，那么在H1中选择Ein最小的，在H2中选择一个Ein最小的。然后2个最小的在进行比较，那么这种做法实际在做的是Ein在H1 $\cup$ H2，因此还是在dvc(H1 $\cup$ H2）中。dvc扩大了。

因此使用Ein来做model的选择，不可取。如果用Eout来做选择，但是Eout不可知，因此使用Eout做model的选择，不可取。

使用Etest来进行模型的选择。

Etest是iid于样本和总体，因此可以是总体中的一个没有使用过的样本，或者是样本中没有使用过的一部分样本。如果使用“污染过”或者叫“已经进行过Ein计算的”样本再进行Etest的话，那么Ein会非常的乐观，并且比较不出模型的优劣

样本数量是D，模型是 $g_m$ ，从D中取出K做为验证集（Validation），其余的D-K的样本做训练集（Train）,模型是 $g^-_m$ 。

那么在训练集得到的 $g^-_m$ ，代入验证集得到的Eout以及Ein也符合霍夫丁不等式，有理论上的保证

$E_{out}(g^-_m)\leq E_{val}(g^-_m)+O(\sqrt{\frac{logM}{K} } )$

由于N-K的样本要小于N个样本，因此计算出来的Ein还是Eout，都要

用5阶和10阶函数进行模型的选择时：

使用样本的Ein选择，是in-sample的gm，黑色实线

使用污染过的验证集进行选择，那么Ein是optimal的虚线

使用没有污染过的验证集进行选择，是红色的 $g^{-*}_m$

使用没有污染过的验证集先进行验证，选择Eval较小的，然后在代入整个样本计算，是蓝色的 $g^{*}_m$

当K增大，N-K则减小，Ein（N-K）增大，因此会看到，当K增大时，红色validation的Ein会在K增大时，超过in-sample的Ein

因此，要做到的是

1. 将Dtrain和Dval分割

2. 使用Dtrain得到g-m

3. 使用Dval代入gm得到Ein较小的g-m

4. 将D代入Ein较小的g-m得到g*m

因为验证集要从样本中取，这就有个矛盾的地方：

如果要测试集和样本集的Eout够接近，那么K要比较小

如果要测试集和验证集的Eout够接近，那么K要比较大

那么通常设置： $K=\frac{N}{5}$

留一法：

如果每次验证集只保留1个样本呢？

那么训练集得到的g-，在验证集上的体现，就是Ein(g-)在这个点上的体现

如何使en逼近Eout(g)呢？可以在所有的样本点上，每次留一个做Validation。轮询一遍，然后求平均

Eloocv和Eout有近似的关系。

Ein和Eloocv那个更好呢？

由于Eloocv会受到某些特殊样本点的干扰，因此有时候会比较抖动。并且实际上，LOOCV做起来会特别耗时间，因此LOOCV只是理想状态下的情况。实际，可以将样本切割成10份，然后轮询做validation。这样的方法叫V-fold的cross validation。做起来也还不错。

总结一下Validation的本质：

All training models: 在hypotheses中做选择

all validation schemes: 在所有的hypotheses中，选在Ein较小的，像是做复赛

all test methods: 就像是做评估的过程