Autômato celular de lógica diferenciável

• DiffLogic CA é uma abordagem de autômatos celulares que combina Neural Cellular Automata e Differentiable Logic Gate Networks para aprender regras locais com gradiente, mantendo estados celulares discretos
• Cada célula tem um estado em vetor binário n-dimensional, e tanto a etapa de percepção quanto a de atualização são processadas por redes de portas lógicas para calcular diretamente o próximo estado
• No experimento com o Conway's Game of Life, o modelo aprendeu em um passo as 512 configurações de uma grade periódica 3x3 para capturar a regra completa, e também reproduziu padrões representativos como glider, block, loaf e boat em inferência hard
• Nos experimentos de geração de padrões, criou um tabuleiro 16x16 em 20 passos e continuou funcionando em grades 4 vezes maiores e horizontes temporais 4 vezes mais longos, além de mostrar tolerância a falhas em células danificadas e autorrecuperação após reativação
• Também gerou o contorno mais complexo de um lizard e um G RGB com 8 cores, mas aprender estruturas complexas ainda exigiu muito ajuste de hiperparâmetros, com NCA hierárquico e portas no estilo LSTM como candidatos a melhoria

---

O problema que o DiffLogic CA busca resolver

• Autômatos celulares normalmente são tratados definindo primeiro regras locais e depois observando os padrões emergentes resultantes
• O DiffLogic CA explora uma forma totalmente diferenciável de aprender regras locais que produzam um padrão complexo desejado
• Neural Cellular Automata tradicionais conseguem aprender padrões e comportamentos arbitrários, mas não operam inerentemente em espaço de estados discretos, o que reduz a interpretabilidade e traz custo de multiplicações de matriz em atualizações contínuas de estado
• Differentiable Logic Gate Networks já foram usadas para descobrir circuitos lógicos combinacionais, mas ainda não havia demonstração de funcionamento em uma configuração de NCA recursiva no espaço e no tempo
• Todo o experimento pode ser reproduzido no notebook

Estrutura básica de Neural Cellular Automata

• Neural Cellular Automata combinam autômatos celulares clássicos com deep learning, aprendendo a regra de atualização por descida de gradiente em vez de projetá-la manualmente
• Cada célula do Growing-NCA tem um vetor de estado n-dimensional sobre uma grade 2D
  • Os 3 canais RGB representam a cor da célula
  • O canal Alpha representa a viabilidade da célula; se o valor de alpha for maior que 0,1, a célula é considerada viva
  • Os demais hidden channels carregam informações mais complexas sobre o ambiente ao redor
• A atualização ocorre em duas etapas
  • Etapa de percepção: aplica-se o Sobel filter por canal para aproximar gradientes espaciais e formar um perception vector que combina o estado atual da célula com informações da vizinhança
  • Etapa de atualização: uma rede neural com cerca de 8.000 parâmetros é aplicada igualmente a todas as células para decidir como cada uma deve mudar
• Como todas as operações são diferenciáveis, o sistema inteiro pode aprender um padrão ou comportamento específico

Como funcionam as Differentiable Logic Gate Networks

• Deep Differentiable Logic Gate Networks usam portas lógicas como AND, OR e XOR como unidade básica, em vez de neurônios artificiais
• A rede é composta por camadas de portas, e cada porta recebe entrada de duas portas da camada anterior em uma estrutura esparsa
• As conexões são inicializadas aleatoriamente e não mudam durante o treinamento; o aprendizado decide apenas qual operação lógica cada porta executa
• Durante o treinamento, as portas lógicas discretas não são usadas de forma direta; entram dois mecanismos
  • Relaxamento contínuo: operações discretas como hard AND são substituídas por versões diferenciáveis que recebem entradas entre 0 e 1
  • Seleção probabilística de portas: cada porta mantém uma distribuição de probabilidade sobre 16 operações binárias possíveis para duas entradas, aprendendo parâmetros de 16 dimensões expressos por softmax
• Ao fim do treinamento, cada porta é fixada na operação de maior probabilidade e, na inferência, executa apenas operações binárias puras
• Para estabilizar o treinamento, a distribuição inicial das portas é enviesada em direção às portas de passagem direta

Estrutura do DiffLogic CA

• O DiffLogic CA segue a estrutura de grade 2D do NCA, mas representa o estado de cada célula como um vetor binário n-dimensional
• Estado da célula e canal são usados com o mesmo sentido, e o vetor binário de estados funciona como memória de trabalho para armazenar informações de iterações anteriores
• A etapa de percepção usa kernels baseados em redes de portas lógicas no lugar do Sobel filter
  • Cada kernel é um circuito separado com estrutura de conexão fixa, enquanto os tipos de portas são aprendidos
  • O kernel é calculado por canal
  • Cada circuito usa 4 camadas projetadas para calcular interações entre a célula central e as células vizinhas
• Na etapa de atualização, a memória anterior da célula e as informações recebidas da vizinhança são concatenadas e passadas para uma Differentiable Logic Gate Network que calcula o novo estado
• Em vez de uma atualização no estilo ODE que soma incrementos gradualmente, como no NCA padrão, o modelo emite diretamente o próximo estado binário
• O funcionamento de uma rodada pode ser visto como dois registradores
  • O registrador cinza contém o estado existente da célula
  • O registrador laranja armazena o resultado da etapa de percepção
  • Após a atualização, o novo estado é escrito no registrador cinza, e o registrador laranja é limpo para a próxima rodada
• Essa estrutura funciona como uma rede de pequenos computadores independentes, em que cada célula se comunica com as vizinhas e toma decisões a partir do que observa

Experimento 1: aprendendo o Conway's Game of Life

• Game of Life é um autômato celular binário em que cada célula vive ou morre na próxima geração com base em seus 8 vizinhos e em seu estado atual
• As regras são quatro
  • Uma célula morta passa a viver se tiver exatamente 3 vizinhos vivos
  • Uma célula viva sobrevive se tiver 2 ou 3 vizinhos vivos
  • Uma célula viva morre se tiver menos de 2 vizinhos
  • Uma célula viva morre se tiver mais de 3 vizinhos
• Como esse experimento trata regras que não dependem de repetições de estado anteriores, o estado da célula foi definido como 1 bit
• A configuração do modelo foi a seguinte
  • 16 kernels de circuito de percepção
  • A estrutura de nós de cada kernel de percepção é [8, 4, 2, 1]
  • A rede de atualização tem 23 camadas
  • As primeiras 16 camadas têm 128 nós cada
  • As camadas seguintes são [64, 32, 16, 8, 4, 2, 1]
• Os dados de treino incluem todas as 512 configurações possíveis em uma grade periódica 3x3
  • Como o próximo estado de cada célula é determinado por ela mesma e seus 8 vizinhos, há 512 configurações 3x3 possíveis
  • Acertar todos os próximos estados em um passo equivale a aprender a regra completa do Game of Life
• A função de perda soma as diferenças quadráticas entre a grade prevista e a grade correta
• Tanto a soft loss quanto a hard loss convergiram completamente, e o circuito aprendido em inferência hard reproduziu padrões de Game of Life em grades maiores
• O número de portas ativas, excluindo pass-through A e B, foi 336, e OR e AND foram as operações mais frequentes nas redes de percepção e atualização
• É possível interagir diretamente com o circuito gerado em Game of Life circuit

Experimento 2: geração de padrão de tabuleiro

• O experimento de geração de padrões foi configurado para aprender regras que evoluem de um estado inicial arbitrário até uma imagem-alvo
• Como a perda é calculada apenas no último timestep, o modelo precisa encontrar uma regra de transição discreta sem supervisão dos estágios intermediários
• O estado da célula tem 8 bits, e o DiffLogic CA é iterado por 20 passos
• A configuração do modelo foi a seguinte
  • 16 kernels de circuito de percepção
  • Cada kernel tem 8, 4 e 2 portas por camada
  • A rede de atualização tem 16 camadas
  • As primeiras 10 camadas têm 256 portas cada
  • As camadas seguintes são [128, 64, 32, 16, 8, 8]
• A função de perda é a soma da diferença quadrática entre o primeiro canal da grade prevista e a grade-alvo no último timestep
• O modelo foi treinado para reconstruir um padrão de tabuleiro 16x16 em até 20 passos
• Tanto a soft loss quanto a hard loss convergiram, e houve formação clara do padrão no primeiro canal
• Embora o modelo não tivesse viés direcional embutido, o padrão mostrou uma propagação do canto inferior esquerdo para o canto superior direito
• O número de portas ativas, excluindo pass-through A e B, foi 22, e após poda a função completa de geração do tabuleiro pôde ser implementada efetivamente com apenas 5 portas lógicas
• O circuito continuou funcionando ao escalar para uma grade 4 vezes maior e um tempo 4 vezes mais longo, indicando que a regra aprendida não estava sobreajustada a um tamanho específico de grade

Dano, autorrecuperação e atualização assíncrona

• No experimento do tabuleiro, foram realizados dois testes de dano assumindo que algumas células falham
  • Uma grande região de células foi desativada permanentemente para simular componentes defeituosos
  • Após certo número de passos, as células inativas foram reativadas
• O sistema manteve a integridade do padrão mesmo sob dano permanente e, quando as células voltaram a ficar online, regenerou o padrão correto
• Mesmo sem ter sido projetado explicitamente para tolerância a falhas e autorrecuperação, o comportamento mostrou danos localizados sem colapso abrupto da função global
• No experimento de atualização assíncrona, nem todas as células são atualizadas ao mesmo tempo; em cada passo, apenas um subconjunto aleatório de células é atualizado
• Esperava-se que o treinamento assíncrono fosse mais difícil do que em NCA convencional
  • O modelo precisa emitir o novo estado completo, e não apenas um incremento por passo
  • Ele precisa lidar com combinações em que células vizinhas estão em estágios diferentes, adiantadas ou atrasadas em relação umas às outras
• No caso do tabuleiro, o treinamento assíncrono teve sucesso com relativa facilidade, e mesmo com diferentes ordens de atualização a partir do mesmo estado inicial o padrão-alvo foi reconstruído em até 50 passos
• Aplicar a regra originalmente treinada de forma síncrona em inferência assíncrona também funcionou
• Em um teste que desativava aleatoriamente, a cada passo de inferência, um retângulo de 10x10 pixels dentro da imagem, as células treinadas de forma assíncrona se recuperaram um pouco mais rápido do dano
• Medindo o erro pela soma das diferenças absolutas entre a imagem-alvo e a reconstruída, o treinamento assíncrono aumentou a robustez a esse tipo de perturbação

Experimento 3: crescimento do contorno de lizard

• O experimento com lizard é uma homenagem ao trabalho original de NCA e testa se o DiffLogic CA consegue aprender formas arbitrárias
• Ao contrário do tabuleiro, que é altamente regular e compressível, o contorno do lizard exige muito mais memorização
• A configuração foi a seguinte
  • O estado da célula tem 128 bits
  • O DiffLogic CA é iterado por 12 passos
  • Há 4 kernels de circuito de percepção
  • Cada kernel tem portas em camadas de 8, 4, 2 e 1
  • A rede de atualização tem 10 camadas
  • As primeiras 8 camadas têm 512 portas cada
  • As camadas finais são [256, 128]
• O modelo foi treinado para gerar um padrão de lizard 20x20 em até 12 passos
• A condição inicial é uma seed central para quebrar a simetria, como em NCA, e condições de contorno periódicas são aplicadas nas bordas da grade
• Mesmo ao avaliar em uma grade maior de 40x40, o padrão de crescimento do lizard foi gerado com sucesso, mostrando que a solução não dependia das condições de contorno
• Tanto a soft loss quanto a hard loss convergiram a 0
• O número de portas ativas, excluindo pass-through A e B, foi 577
• Os kernels de percepção usaram principalmente portas TRUE, enquanto o circuito de atualização usou quase todos os tipos de portas disponíveis
• Aprender a gerar padrões complexos foi difícil de otimizar e exigiu amplo ajuste de hiperparâmetros

Experimento 4: geração de um G colorido

• Como os experimentos anteriores focavam na prática em imagens monocromáticas, foi realizado um teste para gerar uma imagem colorida 16x16 como estado-alvo mais complexo
• O estado da célula tem 64 canais, e o modelo gera uma letra G colorida ao longo de 15 passos
• Os três primeiros canais representam valores RGB, como na convenção de NCA padrão, mas aqui cada valor é restrito a 0 ou 1, formando uma paleta de 8 cores
• A configuração do modelo foi a seguinte
  • 4 kernels de circuito de percepção
  • Cada kernel consiste em 3 camadas com 8, 4 e 2 portas
  • A rede de atualização tem 11 camadas
  • As primeiras 8 camadas têm 512 nós cada
  • As 3 camadas finais são [256, 128, 64]
• O estado inicial é totalmente 0, e não são usadas condições de contorno periódicas
• A função de perda soma as diferenças quadráticas entre a grade prevista e a grade-alvo, considerando apenas os três primeiros canais, 0, 1 e 2, no último timestep
• Tanto a soft loss quanto a hard loss convergiram, e o modelo reconstruiu o G colorido em até 15 passos
• O número de portas ativas, excluindo pass-through A e B, foi 927
• Portas TRUE e FALSE foram muito usadas tanto na rede de percepção quanto na de atualização, e OR foi a porta mais frequente na rede de atualização
• Esse circuito foi mais complexo que os experimentos anteriores tanto em busca de hiperparâmetros quanto em tamanho do circuito

Desafios restantes e direções de melhoria

• O DiffLogic CA propõe uma nova arquitetura e método de treinamento de NCA que usa estados celulares totalmente discretos e atualiza esses estados com circuitos binários recursivos aprendidos
• Ao substituir componentes de rede neural por Deep Differentiable Logic Networks, ele combina a flexibilidade do aprendizado diferenciável com portas lógicas discretas
• Os experimentos de reprodução do Game of Life e geração de padrões mostram que portas lógicas diferenciáveis podem ser aplicadas a autômatos celulares
• Como resultado, confirma-se que Differentiable Logic Gate Networks podem ser treinadas de forma eficaz também em estruturas recursivas
• O modelo atual demonstrou potencial para aprender padrões, mas o treinamento para gerar formas e estruturas mais complexas ainda é difícil
• Como caminhos de melhoria, são sugeridos uma estrutura NCA hierárquica e portas especiais para ajudar no esquecimento de estado
• Integrar um mecanismo de gating no estilo LSTM ao processo de atualização de estado pode combinar de forma mais rica o estado passado com novos estados candidatos, aumentando a dinâmica e a expressividade do modelo

[GN⁺]

Comentários do Hacker News

• Muito interessante. Eu vinha procurando novos substratos de máquina de Turing universal e colecionando-os como Pokémon para experimentos de programação genética. Já tinha brincado com autômatos celulares antes, com rule 30/110 e afins, mas esta abordagem parece muito mais convincente
  Eu nunca tinha pensado em modelar o kernel como um circuito lógico digital. Parece que as restrições de lógica booleana, portas e circuitos criam uma textura interessante para a paisagem de aptidão. Os parâmetros resultantes podem ser convertidos diretamente para implementação em hardware ou, após uma etapa adicional de otimização, compilados em programas simples. Parece melhor do que lidar com números de ponto flutuante mágicos dentro de uma caixa-preta com bilhões de parâmetros

  • Este artigo realmente parece importante. Se você tornar o autômato diferenciável, poderá aplicar otimização por retropropagação ao projeto de circuitos booleanos e aprender comportamentos complexos de sistemas discretos. É impressionante
  • Vale olhar o difflogic. Ele pode compilar circuitos lógicos neurais diferenciáveis para CUDA ou código C. A demo principal é um classificador de MNIST que processa mais de 1 milhão de imagens por segundo em CPU

• Empolgante. Michael Levin foi quem melhor formulou o problema de como células animais conseguem cooperar sem uma hierarquia. Por exemplo, há experimentos biológicos em que, mesmo removendo células oculares de um embrião de sapo, elas migram para o local onde o olho deveria estar
  A pergunta que ele, na minha visão, não conseguiu responder direito era como as células sabem quando devem parar. Entender organização não hierárquica também é central para como a sociedade funciona e para resolver o dilema do prisioneiro em várias escalas de um mundo auto-organizado. Trata-se também de compreender e modelar a complexidade bruta. Esta é a primeira vez que vejo a capacidade de modelar algo assim, e parece haver muitas direções para onde isso pode se expandir

  • Posso estar deixando passar algo óbvio, mas fico me perguntando por que isso não é tratado pelo conhecido mecanismo de gradientes químicos abordado em materiais introdutórios. Basicamente, as células se orientam dentro de várias camadas de gradientes químicos sobrepostos, e esses gradientes são configurados repetidamente, mostrando a cada repetição um comportamento espacial mais complexo
  • Entrevista com Michael Levin, Cognitive Light Cones: https://www.youtube.com/watch?v=YnObwxJZpZc

• Tenho pensado muito sobre inteligência ultimamente, e parece que estamos chegando a um ponto decisivo em que vamos descobrir como ela funciona, ou pelo menos avançar muito no entendimento. Inteligência parece um comportamento que emerge naturalmente, não muito diferente da mecânica newtoniana clássica ou da eletricidade
  No fim, tudo parece se reduzir a regras simples. E se tudo no cérebro que não é discreto for, na verdade, apenas infraestrutura sustentando processos centrais simples, porém importantes, que fazem o trabalho real? E se, no fundo, tudo se resumir a portas lógicas e sinais elétricos? Acho que vêm tempos interessantes por aí

• Há algo especialmente atraente nessa abordagem, principalmente em termos de capacidade de generalização. Mas fico curioso sobre qual é a grande visão. O que isso vai permitir fazer no futuro? Filosoficamente, o que isso nos ensina sobre o mundo? Já sabemos que autômatos celulares unidimensionais são equivalentes a Turing, então, de certo ponto de vista, NCA ou algo assim não é tão surpreendente

  • Pode ser útil se conseguirmos alimentar uma grade com imagens de satélite para simular problemas como propagação de incêndios florestais ou dispersão de poluição
  • Elas provavelmente se tornarão a forma de vida dominante da Terra em termos de consumo de energia, superando bactérias, plantas e humanos
    Surgirão autômatos celulares que interagem com o ambiente, e autômatos que interagem tanto com sistemas de baixo nível quanto com instituições de alto nível. Em certa medida, os humanos também são apenas células individuais interagindo dentro dessas redes. O futuro da inteligência, na minha visão, não está em LLMs, mas em sistemas de autômatos com aspecto metabólico. Autômatos que coevoluem, consomem energia, produzem valor, competem e modelam uns aos outros
    Não estamos sendo substituídos; estamos participando de uma transformação em que a fronteira entre sistemas técnicos e sistemas celulares está ficando difusa e acabará desaparecendo. Sou muito grato por poder testemunhar isso. Referência: https://x.com/zzznah/status/1803712504910020687
  • As propriedades de autocura lembram evolução biológica

• Eu gosto de brincar com autômatos celulares em trabalhos artísticos. É impressionante que padrões podem emergir. Ex.: https://gods.art/math_videos/hex_func27l_21.html
  Acho que também preciso experimentar este DLCA

  • Fico me perguntando se esses padrões continuam sendo gerados infinitamente
  • Isso me lembrou o antigo filme Andromeda Strain

• Há muitas ideias ótimas aqui. Pode ser uma observação pequena, mas este cálculo tem estado. Cada célula tem memória e percepção do ambiente ao redor
  Em contraste, redes neurais modernas em geral não têm estado. Por exemplo, fico curioso se já houve pesquisa sobre LLMs com estado

• É autopromoção, mas é muito relacionado: Robustness and the Halting Problem for Multicellular Artificial Ontogeny (2011)
  Era um autômato celular cujo regra de atualização era um perceptron combinado com difusão isotrópica. Os pesos da rede neural eram otimizados para fazer o autômato celular desenhar figuras e, quando perturbado, reconstruí-las por autocura. Na época, diferenciação automática não era tão acessível quanto hoje, então os pesos foram otimizados com estratégias evolutivas. Claro, é bem provável que usar descida de gradiente seja muito melhor

• Será que isso poderia ser usado no desafio ARC-AGI? Talvez também pudesse ser combinado com esta abordagem recente: https://news.ycombinator.com/item?id=43259182

• Realmente incrível. Como alguém que ficou só lendo por muito tempo e usa bastante modelagem e simulação, isso parece ter grande potencial para entender melhor o comportamento emergente em modelos complexos de comportamento de agentes
  Gostaria de ver isso aplicado a coisas como modelos predador/presa e outros modelos que parecem simples, mas produzem resultados emergentes complexos em grande escala. Vou continuar acompanhando este trabalho

• O padrão xadrez no resultado parece o inverso do padrão-alvo, ou seja, um NOT. Mas não há menção a isso. Fico me perguntando se não é importante o bastante para comentar, ou se estou deixando passar alguma coisa

  • Obrigado por apontar isso. No processo de preparar para publicação, a imagem-alvo acabou sendo invertida, e isso já foi corrigido
  • O que está sendo aprendido não é a imagem exata, mas as características. É por isso que a autocura funciona bem, e também deve haver invariância a deslocamento