Active Learning Methods for Interactive Exploration on Large Databases - Département d'informatique Accéder directement au contenu
Thèse Année : 2021

Active Learning Methods for Interactive Exploration on Large Databases

Méthodes d'apprentissage actif pour l'exploration interactive sur les grandes bases de données

Enhui Huang
  • Fonction : Auteur
  • PersonId : 1041206

Résumé

Faced with an increasing gap between fast growth of data and limited human ability to comprehend data, data analytics tools are now in high demand in many applications across a broad set of domains. In particular, for interactive data exploration systems, an "explore-by-example" framework, which aims to assist the user in performing highly effective data exploration while minimizing the human effort, is becoming increasingly popular. However, the state-of-the-art explore-by-example systems still require a large number of labeled examples to achieve the desired accuracy and cannot handle noisy labels. To address both the slow convergence problem and the label noise problem, in this thesis, we cast the explore-by-example problem in a principled "active learning" framework, and bring the properties of important classes of the user interest to bear on the design of new algorithms and optimizations for active learning-based data exploration. While recent work proposed a polytope-based data space model to filter examples returned by a traditional active learner and to compute an accuracy-based stopping criterion for active learning, our first contribution is to combine the polytope-based model and a traditional active learner into a new Dual-Space Model (\dsm), jointly offering the prediction and sample acquisition functionalities and thereby expediting model convergence. We also provide a set of techniques to improve the interactive performance such that the per-iteration time is maintained within 1 to 2 seconds. Evaluation results using real-world datasets and user interest patterns show that the accuracy of our system is on average 26\% higher than the state-of-the-art explore-by-example systems. Our second contribution is to overcome the slow convergence problem when data exploration is performed in high dimensions. We factorize the high-dimensional space into a set of low-dimensional spaces, build a \dsm\ in each subspace and combine them to be a factorized \dsm\ (\dsmf). We further prove that \dsmf\ achieves a better accuracy-based stopping criterion than \dsm. In case that the user may start exploration with more attributes than those needed in the final model, we propose an online feature selection method that adaptively selects the top-k relevant attributes. Experimental results using real-world workloads show that our system significantly outperforms the state-of-the-art explore-by-example systems in accuracy (19x$\sim$64x accuracy improvement) and convergence speed while maintaining the per-iteration time within 1 to 2 seconds and our online feature selection method improves accuracy from nearly 0 without feature selection, to above 80\%. %We formally define the class of queries that \dsmf\ supports, the decision function it utilizes, and prove that it achieves a better accuracy-based stopping criterion than \dsm. Last but not least, we address the label noise problem when the labels provided by the user are potentially corrupted. We enhance the robustness of our system by integrating advanced data cleansing methods and a refinement of the polytope-based model into \dsmf. The resulting algorithm, referred to as the Robust Dual-Space Model (\rdsmf), is compared to traditional active learning for evaluation since the state-of-the-art explore-by-example systems fail to deal with noisy labels. Experimental results using real-world datasets and user interest patterns show that our proposed algorithm substantially outperforms traditional active learning in accuracy (up to 22x accuracy improvement) while achieving reasonable efficiency for interactive data exploration (1 to 3 seconds per iteration).
Face à un écart grandissant entre la croissance rapide des données et la capacité humaine limitée à comprendre les données, les outils d'analyse de données sont en forte demande dans de nombreuses applications à travers un large éventail de domaines. En particulier, pour les systèmes interactifs d'exploration de données, un cadre « explorer par l’exemple », qui vise à aider un utilisateur humain à effectuer une exploration de données très efficace tout en minimisant son effort, devient de plus en plus populaire. Cependant, ces systèmes de pointe nécessitent toujours un grand nombre d'exemples étiquetés pour obtenir la précision souhaitée et ne peuvent pas gérer les étiquettes bruyantes. Pour résoudre à la fois le problème de la convergence lente et le problème du bruit des étiquettes, dans cette thèse, nous plaçons le problème d’« explorer par l’exemple » dans un cadre d’apprentissage actif fondé sur des principes et apportons les caractéristiques des classes importantes de l'intérêt de l'utilisateur, pour contribuer à la conception de nouveaux algorithmes et à l'optimisation pour l'exploration de données basée sur l'apprentissage actif. Alors que des travaux récents ont proposé un modèle d'espace de données basé sur les polytopes pour filtrer les exemples renvoyés par un apprenant actif traditionnel et pour calculer un critère d'arrêt basé sur la précision pour l'apprentissage actif, notre première contribution vise à combiner le modèle basé sur les polytopes et l’apprenant actif traditionnel en un nouveau modèle à double espace (\dsm), qui offre conjointement les fonctionnalités de prédiction et d'acquisition d'échantillons et ainsi l’accélération de la convergence des modèles. D'ailleurs, nous introduisons un ensemble de techniques pour améliorer les performances interactives de telle sorte que le temps par itération est maintenu entre 1 à 2 secondes. Les résultats de l'évaluation utilisant des jeux de données du monde réel et des patterns d'intérêt des utilisateurs montrent que la précision de notre système est en moyenne 26\% supérieure à celle des systèmes d’explorer par l’exemple de pointe. Notre deuxième contribution consiste à surmonter le problème de la convergence lente lorsque l'exploration des données est effectuée en haute dimension. Nous factorisons l'espace de grande dimension en un ensemble d'espaces de faibles dimensions, construisons un \dsm\ dans chaque sous-espace et les combinons pour former un \dsm\ factorisé (\dsmf). Nous prouvons en outre que \dsmf\ atteint un meilleur critère d'arrêt basé sur la précision que \dsm. Dans le cas où l'utilisateur veut commencer l'exploration avec plus d'attributs que ceux requis dans le modèle final, nous proposons une méthode de sélection de caractéristique en ligne qui donne de manière adaptative les k attributs les plus pertinents. Les résultats expérimentaux montrent que notre système surpasse les systèmes de pointe en termes de précision (entre x19 et x64) et de vitesse de convergence tout en maintenant le temps par itération entre 1 à 2 secondes et notre méthode de sélection de caractéristique en ligne améliore la précision de près de 0 (sans sélection) jusqu’à plus de 80\%. Enfin, nous abordons le problème du bruit lorsque les étiquettes fournies par l'utilisateur sont potentiellement erronées. Nous renforçons la robustesse de notre système en intégrant des méthodes avancées de nettoyage de données et un raffinement du modèle basé sur les polytopes dans \dsmf. L'algorithme obtenu, appelé le modèle à double espace robuste (\rdsmf), est comparé à l'apprentissage actif traditionnel à des fins d'évaluation, car les systèmes d’explorer par l’exemple de pointe sont incapables de gérer les étiquettes bruyantes. Les résultats expérimentaux montrent que notre algorithme améliore considérablement l'apprentissage actif traditionnel en termes de précision (jusqu'à x22) tout en atteignant une efficacité raisonnable pour l'exploration interactive des données (1 à 3 secondes par itération).
Fichier principal
Vignette du fichier
Enhui_thesis_final.pdf (5.7 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

tel-03339951 , version 1 (09-09-2021)
tel-03339951 , version 2 (11-10-2021)

Identifiants

  • HAL Id : tel-03339951 , version 1

Citer

Enhui Huang. Active Learning Methods for Interactive Exploration on Large Databases. Computer Science [cs]. Institut Polytechnique de Paris, 2021. English. ⟨NNT : ⟩. ⟨tel-03339951v1⟩
248 Consultations
201 Téléchargements

Partager

Gmail Facebook X LinkedIn More