Progol

Progol es una implementación de programación lógica inductiva que combina la implicación inversa con la búsqueda de lo general a lo específico a través de un grafo de refinamiento . ^{[ 1 ] [ 2 ]}

La implicación inversa se utiliza con las declaraciones de modo para derivar la cláusula inferior, la cláusula más específica dentro del lenguaje de modo que engloba un ejemplo dado. Esta cláusula se utiliza para guiar una búsqueda en el grafo de refinamiento.

A diferencia de las búsquedas del sistema de inferencia de modelos (MIS) de Ehud Shapiro y del algoritmo FOIL de J. Ross Quinlan , la búsqueda de Progol ofrece una garantía demostrable de devolver una solución con la máxima compresión en el espacio de búsqueda. Para ello, realiza una búsqueda admisible similar a A* , guiada por la compresión, sobre cláusulas que engloban la cláusula más específica.

Progol gestiona los datos ruidosos mediante una medida de compresión que equilibra la descripción de los errores con la longitud de la descripción de la hipótesis. Progol permite utilizar programas Prolog arbitrarios como conocimiento previo y cláusulas definidas arbitrarias como ejemplos.

Progol fue introducido por Stephen Muggleton en 1995. En 1996, Ashwin Srinivasan, Muggleton, Michael Sternberg y Ross King ^{[ 3 ]} lo utilizaron para predecir la actividad mutagénica en compuestos nitroaromáticos . Esto se consideró una aplicación trascendental para la programación lógica inductiva , ya que un algoritmo de aprendizaje inductivo de propósito general había descubierto resultados novedosos y significativos para los expertos en el dominio. ^{[ 4 ]}

Progol demostró ser muy influyente en el campo, y el sistema de programación lógica inductiva Aleph, ampliamente utilizado, se basa directamente en Progol. ^{[ 5 ]}