Rank Aggregation for Non-stationary Data Streams

Ekhine Irurozki; Aritz Perez; Jesus Lobo; Javier Del Ser

doi:10.1007/978-3-030-86523-8_18

Rank Aggregation for Non-stationary Data Streams

Ekhine Irurozki
, Aritz Perez
, Jesus Lobo
, Javier Del Ser

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

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.

Original language	English
Title of host publication	Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2021, Proceedings
Editors	Nuria Oliver, Fernando Pérez-Cruz, Stefan Kramer, Jesse Read, Jose A. Lozano
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	297-313
Number of pages	17
ISBN (Print)	9783030865221
DOIs	https://doi.org/10.1007/978-3-030-86523-8_18
Publication status	Published - 1 Jan 2021
Event	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2021 - Virtual, Online Duration: 13 Sept 2021 → 17 Sept 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	12977 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2021
City	Virtual, Online
Period	13/09/21 → 17/09/21

Keywords

Borda
Concept drift
Evolving preferences
Preference learning
Rank aggregation
Voting

Access to Document

10.1007/978-3-030-86523-8_18

Cite this

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.), Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2021, Proceedings (pp. 297-313). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12977 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-86523-8_18

Irurozki, Ekhine ; Perez, Aritz ; Lobo, Jesus et al. / Rank Aggregation for Non-stationary Data Streams. Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2021, Proceedings. editor / Nuria Oliver ; Fernando Pérez-Cruz ; Stefan Kramer ; Jesse Read ; Jose A. Lozano. Springer Science and Business Media Deutschland GmbH, 2021. pp. 297-313 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2bc78ac707734aaf8908d39c90bc1d27,

title = "Rank Aggregation for Non-stationary Data Streams",

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.",

keywords = "Borda, Concept drift, Evolving preferences, Preference learning, Rank aggregation, Voting",

author = "Ekhine Irurozki and Aritz Perez and Jesus Lobo and \{Del Ser\}, Javier",

note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2021 ; Conference date: 13-09-2021 Through 17-09-2021",

year = "2021",

month = jan,

day = "1",

doi = "10.1007/978-3-030-86523-8\_18",

language = "English",

isbn = "9783030865221",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "297--313",

editor = "Nuria Oliver and Fernando P{\'e}rez-Cruz and Stefan Kramer and Jesse Read and Lozano, \{Jose A.\}",

booktitle = "Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2021, Proceedings",

}

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 & JA Lozano (eds), Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2021, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12977 LNAI, Springer Science and Business Media Deutschland GmbH, 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

Rank Aggregation for Non-stationary Data Streams. / Irurozki, Ekhine; Perez, Aritz; Lobo, Jesus et al.
Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2021, Proceedings. ed. / Nuria Oliver; Fernando Pérez-Cruz; Stefan Kramer; Jesse Read; Jose A. Lozano. Springer Science and Business Media Deutschland GmbH, 2021. p. 297-313 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12977 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Rank Aggregation for Non-stationary Data Streams

AU - Irurozki, Ekhine

AU - Perez, Aritz

AU - Lobo, Jesus

AU - Del Ser, Javier

PY - 2021/1/1

Y1 - 2021/1/1

N2 - 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.

AB - 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.

KW - Borda

KW - Concept drift

KW - Evolving preferences

KW - Preference learning

KW - Rank aggregation

KW - Voting

U2 - 10.1007/978-3-030-86523-8_18

DO - 10.1007/978-3-030-86523-8_18

M3 - Conference contribution

AN - SCOPUS:85115668246

SN - 9783030865221

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 297

EP - 313

BT - Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2021, Proceedings

A2 - Oliver, Nuria

A2 - Pérez-Cruz, Fernando

A2 - Kramer, Stefan

A2 - Read, Jesse

A2 - Lozano, Jose A.

PB - Springer Science and Business Media Deutschland GmbH

T2 - European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2021

Y2 - 13 September 2021 through 17 September 2021

ER -

Irurozki E, Perez A, Lobo J, Del Ser J. Rank Aggregation for Non-stationary Data Streams. In Oliver N, Pérez-Cruz F, Kramer S, Read J, Lozano JA, editors, Machine Learning and Knowledge Discovery in Databases. Research Track - European Conference, ECML PKDD 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2021. p. 297-313. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-86523-8_18

Rank Aggregation for Non-stationary Data Streams

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this