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
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
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?
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
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.
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
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
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
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
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
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.
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.