Online Learning of Optimally Diverse Rankings

• URL: http://arxiv.org/abs/2109.05899v1
• Date: Mon, 13 Sep 2021 12:13:20 GMT
• Title: Online Learning of Optimally Diverse Rankings
• Authors: Stefan Magureanu, Alexandre Proutiere, Marcus Isaksson, Boxun Zhang
• Abstract summary: We propose an algorithm that efficiently learns the optimal list based on users' feedback only. We show that after $T$ queries, the regret of LDR scales as $O((N-L)log(T))$ where $N$ is the number of all items.
• Score: 63.62764375279861
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Search engines answer users' queries by listing relevant items (e.g. documents, songs, products, web pages, ...). These engines rely on algorithms that learn to rank items so as to present an ordered list maximizing the probability that it contains relevant item. The main challenge in the design of learning-to-rank algorithms stems from the fact that queries often have different meanings for different users. In absence of any contextual information about the query, one often has to adhere to the {\it diversity} principle, i.e., to return a list covering the various possible topics or meanings of the query. To formalize this learning-to-rank problem, we propose a natural model where (i) items are categorized into topics, (ii) users find items relevant only if they match the topic of their query, and (iii) the engine is not aware of the topic of an arriving query, nor of the frequency at which queries related to various topics arrive, nor of the topic-dependent click-through-rates of the items. For this problem, we devise LDR (Learning Diverse Rankings), an algorithm that efficiently learns the optimal list based on users' feedback only. We show that after $T$ queries, the regret of LDR scales as $O((N-L)\log(T))$ where $N$ is the number of all items. We further establish that this scaling cannot be improved, i.e., LDR is order optimal. Finally, using numerical experiments on both artificial and real-world data, we illustrate the superiority of LDR compared to existing learning-to-rank algorithms.

Related papers

• Self-Calibrated Listwise Reranking with Large Language Models [137.6557607279876]
  Large language models (LLMs) have been employed in reranking tasks through a sequence-to-sequence approach. This reranking paradigm requires a sliding window strategy to iteratively handle larger candidate sets. We propose a novel self-calibrated listwise reranking method, which aims to leverage LLMs to produce global relevance scores for ranking.
  arXiv  Detail & Related papers  (2024-11-07T10:31:31Z)
• Large Language Models for Relevance Judgment in Product Search [48.56992980315751]
  High relevance of retrieved and re-ranked items to the search query is the cornerstone of successful product search. We present an array of techniques for leveraging Large Language Models (LLMs) for automating the relevance judgment of query-item pairs (QIPs) at scale. Our findings have immediate implications for the growing field of relevance judgment automation in product search.
  arXiv  Detail & Related papers  (2024-06-01T00:52:41Z)
• Hypergraph Enhanced Knowledge Tree Prompt Learning for Next-Basket Recommendation [50.55786122323965]
  Next-basket recommendation (NBR) aims to infer the items in the next basket given the corresponding basket sequence. HEKP4NBR transforms the knowledge graph (KG) into prompts, namely Knowledge Tree Prompt (KTP), to help PLM encode the Out-Of-Vocabulary (OOV) item IDs. A hypergraph convolutional module is designed to build a hypergraph based on item similarities measured by an MoE model from multiple aspects.
  arXiv  Detail & Related papers  (2023-12-26T02:12:21Z)
• Replace Scoring with Arrangement: A Contextual Set-to-Arrangement Framework for Learning-to-Rank [40.81502990315285]
  Learning-to-rank is a core technique in the top-N recommendation task, where an ideal ranker would be a mapping from an item set to an arrangement. Most existing solutions fall in the paradigm of probabilistic ranking principle (PRP), i.e., first score each item in the candidate set and then perform a sort operation to generate the top ranking list. We propose Set-To-Arrangement Ranking (STARank), a new framework directly generates the permutations of the candidate items without the need for individually scoring and sort operations.
  arXiv  Detail & Related papers  (2023-08-05T12:22:26Z)
• RankFormer: Listwise Learning-to-Rank Using Listwide Labels [2.9005223064604078]
  We propose the RankFormer as an architecture that can jointly optimize a novel listwide assessment objective and a traditional listwise objective. We conduct experiments in e-commerce on Amazon Search data and find the RankFormer to be superior to all baselines offline.
  arXiv  Detail & Related papers  (2023-06-09T10:47:06Z)
• Zero-Shot Listwise Document Reranking with a Large Language Model [58.64141622176841]
  We propose Listwise Reranker with a Large Language Model (LRL), which achieves strong reranking effectiveness without using any task-specific training data. Experiments on three TREC web search datasets demonstrate that LRL not only outperforms zero-shot pointwise methods when reranking first-stage retrieval results, but can also act as a final-stage reranker.
  arXiv  Detail & Related papers  (2023-05-03T14:45:34Z)
• Efficient and Accurate Top-$K$ Recovery from Choice Data [1.14219428942199]
  In some applications such as recommendation systems, the statistician is primarily interested in recovering the set of the top ranked items from a large pool of items. We propose the choice-based Borda count algorithm as a fast and accurate ranking algorithm for top $K$-recovery. We show that the choice-based Borda count algorithm has optimal sample complexity for top-$K$ recovery under a broad class of random utility models.
  arXiv  Detail & Related papers  (2022-06-23T22:05:08Z)
• Query Rewriting via Cycle-Consistent Translation for E-Commerce Search [13.723266150864037]
  We propose a novel deep neural network based approach to query rewriting. We formulate query rewriting into a cyclic machine translation problem. We introduce a novel cyclic consistent training algorithm in conjunction with state-of-the-art machine translation models.
  arXiv  Detail & Related papers  (2021-03-01T06:47:12Z)
• Surprise: Result List Truncation via Extreme Value Theory [92.5817701697342]
  We propose a statistical method that produces interpretable and calibrated relevance scores at query time using nothing more than the ranked scores. We demonstrate its effectiveness on the result list truncation task across image, text, and IR datasets.
  arXiv  Detail & Related papers  (2020-10-19T19:15:50Z)
• Learning to Rank under Multinomial Logit Choice [6.929312022493406]
  Learning the optimal ordering of content is an important challenge in website design. We present theoretical analysis leading to an $Omega(sqrtJT)$ lower bound for the problem, and an $tildeO(sqrtJT)$ upper bound on regret of the UCB algorithm.
  arXiv  Detail & Related papers  (2020-09-07T16:15:12Z)

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.