Projektidee: Ein automatisch erstelltes und aktualisiertes Ranking von Algorithmen für maschinelles Lernen macht Fortschritte auf dem Gebiet der allgemeinen künstlichen Intelligenz sicht- und messbar.

Das Messverfahren

Lernverfahren wie rekurrente neuronale Netze, Markov-Modelle und genetische Algorithmen sollen akkurate Vorhersagen liefern. Wissenschaftliche Veröffentlichungen sprechen davon, dass der jeweils vorgestellte Algorithmus “auf gewisse Weise” optimal ist. Für das Gebiet der allgemeinen künstlichen Intelligenz ist interessant, zu wissen, welcher Algorithmus allgemein am besten geeignet ist, d.h. für die Vorhersage von Sequenzen, über die wir lediglich wissen, dass sie von einem berechenbaren Prozess generiert wurden und dass einfache Erklärungen wahrscheinlicher sind als komplizierte.

Eine Sequenz ist eine endliche oder unendliche Folge von Symbolen eines Alphabets (z.B. {0, 1}). Die meisten endlichen Sequenzen sind nicht effektiv lernbar, da kein Programm mit im Vergleich zur Sequenz kurzer Beschreibung existiert, das diese Sequenzen deterministisch ausgibt. Das heißt: Die Kolmogorov-Komplexität der meisten endlichen Sequenzen entspricht der Länge der Sequenzen. Für den Vergleich verschiedener Lernalgorithmen beschränken wir uns auf unendliche Sequenzen mit endlich langen Erzeugerprogrammen.

Ein Vorhersagealgorithmus ist dann allgemein besser als ein anderer, wenn er lernen kann, Sequenzen mit höherer Kolmogorov-Komplexität vorherhersagen (und beide einfache Sequenzen gleich gut vorhersagen können). Praktisch jeder Algorithmus wird folgende Sequenz von sehr niedriger Komplexität lernen können:

111111111111111111111111111111111111111111...

Bei etwas höherer Komplexität werden einige Algorithmen Probleme bekommen:

011011100101110111100010011010101111001101...

Hätte man eine Datenbank, die jedes sequenzerzeugende Programm (oder jede Sequenz) sowie die Komplexität der von jedem Programm generierten Sequenz speichert, so könnte man für eine Reihe von Algorithmen Tests durchführen, um herauszufinden, in welchem Umfang und bis zu welcher Komplexität jeder Algorithmus Sequenzen lernen kann. Mit den Ergebnissen dieser Tests ließe sich ein Ranking erstellen, das auf einen Blick verrät, welcher Algorithmus die meisten und komplexesten Sequenzen lernen kann.

Eine solche Datenbank ist unmöglich: Es gibt unendlich viele sequenzerzeugende Programme, die Sequenzen sind unendlich lang und deren Komplexität ist nicht algorithmisch bestimmbar.

Die Menge der sequenzerzeugenden Programme ist eine Teilmenge aller Programme, und diese Menge ist aufzählbar unendlich. Die Kolmogorov-Komplexität ist definiert als die Länge des kürzesten Programms, das eine Sequenz erzeugt. Generiert man alle Programme, angefangen mit dem kürzesten, so ist bekannt, ob bereits ein kürzeres Programm den gleichen Sequenzbeginn (eine festgelegte Anzahl von Zeichen, z.B. 10.000) erzeugt hat oder ob die Länge des gerade betrachteten Programms als Abschätzung der Komplexität der erzeugten Sequenz verwendet werden kann — Abschätzung deshalb, weil nur eine endliche Anzahl der Zeichen zweier Sequenzen verglichen werden können und nach Rice nicht algorithmisch festgestellt werden kann, ob zwei Programme die gleiche Funktion berechnen.

Mit einigen Abschätzungen ist es möglich, Ausschnitte der beschriebenen Datenbank zu erstellen, die in der Komplexität nach oben beschränkt sind:

1. Wir generieren der Reihe nach Turingmaschinen mit leerem Eingabe- bzw. Arbeitsband und nur in einer Richtung beschreibbarem Ausgabeband, angefangen mit der kürzesten.
2. Uns interessieren nur Turingmaschinen, die unendliche Sequenzen generieren:
   • Hält eine Turingmaschine an, so verwerfen wir diese Turingmaschine.
   • Hat eine Turingmaschine nach 10^12 Schritten noch keine 10.000 Ausgabesymbole erzeugt, so verwerfen wir diese Turingmaschine.

   Andernfalls nehmen wir an, dass die aktuelle Turingmaschine eine der Turingmaschinen ist, die eine unendliche lange Sequenz ausgeben (Abschätzung I).

3. Wenn die ersten 10.000 Zeichen der Sequenz, die eine Turingmaschine erzeugt, noch von keiner anderen Turingmaschine erzeugt wurden, speichern wir die Länge der Beschreibung der Turingmaschine sowie die 10.000 Zeichen der Sequenz in einer Datenbank.
4. Die gespeicherte Länge entspricht in etwa der Länge der kürzesten Turingmaschine, die die Sequenz generiert und ist damit ein Maß für die Kolmogorov-Komplexität der Sequenz (Abschätzung II).

Das wiederholen wir, bis die Datenbank “groß genug” ist. In einer 150 GB großen Datenbank lassen sich bei 10.000 Zeichen pro Sequenzabschnitt etwa 100 Millionen unterschiedliche Sequenzabschnitte speichern.

Der kritische Punkt

Ist die Komplexität der einfachsten in der Datenbank gespeicherten Sequenzen so gering, dass diese mit den meisten Vorhersagealgorithmen gelernt werden können und die Komplexität der komplexesten Sequenzen so groß, dass das Lernen der Sequenz mit aktuellen Vorhersagealgorithmen nicht mehr möglich ist?

Werden in dieser Datenbank “interessante” Sequenzen — Sequenzen von nichttrivialer Komplexität — vorkommen? Oder lediglich 50 Millionen unterschiedliche, sich wiederholende Muster? Wie sieht es aus, wenn die einfachsten Sequenzen herausgefiltert und verworfen werden? Wie sieht es aus, wenn stets der Großteil der Sequenzen verworfen wird, die von den Top 20 Algorithmen zuverlässig vorhergesagt werden?

Bei zwei Bandzuständen (0 und 1) und n internen Zuständen gibt es (4*n)^(2*n) verschiedene Turingmaschinen mit einem in beide Richtungen bewegbaren Band. Die Anzahl der Turingmaschinen steigt schon bei wenigen Zuständen sehr schnell an:

1 interner Zustand: 16 TM
2 interne Zustände: 4096 TM (25 unterschiedliche)
3 interne Zustände: 2.985.984 TM (16.400 unterschiedliche)
4 interne Zustände: 4.294.967.296 TM
5 interne Zustände: 10.240.000.000.000 TM
6 interne Zustände: 36.520.347.436.056.576 TM
7 interne Zustände: 182.059.119.829.942.534.144 TM

Nach Stephen Wolfram stößt man auf interessantes Verhalten, sobald man Turingmaschinen mit mindestens vier internen Zuständen betrachtet. Die minimale Zahl der internen Zustände einer Turingmaschine, die eine bestimmte Sequenz berechnet, dient als Maß für die Komplexität der berechneten Sequenz. Ist das Ranking brauchbar, wenn keine Turingmaschinen mit mehr als sieben internen Zuständen betrachtet werden? Lambda Calculus, wie von John Tromp vorgeschlagen, könnte die bessere Wahl sein. Das Ranking könnte sich jedoch auch damit als unbrauchbar erweisen.

Beantwortete Fragen

Bislang ist es schwierig, einige Fragen aus dem Bereich des maschinellen Lernens zu beantworten. Lässt sich ein Ranking für Lernalgorithmen umsetzen, so wird sich das für folgende Fragen ändern:

Wie sieht der aktuelle Stand der Forschung aus? Oder: Das Ranking.

1. Alle bekannteren Vorhersagealgorithmen werden in einer festgelegten Programmiersprache implementiert und zum Ranking hochgeladen.
2. Jeder Algorithmus wird mit allen oder mit einer statistisch relevanten Auswahl an Sequenzen getestet und erhält einen Score zugeteilt, der besagt, für wie viele Sequenzen und bis zu welcher Komplexität der Algorithmus zuverlässige Vorhersagen macht.
3. Ein Ranking wird erstellt, bei dem die Algorithmen mit dem höchstem Score an der Spitze stehen.

Wie gut ist mein Vorhersagealgorithmus?

1. Ein in einer festgelegten Programmiersprache geschriebener Algorithmus wird auf der Website des Rankings hochgeladen.
2. Der Algorithmus wird mit allen oder mit einer statistisch relevanten Auswahl an Sequenzen getestet und erhält einen Score zugeteilt (s.o).
3. Die Leistung des Algorithmus kann dadurch mit der anderer Algorithmen verglichen werden und der Algorithmus kann in die Highscore-Liste aufgenommen werden.

Welcher Algorithmus ist für mein Vorhersageproblem geeignet?

1. Sequenzen, die typisch für das Problem sind, werden auf der Website des Rankings hochgeladen.
2. Alle Algorithmen, die am Ranking teilnehmen, werden auf die hochgeladenen Sequenzen angewendet.
3. Ein nach Korrektheit der Vorhersagen sortiertes, problem-spezifisches Ranking wird ausgegeben.

Offene Fragen

• Soll die Programmlänge mit in die Berechnung des Scores eines Algorithmus einbezogen werden oder soll es lediglich ein generelles Limit für alle Programme geben?
• Welche Limits sollen für Laufzeit und Programmlänge gesetzt werden?
• Wie lange sollen die Sequenzabschnitte sein, die in der Datenbank gespeichert werden? 10.000 Zeichen?
• Wie sollen die Sequenzabschnitte in Lernsequenz (die den Algorithmen präsentiert wird) und Testsequenz (die vorherzusagen ist) aufgeteilt werden? Wie lang soll der vorherzusagende Abschnitt sein?
• Wie wird die Vorhersage bewertet? Gelten nur komplett richtige Vorhersagen?
• Sollen auch die kürzeren Ausgaben von anhaltenden Turingmaschinen miteinbezogen werden?
• Ein praxistauglicher Algorithmus könnte stark von zusätzlichen Annahmen über seine Umgebung abhängig sein. Ideal sind Vorhersage- und Komprimierungsalgorithmen nur für jeweils eine einzige Wahrscheinlichkeitsverteilung an Eingaben. Ob ein Algorithmus, der für die allgemeinste berechenbare Wahrscheinlichkeitsverteilung an Eingaben ideal ist, auch in der wirklichen Welt brauchbar ist, ist nicht geklärt.
• Ist es zweckmäßiger, probabilistische Sequenzen und Vorhersagealgorithmen statt exakter Algorithmen zuzulassen?
• Wie wird der Score berechnet? Zählen Sequenzen mit niedrigerer Komplexität mehr oder weniger? Wie wird ein Vorhersagealgorithmus bewertet, der zwar komplexe Sequenzen vorhersagen kann, aber bei sehr vielen Sequenzen von niedriger Komplexität fehlschlägt?
• Welche Implementation eines universellen Computers ist am sinnvollsten? Turingmaschinen? Lambda Calculus?

Fazit

Marcus Hutter hat in seiner Doktorarbeit bewiesen, dass die optimale Vorgehensweise einer künstlichen Intelligenz darin besteht, nach einer beliebigen Anzahl von Beobachtungen der Umgebung das kürzeste Programm zu finden, das diese Beobachtungen vorhersagt und anzunehmen, dass die Umgebung durch dieses Programm kontrolliert wird. Verbesserte allgemeine Vorhersagealgorithmen sind demnach mit Fortschritt auf dem Gebiet der künstlichen Intelligenz gleichzusetzen.

Alles, was gemessen wird, verbessert sich. Ich schlage vor, eine Datenbank mit Sequenzabschnitten und zugehöriger (geschätzter) Kolmogorov-Komplexität anzulegen, diese Sequenzen von verschiedenen Lernalgorithmen vorhersagen zu lassen und den Erfolg der Algorithmen in einem Ranking sichtbar zu machen.

Ist diese Idee realistisch?

Lukas Biewald, ehemals NLP-Forscher im Stanford AI Lab:

My job title is “Scientist”, but I never use the scientific method, at least as I remember it from 6th grade earth science where you make a hypothesis and test it with an experiment. Instead I mostly mine through data and look for patterns.

In der experimentellen Neurobiologie sieht es genauso aus, auch wenn wissenschaftliche Veröffentlichungen hier noch immer nach dem Muster “Wir hatten folgende Hypothese, haben Sie überprüft und sie hat sich als wahr herausgestellt” gestrickt sind. Mit dem tatsächlichen Alltag eines Wissenschaftlers hat das wenig gemein.

Dass die herkömmliche wissenschaftliche Methode brauchbar ist, wenn man die Wahrheit dessen überprüfen will, was man zu wissen glaubt, aber dass sie einem nicht sagen kann, wohin man gehen soll, wusste schon Robert M. Pirsig. Das ist nicht neu.

Neu ist, dass das Aufstellen von Hypothesen mehr und mehr automatisisert wird.

Wir wissen wenig über unsere Welt, und das, was wir wissen, ist so seltsam, dass wir es meistens ignorieren. Es gibt keine objektive Zeit; für manche Beobachter geschieht A vor B, für andere B vor A. Wir können nicht feststellen, ob wir in einer Simulation leben. Wir wissen nicht, ob bewusste Beobachter sterben können, und welche Rolle sie in der Physik überhaupt spielen. Wir können nur raten, warum in diesem Universum außer uns niemand zu sehen ist.

Wir wissen wenig über die Zukunft unserer Welt, und das, was uns die Vergangenheit verrät, ist so schwindelerregend, dass wir lieber Konstanz prognostizieren. Ich bin 21 Jahre alt — als ich geboren wurde, gab es kein World Wide Web. Den Großteil meiner Schulzeit über gab es dieses eine Projekt nicht, das es sich zur Aufgabe gemacht hat, jedem Menschen kostenlosen Zugang zum Wissen der Menschheit zu bieten. Als der Vater meiner Freundin geboren wurde, hatte Alan Turing noch nicht beschrieben, was Algorithmen sind. Vor nicht einmal einem Menschenleben gab es keine Computer. Ein halbes Menschenleben weiter und es gab keine Elektrizitätsversorgung. Zwei Menschenleben zuvor keine Dampfmaschinen. Drei Menschenleben weiter und wir sind im Mittelalter.

Eine Generation vor uns brauchte es tagelanges Recherchieren in Bibliotheken, um herauszufinden, ob die Menschheit die Antwort auf eine Frage hat. Heute genügen 10 Sekunden, um die Antwort auf fast jede Frage zu finden, die die Menschheit je beantwortet hat. Ein oder zwei Generationen nach uns genügen 10 Sekunden, um die Antwort auf fast jede Frage zu finden, die je beantwortet werden kann.

Wir verändern alles und merken es nicht. Blind vorwärts ging lange gut.

Wenn es allgemeine Methoden gibt, um ausgehend von vergangenen Ereignissen Vorhersagen zu treffen, und wenn man Vorhersagemethoden nach ihrem Erfolg bewerten kann, so gibt es eine Methode für Vorhersagen, die besser ist als jede andere. Das Ergebnis von Vorhersagen nach dieser Methode stimmt im Durchschnitt besser mit der Realität überein als das jeder anderen Methode — egal, ob Naturkatastrophen, Bevölkerungszahlen oder Aktienwerte vorhergesagt werden.

Solomonoffs Theorie der universellen Induktion ist diese Methode. Man könnte das Problem der optimalen Vorhersage damit als gelöst betrachten — wäre Solomonoffs Theorie nur berechenbar. Ein Algorithmus, der unter beschränkten Ressourcen — wozu auch die algorithmische Komplexität zählen kann — Vorhersagen trifft, die beweisbar besser sind als die jedes anderen denkbaren Algorithmus, ist noch nicht gefunden. Das sollte das zentrale Anliegen des Gebietes der künstlichen Intelligenz sein.

Induktive Wissenschaften wie die Physik, die Chemie oder die Astronomie machen nichts anderes, als Daten zu sammeln und anhand der Daten elegante Theorien zu finden, mit denen sich die Zukunft möglichst exakt vorhersagen lässt.

Es ist sinnvoller, das Problem der Induktion direkt zu lösen.

Angenommen, das zunehmende Verständnis des Phänomens Intelligenz erlaubt es uns, einen Prozess zu erstellen, der eine gewisse Grundintelligenz besitzt und dem Ziele vorgegeben werden können. Wir geben diesem Prozess die Möglichkeit, seine eigene Leistungsfähigkeit durch Selbstmodifikationen zu verbessern und ein Ziel, das weit jenseits des mit menschlicher Intelligenz Erreichbaren liegt. Und warten. Und dann? Read on »

Das Gebiet der künstlichen Intelligenz ist bislang nicht weit über Schachcomputer und Suchmaschinen hinausgekommen. Es gibt Anzeichen dafür, dass wir in diesem Jahrhundert die Schwelle an Verständnis und verfügbarer Technik überschreiten werden, die es uns ermöglicht, das Phänomen Intelligenz technologisch nachzubilden. Ist allgemeine künstliche Intelligenz möglich? Wenn ja, auch wünschenswert? Read on »

“We are scanning those books to be read by an AI”. So lauteten die Worte seiner Gastgeber, schreibt der Historiker George Dyson über seinen Besuch des Google-Hauptquartiers. Eigentlich sollte uns das nicht überraschen. Was künstliche Intelligenz angeht treffen sich Möglichkeiten und Motivation nirgendwo so direkt wie bei Google. Read on »

Jeff Hawkins ist der Gründer von Palm Computing und Handspring und einer der erfolgreichsten Unternehmer des Silicon Valley. Jetzt befasst er sich wieder mit dem Gebiet, das ihn schon als Jugendlicher interessierte: Zu Verstehen, was Intelligenz ist und wie das menschliche Gehirn Intelligenz hervorbringt, um nach diesem Prinzip intelligente Maschinen zu bauen. Read on »

In den Kapiteln “Artificial Intelligence” und “Neural Networks” aus dem Buch “On Intelligence” beschreibt Jeff Hawkins seine persönliche Beziehung zum Gebiet der künstlichen Intelligenz. Er gibt eine kurze Zusammenfassung der Geschichte der traditionellen KI und erklärt, warum weder diese noch der Bereich der neuronalen Netze zu den erhofften intelligenten Maschinen geführt hat. Read on »

In den Kapiteln “A New Framework of Intelligence” und “How the Cortex Works” aus dem Buch “On Intelligence” legt Jeff Hawkins seine Theorie von Intelligenz dar: Er zeigt die zentrale Rolle von Vorhersagen auf und wie sich diese in ein übergeordnetes “memory-prediction framework” integriert, geht auf die Bedeutung von Sequenzen ein und erläutert die Rolle von Thalamus und Hippocampus. Read on »