Programació lògica inductiva

La programació lògica inductiva (ILP) és un subcamp de la intel·ligència artificial simbòlica que utilitza la programació lògica com a representació uniforme d'exemples, coneixements de fons i hipòtesis. Donada una codificació dels coneixements previs coneguts i un conjunt d'exemples representats com una base de dades lògica de fets, un sistema ILP derivarà un programa lògic hipotetitzat que inclou tots els exemples positius i cap dels negatius.

Esquema: exemples positius + exemples negatius + coneixements previs ⇒ hipòtesi.

La programació lògica inductiva és especialment útil en bioinformàtica i processament del llenguatge natural. Gordon Plotkin i Ehud Shapiro van establir les bases teòriques inicials per a l'aprenentatge automàtic inductiu en un entorn lògic.^[1] Shapiro va construir la seva primera implementació (Model Inference System) el 1981: ^[2] un programa Prolog que deduïa inductivament programes lògics a partir d'exemples positius i negatius. La primera implementació completa de primer ordre de programació lògica inductiva va ser Theorist el 1986.^[3] El terme programació lògica inductiva es va introduir per primera vegada ^[4] en un article de Stephen Muggleton el 1991.^[5] Muggleton també va fundar la conferència internacional anual sobre programació lògica inductiva, va introduir les idees teòriques de la invenció de predicats, la resolució inversa ^[6] i la implicació inversa.^[7] Muggleton va implementar la implicació inversa primer al sistema PROGOL. El terme " inductiu " es refereix aquí a la inducció filosòfica (és a dir, suggerir una teoria per explicar fets observats) més que matemàtica (és a dir, demostrar una propietat per a tots els membres d'un conjunt ben ordenat).

Definició formal

El coneixement de fons es dona com una teoria lògica $B$ , comunament en forma de clàusules de Horn utilitzades en programació lògica. Els exemples positius i negatius es donen com a conjunció $E^{+}$ i $E^{-}$ de literals de terra no negats i negats, respectivament. Una hipòtesi correcta $h$ és una proposició lògica que compleix els requisits següents.^[8]

${\begin{array}{llll}{\text{Necessitat:}}&B&\not \models &E^{+}\\{\text{Suficiència:}}&B\land h&\color {blue}{\models }&E^{+}\\{\text{Dèbil consistència:}}&B\land h&\not \models &{\textit {false}}\\{\text{Forta consistència:}}&B\land h\land E^{-}&\not \models &{\textit {false}}\end{array}}$

La " necessitat " no imposa una restricció a $h$ , però prohibeix qualsevol generació d'hipòtesis sempre que els fets positius siguin explicables sense ella. La " suficiència " requereix qualsevol hipòtesi $h$ generada per explicar tots els exemples positius $E^{+}$ . La " consistència feble " prohibeix la generació de qualsevol hipòtesi $h$ que contradigui el coneixement de fons $B$ . La " coherència forta " també prohibeix la generació de qualsevol hipòtesi $h$ que no sigui coherent amb els exemples negatius $E^{-}$ , donats els coneixements bàsics $B$ ; implica " coherència feble "; si no es donen exemples negatius, tots dos requisits coincideixen. Džeroski ^[9] només requereix " Suficiència " (allà anomenada "Completitud") i "Forta consistència ".

Sistema de programació lògica inductiva

El sistema de programació lògica inductiva és un programa que pren com a entrada teories lògiques $B,E^{+},E^{-}$ i produeix una hipòtesi correcta $H$ wrt teories $B,E^{+},E^{-}$ Un algorisme d'un sistema ILP consta de dues parts: cerca d'hipòtesis i selecció d'hipòtesis. Primer es busca una hipòtesi amb un procediment de programació lògica inductiva, després s'escull un subconjunt de les hipòtesis trobades (en la majoria dels sistemes una hipòtesi) mitjançant un algorisme de selecció. Un algorisme de selecció puntua cadascuna de les hipòtesis trobades i retorna les que tenen la puntuació més alta. Un exemple de funció de puntuació inclou la longitud mínima de compressió on una hipòtesi amb una complexitat de Kolmogorov més baixa té la puntuació més alta i es retorna. Un sistema ILP és complet si per a qualsevol teoria lògica d'entrada $B,E^{+},E^{-}$ qualsevol hipòtesi correcta $H$ a partir d'aquestes teories d'entrada es pot trobar amb el seu procediment de cerca d'hipòtesis.

Referències

↑ Shapiro, Ehud Y. Algorithmic program debugging (en anglès). MIT Press, 1983. ISBN 0-262-19218-7.
↑ Shapiro, Ehud Y. «The model inference system». A: Proceedings of the 7th international joint conference on Artificial intelligence (en anglès). 2. Morgan Kaufmann, 1981, p. 1064.
↑ Poole, David. «Theorist: A Logical Reasoning System for Defaults and Diagnosis». A: Nick J. Cercone. The Knowledge Frontier – Essays in the Representation of Knowledge (en anglès). 1st. New York, NY: Springer, 1987, p. 331–352 (Symbolic Computation). DOI 10.1007/978-1-4612-4792-0. ISBN 978-1-4612-9158-9.
↑ De Raedt, Luc. «[[[:Plantilla:GBurl]] A Perspective on Inductive Logic Programming]». A: The Logic Programming Paradigm: A 25-Year Perspective (en anglès). Springer, 2012, p. 335–346. ISBN 978-3-642-60085-2.
↑ Muggleton, S.H. New Generation Computing, 8, 4, 1991, pàg. 295–318. DOI: 10.1007/BF03037089.
↑ Muggleton, S.H.. «Machine invention of first-order predicate by inverting resolution». A: Proceedings of the 5th International Conference on Machine Learning (en anglès), 1988, p. 339–352. DOI 10.1016/B978-0-934613-64-4.50040-2. ISBN 978-0-934613-64-4.
↑ Muggleton, S.H. New Generation Computing, 13, 3–4, 1995, pàg. 245–286. DOI: 10.1007/bf03037227.
↑ Muggleton, Stephen Artificial Intelligence, 114, 1–2, 1999, pàg. 283–296. DOI: 10.1016/s0004-3702(99)00067-3 [Consulta: free].; here: Sect.2.1
↑ Džeroski, Sašo. «Inductive Logic Programming and Knowledge Discovery in Databases». A: Fayyad. Advances in Knowledge Discovery and Data Mining (en anglès). MIT Press, 1996, p. 117–152 See §5.2.4.

[1] Shapiro, Ehud Y. Algorithmic program debugging (en anglès). MIT Press, 1983. ISBN 0-262-19218-7.

[2] Shapiro, Ehud Y. «The model inference system». A: Proceedings of the 7th international joint conference on Artificial intelligence (en anglès). 2. Morgan Kaufmann, 1981, p. 1064.

[3] Poole, David. «Theorist: A Logical Reasoning System for Defaults and Diagnosis». A: Nick J. Cercone. The Knowledge Frontier – Essays in the Representation of Knowledge (en anglès). 1st. New York, NY: Springer, 1987, p. 331–352 (Symbolic Computation). DOI 10.1007/978-1-4612-4792-0. ISBN 978-1-4612-9158-9.

[4] De Raedt, Luc. «[[[:Plantilla:GBurl]] A Perspective on Inductive Logic Programming]». A: The Logic Programming Paradigm: A 25-Year Perspective (en anglès). Springer, 2012, p. 335–346. ISBN 978-3-642-60085-2.

[muggleton1995inverse-5] Muggleton, S.H. New Generation Computing, 8, 4, 1991, pàg. 295–318. DOI: 10.1007/BF03037089.

[6] Muggleton, S.H.. «Machine invention of first-order predicate by inverting resolution». A: Proceedings of the 5th International Conference on Machine Learning (en anglès), 1988, p. 339–352. DOI 10.1016/B978-0-934613-64-4.50040-2. ISBN 978-0-934613-64-4.

[7] Muggleton, S.H. New Generation Computing, 13, 3–4, 1995, pàg. 245–286. DOI: 10.1007/bf03037227.

[8] Muggleton, Stephen Artificial Intelligence, 114, 1–2, 1999, pàg. 283–296. DOI: 10.1016/s0004-3702(99)00067-3 [Consulta: free].; here: Sect.2.1

[9] Džeroski, Sašo. «Inductive Logic Programming and Knowledge Discovery in Databases». A: Fayyad. Advances in Knowledge Discovery and Data Mining (en anglès). MIT Press, 1996, p. 117–152 See §5.2.4.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]