Query-level Early Exit for Additive Learning-to-Rank Ensembles

• URL: http://arxiv.org/abs/2004.14641v1
• Date: Thu, 30 Apr 2020 08:59:45 GMT
• Title: Query-level Early Exit for Additive Learning-to-Rank Ensembles
• Authors: Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, Salvatore Trani
• Abstract summary: Search engine ranking pipelines are commonly based on large ensembles of machine-learned decision trees. In this paper, we investigate the novel problem of textitquery-level early exiting We show that query-level early exiting achieves an overall gain of up to 7.5% in terms of NDCG@10 with a speedup of the scoring process of up to 2.2x.
• Score: 14.240566571342924
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Search engine ranking pipelines are commonly based on large ensembles of machine-learned decision trees. The tight constraints on query response time recently motivated researchers to investigate algorithms to make faster the traversal of the additive ensemble or to early terminate the evaluation of documents that are unlikely to be ranked among the top-k. In this paper, we investigate the novel problem of \textit{query-level early exiting}, aimed at deciding the profitability of early stopping the traversal of the ranking ensemble for all the candidate documents to be scored for a query, by simply returning a ranking based on the additive scores computed by a limited portion of the ensemble. Besides the obvious advantage on query latency and throughput, we address the possible positive impact of query-level early exiting on ranking effectiveness. To this end, we study the actual contribution of incremental portions of the tree ensemble to the ranking of the top-k documents scored for a given query. Our main finding is that queries exhibit different behaviors as scores are accumulated during the traversal of the ensemble and that query-level early stopping can remarkably improve ranking quality. We present a reproducible and comprehensive experimental evaluation, conducted on two public datasets, showing that query-level early exiting achieves an overall gain of up to 7.5% in terms of NDCG@10 with a speedup of the scoring process of up to 2.2x.

Related papers

• JudgeRank: Leveraging Large Language Models for Reasoning-Intensive Reranking [81.88787401178378]
  We introduce JudgeRank, a novel agentic reranker that emulates human cognitive processes when assessing document relevance. We evaluate JudgeRank on the reasoning-intensive BRIGHT benchmark, demonstrating substantial performance improvements over first-stage retrieval methods. In addition, JudgeRank performs on par with fine-tuned state-of-the-art rerankers on the popular BEIR benchmark, validating its zero-shot generalization capability.
  arXiv  Detail & Related papers  (2024-10-31T18:43:12Z)
• Generalized Contrastive Learning for Multi-Modal Retrieval and Ranking [2.5238707656136694]
  We propose Generalized Contrastive Learning for Multi-Modal Retrieval and Ranking (GCL) GCL is designed to learn from fine-grained rankings beyond binary relevance scores. Our results show that GCL achieves a 94.5% increase in NDCG@10 for in-domain and 26.3 to 48.8% increases for cold-start evaluations.
  arXiv  Detail & Related papers  (2024-04-12T15:30:03Z)
• The Surprising Effectiveness of Rankers Trained on Expanded Queries [4.874071145951159]
  We improve the ranking performance of hard or difficult queries without compromising the performance of other queries. We combine relevance scores from the specialized ranker and the base ranker, along with a query performance score estimated for each query. In our experiments on the DL-Hard dataset, we find that a principled query performance based scoring method offers a significant improvement of up to 25% on the passage ranking task.
  arXiv  Detail & Related papers  (2024-04-03T09:12:22Z)
• Can Query Expansion Improve Generalization of Strong Cross-Encoder Rankers? [72.42500059688396]
  We show that it is possible to improve the generalization of a strong neural ranker, by prompt engineering and aggregating the ranking results of each expanded query via fusion. Experiments on BEIR and TREC Deep Learning show that the nDCG@10 scores of both MonoT5 and RankT5 following these steps are improved.
  arXiv  Detail & Related papers  (2023-11-15T18:11:41Z)
• Regularization-Based Methods for Ordinal Quantification [49.606912965922504]
  We study the ordinal case, i.e., the case in which a total order is defined on the set of n>2 classes. We propose a novel class of regularized OQ algorithms, which outperforms existing algorithms in our experiments.
  arXiv  Detail & Related papers  (2023-10-13T16:04:06Z)
• Enhanced Training of Query-Based Object Detection via Selective Query Recollection [35.3219210570517]
  This paper investigates a phenomenon where query-based object detectors mispredict at the last decoding stage while predicting correctly at an intermediate stage. We design and present Selective Query Recollection, a simple and effective training strategy for query-based object detectors.
  arXiv  Detail & Related papers  (2022-12-15T02:45:57Z)
• ReAct: Temporal Action Detection with Relational Queries [84.76646044604055]
  This work aims at advancing temporal action detection (TAD) using an encoder-decoder framework with action queries. We first propose a relational attention mechanism in the decoder, which guides the attention among queries based on their relations. Lastly, we propose to predict the localization quality of each action query at inference in order to distinguish high-quality queries.
  arXiv  Detail & Related papers  (2022-07-14T17:46:37Z)
• Frequent Itemset-driven Search for Finding Minimum Node Separators in Complex Networks [61.2383572324176]
  We propose a frequent itemset-driven search approach, which integrates the concept of frequent itemset mining in data mining into the well-known memetic search framework. It iteratively employs the frequent itemset recombination operator to generate promising offspring solution based on itemsets that frequently occur in high-quality solutions. In particular, it discovers 29 new upper bounds and matches 18 previous best-known bounds.
  arXiv  Detail & Related papers  (2022-01-18T11:16:40Z)
• Heuristic Search for Rank Aggregation with Application to Label Ranking [16.275063634853584]
  We propose an effective hybrid evolutionary ranking algorithm to solve the rank aggregation problem. The algorithm features a semantic crossover based on concordant pairs and a late acceptance local search reinforced by an efficient incremental evaluation technique. Experiments are conducted to assess the algorithm, indicating a highly competitive performance on benchmark instances.
  arXiv  Detail & Related papers  (2022-01-11T11:43:17Z)
• RnG-KBQA: Generation Augmented Iterative Ranking for Knowledge Base Question Answering [57.94658176442027]
  We present RnG-KBQA, a Rank-and-Generate approach for KBQA. We achieve new state-of-the-art results on GrailQA and WebQSP datasets.
  arXiv  Detail & Related papers  (2021-09-17T17:58:28Z)
• Heuristic Rank Selection with Progressively Searching Tensor Ring Network [25.003013285907524]
  Ring Networks (TRNs) have been applied in deep networks, achieving remarkable successes in compression ratio and accuracy. We propose a novel progressive genetic algorithm named Progressively Searching Ring Network Search (PSTRN), which has the ability to find optimal rank precisely and efficiently. Our method is validated on public benchmarks like MNIST, CIFAR10/100, UCF11 and HMDB51, achieving the state-of-the-art performance.
  arXiv  Detail & Related papers  (2020-09-22T14:44:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.