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) 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.

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 bzw. Datensätze 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. 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. In einer verschärften Formulierung von 2001 gilt das No-free-Lunch-Theorem der Optimierung auch für Problemmengen, die unter Permutation abgeschlossen sind.

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.