Paralelización de métodos de aprendizaje semi-supervisado basados en grafos

Abstract

El aprendizaje computacional es un área de estudio de algoritmos para obtener predictores basados en información obtenida de experiencias pasadas. Consiste en métodos que permiten que un sistema aprenda a descubrir patrones, tendencias y relaciones entre los datos, que pueden ser usados para la solución de problemas en áreas de ingeniería. El proceso de aprendizaje puede dividirse en tres tipos: aprendizaje supervisado, no-supervisado, y semi-supervisado. Los algoritmos de aprendizaje semi-supervisado tienen como característica principal que requieren una cantidad reducida de datos con información de clase para su entrenamiento, pero son capaces de aprovechar además la información geométrica de una gran cantidad de elementos que no tienen etiqueta. Estos algoritmos pueden alcanzar rendimientos similares o superiores a los supervisados. Dentro de las técnicas de Aprendizaje Semi-Supervisado, sobresalen los métodos basados en grafos que representan cada muestra como un nodo y sus relaciones como arcos. Entre sus principales ventajas destacan que hay métodos matemáticos muy sólidos para interpretar y obtener sus propiedades; así mismo, a menudo tienen un objetivo global convexo, presentando altas garantías de convergencia. Esto último resulta atractivo para aplicarlo en problemas con cantidades grandes de datos que pueden ser modelados con grafos de manera natural como son: clasificación de páginas Web, sistemas de seguridad, reconocimiento de voz, entre otros. Para el procesamiento de grafos grandes se han desarrollado métodos muy sólidos que permiten soluciones escalables usando Cómputo de Alto Rendimiento. El Cómputo de Alto Rendimiento es una herramienta que permite tratar problemas a una velocidad mucho mayor cuando existe una forma de distribuir y paralelizar el procesamiento de los cálculos. Por otro lado, existen problemas que requieren una gran cantidad de datos, y su almacenamiento en equipos comunes no es posible. Otra ventaja destacable de esta tecnología consiste en que es posible distribuir los archivos para su procesamiento en sistemas de archivos distribuidos, o simplemente a través de varios equipos interconectados por una red local, es decir, existen las condiciones para acceder a ellos en el momento que se requieran de manera independiente. Los algoritmos paralelizados en el presente proyecto de tesis son: el Algoritmo de Propagación de Etiquetas, que tiene por idea principal que puntos cercanos deben tener etiquetas similares, de esta forma, los nodos etiquetados propagan sus etiquetas a los nodos vecinos que no la tienen. La segunda implementación consiste en el Algoritmo de Propagación de Etiquetas usando el Criterio del Costo Cuadrático, éste trata de aprovechar la información generada por la geometría de las relaciones entre los nodos usando la regla de los k-vecinos más cercanos y una medida de similaridad basada en la distancia Euclidiana. En el presente trabajo, el uso del cómputo paralelo y distribuido permitió mejorar los tiempos de respuesta de los algoritmos al distribuir el procesamiento en diferentes unidades de procesamiento y/o otros equipos interconectados a través de una red. Las pruebas realizadas fueron hechas sobre conjuntos de datos medianos y grandes, el rendimiento de clasificación obtenida en ambos algoritmos es similar a los de otros autores usando otros algoritmos de aprendizaje supervisado y semi-supervisado. En este trabajo además se reportan las mejoras en tiempo de ejecución de entre 3x a 7x veces para la implementación paralela con respecto a la implementación secuencial y se reporta el procesamiento de un conjunto con hasta 80,000 elementos usando una implementación distribuida.