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.
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.
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