Programación lógica inductiva

La programación lógica inductiva (ILP) es un subcampo de la inteligencia artificial simbólica que utiliza la programación lógica como una representación uniforme de ejemplos, conocimientos previos e hipótesis. Dada una codificación del conocimiento previo conocido y un conjunto de ejemplos representados como una base de datos lógica de hechos, un sistema ILP derivará un programa lógico hipotético que implica todos los ejemplos positivos y ninguno negativo.

• Plan: ejemplos positivos + ejemplos negativos + conocimientos básicos ⇒ hipótesis.

La programación lógica inductiva es particularmente útil en bioinformática y procesamiento de lenguaje natural. Gordon Plotkin y Ehud Shapiro sentaron las bases teóricas iniciales para el aprendizaje automático inductivo en un entorno lógico. Shapiro construyó su primera implementación (Model Inference System) en 1981: un programa Prolog que infirió inductivamente programas lógicos a partir de ejemplos positivos y negativos. La primera implementación completa de primer orden de la programación lógica inductiva fue Theorist en 1986. El término Programación lógica inductiva se introdujo por primera vez en un artículo de Stephen Muggleton en 1991. Muggleton también fundó la conferencia internacional anual sobre Programación Lógica Inductiva, presentó las ideas teóricas de Invención de Predicados, Resolución Inversa y Implicación Inversa. Muggleton implementó la implicación inversa primero en el sistema PROGOL. El término "inductivo" aquí se refiere a la inducción filosófica (es decir, sugerir una teoría para explicar los hechos observados) en lugar de matemática (es decir, probar una propiedad para todos los miembros de un conjunto bien ordenado).

Definición formal

El conocimientos básicos se da como una teoría lógica B, comúnmente en forma de cláusulas de Cuerno utilizadas en programación lógica. El positivo y negativo ejemplos se dan como conjunción ${displaystyle E^{+}$ y ${displaystyle E^{-}$ de literales de tierra no negativo y negado, respectivamente. A hipótesis correcta h es una propuesta lógica que satisface los siguientes requisitos.

${displaystyle {begin{ll}{text{Necessity:} {begin{array} {begin{ll}{llll}{text{Necessity:}}}}} {begin{begin{ll} {begin{ll}{ll}{ll}{ll}{f}{f}{f}}}{f}}}}}}}}}}}}{f}{f}}}}}}}}}}}}}{f}}}}}}}}}}}}}}}}{f}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {b}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} { no models &E^{+}\{text{Sufficiency:}} {fnMicrosoft Sans Ser:}}}} {fnMicrosoft }\\fnMicrosoft Sans Ser: Bland hiéndose not models ' {false}\{text{Strong consistency:} Bland hland ¿Qué?$

"Necesidad"no impone una restricción h, pero prohíbe cualquier generación de una hipótesis mientras los hechos positivos sean explicables sin ella. "Suficiencia" requiere cualquier hipótesis generada h para explicar todos los ejemplos positivos ${displaystyle E^{+}$. "Congruencia débil" prohíbe la generación de cualquier hipótesis h que contradice el conocimiento de fondo B. "Gran consistencia" también prohíbe la generación de cualquier hipótesis h que es incompatible con los ejemplos negativos ${displaystyle E^{-}$, dada la experiencia B; implica "Congruencia débil"; si no se dan ejemplos negativos, ambos requisitos coinciden. Džeroski sólo requiere "Suficiencia" (llamado "Completeness" allí) y "Gran consistencia".

Ejemplo

Assumed family relations in section "Example"

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

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

Comienza desde el conocimiento previo (cf. imagen)

${fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f} {fnK} {fnMicrosoft} {fnK} {fnh} {fnh} {fnh} {fnh}fnh}f}fnh}fnh}fnh)fnh}fnh}fnh}fnh}fnh}fnh}fnh}fnh]fnh}fnh}fnh}fnh}fnh}fnh}fnh}fnh}fnh)fnh}fnh}fnh]fnh}fnh}fnh}fnh}fnh}fnh}fnh}fnh}fnh}fnh$,

los ejemplos positivos

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

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

La "generalización relativa mínima general de Plotkin (rlgg)" Se utilizará un enfoque de programación lógica inductiva para obtener una sugerencia sobre cómo definir formalmente la relación hija dau.

Este enfoque utiliza los siguientes pasos.

• Relativize cada ejemplo positivo literal con el conocimiento de fondo completo:

  ${fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif}$,

• Convertir en cláusula forma normal:

  $################################################################################################################################################################################################################################################################$,

• Anti-unificar cada par compatible de literales:
  • ${displaystyle {textit {dau}(x_{me},x_{ht} }$ desde ${displaystyle {textit {dau}(m,h)}$ y ${displaystyle {textit {dau}(e,t)}$,
  • ${displaystyle lnot {textit {}(x_{ht},x_{me}}$ desde ${displaystyle lnot {textit {}(h,m)}$ y ${displaystyle lnot {textit {}(t,e)}$,
  • ${displaystylelnot {textit {}(x_{me})}$ desde ${displaystyle lnot {textit {}(m)}$ y ${displaystyle lnot {textit {}(e)}$,
  • ${displaystyle lnot {textit {}(g,m)}$ desde ${displaystyle lnot {textit {}(g,m)}$ y ${displaystyle lnot {textit {}(g,m)}$, similar para todos los demás literales de conocimiento de fondo
  • ${displaystyle lnot {textit {}(x_{gt},x_{me}}$ desde ${displaystyle lnot {textit {}(g,m)}$ y ${displaystyle lnot {textit {}(t,e)}$, y muchos más literales negados
• Eliminar todos los literales negados que contienen variables que no ocurren en un literal positivo:
  • después de borrar todos los literales negados que contienen otras variables que ${displaystyle x_{me},x_{ht}$, sólo ${displaystyle {textit {dau}(x_{me},x_{ht})lor lnot {textit {par}(x_{ht},x_{me})lor lnot {textit {fem}(x_{ht}}}}}}}} {m} {m} {f}}} {f}} {f}}}}}}}}}}}} {f} {m}}}}}}}}}}}}}}}}} {f} {f} {f} {f} {f} {f} {f}}}f}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}f}f}}}}}}}}}}}}}}}}}}}}}}f}}}}}}}}}}}}}}}}$ restos, junto con todos los literales del fondo del conocimiento
• Convertir cláusulas en Horn form:
  • ${displaystyle {textit {}(x_{me},x_{ht})leftarrow {textit {par}(x_{ht},x_{me})land {textit {fem}(x_{me})land ({text{all background knowledge facts})}}}$

La cláusula resultante del Cuerno es la hipótesis h obtenido por el enfoque rlgg. Ignorando los hechos de conocimiento de fondo, la cláusula dice 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}}$ femenino", que es una definición comúnmente aceptada.

En cuanto a los requisitos anteriores, "Necesidad" estaba satisfecho porque el predicado dau no aparece en el conocimiento de fondo, que por lo tanto no puede implicar ninguna propiedad que contenga este predicado, tales como los ejemplos positivos son. "Suficiencia" está satisfecho por la hipótesis computada h, ya que, junto con ${displaystyle {textit {}(h,m)land {textit {}(m)}$ del conocimiento de fondo, implica el primer ejemplo positivo ${displaystyle {textit {dau}(m,h)}$, y de forma similar h y ${displaystyle {textit {par}(t,e)land {textit {fem}(e)}$ del conocimiento de fondo implica el segundo ejemplo positivo ${displaystyle {textit {dau}(e,t)}$. "Congruencia débil"está satisfecho h, desde h sostiene en el (finito) Herbrand estructura descrita por el conocimiento de fondo; similar para "Gran consistencia".

La definición común de la relación de la abuela, viz. ${displaystyle {textit {gra}(x,z)leftarrow {textit {fem} {textit {textit {par}(x,y)land {textit {textit {par}(y,z)}$, no se puede aprender utilizando el enfoque anterior, ya que la variable Sí. sólo ocurre en el cuerpo de la cláusula; los literales correspondientes habrían sido eliminados en el cuarto paso del enfoque. Para superar este defecto, ese paso tiene que ser modificado de tal manera que pueda parametrizarse con diferentes heurísticas literales post-selección. Históricamente, la implementación de GOLEM se basa en el enfoque rlgg.

Sistema de Programación Lógica Inductiva

Inductive Logic El sistema de programación es un programa que toma como teorías lógicas de entrada ${displaystyle B,E^{+},E^{-}$ y produce una hipótesis correcta H # Las teorías # ${displaystyle B,E^{+},E^{-}$ Un algoritmo de un sistema ILP consiste en 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 lógica inductiva, luego un subconjunto de las hipótesis encontradas (en la mayoría de los sistemas una hipótesis) es elegido por un algoritmo de selección. Un algoritmo de selección marca cada una de las hipótesis encontradas y devuelve las que tienen la puntuación más alta. Un ejemplo de la función de puntuación incluye la longitud mínima de compresión donde una hipótesis con una complejidad Kolmogorov más baja tiene la puntuación más alta y se devuelve. Un sistema ILP es completo sif para cualquier teoría lógica de entrada ${displaystyle B,E^{+},E^{-}$ cualquier hipótesis correcta H wrt a estas teorías de entrada se puede encontrar con su procedimiento de búsqueda de hipótesis.

Búsqueda de hipótesis

Sistemas ILP modernos como Progol, Hail e Imparo encuentran una hipótesis H usando el principio de la implicación inversa para las teorías B, E, H: ${displaystyle Bland Hmodels Eiff Bland neg Emodels neg H}$. Primero construyen una teoría intermedia F llamada teoría del puente que satisface las condiciones ${displaystyle Bland neg Emodels F}$ y ${displaystyle Fmodels neg H}$. Entonces ${displaystyle Hmodels neg F}$, generalizan la negación de la teoría del puente F con el anti-penailamiento. Sin embargo, el funcionamiento del anti-penailment ya que ser altamente no-determinista es computacionalmente más caro. Por lo tanto, se puede realizar una búsqueda alternativa de hipótesis utilizando el funcionamiento de la subsunción inversa (antisubsumption) en lugar de lo cual es menos no determinista que el anti-pentimiento.

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 está completo con el ejemplo de Yamamoto. Por su parte, el Imparo se completa tanto por el procedimiento de antivinculación como por su procedimiento de subsunción inversa ampliada.

Implementaciones

• 1BC y 1BC2: clasificación Bayesiana ingenua de primera orden:
• ACE (Un motor combinado)
• Aleph
• Atom Archived 2014-03-26 en la máquina Wayback
• Claudio
• DL-Learner
• DMax
• FastLAS (Aprendizaje rápido de conjuntos de respuestas)
• FOIL (Primera Orden de aprendizaje inductivo)
• Golem
• ILASP (Aprendizaje Inductivo de Programas de Juego de Respuestas)
• Imparo
• Inthelex (Incremental Theory Learner from EXamples) Archivado 2011-11-28 en la máquina Wayback
• Lime
• Metagol
• Mio
• MIS (Model Inference System) por Ehud Shapiro
• PROGOL
• RSD
• Warmr (ahora incluido en ACE)
• ProGolem