David Saulpic récompensé pour ses algorithmes de partitionnement de données

Cette année, le prestigieux prix de thèse Gilles Kahn de la Société informatique de France est remis à David Saulpic, pour Approximation algorithms and sketches for clustering. Ses travaux, fermement inscrits dans l’informatique fondamentale et conduits au laboratoire LIP6 (CNRS/Sorbonne Université), s’inspirent notamment de problèmes de compression et de partitionnement que l’on retrouve dans l’apprentissage automatique.

« Ces problèmes visent à transformer un nuage de points en un petit nombre de centres, tout en s’assurant que chaque point du nuage ne soit pas trop éloigné du centre qui le remplace, décrit David Saulpic. En général je ne propose pas d’implémentations, j’essaye plutôt de comprendre la structure du problème et de savoir ce qui est théoriquement faisable ou non. »

Ces questions, appelées problèmes de clustering, ne peuvent être résolues de manière exacte qu’en testant toutes les configurations possibles, qui peuvent être rapidement plus nombreuses que le nombre d’atomes dans l’univers… Comme c’est inenvisageable, David Saulpic a proposé à la place des algorithmes d’approximations : il a montré qu’il était possible de calculer une solution presque optimale, beaucoup plus rapidement qu’en testant toutes les solutions exactes.

Dans sa thèse, David Saulpic a aussi étudié la simplification des données d’entrée. Il a pour cela utilisé des sketches (esquisses), qui sont ici des représentations réduites des données en entrée. Ses solutions permettent une compression importante des données, tout en garantissant qu’il sera toujours possible d’effectuer différents calculs et opérations avec.

« Avec mes coauteurs, nous avons prouvé que tirer des points au hasard préservait de manière très précise la structure des données, précise David Saulpic. Notamment, toutes les solutions de clustering ont alors le même coût, en termes de distance entre un point et le centre qui le remplace, qu’elles soient calculées à partir de l’ensemble initial des données ou à partir des seules esquisses. Ce modèle est très utile lorsqu’il y a énormément de données en entrée ou quand le calcul est distribué entre plusieurs serveurs. »

David Saulpic a également travaillé sur des modèles d’algorithmes à confidentialité différentielle, c’est-à-dire dont on ne peut pas extraire, à partir du résultat final, d’informations personnelles sur un individu. Cette propriété est importante, car elle donne une certaine garantie de respect de la vie privé Une question qu’il a ensuite développée lors de son postdoctorat, mené à l’Institut de sciences et de technologies d’Autriche (ISTA). Au 1er février, David Saulpic démarrera son premier poste fixe de chercheur, en tant que chargé de recherche CNRS à l’IRIF.

Un excellent début de parcours pour celui qui s’est initié à l’algorithmique en seconde par le biais de France-IOI, l’association organise les Olympiades internationales d’informatique en France et entraîne les participantes et participants. « J’ai alors découvert l’aspect ludique de l’algorithmique, j’y vois des puzzles et des énigmes à résoudre, qui me prennent aux tripes et me maintiennent éveillé la nuit, décrit David Saulpic. J’ai cependant d’abord hésité avec les sciences sociales, avant de me tourner vers la recherche en algorithmique. »

En dehors des travaux issus de sa thèse, David Saulpic s’est aussi intéressé à l’analyse du découpage électoral en France. Une question qui s’est posée au moment où l’on parlait d’une possible réduction du nombre de députés, qui aurait entraîné une remise à plat des circonscriptions. Chacune devant avoir à peu près le même nombre de citoyens, il a comparé avec ses collaborateurs la carte électorale à différents optimums. David Saulpic a également conçu une animation sur les différents systèmes de vote pour la Cité des Sciences.

« Je remercie mes directeurs de thèse de m’avoir guidé et formé, ainsi que la Cité des sciences pour la découverte de la médiation scientifique, conclut David Saulpic. Je vais essayer de poursuivre mes recherches en algorithmique, tout en explorant plus en profondeur leur interface avec les sciences humaines et les interactions de l’informatique avec la société. »