Université de Montréal Faculté des Arts et des Sciences
Département d'Informatique et recherche opérationnelle
SEMINAIRES du DIRO
IFT6090, Hiver 2000

Gena Hahn et Felisa J. Vázquez-Abad

Salle 3195, Pavillon mathématiques et informatique, Université de Montréal

Page principale des séminaires
Vendredi le 28 janvier 2000 : 11h30
Francesc Comellas (UPC), Small-World Communication Networks. (abs)


Mardi le 1er fevrier : 11h30
Michel Dao (CNET France Telecom), Le projet Pétra : une expérience d'ingénierie de domaine. (abs)


Mardi le 8 fevrier : 11h30
Roland P. Malhamé (École Polytechnique et GERAD), Optimisation des règles de production à seuils critiques dans un atelier non fiable de fabrication multi-pièces (abs)


Mardi le 15 fevrier : 11h30
Felisa J. Vázquez-Abad (DIRO), Estimation des probabilités de blocage pour des réseaux de télécommunciations par simulation des chaînes de Monte Carlo. (abs)


Mardi le 22 fevrier : 11h30
François Major (DIRO), Les maladies causees par la proteine prion seraient-elles un vestige du monde de l'ARN? (abs)


Mardi le 7 mars : 11h30
Philippe Langlais (DIRO), Le développement de modèles d'unités dans un système d'aide à la frappe de traductions (abs)


Séminaire conjoint DIRO-GERAD: Jeudi le 16 mars : 14h30, Salle 4488
Peter Caines (McGill), Programmation Dynamique Hierarchique Accélerée (HADP) (abs)


Mardi le 21 mars : 14h30
Max Mignotte, Inférence bayésienne et/ou stratégie d'optimisation pour quelques problèmes de détection, segmentation, classification, restoration, et de suivi de forme en imagerie SONAR ou médicaleitre. (abs)


Mardi le 28 mars : 11h30
Balazs Kegl (Queens), Principal curves: learning, design, and applications (abs)


Vendredi le 31 mars : 11h30
Nicolas Meuleau (MIT), Contrôle optimal des processus partiellement observables sans inférence Bayésienne (abs)


Lundi le 3 avril : 11h30
Massimiliano Pontil (MIT), Kernel machines: theory and applications (abs)


Mardi le 4 avril : 11h30
Bruce Reed (CNRS Paris & McGill), Measuring Connectivity in Graphs (abs)


Jeudi 6 avril 12:30
Guy Mineau (Laval), Techniques d'élagages pour classifications conceptuelles d'objets complexes (abs)


Mardi le 11 avril : 11h30
Samy Bengio (IDIAP), Modélisation de données discrètes en haute dimension à l'aide de réseaux de neurones artificiels (abs)


Vendredi le 14 avril : 11h30
Hakim Lounis, Maintenance du logiciel : quelques travaux (abs)


Mardi le 18 avril : 11h30
Victor Ostromoukhov (MIT), Méthodes avancées de reproduction d'images en demi-ton. (abs)



Small-World Communication Networks

Francesc Comellas (Universitat Politècnica de Catalunya)

Many real life networks, including the world wide web, electric power grids, and social networks, are small-world networks. The two distinguishing characteristics of small-world networks are strong local clustering (nodes have many mutual neighbours), and small average distance between two nodes. Small-world networks are promising candidates for communication networks since typical data-flow patterns in communication networks show a large amount of clustering with a small number of ``long-distance'' communications that need to be completed quickly. Most previous research on small-world networks has used simulations, probabilistic techniques, and random replacements of edges to study the limiting behaviour of these networks. We initiate the study of small-world networks as communication networks using graph-theoretic methods to obtain exact results. We construct networks with strong local clustering and small diameter (instead of average distance). Our networks have the additional properties that they are regular and have constant degree.

Le projet Pétra : une expérience d'ingénierie de domaine

Michel Dao (CNET France Telecom)

L'ingénierie de domaine consiste à organiser les développements d'applications pour un domaine métier donné en les centrant autour d'une modélisation commune du domaine. Cette approche a pour avantage de favoriser la réutilisation lors des développements et l'interopérabilité des applications. Cette démarche comporte trois aspects: l'analyse du domaine, l'élaboration d'une architecture informatique pertinent et la construction d'un référentiel du domaine. Nous présenterons le projet Pétra, réalisé au CNET, qui constitue une expérience d'ingénierie du domaine du trafic dans les réseaux téléphoniques commutés.

Optimisation des règles de production à seuils critiques dans un atelier non fiable de fabrication multi-pièces

Roland P. Malhamé (École Polytechnique et GERAD)

Une formulation de type commmande stochastique optimale du problème de contrôle du flux de production dans un atelier de fabrication avec machines à pannes de type markovien est revue . Dans le cas mono-pièce, mono-machine, l'analyse exacte met en évidence des lois de commande à seuils d'inventaires critiques représentant un compromis optimal entre coûts de stockage des pièces et coûts associés aux retards de livraison . Ces lois de commande (Hedging Policies) sont également revues. Cependant, le cas multi-pièces mène à des équations de la programmation dynamique impossibles à résoudre analytiquement et trop lourdes au point de vue numérique. Nous optons donc de circonscrire nos recherches à l'intérieur d'une classe de lois de production sous-optimales paramétrisées par des seuils critiques et des taux de production admissibles constants par morceaux (Simple Maximal Hedging Policies). Pour un choix de paramètres donné, et dans le cas d'une machine non fiable multi-pièces, nous montrons que le coût de production total peut être décomposé en une somme de coûts associés à des machines individuelles fictives , une par pièce, non fiables et en général semi-markoviennes. Ces machines ont des priorités de production fixes. L'analyse des trajectoires des inventaires de pièces permet de mettre en évidence une technique de représentation markovienne approchée des machines fondée à la fois sur l'analyse des premiers temps de passage , et les approximations de Padé. La disponibilité d'une telle représentation permet de calculer les coûts associés exactement pour un choix donné de paramètres des lois de commande. Le problème de recherche des lois de commande est ainsi réduit à un problème d'optimisation non linéaire sur l'espace des paramètres. Des résultats numériques et de simulation sont présentés. Ce travail est conjoint avec Sami El-Férik de Pratt et Withney, et El-Kébir Boukas du département de Génie Mécanique de l'École Polytechnique de Montréal.

Estimation des probabilités de blocage pour des réseaux de télécommuncations par simulation des chaînes de Monte Carlo

Felisa J. Vázquez-Abad (DIRO)

Blocking probabilities in WDM optical networks as well as cellular networks are hard to compute for realistic sized systems, even though analytical formulas for the distribution exist. This computational difficulty is mainly due to the structure of the state space, which imposes strong coupling constraints amongst components of the occupancy vector. Direct simulation is often used to estimate the blocking probabilities. MCMC methods include Metropolis-Hastings and the Gibbs sampler, which we implement for the estimation of blocking. Next, we show how to implement a Filtered Monte Carlo estimator to the Gibbs sampler, for a randomised and a sequential version of it. The filtered estimators benefit from the variance reduction of conditional expectations and our simulation results suggest that that these methods dramatically outperform the currently used computational methods.

La performance des réseaux de télécommunciations optiques et céllulaires peut être exprimée comme la probabilité de blocage globale et il est possible de trouver une expression analytique en terme des probabilités stationaires d'un processus de naissances et de morts avec des barrières fortément dépendants de l'état. Cette formule requière un temps exponentiel de calcul en fonction du nombre de paires origine-destination et aussi du nombre de fréquences (ou canaux) disponibles pour chaque fibre optique (ou cellule respectivement). Ainsi, la simulation est souvant la méthode choisie pour calculer la performance pour des réseaux de taille réaliste. Or, la simulation directe utilise la méthode d'acceptation/reject est peut s'averer très inefficace. Nous avons implanté des méthodes de simulation par chaînes de Monte Carlo, dont Metropolis-Hastings et l'échantillonage de Gibbs. Dans quelques situations, ces méthodes sont plus performantes, et dans tous les cas, nous pouvons démontrer que le temps de calcul est linéaire par rapport a la taille du réseaux (pas exponentiel). En suite, nous proposons un lissage de la méthode de Gibbs pour réduire la variance. Nous pésentons des résultats de simulation.

Les maladies causees par la proteine prion seraient-elles un vestige du monde de l'ARN?

François Major (DIRO)

Les patients contenant plus de cinq copies d'un element repetes de 24 nucleotides dans leur gene de la proteine prion ont un plus grand risque de developper la forme familiale de la maladie de Creutzfeldt-Jakob. Les energies libres d'ARN structuree de l'ARN messager (ARNm) de la proteine du prion ont ete analysees et comparees a des versions aleatoirement permutées de l'ARNm. Nos resultats indiquent la presence de plusieurs ARN fonctionnels stables qui pourraient etre impliques dans l'expression, la traduction ou la degradation de l'ARNm. Parmi ces ARN fonctionnels se trouvent un antisens inhibiteur du gene de la proteine prion et un pseudo-noeud possedant les proprietes suffisantes pour se lier aux proteines. Ces ARN fonctionnels ont aussi ete detectes dans l'ARNm de 64 autres organismes vivants, incluant les genes Sup35, Ure2p et Rnql de la levure. Il est probable que ces vestiges de l'epoque procaryotique soient impliques dans le changement de conformation entre une proteine prion normale et sa forme maligne qui induit la maladie.

Le développement de modèles d'unités dans un système d'aide à la frappe de traductions

Philippe Langlais (DIRO)

Nous présentons nos travaux pour le développement de modèles de langue et de traduction dans le cadre du projet TransType qui représente un nouveau type d'outil interactif à l'intention des traducteurs professionnels. TransType observe l'utilisateur à mesure qu'il tape une traduction et tente constamment d'anticiper ses intentions en proposant des "suites" aux portions de texte déjà tapées. L'accent sera mis sur la description du modèle probabiliste qui autorise la complétion d'unités, c'est-à-dire des suites de mots syntaxiquement et/ou sémantiquement liés.

Programmation Dynamique Hierarchique Accélerée (HADP)Titre

Peter Caines (Département de génie électrique et informatique, McGill)

La notion d'aggregation d'etat pour une machine M a etat fini (FSM) est fondee sur la relation introduite par Caines et Wei, 1995, de la dynamique coherente entre les blocs d'une partition d'etat quelconque \pi de la machine.
Dans ce travail, avec Dr Gang Shen, on presente la notion de la coherence dynamique (ST-DC) pour les machines a source-destination (ST FSMs) ou le sens de la circulation de l'etat source (S) a l'etat cible (T) est favorise. Ceci donne la definition de la dynamique a haut niveau sur la machine a partition qui est la machine finie correspondante a la partition \pi des blocs donnee.
Si une partition \pi est ST controllable en bloc (ST-IBC), une machine a partition M^\pi d'une ST FSM M est controllable si et seulement si M est controllable. De plus, toutes les machines a partition ST-IBC de M constituent un treillis et toute cha\^ine du haut au bas de ce treillis donne une structure hierarchique de commande a retour.
Nous introduisons la methodologie applee programmation dynamique hierarchique acceleree (HADP), qui accelere sensiblement la procedure de la programmation dynamique standard pour des problemes de trajet optimal au co\^ut d'une certaine sous-optimalite. On donne des limites theoriques au degre de sous-optimalite de l'approche. Un exemple d'une implementation de la methode HADP a un probleme de transport simplifie est aussi donne.

Inférence bayésienne et/ou stratégie d'optimisation pour quelques problèmes de détection, segmentation, classification, restoration, et de suivi de forme en imagerie SONAR ou médicale.

Max Mignotte (DIRO)

L'usage de l'imagerie numérique est en forte progression et occupe une place de choix parmi les méthodologies d'extraction et de représentation des connaissances. La modélisation statistique et le traitement de ces données numérisées permet de réaliser automatiquement des opérations telle que la détection (de zone d'interêt, de forme, etc.), de segmentation, de restoration ou de classifications (de forme, d'objet, etc.) indispensables en robotique, télédétection, imagerie SONAR, imagerie médicale, etc.

Pour ces différents problèmes, la théorie bayésienne de la décision fournit un cadre méthodologique particulièrement intéressant dans lequel certaines propriétés locales ou globales, liées aux informations que l'on cherche à obtenir en imagerie (i.e., la détection d'une zone précise, la segmentation et le suivi d'une forme au cours du temps, etc.), peuvent être prises en compte, estimées (ou définies a priori), modélisées puis intégrées dans un modèle statistique incluant aussi les processus physiques de formation de l'image. En particulier, les bruits multiples intervenant dans les différentes étapes du processus de formation de l'image en sont un exemple. Placée dans ce contexte, la recherche de la solution se réduit à un problème d'optimisation globale. Ce problème reste néanmoins difficile et coûteux en temps de calcul dans la mesure où les fonctions d'énergie à minimiser sont complexes, généralement non linéaires, et dépendent quelquefois d'un nombre plus ou moins important de variables.

Dans cet expose, nous présenterons quelques applications de l'approche Bayésienne Markovienne pour des problèmes de segmentation, de classification d'objets et de classification des fonds en imagerie SONAR ou encore pour des problèmes d'imagerie médicales tel que la détection puis le suivi de formes anatomiques (comme le suivi du contour endocardial dans une séquence d'image échographique) ou encore la restoration d'imagerie médicale (imagerie 3D SPECT). Pour chacune de ces applications, nous préciserons brièvement le modèle statistique reposant sur une formulation bayésienne (ou Markovienne) utilisé, et l'algorithme de relaxation permettant de minimiser efficacement la fonction d'énergie associée à ce modèle.


Principal curves: learning, design, and applications

Balazs Kegl (Queens University)

The subjects of this talk are unsupervised learning in general, and principal curves in particular. Principal curves were introduced by Hastie and Stuetzle (hereafter HS) in a statistical framework to formally capture the notion of a smooth curve passing through the "middle" of a d-dimensional probability distribution or data cloud. In the first part of the talk we introduce the HS definition and some of the alternative definitions and methods for estimating principal curves, and locate principal curves in the family of unsupervised learning methods. We also highlight some of the applications in image analysis, feature extraction, and speech processing.

Although the concept of principal curves as considered by HS has several appealing characteristics, complete theoretical analysis of the model seems to be rather hard. This motivated us to redefine principal curves in a manner that allowed us to carry out extensive theoretical analysis while preserving the informal notion of principal curves. In the second part of the talk we introduce this new theoretical model and analyze it by using tools of statistical learning theory.

The theoretical model proved to be too restrictive to be practical. However, it inspired the design of a new practical algorithm to learn principal curves based on data. In the last part of the talk we describe the polygonal line algorithm, which compares favorably with previous methods both in terms of performance and computational complexity, and present an application to hand-written character skeletonization.


Contrôle optimal des processus partiellement observables sans inférence Bayésienne

Nicolas Meuleau (MIT)

La théorie de la programmation dynamique est la base de nombreuses techniques de planification dans l'incertain. Cependant, elle suppose que l'état du processus à controler est parfaitement connu à chaque instant. La programmation dynamique peut aussi être utilisée quand l'état n'est que partiellement observable, mais sa complexité est alors exponentielle. L'approche Bayésienne permet de calculer une solution optimale, mais elle nécessite de reformuler le problème dans l'espace continu des fonctions de croyance, c'est-à-dire dans l'ensemble des distributions de probabilité sur l'état du système.

Cet exposé présente une approche alternative consistant à chercher directement dans l'espace des stratégies. Je présenterai les motivations et les fondements théoriques de cette approche, puis je montrerai qu'elle peut être appliquée à une grande variété de types de stratégies, notamment les contrôleurs à états finis et les systèmes multi-agent. Des résultats expérimentaux obtenus avec une variété de problèmes illustrent l'efficacité de cette approche.


Kernel machines: theory and applications

Massimiliano PONTIL (MIT)

This talk is about learning from examples using a large family of machines, namely kernel machines. These machines can be seen as minimizers of a regularization functional in an Hilbert Space. Important types of kernel machines are Support Vector Machines and Regularization Networks. I will first present a unified theoretical justification of general kernel machines within a technical extension of Vapnik's Statistical Learning Theory and show distribution independent bounds on their generalization error. Then, I will show applications of these techniques to the problem of object detection and recognition in cluttered images. Finally, I will turn to the problem of learning using voting ensembles of kernel machines. For example, each machine could be trained on a small subset of the data or using different features of the examples. I will discuss practical bounds on the generalization performance of such voting ensembles through a computation of a bound on their cross validation error. I will present experiments supporting the theoretical findings and describe characteristics of kernel machines ensembles suggested from the experiments.

Measuring Connectivity in Graphs

Bruce Reed (CNRS Paris et McGill)

A graph is a set of vertices and an adjacency relation which indicates which pairs of vertices are joined by an edge. Thus, graph theory is essentially the study of connectivity. How then does one measure the connectivity of a graph?

Measuring the connectivity between two vertices is straightforward. A classical theorem of Menger provides easily verifiable neccesary and sufficent conditions for a pair of vertices to be k-connected. This characterization is the basis for much of combinatorial optimization. An appropriate definition of a highly connected graph, or of a highly connected piece of a graph is more difficult. The classical approach is to call a graph k-connected if every pair of its vertices is k-connected. This definition, although natural, does not capture the kind of connectivity that will concern us. It focuses on local properties rather than global ones. The goal of this talk is to introduce the audience to a connectivity invariant, the bramble number, which measures global connectivity. The study of this connectivity measure has proven very fruitful. Indeed this new notion may be as fundamental as that of k-connectivity. We will present some of the many results obtained using this technique. The talk is directed at a wide audience.

La présentation sera faite en français.

Techniques d'élagages pour classifications conceptuelles d'objets complexes

Guy Mineau (Laval)

Les techniques de classification conceptuelle appliquées à de larges ensembles d'objets complexes doivent composer avec des problèmes de complexité inhérents à la représentation même des objets : de trop nombreuses généralisations communes peuvent exister entre objets. Afin de pouvoir appliquer ces techniques en contexte industriel où l'on doit traiter de grands volumes de données, des simplifications doivent être apportées à la détection de similarités communes entre objets afin de restreindre les problèmes de complexité associés à ces techniques. Conséquemment, les similarités communes trouvées sont moins fiables; les structures de classification produites comportent donc des classes d'objets très peu utiles. Les classes utiles de la structure peuvent alors être perdues parmi plusieurs classes inutiles. Afin d'améliorer la fiabilité et l'utilité de la structure de classification produite, des techniques d'élagage applicables dans un tel contexte de structures de classification volumineuses doivent être envisagées.

Les techniques traditionnelles basées sur des évaluateurs statistiques ont besoin d'une vision globale de l'ensemble des données afin de réévaluer la pertinence de chaque classe en termes des objets qu'elle couvre et des classes avoisinantes : elles ont besoin d'un support statistique. Les techniques que nous proposons ici ne visent qu'à modifier la topologie de la structure produite afin d'éliminer les classes jugées localement inutiles. Nous visons ainsi à mettre en place des techniques d'élagage qui sont le plus possible indépendantes de la taille de la structure de classification sur laquelle elles sont appliquées, toujours dans un souci d'application de ces techniques dans un contexte industriel.

Cet exposé présentera certaines approches d'élagage de structures de classification pour objets complexes où le volume de données est important. Il s'agit de techniques de pré-élagage (prepruning) et de post-élagage (postpruning) qui visent à modifier la topologie de la structure afin d'améliorer à la fois le potentiel de caractérisation du domaine ainsi représenté (par l'enlèvement de classes et liens jugés moins utiles), et certaines métriques desquelles dépend l'efficacité des applications qui s'en servent.


Modélisation de données discrètes en haute dimension à l'aide de réseaux de neurones artificiels

Samy Bengio (Institut Dalle Molle d'Intelligence Artificielle Perceptive)

Le "data mining" s'intéresse à l'exploration et surtout l'exploitation d'immenses bases de données de millions de fiches contenant chacune des centaines d'informations différentes (par exemple, les comportements des clients d'un service financier ou d'un service téléphonique). L'objectif consistant à trouver une structure permettant de modéliser puis d'exploiter efficacement de telles bases de données se heurte souvent au problème de "la malédiction de la dimensionalité" (curse of dimensionality).

Cette présentation commence donc par une introduction à la problématique du "data mining" et explique les limites des méthodes actuelles permettant de modéliser la fonction de probabilité jointe de centaines de variables aléatoires discrètes.

Un nouveau modèle est ensuite proposé, utilisant des réseaux de neurones artificiels afin de représenter la distribution jointe sous la forme d'un produit de distribution conditionnelles. Ce modèle utilise un nombre de ressources de l'ordre du carré du nombre de variables mais permet néanmoins de modéliser des relations d'ordre supérieur entre les variables. Ceci est une contribution importante car les modèles connus jusqu'à présent pouvant représenter des relations d'ordre supérieur requièrent plutôt un nombre exponentiel de ressources. Le modèle peut être interprété comme un réseau de Bayes sans variables cachées mais dans lequel les paramètres des distributions conditionnelles sont partiellement partagés selon une connectivité particulière. Cette connectivité peut d'ailleurs être élaguée afin de réduire d'avantage le nombre de paramètres libres du système.

Des expériences sur différents jeux de données montrent une amélioration statistiquement significative de la performance du modèle proposé par rapport à d'autres modèles tels que des réseaux de Bayes, particulièrement lorsque le réseau de neurones est élagué.

email


Maintenance du logiciel : quelques travaux

Hakim LOUNIS (CRIM)

Les coûts en maintenance perfective et corrective du logiciel sont très élevés. Ils sont accentués par la nécessité de comprendre les programmes existants, à laquelle vient se greffer des facteurs aggravants. Dans ce contexte, je présenterai deux stratégies non exclusives pour apporter des solutions à cette problématique. La première, en aval, la rétro-ingénierie et la seconde, en amont, consistant à produire des modèles prédictifs à même d?estimer ces coûts élevés de maintenance.


Méthodes avancées de reproduction d'images en demi-ton.

Victor Ostromoukhov (MIT Computer Graphics Group)

La reproduction d'images en demi-ton (digital halftoning) est une branche d'infographie située au croisement entre géométrie algorithmique, mathématiques discrètes, science de la couleur et ingénierie. Dans cet exposé, nous verrons d'abord l'ensemble de problèmes posés par la reproduction en demi-ton traditionnelle. Je présenterai ensuite les solutions que nous avons développées et qui permettent de réduire les artefacts de reproduction, notamment ceux provoqués par le phénomène de Moiré ou ceux liés à la nature discrète des grilles. Nous verrons ensuite des extensions des méthodes de reproduction traditionnelles: le tramage artistique, la reproduction avec les encres non-standards, la gravure et le dessin assistés par ordinateur, le rendu non-photoréaliste.

Cet exposé présente d'une manière synthétique le travail de recherche de Victor Ostromoukhov au sein du LSP-EPFL (Laboratoire de Systèmes Périphériques, à l'Ecole Polytechnique Fédérale de Lausanne) et du CGG-MIT (The MIT Computer Graphics Group), pendant les cinq dernières années.