Autómatas celulares lógicos diferenciables

• Explora cómo hacer ingeniería inversa de patrones complejos a partir de reglas locales simples
• Un enfoque que combina la capacidad de aprendizaje de los Neural Cellular Automata (NCA) con Differentiable Logic Gate Networks para obtener reglas locales discretas mediante aprendizaje
  • "¿Se pueden aprender las reglas de Conway's Game of Life?"
  • "¿Se pueden reproducir patrones complejos como en NCA y aprender estructuras recurrentes espaciotemporales?"

Introduction

• Los Cellular Automata (CA) forman patrones complejos e impredecibles a partir de reglas locales simples
• Tradicionalmente, en los CA las reglas eran diseñadas directamente por humanos, pero aquí se presenta un método para “aprender” en sentido inverso reglas locales que satisfagan un patrón o comportamiento objetivo dado de antemano
• En particular, Neural Cellular Automata (NCA) se han diseñado para combinar la estructura de los CA con técnicas de deep learning y permitir aprendizaje en un espacio continuo
• Differentiable Logic Gate Networks es una técnica que aproxima de forma continua compuertas lógicas (AND, OR, XOR, etc.) para entrenarlas y luego volver a convertirlas en circuitos lógicos discretos
• Al combinar estas dos ideas, se propone DiffLogic CA, un modelo de CA completamente discreto y entrenable
• Puede verse como un pequeño paso hacia la materia programable (Programmable Matter) o el Computronium
• Este texto sigue el siguiente flujo
  • Resumen de Neural Cellular Automata
  • Resumen de Differentiable Logic Gate Networks
  • Estructura de DiffLogic CA que combina ambas metodologías
  • Experimento de aprendizaje de las reglas de Conway’s Game of Life
  • Experimentos de aprendizaje para generar patrones complejos (tablero ajedrezado, lagartija, imágenes a color, etc.)

Recap – Neural Cellular Automata(NCA)

• Concepto
  • Un sistema que reemplaza las reglas tradicionales de CA por una forma entrenable mediante redes neuronales
  • Cada celda tiene múltiples canales (estado) y forma patrones complejos mediante interacciones locales
  • Usa filtros Sobel y otros para obtener información del entorno, y la red neuronal decide los cambios de estado
• Características
  • Todo el proceso de cálculo es diferenciable, por lo que puede entrenarse para crear el patrón deseado
  • Conserva los elementos clave de los CA, como paralelismo, localidad y cálculo basado en estados, mientras incorpora técnicas de deep learning

Recap – Differentiable Logic Gate Networks(DLGNs)

• Idea central
  • En lugar de una NN tradicional, se entrenan compuertas lógicas (AND, OR, XOR, etc.) aproximadas de forma continua (soft gates)
  • Durante la etapa de entrenamiento, las compuertas operan de forma continua, y en la inferencia final ejecutan operaciones binarias reales
• Proceso de aprendizaje
  • Se aprende una distribución de probabilidad sobre las 16 operaciones lógicas posibles de una compuerta, que finalmente converge a una operación específica
  • La aproximación continua la hace diferenciable, y cuando termina el entrenamiento se convierte en compuertas lógicas totalmente discretas
• Ventajas
  • El circuito final está compuesto completamente por compuertas lógicas binarias, lo que lo hace muy eficiente en hardware
  • Al estar basado en lógica discreta, tiene ventajas en interpretabilidad y eficiencia energética

Differentiable Logic Cellular Automata (DiffLogic CA)

• Estructura
  • En una cuadrícula 2D, cada celda tiene un estado de n bits y la simulación se realiza en etapas de Perception → Update
  • Etapa de Perception
    • La información de los vecinos (por canal) se procesa con kernels de circuitos lógicos
  • Etapa de Update
    • El estado actual y el resultado de Perception se integran con otro circuito lógico para determinar el estado del siguiente instante
• Características
  • Cada celda funciona como un procesador pequeño e independiente que se mueve de forma distribuida
  • Entrena con soft (aproximación continua) y hace inferencia con compuertas hard (binarias), logrando alta eficiencia
  • Tiene una filosofía similar a arquitecturas de cómputo basadas en CA como CAM-8

Experiment 1: Learning Game of Life

• Objetivo
  • Aprender las reglas de Conway's Game of Life con DiffLogic CA y comprobar si puede reproducirlas por completo
• Configuración
  • Estado de celda de 1 bit
  • 16 kernels en Perception (cada uno con estructura de compuertas 8→4→2→1)
  • 23 capas en Update (las primeras 16 capas con 128 nodos, luego [64, 32, 16, 8, 4, 2, 1])
  • Se entrenan todos los estados posibles (512) en una cuadrícula 3x3 para predecir con exactitud el estado del siguiente paso
• Resultados
  • La pérdida de entrenamiento se acerca a 0 y aprende perfectamente la regla local de Game of Life
  • En cuadrículas más grandes reproduce todos los patrones, como gliders y bloques, igual que el Game of Life real
  • En el circuito final se usan muchas compuertas AND y OR

Experiment 2: Pattern Generation

• Ejemplo de tablero ajedrezado (Checkerboard)
  • Celdas con estado de 8 bits forman un tablero ajedrezado de 16x16 en 20 pasos
  • 16 kernels en Perception y 16 capas en Update (hasta 256 compuertas)
  • La pérdida se calcula comparando solo el canal final con el patrón objetivo
• Resultados
  • Forma el tablero ajedrezado con precisión, y la regla se implementa de manera compacta con apenas unas cuantas compuertas
  • La misma regla escala sin problemas a una cuadrícula 4 veces más grande
  • Incluso si algunas celdas se desactivan de forma permanente, el patrón no se rompe demasiado, y al restaurarlas se autocura automáticamente
• Asincronía
  • Incluso entrenando con actualizaciones asíncronas, aprende el patrón ajedrezado sin problema
  • Las reglas entrenadas de forma síncrona también funcionan bien en inferencia asíncrona
  • Las reglas entrenadas de forma asíncrona tienden a recuperarse un poco más rápido ante ruido o daño

Experiment 3: Growing a Lizard

• Objetivo
  • Entrenar la formación de la silueta de una lagartija de 20x20 en solo 12 pasos para comprobar la posibilidad de generar formas complejas
• Configuración
  • Estado de 128 bits
  • Perception con 4 kernels (cada uno con estructura de compuertas [8, 4, 2, 1]), Update con 10 capas (las primeras 8 capas con 512 compuertas, luego [256, 128])
  • Una sola celda activa en el centro de la cuadrícula y condiciones de frontera periódicas
• Resultados
  • La lagartija crece correctamente incluso en una cuadrícula más grande (40x40)
  • Se usan muchísimas compuertas, pero el entrenamiento es posible con el ajuste adecuado de hiperparámetros

Experiment 4: Learning the G with colors

• Objetivo
  • Generar una imagen a color de 16x16 con 3 canales RGB a lo largo de 15 pasos para validar la generación de patrones multicanal
• Configuración
  • Estado de 64 bits (los primeros 3 canales se usan como RGB, y cada canal es 0 o 1)
  • Perception con 4 kernels (cada uno [8, 4, 2]), Update con 11 capas (las primeras 8 capas con 512 compuertas, luego [256, 128, 64])
  • La imagen objetivo es un patrón de G de 16x16 rellenado con uno de 8 colores posibles
• Resultados
  • La pérdida se entrena hasta quedar cerca de 0, y tras 15 pasos reproduce con precisión la G objetivo a color
  • El circuito usa muchas compuertas TRUE y FALSE, y las compuertas OR destacan especialmente

Summary and Discussion

• Qué se hizo
  • Se propuso DiffLogic CA, un modelo de CA completamente discreto y entrenable
  • Reproduce reglas clásicas como Game of Life y muestra capacidad para generar patrones como tablero ajedrezado, lagartija y G a color
  • Al estar compuesto por circuitos lógicos discretos, se espera buena interpretabilidad y eficiencia en hardware
• Importancia
  • Demuestra que los patrones autoorganizados que muestra NCA también pueden aprenderse con compuertas lógicas discretas
  • Considerando propiedades como recuperación ante daño o actualización asíncrona, tiene alto potencial para aplicaciones en cómputo distribuido y tolerante a fallos (robust)
• Limitaciones y trabajo futuro
  • Al aprender imágenes o patrones complejos, se requiere un ajuste apropiado de hiperparámetros
  • Hay margen para explorar compuertas tipo LSTM o estructuras que olviden estado de forma eficiente, permitiendo formar patrones más ricos
  • Puede ampliarse optimizando el tamaño del circuito y mejorando la estabilidad del entrenamiento
• Conclusión
  • DiffLogic CA es un enfoque prometedor que puede conectarse con direcciones teóricas de cómputo distribuido como la materia programable (Programmable Matter) o el Computronium
  • Al ser completamente discreto y entrenable, tiene potencial para convertirse en base de futuros sistemas distribuidos

[GN⁺]

Comentarios en Hacker News

• Muy interesante. Estoy coleccionando nuevos sustratos de máquinas de Turing universales. Los colecciono como si fueran Pokémon para experimentos de programación genética. Ya había usado autómatas celulares (CA), pero este enfoque es mucho más atractivo. Nunca se me había ocurrido modelar el kernel como si fuera un circuito de lógica digital
  • La lógica booleana, las compuertas y las restricciones de los circuitos generan una textura interesante que construye el paisaje de aptitud. Los parámetros resultantes podrían convertirse directamente en implementaciones de hardware o compilarse en programas sencillos tras una etapa adicional de optimización. Parece mejor que la mágica coma flotante de una caja negra con decenas de miles de millones de parámetros
• Me gusta usar autómatas celulares en el arte. Me sorprende qué tipo de patrones pueden aparecer. Creo que tendré que probar DLCA
• Muy interesante. Me impresionó la pregunta que planteó Michael Levin sobre cómo las células animales pueden cooperar sin jerarquías. Hay un experimento en el que las células oculares de un embrión de rana se desplazan a su ubicación original. No había respuesta sobre cómo las células saben cuándo deben detenerse
  • Entender la organización no jerárquica es importante para comprender cómo funciona la sociedad. También es importante para resolver dilemas del prisionero a distintas escalas
  • También se trata de comprender y modelar la complejidad
  • Por primera vez veo la capacidad de modelar este tipo de cosas. Puede avanzar en muchas direcciones. Sorprendente
• Últimamente he estado pensando mucho en la "inteligencia". Parece que estamos en un punto decisivo para entender cómo funciona. La inteligencia es un comportamiento emergente, no muy distinto de la mecánica newtoniana clásica o la electricidad. Al final, se reduce a reglas simples
  • ¿Y si todo lo no discreto del cerebro fuera solo "infraestructura"? ¿Y si solo sostuviera un proceso central fundamentalmente simple pero importante que realiza el trabajo real? ¿Y si todo se redujera a compuertas lógicas y señales eléctricas?
  • Se vienen tiempos interesantes
• Son especialmente atractivos por su capacidad de generalización. Pero ¿cuál es la visión? ¿Qué podrían hacer en el futuro? Filosóficamente, ¿qué podrían enseñarnos sobre el mundo? Sé que los autómatas celulares 1D son equivalentes a Turing. Así que NCA/esto no es especialmente sorprendente
• Es un descubrimiento revolucionario. No se trata de tableros de ajedrez ni de lagartijas. Las ecuaciones diferenciales de Navier-Stokes son reglas de actualización que gobiernan el movimiento de los fluidos. Toda la complejidad, desde la formación de nubes hasta el movimiento de las llamas, está gobernada por leyes simples. Descubrir esa ecuación a partir de muestras reales es ciencia. Se podría aplicar un modelo DLCA a grabaciones de video de humo para derivar las ecuaciones de Navier-Stokes. Si además consideramos que las propias reglas de actualización pueden cambiar según otras reglas de actualización, entraríamos en un territorio interesante. Tal vez esa sea la razón por la que las neuronas del cerebro están conectadas con miles de otras neuronas
  • Los ejecutivos de Google descartarán este descubrimiento por no estar relacionado con el negocio publicitario. Unos años después, cuando DLCA ponga el mundo de cabeza, dirán que lo descubrió uno de sus empleados
• Es un artículo muy interesante. Tengo una pregunta: como se actualiza usando descenso de gradiente "global", las compuertas de las celdas no son realmente paralelas
  • ¿Existe alguna posibilidad de un método de ajuste de pesos estrictamente local?
• La relajación continua del álgebra de Boole es una idea antigua. La síntesis de circuitos es un campo bien estudiado. Google ganó una competencia hace 2 años. Me pregunto si probaron el modelo en el conjunto de datos de la competencia IWLS. Si no, ¿por qué no?
• ¿Podría usarse para el desafío ARC-AGI? ¿Podría combinarse con lo más reciente?
• Esto es autopromoción, pero es relevante => Robustness and halting of multicellular artificial development (2011)
  • Un autómata celular con reglas de actualización combinadas con perceptrones y difusión isotrópica. Los pesos de la red neuronal se optimizaron para que el autómata celular pudiera dibujar imágenes. Tenía autocuración (es decir, reconstruía la imagen cuando era perturbada)
  • En ese entonces, la diferenciación automática no era tan accesible como ahora. Optimicé los pesos con estrategias evolutivas. Claro, usar descenso de gradiente sería mucho mejor