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ónlineal

Regresiónlogística

Perceptron

Bagging Boosting RandomForests

Decision Rule Trees Learning

Naïve k-NearestBayes Neighbours

Multi-Layer SVMPerceptron

K-Means EM Self-OrganizingMaps

…

…

…

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én atributos 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

MediaBaja

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

D3D14

D8

D6

D2D1

¿Cuál es el atributo másinformativo?Temperatura, Dolor garganta oTosSupongamos: Temperatura

16

ejemplo: construcción árbol de decisión (2)

D13

D12D11

D10

D9D4

D7D5

D3D14

D8 D6

D2

D1

TemperaturaMedia

BajaAlta

¿Cuáles son los atributosmá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)

MediaBaja

Alta

Temperatura

Dolor garganta

No Sí

Info[2,3] = .971 bitsInfo[4,0]= 0 bitsInfo[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]= .811Info[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/20

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 inicial se establece fijando cada dato como un clustery 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 clustersanteriores

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)