Download Diapositiva 1

Aprendizaje Automático
Andrea Mesa
21 de mayo de 2010
Aprendizaje automático
Otras denominaciones: machine learning,
statistical learning, data mining, inteligencia
artificial.
Las técnicas de Aprendizaje Automático pueden
utilizarse cuando se quiere modelar un fenómeno
en cualquier área de la ciencia.
Problemas frecuentes en modelización
• interacciones complejas entre las variables de
interés
• datos faltantes
• observaciones dependientes
• tamaño de las muestras y número de variables
Ventajas del Aprendizaje Automático
• predicciones cuantitativas eficientes
• comprensión cualitativa del fenómeno a modelar
y eventualmente su causalidad
• dependiendo de los objetivos que se planteen se
priorizará la exactitud de la predicción o la
comprensión de los patrones subyacentes
• se puede trabajar con comodidad, aun cuando el
número de datos y/o de variables sea grande
Aprendizaje automático
Se divide en:
• Aprendizaje supervisado: regresión, clasificación
• Aprendizaje no supervisado: clustering
Aprendizaje supervisado
Objetivo
aprender a predecir el output Y dado el input X,
mediante la construcción de una función f que
llamamos predictor.
Variables
• X: variable independiente, explicativa, de entrada, input
• Y: variable dependiente, de salida, output
• reales o multidimensionales
• continuas, categóricas, binarias, etc.
• si Y es continua: problema de regresión
• si Y es discreta o categórica: problema de clasificación
• datos: (X1,Y1),….(Xn,Yn) donde cada Xi puede ser un vector
de observaciones
Esquema de ML
Datos
Datos
Elección del
Muestra de
entrenamiento
algoritmo
Muestra de validación
Datos Frescos
(X1,Y1),….(Xn,Yn)
Modificación o no
del los parámetros del
algoritmo
Salida Y
Ejemplo 1
Contaminación ambiental
• Variables de entrada X: vector de variables
ambientales en el día n (temperatura, nivel de ozono,
presión atmosférica, vientos, etc.)
• Variable de salida Y: nivel de contaminación ambiental
en el día n+1
El ejemplo corresponde a un problema de regresión, pero si se
considera la variable de salida Y dividida en categorías el
problema es de clasificación.
Ejemplo 2
Selección de hábitat de Antilorca americana
• Variables de entrada X : abundancia de alimento,
características del terreno (altitud, pendiente), distancia al
agua, etc.
• Variable de salida Y: presencia/ausencia de Antilorca
americana
El output Y es una variable binaria, esto es toma sólo los valores
0,1, por lo que el ejemplo es de clasificación.
Predictor
Buscamos una función (predictor) que minimice el riesgo
de predecir mal, para ello se define una función de pérdida,
L(X, f(X), Y), y se busca f**, entre todas las funciones de
una cierta clase C, que haga mínimo el valor esperado de L
(que llamamos riesgo).
Riesgo:
Predictor
En la práctica este predictor se basa en la
muestra de entrenamiento y se construye como
aquella función que minimiza el riesgo empírico.
Performance del predictor
• Para evitar el sobreajuste (overfitting), se evalúa la
performance del predictor con una nueva muestra llamada
muestra de evaluación o de testeo, independiente de la
muestra de entrenamiento.
• Otras formas de evaluar el predictor: validación cruzada,
bootstrap.
Errores
Llamamos
f*
al mejor entre todos los predictores posibles
f**
al mejor de los predictores posibles en la clase de
funciones C
f
al predictor que usamos en la práctica (esto es: el que
minimiza el riesgo empírico)
Errores
Error de modelización: f* - f**
depende de la elección de la clase C, si consideramos C
como la familia de todas las funciones posibles, tendremos
overfitting.
Error de estimación: f** - f
es un error estadístico, si el tamaño n de la muestra es
grande, bajo ciertas hipótesis sobre la clase C, se cumple
que f converge a f**
Se debe lograr un compromiso entre ambos errores, de forma tal
que el error total sea el menor posible
Errores
Teorema fundamental del Learning
El Teorema fundamental del Learning establece que, bajo
ciertas condiciones sobre la clase de funciones C, f
converge a f**.
Estas condiciones están relacionadas con la dimensión de
Vapnik-Chervonenkis (VC) de C. La dimensión VC mide
“cuan grande” es una clase infinita de funciones, así si C no
es demasiado grande, esto es la dimensión VC es finita, se
está en las hipótesis del Teorema fundamental del
Learning.
Problemas clásicos de la estadística
• Regresión
• Reconocimiento de patrones
• Estimación de densidades
Regresión
Si la función de pérdida es la cuadrática
La función solución es la función de regresión
Así el problema de regresión puede verse como un
problema de minimización del riesgo.
Reconocimiento de patrones
Si la función de pérdida es la indicatriz
Minimizar la probabilidad de clasificar mal equivale a
minimizar el riesgo.
Estimación de densidades
Si la función de pérdida es
Usando varios resultados y haciendo algunas operaciones, el
problema de estimar la densidad g puede verse como un
problema de minimización del riesgo.
Algunos métodos de aprendizaje
automático
• Generalized Additive Models, GAM
• Support Vector Machine, SVM
• Classification and Regression Trees, CART
GAM
Generalized additive models
Hastie & Tibshirani, 1986
GAM
Los modelos aditivos generalizados, GAM, son
una generalización de los modelos lineales que
brindan además, una excelente forma de
interpretar los datos de manera gráfica.
Modelos lineales
Y =β0 + β1 X1 + β2 X2 + … + βd Xd + 
Si llamamos µ =E(Y)
donde  N(0, σ2).
tenemos que
µ =β0 + β1 X1 + β2 X2 + … + βd Xd
Las componentes del vector Y son variables independientes con
distribución normal con E(Y) = μ y varianza constante σ2.
Las variables X0, ….., Xd originan un predictor lineal η dado por
η = β0 + β1X1 +...+βdXd, o en forma matricial, η = Aβ.
Modelos lineales generalizados
g(µ) =β0 + β1 X1 + β2 X2 + … + βd Xd
O en forma matricial
Las componentes del vector Y son variables independientes con
distribución proveniente de una familia exponencial.
El predictor lineal y la variable dependiente están relacionados por una
función de enlace o “link” g, siendo g monótona y diferenciable.
Modelos aditivos generalizados
g(µ) =β0 + f1(X1) + f2(X2) + … + fd(Xd)
Las funciones fi(Xi) son funciones no paramétricas definidas a
partir de los datos denominadas “smoothers” .
Las componentes del vector Y son variables independientes
con distribución proveniente de una familia exponencial.
El predictor aditivo y la variable dependiente están
relacionados por una función de enlace o “link” g, siendo g
monótona y diferenciable.
Parámetros
LM
GLM
β0, β1,…,βd
β0, β1,…,βd
GAM
Estimación
Mínimos
cuadrados
Máxima
verosimilitud
Se estima f(X)
mediante el
algoritmo
Backfitting
Bondad de ajuste
R2
Desvianza
Desvianza
Comparación de
modelos
AIC
F
AIC
Desvianza
AIC
Desvianza
Supuestos
Residuos
normales y
homocedásticos
Y, familia
exponencial
Y, familia
exponencial
Ejemplo
Cifosis
Objetivo: identificación de factores de riesgo de Cifosis
(importancia de la edad al momento de la cirugía, efecto
del número y ubicación de las vértebras a tratar)
Datos: 83 pacientes
Variable dependiente: kyphosis (ausencia=0, presencia=1)
Variables independientes: edad (Age) , número de vértebras
(Number), vértebra inicial (Start)
Modelo: log(p/1-p)=s(Age)+s(Number)+s(Start)
donde p es la probabilidad de presencia de kyphosis.
Ejemplo
Cifosis
SVM
Support Vector Machine
Vapnik, 1995
SVM
En el contexto de clasificación SVM es una
metodología que consiste en encontrar una curva
que separe bien los datos.
SVM
Si los datos son linealmente separables:
SVM
Si los datos no son linealmente separables: se proyectan los
datos en un espacio de dimensión mayor (“feature space”)
donde los datos son linealmente separables.
Ejemplo
Iris
Objetivo: Predecir la especie de la flor de Iris.
Datos: 150 flores
Variable dependiente: especie (setosa, virginica, versicolor)
Variables independientes: largo y ancho del sépalo, largo y
ancho del pétalo
Ejemplo
Clasificación de la flor de Iris en setosa, virginica y
versicolor.
CART
Classification and Regression Trees
Breiman, 1984
CART
Árboles de regresión: para predecir variables continuas
Árboles de clasificación: para predecir variables categóricas
CART
muestra de entrenamiento
nodo raíz
separación
binara de los
datos mediante
condiciones
sobre las
variables
nodos internos
nodos terminales (hojas)
Etapas de construcción de un árbol
Etapa 1
Separación binaria de los datos de acuerdo a una regla
Etapa 2
Decisión del tamaño del árbol
Etapa 3
Asignación de una clase o de un valor a los nodos terminales
Etapa 1
Separación binaria de los datos de acuerdo a una regla
La división de los nodos depende de una única condición sobre una
o más variables
La mejor partición es aquella que incrementa la pureza en los
nodos hijos
Medidas de impureza:
• error de clasificación, entropía, índice de gini
• error cuadrático medio
Etapa 2
Decisión del tamaño del árbol
Criterio de parada
Se fija un umbral de parada y se detiene el proceso de división
cuando se llega a que la impureza en los nodos es inferior al
umbral.
Criterio de poda
Criterio más utilizado.
Evita que el crecimiento del árbol se detenga antes de tiempo.
Etapa 3
Asignación de una clase o de un valor a los nodos terminales
Clasificación
Se elige la clase que esté más representada en cada nodo
terminal (voto mayoritario simple)
Si el máximo se alcanza para dos o más clases, se realiza un
sorteo y se asigna arbitrariamente.
Regresión
Se asigna el promedio de los valores de la variable dependiente
para los casos que están en el nodo terminal.
Ejemplo: Contaminación ambiental
Problema de Regresión:
Variables de Entrada (X): variables meteorológicas
Variable de Salida (Y): concentración de ozono
Ejemplo: Contaminación ambiental
Performance del modelo
Bagging, Boosting
Validación cruzada
Bagging, Boosting
Breiman, 1994
Freund & Schapire, 1996
Bagging, Boosting
Tanto en Bagging y Boosting la idea consiste en combinar
varios predictores para construir un predictor más potente.
Son métodos que permiten estabilizar algoritmos inestables
de regresión y/o clasificación, como por ejemplo árboles de
decisión.
Los árboles son algoritmos inestables
Bagging
Bootstrap AGGregatING
El clasificador bagging combina los outputs de varios
clasificadores construidos utilizando remuestras (muestras
bootstrap) del conjunto de entrenamiento.
La clase que recibe más votos entre los clasificadores es la
clase asignada por el clasificador bagging.
¿Qué es una remuestra?
Se le asigna a cada observación X1, X2,…..,Xn ~ F
el mismo peso (1/n)
Se muestrea de forma aleatoria y con reemplazo obteniendo
B nuevas muestras:
cada una de las cuales tiene distribución asintótica próxima
a la empírica de la muestra original.
¿Qué probabilidad tiene cada observación de salir
en la remuestra?
Para valores de n grandes esta cantidad se aproxima a:
Es decir cada observación tiene un 63% de salir sorteada en
la remuestra.
Ejemplo de muestras bootstrap
s=randsample(1:10,10,true)
s = 10
8
2
5
10
10
5
9
1
4
s=
9
1
2
3
2
7
3
2
1
8
s=
5
10
5
5
9
6
3
7
9
1
s=
7
4
9
6
8
5
4
2
2
7
s=
4
6
2
7
4
9
9
6
5
9
Algoritmo Bagging
Paso1: conjunto de entrenamiento
Paso2: elección del estimador
Paso3: construcción de las remuestras
Paso4: para cada remuestra se calcula el estimador
Paso5: construcción del estimador Bagging, por ejemplo si el
modelo es de regresión
Boosting
Boosting es un proceso iterativo que combina los output de
varios clasificadores débiles para obtener un clasificador
más eficiente. Los clasificadores que muestran mejor
desempeño en la fase de entrenamiento tienen mayor peso
en la votación final.
Ejemplo de algoritmo de Boosting:
Adaboost.M1 (Freund & Schapire, 1997)
Adaboost.M1
• Algoritmo de boosting más conocido para bases de datos
con dos clases.
• Bajo desempeño en problemas de varias clases.
• Al inicio se considera una distribución uniforme para los
pesos de las observaciones, en las sucesivas iteraciones
esta distribución cambia, asignando mayor peso a las
observaciones mal clasificadas en el paso anterior
(remuestras ponderadas)
• Los clasificadores que muestran mejor performance en el
entrenamiento tienen mayor peso en la votación final.
Ejemplo de remuestras ponderadas
vector de pesos
w=[.3 .3 .05 .05 .05 .05 .05 .05 .05 .05]
s=randsample(1:10, 10, true, w)
s= 1
2
7
1
1
1
1
3
1
1
s= 1
5
2
9
2
2
7
2
1
4
s= 7
1
4
2
7
2
5
2
2
1
s= 1
4
2
2
1
4
2
8
8
2
s= 1
1
8
1
1
4
1
2
1
10
Adaboost.M1
Bagging vs Adaboost.M1
Bagging
3 iteraciones
Árbol 1
Clase 1
Árbol 2
Clase 1
Votos clase 1: 2
Votos clase 2: 1
Predicción Bagging: clase 1
Adaboost.M1
3 iteraciones
Árbol 3
Clase 2
Árbol 1
Clase 1
Score=0.6
Árbol 2
Clase 1
Score=0.8
Árbol 3
Clase 2
Score=1.7
Votos clase 1: 2
Votos ponderados clase 1: 1.4
Votos clase 2: 1
Votos ponderados clase 2 : 1.7
Predicción Adaboost.M1: clase 2
Validación cruzada
1. división del conjunto de entrenamiento en k partes iguales
(folds)
2. entrenamiento del modelo con k-1 partes
3. evaluación del modelo con la parte que no fue utilizada en el
paso anterior
4. se repite el proceso para cada una de las k partes
5. el error se calcula como el promedio de los errores calculados en
cada paso
Validación cruzada
En este ejemplo 8-fold se entrena el modelo con los datos
amarillos y se evalúa con los de color rojo.
En cada paso se calcula el error y el error total se define como
el promedio de los errores cometidos en cada paso.
Bibliografía
Breiman, L. Bagging predictors. Machine Learning, 24, 123-140 (1996)
Defeo, O. & Gomez, J. (2005) Morphodynamics and habitat safety in sandy
beaches: life history adaptations ni a supralittoral amphipod. Mar Ecol
Prog Ser, 293: 143-153
Devroye, L. Györfi, L. Lugosi, G. 1996. A Probability Theory of Pattern
Recognition. Springer.
Hastie, T.J; Tibshirani, R.J. 1990. Generalized Additive Models. Chapman &
Hall.
Hastie, T.J, Tibshirani, R.J, Friedman, J. 2001. Elements of Statistical
Learning: data mining, inference and prediction. Springer & Verlag.
Vapnik, V. 1998, Statistical Learning Theory. Wiley.
Wood, S. N. 2006. Generalized Additive Models, An Introduction with R.
Chapman & Hall.