Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Online learning of optimally diverse rankings
KTH.
2018 (English)In: SIGMETRICS 2018 - Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems, Association for Computing Machinery (ACM), 2018, p. 47-49Conference paper, Published paper (Refereed)
Abstract [en]

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 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. This scaling cannot be improved, i.e., LDR is order optimal.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2018. p. 47-49
Keywords [en]
Diversity, Learning to rank, Multi-armed bandits, Online learning
National Category
Other Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-234117DOI: 10.1145/3219617.3219637Scopus ID: 2-s2.0-85052016103ISBN: 9781450358460 (print)OAI: oai:DiVA.org:kth-234117DiVA, id: diva2:1244793
Conference
2018 ACM International Conference on Measurement and Modeling of Computer Systems, SIGMETRICS 2018, Beckman Center, Irvine, United States, 18 June 2018 through 22 June 2018
Note

QC 20180903

Available from: 2018-09-03 Created: 2018-09-03 Last updated: 2018-09-03Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Magureanu, StefanProutiere, Alexandre

Search in DiVA

By author/editor
Magureanu, StefanProutiere, Alexandre
By organisation
KTH
Other Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 33 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf