- DiffLogic CA ist ein Ansatz für zelluläre Automaten, der Neural Cellular Automata mit Differentiable Logic Gate Networks kombiniert, um lokale Regeln gradientenbasiert zu lernen und dabei diskrete Zellzustände beizubehalten
- Jede Zelle besitzt einen n-dimensionalen binären Vektor als Zustand, und sowohl Wahrnehmungs- als auch Update-Phase werden durch Logikgatter-Netzwerke verarbeitet, die den nächsten Zustand direkt berechnen
- Im Experiment mit Conways Game of Life lernte das System in einem Schritt alle 512 Konfigurationen eines periodischen 3x3-Gitters und damit die vollständige Regel; auch bei harter Inferenz reproduzierte es repräsentative Muster wie glider, block, loaf und boat
- Im Experiment zur Mustergenerierung erzeugte es ein 16x16-Schachbrett in 20 Schritten und funktionierte auch auf einem viermal größeren Gitter sowie über die vierfache Zeitspanne; zudem zeigte es Fehlertoleranz bei beschädigten Zellen und Selbstheilung nach Reaktivierung
- Es erzeugte auch die komplexere lizard-Kontur und ein 8-farbiges RGB-G, doch das Lernen komplexer Strukturen erforderte viel Hyperparameter-Tuning, und hierarchische NCA sowie LSTM-ähnliche Gating-Mechanismen bleiben Kandidaten für Verbesserungen
Welches Problem DiffLogic CA adressiert
- Zelluläre Automaten werden normalerweise so behandelt, dass lokale Regeln zuerst festgelegt und die daraus entstehenden emergenten Muster anschließend beobachtet werden
- DiffLogic CA untersucht einen Weg, lokale Regeln, die ein gewünschtes komplexes Muster erzeugen, vollständig differenzierbar zu lernen
- Bestehende Neural Cellular Automata können beliebige Muster und Verhaltensweisen lernen, arbeiten aber nicht inhärent in einem diskreten Zustandsraum, was die Interpretierbarkeit verringert und bei kontinuierlichen Zustandsupdates Kosten für Matrixmultiplikationen verursacht
- Differentiable Logic Gate Networks wurden zur Entdeckung kombinatorischer Logikschaltungen eingesetzt, doch in rekursiven NCA-Setups über Raum und Zeit war ihre Funktionsfähigkeit bislang nicht nachgewiesen
- Das gesamte Experiment lässt sich im Notebook reproduzieren
Grundstruktur von Neural Cellular Automata
- Neural Cellular Automata kombinieren klassische zelluläre Automaten mit Deep Learning und lernen Update-Regeln per Gradientenabstieg, statt sie von Hand zu entwerfen
- Jede Zelle eines Growing-NCA besitzt auf einem 2D-Gitter einen n-dimensionalen Zustandsvektor
- Die 3 RGB-Kanäle repräsentieren die Farbe der Zelle
- Der Alpha-Kanal repräsentiert die Lebensfähigkeit der Zelle; bei einem Alpha-Wert größer als 0,1 gilt die Zelle als lebendig
- Die übrigen hidden channels transportieren komplexere Informationen über die Umgebung
- Das Update besteht aus zwei Schritten
- Wahrnehmungsphase: Ein Sobel-Filter wird kanalweise angewendet, um räumliche Gradienten zu approximieren und einen Wahrnehmungsvektor zu erzeugen, der aktuellen Zellzustand und Umgebungsinformation kombiniert
- Update-Phase: Ein neuronales Netzwerk mit rund 8.000 Parametern wird identisch auf alle Zellen angewendet und entscheidet, wie sich jede Zelle verändert
- Da alle Operationen differenzierbar sind, kann das Gesamtsystem bestimmte Muster oder Verhaltensweisen lernen
Vorgehensweise von Differentiable Logic Gate Networks
- Deep Differentiable Logic Gate Networks verwenden statt künstlicher Neuronen Logikgatter wie AND, OR und XOR als Grundbausteine
- Das Netzwerk besteht aus Gatter-Schichten, wobei jedes Gatter Eingaben von zwei Gattern der vorherigen Schicht erhält und damit eine spärliche Struktur bildet
- Die Verbindungen werden zufällig initialisiert und während des Trainings nicht verändert; das Lernen entscheidet nur, welche logische Operation jedes Gatter ausführt
- Während des Trainings werden diskrete Logikgatter nicht direkt verwendet, sondern zwei Mechanismen eingesetzt
- Kontinuierliche Relaxation: Diskrete Operationen wie hartes AND werden durch differenzierbare Versionen ersetzt, die Eingaben zwischen 0 und 1 akzeptieren
- Stochastische Gatterauswahl: Jedes Gatter besitzt eine Wahrscheinlichkeitsverteilung über 16 mögliche binäre Operationen für zwei Eingaben; gelernt werden 16-dimensionale, per softmax dargestellte Parameter
- Nach Abschluss des Trainings wird jedes Gatter auf die wahrscheinlichste Operation festgelegt, und bei der Inferenz werden nur noch reine Binäroperationen ausgeführt
- Zur Stabilisierung des Trainings wird die anfängliche Gatterverteilung in Richtung pass-through-Gatter verzerrt initialisiert
Struktur von DiffLogic CA
- DiffLogic CA folgt der 2D-Gitterstruktur von NCA, repräsentiert den Zustand jeder Zelle jedoch als n-dimensionalen binären Vektor
- Zellzustand und Kanäle werden synonym verwendet; der binäre Zustandsvektor dient als Arbeitsgedächtnis zum Speichern von Informationen aus vorherigen Iterationen
- Die Wahrnehmungsphase verwendet statt Sobel-Filtern kernelbasierte Logikgatter-Netzwerke
- Jeder Kernel ist eine separate Schaltung mit fester Verbindungsstruktur, deren Gattertypen gelernt werden
- Die Kernel werden kanalweise berechnet
- Jede Schaltung nutzt 4 Schichten, die dafür ausgelegt sind, Interaktionen zwischen Zentralzelle und Nachbarzellen zu berechnen
- Die Update-Phase speist die vorherige Zellspeicherung und die von den Nachbarn erhaltenen Informationen als verkettete Eingabe in ein Differentiable Logic Gate Network ein, das den neuen Zustand berechnet
- Anders als bei Standard-NCA, die ODE-artige inkrementelle Zustandsupdates verwenden, wird der nächste binäre Zustand direkt ausgegeben
- Der Ablauf einer Runde kann als System mit zwei Registern betrachtet werden
- Im grauen Register befindet sich der bestehende Zellzustand
- Im orangefarbenen Register wird das Ergebnis der Wahrnehmungsphase gespeichert
- Nach dem Update wird der neue Zustand ins graue Register geschrieben, während das orangefarbene Register für die nächste Runde geleert wird
- Diese Struktur funktioniert wie ein Netzwerk kleiner unabhängiger Computer, in dem jede Zelle mit ihren Nachbarn kommuniziert und auf Basis der Beobachtungen Entscheidungen trifft
Experiment 1: Lernen von Conways Game of Life
- Game of Life ist ein binärer zellulärer Automat, bei dem jede Zelle in der nächsten Generation lebt oder stirbt, abhängig vom Zustand ihrer 8 Nachbarn und ihrem aktuellen Zustand
- Die Regel besteht aus vier Teilen
- Eine tote Zelle wird in der nächsten Generation lebendig, wenn sie genau 3 lebende Nachbarn hat
- Eine lebende Zelle überlebt, wenn sie 2 oder 3 lebende Nachbarn hat
- Eine lebende Zelle stirbt, wenn sie weniger als 2 Nachbarn hat
- Eine lebende Zelle stirbt, wenn sie mehr als 3 Nachbarn hat
- Da dieses Experiment Regeln ohne Abhängigkeit von früheren Zustandswiederholungen betrachtet, wird der Zellzustand auf 1 Bit gesetzt
- Die Modellkonfiguration ist wie folgt
- 16 Wahrnehmungsschaltungs-Kernel
- Die Knotenstruktur jedes Wahrnehmungskernels ist
[8, 4, 2, 1] - Das Update-Netzwerk hat 23 Schichten
- Die ersten 16 Schichten besitzen jeweils 128 Knoten
- Die folgenden Schichten sind
[64, 32, 16, 8, 4, 2, 1]
- Die Trainingsdaten umfassen alle 512 möglichen Konfigurationen auf einem periodischen 3x3-Gitter
- Da der nächste Zustand jeder Zelle durch sie selbst und ihre 8 Nachbarn bestimmt wird, gibt es 512 mögliche 3x3-Konfigurationen
- Wenn alle nächsten Zustände für einen Schritt korrekt vorhergesagt werden, entspricht das dem Erlernen der vollständigen Game-of-Life-Regel
- Die Verlustfunktion summiert die quadrierten Differenzen zwischen vorhergesagtem und Zielgitter
- Sowohl soft loss als auch hard loss konvergierten vollständig, und bei harter Inferenz reproduzierte die gelernte Schaltung Game-of-Life-Muster auch auf größeren Gittern
- Die Zahl aktiver Gatter betrug 336, pass-through A und B ausgenommen; in Wahrnehmungs- und Update-Netzwerk wurden OR und AND am häufigsten verwendet
- Mit der erzeugten Schaltung kann direkt über die Game-of-Life-Schaltung interagiert werden
Experiment 2: Erzeugung eines Schachbrettmusters
- Das Experiment zur Mustergenerierung ist so angelegt, dass Regeln gelernt werden, die sich aus einem beliebigen Anfangszustand zu einem Zielbild entwickeln
- Der Verlust wird nur am letzten Zeitschritt berechnet, sodass das Modell ohne Zwischenaufsicht diskrete Übergangsregeln finden muss
- Der Zellzustand ist 8 Bit breit, und DiffLogic CA wird 20 Schritte lang iteriert
- Die Modellkonfiguration ist wie folgt
- 16 Wahrnehmungsschaltungs-Kernel
- Jeder Kernel hat pro Schicht 8, 4 und 2 Gatter
- Das Update-Netzwerk hat 16 Schichten
- Die ersten 10 Schichten besitzen jeweils 256 Gatter
- Die folgenden Schichten sind
[128, 64, 32, 16, 8, 8]
- Die Verlustfunktion ist die Summe der quadrierten Differenzen zwischen dem ersten Kanal des vorhergesagten Gitters und dem Zielgitter am letzten Zeitschritt
- Das Modell wurde darauf trainiert, ein 16x16-Schachbrettmuster innerhalb von 20 Schritten wiederherzustellen
- Sowohl soft loss als auch hard loss konvergierten, und im ersten Kanal zeigte sich eine klare Musterbildung
- Das Modell hatte keine eingebaute Richtungspräferenz, dennoch zeigte sich die Eigenschaft, dass sich das Muster von links unten nach rechts oben ausbreitet
- Die Zahl aktiver Gatter betrug 22, pass-through A und B ausgenommen; nach dem Pruning ließ sich die gesamte Schachbrett-Erzeugungsfunktion praktisch mit 5 Logikgattern implementieren
- Die Schaltung funktionierte auch bei einem viermal größeren Gitter und einer vierfach längeren Zeitspanne; die gelernte Regel war also nicht bloß auf eine bestimmte Gittergröße überangepasst
Beschädigung, Selbstheilung und asynchrone Updates
- Im Schachbrett-Experiment wurden zwei Schadensszenarien getestet, um defekte Zellen zu simulieren
- Zellen in einem großen Bereich wurden dauerhaft deaktiviert, um fehlerhafte Bauteile zu simulieren
- Nach einer bestimmten Schrittzahl wurden inaktive Zellen wieder aktiviert
- Das System bewahrte die Integrität des Musters auch bei permanenten Schäden und erzeugte nach dem Wieder-online-Gehen der inaktiven Zellen erneut das korrekte Muster
- Obwohl Fehlertoleranz und Selbstheilung nicht explizit entworfen wurden, zeigte das System ein Verhalten, bei dem Schäden lokal begrenzt bleiben und die Gesamtfunktion nicht abrupt kollabiert
- In Experimenten mit asynchronen Updates wurden nicht alle Zellen gleichzeitig aktualisiert; stattdessen wurde in jedem Schritt nur eine zufällige Teilmenge von Zellen aktualisiert
- Asynchrones Lernen wurde als schwieriger eingeschätzt als bei bestehenden NCA
- In jedem Schritt muss nicht nur ein Inkrement, sondern der vollständige neue Zustand ausgegeben werden
- Kombinationen aus um unterschiedlich viele Schritte vor- oder zurückliegenden Nachbarzellen müssen verarbeitet werden
- Beim Schachbrett gelang asynchrones Lernen vergleichsweise leicht, und auch bei unterschiedlicher Update-Reihenfolge aus demselben Anfangszustand wurde das Zielmuster innerhalb von 50 Schritten rekonstruiert
- Auch bestehende synchron gelernte Regeln funktionierten bei asynchroner Inferenz
- In einem Test, bei dem bei jedem Inferenz-Zeitschritt zufällig ein 10x10-Pixel-Rechteck innerhalb des Bildbereichs deaktiviert wurde, erholten sich asynchron gelernte Zellen etwas schneller von Schäden
- Gemessen über die Summe der absoluten Differenzen zwischen Ziel- und Rekonstruktionsbild erhöhte asynchrones Lernen die Robustheit gegenüber solchen Störungen
Experiment 3: Wachstum einer lizard-Kontur
- Das lizard-Experiment ist eine Hommage an frühere NCA-Arbeiten und prüft, ob DiffLogic CA beliebige Formen lernen kann
- Anders als das stark komprimierbare, regelmäßige Schachbrettmuster erfordert die lizard-Kontur deutlich mehr Memorierung
- Die Konfiguration ist wie folgt
- Der Zellzustand umfasst 128 Bit
- DiffLogic CA wird 12 Schritte lang iteriert
- Es gibt 4 Wahrnehmungsschaltungs-Kernel
- Jeder Kernel besitzt pro Schicht 8, 4, 2 und 1 Gatter
- Das Update-Netzwerk hat 10 Schichten
- Die ersten 8 Schichten besitzen jeweils 512 Gatter
- Die letzten Schichten sind
[256, 128]
- Das Modell wurde darauf trainiert, ein 20x20-lizard-Muster in 12 Schritten zu erzeugen
- Die Anfangsbedingung ist wie bei NCA ein zentraler Seed zum Brechen der Symmetrie, und an den Gitterrändern gelten periodische Randbedingungen
- Auch auf einem größeren 40x40-Gitter erzeugte das Modell erfolgreich das lizard-Wachstumsmuster und zeigte damit, dass die Lösung nicht bloß Randbedingungen ausnutzte
- Sowohl soft loss als auch hard loss konvergierten auf 0
- Die Zahl aktiver Gatter betrug 577, pass-through A und B ausgenommen
- Die Wahrnehmungskernel verwendeten hauptsächlich TRUE-Gatter, während die Update-Schaltung fast alle verfügbaren Gatter nutzte
- Das Lernen komplexer Mustergenerierung war optimierungsseitig schwierig und erforderte umfangreiches Hyperparameter-Tuning
Experiment 4: Erzeugung eines farbigen G
- Da sich die vorherigen Experimente faktisch auf monochrome Bilder konzentrierten, wurde ein Experiment zur Erzeugung eines 16x16-Farbbilds als komplexerer Zielzustand durchgeführt
- Der Zellzustand umfasst 64 Kanäle, und das Modell erzeugt über 15 Schritte ein farbiges G
- Die ersten drei Kanäle repräsentieren wie in Standard-NCA die RGB-Werte, sind hier aber auf binäre Werte 0 oder 1 beschränkt und bilden damit eine Palette aus 8 Farben
- Die Modellkonfiguration ist wie folgt
- 4 Wahrnehmungsschaltungs-Kernel
- Jeder Kernel besteht aus 3 Schichten mit 8, 4 und 2 Gattern
- Das Update-Netzwerk hat 11 Schichten
- Die ersten 8 Schichten besitzen jeweils 512 Knoten
- Die letzten 3 Schichten sind
[256, 128, 64]
- Der Anfangszustand ist vollständig 0, und periodische Randbedingungen werden nicht verwendet
- Die Verlustfunktion summiert am letzten Zeitschritt die quadrierten Differenzen zwischen vorhergesagtem und Zielgitter, jedoch nur für die ersten drei Kanäle 0, 1 und 2
- Sowohl soft loss als auch hard loss konvergierten, und das Modell rekonstruierte das farbige G innerhalb von 15 Schritten
- Die Zahl aktiver Gatter betrug 927, pass-through A und B ausgenommen
- TRUE- und FALSE-Gatter wurden sowohl im Wahrnehmungs- als auch im Update-Netzwerk häufig verwendet; im Update-Netzwerk kam OR am häufigsten vor
- Diese Schaltung war sowohl beim Hyperparameter-Search als auch bei der Schaltungsgröße komplexer als in früheren Experimenten
Offene Aufgaben und Verbesserungsrichtungen
- DiffLogic CA schlägt eine neue NCA-Architektur und Lernmethode vor, die vollständig diskrete Zellzustände nutzt und diese über gelernte rekursive Binärschaltungen aktualisiert
- Durch den Ersatz neuronaler Netzwerkkomponenten durch Deep Differentiable Logic Networks verbindet der Ansatz die Flexibilität differenzierbaren Lernens mit diskreten Logikgittern
- Die Reproduktion von Game of Life und die Experimente zur Mustergenerierung zeigen, dass differenzierbare Logikgatter auf zelluläre Automaten angewendet werden können
- Dadurch wird bestätigt, dass Differentiable Logic Gate Networks auch in rekursiven Strukturen effektiv trainiert werden können
- Das aktuelle Modell zeigte zwar das Potenzial zum Lernen von Mustern, doch das Erzeugen komplexerer Formen und Strukturen bleibt weiterhin schwierig
- Als Verbesserungsrichtungen werden hierarchische NCA-Strukturen und spezielle Gatter vorgeschlagen, die das Vergessen von Zuständen unterstützen
- Wenn LSTM-ähnliche Gating-Mechanismen in den Zustandsupdate-Prozess integriert werden, lassen sich vergangene Zustände und neu berechnete Kandidatenzustände reichhaltiger kombinieren, was Dynamik und Ausdruckskraft des Modells erhöhen kann
1 Kommentare
Hacker-News-Kommentare
Sehr interessant. Ich war auf der Suche nach neuen universellen Turing-Maschinen-Substraten und habe sie wie Pokémon für Experimente mit genetischer Programmierung gesammelt. Früher habe ich auch mit zellulären Automaten wie Rule 30/110 herumgespielt, aber dieser Ansatz ist deutlich überzeugender.
Auf die Idee, den Kernel wie eine digitale Logikschaltung zu modellieren, wäre ich nicht gekommen. Boolesche Logik, Gates und die Einschränkungen von Schaltungen scheinen der Fitness-Landschaft eine interessante Struktur zu geben. Die resultierenden Parameter lassen sich direkt in eine Hardware-Implementierung überführen oder nach einem zusätzlichen Optimierungsschritt in ein einfaches Programm kompilieren. Das wirkt besser, als magische Gleitkommazahlen in einer Blackbox mit Milliarden Parametern zu behandeln.
Spannend. Michael Levin hat am besten herausgearbeitet, wie tierische Zellen ohne Hierarchie zusammenarbeiten können. Es gibt zum Beispiel biologische Experimente, bei denen Augenzellen aus einem Froschembryo entfernt werden und trotzdem an die Stelle wandern, an der ein Auge sein sollte.
Die Frage, die er meiner Ansicht nach nicht wirklich beantworten konnte, war: Woher wissen Zellen, wann sie aufhören müssen? Nicht-hierarchische Organisation zu verstehen, ist auch zentral dafür, wie Gesellschaften funktionieren, und dafür, das Gefangenendilemma auf verschiedenen Skalen einer selbstorganisierten Welt zu lösen. Es geht auch darum, rohe Komplexität zu verstehen und zu modellieren. Das ist das erste Mal, dass ich eine Fähigkeit sehe, solche Dinge zu modellieren, und von hier aus scheinen sich wirklich viele Richtungen zu eröffnen.
Ich denke in letzter Zeit viel über Intelligenz nach und habe das Gefühl, dass wir an einem entscheidenden Punkt stehen, an dem wir herausfinden, wie Intelligenz funktioniert, oder zumindest unser Verständnis deutlich voranbringen. Intelligenz wirkt wie ein natürlich emergentes Verhalten, nicht grundsätzlich anders als klassische Newtonsche Mechanik oder Elektrizität.
Am Ende scheint es auf einfache Regeln hinauszulaufen. Was, wenn alles im Gehirn, das nicht diskret ist, in Wahrheit nur Infrastruktur ist, die einen einfachen, aber wichtigen Kernprozess trägt, der die eigentliche Arbeit leistet? Was, wenn ganz unten letztlich Logikgatter und elektrische Signale stehen? Es dürften spannende Zeiten bevorstehen.
An solchen Ansätzen gibt es etwas besonders Reizvolles, vor allem hinsichtlich der Generalisierungsfähigkeit. Aber ich frage mich, was die große Vision ist. Was werden wir künftig damit tun können? Was lehrt es uns philosophisch über die Welt? Dass eindimensionale zelluläre Automaten Turing-äquivalent sind, wissen wir bereits; aus mancher Perspektive sind NCA oder solche Methoden daher nicht völlig überraschend.
Es wird zelluläre Automaten geben, die mit der Umwelt interagieren, sowie Automaten, die sowohl mit Low-Level-Systemen als auch mit High-Level-Institutionen interagieren. In gewisser Näherung sind auch Menschen nur einzelne Zellen, die innerhalb solcher Netzwerke interagieren. Die Zukunft der Intelligenz sehe ich nicht in LLMs, sondern in Automatensystemen mit metabolischer Dimension: Automaten, die gemeinsam evolvieren, Energie verbrauchen, Wert erzeugen, konkurrieren und einander modellieren.
Wir werden nicht ersetzt; wir nehmen an einer Transformation teil, bei der die Grenze zwischen technischen Systemen und zellulären Systemen verschwimmt und schließlich verschwindet. Ich bin sehr dankbar, das miterleben zu dürfen. Hinweis: https://x.com/zzznah/status/1803712504910020687
Ich spiele für Kunstprojekte gern mit zellulären Automaten. Es ist erstaunlich, welche Muster entstehen können. Beispiel: https://gods.art/math_videos/hex_func27l_21.html
Mit diesem DLCA sollte ich wohl auch einmal herumspielen.
Hier stecken viele tolle Ideen drin. Vielleicht nur eine kleine Beobachtung, aber diese Berechnung hat Zustand. Jede Zelle hat Speicher und eine Wahrnehmung ihrer Umgebung.
Moderne neuronale Netze sind dagegen größtenteils zustandslos. Ich frage mich zum Beispiel, ob es Forschung zu LLMs mit Zustand gibt.
Eigenwerbung, aber sehr relevant: Robustness and the Halting Problem for Multicellular Artificial Ontogeny (2011)
Es ging um einen zellulären Automaten, dessen Aktualisierungsregel ein mit isotroper Diffusion gekoppeltes Perzeptron war. Die Gewichte des neuronalen Netzes wurden optimiert, damit der zelluläre Automat ein Bild zeichnet und sich bei Störungen selbst heilt, indem er das Bild wiederherstellt. Damals war automatische Differenzierung nicht so zugänglich wie heute, daher wurden die Gewichte mit Evolutionsstrategien optimiert. Mit Gradientenabstieg wäre das natürlich wahrscheinlich deutlich besser.
Könnte man das für die ARC-AGI Challenge verwenden? Vielleicht ließe es sich auch mit diesem neueren Ansatz kombinieren: https://news.ycombinator.com/item?id=43259182
Wirklich beeindruckend. Als jemand, der seit Langem meist nur mitliest und viel Modellierung und Simulation nutzt, sehe ich großes Potenzial, das emergente Verhalten komplexer Akteursmodelle besser zu verstehen.
Ich würde gern sehen, wie es auf Dinge wie Räuber-Beute-Modelle angewendet wird, und auf andere Modelle, die einfach erscheinen, aber in großem Maßstab komplexe emergente Ergebnisse hervorbringen. Diese Arbeit werde ich weiter verfolgen.
Das Schachbrettmuster im Ergebnis sieht wie das Gegenteil des Zielmusters aus, also wie ein NOT. Dazu wird aber nichts gesagt. Ich frage mich, ob es nicht wichtig genug ist, erwähnt zu werden, oder ob ich etwas übersehe.