Post on 25-Dec-2019
transcript
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
“Induccion de Reglas”
Carlos Valle Vidalcvalle@inf.utfsm.cl
Departamento de Informatica -Universidad Tecnica Federico Santa Marıa
Santiago, Mayo 2009
1 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Temario
1 Introduccion
2 Reglas Proposicionales
3 Evaluando la calidad de las reglas
2 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Temario
1 Introduccion
2 Reglas Proposicionales
3 Evaluando la calidad de las reglas
3 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Introduccion
Las tecnicas simbolicas emplean algun lenguaje descriptivoen la cual se expresa el aprendizaje.
Reglas de clasificacion simbolicas que generalizan los casosde entrenamiento V ML simbolico V Induccion de reglas
Las reglas proveen facil interpretacion.
Dado un conjunto de entrenamiento, el objetivo seraencontrar un conjunto de reglas que puedan ser usadas parapredecir o clasificar nuevas instancias.
4 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Introduccion (2)
Restricciones del lenguaje usado para describir los datos(data description language)
Lenguaje usado para describir el conjunto de reglasinducidas (hypothesis description language)
Sesgo del lenguaje: Restricciones impuestas por el lenguajepara definir el lenguaje y el ambito de los datos y larepresentacion del conocimiento.
Una regla de clasificacion generica dado un problema declasificacion de dos clases, separa las instancias en dosclases: positiva y negativa
5 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Clase Positiva
Clase positiva se define:Dado
Un lenguaje de descripcion de datos V un sesgo en laestructura de los datos.Ejemplos de entrenamiento V un conjunto de instanciasclasificadas descritas en el lenguaje descripcion de los datosUna hipotesis del lenguaje V sesgo en la estructura de lasreglas inducidasUna funcion de cobertura V define cuando las instanciasestan cubiertas por la regla
EncontrarUna hipotesis agrupadas en un conjunto de reglas descritaspor el lenguaje de hipotesis que sean consistentes (no cubraningun ejemplo negativo) y completas (cubra a todos losejemplos positivos).
6 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Definiciones
Ejemplos V instancias etiquetadas
Instancias por si mismas no estan etiquetadas
Hipotesis: salida del aprendizaje
Aprendizaje inductivo V Reglas invalidables por informacionfutura
Hipotesis inducidas seran representadas por un conjunto deReglas
7 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Definiciones (2)
Regla: expresion de la forma Cabeza← Cuerpo
Cuerpo describe las condiciones en las que la regla se gatilla
Cabeza tıpicamente es la etiqueta de la clase
Cuando se aprenden reglas de una clase, la cabeza esredundante
Una instancia es cubierta por la regla si satisface lascondiciones del cuerpo
Si un ejemplo “calza” con el cuerpo de una regla cuya cabezacoincide con su etiqueta V correctamente cubierta, sino Vincorrectamente cubierta.
8 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Extension a Multiclase
Supongamos que tenemos tres etiquetas c1,c2,c3
Tendremos tres tareas de aprendizaje
La primera contendra las reglas con cabeza c1, y las de c2 yc3 seran los ejemplos negativos
Consistencia y Completitud son condiciones muy estrictas,sin embargo, para grandes datasets esto es imposible (ruido)V aproximar la clase objetivo
9 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Extension a Multiclase (2)
Hay problemas con clases no-disjuntas V relajarconsistencia y completitudV Cobertura suficiente deejemplos positivos, alta precision de la prediccion, o nivel designificancia sobre un cierto umbral.
Se supone que no hay conocimiento previo (backgroundknowledge), solo a traves de los ejemplos
Reglas V proposicionales y relacionales
10 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Temario
1 Introduccion
2 Reglas Proposicionales
3 Evaluando la calidad de las reglas
11 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Representacion de datos
La entrada es un conjunto de instancias sin clasificar
Una instancia es un conjunto de atributos fijosAi, i ∈ {1, . . . ,n}Un atributo puede tener valores discretos o continuos
Un ejemplo ej es un vector de atributos junto a la etiqueta dela clase ej = (v1,j, . . . ,vn,j,cj)La clase puede ser algun valor cj ∈ {c1, . . . ,ck}dentro de lask clases posibles (atributo clase)
Normalmente los datos se organizan en una tabla, donde lascolumnas son los atributos y las filas representan losejemplos.
12 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Representacion de datos
Se intenta comprimir la representacion, en el ejemplo existentodas las combinaciones de los atributos por lo que no sepuede.
13 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Reglas If - Then - Else
Dado un conjunto de ejemplos, construiremos reglas de laforma
IF Condicion THEN Clase
Condicion puede contener uno o mas test para los atributos
La conclusion tiene la forma Clase = ci
Se puede usar Clase← Condicion o Cabeza← Cuerpo(antecedente - consecuente)
14 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Reglas If - Then - Else (2)
Primera y tercera regla consistentes, segunda es completa.
La condicion de la primera regla niega la segunda, el atributoastigmatism de la segunda y tercera regla estan “negados”
15 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Reglas If - Then - Else (3)
Formato de arbol
Existen reglas
IF Condicion THEN Clase [Distribucion de la Clase]
Reglas de la forma {R1,R2,R3, . . . ,DefaultRule}Construir: Hipotesis V Regla V Cuerpo V Caracterıstica
16 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Construccion de Caracterısticas
Reglas definidas por el lenguaje de hipotesis o porconocimiento previoConstructive inductionUn simple algoritmo de construccion de caracterısticas(viendolo como un problema de busqueda)
Para atributos discretos Ai, se generan caracterısticas de laforma Ai = vix y Ai 6= wiyPara atributos continuos Ai, se generan caracterısticas de laforma Ai < (vix +wiy)/2 se crean para todos los posiblesvalores (vix,wiy) y caracterısticas Ai ≥ (vix +wiy)/2 se creanpara todos los posibles valores (wiy,vix)Para atributos con valores enteros Ai se generan las 4 formasAi ≤ (vix +wiy)/2, Ai > (vix +wiy)/2,Ai = vix , Ai 6= wiy
Caracterısticas mas complejas se pueden generar probandolas relaciones Ai = Aj,Ai 6= Aj cuando los atributos son delmismo tipo.
17 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Estructurando el espacio de la regla
No se puede enumerar todo el espacio de reglas posibles
La busqueda se hace basado en criterios de generalizacion yespecializacion
Sea covers(R) el conjunto de instancias cubiertas por RLa regla R es mas general que R′ si (nocion semantica degeneralidad)
1 Ambas tienen el mismo consecuente2 covers(R)⊇ covers(R′)
Un criterio sintactico para una regla IF-THEN-ELSE, es quedado el mismo consecuente, la regla R es m´sa general queR′ si R′ tiene al menos las mismas restricciones comoantecedente de R
Atributos con desigualdades en las condiciones.
18 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Estructurando el espacio de la regla (2)
La generalidad ignora las clases de los ejemplos
Se pueden crear reglas mas especıficas que encierrensubconjuntos de ejemplos que pertenezcan a la misma clase(consistentes o puras)
Balance entre precision y cobertura
19 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Estructurando el espacio de la regla (3)
Se puede probar que la relacion de generalidad es refleja,antisimetrica y transitiva, por lo tanto, es un orden parcialLa relacion de generalidad es util porque
Cuando generalizamos un regla R′ a R todos los ejemploscubiertos por R′ son cubiertos por RCuando especializamos una regla R a R′, todos los ejemplosno cubiertos por R no son cubiertos por R′
Estas propiedades se usan para cortar el espacio debusqueda. La segunda propiedad se usa con los casospositivos, si la regla no cubre, todas las posiblesespecializaciones tampoco
La primera propiedad se usa con los ejemplos negativos, siuna regla cubre un ejemplo negativo, todas lasgeneralizaciones lo haran
20 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Aprendiendo reglas individuales: Estrategias debusqueda
La mayorıa de los learners siguen una de las siguientesestrategias
General a especıfico o topdown learners: comienzan de unaregla general y la especializan mientras cubran ejemplosnegativos.
La especializacion se detiene cuando la regla deja de serinconsistente con ejemplos negativos.
Durante la busqueda las reglas aseguran que al menoscubran un ejemplo positivo.
Learners usan un operador de refinamiento para computarlas posibles especializaciones de una regla
Especıfico a general o bottom-up learners: Comienzan desdeuna regla especıfica y la generalizan hasta que no puedaseguir generalizandola sin cubrir ejemplos negativos.
21 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Aprendiendo reglas individuales: Estrategias debusqueda (2)
El primer metodo genera reglas usualmente mas generalesque el segundo, lo que aumenta su capacidad degeneralizacion V usado en presencia de ruido.
El segundo metodo es recomendado con pocos datos, ocuando hay aprendizaje incremental.
Para pasar de general a especıfico es primordial el operadorde refinamiento
22 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Aprendiendo reglas individuales: Estrategias debusqueda (3)
Un operador de refinamiento ρ para un sesgo de lenguaje Les un mapeo desde L a 2L tal que ∀R ∈ L : ρ(R) es unconjunto de maxima especializacion de R, es decir no existenreglas mas generales en un elemento de ρ(R) y sonestrictamente , mas especıficas que R.
Para una regla R de la forma Clase = ci← condiciones, losrefinamientos R′ de R se obtienen agregando condicionesCond en el cuerpo. Es decir R′ es ci← condiciones&Cond
23 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Learn one rule
Algoritmo 1 General a especıfico para aprendizaje de una solaregla1: Procedure LearnOneRules(Ei,RuleSet)
Input: Ei = Pi⋃
Ni: Conjunto de ejemplos positivos y negativos de la clase ci2: Regla← (Clase = ci← Condiciones), donde Condiciones← 03: repeat4: ρ(Regla) = {R′, donde R′← Clase = ci← Condiciones & Cond}5: Evalue todos los R′ ∈ ρ(regla) de acuerdo al criterio de calidad6: Regla← mejor refinamiento en ρ(regla)7: until Regla satisfaga el criterio de calidad utilizado
Output: Regla
24 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Aprendiendo un conjunto de reglas: Algoritmo deCobertura
El algoritmo anterior tiene que repetirse, con algun criterio decobertura, por ejemplo, que todos los ejemplos positivosesten cubiertos.
El algoritmo de cobertura genera regla hasta que todos losejemplos positivos esten cubiertos, o hasta que se cumplaalgun otro criterio de parada
25 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Learn Set of Rules
Algoritmo 2 Algoritmo de cobertura1: Procedure LearnSetOfRules(Ei,RuleSet)
Input: Ei = Pi⋃
Ni: Conjunto de ejemplos positivos y negativos de la clase ci2: Ecur
i ← Ei,Pcuri ← Pi
3: Ruleset← /0
4: repeat5: LearnOneRule(Ecur
i ,Rule)6: RuleSet← RuleSet
⋃Rule
7: Pcuri ← Pcovered
i , borrar desde Pcuri los ejemplos positivos cubiertos por la
regla8: Ecur
i ← Pcuri
⋃Ni
9: until RuleSet satisfaga el criterio de calidad utilizadoOutput: RuleSet
26 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Aprendiendo un conjunto de reglas: Algoritmo deCobertura (2)
Cada regla dentro de la hipotesis cubre parte del espacio deinstancias, asignandole una clase. El rol de un ejemplopositivo es llamar la atencion del inductor de reglas, haciauna parte del espacio de instancias.
Los ejemplos negativos aseguran que las reglas no cubrandicho espacio.
Algoritmo V Los ejemplos positivos se van removiendo delalgoritmo, mientras los negativos se mantienen.
Remover ejemplos crea dependencias entre reglas
Usar pesos en los ejemplos el que decrece al aumentar lacobertura de las reglas
27 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Aprendiendo un conjunto de reglas: Algoritmo deCobertura (3)
Para generar la base de reglas para todas las clases ci seitera el algoritmo anterior para cada clase k
Este algoritmo se detiene usando un criterio de calidadNecesitamos heurısticas para
Evaluar la calidad de una reglaDecidir cuando para el refinamiento de una reglaCuando agregar reglas al conjunto de reglas de una clase
28 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Learn Rule base
Algoritmo 3 Construyendo un conjunto de reglas para todas lasclases1: Procedure LearnRuleBase(Ei,RuleSet)
Input: E conjunto de ejemplos de entrenamiento2: RuleBase← /0
3: for cada clase ci, i = 1..k do4: Pi← {Conjunto de ejemplos en E con etiqueta ci}5: Ni← {Conjunto de ejemplos en E con etiquetas de otras clases}6: LearnSetOfRules(Pi
⋃Ni,RuleSet)
7: RuleBase← RuleBase⋃
RuleSet8: end for
Output: RuleBase
29 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Temario
1 Introduccion
2 Reglas Proposicionales
3 Evaluando la calidad de las reglas
30 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Matriz de confusion
Metricas de calidad, por ejemplo, precision en la clasificacion
Usaremos reglas del tipo Cabeza← cuerpo tipoIF−THEN−ELSE
Matriz de confusionpredice positivo predice negativo
sea positivo VP FN Possea negativo FP VN Neg
PredPos PredNeg NEsto no es directamente aplicado a las reglas, ya que unaregla no hace predicciones negativas (un ejemplo no cubiertopor una regla, pudiese ser cubierto por otra)
31 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Tabla de Contingencia
Formato regla cabeza← Cuerpo V Predecir como positivoslas instancias que tienen cuerpo verdadero, y que seapositivo significa que la cabeza es positiva
Las predicciones negativas son las instancias donde elcuerpo es falso y que sea negativo significa que la cabeza esfalsa.
N es el numero de ejemplos de entrenamiento, la frecuenciarelativa n(X)
N asociada a X se denota por p(X)
Tabla de Contingencia:
B BH n(HB) n(HB) n(H)H n(HB) n(HB) n(H)
n(B) n(B) N
32 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Definiciones
cobertura es la fraccion de instancias cubiertas por el cuerpode una regla. Vista como medida de generalidad de una regla
Cov(H← B) = p(B)
soporte de una regla se relaciona con la medida deasociacion de la regla, tambien llamada frecuencia
sup(H← B) = p(HB)
33 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Definiciones (2)
precision de una regla es la medida mas importante decalidad
Acc(H← B) = P(H← B)
Esto es la probabilidad de que la cabeza sea verdadera,dado que el cuerpo tambien lo es
TPTP+FP
=n(HB)
n(HB)+n(HB)=
n(HB)n(B)
= p(H|B)
En recuperacion de informacion se llama precision, enasociacion de reglas se llama confianza
34 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Definiciones (3)
Error de la prediccion:Err(H← B) = 1−Acc(H← B) = p(H|B)Informatividad: Inf (R) =− log2 Acc(R), y es la cantidad deinformacion en bits que se necesita para transmitir a alguienque conoce la regla y quiere saber las clasificacionescorrectas de instancias cubiertas por la regla.
Solo necesitamos transmitir los mal clasificados, ya que unaregla bien clasificada no requiere de mas informacion.
35 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Definiciones (4)
ganancia en la prediccion se define como la diferencia entrela precision de dos reglas R = H← B y R′ = H← B′
AccG(R′,R) = Acc(R′)−Acc(R) = p(H|B′)−p(H|B)
Representa la ganancia de ir desde R a R’, por ejemplo alagregar una condicion a BUn caso especial es la precision relativa de una ganancia enla prediccion
RAcc(H← B) = p(H|B)−p(H)
Mide el incremento en la precision de la regla h← B respectoa la regla por defecto H← verdaderoLa ultima regla cubre a todas las instancias para satisfacer HQue tan util es conectar B con H.
36 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Compromiso entre precision y generalidad
Dada dos instancias con la misma precision, se escoge lamas general.
Para incorporar esto a las metricas, se define ganancia de laprecision con pesos, definida por
WAccG(R′,R) =p(B′)P(B)
(p(H|B′)−p(H|B))
la version relativa es la precision relativa con pesos
WRAcc(H← B) = p(B)(p(H|B)−p(H))
Estas metricas prefieren reglas menos precisas pero masgenerales (el costo de los falsos positivos es mas alto que losverdaderos positivos)
37 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Compromiso entre precision y generalidad (2)
Otra manera de lograr el compromiso entre precision ygeneralidades utilizar una nueva metrica ortogonal a laprecision
recall se define como la fraccion de elementos positivos queestan cubiertos por la regla
Recall(H← B) = p(B|H)
Una buena regla tiene alta precision y alto recall
Medida F parametro que indica la importancia relativa entreambas medidas)
especificidad es la fraccion de negativos no cubiertos por laregla
Spec(H← B) = p(B|H)
38 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Estimando Probabilidades
Evaluando sobre el conjunto de entrenamiento, queremosestimar para toda la poblacion.
El estimador de Laplace y el M-estimador, son tecnicasusadas para robustificar la estimacion y aumentar lacapacidad de generalizacion.
Ambos corrigen la frecuencia relativa, usando el punto devista bayesiano comenzando con una probabilidad a priori dela variable aleatoria a ser estimada.
Laplace ocupa un a priori uniforme, mientras que la otratecnica utiliza un criterio no-uniforme.
39 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Estimando Probabilidades (2)
Supongamos que una regla cubre p elementos positivos y nnegativos.
la frecuencia relativa de su precision se estima por pp+n
Si p y n son pequenos, agregar un ejemplo puede generar ungran cambio.
Laplace adapta la frecuencia relativa a p+1p+n+k , donde k es el
numero de clases, esto equivale a agregar k ejemplos uno decada clase.
Esto evita que la probabilidad sea 0 o 1 aun cuando lamuestra lo sugiera
Las frecuencias de la muestra son usadas para generar laprobabilidad a posteriori.
40 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Estimando Probabilidades (3)
m-estimador generaliza esto asumiendo una probabilidad apriori pi para cada clase ci.
el m-estimador es p+mpip+n+m , donde m es una parametro.
Equivale a agregar m ejemplos virtuales de acuerdo a ladistribucion a priori.
m grande es utilizado cuando hay mas ruido V le da mascredito a la probabilidad a priori
41 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Ejemplo
Comencemos con la reglaIFTHEN ContactLenses = hard [#soft=5 #hard=4 #none=15]
Es decir, la regla que clasifica todos los ejemplos como hard
Precision= 7/24, Laplace =5/27=0.19Refinemos la reglaIF TearProduction = reducedTHEN ContactLenses = hard [#soft=0 #hard=0 #none=12]IF TearProduction = normalTHEN ContactLenses = hard [#soft=5 #hard=4 #none=3]
El segundo refinamiento es mejor que el primero. Precision=4/12 = 0.33. Precision ganada = 0.17.IF TearProduction = normalAND Astigmatisgm = yes
THEN ContactLenses = hard [#soft=0 #hard=4 #none=2]
42 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Ejemplo (2)
IF TearProduction = normalAND Astigmatisgm = yesAND Age = young
THEN ContactLenses = hard [#soft=0 #hard=2 #none=0]IF TearProduction = normal
AND Astigmatisgm = yesAND Age = pre-prebyopic
THEN ContactLenses = hard [#soft=0 #hard=1 #none=1]IF TearProduction = normal
AND Astigmatisgm = yesAND Age = prebyopic
THEN ContactLenses = hard [#soft=0 #hard=1 #none=1]IF TearProduction = normal
AND Astigmatisgm = yesAND SpectaclePrescription = myope
THEN ContactLenses = hard [#soft=0 #hard=3 #none=0]IF TearProduction = normal
AND Astigmatisgm = yesAND SpectaclePrescription = hypermetrope
THEN ContactLenses = hard [#soft=0 #hard=1 #none=2]
43 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Ejemplo (3)
44 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Aprendiendo un conjunto de reglas no ordenadas
Se agrega una regla por defecto asignando la clasemayoritaria al conjunto de ejemplos de entrenamiento ESe evaluan todas las reglas, se decide por votacion
Los conflictos se resuelven tomando en cuenta el numero deejemplos de cada clase cubiertos por cada regla.
Supongamos un problema de dos clases, y dos reglas concobertura [10,2] y [4,40]. La cobertura total de las dos reglases [14,42] V [0.25,0.75]Estadıstico tasa de verosimilitud
2Rk
∑i=1
qi log2 (qi/pi)∼ χ2n−1
Donde ri son los ejemplos cubiertos de la claseci, i ∈ {1, . . . ,k}. Sea qi = ri/R y R = ∑
ki=1 ri
45 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Aprendiendo una lista ordenada de decisiones
LearnOneRule puede modificarse para aprender cuerpos dereglas en lugar de reglas completas.
El mejor cuerpo de una regla minimiza la entropıa de losejemplos cubiertos
Entropıa: ∑ki=1 qi log2 qi,qi = ri/R
Cuando el mejor cuerpo es encontrado, se le asigna la clasemayoritaria entre los ejemplos cubiertos
Se remueven todos los ejemplos cubiertos por la regla
Calzar con una regla gatilla directamente su ejecucion
46 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Aprendizaje de reglas de primer orden
Cada tren tiene 2-4 carros
Los carros tienen formas: rectangular, oval, U
Largo: corto o largo
Tipo de techo: sin techo, con punta, dentado
Forma de la carga: circulo,triangulo rectangulo
Numero de cargas: 1-3
47 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Prolog
Una posible regla: “Un tren va al este si tiene un carropequeno y cerrado”eastbound(T) :- hasCar(T,C), clength(C,short), not croof(C,no_roof)
El predicado clength es aplicado a los terminos C (variable),y short (constante)
eastbound/1 : predicado/nro.terminos
hasCar(T,C): T y C son variables si se reemplazan porconstantes
Hecho: hasCar(t1,c11) dice que el tren t1 tiene el carro c11
48 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Prolog (2)
Definicion de Predicado: Reglas con el mismo predicado enla cabeza
Definicion de Predicado extensiva: Definiciones depredicados que incluyen variablesPodemos aprender reglas de clasificacion de primer ordenaprendiendo reglas intencionales de la forma
definiciones de predicados comoeastbound(t1),eastbound(t2), . . . ,eastbound(t5)definiciones extensivas referidas a otros predicados:hasCar(t1,c11),croof (c11,no roof ), . . . ,hasCar(t6,c61)conocimiento adicional, por ejemplo, los carros largos tienen3 ruedas y los cortos 2: cwheels(C,3) :−clength(C, long) ycwheels(C,2) :−clength(C,short)
49 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Modelo de Datos
Un modelo de datos describe la estructura de los datos, ypuede expresarse mediante el modelo entidad-relacion
50 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Base de Datos
SELECT DISTINCT TRAIN.trainID FROM TRAIN, CAR WHERETRAIN.trainID = CAR.train ANDCAR.clength = ’short’ ANDCAR.croof != ’no_roof’
51 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Datalog
Cada tabla se mapea a un predicadotrain(TrainID,Eastbound),car(CarID,Cshape,Clength,Croof,Cwheels,Train),load(LoadID,Lshape, Lnumber,Car)
Cada fila de la BD es un hechotrain(t1,true),car(c11,rect,long.no_roof,2,t1),loan(l11,rect,3,c11)
Una variante es que cada predicado corresponda a unatributo
52 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Datalog (2)
Cada atributo que no clave en cada tabla es mapeado por unpredicado binario, involucrando el atributo y la clave.eastbound(TrainID,Eastbound),cshape(CarID,cshape),clength(CarID,Clength)
atributos binarios pueden mapearse con un solo termino. Ej:eastbound(t1, true) V eastbound(t1)Las hipotesis inducidas pueden escribirse comoeastbound(T) :- hasCar(T,C), clength(C,short), not croof(C,no_roof)
53 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Representacion de terminos
Cada termino representa a una entidadeastbound([car(rect,long, no_roof,2, load(rect,3)),
car(rect,short, peak,2, load(tria,1)),car(rect,long,no_roof,3, load(hexa,1)),car(rect,short, no_roof,2, load(circ,1))])
En esta representacion, podemos representar la hipotesis
eastbound(T) :- member(C,T), arg(2,C,short), not arg(3,C,no_roof)
Esta representacion permite que la informacion de lasentidades permanezca unida
Pero es poco flexible si queremos aprender a distintos nivelesde entidades, por ejemplo, si queremos aprender de loscarros y no de los trenes.
54 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Caracterısticas de primer orden
Consideremos dos clausulaseastbound(T) :- hasCar(T,C), clength(C,short), not croof(C,no_roof)
eastbound(T) :- hasCar(T,C1), clength(C1,short),hasCar(T,C2), not croof(C2,no_roof)
La segunda clausula es mas general que la primera.
El cuerpo de la primera es una caracterıstica de primerorden(la variable comun compartida por las caracterısticasesta en la cabeza) , la segunda contiene dos caracterısticasdistintasPodemos nombrara las caracterısticas, transformando aprimer orden:hasShortCar(T) :- hasCar(T,C), clength(C,short)hasClosedCar(T):- hasCar(T,C), not croof(C,no_roof)
55 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Caracterısticas de primer orden (2)
Podemos trasladar la clausula a una sin variables locales:eastbound(T) :- hasShortCar(T), hasClosedCar(T)
Esta regla solo depende de trenes, podrıamos usar una solatabla en terminos de estas propiedades V reglasemi-proposicional
Proposicionalizacion: Transformar un dataset multi-tabla, enuno de una sola tabla equivalente
Podemos predefinir las caracterısticas de primer orden aconsiderar
56 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Reglas de primer orden v/s proposicionales
Construccion de hipotesis: Si se permite la recursion deLearnSetOfRules introducir reglas de primer orden es mascomplicado ya que existe dependencia entre las reglas.
Construccion de reglas: Se debe asociar una cabeza a unpredicado a aprender, por ejemplo, eastbound(T).
Construccion de cuerpo: Como en LearnOneRule loscuerpos de las reglas tienen proceso de refinamiento
Construccion de caracterısticas: Las caracterısticas deprimer orden son un conjunto de literales, que se construyenmediante refinamiento.
57 / 58
“Induccion deReglas”
Carlos ValleVidal
Introduccion
ReglasProposicionales
Evaluando lacalidad de lasreglas
Consultas y Comentarios
58 / 58