Gólem (ILP)

Golem es un algoritmo de programación lógica inductiva desarrollado por Stephen Muggleton y Cao Feng en 1990. ^[1] Utiliza la técnica de generalización mínima relativa propuesta por Gordon Plotkin , que conduce a una búsqueda de abajo hacia arriba a través de la red de subsunción . ^[2] En 1992, poco después de su introducción, Golem fue considerado el único sistema de programación lógica inductiva capaz de escalar a decenas de miles de ejemplos. ^[3]

Descripción

Golem toma como entrada un programa definido B como conocimiento de fondo junto con conjuntos de ejemplos positivos y negativos, denotados y respectivamente. La idea general es construir la generalización menos general de con respecto al conocimiento de fondo. Sin embargo, si B no es simplemente un conjunto finito de átomos base , entonces esta generalización menos general relativa puede no existir. ^[4] Por lo tanto, en lugar de usar B directamente, Golem usa el conjunto de todos los átomos base que se pueden resolver a partir de B en como máximo h pasos de resolución. Una dificultad adicional es que si no está vacío, la generalización menos general de puede implicar un ejemplo negativo. En este caso, Golem generaliza diferentes subconjuntos de por separado para obtener un programa de varias cláusulas. ^[2] Golem también emplea algunas restricciones en el espacio de hipótesis, asegurando que las generalizaciones menos generales relativas sean polinómicas en el número de ejemplos de entrenamiento. Golem exige que todas las variables en el encabezado de una cláusula también aparezcan en un literal del cuerpo de la cláusula; que el número de sustituciones necesarias para instanciar variables cuantificadas existencialmente introducidas en un literal esté acotado; y que la profundidad de la cadena de sustituciones necesarias para instanciar dicha variable también está limitada. ^[3] ${\textstyle E^{+}}$ ${\textstyle E^{-}}$ ${\textstyle E^{+}}$ ${\textstyle B^{h}}$ ${\textstyle E^{-}}$ ${\textstyle E^{+}}$ ${\textstyle E^{+}}$

Ejemplo

Relaciones familiares supuestas

El siguiente ejemplo 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 .

Se parte del 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.

La generalización menos general relativa se calcula ahora de la siguiente manera para obtener una definición de la relación hija .

• Relativizar cada literal de ejemplo positivo con el conocimiento 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}}}$,

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

  ${\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-unificar cada par ^[5] de literales compatibles ^[6] :
  • ${\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 de fondo ${\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)}$
• Eliminar todos los literales negados que contengan variables que no aparecen en un literal positivo:
  • después de eliminar todos los literales negados que contienen otras variables que no sean , solo queda, junto con todos los literales básicos del conocimiento de fondo ${\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})}$
• Convertir las cláusulas nuevamente 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{all background knowledge facts}})}$

La cláusula de Horn resultante es la hipótesis h obtenida por Golem. De manera informal, la cláusula dice " se llama hija de si es 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}}$

Referencias

1. Muggleton, Stephen H.; Feng, Cao (1990). Arikawa, Setsuo; Goto, Shigeki; Ohsuga, Setsuo; Yokomori, Takashi (eds.). "Inducción eficiente de programas lógicos". Algorithmic Learning Theory, Primer taller internacional, ALT '90, Tokio, Japón, 8-10 de octubre de 1990, Actas . Springer/Ohmsha: 368–381.
2. Nienhuys-Cheng, Shan-hwei; Wolf, Ronald de (1997). Fundamentos de la programación lógica inductiva . Apuntes de clases de informática. Apuntes de clases de inteligencia artificial. Berlín Heidelberg: Springer. pp. 354–358. ISBN 978-3-540-62927-6.
3. Aha, David W. (1992). "Relating relationshipal learning algorithms" (Relacionar algoritmos de aprendizaje relacional). En Muggleton, Stephen (ed.). Programación lógica inductiva . Londres: Academic Press . pág. 247.
4. Nienhuys-Cheng, Shan-hwei; Wolf, Ronald de (1997). Fundamentos de la programación lógica inductiva . Apuntes de clases de informática. Apuntes de clases de inteligencia artificial. Berlín Heidelberg: Springer. p. 286. ISBN 978-3-540-62927-6.
5. es decir, comparten el mismo símbolo de predicado y estado negado/no negado
6. en general: n -tupla cuando se dan n literales de ejemplo positivos