Irgendwo hier liegen die Grenzen des Mustererkennungsapparats in unserem Kopf. Das, was wir verstehen können, ist keine obere Schranke für die Komplexität unserer Welt. Aber ich wiederhole mich.

If you have always wondered why everyone says that your pancakes taste interesting, why women tend to be better at cooking (hint: they think in relations) and what your friends really mean when they rave about heuristic search planning for first-order Markov decision processes, wonder no more. Few answers but lots of pretty pictures, fresh from today’s relational reinforcement learning seminar:

“Half of the meaningful things philosophy has said about artificial intelligence have already been said by Turing 50 years ago.” I do not remember who said this, and it is probably an overstatement, but it is not far from the truth. Even the AI textbook by Russell and Norvig claims that Turing’s paper Computing Machinery and Intelligence contains “virtually all objections [against the possibility of thinking machines] that have been raised in the half century since his paper appeared.”

Here are the slides for the presentation I held in Tuesday’s philosophy class, in the hope that they may be of some use, even if part of it is incomprehensible for anyone who did not read the paper or listen to the talk:

You probably heard of the idea that, at some point in time, we might create systems that solve certain tasks and that get better at these tasks by recursively modifying their code. Here is some scary reasoning:

1. A system cannot predict (=understand) a system of greater algorithmic complexity.
2. Therefore, the only way for a system to improve in a way that increases its algorithmic complexity is trial and error, thereby keeping the best results — i.e. evolution.
3. The only goal that is stable under evolution is rapid reproduction.
4. Therefore, the only stable goal for recursively self-improving systems is rapid reproduction.

I really hope that someone will point out the flaw in this line of thought or show me the reason why it does not apply to our world and to any self-modifying systems we might create.

Hier und jetzt ist der Anfang von allem, was nach uns kommt. Vielleicht werden Sonnensysteme und Galaxien einst unsere Heimat, vielleicht werden Milliarden Leben zu Trillionen, Quadrillionen oder zu einer ähnlich unvorstellbaren Zahl, so viel größer und bedeutender als alles, was jetzt ist, doch es geht nicht ohne uns. Unsere Generation hat sich Fragen und Entscheidungen zu stellen, für die es keine zweite Chance gibt. (Eine davon: Wie überleben wir die nächsten 30 Jahre, wenn fortgeschrittene Bio-, Nano- und Informationstechnologien Einzelpersonen und kleinen Gruppen enormen Einfluss geben?)

Wir Menschen unterscheiden uns nicht großartig in unseren Wünschen. Wir wollen Glück, Freude, Freiheit, Unabhängigkeit, Sicherheit, Wissen, Kreativität, Individualität, Sexualität, Freundschaft und Liebe (nun ja, Männer zumindest). Wir schätzen unser Leben, das unserer Freunde, unserer Familie und das unserer sechs Milliarden Mitmenschen. Trotzdem ziehen wir in verschiedene Richtungen, konkurrieren, intrigieren und machen generell den Eindruck, als ob wir es darauf anlegen, paradox zu handeln.

Wenn wir verstehen, welches Ausmaß die Zukunft hat, die auf dem Spiel steht, und wenn wir uns im Großen und Ganzen einig sind, was uns jetzt und für diese Zukunft wichtig ist, warum funktioniert es dann nicht besser^TM?

Warum leben wir nicht längst in Utopia, wenigstens asymptotisch?

Die Erklärung, die ich nicht glaube: Es geht nicht besser. Würde man jeden Menschen fragen, wie sehr diese Welt seinen Vorstellungen entspricht, und so zu einem Gesamtbild kommen, so gäbe es nichts, was dieses Bild dauerhaft besser machen könnte. Für diese Erklärung spricht die Anpassungsfähigkeit unseres Gehirns, die daran schuld ist, dass die meisten Änderungen unsere Gesamtzufriedenheit nicht dauerhaft verbessern. Glück ist die erste Ableitung positiver Veränderung. Aber, erstens: Lasst uns die offensichtlichen Unmenschlichkeiten dieser Welt beheben, dann können wir noch einmal darüber reden, ob es nicht besser geht. Zweitens: Manche Leute scheinen immer ein bisschen glücklicher zu sein als andere. Gene und Umwelteinflüsse legen die Biochemie unseres Gehirns fest und wir sind dabei, beides zu verstehen.

Die Erklärung, die ich gerne glauben würde: Die Probleme unserer Welt sind komplex. Wir sind auf dem Weg zu Lösungen, aber die erfordern ein gewisses Mindestmaß an Zeit und Technologie. Es wäre falsch, sich an neue Technologien zu klammern, weil diese beinahe immer zu polaren Zwecken eingesetzt werden können, aber ein Blick auf die Geschichte macht klar, dass neue Technologien Einfluss haben. Die Kombination aus omnipräsentem mobilem Web für die Massen und Suchmaschinen, die natürliche Sprache verstehen, könnte die Wissensverteilung weiter demokratisieren. Prognosemärkte (die von Google, Microsoft, HP und Intel bereits intern eingesetzt werden) könnten Teile der Politik rationaler gestalten, der Anfang der vollständigen Aufzeichnung der Menschheitsgeschichte alle kollektiven Entscheidungen.

Die Erklärung, die immer nur andere betrifft: Das sind alles egoistische Nichtsnutze, denen die Menschheit egal ist, so lange sie Familie, Job und ein halbwegs interessantes Leben haben. Unterstützt werden sie in ihrer Haltung von Wissenschaft und Wirtschaft, die Gedanken über den Lauf der Welt zugunsten kurzfristiger und handfester Resultate bestrafen. Andererseits werden gesellschaftliche Fragen gerne mal eben beim Mittagessen gelöst (wenn gerade keine Fußball-WM stattfindet) und mit zufriedenem “Tja, so müsste man’s machen” abgehakt. Zu Handlungen kommt es natürlich nicht, denn dafür bräuchte man Lösungen, die tatsächlich funktionieren, müsste herausfinden, wie man als einzelner zur Umsetzung beitragen kann, und müsste die Lösungen finden, von denen man selbst profitiert. Wozu die Menschheit retten, wenn es nicht entweder Geld, Sex oder Status bringt oder sowieso auf dem Weg zur Rettung des eigenen Lebens liegt?

Die Erklärung, die mich (und dich!) betrifft: Wir arbeiten auf Teilziele hin, die nicht direkt dem entsprechen, was wir wirklich wollen. Weil das fast jeder tut, weil verschiedene Teilziele oft gegensätzliche Aktionen erfordern und weil die Ziele selbst dann oft nicht erreicht werden, heben sich unsere Bemühungen mehr oder weniger auf. Unser Tun führt so zwar zu neuen Methoden und zu neuen Erkenntnissen über unsere Welt, die indirekt zur Realisierung unserer Wünsche beitragen können, ist aber ineffektiv und potentiell schädlich. In dem Moment, in dem wir uns einer Ideologie verschreiben, weil wir glauben, dass die Durchsetzung von deren Axiomen den Menschen das geben wird, was sie wirklich wollen, arbeiten wir an der Verbreitung der Ideologie und nicht mehr an den eigentlichen Problemen.

Glücklicherweise ist die Lösung einfach: Wir wählen in jedem Moment die Handlung, die für sich genommen am ehesten unseren Werten entspricht, anstatt uns auf eine Ideologie oder auf ein langfristiges Ziel festzulegen und darauf hinzuarbeiten.

Dummerweise funktioniert sie nicht in jedem Fall, insbesondere dann nicht, wenn wir existentielle Risiken — Katastrophen, die das Ende der Menschheit bedeuten können — in Betracht ziehen und uns der Fortbestand der Menschheit doch ein bisschen kümmert.

KI in zwei Sätzen: Die Annahme, dass wir in absehbarer Zeit auf einen relativ allgemeinen Mustererkennungsalgorithmus stoßen, der mit genügend Rechenpower die Mustererkennungs- und Vorhersagefähigkeiten des menschlichen Gehirns übertrifft, ist (für diese Art von Annahmen) weit verbreitet. Deutlich kontroverser ist die Idee, dass Algorithmen praktisch möglich sein könnten, die Veränderungen an sich selbst vornehmen, um so große Klassen von formalisierbaren Probleme bestmöglich zu lösen — unabhängig davon, wie anspruchsvoll diese Probleme sind, d.h. wie viel Intelligenz zu deren Lösung nötig ist.

Die formale Analyse der Approximierbarkeit theoretischer Modelle von Superintelligenz in unserer physikalischen Welt benötigt unsere Aufmerksamkeit, wenn wir wissen wollen, wo auf unserer Liste existentieller Risiken und Chancen maschinelles Lernen steht. Forschung auf dem Gebiet ist ein langfristiges Vorhaben, eines, das jahrelanges Lernen voraussetzt und das mit signifikanter Wahrscheinlichkeit fehlschlägt. Das ändert nichts daran, dass solche Forschung wirklich, wirklich wichtig ist.

Letzte Woche, bei Pasta und Pizza, hat Jürgen die Frage in die Runde geworfen, wie groß denn der Anteil unserer Zeit sei, den wir für das Jetzt leben, und wie groß der, den wir für die Zukunft leben. Zunächst allgemeine Übereinkunft, dass man seine Zeit wohl kaum so klar kategorisieren könne. Dann, von dem, dessen theoretische Grundlagenforschung auch in 100 Jahren noch relevant sein wird (mehr als jetzt): I don’t care about the future.

I do. Aber vielleicht macht das keinen Unterschied.

Of course, I have no idea what I am talking about. I am a first-year undergraduate, I have never been to any other conference, and when a fellow student from Germany asked me “What, then, are you doing here?”, I didn’t really mind. The AAAI conference is one of the most popular international AI conferences, certainly the most popular one in North America. This year it took place in Vancouver, Canada. What follows is a list of the tutorials, talks and technical sessions I attended, each with a one-line summary of what I learned.

Tutorials I attended

• General Game Playing is the task to write programs that learn to play arbitrary games solely by being given the rules of a game. Allow games with an infinite number of states and this is as close as you can get to working on AGI without being considered weird by the traditional AI community.
• Autonomous Bidding Agents: If you want people to bid their true values in an auction, use a sealed-bid second-price auction (similar to eBay’s system). The Trading Agent Competition is a useful testbed if you like game theory and view AI as a tool for automated trading and scheduling.
• Constraint-Based Local Search in Comet: If you want to solve constraint satisfaction problems (e.g. a Sudoku), don’t want to spend much time programming and like nice visualizations, use Comet.
• Practical Statisticial Relational AI: We may finally be able to unify logical inference, inductive logic programming, probabilistic inference, and statistical learning using Markov logic networks. Alchemy is supposed to fulfill Prolog’s promises (and it looks like it could).

Talks I heard

• Agents, Bodies, Constraints, Dynamics and Evolution: Robot soccer is a great challenge. We can’t completely avoid ethical choices (but please, don’t think ahead too far, let’s start with Asimov). Robot architectures need to provide an easy way to model constraints on the agent’s actions.
• Graph Identification and Alignment: Nice algorithms for entity resolution, link prediction, and collective classification exist that make it possible to extract useful information from noisy input data, e.g. social relations from a bunch of e-mails.
• AI in a Moore’s Law World: The Stories of Farecast and KnowItAll: The story of Farecast: You can make lots of money using data mining. The story of KnowItAll: It would be awesome if web search engines understood web pages and answered questions instead of just doing keyword searches, but we’re really not there yet and we need much more computing power for more sophisticated approaches.
• Representing and Reasoning about Preferences: You can force people to vote truthfully instead of opportunistically by making manipulation a NP-hard problem.
• Big “A”, Small “I”: Smart Ends from Simple Means: If you are designing a game, don’t compute things the player never gets to see, think about whether sophisticated planning really is better than just-the-next-step computation and remember that Matt Brown likes to do things in a very non-rocket-science kind of way.

Technical sessions

• Deriving a Large-Scale Taxonomy from Wikipedia: Wikipedia’s categories make for a useful network of concepts and, with a little effort, are just as good as the current largest taxonomies, WordNet and ResearchCyc.
• A New Algorithm for Generating Equilibria in Massive Zero-Sum Games: The range of skill in a game, i.e. how many different skill levels exist, is a reasonable measure of the complexity of a game. There is an iterative algorithm for computing approximate equilibrium strategies by fixing the opponent’s set of strategies but I don’t remember how it works.
• Reasoning Patterns of Agents: We can think of five basic reasoning patterns agents use in games — direct effect, influence for no reason, manipulation, signaling and revealing/denying — and these can be used to talk about actions in a more fine-grained way than just saying that an agent maximizes expected utility.
• On the prospects of building a Working Model of the Visual Cortex: More computing power is good and Jeff Hawkins approach may not be totally off, but we don’t want to mention his name.
• Modeling Crowd Behavior using Social Comparison Theory: People act similar to those who are like themselves but not too much like themselves. Simulate this and what you get is fairly convincing crowd behavior.
• Retaliate: Learning Winning Policies in First-Person Shooter Games: Really simple reinforcement learning produces good team strategies for Unreal Tournament’s domination mode.
• Analyzing Reading Behavior by Blog Mining: People who write comments on your blog tend to be regular readers. People who visit your blog are likely to visit similar blogs, too. If you don’t believe this, remember that we can still mention preferential attachment in our paper and thus have a few formulae that make the obvious much more convincing.

(Not quite) random remarks

• Man vs. Machine Poker Tournament: Poker players are lots of fun. This is the last year the human players won, but it is still not clear whether the bot that wins next year will be a boring equilibrium player or a learning bot that exploits its opponent’s weaknesses.
• The outside view of “traditional” AI research is right. I got the impression that most people are happy working on smallish problems. Let’s improve an existing optimization algorithm here and think about a new heuristic there, but don’t even mention general intelligence. That’s science fiction.
• And wrong. Whatever you do, be it natural language processing or robotics, the signs are there that quick hacks won’t get you anywhere near intelligent behavior, that the combination of faster hardware and new neuroscience provides an upper bound for the advent of silicon intelligence and that there are ethical and societal issues that need to be taken care of.
• Times change. On the way back from the conference, an uncle of mine who lives in Vancouver told me about his youth. Most of the time progress feels slow and boring. When you just return from a place where 200 people think about how to make the international network of computers reply to questions in an intelligent way and someone tells you about how he started out as a kind of millwright 50 years ago, that’s not the case.

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.

Ich bin Determinist und jede Sekunde entscheide ich mich zwischen unzähligen Handlungen. Mit der Einsicht, dass Lazy Reason nicht alltagstauglich ist, bleibt nur nicht fassbare Freiheit.

The infinite possibilities each day holds should stagger the mind. The sheer number of experiences I could have is uncountable, breathtaking. And I’m sitting here refreshing my inbox. We live trapped in loops. reliving a few days over and over, and we envision only a handful of paths laid out ahead of us. We see the same things each day, we respond the same way, we think the same thoughts, each day a slight variation on the last, every moment smoothly following the gentle curves of societal norms. We act like if we just get through today, tomororrow our dreams will come back to us. — xkcd

In einer Welt, die ohne vorgegebenen Sinn einfach existiert, erfinden wir uns und das, was wir als sinnvoll ansehen, auf dem Weg in die Zukunft. Jegliche Gründe, Ziele und Zwecke jenseits der biologischen erschaffen wir selbst. Aus “Wie soll ich handeln?” wird “Wer will ich sein?” und “In welcher Welt will ich leben?”.

Mit jeder Handlung machen wir aus dem aktuellen Zustand unserer Welt einen anderen. Der Raum aller möglichen Zustände ist die Menge der Zustände, die keine physikalischen Gesetze verletzen. Denkbar ist eine astronomische Zahl, wünschenswert sind die wenigsten davon. Die Menge der Zustände, die bewusstes Leben enthalten, macht nur eine winzige Ecke im Raum aller möglichen Zustände aus. Unsere Welt ist ein Punkt irgendwo in dieser Ecke.

Manche Zustände unterscheiden sich stärker voneinander als andere. Der Zustand der Welt, in der die Tasse Tee neben mir zwei Zentimeter weiter links steht, liegt näher am aktuellen als der, in dem sich die Tasse in einen feuerspeienden Drachen verwandelt hat. Ein mögliches Maß für den Abstand von zwei Zuständen wäre eine Art Informationsdistanz: Die Länge oder Laufzeit des kürzesten Algorithmus, der aus einer vollständigen Beschreibung von Zustand A die entsprechende Beschreibung von Zustand B berechnet.

Indem ich mich für eine Handlung entscheide, wähle ich einen unserer Nachbarn im im Raum aller möglichen Zustände. Wie sieht die Teilmenge der Zustände aus, die vom jetzigen Zustand der Welt aus durch mein Handeln oder Nicht-Handeln erreicht werden können? Das bestimmt, welchen Einfluss ich mit meinen Entscheidungen als einzelner auf die Welt habe.

Die Frage, was festlegt, welche Zustände ich erreichen kann und welche nicht, führt unmittelbar zu der Frage danach, was unsere Position im Raum aller möglichen Zustände bis jetzt am stärksten verändert hat. Die Antwort definiert, was Optimierungsprozesse sind: Systeme, die den Zustand unserer Welt auf einen kleinen Zielraum mit bestimmten Eigenschaften hin bewegen.

• Evolution ist ein Optimierungsprozess, der Replikatoren — Bakterien, Tiere, Menschen und die Gene dahinter — durch Mutation, Rekombination und Selektion auf effektivere Vermehrung hin optimiert.
• Ein Schachcomputer ist ein Optimierungsprozess, der aus der Vielzahl möglicher Kombinationen von Schachzügen die auswählt, die die Position der Figuren auf einem Schachbrett so verändern, dass sich die Welt in einen Zielraum mit der Eigenschaft “Der Schachcomputer gewinnt.” bewegt.
• Menschliche Intelligenz ist ein mächtiger Optimierungsprozess, der für verschiedenste Ziele eingesetzt werden kann. Rationalität erreicht klar definierte Ziele, nonlineares Handeln die unbewussten.

Cognitive Science ist die Lehre von den Optimierungsprozessen. In Psychologie und Neurobiologie wird der effektivste bekannte Optimierungsprozess, das menschliche Gehirn, analysiert, in Mathe, Informatik, Statistik und Logik werden die methodische Grundlagen für den Bau von künstlichen Optimierungsprozessen unterrichtet.

Optimierung ist ein Vorhersageproblem. Jeder Maschine steht eine festgelegte Menge an Aktionen zur Verfügung. Um ein Ziel zu erreichen, muss die Maschine vorhersagen, welche Kombination aus Aktionen die Welt dem Zielzustand am nächsten bringt. Dass wir Menschen die Auswirkungen unserer Handlungen vorhersagen können, zeigt, dass Quanten- und Chaoseffekte bei Vorhersagen umgangen werden können, wenn man Abstriche bei der Genauigkeit der Prognosen macht.

Intelligenz ist die Fähigkeit, akkurate Vorhersagen zu treffen um Aktionsfolgen zu finden, die unsere Zukunft auf kleine, weit entfernte Regionen im Raum des Möglichen hinsteuern. Die Frage, ob künstliche Intelligenz möglich ist, lautet eigentlich: “Wie weit werden wir uns übertreffen? Wo liegen die Grenzen der Berechenbarkeit?”

Weil die Grenzen, denen wir unterliegen, universell sind, sehen wir sie nicht. Algorithmen, die Information optimal extrahieren, unterliegen keinen kognitiven Fehlern. Die unvoreingenommene Instrumentalisierung aller verfügbaren Mittel stellt einen enormen Machtzuwachs dar; als Menschen schaffen wir es oft nicht, funktionaler Fixiertheit zu entrinnen, sobald wir einmal gelernt haben, wozu etwas gut ist.

Im nächsten und letzten Schritt, der genauso unvermeidbar und unintuitiv ist wie die davor, schreiben wir Optimierungsprozesse, die den Teil ihrer selbst restrukturieren, der für das Optimieren zuständig ist. Algorithmen, die vorhersagen, welche Veränderungen es braucht, um bessere Vorhersagen zu treffen. Prozesse, die Welt auf Zielregionen hin bewegen, von denen wir nicht gedacht hätten, dass sie in unserer unmittelbaren Nachbarschaft liegen.

For a long time, two types of entities shared our world. On the one hand, there were entities that had intentionality and that behaved in a way that lead us to conclude that they did, namely human beings. On the other hand, there were entities like cars and rocks that clearly did not have intentionality and that did not show behavior that could have lead us to conclude that they do. Soon there may be a third type of entities: Robots that show behavior similar to the behavior of human beings and that do neither clearly possess intentionality nor clearly not possess intentionality.

It is amazing that, after almost 30 years of philosophical discussions, John Searle’s argument against the possibility of programming a robot in a way that makes it really think is still alive. I am now going to analyze what it means for an entity to have intentionality, then give a short account of the strongest version of Searle’s thought experiment and finally argue that the only way to deny intentionality to robots on the grounds of Searle’s thought experiment is to assume a priori that intentionality is tied to biochemical processes. Weiterlesen »

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?