Divide-and-Conquer Learning by Anchoring a Conical Hull

Many well-known machine learning methods aim to draw a line between two classes. However, in our recently accepted NIPS 2014 paperDivide-and-Conquer Learning by Anchoring a Conical Hull“, we reduce lots of fundamental machine learning problems (a broad class of latent variable models, matrix factorization, clustering, etc.) to finding the extreme rays of a conical hull in high dimension. Although this is a combinatorial problem, we can distribute it into several sub-problems in ultra-low dimensions (1D or 2D), solve them in parallel, and combine their solution to get the solution for the original problem.

The primary advantages of this method are

1) A significant improvement on speed, even by single-thread computation, our method can be hundreds to thousands times faster than its major rivals, EM algorithm or Gibbs sampling;

2) A more interpretable model, our method is based on the idea of finding a small subset of real data instances to build the model (i.e., separability assumption), and can embed extra prior knowledge of representative point/pattern in learning. This leads to very close or even better performance than its rivals;

3) It finally makes spectral method (i.e., the method of moments) work! Existing spectral method suffers from inaccurate estimate of moments, and can only be used as a initialization of EM algorithm in practice. The separability assumption plays a role of regularization in our method, and is a powerful cure to the large variance of moment estimator.

All the details you need can be found in our long arxiv version:


Code will be released later, but you will find the method is super-easy to implement.


About tianyizhou

Research Assistant at University Washington, Seattle, Working on Machine Learning & Statistics in MODE lab leaded by Prof. Carlos Guestrin, and MELODI lab leaded by Prof. Jeff Bilmes.
This entry was posted in Tianyi's work and tagged , , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s