Modèles d'incertitude, de raisonnement et de décision
6 ECTS - 20% cours, 80% TDs
Parcours-type : D&C
Responsable :
Hélène Fargier
Équipe pédagogique :
Martin Cooper, Marie-Christine Lagasquie, Claudette Cayrol, Hélène Fargier, Thomas Schiex
Contenu
Raisonnement et décision en présence de données incertaines - 1,5 à 2
ECTS
- Représentation de l'incertitude : modèles qualitatifs, théorie
des possibilités, modèles probabilistes bayésiens et non bayésiens,
fonctions de croyance,
- -Fusion de données
- Conditionnement et mise à jour
- Théorie de la décision sous incertitude : au delà de l'utilité
espérée : décision sous ignorance, utilité espérée, muti-prior,
utilité qualitative, utilité dépendant du rang, intégrales de Choquet ;
Justification axiomatiques : Von Neuman & Morgenstein, Savage
- Théorie des jeux (décision contre un adversaire)
- Décision Collective, décision concertée, partage équitable
Complexité des langages et des algorithmes - 0,5 à 1 ECTS
- Rappel de complexité : complexité des algorithmes, complexité
des problèmes, le classe NP, réduction polynomiale, preuves
de complexité
- Complexité des problèmes d'optimisation, functions problems
- Au-delà de NP : NP et Co NP, hiérarchie polynomiale, P-space et pire.
- Structures de données, expressivité, et compilation de connaissances
Langages pour la représentation de connaissances et de
préférences, inférence et complexité - 1 ECTS
- Raisonnement en présence d’informations incomplètes,
incohérentes, de règles avec exceptions, Raisonnement par défaut:
rappels, sémantique, analyse de complexité
- Formalisation dans le cadre ASP (Programmation logique avancée
: programmes disjonctifs, modèles stables, solveurs ASP )
- Langages de représentation de préférences : (CP nets,
préférences lexicographiques, GAI nets, CSP valués)
- Application à l'interrogation de bases de données incomplètes
Une attention particulière sera portée à l'analyse de l'expressivité de ces
langages et de la complexité des problèmes de décision et requetes
associés
Algorithmique avancée pour le traitement de données, de préférences et
de connaissances incertaines - 2 ECTS
- Recommandation et aide à la décision : filtrage collaboratif ;
algorithmique des CSP valués, GAI nets, champs de Markov
- Décision interactive, preference based search et élicitation de
préférences
- Réseaux Bayésiens: représentation (rappels), algorithmes inférence et
d'apprentissage ; complexité
- Diagrammes d'influence et arbres de décision - algorithmique pour
l'optimisation de l'utilité esperée ; introduction aux critères
non bayesiens : l'utilité qualitative, a priori multiples, intégrales de
Choquet ; complexité
- Approches par compilation, algorithmes d'inférence dans les
diagrammes de décision ; complexité
Ce cours s'appuie sur des bases que les étudiants devraient avoir abordées
en M1, à savoir : (i) les bases de la theorie de la
complexité, (ii) la programmation par contraintes et/ou la PNLE et/ou
la logique propositionnelle (iii) les bases de la reconnaissances des formes
et de la théorie de l'apprentissage automatique.