Parallel Traversal of Large Ensembles of Decision Trees
Open Access
- 9 August 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 30 (9) , 2075-2089
Abstract
Machine-learnt models based on additive ensembles of regression trees are currently deemed the best solution to address complex classification, regression, and ranking tasks. The deployment of such models is computationally demanding: to compute the final prediction, the whole ensemble must be traversed by accumulating the contributions of all its trees. In particular, traversal cost impacts applications where the number of candidate items is large, the time budget available to apply the learnt model to them is limited, and the users' expectations in terms of quality-of-service is high. Document ranking in web search, where sub-optimal ranking models are deployed to find a proper trade-off between efficiency and effectiveness of query answering, is probably the most typical example of this challenging issue. This paper investigates multi/many-core parallelization strategies for speeding up the traversal of large ensembles of regression trees thus obtaining machine-learnt models that are, at the same time, effective, fast, and scalable. Our best results are obtained by the GPU-based parallelization of the state-of-the-art algorithm, with speedups of up to 102.6x.Keywords
Funding Information
- BIGDATAGRAPES (780751)
This publication has 19 references indexed in Scilit:
- QuickScorer2015
- CURFIL: Random Forests for Image Labeling on GPU2015
- Practical Lessons from Predicting Clicks on Ads at Facebook2014
- Cache-conscious runtime optimization for ranking ensembles2014
- Runtime Optimizations for Tree-Based Machine Learning ModelsIEEE Transactions on Knowledge and Data Engineering, 2013
- Adapting boosting for information retrieval measuresInformation Retrieval Journal, 2009
- Learning to Rank for Information RetrievalFoundations and Trends® in Information Retrieval, 2009
- An analytical model for a GPU architecture with memory-level and thread-level parallelism awarenessACM SIGARCH Computer Architecture News, 2009
- Cumulated gain-based evaluation of IR techniquesACM Transactions on Information Systems, 2002
- Greedy function approximation: A gradient boosting machine.The Annals of Statistics, 2001