Divide-and-Conquer Learning by Anchoring a Conical Hull
Tianyi Zhou · Jeff Bilmes · Carlos Guestrin

Thu Dec 11th 02:00 -- 06:00 PM @ Level 2, room 210D #None
We reduce a broad class of machine learning problems, usually addressed by EM or sampling, to the problem of finding the $k$ extremal rays spanning the conical hull of a data point set. These $k$ ``anchors'' lead to a global solution and a more interpretable model that can even outperform EM and sampling on generalization error. To find the $k$ anchors, we propose a novel divide-and-conquer learning scheme ``DCA'' that distributes the problem to $\mathcal O(k\log k)$ same-type sub-problems on different low-D random hyperplanes, each can be solved by any solver. For the 2D sub-problem, we present a non-iterative solver that only needs to compute an array of cosine values and its max/min entries. DCA also provides a faster subroutine for other methods to check whether a point is covered in a conical hull, which improves algorithm design in multiple dimensions and brings significant speedup to learning. We apply our method to GMM, HMM, LDA, NMF and subspace clustering, then show its competitive performance and scalability over other methods on rich datasets.

Author Information

Tianyi Zhou (University of Washington, Seattle)

Tianyi Zhou is a 6th-year Ph.D student of Paul G. Allen School of Computer Science and Engineering at University of Washington, Seattle, supervised by Jeff Bilmes and Carlos Guestrin. He has worked with Dacheng Tao at University of Technology Sydney and Nanyang Technological University for 4 years before going to UW. His research covers topics in machine learning, natural language processing, statistics, and data analysis. He has published 30+ papers with 1300+ citations at top conferences and journals including NeurIPS, ICML, ICLR, AISTATS, NAACL, ACM SIGKDD, IEEE ICDM, AAAI, IJCAI, IEEE ISIT, Machine Learning Journal (Springer), DMKD (Springer), IEEE TIP, IEEE TNNLS, etc. He is the recipient of the best student paper award at IEEE ICDM 2013.

Jeff Bilmes (University of Washington, Seattle)
Carlos Guestrin (University of Washington)

More from the Same Authors