Web-Search Ranking with Initialized Gradient Boosted Regression Trees

Ananth Mohan, Zheng Chen, Kilian Q. WeinbergerYahoo! Learning to Rank Challenge 2011 · OpenReview

Abstract: In May 2010 Yahoo! Inc. hosted the Learning to Rank Challenge. This paper summarizes the approach by the highly placed team Washington University in St. Louis. We investigate Random Forests (RF) as a robust baseline and introduce Initialized Gradient Boosted Regression Trees (iGBRT), a hybrid approach that uses RF to initialize the boosting process. By combining the stability of Random Forests with the refining power of Boosting—and treating ranking as a classification task—we achieved state-of-the-art results on industry-standard datasets using only a single desktop computer.

Introduction

In web search, Learning to Rank (LTR) determines the optimal ordering of documents for a given query. The industry standard has long been Gradient Boosted Regression Trees (GBRT). Despite its power, GBRT suffers from two primary weaknesses: sensitivity to hyperparameter tuning (learning rate and iterations) and a reliance on zero-initialization. If the initial gradient steps are suboptimal, the model may fail to reach a global minimum.

Representing Washington University in St. Louis during the 2010 Yahoo! Learning to Rank Challenge, our team sought a lightweight, robust algorithm capable of outperforming large-scale server clusters while remaining efficient enough to train on a single machine.

Methods: The iGBRT Framework

Our strategy centered on three innovations: utilizing Random Forests as a baseline, initializing GBRT with those forests, and reframing ranking as a classification problem.

Initialized GBRT (iGBRT)

Unlike standard GBRT, which starts from a "blank slate" (zero), iGBRT uses a pre-trained Random Forest to provide a "warm start." Random Forests are parallel ensembles that are famously resistant to overfitting and require minimal tuning. By using the RF's predictions as the starting point, the subsequent boosting iterations can focus on refining an already strong solution rather than exploring the entire search space from scratch.

Algorithm 3: The iGBRT process initializes residuals using a Random Forest (F) before performing iterative boosting updates.

Classification over Regression

While LTR models typically use regression to predict continuous relevance scores, we argue for a classification-based approach. Since relevance labels are discrete (e.g., 0 to 4), we trained multiple binary classifiers to predict the probability of a document belonging to each relevance tier. This approach consistently outperformed standard regression and allowed us to derive a new mathematical upper bound for the Expected Reciprocal Rank (ERR) metric.

Experimental Setup

We evaluated our approach on two major benchmarks:

  • Yahoo! Learning to Rank Challenge: Two massive datasets (Set 1 and Set 2) with up to 700 features per query-document pair.
  • Microsoft MSLR-WEB: A public five-fold dataset used to verify consistency across different data distributions.

Key Results

The iGBRT model demonstrated superior accuracy and robustness compared to standalone RF and GBRT models. On Yahoo Set 1, iGBRT (Classification) achieved an ERR of 0.46360, significantly outperforming standard GBRT (0.45448). This performance would have secured 11th place in the original Yahoo competition—a remarkable result given our limited computational resources.

Performance metrics (RMSE, NDCG, ERR) for iGBRT over 1000 iterations. Note how the model starts near the RF baseline (black line) and refines the results further.

As shown in the figure above, the initialization allows the model to start at a high performance level (the black line representing the RF baseline). The subsequent boosting iterations (colored lines representing different learning rates $\alpha$) then refine these predictions. Notably, iGBRT is much less sensitive to the specific choice of learning rate than standard GBRT.

Conclusion and Future Work

The iGBRT approach proves that intelligent initialization can bridge the gap between parallel and sequential ensemble methods. While iGBRT requires more training time than a single model (taking approximately 842 minutes for the classification task on a single 8-core desktop), its efficiency and accuracy make it a viable alternative to massive distributed systems. Future work will focus on tightening the theoretical bounds between classification error and ERR, as well as developing more sophisticated methods for handling missing features in web-scale data.

Summary updated

Abstract

In May 2010 Yahoo! Inc. hosted the Learning to Rank Challenge. This paper summarizes the approach by the highly placed team Washington University in St. Louis. We investigate Random Forests (RF) as...
BibTeX
@inproceedings{mohan2011web,
  author = {Ananth Mohan and Zheng Chen and Kilian Q. Weinberger},
  title = {{Web-Search Ranking with Initialized Gradient Boosted Regression Trees}},
  booktitle = {Yahoo! Learning to Rank Challenge},
  year = {2011},
  url = {https://openreview.net/forum?id=30kj3RklUd},
}
Figure