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.

Electronic downloads

• https://www.src.org/library/publication/p072547/. (Link to paper on SRC website.)
• http://arxiv.org/pdf/1406.5752v1

• 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
                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.},
      URL = {http://terraswarm.org/pubs/421.html}
  }
  

Posted by Tianyi Zhou on 3 Nov 2014.
Groups: services