Differenzierbare Logic Cellular Automata

• Untersucht, wie sich komplexe Muster aus einfachen lokalen Regeln rückwärts konstruieren lassen
• Ein Ansatz, der die Lernfähigkeit von Neural Cellular Automata (NCA) mit Differentiable Logic Gate Networks kombiniert, um diskrete lokale Regeln durch Lernen zu gewinnen
  • „Lassen sich die Regeln von Conway's Game of Life erlernen?“
  • „Lassen sich wie bei NCA komplexe Muster reproduzieren und raumzeitliche rekursive Strukturen erlernen?“

Introduction

• Cellular Automata (CA) erzeugen aus einfachen lokalen Regeln komplexe und schwer vorhersagbare Muster
• Traditionell wurden CA-Regeln direkt von Menschen entworfen, hier wird jedoch ein Verfahren vorgestellt, bei dem Zielmuster oder Zielverhalten vorgegeben werden und die dazu passenden lokalen Regeln rückwärts „gelernt“ werden können
• Insbesondere Neural Cellular Automata (NCA) wurden so entworfen, dass sie Lernbarkeit in kontinuierlichen Räumen ermöglichen, indem Deep-Learning-Methoden mit der CA-Struktur kombiniert werden
• Differentiable Logic Gate Networks sind eine Methode, bei der Logikgatter (AND, OR, XOR usw.) kontinuierlich approximiert, trainiert und anschließend wieder in diskrete Logikschaltungen umgewandelt werden
• Durch die Kombination dieser beiden Ideen wird mit DiffLogic CA ein vollständig diskretes und zugleich lernbares CA-Modell vorgeschlagen
• Dies kann als ein kleiner Schritt in Richtung Programmable Matter oder Computronium gesehen werden
• Der Text folgt dem folgenden Aufbau
  • Zusammenfassung von Neural Cellular Automata
  • Zusammenfassung von Differentiable Logic Gate Networks
  • Die DiffLogic-CA-Architektur, die beide Methoden kombiniert
  • Experimente zum Erlernen der Conway’s-Game-of-Life-Regeln
  • Lernexperimente zur Erzeugung komplexer Muster (Schachbrett, Eidechse, Farbbilder usw.)

Recap – Neural Cellular Automata (NCA)

• Konzept
  • Ein System, das traditionelle CA-Regeln durch eine mit neuronalen Netzen lernbare Form ersetzt
  • Jede Zelle besitzt mehrere Kanäle (Zustände) und bildet durch lokale Interaktionen komplexe Muster
  • Informationen aus der Umgebung werden etwa mit Sobel-Filtern erfasst, und ein neuronales Netz entscheidet über Zustandsänderungen
• Eigenschaften
  • Der gesamte Rechenprozess ist differenzierbar und kann so trainiert werden, gewünschte Muster zu erzeugen
  • Die Kerneigenschaften von CA wie Parallelität, Lokalität und zustandsbasierte Berechnung bleiben erhalten und werden mit Deep-Learning-Methoden kombiniert

Recap – Differentiable Logic Gate Networks (DLGNs)

• Kernidee
  • Anstelle traditioneller NN werden Logikgatter (AND, OR, XOR usw.) als kontinuierliche Approximationen (soft gates) trainiert
  • Während des Trainings arbeiten die Gatter kontinuierlich, bei der finalen Inferenz führen sie echte binäre Operationen aus
• Trainingsprozess
  • Es wird eine Wahrscheinlichkeitsverteilung über die 16 möglichen logischen Operationen eines Gatters gelernt, die schließlich zu einer bestimmten Operation konvergiert
  • Durch die kontinuierliche Approximation wird Differenzierbarkeit erreicht, und nach dem Training erfolgt die Umwandlung in vollständig diskrete Logikgatter
• Vorteile
  • Die finale Schaltung besteht vollständig aus binären Logikgattern und ist daher hardwareseitig sehr effizient
  • Durch die diskrete Logikbasis ergeben sich Vorteile bei Interpretierbarkeit und Energieeffizienz

Differentiable Logic Cellular Automata (DiffLogic CA)

• Architektur
  • Auf einem 2D-Gitter besitzt jede Zelle einen n-Bit-Zustand, und die Simulation läuft in den Schritten Perception → Update ab
  • Perception-Phase
    • Nachbarschaftsinformationen (pro Kanal) werden mit Logikschaltungs-Kernen verarbeitet
  • Update-Phase
    • Der aktuelle Zustand und das Ergebnis der Perception-Phase werden von einer weiteren Logikschaltung zusammengeführt, um den Zustand des nächsten Zeitschritts zu bestimmen
• Eigenschaften
  • Alle Zellen verhalten sich wie kleine, unabhängige Prozessoren, die dezentral arbeiten
  • Durch softes Training (kontinuierliche Approximation) und harte Inferenz (binäre Gatter) ist die Effizienz hoch
  • Die Grundidee ähnelt CA-basierten Computing-Architekturen wie CAM-8

Experiment 1: Learning Game of Life

• Ziel
  • Es wird geprüft, ob sich die Regeln von Conway's Game of Life mit DiffLogic CA erlernen und vollständig reproduzieren lassen
• Setup
  • 1-Bit-Zellzustand
  • 16 Kernel für die Perception-Phase (jeweils mit 8→4→2→1-Gatterstruktur)
  • 23 Layer im Update-Schritt (anfangs 16 Layer mit 128 Knoten, danach [64, 32, 16, 8, 4, 2, 1])
  • Auf einem 3x3-Gitter werden alle möglichen Zustände (512) trainiert, damit der exakte Zustand des nächsten Schritts vorhergesagt wird
• Ergebnisse
  • Der Trainingsverlust nähert sich 0 an und die lokalen Regeln von Game of Life werden perfekt gelernt
  • Auf größeren Gittern werden wie im echten Game of Life alle Muster wie Glider und Block reproduziert
  • In der finalen Schaltung werden AND- und OR-Gatter besonders häufig verwendet

Experiment 2: Pattern Generation

• Schachbrett-Beispiel (Checkerboard)
  • Zellen mit 8-Bit-Zustand formen über 20 Schritte ein 16x16-Schachbrett
  • 16 Kernel in der Perception-Phase, 16 Layer im Update-Schritt (maximal 256 Gatter)
  • Der Verlust wird nur berechnet, indem der finale Kanal mit dem Zielmuster verglichen wird
• Ergebnisse
  • Das Schachbrett wird exakt gebildet, und die Regel wird mit nur wenigen Gattern kompakt implementiert
  • Auch auf einem viermal größeren Gitter skaliert dieselbe Regel problemlos
  • Selbst wenn einige Zellen dauerhaft deaktiviert werden, bleibt das Muster weitgehend intakt; werden die inaktiven Zellen wiederhergestellt, heilt sich das System automatisch selbst
• Asynchronicity
  • Auch mit asynchronen Updates lässt sich das Schachbrettmuster problemlos erlernen
  • Synchron trainierte Regeln funktionieren auch bei asynchroner Inferenz gut
  • Asynchron trainierte Regeln neigen dazu, sich bei Rauschen oder Beschädigungen etwas schneller zu erholen

Experiment 3: Growing a Lizard

• Ziel
  • Es wird trainiert, die Kontur einer 20x20-Eidechse in 12 Schritten zu bilden, um die Erzeugung komplexer Formen zu demonstrieren
• Setup
  • 128-Bit-Zustand
  • 4 Perception-Kernel (jeweils mit [8, 4, 2, 1]-Gatterstruktur), 10 Update-Layer (anfangs 8 Layer mit 512 Gattern, danach [256, 128])
  • Eine aktive Zelle in der Mitte des Gitters, mit periodischen Randbedingungen
• Ergebnisse
  • Auch auf einem großen Gitter (40x40) wächst die Eidechse korrekt
  • Es werden sehr viele Gatter verwendet, aber mit geeignetem Hyperparameter-Tuning ist das Training möglich

Experiment 4: Learning the G with colors

• Ziel
  • Es wird geprüft, ob sich ein 16x16-Farbbild mit 3-kanaligem RGB über 15 Schritte erzeugen lässt, um die Erzeugung mehrkanaliger Muster zu validieren
• Setup
  • 64-Bit-Zustand (die ersten 3 Kanäle werden als RGB verwendet, jeder Kanal ist 0 oder 1)
  • 4 Perception-Kernel (jeweils [8, 4, 2]), 11 Update-Layer (anfangs 8 Layer mit 512 Gattern, danach [256, 128, 64])
  • Das Zielbild ist ein 16x16-G-Muster, dessen Zellen jeweils mit einer von 8 Farben gefüllt werden
• Ergebnisse
  • Der Verlust wird nahezu 0, und nach 15 Schritten wird das farbige Ziel-G exakt reproduziert
  • In der Schaltung werden TRUE- und FALSE-Gatter häufig verwendet, OR-Gatter stechen besonders hervor

Summary and Discussion

• Was wurde gemacht?
  • Es wurde mit DiffLogic CA ein vollständig diskretes und zugleich lernbares CA-Modell vorgeschlagen
  • Es reproduziert klassische Regeln wie Game of Life und zeigt die Fähigkeit zur Mustererzeugung für Schachbrett, Eidechse und ein farbiges G
  • Da es aus diskreten Logikschaltungen besteht, sind intuitive Interpretierbarkeit und hohe Hardwareeffizienz zu erwarten
• Bedeutung
  • Es wird gezeigt, dass sich die selbstorganisierenden Muster von NCA auch mit diskreten Logikgattern erlernen lassen
  • Angesichts von Eigenschaften wie Schadensreparatur und asynchronen Updates besteht hohes Anwendungspotenzial für dezentrales, fehlertolerantes (robustes) Computing
• Grenzen und künftige Aufgaben
  • Beim Lernen komplexer Bilder oder Muster ist geeignetes Hyperparameter-Tuning erforderlich
  • Durch die Erforschung LSTM-artiger Gatter oder Strukturen zum effizienten Vergessen von Zuständen könnten reichhaltigere Muster ermöglicht werden
  • Das Modell kann in Richtung Schaltungsgrößenoptimierung und stabileres Training weiterentwickelt werden
• Fazit
  • DiffLogic CA ist ein vielversprechender Ansatz, der zu theoretischen Richtungen des dezentralen Computings wie Programmable Matter oder Computronium führen könnte
  • Da es vollständig diskret und zugleich lernbar ist, besitzt es Potenzial als Grundlage künftiger verteilter Systeme

[GN⁺]

Hacker-News-Kommentare

• Sehr interessant. Ich sammle neue universelle Turingmaschinen-Substrate. Für Experimente mit genetischer Programmierung sammle ich sie wie Pokémon. Ich habe zuvor zelluläre Automaten (CA) verwendet, aber dieser Ansatz ist deutlich attraktiver. Ich wäre nie auf die Idee gekommen, den Kernel wie eine digitale Logikschaltung zu modellieren
  • Boolesche Logik, Gates und die Beschränkungen von Schaltungen erzeugen eine interessante Struktur in der Fitness-Landschaft. Die resultierenden Parameter könnten direkt in eine Hardware-Implementierung übertragen oder über zusätzliche Optimierungsschritte in einfache Programme kompiliert werden. Sie wirken besser als das magische Floating-Point-Verhalten einer Blackbox mit Milliarden von Parametern
• Ich nutze zelluläre Automaten gern für Kunst. Es überrascht mich, welche Muster entstehen können. Ich sollte DLCA wohl ausprobieren
• Sehr interessant. Beeindruckend fand ich die Frage, die Michael Levin dazu aufgeworfen hat, wie tierische Zellen ohne Hierarchie kooperieren können. Es gibt ein Experiment, bei dem sich Augenzellen in einem Froschembryo an ihren ursprünglichen Ort bewegen. Es gab keine Antwort darauf, wie die Zellen wissen, wann sie aufhören müssen
  • Nicht-hierarchische Organisation zu verstehen, ist wichtig, um zu verstehen, wie Gesellschaft funktioniert. Es ist auch wichtig, um Gefangenendilemmata auf verschiedenen Skalen zu lösen
  • Es geht auch darum, Komplexität zu verstehen und zu modellieren
  • Zum ersten Mal sehe ich die Fähigkeit, so etwas zu modellieren. Das könnte in viele Richtungen gehen. Erstaunlich
• Ich habe in letzter Zeit viel über „Intelligenz“ nachgedacht. Es wirkt, als stünden wir an einem entscheidenden Punkt, um zu verstehen, wie Intelligenz funktioniert. Intelligenz ist ein natürlich emergentes Verhalten, nicht wesentlich anders als klassische Newtonsche Mechanik oder Elektrizität. Am Ende läuft sie auf einfache Regeln hinaus
  • Was, wenn alles Nicht-Diskrete im Gehirn nur „Infrastruktur“ ist? Wenn es nur die grundlegend einfachen, aber wichtigen Kernprozesse unterstützt, die die eigentliche Arbeit leisten? Wenn letztlich alles auf Logikgatter und elektrische Signale hinausläuft?
  • Spannende Zeiten kommen auf uns zu
• Sie sind besonders im Hinblick auf Generalisierungsfähigkeit attraktiv. Aber was ist die Vision? Was könnte man in Zukunft damit tun? Und philosophisch: Was könnten sie uns über die Welt lehren? Ich weiß, dass 1D-zelluläre Automaten Turing-äquivalent sind. Daher sind NCA/diese hier nicht besonders überraschend
• Das ist ein Durchbruch. Es geht nicht um Schachbretter oder Eidechsen. Die Navier-Stokes-Differentialgleichungen sind die Aktualisierungsregeln, die die Bewegung von Fluiden bestimmen. Die gesamte Komplexität von Wolkenbildung, Flammenbewegung usw. wird von einfachen Gesetzen beherrscht. Wissenschaft bedeutet, diese Gleichung anhand realer Stichproben zu entdecken. Man könnte das DLCA-Modell auf Videoaufnahmen von Rauch anwenden und die Navier-Stokes-Gleichungen herleiten. Wenn man berücksichtigt, dass sich die Aktualisierungsregeln selbst nach anderen Aktualisierungsregeln ändern können, betritt man ein spannendes Gebiet. Das könnte der Grund sein, warum Neuronen im Gehirn mit Tausenden anderer Neuronen verbunden sind
  • Google-Führungskräfte werden diese Entdeckung ignorieren, weil sie nichts mit dem Werbegeschäft zu tun hat. Wenn DLCA in ein paar Jahren die Welt auf den Kopf stellt, werden sie behaupten, einer ihrer Mitarbeiter habe es entdeckt
• Sehr interessante Arbeit. Eine Frage: Da die Aktualisierung über „globalen“ Gradientenabstieg erfolgt, sind die Zell-Gates nicht wirklich parallel
  • Gibt es eine mögliche Methode zur streng lokalen Anpassung der Gewichte?
• Die kontinuierliche Relaxation der Booleschen Algebra ist eine alte Idee. Schaltungssynthese ist ein gut erforschtes Gebiet. Google hat vor zwei Jahren den Wettbewerb gewonnen. Ich frage mich, ob man den Lerner auf den Datensatz des IWLS-Wettbewerbs angewendet hat. Falls nicht, warum nicht?
• Könnte man das für die ARC-AGI-Challenge verwenden? Könnte man es mit den neueren Ansätzen kombinieren?
• Eigenwerbung, aber relevant => Robustness and Halting in Artificial Multi-Cellular Development (2011)
  • Zelluläre Automaten, bei denen die Aktualisierungsregeln mit Perzeptronen und isotroper Diffusion kombiniert werden. Die Gewichte des neuronalen Netzes werden so optimiert, dass der zelluläre Automat Bilder zeichnen kann. Selbstheilung (d. h. das Bild wird rekonstruiert, wenn es gestört wird)
  • Damals war automatische Differenzierung nicht so zugänglich wie heute. Ich habe die Gewichte mit evolutionären Strategien optimiert. Natürlich wäre es viel besser, Gradientenabstieg zu verwenden