Universidad de Oviedo

Centro de Inteligencia Artificial

SISTEMAS INTELIGENTES T8: Aprendizaje basado en instancias www.aic.uniovi.es/ssii

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Índice

•  Aprendizaje basado en instancias •  Métricas •  NN Vecino más próximo: ° 

Regiones de Voronoi

° 

El parámetro K

•  Problemas de los algoritmos basados en instancias •  Técnicas de reducción de instancias Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Universidad de Oviedo

Centro de Inteligencia Artificial

Aprendizaje basado en instancias (IBL) •  Idea: en situaciones parecidas se toman decisiones similares •  Si tenemos que tomar una decisión, buscaremos en nuestra memoria el caso que más se parece a la situación actual y repetiremos la misma (acertada) acción •  Aprendizaje: la clase de un nuevo ejemplo será la misma que la del ejemplo más similar de entre los que conocemos •  Quizás es la técnica de aprendizaje más intuitiva y sencilla. Ha generado multitud de algoritmos •  Case Base Reasoning (CBR): instancias con representaciones simbólicas

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Similitud y distancia •  Un concepto recurrente en todos las técnicas de aprendizaje (supervisado y no supervisado) es el concepto de similitud •  Motivo: objetos similares tendrán clases/grupos similares •  Problema: Es difícil que dos cosas sean exactamente iguales • 

Más similar : ¿Cómo se mide la similitud?

•  La distancia es la inversa de la similitud •  Muchas técnicas basan su aprendizaje en los métodos que miden la similitud (distancia) •  Los algoritmos basados en instancias depende casi totalmente del concepto de distancia Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Métricas (I) •  Es el aspecto clave de estos sistemas •  No existe el ajuste exacto, como en las reglas o árboles •  El sistema hereda las desviaciones de su métrica °  ° 

cada métrica proporciona su sesgo de aprendizaje no existe una métrica que funcione bien en todos los problemas

•  Más empleadas: euclídea, HVDM....

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Métricas (II)

d(x,y) es una métrica si y solo si cumple: °  °  ° 

d(x,y) >= 0 d(x,y) = d(y,x) d(x,y) >= d(x,w) + d(w,y)

para todo par de ejemplos x e y

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Métricas (III) •  Atributos numéricos ° 

n

n

2

∑ (xi − yi )

Distancia Euclídea:

2

∑ wi (xi − yi )

i =1

i =1

n

° 

Distancia de Manhattan:

∑x −y i

i

i =1

° 

Distancia de Chebychev:

maxi =1.. n xi − yi

•  Atributos discretos: °  ° 

Solapamiento (atr. discretos): Si tienen el mismo valor la distancia es 0, sino 1 VDM 2

⎛ N a , x ,c N a , y ,c ⎞ ⎟ vdma (x, y ) = ∑ ⎜ − ⎜ N a , y ⎟⎠ c =1 ⎝ N a , x C

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

VDM ⎛ N a , x ,c N a , y ,c ⎞ ⎟ vdma (x, y ) = ∑ ⎜ − ⎜ N a , y ⎟⎠ c =1 ⎝ N a , x C

2

Color

Peso

Manzana

Rojo

10

NO

Verde

145

SI

Rojo

120

SI

Verde

118

SI

Naranja

130

NO

Naranja

155

NO

Verde

130

SI

Rojo

135

SI

Naranja

140

NO

⎛ N Color , Rojo, SI N Color ,Verde, SI vdmColor (Rojo, Verde ) = ⎜ − ⎜ N N Color ,Verde ⎝ Color , Rojo

2

⎞ ⎟ + ⎟ ⎠

⎛ N Color , Rojo, NO N Color ,Verde, NO ⎞ ⎜ ⎟ − ⎜ N N Color ,Verde ⎟⎠ ⎝ Color , Rojo 2

2

vdmColor (Rojo,Verde) = (0.66 − 1) + (0.33 − 0) = 0.218

2

2

vdmColor (Rojo, Naranja) = (0.66 − 0) + (0.33 − 1) = 0.871 2

2

vdmColor (Naranja,Verde) = (0 − 1) + (1 − 0) = 2

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

2

Centro de Inteligencia Artificial

Universidad de Oviedo

Algoritmo del vecino más próximo (NN) •  Algoritmo simple y efectivo •  Función de aprendizaje: almacena todos los ejemplos de entrenamiento (lazy learning) •  Difieren el trabajo hasta el momento de la clasificación •  Función de evaluación: por mínima distancia

d ( x, q ) =

2 ( ) x − q ∑ a a a∈ A

•  Ejemplos no vistos: clase del ejemplo (UNO) almacenado (vecino) más próximo •  Las regiones que se forman con 1-NN se denominan regiones de Voronoi •  Múltiples versiones variando la métrica y el número de vecinos considerados (k-NN) Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Ejemplo

Atributo 2

Atributo 1 Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Regiones de Voronoi

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

El parámetro K (I) Para clasificar un nuevo ejemplo x, observamos los K ejemplos más próximos y asignamos a x la clase más frecuente

k=1 k=6 x

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

El parámetro K (II) •  Parámetro clave •  Se suele elegir impar para deshacer los posibles empates •  Sirve para reducir la sensibilidad al ruido •  Hace un poco más lento el proceso de clasificación de nuevos casos. Para solucionarlo se pueden indexar los ejemplos •  Ejemplos: °  ° 

si k es muy bajo: sistema sensible al ruido si k es muy alto: las zonas más densas pueden acaparar las menos densas

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Problemas de los NN s (I)

1.  Almacenan demasiadas instancias °  °  °  ° 

Se incrementa el tiempo de respuesta Aumenta la sensibilidad frente al ruido Sobreajuste Soluciones ininteligibles

Solución: Técnicas de reducción de instancias °  °  ° 

Incrementales Decrementales Por lotes Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Problemas de los NN s (II)

2.  Atributos: igual importancia Solución: técnicas de selección de atributos °  ° 

Eliminación de atributos irrelevantes Ponderar la importancia de cada atributo

3.  Problemas derivados de la métrica utilizada Solución: seleccionar la métrica que mejor se adapta a cada problema Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Técnicas de reducción de instancias •  Objetivo: dado un conjunto de instancias S se busca un subconjunto R que resuelva el problema como S (o mejor) y con menos ejemplos •  El mayor o menor acierto, en determinadas situaciones, no es lo más importante •  Ventajas: °  °  ° 

Se reduce el tiempo de respuesta. Fundamental en problemas en tiempo real Menor sensibilidad al ruido Conocimiento más inteligible ¿?

•  Se pueden utilizar no sólo para producir clasificadores °  ° 

Eliminación de ruido Elección de prototipos

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Tipos de algoritmos de reducción •  Incrementales: R inicialmente vacío, y se añaden instancias de S que cumplan alguna condición °  ° 

Problema: influye el orden de presentación. Barajado Ventaja: se pueden añadir nuevas instancias después de aprender

•  Decrementales: R=S y se van eliminando aquellas instancias que verifiquen algún criterio °  ° 

Problema: Mayor coste computacional Ventaja: Consiguen mayor reducción

•  Por lotes: La decisión de eliminar/incluir una instancia depende de un lote de ejemplos. °  ° 

Problema: Tamaño de los lotes? Ventaja: No toman decisiones sin partir de una información suficiente Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

Algoritmos de reducción •  Incrementales: °  ° 

CNN: añaden los ejemplos de S mal clasificados con los que llevamos seleccionados en R IB2: igual que CNN salvo inicializaciones

•  Decrementales °  ° 

RNN: borra las instancias de R que no provocan que se clasifiquen mal otras instancias de S ENN: borra las instancias de R que no coinciden con la clase mayoritaria de sus k vecinos (RENN repetir ENN) ›  Filtro de ruido

° 

Familia DROP: Borra una instancia de R si los k más cercanos a ella pueden clasificarse correctamente sin ella

•  Lotes: ° 

SNN: demasiada complejidad

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Universidad de Oviedo

Centro de Inteligencia Artificial

RENN Repited Edited NN rule

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Universidad de Oviedo

Centro de Inteligencia Artificial

DROP 1

Sistemas Inteligentes - T8: Aprendizaje basado en instancias

Centro de Inteligencia Artificial

Universidad de Oviedo

RISE [Domingos, 96] •  Es un sistema de aprendizaje híbrido •  Combina °  ° 

reglas instancias

•  Las reglas se inducen mediante la generalización de instancias •  Una instancia puede considerarse como la regla más específica •  Para clasificar un nuevo ejemplo, aplica la regla (o instancia) que se encuentra más cerca Sistemas Inteligentes - T8: Aprendizaje basado en instancias