No-free-Lunch-Theoreme

Die No-free-Lunch-Theoreme („no free lunch“ ist englisch für „kein kostenloses Mittagessen“ bzw. sinngemäß „nichts ist umsonst“, daher auch Nichts-ist-umsonst-Theoreme^[1]) sind im Wesentlichen zwei mathematische Theoreme aus der Optimierung und Komplexitätstheorie über die Berechenbarkeit bestimmter mathematischer Problemstellungen. Die Theoreme zeigen Grenzen von Optimierungsalgorithmen bzw. Verfahren des maschinellen Lernens auf.

Beteilige dich an der Diskussion!

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)

Die Theoreme basieren auf der Prämisse, dass der Suchraum durch eine Wahrscheinlichkeitsfunktion gegeben ist. Vereinfacht sagen sie aus, dass kein universell gutes Verfahren zur Lösung eines Optimierungsproblems oder zum Abstrahieren von Datensätzen existiert, wenn die Menge aller Probleme^[2] bzw. Datensätze^[3] betrachtet wird. Ist eine bestimmte Strategie in einem Teilbereich besser als eine andere, so muss sie in einem anderen Teilbereich schlechter sein (Nichts ist umsonst). Insbesondere zeigt sich, dass keine Strategie, wenn sie auf die Grundgesamtheit aller Fälle angewandt wird, besser abschneidet als bloßes Raten.

Es kann effiziente Algorithmen geben, wenn der Suchraum Struktur aufweist (z. B. eine stetige, differenzierbare Funktion darstellt), oder wenn sogar eine geschlossene Lösung existiert (z. B. Extremum einer quadratischen Funktion), die ganz ohne Suche bestimmbar ist. Es ist also durchaus möglich, für bestimmte Problemmengen Strategien zu entwickeln, die besser sind als andere.^[4] Im Alltag ist dem Suchraum in den meisten Fällen schon durch die Naturgesetze eine Struktur aufgeprägt, sodass meist effizient gesucht/optimiert werden kann.

Die No-free-Lunch-Theoreme sind Unmöglichkeitssätze, wie auch der gödelsche Unvollständigkeitssatz in der Mathematik oder das Arrow-Theorem in der Sozialwahltheorie. Die Bezeichnung stammt von der englischen Redensart There ain’t no such thing as a free lunch. David Wolpert und William G. Macready entdeckten sie 1995.^[5] In einer verschärften Formulierung von 2001 gilt das No-free-Lunch-Theorem der Optimierung auch für Problemmengen, die unter Permutation abgeschlossen sind.^[6]

Originalformulierung

Wolpert und Macready veröffentlichten das No-free-Lunch-Theorem zu Optimierungsproblemen, die sich während der Problemsuche nicht ändern, so:

Theorem 1: Für zwei Algorithmen a₁ und a₂ gilt:

${\displaystyle \sum _{f}P(h_{m}^{y}|f,m,a_{1})=\sum _{f}P(h_{m}^{y}|f,m,a_{2}).}$

Wenn alle Funktionen ${\displaystyle f}$ gleich wahrscheinlich auftreten, ist die Wahrscheinlichkeit ${\displaystyle P}$, eine beliebige Folge von ${\displaystyle m}$ Werten während der Optimierung anzutreffen, nicht vom Optimierungsalgorithmus abhängig.

Versuchte Anwendung auf Evolutionsprozesse

William A. Dembski hat die No-free-Lunch-Theoreme für seine umstrittenen Hypothesen der spezifizierten Komplexität angewandt, die seiner Meinung nach mathematische Schranken für Evolutionsprozesse formulieren.^[7] Dembski verwendet diese Schranken als Argument gegen die Evolutionstheorie und für ein Intelligent Design.

Diese Argumentation wird jedoch allgemein als nicht wissenschaftlich seriös betrachtet.^{[8][9][10][11][12]} Neben anderen Einwänden wird hauptsächlich angeführt, dass Evolutionsprozesse nicht als eine Suche nach einem bestimmten von vornherein vorgegebenen optimalen Element innerhalb einer Such-Menge betrachtet werden können, wie es die No-free-Lunch-Theoreme voraussetzen.^[9][13] Die darwinsche Evolution ist im Allgemeinen eher als eine „Vermeidungsstrategie“ statt als „Suchstrategie“ zu betrachten, da hauptsächlich Überleben und Reproduktion zählen und nur solche Evolutionsschritte sicher ausgeschlossen sind, die zu Arten führen, welche dazu prinzipiell nicht in der Lage sind. Die No-free-Lunch-Theoreme sind also gar nicht anwendbar.

Ein weiterer Einwand besagt, dass die Theoreme eine Aussage über den Durchschnitt aller denkbaren Probleme machen. In der Evolutionstheorie bedeutet das: gemittelt über alle möglichen Fitnesslandschaften. Über die Effektivität des Prozesses aus Mutation und Selektion für die tatsächlich vorkommenden Fitnesslandschaften können die Theoreme nichts aussagen. Insbesondere sind die Mehrzahl aller theoretisch denkbaren Fitnesslandschaften völlig regellos, während bereits die Naturgesetze eine gewisse Struktur voraussetzen.^[11]

Wolpert selbst verwirft Dembskis Ausführungen als unmathematisch (written in jello)^[10] und fügt zudem an, dass die Fitnessfunktion evolutionärer Systeme weder als in der Zeit konstant noch als für alle Individuen identisch angesehen werden kann. Dies ist aber eine wichtige Voraussetzung für die No-free-Lunch-Theoreme und macht daher ebenfalls eine Anwendung auf evolutionäre Prozesse unmöglich.^[10][11] Tatsächlich konnten Wolpert und Macready für eine bestimmte Klasse solcher ko-evolutionärer Systeme die Existenz optimaler Algorithmen beweisen.^[14]

Siehe auch

• Liste von Sätzen der Informatik

Literatur

• Delbaen, Schachermayer: What is ... a free lunch?, Notices of the AMS, Mai 2004

Weblinks

• David H. Wolpert, William G. Macready: , 31. Dezember 1996 (PDF-Datei; 343 kB)
• Artikel der 1995 International Conference on Genetic Algorithms (ICGA-95) in Pittsburgh
• Sammlung von Artikeln zum Thema No-free-Lunch

Einzelnachweise

1. Ethem Alpaydin: Maschinelles Lernen., 2., erweiterte Auflage, De Gruyter, Berlin 2019, ISBN 978-3-11-061789-4 (abgerufen über De Gruyter Online)
2. Xinjie Yu, Mitsuo Gen: Introduction to Evolutionary Algorithms. S. 102.
3. Peter Flach: Machine Learning: The Art and Science of Algorithms that Make Sense of Data. S. 10.
4. Raymond Chiong: Nature-Inspired Algorithms for Optimisation. S. 34.
5. David H. Wolpert, William G. Macready: No free lunch theorems for search. Vol. 10, Technical Report SFI-TR-95-02-010, Santa Fe Institute, 1995.
6. Anne Auger, Benjamin Doerr: Theory of Randomized Search Heuristics: Foundations and Recent Developments. S. 258.
7. William A. Dembski: No Free Lunch: Why Specified Complexity Cannot Be Purchased without Intelligence. Rowman & Littlefield, Lanham, Md. 2002, ISBN 0-7425-1297-5.
8. J. Rosenhouse: Probability, Optimization Theory, and Evolution. In: Evolution. 56(8), 2002, S. 1721–1722.
9. H. Allen Orr: Book Review of No Free Lunch. Boston Review
10. David Wolpert: William Dembski’s treatment of the No Free Lunch theorems is written in jello. Mathematical Reviews, 2003.
11. Richard Wein: Not a Free Lunch But a Box of Chocolates. 2002.
12. M. Perakh: There is a free lunch after all: William Dembski’s wrong answers to irrelevant questions. In: M. Young, T. Edis (Hrsg.): Why Intelligent Design Fails. Rutgers University Press, 2004, chapter 11.
13. Richard Dawkins: The Blind Watchmaker. W. W. Norton & Company, New York 1996, S. 50.
14. D. H. Wolpert, W. G. Macready: Coevolutionary free lunches. In: IEEE Transactions on Evolutionary Computation. 2005, 9(6), S. 721–735.