Probabilistic Linear Logic Programming with an Application to Bayesian Network Computations (Extended Version)

Resumo Técnico: Probabilistic Linear Logic Programming (probLO)

1. O Problema

A integração de Redes Bayesianas (modelos gráficos probabilísticos que representam dependências condicionais entre variáveis) dentro de frameworks de Programação Lógica permanece um desafio não trivial. As principais dificuldades identificadas pelos autores são:

• Estrutura de Dependência Complexa: As redes bayesianas frequentemente envolvem variáveis com múltiplos pais e filhos, formando estruturas que não são árvores simples. A maioria das abordagens existentes em Programação Lógica Probabilística (PLP) baseia-se em lógica clássica ou cláusulas de Horn, onde cada método possui um único "cabeçalho" (head), sugerindo implicitamente uma estrutura de dependência em árvore.
• Gestão de Recursos e Ciclos: Embora as redes bayesianas sejam acíclicas (DAGs), a lógica clássica permite a reutilização ilimitada de fatos (cláusulas). No entanto, para o cálculo de probabilidades condicionais em redes bayesianas, a intuição é que cada variável deve ser computada exatamente uma vez por consulta (uso linear), evitando redundâncias ou necessidade de construtos auxiliares complexos para evitar ciclos.
• Interpretação Semântica Externa: Muitas abordagens atuais dependem de uma interpretação semântica externa para calcular as probabilidades, em vez de realizar o cálculo diretamente dentro do mecanismo de inferência lógica.

2. Metodologia: A Linguagem probLO

Os autores propõem o probLO (Probabilistic Linear Objects), uma extensão da linguagem LO (Linear Objects) de Andreoli e Pareschi, que é fundamentada na Lógica Linear (especificamente no fragmento Multiplicativo-Aditivo com mix, MALLmix).

A metodologia baseia-se nos seguintes pilares:

• Lógica Linear como Fundamento: A sensibilidade a recursos da Lógica Linear alinha-se perfeitamente com a necessidade de computar a probabilidade condicional de cada nó da rede apenas uma vez.
• Métodos Multi-Head (Cabeçalho Múltiplo): Diferente da Prolog tradicional, o probLO utiliza métodos com múltiplos cabeçalhos. Um método é representado como uma fórmula bipolar (bipole) da lógica linear:
  • Cabeçalho (Head): Representa os efeitos ou resultados (múltiplos átomos).
  • Corpo (Body): Representa as premissas ou evidências.
  • Isso permite representar a produção simultânea de múltiplos resultados dada uma evidência, capturando a estrutura de DAGs sem redundância.
• Anotação Probabilística: Cada método é anotado com um valor de probabilidade $p \in [0, 1]$. A semântica operacional define que, ao aplicar um método durante a busca por prova, a probabilidade do estado resultante é o produto da probabilidade do estado atual pela probabilidade do método aplicado.
• Conectivos Aditivos para Incerteza: A incerteza sobre o valor de uma variável booleana (desconhecida) é representada por uma conjunção aditiva ($\&$ ou $\&$ no texto, denotada como $N$ no cálculo de sequentes) entre os átomos de "Verdadeiro" e "Falso" ($ttX \& ffX$). A regra de ramificação (bra) soma as probabilidades dos ramos, simulando o cálculo de marginais.

3. Contribuições Principais

O artigo apresenta as seguintes contribuições teóricas e práticas:

1. Caracterização de Aciclicidade (Teorema 2): Demonstra-se como a propriedade de um grafo direcionado ser acíclico (DAG) pode ser caracterizada puramente dentro do framework da LO (usando o fragmento multiplicativo com a regra mix). A prova de aciclicidade corresponde a uma busca por prova que visita os nós das folhas até a raiz, explorando novos nós apenas quando todos os seus filhos foram processados.
2. Definição do probLO: Introdução de uma linguagem com métodos probabilísticos multi-head e tabelas condicionais (probLO-tables) que encapsulam as distribuições de probabilidade condicional de variáveis booleanas.
3. Codificação de Redes Bayesianas: Mostra-se como codificar qualquer Rede Bayesiana booleana em um programa probLO, onde cada tabela condicional da rede se torna uma tabela probLO contendo métodos para os valores Verdadeiro e Falso.
4. Cálculo Direto de Probabilidades (Teorema 3): Prova-se que a semântica operacional do probLO calcula corretamente:
   • Probabilidades Conjuntas: O produto das probabilidades dos métodos aplicados ao longo de uma derivação sem ramificação.
   • Probabilidades Marginais: A soma das probabilidades das derivações resultantes da aplicação da regra de ramificação (bra) sobre as variáveis a serem marginalizadas.
5. Consistência Booleana: Estabelecimento de que, em uma derivação bem-sucedida, não é possível coexistir os átomos $ttX$e$ffX$ simultaneamente no mesmo estado, garantindo a coerência lógica da inferência.

4. Resultados e Exemplos

• Exemplo da Rede "Céu-Chuva-Grama": O artigo utiliza a rede bayesiana clássica (Cloudy, Sprinklers, Rain, WetGrass, TrafficJam) para ilustrar a codificação.
• Cálculo de Marginais: É demonstrado como calcular a probabilidade marginal $Pr(C=True, R=True, W=False, T=False)$ diretamente através de uma derivação no probLO. O processo envolve:
  1. Aplicação sequencial de métodos (multiplicação de probabilidades).
  2. Ramificação (bra) para somar os caminhos alternativos (ex: quando o estado da variável "Sprinklers" é desconhecido e precisa ser marginalizado).
• Complexidade Computacional: O Corolário 2 afirma que o custo computacional para calcular probabilidades conjuntas e marginais no probLO é assintoticamente equivalente ao cálculo direto na rede bayesiana ($O(n)$ para conjuntas e $O(n^2 2^k)$ para marginais, onde $n$ é o número de variáveis e $k$ o número de variáveis marginalizadas).
• Otimização: Os autores sugerem que a análise estática do objetivo inicial pode evitar backtracking desnecessário, selecionando o método simples correto em cada tabela condicional antes da execução, baseando-se na consistência booleana.

5. Significado e Impacto

• Unificação Teórica: O trabalho oferece uma fundação lógica rigorosa para a inferência bayesiana, unindo a teoria da prova (cálculo de sequentes, focos de prova) com a teoria da probabilidade.
• Semântica Interna: Ao contrário de sistemas que usam lógica para representar a estrutura e um motor externo para calcular números, o probLO realiza o cálculo numérico dentro do processo de busca por prova, utilizando a multiplicação e adição como regras operacionais da lógica.
• Flexibilidade Estrutural: O uso de métodos multi-head e conectivos lineares permite representar dependências complexas (DAGs) de forma natural, sem forçar a estrutura em árvores ou depender de cláusulas auxiliares complexas.
• Futuro: O trabalho abre caminho para a implementação de algoritmos de inferência otimizados (como árvores de cliques ou eliminação de variáveis) diretamente no nível da prova lógica, explorando a sensibilidade a recursos da Lógica Linear para modelar a eficiência computacional.

Em suma, o probLO demonstra que a Programação Lógica Linear, com suas regras de consumo de recursos e métodos multi-head, é um framework expressivo e matematicamente sólido para a representação e computação de Redes Bayesianas.