Aprendizaje multi-etiqueta distribuido en apache spark

Resumen

1. Introducción o motivación de la tesis La aparicion de nuevas tecnologias ha dado lugar a un incremento exponencial del volumen de datos almacenados en los sistemas modernos. La cantidad de datos generados por los consumidores continua creciendo en numeros absolutos. Por otra parte, el volumen de datos generados por otros sistemas de computacion tambien esta sufriendo un rapido incremento. Al mismo tiempo que los datos aumentan en volumen, tambien lo hacen en complejidad, lo cual supone un obstaculo a la hora de utilizarlos para diferentes fines. El crecimiento exponencial de los datos, tanto en tamano como en complejidad, han producido la necesidad de encontrar tecnicas que puedan extraer la informacion util de forma precisa, eficiente y escalable. Una de las tecnicas mas avanzadas para la extraccion de informacion de un conjunto de datos es el Aprendizaje Automatico (Machine learning). Esta tecnica extrae la informacion generalizando por experiencia, es decir, es capaz de aprender reglas y relaciones entre datos ya conocidos y extrapolarlos a otros datos. Uno de los paradigmas dentro de este campo es conocido como aprendizaje multi-etiqueta, en el cual cada instancia de los datos es asociada con multiples variables (etiquetas) simultaneamente. Desafortunadamente la capacidad de computo de los procesadores no ha incrementado de la misma forma que el volumen y la complejidad de los datos. Por lo que la mayoria de los investigadores y empresas se ha visto forzada a migrar el computo de las tareas a entornos compuestos por multiples maquinas. Estos entornos requieren de nuevas herramientas de programacion orientadas a sistemas distribuidos. El modelo de programacion mas popular orientado a la computacion de datos a gran escala es el MapReduce. Este modelo define como la computacion se puede distribuir entre varias maquinas mediante un particionamiento de los datos. Una de las primeras implementaciones de este modelo es Hadoop, desafortunadamente Hadoop depende del uso de almacenamiento secundario lo cual introduce una alta latencia. Apache Spark es un framework que soluciona este problema mediante la posibilidad de mantener y operar con los datos en memoria. Esto hace que Spark se proclame como la mejor opcion en la actualidad para la ejecucion de aplicaciones con una alta intensidad de computo, como por ejemplo Aprendizaje Automatico. 2.Contenido de la investigación La presente Tesis Doctoral propone una serie de algoritmos para problemas multi-etiqueta utilizando Apache Spark como modelo de programacion distribuido. El objetivo es proponer nuevos metodos para el aprendizaje y procesamiento de datos multi-etiqueta caracterizados por una gran cantidad de instancias, atributos, y/o etiquetas. Para ello se han estudiado una serie de propuestas, con un enfoque ascendiente en el cual cada una ha establecido la base de la siguiente. En primer lugar, se han estudiado diferentes estrategias para la distribucion del aprendizaje de datos multi-etiqueta. Para ello se propusieron el estudio de cinco estrategias diferentes: una implementacion base que, utilizada un unico hilo en una unica maquina, una version que utilizaba multiples hilos en una misma maquina, una version distribuida que utilizada la version mono-hilo en multiples maquinas, otra version distribuida que utilizaba la version multi-hilo en multiples maquinas, y, por ultimo, una version que extendia los metodos nativos de Spark. Esta version construye modelos colaborativos distribuyendo las instancias, mientras que las anteriores requieren de todas las instancias en todas las maquinas y cada una utiliza diferentes sets de etiquetas. El analisis de los resultados demuestra que la distribucion de las instancias en el modelo nativo de Spark produce un mayor rendimiento y mejor escalabilidad. Utilizando esta estrategia para el aprendizaje de modelos multi-etiqueta, se decide estudiar uno de los metodos con mas aplicaciones pero que a su vez sufre de grandes problemas de rendimiento: multi-label k Nearest Neighbor (Ml-knn). Este metodo hace predicciones en base a la distancia que separa diferentes instancias. Por lo tanto, requiere del almacenaje de todas las instancias conocidas. Para discernir de la mejor estrategia para poder incorporar este metodo a sistemas distribuidos y que aprenda de un gran volumen de datos, se estudian diferentes implementaciones: una implementacion iterativa que comprueba las distancias entre todas las instancias, otra que utiliza un arbol para indexar las instancias a traves de multiples maquinas, y, por ultimo, una que utiliza una serie de hashes para indexar y agrupar las instancias. Estos metodos son comparados y evaluados respecto a sus predicciones, sus tiempos de ejecucion, y su escalabilidad respecto al numero de instancias, atributos, y etiquetas. Los resultados del estudio indican que el metodo basado en un arbol permite ejecutar cientos de veces mas rapido que los otros metodos manteniendo una precision equivalente a la de los metodos exactos. Una de las caracteristicas que mas dificulta el aprendizaje de los modelos multi-etiqueta es la gran dimensionalidad de los datos, es decir, el gran numero de atributos asignado a las instancias. Por otra parte, se ha demostrado en multiples ocasiones que la calidad de los modelos aumenta descartando atributos irrelevantes y/o redundantes. Pero aun existe mucho debate en torno a la forma en la que se puede evaluar cada uno de los atributos respecto a multiples etiquetas. Por lo tanto, realizamos un analisis detallado de las diferentes estrategias discutiendo sus ventajas y desventajas. Tras lo cual seleccionamos el metodo que consideramos mas conveniente, especialmente para datos caracterizados por su gran numero de instancias y atributos. En base a esta estrategia proponemos dos metodos nuevos, los cuales no requieren de ningun tipo de transformacion de datos y son capaces de utilizar multiples etiquetas simultaneamente. El primer metodo selecciona los atributos cuyas medidas individuales de informacion forman la mayor normal Euclidea, mientras que el segundo metodo selecciona aquellos que presentan la mayor media geometrica. Los resultados indican que el primer metodo presenta los mejores resultados para datos binarios y con un menor numero de etiquetas, mientras que el segundo metodo en preferible para datos continuos o con un mayor numero de etiquetas. Todos los algoritmos y metodos de la presente Tesis Doctoral han sido evaluados mediante una serie de test no parametricos. Los algoritmos propuestos han sido comparados frente a los algoritmos mas utilizados en cada una de las tareas, por lo tanto, validando la eficiencia de cada una de las propuestas. Finalmente se presentan una serie de lineas de investigacion orientadas a ampliar o mejorar las conclusiones obtenidas en la presente Tesis Doctoral. Todas estas lineas de investigacion estan relacionadas con el aprendizaje multi-etiqueta y/o el aprendizaje en sistemas distribuidos. 3.Conclusión La presente Tesis Doctoral ha presentado una serie de algoritmos dentro de la implementación de un framework para el aprendizaje distribuido de problemas multi-etiqueta en Apache Spark. Una serie de métodos han dicho implementados, desde nuevos métodos propuestos a métodos tradicionales utilizados en el estudio comparativo. Los métodos propuestos son: tres estrategias diferentes para el aprendizaje distribuido de “k nearest neighbor” utilizando datos multi-etiqueta, y dos métodos distribuidos para la selección de atributos basados en el uso de “mutual information”. Todos estos métodos han sido implementados utilizando el modelo de arquitectura optimo en Apache Spark. El método de aprendizaje distribuido de “k nearest neighbors” basado en el uso de árboles para la indexación de instancias permite ejecutar cientos de veces más rápido que los otros métodos distribuidos manteniendo una calidad en las predicciones equivalente a la de un método exacto. Por otra parte, este método ha sido posteriormente empleado para evaluar los métodos propuestos de selección de atributos para problemas multi-etiqueta. El uso de un método optimo como clasificador base ha permitido ampliar el número de casos en los que se han evaluado los métodos propuestos. Los métodos propuestos mejoran ampliamente los resultados de aquellos basados en el test de chi-square. Respecto a la comparativa de los métodos que usan “mutual information”, el método que utiliza la máxima distancia Euclídea mejora ampliamente los resultados para los atributos discretos, y el método que maximiza la media geométrica iguala el rendimiento de otro de los métodos de “mutual information”. Finalmente podemos concluir que cada una de las estrategias propuestas depende de la naturaleza de los atributos, pero que es posible mejorar ampliamente los resultados de los métodos del estado del arte. 4. Bibliografía TSOUMAKAS, Grigorios, KATAKIS, Ioannis y VLAHAVAS, Ioannis. Mining Multi-label Data. Springer, 2009, 667–685. TSOUMAKAS, Grigorios, KATAKIS, Ioannis y VLAHAVAS, Ioannis. "Random k-labelsets for multilabel classification". IEEE Transactions on Knowledge and Data Engineering. 2011, vol 23, nпїЅm. 7, p. 1079–1089. TSOUMAKAS, Grigorios, SPYROMITROS-XIOUFIS, Eleftherios, VILCEK, Jozef y VLAHAVAS, Ioannis. "Mulan: A java library for multi-label learning". Journal of Machine Learning Research. 2011, vol 12, nпїЅm. Jul, p. 2411–2414. ZHANG, Min-Ling y ZHOU, Zhi-Hua. "ML-KNN: A lazy learning approach to multi-label learning". Pattern Recognition. 2007, vol 40, nпїЅm. 7, p. 2038–2048. MAILLO, Jesъs, TRIGUERO, Isaac y HERRERA, Francisco. A MapReduce-based k-nearest neighbor approach for big data classification. 2015.p. 167–172. LIU, Ting, ROSENBERG, Charles y ROWLEY, Henry A. Clustering billions of images with large scale nearest neighbor search. 2007.p. 28–28. KRASKOV, Alex, ER, STЦGBAUER, Harald y GRASSBERGER, Peter. "Estimating mutual information". Physical review E. 2004, vol 69, nпїЅm. 6, p. 066138. LEE, Jaesung y KIM, Dae-Won. "Feature selection for multi-label classification using multivariate mutual information". Pattern Recognition Letters. 2013, vol 34, nпїЅm. 3, p. 349–357. LEE, Jaesung y KIM, Dae-Won. "Mutual Information-based multi-label feature selection using interaction information". Expert Systems with Applications. 2015, vol 42, nпїЅm. 4, p. 2013–2025. LIN, Yaojin, HU, Qinghua, LIU, Jinghua y DUAN, Jie. "Multi-label feature selection based on max-dependency and min-redundancy". Neurocomputing. 2015, vol 168, p. 92–103. DOQUIRE, Gauthier y VERLEYSEN, Michel. "Mutual information-based feature selection for multi-label classification". Neurocomputing. 2013, vol 122, p. 148–155. ROSS, Brian C. "Mutual information between discrete and continuous data sets". PloS one. 2014, vol 9, nпїЅm. 2, p. e87357.