[Lrde Annonce] [Séminaire des étudiants CSI] : mercredi 25 juin 2008

Bonjour, Vous êtes tous cordialement invités à assister au séminaire qui aura lieu le mercredi 25 juin 2008 à 14 heures en Amphi 4 (KB). Veuillez noter qu'après les étudiants, Sébastien Hémon présentera entre 16h45 et 17h45 l'article "Equilibres de Nash approchés dans les jeux multi-joueurs" de Sébastien Hémon, Miklos Santha and Michel de Rougemont présenté à SAGT 08 en mai 2008. http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/2008-01-18-SAGT ----------------------------------------------------------------------- Le programme du séminaire : *Olena et Théorie des Jeux* http://www.lrde.epita.fr/cgi-bin/twiki/view/Publications/Seminar-2008-06-25 OLENA 14h00 : Ligne de partage des eaux topologique -- Alexandre Abraham 14h30 : Taxonomie des images de Milena -- Nicolas Ballas 15h00 : Transformation des courbes de niveau rapide -- Matthieu Garrigues 15h30 : Recalage d'image rapide -- Ugo Jardonnet THEORIE DES JEUX 16h15 : Etude et implémentation du Fictitious Play alterné -- Antoine Leblanc 16h45 : Equilibres de Nash approchés dans les jeux multi-joueurs -- Sebastien Hemon et al. ----------------------------------------------------------------------- Les Résumés des exposés : ************************** OLENA Ligne de partage des eaux topologique -- 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 graphe généraux, etc.). Taxonomie des images de Milena -- 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 des courbes de niveau rapide -- 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 d'image rapide -- 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é -- 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 -- 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. -- Daniela Becker