Dalam teori pembelajaran statistik, tidak adakah masalah overfitting pada set tes?

Mari kita pertimbangkan masalah tentang mengklasifikasikan dataset MNIST.

Berdasarkan laman web MNIST Yann LeCun , 'Ciresan et al.' mendapat tingkat kesalahan 0,23% pada set uji MNIST menggunakan Jaringan Nevoltural Convolutional.

Mari masing menunjukkan MNIST pelatihan ditetapkan sebagai , MNIST uji ditetapkan sebagai D t e s t , hipotesis akhir mereka diperoleh dengan menggunakan D t r a i n sebagai h 1 , dan tingkat kesalahan mereka pada MNIST Uji set menggunakan h 1 sebagai E t e s t ( h 1 ) = 0,0023 .$D_{train}$$D_{test}$$D_{train}$$h_{1}$$h_{1}$$E_{test}(h_{1}) = 0.0023$

Dalam pandangan mereka, karena secara acak sampel uji set dari ruang input terlepas dari h 1 , mereka dapat bersikeras bahwa out-of-sampel kinerja kesalahan hipotesis terakhir mereka E o u t ( h 1 ) dibatasi sebagai berikut dari Hoeffding's Inequality P [ | E o u t ( h 1 ) - E t e s t ( h 1 ) | < ϵ | $D_{test}$$h_{1}$$E_{out}(h_{1})$ dimanaN 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}|$

Dengan kata lain, setidaknya probabilitas , 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}}$$

Mari kita pertimbangkan sudut pandang lain. Misalkan beberapa orang ingin mengklasifikasikan set tes MNIST dengan baik. Jadi dia pertama kali melihat halaman Web MNIST Yann LeCun , dan menemukan hasil berikut yang diperoleh orang lain menggunakan 8 model yang berbeda,

dan memilih modelnya yang berkinerja terbaik pada set uji MNIST di antara 8 model.$g$

Baginya, proses belajar sedang mengambil hipotesis yang dilakukan terbaik pada tes set D t e s t dari satu set hipotesis H t r a i n e d = { h 1 , h 2 , . . , h 8$g$$D_{test}$$H_{trained}=\{h_1, h_2, .. ,h_8\}$ .

$E_{test}(g)$

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

$1-\delta$

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

Hasil ini menyiratkan bahwa mungkin ada overfitting pada set tes jika kami memilih model berkinerja terbaik di antara beberapa model.

$h_{1}$$E_{test}(h_{1}) = 0.0023$$h_{1}$$D_{test}$$h_{1}$ adalah hipotesis overfitted pada tes MNIST set.

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

Consequently, we got two inequalities

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

Howerver, it is obvious that these two inequalities are incompatible.

Where am I doing wrong? Which one is right and which one is wrong?

If the latter is wrong, what is the right way to apply the VC bound for finite hypothesis sets in this case?

Among those two inequalities, I think the later is wrong. In brief, what's wrong here is the identity $g=h_1$ given that $g$ is a function of the test data while $h_1$ is a model that is independent of test data.

In fact, $g$ is one of the 8 models in $H_{trained} = \{ h_1, h_2,..., h_8 \}$ that best predicts test set $D_{test}$.

Therefore, $g$ is a function of $D_{test}$. For a specific test set, $D^*_{test}$ (like the one you mentioned), it could happens that $g(D^*_{test}) = h_1$, but in general, depending on the test set, $g(D_{test})$ could take any value in $H_{trained}$. On the other hand $h_1$ is just one value in $H_{trained}$.

For the other question:

If the latter is wrong, what is the right way to apply the VC bound for finite hypothesis sets in this case?

Just don't replace $g$ by $h_1$, you will get the correct bound (for $g$, of course) and it will have no conflict with the other bound (which is for $h_1$).