Zrozumienie twierdzenia o braku darmowego lunchu w klasyfikacji wzorców Dudy i in

Mam kilka pytań dotyczących zapisów używanych w rozdziale 9.2 Brak nieodłącznej wyższości jakiegokolwiek klasyfikatora w klasyfikacji wzorów Dudy, Harta i Bociana . Najpierw pozwól mi zacytować odpowiedni tekst z książki:

• Dla uproszczenia rozważmy problem dwóch kategorii, w którym zestaw szkoleniowy składa się ze wzorów i powiązanych etykiet kategorii dla wygenerowanych przez nieznaną funkcję docelową, której należy się nauczyć, , gdzie .$D$$x^i$$y_i = ± 1$$i = 1,..., n$$F(x)$$y_i = F(x^i)$
• Niech oznacza (dyskretny) zestaw hipotez lub możliwych zestawów parametrów, których należy się nauczyć. Szczególną hipotezę można opisać za pomocą skwantowanych wag w sieci neuronowej lub parametrów 0 w modelu funkcjonalnym lub zestawów decyzji w drzewie i tak dalej.$H$$h(x) \in H$
• Ponadto oznacza wcześniejsze prawdopodobieństwo, że algorytm wygeneruje hipotezę po treningu; zauważ, że nie jest prawdopodobne, że jest poprawne.$P(h)$$h$$h$
• Następnie, oznacza prawdopodobieństwo, że algorytm otrzymując hipotezy po wyszkolonych na danych . W deterministycznych algorytmach uczenia się, takich jak najbliższy sąsiad i drzewa decyzyjne, będzie wszędzie zero, z wyjątkiem pojedynczej hipotezy . W przypadku metod stochastycznych (takich jak sieci neuronowe trenowane z losowych wag początkowych) lub stochastycznego uczenia Boltzmanna może być szerokim rozkładem.$P(h|D)$$h$$D$$P(h|D)$$h$$P(h|D)$
• Niech będzie błędem dla zerowej lub innej funkcji utraty.$E$

Oczekiwany błąd klasyfikacji poza treningiem, gdy prawdziwą funkcją jest a prawdopodobieństwo dla tego algorytmu uczenia się kandydata jest podane przezk P k ( h ( x ) | D ) E k ( E | F , n ) = ∑ x ∉ D P ( x ) [ 1 - δ ( F ( x ) , h ( x ) ) ] P k ( h ( x ) | D $F(x)$$k$$P_k(h(x)|D)$

$$\mathcal{E}_k(E|F,n) = \sum_{x\notin D} P(x) [1-\delta(F(x), h(x))] P_k(h(x)|D)$$

Twierdzenie 9.1. (Bez darmowego lunchu) W przypadku dowolnych dwóch algorytmów uczenia się i spełnione są następujące warunki, niezależnie od rozkładu próbkowania i liczby punktów treningowych:P 2 ( h | D ) P ( x ) $P_1 (h |D)$$P_2(h|D)$$P(x)$$n$

1. Równomiernie uśrednione dla wszystkich funkcji docelowych ,$F$$\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n) = 0$

2. Dla każdego ustalonego zestawu treningowego , równomiernie uśrednionego dla , $D$$F$$\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D) = 0$

Część 1 faktycznie mówi

$$\sum_F \sum_D P(D|F) [\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n)] = 0$$

Część 2 faktycznie mówi

$$\sum_F [\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D)] = 0$$

Moje pytania są

1. We wzorze , tj. można wymienić z i przenieść go na zewnątrz suma , ponieważ tak naprawdę jest to rozkład na biorąc pod uwagę dla tego stochastycznego algorytmu uczenia się?$\mathcal{E}_k(E|F,n)$ $$\mathcal{E}_k(E|F,n) = \sum_{x\notin D} P(x) [1-\delta(F(x), h(x))] P_k(h(x)|D),$$ $P_k(h(x)|D)$$P_k(h|D)$$\sum_{x \notin D}$$h$$H$$D$$k$
2. Biorąc pod uwagę, że ty algorytm uczenia kandydata jest metodą stochastyczną, dlaczego we wzorze nie ma sumy powyżej , tj. ?$k$$\mathcal{E}_k(E|F,n)$$h$$\sum_{h \in H}$

3. Czym różnią się i ?$\mathcal{E}_i (E|F, D)$$\mathcal{E}_i (E|F, n)$

   Czy oznacza poziom błędu poza treningiem przy danym zestawie treningowym ?$\mathcal{E}_i (E|F, D)$$D$

   Czy oznacza średni poziom błędu poza treningiem, średni dla całego zestawu treningów, biorąc pod uwagę rozmiar treningu ? Jeśli tak, dlaczego część 1 w twierdzeniu NFL jest średnia nad zestawami treningowymi, pisząc , i dlaczego we wzorze na , nie ma średniej dla całego zestawu treningów, biorąc pod uwagę rozmiar treningu ?$\mathcal{E}_i (E|F, n)$$n$$\mathcal{E}_i (E|F, n)$$\sum_D$$\mathcal{E}_k(E|F,n)$$n$

4. Czy w części 1 twierdzenia NFL oznacza sumowanie wszystkich zestawów treningowych o ustalonym rozmiarze treningu ?$\sum_D$$n$
5. Jeśli dalsze sumowanie wszystkich możliwych wartości w wielkości treningu w części 1, wynikiem jest nadal 0, prawda?$\mathbb{N}$$n$
6. We wzorze , jeśli zmienię na , tzn. niekoniecznie jest ograniczony do poza zestawem treningowym, czy obie części Twierdzenie NFL nadal jest prawdziwe?$\mathcal{E}_k(E|F,n)$$\sum_{x \notin D}$$\sum_x$$x$
7. Jeśli prawdziwa zależność pomiędzy a , nie są uważane za funkcją deterministyczną jako , lecz warunkowego rozkładów , albo łącznego rozkładu , który jest odpowiednikiem znając i (zobacz także moje inne pytanie ), wtedy mogę zmienić na (z dziwnym wskazane w części 1 i 2). Czy dwie części twierdzenia NFL są nadal prawdziwe?$x$$y$$F$$y=F(x)$$P(y|x)$$P(x,y)$$P(y|x)$$P(x)$$\mathcal{E}_k (E|F,n)$ $$\mathcal{E}_k(E|P(x,y),n) = \mathcal{E}_{x,y} [1-\delta(y, h(x))] P_k(h(x)|D)$$ $P_k(h(x)|D)$

Dziękuję i pozdrawiam!

Odpowiem na pytania, na które, jak sądzę, znam odpowiedzi.

1. Ta odpowiedź brzmi „nie”, ponieważ wybierasz który nie był częścią zestawu dopasowania a więc zależy od .$x$$D$$h$$x$
2. $h$ jest oceniane tylko przy wartościach w zestawie testowym w celu uzyskania oczekiwanego poziomu błędu, więc nie jest oceniane w całym zestawie ale tylko przy dyskretnym zbiorze w zestawie testowym.$x$$H$$x$
3. $\mathcal{E}_i(E|F, D)$ jest spodziewany przy zbiorze treningowym stopy błędów danej funkcji , a zbiór uczący . Ale Myślę, że jest inaczej, ponieważ zależysz tylko od liczby punktów treningowych a nie od rzeczywistych wartości . To zastanawiające, biorąc pod uwagę kolejne stwierdzenia.$F$$D$$\mathcal{E}_i(E|F, n)$$n$$x$
4. $D$ jest zbiorem wektorów szkoleniowych. W jest wektorów szkoleniowych . Więc jesteś zsumowanie na stałe szkoleniowe wektorów w . Jest tylko jeden zestaw .$n$$D$$n$$D$$D$
5. Myślę, że odpowiedź na 5 jest przecząca. Notacja wydaje się nieco myląca.

Nie można komentować 6 i 7.