Resumo Técnico: EM-NESY: Expectativa-Maximização para Aprendizado Neurosimbólico

Declaração do Problema

Modelos neurosimbólicos (NeSy) visam integrar os pontos fortes perceptivos de redes neurais com as capacidades de raciocínio da lógica simbólica. Embora os modelos NeSy de última geração alcancm tipicamente o treinamento de ponta a ponta através da retropropagação de gradientes por meio de componentes neurais e simbólicos, essa abordagem enfrenta desafios significativos quando o componente simbólico depende de inferência aproximada.

A inferência probabilística exata é frequentemente #P-hard e computacionalmente intratável para tarefas complexas. Consequentemente, muitos sistemas recorrem a métodos de inferência aproximada (ex: amostragem, propagação de crença ou relaxações de programação linear). No entanto, esses métodos introduzem problemas de diferenciabilidade:

1. Não-diferenciabilidade: Técnicas como amostragem são inerentemente não-diferenciáveis, exigindo estimadores de gradiente especializados (ex: REINFORCE) ou truques de reparametrização.
2. Sobrecarga Computacional: Mesmo métodos iterativos teoricamente diferenciáveis (ex: propagação de crença) tornam-se impraticáveis para diferenciar na prática devido ao grafo computacional massivo necessário para retropropagar através de todas as iterações.

As soluções atuais frequentemente exigem modificações específicas de inferência para garantir a diferenciabilidade, limitando a flexibilidade e a escalabilidade dos sistemas NeSy.

Metodologia: EM-NeSy

Os autores propõem o EM-NeSy, um framework de aprendizado que trata o aprendizado NeSy probabilístico como uma instância do algoritmo de Expectativa-Maximização (EM). Esta formulação desacopla o processo de inferência simbólica do cálculo do gradiente, permitindo o uso de qualquer motor de inferência (exato ou aproximado, diferenciável ou não).

O Framework

O modelo NeSy é tratado como um modelo de variáveis latentes onde:

• $X$: Entrada subsimbólica (ex: imagens).
• $Z$: Variáveis simbólicas latentes (preditas neuralmente).
• $Y$: Saída simbólica alvo (ex: validade de uma grade de Sudoku).
• $\theta$: Parâmetros da rede neural.

O processo de aprendizado alterna entre dois passos:

1. E-Step (Expectativa):
   O componente simbólico calcula a distribuição posterior das variáveis latentes $Z$ condicionada à observação do rótulo $Y$ e da entrada $X$:
   $$p(z|y, x, \theta) = \frac{p_{Ne}(z|x, \theta)p_{Sy}(y|z)}{p(y|x, \theta)}$$
   Aqui, $p_{Ne}$ é a priori neural e $p_{Sy}$ é a verossimilhança simbólica. Crucialmente, este passo atua como um "corretor probabilístico", realizando a abdução de rótulos suaves ou rígidos para $Z$ com base no conhecimento de fundo. Este passo pode ser realizado por qualquer motor de inferência simbólica (exato, aproximado, baseado em amostragem, etc.) sem exigir diferenciabilidade.

2. M-Step (Maximização):
   Os parâmetros neurais $\theta$ são atualizados minimizando a entropia cruzada entre a a priori neural $p_{Ne}(z|x, \theta)$ e a posterior $\ell(z)$ calculada no E-step:
   $$L_{EM-NeSy}(\theta) = -\sum_{z \in R(Z)} \ell(z) \log p_{Ne}(z|x, \theta)$$
   Os gradientes são retropropagados apenas através do componente neural, tratando a posterior $\ell(z)$ como uma constante. Isso elimina a necessidade de diferenciar através do processo de inferência simbólica.

Equivalência Teórica

O artigo prova que, sob inferência exata, os gradientes calculados pelo EM-NeSy são matematicamente equivalentes aos de um aprendizado NeSy padrão diferenciável de ponta a ponta (Teorema 3.1). Assim, o EM-NeSy recupera o cenário padrão quando a inferência exata é viável, mas oferece uma vantagem distinta quando esta não o é.

Variantes e Extensões

• Hard EM: Utiliza atribuições de Máxima Posterior (MAP) em vez de posteriors suaves.
• Multi-M EM: Realiza múltiplos passos de M (atualizações de gradiente) para um único passo de E para acelerar a convergência sem recomputar a posterior custosa.
• Inferência Aproximada: O framework suporta naturalmente métodos baseados em amostragem (ex: Amostragem de Rejeição, Amostragem ABC) e algoritos iterativos (ex: Propagação de Crença) sem modificações.

Principais Contribuições

1. Reformulação do Aprendizado NeSy: Os autores reestruturaram o aprendizado NeSy dentro do framework EM, permitindo o uso de variantes avançadas de EM (EM Generalizado, EM Estocástico, Hard EM) para melhor flexibilidade.
2. Integração Livre de Diferenciabilidade: Um framework geral é proposto que integra qualquer motor de inferência probabilística em um modelo NeSy sem exigir que o processo de inferência simbólica seja diferenciável.
3. Escalabilidade e Eficiência: A abordagem demonstra que o aprendizado NeSy pode escalar para tarefas onde a inferência exata é intratável ou onde diferenciar através de solvers iterativos é computacionalmente proibitivo.

Resultados Experimentais

Os autores avaliaram o EM-NeSy em três benchmarks: MNISTAdd (adição de dígitos manuscritos), Visual Sudoku e Warcraft path-planning.

• Inferência Exata (MNISTAdd): O EM-NeSy alcançou uma precisão comparável ao NeSy diferenciável padrão de ponta a ponta (BP-std) e ao DeepStochLog. No entanto, superou-os significativamente em escalabilidade e eficiência. Enquanto o DeepStochLog falhou em escalar para 15 dígitos devido aos limites de compilação de conhecimento, o EM-NeSy escalou para 100 dígitos. Também reduziu o uso de memória de pico de ~90 GB para ~35 GB e reduziu o tempo de treinamento.
• Inferência Aproximada/Não-Diferenciável:
  • Visual Sudoku: Métodos diferenciáveis padrão (Scallop, SL) excederam o tempo limite em grades 9x9. O EM-NeSy usando amostragem de Computação Bayesiana Aproximada (ABC) alcançou uma precisão competitiva (53,3%) com tempo de treinamento mínimo (8,24 min), enquanto outros métodos eram inaplicáveis.
  • Warcraft Path-Planning: O EM-NeSy com amostragem ABC alcançou o estado da arte em precisão (98,80% em 12x12, 69,60% em 30x30) com tempos de treinamento significativamente mais rápidos em comparação com I-MLE e EXAL.
• Limitações Observadas: O desempenho do EM-NeSy depende da qualidade da posterior aproximada. O Hard EM (MAP) mostrou viés no MNISTAdd, e a propagação de crença de laços (loopy belief propagation) falhou no Sudoku 9x9 devido à estrutura do grafo de fatores. A amostragem ABC mostrou alta variância em instâncias maiores, mas permaneceu eficaz em configurações menores.

Significância e Alegações

O artigo afirma que o EM-NeSy fornece um framework de aprendizado unificado que simplifica substancialmente o design de modelos ao eliminar a necessidade de modificações de diferenciabilidade específicas de inferência. Ao tratar o aprendizado NeSy como um problema de EM, a abordagem:

• Permite o uso de qualquer motor de inferência simbólica, incluindo solvers especializados, otimizados ou não-diferenciáveis.
• Recupera o aprendizado padrão de ponta a ponta sob inferência exata, oferecendo simultaneamente uma eficiência computacional e escalabilidade de memória superiores.
• Permite que sistemas NeSy enfrentem tarefas envolvendo restrições combinatórias complexas (como planejamento de caminho ou Sudoku), onde a inferência exata é inviável ou aproximações diferenciáveis são difíceis de construir.

Os autores concluem que, embora o EM-NeSy não resolva o problema de selecionar aproximações eficazes (que permanece dependente da tarefa), ele remove a barreira da diferenciabilidade, permitindo assim sistemas neurosimbólicos mais escaláveis e flexíveis.