• Langue : Anglais
• Discipline : Mathématiques et leurs interactions
• Identifiant : 2024ULILB008
• Type de thèse : Doctorat
• Date de soutenance : 16/05/2024

Résumé en langue originale

Le classement et les comparaisons apparaissent dans de nombreuses applications de la vie de tous les jours, telles que les tournois sportifs ou les systèmes de recommandation. Dans ces domaines, les données sont souvent composées de comparaisons appairées entre un ensemble d'objets, qui peuvent être résumées dans un graphe de comparaison. De nombreux modèles paramétriques pour les problèmes de classement ont été introduits, tels que le modèle de Bradley-Terry-Luce (BTL), dans lequel on suppose que les objets possèdent une qualité sous-jacente. Le classement est ensuite déduit des scores de qualité. De nombreux algorithmes d'estimation ont été analysés ces dernières années, comme l'algorithme de maximum de vraisemblance ou une méthode spectrale. Cependant, les classements et préférences personnelles peuvent évoluer avec le temps. Afin de prendre cela en compte, nous allons considérer une suite de graphes de comparaison, ou un graphe dynamique, qui rassemble les données à divers points de temps.Nous allons d'abord étudier une extension du modèle BTL au cas dynamique, introduit par Bong et al. en supposant que les scores de qualités sont Lipschitz. Notre algorithme est basé sur la méthode des plus proches voisins et sur l'algorithme de Rank Centrality, méthode d'estimation bien connue dans le cas statique. Nous fournissons des bornes [dollar]ell_2[dollar] et [dollar]ell_infty[dollar] pour notre estimateur et montrons les performances de notre algorithme sur des données réelles et synthétiques.Dans un second temps, nous introduirons une version dynamique du modèle de Translation-Synchronisation sous une une hypothèse globale de régularité. Nous proposerons deux estimateurs, le premier basé sur une approche des moindres carrés avec une pénalité traduisant la régularité, et le deuxième basé sur la projection sur l'espace des vecteurs propres de basse fréquence d'un opérateur de régularité approprié. Nous montrerons que ces deux méthodes donnent des estimateurs consistants. Nous montrerons à nouveau les performances de nos algorithmes sur des données réelles et synthétiques.

Résumé traduit

Ranking and comparing arise in many real life applications, such as sports tournaments or recommendation systems. In these domains, datasets are composed of pairwise comparisons between a collection of items that can also be summarized into a comparison graph. Many parametric statistical models for ranking were introduced, such as the Bradley-Terry-Luce model, where the items are supposed to have a latent strength. The ranking are then derived from this strengths. Numerous estimation algorithms have been analyzed over the past decades, for example the maximum-likelihood or the spectral method. However, most of them do not account for the temporal aspect of the data. Indeed, ranking and personal preferences can evolve over time. In order to include temporality, we will consider a sequence of comparison graphs, or dynamic graphs, that gathers data at different time instances.We will first study an extension of the BTL model to this dynamic setting, introduced by Bong et al. under a local Lipschitz assumption on the strengths. Our algorithm is based on a nearest-neighbor approach and on the Rank Centrality algorithm, a classic estimation method in the static case. We will show [dollar]ell_2[dollar] and [dollar]ell_infty[dollar] bounds for our estimator and show our algorithm performance on both synthetic and real data.In a second part, we will introduce a dynamic version of the Translation-Synchronization model under a global smoothness assumption. We will propose two estimators, one based on a smoothness-penalized least squares approach and the other based on projection onto the low frequency eigenspace of a suitable smoothness operator. We will show that both method give consistent estimators. We also display the performance of our algorithms on synthetic and real datasets.