Gradient-Based Program Synthesis with Neurally Interpreted Languages

Título: Síntese de Programas Baseada em Gradiente com Linguagens Interpretadas Neuralmente (NLI)

1. Problema e Contexto

O campo da indução de programas enfrenta um dilema fundamental entre abordagens simbólicas e neuronais:

• Métodos Simbólicos: Oferecem excelente generalização composicional e eficiência de dados, mas dependem de Linguagens Específicas de Domínio (DSLs) criadas manualmente. Isso limita a escalabilidade, pois a criação de DSLs é trabalhosa e não se transfere facilmente para novos domínios. Além disso, a busca combinatória em espaços de programas é computacionalmente cara.
• Métodos Neuronais: Escalam bem e aprendem flexivelmente a partir de dados, mas tendem a falhar em generalização composicional e em cenários fora da distribuição (OOD). Eles funcionam como modelos monolíticos onde o conhecimento está entrelaçado nos pesos, dificultando a reutilização de conceitos aprendidos para novas tarefas.

O objetivo deste trabalho é preencher essa lacuna criando um modelo que aprenda sua própria linguagem simbólica discreta de ponta a ponta, combinando a composicionalidade das linguagens discretas com a capacidade de busca baseada em gradiente das redes neurais.

2. Metodologia: Neural Language Interpreter (NLI)

Os autores propõem uma arquitetura chamada Neural Language Interpreter (NLI), uma instância de Latent Adaptation Network (LAN). O NLI aprende uma linguagem de programação discreta e simbólica diretamente dos dados de entrada-saída, sem supervisão de programas reais.

Componentes Principais:

1. Indutor de Programas (Encoder):

   • Recebe uma especificação de exemplos (pares entrada-saída) e infere uma representação latente do programa.
   • Gera uma sequência de tokens discretos (vetores de probabilidade sobre um código de vocabulário) que representam o programa.
   • Utiliza o Gumbel-Softmax para permitir a diferenciação durante o treinamento, aproximando a amostragem discreta de forma contínua.
   • Inclui um token de "skip" (pular) para permitir programas de comprimento variável, ignorando passos computacionais desnecessários.

2. Executor Neural (Decoder):

   • Atua como um interpretador recursivo que executa o programa token por token.
   • Diferente de abordagens anteriores (como LPN) que mapeiam todo o programa em um único vetor latente, o executor do NLI atualiza o estado intermediário iterativamente para cada token.
   • Isso permite que o modelo lide com programas de comprimento variável e generalize para composições mais longas do que as vistas no treinamento.

3. Busca Baseada em Gradiente no Tempo de Inferência:

   • Uma inovação crucial é a capacidade de refinar a previsão inicial do indutor durante a inferência.
   • Em vez de buscar no espaço discreto (que é não diferenciável), a busca ocorre no espaço contínuo relaxado dos embeddings latentes.
   • Utiliza descida de gradiente para otimizar os embeddings latentes, maximizando a verossimilhança dos dados de especificação. Isso permite encontrar programas que explicam melhor os dados, mesmo que sejam composições novas não vistas durante o treinamento.

Função de Perda e Regularização:

• O modelo é treinado com uma perda de reconstrução (prever a saída correta) e uma perda de regularização no encoder.
• A regularização penaliza o uso de muitos tokens únicos no lote, incentivando o modelo a descobrir um conjunto compacto de primitivas e reutilizá-las (promovendo a composicionalidade).

3. Contribuições Chave

• Linguagem Simbólica Aprendida: O NLI descobre autonomamente um vocabulário de operações primitivas e uma sintaxe para combiná-las, sem depender de uma DSL pré-definida por humanos.
• Generalização Composicional: Ao usar uma execução recursiva token a token e busca baseada em gradiente, o modelo consegue compor primitivas aprendidas em novas estruturas e comprimentos, superando a limitação de generalização de modelos puramente contínuos.
• Adaptação no Tempo de Inferência: A introdução da busca por gradiente no espaço latente relaxado permite que o modelo ajuste dinamicamente o programa para tarefas específicas, agindo como uma busca local eficiente com sinais de gradiente.
• Aprendizado End-to-End: Todo o sistema (indutor + executor) é diferenciável, permitindo treinamento direto a partir de pares entrada-saída.

4. Resultados Experimentais

Os autores avaliaram o NLI em benchmarks de generalização composicional e no conjunto de dados DeepCoder.

• Benchmarks Personalizados (Shift-L, Shift-P, Comp-I):

  • Shift-L (Generalização de Comprimento): O NLI com busca por gradiente alcançou 99% de precisão em deslocamentos de sequência maiores do que os vistos no treinamento (extrapolação), enquanto outros métodos (ICL, TTT, LPN) falharam (0% de precisão).
  • Comp-I (Composição de Primitivas): O NLI alcançou 91% ao compor funções vistas isoladamente (ex: $f(g(x))$), superando significativamente os baselines.
  • Shift-P (Extração de Primitivas): O modelo conseguiu "descompilar" primitivas simples a partir de programas complexos, atingindo 100% de precisão.
  • Análise de Representações: O modelo aprendeu tokens específicos para "deslocamento de 1 passo" e "deslocamento de 2 passos", combinando-os para formar deslocamentos maiores (ex: 8 passos = 4 tokens de 1 passo + 2 tokens de 2 passos), demonstrando compressão e composicionalidade reais.

• DeepCoder:

  • O NLI superou métodos puramente neurais anteriores (como Latent Programmer e Transformers) e foi competitivo com métodos neuro-simbólicos (como ExeDec), mesmo sem acesso a anotações de programas reais durante o treinamento (apenas pares I/O).

• Estudos de Ablação:

  • A remoção da execução recorrente, da natureza discreta ou do Gumbel-Softmax fez a precisão fora da distribuição cair para quase zero, confirmando que esses componentes são essenciais para a generalização.

5. Significado e Conclusão

O trabalho estabelece um novo paradigma para a síntese de programas, demonstrando que é possível combinar a composicionalidade de linguagens discretas com a flexibilidade e eficiência de busca das redes neurais.

• Impacto: O NLI supera a barreira de que modelos neurais não conseguem generalizar sistematicamente para novas composições. Ele oferece uma alternativa viável aos métodos simbólicos tradicionais, eliminando a necessidade de engenharia manual de DSLs.
• Limitações e Futuro: O custo computacional da busca no tempo de inferência é um gargalo, e a expressividade atual é limitada a fluxos sequenciais estritos (sem ramificação condicional ou primitivas parametrizadas). No entanto, o trabalho abre caminho para modelos que aprendem suas próprias linguagens de programação para resolver problemas complexos de forma adaptativa.

Em resumo, o NLI prova que a busca baseada em gradiente em espaços de programas relaxados, combinada com uma arquitetura de interpretação recursiva, é uma estratégia poderosa para a indução de programas com forte generalização composicional.