Approaches when learning from huge datasets?

Question

Basically, there are two common ways to learn against huge datasets (when you're confronted by time/space restrictions):

1. Cheating :) - use just a "manageable" subset for training. The loss of accuracy may be negligible because of the law of diminishing returns - the predictive performance of the model often flattens out long before all the training data is incorporated into it.
2. Parallel computing - split the problem into smaller parts and solve each one on a separate machine/processor. You need a parallel version of the algorithm though, but good news is that a lot of common algorithms are naturally parallel: nearest-neighbor, decision trees, etc.

Are there other methods? Is there any rule of thumb when to use each? What are the drawbacks of each approach?

Answer 1

Stream Mining is one answer. It is also called:

• Data Stream Mining
• Online Learning

• Massive Online Learning

  Instead of putting all data set in memory and training from it. They put chunks of it in memory and train classifier/clusters from these stream of chunks. See following links.

• Data_stream_mining from wikipedia.

• MOA: Massive Online Analysis

  • Article
  • Tool, written in Java, able to use weka algorithms
  • Book

• Mining of Massive Datasets Book , From Stanford University. It uses MapReduce as a tool.

• Videos in videolectures.net. Search it similar videos exists in that site.

  • State of the Art in Data Stream Mining
  • Mining Massive Data Sets

Answer 2

Instead of using just one subset, you could use multiple subsets as in mini-batch learning (e.g. stochastic gradient descent). This way you would still make use of all your data.

Answer 3

Ensembles like bagging or blending -- no data is wasted, the problem automagically becomes trivially parallel and there might be significant accuracy/robustness gains.