Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones Aprendizaje Computacional
INAOE
(INAOE) 1 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Contenido
1 Introduccion
2 Aprendizaje
3 Aprendizaje Inductivo
4 Espacio de Versiones
(INAOE) 2 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Introduccion
Objetivo General
• La capacidad de aprender es uno de los atributosdistintivos del ser humano
• El aprendizaje es una de las principales areas de IA• Generacion y almacenamiento de datos +
automatizacion procesos + avances enalmacenamiento⇒ muchos datos
• Interes comercial⇒ desarrollo acelerado
(INAOE) 3 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Introduccion
Objetivo General
• El area de aprendizaje en general trata de construirprogramas que mejoren su desempenoautomaticamente con la experiencia.
• Los objetivos del curso son:• Dar un panorama general de lo que es aprendizaje
computacional y• conocer a detalle las tecnicas mas importantes
empleadas.
(INAOE) 4 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Introduccion
Temario
1 Introduccion a aprendizaje computacional2 Tecnicas principales:
• Arboles de decision y regresion• Reglas de clasificacion• Reglas de asociacion• Clustering (k-means, mezcla de Gaussianas,
jerarquicos)• Clasificacion basada en distancia (kNN y otros)• Metodos Bayesianos• Redes neuronales• SVM (maquinas de soporte vectorial)
3 Temas relacionados:• Evaluacion de algoritmos, validacion, overfitting• LDA y PCA• Seleccion de atributos
4 Preambulo de otras tecnicas
(INAOE) 5 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Introduccion
Temas no vistos
• Algoritmos geneticos• Ensambles de clasificadores• Aprendizaje por refuerzo• Programacion Logica Inductiva• Aprendizaje semi-supervisado• Aprendizaje por transferencia• Procesos Gaussianos• Deep Learning• ...
(INAOE) 6 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Introduccion
Evaluacion
La evaluacion del curso se hara con base en:• dos examenes (2/3)• proyecto final (1/3)
(INAOE) 7 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Introduccion
Referencias
1 T. Mitchell (1997) Machine Learning, McGraw–Hill.2 I.H. Witten, E. Frank (2005) Data Mining: practical
machine learning tools and techniques 2nd. Edition.Morgan Kaufmann
3 J. Han, M. Kamber (2001) Data Mining: concepts andtechniques, Morgan Kaufmann.
4 E. Alpaydin (2010) Introduction to Machine Learning,MIT Press
5 C. Bishop (2006). Pattern Recognition and MachineLearning. Springer.
6 P. Flach (2012). Machine Learning: The art and scienceof algorithms that make sense of data, CambridgeUniversity Press.
(INAOE) 8 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Aprendizaje Computacional
• Posiblemente la caracterıstica mas distintiva de lainteligencia humana
• Desde el comienzo de las computadoras secuestiono si serıan capaces de aprender
• La capacidad de aprendizaje abre una amplia gama denuevas aplicaciones
• El entender como aprenden las maquinas nos puedeayudar a entender el aprendizaje humano
(INAOE) 9 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Aprendizaje Computacional
El aprendizaje humano es diverso e incluye:
• adquisicion de conocimiento• desarrollo de habilidades a traves de instruccion y
practica• organizacion de conocimiento• descubrimiento de hechos• ...
De la misma forma ML estudia y modelacomputacionalmente los procesos de aprendizaje en susdiversas manifestacionesSe tiene mas teorıa y mas aplicaciones lo que reflejamaduracion
(INAOE) 10 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Aprendizaje Computacional
Aprendizaje: Es el campo de estudio que le da a lascomputadoras la habilidad de aprender sin ser programadasexplıcitamente [Samuel, 59]
Aprendizaje: Cambios adaptivos en el sistema para hacer lamisma tarea(s) de la misma problacion de una manera maseficiente y efectiva la proxima vez [Simon, 83].
Aprendizaje: Un programa de computadora se dice queaprende de experiencia E con respecto a una clase detareas T y medida de desempeno D, si su desempeno enlas tareas en T , medidas con D, mejora con experiencia E[Mitchell, 97].
(INAOE) 11 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Perspectivas
Los objetivos dependen de la perspectiva:• ingenieril (resolver tareas)• simulacion cognitiva• analisis teorico
Programar una maquina lleva mucho tiempo, ML puedesuavizar ese proceso
(INAOE) 12 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Aprendizaje en Sistemas Expertos
Desde el punto de vista de sistemas basados enconocimiento...
“. . . knowledge is currently acquired in a verypainstaking way; individual computer scientistswork with individual experts to explicate theexpert’s heuristics – the problem of knowledgeacquisition is the critical bottleneck in artificialintelligence.” Feigenbaum and McCorduck
(INAOE) 13 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Aprendizaje en Sistemas Expertos
Desde el punto de vista de sistemas basados enconocimiento...
“Knowledge engineers have generally assumedthat the procedural knowledge which drives anexpert’s skilled behavior can be elicited bydialogue. The findings of the past decade in brainscience, cognitive psychology and commercialsoftware do not support this idea. Evidence islacking that skills, having once reached the“automization” stage, can be de-automized bydialogue so as to make their inner workingsaccessible to introspective report.” Donald Michie
(INAOE) 14 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tareas de Aprendizaje
• Descripcion: normalmente es usada como analisispreliminar de los datos (resumen, caracterısticas de losdatos, casos extremos, etc.). Con esto, el usuario sesensibiliza con los datos y su estructuraBusca derivar descripciones concisas de caracterısticasde los datos (e.g., medias, desviaciones estandares,etc.).
(INAOE) 15 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tareas de Aprendizaje
• Prediccion: Clasificacion y Estimacion.• Clasificacion: Los datos son objetos caracterizados
por atributos que pertenecen a diferentes clases(etiquetas discretas).La meta es inducir un modelo para poder predecir unaclase dados los valores de los atributos.Se usan por ejemplo, arboles de decision, reglas, SVM,etc.
(INAOE) 16 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tareas de Aprendizaje
• Prediccion: Clasificacion y Estimacion.• Estimacion o Regresion: las clases son continuas.
La meta es inducir un modelo para poder predecir elvalor de la clase dados los valores de los atributos.Se usan por ejemplo, arboles de regresion, regresionlineal, redes neuronales, LWR, etc.
(INAOE) 17 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tareas de Aprendizaje
• Segmentacion: separacion de los datos en subgruposo clases interesantes.Las clases pueden ser exhaustivas y mutuamenteexclusivas o jerarquicas y con traslapes.Se puede utilizar con un clasificadorSe usan algoritmos de clustering, SOM(self-organization maps), EM (expectationmaximization), k−means, etc.Normalmente el usuario tiene una buena capacidad deformar las clases
(INAOE) 18 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tareas de Aprendizaje
• Analisis de dependencias: El valor de un elementopuede usarse para predecir el valor de otro. Ladependencia puede ser probabilıstica, puede definiruna red de dependencias o puede ser funcional (leyesfısicas).Tambien se ha enfocado a encontrar si existe una altaproporcion de valores de algunos atributos que ocurrencon cierta medida de confianza junto con valores deotros atributos.Se pueden utilizar redes Bayesianas, redes causales, yreglas de asociacion.
(INAOE) 19 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tareas de Aprendizaje
• Deteccion de desviaciones, casos extremos oanomalias: Detectar los cambios mas significativos enlos datos con respecto a valores pasados o normales.Sirve para filtrar grandes volumenes de datos que sonmenos probables de ser interesantes. El problemaesta en determinar cuando una desviacion essignificativa para ser de interes.
(INAOE) 20 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tareas de Aprendizaje
• Aprendizaje de la mejor accion a tomar a partir deexperiencia: Esto involucra busqueda y exploracion delambiente. Esto esta relacionado principalmente conaprendizaje por refuerzo, pero tambien con tecnicascomo aprendizaje de macro-operadores, chunking yEBL.
(INAOE) 21 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tareas de Aprendizaje
• Optimizacion y busqueda: Existen una gran cantidadde algoritmos de busqueda tanto determinıstica comoaleatoria, individual como poblacional, local comoglobal, que se utilizan principalmente para resolveralgun problema de optimizacion. Aquı podemos incluira los algoritmos geneticos, recocido simulado,ant-colony, tecnicas de busqueda local, enjambres, etc.
(INAOE) 22 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tecnicas Comunes
• Arboles de decision y reglas de clasificacion: realizancortes sobre una variable (lo cual limita su expresividad,pero facilita su comprension). Generalmente se usantecnicas heurısticas en su construccion (e.g., ID3, C4.5,CN2). Ver figura.
(INAOE) 23 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tecnicas Comunes
DV_T
NO2_F
SO2_L O3_L
RH_F
TMP_F
O3_Q
NO2_X DV_X
DV_F
DV_L
NO2_T
TMP_L
O3_X
SO2_F
RH_Q
NOX_X
RH_L
O3_Q
DV_T
VV_Q
HORA
VV_T
NO2_T
RH_QNOX_X
RH_L DV_X
C2
C4
C6
C8
C11 C13
C1
C3
C5
C7
C10
C12
C5
C4
C7 C4
C5 C10C1
C11
C7 C3
C3
C7C2
C6 C6 C2 C3
120
57
4946
72
39 89
11
32
39
219484 286
4587
291219
168
227
2310
346
43423
231
43
77
162
Figura: Prediccion de Ozono en la Ciudad de Mexico.(INAOE) 24 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tecnicas Comunes• Metodos de clasificacion y regresiones no–lineales:
tratan de ajustar combinaciones de funciones lineales yno–lineales, por ejemplo, redes neuronales (e.g.,backpropagation), metodos de splines adaptativos, etc.
Entradas Salidas
Figura: Red Neuronal prototıpica.
(INAOE) 25 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tecnicas Comunes• Metodos basados en ejemplos prototıpicos: se hacen
aproximaciones con base en los ejemplos o casos masconocidos (Examplar–based learning y Case–basedresoning). El problema es como determinar una medidade similaridad adecuada.
Figura: Aprendizaje basado en instancias.
(INAOE) 26 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tecnicas Comunes
• Modelos graficos de dependencias probabilısticas:basicamente se utilizan redes bayesianas, en dondedado un modelo estructural y probabilıstico, seencuentran los valores de ciertas variables dadosvalores de otras variables. Ver figura.
(INAOE) 27 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tecnicas Comunes
edad
buenestudian.
nivel socio- econo.
autoextra
anoauto
kilome.
seguri.experien.
habilid. manejo
histor.manejo
marca
ABS
bolsas aire
calidadmanejo
condic.camino
accident
valor comerc.
antirobo
lugarhogar
robo
costocochepropio
costopropied.
costootrosautos
costopersonal costo
medico
defensas
danospersona.
Figura: Red Bayesiana de seguros de coches.
(INAOE) 28 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tecnicas Comunes• Modelos relacionales: Programacion logica inductiva (o
ILP), en donde la busqueda del modelo se basa enlogica y heurısitcas.
nitrofurazone 4-nitropenta[cd]pyrene
6-nitro-7,8,9,10-tetrahydrobenzo[a]pyrene 4-nitroindole
ACTIVO
INACTIVO
O = N CH = N - NH - C - NH
OO
+
-
N = O
O
+
-
N
OO
+
- N H
N
OO+
-
U
V Y = Z
XW
Figura: Prediccion de mutagenesis.
(INAOE) 29 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tecnicas Comunes
• Reglas de Asociacion: reglas que relacionan unconjunto de pares atributo-valor con otros paresatributo-valor. Por ejemplo:
edad(X ,20 . . . 29) ∧ ingresos(X ,20K . . . 29K )⇒ compra(X,CD)[soporte = 2 %,confianza = 60 %]
(INAOE) 30 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Tecnicas Comunes• Clustering: agrupan datos cuya distancia
multidimensional dentro de la clase es pequena y entreclases es grande.
x
x
x
xx
x
Figura: Ejemplo de Clustering.
(INAOE) 31 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Ejemplos
Algunos ejemplos de aplicaciones que usan aprendizaje:• Sistemas de reconocimiento de voz (e.g., SPHINX, Lee
89),• Manejo de vehıculos autonomos (ALVINN, Pomerleau
89)• Clasificacion de nuevas estructuras de astronomıa
(SkyCat, Fayyad et al. 95)• Aprendiendo a jugar Backgammon (TD-Gammon,
Tesauro 92)• Muchas aplicaciones de las que no estamos
conscientes (sistema postal, tarjetas de credito,recomendaciones de Amazon, sistemas de seguridad,uso de combustible en coches, ...)
(INAOE) 32 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Ejemplos RecientesAlgunos ejemplos mas recientes:• Control en robots autonomos• Control en vehıculos autonomos
• Identificacion de edificios famosos (google googles)• Agrupacion de imagenes parecidas (ImageSwirl) y
etiquetado automatico
• Aprender caras y gatos usando 16,000 procesadores,red neuronal con mas de mil millones de conecciones yusando 10 millones de imagenes.
(INAOE) 33 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Aplicaciones
Existe una gran cantidad de aplicaciones tales como:• astronomıa• biologıa molecular• aspectos climatologicos• medicina• industria y manufactura• mercadotecnia• inversion en casas de bolsa y banca• deteccion de fraudes y comportamientos inusuales• analisis de canastas de mercado• aprendizaje de tareas en robotica• ...
(INAOE) 34 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Areas Relacionadas
• Inteligencia Artificial• Metodos Bayesianos• Teorıa de complejidad computacional• Teorıa de control• Teorıa de informacion• Filosofıa• Psicologıa y neurobiologıa• Estadıstica
(INAOE) 35 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Consideraciones
Algunos puntos que aclarar cuando se quiere correr odesarrollar algun algoritmo de aprendizaje son:• Que algoritmos existen para resolver cierta tarea?
cuando y como usarlos? que propiedades tienen?• Cuantos datos o tiempo de entrenamiento necesito?
que tanta confianza puedo tener en los resultados?• Como y cuando usar conocimiento del dominio?• ...
Se espera que algunas de estas preguntas las puedanresolver al final del curso.
(INAOE) 36 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje
Retos
• Volumen de datos (mega, giga y hasta terabytes)• Alta dimensionalidad y/o pocos datos• Sobreajuste (overfitting)• Datos y conocimiento dinamicos• Ruido, incertidumbre y datos incompletos y/o esparsos• Relaciones complejas entre campos, jerarquıas, etc.• Interpretacion de los resultados• Incorporacion de conocimiento del dominio• Interaccion activa del usuario• Integracion con otros sistemas
(INAOE) 37 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje Inductivo
El aprendizaje inductivo puede verse como el proceso deaprender una funcion.Por ejemplo, en aprendizaje supervisado, al elemento deaprendizaje se le da un valor correcto (o aproximadamentecorrecto) de una funcion a aprender para entradasparticulares y cambia la representacion de la funcion queesta infiriendo, para tratar de aparear la informacion dadapor la retroalimentacion que ofrecen los ejemplos.
(INAOE) 38 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
• Un ejemplo es un par (x, f (x)), donde x es la entrada(que generalmente es un vector) y f (x) la salida.
• El proceso de inferencia inductiva pura (o induccion) es:dada una coleccion de ejemplos de f , regresar unafuncion h tal que se aproxime a f . A la funcion h se lellama la hipotesis.
• En principio existen muchas posibilidades para escogerh, cualquier preferencia se llama bias o sesgo. Todoslos algoritmos de aprendizaje exhiben algun tipo desesgo.
• La seleccion de una representacion para la funciondeseada es probablemente el factor mas importante enel diseno de un sistema de aprendizaje.
(INAOE) 39 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
• Desde un punto de vista mas tradicional (hablando derepresentaciones simbolicas/reglas,...), podemos decirque una buena parte de ML esta dedicada a inferirreglas a partir de ejemplos.
• Descripciones generales de clases de objetos,obtenidas a partir de un conjunto de ejemplos, puedenser usadas para clasificar o predecir.
• En general, el interes no esta en aprender conceptosde la forma en que lo hacen los humanos, sinoaprender representaciones simbolicas de ellos.
(INAOE) 40 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
Angluin y Smith listan cinco elementos que deben deespecificarse para caracterizar un problema de inferenciainductiva:
1 La clase de reglas2 El espacio de hipotesis3 El conjunto de ejemplos y su presentacion4 La clase del metodo de inferencia5 El criterio de exito
(INAOE) 41 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
La clase de reglas:La clase de reglas denota la clase de funciones o lenguajebajo consideracion. Por ejemplo, todas las expresionesregulares sobre un alfabeto especıfico, lenguajes libres decontexto, funciones recursivamente enumerables,programas en Prolog, etc.
(INAOE) 42 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
El espacio de hipotesis:El espacio de hipotesis es el conjunto de descripciones talque cada regla en la clase tiene por lo menos unadescripcion en el espacio de hipotesis. Diferentes espaciosde hipotesis pueden usarse para la misma clase de reglas.
El lenguaje de hipotesis debe de tener descripciones paratodas las reglas en la clase, pero puede contener mas.
Por conveniencia, normalmente se asume que el lenguajedescrito por el espacio de hipotesis (i.e., el lenguaje dehipotesis) es el mismo que el de la clase de reglas:
(INAOE) 43 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
• Lenguaje de Hipotesis: sintaxis usada en laconstruccion de hipotesis
• Espacio de Hipotesis: conjunto de todas las posibleshipotesis dentro del lenguaje de hipotesis
El lenguaje de hipotesis determina el espacio de hipotesisdel cual el metodo selecciona sus reglas e imponerestricciones/preferencias en lo que se puede aprender yque estrategias de razonamiento utilizar
Al escoger un lenguaje, debemos de considerar lo quequeremos que el sistema realice, la informacion que se ledebe de proporcionar y si lo va a resolver a tiempo
Existe, como en los metodos de inferencia de KR, unbalance fundamental entre la expresividad y la eficiencia
(INAOE) 44 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Espacio de Hipotesis
X Y
XY
X Y
XY XY XY
f(X).f(a).
f(X) :- g(Y). f(X) :- h(Y).
f(a) :- g(b), h(c).
f(b).f(c).
f(a) :- g(X). f(c) :- h(c).
Figura: El espacio de hipotesis depende de la expresividad dellenguaje.
(INAOE) 45 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Espacio de Hipotesis
x
f(x)f(x) = mx + b
f(x) = ax + bx + c2
f(x) = ax + bx + cx + d23
Figura: Que tan bien se ajusta el modelo depende de laexpresividad del lenguaje.
(INAOE) 46 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
• El lenguaje de hipotesis depende del area deaplicacion. Una vez definido, una buena parte deltiempo se dedica a seleccionar cuidadosamente lasestructuras de conocimiento adecuadas para la tareade aprendizaje.
• Este tiempo se vuelve mas crıtico cuando el lenguaje dehipotesis restringe la expresividad y el conocimiento deldominio tiene que adaptarse al formalismo adoptado.
• El proceso de inducion puede verse como unabusqueda de hipotesis o reglas.
(INAOE) 47 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje como Busqueda
• El espacio puede buscarse sistematicamente, hastaencontrar la regla adecuada.
• Podemos tener una enumeracion de descripciones,digamos d1, . . . ,dn, tal que cada regla en el espacio dehipotesis tiene una o mas descripciones en estaenumeracion.
• Dada una coleccion de ejemplos, identificacion en ellımite recorre esta lista encontrando la primeradescripcion, digamos di , que es compatible con losejemplos vistos y conjetura a di .
• Sin embargo es impractico a menos que se tenga unnumero limitado de descripciones
(INAOE) 48 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje como Busqueda
• Normalmente es crucial estructurar el espacio dehipotesis. Esto se puede hacer con un modelo degeneralizacion.
• A grandes razgos una regla R1 es mas general que otraregla R2 (o R2 es mas especıfica que R1), si encualquier mundo R1 puede mostrar los mismosresultados que R2.
• Una estructuracion permite cortar ramas durante labusqueda sabiendo que especializaciones ogeneralizaciones de reglas hereden alguna propiedad.
• Las propiedades mas comunes son: incapacidad decubrir un ejemplo conocido como verdadero o probarun ejemplo conocido como falso.
(INAOE) 49 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
Conjunto de ejemplos y su presentacion:Existen diferentes tipos de presentacion de datos y susefectos en el proceso de inferencia
Los ejemplos pueden dar una retroalimentacion directa oindirecta. Por ejemplo, al aprender a jugar un cierto juego, laretroalimentacion se puede dar en cada jugada o al final deljuego o despues de un conjunto de jugadas que provocaronuna perdida de material, etc. Aquı, surge el problema deasignacion de credito (cual jugada es responsable del exitoo fracaso).
Una presentacion puede consistir en: (i) solo ejemplospositivos y (ii) positivos y negativos.
(INAOE) 50 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
• Casi todos los algoritmos requieren presentacionesadmisibles (para cada regla falsa consistente con losejemplos existe un ejemplo negativo que la refuta)Popper: Las teorıas deben de ser refutables con hechos
• Los ejemplos se usan para probar y formar hipotesis(sobre un espacio de ejemplos)
• La seleccion puede ser por un oraculo, el medioambiente, en forma aleatoria o por el sistema y se tieneque tener un balance entre exploracion y explotacion
• Una “buena” seleccion (posiblemente con conocimientodel dominio) de ejemplos puede mejorar el desempenode un sistema (ver Active Learning)
• Se asume que la distribucion que siguen los ejemploses similar a la de ejemplos futuros.
(INAOE) 51 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
Metodos de inferencia:Intuitivamente un metodo de inferencia es un procesocomputacional de algun tipo que lee ejemplos y producehipotesis del espacio de hipotesis.
Existe una gran cantidad de metodos: Algunos realizanajustes graduales en base a refuerzos sobre prediccionessucesivas (e.g., RL, NN, etc.). Otros construyenincrementalmente hipotesis tratando de cubrir la mayorparte de un conjunto de ejemplos (e.g., reglas declasificacion, ILP) o en base a mejores particiones deejemplos (e.g., TDIDT). Otros, guardan ejemplosprototıpicos (e.g., CBR, IBL). Algunos buscan relacionesentre variables (e.g., BN). Finalmente, algunos algoritmoscombinan o modifican hipotesis promisorias (e.g., GA).
(INAOE) 52 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
Criterio de exito:Un componente importante dentro de la especificacion deun problema de inferencia es el criterio de exito.Identificacion en el lımite es uno de ellos.
Recientemente Valiant, propuso un criterio de identificacioncorrecta de una regla a partir de ejemplos usando un criterioestocastico.
La idea es que despues de un muestreo aleatorio deejemplos positivos y negativos de una regla, unprocedimiento de identificacion debe de producir una reglaque con “alta probabilidad” no sea “muy diferente” de laregla correcta (PAC)
(INAOE) 53 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
PAC Learning
Se basa en dos parametros: ε y δ. ε es una medida detolerancia o un lımite de la diferencia permitida entre la reglacorrecta y la hipotesis generada. δ es una medida deconfianza.
Informalmente, un procedimiento de identificacion se diceser probablemente aproximadamente correcto o PAC si ladiferencia entre la regla correcta y la hipotesis es menosque ε con probabilidad mayor a 1− δ.
(INAOE) 54 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Aprendizaje
En la practica queremos ciertas garantias de la calidad de lahipotesis. Las mas comunes son que sea completo yconsistente (ver figura):
• Una hipotesis es completa si cubre todos los ejemplospositivos
• Una hipotesis es consistente si no cubre a ninguno delos ejemplos negativos
A veces el usuario determina el criterio de paro. Si elsistema genera sus propios ejemplos, este lo determina.
(INAOE) 55 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Aprendizaje Inductivo
Completo y Consistente
x x
xxx
x
Completo y Consistente
x x
xxx
x
Completo e Inconsistente
x x
xxx
x
Inompleto y Consistente
x x
xxx
x
Incompleto e Inconsistente
H H
H H
Figura: Completo y Consistente (X positivos y O negativos).(INAOE) 56 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Aprendizaje
• Desde el punto de vista de logica tratamos de encontraruna expresion logica de un predicado meta (M) y quenos sirva para clasificar ejemplos correctamente.
• Cada hipotesis propone una expresion, y la llamaremosla definicion candidata del predicado meta.
• Como lo mencionamos antes, el espacio de hipotesis Hes el conjunto de todas las hipotesis {H1,H2, . . . ,Hn},que el algoritmo de aprendizaje esta disenado aproducir.
(INAOE) 57 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Aprendizaje
• Cada hipotesis predice que un cierto conjunto deejemplos (aquellos que satisfacen su definicioncandidata) son ejemplos del predicado meta. A estosejemplos tambien se les llama la extension delpredicado.
• En este sentido dos hipotesis son logicamenteequivalentes si tienen la misma extension.
• Los ejemplos son objetos para los cuales el predicadometa puede o no satisfacerse.
• Una hipotesis es consistente logicamente con losejemplos si se cumple o no dependiendo si el ejemploes positivo o negativo.
(INAOE) 58 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Aprendizaje
Las condiciones por las cuales una hipotesis puede serinconsistente con algun ejemplo son:
• Un ejemplo es un negativo falso para la hipotesis (i.e.,la hipotesis dice que debe de ser negativo y en realidades positivo)
• Un ejemplo es un positivo falso para la hipotesis (i.e., lahipotesis dice que debe de ser positivo y en realidad esnegativo)
Si asumimos que el ejemplo es una observacion correcta,un falso positivo o negativo implica que la hipotesis tieneque ser rechazada.
(INAOE) 59 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
AprendizajeDesde un esquema de logica, podemos caracterizar elaprendizaje inductivo eliminando gradualmente hipotesisque sean inconsistentes con los ejemplos (ver figura).
Ejemplo: 4 Espadas (+)
Ejemplo: 7 Espadas (+)
Ejemplo: 5 Corazones (-)
? ?
Num ? ? Num
4 ? Num Negro ? Espadas
4 Negro Num Espadas
4 Espadas? ?
Num ? ? Num
Num Negro ? Espadas
Num Espadas
? Num
Num Negro ? Espadas
Num EspadasEjemplo: 3 Treboles (+)
? Num
Num Negro
Ejemplo: Reina Treboles (-)
Num Negro
Figura: Proceso de eliminacion de hipotesis.
Sin embargo, el espacio es muy grande (e incluso infinito enmuchos casos) haciendo su implantacion directa impractica(sino imposible).
(INAOE) 60 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Busqueda de la mejor hipotesis actual
• La idea es mantener una sola hipotesis, e irla ajustandoconforme nuevos ejemplos se consideran, manteniendoconsistencia.
• El algoritmo basico puede encontrarse descrito desde1943 (John Stuart Mill).
• Si tenemos una hipotesis Hr y recibimos un negativofalso, entonces la extension de la hipotesis debeaumentarse para incluirlo. A esto se le llamageneralizacion.
• Si tenemos un positivo falso, entonces la extension dela hipotesis debe reducirse para excluirlo. A esto se lellama especializacion.
(INAOE) 61 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Aprendizajex x
x
x
xx
x
x x
x
x
xx
x
x x
x
x
xx
xx
Especializar Generalizar
Figura: Proceso de especializar y generalizar.
(INAOE) 62 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Aprendizaje
• Definimos generalizacion y especializacion comooperaciones que cambian la extension de una hipotesis
• Intuitivamente H1 es mas general que H2 si la “cubre”• Sintacticamente, una posible forma de generalizar es
eliminando condiciones volviendo las definiciones masdebiles y por lo tanto cubriendo un conjunto mayor deejemplos o anadiendo disjunciones
• De forma dual, podemos especializar anadiendocondiciones o eliminando disjunciones.
(INAOE) 63 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Algoritmo de Mejor Hipotesis Actual
funcion mejor-hipotesis-actual(ejemplos)regresa una hipotesis
H ← cualquier hipotesis consistente con el primer ejemploen ejemplos
para cada uno de los ejemplos restantes hacersi e es positivo falso para H entonces
H ← selecciona una especializacion de H consistentecon ejemplos
sino si e es negativo falso para H entoncesH ← selecciona una generalizacion de H consistente
con ejemplossi no se puede construir una especializacion /
generalizacion consistente entonces fallaregresa H
(INAOE) 64 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Algoritmo de Mejor Hipotesis ActualEl algoritmo sigue basicamente una busqueda enprofundidad. Podemos empezar con una generalizacion ocon una especializacion consistente con los ejemplosEstas ideas se han usado en varios sistemas deaprendizaje, sin embargo, tiene algunos problemas:
1 Verificar todas las instancias anteriores cada vez quese hace una modificacion
2 Es difıcil encontrar buenas heurısticas de busqueda y elhacer backtracking puede volverse “eterno” (se tomandecisiones locales sin suficiente informacion)
Alternativamente, podemos buscar a lo ancho (i.e.,mantener varias hipotesis a la vez). Si lo hacemos deespecıfico a general, podemos tratar de mantener todas lasgeneralizaciones mas especıficas que sean consistentescon las observaciones (o hacerlo de general a especıfico)
(INAOE) 65 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Algoritmo Especıfico a General BFS
H ← el conjunto de generalizaciones mas especıficasconsistentes con los ejemplos vistos en ejemplos
para cada uno de los ejemplos restantes hacersi e es positivo falso para alguna hipotesis en Hentonces H ← las hipotesis que no son
consistentes con el ejemplosino si e es negativo falso para alguna hipotesis en Hentonces H ← generaliza miembros de H, pero
solo al punto de aceptar el ejemploElimina de H cualquier elemento que sea
(i) mas general que otro elemento o(ii) aparea otros negativos
si no se puede construir una generalizacion consistenteentonces falla
regresa H
(INAOE) 66 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Aprendizaje
• Los ejemplos positivos fuerzan las generalizaciones ylos negativos eliminan generalizaciones. Sigue unproceso monotonico de especıfico a general.
• Sin embargo, cada vez que generalizamos, seguimosteniendo que verificar consistencia con todos losejemplos positivos.
• Una alternativa es mantener todas y solo aquellashipotesis que son consistentes con todos los datos.
(INAOE) 67 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Busqueda con el menor compromiso
• Con cada instancia nueva, o no se hace nada, o seeliminan algunas hipotesis.
• Asumiendo que el espacio de hipotesis inicial tiene unarespuesta correcta, la disjuncion de hipotesis reducida,va a seguir teniendola. Al conjunto de hipotesisconsistentes con los ejemplos se le llama espacio deversiones (version space).
• Una propiedad importante del algoritmo es que esincremental (nunca se tiene que regresar paraexaminar ejemplos viejos).
(INAOE) 68 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Busqueda con el menor compromiso
• Problema obvio: si el espacio es gigantesco, comopodemos escribir la disjuncion completa de hipotesis.
• El punto es que no la tenemos que escribir! Se puedehacer una analogıa con numeros reales. Si queremosrepresentar todos los numeros entre 1 y 2⇒ [1,2].
• Esto lo podemos hacer porque existe un ordenamiento.• La generalizacion / especializacion tambien nos da un
orden, en este caso un orden parcial
(INAOE) 69 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
AprendizajeMuy general
Muy especifico
masespecifico
masgeneral
Figura: Orden parcial entre hipotesis.
(INAOE) 70 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Aprendizaje
En este caso, las fronteras no son puntuales, sino conjuntosde hipotesis o conjuntos frontera (boundary sets).Lo bueno es que podemos representar todo el espacio deversiones usando solo 2 conjuntos de frontera:
• la frontera mas general (el conjunto G)• la frontera mas especıfica (el conjunto S)
Todo lo que esta entre S y G esta garantizado a serconsistente con los ejemplos (el tamano de S y G dependedel lenguaje).
(INAOE) 71 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Espacio de Versiones
Resumiendo:• el espacio de versiones actual es el conjunto de
hipotesis consistente con todos los ejemplos vistos• cada elemento del conjunto S es consistente con todas
las observaciones hasta el momento y no existenhipotesis consistentes que sean mas especıficas
• cada elemento del conjunto G es consistente con todaslas observaciones hasta el momento y no existenhipotesis consistentes que sean mas generales
(INAOE) 72 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Espacio de Versiones
El espacio de versiones inicial tiene que representar a todaslas hipotesis. Esto se puede lograr haciendo G = True(contiene todo) y S = False (su extension es vacıa).
Se tienen que cumplir dos propiedades:• Toda hipotesis consistente esta entre S y G• Toda hipotesis entre S y G es consistente
Lo unico que queda es como actualizar S y G. Si Si es unade las hipotesis en S y Gi una en G
(INAOE) 73 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Espacio de Versiones
generalizar
especializar
e+
eH cubre
H no cubre
Figura: Actualizacion en el espacio de versiones
(INAOE) 74 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Espacio de Versiones
1 Positivo falso para Si : Si es muy general, pero pordefinicion no existe una especializacion de Siconsistente, por lo que la eliminamos
2 Negativo falso para Si : Si es muy especıfico y tenemosque substituirlo por su generalizacion inmediata
3 Positivo falso para Gi : Gi es muy general y tenemosque substituirlo por su especializacion inmediata
4 Negativo falso para Gi : Gi es muy especıfico, pero pordefinicion no existe una generalizacion de Giconsistente, por lo que la eliminamos
(INAOE) 75 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Espacio de Versiones
Continuamos con estas operaciones hasta que:1 En el espacio de versiones queda una sola hipotesis2 El espacio de versiones se colapsa (S y G se vuelven
vacıas), por lo que no hay una hipotesis consistentecon los ejemplos
3 Se acabaron los ejemplos y tenemos varias hipotesisen el espacio de versiones, i.e., una disjuncion dehipotesis (con un nuevo ejemplo, si todas las hipotesisestan de acuerdo, clasificamos el ejemplo, sino,podemos tomar un voto mayoritario)
(INAOE) 76 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Algoritmo de Espacio de Versiones
Inicializa los conjuntos S y G con Falso y VerdaderoPara cada ejemplo ei subsecuente
si e es negativo entonces• Manten en S solo las hipotesis que no cubren a ei• Especializa en G aquellas hipotesis que
cubran a ei , pero solo al punto para nocubrirlo y que sigan siendo las mas generales
• Elimina de G cualquier elemento mas especıficosino si ei es positivo entonces• Manten en G solo las hipotesis que cubren a ei• Generaliza en S aquellas hipotesis
que no cubran a ei , pero solo al punto paracubrirlo y que sigan siendo las mas especıficas
• Elimina de S cualquier elemento mas general
(INAOE) 77 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Espacio de Versiones
Ventajas:• Detecta cuando acaba (cuando los ejemplos son
suficientes)• Cuando hay solo algunos ejemplos, sigue dando
resultados
(INAOE) 78 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Espacio de Versiones
Problemas:1 Asume que podemos calcular la relacion
mas-general-que2 Si el dominio tiene ruido o insuficientes atributos para
una clasificacion exacta, el espacio de versiones secolapsa
3 Si permitimos una disjuncion ilimitada en el espacio dehipotesis, el conjunto S va a tener una disjuncion de losejemplos positivos y G va a tener la negacion de ladisjuncion de los ejemplos negativos
(INAOE) 79 / 80
Introduccion
Aprendizaje
AprendizajeInductivo
Espacio deVersiones
Espacio de Versiones
Espacio de Versiones
• Para el manejo de ruido no existe una solucion general(pero vamos a ver varias).
• Para el caso de disjunciones ilimitadas, podemos usaruna jerarquıa de generalizaciones.
• El algoritmo en Meta-Dendral y en LEX• Puede servir para generar automaticamente ejemplos
que dividan el espacio de busqueda.• Unos anos depues, se desarrollo una generalizacion del
algoritmo que permite manejar ruido, valores faltantes eincorporar conocimiento del dominio usando conjuntosde fronteras que permiten cierta cantidad de ruido ymetodos para fusionar elementos de las fronteras.
(INAOE) 80 / 80