La programación lógica probabilística es un paradigma de programación que combina la programación lógica con probabilidades.
La mayoría de los enfoques de la programación lógica probabilística se basan en la semántica de distribución, que divide un programa en un conjunto de hechos probabilísticos y un programa lógico. Define una distribución de probabilidad a partir de las interpretaciones del universo Herbrand del programa.
La mayoría de los enfoques de la programación lógica probabilística se basan en la semántica de distribución [1], que subyace a muchos lenguajes como Probabilistic Horn Abduction, PRISM, Independent Choice Logic, probabilistic Datalog , Logic Programs with Annotated Disjunctions, ProbLog , P-log y CP-logic. Si bien la cantidad de lenguajes es grande, muchos comparten un enfoque común, de modo que existen transformaciones con complejidad lineal que pueden traducir un lenguaje a otro. [2]
Bajo la semántica de distribución, un programa de lógica probabilística se interpreta como un conjunto de hechos probabilísticos independientes ( fórmulas atómicas fundamentales anotadas con una probabilidad) y un programa lógico que puede usar los hechos probabilísticos en los cuerpos de sus cláusulas. La probabilidad de cualquier asignación de valores de verdad a los fundamentos de las fórmulas asociadas con los hechos probabilísticos está dada por el producto de sus probabilidades; esto es equivalente a suponer que las elecciones de hechos probabilísticos son variables aleatorias independientes . [1] [3]
Si para cualquier elección de valores de verdad para los hechos probabilísticos, el programa lógico resultante está estratificado , tiene un modelo Herbrand mínimo único que puede verse como la interpretación única asociada con esa elección de valores de verdad. [1]
Las subclases importantes de los programas estratificados son los programas positivos, que no utilizan la negación, pero pueden ser recursivos, y los programas acíclicos, que pueden utilizar la negación pero no tienen dependencias recursivas. [1]
La semántica del modelo estable que subyace a la programación de conjuntos de respuestas da sentido a los programas no estratificados al asignar potencialmente más de un conjunto de respuestas a cada asignación de valor de verdad de los hechos probabilísticos. Esto plantea la cuestión de cómo distribuir la masa de probabilidad entre los conjuntos de respuestas. [4] [5]
El lenguaje de programación lógica probabilística P-Log resuelve esto dividiendo la masa de probabilidad equitativamente entre los conjuntos de respuestas, siguiendo el principio de indiferencia . [4] [6]
Alternativamente, la programación de conjuntos de respuestas probabilísticas bajo la semántica de credos asigna un conjunto de credos a cada consulta. Su límite de probabilidad inferior se define considerando únicamente aquellas asignaciones de valores de verdad de los hechos probabilísticos para los cuales la consulta es verdadera en cada conjunto de respuestas del programa resultante (razonamiento cauteloso); su límite de probabilidad superior se define considerando aquellas asignaciones para las cuales la consulta es verdadera en algún conjunto de respuestas (razonamiento valiente). [4] [5]
En el marco de la semántica de distribución, un programa de lógica probabilística define una distribución de probabilidad sobre las interpretaciones de sus predicados en su universo Herbrand . La probabilidad de una consulta básica se obtiene entonces a partir de la distribución conjunta de la consulta y los mundos: es la suma de la probabilidad de los mundos en los que la consulta es verdadera. [2] [7] [8]
El problema de calcular la probabilidad de las consultas se denomina inferencia (marginal) . Resolverlo calculando todos los mundos y luego identificando aquellos que implican la consulta es poco práctico ya que el número de mundos posibles es exponencial en el número de hechos probabilísticos básicos. [2] De hecho, ya para programas acíclicos y consultas atómicas , calcular la probabilidad condicional de una consulta dada una conjunción de átomos como evidencia es #P -completo. [9]
Por lo general, la inferencia exacta se realiza recurriendo a la compilación de conocimiento : según esto, una teoría proposicional y una consulta se compilan en un “lenguaje de destino”, que luego se utiliza para responder consultas en tiempo polinomial . La compilación se convierte en el principal cuello de botella computacional, pero se ha dedicado un esfuerzo considerable al desarrollo de compiladores eficientes. Los métodos de compilación difieren en la compacidad del lenguaje de destino y la clase de consultas y transformaciones que admiten en tiempo polinomial. [2]
Como el costo de la inferencia puede ser muy alto, se han desarrollado algoritmos aproximados que calculan subconjuntos de explicaciones posiblemente incompletas o utilizan un muestreo aleatorio. En el primer enfoque, un subconjunto de las explicaciones proporciona un límite inferior y el conjunto de explicaciones parcialmente expandidas proporciona un límite superior. En el segundo enfoque, la veracidad de la consulta se comprueba repetidamente en un programa de lógica común muestreado del programa probabilístico. La probabilidad de la consulta se da entonces por la fracción de éxitos. [2] [10]
La programación lógica inductiva probabilística tiene como objetivo aprender programas lógicos probabilísticos a partir de datos. Esto incluye el aprendizaje de parámetros, que estima las anotaciones de probabilidad de un programa mientras el usuario proporciona las cláusulas, y el aprendizaje de estructuras, en el que las cláusulas mismas son inducidas por el sistema de programación lógica inductiva probabilística. [2]
Los enfoques comunes para el aprendizaje de parámetros se basan en la expectativa-maximización o el descenso de gradiente , mientras que el aprendizaje de estructura se puede realizar buscando el espacio de cláusulas posibles bajo una variedad de heurísticas. [2]
A partir del 3 de febrero de 2024, este artículo se deriva total o parcialmente de Riguzzi, Fabrizio; Bellodi, Elena; Zese, Riccardo (2014). "Una historia de la programación lógica inductiva probabilística". Frontiers in Robotics and AI . 1 . doi : 10.3389/frobt.2014.00006 . El titular de los derechos de autor ha otorgado una licencia para el contenido que permite su reutilización conforme a CC BY-SA 3.0 y GFDL . Se deben respetar todos los términos pertinentes.