"MapReduce is Good Enough" by Twitter scientist

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

by Peteris • 14 years ago

36 29 14 years ago

arxiv.org

batgaijin2• 14 years ago

Funny how Twitter happens to have the guy who invented Storm...

heretohelp2• 14 years ago

On that note, what are the viable alternatives?

All I'm really aware of are Google Proprietary Magic™ (motherfuckers. I want colossus baaaaad), CFS from DataStax, Storm (sorta-not-really?), and Spark.

chad_walters• 14 years ago

There is also S4: http://incubator.apache.org/s4/

bunderbunder2• 14 years ago

Sector/Sphere is what the Sloan Digital Sky Survey uses.

Instead of supplying map and reduce routines, you implement generic "user defined functions". This gives you some more flexibility about how the work is handled, though if you want to just implement map and reduce UDFs, it supposedly gets better performance than Hadoop.

It's also designed to support distributing work over WANs. I think Hadoop really wants every compute node to be on the same LAN.

rm9995• 14 years ago

I don't quite understand the gradient descent section. How do you parallelize stochastic gradient descent? Each iteration changes theta, so any parallel computations will be computing the wrong gradient. His citation for that section doesn't seem to address this, but I only skimmed that paper so I could be wrong.

bravura• 14 years ago

You are correct that each iteration changes theta. You are also correct that parallel computations will be computing the wrong gradient.

However, this is not bad.

Stochastic gradient descent (non-parallel, simply sequential) also computes the "wrong" gradient. If you compute the gradient over the entire example set, you get the "true" gradient.

Nonetheless, SGD (stochastic gradient descent) converges faster than batch gradient descent, because the cost of each update is cheaper (one example vs. all example gradient computation). More importantly, doing a stochastic gradient descent sometimes leads to finding better local optimum. Batch tends to get you into easy-to-find local optimum, and you have no stochasticity that temporarily pops you out of a local minimum and allows you to find a better one. (See Lecun paper from 97 or 98, "Efficient Backprop".)

[edit: I initially wrote the following: "So computing a stochastic gradient over each example in parallel, and them aggregating them, isn't necessarily a bad idea. It's particularly a good idea when you are operating over zipf-ian sparse distributions, like natural language inputs, where many words will be quite rare and infrequently updated in a sequential SGD approach."

Jimmy Lin presents that approach, but points out that the aggregator step is a bottleneck. So, as pointed out by iskander's child comment, each mapper trains SGD on a subset of the examples, and the trained models are aggregated into an ensemble. Thank you for the correction. The point stands that stochastic updates can give superior generalization accuracy to batch updates.]

iskander5• 14 years ago

>So computing a stochastic gradient over each example in parallel, and them aggregating them, isn't necessarily a bad idea.

Wait a minute, I don't think that's what the paper is suggesting. The communication costs of aggregating every micro-step of SGD would be extreme. I think Jimmy Lin is saying you should partition the data, train one model per partition using SGD, and then combine the models in an ensemble.

rm9995• 14 years ago

I still don't get how it's parallelized, what's the reduce step? Is it averaging all the gradients from the maps? If so, that seems like what you were originally saying from your edit (and sounds like the functional equivalent of batch gradient descent).

iskander5• 14 years ago

He doesn't! Each mapper trains a model using stochastic gradient descent on a subset of the data and they are then combined into an ensemble.

A more sophisticated alternative is the Terascale Learning Algorithm (http://www.slideshare.net/pauldix/terascale-learning) from John Langford & friends.

rm9995• 14 years ago

I used to do a cheap man's version of this for neural networks: train many models in parallel on subsets of my data and then choose the one with the best validation performance (I avoided ensembles for speed reasons). But I often found with good model parameters and good quality data most of the models came out very similarly, except a few unlucky ones who found bad local minima. So I usually just downsampled the hell out of my data and built one or two models.

elchief• 14 years ago

But dremel...

npguy• 14 years ago

What are the author's thoughts on Dremel?

shin_lao4• 14 years ago

I have a naive question regarding MapReduce.

I tend to observe that MapReduce is often used to do "search requests" that would be more easily answered with indexes.

Am I missing something?

johngibbon3• 14 years ago

Where does the index come from?

shin_lao4• 14 years ago

Indexing can be done on the fly, when adding or modifying entries.

lmm• 14 years ago

Even leaving aside the cost of storing an index, if you're only going to use that dataset for a small number of queries then it's cheaper to just perform them directly rather than construct an index first. As the paper points out at the end, Hadoop is fundamentally batchy; it works best when you have discrete chunks of data (e.g. weekly) and you want to reduce each one into some summarized form, then never use the raw data again.

bunderbunder2• 14 years ago

The major search engines are using map/reduce to build the indexes that searches are run against.

"MapReduce is Good Enough" by Twitter scientist

Related Stories