Automates cellulaires logiques différentiables

• Exploration d’une méthode d’ingénierie inverse de motifs complexes à partir de règles locales simples
• Une approche qui combine la capacité d’apprentissage des Neural Cellular Automata (NCA) avec les Differentiable Logic Gate Networks pour obtenir, par apprentissage, des règles locales discrètes
  • « Peut-on apprendre les règles du Game of Life de Conway ? »
  • « Peut-on reproduire des motifs complexes comme avec les NCA et apprendre des structures récurrentes spatio-temporelles ? »

Introduction

• Les Cellular Automata (CA) partent de règles locales simples pour former des motifs complexes et difficiles à prédire
• Traditionnellement, les règles des CA étaient conçues manuellement, mais ici on présente une méthode permettant d’“apprendre” à rebours des règles locales qui satisfont un motif ou un comportement cible donné à l’avance
• En particulier, les Neural Cellular Automata (NCA) ont été conçus pour combiner la structure des CA avec des techniques de deep learning afin de permettre l’apprentissage dans un espace continu
• Les Differentiable Logic Gate Networks sont une technique qui approxime de façon continue des portes logiques (AND, OR, XOR, etc.) pour les apprendre, puis les reconvertit à la fin en circuits logiques discrets
• En combinant ces deux idées, les auteurs proposent DiffLogic CA, un modèle de CA entièrement discret et entraînable
• Cela peut être vu comme un petit pas vers la matière programmable (Programmable Matter) ou le Computronium
• L’article suit le fil conducteur suivant
  • Résumé des Neural Cellular Automata
  • Résumé des Differentiable Logic Gate Networks
  • Structure de DiffLogic CA, qui combine les deux approches
  • Expérience d’apprentissage des règles du Game of Life de Conway
  • Expériences d’apprentissage pour générer des motifs complexes (damier, lézard, image couleur, etc.)

Récapitulatif – Neural Cellular Automata (NCA)

• Concept
  • Un système qui remplace les règles traditionnelles des CA par une forme entraînable via un réseau de neurones
  • Chaque cellule possède plusieurs canaux (états) et forme des motifs complexes via des interactions locales
  • Des filtres Sobel et autres sont utilisés pour capter l’information du voisinage, puis le réseau de neurones décide des changements d’état
• Caractéristiques
  • Tout le processus de calcul est différentiable, ce qui permet un apprentissage orienté vers la production d’un motif souhaité
  • L’approche conserve les principes clés des CA — parallélisme, localité, calcul fondé sur l’état — tout en y ajoutant des techniques de deep learning

Récapitulatif – Differentiable Logic Gate Networks (DLGNs)

• Idée centrale
  • Au lieu d’un réseau neuronal classique, l’apprentissage se fait à partir d’une approximation continue de portes logiques (AND, OR, XOR, etc.), appelée soft gate
  • Pendant l’apprentissage, les portes fonctionnent de manière continue, puis lors de l’inférence finale, elles exécutent de véritables opérations binaires
• Processus d’apprentissage
  • Le modèle apprend une distribution de probabilité sur les 16 opérations logiques possibles d’une porte, pour converger finalement vers une opération spécifique
  • L’approximation continue rend le système différentiable, puis à la fin de l’apprentissage il est converti en portes logiques entièrement discrètes
• Avantages
  • Le circuit final est composé exclusivement de portes logiques binaires, avec une forte efficacité matérielle
  • La logique discrète offre des avantages en termes d’interprétabilité et d’efficacité énergétique

Differentiable Logic Cellular Automata (DiffLogic CA)

• Structure
  • Dans une grille 2D, chaque cellule possède un état sur n bits, et la simulation se déroule selon les étapes Perception → Update
  • Étape de Perception
    • Les informations du voisinage (par canal) sont traitées par des noyaux de circuits logiques
  • Étape d’Update
    • L’état courant et le résultat de la Perception sont fusionnés par un autre circuit logique pour déterminer l’état au pas suivant
• Caractéristiques
  • Chaque cellule agit comme un petit processeur indépendant et distribué, évoluant de manière autonome
  • L’apprentissage se fait en version soft (approximation continue), puis l’inférence en portes hard (binaires), ce qui améliore l’efficacité
  • L’approche partage une philosophie proche des architectures de calcul basées sur les CA comme CAM-8

Expérience 1 : Apprendre le Game of Life

• Objectif
  • Apprendre les règles du Game of Life de Conway avec DiffLogic CA afin de vérifier s’il peut les reproduire parfaitement
• Configuration
  • État de cellule sur 1 bit
  • 16 noyaux pour la Perception (chacun avec une structure de portes 8→4→2→1)
  • 23 couches pour l’Update (16 premières couches à 128 nœuds, puis [64, 32, 16, 8, 4, 2, 1])
  • Apprentissage sur tous les états possibles d’une grille 3x3 (512 au total) afin de prédire exactement l’état de l’étape suivante
• Résultats
  • La loss converge vers 0 et les règles locales du Game of Life sont apprises parfaitement
  • Sur des grilles plus grandes, le modèle reproduit tous les motifs du Game of Life, comme les gliders ou les blocs
  • Le circuit final utilise beaucoup de portes AND et OR

Expérience 2 : Génération de motifs

• Exemple du damier (Checkerboard)
  • Des cellules avec un état sur 8 bits forment un damier 16x16 en 20 étapes
  • 16 noyaux pour la Perception, 16 couches pour l’Update (jusqu’à 256 portes)
  • La loss est calculée en comparant uniquement le canal final au motif cible
• Résultats
  • Le damier est formé avec précision, et la règle est implémentée de manière concise avec seulement quelques portes
  • La même règle passe sans problème à une grille 4 fois plus grande
  • Même si certaines cellules sont désactivées de façon permanente, le motif se dégrade peu ; lorsqu’on les restaure, l’auto-réparation se produit automatiquement
• Asynchronisme
  • Le motif en damier est appris sans difficulté même avec des mises à jour asynchrones
  • Une règle apprise en mode synchrone fonctionne aussi bien en inférence asynchrone
  • Les règles apprises de manière asynchrone tendent à se restaurer un peu plus vite en présence de bruit ou de dommages

Expérience 3 : Faire pousser un lézard

• Objectif
  • Apprendre à former en 12 étapes la silhouette d’un lézard 20x20, afin de vérifier la capacité à générer des formes complexes
• Configuration
  • État sur 128 bits
  • Perception avec 4 noyaux (chacun avec une structure de portes [8, 4, 2, 1]), Update avec 10 couches (8 premières couches à 512 portes, puis [256, 128])
  • Une cellule active unique au centre de la grille, avec conditions aux limites périodiques
• Résultats
  • Le lézard se développe correctement même sur une grande grille (40x40)
  • De très nombreuses portes sont utilisées, mais l’apprentissage reste possible avec un bon réglage des hyperparamètres

Expérience 4 : Apprendre le G en couleurs

• Objectif
  • Générer sur 15 étapes une image couleur 16x16 comprenant 3 canaux RGB, afin de valider la génération de motifs multicanaux
• Configuration
  • État sur 64 bits (les 3 premiers canaux servent de RGB, chaque canal valant 0 ou 1)
  • Perception avec 4 noyaux (chacun [8, 4, 2]), Update avec 11 couches (8 premières couches à 512 portes, puis [256, 128, 64])
  • L’image cible est un motif 16x16 en forme de G, rempli avec l’une des 8 couleurs possibles
• Résultats
  • La loss converge presque à 0, et après 15 étapes le G coloré cible est reproduit avec précision
  • Le circuit utilise beaucoup de portes TRUE et FALSE, avec une présence marquée des portes OR

Résumé et discussion

• Ce qui a été fait
  • Proposition de DiffLogic CA, un modèle de CA entièrement discret mais entraînable
  • Reproduction de règles classiques comme le Game of Life, et démonstration de la capacité à générer des motifs tels qu’un damier, un lézard ou un G coloré
  • La structure en circuits logiques discrets laisse espérer à la fois une interprétation intuitive et une bonne efficacité matérielle
• Apport
  • La démonstration qu’il est possible d’apprendre, sur la base de portes logiques discrètes, des motifs auto-organisés du type de ceux observés avec les NCA
  • En tenant compte de propriétés comme la récupération après dommage ou les mises à jour asynchrones, l’approche semble prometteuse pour le calcul distribué et tolérant aux pannes
• Limites et pistes futures
  • L’apprentissage de motifs ou d’images complexes nécessite un réglage approprié des hyperparamètres
  • Il reste possible d’explorer des portes de type LSTM ou des structures capables d’oublier efficacement l’état, afin de permettre des motifs encore plus riches
  • Le travail peut être étendu vers l’optimisation de la taille des circuits et l’amélioration de la stabilité de l’apprentissage
• Conclusion
  • DiffLogic CA est une approche prometteuse qui pourrait mener vers des formes théoriques de calcul distribué comme la matière programmable (Programmable Matter) ou le Computronium
  • À la fois entièrement discret et entraînable, il présente un potentiel comme fondation de futurs systèmes distribués

[GN⁺]

Commentaires sur Hacker News

• Très intéressant. Je collectionne de nouveaux substrats de machines de Turing universelles. Je les collectionne comme des Pokémon pour des expériences de programmation génétique. J’ai déjà utilisé des automates cellulaires (CA), mais cette approche est bien plus séduisante. Je n’avais jamais envisagé de modéliser le noyau comme un circuit logique numérique
  • La logique booléenne, les portes et les contraintes des circuits créent une texture intéressante qui façonne le paysage de fitness. Les paramètres résultants peuvent être directement traduits en implémentation matérielle ou compilés en programmes simples après une étape d’optimisation supplémentaire. Cela semble meilleur que la magie opaque des nombres à virgule flottante d’une boîte noire avec des milliards de paramètres
• J’aime utiliser les automates cellulaires dans l’art. C’est étonnant de voir quels motifs peuvent émerger. Il faut que j’essaie DLCA
• Très intéressant. La question posée par Michael Levin sur la manière dont les cellules animales peuvent coopérer sans hiérarchie m’a marqué. Il existe une expérience où les cellules de l’œil d’un embryon de grenouille retournent à leur position d’origine. On n’avait pas de réponse à la question de savoir comment les cellules savent quand s’arrêter
  • Comprendre l’organisation non hiérarchique est important pour comprendre le fonctionnement de la société. C’est aussi important pour résoudre le dilemme du prisonnier à différentes échelles
  • Il s’agit aussi de comprendre et de modéliser la complexité
  • Pour la première fois, j’ai l’impression de voir la capacité de modéliser ce genre de choses. Cela peut aller dans de nombreuses directions. Étonnant
• Ces derniers temps, j’ai beaucoup réfléchi à l’« intelligence ». Nous semblons être à un moment décisif dans la compréhension de son fonctionnement. L’intelligence est un comportement émergent de la nature, pas si différent de la mécanique newtonienne classique ou de l’électricité. Au final, tout se ramène à des règles simples
  • Et si tout ce qui n’est pas discret dans le cerveau n’était que de l’« infrastructure » ? Et si cela servait seulement à soutenir un processus central fondamentalement simple mais crucial, celui qui accomplit réellement le travail ? Et si tout se ramenait à des portes logiques et à des signaux électriques ?
  • Une époque fascinante s’annonce
• Ils sont particulièrement séduisants, notamment par leur capacité de généralisation. Mais quelle est la vision ? Que pourra-t-on en faire à l’avenir ? Sur le plan philosophique, qu’est-ce que cela peut nous apprendre sur le monde ? Je sais que les automates cellulaires 1D sont équivalents à une machine de Turing. Donc les NCA / ceux-ci ne sont pas particulièrement surprenants
• C’est une percée. Il ne s’agit pas de damiers ou de lézards. Les équations différentielles de Navier-Stokes sont les règles de mise à jour qui gouvernent le mouvement des fluides. Toute la complexité, comme la formation des nuages ou le mouvement des flammes, est régie par des lois simples. Découvrir cette équation à partir d’échantillons réels, c’est cela la science. On pourrait appliquer un modèle DLCA à des enregistrements vidéo de fumée pour dériver les équations de Navier-Stokes. Si l’on considère que les règles de mise à jour elles-mêmes peuvent changer selon d’autres règles de mise à jour, on entre dans un domaine passionnant. C’est peut-être pour cela que les neurones du cerveau sont connectés à des milliers d’autres neurones
  • Les dirigeants de Google balayeront cette découverte en disant qu’elle n’a rien à voir avec leur activité publicitaire. Quelques années plus tard, quand DLCA aura bouleversé le monde, ils prétendront que cela a été découvert par leurs employés
• Article très intéressant. J’ai une question : comme les mises à jour sont effectuées à l’aide d’une descente de gradient « globale », les portes cellulaires ne sont pas réellement parallèles
  • Existe-t-il une méthode plausible d’ajustement des poids strictement locale ?
• La relaxation continue de l’algèbre de Boole est une vieille idée. La synthèse de circuits est un domaine bien étudié. Google a remporté une compétition il y a deux ans. Je me demande s’ils ont essayé d’appliquer l’apprenant au jeu de données du concours IWLS. Sinon, pourquoi pas ?
• Pourrait-on l’utiliser pour le challenge ARC-AGI ? Pourrait-on le combiner avec les approches récentes ?
• Auto-promo, mais c’est lié => Robustesse et problème de l’arrêt dans le développement artificiel multicellulaire (2011)
  • Une automate cellulaire dont la règle de mise à jour combine des perceptrons et une diffusion isotrope. Les poids du réseau neuronal étaient optimisés pour que l’automate cellulaire puisse dessiner une image. Auto-réparation (c’est-à-dire reconstruction de l’image lorsqu’elle était perturbée)
  • À l’époque, la différenciation automatique n’était pas aussi accessible qu’aujourd’hui. J’ai optimisé les poids avec des stratégies évolutionnaires. Bien sûr, utiliser la descente de gradient serait bien meilleur