Parallel boosted regression trees for web search ranking

Stephen Tyree, Kilian Q. Weinberger, Kunal Agrawal, Jennifer PaykinWWW 2011 · DOI

TL;DR

This paper introduces a novel parallel algorithm for training Gradient Boosted Regression Trees (GBRTs), a state-of-the-art technique for web search ranking. By parallelizing the construction of individual regression trees using a master-worker approach and approximating splits with histograms, they achieve significant speedups on large datasets without substantial loss in ranking accuracy.

What Problem Does This Paper Address?

Web search engines rely on sophisticated ranking functions to order search results. Machine-learned ranking (MLR) has become the dominant paradigm, with Gradient Boosted Regression Trees (GBRTs) being a leading method. However, training GBRTs on massive web-scale datasets is computationally intensive, posing a significant bottleneck. Existing parallelization efforts for boosting often focus on the overall boosting process rather than the construction of individual weak learners (regression trees). This paper addresses the challenge of efficiently training GBRTs on large datasets by proposing a parallel approach that specifically targets the tree construction phase.

Methods

The core of this paper is a novel parallel algorithm for training GBRTs, building upon the master-worker paradigm. Here's a breakdown of their approach:

  • Parallel Tree Construction: Instead of parallelizing the entire boosting process, the authors parallelize the construction of each individual regression tree.
  • Master-Worker Architecture: A master processor coordinates the training, while multiple worker processors handle data partitioning and histogram computation.
  • Data Partitioning: The training data is divided among the workers. Each worker only processes its assigned partition.
  • Histogram-Based Approximation: To reduce communication overhead, workers summarize their data partitions using histograms. These histograms capture essential statistics (number of data points and sum of relevance scores) within bins, allowing the master to approximate the optimal split points for tree nodes. This is a key departure from exact tree construction methods that require full data scans.
  • Layer-by-Layer Tree Building: The master processor uses the aggregated histograms to determine the best split for each leaf node, effectively building one layer of the regression tree at a time. This layer is then sent back to the workers, who use it to update their data partitions for the next iteration.
  • Overlap of Computation and Communication: The algorithm is designed to overlap communication and computation. Workers compute histograms feature by feature and send them to the master while processing subsequent features, minimizing idle time.
  • Limited Depth Trees: The approach is specifically tailored for GBRTs that use shallow regression trees (typically depth 4-6). This is crucial because the communication cost in their histogram-based method grows exponentially with tree depth.

Datasets

The authors evaluated their approach using two prominent web search ranking datasets:

  • Yahoo! Inc.'s Learning to Rank Challenge 2010: This dataset was used in two sets (Set 1 and Set 2), with Set 1 being significantly larger than Set 2.
  • Microsoft's LETOR dataset: Five folds of this dataset were used for evaluation.

These datasets are standard benchmarks for evaluating learning-to-rank algorithms.

Key Insights and Ideas

  • Approximation for Speed: The paper demonstrates that for web search ranking, a slight loss in the accuracy of individual regression trees (due to histogram-based approximations) can be compensated for by using slightly deeper trees or more boosting iterations, without significantly impacting the overall ranking performance. This is a crucial insight that enables efficient parallelization.
  • Communication is Key: The primary bottleneck in parallelizing tree construction is communication. By using histograms to summarize data, the authors drastically reduce the amount of data that needs to be transferred between processors, making the approach scalable.
  • Limited Depth is a Feature, Not a Bug: The algorithm's effectiveness is tied to the use of shallow trees. This is a practical consideration for GBRTs in web search ranking, where very deep trees are often not necessary and can lead to overfitting.
  • Generalizability: The master-worker, data-partitioning approach is inherently generalizable to various parallel architectures, including shared-memory machines, clusters, and potentially cloud environments.

Key Results

  • Significant Speedups: The parallel GBRT (pGBRT) algorithm achieved impressive speedups. On shared-memory machines, they observed near-perfect linear speedups up to 48 cores. On distributed-memory clusters, they achieved speedups of up to 25 with 32 processors.
  • Minimal Accuracy Loss: For the Yahoo datasets, the pGBRT algorithm showed no significant loss in accuracy (ERR and NDCG) compared to the exact GBRT implementation. For the Microsoft LETOR data, a very small reduction in accuracy was observed.
  • Competitive Performance: The pGBRT algorithm, even with its approximate nature, achieved ranking quality competitive with state-of-the-art methods, placing highly in the Yahoo Learning to Rank Challenge leaderboard.
  • Scalability: The approach scales well with data size, and the authors expect even higher speedups on larger datasets.

Limitations and Future Work

  • Accuracy Trade-off: While the accuracy loss is minimal, it is still present. The authors acknowledge that further improvements could be made by using more specialized cost functions or exploring more aggressive speed-accuracy trade-offs in histogram approximation.
  • Master Bottleneck: In the current master-worker setup, the master can become a bottleneck as the number of workers increases. The authors suggest future work to eliminate the master by using pairwise histogram merging among workers.
  • Cloud Environments: Further experiments on cloud platforms are planned to assess performance on non-dedicated machines.
  • Stochastic Approximations: Investigating more aggressive stochastic approximations of histograms for splits is another avenue for future research.

Summary updated

BibTeX
@inproceedings{tyree2011parallel,
  author = {Stephen Tyree and Kilian Q. Weinberger and Kunal Agrawal and Jennifer Paykin},
  title = {{Parallel boosted regression trees for web search ranking}},
  booktitle = {The Web Conference},
  year = {2011},
  doi = {10.1145/1963405.1963461},
}
Figure