验证

模型选择问题

若有$M$个候选模型$\mathcal H_1,\mathcal H_2,\ldots,\mathcal H_M$和相应的算法$\mathcal A_1,\mathcal A_2,\ldots,\mathcal A_M$，如何选择$\mathcal H_{m^*}$使得$g_{m^*}=\mathcal A_{m^*}(\mathcal D)$有低的$E_{out}(g_{m^*})$？

由于$P(\mathbf x)$和$P(y|\mathbf x)$未知，那么$E_{out}$未也知……

一、利用数据可视化不可行

只有一些数据集……基于视觉化的选择是“human learning”，并且高维度的数据不能视觉化。

二、利用$E_{in}$很危险

如果利用$E_{in}$选择，高维特征变换通常犹豫低维，非正则化方法通常优于正则化方法。若$\mathcal A_1$在$\mathcal H_1$最小化$E_{in}$，$\mathcal A_2$在$\mathcal H_2$最小化$E_{in}$，二者再择优$g_{m^*}$在$\mathcal H_1\cup\mathcal H_2$中得到最小的$E_{in}$，这样增加了额外的模型复杂度，VC维$d_{VC}(\mathcal H_1\cup\mathcal H_2)$变大了，泛化能力差。

三、利用$E_{test}$是作弊

根据finite-bin Hoeffding可得 \[ E_{out}(g_{m^*})\leq E_{test}(g_{m^*})+O\left(\sqrt{\log M\over N_{test}}\right)， \] 看上去很美，$\mathcal D_{test}$是没用于模型训来的干净数据，可是$\mathcal D_{test}$（相当于老师的考卷）从哪里来呢？

四、$E_{in}$和$E_{test}$折中的合法作弊方案$E_{val}$

• $\mathcal D_{val}\subset\mathcal D$；
• 可以获取的；
• 若$\mathcal D_{val}$没用于$\mathcal A_m$，那么它是干净的，就像测试数据一样。

单一验证集

数据$\mathcal D$的划分和相应关系如下：

\begin{align*} E_{in}(h)\quad&\quad&\quad&\quad &E_{val}(h)\\ \uparrow\quad\quad&\quad&\quad&\quad &\uparrow\;\;\,\,\\ \quad\underbrace{\mathcal D}_{\mbox{size }N}\quad\,&\rightarrow&\underbrace{\mathcal D_{train}}_{\mbox{size }N-K}\quad\quad\,&\cup&\underbrace{\mathcal D_{val}}_{\mbox{size }K}\;\\ \downarrow\quad\quad&\quad &\downarrow\quad\quad\quad\;&\quad&\quad\\ g_m=\mathcal A_m(\mathcal D)&\quad &g_m^-=\mathcal A_m(\mathcal D_{trian})&\quad&\quad \end{align*}

$\mathcal D_{val}\subset\mathcal D$称为验证集（validation set），用于模拟测试集。$\mathcal D_{val}$是随机从$\mathcal D$中抽取的$K$个样本，那么$\mathcal D_{val}\overset{iid}{\sim} P(\mathbf x,y)$，通过数据建立了$E_{val}$与$E_{out}$的联系。确保$\mathcal D_{val}$是干净的，$\mathcal A_m$只使用了$\mathcal D_{train}$进行模型选择（也就是训练得到模型参数，从$\mathcal H$中选出$h$）。

原来使用$\mathcal D$扮演两个角色，既要计算$E_{in}$进行模型选择，又要通过算法得到$g$，两个角色导致资料被污染。利用$D_{val}$，通过最佳$E_{val}$进行模型选择 \[ m^*=\underset{1\leq m\leq M}{\arg\min}(E_m=E_{val}(\mathcal A_m(\mathcal D_{train})))， \] 可得如下误差保证 \begin{equation} E_{out}(g_m^-)\leq E_{val}(g_m^-)+O\left(\sqrt{\log M\over K}\right)， \end{equation} 但是只用$N-K$个训练模型out-of-sample误差会偏大（也可从学习曲线看出，理论上若要成立，还需更严格的限制条件）， \[ E_{out}\left(\underbrace{g_{m^*}}_{\mathcal A_m^*(\mathcal D)}\right)\leq E_{out}\left(\underbrace{g_{m^*}^-}_{\mathcal A_m^*(\mathcal D_{train})}\right)， \] 因此， \[ E_{out}(g_{m^*})\leq E_{out}(g_{m^*}^-)\leq E_{val}(g_{m^*}^-)+O\left(\sqrt{\log M\over K}\right)。 \]

图 1: 基于验证集的模型选择方案 [PNG]

模型选择整个方案如上图所示，得到$g_{m^*}^-$之后，再回到原来整个数据集上得到$g_{m^*}$效果会更好¹。

图 2: 模型选择的学习曲线 [PNG]

上图是在$\mathcal H_{\Phi_5}$和$\mathcal H_{\Phi_{10}}$中进行模型选择的学习曲线。$g_{m^*}$的效果要优于$g_{m^*}^-$。利用$E_{in}$总会选择到复杂的模型，利用$E_{out}$的作弊方案选择结果总最优。随着验证集不断增大，用于模型选择的训练集不断减小，所以$g_{m^*}^-$甚至会比$g_{\widehat m}$效果差，对很小的训练集，采用$E_{in}$还算不错的模型选择方案。

对大的验证集样本数$K$，有$E_{val}(g^-)\approx E_{out}(g^-)$，但$g_{m^*}^-$通常比$g_{m^*}$糟糕；对小的$K$，有$g_m^-\approx g_m$和$E_{out}(g)\approx E_{out}(g^-)$，但$E_{val}$和$E_{out}$差异较大； \[ E_{out}(g)\underset{\mbox{small }K}{\approx}E_{out}(g^-)\underset{\mbox{large }K}{\approx}E_{val}(g^-)。 \]

从时间上看，由于部分数据当作了验证集，在训练集上选择每个模型的时间会缩短。

$K={N\over 5}$通常是不错的选择。

留1交叉验证

当在验证集的$K=1$的极端情况下，$g^-$和$g$就会非常接近，但$E_{out}$和$E_{val}$差异就很大。能否在$K=1$时找到方案，使得$E_{out}\approx E_{val}$？✅

当$K=1$时，验证集$\mathcal D_{val}^{(n)}=\{(\mathbf x_n,y_n)\}$，误差为$E_{val}^{(n)}(g_n^-)=err(g_n^-(\mathbf x_n),y_n)=e_n$，将留1交叉验证（leave-one-out cross validation）误差 \begin{equation} E_{loocv}(\mathcal H,\mathcal A)={1\over N}\sum_{n=1}^Ne_n={1\over N}\sum_{n=1}^Nerr(g_n^-(\mathbf x_n),y_n) \end{equation} 作为$E_{out}(g)$的近似，$E_{loocv}(\mathcal H,\mathcal A)\approx E_{out}(g)$，然后进行模型选择， \begin{equation} m^*=\underset{1\leq m\leq M}{\arg\min}(E_m=E_{loocv}(\mathcal H_m,\mathcal A_m))。 \end{equation}

图 3: loocv选择常数模型而非线性模型 [PNG]

用$\underset{\mathcal D_n}{\varepsilon}$表示在训练集上的数学期望，那么有² \begin{aligned} \underset{\mathcal D}{\varepsilon}E_{loocv}(\mathcal H,\mathcal A) = \underset{\mathcal D}{\varepsilon}{1\over N}\sum_{n=1}^Ne_n &= {1\over N}\sum_{n=1}^N\underset{\mathcal D}{\varepsilon}e_n\\ &={1\over N}\sum_{n=1}^N\underset{\mathcal D_n}{\varepsilon}\underset{(\mathbf x_n,y_n)}{\varepsilon}err(g_n^-(\mathbf x_n),y_n)\\ &={1\over N}\sum_{n=1}^N\underset{\mathcal D_n}{\varepsilon}E_{out}(g_n^-)\\ &={1\over N}\sum_{n=1}^N\overline{E_{out}}(N-1)\\ &=\overline{E_{out}}(N-1)， \end{aligned} 因此可得$E_{loocv}(\mathcal H,\mathcal A)$和$E_{out}(g^-)$联系紧密，通常称作$E_{out}(g)$几乎无偏的估计（almost unbiased estimate）。

图 4: loocv手写识别示例 [JPG]

上图手写识别例子中，通过验证确定选择多少维多项式特征。若用$E_{in}$，特征维度越多越好；利用$E_{loocv}$（图中标注为$E_{cv}$），会选到较低纬度的特征。

V-fold交叉验证

由于loocv需要训练$N$次，时间复杂度非常大，在实际中并不总是可行的。但也有特例，线性回归的的loocv容易计算。通过单点估计误差波动较大，结果不是很稳定，曲线上有些跳动的点。如何降低loocv的计算量？

将数据集$\mathcal D$随机分为$V$等份（loocv相当于将数据集分为$N$等份），$V-1$份用于训练模型，剩余的1份用于验证，这称为V-fold交叉验证， \begin{equation} E_{cv}(\mathcal H,\mathcal A)={1\over V}\sum_{v=1}^VE_{val}^{(v)}(g_v^-)， \end{equation} 模型选择方式为 \begin{equation} m^*=\underset{1\leq m\leq M}{\arg\min}(E_m=E_{cv}(\mathcal H_m,\mathcal A_m))。 \end{equation}

通常情况，$V=10$。

通常，V-fold交叉验证要优于单一验证集方法，计算量也更大，5-fold或10-fold通常都会工作得很好，实际中loocv并不常用。

小结

各种模型选择的关系：

• 模型训练（初赛）：从假设集中选择；
• 验证方案（复赛）：从训练好的模型中选择；
• 测试：衡量最终的表现（测试集只在此时才能使用1次）。

由于资料污染，以及付出了模型复杂度代价等因素，通常验证的结果仍然会比最终测试结果乐观。因此，提交测试结果而非验证结果更客观。

参考资料

脚注