Paralelización eficiente en métodos de núcleo

Resumen

Los métodos de núcleo son técnicas muy utilizadas en el área de aprendizaje automático debido a que son capaces de obtener buenos resultados en un gran número de tareas reales. El principal motivo de su éxito es que permiten crear soluciones no lineales de forma muy sencilla, transformando el espacio de entrada en un espacio de alta dimensionalidad donde los productos escalares se obtienen utilizando una función de núcleo. Entre las técnicas más extendidas tenemos por un lado las Máquinas de Vectores Soporte (SVMs, que funcionan muy bien en problemas de clasificación, y por otro lado los Procesos Gaussianos (GP), muy utilizados en problemas de regresión. Los métodos de núcleo siempre han tenido dos puntos débiles que limitan su aplicación práctica. En primer lugar está el coste computacional asociado a entrenar este tipo de algoritmos, que tiene problemas de escalabilidad que reducen mucho su campo de actuación. El segundo problema está asociado a que sean métodos no paramétricos, en los métodos de núcleo la complejidad de los modelos se ajusta automáticamente y no viene prefijada de antemano. Esta capacidad de autoajuste hizo muy populares este tipo de técnicas pero cuando se trabaja con volúmenes de datos grandes se obtienen modelos demasiado complejos que son muy lentos para procesar nuevas muestras. En los últimos años una serie de factores como la redes sociales, el comercio electrónico, los dispositivos móviles y la colaboración utilizando las nuevas tecnologías han hecho que las bases de datos se hayan incrementado enormemente y que se haya pasado de la problemática de no tener suficientes datos para solucionar una tarea al problema completamente opuesto de tener tal volumen de datos que resulte muy costoso y complicado procesarlos. Si al hecho de que actualmente se disponga de bases de datos mucho más grandes le unimos la problemática que tienen los métodos de núcleo en cuanto a coste computacional y escalabilidad, nos encontramos con que este tipo de técnicas ha visto muy reducido su campo de acción. Afortunadamente también han surgido líneas de investigación que permiten enfrentarnos a este tipo de problemas como son la paralelización y las aproximaciones semi-paramétricas. Por un lado, el número de núcleos de procesamiento en los ordenadores se ha incrementado considerablemente dando lugar a nueva líneas de investigación para adaptar técnicas clásicas de aprendizaje automático a un nuevo escenario de paralelización en el que múltiples recursos trabajan de forma simultánea bajo el principio de que los problemas pueden dividirse en tareas más pequeñas que pueden resolverse al mismo tiempo. Por otro lado, las soluciones semi-paramétricas son aproximaciones que fijan de antemano la complejidad de los modelos que se obtienen y evitan el problema de obtener soluciones demasiado lentas a la hora de evaluar nuevas muestras. Este tipo de soluciones pueden además reducir el coste computacional del entrenamiento para evitar que escale de forma cúbica con el número de muestras. En esta Tesis se hace uso de estas líneas y se presentan nuevos algoritmos paralelos para entornos multiprocesador y multinúcleo de versiones tanto completas como semi-paramétricas de diferentes métodos de núcleo. En primer lugar, se presenta un nuevo esquema de paralelización que se beneficia de la formulación matricial de los métodos de núcleo y propone unos criterios de diseño tanto de bajo como de alto nivel de las operaciones que se llevan a cabo en este tipo de algoritmos y permiten una implementación paralela eficiente. Para demostrar la utilidad de estas técnicas y con el objeto de aunar las dos principales líneas de investigación en lo referente escalabilidad de métodos de núcleo, se ha realizado una implementación de SVMs semi-paramétricas y GPs tanto completos como semi-paramétricos. Los resultados obtenidos al utilizar como referencia otras soluciones existentes demuestran la utilidad y eficiencia de estas técnicas. En segundo lugar y tras analizar las limitaciones del modelo propuesto anteriormente, que hacía uso de una resolución de sistemas lineales paralela utilizando una inversión por bloques, se ha propuesto un nuevo esquema basado en una factorización de Cholesky paralela que mejora la estabilidad numérica y es más eficiente computacionalmente. Con este nuevo esquema se ha realizado una implementación de SVMs tanto completas como semi-paramétricas y los resultados obtenidos han mostrado su superioridad respecto al modelo anterior. Como añadido, también se han muestran otros aportes que se corresponden a resultados y premios obtenidos en competiciones de aprendizaje automático gracias a los conocimientos sobre paralelización adquiridos en este trabajos. El trabajo finaliza con una revisión de las aportaciones realizadas y sugerencias de nuevas líneas de investigación abiertas.