X-CLEaVER: Learning ranking ensembles by growing and pruning trees

Lucchese C., Nardini F. M., Orlando S., Perego R., Silvestri F., Trani S.

Settore INF/01 - Informatica  Efficiency  Efciency  Artificial Intelligence  Theoretical Computer Science  Pruning  Learning to rank  Settore ING-INF/05 - Sistemi di Elaborazione delle Informazioni 

Learning-to-Rank (LtR) solutions are commonly used in large-scale information retrieval systems such as Web search engines, which have to return highly relevant documents in response to user query within fractions of seconds. The most effective LtR algorithms adopt a gradient boosting approach to build additive ensembles of weighted regression trees. Since the required ranking effectiveness is achieved with very large ensembles, the impact on response time and query throughput of these solutions is not negligible. In this article, we propose X-CLEaVER, an iterative meta-algorithm able to build more efcient and effective ranking ensembles. X-CLEaVER interleaves the iterations of a given gradient boosting learning algorithm with pruning and re-weighting phases. First, redundant trees are removed from the given ensemble, then the weights of the remaining trees are fne-tuned by optimizing the desired ranking quality metric. We propose and analyze several pruning strategies and we assess their benefts showing that interleaving pruning and re-weighting phases during learning is more effective than applying a single post-learning optimization step. Experiments conducted using two publicly available LtR datasets show that X-CLEaVER can be successfully exploited on top of several LtR algorithms as it is effective in optimizing the effectiveness of the learnt ensembles, thus obtaining more compact forests that hence are much more efcient at scoring time.

Source: ACM transactions on intelligent systems and technology (Print) 9 (2018). doi:10.1145/3205453

Publisher: Association for Computing Machinery, New York, NY , Stati Uniti d'America

Metrics