Résolution de problèmes d'optimisation combinatoire par élicitation robuste des préférences

Par Nawal Benabbou, 19 novembre, 2020

L'élicitation des préférences pour l'aide à la décision est un domaine fondamental de l'intelligence artificielle, dont l'objectif est de concevoir des méthodes permettant de formuler des recommandations personnalisées, en recueillant des informations sur les préférences des agents. Par exemple, il peut s'agir de systèmes de recommandation que l'on trouve sur le web pour l'achat d'un bien, le choix d'un séjour de vacances ou encore la sélection de films/séries dans une base de données de vidéos. Ces systèmes servent également dans des contextes où les enjeux de la décision sont plus importants, comme dans le cadre de la planification de traitements thérapeutiques, de la gestion de politiques publiques ou encore de choix stratégiques pour une organisation.

Dans de nombreux contextes, ces systèmes de recommandation doivent solliciter directement les agents en leur posant des questions sur leurs préférences subjectives, afin de collecter des informations leur permettant de formuler une recommandation pertinente.
En pratique, le nombre de questions que l'on peut poser aux agents est assez limité, ces derniers ne souhaitant pas forcément répondre à un trop grand nombre de questions.
Dans l'optique de limiter le nombre de questions nécessaires à la prise de décision, des procédures d'élicitation partielle ont été proposées : il s'agit de poser des questions aux agents, soigneusement choisies les unes après les autres, pour réduire progressivement l'imprécision sur les paramètres du modèle de préférences, de manière à formuler rapidement une recommandation.
Plus récemment, cette approche a été adaptée pour pouvoir tenir compte des éventuelles erreurs des agents dans leurs réponses aux questions, en utilisant une approche Bayésienne.

Dans le cadre de ce stage, il s'agit d'étendre cette dernière approche à des problèmes de décision où l'ensemble des alternatives possibles est très grand, et défini de manière implicite comme l'ensemble des solutions réalisables d'un problème d'optimisation combinatoire (comme le plus court chemin, l'arbre couvrant de cout min, le sac à dos).
Plus précisément, il s'agira de concevoir des algorithmes de résolution interactifs, utilisant des solutions algorithmiques comme la programmation linéaire, l'approche gloutonne, la programmation dynamique ou encore le branch and bound, et réalisant des révisions Bayésiennes à chaque réponse obtenue des agents de manière efficace.

Durée du stage : 5 ou 6 mois
Contact : nawal.benabbou@lip6.fr, nadjet.bourdache@lip6.fr

Lieu
Sorbonne Université - LIP6
Thématiques
Encadrant
Nawal Benabbou
Co-encadrant
Nadjet Bourdache
Référent universitaire
n/a
Tags
Attribué
Non
Année
2021