Es wurde kein Satz über freies Mittagessen in der Pattern Classification von Duda et al

Ich habe einige Fragen zu den in Abschnitt 9.2 verwendeten Notationen. Mangelnde inhärente Überlegenheit eines Klassifikators in der Duda, Hart und Stork's Pattern Classification . Lassen Sie mich zuerst einen relevanten Text aus dem Buch zitieren:

• Der Einfachheit halber sei ein Problem mit zwei Kategorien betrachtet, bei dem der Trainingssatz $D$ aus Mustern $x^i$ und zugeordneten Kategoriebeschriftungen $y_i = ± 1$ für $i = 1,..., n$ erzeugt durch die zu lernende unbekannte Zielfunktion $F(x)$ , wobei $y_i = F(x^i)$ .
• Es sei $H$ die (diskrete) Menge von Hypothesen oder mögliche Mengen von zu lernenden Parametern. Eine bestimmte Hypothese $h(x) \in H$ könnte durch quantisierte Gewichte in einem neuronalen Netzwerk oder Parameter 0 in einem Funktionsmodell oder Mengen von Entscheidungen in einem Baum usw. beschrieben werden.
• Weiterhin ist $P(h)$ die vorherige Wahrscheinlichkeit, dass der Algorithmus nach dem Training die Hypothese $h$ ; Beachten Sie, dass dies nicht die Wahrscheinlichkeit ist, dass $h$ korrekt ist.
• Als nächstes bezeichnet $P(h|D)$ die Wahrscheinlichkeit, dass der Algorithmus die Hypothese liefert, $h$wenn er auf die Daten trainiert $D$. In deterministischen Lernalgorithmen wie dem nächsten Nachbarn und Entscheidungsbäumen ist $P(h|D)$ überall Null, mit Ausnahme einer einzelnen Hypothese $h$ . Für stochastische Methoden (wie neuronale Netze, die aus zufälligen Anfangsgewichten trainiert wurden) oder für stochastisches Boltzmann-Lernen kann $P(h|D)$ eine breite Verteilung sein.
• Sei $E$ der Fehler für eine Null-Eins-Funktion oder eine andere Verlustfunktion.

Der erwartete Klassifizierungsfehler außerhalb des Trainingssatzes, wenn die wahre Funktion $F(x)$ und die Wahrscheinlichkeit für den $k$ ten Kandidaten-Lernalgorithmus $P_k(h(x)|D)$ ist, ist durch

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

Satz 9.1. (Kein freies Mittagessen) Für zwei beliebige Lernalgorithmen $P_1 (h |D)$ und $P_2(h|D)$ gilt unabhängig von der Stichprobenverteilung $P(x)$ und der Anzahl $n$ der Trainingspunkte Folgendes :

1. Einheitlich gemittelt über alle Zielfunktionen $F$ , $\mathcal{E}_1 (E|F, n) — \mathcal{E}_2(E|F, n) = 0$

2. Für jeden festen Trainingssatz $D$ , der gleichmäßig über gemittelt wird $F$, gilt $\mathcal{E}_1 (E|F, D) — \mathcal{E}_2(E|F, D) = 0$

Teil 1 ist eigentlich sagen

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

Teil 2 sagt eigentlich

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

Meine Fragen sind

1. In der Formel von , das heißt E k ( E | F , n ) = Σ x ∉ D P ( x ) [ 1 - δ ( F ( x ) , h ( x ) ) ] P k ( h ( x ) | D ) , kann ich P ersetzen$\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),$$ mit P k ( h | D ) und außerhalb der Summe bewegen Σ x ∉ D , weil es wirklich eine Verteilung ist h über H gegeben D für die k - ten stochastischen Lernalgorithmus?$P_k(h(x)|D)$$P_k(h|D)$$\sum_{x \notin D}$$h$$H$$D$$k$
2. Da der te Kandidaten-Lernalgorithmus eine stochastische Methode ist, warum in der Formel von E$k$ , gibt es keine Summe über h , dh Σ h ∈ H ?$\mathcal{E}_k(E|F,n)$$h$$\sum_{h \in H}$

3. Wie geht es und E i ( E | F , n ) voneinander?$\mathcal{E}_i (E|F, D)$$\mathcal{E}_i (E|F, n)$

   Bedeutet die Fehlerrate außerhalb des Trainings bei einem Trainingssatz D ?$\mathcal{E}_i (E|F, D)$$D$

   Bedeutet die durchschnittliche Fehlerrate außerhalb des Trainings über alle Trainingssätze bei einer Trainingsgröße n ? Wenn ja, warum setzt Teil 1 des NFL-Theorems E i ( E | F , n ) erneut über Trainingsmengen, indem er by schreibt $\mathcal{E}_i (E|F, n)$$n$$\mathcal{E}_i (E|F, n)$ , und warum in der Formel für E k ( E | F , n ) , gibt es keine Mittel über alle Trainingssätze haben eine Trainingsgröße n ?$\sum_D$$\mathcal{E}_k(E|F,n)$$n$

4. in Teil 1 des NFL-Theorems das Summieren aller Trainingssätze mit einer festen Trainingsgröße n ?$\sum_D$$n$
5. Wenn man alle möglichen Werte in der Trainingsgröße n in Teil 1 weiter summiert , ist das Ergebnis immer noch 0, oder?$\mathbb{N}$$n$
6. In der Formel von $\mathcal{E}_k(E|F,n)$ , ändern , wenn ich zu Σ x , dh x ist nicht notwendigerweise beschränkt außerhalb des Trainingssatzes sein, werden beiden Teile in NFL Satz noch wahr sein?$\sum_{x \notin D}$$\sum_x$$x$
7. Wenn die wahre Beziehung zwischen und y nicht als deterministische Funktion F wie y = F ( x ) angenommen wird , sondern als bedingte Verteilung P ( y | x ) oder als gleichwertige gemeinsame Verteilung P ( x , y ) zu wissen , P ( y | x ) und P ( x ) (siehe auch meine andere Frage ), dann kann ich ändern E k$x$$y$$F$$y=F(x)$$P(y|x)$$P(x,y)$$P(y|x)$$P(x)$ zu E k ( E | P ( x , y ) , n ) = E x , y [ 1 - δ ( y , h ( x ) ) ] P k ( h ( x ) | D ) (mit das seltsame P k ( h ( 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)$$ auf die in Teil 1 und 2 hingewiesen wurde. Stimmen die beiden Teile des NFL-Theorems noch?$P_k(h(x)|D)$

Danke und Grüße!

Ich werde die Fragen beantworten, auf die ich die Antworten zu kennen glaube.

1. $x$$D$$h$$x$
2. $h$$x$$H$$x$
3. $\mathcal{E}_i(E|F, D)$$F$$D$ . Aber$\mathcal{E}_i(E|F, n)$ Ich denke, das ist anders, weil Sie nur von der Anzahl der Trainingspunkte abhängig sind $n$ und nicht die tatsächliche $x$Werte. Dies ist jedoch angesichts der nachfolgenden Aussagen verwirrend.
4. $D$ist der Satz von Trainingsvektoren. Es gibt$n$ Trainingsvektoren in $D$. Du summierst also über das Feste$n$ Trainingsvektoren in $D$. Es gibt nur einen Satz$D$.
5. Ich denke die Antwort auf 5 ist nein. Die Notation scheint etwas verwirrend zu sein.

Ich kann zu 6 und 7 keinen Kommentar abgeben.