Download Diapositiva 1
Document related concepts
Transcript
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.