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

1. El Problema

La programación lógica probabilística (PLP) busca integrar conocimiento lógico estructurado con información incierta. Sin embargo, representar y razonar sobre Redes Bayesianas dentro de marcos de programación lógica existentes presenta desafíos significativos:

• Estructura de Dependencias: La mayoría de los enfoques de PLP (como ProbLog, PRISM, LPADs) se basan en lógica clásica o cláusulas de Horn, donde cada método tiene una sola cabeza (un átomo). Esto sugiere implícitamente una estructura de dependencias en forma de árbol. Las redes bayesianas, en cambio, son grafos acíclicos dirigidos donde una variable puede tener múltiples padres y múltiples hijos, lo que no se modela naturalmente con cláusulas de una sola cabeza.
• Reutilización de Recursos: En la lógica clásica, las cláusulas pueden reutilizarse infinitamente. En una red bayesiana, el cálculo de la probabilidad condicional de un nodo debe ser lineal: cada variable debe computarse exactamente una vez por consulta para evitar redundancias y errores en la propagación de probabilidades.
• Interpretación Semántica Externa: Muchos sistemas actuales requieren una interpretación semántica externa para calcular las probabilidades, separando la lógica del cálculo numérico.

2. Metodología

Los autores proponen probLO (Probabilistic Linear Objects), una extensión del lenguaje LO (Linear Objects) de Andreoli y Pareschi, el cual está fundamentado en la Lógica Lineal Multiplicativa-Aditiva (MALLmix).

Fundamentos Teóricos

• Lógica Lineal (LL): Se utiliza por su sensibilidad a los recursos. En LL, las proposiciones se consumen al usarse, lo que encaja perfectamente con la intuición de que una variable en una red bayesiana debe computarse una sola vez.
• Pruebas Focalizadas (Focusing Proofs): La semántica operativa se deriva de la teoría de pruebas focalizadas. Los métodos de programación se modelan como bipolos (fórmulas de la forma $P \otimes N$, donde $P$ es positivo y $N$ negativo).
• Cláusulas Multi-cabeza: La innovación clave es el uso de métodos con múltiples cabezas (multi-head). En probLO, un método puede tener varias cabezas ($h_1, ..., h_n$) y un cuerpo ($b_1, ..., b_m$). Esto permite representar la dependencia condicional $Pr(X_1, ..., X_n | Y_1, ..., Y_m)$ de manera directa, donde las $X$ son las cabezas y las $Y$ el cuerpo.

Definición de probLO

• Sintaxis: Un método probabilístico se anota con un valor $p \in [0, 1]$.
  $$p :: [h_1, ..., h_n] :- [b_1, ..., b_m]$$
• Semántica Operativa:
  • El estado del programa es un secuente ponderado: $p :: P ; \Gamma$, donde $p$ es la probabilidad acumulada, $P$ es el programa y $\Gamma$ es el multiconjunto de objetivos actuales.
  • Regla exp (Expansión): Al aplicar un método, la probabilidad del estado se actualiza multiplicando la probabilidad de los premisos por la probabilidad del método ($q \cdot p$).
  • Regla bra (Bifurcación): Para manejar la incertidumbre (disyunción aditiva $\parr$), el sistema bifurca la ejecución en dos ramas (ej. $X=True$y$X=False$) y suma las probabilidades de los resultados finales.
  • Consistencia Booleana: Se garantiza que una derivación exitosa nunca contenga simultáneamente los átomos ttX (True) y ffX (False) para la misma variable, asegurando la coherencia lógica.

Codificación de Redes Bayesianas

Cada nodo de la red bayesiana se codifica como una tabla probLO (probLO-table), que agrupa métodos simples para cada combinación posible de valores de los padres.

• Si una variable $X$ tiene padres $Y_1, ..., Y_k$, la tabla contiene métodos para cada asignación de valores de los padres, produciendo las probabilidades condicionales de $X$.
• El teorema de factorización de las redes bayesianas se refleja directamente en la estructura de la búsqueda de pruebas: la probabilidad conjunta es el producto de las probabilidades de cada paso de la derivación.

3. Contribuciones Clave

1. probLO: Introducción de un lenguaje de programación lógica probabilística basado en lógica lineal que soporta métodos multi-cabeza y computación numérica interna.
2. Caracterización de Grafos Acíclicos (Teorema 2): Demostración de que la ausencia de ciclos en un grafo dirigido puede caracterizarse y decidirse en tiempo lineal dentro del marco de LO puro (usando la regla mix), mediante una exploración de grafos de hojas a raíces.
3. Cálculo Directo de Probabilidades (Teorema 3): Prueba formal de que la semántica operativa de probLO calcula correctamente:
   • Probabilidades Conjuntas: El producto de las probabilidades de los métodos aplicados en una derivación sin bifurcación.
   • Probabilidades Marginales: La suma de las probabilidades de las derivaciones que resultan de las reglas de bifurcación (bra) sobre las variables no observadas.
4. Eliminación de Interpretación Externa: El sistema realiza los cálculos numéricos internamente durante la búsqueda de pruebas, sin depender de motores externos de inferencia.

4. Resultados

• Correctitud: Se demuestra que la derivación de un estado $p :: P ; \Gamma$ en probLO es válida si y solo si $p$ es igual a la probabilidad conjunta o marginal correspondiente definida por la red bayesiana codificada.
• Complejidad: El costo computacional para calcular probabilidades conjuntas es $O(n)$ y para marginales es $O(n 2^k)$ (donde $n$ es el número de variables y $k$ el número de variables marginales), lo cual es comparable a los métodos estándar de inferencia en redes bayesianas.
• Ejemplos: El artículo incluye ejemplos detallados (Figuras 1, 2 y 9) mostrando cómo una red bayesiana clásica (nubes, lluvia, aspersores, pasto mojado, tráfico) se codifica y cómo se deriva la probabilidad marginal de un evento específico paso a paso, mostrando la multiplicación y suma de probabilidades directamente en la estructura de la prueba.

5. Significado e Impacto

• Unificación Teórica: El trabajo establece un puente sólido entre la teoría de la demostración (Lógica Lineal) y la inferencia probabilística. Muestra que las redes bayesianas pueden verse como procesos de búsqueda de pruebas en un sistema lógico específico.
• Gestión de Recursos: Resuelve el problema de la reutilización de variables en lógica probabilística al aprovechar la naturaleza "consumible" de la lógica lineal, asegurando que cada variable se procese exactamente una vez.
• Modularidad: Al usar bipolos y tablas modulares, el enfoque permite una representación clara y estructurada de dependencias complejas que no son árboles, superando las limitaciones de la lógica de Horn.
• Futuro: Los autores sugieren que este marco podría extenderse para incluir técnicas de optimización de inferencia bayesiana (como árboles de cliques o eliminación de variables) directamente en la semántica operativa, aprovechando la sensibilidad a los recursos de la lógica lineal para modelar algoritmos de inferencia avanzados a nivel de prueba.

En resumen, el paper presenta probLO como un marco teórico y práctico robusto que integra nativamente el razonamiento probabilístico en la lógica lineal, ofreciendo una alternativa elegante y formalmente verificable a los enfoques tradicionales de programación lógica probabilística para el manejo de redes bayesianas.