Ver el código de «Programación lógica inductiva»


La '''Programación lógica inductiva''' ('''ILP''', por sus siglas en inglés) es un subcampo de la[[inteligencia artificial simbólica]] que usa [[programación lógica]] como representación uniforme para ejemplos, hipótesis y conocimiento previo. Dada una codificación del conocimiento previo sabida y un conjunto de ejemplos representados como [[base de datos]] lógica de hechos, un sistema de ILP derivará una lógica hipotetizada cuya [[consecuencia lógica]] implique todos los ejemplos positivos y ninguno de los negativos.

* Esquema: ''Ejemplos positivos'' + ''ejemplos negativos'' + ''conocimiento previo'' &#x21D2; hipòtesis.

La programación lógica inductiva es particularmente útil en [[bioinformática]] y [[Procesamiento de lenguajes naturales|procesamiento del lenguaje natural]] . [[Gordon Plotkin]] y [[Ehud Shapiro]] sentaron las bases teóricas iniciales para el aprendizaje automático inductivo en un entorno lógico.<ref>Plotkin G.D. [https://www.era.lib.ed.ac.uk/bitstream/handle/1842/6656/Plotkin1972.pdf;sequence=1 Automatic Methods of Inductive Inference], PhD thesis, University of Edinburgh, 1970.</ref><ref>Shapiro, Ehud Y. [http://ftp.cs.yale.edu/publications/techreports/tr192.pdf Inductive inference of theories from facts], Research Report 192, Yale University, Department of Computer Science, 1981. Reprinted in J.-L. Lassez, G. Plotkin (Eds.), Computational Logic, The MIT Press, Cambridge, MA, 1991, pp. 199–254.</ref><ref>Shapiro, Ehud Y. (1983). ''Algorithmic program debugging''. Cambridge, Mass: MIT Press. {{ISBN|0-262-19218-7}}</ref> Shapiro construyó su primera implementación (Modelo de Sistema de Inferencia) en 1981:<ref>Shapiro, Ehud Y. "[http://dl.acm.org/citation.cfm?id=1623364 The model inference system]." Proceedings of the 7th international joint conference on Artificial intelligence-Volume 2. Morgan Kaufmann Publishers Inc., 1981.</ref> un programa [[Prolog]] que dedujo inductivamente programas lógicos a partir de ejemplos positivos y negativos. El término ''Programación lógica inductiva'' se introdujo por primera vez<ref>Luc De Raedt. A Perspective on Inductive Logic Programming. The Workshop on Current and Future Trends in Logic Programming, Shakertown, to appear in Springer LNCS, 1999. [[CiteSeerX]]: {{URL|1=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.1790|2=10.1.1.56.1790}}</ref> en un artículo de [[Stephen Muggleton]] en 1991.<ref name="muggleton1995inverse">{{Cita publicación|título=Inductive logic programming|apellidos=Muggleton|nombre=S.H.|publicación=New Generation Computing|volumen=8|número=4|páginas=295–318|doi=10.1007/BF03037089|pmc=|pmid=|año=1991}}</ref> Muggleton también fundó la conferencia internacional anual sobre programación de lógica inductiva, introdujo las ideas teóricas de la Invención de Predicados, la [[resolución inversa]],<ref>Muggleton S.H. and Buntine W. "[https://www.sciencedirect.com/science/article/pii/B9780934613644500402 Machine invention of first-order predicate by inverting resolution]","Proceedings of the 5th International Conference on Machine Learning, 1988.</ref> y la implicación inversa.<ref>{{Cita publicación|url=|título=Inverting entailment and Progol|apellidos=Muggleton|nombre=S.H.|publicación=New Generation Computing|volumen=13|número=3–4|páginas=245–286|doi=10.1007/bf03037227|año=1995}}</ref> Muggleton implementó la vinculación inversa primero en el sistema PROGOL . El término " ''inductivo'' " aquí se refiere a la ''inducción'' [[Razonamiento inductivo|filosófica]] (es decir, que sugiere una teoría para explicar los hechos observados) en lugar de [[Inducción matemática|matemática]] (es decir, que demuestra una propiedad para todos los miembros de un conjunto bien ordenado). 

== Definición formal ==
Los ''conocimientos previos'' se dan como una teoría lógica {{Mvar|B}}, comúnmente en forma de [[Cláusula de Horn|cláusulas Horn]] utilizadas en la [[programación lógica]] . Los ejemplos ''positivos'' y ''negativos'' se dan como una conjunción <math>E^+</math> y <math>E^-</math> de ''[[ground literals]]'' sin negar y negados, respectivamente. Una ''hipótesis correcta'' {{Mvar|h}} es una proposición lógica que satisface los siguientes requisitos.<ref>{{Cita publicación|título=Inductive Logic Programming: Issues, Results and the Challenge of Learning Language in Logic|apellidos=Muggleton|nombre=Stephen|publicación=Artificial Intelligence|volumen=114|número=1–2|páginas=283–296|doi=10.1016/s0004-3702(99)00067-3|año=1999}}; here: Sect.2.1</ref> 

: [[Consecuencia lógica| <math>\begin{array}{llll} \text{Necesidad:} & B & \not\models & E^+ \\ \text{Suficiencia:} & B \land h & \color{blue}{\models} & E^+ \\ \text{Consistencia débil:} & B \land h & \not\models & \textit{false} \\ \text{Consistencia fuerte:} & B \land h \land E^- & \not\models & \textit{false} \end{array}</math>]]

La " ''necesidad'' " no impone una restricción a {{Mvar|h}}, pero prohíbe cualquier generación de hipótesis mientras los hechos positivos sean explicables sin ella.

La "s''uficiencia'' " es lo que requiere cualquier hipótesis generada {{Mvar|h}} para explicar todos los ejemplos positivos <math>E^+</math>. 

La " ''consistencia débil'' " prohíbe la generación de cualquier hipótesis {{Mvar|h}} que contradiga el conocimiento básico {{Mvar|B}}. 

La "''consistencia fuerte'' " también prohíbe la generación de cualquier hipótesis {{Mvar|h}} que sea inconsistente con los ejemplos negativos <math>E^-</math>, dado el conocimiento de fondo {{Mvar|B}} ; esto implica "''Consistencia débil'' "; Si no se dan ejemplos negativos, ambos requisitos coinciden. Džeroski<ref>{{Obra citada|título=Advances in Knowledge Discovery and Data Mining|apellidos=Džeroski|nombre=Sašo|editorial=MIT Press|capítulo=Inductive Logic Programming and Knowledge Discovery in Databases|páginas=117–152|editor=Fayyad|nombre-editor=U.M.|editor2=Piatetsky-Shapiro|editor3=Smith|editor4=Uthurusamy|year=1996|editor2-first=G.}}; here: Sect.5.2.4</ref> requiere solo "''Suficiencia'' " (que llama "Completitud") y "''Consistencia fuerte'' ".

== Ejemplo ==
[[Archivo:Family_relations_example_for_inductive_logic_programming_article.gif|izquierda|miniaturadeimagen| Presuntas relaciones familiares en la sección "Ejemplo" ]]
El siguiente ejemplo bien conocido sobre el aprendizaje de definiciones de relaciones familiares utiliza las siguientes abreviaturas: 

: {{Math|''par'': ''padre''}}, {{Math|''fem'': ''mujer''}}, {{Math|''dau'': ''hija''}}, {{Math|''g'': ''George''}}, {{Math|''h'': ''Helen''}}, {{Math|''m'': ''Mary''}}, {{Math|''t'': ''Tom''}}, {{Math|''n'': ''Nancy''}}, y {{Math|''e'': ''Eve''}}.

Comienza con el sgte. conocimiento previo (cf. imagen): 

: <math>\textit{par}(h,m) \land \textit{par}(h,t) \land \textit{par}(g,m) \land \textit{par}(t,e) \land \textit{par}(n,e) \land \textit{fem}(h) \land \textit{fem}(m) \land \textit{fem}(n) \land \textit{fem}(e)</math> , 

los ejemplos positivos 

: <math>\textit{dau}(m,h) \land \textit{dau}(e,t)</math> , 

y la proposición trivial {{Mvar|true}} para denotar la ausencia de ejemplos negativos. 

El enfoque de Plotkin<ref>{{Cita publicación|título=A Note on Inductive Generalization|apellidos=Plotkin|nombre=Gordon D.|publicación=Machine Intelligence|volumen=5|páginas=153–163|apellidos-editor=Meltzer|nombre-editor=B.|enlace-editor=Michie|año=1970}}</ref><ref>{{Cita publicación|título=A Further Note on Inductive Generalization|apellidos=Plotkin|nombre=Gordon D.|publicación=Machine Intelligence|volumen=6|páginas=101–124|apellidos-editor=Meltzer|nombre-editor=B.|enlace-editor=Michie|año=1971}}</ref> de "''generalización general menos relativa (rlgg)'' " a la ''programación lógica inductiva'' se utilizará para obtener una sugerencia sobre cómo definir formalmente la relación hija {{Mvar|dau}} . 

Este enfoque utiliza los siguientes pasos. 

* Relativiza cada ejemplo positivo literal con el conocimiento previo (o de fondo) completo: 
*: <math>\begin{align}
\textit{dau}(m,h) \leftarrow \textit{par}(h,m) \land \textit{par}(h,t) \land \textit{par}(g,m) \land \textit{par}(t,e) \land \textit{par}(n,e) \land \textit{fem}(h) \land \textit{fem}(m) \land \textit{fem}(n) \land \textit{fem}(e) \\
\textit{dau}(e,t) \leftarrow \textit{par}(h,m) \land \textit{par}(h,t) \land \textit{par}(g,m) \land \textit{par}(t,e) \land \textit{par}(n,e) \land \textit{fem}(h) \land \textit{fem}(m) \land \textit{fem}(n) \land \textit{fem}(e)
\end{align}</math> , 
* Lo convierte en [[Forma normal conjuntiva|cláusula forma normal]] : 
*: <math>\begin{align}
\textit{dau}(m,h) \lor \lnot \textit{par}(h,m) \lor \lnot \textit{par}(h,t) \lor \lnot \textit{par}(g,m) \lor \lnot \textit{par}(t,e) \lor \lnot \textit{par}(n,e) \lor \lnot \textit{fem}(h) \lor \lnot \textit{fem}(m) \lor \lnot \textit{fem}(n) \lor \lnot \textit{fem}(e) \\
\textit{dau}(e,t) \lor \lnot \textit{par}(h,m) \lor \lnot \textit{par}(h,t) \lor \lnot \textit{par}(g,m) \lor \lnot \textit{par}(t,e) \lor \lnot \textit{par}(n,e) \lor \lnot \textit{fem}(h) \lor \lnot \textit{fem}(m) \lor \lnot \textit{fem}(n) \lor \lnot \textit{fem}(e)
\end{align}</math> , 
* [[ Anti-unificación (informática) |Anti-unifica]] cada par compatible<ref>i.e. sharing the same predicate symbol and negated/unnegated status</ref><ref>in general: {{Mvar|n}}-tuple when {{Mvar|n}} positive example literals are given</ref> de literales: 
** <math>\textit{dau}(x_{me},x_{ht})</math> de <math>\textit{dau}(m,h)</math> y <math>\textit{dau}(e,t)</math> , 
** <math>\lnot \textit{par}(x_{ht},x_{me})</math> de <math>\lnot \textit{par}(h,m)</math> y <math>\lnot \textit{par}(t,e)</math> , 
** <math>\lnot \textit{fem}(x_{me})</math> de <math>\lnot \textit{fem}(m)</math> y <math>\lnot \textit{fem}(e)</math> , 
** <math>\lnot \textit{par}(g,m)</math> de <math>\lnot \textit{par}(g,m)</math> y <math>\lnot \textit{par}(g,m)</math>, similar para todos los demás literales de conocimiento de fondo 
** <math>\lnot \textit{par}(x_{gt},x_{me})</math> de <math>\lnot \textit{par}(g,m)</math> y <math>\lnot \textit{par}(t,e)</math> y muchos más literales negados 
* Elimina todos los literales negados que contienen variables que no aparecen en un literal positivo: 
** después de eliminar todos los literales negados que contienen otras variables que <math>x_{me},x_{ht}</math>, solamente <math>\textit{dau}(x_{me},x_{ht}) \lor \lnot \textit{par}(x_{ht},x_{me}) \lor \lnot \textit{fem}(x_{me})</math> permanece, junto con todos los literales básicos del conocimiento de fondo 
* Convierta las cláusulas de nuevo a la forma Horn: 
** <math>\textit{dau}(x_{me},x_{ht}) \leftarrow \textit{par}(x_{ht},x_{me}) \land \textit{fem}(x_{me}) \land (\text{todos los hechos del conocimiento previo})</math> 

La cláusula Horn resultante es la hipótesis {{Mvar|h}} obtenida por el enfoque rlgg. Ignorando los hechos del conocimiento de fondo, la cláusula lee informalmente " ''<math>x_{me}</math> se llama hija de <math>x_{ht}</math> Si <math>x_{ht}</math> es el padre de <math>x_{me}</math> y <math>x_{me}</math> es femenino'' ", que es una definición comúnmente aceptada. 

Con respecto a los requisitos anteriores, La "''Necesidad'' " se cumplió porque el predicado {{Mvar|dau}} no aparece en el conocimiento de fondo. La "''suficiencia'' " se satisface con la hipótesis calculada {{Mvar|h}}, ya que, junto con <math>\textit{par}(h,m) \land \textit{fem}(m)</math> desde el conocimiento previo, implica el primer ejemplo positivo <math>\textit{dau}(m,h)</math> y de manera similar {{Mvar|h}} y <math>\textit{par}(t,e) \land \textit{fem}(e)</math> desde el conocimiento previo implica el segundo ejemplo positivo <math>\textit{dau}(e,t)</math>. La "''Consistencia débil'' " es satisfecha por {{Mvar|h}}, ya que {{Mvar|h}} se mantiene en la [[estructura Herbrand]] (finita) descrita por el conocimiento de fondo; lo mismo pasa con la "''Consistencia fuerte''". 

La definición común de la relación de la abuela, a saber. <math>\textit{gra}(x,z) \leftarrow \textit{fem}(x) \land \textit{par}(x,y) \land \textit{par}(y,z)</math>, no se puede aprender utilizando el enfoque anterior, ya que la variable {{Mvar|y}} ocurre solo en el cuerpo de la cláusula; los literales correspondientes se habrían eliminado en el cuarto paso del enfoque. Para superar este defecto, ese paso tiene que modificarse de modo que pueda parametrizarse con diferentes ''heurísticas de post-selección literales'' . Históricamente, la implementación de GOLEM se basa en el enfoque rlgg. 

== Sistemas de programación de lógica inductiva ==
Un sistema de programación lógica inductiva es un programa que toma como entrada teorías lógicas de entrada <math>B, E^+, E^-</math> y genera una hipótesis correcta {{Mvar|H}}. Un algoritmo de un sistema ILP consta de dos partes: búsqueda de hipótesis y selección de hipótesis. Primero se busca una hipótesis con un procedimiento de programación de lógica inductiva, luego se elige un subconjunto de las hipótesis encontradas (en la mayoría de los sistemas, una hipótesis) mediante un algoritmo de selección. Un algoritmo de selección puntúa cada una de las hipótesis encontradas y devuelve las que tienen la puntuación más alta. Un ejemplo de función de puntaje puede ser una que incluya longitud de compresión mínima donde una hipótesis con la menor [[Complejidad de Kolmogórov|complejidad de Kolmogorov]] tiene el puntaje más alto y por lo tanto se la elige. Un sistema ILP está completo si y solo si para cualquier teoría lógica de entrada <math>B, E^+, E^-</math> cualquier hipótesis correcta {{Mvar|H}}  se puede encontrar con su procedimiento de búsqueda de hipótesis. 

=== Búsqueda de hipótesis ===
Los sistemas ILP modernos como Progol,<ref name="muggleton1995inverse"/> Hail<ref>Ray, O., Broda, K., & Russo, A. M. (2003). [https://www.academia.edu/download/45316629/Hybrid_Abductive_Inductive_Learning_A_Ge20160503-29931-1y1tcvk.pdf Hybrid abductive inductive learning] {{Wayback|url=https://www.academia.edu/download/45316629/Hybrid_Abductive_Inductive_Learning_A_Ge20160503-29931-1y1tcvk.pdf |date=20220408011212 }}. In LNCS: Vol. 2835. Proceedings of the 13th international conference on inductive logic programming (pp. 311–328). Berlin: Springer.</ref> e Imparo<ref>Kimber, T., Broda, K., & Russo, A. (2009). [https://link.springer.com/content/pdf/10.1007/978-3-642-04238-6.pdf#page=183 Induction on failure: learning connected Horn theories]. In LNCS: Vol. 5753. Proceedings of the 10th international conference on logic programing and nonmonotonic reasoning (pp. 169–181). Berlin: Springer.</ref> encuentran una hipótesis {{Mvar|H}} utilizando el principio de la vinculación inversa para las teorías {{Mvar|B}}, {{Mvar|E}}, {{Mvar|H}} : <math>B \land H \models E \iff B \land \neg E \models \neg H</math> . Primero construyen una teoría intermedia {{Mvar|F}} llamada teoría de puente que satisface las condiciones <math>B \land \neg E \models F</math> y <math>F \models \neg H</math> . Entonces como <math>H \models \neg F</math>, generalizan la negación de la teoría del puente {{Mvar|F}} con la anti-vinculación.<ref>Yoshitaka Yamamoto, Katsumi Inoue, and Koji Iwanuma. [https://link.springer.com/content/pdf/10.1007/s10994-011-5250-y.pdf Inverse subsumption for complete explanatory induction]. Machine learning, 86(1):115–139, 2012.</ref> Sin embargo, la operación del anti-vinculación, dado que es altamente no determinista es computacionalmente más costosa. Por lo tanto, se puede realizar una búsqueda alternativa de hipótesis utilizando la operación de la subsunción inversa (anti-subsunción), que es menos no determinista que la anti-vinculación. 

Surgen preguntas sobre la integridad de un procedimiento de búsqueda de hipótesis de un sistema ILP específico. Por ejemplo, el procedimiento de búsqueda de hipótesis de Progol basado en la regla de inferencia de vinculación inversa no se completa con '''el ejemplo de Yamamoto''' .<ref>Akihiro Yamamoto. [https://link.springer.com/chapter/10.1007/3540635149_58 Which hypotheses can be found with inverse entailment?] In Inductive Logic Programming, pages 296–308. Springer, 1997.</ref> Por otro lado, Imparo se completa por el procedimiento anti-vinculación<ref name="kimber2009induction">Timothy Kimber. [http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.560694 Learning definite and normal logic programs by induction on failure] {{Wayback|url=http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.560694 |date=20200711225706 }}. PhD thesis, Imperial College London, 2012.</ref> y su procedimiento de subsunción inversa extendida.<ref>David Toth (2014). [[arxiv:1407.3836|Imparo is complete by inverse subsumption]]. arXiv:1407.3836</ref> 

=== Implementaciones ===

* [http://www.cs.bris.ac.uk/Research/MachineLearning/1BC/ 1BC y 1BC2: clasificadores bayesianos "ingenuos" de primer orden:] 
* [http://dtai.cs.kuleuven.be/ACE/ ACE (un motor combinado)] 
* [http://web.comlab.ox.ac.uk/oucl/research/areas/machlearn/Aleph/ Aleph] 
* [http://www.ahlgren.info/research/atom/ Atom] {{Wayback|url=http://www.ahlgren.info/research/atom/ |date=20140326152728 }} 
* {{Enlace roto|1=[http://dtai.cs.kuleuven.be/claudien/ Claudien] |2=http://dtai.cs.kuleuven.be/claudien/ }} 
* [http://dl-learner.org DL-Learner] {{Wayback|url=http://dl-learner.org/ |date=20190815184411 }} 
* [http://dtai.cs.kuleuven.be/dmax/ DMax] 
* [https://spike-imperial.github.io/FastLAS/ FastLAS (Aprendizaje rápido desde conjuntos de respuestas)] 
* {{Enlace roto|1=[ftp://ftp.cs.su.oz.au/pub/foil6.sh] |2=ftp://ftp.cs.su.oz.au/pub/foil6.sh }} [[FOIL]] 
* [http://www.doc.ic.ac.uk/~shm/Software/golem] [[Golem (ILP)]] 
* [http://www.ilasp.com/ ILASP (Aprendizaje inductivo de programas desde conjunto de respuestas)] 
* Imparo<ref name="kimber2009induction"/> 
* [http://lacam.di.uniba.it:8000/systems/inthelex/ Inthelex (INcremental THEory Learning from EXamples)] {{Wayback|url=http://lacam.di.uniba.it:8000/systems/inthelex/ |date=20111128110512 }} 
* [https://web.archive.org/web/20020516195248/http://cs.anu.edu.au/people/Eric.McCreath/lime.html Lima] 
* [http://github.com/metagol/metagol Metagol] 
* [https://archive.today/20130219215544/http://libra.msra.cn/Publication/3392493/mio-user-s-manual Mio] 
* MIS (Sistema de inferencia modelo) de Ehud Shapiro
* [https://github.com/dice-group/Ontolearn Ontolearn] 
* [http://www.doc.ic.ac.uk/~shm/Software/progol5.0] PROGOL 
* [http://labe.felk.cvut.cz/~zelezny/rsd/ RSD] {{Wayback|url=http://labe.felk.cvut.cz/~zelezny/rsd/ |date=20070301162526 }} 
* Warmr (ahora incluido en ACE) 
* [http://ilp.doc.ic.ac.uk/ProGolem/ ProGolem]<ref>{{Cita publicación|url=http://www.doc.ic.ac.uk/~jcs06/papers/ilp09/progolem.pdf|título=ProGolem: a system based on relative minimal generalization|apellidos=Muggleton|nombre=Stephen|apellidos2=Santos|nombre2=Jose|fecha=2009|publicación=ILP|apellidos3=Tamaddoni-Nezhad|nombre3=Alireza}}</ref><ref>{{Cita publicación|url=http://www.doc.ic.ac.uk/~jcs06/Hexose/hexose.pdf|título=Automated identification of features of protein-ligand interactions using Inductive Logic Programming: a hexose binding case study|apellidos=Santos|nombre=Jose|apellidos2=Nassif|nombre2=Houssam|fecha=2012|publicación=BMC Bioinformatics|volumen=13|página=162|doi=10.1186/1471-2105-13-162|pmc=3458898|pmid=22783946|apellidos3=Page|nombre3=David|apellidos4=Muggleton|nombre4=Stephen|apellidos5=Sternberg|nombre5=Mike|fechaacceso=10 de julio de 2020|fechaarchivo=3 de marzo de 2016|urlarchivo=https://web.archive.org/web/20160303210331/http://www.doc.ic.ac.uk/~jcs06/Hexose/hexose.pdf|deadurl=yes}}</ref>

== Véase también ==

* [[Razonamiento de sentido común]] 
* [[Análisis formal de conceptos|Análisis conceptual formal]] 
* [[Razonamiento inductivo]] 
* [[Programación inductiva]] 
* [[Probabilidad inductiva]] 
* [[Aprendizaje estadístico relacional]] 
* [[Espacio de versiones|Versión del espacio de versiones]] 

== Referencias ==
{{Listaref}}

== Otras lecturas ==
{{Refbegin}}
* {{Cita publicación | last1 = Muggleton | first1 = S. | last2 = De Raedt | doi = 10.1016/0743-1066(94)90035-3 | first2 = L. | title = Inductive Logic Programming: Theory and methods | journal = The Journal of Logic Programming | volume = 19–20 | pages = 629–679 | year = 1994 | pmid =  | pmc = }}
* {{cite book | first1 = N. | last1 = Lavrac | first2 = S. | last2 = Dzeroski | title = Inductive Logic Programming: Techniques and Applications | publisher = Ellis Horwood | location = New York | year = 1994 | isbn = 978-0-13-457870-5 | url = http://www-ai.ijs.si/SasoDzeroski/ILPBook/ | access-date = 22 de septiembre de 2004 | archive-url = https://web.archive.org/web/20040906084947/http://www-ai.ijs.si/SasoDzeroski/ILPBook/ | archive-date = 6 de septiembre de 2004 }}
* Visual example of inducing the grandparenthood relation by the [[#Implementations|Atom system]]. http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html {{Wayback|url=http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html |date=20140326101408 }}
{{Refend}}

{{Control de autoridades}}