UniRank : un algorithme de bandit générique pour l'ordonnancement en ligne
| Autor: | Gauthier, Camille-Sovanneary, Gaudel, Romaric, Fromont, Élisa |
|---|---|
| Přispěvatelé: | Gaudel, Romaric, Louis Vuitton, Large Scale Collaborative Data Mining (LACODAM), Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-GESTION DES DONNÉES ET DE LA CONNAISSANCE (IRISA-D7), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Ecole Nationale de la Statistique et de l'Analyse de l'Information [Bruz] (ENSAI), Centre de Recherche en Economie et Statistique [Bruz] (CREST), Institut Universitaire de France (IUF), Ministère de l'Education nationale, de l’Enseignement supérieur et de la Recherche (M.E.N.E.S.R.), Elisa Fromont et Nicolas Courty |
| Jazyk: | francouzština |
| Rok vydání: | 2022 |
| Předmět: | |
| Zdroj: | CAP-RFIAP 2022-Conférence française sur l'apprentissage machine-Reconnaissance de formes, Images, Apprentissage et Perception CAP-RFIAP 2022-Conférence française sur l'apprentissage machine-Reconnaissance de formes, Images, Apprentissage et Perception, Elisa Fromont et Nicolas Courty, Jul 2022, Vannes, France |
| Popis: | International audience; Nous abordons, dans le cadre d'un bandit à multi-choix, le problème d'ordonnancement en ligne consistant à assigner $L$ éléments à $K$ positions prédéfinies sur une page web afin de maximiser le nombre de clics de l'utilisateur. Nous proposons un algorithme générique, UniRank, qui traite les modèles de clics de l'état de l'art. La borne sur le regret de cet algorithme est une conséquence directe de la propriété de pseudo-unimodalité de l'espérance de récompense vis-à-vis d'un graphe où chaque nœud est un ordre sur des ensembles d'éléments indiscernables.La principale contribution d'UniRank est son regret en ${\cal O}\left(L/\Delta \log T\right)$ pour $T$ affectations consécutives, où $\Delta$ mesure l'écart de récompense entre deux éléments.Cette limite de regret est basée sur la condition généralement implicite selon laquelle deux éléments peuvent ne pas avoir le même attrait.Des expériences contre des algorithmes de l'état de l'art, spécialisés ou non pour différents modèles de clics, montrent que notre méthode a de meilleures performances en matière de regret que d'autres algorithmes génériques sur deux ensembles de données réelles. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|