Sequential prediction for budgeted learning : Application to trigger design

Prédiction séquentielle pour l'apprentissage budgété : Application à la conception de trigger Cette thèse aborde le problème de classification en apprentissage statistique sous un angle nouveau en rajoutant une dimension séquentielle au processus de classification. En particulier, nous nous intéressons au cas de l'apprentissage à contraintes de budget (ou apprentissage budgété) où l'objectif est de concevoir un classifieur qui, tout en apportant des prédictions correctes, doit gérer un budget computationnel, consommé au fur et à mesure que les différents attributs sont acquis ou évalués. Les attributs peuvent avoir des coûts d'acquisition différents et il arrive souvent que les attributs les plus discriminatifs soient les plus coûteux. Le diagnostic médical et le classement de pages web sont des exemples typiques d'applications de l'apprentissage budgété. Pour le premier, l'objectif est de limiter le nombre de tests médicaux que le patient doit endurer et, pour le second, le classement doit se faire dans un temps assez court pour ne pas faire fuir l'usager. Au cours de cette thèse, nous nous sommes intéressés à des contraintes de budget atypiques, que la conception de trigger nous a motivés à investiguer. Les triggers sont un type de classifieurs rapides, temps-réel et sensibles aux coûts qui ont pour objectif de filtrer les données massives que les accélérateurs de particules produisent et d'en retenir les événements les plus susceptibles de contenir le phénomène étudié, afin d'être enregistrés pour des analyses ultérieures. La conception de trigger impose des contraintes computationnelles strictes lors de la classification mais, surtout, exhibe des schémas complexes de calcul du coût de chaque attributs. Certains attributs sont dépendants d'autres attributs et nécessitent de calculer ces derniers en amont, ce qui a pour effet d'augmenter le coût de la classification. De plus, le coût des attributs peut directement dépendre de leur valeur concrète. On retrouve ce cas de figure lorsque les extracteurs d'attributs améliorent la qualité de leur sortie avec le temps mais peuvent toujours apporter des résultats préliminaires. Enfin, les observations sont regroupées en sacs et, au sein du même sac, certaines observations partagent le calcul d'un sous-ensemble d'attributs. Toutes ces contraintes nous ont amenés à formaliser la classification sous un angle séquentiel.Dans un premier temps, nous proposons un nouveau cadriciel pour la classification rapide en convertissant le problème initial de classification en un problème de prise décision. Cette reformulation permet d'un part d'aborder la séquentialité de manière explicite, ce qui a pour avantage de pouvoir aisément incorporer les différentes contraintes que l'on retrouve dans les applications réelles, mais aussi d'avoir à disposition toute une palette d'algorithmes d'apprentissage par renforcement pour résoudre le nouveau problème. Dans une seconde partie, nous appliquons notre modèle de classification séquentielle à un problème concret d'apprentissage à contraintes de budget et démontrant les bénéfices de notre approche sur des données simulées (à partir de distributions simplifiées) de l'expérience LHCb (CERN).