document: Parallel boosted regression trees for web search ranking 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 . Since this approach is based on data partitioning , and requires a small amount of communication , it generalizes to distributed and shared memory machines , as well as clouds . We present experimental results on both shared memory machines and clusters for two large scale web search ranking data sets . We demonstrate that the loss in accuracy induced due to the histogram approximation in the regression tree creation can be compensated for through slightly deeper trees . As a result , we see no significant loss in accuracy on the Yahoo data sets and a very small reduction in accuracy for the Microsoft LETOR data . In addition , on shared memory machines , we obtain almost perfect linear speed-up with up to about 48 cores on the large data sets . On distributed memory machines , we get a speedup of 25 with 32 processors . Due to data partitioning our approach can scale to even larger data sets , on which one can reasonably expect even higher speedups .
doc_bio_tags: O B I I O B I B O B I I O O O O O O O O O O O O O B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I B O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O