prueba

Aprendizaje Automático

FOIL

Ejercicio 1. FOIL
Se utiliza el algoritmo FOIL para el aprendizaje del concepto ALCANZABLE(A, B). El
conjunto de ejemplos utilizado corresponde al grafo de lafigura:
4
1

2

3
5

Conectado = [(1,2), (2,3), (3,4), (3,5)]
Alcanzable = [(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,4), (3,5)]
La salida del algoritmo produce las dos reglassiguientes:
R1: ALCANZABLE(A, B) :- Conectado(A, B)
R2: ALCANZABLE(A, B) :- Conectado(A, C), Alcanzable (C, B)
1. Justificar detalladamente la obtención de la regla R1 admitiendo que el conjunto deliterales que producen las tres mayores ganancias son:
{Conectado(A, B), Conectado(A, C), Conectado(C, B)}
Para ello, obtener:
(a) Los conjuntos E0+ y E0-.
(b) Los conjuntos E0++, E1+ y E1- comoresultado de añadir, en cada caso, cada uno
de los literales indicados.
(c) La ganancia asociada a utilizar cada literal.
2. La regla R1 no cubre todos los ejemplos positivos. ¿Cuál es el conjunto deejemplos
positivos no cubiertos por R1?
3. Para el conjunto de ejemplos no cubiertos por R1, calcular la ganancia que supone
añadir el literal Conectado(A, C) a la nueva regla R2, indicando lacomposición de
los conjuntos implicados E2+, E2-, E2++, E3+ y E3-.
4. Construida ahora la regla parcial
ALCANZABLE(A, B) :- Conectado(A, C)
Calcular la ganancia que supone añadir el nuevo literalAlcanzable (C, B) a dicha
regla parcial, indicando nuevamente la composición de los conjuntos E3+, E3-, E3++,
E4+ y E4-.

Enrique J. Carmona Suárez

Dpto. Inteligencia Artificial

ETSI Informática,UNED

Aprendizaje Automático

FOIL

Solución:
El conjunto de ejemplos positivos y negativos del concepto meta son, respectivamente:
E0+ = [(1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5),(3,4), (3,5)]

⇒

Card(E0+) = 9

E0- = [ (1,1), (2,1), (2,2), (3,1), (3,2), (3,3), (4,1), (4,2),
(4,3), (4,4), (4,5), (5,1), (5,2), (5,3), (5.4), (5,5) ]

⇒

Card(E0-) = 16

Si extendemos...