Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method

Karlé, Eglantine; Tyagi, Hemant

Type de document :

Article dans une revue scientifique: Article original

Titre :

Dynamic Ranking with the BTL Model: A Nearest Neighbor based Rank Centrality Method

Auteur(s) :

Karlé, Eglantine [Auteur]
MOdel for Data Analysis and Learning [MODAL]
Inria Lille - Nord Europe
Tyagi, Hemant [Auteur]
MOdel for Data Analysis and Learning [MODAL]
Inria Lille - Nord Europe

Titre de la revue :

Journal of Machine Learning Research

Pagination :

1--57

Éditeur :

Microtome Publishing

Date de publication :

2023-09-23

ISSN :

1532-4435

Discipline(s) HAL :

Mathématiques [math]
Statistiques [stat]

Résumé en anglais : [en]

Many applications such as recommendation systems or sports tournaments involve pairwise comparisons within a collection of n items, the goal being to aggregate the binary outcomes of the comparisons in order to recover the ...
Lire la suite >Many applications such as recommendation systems or sports tournaments involve pairwise comparisons within a collection of n items, the goal being to aggregate the binary outcomes of the comparisons in order to recover the latent strength and/or global ranking of the items. In recent years, this problem has received significant interest from a theoretical perspective with a number of methods being proposed, along with associated statistical guarantees under the assumption of a suitable generative model. While these results typically collect the pairwise comparisons as one comparison graph G, however in many applications-such as the outcomes of soccer matches during a tournamentthe nature of pairwise outcomes can evolve with time. Theoretical results for such a dynamic setting are relatively limited compared to the aforementioned static setting. We study in this paper an extension of the classic BTL (Bradley-Terry-Luce) model for the static setting to our dynamic setup under the assumption that the probabilities of the pairwise outcomes evolve smoothly over the time domain [0, 1]. Given a sequence of comparison graphs (G_t')_{t' ∈T} on a regular grid T ⊂ [0, 1], we aim at recovering the latent strengths of the items w^*_t ∈ R^n at any time t ∈ [0, 1]. To this end, we adapt the Rank Centrality method-a popular spectral approach for ranking in the static case-by locally averaging the available data on a suitable neighborhood of t. When (G_t')_{t' ∈T} is a sequence of Erdös-Renyi graphs, we provide non-asymptotic l_2 and l_∞ error bounds for estimating w^*_t which in particular establishes the consistency of this method in terms of n, and the grid size |T |. We also complement our theoretical analysis with experiments on real and synthetic data.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Laboratoire Paul Painlevé - UMR 8524

Source :

Harvested from HAL

Fichiers

document
Accès libre
Accéder au document

Dynamic_BTL_NN.pdf
Accès libre
Accéder au document

2109.13743
Accès libre
Accéder au document

Dynamic Ranking with the BTL Model: A ... BibTeX CSV Excel RIS

Fichiers

Dynamic Ranking with the BTL Model: A ...

BibTeX

CSV

Excel

RIS