Flattening a Hierarchical Clustering through Active Learning - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2019

Flattening a Hierarchical Clustering through Active Learning

Résumé

We investigate active learning by pairwise similarity over the leaves of trees originating from hierarchical clustering procedures. In the realizable setting, we provide a full characterization of the number of queries needed to achieve perfect reconstruction of the tree cut. In the non-realizable setting, we rely on known important-sampling procedures to obtain regret and query complexity bounds. Our algorithms come with theoretical guarantees on the statistical error and, more importantly, lend themselves to linear-time implementations in the relevant parameters of the problem. We discuss such implementations, prove running time guarantees for them, and present preliminary experiments on real-world datasets showing the compelling practical performance of our algorithms as compared to both passive learning and simple active learning baselines.
Fichier principal
Vignette du fichier
1906.09458.pdf (825.64 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02376981 , version 1 (22-11-2019)

Identifiants

  • HAL Id : hal-02376981 , version 1

Citer

Fabio Vitale, Anand Rajagopalan, Claudio Gentile. Flattening a Hierarchical Clustering through Active Learning. Conference on Neural Information Processing Systems, Dec 2019, Vancouver, Canada. ⟨hal-02376981⟩
44 Consultations
48 Téléchargements

Partager

Gmail Facebook X LinkedIn More