Optimale Vorhersagen
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.
Artikel
Zunächst ein bisschen Definition. Ohne mir Solomonoffs Theorie durchgelesen zu haben [1], wie funktionieren Vorhersagemethoden? Sie approximieren aus dem Zustand der in diesem Augenblick gültigen Faktoren einen Folgezustand, der zu einer bestimmten Zeit in der Zukunft existiert.
Was wäre dann eine optimale Vorhersagemethode ohne Berücksichtigung eventueller Ressourcenknappheiten? Eine Methode, die aus allen möglichen Faktoren den exakten Folgezustand errechnet.
Eine optimale Vorhersagemethode unter Berücksichtigung der Ressource Speicherplatz würde nur die Faktoren mit dem größten Einfluss auf den Folgezustand berücksichtigen und daraus eine (im Durchschnitt) möglichst genaue Vorhersage errechnen.
Eine optimalste Vorhersagemethode unter Berücksichtigung der Ressourcen Speicherplatz und Zeit würde in gegebener Zeit möglichst die Faktoren mit großem Einfluss auf den Folgezustand finden und daraus eine möglichst genaue Vorhersage berechnen.
Letzteres trifft vermutlich am besten die Realität, da wir es mit Platz- und Zeitproblemen zu tun haben. Durch die Ressource Zeit wird das Problem auch erst richtig kompliziert. Wieviel der vorhandenen Zeit verwende ich für die Findung der für die Vorhersage wichtigen Faktoren und wieviel Zeit verwende ich auf die Vorhersage selbst? Wenn wir die Antwort auf diese Frage errechnen wollen, müssen wir weitere Rechenzeit investieren. Doch wieviel? Wir könnten es wieder errechnen. Wiederum lautet die Frage, wieviel Zeit darf ich maximal für die Errechnung der maximalen Zeit für die Errechnung der wichtigen Faktoren verwenden? Diese Reihe ließe sich unendlich fortsetzen.
Erst wenn man dieses Problem gelöst hat, könnte man sich um die eigentliche Vorhersage kümmern.
Die Evolution hat das Gehirn anders geformt. Wir besitzen fest installierte Filter, die die für uns wichtigen Informationen schnell herausfiltern und alles andere vernachlässigen. Dabei ist vor allem die Schnelligkeit bis man zu einer Vorhersage kommt ein Selektionsvorteil gegenüber der Exaktheit des Ergebnisses gewesen.
Ich bin skeptisch, ob ein theoretisches Konstrukt wie das einer universellen Induktion zu effizienten und praktikablen Lösungen führen wird, lasse mich aber auch gerne von etwas anderem überzeugen.
[1] Habe gerade keinen PDF-Reader zur Hand. Werde ich nachholen, wenn ich wieder zu Hause bin.
Eine optimale Vorhersagemethode muss nicht den exakten Folgezustand errechnen. Tatsächlich kann das keine Methode: Induktion erlaubt niemals Vorhersagen mit der Wahrscheinlichkeit 1.
Wenn wir zwei Vorhersagemethoden vergleichen, wird trotzdem eine im Durchschnitt besser abschneiden als die andere. Für die Bezeichnung “optimal” genügt, dass eine Methode bei gleicher Information exakter ist als jede andere Methode.
Muss man diese beiden Rechenschritte trennen? Kann man das überhaupt, wenn man einen Vorhersagealgorithmus finden will, der für eine möglichst große Menge an Umgebungen optimal ist — also abgesehen von der Annahme, dass die Umgebung berechenbar ist, keine (oder kaum) weitere Annahmen macht?
Wer an Faktoren und an die Aufteilung der Zeit zwischen der Suche nach Faktoren und der eigentlichen Prognose denkt, hat sich bereits auf einen konkreten und vermutlich nicht optimalem Ansatz für das Vorhersageproblem festgelegt.
Eine andere Sichtweise: Jedes Vorhersageproblem lässt sich auf die Form der Vorhersage binärer Sequenzen bringen.
011011100101110111100010 ... ?Wir wissen nicht, durch welches Programm sich diese Sequenz — und damit der nächste Datenpunkt in dieser Sequenz — berechnen lässt. Jedes Programm, das diese Sequenz ausgibt, ist eine unserer Hypothesen. Ockham’s Rasiermesser besagt, dass von mehreren Hypothesen, die den gleichen Sachverhalt erklären, die einfachste zu bevorzugen ist.
Programme sind dann einfacher, wenn sie eine niedrigere algorithmische Komplexität haben. Ein Programm x ist umso einfacher, je kürzer das kürzeste Programm ist, das dieselbe Ausgabe besitzt wie x. Die Lösung des Vorhersageproblems besteht grob gesagt darin, das kürzeste Programm zu finden, das diese Sequenz generiert.
Dass unser Gehirn nicht nur die Informationen besitzt, die wir im Laufe unseres Lebens aufnehmen, sondern aufgrund Millionen von Jahren Evolution auch über einige Dispositionen a priori verfügt, die für das Verständnis der Welt Voraussetzung sein könnten, ist ein wichtiger Punkt. Ein theoretisch optimaler Algorithmus ist vielleicht nur dann brauchbar, wenn er zusätzliche Annahmen über die Umgebung macht.
Zuletzt bearbeitet am 7. März 2007, 21:31 Uhr.
Sieht so aus als sei ich hier auf einen Idsia-fan gestossen :o)
Leider hab ich eine schlechte Nachicht: es kann keinen beweisbar optimalen Vorhersagealgorithmus geben, jedenfalls nicht sobald die Vorhersagen von einer gewissen Kolmogorov-Komplexitaet sind (der Beweis hierfuer ist neu, und kommt von Shane: http://www.idsia.ch/~shane/).
Deswegen die Einschränkung “wozu auch die algorithmische Komplexität zählen kann”. Dass ich damit die Komplexität der vorherzusagenden Sequenz und nicht die des Vorhersagealgorithmus gemeint habe, war undeutlich. Ich habe bis jetzt noch keine feste Meinung zur praktischen Relevanz der Ergebnisse von Shane Legg. Hätte aber gerne eine — das Thema (und vieles von dem, was bei Idsia gemacht wird) ist spannend.
Shane Legg beweist doch, dass es keinen Vorhersagealgorithmus der Kolmogorov-Komplexität k gibt, der lernen kann, alle Sequenzen mit einer Komplexität von ungefähr k vorherzusagen, auch nicht probabilistisch (weil sich dann aus dem Algorithmus leicht eine Sequenz konstruieren ließe, für die der Algorithmus fehlschlägt).
Er beweist desweiteren, dass ab einer bestimmten Komplexität k des Vorhersagealgorithmus nicht mehr bewiesen werden kann, dass der Algorithmus zu der Menge der Vorhersagealgorithmen gehört, die lernen können, alle Sequenzen mit höchstens Komplexität k vorherzusagen.
Ist denn damit schon gezeigt, dass es keinen Vorhersagealgorithmus geben kann, der beweisbar mehr Sequenzen (oder mehr Sequenzen mit höchstens einer bestimmten Komplexität) lernen kann als jeder andere Algorithmus gleicher Komplexität? Oder, schwächer: Als jeder andere Algorithmus gleicher Komplexität, von dem bewiesen werden kann, welche Menge an Sequenzen er lernen kann?
Zuletzt bearbeitet am 18.3.2007, 00:10 Uhr.
[…] optimaler Vorhersagealgorithmus muss alle möglichen Einflussfaktoren kennen, deren tatsächlichen Einfluss beurteilen, […]
Hi,
ich will mich hier gar nicht in die Diskussion einmischen (das könnte ich auch gar nicht ;)
Ich lese gerade die Einstein-Biografie von Jürgen Neffe- so ganz intuitiv denke ich, dass der menschliche Geist in der Lage ist, ziemlich überraschende und auch gar nicht nur auf Messungen beruhende Aussagen zu machen, die dann erstaunlich weit reichende Folgen haben. Einstein hat seine Relativitätstheorie mit Papier und Bleistift gefunden. (Er war ja theoretische Physiker.) Natürlich wusste er von der Arbeit der Experimentalphysiker seiner Zeit, aber trotzdem hat seine Theorie, größtenteils entstanden aus Gedankenexperimenten, Vorhersagen möglich gemacht, an denen die Experimentalphysik immer noch zu knappsen hat, z.B. steht die Messung von Gravitationswellen noch aus.
Das finde ich ziemlich krass :)
Wieso ist der menschliche Geist dazu überhaupt in der Lage? Haben wir mehr evolutionäres a priori-Wissen, als ich so spontan denke? Warum scheint unsere Welt so einem Prinzip wie “Schönheit” zu folgen? (Auch wenn mancher die Quantenphysik nicht als “schön” bezeichnen mag, inklusive Einstein, auch wenn sie ja sicher richtig ist.)
Meine Frage also ist: Wieso können Menschen Kraft ihres Kopfes so sehr tiefgreifende, vorhersagekräftigen Theorien aufstellen, ohne rekursiv oder wie auch immer sich Messungen annähernd zu arbeiten? Wieso spielt so viel “Philosophie” mit? OK, ist evtl. etwas abseits des Themas, aber egal ;)
Anderes, einfacheres Problem: Berechne aus einer ungeordneten Liste von Werten das Maximum. Wie kannst du dir jemals sicher sein, das Maximum gefunden zu haben, bevor du dir nicht alle Werte angeschaut hast?
So essentiell wie die Betrachtung der Werte für das Auffinden eines Maximums ist, ist es auch der aktuelle Zustand für eine Prognose. Doch unter Zeitdruck (d.h. unter Berücksichtung der Ressource Zeit) wirst du dir nicht alle Werte anschauen können. Schon gar nicht, wenn es nahezu unendlich viele gibt. Daher wirst du eine Entscheidungsregel brauchen, die entscheidet, welche Werte in die Berechnung mit einbezogen werden und welche nicht - genauso wie du gezwungen bist, dich bei einem aktuellen Zustand auf bestimmte Teilbereiche (Faktoren) zu konzentrieren.
Dann lässt du also nur Hypothesen zu, die EXAKT diese Sequenz ausgeben? Wenn dies der Fall ist und nur solche Hypothesen als optimal zu bezeichnen sind, dann wage ich zu behaupten, dass sie in der Praxis keinerlei Relevanz haben, denn die Realität lässt sich nicht zu 100% vorhersagen.
Schöne Grüße,
Lucas
An Benedict:
Weil intelligentes Leben nur in Welten entstehen kann, die genügend Regelmäßigkeit aufweisen, so dass zuverlässige Vorhersagen über die Umgebung möglich sind, und genügend Komplexität, so dass Konstrukte wie das menschliche Gehirn evolutionär entstehen können.
Beim Blick auf den Wikipedia-Artikel zum Thema Schönheit ist mir folgender Absatz aufgefallen: “Jürgen Schmidhubers komplexitätsbasierte Theorie der Schönheit sieht daher das subjektiv schönste Muster aus einer Reihe vergleichbarer Muster als dasjenige mit der kürzesten Beschreibung in der Musterkodiersprache des subjektiven Beobachters.” — Jep, das ist der Schmidhuber.
Weil manche Menschen einen sehr effektiven Ansatz entwickelt haben, um möglichst kurze Beschreibungen komplexer Phänomene zu finden. Sehr kurze Beschreibungen zu finden ist nicht umsonst ein KI-vollständiges Problem.
An Lucas:
Mich kümmert, wie ein Algorithmus aussieht, der für eine Menge an Datenpunkten jeden Datenpunkt betrachtet und jeden “in die Rechnung miteinbezieht”. Deine Entscheidungsregel, die besagt, welcher Wert in die Rechnung miteinbezogen wird, entspricht einem gewichtenden “in die Rechnung miteinbeziehen”.
Wie bestimmt wird, wie die Menge an Datenpunkten aussehen soll, mag Grund zu der Annahme sein, dass Physiker und Astronomen demnächst nicht völlig arbeitslos werden, ist aber für mich irrelevant. (Okay, nicht völlig irrelevant. Ein optimaler Algorithmus, wie er von mir beschrieben wurde, kann auch zur Optimierung der einzubeziehenden Daten verwendet werden.)
Was ich oben geschrieben habe, gilt auch für probabilistische Vorhersagealgorithmen. Wie ein optimaler Algorithmus aussieht, hängt dann von der Gewichtung der Exaktheit der Übereinstimmung mit der Sequenz einerseits und der Kürze des Algorithmus andererseits ab. Je fehlerfreier die vorhandenen Daten, desto stärker muss die Exaktheit der Übereinstimmung gewichtet werden.
Dass eine exakte Vorhersage des nächsten Zustands unmöglich ist, ist klar.
An Andreas:
“Weil intelligentes Leben nur in Welten entstehen kann, die genügend Regelmäßigkeit aufweisen, so dass zuverlässige Vorhersagen über die Umgebung möglich sind, und genügend Komplexität, so dass Konstrukte wie das menschliche Gehirn evolutionär entstehen können.”
Mhm… das klingt so, als würde irgendetwas wie “Intelligenz” auch unabhängig von der Welt existieren. (Du meinst mit “Welt” doch die Gesetzmäßigkeiten unseres Universums, und nicht “die Erde”, oder?)
Ich würde spontan sagen, dass Intelligenz doch den Gesetzen unserer Welt folgt. Also ist Intelligenz immer abhängig von der Welt in der sie entsteht. Und dann ist auch klar, dass die Welt schön ist, wenn der Betrachter, der sie als schön betrachtet, ihr entspringt. Und das wäre dann sogar unabhängig davon, wie die Welt gebaut ist, solange ein bewusster Beobachter entsteht. Ok, ist aber alles Spekulatius.