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.

Electronic downloads

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
                  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

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.