Welche Auswirkungen hat der Satz „No Free Lunch“ auf das maschinelle Lernen?

Der Satz von No Free Lunch (NFL) besagt (siehe das Papier Coevolutionary Free Lunches von David H. Wolpert und William G. Macready).

Zwei beliebige Algorithmen sind gleichwertig, wenn ihre Leistung über alle möglichen Probleme gemittelt wird

Ist der Satz "No Free Lunch" wirklich wahr? Was bedeutet das eigentlich? Ein schönes Beispiel (im ML-Kontext), das diese Behauptung veranschaulicht, wäre schön.

Ich habe einige Algorithmen gesehen, die sich sehr schlecht verhalten, und es fällt mir schwer zu glauben, dass sie tatsächlich dem oben genannten Theorem folgen. Daher versuche ich zu verstehen, ob meine Interpretation dieses Theorems korrekt ist oder nicht. Oder ist es nur ein anderer Ziersatz wie der Universal Approximation Theorem von Cybenko?

Dies ist eine sehr häufige Reaktion, nachdem man zum ersten Mal auf die No Free Lunch-Theoreme (NFLs) gestoßen ist. Das für maschinelles Lernen ist besonders unintuitiv, weil es gegen alles verstößt, was in der ML-Community diskutiert wird. Das heißt, der Satz ist wahr, aber was er bedeutet, ist offen für einige Debatten.

Um den Satz für Leute, die ihn nicht kennen, neu zu formulieren, ist der NFL-Satz für maschinelles Lernen wirklich ein Sonderfall des NFL-Satzes für die lokale Suche und Optimierung . Die lokale Suchversion ist leichter zu verstehen. Der Satz macht die folgende, etwas radikale Behauptung:

Gemittelt über alle möglichen Optimierungsprobleme entspricht die durchschnittliche Lösungsqualität , die von einem von Ihnen ausgewählten lokalen Suchalgorithmus gefunden wird, genau der durchschnittlichen Lösungsqualität eines lokalen "Such" -Algorithmus, der nur mögliche Lösungen generiert, indem er gleichmäßig zufällig aus dem Raum abtastet aller Lösungen.

Eine andere Formulierung, wenn die Leute eine noch stärkere Reaktion wünschen, lautet: Wenn Sie die beste Lösung für ein Problem finden möchten, ist es genauso gut, Dinge auszuprobieren, die Ihre Lösung iterativ schlechter zu machen scheinen, als Dinge zu versuchen, die dies tun scheinen Ihre Lösung iterativ besser zu machen. Im Durchschnitt sind beide Ansätze gleich gut.

Okay, warum ist das so? Nun, der Schlüssel liegt im Detail. Wolpert hat den Satz manchmal als Spezialisierung von Humes Arbeit über das Problem der Induktion beschrieben . Die grundlegende Aussage zum Induktionsproblem lautet: Wir haben keine logische Grundlage für die Annahme, dass die Zukunft wie die Vergangenheit sein wird. Logischerweise gibt es keinen Grund, warum sich die Gesetze der Physik morgen nicht alle radikal ändern könnten. Aus rein logischer Sicht ist es völlig vernünftig, dass sich die Zukunft in vielerlei Hinsicht von der Vergangenheit unterscheiden kann. Humes Problem ist , dass im Allgemeinen die Zukunft ist wie die Vergangenheit in vielerlei Hinsicht. Er versuchte , ein philosophisches (logisches) Argument zu formulieren , dass dies erforderlich , so sein, aber im Grunde gescheitert.

$k$

Eine sehr kurze Zusammenfassung könnte sein:

Ein Algorithmus für maschinelles Lernen kann nur dazu gebracht werden, bei einigen Arten von Problemen besser zu arbeiten, indem er bei anderen Arten von Problemen schlechter funktioniert.

Was bedeutet dies Mittel in einem praktischen Sinn? Dies bedeutet, dass Sie einen Apriori- Grund für die Annahme haben müssen, dass Ihr Algorithmus bei einem bestimmten Problem wirksam ist . Wie genau ein guter Grund aussieht, ist Gegenstand heftiger Debatten innerhalb der ML-Community. Dies hängt sehr eng mit dem Bias / Varianz-Kompromiss zusammen .

Einige häufige Antworten sind:

• Wenn Sie an einem neuen Optimierungsproblem suchen, obwohl es könnte jede beliebige Art von Struktur hat, sind die Probleme , die wir tatsächlich Begegnung in der realen Welt viel mehr regelmäßig sind und bestimmte gemeinsame Themen vorhanden, wie die Tatsache , dass die beweglichen " bergauf "(Fehler minimieren) führt iterativ zu guten Lösungen. Grundsätzlich sagt diese Denkschule, dass NFL ein Ziersatz ist: Die meisten ML-Algorithmen arbeiten besser mit "der Art von Problemen, die wir im wirklichen Leben sehen", indem sie schlechter mit "der Art von Problemen arbeiten, die wir im wirklichen Leben nicht sehen".
• Wenn Sie an einem neuen Optimierungsproblem in [insert Ihre Lieblings - Anwendungsdomäne] suchen, obwohl es könnte jede beliebige Art von Struktur hat, neigen dazu , Probleme zu aussehen wie [was auch immer Sie denken], die [Ihr Lieblings - Algorithmus] viel mehr machen effektiver als zufälliges Raten.
• Wolpert & McCready selbst veröffentlichte ein interessantes Ergebnis zeigt , dass es tatsächlich sind Optimierungsprozessen spezialisiert ist , auf Basis von Co-Evolution, die sind durchweg als zufällige Erraten besser.

Unabhängig davon ist es unbestreitbar, dass einige Algorithmen in bestimmten Subdomänen besser sind als andere (wir können dies empirisch sehen). NFL sagt uns, dass sie woanders schlechter sein müssen, um dort besser zu werden. Die Frage, die zur Debatte steht, ist, ob das "irgendwo anders" echte oder rein künstliche Probleme sind.