Divide-and-Conquer Learning by Anchoring a Conical Hull
Tianyi Zhou, Jeffrey A. Bilmes, Carlos Guestrin

Citation
Tianyi Zhou, Jeffrey A. Bilmes, Carlos Guestrin. "Divide-and-Conquer Learning by Anchoring a Conical Hull". Neural Information Processing Systems Conference (NIPS), December, 2014.

Abstract
We reduce a broad class of fundamental machine learning problems, usually addressed by EM or sampling, to the problem of finding the $k$ extreme 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 independently by any existing solver. For the 2D sub-problem, we instead 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 inside other algorithms to check whether a point is covered in a conical hull, and thus improves algorithm design in multiple dimensions by significant speedup. 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.

 Citation formats
• HTML
Tianyi Zhou, Jeffrey A. Bilmes, Carlos Guestrin. <a
href="http://www.terraswarm.org/pubs/421.html"
>Divide-and-Conquer Learning by Anchoring a Conical
Hull</a>, Neural Information Processing Systems
Conference (NIPS), December, 2014.
• Plain text
Tianyi Zhou, Jeffrey A. Bilmes, Carlos Guestrin.
"Divide-and-Conquer Learning by Anchoring a Conical
Hull". Neural Information Processing Systems Conference
(NIPS), December, 2014.
• BibTeX
@inproceedings{ZhouBilmesGuestrin14_DivideandConquerLearningByAnchoringConicalHull,
author = {Tianyi Zhou and Jeffrey A. Bilmes and Carlos
Guestrin},
title = {Divide-and-Conquer Learning by Anchoring a Conical
Hull},
booktitle = {Neural Information Processing Systems Conference
(NIPS)},
month = {December},
year = {2014},
abstract = {We reduce a broad class of fundamental machine
learning problems, usually addressed by EM or
sampling, to the problem of finding the $k$
extreme 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 independently by
any existing solver. For the 2D sub-problem, we
instead 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 inside other algorithms to check
whether a point is covered in a conical hull, and