Was ist der Satz ohne kostenloses Mittagessen?

7

Ich habe über das No Free Lunch Theorem gelesen, aber ich kann nicht ganz verstehen, worum es geht. Ich habe diesen Satz an anderer Stelle als die Behauptung beschrieben, dass "kein universeller Allzweckoptimierer existiert". Auf der anderen Seite spricht der Wikipedia-Artikel von "Kandidatenlösungen", die "einzeln bewertet" werden - wenn wir nur Algorithmen einer bestimmten Form betrachten, dann ist das ein viel begrenzterer Anspruch.

Kann jemand erklären, was dieser Satz tatsächlich behauptet?

algorithms terminology optimization heuristics Casebash
quelle
Haben Sie den gesamten Artikel gelesen, insbesondere die formale Erklärung und die Interpretationen ?
Raphael
fyi P ≠ NP kann als mit dem thm verwandt angesehen werden. Ein Kontrapunkt zu diesem Theorem ist jedoch, dass definitiv unterschiedliche ML-Algorithmen eine unterschiedliche Leistung für reale Daten aufweisen und optimierbar sind.
vzn

Antworten:

10

Das No Free Lunch Theorem (NFL) wurde aufgestellt, um Ansprüche der Form zu entlarven:

Meine Optimierungsstrategie X ist immer die beste.

Insbesondere im Bereich der genetischen / evolutionären Algorithmen ergaben sich solche Behauptungen.

Die Aussage lautet ungefähr: Jede Optimierungsstrategie ist bei vielen Problemen schlecht . Daher kann es keine immer beste Strategie geben und Ihre Behauptung über X ist falsch.

Raphael
quelle
1
Wie um alles in der Welt wird dies aus Neugier als "kein kostenloses Mittagessen" bezeichnet? Ihre Erklärung macht Sinn, aber ich kann nicht sehen, was es mit dem Mittagessen zu tun hat (nom).
StackExchange What The Heck
3
@yochannah Hast du jemals den Satz "Es gibt kein kostenloses Mittagessen" gehört ? In diesem Zusammenhang bedeutet dies für mich, dass ein Algorithmus einige Situationen besser haben kann, aber nicht alles besser. Siehe auch den Artikel von Wikipedia zum Theorem mit seiner eigenen Analogie / Erklärung.
Tim S.
4
@yochannah Du denkst vielleicht , der nette Verkäufer möchte dich nur zum Mittagessen einladen, aber es gibt immer einen Haken.
Raphael
3

Soweit ich weiß, zielt diese Theorie auf globale Optimierungsmethoden wie genetische Algorithmen, neuronale Netze, simuliertes Tempern usw. ab.

Die Hauptbehauptung ist, dass diese Methoden, wenn wir alle möglichen Probleminstanzen eines bestimmten Problems berücksichtigen, genauso gut sind wie alle anderen Optimierer, die die gleiche Anzahl von Kandidatenlösungen berücksichtigen, beispielsweise Random Walk.

Die Allzweckoptimierer funktionieren wahrscheinlich gut auf vielen gängigen / realen Probleminstanzen, aber diese repräsentieren nicht den gesamten Bereich möglicher Probleminstanzen.

Ron Teller
quelle