Parallelization of a graph-based multi-view machine learning algorithm
Title
Parallelization of a graph-based multi-view machine learning algorithmAuthor(s)
Directors
González-Domínguez, JorgeTouriño, Juan
Date
2023Center/Dept./Entity
Universidade da Coruña. Facultade de InformáticaDescription
Traballo fin de grao (UDC.FIC). Enxeñaría Informática. Curso 2022/2023Abstract
[Abstract]: In recent years, a perfect storm has unfolded in the field of machine learning. Increases
in computational power, a surge of interest for analyzing big volumes of data, and novel
developments in data processing techniques have all contributed to massive leaps both in research
and practical applications. Moreover, the ever-increasing diversity in the nature of the
data studied has boosted an emerging paradigm: multi-view learning. Multi-view algorithms
are characterized by their superior capability to harvest knowledge from data obtained from
multiple sources or “views”. This paradigm has shown impressive results in various contexts.
This thesis focuses on the efforts to apply multi-view learning to unsupervised clustering
problems, which can offer great insight into underlying patterns in data. In 2019, H. Wang, Y.
Yang, and B. Liu presented a novel solution to the problem: Graph-Based Multi-View Clustering.
It combined methods used in graph-based and spectral clustering, and presented a new
data-fusion approach that outperformed state-of-the-art techniques.
Despite its impressive results, the computational requirements to execute this algorithm
over big data are prohibitive. The provided reference implementation works under the MATLAB
interpreter and lacks scalability due to its high memory usage and cubic time complexity.
This work aims to address those shortcomings, presenting an implementation built from the
ground up in C language, and designed specifically to scale in high performance computing
cluster environments. For this purpose, both shared-memory and distributed-memory
parallelism techniques will be employed, via OpenMP and MPI, respectively. This highly optimized
implementation reduces not only memory usage, but also the algorithm’s complexity
to quadratic, which theoretical analysis suggests to be optimal. Standard, highly performant
linear algebra libraries were used to accelerate execution. Furthermore, both the lowered
memory requirements and the possibility to run the code in distributed-memory systems
allow this method to be used for analysis of much bigger datasets, that would have been
impossible to process before.
Extensive experimental tests were performed over a suitable high performance computing
cluster, using a total of 288 CPU cores and 2.25TiB of memory. The results are considered
satisfactory. During the jump from MATLAB to C, performance increased by factors of up to
60 when testing with the small datasets that could be processed sequentially. On top of that,
parallelization achieved additional speedups. During testing, speeds up to 60 times faster than
the sequential C counterpart were observed, with the possibility of further scaling depending
on the resources allocated. [Resumo]: Nos últimos anos, unha tormenta perfecta tomou por sorpresa ao campo da aprendizaxe
automática. Aumentos da potencia computacional, grande afluencia na interese por analizar
grandes conxuntos de datos, e innovacións no procesado de datos contribuíron a grandes
saltos tanto na investigación coma no uso práctico. Ademais, o constante incremento na diversidade
dos datos estudados levou a un novo paradigma: a aprendizaxe multi-vista. Os algoritmos
multi-vista caracterizanse pola súa capacidade de explotar o coñecemento dos datos
estruturados dependendo da súa orixe ou “vista”. Este paradigma mostra resultados remarcables
en contextos varios. Este traballo de fin de grao se centra nos esforzos de aplicar aprendizaxe
multi-vista a problemas de agrupamento non supervisado, que ofrecen información
interesante sobre patróns ocultos nos datos. En 2019, H. Wang, Y. Yang, e B. Liu presentaron
unha solución innovadora ao problema: agrupamento multi-vista baseado en grafos. Este
combina métodos empregados en agrupamento por grafos e espectral, e presenta un novo
mecanismo de fusión de datos que supera os resultados obtidos no estado da arte.
Pese a estes resultados, os requisitos computacionais para executar este algoritmo sobre
grandes conxuntos de datos son prohibitivos. A implementación de referencia proporcionada
funciona baixo o intérprete de MATLAB, e carece de escalabilidade debido ao seu elevado
uso de memoria e complexidade computacional cúbica. Este traballo busca aliviar estes problemas,
presentando unha implementación construída dende cero en linguaxe C, e deseñada
especificamente para o seu uso en sistemas de computación de altas prestacións. Para isto,
farase uso tanto de técnicas de paralelismo en memoria compartida coma distribuída, mediante
OpenMP e MPI, respectivamente. Esta implementación, altamente optimizada, reduce
o uso de memoria e a complexidade computacional do algoritmo. Esta será cuadrática, o cal
é óptimo segundo a análise teórica. Empregáronse librerías estándar de álxebra lineal de alto
rendemento para acelerar a execución. Adicionalmente, tanto os relaxados requisitos de memoria
coma a posibilidade de executar o código en sistemas de memoria distribuída permiten
que este método analice conxuntos de datos moito maiores, que non eran posibles de tratar
con anterioridade.
Leváronse a cabo numerosas probas de rendemento sobre un moderno clúster de computación
de altas prestacións, usando un total de 288 núcleos de CPU e 2.25TiB de memoria. Os
resultados considéranse satisfactorios. O salto dende MATLAB a C é responsable de aceleracións
con tempos ata 60 veces menores en probas cos datos que os métodos secuenciais poden
procesar. Aínda por riba, o proceso de paralelización obtivo aceleracións adicionais. Durante
as probas, observáronse velocidades ata 60 veces máis rápidas cas da implementación en C
secuencial, coa posibilidade de escalar máis aló dependendo dos recursos dispoñibles.
Keywords
Multi-view clustering
Graph-based clustering
Machine learning
High performance computing
Parallel computing
MPI
OpenMP
Big Data
Agrupamento multi-vista
Agrupamento baseado en grafos
Aprendizaxe máquina
Computación de altas prestacións
Computación paralela
Graph-based clustering
Machine learning
High performance computing
Parallel computing
MPI
OpenMP
Big Data
Agrupamento multi-vista
Agrupamento baseado en grafos
Aprendizaxe máquina
Computación de altas prestacións
Computación paralela
Rights
Atribución 3.0 España