Autômatos Celulares Lógicos Diferenciáveis

• Explora como fazer a engenharia reversa de padrões complexos a partir de regras locais simples
• Uma abordagem que combina a capacidade de aprendizado de Neural Cellular Automata (NCA) com Differentiable Logic Gate Networks para obter regras locais discretas por meio de aprendizado
  • "Será que é possível aprender as regras do Conway's Game of Life?"
  • "Será que dá para reproduzir padrões complexos como no NCA e aprender estruturas recorrentes espaço-temporais?"

Introduction

• Cellular Automata (CA) partem de regras locais simples, mas formam padrões complexos e difíceis de prever
• Tradicionalmente, no CA as regras eram projetadas manualmente por humanos, mas aqui é apresentada uma forma de "aprender" no sentido inverso regras locais que satisfaçam um padrão ou comportamento-alvo previamente definido
• Em especial, Neural Cellular Automata (NCA) foram projetados para permitir aprendizado em espaço contínuo ao combinar a estrutura de CA com técnicas de deep learning
• Differentiable Logic Gate Networks é uma técnica que aproxima continuamente portas lógicas (AND, OR, XOR etc.) para treinamento e depois as converte novamente em circuitos lógicos discretos
• Combinando essas duas ideias, é proposto o DiffLogic CA, um modelo de CA totalmente discreto e treinável
• Isso pode ser visto como um pequeno passo em direção a Programmable Matter ou Computronium
• Este texto segue o fluxo abaixo
  • Resumo de Neural Cellular Automata
  • Resumo de Differentiable Logic Gate Networks
  • Estrutura do DiffLogic CA que combina as duas metodologias
  • Experimento de aprendizado das regras do Conway’s Game of Life
  • Experimentos de aprendizado para gerar padrões complexos (xadrez, lagarto, imagens coloridas etc.)

Recap – Neural Cellular Automata(NCA)

• Conceito
  • Um sistema que substitui regras tradicionais de CA por uma forma treinável com redes neurais
  • Cada célula possui múltiplos canais (estado) e forma padrões complexos por meio de interações locais
  • Usa filtros como Sobel para obter informações da vizinhança, e a rede neural decide as mudanças de estado
• Características
  • Todo o processo de cálculo é diferenciável, permitindo treinamento para gerar o padrão desejado
  • Combina técnicas de deep learning preservando os elementos centrais do CA, como paralelismo, localidade e computação baseada em estado

Recap – Differentiable Logic Gate Networks(DLGNs)

• Ideia central
  • Em vez de uma NN tradicional, portas lógicas (AND, OR, XOR etc.) são aproximadas continuamente (soft gate) para treinamento
  • Na fase de aprendizado, as portas operam de forma contínua; na inferência final, executam operações binárias reais
• Processo de aprendizado
  • Aprende uma distribuição de probabilidade sobre as 16 operações lógicas possíveis da porta, convergindo ao final para uma operação específica
  • A aproximação contínua torna o sistema diferenciável e, ao fim do treinamento, ele é convertido em portas lógicas totalmente discretas
• Vantagens
  • O circuito final é composto inteiramente por portas lógicas binárias, o que traz alta eficiência em hardware
  • Por ser baseado em lógica discreta, oferece vantagens em interpretabilidade e eficiência energética

Differentiable Logic Cellular Automata (DiffLogic CA)

• Estrutura
  • Em uma grade 2D, cada célula tem um estado de n bits, e a simulação ocorre nas etapas Perception → Update
  • Etapa Perception
    • As informações da vizinhança (por canal) são processadas por kernels de circuitos lógicos
  • Etapa Update
    • O estado atual e o resultado de Perception são integrados por outro circuito lógico para determinar o estado do próximo instante
• Características
  • Todas as células funcionam de forma distribuída como pequenos processadores independentes em movimento
  • Aprende no modo soft (aproximação contínua) e faz inferência com portas hard (binárias), garantindo alta eficiência
  • Compartilha uma filosofia semelhante à de arquiteturas de computação baseadas em CA como o CAM-8

Experiment 1: Learning Game of Life

• Objetivo
  • Aprender as regras do Conway's Game of Life com DiffLogic CA e verificar se é possível reproduzi-las completamente
• Configuração
  • Uso de estado de célula com 1 bit
  • 16 kernels em Perception (cada um com estrutura de portas 8→4→2→1)
  • 23 camadas em Update (primeiras 16 camadas com 128 nós, depois [64, 32, 16, 8, 4, 2, 1])
  • Em uma grade 3x3, todos os estados possíveis (512) são usados no treinamento para prever exatamente o estado do próximo passo
• Resultados
  • A perda de treinamento se aproxima de 0, aprendendo perfeitamente a regra local do Game of Life
  • Em grades maiores, reproduz todos os padrões como no Game of Life real, incluindo gliders, blocos etc.
  • No circuito final, portas AND e OR são muito usadas

Experiment 2: Pattern Generation

• Exemplo do tabuleiro xadrez (Checkerboard)
  • Células com estado de 8 bits formam um tabuleiro 16x16 ao longo de 20 passos
  • 16 kernels em Perception, 16 camadas em Update (máximo de 256 portas)
  • A perda é calculada comparando apenas o canal final com o padrão-alvo
• Resultados
  • Forma exatamente o padrão xadrez, com a regra implementada de forma concisa usando apenas poucas portas
  • Em uma grade 4 vezes maior, a mesma regra escala e funciona sem problemas
  • Mesmo desativando permanentemente algumas células, o padrão não se degrada muito; ao restaurar as células desativadas, ocorre autocura automaticamente
• Asynchronicity
  • Mesmo com treinamento por atualização assíncrona, o padrão xadrez é aprendido sem problemas
  • Regras treinadas de forma síncrona também funcionam bem quando aplicadas em inferência assíncrona
  • Regras treinadas de forma assíncrona tendem a se recuperar um pouco mais rápido em cenários com ruído ou dano

Experiment 3: Growing a Lizard

• Objetivo
  • Treinar a formação do contorno de um lagarto 20x20 em 12 passos, verificando a possibilidade de gerar formas complexas
• Configuração
  • Estado de 128 bits
  • Perception com 4 kernels (cada um com estrutura de portas [8, 4, 2, 1]), Update com 10 camadas (primeiras 8 camadas com 512 portas, depois [256, 128])
  • Uma única célula ativa no centro da grade, usando condições de contorno periódicas
• Resultados
  • O lagarto cresce normalmente até em uma grade maior (40x40)
  • Muitas portas são usadas, mas o treinamento é viável com o ajuste adequado de hiperparâmetros

Experiment 4: Learning the G with colors

• Objetivo
  • Gerar uma imagem colorida 16x16 com 3 canais RGB ao longo de 15 passos, validando a geração de padrões multicanais
• Configuração
  • Estado de 64 bits (os 3 primeiros canais são usados como RGB, e cada canal é 0 ou 1)
  • Perception com 4 kernels (cada um com [8, 4, 2]), Update com 11 camadas (primeiras 8 camadas com 512 portas, depois [256, 128, 64])
  • A imagem-alvo é um padrão 16x16 da letra G preenchido com uma entre 8 cores possíveis
• Resultados
  • Aprende com perda próxima de 0 e reproduz exatamente a letra G colorida-alvo após 15 passos
  • No circuito, portas TRUE e FALSE são muito usadas, com destaque para portas OR

Summary and Discussion

• O que foi feito
  • Foi proposto o DiffLogic CA, um modelo de CA totalmente discreto e treinável
  • Ele replica regras clássicas como Game of Life e demonstra capacidade de gerar padrões como xadrez, lagarto e G colorido
  • Como é composto por circuitos lógicos discretos, pode oferecer interpretação intuitiva e eficiência em hardware
• Significado
  • Demonstra que padrões auto-organizados observados em NCA também podem ser aprendidos com base em portas lógicas discretas
  • Considerando características como recuperação de danos e atualização assíncrona, há alto potencial de aplicação em computação distribuída e tolerante a falhas (robust)
• Limitações e trabalhos futuros
  • Ao aprender imagens ou padrões complexos, ainda é necessário ajuste adequado de hiperparâmetros
  • Há espaço para explorar portas do tipo LSTM ou estruturas que esqueçam estado com eficiência, permitindo formação de padrões mais ricos
  • Também é possível expandir o trabalho na direção de otimização da escala do circuito e estabilização do treinamento
• Conclusão
  • DiffLogic CA é uma abordagem promissora que pode levar a direções teóricas de computação distribuída como Programmable Matter ou Computronium
  • Por ser totalmente discreto e ainda assim treinável, tem potencial para servir de base a futuros sistemas distribuídos

[GN⁺]

Comentários no Hacker News

• Muito interessante. Estou colecionando novas plataformas de máquinas de Turing de propósito geral. Estou colecionando como se fossem Pokémon para experimentos de programação genética. Já usei autômatos celulares (CA) antes, mas esta abordagem é muito mais atraente. Nunca tinha pensado em modelar o kernel como um circuito lógico digital
  • A lógica booleana, os gates e as restrições dos circuitos criam uma textura interessante que constrói a paisagem de fitness. Os parâmetros resultantes podem ser convertidos diretamente em implementações de hardware ou compilados em programas simples após uma etapa adicional de otimização. Parece melhor do que a mágica de ponto flutuante de caixas-pretas com dezenas de bilhões de parâmetros
• Gosto de usar autômatos celulares na arte. É surpreendente que tipos de padrões podem surgir. Acho que preciso experimentar DLCA
• Muito interessante. Fiquei impressionado com a pergunta levantada por Michael Levin sobre como células animais podem cooperar sem hierarquias. Há um experimento em que células do olho de um embrião de sapo se movem de volta para sua posição original. Não havia resposta sobre como as células sabem quando devem parar
  • Entender a organização não hierárquica é importante para compreender como a sociedade funciona. Também é importante para resolver o dilema do prisioneiro em diferentes escalas
  • Também tem a ver com entender e modelar a complexidade
  • Pela primeira vez, vejo a capacidade de modelar esse tipo de coisa. Isso pode seguir em muitas direções. Impressionante
• Tenho pensado muito sobre "inteligência" recentemente. Parece que estamos em um momento decisivo para entender como a inteligência funciona. Inteligência é um comportamento emergente, não muito diferente da mecânica newtoniana clássica ou da eletricidade. No fim, tudo se reduz a regras simples
  • E se tudo no cérebro que não é discreto for apenas "infraestrutura"? E se isso servir de suporte para um processo central fundamentalmente simples, mas importante, que realiza o trabalho real? E se tudo se resumir a portas lógicas e sinais elétricos?
  • Tempos interessantes estão chegando
• Eles são especialmente atraentes em termos de capacidade de generalização. Mas qual é a visão? O que isso poderá fazer no futuro? Filosoficamente, o que isso pode nos ensinar sobre o mundo? Sei que autômatos celulares 1D são equivalentes a Turing. Portanto, NCA/isso não é tão surpreendente assim
• É uma descoberta revolucionária. Não se trata de tabuleiros quadriculados nem de lagartos. As equações diferenciais de Navier-Stokes são as regras de atualização que governam o movimento dos fluidos. Toda a complexidade, como a formação de nuvens e o movimento das chamas, é governada por leis simples. Descobrir essa equação a partir de amostras reais é ciência. É possível aplicar o modelo DLCA a gravações de vídeo de fumaça para derivar as equações de Navier-Stokes. Se considerarmos que a própria regra de atualização pode mudar de acordo com outras regras de atualização, entraremos em um território interessante. Pode ser por isso que os neurônios do cérebro estão conectados a milhares de outros neurônios
  • Os executivos do Google vão ignorar essa descoberta dizendo que ela não tem relação com o negócio de publicidade. Alguns anos depois, quando o DLCA virar o mundo de cabeça para baixo, vão dizer que foi um funcionário deles que descobriu isso
• Artigo muito interessante. Tenho uma pergunta: como as atualizações são feitas usando descida de gradiente "global", os gates das células não são realmente paralelos
  • Existe alguma possibilidade de um método de ajuste de pesos estritamente local?
• O relaxamento contínuo da álgebra booleana é uma ideia antiga. Síntese de circuitos é uma área bem estudada. O Google venceu uma competição há 2 anos. Fico curioso se aplicaram o aprendiz ao conjunto de dados da competição IWLS. Se não, por que não?
• Será que isso pode ser usado no desafio ARC-AGI? Poderia ser combinado com o trabalho recente?
• É jabá próprio, mas é relacionado => Robustez e o problema da parada na morfogênese artificial multicelular (2011)
  • Uma regra de atualização de autômato celular combinada com perceptrons e difusão isotrópica. Os pesos da rede neural foram otimizados para que o autômato celular pudesse desenhar imagens. Havia autocura (ou seja, ele reconstruía a imagem quando era perturbado)
  • Na época, diferenciação automática não era tão acessível quanto hoje. Os pesos foram otimizados com estratégias evolutivas. Claro, usar descida de gradiente seria muito melhor