Hispanopedia Wiki
Articulo de referencia

Programación lógica probabilística

La programación lógica probabilística es un paradigma de programación que combina la programación lógica con las probabilidades. La mayoría de los enfoques de la programación ló...

Hispanopedia WikiContenido en espanolLectura gratuita

La programación lógica probabilística es un paradigma de programación que combina la programación lógica con las 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 sobre las interpretaciones del universo de Herbrand del programa.

Idiomas

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 Abducción de Horn Probabilística, PRISM, Lógica de Elección Independiente, Datalog probabilístico , Programas Lógicos con Disyunciones Anotadas, ProbLog , P-log y CP-logic. Si bien el número 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 ]

Semántica

Bajo la semántica de distribución, un programa lógico probabilístico se interpreta como un conjunto de hechos probabilísticos independientes ( fórmulas atómicas básicas anotadas con una probabilidad) y un programa lógico que puede usar los hechos probabilísticos en el cuerpo de sus cláusulas. La probabilidad de cualquier asignación de valores de verdad a las bases de las fórmulas asociadas con los hechos probabilísticos viene dada por el producto de sus probabilidades; esto es equivalente a suponer que las elecciones de los hechos probabilísticos son variables aleatorias independientes . [ 1 ] [ 3 ]

Programas estratificados

Si para cualquier elección de valores de verdad para los hechos probabilísticos, el programa lógico resultante es estratificado , tiene un modelo de 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 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 ]

Programas de conjuntos de respuestas

La semántica de modelos estables subyacente 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 credal asigna un conjunto credal a cada consulta. Su límite inferior de probabilidad 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 superior de probabilidad se define considerando aquellas asignaciones para las cuales la consulta es verdadera en algún conjunto de respuestas (razonamiento audaz). [ 4 ] [ 5 ]

Inferencia

Bajo 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 de 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 donde 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 impracticable, ya que el número de mundos posibles es exponencial en el número de hechos probabilísticos básicos. [ 2 ] De hecho, incluso 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 ]

Inferencia exacta

Por lo general, la inferencia exacta se realiza recurriendo a la compilación de conocimiento : según este método, una teoría proposicional y una consulta se compilan en un "lenguaje objetivo", 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 objetivo y en la clase de consultas y transformaciones que admiten en tiempo polinomial. [ 2 ]

Inferencia aproximada

Dado que el costo de la inferencia puede ser muy elevado, se han desarrollado algoritmos aproximados. Estos calculan subconjuntos de explicaciones posiblemente incompletas o utilizan muestreo aleatorio. En el primer enfoque, un subconjunto de las explicaciones proporciona una cota inferior y el conjunto de explicaciones parcialmente expandidas proporciona una cota superior. En el segundo enfoque, la veracidad de la consulta se verifica repetidamente en un programa lógico ordinario muestreado del programa probabilístico. La probabilidad de la consulta viene dada entonces por la fracción de éxitos. [ 2 ] [ 10 ]

Aprendiendo

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 que las cláusulas son proporcionadas por el usuario, y el aprendizaje de la estructura, en el que las cláusulas 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 maximización de expectativas o el descenso de gradiente , mientras que el aprendizaje de la estructura se puede realizar buscando en el espacio de cláusulas posibles bajo una variedad de heurísticas. [ 2 ]

Véase también

Referencias

  1. 1 2 3 4 Riguzzi, Fabrizio; Swift, Theresa (2018-09-01), "Una revisión de la programación lógica probabilística" , Programación lógica declarativa: teoría, sistemas y aplicaciones , ACM, pp. 185–228 , doi : 10.1145/3191315.3191319 , ISBN  978-1-970001-99-0, S2CID 70180651 , consultado el 25/10/2023 
  2. 1 2 3 4 5 6 7 Riguzzi, Fabrizio; Bellodi , Elena; Zese, Riccardo (2014). "Una historia de la programación lógica inductiva probabilística" . Fronteras en Robótica e IA . 1. doi : 10.3389/frobt.2014.00006 . ISSN 2296-9144 . 
  3. ↑ De Raedt, Luc; Kimmig, Angelika (2015-07-01). "Conceptos de programación probabilística (lógica)" . Machine Learning . 100 (1): 5– 47. doi : 10.1007/s10994-015-5494-z . ISSN 1573-0565 . 
  4. 1 2 3 Riguzzi, Fabrizio (22 de mayo de 2023), "Programación probabilística de conjuntos de respuestas" , Fundamentos de la programación lógica probabilística , Nueva York: River Publishers, págs. 165–173 , doi : 10.1201/9781003427421-6 , ISBN  978-1-003-42742-1, recuperado el 3 de febrero de 2024
  5. 1 2 Cozman, Fabio Gagliardi; Mauá, Denis Deratani (2020). "La alegría de la programación de conjuntos de respuestas probabilísticas: semántica, complejidad, expresividad, inferencia" . International Journal of Approximate Reasoning . 125 : 218–239 . doi : 10.1016/j.ijar.2020.07.004 . S2CID 222233309 . 
  6. ↑ Baral, Chitta; Gelfond, Michael; Rushton, Nelson (2009). "Razonamiento probabilístico con conjuntos de respuestas" . Theory and Practice of Logic Programming . 9 (1): 57– 144. doi : 10.1017/S1471068408003645 . ISSN 1471-0684 . 
  7. ↑ Poole, David (1993). "Abducción de Horn probabilística y redes bayesianas" . Inteligencia Artificial . 64 (1): 81– 129. doi : 10.1016/0004-3702(93)90061-f . ISSN 0004-3702 . 
  8. ↑ Sato, Taisuke (1995), "Un método de aprendizaje estadístico para programas lógicos con semántica de distribución" , Actas de la 12.ª Conferencia Internacional sobre Programación Lógica , The MIT Press, págs. 715–730 , doi : 10.7551/mitpress/4298.003.0069 , ISBN  978-0-262-29143-9, consultado el 25/10/2023
  9. ↑ Riguzzi, Fabrizio (2023). Fundamentos de la programación lógica probabilística: lenguajes, semántica, inferencia y aprendizaje (2.ª ed.). Gistrup, Dinamarca: River Publishers . p. 180. ISBN   978-87-7022-719-3.
  10. ↑ Kimmig, Angelika; Demoen, Bart; Raedt, Luc De; Costa, Vítor Santos; Rocha, Ricardo (2011). "Sobre la implementación del lenguaje de programación lógica probabilística ProbLog" . Theory and Practice of Logic Programming . 11 ( 2–3 ): 235–262 . arXiv : 1006.4442 . doi : 10.1017/S1471068410000566 . ISSN 1475-3081 . S2CID 2022299 .  

A fecha de 3 de febrero de 2024, este artículo se deriva total o parcialmente de Riguzzi, Fabrizio; Bellodi, Elena; Zese, Riccardo (2014). " A History of Probabilistic Inductive Logic Programming" . Frontiers in Robotics and AI . 1. doi : 10.3389/frobt.2014.00006 .El titular de los derechos de autor ha otorgado una licencia que permite la reutilización del contenido bajo las licencias CC BY-SA 3.0 y GFDL . Deben respetarse todos los términos pertinentes.