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:
Click to access 1406.5752v1.pdf
Code will be released later, but you will find the method is super-easy to implement.
Tianyi Zhou's Research Blog 