Aprendizaje inductivo: rboles y reglas de decisi n · El algoritmo FOIL Inteligencia Artificial II 2012–2013 Aprendizaje inductivo: árboles y reglas de decisión. Aprendizaje

Aprendizaje inductivo: arboles y reglas de decision

M. A. Gutierrez NaranjoF. J. Martın MateosJ. L. Ruiz Reina

Dpto. Ciencias de la Computacion e Inteligencia Artificial

Universidad de Sevilla

Inteligencia Artificial II 2012–2013 Aprendizaje inductivo: arboles y reglas de decision

Contenido

Introduccion

Arboles de decision:

El algoritmo ID3Entropıa e informacionBusqueda y sesgo inductivoSobreajuste y ruidoPoda y otras cuestiones

Reglas:

Reglas proposicionalesAlgoritmo de cobertura para aprendizaje de reglasproposicionalesReglas de primer orden: programacion logica inductivaEl algoritmo FOIL


Aprendizaje

Definiciones de aprendizaje:

Cualquier cambio en un sistema que le permita realizar lamisma tarea de manera mas eficiente la proxima vez (H.Simon)Modificar la representacion del mundo que se esta percibiendo(R. Michalski)Realizar cambios utiles en nuestras mentes (M. Minsky)

Aprendizaje automatico: construir programas que mejoranautomaticamente con la experiencia

Ejemplos de tareas:

Construccion de bases de conocimiento a partir de laexperienciaClasificacion y diagnosticoMinerıa de datos, descubrir estructuras desconocidas engrandes grupos de datosResolucion de problemas, planificacion y accion


Tipos de aprendizaje y paradigmas

Tipos de aprendizaje

SupervisadoNo supervisadoCon refuerzo

Paradigmas

Aprendizaje por memorizacionClasificacion (Clustering)Aprendizaje inductivoAprendizaje por analogıaDescubrimientoAlgoritmos geneticos, redes neuronales


Aprendizaje supervisado (ejemplo)

Conjunto de entrenamiento

Ejemplos: dıas en los que es recomendable (o no) jugar al tenisRepresentacion como una lista de pares atributo–valor

Ej. Cielo Temperatura Humedad Viento JugarTenisD1 Soleado Alta Alta Debil -D2 Soleado Alta Alta Fuerte -D3 Nublado Alta Alta Debil +D4 Lluvia Suave Alta Debil +. . .

Objetivo: Dado el conjunto de entrenamiento, aprender elconcepto “Dıas en los que se juega al tenis”

Problema: ¿Como expresar lo aprendido?

En este tema, veremos algoritmos para aprender arboles dedecision y para aprender reglas


Arboles de decision

Ejemplos de arboles de decision

Cielo

LluviaSoleado Nublado

+Viento

Debil

+

Humedad

Alta

+− −

Normal Fuerte


Arboles de decision

Ejemplos de arboles de decision

Color

Rojo Verde Azul

Forma

Redondo Cuadrado

Grande

Tamano

Pequeno

Grande

−

Tamano

Pequeno

+ −

+ −

+


Arboles de decision

Arboles de decision

Nodos interiores: atributosArcos: posibles valores del nodo origenHojas: valor de clasificacion (usualmente + o −, aunquepodrıa ser cualquier conjunto de valores, no necesariamentebinario)Representacion de una funcion objetivo

Disyuncion de reglas proposicionales:

(Cielo=Soleado ∧ Humedad=Alta → JugarTenis= −)∨ (Cielo=Soleado ∧ Humedad=Normal → JugarTenis= +)∨ (Cielo=Nublado → JugarTenis= +)∨ (Cielo=Lluvioso ∧ Viento=Fuerte → JugarTenis= −)∨ (Cielo=Lluvioso ∧ Viento=Debil → JugarTenis= +)

Capaz de representar cualquier subconjunto de instancias


Aprendizaje de arboles de decision

Objetivo: aprender un arbol de decision consistente con losejemplos, para posteriormente clasificar ejemplos nuevos

Ejemplo de conjunto de entrenamiento:

Ej. Cielo Temperatura Humedad Viento JugarTenisD1 Soleado Alta Alta Debil -D2 Soleado Alta Alta Fuerte -D3 Nublado Alta Alta Debil +D4 Lluvia Suave Alta Debil +. . .


Algoritmo ID3

Algoritmo ID3ID3(Ejemplos, Atributo-objetivo, Atributos)1. Si todos los Ejemplos son positivos, devolver un nodo

etiquetado con +2. Si todos los Ejemplos son negativos, devolver un nodo

etiquetado con -3. Si Atributos esta vacıo, devolver un nodo etiquetado con el valor

mas frecuente de Atributo-objetivo en Ejemplos.4. En otro caso:4.1. Sea A el atributo de Atributos que MEJOR clasifica Ejemplos4.2. Crear Arbol, con un nodo etiquetado con A.4.3. Para cada posible valor v de A, hacer:

* Anadir un arco a Arbol, etiquetado con v.

* Sea Ejemplos(v) el subconjunto de Ejemplos con valor delatributo A igual a v.

* Si Ejemplos(v) es vacıo:- Entonces colocar debajo del arco anterior un nodo etiquetado

con el valor mas frecuente de Atributo-objetivo en Ejemplos.- Si no, colocar debajo del arco anterior el subarbol

ID3(Ejemplos(v), Atributo-objetivo, Atributos-{A}).4.4 Devolver Arbol


¿Como saber que atributo clasifica mejor?

Entropıa de un conjunto de ejemplos D (resp. de unaclasificacion):

Ent(D) = − |P||D|

· log2|P||D|

− |N||D|

· log2|N||D|

donde P y N son, respectivamente, los subconjuntos deejemplos positivos y negativos de D

Notacion: Ent([p+, n−]), donde p = |P| y n = |N|

Intuicion:

Mide la ausencia de “homegeneidad” de la clasificacionTeorıa de la Informacion: cantidad media de informacion (enbits) necesaria para codificar la clasificacion de un ejemplo

Ejemplos:

Ent([9+, 5−]) = − 914

· log2914

− 514

· log2514

= 0,94

Ent([k+, k−]) = 1 (ausencia total de homogeneidad)Ent([p+, 0−]) = Ent([0+, n−]) = 0 (homogeneidad total)


Ganancia de informacion

Preferimos nodos con menos entropıa (arboles pequenos)

Entropıa esperada despues de usar un atributo A en el arbol:∑

v∈Valores(A)|Dv||D|

· Ent(Dv)

donde Dv es el subconjunto de ejemplos de D con valor delatributo A igual a v

Ganancia de informacion esperada despues de usar unatributo A:Ganancia(D,A) = Ent(D) −

∑v∈Valores(A)

|Dv||D|

· Ent(Dv)

En el algoritmo ID3, en cada nodo usamos el atributo conmayor ganancia de informacion (considerando los ejemploscorrespondientes al nodo)


Algoritmo ID3 (ejemplo 1)

Conjunto de entrenamiento:

Ej. Cielo Temperatura Humedad Viento JugarTenisD1 Soleado Alta Alta Debil -D2 Soleado Alta Alta Fuerte -D3 Nublado Alta Alta Debil +D4 Lluvia Suave Alta Debil +D5 Lluvia Baja Normal Debil +D6 Lluvia Baja Normal Fuerte -D7 Nublado Baja Normal Fuerte +D8 Soleado Suave Alta Debil -D9 Soleado Baja Normal Debil +D10 Lluvia Suave Normal Debil +D11 Soleado Suave Normal Fuerte +D12 Nublado Suave Alta Fuerte +D13 Nublado Alta Normal Debil +D14 Lluvia Suave Alta Fuerte -



Normal

Humedad

Alta

[3+, 4−] [6+, 1−]

Viento

Fuerte Debil

[6+, 2−] [3+, 3−]

TemperaturaCielo

[2+, 2−] [4+, 2−] [3+, 1−]

BajaSuaveAltaLluvia

[2+, 3−] [3+, 2−][4+, 0−]

Soleado Nublado



Entropıa inicial: Ent([9+, 5−]) = 0,94

Seleccion del atributo para el nodo raız:

Ganancia(D,Humedad) =0,94 − 7

14· Ent([3+, 4−]) − 7

14· Ent([6+, 1−]) = 0,151

Ganancia(D,Viento) =0,94 − 8

14· Ent([6+, 2−]) − 6

14· Ent([3+, 3−]) = 0,048

Ganancia(D,Cielo) =0,94 − 5

14· Ent([2+, 3−]) − 4

14· Ent([4+, 0−])

− 514

· Ent([3+, 2−]) = 0,246 (mejor atributo)Ganancia(D,Temperatura) =0,94 − 4

14· Ent([2+, 2−]) − 6

14· Ent([4+, 2−])

− 414

· Ent([3+, 1−]) = 0,02

El atributo seleccionado es Cielo



Arbol parcialmente construido:

?

Cielo

Soleado Nublado Lluvia

+ ?



Seleccion del atributo para el nodo Cielo=Soleado

DSoleado = {D1,D2,D8,D9,D11} con entropıaEnt([2+, 3−]) = 0,971

Ganancia(DSoleado,Humedad) =0,971 − 3

5· 0 − 2

5· 0 = 0,971 (mejor atributo)

Ganancia(DSoleado,Temperatura) =0,971 − 2

5· 0 − 2

5· 1 − 1

5· 0 = 0,570

Ganancia(DSoleado,Viento) =0,971 − 2

5· 1 − 3

5· 0,918 = 0,019

El atributo seleccionado es Humedad



Seleccion del atributo para el nodo Cielo=Lluvia:

DLluvia = {D4,D5,D6,D10,D14} con entropıaEnt([3+, 2−]) = 0,971

Ganancia(DLluvia,Humedad) =0,971 − 2

5· 1 − 3

5· 0,918 = 0,820

Ganancia(DLluvia,Temperatura) =0,971 − 3

5· 0,918 − 2

5· 1 = 0,820

Ganancia(DLluvia,Viento) =0,971 − 3

5· 0 − 2

5· 0 = 0,971 (mejor atributo)

El atributo seleccionado es Viento



Arbol finalmente aprendido:

Cielo

LluviaSoleado Nublado

+Viento

Debil

+

Humedad

Alta

+− −

Normal Fuerte



Conjunto de entrenamiento:

Ej. Color Forma Tamano ClaseO1 Rojo Cuadrado Grande +O2 Azul Cuadrado Grande +O3 Rojo Redondo Pequeno -O4 Verde Cuadrado Pequeno -O5 Rojo Redondo Grande +O6 Verde Cuadrado Grande -



Entropıa inicial en el ejemplo de los objetos,Ent([3+, 3−]) = 1

Seleccion del atributo para el nodo raız:

Ganancia(D,Color) =1− 3

6·Ent([2+, 1−])− 1

6·Ent([1+, 0−])− 2

6·Ent([0+, 2−]) =

0,543Ganancia(D,Forma) =1 − 4

6· Ent([2+, 2−]) − 2

6· Ent([1+, 1−]) = 0

Ganancia(D,Tamano) =1 − 4

6· Ent([3+, 1−]) − 2

6· Ent([0+, 2−]) = 0,459

El atributo seleccionado es Color



Arbol parcialmente construido:

?

Color

Rojo Verde Azul

− +



Seleccion del atributo para el nodo Color=Rojo:

DRojo = {O1,O3,O5} con entropıa Ent([2+, 1−]) = 0,914

Ganancia(DRojo,Forma) =0,914 − 1

3· Ent([1+, 0−]) − 2

3· Ent([1+, 1−]) = 0,247

Ganancia(DRojo,Tamano) =0,914 − 2

3· Ent([2+, 0−]) − 1

3· Ent([0+, 1−]) = 0,914

El atributo seleccionado es Tamano



Arbol finalmente aprendido:

Grande

Color

Rojo Verde Azul

−Tamano

Pequeno

+

+ −


Busqueda y sesgo inductivo

Busqueda en un espacio de hipotesis

Espacio de todos los arboles de decisionUn unico arbol candidato en cada pasoSin retroceso (peligro de optimos locales), busqueda enescaladaDecisiones tomadas a partir de conjuntos de ejemplos

Sesgo inductivo

Se prefieren arboles mas cortos sobre los mas largosSesgo preferencial, implıcito en la busquedaPrincipio de la navaja de Occam


Medida del rendimiento del aprendizaje

Conjunto de entrenamiento y conjunto de prueba

Aprender con el conjunto de entrenamientoMedida del rendimiento: proporcion de ejemplos bienclasificados en el conjunto de prueba

Repeticion de este proceso

Curva de aprendizajeEstratificacion: cada clase correctamente representada en elentrenamiento y en la prueba

Validacion cruzada

Dividir en k partes, y hace k aprendizajes, cada uno de ellostomando como prueba una de las partes y entrenamiento elresto. Finalmente hacer la media de los rendimientos.En la practica: validacion cruzada, con k = 10 y estratificacion


Sobreajuste y ruido

Una hipotesis h ∈ H sobreajusta los ejemplos deentrenamiento si existe h′ ∈ H que se ajusta peor que h a losejemplos pero actua mejor sobre la distribucion completa deinstancias.

Ruido: ejemplos incorrectamente clasificados. Causasobreajuste

Ejemplo: supongamos que por error, se incluye el ejemplo<Azul,Redondo,Pequeno> como ejemplo negativo

El arbol aprendido en este caso serıa (sobrejustado a losdatos):

Color

Rojo Verde Azul

Grande

−Tamano

+ −

Pequeno

+

Color

Rojo Verde Azul

Forma

CuadradoGrande

−Tamano

+ − − +

RedondoPequeno


Sobreajuste y ruido

Otras causas de sobreajuste:

Atributos que en los ejemplos presentan una aparenteregularidad pero que no son relevantes en realidadConjuntos de entrenamiento pequenos

Maneras de evitar el sobreajuste:

Parar el desarrollo del arbol antes de que se ajusteperfectamente a todos los datosPodar el arbol a posteriori

Poda a posteriori, dos aproximaciones:

Transformacion a reglas, podado de las condiciones de lasreglasRealizar podas directamente en el arbolLas podas se producen siempre que reduzcan el error sobre unconjunto de prueba


Podado de arboles

Algoritmo de poda para reducir el error1. Dividir el conjunto de ejemplos en Entrenamiento y Prueba2. Arbol=arbol obtenido por ID3 usando Entrenamiento3. Continuar=True4. Mientras Continuar:

* Medida = proporcion de ejemplos en Prueba correctamenteclasificados por Arbol

* Por cada nodo interior N de Arbol:- Podar temporalmente Arbol en el nodo N y sustituirlo por una

hoja etiquetada con la clasificacion mayoritaria en ese nodo- Medir la proporcion de ejemplos correctamente clasificados en

el conjunto de prueba.

* Sea K el nodo cuya poda produce mejor rendimiento

* Si este rendimiento es mejor que Medida, entoncesArbol = resultado de podar permanentemente Arbol en K

* Si no, Continuar=Falso5. Devolver Arbol


Otras cuestiones practicas del algoritmo ID3

Extensiones del algoritmo:

Atributos con valores contınuosOtras medidas para seleccionar atributosOtras estimaciones de errorAtributos sin valoresAtributos con coste

Algoritmos C4.5 y C5.0 (Quinlan)


Cambiando la salida: reglas proposicionales

Reglas de clasificacion:

R1: Si Cielo=Soleado ∧ Humedad=Alta

Entonces JugarTenis= −R2: Si Astigmatismo=+ ∧ Lagrima=Normal

Entonces Lente=Rigida

Ventaja de usar el formalismo de reglas

ClaridadModularidadExpresividad: pueden representar cualquier conjunto deinstanciasMetodos generalizables a primer orden de manera naturalFormalismo usado en sistemas basados en el conocimiento

Reglas y arboles de decision

Facil traduccion de arbol a reglas, pero no a la inversa


Aprendizaje de reglas

Objetivo: aprender un conjunto de reglas consistente con losejemplos

Una regla cubre un ejemplo si el ejemplo satisface lascondicionesLo cubre correctamente si ademas el valor del atributo en laconclusion de la regla coincide con el valor que el ejemplotoma en ese atributo

Una medida del ajuste de una regla R a un conjunto deejemplos D:

Frecuencia relativa: p/t (donde t = ejemplos cubiertos por Ren D, p = ejemplos correctamente cubiertos). Notacion:FR(R,D)

Algoritmos de aprendizaje de reglas:

ID3 + traduccion a reglasCoberturaAlgoritmos geneticos


Un conjunto de entrenamiento

Ej. Edad Dignostico Astigmatismo Lagrima LenteE1 Joven Miope - Reducida NingunaE2 Joven Miope - Normal BlandaE3 Joven Miope + Reducida NingunaE4 Joven Miope + Normal RıgidaE5 Joven Hipermetrope - Reducida NingunaE6 Joven Hipermetrope - Normal BlandaE7 Joven Hipermetrope + Reducida NingunaE8 Joven Hipermetrope + Normal RıgidaE9 PrePresbicia Miope - Reducida NingunaE10 PrePresbicia Miope - Normal BlandaE11 PrePresbicia Miope + Reducida NingunaE12 PrePresbicia Miope + Normal RıgidaE13 PrePresbicia Hipermetrope - Reducida NingunaE14 PrePresbicia Hipermetrope - Normal BlandaE15 PrePresbicia Hipermetrope + Reducida NingunaE16 PrePresbicia Hipermetrope + Normal Ninguna


Un conjunto de entrenamiento

Ej. Edad Dignostico Astigmatismo Lagrima LenteE17 Presbicia Miope - Reducida NingunaE18 Presbicia Miope - Normal NingunaE19 Presbicia Miope + Reducida NingunaE20 Presbicia Miope + Normal RıgidaE21 Presbicia Hipermetrope - Reducida NingunaE22 Presbicia Hipermetrope - Normal BlandaE23 Presbicia Hipermetrope + Reducida NingunaE24 Presbicia Hipermetrope + Normal Ninguna

R2: Si Astigmatismo=+ ∧ Lagrima=Normal


R2 cubre E4, E8, E12, E16, E20 y E24, de los cuales cubrecorrectamente E4, E8, E12 y E20


Aprendiendo reglas que cubren ejemplos

Aprender una regla para clasificar Lente=Rigida

Si ?Entonces Lente=Rigida

Alternativas para ?, y frecuencia relativa de la regla resultante

Edad=Joven 2/8Edad=PrePresbicia 1/8Edad=Presbicia 1/8Diagnostico=Miopıa 3/12Diagnostico=Hipermetropıa 1/12Astigmatismo=− 0/12Astigmatismo=+ 4/12 *Lagrima=Reducida 0/12Lagrima=Normal 4/12 *

Regla parcialmente aprendida

Si Astigmatismo=+Entonces Lente=Rigida



Continuamos para excluir ejemplos cubiertos incorrectamente

Si Astigmatismo=+ ∧ ?Entonces Lente=Rigida


Edad=Joven 2/4Edad=PrePresbicia 1/4Edad=Presbicia 1/4Diagnostico=Miopıa 3/6Diagnostico=Hipermetropıa 1/6Lagrima=Reducida 0/6Lagrima=Normal 4/6 *

Regla parcialmente aprendida

Si Astigmatismo=+ ∧ Lagrima=Normal




Continuamos para excluir ejemplos cubiertos incorrectamente

Si Astigmatismo=+ ∧ Lagrima=Normal ∧ ?Entonces Lente=Rigida


Edad=Joven 2/2 *Edad=PrePresbicia 1/2Edad=Presbicia 1/2Diagnostico=Miopıa 3/3 *Diagnostico=Hipermetropıa 1/3

Regla finalmente aprendida (no cubre incorrectamente ningunejemplo)

Si Astigmatismo=+ ∧ Lagrima=Normal ∧Diagnostico=Miopia




Queda un ejemplo con Lente=Rigida no cubierto por R2

Comenzamos otra vez con “Si ? Entonces Lente=Rigida”,pero ahora con D′ = D \ {E4, E12, E20}

Reglas finalmente aprendidas para Lente=Rigida:

R1: Si Astigmatismo= + ∧ Lagrima=Normal ∧Diagnostico=Miopia


R2: Si Edad=Joven ∧ Astigmatismo= + ∧Lagrima=Normal


Cubren correctamente los 4 ejemplos de Lente=Rigida (y sesolapan)

Ahora se podrıa continuar para aprender reglas queclasifiquen:

Lente=Blanda

Lente=Ninguna


Algoritmo de aprendizaje de reglas por cobertura

Algoritmo de aprendizaje por coberturaAprendizaje-por-Cobertura(D,Atributo,v)1. Hacer Reglas-aprendidas igual a vacıo2. Hacer E igual a D3. Mientras E contenga ejemplos cuyo valor de Atributo es v, hacer:3.1 Crear una regla R sin condiciones y conclusion Atributo=v3.2 Mientras que haya en E ejemplos cubiertos por R incorrectamente

o no queden atributos que usar, hacer:3.2.1 Elegir la MEJOR condicion A=w para anadir a R, donde A es

un atributo que no aparece en R y w es un valor de losposibles que puede tomar A

3.2.2 Actualizar R anadiendo la condicion A=w a R3.3 Incluir R en Reglas-aprendidas3.4 Actualizar E quitando los ejemplos cubiertos por R4. Devolver Reglas-Aprendidas

Algoritmo para aprender un conjunto de reglas (a partir de D)

Reglas para predecir situaciones en las que un Atributo dadotoma un valor v


Control en el algoritmo de cobertura

Bucle externo:

Anade reglas (la hipotesis se generaliza)Cada regla anadida cubre algunos ejemplos correctamenteElimina en cada vuelta los ejemplos cubiertos por la reglaanadidaY se anaden reglas mientras queden ejemplos sin cubrir

Bucle interno:

Anade condiciones a la regla (la regla se especializa)Cada nueva condicion excluye ejemplos cubiertosincorrectamenteY esto se hace mientras haya ejemplos incorrectamentecubiertos

Cobertura frente a ID3

Aprende una regla cada vez, ID3 lo hace simultaneamenteID3: elecciones de atributosCobertura: elcciones de parejas atributo-valor


Algoritmo de cobertura (propiedades)

Diferentes criterios para elegir la mejor condicion en cadavuelta del bucle interno:

Se anade la condicion que produzca la regla con mayorfrecuencia relativa (como en el ejemplo)Se anade la que produzca mayor ganancia de informacion:

p · (log2p′

t′− log2

pt)

donde p′/t′ es la frecuencia relativa despues de anadir lacondicion y p/t es la frecuencia relativa antes de anadir lacondicion

Las reglas aprendidas por el algoritmo de cobertura se ajustanperfectamente al conjunto de entrenamiento (peligro desobreajuste)

Podado de las reglas a posterioriEliminar progresivamente condiciones hasta que no seproduzca mejoraCriterio probabilıstico para decidir la mejora


Insuficiencia expresiva de las reglas proposicionales

Ejemplo:

Aprender el concepto “ser hija de” a partir de una base dedatos de relaciones entre miembros de una familia, conejemplos positivos y negativos del conceptoDificultad de ser expresado en el modelo proposicional de paresatributo-valor

Formalizacion del ejemplo en logica de primer orden

Ejemplos positivos: (maria,ana), (eva,tomas)Ejemplos negativos: (tomas,ana), (eva,ana), (eva,ignacio)Conocimiento base: hombre(tomas), hombre(ignacio)mujer(ana), mujer(eva), mujer(maria),progenitor(ana,maria), progenitor(ana,tomas),progenitor(tomas,eva), progenitor(tomas,ignacio)


Programacion Logica Inductiva

Datos:

Ejemplos positivos: E⊕

Ejemplos negativos: E⊖

Conocimiento base: TLenguaje de hipotesis: L

Condiciones:

Necesidad a priori: (∃e⊕ ∈ E⊕)[T 6⊢ e⊕]Consistencia a priori: (∀e⊖ ∈ E⊖)[T 6⊢ e⊖]

Objetivo: Encontrar un conjunto finito H ⊂ L tal que secumplan

Suficiencia a posteriori: (∀e⊕ ∈ E⊕)[T⋃

H ⊢ e⊕]Consistencia a posteriori: (∀e⊖ ∈ E⊖)[T

⋃H 6⊢ e⊖]


Terminologıa en PLI

Se aprenden relaciones (o predicados) en lugar de paresatributo-valor

Los ejemplos vienen dados por tuplas de constantes sobre losque la relacion es cierta o falsa

(eva,tomas) es un ejemplo positivo de la relacion “ser hija de”y (tomas,ana) un ejemplo negativo

Una regla cubre un ejemplo si el ejemplo satisface lascondiciones de la regla.

La regla hija(A,B) :- progenitor(B,A), mujer(A)

cubre el ejemplo (maria,ana) y no cubre el ejemplo(eva,ignacio)

Una regla cubre correctamente un ejemplo si y solo si este espositivo

Objetivo: Encontrar un conjunto de reglas PROLOG quecubra todos los ejemplos positivos y ninguno negativo


El algoritmo FOIL

Algoritmo FOILFOIL(Ejemplos,Conocimiento-base,Predicado-objetivo)1. Hacer Reglas-aprendidas igual a vacıo2. Hacer E igual a Ejemplos3. Mientras E contenga ejemplos positivos, hacer:3.1 Crear una regla R sin cuerpo y con cabeza P(X1,...,Xn)

(donde P es el Predicado-objetivo y n su aridad)3.2 Mientras que haya en E ejemplos negativos cubiertos por R:3.2.1 GENERAR todos los posibles literales que pueden ser

anadidos al cuerpo de la regla R3.2.2 De todos ellos, sea L el MEJOR3.2.2 Actualizar R anadiendo el literal L al cuerpo de R3.3 Incluir R en Reglas-aprendidas3.4 Actualizar E quitando los ejemplos cubiertos por R4. Devolver Reglas-Aprendidas

Debemos precisar GENERAR y MEJOR


Generacion de nuevos literales en FOIL

Literales tomados de los predicados del conocimiento base:

De la forma Q(x1, . . . , xn) donde Q es un predicado delconocimiento base y xi son variables de la regla que se quiereextender o nuevas (al menos una de las variables ha de estaren la regla)Para ampliar la regla hija(A,B) :- podemos usar:hombre(A), hombre(B), mujer(A), mujer(B),progenitor(C,A), progenitor(A,C), progenitor(C,B),progenitor(B,C), progenitor(A,A), progenitor(B,A),progenitor(A,B), progenitor(B,B)

Literales de igualdad entre las variables que aparecen en laregla

Negaciones de los anteriores


Eleccion del mejor literal

El criterio mas usado:

Dada una regla R y un literal L medimos la mejora producidaen la cobertura al anadir un nuevo literal L a R para obteneruna nueva regla R′

Se elige el que produzca mayor ganancia de informacion:

t · (log2p′

p′+n′− log2

pp+n

)

donde R cubre p ejemplos positivos y n negativos, R′ cubre p′

ejemplos positivos y n′ negativos y t es el numero de ejemplospositivos cubiertos por R que siguen cubriendose en R′

Otros criterios posibles

Frecuencia relativaContenido de informacion


Un ejemplo de calculo de la ganancia de informacion

Ejemplos cubiertos por la regla hija(A,B) :-

Positivos (2): (maria,ana) y (eva,tomas)

Negativos (3): (tomas,ana), (eva,ana) y (eva,ignacio)

Ejemplos cubiertos por la reglahija(A,B) :- progenitor(B,A)

Positivos (2): (maria,ana) y (eva,tomas).Negativos (1): (tomas,ana).Positivos cubiertos por la regla original que siguen estandocubiertos por la regla extendida (2): (maria,ana), y(eva,tomas).

Ganancia de informacion producida:2 · (log2(2/(2 + 1)) − log2(2/(2 + 3))) = 1,474


Literales que introducen nuevas variables

Al introducir nuevas variables:

Las tuplas se extienden con las nuevas ligadurasPor tanto, el numero de ejemplos cubiertos puede aumentar(tanto positivos como negativos)Precision del valor t en la formula de ganancia de informacion:un ejemplo positivo se considera que sigue cubierto al extenderla regla si existe alguna extension del ejemplo que quedacubierto por la regla


Literales que introducen nuevas variables (ejemplo)

Ejemplos cubiertos por la regla hija(A,B) :-

Positivos (2): (maria,ana) y (eva,tomas)

Negativos (3): (tomas,ana), (eva,ana) y (eva,ignacio)

Ejemplos (extendidos) cubiertos por la reglahija(A,B) :- progenitor(B,C)

Positivos (4): (maria,ana,maria), (maria,ana,tomas),(eva,tomas,eva) y (eva,tomas,ignacio)

Negativos (4): (tomas,ana,maria), (tomas,ana,tomas),(eva,ana,maria) y (eva,ana,tomas)

Positivos cubiertos por la regla original que siguen estandocubiertos por la regla extendida (2): (maria,ana), y(eva,tomas).

Ganancia de informacion producida:2 · (log2(4/(4 + 4)) − log2(2/(2 + 3))) = 0,644


Ejemplo con FOIL

Regla inicial: hija(A,B) :-

Ejemplos positivos cubiertos: (maria, ana), (eva, tomas)Ejemplos negativos cubiertos: (tomas, ana), (eva, ana),(eva, ignacio)

Posibles reglas y ganancia de las mismashija(A,B) :- hombre(A) 0.000hija(A,B) :- hombre(B) 0.322hija(A,B) :- mujer(A) 0.644hija(A,B) :- mujer(B) -0.263hija(A,B) :- progenitor(C,A) 0.000hija(A,B) :- progenitor(A,C) 0.000hija(A,B) :- progenitor(C,B) 0.322hija(A,B) :- progenitor(B,C) 0.644hija(A,B) :- progenitor(A,A) 0.000hija(A,B) :- progenitor(B,A) 1.474hija(A,B) :- progenitor(A,B) 0.000hija(A,B) :- progenitor(B,B) 0.000

Regla extendida: hija(A,B) :- progenitor(B,A)


Ejemplo con FOIL

Regla obtenida: hija(A,B) :- progenitor(B,A)

Ejemplos positivos cubiertos: (maria, ana), (eva, tomas)Ejemplos negativos cubiertos: (tomas, ana)Posibles reglas y ganancia de las mismashija(A,B) :- progenitor(B,A), hombre(A) 0.000hija(A,B) :- progenitor(B,A), hombre(B) 0.585hija(A,B) :- progenitor(B,A), mujer(A) 1.170hija(A,B) :- progenitor(B,A), mujer(B) -0.415hija(A,B) :- progenitor(B,A), progenitor(C,A) 0.000hija(A,B) :- progenitor(B,A), progenitor(A,C) 0.000hija(A,B) :- progenitor(B,A), progenitor(C,B) 0.585hija(A,B) :- progenitor(B,A), progenitor(B,C) 0.000hija(A,B) :- progenitor(B,A), progenitor(A,A) 0.000hija(A,B) :- progenitor(B,A), progenitor(B,A) 0.000hija(A,B) :- progenitor(B,A), progenitor(A,B) 0.000hija(A,B) :- progenitor(B,A), progenitor(B,B) 0.000

Regla extendida: hija(A,B) :- progenitor(B,A), mujer(A)


Ejemplo

Aprender la relacion “ser abuelo de” a partir del siguienteejemplo

Isabel - Felipe

Diana - Carlos

Guillermo Harry

EduardoAndres - Sara

EugeniaBeatriz

Ana - Frank

Pedro Zara


Ejemplo

Ejemplos positivos: (felipe,guillermo), (felipe,harry),(felipe,pedro), (felipe,zara), (felipe,beatriz),(felipe,eugenia)

Ejemplos negativos: Todos los demas (Hipotesis del MundoCerrado)

Conocimiento base:padre(felipe,carlos), padre(felipe,ana), padre(felipe,andres),

padre(felipe,eduardo), padre(carlos,guillermo), padre(carlos,harry),

padre(mark,pedro), padre(mark,zara), padre(andres,beatriz),

padre(andres,eugenia), madre(isabel,carlos), madre(isabel,ana),

madre(isabel,andres), madre(isabel,eduardo), madre(diana,guillermo),

madre(diana,harry), madre(ana,pedro), madre(ana,zara),

madre(sara,beatriz), madre(sara,eugenia),

progenitor(X,Y) :- padre(X,Y),

progenitor(X,Y) :- madre(X,Y)


Ejemplo con FOIL

Regla inicial: abuelo(A,B) :-

Ejemplos positivos cubiertos: (felipe,guillermo),(felipe,harry), (felipe,pedro), (felipe,zara),(felipe,beatriz), (felipe,eugenia)Ejemplos negativos cubiertos: (felipe,felipe),(felipe,isabel), (felipe,diana), (felipe,carlos),(felipe,ana), (felipe,frank), (felipe,andres),(felipe,sara), (felipe,eduardo), (isabel,isabel),(isabel,diana), (isabel,carlos), (isabel,ana),(isabel,frank), (isabel,andres), (isabel,sara),(isabel,eduardo), (isabel,guillermo), (isabel,harry),(isabel,pedro), (isabel,zara), (isabel,beatriz),(isabel,eugenia), ...


Ejemplo con FOIL


Posibles reglas y ganancia de las mismasabuelo(A,B) :- padre(C,A) 0.000abuelo(A,B) :- padre(A,C) 15.510abuelo(A,B) :- padre(C,B) 3.510abuelo(A,B) :- padre(B,C) 0.000abuelo(A,B) :- padre(A,A) 0.000abuelo(A,B) :- padre(B,A) 0.000abuelo(A,B) :- padre(A,B) 0.000abuelo(A,B) :- padre(B,B) 0.000abuelo(A,B) :- madre(C,A) 0.000abuelo(A,B) :- madre(A,C) 0.000abuelo(A,B) :- madre(C,B) 3.510abuelo(A,B) :- madre(B,C) 0.000abuelo(A,B) :- madre(A,A) 0.000abuelo(A,B) :- madre(B,A) 0.000abuelo(A,B) :- madre(A,B) 0.000abuelo(A,B) :- madre(B,B) 0.000


Ejemplo con FOIL


Posibles reglas y ganancia de las mismasabuelo(A,B) :- progenitor(C,A) 0.000abuelo(A,B) :- progenitor(A,C) 9.510abuelo(A,B) :- progenitor(C,B) 3.510abuelo(A,B) :- progenitor(B,C) 0.000abuelo(A,B) :- progenitor(A,A) 0.000abuelo(A,B) :- progenitor(B,A) 0.000abuelo(A,B) :- progenitor(A,B) 0.000abuelo(A,B) :- progenitor(B,B) 0.000

Regla extendida: abuelo(A,B) :- padre(A,C)


Ejemplo con FOIL

Regla obtenida: abuelo(A,B) :- padre(A,C)

Ejemplos positivos cubiertos: (felipe,guillermo),(felipe,harry), (felipe,pedro), (felipe,zara),(felipe,beatriz), (felipe,eugenia)Ejemplos negativos cubiertos: (felipe,ana), (felipe,andres),(felipe,carlos), (felipe,diana), (felipe,eduardo),(felipe,felipe), (felipe,isabel), (felipe,mark),(felipe,sara), (carlos,ana), (carlos,andres),(carlos,beatriz), (carlos,carlos), (carlos,diana),(carlos,eduardo), (carlos,eugenia), (carlos,felipe),(carlos,guillermo), (carlos,harry), (carlos,isabel),(carlos,mark), (carlos,pedro), (carlos,sara),(carlos,zara), ...


Ejemplo con FOIL


Posibles reglas y ganancia de las mismasabuelo(A,B) :- padre(A,C), progenitor(D,A) 0.000abuelo(A,B) :- padre(A,C), progenitor(A,D) 3.087abuelo(A,B) :- padre(A,C), progenitor(D,B) 3.510abuelo(A,B) :- padre(A,C), progenitor(B,D) 0.000abuelo(A,B) :- padre(A,C), progenitor(D,C) 0.000abuelo(A,B) :- padre(A,C), progenitor(C,D) 7.932abuelo(A,B) :- padre(A,C), progenitor(A,A) 0.000abuelo(A,B) :- padre(A,C), progenitor(B,A) 0.000abuelo(A,B) :- padre(A,C), progenitor(C,A) 0.000abuelo(A,B) :- padre(A,C), progenitor(A,B) 0.000abuelo(A,B) :- padre(A,C), progenitor(B,B) 0.000abuelo(A,B) :- padre(A,C), progenitor(C,B) 15.863abuelo(A,B) :- padre(A,C), progenitor(A,C) 0.000abuelo(A,B) :- padre(A,C), progenitor(B,C) 0.000abuelo(A,B) :- padre(A,C), progenitor(C,C) 0.000abuelo(A,B) :- padre(A,C), madre(D,A) 0.000abuelo(A,B) :- padre(A,C), madre(A,D) 0.000abuelo(A,B) :- padre(A,C), madre(D,B) 3.510


Ejemplo con FOIL


Posibles reglas y ganancia de las mismasabuelo(A,B) :- padre(A,C), madre(B,D) 0.000abuelo(A,B) :- padre(A,C), madre(D,C) 0.000abuelo(A,B) :- padre(A,C), madre(C,D) 7.932abuelo(A,B) :- padre(A,C), madre(A,A) 0.000abuelo(A,B) :- padre(A,C), madre(B,A) 0.000abuelo(A,B) :- padre(A,C), madre(C,A) 0.000abuelo(A,B) :- padre(A,C), madre(A,B) 0.000abuelo(A,B) :- padre(A,C), madre(B,B) 0.000abuelo(A,B) :- padre(A,C), madre(C,B) 5.288abuelo(A,B) :- padre(A,C), madre(A,C) 0.000abuelo(A,B) :- padre(A,C), madre(B,C) 0.000abuelo(A,B) :- padre(A,C), madre(C,C) 0.000abuelo(A,B) :- padre(A,C), padre(D,A) 0.000abuelo(A,B) :- padre(A,C), padre(A,D) 3.087abuelo(A,B) :- padre(A,C), padre(D,B) 3.510abuelo(A,B) :- padre(A,C), padre(B,D) 0.000abuelo(A,B) :- padre(A,C), padre(D,C) 0.000abuelo(A,B) :- padre(A,C), padre(C,D) 7.932


Ejemplo con FOIL


Posibles reglas y ganancia de las mismasabuelo(A,B) :- padre(A,C), padre(A,A) 0.000abuelo(A,B) :- padre(A,C), padre(B,A) 10.000abuelo(A,B) :- padre(A,C), padre(C,A) 0.000abuelo(A,B) :- padre(A,C), padre(A,B) 0.000abuelo(A,B) :- padre(A,C), padre(B,B) 0.000abuelo(A,B) :- padre(A,C), padre(C,B) 10.575abuelo(A,B) :- padre(A,C), padre(A,C) 0.000abuelo(A,B) :- padre(A,C), padre(B,C) 0.000abuelo(A,B) :- padre(A,C), padre(C,C) 0.000abuelo(A,B) :- padre(A,C), abuelo(C,A) 0.000abuelo(A,B) :- padre(A,C), abuelo(C,B) 0.000abuelo(A,B) :- padre(A,C), abuelo(A,C) 0.000abuelo(A,B) :- padre(A,C), abuelo(B,C) 0.000abuelo(A,B) :- padre(A,C), abuelo(C,C) 0.000

Regla extendida:abuelo(A,B) :- padre(A,C), progenitor(C,B)


Ejemplo de relacion recursiva con FOIL

Grafo

1 2 3

4

5

Ejemplos positivos: (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5),(3,4), (3,5)

Conocimiento base: enlace(1,2), enlace(2,3),enlace(3,4), enlace(3,5)



Regla inicial: camino(A,B) :-

Ejemplos positivos cubiertos: (1,2), (1,3), (1,4), (1,5), (2,3),(2,4), (2,5), (3,4), (3,5)Ejemplos negativos cubiertos: (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)

Posibles reglas y ganancia de las mismascamino(A,B) :- enlace(C,A) -2.630camino(A,B) :- enlace(A,C) 5.503camino(A,B) :- enlace(C,B) 2.897camino(A,B) :- enlace(B,C) -1.578camino(A,B) :- enlace(A,A) 0.000camino(A,B) :- enlace(B,A) 0.000camino(A,B) :- enlace(A,B) 5.896camino(A,B) :- enlace(B,B) 0.000

Regla extendida: camino(A,B) :- enlace(A,B)

No cubre ejemplos negativos



Regla inicial: camino(A,B) :-

Ejemplos positivos cubiertos: (1,3), (1,4), (1,5), (2,4), (2,5)Ejemplos negativos cubiertos: (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)

Posibles reglas y ganancia de las mismascamino(A,B) :- enlace(C,A) -2.034camino(A,B) :- enlace(A,C) 2.925camino(A,B) :- enlace(C,B) 1.962camino(A,B) :- enlace(B,C) -1.017camino(A,B) :- enlace(A,A) 0.000camino(A,B) :- enlace(B,A) 0.000camino(A,B) :- enlace(A,B) 0.000camino(A,B) :- enlace(B,B) 0.000

Regla extendida: camino(A,B) :- enlace(A,C)



Regla obtenida: camino(A,B) :- enlace(A,C)

Ejemplos positivos cubiertos: (1,3), (1,4), (1,5), (2,4), (2,5)Ejemplos negativos cubiertos: (1,1), (2,1), (2,2), (3,1), (3,2),(3,3)

Posibles reglas y ganancia de las mismascamino(A,B) :- enlace(A,C), camino(C,A) 0.000camino(A,B) :- enlace(A,C), camino(C,B) 7.427camino(A,B) :- enlace(A,C), camino(A,C) 0.000camino(A,B) :- enlace(A,C), camino(B,C) 0.000camino(A,B) :- enlace(A,C), camino(C,C) 0.000camino(A,B) :- enlace(A,C), enlace(D,A) -1.673camino(A,B) :- enlace(A,C), enlace(A,D) -2.573camino(A,B) :- enlace(A,C), enlace(D,B) 2.427camino(A,B) :- enlace(A,C), enlace(B,D) -1.215camino(A,B) :- enlace(A,C), enlace(D,C) 0.000camino(A,B) :- enlace(A,C), enlace(C,D) 3.539



Regla obtenida: camino(A,B) :- enlace(A,C)

Posibles reglas y ganancia de las mismascamino(A,B) :- enlace(A,C), enlace(A,A) 0.000camino(A,B) :- enlace(A,C), enlace(B,A) 0.000camino(A,B) :- enlace(A,C), enlace(C,A) 0.000camino(A,B) :- enlace(A,C), enlace(A,B) 0.000camino(A,B) :- enlace(A,C), enlace(B,B) 0.000camino(A,B) :- enlace(A,C), enlace(C,B) 4.456camino(A,B) :- enlace(A,C), enlace(A,C) 0.000camino(A,B) :- enlace(A,C), enlace(B,C) 0.000camino(A,B) :- enlace(A,C), enlace(C,C) 0.000

Regla extendida:camino(A,B) :- enlace(A,C), camino(C,B)

No cubre ejemplos negativos



Grafo

1 2 3

4

5

Concepto aprendido:camino(A,B) :- enlace(A,B)

camino(A,B) :- enlace(A,C), camino(C,B)


Bibliografıa

Mitchell, T.M. Machine Learning (McGraw-Hill, 1997)

Cap. 3: “Decision tree learning”Cap. 10: “Learning Sets of Rules”

Russell, S. y Norvig, P. Artificial Intelligence (A modernapproach) (Second edition) (Prentice Hall, 2003)

Cap. 18: “Learning from observations”Cap. 19: “Knowledge in learning”

Russell, S. y Norvig, P. Inteligencia artificial (Un enfoquemoderno) (Tercera edicion) (Pearson-Prentice Hall, 2010)

Witten, I.H. y Frank, E. Data mining (Second edition)(Morgan Kaufmann Publishers, 2005)

Cap. 3, 4, 5 y 6.


Documents

Aprendizaje inductivo: rboles y reglas de decisi n · El algoritmo FOIL Inteligencia Artificial II 2012–2013 Aprendizaje inductivo: árboles y reglas de decisión. Aprendizaje