suivant: À propos de ce
Ce séminaire est étroitement associé au groupe PAGE Probabilités et Applications de Grenoble et ses Environs
L'objectif est de permettre les contacts entre des chercheurs de différentes communautés Grenobloises travaillant avec les mêmes familles d'outils. Cela devrait déboucher sur une activité de ``type'' groupe de travail inter-laboratoires sur des thématiques précises.
Jeudi 11 mai 2006 de 14h00-15h00
Salle de séminaire du laboratoire ID-IMAG
Résumé :
In this talk we briefly discuss the application of Markov chains to large scale systems modeling and examine the effectiveness of using Kronecker product preconditioners to compute the stationary distribution of the Markov chain.
Many very large Markov chains can be represented efficiently as Stochastic Automata Networks (SAN). A SAN is composed of individual automata which often act independently, requiring only infrequent interaction. SANs represent the transition rate matrix of the underlying Markov chain compactly as the sum of Kronecker products of smaller matrices. Thus memory savings are immediate. Unfortunately, the benefit of a SAN's compact representation, known as the descriptor, is often out-weighted by its tendency to make analysis of the underlying Markov chain tough.
While iterative or projection methods have been used, the time til these methods converge is still unsatisfactory. SAN's compact representation has made the next logical research step of preconditioning thorny. Several preconditioners for SANs have been proposed and tested, yet each has enjoyed little or no success. Encouraged by the recent success of approximate inverses as preconditioners, we have explored the use of the nearest Kronecker product of Pitsianis and Van Loan.
Jeudi 5 janvier 2006 de 15h30-16h30
Amphi Gastinel F022 Batiment UFR-IMA
Résumé :
The key operation to obtain stationary and transient solutions of models described by Kronecker structured formalisms using iterative methods is the Vector-Descriptor product. This operation is usually performed with the Shuffle algorithm, which was proposed to Stochastic Automata Networks, but it is also currently used by Stochastic Petri Nets and Performance Evaluation Process Algebra solvers. This paper presents an alternative algorithm to perform the Vector-Descriptor product, called Slice algorithm. The numerical advantages of this new algorithm over the previous one is shown to SAN models, in which the computational costs are compared. Finally, we discuss some possible optimizations of the Slice algorithm and implementation issues regarding parallel versions of both algorithms.
Jeudi 24 novembre 2005 de 15h00-16h00
Salle de Séminaire Laboratoire Informatique et Distribution
Résumé :
Cet exposé porte sur l'étude des performances des réseaux de Petri à choix libres temporisés. La mesure que nous étudions est le débit, défini comme le nombre moyen de transitions franchies par unité de temps. Le débit dépend de la suite de tirs choisie, et donc d'une politique de résolution de conflits (au niveau des places de choix). Nous étudions trois politiques de résolution de conflits : le routage Bernoulli, le routage périodique déterministe et la politique de compétition.
Dans un premier temps, nous montrons l'existence du débit pour ces politiques de routage, et montrons comment le calculer pour des temporisations exponentielles. Dans un deuxième temps, nous présentons un algorithme de simulation exacte qui permet d'evaluer le débit quand les calculs exacts ne sont plus faisables. Enfin, nous montrons comment trouver la politique qui optimise le débit en fonction de l'information disponible.
Centre Saint-Hugues de Biviers
Jeudi 29 septembre 2005 Amphi Vauquois UFR-IMA
Résumé :
Globalement, je pense présenter le problème de classification (en général) lorsqu'on a des informations de type distances entre individus, avec quelques applications (segmentation, reconnaissance de textures, clustering de données biologique...). Plus précisement je présente l'approche markovienne avec une formulation sous forme d'énergie à minimiser et après je passe en revue un certain nombre de techniques pour cela, ex Relaxation, Champ moyen etc...
Jeudi 16 juin 2005 Amphi Vauquois UFR-IMA
Résumé :
Dans cet exposé on étudie des modèles mathématiques pour les centres d'appels, ou, plus généralement, les centres de contacts clients. On parle des modèles utilisés actuellement pour la gestion des centres d'appels, et ensuite on discutons les imperfections de ces modèles. Puis nous traitons des modèles plus avancés liés aux fluctuations des paramètres, et aux centres d'appels avec plusieurs compétences et plusieurs canaux de communication. Finalement on expose des développements récents liés à la transition d'un centre de coût à un centre de profits et lié au besoin de donner des priorités différentes aux différents types d'appels.
Les systèmes de distribution de contenu comme les caches web et les réseaux d'échanges de fichiers doivent être capables de servir une population de clients à la fois très grande (centaines de milliers) et fortement dynamique (temps de connexion très courts). Ces caractéristiques rendent leur analyse très coûteuse par les approches traditionnelles comme les modèles markoviens ou la simulation. Dans ces travaux nous proposons des modèles fluides simples permettant de s'affranchir de l'une des dimensions du problème. Nous les appliquons à différents systèmes de distribution de contenu, en particulier des systèmes de caches web et un système pair-à-pair de distribution de fichiers appelé BitTorrent.
Nous montrons que ces modèles permettent, pour une faible complexité, de mieux comprendre ces systèmes et de résoudre certains problèmes d'optimisation.
Une chaîne de Markov constructive indexée parvérifiant une relation de récurrence de la forme
où
est une variable aléatoire indépendante de la suite
. La suite
s'appelle la suite des «innovations» de la chaîne. La filtration naturelle
de la suite
est alors « à accroissements indépendants » puisque
et
.
Cependant, il existe des exemples simples oùbien que la tribu asymptotique
soit triviale (
Lorsque les variables aléatoiressont iid et à valeurs dans un ensemble dénombrable, une condition suffisante (due à Rosenblatt) pour que la suite
soit "point - collapsing", c'est-à-dire qu'une certaine composée d'applications
est constante. L'utilisation de telles composées est d'ailleurs l'ingrédient de l'algorithme de simulation exact de Propp et Wilson.
Dans le cas où la tribuindépendante de la suite
et de loi uniforme sur
ou sur un ensemble fini telle que
.
D'une manière générale, l'invariance d'ensembles ainsi que les techniques de comparaisons et/ou de réductions de systèmes dynamiques (linéaires, non-linéaires, stochastiques) sont des notions qui se retrouvent dans plusieurs disciplines: automatique-controle, probabilités appliquées, informatique, économie.
Ces liens ont d'abord été étudies pour des systèmes linéaires sur des semi-anneaux ou semi-corps idempotents. Mais ici nous présentons les résultats pour les systèmes linéaires sur (R,+,x).
L'approche géométrique nous permet d'identifier les liens existants entre ces différentes notions dans le cas suivant: -invariance positive de polyèdres, -technique de comparaison via des ordres linéaires, -technique de réduction via weak lumpability.
De ces relations, il est par exemple possible de fournir la condition nécessaire et suffisante de comparaison point a point sur des chaînes de Markov a espace d'état différents.
Ce travail s'inscrit dans le cadre d'un projet MathSTIC2004-05 intitule: « Contrôle de Systèmes a Événements Discrets via des Techniques de Comparaison et de Réduction de Systèmes Stochastiques ».
Références et résumé des transparents
Jean Mairesse
mairesse[at]liafa.jussieu.fr
http://www.liafa.jussieu.fr/
mairesse
LIAFA
Paris
Jeudi 13 janvier 2005 UFR-IMA
Résumé :
On définit une famille de groupes discrets qui contient les groupes finis, les groupes libres et qui est stable par produit libre. On montre que toute marche aléatoire transiente et au plus proche voisin sur le (graphe de Cayley du) groupe admet une mesure harmonique Markovienne. Cette mesure est entièrement détermine par la résolution d'un système d'équations polynomiales. Une conséquence est que la dérive (vitesse de fuite) ou encore l'entropie de la marche aléatoire est `explicitement' calculable. Dans le cas du groupe libre, on retrouve des résultats classiques essentiellement dus a Dynkin et Malyutov (1961).
On montrera comment ces résultats peuvent s'interpréter pour l'évaluation de performances de files d'attente. On montrera également une application a l'étude des tresses aléatoires a trois brins.
Jean-Marc Vincent
ID-IMAG
Projet Decore-Imag
Projet Inria-Imag APACHE
Jean-Marc.Vincent[at]imag.fr
http://www-id.imag.fr/Laboratoire/Membres/Vincent_Jean-Marc/
Jeudi 2 décembre 2004 UFR-IMA
Résumé :
L'estimation de la distribution stationnaire de chaînes de Markov est un problème central en évaluation de performances de systèmes et de réseaux. Les méthodes traditionnelles reposent sur la simulation de trajectoires et l'utilisation du théorème ergodique (proportion de passage dans un état donné). En physique statistique, Propp & Wilson ont proposé une méthode d'échantillonnage selon la loi stationnaire par couplage dans le passé (Perfect Sampling). Nous adaptons cette méthode au contexte de l'évaluation de performances. Le plan de l'exposé est le suivant:
1) Simulation parfaite de fonctionnelles de chaînes de Markov non monotones
2) PSI : un logiciel de simulation parfaite
3) Réseaux de files d'attente et simulation parfaite
4) PSI2 : un logiciel de simulation parfaite de modèles markoviens multidimensionnels monotones
Travail joint avec Corine Marchand, Florent Morata, Bernard Tanzi, Abdelhak Imoussaten
Les codes correcteurs d'erreurs FEC (pour: Forward Error Correction) peuvent être utilisés dans les réseaux pour compenser la perte de paquets, dans les cas où la retransmission d'information est trop coûteuse, ou inutile. L'efficacité de la FEC dépend de la façon dont les pertes de paquets se regroupent. Il est généralement admis que FEC marche mieux quand les pertes ne sont pas en rafales.
Le sujet de l'exposé est l'interaction de FEC avec deux mécanismes standards de gestion des files d'attente: Drop Tail et RED, qui sont les causes de pertes de paquets. Nous montrons par simulations et à l'aide d'un modèle simplifié que FEC fonctionne mieux avec RED qu'avec Drop Tail, ce qui était attendu, mais seulement pour certaines conditions sur le trafic et le taux de redondance. Ceci montre qu'un réseau sans rafales de pertes de paquets, ce qui est effectivement le cas avec RED, n'est pas une garantie d'efficacité pour l'utilisation de FEC.
Il s'agit d'un travail joint avec T. Alemu et Y. Calas.