Seite 2: Erforschung von Systemräumen

Inhaltsverzeichnis

"Kann man ein System finden, das X ausführt?" Das könnt beispielsweise eine Turingmaschine sein, die sehr lange läuft, bevor sie hält, oder ein zellulärer Automat, der wächst, aber nur sehr langsam, oder eine Chemikalie mit einer bestimmten Eigenschaft.

Dies ist eine etwas andere Art von Fragestellung als die, die bisher diskutiert wurden. Es geht nicht darum, eine bestimmte Regel zu nehmen und zu sehen, welche Konsequenzen sie hat. Es geht darum, zu identifizieren, welche Regel existieren könnte, die bestimmte Konsequenzen hat.

Angesichts eines Raums möglicher Regeln ist ein Ansatz die erschöpfende Suche. In gewissem Sinne ist dies letztlich der einzige wirklich unvoreingenommene Ansatz, der entdecken wird, was es zu entdecken gibt, selbst wenn man es nicht erwartet. Natürlich benötigt man selbst bei der erschöpfenden Suche noch eine Möglichkeit, zu bestimmen, ob ein bestimmtes Kandidatensystem das festgelegte Kriterium erfüllt. Aber jetzt ist dies das Problem der Vorhersage einer Berechnung – wobei das oben Gesagte gilt.

Aber kann man besser als die erschöpfende Suche vorgehen? Und kann man etwa einen Weg finden, herauszufinden, welche Regeln erkundet werden sollen, ohne jede Regel anschauen zu müssen? Ein Ansatz ist, so etwas wie das zu tun, was in der biologischen Evolution durch natürliche Selektion geschieht: Man beginnt, sagen wir, mit einer bestimmten Regel und ändert sie dann schrittweise (möglicherweise zufällig), indem man bei jedem Schritt die Regel oder Regeln behält, die am besten abschneiden, und die anderen verwirft.

Dies ist keine KI im hier operationell definierten Sinne (es ähnelt mehr einem genetischen Algorithmus) – obwohl es etwas wie die innere Trainingsschleife eines neuronalen Netzes ist. Aber wird es funktionieren? Nun, das hängt von der Struktur des Regelraums ab – und, wie man im maschinellen Lernen sieht, funktioniert es tendenziell besser in höherdimensionalen Regelräumen als in niedrigerdimensionalen. Denn mit mehr Dimensionen besteht eine geringere Chance, dass man „in einem lokalen Minimum stecken bleibt“ und keinen Weg heraus zu einer "besseren Regel“ findet.

Im Allgemeinen, wenn der Kontrollraum wie eine komplizierte fraktale Berglandschaft ist, kann man vernünftigerweise erwarten, dass schrittweise Fortschritte gemacht werden. KI-Methoden, wie beispielsweise das Lernen durch Verstärkung, können dabei helfen, die zu unternehmenden Schritte zu verfeinern. Ist das Gelände jedoch eher flach, beispielsweise mit nur einem Loch irgendwo ("Golfplatz-Stil“), kann nicht erwartet werden, dass das Loch schrittweise gefunden wird. Wie sieht also die typische Struktur von Regelräumen aus? Sicherlich gibt es viele Fälle, in denen der Regelraum insgesamt ziemlich groß ist, aber die Anzahl der Dimensionen bescheiden ist. Und in solchen Fällen (ein Beispiel ist die Suche nach kleinen Turingmaschinen mit langen Haltezeiten) scheint es oft "isolierte Lösungen“ zu geben, die nicht schrittweise erreicht werden können. Aber wenn es mehr Dimensionen gibt, scheint es wahrscheinlich, dass das, was im Wesentlichen die rechnerische Irreduzibilität darstellt, mehr oder weniger garantiert, dass es eine "ausreichend zufällige Landschaft“ gibt, in der schrittweise Methoden gut funktionieren können, wie wir es in den vergangenen Jahren im maschinellen Lernen gesehen haben.

Und was ist mit KI? Könnte es einen Weg geben, dass KI lernt, wie man direkt im Regelraum "Gewinner auswählt“, ohne irgendeinen inkrementellen Prozess? Könnten wir vielleicht einen Einbettungsraum finden, in dem die gewünschten Regeln auf einfache Weise angeordnet sind – und somit effektiv „vorab für uns identifiziert“ werden? Letztendlich hängt es davon ab, wie der Regelraum beschaffen ist und

ob der Prozess seiner Erkundung notwendigerweise (multi)computational irreduzibel ist, oder ob zumindest die Aspekte davon, die uns interessieren, durch einen reduzierbaren Prozess erkundet werden können. (Übrigens versucht man, KI direkt zu verwenden, um Systeme mit bestimmten Eigenschaften zu finden, ist ein wenig so, als würde man versuchen, KI direkt zu verwenden, um neuronale Netze aus Daten ohne inkrementelles Training zu generieren.)

Betrachten wir ein einfaches Beispiel auf Basis von zellulären Automaten. Angenommen, Sie möchten eine Regel für zelluläre Automaten finden, die – ausgehend von einer einzigen Zellen-Anfangsbedingung – eine Weile wächst, aber dann nach einer bestimmten, genauen Anzahl von Schritten ausstirbt. Sie können versuchen, dies mit einem sehr minimalen KI-ähnlichen evolutionären Ansatz zu lösen: Beginnend mit einer zufällig ausgewählten Regel, dann in jeder Generation eine bestimmte Anzahl von "Nachkommen“-Regeln erzeugen, bei denen jeweils ein Element zufällig geändert wird – dann die "beste" dieser Regeln behalten. Wenn Sie eine Regel finden wollen, die genau 50 Schritte lebt, definieren Sie "beste" als diejenige, die eine Verlustfunktion minimiert, die gleich der Entfernung von 50 der Anzahl der Schritte ist, die eine Regel tatsächlich "lebt".

So könnte man beispielsweise von der zufällig ausgewählten (Drei-Farben-)Regel starten:

Die evolutionäre Abfolge von Regeln (hier nur die Ergebniswerte gezeigt) könnte wie folgt aussehen:

Wenn das Verhalten dieser Regeln betrachtet wird, zeigt sich, dass sie – nach einem wenig vielversprechenden Start – erfolgreich eine Regel entwickeln, die das Kriterium "genau 50 Schritte zu leben“ erfüllt:

Im Bild sieht man ein zufällig gewählter Evolutionspfad. Doch was geschieht auf anderen Pfaden? Hier ist die Entwicklung des Verlusts (über den Verlauf von 100 Generationen) für eine Sammlung von Pfaden:

Und wir sehen, dass es hier nur einen "Gewinner" gibt, der keinen Verlust erleidet; auf allen anderen Wegen bleibt die Evolution "stecken".

Wie bereits erwähnt, sinkt die Wahrscheinlichkeit, stecken zu bleiben, mit mehr Dimensionen. Wenn man sich etwa die Regeln für vierfarbige zelluläre Automaten ansieht, gibt es jetzt 64 statt 27 mögliche Elemente (oder effektiv Dimensionen), die verändert werden können, und in diesem Fall kommen viele Wege der Evolution weiter

und es gibt noch mehr "Gewinner" wie in diesem Beispiel:

Neuronale Netze könnten helfen, die Evolution von zellulären Automaten schneller zu verstehen, indem sie die Berechnung des Verlusts für Regeln beschleunigen. Allerdings könnte die Komplexität der Berechnungen ein Hindernis sein. Eine Idee ist, neuronale Netze zu nutzen, um zu entscheiden, welche Änderungen bei jeder Generation gemacht werden sollen. Aber die Komplexität der Berechnungen macht es schwierig für neuronale Netze, uns genau zu sagen, was wir tun sollen, auch wenn sie helfen, nicht festzustecken.