WiWaSo

Alle Optimierungsalgorithmen sind gleich gut, wenn man ihre Performanz über alle möglichen Problemklassen betrachtet.

Mit Optimierungsalgorithmen ist alles gemeint, was nach Extrempunkten einer beliebigen Kostenfunktion suchen kann. Dazu zählen leider auch, was mich direkt betrifft, alle generellen maschinellen Lernverfahren, insbesondere genetische Algorithmen. No Free Lunch kann man auch so erklären:

Für jede Problemklasse, auf denen ein Algorithmus A besser ist als ein Algorithmus B gibt es eine Problemklasse, auf der B besser ist als A.

Bevor man jetzt alle Arbeiten an Optimierungsalgorithmen für alle Zeit mit der Begründung "blinde Suche ist ja blöderweise genausogut" einstellt, sollte man aber bedenken, dass in der praktischen Anwendung das Geheimnis des Erfolgs meist darin liegt, genau den für die Problemklasse richtigen Algorithmus zu finden. Wenn man sich nicht unbedingt alle möglichen Probleme interessiert, sondern nur für die, die man gerade jetzt lösen muss, ist maschinelles Lernen tatsächlich nicht völlig sinnlos :)

Auch wenn man bei WiWaSo eigene Unkenntnis nicht gerne zugibt: No Free Lunch zählte nicht zum Curriculum in jenen wilden Jahren der Künstlichen Intelligenz (ca. 1989-1995), als ich noch prüfungsrelevanten Stoff pauken musste. Den Verdacht, dass No Free Lunch (NFL) gilt, hat irgendwann jeder, der mit Lernverfahren arbeiten muss. Dass es aber tatsächlich einen Beweis gibt, ist bis vor einem Jahr völlig an mir vorbei gegangen. Schön, dass die Seite www.no-free-lunch.org die wichtigsten Papiere zu diesem Thema listet, damit ignorante wenig aufmerksame Menschen so wie ich etwas für ihre Bildung tun können. Weniger schön, dass jener unsägliche Kreationist Bill Dembski mit seinem Machwerk des absichtlichen Nichtverstehens von NFL immerhin auf Platz 3 der Leseempfehlung landet.

Die Inkompatibilität von No-Free Lunch und Anti-Evolutions-Argumenten erläutert Marc Chu-Caroll hier: die im NFL vorausgesetzte statische Fitness-Landschaft, d.h., die feste Kostenfunktion, ist keine Eigenschaft von biologischen Systemen. Was heute ein gutes lokales Maximum ist (Lebewesen lebt und macht viele Kinder) kann morgen schon eine biologische Nische mit wenig Überlebenschancen sein (Lebewesen hat nicht ausreichend Immunität gegen neuen Krankheitserreger). Da wir die Fitnesslandschaft von Lebewesen nicht statisch beschreiben können, kann man hier NFL auch nicht anwenden, um die Evolutionstheorie mathematisch zu unterminieren. Nach allem, was wir heute wissen, funktioniert Evolution ganz gut. Wenn ein Theorem für das mathematische Modell der Wirklichkeit voraussagt, dass die Wirklichkeit so nicht funktionieren kann, dann ist es offensichtlich sinnvoll, sich ein besseres Modell zu suchen. Ich habe aber den Verdacht, dass es für nicht-statische Fitnesslandschaften ein dem NFL-äquivalentes Theorem gibt. Wahrscheinlich liegt der besondere Erfolg evolutionärer Suchstrategien neben der eingebauten Flexibilität in besonderen Eigenschaften des Suchraums, der durch die Art der Vermehrung von Lebewesen (Kopieren der DNA) festgelegt ist. Auf Fitnesslandschaften, die besondere Merkmale aufweisen müssen, gilt NFL nämlich ebenfalls nicht.