Parallel boosted regression trees for web search ranking
Published 28 March 2011
Stephen Tyree, Kilian Q. Weinberger, Kunal Agrawal, Jennifer Paykin
Citations164
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A novel method for parallelizing the training of GBRT, which parallelizes the construction of the individual regression trees and operates using the master-worker paradigm, and demonstrates that the loss in accuracy induced due to the histogram approximation in the regression tree creation can be compensated for through slightly deeper trees.
Abstract
Gradient Boosted Regression Trees (GBRT) are the current state-of-the-art learning paradigm for machine learned web-search ranking - a domain notorious for very large data sets. In this paper, we propose a novel method for parallelizing the training of GBRT. Our technique parallelizes the construction of the individual regression trees and operates using the master-worker paradigm as follows. The data are partitioned among the workers. At each iteration, the worker summarizes its data-partition using histograms. The master processor uses these to build one layer of a regression tree, and then sends this layer to the workers, allowing the workers to build histograms for the next layer. Our algorithm carefully orchestrates overlap between communication and computation to achieve good performance.
Keywords
Computer Science
Machine LearningRandom Forests
126,192 Citations2001Leo Breiman
Internal estimates monitor error, strength, and correlation and these are used to show the response to increasing the number of features used in the forest, and are also applicable to regression.
The Annals of StatisticsGreedy function approximation: A gradient boosting machine.
28,973 Citations2001Jerome H. Friedman
A general gradient descent boosting paradigm is developed for additive expansions based on any fitting criterion, and specific algorithms are presented for least-squares, least absolute deviation, and Huber-M loss functions for regression, and multiclass logistic likelihood for classification.
BiometricsClassification and Regression Trees.
23,841 Citations1984Alexander Gordon, Leo Breiman +3 more
ACM Transactions on Information SystemsCumulated gain-based evaluation of IR techniques
4,634 Citations2002Kalervo Järvelin, Jaana Kekäläinen
This article proposes several novel measures that compute the cumulative gain the user obtains by examining the retrieval result up to a given ranked position, and test results indicate that the proposed measures credit IR methods for their ability to retrieve highly relevant documents and allow testing of statistical significance of effectiveness differences.
Optimizing search engines using clickthrough data
3,898 Citations2002Thorsten Joachims
The goal of this paper is to develop a method that utilizes clickthrough data for training, namely the query-log of the search engine in connection with the log of links the users clicked on in the presented ranking.
Learning to rank using gradient descent
2,759 Citations2005Chris Burges, Tal Shaked +5 more
RankNet is introduced, an implementation of these ideas using a neural network to model the underlying ranking function, and test results on toy data and on data from a commercial internet search engine are presented.
Learning to rank
1,917 Citations2007Zhe Cao, Tao Qin +3 more
It is proposed that learning to rank should adopt the listwise approach in which lists of objects are used as 'instances' in learning, and introduces two probability models, respectively referred to as permutation probability and top k probability, to define a listwise loss function for learning.
From RankNet to LambdaRank to LambdaMART: An Overview
1,028 Citations2010Christopher J. C. Burges
RankNet, LambdaRank, and LambdaMART have proven to be very successful algorithms for solving real world ranking problems and the details are spread across several papers and reports, so here is a self-contained, detailed and complete description of them.
Expected reciprocal rank for graded relevance
831 Citations2009Olivier Chapelle, Donald Metlzer +2 more
This work presents a new editorial metric for graded relevance which overcomes this difficulty and implicitly discounts documents which are shown below very relevant documents and calls it Expected Reciprocal Rank (ERR).
SPRINT: A Scalable Parallel Classifier for Data Mining
781 Citations1996John Shafer, Rakesh Agrawal +1 more
A new decision-tree-based classification algorithm, called SPRINT, is presented that removes all of the memory restrictions, and is fast and scalable, and designed to be easily parallelized, allowing many processors to work together to build a single consistent model.
A support vector method for optimizing average precision
720 Citations2007Yisong Yue, Thomas Finley +2 more
This work presents a general SVM learning algorithm that efficiently finds a globally optimal solution to a straightforward relaxation of MAP, and shows its method to produce statistically significant improvements in MAP scores.
Machine LearningMultiBoosting: A Technique for Combining Boosting and Wagging
699 Citations2000Geoffrey I. Webb
MultiBoosting is an extension to the highly successful AdaBoost technique for forming decision committees that is able to harness both AdaBoost's high bias and variance reduction with wagging's superior variance reduction.
McRank: Learning to Rank Using Multiple Classification and Gradient Boosting
434 Citations2007Ping Li, Qiang Wu +1 more
This work considers the DCG criterion (discounted cumulative gain), a standard quality measure in information retrieval, and proposes using the Expected Relevance to convert class probabilities into ranking scores.
LETOR: Benchmark Dataset for Research on Learning to Rank for Information Retrieval
419 Citations2007Tie‐Yan Liu, Jun Xu +3 more
This paper has constructed a benchmark dataset referred to as LETOR, derived the LETOR data from the existing data sets widely used in IR, namely, OHSUMED and TREC data and provided the results of several state-ofthe-arts learning to rank algorithms on the data.
Data Mining and Knowledge DiscoveryRainForest—A Framework for Fast Decision Tree Construction of Large Datasets
349 Citations2000Johannes Gehrke, Raghu Ramakrishnan +1 more
This paper presents a unifying framework called Rain Forest for classification tree construction that separates the scalability aspects of algorithms for constructing a tree from the central features that determine the quality of the tree.
Stochastic gradient boosted distributed decision trees
330 Citations2009Jerry Ye, Jyh-Herng Chow +2 more
Two different distributed methods that generates exact stochastic GBDT models are presented, the first is a MapReduce implementation and the second utilizes MPI on the Hadoop grid environment.
SoftRank
326 Citations2008Michael Taylor, John Guiver +2 more
This work presents a new family of training objectives that are derived from the rank distributions of documents, induced by smoothed scores, called SoftRank, and focuses on a smoothed approximation to Normalized Discounted Cumulative Gain (NDCG), called SoftNDCG.
Proceedings of the VLDB EndowmentPLANET
268 Citations2009Biswanath Panda, Joshua S. Herbach +2 more
This paper describes PLANET: a scalable distributed framework for learning tree models over large datasets, and shows how this framework supports scalable construction of classification and regression trees, as well as ensembles of such models.
Mining Very Large Databases with Parallel Processing
205 Citations2000Alex A. Freitas, Simon Lavington
Mining Very Large Databases with Parallel Processing addresses the problem of large-scale data mining, describing advances in the integration of three computer science areas, namely: "intelligent" (machine learning-based) data mining techniques; relational databases and parallel processing.
Information RetrievalGradient descent optimization of smoothed information retrieval metrics
205 Citations2009Olivier Chapelle, Mingrui Wu
This work proposes an algorithm which aims at directly optimizing popular measures such as the Normalized Discounted Cumulative Gain and the Average Precision, to minimize a smooth approximation of these measures with gradient descent.
A General Boosting Method and its Application to Learning Ranking Functions for Web Search
185 Citations2007Zhaohui Zheng, Hongyuan Zha +4 more
This work presents a general boosting method extending functional gradient boosting to optimize complex loss functions that are encountered in many machine learning problems, based on optimization of quadratic upper bounds of the loss functions.
A Streaming Parallel Decision Tree Algorithm
139 Citations2010Yael Ben‐Haim, Elad Tom-Tov
Data Mining and Knowledge DiscoveryParallel Formulations of Decision-Tree Classification Algorithms
110 Citations1999Anurag Srivastava, Eui-Hong Han +2 more
This paper describes two basic parallel formulations of classification decision tree learning algorithm based on induction and proposes a hybrid method that employs the good features of these methods.
Journal of Machine Learning ResearchA Streaming Parallel Decision Tree Algorithm
92 Citations2010Ben-HaimYael, Tom-TovElad
The algorithm is executed in a distributed environment and is especially designed for classifying large data sets and streaming data and is empirically shown to be as accurate as a standard decision tree classifier, while being scalable for processing of streaming data on multiple processors.
Distributed and Parallel DatabasesBoosting Algorithms for Parallel and Distributed Learning
91 Citations2002Aleksandar Lazarević, Zoran Obradović
A framework for parallel and distributed boosting algorithms intended for efficient integrating specialized classifiers learned over very large, distributed and possibly heterogeneous databases that cannot fit into main computer memory is proposed.
Kluwer Academic Publishers eBooksParallel Formulations of Decision-Tree Classification Algorithms
59 Citations2006Anurag Srivastava, Eui-Hong Han +2 more
Lecture notes in computer scienceParallel Implementation of Decision Tree Learning Algorithms
27 Citations2001Nuno Amado, João Gama +1 more
A new parallel implementation of the C4.5 decision tree construction algorithm is described and some experimental results are presented that can be used to predict the expected behavior of the algorithm.
BagBoo
24 Citations2010Dmitry Pavlov, Alexey Gorodilov +1 more
It is demonstrated that while impressive experimental evaluation results are presented here in the context of regression trees, the hybrid BagBoo model is applicable to other domains, such as classification, and base training models.
Lecture notes in computer scienceParallel induction algorithms for data mining
21 Citations1997John Darlington, Yi -ke Guo +2 more
Preliminary results on experiments in parallelising C4.5, a classification-rule learning system using decision-trees as a model representation, which has been used as a base model for investigating methods for parallelising induction algorithms are presented.
A New Framework for Distributed Boosting Algorithm
9 Citations2007Nguyen Thi Van Uyen, Tae Choong Chung
A new framework for building boosting classifier on distributed databases to utilize the parallelism of distributed databases and the accuracy of the proposed method is almost equal to the accuracy when applying boosting algorithm to the whole dataset.