Flattening a Hierarchical Clustering through Active Learning

2019/06/22 by Vitale, Fabio, Rajagopalan, Anand, Gentile, Claudio
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1906.09458

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.

Related

• Active Clustering: Robust and Efficient Hierarchical Clustering using Adaptively Selected Similarities
• Efficient Active Algorithms for Hierarchical Clustering
• Adaptive Hierarchical Clustering Using Ordinal Queries
• Bisect and Conquer: Hierarchical Clustering via Max-Uncut Bisection
• Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees