Ich habe einige Zahlen, will die nächste in der Folge vorhersagen und weiß nichts über die Herkunft der Zahlen. Kann ich eine Vorhersage treffen? (Nein.)

1010101010101010101010101010101010101010_

Nun habe ich dieselben Zahlen, darf aber annehmen, dass einfache Erklärungen wahrscheinlicher sind als komplizierte. Kann ich jetzt eine Vorhersage treffen? (Nein.)

1010101010101010101010101010101010101010_

Ich nehme zusätzlich an, dass die Folge auf irgendeine Weise berechnet werden kann. Kann ich jetzt die wahrscheinlichste nächste Zahl vorhersagen? (Nein, nicht in endlicher Zeit. Das allgemeine Vorhersageproblem ist unlösbar.)

1010101010101010101010101010101010101010_

Kann ich einen Algorithmus schreiben, dessen Ausgabe gegen die wahrscheinlichste nächste Zahl konvergiert, wenn die Laufzeit gegen geht? (Ja. Dovetailer über alle möglichen Programme, angefangen mit dem kürzesten; die Ausgabe des kürzesten Programms, das die Zahlen und eine zusätzliche ausgibt, ist die aktuelle Hypothese.)

Wir Menschen treffen jeden Tag Vorhersagen. Der Vorteil, den wir gegenüber derzeitigen Algorithmen haben, liegt in den zusätzlichen Annahmen, die wir unbewusst machen, in der Art von inductive bias, mit dem uns die Evolution ausgestattet hat. Die Aufgabe von Forschern auf dem Gebiet des maschinellen Lernens ist es, den Suchraum von Algorithmen derart einzuschränken, dass die Laufzeit der Algorithmen polynomiell wird, und dabei möglichst wenige Lösungen für Vorhersageprobleme auszuschließen, die für unsere Welt relevant sind.

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?

Django is my web programming framework of choice. The following 1.500 words describe what I would add to the core framework in order to make machine-to-machine communication (APIs) for almost every web application a matter of minutes. Weiterlesen »

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.

Es braucht etwa 100 Zeilen Python-Code, um die Geschichte aller möglichen berechenbaren Universen zu berechnen. 100 Zeilen, um alles zu berechnen, was je berechnet werden kann. Die Physik unseres Universums ist möglicherweise berechenbar.

Was, wenn sich erweist, dass die am besten mit der Realität übereinstimmenden physikalischen Theorien die sind, die berechenbar sind? Wir können simulieren, wie Billardkugeln zusammenstoßen und welche sich wohin bewegt. Ein simulierter Zusammenstoß ist kein echter Zusammenstoß. Für uns. Für ein simuliertes Wesen? Führt die Simulation eines bewussten physikalischen Systems zu Bewusstsein?

Die Individualität einer Person ist vom Muster des Zusammenspiels der Materie abhängig, nicht von der Materie selbst. Die Atome jeder Zelle werden nach der Geburt eines Menschen viele Male ausgetauscht. Quantenphysikalisch gesehen sind zwei Teilchen einer Art sowieso nicht nur nicht unterscheidbar, sondern identisch. Wenn alle Protonen eines Körpers durch "andere" Protonen ersetzt werden, so hat das den Zustand nicht verändert. Teilchen haben keine Identität.

Wenn die Physik unseres Universums berechenbar ist oder es keinen subjektiven Unterschied zwischen Bewusstsein und der Simulation von Bewusstsein gibt, so resultiert die Ausführung eines solchen Programms (ein "Universal Dovetailer") in allen bewussten Erfahrungen, die je ein Wesen haben kann. Unabhängig davon, wie man "Wesen" oder "bewusste Erfahrung" definiert.

Aber: Ist die Erfahrung von Bewusstsein auch unabhängig davon, ob bei der Ausführung des Programms, die — wie die Ausführung jedes Programms — in diskreten Schritten abläuft, ein Rechenschritt pro Nanosekunde oder ein Rechenschritt pro Jahr ausgeführt wird? Auch dann, wenn während des Jahres der Computer, auf dem das Programm ausgeführt wird, ausgetauscht und nach Tokio verfrachtet wird? Auch dann, wenn das Ergebnis des Rechenschritts ein Jahr später nicht direkt berechnet wird, sondern bei der Berechnung aller Permutationen der Sequenz von 0en und 1en auftaucht, die die Länge des erwarteten Rechenergebnisses hat?

Stathis Papaiaonnou schreibt an die Singularity-Mailingliste:

If you look at it the right way, anything could be a computation. This has been given by John Searle as a reductio ad absurdum against computationalism, and explored by several other authors (eg. Hilary Putnam, David Chalmers, Greg Egan). The usual counterargument is that in order to map a computation onto an arbitrary physical process, the mapping function must contain the computation already, but this is only significant for an external observer. The inhabitants of a virtual environment will not suddenly cease being conscious if all the manuals showing how an external observer might interpret what is going on in the computation are lost; it matters only that there is some such possible interpretation. Moreover, it is possible to map many computations to the one physical process. In the limiting case, a single state, perhaps the null state, can be mapped onto all computations.

Welche Art von Kontinuität ist für bewusste Erfahrungen nötig?

Was ich gerne vor Beginn meines Studiums in Osnabrück gewusst hätte.

Unter anderem: Wie das erste Semester aussieht. Was man in den einzelnen Fächern lernt. Wer das Studium nach zwei Semestern abbrechen wird. Wie die Bachelor-Note zustande kommt. Was Cognitive-Science-Studenten nach dem Studium machen. Bonus: Zusammenfassungen der Vorlesungen, Mitschriften und Beispielaufgaben.

Lies weiter und du erfährst, ob du Cognitive Science studieren willst und wie du das erste Semester überstehst. Weiterlesen »

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? Weiterlesen »

Die Anwendung neuronaler Netze ist nach wie vor eines der bedeutendsten und interessantesten Themen der künstlichen Intelligenz. Die Kenntnis von Hintergründen und Einsatzmöglichkeiten ist nicht nur für Informatik-Studenten ein Muss, auch Hobby-Programmierer und KI-Interessierte können großen Nutzen daraus ziehen. Doch welche Lektüre ist für wen am besten geeignet? Bei etwa 20 Büchern in deutscher Sprache fällt die Auswahl nicht leicht. Weiterlesen »