Skip to Main content Skip to Navigation
Conference papers

Flattening a Hierarchical Clustering through Active Learning

Fabio Vitale 1 Anand Rajagopalan 2 Claudio Gentile 2
1 MAGNET - Machine Learning in Information Networks
Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Team Magnet Connect in order to contact the contributor
Submitted on : Friday, November 22, 2019 - 7:24:08 PM
Last modification on : Friday, January 21, 2022 - 3:12:02 AM


Files produced by the author(s)


  • HAL Id : hal-02376981, version 1


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⟩



Les métriques sont temporairement indisponibles