TL;DR
This paper introduces PLANET, a novel framework for training decision tree ensembles on massive datasets using Google's MapReduce infrastructure. It addresses the challenge of scaling tree learning beyond single-machine memory limits by decomposing the process into parallelizable MapReduce jobs, enabling efficient and robust training on commodity hardware.
What Problem Does This Paper Address?
Training decision trees and their ensembles (like random forests or boosted trees) is a fundamental task in machine learning, widely used for classification and regression. However, as datasets grow to enormous sizes (millions or billions of records), traditional in-memory algorithms become infeasible. Existing parallel tree learning methods often rely on specialized hardware or complex distributed computing architectures. The authors aim to leverage the ubiquitous and scalable MapReduce framework, commonly found in large tech companies, to build production-ready, massively parallel tree learning systems that are simpler to deploy and manage on commodity clusters.
Methods
PLANET frames tree learning as a series of distributed computations executed via MapReduce. The core idea is to manage the tree construction process using a central Controller. This Controller maintains two queues: MapReduceQueue (MRQ) for nodes whose data partitions are too large for memory, and InMemoryQueue (InMemQ) for nodes whose data fits in memory.
The key MapReduce jobs are:
- MR_ExpandNodes: This job takes a set of nodes from MRQ and computes candidate "good splits" for them. It involves a mapper that traverses the current model for each data record and aggregates statistics (sum of values, sum of squared values, count) for potential split points. A reducer then uses these aggregated statistics to evaluate split quality.
- MR_InMemory: For nodes in InMemQ, this job performs in-memory tree induction using a standard greedy algorithm (like Algorithm 1 in the paper).
PLANET employs several optimizations:
- Forward Scheduling: To mitigate MapReduce job setup latency, PLANET proactively sets up subsequent MapReduce jobs while previous ones are still running.
- Fingerprinting: For unordered attributes, string comparisons in predicates were a bottleneck. Fingerprinting (hashing) these strings significantly speeds up tree traversal.
- Equidepth Histograms: For ordered attributes, instead of evaluating every possible split point, PLANET uses pre-computed equidepth histograms to select a representative subset of split points, reducing computation.
The framework supports ensemble learning (bagging and boosting) by extending the Controller's ability to manage multiple tree constructions concurrently or sequentially.
Datasets
The primary dataset used for evaluation is ADCORPUS, derived from Google's sponsored search ads. This dataset is used for predicting "bounce rates" (users returning to the search engine immediately after clicking an ad). It contains approximately 314 million records with a mix of categorical and numerical features, including generalized query and advertiser keywords clustered into about 500 categories. The authors also mention using a sample of 10 million records for comparison with an in-memory GBM implementation.
Key Insights and Ideas
- MapReduce as a Viable Platform for Iterative ML: The paper demonstrates that MapReduce, often seen as batch-oriented, can effectively support iterative machine learning tasks like tree induction, provided the process is carefully decomposed into MapReduce jobs.
- Decoupling Data Size and Computation: By using MRQ and InMemQ, PLANET intelligently routes nodes to either distributed or in-memory computation based on data size, optimizing resource utilization.
- The Power of Forward Scheduling: Reducing job setup latency through forward scheduling is crucial for improving the overall throughput of iterative MapReduce applications.
- Trade-offs for Scalability: PLANET makes deliberate trade-offs, such as using approximate histograms for split point selection and scanning the entire dataset in mappers even if only a subset is needed for a specific node, to achieve simpler implementation and better scalability.
- Commodity Hardware is Sufficient: The success of PLANET on commodity clusters highlights that massive-scale ML is achievable without specialized hardware.
Key Results
- Scalability: PLANET demonstrates good scalability with increasing dataset size and number of machines. Training time increases proportionally with data size, and adding more machines generally decreases training time, though marginal returns are observed beyond a certain point (around 400 machines for their setup).
- MR_InMemory Benefits: Using MR_InMemory for nodes with smaller data partitions significantly reduces training time as tree depth increases, compared to a purely MR_ExpandNodes approach. For example, training a depth-12 tree took much longer without MR_InMemory.
- Ensemble Performance: Figure 5 shows that error rates (variance reduction) decrease as more trees are added to a boosted ensemble, with depth-3 trees converging faster than depth-1 trees.
- Optimization Impact: Fingerprinting unordered attributes provided about a 40% improvement in tree traversal costs.
Limitations and Future Work
- Sampling: The current implementation primarily supports sampling without replacement for ensemble methods. The authors are exploring efficient techniques for sampling with replacement and comparing their impact.
- Split Metrics: PLANET currently uses variance as the split metric for regression trees. The authors plan to extend it to support other metrics.
- Multi-class Classification: The current focus is on binary classification and regression. Extending to multi-class classification is a future direction.
- Incremental Learning: The framework does not currently support incremental learning.
- MapReduce Overhead: While MapReduce is powerful, its startup and teardown costs can be significant bottlenecks for highly iterative processes. The paper discusses optimizations like forward scheduling to mitigate this.
- Unnecessary Data Transfer: Scanning the entire dataset in mappers, even if only a subset is relevant for a node, can lead to unnecessary data transfer. The authors acknowledge this but prioritize system simplicity and existing MapReduce optimizations.
Summary updated