C3_M4_Aprendizaje automático, métodos y aplicaciones

Vista previa del material en texto

Aprendizaje automático: 
métodos y aplicaciones
Fernando Díaz Gómez
Depto. de Informática
E. U. de Informática ‐ UVa
contenidos
• Introducción al aprendizaje automático
• Aprendizaje inductivo
• Aprendizaje supervisado
• Aprendizaje no supervisado
2
antecedentes: sistemas expertos
• Los inicios de la Inteligencia Artificial (AI, Artificial Intelligence) se centraron 
en el desarrollo de sistemas expertos (expert systems), es decir, 
• aplicación que emula la capacidad de toma de decisiones por parte de un experto 
humano en la resolución de un problema en un dominio de aplicación específico
• El desarrollo de los sistemas expertos participaban habitualmente un 
experto (en el dominio de aplicación) y un ingeniero de conocimiento
• El ingeniero de conocimiento extrae reglas a partir de entrevistas con el experto y 
utiliza estas reglas para crear el programa (sistema) experto
• En este proceso de desarrollo, el cuello de botella es la interacción experto‐ingeniero 
de conocimiento
• Sería mucho mejor si se pudiera automatizar el proceso de ingeniería de 
conocimiento o mejor aún si se consiguiera que el sistema adquiriera la 
capacidad de aprender a ser un experto a partir de una serie de ejemplos
3
definiciones: aprendizaje automático
"Field of study that gives computers the ability to learn without being explicitly 
programmed" ( Arthur Samuel, 1959)
Dado que es imposible prever la solución de todos los problemas, se busca 
aportar a los programas la capacidad de adaptarse sin tener que ser 
reprogramados
“Any change in a System that allows it to perform better the second time on 
repetition of the same task or on another task drawn from the same 
population” (Herber Simon, 1989)
Un atributo de un agente inteligente es la capacidad de adaptación, en base a 
la experiencia adquirida, para mejorar su desempeño en tareas conocidas o 
resolver nuevos problemas similares
4
motivación: ¿por qué aprender?
• Para entender y mejorar la eficiencia del aprendizaje humano
• Para descubrir nuevos conceptos, estructuras o patrones útiles, 
previamente desconocidos: minería de datos (DM, Data Mining) o 
descubrimiento de conocimiento (KD, Knowledge discovery)
• Para posibilitar la resolución de problemas en los que el conocimiento 
acerca de su dominio es parcial o incompleto
• La mayoría de sistemas de IA que resuelven problemas reales (y por tanto, complejos 
y grandes) no pueden construirse directamente y requieren mecanismos de 
actualización dinámicos que incorporen nueva información/conocimiento
• El aprendizaje de nuevas características amplía el conocimiento acerca del dominio y 
reduce la “fragilidad” del sistema
• Para construir agentes software que puedan adaptarse a sus usuarios u 
otros agentes software
5
motivación: ¿por qué aprender?
• Como herramienta, el aprendizaje automático es útil para 
implementar:
• Tareas difíciles de programar (reconocimiento de caras, voz, ...)
• Aplicaciones auto adaptables (interfaces inteligentes, sistemas anti‐spam, 
sistemas de recomendación, ...)
• Minería de datos (análisis de datos inteligente), etc.
• … en todo tipo de dominios de aplicación:
• Búsquedas web, Biología computacional (bioinformática), Finanzas, Comercio 
electrónico, Exploración del espacio, Robótica,  Extracción de información 
Redes sociales, etc.
6
principales enfoques de aprendizaje 
automático
• Aprendizaje memorístico: se establece una correspondencia 1 a 1 entre las 
entradas y la representación almacenada, almacenamiento y recuperación 
basados en la asociación
• Aprendizaje basado en analogías: determinar la correspondencia entre 
dos representaciones diferentes
• Aprendizaje inductivo: se utilizan ejemplos específicos para alcanzar 
conclusiones (hipótesis, modelos) generales
• Algoritmos genéticos: técnicas de búsqueda evolutivas, basados en la analogía de la 
“supervivencia del mejor adaptado”
• Redes neuronales artificiales: modelos de computación y aprendizaje inspirados en 
el cerebro humano
• Aprendizaje por refuerzo: Realimentación proporcionada al final de una 
secuencia de pasos, mediante un refuerzo positivo o negativo
7
aprendizaje inductivo
• Dado un conjunto de ejemplos, son todos los métodos que tratan de 
extrapolar la información contenida en ellos para realizar predicciones lo 
más precisas posibles sobre futuros ejemplos
• Importante, la capacidad de generalización de los métodos de aprendizaje inductivo
• Aprendizaje supervisado vs. Aprendizaje no supervisado
• Aprender una función/modelo desconocido f(X) = Y, donde X es un ejemplo de 
entrada e Y es la salida deseada
• El aprendizaje supervisado implica que se nos proporcionan un conjunto de pares de 
entrenamiento (X, Y) por parte de un “profesor” (un supervisor)
• El aprendizaje no supervisado significa que sólo disponemos de los ejemplos de 
entrada X y alguna función de realimentación/evaluación de nuestro rendimiento
8
aprendizaje inductivo: métodos
Supervisados No supervisados
Lineales No Lineales
Sencillos Combinados
Interpretables Difíciles de interpretar
Regresión
lineal
Regresión
logística
Perceptron
Bagging Boosting Random
Forests
Decision Rule 
Trees Learning
Naïve k-Nearest
Bayes Neighbours
Multi-Layer SVM
Perceptron
K-Means EM Self-Organizing
Maps
…
…
…
9
aprendizaje inductivo: cuestiones asociadas
• Además de las cuestiones relacionadas con el diseño de métodos de 
aprendizaje, existen otro número de cuestiones asociadas que deben 
tratarse, como por ejemplo:
• Selección de características (FS, Feature Selection): métodos de filtrado, envolventes, 
embebidos
• Reducción de la dimensionalidad, por ejemplo, PCA (Principal Component Analysis)
• Valores perdidos, incompletos, etc. (una de las fuentes de incertidumbre)
• Aprendizaje sensible al coste (falsos positivos, falsos negativos)
• Distribuciones no balanceadas de los datos entrenamiento
• Visualización de datos (n‐dimensionales)
• Evaluación del rendimiento de los métodos de aprendizaje (metodología 
experimental)
• Incorporación de conocimiento explícito del dominio
• …
10
aprendizaje supervisado
• Dado un conjunto de ejemplos de entrada X y su correspondiente 
valor deseado Y para cada uno de ellos, se trata de establecer una 
función (modelo/hipótesis) f(), que permita predecir el valor Y* =f(X*) 
para nuevos ejemplos X*
• Si f() es una función discreta, se habla de clasificación supervisada
• En general, clasificación multiclase, y si f() sólo puede tomar dos valores (ejemplos 
positivos y negativos) se habla de clasificación biclase o aprendizaje de conceptos 
(concept learning)
• Si f() es una función continua, se habla de modelos de regresión
• Si f() es una probabilidad, se habla de estimación de distribuciones de 
probabilidad
11
clasificación supervisada
• Los datos de entrada bruto (que suelen proceder de sensores) se pre‐
procesan para obtener el vector de características (feature vector) X, que 
convenientemente describe todas las características relevantes para 
clasificar los ejemplos
• En los enfoques de aprendizaje simbólico, cada dato tiene asociado un 
significado, por ejemplo en forma de lista de pares atributo valor
• Ejemplo: X= [Persona: Juan, ColorOjos: Marrón; Edad: Joven; Sexo: Hombre] ‐> 
Variedad de representación de los dominios de los atributos: discretos vs continuos, 
etc. 
• Así, cada ejemplo disponible del conjunto de entrenamiento se puede 
interpretar como un punto en el espacio n‐dimensional del espacio de 
características (feature space) F, donde n es el número de atributos que 
describen cada ejemplo
12
clasificación supervisada como una búsqueda
• El espacio de instancias (instance space) I define el lenguaje para los ejemplos 
del conjunto de entrenamiento (training set) y de validación (test set) 
• Típicamente, pero no es así siempre (por ejemplo, SVMs) cada instancia i  I es un vector de 
características 
• Las características se denominan a veces tambiénatributos o variables
• I: V1 x V2 x … x Vk, i = (v1, v2, …, vk)
• La variable de clase C proporciona la clase de la instancia (ejemplo) que tiene que 
predecirse
• El espacio de modelos (model space) M define todos los posibles clasificadores
• M: I  C, donde M = {m1, ..., mn} es posiblemente un conjunto infinito
• El espacio de modelos a veces, pero no siempre, se define en términos de las mismas 
caracterísitcas del espacio de instancias (por ejemplo, algoritmos genéticos)
• Bajo esta perspectiva, construir el clasificador consiste en buscar una buena 
hipótesis (consistente, completo, simple) en el espacio de modelos y este proceso 
de búsqueda está dirigido por el conjunto de datos de entrenamiento 
13
clasificación supervisada como una búsqueda
• También bajo esta visión, los métodos de aprendizaje automático, en 
general, y de construcción de clasificadores, en particular, se caracterizan 
por manejar:
• Un esquema de representación de los modelos/hipótesis/soluciones que manipulan
• Árboles de decisión, reglas if‐then, instancias, modelos gráficos (redes Bayesianas, de 
Markov), redes neuronales, máquinas de vectores soporte, ensembles de clasificadores, etc.
• Una función de evaluación que permite estimar la bondad del modelo ajustado 
hasta el momento
• Precisión, sensibilidad y especificidad, error cuadrático, verosimilitud, probabilidad a 
posteriori, coste/utilidad, entropía, métricas basadas en distancia, métricas basadas en 
cantidad de información (K‐L divergence), etc.
• Un mecanismo de optimización (y posiblemente búsqueda) que dirige el proceso de 
búsqueda en el espacio de modelos
• Optimización combinatoria y optimización estocástica: metaheurísticas
• Optimización matemática: programación lineal, descenso del gradiente, etc.
14
ejemplo: árboles de decisión
Un árbol de decisión para el concepto Gripe
Temperatura
Tos Dolor garganta
Media
Baja
Alta
Sí No Sí No
Gripe No gripe
No gripe
Gripe No gripe
15
ejemplo: construcción árbol de decisión (1)
D13
D12 D11
D10 D9
D4
D7
D5
D3
D14
D8
D6
D2
D1
¿Cuál es el atributo más
informativo?
Temperatura, Dolor garganta o
Tos
Supongamos: Temperatura
16
ejemplo: construcción árbol de decisión (2)
D13
D12D11
D10
D9
D4
D7
D5
D3
D14
D8 D6
D2
D1
Temperatura
Media
Baja
Alta
¿Cuáles son los atributos
más informativos?
La respuesta nos la da la Tª de la información con los conceptos de cantidad 
de información y entropía
Tos y Dolor garganta
Supongamos:
17
ejemplo: construcción árbol de decisión (3)
Media
Baja
Alta
Temperatura
Dolor garganta
No Sí
Info[2,3] = .971 bits
Info[4,0]= 0 bits
Info[3,2]= .971 bits
Entropia = 5/14 *.971
+ 4/14 * 0 + 5/14 * .971
= .693
Previa Info[9,5] = .940
 Ganancia= .940 - .693 = .247
Info[2,6]= .811
Info[3,3]= 1
Entropía = 8/14 +.811 
+ 6/14 * 1 = .892
Previa Info[9,5] = .940
 Ganancia = .940 - .892 = .048
18
ejemplo: multi‐layer perceptron
Ejemplos MLPs:
Unidades de entrada
Unidades ocultas
Unidades de salida
pesos
19
ejemplo: modelo de cálculo de un MLP
20
• hj=g(wji.xi)
• yk=wkj.hj
donde g(x)= 1/(1+e )
x1 x2 x3 x4 x5 x6
h1 h2 h3
y1 k
j
i
wji’s
wkj’sg (sigmoid): 
0
1/2
0
1
Típicamente, y1=1 para ejemplos positivos 
e y1=0 para ejemplos negativos
-x
i
j
ejemplo: aprendizaje MLP (1)
• El aprendizaje consiste en la búsqueda a través del espacio de todas 
las posibles matrices de pesos por una combinación de pesos que 
minimicen el error cometido al clasificar los ejemplos positivos y 
negativos del conjunto de entrenamiento
• Por lo tanto es un problema de optimización que trata de minimizar la 
suma del error cuadrático:
21, ( )
2 o o
p p P P
p o
E E E t y  
21
ejemplo: aprendizaje MLP (2)
• El problema de optimización se resuelve aplicando de optimización 
clásicas, como el descenso del gradiente, que permite modificar los pesos 
de la red iterativamente en una pequeña fracción (tasa de aprendizaje) en 
la dirección opuesta al gradiente de la función de error
• Si el gradiente es 0, se alcanza un mínimo local y se dice que el 
entrenamiento de la red converge, aunque no se puede garantizar que 
converja a un mínimo global
• Capacidad de generalización, sobre entrenamiento, mal condicionamiento, 
optimización estocástica, etc.
• Problema: cómo imputar el error a cada unidad oculta cuando se 
desconoce cual es su salida esperada. Solución: algoritmo de retro‐
propragación del error
22
ejemplo: ensembles de clasificadores
• Con el fin de conseguir una respuesta más fiable de un clasificador 
automático, una buena idea sería combinar las decisiones de varios 
clasificadores base a través de un tipo de esquema de votación
• Bagging y Boosting son los dos esquemas de combinación más 
utilizados y habitualmente mejoran considerablemente los resultados 
de los clasificadores de base
• Una desventaja de estos modelos de combinación de clasificadores es 
que, como en el caso de las redes neuronales, el modelo aprendido es 
más difícil, sino imposible, de interpretar
23
ejemplo: bagging y boosting
• Bagging: Se basa en perturbar la composición de los datos del conjunto de 
aprendizaje. Con cada conjunto de datos se entrena un clasificador base y 
entonces se obtiene la respuesta final para una nueva instancia, mediante 
un esquema de votación en el que intervienen todos los clasificadores 
entrenados (por ejemplo, voto por mayoría)
• Este procedimiento reduce la porción del error en la precisión del clasificador que se 
puede imputar a la variabilidad asociada a los conjuntos de entrenamiento
• Boosting: En este caso se trata de entrenar distintos clasificadores que 
complementen a otros. Un primer clasificador se entrona, y las instancias 
sobre las que este clasificador comete errores, se les adjudica un peso 
mayor que los ejemplos clasificados correctamente. Entonces, un nuevo 
clasificador (posiblemente diferente) se entrena con los mismos datos de 
entrenamiento pero centrándose en los ejemplos con más peso, y así, 
sucesivamente
24
clustering: introducción
• Puede considerarse que el clustering es el problema del aprendizaje 
no supervisado más importante, y como cualquier otro problema de 
este tipo, trata de encontrar una estructura dentro de una colección 
de datos sin etiquetar
• Una definición más informal de clustering podría ser “el proceso de 
organizar objetos en grupos cuyos miembros son similares entre sí en 
cierto modo”. 
• Un cluster es por tanto una colección de objetos que son “similares” 
entre ellos y “diferentes” a los objetos que pertenecen a otros clusters
25
clustering: objetivos
• Determinar un agrupamiento intrínseco en un conjunto de datos sin 
etiquetar
• Pero cómo decidir qué es un buen agrupamiento
• Puede demostrarse que no existe un criterio de optimalidad absoluto, 
independiente de la aplicación final
• Por tanto, el usuario es quien debe establecer el criterio de bondad, de modo 
que el resultado del agrupamiento se ajuste a sus necesidades
• Por ejemplo, podríamos estar interesados en encontrar elementos 
representativos de grupos homogéneos (reducción de datos), en encontrar 
grupos intrínsecos y describirlos en base a sus propiedades (descubrimiento 
de tipos de datos), en encontrar datos anómalos (detección de valores 
extremos), etc.
26
clustering: tipos
• Agrupamiento exclusivo: En este caso los datos se agrupan de un modo exclusivo, de 
modo que si un dato pertenece a un cluster entonces no puede estar incluido en otro. Un 
ejemplo de este tipo de algoritmos es el algoritmo K‐Means
• Agrupamiento solapado: En este caso se utilizan conjuntos difusos para agrupar los 
datos, de forma que cada punto puede pertenecer a dos o más clusters con diferentes 
grados de pertenencia. El ejemplo más representativo de este tipo de algoritmos es el 
algoritmo Fuzzy C‐means
• Agrupamiento jerárquico: Este tipo de algoritmos se basa en la unión sucesiva de los dos 
clustersmás próximos. La condición inicialse establece fijando cada dato como un cluster
y después de cierto número de iteraciones se consigue un árbol o dendograma, donde 
cada nivel proporciona un agrupamiento de los datos. Dentro de este tipo se encuentra 
cualquier versión del algoritmo Hierarchical clustering
• Agrupamiento probabilista: En esta caso se utiliza una aproximación completamente 
probabilista para resolver el problema y el ejemplo más representativo es la mezcla de 
Gaussianas (Mixture of Gaussians)
27
ejemplo: clustering jerárquico (1)
• Dado un conjunto de N puntos y una matriz de distancia (similitudes) N * 
N, el proceso básico del clustering jerárquico (definido por Johnson en 
1967) es el siguiente:
1. Comenzar asignando cada punto a un cluster, de modo que si se tienen N 
elementos, se comienza con N clusters, cada uno de un único elemento. Sea las 
distancias (similitudes) entre los clusters, la misma que las distancias (similitudes) 
entre los puntos que contienen
2. Encontrar el par de clustersmás cercanos (más similares) y juntarlos en un único 
cluster, de modo que se tiene un clustermenos
3. Calcular las distancias (similitudes) entre el nuevo cluster y cada uno de los clusters
anteriores
4. Repetir los pasos 2 y 3 hasta que todos los puntos de datos estén agrupados en un 
único cluster de tamaño N
28
ejemplo: clustering jerárquico (2)
• El paso 3 del algoritmo anterior puede realizarse de diferentes 
formas, lo que conduce a diferentes variantes:
• Enlace sencillo (single‐linkage): En este caso se considera que la 
distancia entre un cluster y otro es igual a la distancia más pequeña, 
entre cualquier punto del primer cluster y cualquier otro del segundo
• Enlace completo (complete‐linkage): En este caso se considera la 
distancia entre dos clusters, igual a la distancia mayor entre cualquier 
punto de uno y cualquier punto del otro
• Enlace promedio (average‐linkage): La distancia entre dos clusters, 
viene dada por la distancia media entre cualquier punto del primero con 
cualquier punto del segundo
• Este tipo de agrupamiento se denomina aglomerativo ya que 
junta clusters iterativamente.
• También puede ser divisivo, comenzando con todos los puntos en un 
único cluster y desmenuzándolo iterativamente
29
ejemplo: clustering jerárquico (4)
30
ejemplo: clustering jerárquico (3)
31
Completado el árbol jerárquico (o 
dendograma), si se quieren obtener k clusters, 
basta con cortar el árbol por el nivel k‐1 desde 
la raíz (que se considera el nivel 0)