Timezone: »

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

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.

Author Information

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

More from the Same Authors