La Programación lógica inductiva (ILP, por sus siglas en inglés) es un subcampo de lainteligencia 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 ⇒ hipòtesis.

La programación lógica inductiva es particularmente útil en bioinformática y 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.^[1]​^[2]​^[3]​ Shapiro construyó su primera implementación (Modelo de Sistema de Inferencia) en 1981:^[4]​ 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^[5]​ en un artículo de Stephen Muggleton en 1991.^[6]​ 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,^[7]​ y la implicación inversa.^[8]​ Muggleton implementó la vinculación inversa primero en el sistema PROGOL . El término " inductivo " aquí se refiere a la inducción filosófica (es decir, que sugiere una teoría para explicar los hechos observados) en lugar de matemática (es decir, que demuestra una propiedad para todos los miembros de un conjunto bien ordenado).

Los conocimientos previos se dan como una teoría lógica B, comúnmente en forma de cláusulas Horn utilizadas en la programación lógica . Los ejemplos positivos y negativos se dan como una conjunción ${\displaystyle E^{+}}$ y ${\displaystyle E^{-}}$ de ground literals sin negar y negados, respectivamente. Una hipótesis correcta h es una proposición lógica que satisface los siguientes requisitos.^[9]​

${\displaystyle {\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}}}$

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

La "suficiencia " es lo que requiere cualquier hipótesis generada h para explicar todos los ejemplos positivos ${\displaystyle E^{+}}$.

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

La "consistencia fuerte " también prohíbe la generación de cualquier hipótesis h que sea inconsistente con los ejemplos negativos ${\displaystyle E^{-}}$, dado el conocimiento de fondo B ; esto implica "Consistencia débil "; Si no se dan ejemplos negativos, ambos requisitos coinciden. Džeroski^[10]​ requiere solo "Suficiencia " (que llama "Completitud") y "Consistencia fuerte ".

El siguiente ejemplo bien conocido sobre el aprendizaje de definiciones de relaciones familiares utiliza las siguientes abreviaturas:

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

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

${\displaystyle {\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)}$ ,

los ejemplos positivos

${\displaystyle {\textit {dau}}(m,h)\land {\textit {dau}}(e,t)}$ ,

y la proposición trivial true para denotar la ausencia de ejemplos negativos.

El enfoque de Plotkin^[11]​^[12]​ 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 dau .

Este enfoque utiliza los siguientes pasos.

• Relativiza cada ejemplo positivo literal con el conocimiento previo (o de fondo) completo:

  ${\displaystyle {\begin{aligned}{\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{aligned}}}$ ,

• Lo convierte en cláusula forma normal :

  ${\displaystyle {\begin{aligned}{\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{aligned}}}$ ,

• Anti-unifica cada par compatible^[13]​^[14]​ de literales:
  • ${\displaystyle {\textit {dau}}(x_{me},x_{ht})}$ de ${\displaystyle {\textit {dau}}(m,h)}$ y ${\displaystyle {\textit {dau}}(e,t)}$ ,
  • ${\displaystyle \lnot {\textit {par}}(x_{ht},x_{me})}$ de ${\displaystyle \lnot {\textit {par}}(h,m)}$ y ${\displaystyle \lnot {\textit {par}}(t,e)}$ ,
  • ${\displaystyle \lnot {\textit {fem}}(x_{me})}$ de ${\displaystyle \lnot {\textit {fem}}(m)}$ y ${\displaystyle \lnot {\textit {fem}}(e)}$ ,
  • ${\displaystyle \lnot {\textit {par}}(g,m)}$ de ${\displaystyle \lnot {\textit {par}}(g,m)}$ y ${\displaystyle \lnot {\textit {par}}(g,m)}$, similar para todos los demás literales de conocimiento de fondo
  • ${\displaystyle \lnot {\textit {par}}(x_{gt},x_{me})}$ de ${\displaystyle \lnot {\textit {par}}(g,m)}$ y ${\displaystyle \lnot {\textit {par}}(t,e)}$ 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 ${\displaystyle x_{me},x_{ht}}$, solamente ${\displaystyle {\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})}$ permanece, junto con todos los literales básicos del conocimiento de fondo
• Convierta las cláusulas de nuevo a la forma Horn:
  • ${\displaystyle {\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}})}$

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

Con respecto a los requisitos anteriores, La "Necesidad " se cumplió porque el predicado dau no aparece en el conocimiento de fondo. La "suficiencia " se satisface con la hipótesis calculada h, ya que, junto con ${\displaystyle {\textit {par}}(h,m)\land {\textit {fem}}(m)}$ desde el conocimiento previo, implica el primer ejemplo positivo ${\displaystyle {\textit {dau}}(m,h)}$ y de manera similar h y ${\displaystyle {\textit {par}}(t,e)\land {\textit {fem}}(e)}$ desde el conocimiento previo implica el segundo ejemplo positivo ${\displaystyle {\textit {dau}}(e,t)}$. La "Consistencia débil " es satisfecha por h, ya que 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. ${\displaystyle {\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)}$, no se puede aprender utilizando el enfoque anterior, ya que la variable 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.

Un sistema de programación lógica inductiva es un programa que toma como entrada teorías lógicas de entrada ${\displaystyle B,E^{+},E^{-}}$ y genera una hipótesis correcta 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 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 ${\displaystyle B,E^{+},E^{-}}$ cualquier hipótesis correcta H se puede encontrar con su procedimiento de búsqueda de hipótesis.

Los sistemas ILP modernos como Progol,^[6]​ Hail^[15]​ e Imparo^[16]​ encuentran una hipótesis H utilizando el principio de la vinculación inversa para las teorías B, E, H : ${\displaystyle B\land H\models E\iff B\land \neg E\models \neg H}$ . Primero construyen una teoría intermedia F llamada teoría de puente que satisface las condiciones ${\displaystyle B\land \neg E\models F}$ y ${\displaystyle F\models \neg H}$ . Entonces como ${\displaystyle H\models \neg F}$, generalizan la negación de la teoría del puente F con la anti-vinculación.^[17]​ 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 .^[18]​ Por otro lado, Imparo se completa por el procedimiento anti-vinculación^[19]​ y su procedimiento de subsunción inversa extendida.^[20]​

• 1BC y 1BC2: clasificadores bayesianos "ingenuos" de primer orden:
• ACE (un motor combinado)
• Aleph
• Atom Archivado el 26 de marzo de 2014 en Wayback Machine.
• Claudien (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
• DL-Learner Archivado el 15 de agosto de 2019 en Wayback Machine.
• DMax
• FastLAS (Aprendizaje rápido desde conjuntos de respuestas)
• [1] (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última). FOIL
• [2] Golem (ILP)
• ILASP (Aprendizaje inductivo de programas desde conjunto de respuestas)
• Imparo^[19]​
• Inthelex (INcremental THEory Learning from EXamples) Archivado el 28 de noviembre de 2011 en Wayback Machine.
• Lima
• Metagol
• Mio
• MIS (Sistema de inferencia modelo) de Ehud Shapiro
• Ontolearn
• [3] PROGOL
• RSD Archivado el 1 de marzo de 2007 en Wayback Machine.
• Warmr (ahora incluido en ACE)
• ProGolem^[21]​^[22]​

• Razonamiento de sentido común
• Análisis conceptual formal
• Razonamiento inductivo
• Programación inductiva
• Probabilidad inductiva
• Aprendizaje estadístico relacional
• Versión del espacio de versiones