En la teoría del aprendizaje estadístico, ¿no hay un problema de sobreajuste en un conjunto de prueba?

Consideremos el problema de clasificar el conjunto de datos MNIST.

Según la página web MNIST de Yann LeCun , 'Ciresan et al.' obtuvo una tasa de error del 0.23% en el conjunto de prueba MNIST usando la red neuronal convolucional.

Denotemos el conjunto de entrenamiento MNIST como $D_{train}$ , el conjunto de prueba MNIST como $D_{test}$ , la hipótesis final que obtuvieron usando $D_{train}$ como $h_{1}$ , y su tasa de error en el conjunto de prueba MNIST usando $h_{1}$ como $E_{test}(h_{1}) = 0.0023$ .

Desde su punto de vista, dado que $D_{test}$ es un conjunto de pruebas muestreado aleatoriamente desde el espacio de entrada independientemente de $h_{1}$ , pueden insistir en que el rendimiento de error fuera de la muestra de su hipótesis final $E_{out}(h_{1})$ se limite de la siguiente manera de la desigualdad P de Hoeffding [ | E o u t ( h 1 ) - E t e s t ( h 1 ) | < ϵ | ] donde N t e s t = | D t e s t | .

$$P[|E_{out}(h_{1}) - E_{test}(h_{1})| < \epsilon|] \geq 1 - 2e^{2\epsilon^{2}N_{test}}$$
$N_{test}=|D_{test}|$

En otras palabras, al menos probabilidad , E o u t ( h 1 ) ≤ E t e s t ( h 1 ) + $1-\delta$

$$E_{out}(h_1) \leq E_{test}(h_1) + \sqrt{{1 \over 2N_{test}}ln{2\over\delta}}$$

Consideremos otro punto de vista. Supongamos que alguna persona quiere clasificar bien el conjunto de pruebas MNIST. Así que primero miró la página web MNIST de Yann LeCun , y encontró los siguientes resultados obtenidos por otras personas usando 8 modelos diferentes,

y eligió su modelo que mejor se desempeñó en el conjunto de pruebas MNIST entre 8 modelos.$g$

Para él, el proceso de aprendizaje consistía en elegir una hipótesis que funcionara mejor en el conjunto de pruebas D t e s t de un conjunto de hipótesis H t r a i n $g$$D_{test}$.$H_{trained}=\{h_1, h_2, .. ,h_8\}$

Por lo tanto, el error en el conjunto de prueba es un error 'en muestra' para este proceso de aprendizaje, por lo que puede aplicar el límite de VC para conjuntos de hipótesis finitas como la siguiente desigualdad. P [ | E o u t ( g ) - E i n ( g ) | < ϵ ] ≥ 1 - 2 | H t r a i n e d | e 2 ϵ 2$E_{test}(g)$

$$P[|E_{out}(g)-E_{in}(g)|<\epsilon] \geq 1 - 2|H_{trained}|e^{2\epsilon^{2}N_{test}}$$

En otras palabras, al menos probabilidad , E o u $1-\delta$

$$E_{out}(g) \leq E_{test}(g) + \sqrt{{1 \over 2N_{test}}ln{2|H_{trained}|\over\delta}}$$

Este resultado implica que podría haber un sobreajuste en el conjunto de prueba si seleccionamos el modelo que funciona mejor entre varios modelos.

$h_{1}$$E_{test}(h_{1}) = 0.0023$$h_{1}$$D_{test}$$h_{1}$

$$E_{out}(h_1) \leq E_{test}(h_1) + \sqrt{{1 \over 2N_{test}}ln{2|H_{trained}|\over\delta}}$$

$$P[\;E_{out}(h_1) \leq E_{test}(h_1) + \sqrt{{1 \over 2N_{test}}ln{2\over\delta}}\;] \geq 1-\delta$$ $$P[\;E_{out}(h_1) \leq E_{test}(h_1) + \sqrt{{1 \over 2N_{test}}ln{2|H_{trained}|\over\delta}}\;] \geq 1-\delta$$

Sin embargo, es obvio que estas dos desigualdades son incompatibles.

¿Dónde estoy haciendo mal? ¿Cuál está bien y cuál está mal?

Si esto último es incorrecto, ¿cuál es la forma correcta de aplicar el límite de VC para conjuntos de hipótesis finitas en este caso?

Entre esas dos desigualdades, creo que la última está mal. En resumen, lo que está mal aquí es la identidad$g=h_1$ Dado que $g$ es una función de los datos de prueba mientras $h_1$ es un modelo que es independiente de los datos de prueba.

De hecho, $g$ es uno de los 8 modelos en $H_{trained} = \{ h_1, h_2,..., h_8 \}$ que mejor predice el conjunto de pruebas $D_{test}$.

Por lo tanto, $g$ es una función de $D_{test}$. Para un conjunto de prueba específico,$D^*_{test}$ (como el que mencionaste), podría suceder que $g(D^*_{test}) = h_1$, pero en general, dependiendo del conjunto de prueba, $g(D_{test})$ podría tomar cualquier valor en $H_{trained}$. Por otra parte$h_1$ es solo un valor en $H_{trained}$.

Para la otra pregunta:

Si esto último es incorrecto, ¿cuál es la forma correcta de aplicar el límite de VC para conjuntos de hipótesis finitas en este caso?

Simplemente no reemplace $g$ por $h_1$, obtendrá el límite correcto (para $g$, por supuesto) y no tendrá conflicto con el otro límite (que es para $h_1$)