Hispanopedia Wiki
Articulo de referencia

Programación lógica abductiva

La programación lógica abductiva ( PLA ) es un marco de representación del conocimiento de alto nivel que permite resolver problemas de forma declarativa, basándose en el razona...

Hispanopedia WikiContenido en espanolLectura gratuita

La programación lógica abductiva ( PLA ) es un marco de representación del conocimiento de alto nivel que permite resolver problemas de forma declarativa, basándose en el razonamiento abductivo . Extiende la programación lógica convencional al permitir que algunos predicados se definan de forma incompleta, denominándose predicados abducibles. La resolución de problemas se lleva a cabo mediante la derivación de hipótesis sobre estos predicados abducibles (hipótesis abductivas) como soluciones a los problemas a resolver. Estos problemas pueden ser observaciones que requieren explicación (como en la abducción clásica) u objetivos que deben alcanzarse (como en la programación lógica convencional ). Se puede utilizar para resolver problemas en diagnóstico, planificación , lenguaje natural y aprendizaje automático . También se ha utilizado para interpretar la negación como un fallo, en una forma de razonamiento abductivo.

Sintaxis

Los programas de lógica abductiva tienen tres componentes,⟨PAG,A,Ido⟩,{\displaystyle \langle P,A,IC\rangle,}dónde:

  • P es un programa lógico exactamente de la misma forma que en la programación lógica.
  • A es un conjunto de nombres de predicados, llamados predicados abducibles.
  • IC es un conjunto de fórmulas clásicas de primer orden .

Normalmente, el programa lógico P no contiene ninguna cláusula cuyo encabezado (o conclusión) haga referencia a un predicado abducible. (Esta restricción puede hacerse sin pérdida de generalidad). Además, en la práctica, muchas veces, las restricciones de integridad en IC suelen estar restringidas a la forma de negaciones, es decir, cláusulas de la forma:

 falso:- A1,...,An, no B1, ..., no Bm.

Esta restricción implica que no es posible que todos los A1,...,An sean verdaderos y al mismo tiempo todos los B1,...,Bm sean falsos.

Significado informal y resolución de problemas

Las cláusulas en P definen un conjunto de predicados no abducibles y, a través de ellos, proporcionan una descripción (o modelo) del dominio del problema. Las restricciones de integridad en IC especifican propiedades generales del dominio del problema que deben respetarse en cualquier solución del mismo.

Un problema, G , que expresa una observación que necesita ser explicada o un objetivo que se desea, se representa mediante una conjunción de literales positivos y negativos (NAF). Estos problemas se resuelven calculando "explicaciones abductivas" de G.

Una explicación abductiva de un problema G es un conjunto de instancias básicas positivas (y a veces también negativas) de los predicados abducibles, de tal manera que, al añadirlas al programa lógico P, se cumplen tanto el problema G como las restricciones de integridad IC. Así, las explicaciones abductivas extienden el programa lógico P mediante la adición de definiciones completas o parciales de los predicados abducibles. De este modo, las explicaciones abductivas forman soluciones al problema según la descripción del dominio del problema en P e IC. La extensión o completitud de la descripción del problema proporcionada por las explicaciones abductivas aporta información nueva, hasta entonces no contenida en la solución al problema. Se pueden aplicar criterios de calidad para preferir una solución sobre otra, a menudo expresados ​​mediante restricciones de integridad, para seleccionar explicaciones abductivas específicas del problema G.

En la programación lógica algebraica (PLA), la computación combina el razonamiento regresivo de la programación lógica normal (para reducir los problemas a subproblemas) con una especie de verificación de integridad para demostrar que las explicaciones abductivas satisfacen las restricciones de integridad.

Los dos ejemplos siguientes, escritos en un inglés estructurado sencillo en lugar de con la sintaxis estricta de ALP, ilustran la noción de explicación abductiva en ALP y su relación con la resolución de problemas.

Ejemplo 1

El programa de lógica abductiva,⟨PAG,A,Ido⟩{\displaystyle \langle P,A,{\mathit {IC}}\rangle }, tiene enPAG{\displaystyle P}Las siguientes oraciones:

 El césped está mojado si llovió. El césped está mojado si el aspersor estaba encendido. El sol brillaba.

Los predicados abducibles enA{\displaystyle A}son "llovió" y "el aspersor estaba encendido" y la única restricción de integridad enIdo{\displaystyle {\mathit {IC}}}es:

 falso si llovía y brillaba el sol.

La observación de que el césped está mojado tiene dos posibles explicaciones: «llovió» y «el aspersor estaba encendido», las cuales implican dicha observación. Sin embargo, solo la segunda explicación, «el aspersor estaba encendido», satisface la restricción de integridad.

Ejemplo 2

Consideremos el programa lógico abductivo que consta de las siguientes cláusulas (simplificadas):

 X es ciudadano si X nació en los EE. UU. X es ciudadano si X nació fuera de los EE. UU. y X es residente de los EE. UU . y X se naturalizó. X es ciudadano si X nació fuera de los EE. UU . y Y es la madre de X y Y es ciudadana y X está registrado. Mary es la madre de John. Mary es ciudadana.

junto con los cinco predicados abducibles, "nació en los EE. UU.", "nació fuera de los EE. UU.", "es residente de los EE. UU.", "es naturalizado" y "está registrado" y la restricción de integridad:

 falso si John reside en los Estados Unidos.

El objetivo "John es ciudadano" tiene dos soluciones abductivas: "John nació en los EE. UU." y "John nació fuera de los EE. UU.", o "John está registrado". La posible solución de obtener la ciudadanía por residencia y naturalización falla porque viola la restricción de integridad.

Un ejemplo más complejo, escrito también con la sintaxis más formal de ALP, es el siguiente.

Ejemplo 3

El programa de lógica abductiva que se muestra a continuación describe un modelo simple del metabolismo de la lactosa de la bacteria E. coli. El programa, P , describe (en su primera regla) que E. coli puede alimentarse del azúcar lactosa si produce dos enzimas: permeasa y galactosidasa. Como todas las enzimas, estas se producen si están codificadas por un gen (Gen) que se expresa (descrito por la segunda regla). Las dos enzimas, permeasa y galactosidasa, están codificadas por dos genes, lac(y) y lac(z) respectivamente (indicados en la quinta y sexta regla del programa), en un grupo de genes (lac(X)) —llamado operón— que se expresa cuando las cantidades (amt) de glucosa son bajas y las de lactosa son altas, o cuando ambas se encuentran en un nivel medio (véanse la cuarta y quinta regla). Los abducibles, A , declaran todas las instancias básicas del predicado "cantidad" como asumibles. Esto refleja que, en el modelo, las cantidades de las diversas sustancias en cualquier momento son desconocidas. Esta es información incompleta que debe determinarse en cada caso particular. Las restricciones de integridad, IC , establecen que la cantidad de cualquier sustancia (S) solo puede tomar un valor.

Conocimiento del dominio (P)
alimentar ( lactosa ) :- hacer ( permeasa ), hacer ( galactosidasa ). hacer ( Enzima ) :- codificar ( Gen , Enzima ), expresar ( Gen ). expresar ( lac ( X )) :- cantidad ( glucosa , baja ), cantidad ( lactosa , alta ). expresar ( lac ( X )) :- cantidad ( glucosa , media ), cantidad ( lactosa , media ). codificar ( lac ( y ), permeasa ). codificar ( lac ( z ), galactosidasa ). temperatura ( baja ) :- cantidad ( glucosa , baja ).
Restricciones de integridad (CI)
falso :- cantidad ( S , V1 ), cantidad ( S , V2 ), V1 ≠ V2 .
Abducibles (A)
abducible_predicate ( cantidad ).

El objetivo del problema esGRAMO=alimento (lactosa){\displaystyle G={\text{alimento(lactosa)}}}Esto puede surgir como una observación que debe explicarse o como un estado de cosas que debe alcanzarse mediante la elaboración de un plan. Este objetivo tiene dos explicaciones abductivas:

{Δ1={cantidad(lactosa, alto), cantidad(glucosa, bajo)}Δ2={cantidad(lactosa, media), cantidad(glucosa, media)}{\displaystyle {\begin{cases}\Delta _{1}=\{{\text{cantidad(lactosa, alta), cantidad(glucosa, baja)}}\}\\\Delta _{2}=\{{\text{cantidad(lactosa, media), cantidad(glucosa, media)}}\}\end{cases}}}

La decisión sobre cuál de las dos opciones adoptar podría depender de la información adicional disponible; por ejemplo, se puede saber que cuando el nivel de glucosa es bajo, el organismo presenta un comportamiento determinado. En el modelo, dicha información adicional es que la temperatura del organismo es baja, y al observar la veracidad o falsedad de esto, es posible elegir la primera o la segunda explicación, respectivamente.

Una vez elegida una explicación, esta pasa a formar parte de la teoría, la cual puede utilizarse para extraer nuevas conclusiones. La explicación, y en general estas nuevas conclusiones, constituyen la solución del problema.

Razonamiento por defecto en ALP

Como se muestra en el sistema Theorist, [ 1 ] [ 2 ] la abducción también puede usarse para el razonamiento por defecto . Además, la abducción en ALP puede simular la negación como un fallo en la programación lógica normal.

Consideremos el ejemplo clásico del razonamiento por defecto: que un pájaro puede volar si no se puede demostrar que es anormal. He aquí una variante del ejemplo que utiliza la negación como fallo:

canfly ( X ) :- pájaro ( X ), no ( ave_voladora_anormal ( X )). ave_voladora_anormal ( X ):- herido ( X ). pájaro ( john ). pájaro ( mary ). herido ( john ).

Aquí se muestra el mismo ejemplo utilizando un predicado abducible con una restricción de integridad en ALP:normal_flying_bird(_)

canfly ( X ) :- pájaro ( X ), pájaro_volador_normal ( X ). falso :- pájaro_volador_normal ( X ), herido ( X ). pájaro ( john ). pájaro ( mary ). herido ( john ).

El predicado abducible es el contrario del predicado .normal_flying_bird(_),abnormal_flying_bird(_)

Utilizando la abducción en ALP es posible concluir bajo la suposición . La conclusión se puede derivar de la suposición porque no se puede demostrar que se viole la restricción de integridad, lo cual se debe a que no se puede demostrar que En contraste, no es posible concluir porque la suposición junto con el hecho viola la restricción de integridad. Esta forma de razonamiento en ALP simula el razonamiento con la negación como fallo. [ 3 ]canfly(mary)normal_flying_bird(mary)wounded(mary).canfly(john),normal_flying_bird(john)wounded(john)

Por el contrario, es posible simular la abducción en ALP usando la negación como fallo con la semántica del modelo estable . [ 4 ] Esto se puede hacer añadiendo, para cada predicado abducible, un predicado contrario adicional y un par de cláusulas:p,negp,

p :- no ( negp ). negp :- no ( p ).

Este par de cláusulas tiene dos modelos estables, uno en el que es verdadero y otro en el que es verdadero. Esta técnica para simular el secuestro se usa comúnmente en la programación de conjuntos de respuestas para resolver problemas mediante una metodología de generación y prueba .p,negp,

semántica formal

La semántica formal de la noción central de una explicación abductiva en ALP se puede definir de la siguiente manera.

Dado un programa de lógica abductiva,⟨PAG,A,Ido⟩{\displaystyle \langle P,A,{\mathit {IC}}\rangle }, una explicación abductiva para un problemaGRAMO{\displaystyle G}es un conjuntoΔ{\displaystyle \Delta }de átomos fundamentales sobre predicados abducibles tales que:

  • PAG∪Δ⊨GRAMO{\displaystyle P\cup \Delta \models G}
  • PAG∪Δ⊨Ido{\displaystyle P\cup \Delta \models IC}
  • PAG∪Δ{\displaystyle P\cup \Delta }es consistente

Esta definición deja abierta la elección de la semántica subyacente de la programación lógica a través de la cual damos el significado exacto de la relación de implicación.⊨{\displaystyle \models }y la noción de consistencia de los programas lógicos (extendidos). Cualquiera de las diferentes semánticas de la programación lógica, como la semántica de completitud, la estable o la bien fundada, puede (y se ha utilizado en la práctica) para dar diferentes nociones de explicaciones abductivas y, por lo tanto, diferentes formas de marcos de programación abductiva.

La definición anterior adopta una perspectiva particular sobre la formalización del rol de las restricciones de integridad.Ido{\displaystyle {\mathit {IC}}}como restricciones sobre las posibles soluciones abductivas. Requiere que estas se deriven del programa lógico extendido con una solución abductiva, lo que significa que en cualquier modelo del programa lógico extendido (que se puede pensar como un mundo resultante dadoΔ{\displaystyle \Delta }) se cumplen los requisitos de las restricciones de integridad. En algunos casos, esto puede ser innecesariamente fuerte y el requisito más débil de consistencia, a saber, quePAG∪Ido∪Δ{\displaystyle P\cup {\mathit {IC}}\cup \Delta }Es consistente, puede ser suficiente, lo que significa que existe al menos un modelo (mundo resultante posible) del programa extendido donde se cumplen las restricciones de integridad. En la práctica, en muchos casos, estas dos formas de formalizar el rol de las restricciones de integridad coinciden, ya que el programa lógico y sus extensiones siempre tienen un modelo único. Muchos de los sistemas ALP utilizan la vista de implicación de las restricciones de integridad, ya que esta se puede implementar fácilmente sin necesidad de procedimientos especializados adicionales para la satisfacción de las restricciones de integridad, puesto que esta vista trata las restricciones de la misma manera que el objetivo del problema. En muchos casos prácticos, la tercera condición en esta definición formal de una explicación abductiva en ALP se satisface trivialmente o está contenida en la segunda condición mediante el uso de restricciones de integridad específicas que capturan la consistencia.

Implementación y sistemas

La mayoría de las implementaciones de ALP extienden el modelo computacional de programación lógica basado en la resolución SLD. ALP también puede implementarse mediante su vinculación con la Programación de Conjuntos de Respuestas (ASP), donde se pueden emplear los sistemas ASP. Ejemplos de sistemas que utilizan este enfoque son ACLP, A-system, CIFF, SCIFF, ABDUAL y ProLogICA.

Véase también

Notas

  1. ↑ Poole, David; Goebel, Randy; Aleliunas, Romas (febrero de 1986). Theorist: Un sistema de razonamiento lógico para valores predeterminados y diagnóstico (PDF) (Informe de investigación). Univ. Waterloo.
  2. ↑ Poole, David; Goebel, Randy; Aleliunas, Romas (1987). «Theorist: A Logical Reasoning System for Defaults and Diagnosis». En Nick J. Cercone; Gordon McCalla (eds.). The Knowledge Frontier – Essays in the Representation of Knowledge . Symbolic Computation (1.ª ed.). Nueva York, NY: Springer. pp. 331–352 . doi : 10.1007/978-1-4612-4792-0 . ISBN   978-1-4612-9158-9. S2CID 38209923 . 
  3. ↑ Eshghi, K. y Kowalski, RA, 1989, junio. La abducción comparada con la negación por fracaso. En ICLP (Vol. 89, págs. 234-255).
  4. ↑ Kakas, AC, Kowalski, RA y Toni, F. , 1992. Programación lógica abductiva. Journal of logic and computation, 2(6), pp.719-770.

Referencias

  • Poole, D.; Goebel, R.; Aleliunas, R. (1987). «Theorist: un sistema de razonamiento lógico para valores predeterminados y diagnóstico» . En Cercone, Nick; McCalla, Gordon (eds.). La frontera del conocimiento: ensayos sobre la representación del conocimiento . Springer. pp. 331–352 . ISBN  978-0-387-96557-4.
  • Kakas, AC; Mancarella, P. (1990). «Modelos estables generalizados: una semántica para la abducción». En Aiello, LC (ed.). ECAI 90: actas de la 9.ª Conferencia Europea sobre Inteligencia Artificial . Pitman. pp. 385–391 . ISBN  978-0273088226.
  • Console, L.; Dupre, DT; Torasso, P. (1991). "Sobre la relación entre abducción y deducción". Journal of Logic and Computation . 1 (5): 661– 690. CiteSeerX 10.1.1.31.9982 . doi : 10.1093/logcom/1.5.661 . 
  • Kakas, AC; Kowalski, RA ; Toni, F. (1993). "Programación lógica abductiva". Journal of Logic and Computation . 2 (6): 719– 770. CiteSeerX 10.1.1.37.3655 . doi : 10.1093/logcom/2.6.719 . 
  • Denecker, Marc; De Schreye, Danny (febrero de 1998). "SLDNFA: Un procedimiento abductivo para programas lógicos abductivos". Journal of Logic Programming . 34 (2): 111– 167. CiteSeerX 10.1.1.21.6503 . doi : 10.1016/S0743-1066(97)00074-5 . 
  • Denecker, M.; Kakas, AC (julio de 2000). "Número especial: programación lógica abductiva" . Journal of Logic Programming . 44 ( 1–3 ): 1–4 . doi : 10.1016/S0743-1066(99)00078-3 .
  • Denecker, M.; Kakas, AC (2002). «Abducción en programación lógica» . En Kakas, AC; Sadri, F. (eds.). Lógica computacional: Programación lógica y más allá: Ensayos en honor a Robert A. Kowalski . Lecture Notes in Computer Science. Vol.  2407. Springer. pp. 402–437 . ISBN  978-3-540-43959-2.
  • Poole, D. (1993). "Abducción probabilística de Horn y redes bayesianas" (PDF) . Inteligencia artificial . 64 (1): 81– 129. doi : 10.1016/0004-3702(93)90061-F .
  • Esposito, F.; Ferilli, S.; Basile, TMA; Di Mauro, N. (febrero de 2007). "Inferencia de teorías de abducción para el manejo de la incompletitud en el aprendizaje de primer orden" (PDF) . Knowledge and Information Systems . 11 (2): 217– 242. doi : 10.1007/s10115-006-0019-5 . S2CID 10699982. Archivado del original (PDF) el 17 de julio de 2011. 
  • ACLP
  • LCA
  • CIENCIA
  • Un sistema