Parallel Traversal of Large Ensembles of Decision Trees
| Autor: | Franco Maria Nardini, Claudio Lucchese, Salvatore Orlando, Raffaele Perego, Rossano Venturini, Nicola Tonellotto, Francesco Lettich |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Decision Tree Ensembles
Data structures GPUs Computer science Decision tree 02 engineering and technology Machine learning computer.software_genre Electronic mail SIMD Ranking (information retrieval) Data modeling Parallel Algorithms 0202 electrical engineering electronic engineering information engineering Learning-to-Rank NUMA multiprocessors Efficient Machine Learning 020203 distributed computing Data models Regression tree analysis Settore INF/01 - Informatica business.industry Data structure Tree traversal Computational Theory and Mathematics Ranking Hardware and Architecture Signal Processing Artificial intelligence business Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni computer |
| Zdroj: | IEEE Transactions on Parallel and Distributed Systems IEEE transactions on parallel and distributed systems 30 (2019): 2075–2089. doi:10.1109/TPDS.2018.2860982 info:cnr-pdr/source/autori:Lettich F.; Lucchese C.; Nardini F.M.; Orlando S.; Perego R.; Tonellotto N.; Venturini R./titolo:Parallel Traversal of Large Ensembles of Decision Trees/doi:10.1109%2FTPDS.2018.2860982/rivista:IEEE transactions on parallel and distributed systems (Print)/anno:2019/pagina_da:2075/pagina_a:2089/intervallo_pagine:2075–2089/volume:30 |
| DOI: | 10.1109/TPDS.2018.2860982 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|