En développant des outils pour étudier les chaînes de Markov réversibles ainsi qu’une classification des arbres par leur constante de branchement, on pourra traiter du problème du retour à l’origine d’une marche aléatoire sur un arbre. Ces mêmes outils nous permettront d’étudier la percolation sur les arbres. En particulier, il sera possible de relier explicitement la constante de branchement d’un arbre à la valeur critique pour la marche aléatoire biaisée et à la valeur critique de percolation. Par la suite, on détaille comment en arriver à des bornes intéressantes pour deux valeurs critiques du processus de contact sur l’arbre homogène, un résultat de Pemantle. On généralise aussi un résultat de Schinazi qui nous permet de trouver une borne inférieure pour la valeur critique de survie du processus de contact sur le recouvrement universel d’un graphe fini.

Cette thèse porte sur les problèmes de prise de décisions séquentielles sous incertitudes dans un système mono ou multi-agents. Les processus décisionnels de Markov offrent un modèle mathématique permettant à la fois de formaliser et de résoudre de tels problèmes. Il existe de multiple travaux proposant des techniques efficaces pour la résolution des processus décisionnels de Markov. Néanmoins, trois facteurs, dits malédictions, limitent grandement le passage à l'échelle de ces techniques. Le premier facteur, la malédiction de la dimension, est le plus connu. Il lie la complexité des algorithmes au nombre d'états du système dont la croissance est exponentielle en fonction des attributs des états. Le second facteur, la malédiction de l'historique, a été identifié plus récemment. Il lie la complexité des algorithmes à la dimension exponentielle de l'espace des historiques à prendre en compte afin de résoudre le problème. Enfin, le dernier facteur, là malédiction de la distributivité, est identifié dans cette thèse. Il lie la complexité des algorithmes à la contrainte du contrôle distribué d'un système, résultant sur une complexité doublement exponentielle. À travers nos contributions, nous proposons une réponse à chacune des trois malédictions. Nous atténuons à la fois la malédiction de la dimension et la malédiction de l'historique en exploitant les dépendances causales soit entre états soit entre historiques. Suivant cette idée, nous proposons une famille d'algorithmes exacts et approximatifs, nommée programmation dynamique topologique, visant à résoudre les processus décisionnels de Markov complètement ou partiellement observables. Ces algorithmes permettent de réduire considérablement le nombre de mises à jour d'un état ou d'un historique. Ainsi, lorsque les problèmes sont munis d'une structure topologique, la programmation dynamique topologique offre une solution efficace. Pour pallier aux effets de la malédiction de la distributivité, nous avons proposé d'étendre la planification centralisée au cadre du contrôle distribué. Nous proposons une analyse formelle des problèmes de contrôle distribué des processus décisionnels de Markov sous le regard de la planification centralisée. De cette analyse, de nombreux algorithmes de planification centralisée ont vu le jour. Parmi eux, figure point-based incremental pruning (PBIP), l'algorithme approximatif pour la résolution des processus de Markov décentralisés, le plus efficace à ce jour.

La prise de décision dans un environnement partiellement observable est un sujet d'actualité en intelligence artificielle. Une façon d'aborder ce type de problème est d'utiliser un modèle mathématique. Notamment, les POMDPs (Partially Observable Markov Decision Process) ont fait l'objet de plusieurs recherches au cours des dernières années. Par contre, résoudre un POMDP est un problème très complexe et pour cette raison, le modèle n'a pas été utilisé abondamment. Notre objectif était de continuer les progrès ayant été réalisé lors des dernières années, avec l'espoir que nos travaux de recherches seront un pas de plus vers l'application des POMDPs dans des applications d'envergures. Dans un premier temps, nous avons développé un nouvel algorithme hors-ligne qui, sur des problèmes tests, est plus performant que les meilleurs algorithmes existants. La principale innovation vient du fait qu'il s'agit d'un algorithme stochastique alors que les algorithmes traditionnels sont déterministes. Dans un deuxième temps, nous pouvons également appliquer cet algorithme dans des environnements en-lignes. Lorsque ceux-ci revêtent une certaine particularité, notre algorithme est beaucoup plus performant que la compétition. Finalement, nous avons appliqué une version simplifiée de notre algorithme dans le cadre du projet Combat Identification du RDDC-Valcartier. / Decision making under uncertainty is a popular topic in the field of artificial intelligence. One popular way to attack such problems is by using a sound mathematical model. Notably, Partially Observable Markov Processes (POMDPs) have been the subject of extended researches over the last ten years or so. However, solving a POMDP is a very time-consuming task and for this reason, the model has not been used extensively. Our objective was to continue the tremendous progress that has been made over the last couple of years, with the hope that our work will be a step toward applying POMDPs in large-scale problems. To do so, we combined different ideas in order to produce a new algorithm called SSVI (Stochastic Search Value Iteration). Three major accomplishments were achieved throughout this research work. Firstly, we developed a new offline POMDP algorithm which, on benchmark problems, proved to be more efficient than state of the arts algorithm. The originality of our method comes from the fact that it is a stochastic algorithm, in comparison with the usual determinist algorithms. Secondly, the algorithm we developed can also be applied in a particular type of online environments, in which this algorithm outperforms by a significant margin the competition. Finally, we also applied a basic version of our algorithm in a complex military simulation in the context of the Combat Identification project from DRDC-Valcartier.

L’apprentissage (machine) de modèle et l’estimation d’état sont cruciaux pour interpréter les phénomènes sous-jacents à de nombreuses applications du monde réel. Toutefois, il est souvent difficile d’apprendre le modèle d’un système et de capturer les états latents, efficacement et avec précision, en raison du fait que la connaissance du monde est généralement incertaine. Au cours des dernières années, les approches d’estimation et de modélisation bayésiennes ont été extensivement étudiées afin que l’incertain soit réduit élégamment et de manière flexible. Dans la pratique cependant, différentes limitations au niveau de la modélisation et de l’estimation bayésiennes peuvent détériorer le pouvoir d’interprétation bayésienne. Ainsi, la performance de l’estimation est souvent limitée lorsque le modèle de système manque de souplesse ou/et est partiellement inconnu. De même, la performance de la modélisation est souvent restreinte lorsque l’estimateur Bayésien est inefficace. Inspiré par ces faits, nous proposons d’étudier dans cette thèse, les connections possibles entre modélisation bayésienne (via le processus gaussien) et l’estimation bayésienne (via le filtre de Kalman et les méthodes de Monte Carlo) et comment on pourrait améliorer l’une en utilisant l’autre. À cet effet, nous avons d’abord vu de plus près comment utiliser les processus gaussiens pour l’estimation bayésienne. Dans ce contexte, nous avons utilisé le processus gaussien comme un prior non-paramétrique des modèles et nous avons montré comment cela permettait d’améliorer l’efficacité et la précision de l’estimation bayésienne. Ensuite, nous nous somme intéressé au fait de savoir comment utiliser l’estimation bayésienne pour le processus gaussien. Dans ce cadre, nous avons utilisé différentes estimations bayésiennes comme le filtre de Kalman et les filtres particulaires en vue d’améliorer l’inférence au niveau du processus gaussien. Ceci nous a aussi permis de capturer différentes propriétés au niveau des données d’entrée. Finalement, on s’est intéressé aux interactions dynamiques entre estimation bayésienne et processus gaussien. On s’est en particulier penché sur comment l’estimation bayésienne et le processus gaussien peuvent ”travailler” de manière interactive et complémentaire de façon à améliorer à la fois le modèle et l’estimation. L’efficacité de nos approches, qui contribuent à la fois au processus gaussien et à l’estimation bayésienne, est montrée au travers d’une analyse mathématique rigoureuse et validée au moyen de différentes expérimentations reflétant des applications réelles. / Model learning and state estimation are crucial to interpret the underlying phenomena in many real-world applications. However, it is often challenging to learn the system model and capture the latent states accurately and efficiently due to the fact that the knowledge of the world is highly uncertain. During the past years, Bayesian modeling and estimation approaches have been significantly investigated so that the uncertainty can be elegantly reduced in a flexible probabilistic manner. In practice, however, several drawbacks in both Bayesian modeling and estimation approaches deteriorate the power of Bayesian interpretation. On one hand, the estimation performance is often limited when the system model lacks in flexibility and/or is partially unknown. On the other hand, the modeling performance is often restricted when a Bayesian estimator is not efficient and/or accurate. Inspired by these facts, we propose Interactions Between Gaussian Processes and Bayesian Estimation where we investigate the novel connections between Bayesian model (Gaussian processes) and Bayesian estimator (Kalman filter and Monte Carlo methods) in different directions to address a number of potential difficulties in modeling and estimation tasks. Concretely, we first pay our attention to Gaussian Processes for Bayesian Estimation where a Gaussian process (GP) is used as an expressive nonparametric prior for system models to improve the accuracy and efficiency of Bayesian estimation. Then, we work on Bayesian Estimation for Gaussian Processes where a number of Bayesian estimation approaches, especially Kalman filter and particle filters, are used to speed up the inference efficiency of GP and also capture the distinct input-dependent data properties. Finally, we investigate Dynamical Interaction Between Gaussian Processes and Bayesian Estimation where GP modeling and Bayesian estimation work in a dynamically interactive manner so that GP learner and Bayesian estimator are positively complementary to improve the performance of both modeling and estimation. Through a number of mathematical analysis and experimental demonstrations, we show the effectiveness of our approaches which contribute to both GP and Bayesian estimation.

Cette thèse s’inscrit dans le vaste domaine des équations aux dérivées partielles et des systèmes dynamiques, et s’articule autour de deux sujets distincts. Le premier est relié à l’étude des équations de coagulation-fragmentation discrètes avec diffusion. En utilisant des lemmes de dualité, on établit de nouvelles estimations Lp pour des moments polynomiaux associés aux solutions, sous une hypothèse de convergence des coefficients de diffusion. Ces estimations sur les moments permettent ensuite d’obtenir de nouveaux résultats de régularité, et de démontrer qu’une fragmentation suffisamment forte peut empêcher la gelation dans le modèle incluant la diffusion. Le second sujet est celui des preuves assistées par ordinateur dans le domaine des systèmes dynamiques. On améliore et on applique une méthode basée sur le théorème du point fixe de Banach, permettant de valider a posteriori des solutions numériques. Plus précisément, on élargit le cadre d’application de cette méthode pour inclure des opérateurs avec un terme dominant linéaire tridiagonal, on perfectionne une technique permettant de calculer et de valider des variétés invariantes, et on introduit une nouvelle technique qui améliore de manière significative l’utilisation de l’interpolation polynomiale dans le cadre de ces méthodes de preuves assistées par ordinateur. Ensuite, on applique ces techniques pour démontrer l’existence d’ondes progressives pour l’équation du pont suspendu, et pour étudier les états stationnaires non homogènes d’un système de diffusion croisée. / This thesis falls within the broad framework of partial differential equations and dynamical systems, and focuses more specifically on two independent topics. The first one is the study of the discrete coagulation-fragmentation equations with diffusion. Using duality lemma we establish new Lp estimates for polynomial moments of the solutions, under an assumption of convergence of the diffusion coefficients. These moment estimates are then used to obtain new results of smoothness and to prove that strong enough fragmentation can prevent gelation even in the diffusive case. The second topic is the one of computer-assisted proofs for dynamical systems. We improve and apply a method enabling to a posteriori validate numerical solutions, which is based on Banach’s fixed point theorem. More precisely, we extend the range of applicability of the method to include operators with a dominant linear tridiagonal part, we improve an existing technique allowing to compute and validate invariant manifolds, and we introduce an new technique that significantly improves the usage of polynomial interpolation for a posteriori validation methods. Then, we apply those techniques to prove the existence of traveling waves for the suspended bridge equation, and to study inhomogeneous steady states of a cross-diffusion system.

Ce mémoire présente les résultats d’estimation de ressources minérales en éléments des terres rares (ETR) réalisés à l’aide de simulations géostatistiques gaussiennes séquentielles (SGS) en facteurs spatialement décorrélés par la méthode MAF (Minimum/Maximum Autocorrelation Factors). Cette étude s’inscrit dans le cadre du projet de recherche « Caractérisation des gîtes de terres rares d’intrusions alcalines : géologie, métallogénie et géométallurgie du complexe syénitique de Kipawa » (FRQNT, 2017, p. 59). Les SGS se proposent comme une méthode alternative à la technique reconnue du krigeage ordinaire ayant été utilisée pour l’estimation des ressources minérales d’ETR du gisement de Kipawa, site à l’étude. Ce mémoire compare les résultats d’estimation des ressources minérales d’ETR des SGS à ceux du krigeage ordinaire. À cette fin, le site à l’étude est d’abord présenté en compagnie de la base de données conjointement utilisées par les deux méthodes. Ensuite, une revue de littérature aborde les notions et concepts nécessaires à la réalisation des SGS de cette étude. Une fois ces connaissances acquises, la méthode de recherche est développée. Son aboutissement permet de présenter les résultats et d’en discuter. Globalement, les résultats démontrent que les SGS en facteurs offrent l’avantage de procéder à l’estimation de ressources minérales d’ETR de façon multivariée, de limiter le lissage des résultats tout en fournissant une évaluation de leur incertitude. Les SGS proposent une distribution normale des ressources minérales en ETR totaux allant d’un minimum de 91 035 t à un maximum de 103 118 t. D’autre part, le krigeage ordinaire en estime, sans teneur de coupure, une valeur unique de 113 717 t. En conclusion, le tonnage évalué des ressources minérales en ETR du gisement Kipawa est moindre par la méthode des SGS que par le krigeage ordinaire. MOTS CLÉS : Simulations, géostatistique, simulations gaussiennes séquentielles (SGS), facteurs d’autocorrélation minimum/maximum (MAF), éléments des terres rares (ETR), ressources minérales. / This thesis presents the results of rare earth elements (REE) mineral resources estimate using Sequential Gaussian Simulations (SGS) of spatially decorrelated factors calculated from the Minimum/Maximum Autocorrelation Factors (MAF) method. This study is part of the research project "Characterization of REE deposits of alkaline intrusions: geology, metallogeny and geometallurgy of the Kipawa syenite complex" (FRQNT, 2017, p. 59). SGS are proposed as an alternative method to the acknowledge ordinary kriging technic which was used for the REE mineral resources estimation of the Kipawa deposit, site under study. This report compares the results of the SGS mineral resources estimate to those of ordinary kriging. To this end, the study site is first presented along with the database jointly used by the two methods. Then, a literature review discusses the notions and concepts required to carry out the SGS of this study. Once this knowledge acquired, the research method is developed. Afterward, the results are presented and discussed. Overall, results demonstrate that SGS of MAF factors offer the advantage of estimating REE mineral resources in a multivariate manner, limiting the smoothing of the results while providing an assessment of their uncertainty. The SGS propose a normal distribution of the total REE ranging from a minimum of 91 035 t to a maximum of 103 118 t. On the other hand, the ordinary kriging estimates a single value of 113 717 t in total REE with no cut-off grade. In conclusion, the SGS method evaluates a lesser tonnage of REE mineral ressources at the Kipawa deposit than the ordinary kriging technic. KEYWORDS: Simulations, Geostatistic, Sequential Gaussian Simulations (SGS), Min/Max Autocorrelation Factors (MAF), Rare Earth Elements (REE), Mineral resources.

La modélisation de phénomènes biologiques qui impliquent un très grand nombre d'unités pose toujours un défi. De nombreux modèles présentent une vision globale de la dynamique moyenne du phénomène sous la forme d'un système d'équations différentielles ordinaires. C'est le cas notamment du modèle de Wilson-Cowan, qui décrit l'activité qui se propage dans un réseau de neurones biologiques. Une limite importante de ce modèle est qu'il néglige d'éventuelles corrélations entre les états de différents neurones. L'objectif premier de ce mémoire est ainsi de le généraliser afin de décrire de telles corrélations. On veut aussi mieux en comprendre les fondements mathématiques et les liens qu'il a avec des modèles semblables utilisés en épidémiologie et en écologie. Pour s'attaquer à ce problème, on construit une chaîne de Markov en temps continu qui décrit l'évolution des états des nœuds d'un graphe, et qui peut ainsi modéliser un phénomène biologique d'un point de vue microscopique. Étant donné le très grand nombre de nœuds que comporte le graphe, ce modèle microscopique est difficile à analyser. À partir du processus stochastique, on obtient alors par un moyennage un système d'équations différentielles ordinaires afin de décrire la dynamique sur le graphe d'un point de vue macroscopique. Deux applications de cette méthode sont alors présentées : l'une en épidémiologie et l'autre en neurosciences. On se concentre particulièrement sur l'application en neurosciences, qui permet de décrire la dynamique d'un réseau de neurones biologiques et de généraliser le modèle de Wilson-Cowan. En effet, on arrive à proposer deux nouveaux systèmes qui sont des extensions de ce modèle, puisqu'elles permettent de considérer des corrélations entre les états de différents neurones. On présente finalement un exemple dans lequel le comportement dynamique de l'une de ces extensions est plus près du comportement du processus stochastique que celui du modèle de Wilson-Cowan. / Modeling biological phenomena that involve a very large number of individual units is always a challenge. In this context, many models consist in a system of ordinary differential equations that gives an overview of the mean dynamics of a phenomenon. Among these is the Wilson-Cowan model, which describes the activity of a biological neural network. An important weakness of this model is that it neglects all possible correlations between the states of different neurons. The main goal of this thesis is to generalize Wilson-Cowan's model to describe such correlations. We also seek to get a better understanding of its mathematical foundations, as well as its links with other models used in epidemiology and ecology. To tackle this problem, we construct a continuous-time Markov chain to describe the evolution of the states of the nodes of a large graph. Such a process can then model a biological phenomenon from a microscopic point of view. Since the size of the graph is very large, this microscopic model is hard to analyze. Hence, from the stochastic process, we use an averaging method to obtain a system of ordinary differential equations which describes the dynamics on the graph from a macroscopic point of view. We show two applications of this method : one in epidemiology and the other in neuroscience. We focus on the application in neuroscience, which leads to a description of the dynamics a biological neural network and generalizes Wilson-Cowan's model. Indeed, we introduce two new systems which are extensions of this model since they can describe correlations between the states of different neurons. Finally, we present an example where the behavior of the stochastic process is closer to the dynamical behavior of one of the extensions than that of Wilson-Cowan's model.

Tableau d'honneur de la Faculté des études supérieures et postdoctorales, 2011-2012 / Dans ce mémoire, nous comparons deux modèles de processus probabilistes évoluant dans un environnement continu. Les processus de Markov étiquetés sont des systèmes de transitions pour lesquels l’ensemble des états est non-dénombrable, mais qui évoluent de manière discrète dans le temps. Les mesures de probabilité définies sur l’ensemble des états peuvent avoir un support infini. Les processus hybrides sont une combinaison d’un processus à espace d’états continu qui évolue de manière continue dans le temps et une composante discrète qui intervient pour contrôler l’évolution. Les extensions probabilistes des processus hybrides présentes dans la littérature restreignent le comportement probabiliste à la composante discrète. Nous utilisons deux exemples de systèmes, un avion et un bateau, pour faire ressortir les divergences entre les deux modèles ainsi que leurs limitations, et nous définissons une généralisation qui peut modéliser fidèlement ces exemples. Nous avons également pu montrer, dans un article publié dans un atelier international, comment utiliser, dans le contexte probabiliste, la «substitution d’horloge» et l’«approximation par portrait» qui sont des techniques proposées par Henzinger et al. pour les processus non probabilistes. Ces techniques permettent, sous certaines conditions, de définir un processus probabiliste rectangulaire à partir d’un qui est non rectangulaire, rendant ainsi possible la vérification formelle de toute classe de système hybride probabiliste. / We compare two models of processes involving uncountable space. Labelled Markov processes are probabilistic transition systems that can have uncountably many states, but still make discrete time steps. The probability measures on the state space may have uncountable support and a tool has been developed for verification of such systems. Hybrid processes are a combination of a continuous space process that evolves continuously with time and of a discrete component, such as a controller. Existing extensions of Hybrid processes with probability restrict the probabilistic behavior to the discrete component. We have also shown, in a paper, how to compute for probabilistic hybrid systems, the clock approximation and linear phase-portrait approximation that have been proposed for non probabilistic processes by Henzinger et al. The techniques permit, under some conditions, to define a rectangular probabilistic process from a non rectangular one, hence allowing the model-checking of any class of systems. To highlight the differences between Labelled Markov processes and probabilistic hybrid systems, we use two examples, the ones of a boat and an aircraft, and

La publicité constitue l'un des nerfs de la guerre des sociétés de consommation. Or, l'impact d'une publicité est souvent tributaire de son degré de créativité, qualité qui contribue notamment à retenir l'attention, à convaincre ou qui incite à agir (Belch et al. 2008). À ce jour, les études qui ont examiné le processus créatif en contexte publicitaire se sont essentiellement concentrées sur l'analyse a posteriori des productions issues de ce processus, en questionnant peu la"mécanique" cognitive à leur origine ou en essayant de l'inférer (Griffm 2008). Or, selon Mumford et al. (2006), pour réellement comprendre la pensée créative, il est nécessaire d'identifier et de caractériser les connaissances qui interviennent lors de la génération d'idées et de la formulation de solutions, ainsi que les opérations cognitives (processus mentaux) appliquées à ces mêmes connaissances. Ce faisant, il devient dès lors possible de mettre au jour les stratégies cognitives employées à chacune des étapes de l'effort créatif. C'est dans cette optique qu'a été menée une collecte de données qualitatives en agence, à l'occasion des séances de conception publicitaire d'une équipe créative.La principale méthode de recherche retenue a été l'analyse de protocoles verbaux concomitants à la résolution de problèmes. L'analyse des données recueillies a été réalisée à la lumière de trois types de connaissances (les connaissances schématiques, les connaissances associatives, les connaissances liées à des expériences antérieures) et de quatre types d'opérations cognitives (le réemploi, l'analogie, la combinaison, l'abstraction) reconnus pour être impliqués dans la résolution créative de problèmes (Hunter et al. 2006; Mumford et al. 2006; Welling 2007). Cette analyse a notamment permis d'identifier et de documenter diverses stratégies cognitives, parfois différentes chez les novices et les experts. Ces stratégies ont ensuite été intégrées dans un modèle afin de rendre compte de leur mises en oeuvre et ainsi de contribuer à une meilleure compréhension des processus stratégiques de la pensée en contexte créatif publicitaire.

Thèse diffusée initialement dans le cadre d'un projet pilote des Presses de l'Université de Montréal/Centre d'édition numérique UdeM (1997-2008) avec l'autorisation de l'auteur.