Algoritmo de aprendizaje inductivo de primer orden (FOIL)

Prerrequisitos: predicados y cuantificadores , aprender una regla , algoritmo de cobertura secuencial

Antes de entrar en el Algoritmo FOIL , comprendamos el significado de las reglas de primer orden y las diversas terminologías involucradas en él. 

Lógica de primer orden:

Todas las expresiones en lógica de primer orden se componen de los siguientes atributos:  

1. constantes — p. ej., tyler, 23, a
2. variables — p. ej., A, B, C
3. símbolos predicados, por ejemplo, hombre, padre (solo valores verdaderos o falsos)
4. símbolos de función, por ejemplo, edad (puede tomar cualquier constante como valor)
5. conectores — p. ej., ∧, ∨, ¬, →, ←
6. cuantificadores — p. ej., ∀, ∃

Término: Se puede definir como cualquier constante, variable o función aplicada a cualquier término. por ejemplo , edad (bob)

Literal: se puede definir como cualquier predicado o predicado negado aplicado a cualquier término. por ejemplo, mujer (demanda), padre (X, Y)

Tiene 3 tipos:

• Ground Literal: un literal que no contiene variables. por ejemplo, mujer (demanda)
• Literal positivo: un literal que no contiene un predicado negado. por ejemplo, mujer (demanda)
• Literal negativo: un literal que contiene un predicado negado. por ejemplo, padre (X, Y)

Cláusula: se puede definir como cualquier disyunción de literales cuyas variables se cuantifican universalmente.

where, 

M1, M2, ...,Mn --> literals (with variables universally quantified)
V --> Disjunction (logical OR)

Cláusula Horn: se puede definir como cualquier cláusula que contenga exactamente un literal positivo. 

Ya que, 

y

Entonces la cláusula del cuerno se puede escribir como 

where, 
H --> Horn Clause
L1,L2,...,Ln --> Literals 

(A ⇠ B) --> can be read as 'if B then A' [Inductive Logic]

and

∧ --> Conjunction (logical AND)
∨ --> Disjunction (logical OR)
¬ --> Logical NOT

Aprendiz inductivo de primer orden (FOIL)

En el aprendizaje automático, el aprendizaje inductivo de primer orden (FOIL) es un algoritmo de aprendizaje basado en reglas. Es una extensión natural de los algoritmos SEQUENTIAL-COVERING y LEARN-ONE-RULE. Sigue un enfoque codicioso. 

Aprendizaje inductivo:

Aprendizaje inductivo analizando y comprendiendo la evidencia y luego usándola para determinar el resultado. Se basa en la Lógica Inductiva.

Algoritmo involucrado

FOIL(Target predicate, predicates, examples)

• Pos ← positive examples
• Neg ← negative examples
• Learned rules ← {}
• while Pos, do
    //Learn a NewRule 
    – NewRule ← the rule that predicts target-predicate with no preconditions
 
    – NewRuleNeg ← Neg 
    – while NewRuleNeg, do
        Add a new literal to specialize NewRule
        1. Candidate_literals ← generate candidates for newRule based on Predicates
        2. Best_literal ← 
                 argmaxL∈Candidate literalsFoil_Gain(L,NewRule)

        3. add Best_literal to NewRule preconditions
        4. NewRuleNeg ← subset of NewRuleNeg that satisfies NewRule preconditions 
    – Learned rules ← Learned rules + NewRule 
    – Pos ← Pos − {members of Pos covered by NewRule}
 
• Return Learned rules

Funcionamiento del algoritmo: 

En el algoritmo, el ciclo interno se utiliza para generar una nueva regla óptima. Consideremos un ejemplo y comprendamos el funcionamiento paso a paso del algoritmo. 

Say we are tying to predict the Target-predicate- GrandDaughter(x,y).
We perform the following steps: [Refer Fig 2]

Step 1 - NewRule = GrandDaughter(x,y)
Step 2 - 
      2.a - Generate the candidate_literals. 
        (Female(x), Female(y), Father(x,y), Father(y.x), 
         Father(x,z), Father(z,x), Father(y,z), Father(z,y))

      2.b - Generate the respective candidate literal negations.
        (¬Female(x), ¬Female(y), ¬Father(x,y), ¬Father(y.x), 
         ¬Father(x,z), ¬Father(z,x), ¬Father(y,z), ¬Father(z,y))

Step 3 - FOIL might greedily select Father(x,y) as most promising, then
      NewRule = GrandDaughter(x,y) ← Father(y,z) [Greedy approach]

Step 4 - Foil now considers all the literals from the previous step as well as:
     (Female(z), Father(z,w), Father(w,z), etc.) and their negations.

Step 5 - Foil might select Father(z,x), and on the next step Female(y) leading to
         NewRule = GrandDaughter (x,y) ← Father(y,z) ∧ Father(z,x) ∧ Female(y)

Step 6 - If this greedy approach covers only positive examples it terminates 
     the search for further better results.

FOIL now removes all positive examples covered by this new rule. 
If more are left then the outer while loop continues.

FOIL: Medida de Evaluación de Desempeño

El rendimiento de una nueva regla no está definido por su medida de entropía (como el método RENDIMIENTO en el algoritmo Learn-One-Rule).

FOIL utiliza un algoritmo de ganancia para determinar qué nueva regla especializada optar. La utilidad de cada regla se estima por el número de bits necesarios para codificar todos los enlaces positivos. [Ec.1]

where, 
L is the candidate literal to add to rule R

p0 = number of positive bindings of R
n0 = number of negative bindings of R
p1 = number of positive binding of R + L
n1 = number of negative bindings of R + L
t  = number of positive bindings of R also covered by R + L

El algoritmo FOIL es otro algoritmo de aprendizaje basado en reglas que se extiende sobre los algoritmos de cobertura secuencial + aprender una regla y utiliza una métrica de rendimiento diferente (aparte de la ganancia de información/entropía) para determinar la mejor regla posible. Para cualquier duda/consulta con respecto al algoritmo, comente a continuación.