Timezone: »

 
Poster
Flattening a Hierarchical Clustering through Active Learning
Fabio Vitale · Anand Rajagopalan · Claudio Gentile

Thu Dec 12 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #5
in Algorithms -- Active Learning »

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 {\em 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.

Keywords: Learning Theory · Active Learning · Algorithms · Algorithms -> Clustering; Algorithms -> Semi-Supervised Learning; Theory
[ Paper]  [ Slides] 

Author Information

Fabio Vitale (University of Lille - INRIA Lille (France))
Anand Rajagopalan (Google)
Claudio Gentile (Google Research)

More from the Same Authors