Programación lógica inductiva - Inductive logic programming

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.

• Esquema: ejemplos positivos + ejemplos negativos + conocimientos previos ⇒ 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. Shapiro construyó su primera implementación (Model Inference System) en 1981: un programa Prolog que infería inductivamente programas lógicos a partir de ejemplos positivos y negativos. El término Programación Lógica Inductiva fue introducido 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, introdujo las ideas teóricas de Invención de Predicados, Resolución Inversa y Vinculación Inversa. Muggleton implementó la vinculación inversa primero en el sistema PROGOL . El término " inductivo " aquí se refiere a una 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).

Definicion formal

El conocimiento previo se da como una teoría lógica B , comúnmente en forma de cláusulas de Horn utilizadas en la programación lógica . Los ejemplos positivos y negativos se dan como una conjunción y de literales fundamentales innecesarios y negados , respectivamente. Una hipótesis correcta h es una proposición lógica que satisface los siguientes requisitos. ${\ Displaystyle E ^ {+}}$${\ Displaystyle E ^ {-}}$

${\ displaystyle {\ begin {array} {llll} {\ text {Necesidad:}} & B & \ no \ modelos & 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 una hipótesis siempre que los hechos positivos sean explicables sin ella. La " suficiencia " requiere cualquier hipótesis generada h para explicar todos los ejemplos positivos . " Consistencia débil generación prohíbe" de cualquier hipótesis h que contradice el conocimiento de fondo B . La " consistencia fuerte " también prohíbe la generación de cualquier hipótesis h que sea inconsistente con los ejemplos negativos , dado el conocimiento previo B ; implica " Consistencia débil "; si no se dan ejemplos negativos, ambos requisitos coinciden. Džeroski solo requiere " Suficiencia " (llamada "Completitud" allí) y " Consistencia fuerte ". ${\ Displaystyle E ^ {+}}$${\ Displaystyle E ^ {-}}$

Ejemplo

Relaciones familiares supuestas en la sección "Ejemplo"

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

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

Comienza con el conocimiento previo (ver 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 verdadera para denotar la ausencia de ejemplos negativos.

El enfoque de la " generalización relativa mínima general (rlgg) " de Plotkin para 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.

• Relativice cada literal de ejemplo positivo con el conocimiento previo completo:

  ${\ Displaystyle {\ begin {alineado} {\ 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 {alineado}}}$,

• Convertir a la forma normal de la cláusula :

  ${\ Displaystyle {\ begin {alineado} {\ 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 {alineado}}}$,

• Anti-unifica cada par compatible de literales:
  • ${\ displaystyle {\ textit {dau}} (x_ {me}, x_ {ht})}$desde y ,${\ Displaystyle {\ textit {dau}} (m, h)}$${\ Displaystyle {\ textit {dau}} (e, t)}$
  • ${\ Displaystyle \ lnot {\ textit {par}} (x_ {ht}, x_ {me})}$desde y ,${\ Displaystyle \ lnot {\ textit {par}} (h, m)}$${\ Displaystyle \ lnot {\ textit {par}} (t, e)}$
  • ${\ Displaystyle \ lnot {\ textit {fem}} (x_ {me})}$desde y ,${\ Displaystyle \ lnot {\ textit {fem}} (m)}$${\ Displaystyle \ lnot {\ textit {fem}} (e)}$
  • ${\ Displaystyle \ lnot {\ textit {par}} (g, m)}$de y , similar para todos los demás literales de conocimiento previo${\ Displaystyle \ lnot {\ textit {par}} (g, m)}$${\ Displaystyle \ lnot {\ textit {par}} (g, m)}$
  • ${\ Displaystyle \ lnot {\ textit {par}} (x_ {gt}, x_ {me})}$de y , y muchos más literales negados${\ Displaystyle \ lnot {\ textit {par}} (g, m)}$${\ Displaystyle \ lnot {\ textit {par}} (t, e)}$
• Elimine todos los literales negados que contienen variables que no ocurren en un literal positivo:
  • después de eliminar todos los literales negados que contienen otras variables que , solo queda, junto con todos los literales básicos del conocimiento previo${\ displaystyle x_ {me}, x_ {ht}}$${\ Displaystyle {\ textit {dau}} (x_ {me}, x_ {ht}) \ lor \ lnot {\ textit {par}} (x_ {ht}, x_ {me}) \ lor \ lnot {\ textit {fem}} (x_ {me})}$
• Convierta las cláusulas de nuevo a la forma de Horn:
  • ${\ displaystyle {\ textit {dau}} (x_ {me}, x_ {ht}) \ leftarrow {\ textit {par}} (x_ {ht}, x_ {me}) \ land {\ textit {fem}} (x_ {me}) \ land ({\ text {todos los conocimientos previos}})}$

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

Con respecto a los requisitos anteriores , se satisfizo " Necesidad " porque el predicado dau no aparece en el conocimiento de fondo, lo que, por lo tanto, no puede implicar ninguna propiedad que contenga este predicado, como los ejemplos positivos. La " suficiencia " se satisface mediante la hipótesis calculada h , ya que, junto con los conocimientos previos, implica el primer ejemplo positivo , y de manera similar h y los conocimientos previos implican el segundo ejemplo positivo . La " consistencia débil " se satisface con h , ya que h se mantiene en la estructura (finita) de Herbrand descrita por el conocimiento previo; similar para " Consistencia fuerte ". ${\ Displaystyle {\ textit {par}} (h, m) \ land {\ textit {fem}} (m)}$${\ Displaystyle {\ textit {dau}} (m, h)}$${\ Displaystyle {\ textit {par}} (t, e) \ land {\ textit {fem}} (e)}$${\ Displaystyle {\ textit {dau}} (e, t)}$

La definición común de la relación de abuela, a saber. , no se puede aprender usando el enfoque anterior, ya que la variable y aparece solo en el cuerpo de la cláusula; los literales correspondientes se habrían eliminado en el cuarto paso del enfoque. Para superar esta falla, ese paso debe modificarse de manera que se pueda parametrizar con diferentes heurísticas de post-selección literal . Históricamente, la implementación de GOLEM se basa en el enfoque rlgg. ${\ displaystyle {\ textit {gra}} (x, z) \ leftarrow {\ textit {fem}} (x) \ land {\ textit {par}} (x, y) \ land {\ textit {par}} (y, z)}$

Sistema de programación lógica inductiva

El sistema de Programación Lógica Inductiva es un programa que toma como entrada las teorías lógicas y genera una hipótesis correcta. Teorías H wrt 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 puntuación incluye la longitud de compresión mínima donde una hipótesis con una complejidad de Kolmogorov más baja tiene la puntuación más alta y se devuelve. Un sistema de ILP es si y sólo si completa para cualquier teoría lógica de entrada cualquier correcta hipótesis H wrt a estas teorías de entrada se puede encontrar con su procedimiento de búsqueda hipótesis. ${\ Displaystyle B, E ^ {+}, E ^ {-}}$${\ Displaystyle B, E ^ {+}, E ^ {-}}$${\ Displaystyle B, E ^ {+}, E ^ {-}}$

Búsqueda de hipótesis

ILP sistemas modernos como Progol, granizo y Imparo encontrar una hipótesis H utilizando el principio de la vinculación inversa para las teorías B , E , H : . Primero construyen una teoría intermedia F llamada teoría puente que satisface las condiciones y . Entonces como , generalizan la negación de la teoría del puente F con la anti-vinculación. Sin embargo, el funcionamiento de la anti-vinculación, dado que es altamente no determinista, es computacionalmente más costoso. Por lo tanto, se puede realizar una búsqueda de hipótesis alternativas utilizando la operación de la subsunción inversa (anti-subsunción), que es menos no determinista que la anti-vinculación. ${\ Displaystyle B \ land H \ models E \ iff B \ land \ neg E \ models \ neg H}$${\ Displaystyle B \ land \ neg E \ models F}$${\ Displaystyle F \ modelos \ neg H}$${\ Displaystyle H \ modelos \ neg F}$

Surgen preguntas sobre la completitud 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 otro lado, Imparo se completa tanto con el procedimiento anti-vinculación como con su procedimiento extendido de subsunción inversa.

Implementaciones

• 1BC y 1BC2: clasificadores bayesianos ingenuos de primer orden:
• ACE (un motor combinado)
• Aleph
• Átomo
• Claudien
• Aprendiz de DL
• DMax
• FastLAS (aprendizaje rápido a partir de conjuntos de respuestas)
• FOIL (alumno inductivo de primer orden)
• Golem
• ILASP (Programas de aprendizaje inductivo de conjuntos de respuestas)
• Imparo
• Inthelex (aprendiz teórico incremental de ejemplos)
• Lima
• Metagol
• Mio
• MIS (sistema de inferencia modelo) por Ehud Shapiro
• PROGOL
• RSD
• Warmr (ahora incluido en ACE)
• ProGolem

Ver también

• Razonamiento de sentido común
• Análisis de concepto formal
• Razonamiento inductivo
• Programación inductiva
• Probabilidad inductiva
• Aprendizaje relacional estadístico
• Aprendizaje espacial de versiones

Referencias

Otras lecturas