Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Le travail que nous présentons dans ce mémoire apporte sa contribution au domaine dela surveillance et de la supervision en ligne des systèmes à événements discrets complexes.Il se place dans un contexte perturbé par l'occurrence d'aléas de fonctionnement d'une partieopérative au sein duquel nous visons à mettre à disposition des équipes de maintenance desoutils pour les aider à localiser rapidement les équipements à l'origine probable de défautsproduits : localiser mieux pour maintenir mieux et donc minimiser encore davantage les tempsde dérives équipements. Si les équipements de production étaient en mesure de détecterde telles dérives, le problème pourrait être considéré comme simple, cependant, la présenced'équipements de métrologie montre le contraire. Aussi, partant du constat que les équipementsde production ne peuvent être dotés d'un système de captage couvrant de manière exhaustivel'ensemble des paramètres à observer, que la fiabilité des capteurs est variable dans le temps,que les contextes de production sont particulièrement stressants, nous avons proposé ici dedévelopper une approche probabiliste basée sur un raisonnement Bayésien permettant d'estimeren temps réel la confiance qui peut être accordée aux opérations réalisées par les équipementsde production.

La génération aléatoire d'objets combinatoires est un problème qui se pose dans de nombreux domaines de recherche (réseaux de communications, physique statistique, informatique théorique, combinatoire, etc.). Couramment, la distribution des échantillons est définie comme la distribution stationnaire d'une chaîne de Markov ergodique. En 1996, Propp et Wilson ont proposé un algorithme permettant l'échantillonnage sans biais de la distribution stationnaire. Ce dernier appelé aussi algorithme de simulation parfaite, requiert la simulation en parallèle de tous les états possibles de la chaîne. Plusieurs stratégies ont été mises en œuvre afin de ne pas avoir à simuler toutes les trajectoires. Elles sont intrinsèquement liées à la structure de la chaîne considérée et reposent essentiellement sur la propriété de monotonie, la construction de processus bornants qui exploitent la structure de treillis de l'espace d'états ou le caractère local des transitions. Dans le domaine des réseaux de communications, on s'intéresse aux performances des réseaux de files d'attente. Ces derniers se distinguent en deux groupes : ceux dont la distribution stationnaire possède une forme produit qui est facile à évaluer par le calcul et les autres. Pour ce dernier groupe, on utilise la génération aléatoire pour l'évaluation de performances. De par la structure des chaînes qui leurs sont associées, les réseaux ouverts de files d'attente se prêtent bien à la simulation via l'algorithme de simulation parfaite mais pas les réseaux fermés. La difficulté réside dans la taille de l'espace des états qui est exponentielle en le nombre de files à laquelle s'ajoute une contrainte globale à savoir le nombre constant de clients. La contribution principale de cette thèse est une nouvelle structure de données appelée diagramme. Cette structure est inspirée de la programmation dynamique et introduit une nouvelle technique de construction de processus bornant. La première partie du manuscrit est consacrée à la mise en œuvre de l'algorithme de Propp et Wilson pour des réseaux fermés n'étant pas nécessairement à forme produit. La représentation des états par un diagramme et l'opération de transition pour le processus bornant a dès lors une complexité polynomiale en le nombre de files et de clients. Cette technique est ensuite étendue aux réseaux fermés multiclasses ainsi qu'aux réseaux possédant des synchronisations. Une spécification des ensembles d'objets pouvant être représentés par un diagramme ainsi que des algorithmes agissant sur cette structure de données sont également proposés dans cette thèse. La méthode de Botzmann est une autre technique de simulation sans biais. Basée sur la combinatoire analytique, elle permet l'échantillonnage uniforme d'objets appartenant à une même classe combinatoire. Elle est employée dans la seconde partie de cette thèse afin d'échantillonner la distribution stationnaire de réseaux fermés à forme produit et pour la génération des multi-ensembles de taille fixe. Dans ce cadre, les diagrammes sont une nouvelle fois mis à profit. Enfin, la troisième partie présente les logiciels découlant des travaux présentés tout au long de ce travail, et qui implémentent les diagrammes et mettent en œuvre la simulation parfaite de réseaux fermés de files d'attente. / Random generation of combinatorial objects is an important problem in many fields of research (communications networks, theoretical computing, combinatorics, statistical physics, ...). This often requires sampling the stationary distribution of an ergodic Markov chain. In 1996, Propp and Wilson introduced an algorithm to produce unbiased samples of the stationary distribution, also called a perfect sampling algorithm. It requires parallel simulation of all possible states of the chain. To avoid simulating all the trajectories, several strategies have been implemented. But they are related to the structure of the chain and require a monotonicity property, or a construction of a bounding chain that exploits the lattice structure of the state space or the local character of the transitions.In the field of communications networks, attention is paid to the performance of queueing networks, that can be distinguished into two groups: the networks that have a product form stationary distribution which is easy to compute. Random generation can be used for the others. Perfect sampling algorithms can be used for open queueing networks, thanks to the lattice structure of their state space. Unfortunately, that is not the case for closed queueing networks, due to the size of the state space which is exponential in the number of queues and a global constraint (a constant number of customers). The main contribution of this thesis is a new data structure called a diagram. It is inspired by dynamic programming and allows a new technique of construction of bounding processes. The first part of the manuscript is devoted to the implementation of the Propp and Wilson algorithm for closed queueing networks. The representation of a set of states by a diagram and the transition operation for the bounding process has a polynomial complexity in the number of queues and customers. This technique is extended to closed multi-class networks and to networks with synchronizations. Specification of sets of objects that can be represented by a diagram and generic algorithms that use this data structure are proposed in this manuscript. The Boltzmann method is another unbiased sampling technique. It is based on analytical combinatorics and produces uniform samples from objects that belong to the same combinatorial class. It is used in the second part of this thesis in order to sample the stationary distribution of closed networks with product form and for the generation of multisets of fixed cardinality. Diagrams are used again in this context. Finally, the third part presents the software produced during this thesis, implementing diagrams and perfect simulation of closed queueing networks.

Lors de dette dernière décennie, l'évolution des technologies a permis le développement de drones de taille et de poids réduit aptes à évoluer dans des environnements intérieurs ou urbains. Pour exécuter les missions qui leur sont attribuées, les drones doivent posséder un système de navigation robuste, comprenant, notamment, une fonctionnalité temps réel d'ego-localisation précise dans un repère absolu. Nous proposons de résoudre cette problématique par la mise en correspondance des dernières images acquises avec des images géoréférencées de type Google Streetview.Dans l'hypothèse où il serait possible pour une image requête de retrouver l'image géo-référencée représentant la même scène, nous avons tout d'abord étudié une solution permettant d'affiner la localisation grâce à l'estimation de la pose relative entre ces deux images. Pour retrouver l'image de la base correspondant à une image requête, nous avons ensuite étudié et proposé une méthode hybride exploitant à la fois les informations visuelles et odométriques mettant en oeuvre une chaîne de Markov à états cachés. Les performances obtenues, dépendant de la qualité de la mesure de similarité visuelle, nous avons enfin proposé une solution originale basée sur l'apprentissage supervisé de distances permettant de mesurer les similarités entre les images requête et les images géoréférencées proches de la position supposée. / In this last decade, technology evolution has enabled the development of small and light UAV able to evolve in indoor and urban environments. In order to execute missions assigned to them, UAV must have a robust navigation system, including a precise egolocalization functionality within an absolute reference. We propose to solve this problem by mapping the latest images acquired with geo-referenced images, i.e. Google Streetview images.In a first step, assuming that it is possible for a given query image to retrieve the geo-referenced image depicting the same scene, we study a solution, based on relative pose estimation between images, to refine the location. Then, to retrieve geo-referenced images corresponding to acquired images, we studied and proposed an hybrid method exploiting both visual and odometric information by defining an appropriate Hidden Markov Model (HMM), where states are geographical locations. The quality of achieved performances depending of visual similarities, we finally proposed an original solution based on a supervised metric learning solution. The solution measures similarities between the query images and geo-referenced images close to the putative position, thanks to distances learnt during a preliminary step.

Cette thèse contient deux parties: la simulation des événements rares et le rééchantillonnage non-intrusif stratifié pour la programmation dynamique. La première partie consiste à quantifier des statistiques liées aux événements très improbables mais dont les conséquences sont sévères. Nous proposons des transformations markoviennes sur l'espace des trajectoires et nous les combinons avec les systèmes de particules en interaction et l'ergodicité de chaîne de Markov, pour proposer des méthodes performantes et applicables en grande généralité. La deuxième partie consiste à résoudre numériquement le problème de programmation dynamique dans un contexte où nous avons à disposition seulement des données historiques en faible nombre et nous ne connaissons pas les valeurs des paramètres du modèle. Nous développons et analysons un nouveau schéma composé de stratification et rééchantillonnage / This thesis contains two parts: rare events simulation and non-intrusive stratified resampler for dynamic programming. The first part consists of quantifying statistics related to events which are unlikely to happen but which have serious consequences. We propose Markovian transformation on path spaces and combine them with the theories of interacting particle system and of Markov chain ergodicity to propose methods which apply very generally and have good performance. The second part consists of resolving dynamic programming problem numerically in a context where we only have historical observations of small size and we do not know the values of model parameters. We propose and analyze a new scheme with stratification and resampling techniques.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

L’observance, qui décrit à quel degré le patient suit la prescription, est un facteur essentiel pour que le traitement réussisse. Les observances des patients varient beaucoup et l’efficacité du médicament varie parallèlement. Par conséquent, il faut avoir des paramètres sensibles et fiables pour mesurer l’observance. Dans la littérature, on trouve beaucoup de paramètres pour évaluer l’observance mais leurs avantages, limites et inconvénients, en ce qui concerne l’évaluation de l’impact de l’observance sur les effets des médicaments n’ont pas encore été étudiés en profondeur. L’évaluation de ces paramètres nécessite de les tester dans différentes situations. Comme les données disponibles sur l’observance ne concernent pas un ensemble exhaustif de situations, le recours à la simulation, en s’inspirant des cas réels ou plausibles, est très pertinent. On a ainsi réussi à développer un modèle dont les paramètres sont simples et compréhensibles et qui est pratique et flexible pour simuler les différents cas et même les cas extrêmes de l’observance. On a proposé de nouveaux paramètres pour mesurer l’impact biopharmaceutique de l’observance. Ensuite, on a comparé la performance, en termes de sensibilité et la fiabilité, des paramètres proposés et celles de paramètres déjà utilisés. En conclusion, on peut souligner qu’il n’y a pas de paramètre parfait étant donné que chacun a ses propres limites. Par exemple, pour les médicaments dont les effets sont directement liés aux leurs concentrations plasmatiques, le pourcentage des doses prises, qui est le paramètre le plus utilisé, offre la pire performance; par contre, le pourcentage des doses correctes nettes qui est un nouveau paramètre possède une bonne performance et des avantages prometteurs. / Compliance, which refers to the degree of the conformity to the prescription, is an essential factor for a successful treatment. The compliances of patients vary widely and the effectiveness of medication varies in parallel. Therefore, we need to have reliable and sensible parameters to measure it. In literature, there are many parameters to describe it, but their advantages, disadvantages and limitations regarding the assessment of the impact of compliance on drug have not yet been studied in depth. The evaluation of these parameters requires testing them in different situations. As available compliance data are not exhaustive, the use of the simulation, based on real or plausible cases, is very relevant. We succeeded to develop a model whose parameters are simple and understandable and which is convenient and flexible to simulate the different cases and even the extreme cases of compliance. We proposed new parameters for measuring the biopharmaceutical impact of compliance. Then, we compared the performance, in terms of sensibility and reliability, of these parameters and those already used to assess compliance and discussed their performances and limitations. In conclusion, we can emphasize that there is no ideal parameter since each one has its own limitations. For example, for drugs whose effects are directly related to their plasma concentrations, the percentage of taken doses, which is the most used parameter, has the worst performance, on the other hand, the percentage of the weighted correct doses, which is a new parameter, possesses a good performance and promising advantages.

Dans un contexte de recherche de solutions pour une agriculture à la fois productive et durable, les principes, théories et méthodes de l’écologie semblent offrir des pistes à explorer pour comprendre le fonctionnement biologique des agro-écosystèmes. Notre cas d’étude concernait les informations collectées par un réseau d’observatoires de la flore adventice à l’échelon national (‘Biovigilance Flore’) sur lequel nous avons recherché les règles sous jacentes à l’assemblage et la dynamique des communautés adventices au sein des parcelles de grandes cultures annuelles. Nous avons en particulier étudié les relations qui peuvent exister au sein des espèces d’une même communauté ainsi que celles affectant les relations des communautés à leur environnement. Pour tenir compte de son importance avérée dans la constitution des assemblages, nous avons conduit notre étude en tenant compte de l’abondance de la population de chaque espèce. Les principaux résultats issus des travaux réalisés au cours de cette thèse sont : Un assemblage non aléatoire des abondances et une structuration conduisent à une homogénéisation des abondances observées à l’échelle des parcelles. Selon la densité totale d’adventices sur une parcelle, on observe des structurations opposées selon qu’une espèce domine, ou non, dans la communauté. Même si la méthodologie employée pour réaliser les relevés nous empêche d’en avoir la preuve, nous suspectons que l’abondance des adventices répond à la compétition qui s’exerce dans certaines conditions directement entre espèces adventices.Le choix du modèle nul servant de base de comparaison dans les situations où il n’y a pas de témoin joue un rôle important dans la conduite des analyses des observations issues d’inventaires. L’échelle semi-quantitative pour rendre compte des variations d’abondance pose problème puisque aucun modèle nul n’a été développé pour ce format particulier. Un modèle adapté à notre situation, mais malgré tout générique, a été développé. Il apporte une amélioration sensible par rapport à l’existant pour étudier le degré de co occurrence (ainsi que la dispersion de traits) dans le cas de données semi-quantitatives. Ceci a des conséquences sur notre capacité à distinguer les facteurs ayant un rôle de filtre sur la flore potentielle qui s’exprime. La modélisation de la dynamique d’une espèce au sein d’une parcelle au fil des successions culturales nécessite de rendre compte de la dynamique du stock de graines dans le sol. Inconnu, ce stock de graines a été considéré comme une variable cachée, modélisable par l’utilisation d’un modèle de Markov caché. Cette approche s’est trouvée être remarquablement adaptée à la biologie des espèces annuelles. Nous avons ainsi pu appréhender l’effet des pratiques culturales sur la dynamique du stock de graines et de la flore levée. Cette étude a des retombées tant sur l’identification des traits d’histoire de vie que sur leur variabilité face à des stratégies de gestion qui seraient déployées pour assurer le contrôle d’une flore spécifique. Nous avons ainsi pu appliquer avec succès quelques principes théoriques et améliorer les méthodes d’analyse afin de tenir compte des spécificités des espèces adventices, de l’amplitude des fluctuations du milieu dans lequel elles évoluent et des spécificités de nos données. Il existe une marge de progrès sur la collecte des données à réaliser sur les réseaux d’observatoires si l’on veut maîtriser la connaissance des leviers les plus à même d’aider au contrôle de la flore adventice / To develop solutions for a productive and sustainable agriculture, principles, theories, andmethods of ecology may contribute to understand the biological processes governing the agroecosystem.The present case study was based on data collected by a network of observatories of weeds covering the whole of France (‘Biovigilance Flore’) and aimed at establishing forrules governing the assemblage and dynamics of weed communities in fields grown with annual crops. We particularly studied the possible relationships between species within acommunity, as well as the relationships between communities and their environment. Analyses were based on species abundances to take account of their effect on community assemblages. The main results of this PhD thesis are: Abundances of weed species are not randomly distributed within a field, and this distribution as well as the community pattern result into a homogenization of observed weed abundances at the field scale. The community pattern depends on the total weed abundance in the field and on whether the species is dominant in the community. We concluded that weed abundances responded to weed-weed competition in certain conditions though the sampling methodology was not adapted to prove this assumption. The choice of the null model for comparisons in situations without a control greatlyinfluences the procedure for analysing assemblages. This problem arises particularly at the semi-quantitative scale since no null model has yet been developed for this particular case. Hence, a generic null model was developed for our particular situation. It considerably improved the study of co-occurrences and trait dispersal in case of semi-quantitative datasets and thus our ability to identify factors and processes determining flora composition.Modelling the weed dynamics of a field over the crop succession needs to take into account the dynamics of the weed seed bank in the soil. As it was unknown, the seedbank wasconsidered as a hidden variable and modelled using a Hidden Markov Model (HMM). This approach was well adapted for predicting the life cycle of annual species. We thus identified effects of cultural practices on the dynamics of the seedbank and of the emerged flora. Thisstudy allowed us to identify life-history traits and weed management strategies adapted to aspecific weed flora.We successfully applied various ecological theories and improved methods to take into account the specificities of weed species, the variations in their environment as well as the specificities of our data-set. The quality and reliability of the data collected in the observatory network must be increased if we want to correctly identify management levers likely to contribute to sustainable weed management

Ce travail de thèse se propose d'analyser et d'évaluer les modèles de calcul des flux polluants (MCFP) des rejets urbains par temps de pluie. Pour cela, un banc d'essai a été établi qui repose sur l'utilisation d'une méthodologie basée sur la théorie bayésienne. Ce banc d'essai a été utilisé à des différentes échelles d'espace tout au long du cheminement de l'eau de ruissellement depuis les chaussées jusqu'à l'exutoire du réseau d'assainissement sur le site du bassin versant expérimental du Marais à Paris. Cette méthodologie du banc d'essai utilise une technique de simulation par chaîne de Markov (algorithme Metropolis) pour estimer la distribution de probabilité a posteriori des paramètres du modèle, ce qui permet : - Une évaluation quantitative des incertitudes liées à l'estimation des paramètres ainsi que leurs interactions ; - Une estimation quantitative du niveau d'incertitude dans les résultats d'application de ces modèles ; - Une estimation du pouvoir prédictif du modèle. A l'échelle locale, des modèles d'accumulation, d'entraînement des solides sur les surfaces urbaines, et des modèles d'érosion des solides dans les réseaux d'assainissement ont été testés et analysés. A l'échelle du bassin versant le couplage des modèles élémentaires tel qu'ils sont utilisés dans les logiciels actuels, a pu être évalué. La méthodologie de mise en œuvre a produit des résultats fiables en particulier des distributions de paramètres des modèles qui aident à l'analyse mathématique et à l'interprétation des modèles couramment utilisés. Elle a démontré l'existence de larges incertitudes liées à l'utilisation des MCFP à l'échelle de bassin versant. Ces modèles n'expliquent qu'une faible partie de la variation de la concentration des MES entre 2 événements pluvieux ou à l'intérieur d'un même événement sur le site étudié.

Cette thèse porte sur la méthode de Monte-Carlo ainsi que sur des applications de cette méthode à la physique statistique. La première partie concerne l'étude de la transition de phase liquide-solide à deux dimensions. La nature de cette transition est un problème de la physique statistique qui a longtemps été débattu, et en particulier pour le modèle fondamental des disques durs. Dans le but de traiter ce problème, nous avons développé l'algorithme de Monte-Carlo dit ''event-chain''. Notre analyse numérique montre que la transition se déroule en deux étapes: en augmentant la densité, le système passe de manière discontinue d'une phase liquide à une phase dite hexatique, puis de manière continue à une phase solide par une transition de type Kosterlitz-Thouless. Ces résultats posent une nouvelle base théorique aux expériences sur les solides bidimensionnels. La deuxième partie concerne les algorithmes d'échantillonage parfait utilisant la méthode ''Coupling from the past''. Ces algorithmes de Monte-Carlo permettent d'échantillonner des systèmes selon la distribution exacte désirée, ce qui supprime le problème de la connaissance du temps de thermalisation d'une chaîne de Markov. Cette méthode s'est avérée inefficace pour des systèmes physiques où elle serait utile: les verres de spins à basse température, ou les sphères dures à haute densité par exemple. Nous avons étudié différents algorithmes exacts pour ces systèmes. Les résultats obtenus montrent que cette limitation est due aux transitions vers le chaos des chaînes de Markov, ces transitions étant d'origine dynamique et non thermodynamique.