Many well-known machine learning methods aim to draw a line between two classes. However, in our recently accepted **NIPS 2014 paper** “**Divide-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:

http://arxiv.org/pdf/1406.5752v1.pdf

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

### Like this:

Like Loading...

*Related*

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