6
$\begingroup$

I am currently doing my Phd in computational biology at Stanford. I get the data I need to answer the questions I am interested in. The data sets are sometimes "large" and these large problems take longer time periods to solve (a couple of days sometimes).

That being said I was wondering how machine learning on extremely massive data sets works? Suppose google wants to solve $Ax = b$ where $A$ has 10 billion rows, finding any gradients seems prohibitive. If google actually ran these simulations for as long as it takes (my equivalent of a couple of days), the solution maybe worthless before it arrives. This problem will be accentuated while training neural networks or implementing more complicated methods. What are practical solutions to this problem?

I have seen statements like "We pick representative samples...". This is an absurd statement in my opinion because when p >> n, nothing is representative since the systems are under-determined. Any help on what 'representative' in these cases will also help.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ Subsampling is not always absurd, in fact it makes perfect sense for many applications. Just because you have billions of instances, does not mean you need to use all of them to capture the information you want. The law of large numbers applies. Using less data will increase uncertainty, but not necessarily beyond acceptable levels. $\endgroup$
    – Marc Claesen
    Commented Aug 11, 2014 at 7:56
  • $\begingroup$ While that is true, when we are in a high dimensional space, whatever sample size you pick is not going to be "large enough" for the law of large numbers to kick in. It will again essentially be the curse of dimensionality problem. 10 billion samples itself is "not large enough" in some sense, let alone a couple of million $\endgroup$
    – Sid
    Commented Aug 11, 2014 at 8:03
  • 1
    $\begingroup$ So you're dealing with potentially 10 billion rows and p >> n?! $\endgroup$
    – Steve S
    Commented Aug 11, 2014 at 15:15
  • $\begingroup$ Apologies for not being clear. The p>>n was when you have a couple million users sampled. That being said, the law of large numbers will never kick in. If 10 points are required to densely pack a 1-D space, $10^100$ points will be require to densely pack a 100-D space..let alone a couple of million. The law of large numbers will not solve this problem! $\endgroup$
    – Sid
    Commented Aug 11, 2014 at 19:49

4 Answers 4

Reset to default
6
$\begingroup$

I have seen statements like "We pick representative samples...". This is an absurd statement...

I agree with you on this. And I don't think representative sampling is what they do (anymore). My understanding is that they analyse big data with distributed computing, using technology like Hadoop, Spark, and MLLib. I am sure they write their proprietary and complex machine learning / analysis libraries on top of these.

The algorithms for these "distributable" systems are coded differently than how you and I would code them in e.g. R, Matlab or Python. They need to be scalable and parallelisable, which is an issue for some algorithms. MLLib, for instance, currently only supports some very basic algorithms (list available on their website).

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ This is pretty much it. One note though, Google doesn't build on top of Hadoop or Spark. Hadoop is basically a copy of Google's proprietary MapReduce framework. Considering the fact that Google published their framework, we can assume that they have much better solutions now (they wouldn't advertise their own trade secrets). $\endgroup$
    – Marc Claesen
    Commented Aug 11, 2014 at 7:52
  • $\begingroup$ Thank you, this really helps. Just to be clear..does distributable coding mean you give the command inv(A) and the system figures out how to implement inv(A) on this massive system or does it mean that inv(A) is (maybe) out of bounds because of the size of the file in question and you need to find alternative routes to the problem? $\endgroup$
    – Sid
    Commented Aug 11, 2014 at 8:15
  • $\begingroup$ As far as I understand, the approach is "divide and conquer". Different parts of A are kept and processed at different hard-drive or (more optimally) memory locations and then consolidated to give you the exact or approximate answer. Again, it would be good to get a computer scientist's opinion though. $\endgroup$
    – Zhubarb
    Commented Aug 11, 2014 at 8:22
  • 1
    $\begingroup$ @Sid the system will figure out how to formulate a given inv(A) in terms of a map-reduce combination (more info at: en.wikipedia.org/wiki/MapReduce). A very simple (contrived) example is finding the maximum of a huge list: which can be achieved through partitioning the list into smaller sublists, finding the maxima of each sublist and then finding the maximum of the maxima. $\endgroup$
    – Marc Claesen
    Commented Aug 11, 2014 at 8:22
  • 1
    $\begingroup$ H2O is a open sourced framework from 0xdata designed to work with hadoop in scenarios that you mentioned. If you have a hadoop cluster, using H2O is a breeze and you can use R to control H2O. Spark and MLLib as mentioned previously also help. $\endgroup$
    – Arun Jose
    Commented Aug 11, 2014 at 11:56
6
$\begingroup$

Beyond subsampling and divide-and-conquer distributed computing, both important and useful, there are many other ways of solving such problems. To name just a couple, parallel coordinate descent (iterate on each variable independently, combine solutions later), and online methods, like stochastic gradient descent (SGD).

Have a look at https://github.com/JohnLangford/vowpal_wabbit for quite a widely used approach to online learning with SGD. Also Alex Smola has done quite a bit of work on large-scale learning.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Sophia-ml seems relevant here as well. $\endgroup$
    – Jessica Collins
    Commented Aug 11, 2014 at 11:53
3
$\begingroup$

Massively parallel matrix inversion is actually doable with open source software such as MUMPS, although I'm not sure how it would scale to 10bio rows. It's used for large scale finite elements in automotive so it's industrial strength for sure.

As for the class of algorithms used, it's a multifrontal approach (divide the matrix into zones that don't 'interfere' with each other in the sense of cholesky-like outer product updates, solve each part and gather rectangular 'interference' updates). Much more details on the mumps website, http://mumps.enseeiht.fr/ .

Now if you're just doing linear regression, the result will be x = (AtA)-1At b and you can probably parallelize the computation of the covar matrix (AtA) and the error term efficiently to run on different machines and then aggregate the results. This supposes A has only a few columns.

Improve this answer
$\endgroup$
1
$\begingroup$

Thank you all for your comments. Turns out Apache spark does L1 penalized regressions. I found links to training videos here which some of you may find helpful.

Turns out the folk at Google who seriously studied this problem and founded the Map-Reduce architecture were Jeff Dean and Sanjay Ghemawat, both of whom have become silicon-valley rockstars. Jeff Dean has his own Chuck Norris persona!!!

http://www.quora.com/What-are-all-the-Jeff-Dean-facts?share=1

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.