Olena et théorie des jeux
Les étudiants de l’option CSI présentent leurs travaux. Comme la semaine dernière, ce sont des étudiants de la promo 2009 qui interviendront ce mercredi 25 juin, à 14h, en amphi 4.
Au programme, Olena et la théorie des jeux, suivis de la présentation de Sébastien Hémon de l’article « Equilibres de Nash approchés dans les jeux multi-joueurs ».
- OLENA
– 14h00 : Ligne de partage des eaux topologiques par Alexandre Abraham
– 14h30 : Taxonomie des images de Milena par Nicolas Ballas
– 15h00 : Transformation rapide des courbes de niveau par Matthieu Garrigues
– 15h30 : Recalage rapide d’image par Ugo Jardonnet
- THEORIE DES JEUX
– 16h15 : Etude et implémentation du Fictitious Play alterné par Antoine Leblanc
– 16h45 : Equilibres de Nash approchés dans les jeux multi-joueurs par Sebastien Hemon et al.
Résumés :
- OLENA
– Ligne de partage des eaux topologiques par Alexandre Abraham
Segmenter une image consiste à en extraire les régions d’intérêt, par exemple pour séparer des cellules cancéreuses en imagerie médicale.
L’approche par transformation de la ligne de partage des eaux (LPE) ou Watershed Transform permet d’obtenir une telle segmentation. Il en existe de nombreuses définitions, ainsi que diverses implémentations, dont certaines sont à la fois performantes et produisent un résultat avec de bonnes propriétés, comme le Topological Watershed. Cet exposé présentera l’implémentation d’un algorithme calculant cette LPE au sein de Milena, la bibliothèque C++ générique de traitement d’images de la plate-forme Olena, développée au LRDE. Nous nous intéresserons tout d’abord aux formats d’images « classiques », puis à la généralisation à des formats d’images plus inhabituels (images à support de graphes généraux, etc.).
– Taxonomie des images de Milena par Nicolas Ballas
Milena est la bibliothèque de traitement d’images générique de la plate-forme Olena. Cette bibliothèque a pour but d’être performante tout en restant simple. L’introduction dans Milena de nouveaux types d’images basés sur des graphes a mis en évidence des problèmes de modélisation qui sont un frein pour sa généricité. Par exemple, nous avons toujours considéré que « les images ont des points ». Néanmoins, certains types d’images possèdent des sites qui ne sont pas des points (mais des arrêtes, faces, ou même des ensembles de points). Une autre supposition erronée était de considérer que les sites étaient toujours localisés par un vecteur (càd, (x,y) dans le plan 2D). Cette supposition est fausse lorsque l’on manipule des sites qui ne sont pas « Pointwise ». Il etait donc nécessaire de modifier les types d’images utilisés dans Milena et les propriétées qui leur sont associées. Pendant ce séminaire, nous présenterons une nouvelle classification d’images permettant de résoudre ces problèmes.
– Transformation rapide des courbes de niveau par Matthieu Garrigues
La transformation rapide des courbes de niveaux (FLLT) construit une représentation d’une image indépendante du contraste. Cet algorithme construit un arbre suivant les inclusions des formes. Pour un filtre, être invariant suivant le contraste est un plus. Par exemple, en analyse de document, cette représentation a le précieux avantage d’extraire facilement et rapidement les caractères indépendamment du fait qu’ils soient plus clairs ou plus foncés que leur voisinage. Ce document présente l’introduction de l’algorithme dans notre bibliothèque de traitement d’images et montre les résultats de quelques filtres connectés que peut engendrer cette représentation.
– Recalage rapide d’image par Ugo Jardonnet
Le recalage d’images est une technique classique en traitement d’images.
Soit A et B deux images représentant le même objet (par exemple une radiographie et une image à résonance magnétique (IRM)), on calcule une transformation deAtelle que le recalage de l’objet dans A soit aligné sur l’objet dans B. Typiquement, cette technique peut permettre la lecture simultanée de deux mesures A et B. Cet exposé discutera des procédés de recalage rapide utilisés dans Milena, la bibliothèque C++ générique de traitement d’images de la plate-forme Olena, développée au LRDE. Certaines améliorations seront présentées.
- THEORIE DES JEUX
– Etude et implémentation du Fictitious Play alterné par Antoine Leblanc
Le calcul d’un équilibre de Nash dans un jeu fini est un problème démontré PPAD-complet, ce qui signifie qu’il paraît impossible de trouver une méthode de calcul efficace ; la complexité en pire cas des algorithmes usuels est 2O(n) pour un jeu de taille n. La recherche en ce domaine s’oriente donc vers le calcul d’équilibres approchés, à savoir des situations vérifiant les conditions d’un équilibre de Nash à ! près.
L’algorithme du Fictitious Play s’inscrit dans cette démarche de recherche. Son principe est simple : à chaque itération, chacun des joueurs « renforce » celle de ses stratégies pures qui est la plus efficace face à ses adversaires. Pour certains jeux, cet algorithme converge vers un équilibre de Nash, fournissant ainsi un algorithme d’approximation efficace. La convergence ne peut toutefois être prouvée que pour un nombre limité de cas. Pour cette raison, il est intéressant d’étudier d’autres algorithmes basés sur le Fictitious Play, afin de trouver d’autres cas de convergence. Nous allons étudier ici le Fictitious Play alterné, dans lequel seul le joueur le plus « éloigné » de son gain optimal renforce sa stratégie la plus efficace.
– Equilibres de Nash approchés dans les jeux multi-joueurs par Sebastien Hemon et al.
Les équilibres de Nash sont des positions-clés de tout jeu admettant une représentation finie : en effet, quel que soit le nombre de joueurs et de stratégies, une telle position existe toujours. Lorsqu’elle est atteinte, elle dissuade tout joueur de vouloir se détourner de sa stratégie actuelle, d’où la notion d’équilibre. De nombreux problèmes y font appel mais calculer de façon effective l’équilibre demeure un problème difficile. En effet, le meilleur algorithme connu pour, dans le cas général, calculer un équilibre est exponentiel en le nombre de stratégies. Nous présenterons ici la notion d’équilibres approchés, et donnerons des résultats concernant leur calcul. Nous montrerons qu’il ne saurait exister d’algorithmes pouvant calculer un équilibre, même approché, sans utiliser au moins, pour un joueur, un nombre logarithmique de stratégies. Nous montrerons comment calculer un équilibre approché en temps sub-exponentiel nO( ln n 2 ), ce qui demeure actuellement, pour le cas général, la meilleure complexité en pire cas.
Enfin, nous présenterons une approche inductive de transfert d’approximation d’une position d’un jeu à deux joueurs en une approximation pour un jeu à r joueurs, ce qui confère des résultats novateurs dans le domaine.