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

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

Learning to rank  Efficiency  Pruning 

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), vol. 9