Aprendiz inductivo de primer orden

En el aprendizaje automático , el algoritmo de aprendizaje inductivo de primer orden ( FOIL , por sus siglas en inglés) es un algoritmo de aprendizaje basado en reglas.

Fondo

Desarrollado en 1990 por Ross Quinlan , ^{[ 1 ]} FOIL aprende cláusulas de Horn sin funciones , un subconjunto del cálculo de predicados de primer orden . Dados ejemplos positivos y negativos de algún concepto y un conjunto de predicados de conocimiento previo , FOIL genera inductivamente una definición o regla lógica para el concepto. La regla inducida no debe incluir constantes ( color(X,red) se convierte en color(X,Y), red(Y) ) ni símbolos de función, pero puede permitir predicados negados; también se pueden aprender conceptos recursivos.

Al igual que el algoritmo ID3 , FOIL realiza un ascenso de colinas utilizando una métrica basada en la teoría de la información para construir una regla que cubra los datos. Sin embargo, a diferencia de ID3, FOIL utiliza un método de "separar y conquistar" en lugar de "divide y vencerás" , centrándose en crear una regla a la vez y recopilando los ejemplos no cubiertos para la siguiente iteración del algoritmo.

Algoritmo

El algoritmo FOIL es el siguiente:

Lista de ejemplos y predicados que se van a aprender

Salida: Un conjunto de cláusulas de Horn de primer orden.

FOIL( Pred , Pos , Neg )

Sea Pos el ejemplo positivo

Sea Pred el predicado que se va a aprender.

Hasta que Pos esté vacío, haga lo siguiente:

Sea Neg el ejemplo negativo

Establecer el cuerpo como vacío

Llamar LearnClauseBody

Agregar Pred ← Cuerpo a la regla

Eliminar de Pos todos los ejemplos que satisfagan Body

Procedimiento LearnCláusulaCuerpo

Hasta que Neg esté vacío, haga lo siguiente:

Elige una L literal

Unir L al cuerpo

Eliminar de Neg los ejemplos que no satisfacen L

Ejemplo

Supongamos que la tarea de FOIL es aprender el concepto abuelo(X,Y) dadas las relaciones padre(X,Y) y progenitor(X,Y) . Además, supongamos que nuestro Cuerpo actual consiste en abuelo(X,Y) ← progenitor(X,Z) . Esto se puede extender uniendo Cuerpo con cualquiera de los literales padre(X,X) , padre(Y,Z) , progenitor(U,Y) o muchos otros; para crear este literal, el algoritmo debe elegir tanto un nombre de predicado como un conjunto de variables para el predicado (al menos una de las cuales debe estar presente ya en un literal no negado de la cláusula). Si FOIL extiende una cláusula abuelo(X,Y) ← verdadero uniendo el literal progenitor(X,Z) , está introduciendo la nueva variable Z. Los ejemplos positivos ahora consisten en aquellos valores < X,Y,Z > tales que abuelo(X,Y) es verdadero y progenitor(X,Z) es verdadero; Los ejemplos negativos son aquellos en los que abuelo(X,Y) es verdadero pero padre(X,Z) es falso.

En la siguiente iteración de FOIL después de agregar parent(X,Z) , el algoritmo considerará todas las combinaciones de nombres de predicados y variables tales que al menos una variable en el nuevo literal esté presente en la cláusula existente. Esto resulta en un espacio de búsqueda muy grande. ^{[ 2 ]} Varias extensiones de la teoría FOIL han demostrado que las adiciones al algoritmo básico pueden reducir este espacio de búsqueda, a veces drásticamente.

Aprendiz combinado de primer orden

El algoritmo FOCL ^{[ 3 ]} ( First Order Combined Learner ) extiende FOIL de diversas maneras, lo que afecta la forma en que FOCL selecciona los literales a probar al extender una cláusula en construcción. Se permiten restricciones en el espacio de búsqueda, así como predicados definidos en una regla en lugar de en un conjunto de ejemplos (llamados predicados intensionales ); y, lo que es más importante, se permite una hipótesis potencialmente incorrecta como aproximación inicial al predicado que se va a aprender. El objetivo principal de FOCL es incorporar los métodos de aprendizaje basado en explicaciones (EBL) a los métodos empíricos de FOIL.

Sin embargo, incluso cuando no se proporciona información adicional a FOCL sobre FOIL, utiliza una estrategia de búsqueda iterativa de ampliación similar a la búsqueda en profundidad : primero, FOCL intenta aprender una cláusula sin introducir variables libres. Si esto falla (no hay ganancia positiva), se permite una variable libre adicional por cada fallo hasta que el número de variables libres supere el máximo utilizado para cualquier predicado.

Restricciones

A diferencia de FOIL, que no impone restricciones de tipado a sus variables, FOCL utiliza el tipado como una forma económica de incorporar un conocimiento previo sencillo. Por ejemplo, un predicado livesAt(X,Y) puede tener tipos livesAt(persona, ubicación) . Sin embargo, puede ser necesario introducir predicados adicionales: sin tipos, nextDoor(X,Y) podría determinar si la persona X y la persona Y viven una al lado de la otra, o si dos ubicaciones están una al lado de la otra. Con tipos, se necesitarían dos predicados diferentes , nextDoor(persona, persona) y nextDoor(ubicación, ubicación), para mantener esta funcionalidad. Sin embargo, este mecanismo de tipado elimina la necesidad de predicados como isPerson(X) o isLocation(Y) , y no es necesario considerar livesAt(A,B) cuando A y B se definen como variables de persona, lo que reduce el espacio de búsqueda. Además, el tipado puede mejorar la precisión de la regla resultante al eliminar literales imposibles como livesAt(A,B), que, sin embargo, pueden parecer tener una gran ganancia de información .

En lugar de implementar predicados triviales como equals(X,X) o between(X,X,Y) , FOCL introduce restricciones implícitas en las variables, reduciendo aún más el espacio de búsqueda. Algunos predicados deben tener todas las variables únicas, otros deben tener conmutatividad ( adjacent(X,Y) es equivalente a adjacent(Y,X) ), otros pueden requerir que una variable en particular esté presente en la cláusula actual, y existen muchas otras restricciones potenciales.

Reglas operativas

Las reglas operacionales son aquellas que se definen de forma extensional , es decir, como una lista de tuplas para las que un predicado es verdadero. FOIL solo permite reglas operacionales; FOCL extiende su base de conocimiento para permitir combinaciones de reglas llamadas reglas no operacionales, así como reglas parcialmente definidas o incorrectas para mayor robustez. Permitir definiciones parciales reduce la cantidad de trabajo necesario, ya que el algoritmo no necesita generar estas definiciones parciales por sí mismo, y las reglas incorrectas no añaden significativamente trabajo, puesto que se descartan si no se considera que proporcionan una ganancia de información positiva. Las reglas no operacionales son ventajosas, ya que las reglas individuales que combinan pueden no proporcionar ganancia de información por sí solas, pero son útiles cuando se toman en conjunto. Si un literal con la mayor ganancia de información en una iteración de FOCL no es operacional, se operacionaliza y su definición se añade a la cláusula en construcción.

Entradas: Texto literal a operacionalizar, Lista de ejemplos positivos, Lista de ejemplos negativos.

Salida literal en forma operacional

Operacionalizar (Literal, Ejemplos positivos, Ejemplos negativos)

Si Literal está operativo

Devolver literal

Inicializa OperationalLiterals al conjunto vacío.

Para cada cláusula en la definición de Literal

Calcula la ganancia de información de la cláusula sobre ejemplos positivos y ejemplos negativos.

Para la cláusula con la ganancia máxima

Para cada L literal en la cláusula

Agregue Operationalize( L , Ejemplos positivos, Ejemplos negativos) a OperationalLiterals

Una regla operacional podría ser el literal lessThan(X,Y) ; una regla no operacional podría ser between(X,Y,Z) ← lessThan(X,Y), lessThan(Y,Z) .

Reglas iniciales

La adición de reglas no operativas a la base de conocimiento aumenta el tamaño del espacio que FOCL debe explorar. En lugar de simplemente proporcionar al algoritmo un concepto objetivo (por ejemplo, abuelo(X,Y) ), el algoritmo toma como entrada un conjunto de reglas no operativas que prueba para verificar su corrección y operacionaliza para su concepto aprendido. Un concepto objetivo correcto mejorará claramente el tiempo de cálculo y la precisión, pero incluso un concepto incorrecto le dará al algoritmo una base desde la cual trabajar y mejorar la precisión y el tiempo. ^{[ 3 ]}

Referencias

http://www.csc.liv.ac.uk/~frans/KDD/Software/FOIL_PRM_CPAR/foil.html

↑ JR Quinlan. Aprendizaje de definiciones lógicas a partir de relaciones. Aprendizaje automático, volumen 5, número 3, 1990.
↑ Sea Var el mayor número de variables distintas para cualquier cláusula en la regla R , excluyendo la última conjunción. Sea MaxP el número de predicados con la mayor aridad MaxA . Entonces, una aproximación del número de nodos generados para aprender R es: NodosBuscados ≤ 2 * MaxP * (Var + MaxA – 1) ^MaxA , como se muestra en Pazzani y Kibler (1992).
1 2 Michael Pazzani y Dennis Kibler. La utilidad del conocimiento en el aprendizaje inductivo. Machine Learning, Volumen 9, Número 1, 1992.

[Quinlan1990-1] JR Quinlan. Aprendizaje de definiciones lógicas a partir de relaciones. Aprendizaje automático, volumen 5, número 3, 1990.

[2] Sea Var el mayor número de variables distintas para cualquier cláusula en la regla R , excluyendo la última conjunción. Sea MaxP el número de predicados con la mayor aridad MaxA . Entonces, una aproximación del número de nodos generados para aprender R es: NodosBuscados ≤ 2 * MaxP * (Var + MaxA – 1) ^MaxA , como se muestra en Pazzani y Kibler (1992).

[Pazzani-3] 1 2 Michael Pazzani y Dennis Kibler. La utilidad del conocimiento en el aprendizaje inductivo. Machine Learning, Volumen 9, Número 1, 1992.

[ 1 ]

[ 2 ]

[ 3 ]