- DiffLogic CA est une approche d’automates cellulaires qui combine les Neural Cellular Automata et les Differentiable Logic Gate Networks afin d’apprendre des règles locales par descente de gradient tout en conservant des états de cellule discrets
- Chaque cellule possède un état sous forme de vecteur binaire à n dimensions, et les étapes de perception comme de mise à jour sont traitées par des réseaux de portes logiques pour calculer directement l’état suivant
- Dans l’expérience Conway’s Game of Life, le modèle a appris une étape sur les 512 configurations d’une grille périodique 3x3 et a ainsi acquis l’ensemble des règles ; même en inférence dure, il reproduit des motifs représentatifs comme glider, block, loaf et boat
- L’expérience de génération de motifs produit un damier 16x16 en 20 étapes, fonctionne aussi sur une grille 4 fois plus grande et sur une durée 4 fois plus longue, et montre une tolérance aux pannes sur des cellules endommagées ainsi qu’une auto-réparation après réactivation
- Le modèle génère aussi un contour de lizard plus complexe et un G RGB en 8 couleurs, mais l’apprentissage de structures complexes a nécessité beaucoup de réglage d’hyperparamètres, et les NCA hiérarchiques ainsi que des portes de type LSTM restent des pistes d’amélioration
Le problème visé par DiffLogic CA
- Les automates cellulaires sont généralement abordés en définissant d’abord des règles locales, puis en observant les motifs émergents qui en résultent
- DiffLogic CA explore une méthode permettant, lorsqu’un motif complexe est souhaité, d’apprendre les règles locales qui le produisent de façon entièrement différentiable
- Les Neural Cellular Automata existants peuvent apprendre des motifs et comportements arbitraires, mais ils ne fonctionnent pas intrinsèquement dans un espace d’états discret, ce qui réduit leur interprétabilité et impose le coût de multiplications matricielles pour les mises à jour d’états continus
- Les Differentiable Logic Gate Networks ont été utilisés pour découvrir des circuits logiques combinatoires, mais leur fonctionnement n’avait pas encore été démontré dans une configuration NCA récursive à la fois dans l’espace et dans le temps
- L’ensemble des expériences peut être reproduit dans le notebook
Structure de base des Neural Cellular Automata
- Les Neural Cellular Automata combinent les automates cellulaires classiques avec le deep learning afin d’apprendre les règles de mise à jour par descente de gradient, au lieu de les concevoir à la main
- Chaque cellule de Growing-NCA possède un vecteur d’état à n dimensions sur une grille 2D
- Les 3 canaux RGB représentent la couleur de la cellule
- Le canal alpha représente la viabilité de la cellule ; si la valeur alpha est supérieure à 0,1, la cellule est considérée comme vivante
- Les autres hidden channels transmettent des informations plus complexes sur l’environnement alentour
- La mise à jour se fait en deux étapes
- Étape de perception : un filtre de Sobel est appliqué canal par canal pour approximer les gradients spatiaux et produire un perception vector combinant l’état courant de la cellule et les informations de son voisinage
- Étape de mise à jour : un réseau de neurones d’environ 8 000 paramètres est appliqué de façon identique à toutes les cellules pour déterminer comment chacune doit changer
- Toutes les opérations étant différentiables, le système entier peut apprendre un motif ou un comportement donné
Méthode des Differentiable Logic Gate Networks
- Les Deep Differentiable Logic Gate Networks utilisent comme unités de base des portes logiques telles que AND, OR, XOR, plutôt que des neurones artificiels
- Le réseau est composé de couches de portes, et chaque porte possède une structure creuse recevant ses entrées de deux portes de la couche précédente
- Les connexions sont initialisées aléatoirement puis ne changent pas pendant l’apprentissage ; l’apprentissage détermine uniquement quelle opération logique chaque porte exécute
- Pendant l’apprentissage, les portes logiques discrètes ne sont pas utilisées directement ; deux mécanismes sont employés
- Relaxation continue : une opération discrète comme hard AND est remplacée par une version différentiable acceptant des entrées entre 0 et 1
- Sélection probabiliste des portes : chaque porte possède une distribution de probabilité sur les 16 opérations binaires possibles pour deux entrées, et apprend un paramètre à 16 dimensions exprimé par softmax
- Une fois l’apprentissage terminé, chaque porte est fixée sur l’opération ayant la probabilité la plus élevée, et l’inférence n’exécute plus que des opérations binaires pures
- Pour stabiliser l’apprentissage, la distribution initiale des portes est biaisée vers les portes pass-through
Structure de DiffLogic CA
- DiffLogic CA suit la structure en grille 2D des NCA, mais représente l’état de chaque cellule comme un vecteur binaire à n dimensions
- L’état de cellule et les canaux sont utilisés avec le même sens, et le vecteur d’état binaire sert de mémoire de travail stockant les informations de l’itération précédente
- L’étape de perception utilise, au lieu d’un filtre de Sobel, des noyaux fondés sur des réseaux de portes logiques
- Chaque noyau est un circuit distinct avec une structure de connexions fixe, et le type des portes est appris
- Les noyaux sont calculés canal par canal
- Chaque circuit utilise 4 couches conçues pour calculer les interactions entre la cellule centrale et les cellules voisines
- L’étape de mise à jour concatène l’ancienne mémoire de la cellule et les informations reçues de ses voisines, puis les donne à un Differentiable Logic Gate Network pour calculer le nouvel état
- Contrairement aux NCA standards, il ne s’agit pas d’une mise à jour de type ODE ajoutant progressivement à l’état : l’état binaire suivant est produit directement
- Une ronde de fonctionnement peut être vue comme deux registres
- Le registre gris contient l’état existant de la cellule
- Le registre orange stocke le résultat de l’étape de perception
- Après la mise à jour, le nouvel état est écrit dans le registre gris, et le registre orange est vidé pour la ronde suivante
- Cette structure fonctionne comme un réseau de petits ordinateurs indépendants où chaque cellule communique avec ses voisines et prend des décisions à partir de ses observations
Expérience 1 : apprentissage de Conway’s Game of Life
- Game of Life est un automate cellulaire binaire où chaque cellule vit ou meurt à la génération suivante selon l’état de ses 8 voisines et son propre état courant
- Les règles sont au nombre de quatre
- Une cellule morte devient vivante à la génération suivante si elle a exactement 3 voisines vivantes
- Une cellule vivante survit si elle a 2 ou 3 voisines vivantes
- Une cellule vivante meurt si elle a moins de 2 voisines vivantes
- Une cellule vivante meurt si elle a plus de 3 voisines vivantes
- Comme cette expérience cible une règle qui ne dépend pas de la répétition des états précédents, l’état de cellule est fixé à 1 bit
- La configuration du modèle est la suivante
- 16 noyaux de circuits de perception
- La structure de nœuds de chaque noyau de perception est
[8, 4, 2, 1] - Le réseau de mise à jour comporte 23 couches
- Les 16 premières couches ont chacune 128 nœuds
- Les couches suivantes sont
[64, 32, 16, 8, 4, 2, 1]
- Les données d’apprentissage incluent les 512 configurations possibles d’une grille périodique 3x3
- Comme l’état suivant de chaque cellule est déterminé par elle-même et ses 8 voisines, il existe 512 configurations 3x3
- Prédire correctement tous les états suivants en une étape revient à apprendre l’ensemble des règles de Game of Life
- La fonction de perte additionne les différences au carré entre la grille prédite et la grille de référence
- La soft loss comme la hard loss convergent totalement, et en inférence dure, le circuit appris reproduit les motifs de Game of Life même sur des grilles plus grandes
- Le nombre de portes actives est de 336, hors pass-through A et B ; OR et AND sont les plus utilisées dans le réseau de perception comme dans celui de mise à jour
- Le circuit généré peut être manipulé directement via le circuit Game of Life
Expérience 2 : génération d’un motif en damier
- L’expérience de génération de motifs est configurée pour apprendre une règle qui fait évoluer un état initial arbitraire vers une image cible
- La perte n’étant calculée qu’au dernier timestep, le modèle doit trouver des règles de transition discrètes sans supervision étape par étape intermédiaire
- L’état de cellule est sur 8 bits, et DiffLogic CA est itéré pendant 20 étapes
- La configuration du modèle est la suivante
- 16 noyaux de circuits de perception
- Chaque noyau possède 8, 4 et 2 portes selon les couches
- Le réseau de mise à jour comporte 16 couches
- Les 10 premières couches ont chacune 256 portes
- Les couches suivantes sont
[128, 64, 32, 16, 8, 8]
- La fonction de perte est la somme des différences au carré, au dernier timestep, entre le premier canal de la grille prédite et la grille cible
- Le modèle est entraîné à reconstruire un motif de damier 16x16 en 20 étapes
- La soft loss comme la hard loss convergent, et une formation de motif nette apparaît dans le premier canal
- Bien que le modèle n’ait aucun biais directionnel intégré, le motif présente une propriété de propagation du bas gauche vers le haut droit
- Le nombre de portes actives est de 22, hors pass-through A et B, et après élagage, toute la fonction de génération du damier peut en pratique être implémentée avec 5 portes logiques
- Le circuit fonctionne même avec une grille 4 fois plus grande et une durée 4 fois plus longue, et la règle apprise n’est donc pas une forme de surapprentissage à une taille de grille donnée
Dommages, auto-réparation et mises à jour asynchrones
- Dans l’expérience du damier, deux expériences de dommages sont menées en supposant que certaines cellules tombent en panne
- Désactiver définitivement les cellules d’une grande zone pour simuler des composants défectueux
- Réactiver les cellules désactivées après un certain nombre d’étapes
- Le système conserve l’intégrité du motif même en cas de dommage permanent et régénère le bon motif après le retour en ligne des cellules désactivées
- Bien que la tolérance aux pannes et l’auto-réparation n’aient pas été explicitement conçues, le comportement observé montre une localisation des dommages et évite un effondrement brutal de la fonction globale
- Dans l’expérience de mise à jour asynchrone, toutes les cellules ne sont pas mises à jour simultanément ; à chaque étape, seul un sous-ensemble aléatoire de cellules est mis à jour
- L’apprentissage asynchrone devait être plus difficile qu’avec les NCA existants
- À chaque étape, il faut produire un nouvel état complet, et non un incrément
- Il faut gérer des combinaisons où les cellules voisines ont de l’avance ou du retard de plusieurs étapes les unes par rapport aux autres
- Sur le damier, l’apprentissage asynchrone réussit relativement facilement et reconstruit le motif cible en 50 étapes à partir du même état initial, même avec des ordres de mise à jour différents
- Les règles existantes apprises en mode synchrone fonctionnent aussi lorsqu’elles sont appliquées en inférence asynchrone
- Dans un test qui désactive aléatoirement, à chaque timestep d’inférence, un rectangle de 10x10 pixels dans la zone de l’image, les cellules entraînées de façon asynchrone récupèrent un peu plus vite après les dommages
- En mesurant l’erreur par la somme des différences absolues entre l’objectif et l’image reconstruite, l’apprentissage asynchrone renforce la robustesse face à ce type de perturbation
Expérience 3 : croissance du contour de lizard
- L’expérience lizard est un hommage au travail NCA original et vérifie si DiffLogic CA peut apprendre une forme arbitraire
- Contrairement au damier, qui est un motif régulier fortement compressible, le contour de lizard exige davantage de mémorisation
- La configuration est la suivante
- L’état de cellule est sur 128 bits
- DiffLogic CA est itéré pendant 12 étapes
- Il y a 4 noyaux de circuits de perception
- Chaque noyau possède 8, 4, 2 et 1 portes selon les couches
- Le réseau de mise à jour comporte 10 couches
- Les 8 premières couches ont chacune 512 portes
- Les dernières couches sont
[256, 128]
- Le modèle est entraîné à générer un motif lizard 20x20 en 12 étapes
- La condition initiale est une seed centrale, comme dans les NCA, pour briser la symétrie, et des conditions aux limites périodiques sont appliquées aux bords de la grille
- Évalué sur une grille plus grande de 40x40, le modèle génère aussi correctement le motif de croissance lizard, ce qui montre que la solution ne repose pas sur les conditions aux limites
- La soft loss et la hard loss convergent toutes deux vers 0
- Le nombre de portes actives est de 577, hors pass-through A et B
- Les noyaux de perception utilisent principalement des portes TRUE, tandis que le circuit de mise à jour utilise presque toutes les portes disponibles
- L’apprentissage de génération de motifs complexes est difficile à optimiser et nécessite un réglage d’hyperparamètres étendu
Expérience 4 : génération d’un G coloré
- Les expériences précédentes portant en pratique sur des images monochromes, une expérience est menée avec un état cible plus complexe : générer une image couleur 16x16
- L’état de cellule compte 64 canaux, et le modèle génère une lettre G colorée pendant 15 étapes
- Les trois premiers canaux représentent les valeurs RGB comme dans la convention standard des NCA, mais ici chaque valeur est limitée à une représentation binaire 0 ou 1, créant une palette de 8 couleurs
- La configuration du modèle est la suivante
- 4 noyaux de circuits de perception
- Chaque noyau est constitué de 3 couches comportant 8, 4 et 2 portes
- Le réseau de mise à jour comporte 11 couches
- Les 8 premières couches ont chacune 512 nœuds
- Les 3 dernières couches sont
[256, 128, 64]
- L’état initial est entièrement à 0, et aucune condition aux limites périodique n’est utilisée
- La fonction de perte additionne, au dernier timestep, les différences au carré entre la grille prédite et la grille cible, uniquement sur les trois premiers canaux, c’est-à-dire les canaux 0, 1 et 2
- La soft loss et la hard loss convergent, et le modèle reconstruit le G coloré en 15 étapes
- Le nombre de portes actives est de 927, hors pass-through A et B
- Les portes TRUE et FALSE sont beaucoup utilisées dans le réseau de perception comme dans le réseau de mise à jour, et les portes OR sont les plus utilisées dans le réseau de mise à jour
- Ce circuit s’avère plus complexe que ceux des expériences précédentes, à la fois en recherche d’hyperparamètres et en taille de circuit
Questions ouvertes et pistes d’amélioration
- DiffLogic CA propose une nouvelle structure et méthode d’apprentissage de NCA qui utilise des états de cellule entièrement discrets et les met à jour via des circuits binaires récursifs appris
- En remplaçant les composants de réseaux de neurones par des Deep Differentiable Logic Networks, il combine la flexibilité de l’apprentissage différentiable avec des portes logiques discrètes
- Les expériences de reproduction de Game of Life et de génération de motifs montrent que les portes logiques différentiables peuvent être appliquées aux automates cellulaires
- Les résultats confirment ainsi que les Differentiable Logic Gate Networks peuvent être appris efficacement même dans des structures récursives
- Le modèle actuel démontre sa capacité à apprendre des motifs, mais l’apprentissage de formes et de structures plus complexes reste difficile
- Parmi les pistes d’amélioration figurent des structures NCA hiérarchiques et des portes spécialisées aidant à oublier l’état
- Intégrer des mécanismes de gating de type LSTM au processus de mise à jour d’état permettrait de combiner plus richement les états passés et les nouveaux états candidats calculés, afin d’accroître la dynamique et l’expressivité du modèle
1 commentaires
Avis sur Hacker News
Très intéressant. Je cherchais de nouveaux substrats de machine de Turing universelle, et je les collectionnais un peu comme des Pokémon pour des expériences de programmation génétique. J’avais déjà bricolé avec des automates cellulaires, rule 30/110 et autres, mais cette approche est bien plus convaincante.
Je n’avais pas pensé à modéliser le noyau comme un circuit logique numérique. Les contraintes de la logique booléenne, des portes et des circuits semblent créer une texture intéressante pour façonner le paysage d’aptitude. Les paramètres obtenus peuvent être directement convertis en implémentation matérielle, ou compilés en programme simple après une étape d’optimisation supplémentaire. Cela paraît préférable à la manipulation de nombres à virgule flottante quasi magiques dans une boîte noire de dizaines de milliards de paramètres.
Passionnant. Michael Levin est celui qui a le mieux formulé la question de savoir comment des cellules animales peuvent coopérer sans structure hiérarchique. Il existe par exemple des expériences en biologie où, même si l’on retire des cellules oculaires d’un embryon de grenouille, elles migrent vers l’endroit où l’œil doit se trouver.
La question à laquelle, selon moi, il n’a pas vraiment répondu est : comment les cellules savent-elles quand s’arrêter ? Comprendre l’organisation non hiérarchique est aussi essentiel pour comprendre le fonctionnement des sociétés, et pour résoudre le dilemme du prisonnier à différentes échelles dans un monde auto-organisé. C’est aussi comprendre et modéliser la complexité brute. C’est la première fois que je vois une capacité à modéliser ce genre de choses, et les directions possibles à partir de là semblent vraiment nombreuses.
Je réfléchis beaucoup à l’intelligence ces temps-ci, et j’ai l’impression que nous sommes à un point décisif où nous allons découvrir comment elle fonctionne, ou du moins faire fortement progresser notre compréhension. L’intelligence ressemble à un comportement émergent naturel, pas si différent de la mécanique newtonienne classique ou de l’électricité.
Au bout du compte, cela semble se ramener à des règles simples. Et si tout ce qui, dans le cerveau, n’est pas discret n’était en fait qu’une infrastructure soutenant quelques processus centraux simples mais essentiels qui font le vrai travail ? Et si, tout au fond, il ne restait que des portes logiques et des signaux électriques ? Les temps à venir s’annoncent passionnants.
Cette approche a quelque chose de particulièrement séduisant, notamment du point de vue de sa capacité de généralisation. Mais je me demande quelle est la grande vision. Qu’est-ce que cela nous permettra de faire à l’avenir ? Philosophiquement, qu’est-ce que cela nous apprend sur le monde ? Nous savons déjà que les automates cellulaires unidimensionnels sont équivalents à Turing, donc d’un certain point de vue, les NCA ou ce type de méthode ne sont pas si surprenants.
Il y aura des automates cellulaires qui interagiront avec leur environnement, et des automates qui interagiront à la fois avec des systèmes de bas niveau et des institutions de haut niveau. Avec une certaine approximation, les humains ne sont eux aussi que des cellules individuelles interagissant au sein de tels réseaux. À mon avis, l’avenir de l’intelligence n’est pas dans les LLM, mais dans des systèmes d’automates dotés d’une dimension métabolique. Des automates qui coévoluent, consomment de l’énergie, produisent de la valeur, se concurrencent et se modélisent mutuellement.
Nous ne sommes pas remplacés ; nous participons à une transformation où la frontière entre systèmes technologiques et systèmes cellulaires s’estompe puis finit par disparaître. Je suis très reconnaissant de pouvoir en être témoin. Référence : https://x.com/zzznah/status/1803712504910020687
J’aime jouer avec les automates cellulaires dans mes travaux artistiques. C’est étonnant de voir quels motifs peuvent émerger. Exemple : https://gods.art/math_videos/hex_func27l_21.html
Je devrais aussi essayer ce DLCA.
Il y a beaucoup de belles idées ici. C’est peut-être une petite observation, mais ce calcul a un état. Chaque cellule possède une mémoire et une perception de son environnement immédiat.
À l’inverse, les réseaux neuronaux modernes sont pour la plupart sans état. Je me demande par exemple s’il y a eu des travaux sur des LLM avec état.
Auto-promo, mais très pertinent : Robustness and the Halting Problem for Multicellular Artificial Ontogeny (2011)
Il s’agissait d’un automate cellulaire dont la règle de mise à jour était un perceptron combiné à une diffusion isotrope. Nous optimisions les poids du réseau neuronal pour que l’automate cellulaire dessine une image, puis, en cas de perturbation, qu’il la reconstruise grâce à l’auto-guérison. À l’époque, la différentiation automatique n’était pas aussi accessible qu’aujourd’hui, donc nous optimisions les poids avec des stratégies évolutives. Bien sûr, la descente de gradient aurait probablement été bien meilleure.
Peut-on utiliser cela pour le défi ARC-AGI ? Il serait peut-être possible de le combiner avec cette approche récente : https://news.ycombinator.com/item?id=43259182
Vraiment impressionnant. Je suis un lecteur silencieux de longue date, et comme quelqu’un qui utilise beaucoup la modélisation et la simulation, j’y vois un grand potentiel pour mieux comprendre le comportement émergent de modèles complexes d’agents.
J’aimerais voir cela appliqué à des modèles comme prédateur/proie, ainsi qu’à d’autres modèles qui semblent simples mais produisent, à très grande échelle, des résultats émergents complexes. Je compte suivre ce travail de près.
Le motif en damier du résultat ressemble à l’inverse du motif cible, c’est-à-dire à un NOT. Pourtant, il n’en est pas fait mention. Je me demande si ce n’est pas assez important pour être signalé, ou si je passe à côté de quelque chose.