Algorithmes de partitionnement par comparaison de paires
Time: 11:00 -- Location: Salle Philippe Flajolet du LIX
On cherche à reconstruire une partition d'un ensemble donné en envoyant des paires d'éléments à un oracle qui nous indique s'ils appartiennent à la même partie de la partition. Nous cherchons les algorithmes qui retrouvent la partition en un minimum de questions à l'oracle. Ce problème est similaire au problème classique du tri : on reconstruit une partition au lieu d'une permutation. Dans le cas où la partition est tirée aléatoirement uniformément parmi celles d'une taille donnée, nous caractérisons les algorithmes de complexité moyenne optimale, prouvons qu'ils partagent la même distribution sur le nombre de questions et analysons cette distribution. Nous étudions également un modèle de partitions aléatoires où chaque élément choisit sa partie indépendamment suivant la même loi de support fini. Ce travail est motivé par l'annotation de données d'entraînement par des experts humains pour l'apprentissage supervisé.
Travail en commun avec Quentin Lutz (Nokia Bell Labs), Maya Stein (Université du Chili) et Alex Scott (université d'Oxford) Publié à Neurips 2021