Algoritmo FOCL

Requisito previo: Algoritmo FOIL

El algoritmo de aprendizaje combinado de primer orden (FOCL) es una extensión del algoritmo FOIL puramente inductivo. Utiliza la teoría del dominio para mejorar aún más la búsqueda de la mejor regla y mejora en gran medida la precisión. Incorpora los métodos de aprendizaje basado en explicaciones (EBL) a los métodos existentes de FOIL. Pero antes de entrar en el funcionamiento de FOCL, primero comprendamos lo siguiente:

• Teoría del dominio
• Aprendizaje basado en explicaciones

Aprendizaje basado en explicaciones (EBL)

En términos simples, es la capacidad de obtener técnicas básicas de resolución de problemas mediante la observación y el análisis de soluciones a problemas específicos. En términos de Machine Learning, es un algoritmo que tiene como objetivo comprender por qué un ejemplo es parte de un concepto particular para hacer generalizaciones o formar conceptos a partir de ejemplos de entrenamiento. Por ejemplo, EBL usa una teoría de dominio y crea un programa que aprende a jugar al ajedrez. 

Intuición: 

El objetivo de EBL es comprender las propiedades esenciales de un concepto particular. Entonces, necesitamos averiguar qué hace que un ejemplo sea parte de un concepto particular. A diferencia del algoritmo FOIL, aquí nos centramos en un ejemplo en lugar de recopilar varios ejemplos. 

La capacidad de explicar ejemplos únicos se conoce como «Teoría del dominio».

Un EBL acepta 4 tipos de entrada:

i) A training example: what the learning model sees in the world.
ii) A goal concept: a high level description of what the model is supposed to learn.
iii) A operational criterion: states which other terms
 can appear in the generalized result.
iv) A domain theory: set of rules that describe relationships between objects and actions in a domain.

A partir de los 4 parámetros anteriores, EBL usa la teoría del dominio para encontrar el ejemplo de entrenamiento que mejor describa el concepto de meta mientras respeta el criterio operativo y mantiene nuestra justificación lo más general posible.  

EBL implica 2 pasos:

1. Explicación: la teoría del dominio se utiliza para eliminar todos los ejemplos de entrenamiento sin importancia y conservar los importantes que describen mejor el concepto de objetivo.
2. Generalización: la explicación del concepto de meta se hace lo más general y ampliamente aplicable posible. Esto asegura que todos los casos estén cubiertos, no solo algunos específicos. 

Arquitectura EBL:  

• Modelo EBL durante el entrenamiento 
  • Durante el entrenamiento, el modelo generaliza el ejemplo de entrenamiento de tal manera que todos los escenarios conducen al concepto de objetivo, no solo en casos específicos. (Como se muestra en la figura 1)

• Modelo EBL después del entrenamiento 
  • Después del entrenamiento, el modelo EBL tiende a alcanzar directamente el espacio de hipótesis que involucra el concepto de meta.  (Como se muestra en la figura 2)

FOCL

El objetivo de FOCL, como FOIL, es crear una regla en términos de predicados definidos extensionalmente, que cubra todos los ejemplos positivos y ninguno de los ejemplos negativos. A diferencia de FOIL, FOCL integra conocimientos previos y métodos EBL, lo que conduce a una búsqueda mucho más eficiente del espacio de hipótesis que se ajusta a los datos de entrenamiento. (Como se muestra en la figura 3)

Fig. 3 – FOIL vs FOCL

FOCL: Intuición

Al igual que FOIL, FOCL también tiende a realizar un proceso iterativo de aprendizaje de un conjunto de mejores reglas para cubrir los ejemplos de entrenamiento y luego eliminar todos los ejemplos de entrenamiento cubiertos por esa mejor regla. (utilizando un algoritmo de cobertura secuencial)

Sin embargo, lo que hace que el algoritmo FOCL sea más poderoso es el enfoque que adapta mientras busca la mejor regla. 

Un literal se denomina operativo si puede describir correctamente el ejemplo de entrenamiento que conduce a la hipótesis de salida. Por el contrario, los literales que ocurren solo como características intermedias en la teoría del dominio, pero no como atributos primitivos de las instancias, se consideran no operativos . Los predicados no operativos se evalúan de la misma manera que los predicados operativos en FOCL. 

Algoritmo involucrado: 

//Inputs Literal --> operationalized 
List of positive examples 
List of negative examples
//Output Literal --> operational form
Operationalize(Literal, Positive examples, Negative examples):
    If(Literal = operational):
        Return Literal
    Initialize Operational_Literals to the empty set
    For each clause in the definition of Literal
        Compute information gain of the clause over Positive examples and Negative examples
    For the clause with the maximum gain
        For each literal L in the clause
            Operational_Literals <-- Operationalize(L, Positive examples, Negative examples)

Funcionamiento del Algoritmo

Paso 1: use el mismo método que se hizo en FOIL y agregue una sola característica para cada literal operativo que no sea parte del espacio de hipótesis para crear candidatos para la mejor regla.
(las flechas continuas en la Fig. 4 indican especializaciones de botella)

Paso 2: cree un literal operativo que sea lógicamente eficiente para explicar el concepto de objetivo de acuerdo con la teoría del dominio.
(las flechas discontinuas en la figura 4 indican especializaciones de botella basadas en la teoría del dominio)

Paso 3: agregue este conjunto de literales a las condiciones previas actuales de la hipótesis.

Paso 4: elimine todas aquellas condiciones previas del espacio de hipótesis que son innecesarias de acuerdo con los datos de entrenamiento.

Consideremos el ejemplo que se muestra en la figura 4. 

• Primero, FOCL crea todos los literales candidatos que tienen la posibilidad de convertirse en la mejor regla (todos indicados por flechas sólidas). Algo que ya hemos visto en el algoritmo FOIL. Además, crea varios literales candidatos lógicamente relevantes propios. (la teoría del dominio)
• Luego, selecciona uno de los literales de la teoría del dominio cuya condición previa coincida con el concepto de meta. Si hay varios de estos literales presentes, simplemente selecciona uno que brinda la mayor cantidad de información relacionada con el concepto de objetivo.

For example, 
    If the bottle (goal concept) is made of steel (while satisfying the other domain theory preconditions),
    then the algorithm will select that as it the most relevant information related to the goal concept.
    i.e. the bottle.

• Ahora, todos esos literales que se eliminaron a menos que afecten la precisión de la clasificación sobre los ejemplos de entrenamiento. Esto se hace para que la teoría del dominio no especialice demasiado el resultado añadiendo literales irrelevantes. Este conjunto de literales ahora se agrega a las condiciones previas de la hipótesis actual. 
• Finalmente, se selecciona un literal candidato que proporciona la máxima ganancia de información entre dos métodos de especialización. (FOIL y teoría del dominio)

FOCL es un poderoso algoritmo de aprendizaje automático que utiliza EBL y técnicas de teoría de dominio, alcanzando el espacio de hipótesis de manera rápida y eficiente. Ha mostrado resultados más mejorados y precisos que el algoritmo FOIL inductivo. Un estudio sobre «Posiciones legales en el tablero de ajedrez» mostró que en 60 ejemplos de entrenamiento que describen 30 posiciones legales y 30 ilegales en el tablero, la precisión de FOIL fue de alrededor del 86 %, mientras que la de FOCL fue de alrededor del 94 %. 
Se han obtenido resultados similares en otros dominios. Para cualquier duda/consulta, comenta abajo.