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.

lundi 11 avril 2011 à 11h salle 076
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
Valentin Feray : Pasep, permutations et distribution stationnaire limite

Le PASEP (Partially Asymetric Simple Exclusion Process) est un modèle simple de physique statistique. Il s'agit d'une chaîne de Markov sur les mots binaires de longueur n. Sa mesure stationnaire peut être décrite combinatoirement en utilisant des permutations (travaux de S. Corteel et L. Williams). Nous allons expliquer ces résultats, puis étudier le comportement de la mesure stationnaire quand n tend vers l'infini.

lundi 21 mars 2011 à 11h salle 076
Ph. Duchon : 9 - Chaîne de Markov et génération aléatoire

lundi 7mars et 7 mars 2011 à 11h salle 076
Paul Dorbec : Suite !

lundi 28 février et 7 mars 2011 à 11h salle 076
Paul Dorbec La méthode probabiliste en théorie des graphes.

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
Ph. Duchon : 8 - Chaîne de Markov et génération aléatoire

lundi 7 février 2011 à 11h salle 076
François Caron : Modèles statistiques et algorithmes pour le classement

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.
Article:
http://hal.archives-ouvertes.fr/docs/00/53/36/38/PDF/rankingv13_inria.pdf

lundi 31 janvier 2011 à 11h salle 076
Ph. Duchon : 7 - Chaîne de Markov et génération aléatoire

lundi 24 janvier 2011 à 11h salle 076
Nasser Saheb : CPO des mesures
Afin de formaliser la sémantique dénotationnelle des programmes probabilistes, nous introduisons le cpo (complete partial order) des mesures de probabilité. Cette approche permet d'éviter les identifications non souhaitables, liées à un préordre imposé dans l'approche relationnelle du non-déterminisme. Nous étudions ensuite les propriétés importantes de cette construction.

lundi 17 janvier 2011 à 11h salle 076
Ph. Duchon : 6 - Chaîne de Markov et génération aléatoire

lundi 10 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 !