La programación lógica abductiva ( ALP ) es un marco de representación de conocimiento de alto nivel que se puede utilizar para resolver problemas de forma declarativa basándose en el razonamiento abductivo . Extiende la programación lógica normal al permitir que algunos predicados se definan de manera incompleta, declarados como predicados abducibles. La resolución de problemas se efectúa derivando hipótesis sobre estos predicados abducibles (hipótesis abductivas) como soluciones de problemas a resolver. Estos problemas pueden ser observaciones que deben explicarse (como en la abducción clásica) o metas que deben lograrse (como en la programación lógica normal ). Se puede utilizar para resolver problemas de diagnóstico, planificación , lenguaje natural yaprendizaje automático . También se ha utilizado para interpretar la negación como fracaso como una forma de razonamiento abductivo.
Sintaxis
Los programas de lógica abductiva tienen tres componentes, dónde:
- P es un programa lógico de exactamente 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 encabezamiento (o conclusión) se refiera a un predicado abducible. (Esta restricción se puede hacer sin pérdida de generalidad). También en la práctica, muchas veces, las restricciones de integridad en IC a menudo se restringen a la forma de denegaciones, es decir, cláusulas de la forma:
falso: - A1, ..., An, no B1, ..., no Bm.
Tal restricción significa que no es posible que todo A1, ..., An sea verdadero y al mismo tiempo todo B1, ..., Bm sea falso.
Significado informal y resolución de problemas
Las cláusulas en P definen un conjunto de predicados no abducibles y, a través de esto, 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 de un problema.
Un problema, G , que expresa una observación que debe explicarse o un objetivo que se desea, se representa mediante una conjunción de literales positivos y negativos (NAF). Tales problemas se resuelven mediante el cálculo de "explicaciones abductivas" de G .
Una explicación abductiva de un problema G es un conjunto de instancias fundamentales positivas (y a veces también negativas) de los predicados abducibles, de modo que, cuando se agregan al programa lógico P, se mantienen el problema G y las restricciones de integridad IC. Así, las explicaciones abductivas amplían el programa lógico P mediante la adición de definiciones completas o parciales de los predicados abducibles. De esta manera, las explicaciones abductivas forman soluciones del problema de acuerdo con la descripción del dominio del problema en P e IC. La extensión o finalización de la descripción del problema dada por las explicaciones abductivas proporciona nueva información, hasta ahora no contenida en la solución del problema. Criterios de calidad para preferir una solución sobre otra, a menudo expresada a través de las restricciones de integridad, se puede aplicar para seleccionar las explicaciones abductivas específicos del problema G .
La computación en ALP combina el razonamiento hacia atrás de la programación lógica normal (para reducir problemas a subproblemas) con una especie de verificación de integridad para mostrar que las explicaciones abductivas satisfacen las restricciones de integridad.
Los siguientes dos ejemplos, escritos en un inglés estructurado simple en lugar de en 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, , tiene en Las siguientes frases:
La hierba está mojada si llovió.
La hierba está mojada si el aspersor estaba encendido.
El sol estaba brillando.
Los predicados abducibles en son "llovió" y "el aspersor estaba encendido" y la única restricción de integridad en es:
falso si llovía y el sol brillaba.
La observación de que la hierba está mojada tiene dos posibles explicaciones, "llovió" y "el aspersor estaba encendido", que implican la observación. Sin embargo, solo la segunda posible explicación, "el aspersor estaba encendido", satisface la restricción de integridad.
Ejemplo 2
Considere el programa de lógica abductiva que consta de las siguientes cláusulas (simplificadas):
X es ciudadano si X nació en EE. UU.
X es ciudadano si X nació fuera de EE. UU. Y X es residente de EE. UU. Y X está naturalizado.
X es un ciudadano si X es nacido fuera de los EE.UU. , y Y es la madre de X e Y es un ciudadano y X se ha registrado.
María es la madre de Juan.
María 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.", "está naturalizado" y "está registrado" y la restricción de integridad:
falso si John es residente de EE. UU.
El objetivo "John es ciudadano" tiene dos soluciones abductivas, una de las cuales es "John nació en los EE. UU.", La otra es "John nació fuera de los EE. UU." Y "John está registrado". La solución potencial de convertirse en ciudadano por residencia y naturalización fracasa porque viola la restricción de integridad.
Un ejemplo más complejo que también está escrito en la sintaxis más formal de ALP es el siguiente.
Ejemplo 3
El siguiente programa de lógica abductiva 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 de 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 lactosa son altas o cuando ambas están en un nivel medio (ver la cuarta y quinta regla). Los abducibles, A , declaran todas las instancias básicas de los predicados "cantidad" como asumibles. Esto refleja que en el modelo se desconocen las cantidades en cualquier momento de las diversas sustancias. Ésta es información incompleta que debe determinarse en cada caso problemático. Las restricciones de integridad, IC , establecen que la cantidad de cualquier sustancia (S) solo puede tomar un valor.
- Conocimiento del dominio (P)
pienso ( lactosa ) : - fabricar ( permeasa ), fabricar ( galactosidasa ). hacer ( enzima ) : - código ( gen , enzima ), expresar ( gen ). express ( lac ( X )) : - cantidad ( glucosa , bajo ), cantidad ( lactosa , hi ). express ( lac ( X )) : - cantidad ( glucosa , medio ), cantidad ( lactosa , medio ). código ( lac ( y ), permease ). código ( lac ( z ), galactosidasa ). temperatura ( baja ) : - cantidad ( glucosa , baja ).
- Restricciones de integridad (IC)
falso : - monto ( S , V1 ), monto ( S , V2 ), V1 ≠ V2 .
- Abducibles (A)
abducible_predicate ( cantidad ).
El objetivo del problema es . Esto puede surgir como una observación que debe explicarse o como un estado de cosas que debe lograrse al encontrar un plan. Este objetivo tiene dos explicaciones abductivas:
La decisión de cuál de los dos adoptar podría depender de la información adicional que esté disponible, por ejemplo, se puede saber que cuando el nivel de glucosa es bajo, el organismo exhibe un cierto comportamiento; en el modelo, tal información adicional es que la temperatura del organismo es bajo - y al observar la verdad o falsedad de esto es posible elegir la primera o la segunda explicación respectivamente.
Una vez que se ha elegido una explicación, esta se convierte en parte de la teoría, que se puede utilizar para sacar nuevas conclusiones. La explicación y, de manera más general, estas nuevas conclusiones forman la solución del problema.
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, , una explicación abductiva de un problema es un conjunto de átomos de tierra en predicados abducibles tales que:
- 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. y la noción de coherencia de los programas lógicos (extendidos). Cualquiera de las diferentes semánticas de la programación lógica, como la semántica completa, estable o 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 ALP.
La definición anterior tiene una visión particular sobre la formalización del papel de las restricciones de integridad. como restricciones a las posibles soluciones abductivas. Requiere que estos estén implicados por el programa lógico extendido con una solución abductiva, lo que significa que en cualquier modelo del programa lógico extendido (que uno puede considerar como un mundo subsiguiente dado) se cumplen los requisitos de las restricciones de integridad. En algunos casos esto puede ser innecesariamente fuerte y el requisito de consistencia más débil, es decir, quees consistente, puede ser suficiente, lo que significa que existe al menos un modelo (posible mundo subsiguiente) del programa extendido donde se mantienen 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 vinculación de las restricciones de integridad, ya que esto se puede implementar fácilmente sin la necesidad de procedimientos especializados adicionales para satisfacer las restricciones de integridad, ya 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 coherencia.
Implementación y sistemas
La mayoría de las implementaciones de ALP amplían el modelo computacional de programación lógica basado en resolución SLD. ALP también se puede implementar mediante su enlace con la Programación de Conjunto de Respuestas (ASP), donde se pueden emplear los sistemas ASP. Ejemplos de sistemas del primer enfoque son ACLP, A-system, CIFF, SCIFF, ABDUAL y ProLogICA.
Ver también
Notas
Referencias
- Poole, D .; Goebel, R .; Aleliunas, R. (1987). "Teórico: un sistema de razonamiento lógico para los defectos y el diagnóstico" . En Cercone, Nick; McCalla, Gordon (eds.). La frontera del conocimiento: ensayos en la representación del conocimiento . Saltador. págs. 331–352. ISBN 978-0-387-96557-4.
- Kakas, AC; Mancarella, P. (1990). "Modelos estables generalizados: una semántica de la abducción". En Aiello, LC (ed.). ECAI 90: actas de la IX Conferencia Europea de Inteligencia Artificial . Minero. págs. 385–391. ISBN 978-0273088226.
- Consola, L .; Dupre, DT; Torasso, P. (1991). "Sobre la relación entre la sustracción y la deducción". Revista de Lógica y Computación . 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". Revista de Lógica y Computación . 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 de lógica abductiva". J. Programación lógica . 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). "Edición especial: programación lógica abductiva" . J. Programación lógica . 44 (1–3): 1–4. doi : 10.1016 / S0743-1066 (99) 00078-3 .
- Denecker, M .; Kakas, AC (2002). "Abducción en la programación lógica" . En Kakas, AC; Sadri, F. (eds.). Lógica computacional: programación lógica y más: ensayos en honor a Robert A. Kowalski . Apuntes de conferencias en Ciencias de la Computación. 2407 . Saltador. págs. 402–437. ISBN 978-3-540-43959-2.
- Poole, D. (1993). "Abducción probabilística del cuerno 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 las teorías de la abducción para el manejo de la incompletitud en el aprendizaje de primer orden" (PDF) . Knowl. Inf. Syst . 11 (2): 217–242. doi : 10.1007 / s10115-006-0019-5 . Archivado desde el original (PDF) el 17 de julio de 2011.