Resumo Técnico: Propagação de Decisão Neural para Programação por Conjuntos de Resposta

1. Declaração do Problema

A integração da Programação por Conjuntos de Resposta (ASP) com redes neurais emergiu como uma via promissora para a IA Neuro-simbólica, permitindo que sistemas combinem aprendizado robusto com raciocínio simbólico. No entanto, abordagens existentes (por exemplo, NeurASP, SLASH) geralmente dependem de solvers ASP clássicos dentro de seus pipelines de raciocínio. Essa dependência cria um gargalo significativo para a escalabilidade, uma vez que solvers simbólicos são frequentemente computacionalmente caros e difíceis de integrar em frameworks de treinamento diferenciáveis de ponta a ponta. Além disso, embora alguns métodos tentem podar espaços de busca usando feedback probabilístico, eles ainda dependem fundamentalmente de mecanismos de resolução discretos e não diferenciáveis.

O artigo aborda a necessidade de um método escalável e diferenciável para calcular modelos estáveis que possa aprender heurísticas de decisão e integrar-se perfeitamente com redes neurais, sem depender de solvers simbólicos externos.

2. Metodologia

2.1 Propagação de Decisão (DProp)

Os autores propõem primeiro a Propagação de Decisão (DProp), um algoritmo inovador para calcular modelos estáveis em ASP clássico. O DProp opera sobre um conjunto de átomos $A$, particionando-os em três conjuntos disjuntos: Verdadeiro ($T$), Falso ($F$) e Indecidido ($U$). O algoritmo itera através de duas fases alternadas até a terminação:

1. Fase de Decisão: O algoritmo seleciona não determinísticamente um átomo indecidido $a \in U$ e compromete-o como Falso (movendo-o para $F$).
2. Fase de Propagação: Com o conjunto $F$ fixo, o algoritmo deriva consequências usando uma abordagem de encadeamento para frente. Ele calcula o ponto fixo mínimo do operador de consequência imediata $C_{P, A \setminus F}$ começando a partir da atual $T$. Átomos derivados como verdadeiros são movidos de $U$ para $T$.

O processo termina quando $U$ está vazio. Um cálculo é considerado bem-sucedido se terminar com $U = \emptyset$ e sem contradição ($T \cap F = \emptyset$). Os autores provam que qualquer cálculo DProp bem-sucedido captura a semântica de modelo estável do programa. Especificamente, um conjunto $S$ é um modelo estável se e somente se for o conjunto final de verdadeiros de uma execução DProp bem-sucedida.

2.2 Propagação de Decisão Neural (NDProp)

Para permitir aprendizado e integração com redes neurais, os autores desenvolvem o NDProp, uma extensão diferenciável do DProp.

• Representação: Em vez de conjuntos binários, o NDProp mantém graus de verdade contínuos $\tau \in [0, 1]^n$ e graus de falsidade $\phi \in [0, 1]^n$ para cada átomo. Uma pontuação de pertinência $p_i = \frac{1}{2}(\tau_i + 1 - \phi_i)$ representa o valor de verdade suave.
• Decisão Diferenciável: A fase de "Decisão" é implementada por meio de um módulo de decisão de Rede Neural Recorrente (RNN). A RNN recebe o estado atual ($\tau, \phi$ e grau de indecisão $\mu$) e produz logits de decisão, que são convertidos em pontuações $\delta$ via uma função sigmoide. Os graus de falsidade são atualizados aditivamente: $\phi^{t+1} = \phi^t + (\mu^t \odot \delta^t)$. Isso permite que a rede aprenda quais átomos falsificar.
• Propagação Diferenciável: A fase de "Propagação" usa operadores de lógica difusa (t-normas e t-conormas) para atualizar os graus de verdade $\tau$. Ela itera um operador de consequência imediata suave $C_{P, \phi}$ até a convergência (ou um número fixo de passos).
• Recuperação Nítida: Os autores provam que, quando as entradas e saídas são restritas a valores binários (0 ou 1), o NDProp coincide exatamente com o algoritmo DProp discreto.
• Aplicação de Estabilidade: O artigo demonstra que a imposição de saídas binárias via uma função de perda (por exemplo, Entropia Cruzada Binária) força inerentemente o sistema a convergir para modelos estáveis, desde que a propagação atinja um ponto fixo. Isso permite treinamento não supervisionado, onde o modelo aprende a encontrar modelos estáveis sem rótulos explícitos para os conjuntos de resposta.

3. Contribuições Principais

1. Algoritmo DProp: Introdução de um novo método para calcular modelos estáveis baseado em decisões alternadas de falsidade e propagações de verdade, com uma prova formal de que execuções bem-sucedidas capturam a semântica de modelo estável.
2. Framework NDProp: Desenvolvimento de uma extensão totalmente diferenciável (NDProp) que usa redes neurais para tomada de decisão e lógica difusa para propagação. Mostra-se que coincide com o DProp no caso nítido.
3. Dinâmicas de Aprendizado: Demonstração de que o NDProp pode aprender heurísticas de decisão para resolver problemas ASP aleatórios sem depender de solvers externos.
4. Integração Neuro-simbólica: Integração bem-sucedida do NDProp em pipelines neuro-simbólicos, mostrando que o treinamento de ponta a ponta de percepção e raciocínio produz precisão e escalabilidade superiores em comparação com baselines baseadas em solvers.

4. Resultados Experimentais

Os autores conduziram três tipos de experimentos:

• Resolução de ASP Aleatória: Usando programas negativos aleatórios de dois literais (N2L) e 3-LP, o NDProp foi treinado para aprender dinâmicas de decisão. Os resultados mostraram que o NDProp superou significativamente uma baseline de decisão aleatória (RDProp), mesmo em uma configuração de 1-shot, e generalizou bem para tamanhos de problema maiores.
• Benchmarks Neuro-simbólicos: Avaliado em tarefas aritméticas baseadas em MNIST (Adição, Add2x2, Apply2x2, Pertencimento). O NDProp foi comparado contra NeurASP e SLASH.
  • Precisão: O NDProp alcançou maior precisão de reconhecimento e inferência em todas as tarefas.
  • Velocidade: O NDProp demonstrou velocidades de inferência significativamente mais rápidas (em média 46 vezes mais rápido que o NeurASP e 7,5 vezes mais rápido que o SLASH) devido à paralelização em GPU e à eliminação de chamadas a solvers simbólicos.
• Raciocínio com Dados Incompletos: Em uma tarefa de Sudoku Visual com previsões imperfeitas de classificador de dígitos, o NDProp superou tanto uma baseline puramente neural quanto um solver ASP padrão. Enquanto o solver ASP falhou significativamente quando as previsões eram ruidosas (1% dos dados), o NDProp manteve robustez usando as previsões ruidosas como heurísticas para guiar a busca por uma solução compatível.

5. Significado e Alegações

O artigo alega que o NDProp oferece um solver de conjuntos de resposta totalmente diferenciável baseado em semânticas de ponto fixo inovadoras. Seu significado principal reside em:

• Escalabilidade: Ao remover a dependência de solvers simbólicos clássicos, o NDProp alcança velocidades de inferência muito mais altas e escala melhor para problemas maiores.
• Aprendizado de Ponta a Ponta: Permite a otimização conjunta de percepção (redes neurais) e raciocínio (lógica), levando a saídas mais coesas e consistentes em sistemas neuro-simbólicos.
• Solvência Teórica: O método preserva uma conexão clara com a semântica clássica de modelo estável, garantindo que as saídas binárias correspondam a modelos estáveis válidos.

Os autores concluem que, embora a seleção de t-normas e extensões para variantes difusas ou construções complexas (restrições, agregados) permaneçam trabalho futuro, o NDProp representa um passo significativo em direção a tornar o raciocínio ASP escalável e aprendível dentro de arquiteturas neurais.