Rank Aggregation for Non-stationary Data Streams
Loading...
Identifiers
Publication date
2021-09-11
Advisors
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Citations
Export
Abstract
The problem of learning over non-stationary ranking streams arises naturally, particularly in recommender systems. The rankings represent the preferences of a population, and the non-stationarity means that the distribution of preferences changes over time. We propose an algorithm that learns the current distribution of ranking in an online manner. The bottleneck of this process is a rank aggregation problem. We propose a generalization of the Borda algorithm for non-stationary ranking streams. As a main result, we bound the minimum number of samples required to output the ground truth with high probability. Besides, we show how the optimal parameters are set. Then, we generalize the whole family of weighted voting rules (the family to which Borda belongs) to situations in which some rankings are more reliable than others. We show that, under mild assumptions, this generalization can solve the problem of rank aggregation over non-stationary data streams.
Description
Publisher Copyright: © 2021, Springer Nature Switzerland AG.
Keywords
Preference learning , Rank aggregation , Borda , Evolving preferences , Voting , Concept drift , Preference learning , Rank aggregation , Borda , Evolving preferences , Voting , Concept drift , Theoretical Computer Science , General Computer Science , Funding Info , This work is partially funded by the Industrial Chair “Data science & Artificial Intelligence for Digitalized Industry & Services” from Telecom Paris (France), _x000D_ the Basque Government through the BERC 2018–2021 and the Elkartek program (KK-2018/00096, KK-2020/00049), _x000D_ and by the Spanish Government excellence accreditation Severo Ochoa SEV-2013-0323 (MICIU) and the project TIN2017-82626-R (MINECO). _x000D_ J. Del Ser also acknowledges funding support from the Basque Government (Consolidated Research Gr. MATHMODE, IT1294-19). , This work is partially funded by the Industrial Chair “Data science & Artificial Intelligence for Digitalized Industry & Services” from Telecom Paris (France), _x000D_ the Basque Government through the BERC 2018–2021 and the Elkartek program (KK-2018/00096, KK-2020/00049), _x000D_ and by the Spanish Government excellence accreditation Severo Ochoa SEV-2013-0323 (MICIU) and the project TIN2017-82626-R (MINECO). _x000D_ J. Del Ser also acknowledges funding support from the Basque Government (Consolidated Research Gr. MATHMODE, IT1294-19).
Type
Citation
Irurozki , E , Perez , A , Lobo , J & Del Ser , J 2021 , Rank Aggregation for Non-stationary Data Streams . in N Oliver , F Pérez-Cruz , S Kramer , J Read & J A Lozano (eds) , unknown . vol. 12977 , 0302-9743 , Springer , pp. 297-313 , European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2021 , Virtual, Online , 13/09/21 . https://doi.org/10.1007/978-3-030-86523-8_18
conference
conference