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 (CRIStAL) - 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 metadatas

Cited literature [29 references]  Display  Hide  Download

https://hal.inria.fr/hal-02376981
Contributor : Team Magnet <>
Submitted on : Friday, November 22, 2019 - 7:24:08 PM
Last modification on : Tuesday, November 26, 2019 - 1:36:04 AM

File

1906.09458.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02376981, version 1

Citation

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⟩

Share

Metrics

Record views

37

Files downloads

102