| GT probabilité et informatique |
Pour vous inscrire, c'est-à-dire recevoir les annonces des exposés et des différents événements :
- si vous faites partie du LaBRI https://www3.labri.fr/intranet/gt/script/index.php
- si ce n'est pas le cas, ou si c'est trop dur : envoyez moi un e-mail.
| Lundi 12 mars 2012 à 11h salle 076 François Caron : Méthodes bayésiennes non paramétriques pour la classification non supervisée de données Le processus de Dirichlet est un modèle Bayésien non paramétrique très populaire en statistiques et machine learning pour le clustering de données et l’estimation de densité. L’un des intérêts de ce modèle est que le nombre de clusters, ou de modes de la densité, ne doit pas être fixé par avance, mais est estimé à partir des données. Je présenterai le processus du restaurant chinois, qui définit la distribution a priori sur la partition aléatoire sous-jacente. Enfin, je présenterai des algorithmes de Monte Carlo par chaine de Markov pour estimer les paramètres de ce modèle. Lundi 6 février 2012 à 11h salle 076 Yvan Le Borgne : Formulation d'énumérations d'animaux dirigés en terme de systèmes dynamiques probabilistes. Depuis les années 80, on a mis en évidence une relation entre diverses énumérations des animaux dirigés sur le réseau carré et la densité de certains modèles de gaz sur la ligne. Je propose de revisiter cette relation pour formaliser un lien entre ces questions et des systèmes dynamiques probabilistes sur le carré unité. La preuve passe par l'analyse de l'exécution d'une sorte de machine de Turing probabiliste. Lundi 23 janvier 2012 à 11h salle 076 Allyx Fontaine : Interprétation d'algorithmes probabilistes Afin de prouver des propriétés d'algorithmes probabilistes à l'aide d'un assistant de preuve tel Coq, une nouvelle méthode a été introduite dans la bibliothèque Alea. Elle est basée sur l'interprétation monadique des programmes probabilistes vu en tant que distributions probabilistes. Nous présentons en premier lieu comment l'interprétation des algorithmes probabilistes comme des distributions a permis de constituer la bibliothèque Alea de preuves formelles de propriétés de ces programmes. Cette approche, qui ne concerne que les distributions discrètes, nous donne des règles pour analyser des fonctions récursives. Nous appliquerons ensuite cette théorie à l'exemple d'une marche aléatoire simple dont la terminaison avec probabilité 1 a été prouvée en Coq. Lundi 9 et 16 janvier 2012 à 11h salle 076 Florent Foucaud : Méthode probabiliste pour les codes identifiants dans les graphes de degré maximum donné Dans un graphe, un code identifiant est un ensemble de sommets qui est à la fois dominant et séparant, c'est-à-dire que chaque sommet est couvert par un sommet du code, et que pour chaque paire u,v de sommets, u et v ont des voisinages distincts dans le code. Les codes identifiants ont été introduits en 1998 par Karpovsky et al. et ont depuis été étudiés par une active communauté. Nous nous intéressons ici à des bornes sur la taille minimum d'un code identifiant. Dans un premier exposé, nous montrerons comment donner une borne supérieure sur ce paramètre en fonction de l'ordre et du degré maximum du graphe. La preuve utilise le lemme local de Lovasz couplé à l'inégalité de Chernoff. Dans un second exposé, nous montrerons que la borne du premier exposé peut être largement améliorée lorsque la maille du graphe et son degré minimum sont suffisamment grands. Nous appliquerons ce résultat pour montrer qu'avec forte probabilité, un graphe régulier tiré uniformément au hasard a un code identifiant relativement petit. Ce dernier résultat utilise le modèle de Bollobas dit "des configurations" pour les graphes aléatoires réguliers. Ces exposés se veulent pédagogiques et l'accent sera mis sur les techniques probabilistes utilisées. Lundi 28 novemvre 2011 à 11h salle 076 Gilles Zémor : Percolation, codes correcteurs, et codes correcteurs quantiques Un certain nombre de constructions modernes de correcteurs d'erreurs font appel à une structure de graphe sous-jacente. Le problème de la correction des effacements pour ces codes est proche des problématiques de percolation. Ce phénomène est encore plus apparent dans le domaine des codes correcteurs quantiques. Nous montrerons comment passer d'un point de vue à l'autre, et montrerons comment utiliser des bornes sur la capacité de correction d'effacements quantiques pour majorer la probabilité critique pour la percolation sur des pavages du plan hyperbolique (travail commun avec Nicolas Delfosse). lundi 14 novembre 2011 à 11h salle 076 Valentin Féray : Étude asymptotique du nombre d'adjacences dans une permutation aléatoire uniforme. On dit que i est une adjacence d'une permutation sigma si i+1 apparaît juste après i dans sigma. Il a été prouvé par différents auteurs que le nombre d'adjacences dans une grande permutation suit une loi de Poisson. Notons que les images de i et de j dans une permutation aléatoire ne sont pas indépendantes car elles doivent être différentes. Nous allons montrer qu'elles sont "presque indépendantes" dans un certain sens (en utilisant des cumulants). Ceci permet de donner une nouvelle preuve et de nombreuses extensions du résultat ci-dessus. lundi 7 novembre 2011 à 11h salle 076 Fabien Lotte : Introduction à la classification de signaux électroencéphalographiques (EEG) pour la conception d'interfaces cerveau-ordinateur Les interfaces cerveau-ordinateur (ou BCI, terme venant de l'anglais Brain-Computer Interface) sont des systèmes de communication permettant à un utilisateur d'envoyer des commandes à un ordinateur en utilisant uniquement son activité cérébrale, celle-ci étant généralement mesurée par électroencéphalographie (EEG). Dans cette présentation, nous verrons d'abord brièvement comment marchent et à quoi servent les BCI, puis nous nous intéressons à comment traiter et classifier les signaux EEG afin d'identifier l'état mental de l'utilisateur. Nous aborderons ainsi quelques techniques d'apprentissage artificiel (machine learning) utilisées dans ce contexte. lundi 24 octobre 2011 à 11h salle 076 JF Marckert : Élection dans un arbre En algorithmique distribuée, le problème de l'élection est un problème crucial. Prosaïquement, on imagine un réseau de communication sous la forme d'un graphe, où les noeuds sont des entités communicantes et les arêtes des canaux de communication. Résoudre le problème de l'élection consiste à définir un algorithme que chaque noeud doit exécuter, de manière à ce qu'à la fin des opérations un noeud et un seul soit désigné "élu". Ceci doit se faire en utilisant uniquement les canaux de communication et doit marcher sur tout graphe, ou pour tout graphe dans une certaine classe (les noeuds, par dessus le marché, ne connaissent pas le graphe, mais uniquement l'ensemble de leurs voisins). Si le graphe est un arbre, alors une méthode consiste à ce que les feuilles s'auto-éliminent à des temps aléatoires. Le dernier en lice est décrété élu. On discute dans cet exposé de la loi du noeud finalement élu... (travail commun avec Akka Zemmari et Nasser Saheb-Djahromi). lundi 17 octobre 2011 à 11h salle 076 Philippe Duchon : Convergence de chaines de Markov contrôlées par un adversaire Beaucoup de chaînes de Markov permettant d'engendrer aléatoirement des structures discrètes peuvent être décrites par un petit nombre d'actions randomisées, chaque "pas" de la chaîne de Markov correspondant à un choix lui-même aléatoire de l'action à effectuer. En algorithmique distribuée, il n'est pas rare de modéliser le non-déterminisme d'un système en donnant à un adversaire le choix de l'action à exécuter. L'objectif du présent travail est d'explorer dans quelles conditions les résultats de convergence persistent dans ce genre de situation moins confortable. lundi 3 octobre 2011 à 11h salle 076 Hugo Gimbert : Playing in the Dark We consider partially observable Markov decision processes with finitely many states and actions. When playing in the dark, a player has no feedback about the decisions he takes: he does not know what is the state of the game or whether he has won or not. A classical result of Paz shows that the value of such games is not computable in general. We will survey recent negative and positive results: on one hand other similar decision problems are undecidable and on the other hand restricting the class of input games turns some of these decision problems into decidable problems. 2010 - 2011
lundi 30 mai 2011 à 11h salle 076 Jean-Francois Marckert : Convergence des structures combinatoires vers des objets continus En combinatoire, mais cela est vrai également dans de nombreuses disciplines (physique, chimie, biologie, économie, probabilité, ... ), lorsqu'on observe globalement "un gros objet de nature discrète", on voit apparaître un objet plutôt de nature continue: la normalisation (utilisée pour visualiser notre objet discret) ayant écrasé les détails, on ne voit plus que "les grandes tendances", qui elles sont de nature continue. Un résultat saillant en théorie des probabilités est la convergence des marches aléatoires vers le mouvement Brownien; ceci englobe le cas "combinatoire" des marches +1 ou -1 de longueur n, sous la loi uniforme. Ces dernières années, de nombreux résultats du même type ont été obtenus pour des structures combinatoires plus complexes : correctement normalisées, elles convergent en distribution vers des objets continus aléatoires (c'est ce genre de résultats qui a valu à W. Werner la médaille Fields il y a quelques années). Dans cet exposé que j'espère pédagogique, j'expliquerai l'utilité de ces résultats pour la compréhension des grands objets discrets. Autour d'exemples, j'essaierai d'expliquer comment se prouvent de tels résultats. lundi 16 mai 2011 à 11h salle 076 Nicolas Hanusse : Localiser une cible avec un agent guidé par des conseils non fiables: comment battre la marche aléatoire avec une montre ? A cause de la taille et de la dynamique des réseaux, il est impossible de garantir que tous les noeuds disposent d'informations fiables. Supposons que seuls k d'entre eux ne sont pas fiables, comment effectuer un routage ou une recherche d'information ? Des solutions, basées sur des algorithmes déterministes et probabilistes, seront discutées. lundi 2 mai 2011 à 11h salle 076 Eric Fusy : Génération de Boltzmann de structures combinatoires On montrera comment, lorsqu'une famille combinatoire possède une décomposition naturelle "pas trop compliquée" (exemple : un arbre binaire est soit un noeud, soit une paire d'arbres binaires), on peut traduire cette décomposition en un générateur aléatoire de manière automatique. Ph. Duchon : 11 - Chaîne de Markov et génération aléatoire lundi 4 avril 2011 à 11h salle 076 Ph. Duchon : 10 - Chaîne de Markov et génération aléatoire lundi 28 mars 2011 à 11h salle 076 lundi 21 mars 2011 à 11h salle 076 lundi 7mars et 7 mars 2011 à 11h salle 076 lundi 28 février et 7 mars 2011 à 11h salle 076 En gros, la méthode probabiliste repose sur le principe suivant : pour prouver l'existence d'un objet avec une propriété donnée, on définit un espace de probabilité sur une famille d'objets plus large et on montre qu'un élément de cet espace à la propriété requise avec une propriété positive. Dans cet exposé, nous présenterons cette méthode et traiterons quelques exemples d'utilisation de cette méthode en théorie des graphes. lundi 14 février 2011 à 11h salle 076 lundi 7 février 2011 à 11h salle 076 Le modèle de
Bradley-Terry est un modèle probabiliste utilisé lorsque des éléments
d'un ensemble sont comparés les uns aux autres par paire. Dans cet
exposé, je montrerai comment estimer les paramètres de ce modèle en
utilisant deux algorithmes bien connus en statistiques, l'algorithme EM
(Expectation-Maximisation) et l'algorithme de Gibbs. Je montrerai
différents résultats sur le classement des équipes en ligue 1 de
football et la prédiction de rencontres d'échecs. Enfin, je discuterai
plusieurs extensions de ce modèle ainsi qu'un modèle de graphe
aléatoire très proche du modèle de Bradley-Terry. lundi 31 janvier 2011 à 11h salle 076 lundi 24 janvier 2011 à 11h salle 076 lundi 17 janvier 2011 à 11h salle 076 Hugo Gimbert : Optimal positional strategies in stochastic games We consider Markov decision processes with finitely many states and actions. Roughly speaking, a Markov decision process is a Markov chain whose execution is influenced by a player: at each step, depending on the current state of the Markov chain, the player is allowed to choose which probability distribution will be used to make the transition to the next state. His choices are restricted to a finite set of distributions, also called actions. The goal of the player is to maximize his expected payoff, which is computed by a payoff function. Such a function associates to each infinite sequence of states and actions a real number. For arbitrary payoff function, the player may have to play very complex strategies to maximize his expected payoff. We are interested in positional payoff functions that make the job very simple for the player: whatever is the Markov decision process, the player is able to play optimally with no memory at all. More precisely, for each state, the player can choose again and again the same action each time the process reaches this state. We will present a theorem about positional payoff functions which provides a unified proof of several results previously known, as well as new examples of Markov decision processes in which simple optimal strategies are guaranteed to exist.o lundi 3 janvier 2011 à 11h salle 076 Ph. Duchon : 5 - Chaîne de Markov et génération aléatoire lundi 13 décembre 2010 à 11h salle 076 François Queyroi : Graphes aléatoires : (quelques) modèles et algorithmes Issus du célèbre modèle d'Erdös-Réyni introduit à la fin des années cinquantes, les graphes aléatoires ont suscité de nombreux travaux, particulièrement ces derniéres années. L'intérêt de tels objets est en effet multiple : détection de connexions manquantes, inférence sur des propriétés topologiques etc. On verra, au cours de ce bref état de l'art, que l'on peut distinguer deux approches, à savoir une approche algorithmique visant à reproduire certaines propriétés des réseaux et une approche statistique visant à estimer les paramètres d'un modèle probabiliste. On se focalisera sur la deuxième, peut-être moins connue au sein de la communauté informatique. Cette présentation sera également l'occasion de présenter une application des chaînes de Markov pour la maximisation de la vraisemblance d'un modèle. lundi 6 décembre 2010 à 11h salle 076 Ph. Duchon : 4 - Chaîne de Markov et génération aléatoire lundi 29 novembre 2010 à 11h salle 076 N. Bonichon : Routage à la boussole : comportement asymptotique sur un ensemble aléatoire de points Nous étudions quelques algorithmes de routage glouton dans le plan. En particulier, nous nous intéressons à des résultats asymptotiques, lorsque le nombre de points tend vers l’infini et sont choisis selon une distribution de probabilité à support borné. Nous obtenons des résultats asymptotiques concernant la géométrie des trajectoires, le nombre de points visités et le comportement de différentes fonctions de coût. Travail réalisé en collaboration avec Jean-François Marckert. lundi 22 novembre 2010 à 11h salle 075 Ph. Duchon : 3 - Chaîne de Markov et génération aléatoire lundi 8 novembre 2010 à 11h salle 076 C. Johnen : Circulation auto-stabilisante d'un jeton dans les anneaux unidirectionnels et anonymes Un des problèmes de base de l'algorithmique auto-stabilisante est la circulation de jeton. Nous étudierons ce problème dans un contexte particulièrement difficile : les anneaux anonymes unidirectionels où les processus sont asynchrones. Les vitesses respectives des processus varient au cours du temps et sont non bornées. Dans ce contexte, les techniques algorithmiques basées sur les marches aléatoires ne peuvent être utilisées. Nous présenterons la technique algorithmique utilisée et son analyse. lundi 18 octobre 2010 à 11h salle 075 Ph. Duchon : 2- Chaîne de Markov et génération aléatoire lundi 11 octobre 2010 à 11h salle 075 A. Zemmari : Algorithmique distribuée et probabilité En algorithmique distribuée, plusieurs problèmes n'admettent pas de solution déterministe sous certaines hypothèses (anonymat par exemple). On se retrouve donc à devoir concevoir une solution probabiliste à ces problèmes. Dans cet exposé, je montrerai quelques exemples de solutions probabilistes à des problèmes fondamentaux en algorithmique distribuée tels que le MIS, le coloriage ou la décomposition de graphes. Je présenterai en particulier une analyse d'un algorithme optimal pour réaliser le coloriage. Cet exposé présente des travaux menés en collaboration avec Y. Métivier, J.M. Robson et N. Saheb. lundi 4 octobre 2010 à 11h salle 076 Ph. Duchon : 1 - Chaînes de Markov et génération aléatoire Les chaînes de Markov d'espace d'états fini sont un type de processus aléatoires simple, qui sont particulièrement faciles à utiliser pour la mise au point d'algorithmes de génération aléatoire (uniforme ou non) d'objets discrets. lundi 27 septembre 2010 à 11h salle 076 JF Marckert : calculs et notions de base en probabilité lundi 20 septembre 2010 à 11h salle 076 : discussion ! |