Proposition de stage de DEA ou d'ingénieur

2006-2007

Titre : "Apprentissage en ressources limitées sur des flux de données : data streaming"

Résumé :

Dans le modèle du flux de données (data streaming), les données à traiter arrivent en séquence et l'apprenant n'a qu'une capacité de stockage limitée et ne peut ré-examiner les données passées. Il doit donc traiter les données à la volée et en concevoir un modèle dans un espace mémoire limité (typiquement en o(n) ou en O(poly-log n)).

Ce modèle est adapté à l'étude du traitement des masses de données qui ne peuvent pas être entièrement stockée dans la mémoire de travail de l'apprenant. C'est le cas par exemple des données récupérées dans les réseaux de télécommunication, les logs d'utilisation de grilles de données ou encore dans les observations par satellites.

Deux questions se posent spécialement : (i) quelles sont les informations sur les données qui peuvent être stockées économiquement (e.g. un min ou une moyenne ne requièrent qu'un espace mémoire (quasi-) constant) et (ii) quels sont les algorithmes permettant d'apprendre incrémentalement au mieux face à un flux de données, et en particulier, comment régler au mieux le compromis taille mémoire et précision du modèle appris ?

Le sujet du stage est

•  d'étudier des protocoles proposés dans la littérature sur le data-streaming en essayant de répondre aux questions ci-dessus,
•  et de concevoir et tester des algorithmes performants pour ces protocoles.

Le sujet de ce stage se situe dans un domaine en pleine extension, et mis en avant dans une action européenne à laquelle participe Antoine Cornuéjols. Il devrait déboucher sur un travail de thèse.