机器学习——Validation
上次regularization最后留下了一个问题:$\lambda$的选择。其实仔细想想,从学习机器学习到现在,我们面临的选择,可不止一个$\lambda$.
模型的选择(PLA,POKCET,Linear Regression,Logistic Regression),特征转换的方法(用什么样的多项式转换),Regularizer的选择等等,这些组合起来足够让人头大。而实际上,也没有一种永远都表现得很好的组合,对于不同的问题需要不同的方法,也就是做选择是必须的。
为了简化问题,我们就仅以不同的假说的选择为例。其他的选择也与这个类似。
假设我们目前有2个$H$,一个$H_2$,另一个$H_{10}$,应该选择哪一个?
一个简单的想法,是利用$E_{in}$去判断。但是这个想法太naive了。我们之前讲过过拟合了,如果用$E_{in}$去判断,那就不用想了,因为$H_{10}$一定比$H_2$要好,而且如果两个模型一个加了$regularization$,它的表现一定不如另一个.而且如果两个$H$没有交集,从两个$E_{in}$中选择一个好的,那么实际上是在两个$H$的并集中选择,这也就意味着增大了代价,更容易得到不好的$E_{out}$。
另一种简单的想法,用测试数据来判断。这是一个很好的办法。我们知道$E_{test}$与$E_{out}$是满足霍夫丁不等式的,因此可以得到:
$$
E_{out} \leq E_{test}+O(\sqrt {\frac{\log M}{N_{test} } })
$$
所以用测试集来从模型中选择一个最好的是可行的。但是测试集从哪里来?
一般来说,测试集是锁在老板的柜子中。测试集相当于考试试卷,用来评判最终的分数.我们无法得到测试集,这就像考试前你想让自己做到最好,你没法用考试的卷子来测试自己,这叫作弊。
但是我们可以自己测验自己。这就是validation。
从给到的训练集当中,我们随机挑出一部分(保证iid),用来当作val集,其余部分用来训练模型。然后通过val集来选出表现最好的g’.为什么不是g?因为毕竟它的训练集相对于之前要少了很多,所以加个标识以区分。
一般来说,得到g’以后,也就是选出了我们想要的那个$H$,然后我们要做的就是将验证集再次融合回去,用这个整体的训练集在该假说上训练。毕竟某种程度上来说,N越大,得到的模型是越好的。而且
$$
E_{out}(g_{H_{chosen} }) < E_{out}(g’{H{chosen} })
$$
上式是实际中的一个很常见的式子,但理论上要这么保证还需要一定的限制条件。
假设我们从N个训练样本中挑出K个来做验证集,当然这个K的大小是会影响结果的。如果K很大,那么很开心,$E_{val}$与$E_{out}$更有可能很接近,这对于选择g’来说是很好的,但是K过大意味着留下来的训练样本过少,g’与g差别很大,可能导致我们无法找到应该选择的那个$H$;另一方面,K很小,g与g’相差很小,但是$E_{val}$与$E_{out}$可能实际上差的很远,也不能得到好的结果。因此这又是一个难题。
一般来说有下图:
可以看到如果K过大,导致训练g’的训练集很小,使得它的学习效果很差,甚至不如不用验证的情况。
为了解决这个问题,引入一种新的工具:交叉验证。
首先我们考虑一种很极端的情况:K=1.每次留出一个来做验证,对于单个样本来说它当然无法代表$E_{out}$.但是如果我们对这个过程进行N次,所有的样本都曾做过验证集,最后求出来$E_{val}$的平均值,可以证明它就能代表g’的$E_{out}$.上面的办法,叫做leave-one-out cross validation.假设它得到的错误我们称为$E_{looc}$,则有下面的证明:
(上面的证明我是看不大懂的)
这似乎是个很好的方法,但是它有个很致命的缺陷:计算量(N)倍的力气去计算g’。
因此,实际中我们很少用leave one out cross,而使用V-Fold Cross。将样本分为10(或者其他数)份,然后留一份作为val集,像上面一样交叉验证。这样需要的力气就是10倍,可以接受,而且能得到比非交叉验证更好的结果。
对于其他情况的选择,也可以用这样的办法,因为我们最终目的是得到尽量好的$E_{out}$。
最后,validation依然是为了做选择,因此它的结果依然是比较optimistic,算法最终的衡量还是要通过测试集,而不是将最好的validation结果作为衡量标准,这是自欺欺人的表现。