Die Algorithmische Zufälligkeit

Hutter’s Forschungen sind zu theoretisch, um sie visualisieren zu können, daher ist hier ein Pseudo-Zufall abgebildet, erstellt mit einem Computerprogramm. Marcus Hutter ist Professor an der Research School für Computerwissenschaften der Australian National University in Canberra. Berühmt haben ihn vor allem seine Forschungen auf dem Gebiet der künstlichen Intelligenz gemacht, das ist im Prinzip Philosophie mit ziemlich viel Mathematik. Hier erklärt er, warum algorithmische Zufälligkeit essenziell ist für die Konstruktion künstlicher Intelligenz. Algorithmische Zufälligkeit ist allgemein anerkannt als der beste, zumindest als der Standardbegriff der Zufälligkeit. Es gibt einige gleichwertige Definitionen der algorithmischen Zufälligkeit, eine von ihnen ist die folgende: Nimm alle computergestützten Tests auf Zufälligkeit, die du durchführen kannst, und wenn eine Kette von Daten alle diese Tests besteht, dann kannst du sagen, diese Folge ist ein algorithmischer Zufall oder eine sogenannte Martin-Löf-Zufälligkeit. Es gibt eine wesentlich einfachere Definition und die lautet: Wenn eine Kette nicht durch den bestmöglichen theoretischen Kompressor komprimiert werden kann—die sogenannte Kolmogorow-Komplexität—dann liegt ein Kolmogorow-Zufall vor. Diese zweite Definition leuchtet intuitiv ein, denn wenn wir davon ausgehen, dass eine Folge komprimierbar ist, dann lässt sie sich auch kürzen. Das bedeutet, du hast eine gewisse Regelmäßigkeit, also kann das Ganze kein Zufall sein. Diese beiden Definitionen sind daher gleichwertig. Die kurze Antwort auf die Frage, warum Zufälligkeit eine wichtige Rolle spielt in der Theorie der künstlichen Intelligenz, lautet, dass ein intelligentes System unterscheiden kann zwischen einem nützlichen Signal und einem zufälligen Geräusch. Daher ist es wichtig, die Zufälligkeit zu untersuchen, aber das ist nicht der eigentliche Grund. Wenn eine Zeichenkette algorithmisch zufällig ist, dann gibt es da keine Struktur und nichts, von dem man lernen könnte. Wenn auf der anderen Seite die Zeichenkette komprimierbar ist, sollte ein intelligentes System diese Struktur auch nutzen. Eine Zeichenkette zu komprimieren, hängt also eng damit zusammen, Regelmäßigkeiten in der Kette aufzufinden, das bedeutet, die Kette zu verstehen und in der Lage zu sein, ein Modell von ihr anzufertigen. Und dann kann man diese Modelle für Vorhersagen nutzen—wir wissen alle, wie wichtig es ist, zumindest einige Aspekte der Zukunft vorherzusagen, um intelligent handeln zu können. Der Prozess läuft also von Kompression über Regelmäßigkeit und Modellbildung zur Vorhersage, und schließlich zu intelligenten Handlungen. Die Theorie der algorithmischen Zufälligkeit ist über das Konzept der Komprimierbarkeit indirekt hilfreich für das Problem der Induktion. Nehmen wir an, du hast eine Reihe an Wetterdaten und willst vorhersagen, ob es morgen regnet oder nicht. Normalerweise wirst du auf der Grundlage historischer Daten ausgeklügelte Klimamodelle konstruieren—das ist alles, was wir haben, wir können unsere Welt beobachten und dann Modelle von ihr anfertigen. Und dieses Anfertigen von Modellen ist der induktive Schritt. Aber wie funktioniert diese Modellbildung? Die Menschen machen das irgendwie mit der Hand, aber wie sollte das ein Computer bewerkstelligen? Du kannst ihn so programmieren, dass er Ähnliches tut wie du, aber in letzter Konsequenz wirst du vor der Frage stehen, philosophisch oder allgemein, was das Anfertigen von Modellen eigentlich ist. Die Antwort lautet: Das Anfertigen von Modellen bedeutet, Kurzbeschreibungen deiner Daten zu finden. Wenn du ein Universalsystem der künstlichen Intelligenz entwickeln willst, dann brauchst du einen universalen Induktionsschritt oder einen universalen Modell-Lern-Schritt. Die zugrunde liegende Idee dabei ist, Kurzprogramme von Daten zu finden und diese Programme dann als Modelle für Vorhersagen zu nutzen. Und das ist vollkommen generisch; du brauchst überhaupt keine Vorannahmen über deine Daten. Welcher Art auch immer deine Daten sind, nutze einen Kompressor, um ein Kurzprogramm für sie zu finden und verwende dann dieses Kurzprogramm für Vorhersagen. Ein wunderbarer Vorteil der algorithmischen Zufälligkeit und der Induktionstheorie nach Solomonoff ist der, dass du dir keine Gedanken darüber machen musst, wie beliebige Geräusche von sinnvollen Daten unterschieden werden können. Wenn du zum Beispiel die Kette 10101010 hast … die aber wegen Nebengeräuschen ein kleines bisschen verzerrt ist, wird Solomonoff voraussagen, dass die Kette in Zukunft auch 10101010 sein wird … mit kleinen Nebengeräuschen, ohne die Geräusche von den Zeichen zu unterscheiden. In der Praxis musst du dich dieser Theorie annähern. So weit sind wir heute noch nicht, aber wir haben einen einzelnen Agenten entwickelt, der fähig ist von null an zu lernen, ohne darüber informiert zu sein, was er tatsächlich tun soll. Er lernt selbst, richtig zu handeln. Er lernt rein aus der Erfahrung Tic Tac Toe zu spielen; wenn du ihn mit Pac-Man verknüpfst, dann lernt er das zu spielen; wenn du ihn mit einer ganz einfachen Version von Poker verbindest, dann lernt er Pokerspielen. Er ist nicht programmiert, die Regeln der Spiele zu kennen; er lernt lediglich, indem er spielt und gelegentlich Rückmeldungen darüber bekommt, ob er gewonnen oder verloren hat. Wir hoffen, in den kommenden zehn Jahren von diesen Strategiespielen zu realistischeren Spielen oder anderen Problemen übergehen zu können.

Illustration von Marius Watz