Czy w statystycznej teorii uczenia się nie występuje problem przeregulowania zestawu testowego?

Rozważmy problem związany z klasyfikacją zestawu danych MNIST.

Według strony MNIST Yanna LeCuna „Ciresan i in.” uzyskał poziom błędu 0,23% w zestawie testowym MNIST przy użyciu sieci neuronowej Convolutional.

Oznaczmy zestaw treningowy MNIST jako , zestaw testowy MNIST jako , ostateczną hipotezę, którą uzyskali przy użyciu jako , oraz ich wskaźnik błędów na zestawie testowym MNIST przy użyciu jako . $D_{train}$ $D_{test}$ $D_{train}$ $h_{1}$ $h_{1}$ $E_{test}(h_{1}) = 0.0023$

W ich punktu widzenia, ponieważ $D_{test}$ jest losowo zestaw testowy z przestrzeni wejściowej niezależnie od $h_{1}$ można podkreślają, że nie stanowiącego przykład wykonania błędu ostatecznego hipotezy $E_{out}(h_{1})$ jest ograniczone jak wynika z nierówności Hoeffdinga

P [| E_{o u t} (h_{1}) - E_{t e s t} (h_{1}) | < ϵ |] \geq 1 - 2 e^{2 ϵ^{2} N_{t e s t}}

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

N_{t e s t} = | D_{t e s t} |

$N_{test}=|D_{test}|$ .

Innymi słowy, przynajmniej prawdopodobieństwo , $1-\delta$

E_{o u t} (h_{1}) \leq E_{t e s t} (h_{1}) + \sqrt{\frac{1}{2 N_{t e s t}} l n \frac{2}{δ}}

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

Rozważmy inny punkt widzenia. Załóżmy, że ktoś chce dobrze sklasyfikować zestaw testów MNIST. Więc po raz pierwszy spojrzał na stronę MNIST Yanna LeCuna i znalazł następujące wyniki uzyskane przez inne osoby używające 8 różnych modeli,

Wyniki klasyfikacji MNIST

i wybrał swój model który wypadł najlepiej na zestawie testowym MNIST spośród 8 modeli. $g$

Dla niego proces uczenia się polegał na wybraniu hipotezy która najlepiej działała na zestawie testowym z zestawu hipotez . $g$ $D_{test}$ $H_{trained}=\{h_1, h_2, .. ,h_8\}$

Zatem błąd w zestawie testowym jest błędem „w próbie” dla tego procesu uczenia się, więc może zastosować ograniczenie VC dla skończonych zestawów hipotez jako następującą nierówność. $E_{test}(g)$

P. [| {mi}_{o u t} (sol) - {mi}_{ja n} (sol) | < ϵ] \geq 1 - 2) | {H.}_{t r za ja n mi re} | {mi}^{2) ϵ^{2)} {N.}_{t mi s t}}

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

Innymi słowy, przynajmniej prawdopodobieństwo , $1-\delta$

{mi}_{o u t} (sol) \leq {mi}_{t mi s t} (sol) + \sqrt{\frac{1}{2) {N.}_{t mi s t}} l n \frac{2) | {H.}_{t r za ja n mi re} |}{δ}}

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

Ten wynik sugeruje, że zestaw testowy może być przeregulowany, jeśli wybieramy model, który działa najlepiej spośród kilku modeli.

W takim przypadku osoba może wybrać , który ma najniższy poziom błędu . Ponieważ jest najlepszą hipotezą wśród 8 modeli w tym konkretnym zestawie testowym , może istnieć pewna możliwość, że jest hipotezą przełożoną na zestawie testowym MNIST. $h_{1}$ $E_{test}(h_{1}) = 0.0023$ $h_{1}$ $D_{test}$ $h_{1}$

Dlatego osoba ta może nalegać na następującą nierówność.

{mi}_{o u t} (h_{1}) \leq {mi}_{t mi s t} (h_{1}) + \sqrt{\frac{1}{2) {N.}_{t mi s t}} l n \frac{2) | {H.}_{t r za ja n mi re} |}{δ}}

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

W rezultacie otrzymaliśmy dwie nierówności i .

P. [{mi}_{o u t} (h_{1}) \leq {mi}_{t mi s t} (h_{1}) + \sqrt{\frac{1}{2) {N.}_{t mi s t}} l n \frac{2)}{δ}}] \geq 1 - δ

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

P. [{mi}_{o u t} (h_{1}) \leq {mi}_{t mi s t} (h_{1}) + \sqrt{\frac{1}{2) {N.}_{t mi s t}} l n \frac{2) | {H.}_{t r za ja n mi re} |}{δ}}] \geq 1 - δ

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

Jednak oczywiste jest, że te dwie nierówności są niezgodne.

Gdzie robię źle? Który jest właściwy, a który zły?

Jeśli to drugie jest błędne, jaki jest właściwy sposób zastosowania granicy VC dla skończonych zestawów hipotez w tym przypadku?

— asqdf
źródło

Pomiędzy tymi dwoma nierównościami myślę, że późniejsze jest błędne. W skrócie, to, co jest nie tak, to tożsamość biorąc uwagę, że jest funkcją danych testowych, podczas gdy jest modelem niezależnym od danych testowych. $g=h_1$ $g$ $h_1$

W rzeczywistości jest jednym z 8 modeli w który najlepiej przewiduje zestaw testowy . $g$ $H_{trained} = \{ h_1, h_2,..., h_8 \}$ $D_{test}$

Dlatego jest funkcją . W przypadku konkretnego zestawu testowego, (jak ten, o którym wspomniałeś), może się , że , ale ogólnie, w zależności od zestawu testowego, może przyjąć dowolną wartość w . Z drugiej strony jest tylko jedną wartością w . $g$ $D_{test}$ $D^*_{test}$ $g(D^*_{test}) = h_1$ $g(D_{test})$ $H_{trained}$ $h_1$ $H_{trained}$

W przypadku drugiego pytania:

Jeśli to drugie jest błędne, jaki jest właściwy sposób zastosowania granicy VC dla skończonych zestawów hipotez w tym przypadku?

Po prostu nie zamieniaj na , otrzymasz poprawną granicę ( oczywiście dla ) i nie będzie ona powodować konfliktu z drugą granicą (która dotyczy ). $g$ $h_1$ $g$ $h_1$

— Tĩnh Trần
źródło