logo EDITE Sujets de doctorat

On the Design of Incremental and Scalable Machine Learning Algorithms

Sujet proposé par
Directeur de thèse:
Encadré par
Doctorant: Duc-Trung NGUYEN
Unité de recherche UMR 7102 Laboratoire de recherche d'EURECOM

Domaine: Sciences et technologies de l'information et de la communication

Projet

The objective of this Thesis is to work on the design of scalable machine learning algorithms to build statistical models based on large volumes of data. This include: • An appropriate design of the algorithmic technique striking the best possible balance between parallelism and communication cost, together with an appropriate definition of auxiliary data structures that hold intermediate data, by taking into account I/O and memory requirements • Ana analysis of the impact on the underlying parallel execution engine of the algorithm design and its data structures, with a particular focus on the I/O and memory consumption patterns • An extension of the aforementioned scalable algorithm design to cope with the problem of an on-line, real-time learning of statistical models

Enjeux

Research in parallel data processing of large datasets (in which I/O is the bottleneck, not the CPU) has received a lot of attention in recent years. Popularized by Google with their work on large-scale data processing systems and by the Apache Hadoop open-source project and more recently by the advent of modern parallel processing engines such as Apache Spark, MapReduce – which constitutes the underlying programming model used in this Thesis – is a promising approach for the design of scalable algorithms. In MapReduce, a data analysis task consists of three phases and accepts as input a dataset, appropriately partitioned and stored in a distributed file system. In the first phase, called Map, a user-defined function is applied in parallel to input partitions to produce intermediate data, which is stored on the local file system of each machine of the cluster; intermediate data is sorted and partitioned when written to disk. Next, during the Shuffle phase, intermediate data is "routed" to the machines responsible for executing the last phase, called Reduce. In this phase, intermediate data from multiple mappers is sorted and aggregated to produce output data, which is written back on the distributed file system. Now, the implementation of an algorithm or a data processing task in MapReduce, requires familiarity with many low-level system details, which need to be adapted and optimized to every specific analytic job. For example, the implementation of simple clustering algorithms, that are largely used in many fields related to machine learning, is difficult and in general leads to inefficient use of system resources. As a consequence, the goal of this Thesis is to push the research and development of scalable algorithm design one step forward by focusing on the underlying complexity of the MapReduce programming paradigm, and on the specific mechanisms and data structures that determine its physical resource utilization. Furthermore, the candidate will also focus on the problem of the incremental, on-line learning of statistical models computed over large amount of streaming data. The approach in this Thesis involves three main research directions: • Scalable algorithm design: to address the problem of building statistical models for inference and prediction problems, as well as for un-supervised learning tasks • System performance evaluation: experimental approach to assess the properties of the scalable machine learning algorithms and their impact on the underlying parallel execution framework • Incremental machine learning: real-time learning of statistical models on large-scale data streams Academic Supervisor: Prof. Pietro Michiardi, EURECOM PhD Candidate: Duc-Trung NGUYEN Conception d’algorithmes d’apprentissage de models statistiques incrementaux et pouvant passer a l’echelle L'objectif de cette thèse est de travailler sur la conception d'algorithmes d'apprentissage pouvant passer à l’échelle, pour construire des modèles statistiques basés sur de gros volumes de données. Ceci inclus: • La conception des techniques algorithmique pouvant atteindre le meilleur équilibre possible entre le parallélisme et le coût de la communication, avec une définition appropriée de structures de données auxiliaires qui contiennent des données intermédiaires, en tenant compte du cout en termes d’I/O et des besoins en mémoire • Analyse de l'impact sur le système d'exécution parallèle sous-jacente des algorithmes et de ses structures de données, avec un accent particulier sur la consommation d'I/O et de la mémoire • Une extension des algorithmes définis ci-dessus pour faire face au problème de l'apprentissage des modèles statistiques en temps réel La recherche dans le traitement parallèle de grands ensembles de données (dans laquelle le I/O est le goulot d'étranglement, pas le CPU) a reçu beaucoup d'attention ces dernières années. Popularisé par Google avec leur travail sur les systèmes de traitement de données et par le projet open-source Apache Hadoop et plus récemment par Apache SPARK, MapReduce - qui constitue le paradigme de programmation sous jacent pour le travail dans cette thèse - est un outils prometteur pour la conception d’algorithmes pouvant passer a l’échelle. En MapReduce, une tache d'analyse de données se compose de trois phases et accepte en entrée un ensemble de données, partitionnées de manière appropriée et stockée dans un système de fichiers distribué. Dans la première phase, dite MAP, une fonction définie par l'utilisateur est appliquée en parallèle à des partitions d'entrée pour produire des données intermédiaires qui sont stockées sur le système de fichiers local de chaque ordinateur du cluster de calcul; les données intermédiaires sont triées et répartis lors de l'écriture sur le disque. Ensuite, au cours de la phase SHUFFLE, les données intermédiaires sont "dirigée" vers les machines responsables de l'exécution de la dernière phase, appelée REDUCE. Dans cette phase, les données intermédiaires sont triées et regroupées pour produire des données de sortie, qui sont écrites sur le système de fichiers distribué. Maintenant, pour la mise en œuvre d'un algorithme ou une tâche de traitement de données dans MapReduce, il faut connaître beaucoup de détails du système de bas niveau, qui doivent être adaptés et optimisés pour chaque travail d'analyse spécifique. Par exemple, la mise en œuvre des algorithmes de clustering simples, qui sont largement utilisés dans de nombreux domaines liés à l'apprentissage statistique, est difficile et conduit en général à une utilisation inefficace des ressources du système. En conséquence, l'objectif de cette Thèse est de pousser la recherche et le développement de la conception d'algorithmes un pas en avant en mettant l'accent sur la complexité sous-jacente du paradigme de programmation MapReduce, et sur les mécanismes spécifiques et des structures de données qui déterminent l’utilisation des ressources physiques du système. En outre, le candidat mettra également l'accent sur le problème de l'apprentissage progressif, en ligne, de modèles statistiques calculés sur une grande quantité de données transmises en continu. L'approche adoptée dans cette thèse comporte trois principaux axes de recherche: • Conception d'algorithmes: pour résoudre le problème de la construction de modèles statistiques pour l'inférence et les problèmes de prédiction, ainsi que pour des tâches d'apprentissage non supervisé • L'évaluation des performances du système d’exécution à travers un approche expérimentale, pour évaluer les propriétés des algorithmes d'apprentissage et leur impact sur les systèmes d'exécution parallèle • La conception d’algorithmes d’apprentissage incrémental en utilisant comme source de données un flux continu