Ray Solomonoff

Ray Solomonoff (25. Juli 1926 – 7. Dezember 2009) ^{[ 1 ] [ 2 ]} war ein US-amerikanischer Mathematiker, der die algorithmische Wahrscheinlichkeitstheorie ^{[ 3 ]} und seine Allgemeine Theorie des induktiven Schließens (auch bekannt als Universelles Induktives Schließen) ^{[ 4 ]} entwickelte und zu den Begründern der algorithmischen Informationstheorie zählte . ^{[ 5 ]} Er gilt als einer der Wegbereiter des Zweigs der künstlichen Intelligenz, der auf maschinellem Lernen , Vorhersage und Wahrscheinlichkeitstheorie basiert . Seinen ersten Bericht über nicht-semantisches maschinelles Lernen veröffentlichte er 1956. ^{[ 6 ]}

Solomonoff beschrieb die algorithmische Wahrscheinlichkeit erstmals 1960 und veröffentlichte den Satz, der die Kolmogorov-Komplexität und die algorithmische Informationstheorie begründete . Er stellte diese Ergebnisse erstmals 1960 auf einer Konferenz am Caltech ^{[ 7 ]} und in einem Bericht vom Februar 1960 mit dem Titel „A Preliminary Report on a General Theory of Inductive Inference“ ^{[ 8 ] vor. In seinen 1964 erschienenen Publikationen „A Formal Theory of Inductive Inference“, Teil I [ 9 ]} und Teil II ^{[ 10 ]} , erläuterte er diese Ideen ausführlicher.

Die algorithmische Wahrscheinlichkeit ist eine mathematisch formalisierte Kombination aus Ockhams Rasiermesser [ ^{11 ] [ 12 ] [ 13 ] [ 14 ] und} dem Prinzip der multiplen Erklärungen ^{[ 15 ]} . Sie ist eine maschinenunabhängige Methode, um jeder Hypothese (jedem Algorithmus/Programm), die eine gegebene Beobachtung erklärt, einen Wahrscheinlichkeitswert zuzuordnen. Dabei erhält die einfachste Hypothese (das kürzeste Programm) die höchste Wahrscheinlichkeit, während die Wahrscheinlichkeiten für zunehmend komplexere Hypothesen abnehmen.

Solomonoff begründete die Theorie des universellen induktiven Schließens , die auf soliden philosophischen Grundlagen basiert ^{[ 4 ]} und ihre Wurzeln in der Kolmogorov-Komplexität und der algorithmischen Informationstheorie hat . Die Theorie verwendet algorithmische Wahrscheinlichkeit in einem Bayes'schen Rahmen. Die universelle A-priori-Wahrscheinlichkeit wird über die Klasse aller berechenbaren Maße gebildet; keine Hypothese hat die Wahrscheinlichkeit Null. Dies ermöglicht es, das Bayes'sche Kausalitätsprinzip anzuwenden, um das wahrscheinlichste nächste Ereignis in einer Ereigniskette und dessen Wahrscheinlichkeit vorherzusagen. ^{[ 10 ]}

Obwohl er vor allem für seine algorithmische Wahrscheinlichkeitstheorie und seine allgemeine Theorie des induktiven Schließens bekannt ist , machte er im Laufe seines Lebens viele weitere wichtige Entdeckungen, die meisten davon auf sein Ziel in der künstlichen Intelligenz ausgerichtet: die Entwicklung einer Maschine, die schwierige Probleme mithilfe probabilistischer Methoden lösen kann.

Ray Solomonoff wurde am 25. Juli 1926 in Cleveland, Ohio , als Sohn jüdisch- russischer Einwanderer, Phillip Julius und Sarah Mashman Solomonoff, geboren. Er besuchte die Glenville High School und schloss sie 1944 ab. Im selben Jahr trat er als Ausbilder für Elektronik in die US-Marine ein . Von 1947 bis 1951 studierte er an der Universität von Chicago unter Professoren wie Rudolf Carnap und Enrico Fermi und erwarb dort 1951 einen Master of Science in Physik.

Schon in seiner frühesten Kindheit war er von der reinen Freude an mathematischen Entdeckungen und dem Wunsch angetrieben, Neuland zu betreten ^{[ 16 ]} . Im Alter von 16 Jahren, im Jahr 1942, begann er mit der Suche nach einer allgemeinen Methode zur Lösung mathematischer Probleme.

1952 lernte er Marvin Minsky , John McCarthy und andere an künstlicher Intelligenz Interessierte kennen. 1956 organisierten Minsky, McCarthy und weitere Forscher die Dartmouth Summer Research Conference on Artificial Intelligence , zu der Solomonoff als einer der zehn ersten Teilnehmer eingeladen war – er, McCarthy und Minsky waren die einzigen, die den gesamten Sommer blieben. Dank dieser Gruppe wurde Künstliche Intelligenz erstmals als eigenständige Wissenschaft anerkannt. Computer konnten damals zwar sehr spezifische mathematische Probleme lösen, aber kaum etwas anderes. Solomonoff wollte einer umfassenderen Frage nachgehen: Wie lassen sich Maschinen allgemein intelligenter machen und wie können Computer Wahrscheinlichkeitsrechnung zu diesem Zweck nutzen?

Er verfasste drei Arbeiten, zwei davon zusammen mit Anatol Rapoport , in den Jahren 1950–52, ^{[ 17 ]} die als früheste statistische Analyse von Netzwerken gelten.

Er war einer der zehn Teilnehmer des Dartmouth Summer Research Project on Artificial Intelligence im Jahr 1956. Er verfasste und verteilte einen Bericht unter den Teilnehmern: „Eine induktive Inferenzmaschine“ ^{[ 6 ]} . Darin betrachtete er maschinelles Lernen als probabilistisch und betonte die Bedeutung von Trainingssequenzen sowie die Verwendung von Teilen vorheriger Problemlösungen zur Konstruktion von Testlösungen für neue Probleme. Eine Version seiner Ergebnisse veröffentlichte er 1957 ^{[ 18 ].} Dies waren die ersten Arbeiten zum probabilistischen maschinellen Lernen.

Ende der 1950er Jahre erfand er probabilistische Sprachen und die dazugehörigen Grammatiken. ^{[ 19 ]} Eine probabilistische Sprache ordnet jeder möglichen Zeichenkette einen Wahrscheinlichkeitswert zu.

Die Verallgemeinerung des Konzepts der probabilistischen Grammatiken führte ihn 1960 zu seiner Entdeckung der algorithmischen Wahrscheinlichkeit und der allgemeinen Theorie des induktiven Schließens.

Vor den 1960er Jahren basierte die übliche Methode zur Wahrscheinlichkeitsberechnung auf der Häufigkeit: dem Verhältnis der günstigen Ergebnisse zur Gesamtzahl der Versuche. In seiner Publikation von 1960 und insbesondere in seinen Veröffentlichungen von 1964 überarbeitete Solomonoff diese Definition von Wahrscheinlichkeit grundlegend. Er nannte diese neue Form der Wahrscheinlichkeit „algorithmische Wahrscheinlichkeit“ und zeigte, wie sie sich in seiner Theorie des induktiven Schließens zur Vorhersage nutzen lässt. Im Rahmen dieser Arbeit legte er die philosophische Grundlage für die Anwendung des Bayes-Kausalitätsprinzips zur Vorhersage.

Der grundlegende Satz der später als Kolmogorov-Komplexität bezeichneten Theorie war Teil seiner Allgemeinen Theorie. In seinen 1960 veröffentlichten Arbeiten beginnt er: „Betrachten wir eine sehr lange Symbolfolge … Wir betrachten eine solche Symbolfolge als ‚einfach‘ und mit einer hohen Wahrscheinlichkeit a priori, wenn es eine sehr kurze Beschreibung dieser Folge gibt – natürlich unter Verwendung einer festgelegten Beschreibungsmethode. Genauer gesagt: Verwenden wir zur Beschreibung nur die Symbole 0 und 1, so ordnen wir einer Symbolfolge die Wahrscheinlichkeit 2 ^{− N} zu, wenn ihre kürzestmögliche Binärdarstellung N Ziffern enthält.“ ^{[ 20 ]}

Die Wahrscheinlichkeit bezieht sich auf eine bestimmte universelle Turingmaschine . Solomonoff zeigte und bewies 1964, dass die Wahl der Maschine zwar einen konstanten Faktor hinzufügen könnte, die Wahrscheinlichkeitsverhältnisse aber nicht wesentlich verändert. Diese Wahrscheinlichkeiten sind maschinenunabhängig.

1965 veröffentlichte der russische Mathematiker Kolmogorow unabhängig ähnliche Ideen. Als er von Solomonows Arbeit erfuhr, würdigte er ihn, und Solomonows Werk war mehrere Jahre lang in der Sowjetunion bekannter als in der westlichen Welt. In der wissenschaftlichen Gemeinschaft herrschte jedoch weitgehend Einigkeit darüber, diese Art von Komplexität mit Kolmogorow in Verbindung zu bringen, der sich mehr mit der Zufälligkeit einer Folge befasste. Algorithmische Wahrscheinlichkeit und die universelle (Solomonow-)Induktion wurden mit Solomonow assoziiert, der sich auf Vorhersagen – die Extrapolation einer Folge – konzentrierte.

Später in derselben Publikation von 1960 beschreibt Solomonoff seine Erweiterung der Theorie des kürzesten Einzelcodes. Dies ist die algorithmische Wahrscheinlichkeitstheorie. Er erklärt: „Wenn es mehrere verschiedene Methoden zur Beschreibung einer Sequenz gibt, sollte jeder dieser Methoden ein Gewicht bei der Bestimmung der Wahrscheinlichkeit dieser Sequenz zugewiesen werden.“ ^{[ 21 ]} Anschließend zeigt er, wie diese Idee genutzt werden kann, um die universelle A-priori-Wahrscheinlichkeitsverteilung zu generieren und wie sie die Anwendung des Bayes-Theorems in der induktiven Inferenz ermöglicht. Die induktive Inferenz, die die Vorhersagen aller Modelle, welche eine bestimmte Sequenz beschreiben, unter Verwendung geeigneter, auf der Länge dieser Modelle basierender Gewichte addiert, liefert die Wahrscheinlichkeitsverteilung für die Fortsetzung dieser Sequenz. Diese Vorhersagemethode ist seither als Solomonoff-Induktion bekannt .

Er erweiterte seine Theorie und veröffentlichte eine Reihe von Berichten, die zu den Veröffentlichungen im Jahr 1964 führten. Die Arbeiten von 1964 geben eine detailliertere Beschreibung der algorithmischen Wahrscheinlichkeit und der Solomonoff-Induktion und stellen fünf verschiedene Modelle vor, darunter das Modell, das im Volksmund als die universelle Verteilung bezeichnet wird.

Andere Wissenschaftler, die an der Dartmouth-Sommerkonferenz 1956 teilgenommen hatten (wie Newell und Simon ), entwickelten den Zweig der Künstlichen Intelligenz, der auf faktenbasierten Maschinen basierte, die durch Wenn-Dann-Regeln gesteuert wurden. Solomonoff hingegen konzentrierte sich auf Wahrscheinlichkeit und Vorhersage; seine KI-Vision beschrieb Maschinen, die der algorithmischen Wahrscheinlichkeitsverteilung folgten. Die Maschine generiert Theorien mit den zugehörigen Wahrscheinlichkeiten, um Probleme zu lösen, und aktualisiert die Wahrscheinlichkeitsverteilung der Theorien, sobald neue Probleme und Theorien entstehen.

1968 fand er einen Beweis für die Wirksamkeit der algorithmischen Wahrscheinlichkeitstheorie ^{[ 22 ]} , veröffentlichte ihn aber hauptsächlich aufgrund mangelnden allgemeinen Interesses erst zehn Jahre später. In seinem Bericht veröffentlichte er den Beweis für den Konvergenzsatz.

In den Jahren nach seiner Entdeckung der algorithmischen Wahrscheinlichkeit konzentrierte er sich darauf, wie man diese Wahrscheinlichkeit und die Solomonoff-Induktion für tatsächliche Vorhersagen und Problemlösungen für KI nutzen kann. Er wollte auch die tieferen Implikationen dieses Wahrscheinlichkeitssystems verstehen.

Ein wichtiger Aspekt der algorithmischen Wahrscheinlichkeit ist, dass sie vollständig und unberechenbar ist.

In seinem Bericht von 1968 zeigt er, dass die algorithmische Wahrscheinlichkeitstheorie vollständig ist ; das heißt, wenn in einem Datensatz eine beschreibbare Regelmäßigkeit existiert, wird sie diese schließlich mit einer relativ kleinen Stichprobe der Daten entdecken. Die algorithmische Wahrscheinlichkeitstheorie ist das einzige bekannte Wahrscheinlichkeitssystem, das in diesem Sinne vollständig ist. Als notwendige Folge ihrer Vollständigkeit ist sie nicht berechenbar . Die Nichtberechenbarkeit ergibt sich daraus, dass einige Algorithmen – eine Teilmenge der partiell rekursiven Algorithmen – aufgrund der zu langen Berechnungszeit nie vollständig ausgewertet werden können. Diese Programme werden aber zumindest als mögliche Lösungen erkannt. Andererseits ist jedes berechenbare System unvollständig . Es wird immer Beschreibungen außerhalb des Suchraums dieses Systems geben, die selbst bei unendlich langer Berechnungszeit nie erkannt oder berücksichtigt werden. Berechenbare Vorhersagemodelle verschleiern diese Tatsache, indem sie solche Algorithmen ignorieren.

In vielen seiner Veröffentlichungen beschrieb er, wie man nach Lösungen für Probleme sucht, und in den 1970er und frühen 1980er Jahren entwickelte er das, was seiner Meinung nach der beste Weg war, die Maschine zu aktualisieren.

Die Anwendung von Wahrscheinlichkeitsrechnung in der KI verlief jedoch nicht reibungslos. In den Anfängen der KI war die Relevanz von Wahrscheinlichkeitsrechnung problematisch. Viele in der KI-Community hielten Wahrscheinlichkeitsrechnung für ihre Arbeit für unbrauchbar. Zwar nutzte die Mustererkennung eine Form der Wahrscheinlichkeitsrechnung, doch da es keine umfassende Theorie zur Integration von Wahrscheinlichkeitsrechnung in KI-Bereiche gab, verzichteten die meisten Bereiche gänzlich darauf.

Es gab jedoch Forscher wie Pearl und Peter Cheeseman, die argumentierten, dass Wahrscheinlichkeit in der künstlichen Intelligenz Anwendung finden könne.

Um 1984 wurde auf einer Jahrestagung der American Association for Artificial Intelligence (AAAI) beschlossen, dass Wahrscheinlichkeit in keiner Weise für KI relevant sei.

Es bildete sich eine Protestgruppe, und im darauffolgenden Jahr fand im Rahmen der AAAI-Tagung ein Workshop zum Thema „Wahrscheinlichkeit und Unsicherheit in der KI“ statt. Dieser jährliche Workshop wird bis heute fortgeführt. ^{[ 23 ]}

Als Teil des Protests beim ersten Workshop hielt Solomonoff einen Vortrag darüber, wie man die universelle Verteilung auf Probleme der KI anwenden kann ^{[ 24 ].} Dies war eine frühe Version des Systems, das er seitdem entwickelt hat.

In diesem Bericht beschrieb er die von ihm entwickelte Suchtechnik. Bei Suchproblemen ist die optimale Suchreihenfolge die Zeit , wobei die für den Test benötigte Zeit und die Erfolgswahrscheinlichkeit dieses Tests ist. Er nannte dies die „konzeptionelle Sprunggröße“ des Problems. Levins Suchtechnik nähert sich dieser Reihenfolge an ^{[ 25 ]} , und so nannte Solomonoff, der Levins Arbeit studiert hatte, diese Suchtechnik Lsearch. ${\displaystyle T_{i}/P_{i}}$${\displaystyle T_{i}}$${\displaystyle P_{i}}$

In weiteren Arbeiten untersuchte er, wie die Zeit für die Lösungssuche begrenzt werden kann, und schrieb über ressourcenbeschränkte Suche. Der Suchraum wird durch die verfügbare Zeit oder die Rechenkosten begrenzt, anstatt ihn – wie bei einigen anderen Vorhersagemethoden, z. B. der Methode der minimalen Beschreibungslänge – einzuschränken .

Solomonoff beschäftigte sich zeitlebens mit den potenziellen Vorteilen und Gefahren der KI und thematisierte dies in zahlreichen seiner Veröffentlichungen. 1985 analysierte er eine wahrscheinliche Entwicklung der KI und stellte eine Formel auf, die den Zeitpunkt des Erreichens des „Unendlichkeitspunktes“ vorhersagte. ^{[ 26 ]} Diese Arbeit ist Teil der Geschichte des Denkens über eine mögliche technologische Singularität .

Ursprünglich wurden algorithmische Induktionsmethoden zur Extrapolation geordneter Zeichenkettenfolgen verwendet. Es wurden Methoden benötigt, um mit anderen Datentypen umzugehen.

In einem Bericht aus dem Jahr 1999 ^{[ 27 ]} werden die universelle Verteilung und zugehörige Konvergenzsätze auf ungeordnete Mengen von Zeichenketten verallgemeinert, und in einem Bericht aus dem Jahr 2008 ^{[ 28 ]} werden sie auf ungeordnete Paare von Zeichenketten verallgemeinert.

In den Jahren 1997, ^{[ 29 ]} 2003 und 2006 zeigte er, dass Unberechenbarkeit und Subjektivität sowohl notwendige als auch wünschenswerte Eigenschaften eines jeden Hochleistungs-Induktionssystems sind.

1970 gründete er sein eigenes Ein-Mann-Unternehmen, Oxbridge Research, und setzte seine Forschung dort fort, abgesehen von Aufenthalten an anderen Institutionen wie dem MIT, der Universität des Saarlandes und dem Dalle Molle Institut für Künstliche Intelligenz in Lugano. 2003 erhielt er als Erster den Kolmogorov-Preis des Computer Learning Research Center (CLRC) am Royal Holloway, University of London , wo er auch die erste Kolmogorov-Vorlesung hielt. Zuletzt war Solomonoff Gastprofessor am CLRC.

Im Jahr 2006 sprach er auf der AI@50- Konferenz „Dartmouth Artificial Intelligence Conference: the Next Fifty Years“, die anlässlich des fünfzigjährigen Jubiläums der ursprünglichen Dartmouth-Sommerstudiengruppe stattfand. Solomonoff war einer der fünf ursprünglichen Teilnehmer.

Im Februar 2008 hielt er die Hauptrede auf der Konferenz „Aktuelle Trends in Theorie und Anwendung der Informatik“ (CTTACS) an der Notre Dame University im Libanon. Anschließend folgte eine kurze Vorlesungsreihe, und er begann mit der Forschung zu neuen Anwendungen der algorithmischen Wahrscheinlichkeitstheorie.

Algorithmische Wahrscheinlichkeit und Solomonoff-Induktion bieten viele Vorteile für Künstliche Intelligenz. Algorithmische Wahrscheinlichkeit liefert äußerst genaue Wahrscheinlichkeitsschätzungen. Diese Schätzungen können mit einer zuverlässigen Methode revidiert werden, sodass sie weiterhin akzeptabel bleiben. Sie nutzt die Suchzeit sehr effizient. Neben Wahrscheinlichkeitsschätzungen hat die algorithmische Wahrscheinlichkeit für KI einen weiteren wichtigen Wert: Ihre Modellvielfalt ermöglicht es uns, unsere Daten auf vielfältige Weise zu interpretieren.

Eine Beschreibung von Solomonoffs Leben und Werk vor 1997 findet sich in „The Discovery of Algorithmic Probability“, Journal of Computer and System Sciences, Band 55, Nr. 1, S. 73–88, August 1997. Der Artikel sowie die meisten anderen hier erwähnten Publikationen sind auf seiner Website auf der Publikationsseite verfügbar .

In einem Artikel, der im Jahr seines Todes veröffentlicht wurde, hieß es über Solomonoff: „Ein sehr konventioneller Wissenschaftler versteht seine Wissenschaft anhand eines einzigen ‚aktuellen Paradigmas‘ – der Erklärungsweise, die gerade am weitesten verbreitet ist. Ein kreativerer Wissenschaftler versteht seine Wissenschaft auf vielfältige Weise und kann leichter neue Theorien und neue Erklärungsansätze entwickeln, wenn das ‚aktuelle Paradigma‘ nicht mehr zu den aktuellen Daten passt.“ ^{[ 30 ]}

Im Jahr 2011 veröffentlichte er im Rahmen eines umfassenden Sammelbandes zur algorithmischen Informationstheorie und künstlichen Intelligenz – Randomness Through Computation: Some Answers, More Questions ^{[ 31 ]} – seine letzte Arbeit, zusammen mit anderen namhaften Persönlichkeiten auf diesem Gebiet wie Gregory Chaitin oder Jürgen Schmidhuber , in der er über das Potenzial der algorithmischen Wahrscheinlichkeit zur Erreichung von AGI und starker KI reflektierte. ^{[ 32 ]}

• Ming Li und Paul Vitanyi , Einführung in die Kolmogorov-Komplexität und ihre Anwendungen. Springer-Verlag, New York, 2008, enthält historische Anmerkungen zu Solomonoff sowie eine Beschreibung und Analyse seiner Arbeit.
• Marcus Hutters universelle künstliche Intelligenz

• Ray Solomonoffs Homepage
• Eine detaillierte Beschreibung der algorithmischen Wahrscheinlichkeit findet sich in dem Artikel „Algorithmic Probability“ von Hutter, Legg und Vitanyi in der Scholarpedia.
• Ray Solomonoff (1926–2009) 85. Gedenkkonferenz, Melbourne, Australien, Nov./Dez. 2011 und Proceedings, „Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence“, Springer, LNAI/LNCS 7070 .
• Pionier des maschinellen Lernens wurde am 14. Dezember 2011 gefeiert.