Cette thèse se situe à l'interface de la statistique et de la fouille de données. Elle est composée de trois parties indépendantes. Dans la première, nous cherchons à estimer l'ordre (le nombre d'États cachés) d'un modèle de Markov caché dont la distribution d'émission appartient à la famille exponentielle. Nous nous plaçons dans le cas où aucune borne supérieure sur cet ordre n'est connue a priori. Nous définissons deux estimateurs pénalisés pour cet ordre, l'un basé sur le maximum de vraisemblance et l'autre sur une statistique de mélange bayésien. Nous montrons la consistance forte de ces estimateurs. Dans la deuxième partie, nous extrayons des motifs séquentiels dont la fréquence est exceptionnellement élevée par rapport à un modèle de Markov. L'approche consiste à dénombrer dynamiquement toutes les positions possibles d'un motif au sein d'une séquence. Puis la fréquence observée est comparée à la fréquence attendue à l'aide d'un test binomial. Une procédure est utilisée pour tenir compte des tests multiples. Des expérimentations sont menées sur des bases synthétiques et des séquences de protéines. Enfin, dans la troisième partie, nous nous intéressons au calcul de l'estimateur à noyau de la densité. Les observations sont regroupées dans des structures hiérarchiques d'arbres binaires. Les calculs sont réalisés sur les nœuds, plutôt que sur les points, pour une plus grande efficacité. Nous effectuons le calcul sur un Échantillon de points de chaque nœud, au lieu de sa totalité, en utilisant des inégalités de concentration non-paramétriques pour contrôler l'erreur. Puis, nous proposons un nouveau parcours de l'arbre pour effectuer ces échantillonnages sur un nombre réduit de nœuds. Nous testons notre approche sur des jeux de données synthétiques. / This Ph.D thesis lies at the interface of statistics and data mining. It contains three independent parts. In the first one, we aim at estimating the order (the number of hidden states) of a Hidden Markov Model, whose emission distribution belongs to the exponential family. We suppose that no upper bound is known on this order. We define two penalised estimators for this order, one based on the maximum likelihood, an the other on a bayesian mixture statistic. We prove that both estimators are strongly consistent. In the second part, we extract sequential patterns of exceptional frequency given a Markov model. We first dynamically enumerate all the possible occurences of a pattern in a sequence. Then, the observed frequency is compared to the expected frequency using a binomial test. Multiple testing is taken into account. Experiments are led on synthetic databases and protein sequences. Finally, in the third chapter, we are interested in kernel density estimation. The observations are gathered in hierarchical structures called binary trees. Computations are done on nodes of trees, rather than on raw observations, for greater efficiency. We only take into account samples on each node, instead of all the observations, using a non-parametric concentration inequality to control the error. We also propose to only browse some parts of the tree. We test our approach on synthetic datasets.

Le potentiel de l’assimilation d’un type d’observation pour la prévision hydrologique a été démontré dans certaines études. Cependant, le potentiel de l’assimilation simultanée de plusieurs types d’observations a été peu validé, particulièrement pour les données comprenant une information sur la neige au sol. De plus, l’amplitude et la durée de l’impact de l’assimilation de données peuvent dépendre du type de données assimilé, ainsi que du contenu du vecteur d’état employé pour mettre à jour les variables ou les paramètres du modèle hydrologique. La présente thèse examine l’impact de l’assimilation de données multivariées en fonction du type de données assimilé et du contenu du vecteur d’état pour la prévision hydrologique à court terme (horizon de prévision jusqu’à 5 jours) et moyen terme (horizon de prévision entre 25 et 50 jours). Le filtre de Kalman d’ensemble est employé pour assimiler les observations de l’équivalent en eau de la neige à trois endroits sur le bassin versant de la rivière Nechako, ainsi que le débit à l’exutoire, dans le modèle hydrologique CEQUEAU. Les scénarios d’assimilation sont premièrement testés dans un cadre synthétique afin d’identifier les variables les plus susceptibles à l’assimilation des données pour la prévision hydrologique. La robustesse des scénarios d’assimilation de données est ensuite testée en introduisant un biais sur les précipitations solides. Finalement, les observations réelles sont assimilées pour vérifier l’impact réel des scénarios pour la prévision hydrologique. Les résultats montrent une amélioration variable des prévisions hydrologiques en fonction des scénarios selon plusieurs critères de performance mesurant l’exactitude, le biais et la représentativité de l’incertitude représentée par les prévisions d’ensemble. L’assimilation du débit pour la mise à jour des variables améliore principalement les prévisions à court terme, tandis que l’impact de la mise à jour de certains paramètres persiste à moyen terme. L’assimilation de l’équivalent en eau de la neige améliore les prévisions à court et moyen terme, principalement pendant la période de fonte de neige. Pour la plupart des scénarios, l’assimilation simultanée du débit et de l’équivalent en eau de la neige surpasse l’assimilation des données individuellement. Ces résultats sont cohérents entre les cadres synthétique et réel.

Thèse numérisée par la Division de la gestion de documents et des archives de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

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

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Un mot de données (resp. un arbre de données) est un mot (resp. arbre) fini, dont chaque position est étiquetée avec une lettre d'un alphabet fini et une donnée d'un domaine infini. Dans cette thèse, nous étudions des automates et des logiques sur des mots et des arbres de données ayant des propriétés décidables: nous nous concentrons sur le problème du test du vide dans le cas des automates, et sur le problème de la satisfaisabilité dans le cas des logiques. Sur les mots de données, nous présentons une extension décidable du modèle d'automate alternant avec registre étudié par Demri et Lazic. En outre, nous montrons la décidabilité du problème de satisfaisabilité pour la logique du temps linéaire sur les mots de données LTL(X,F,U) (étudié par Demri et Lazic) étendue avec une quantification sur des données. Nous montrons aussi que la borne inférieure de non-récursivité primitive montré par Demri et Lazic pour LTL(X,F) est déjà valable pour LTL(F). Sur les arbres de données, nous considérons trois modèles décidables d'automates avec des caractéristiques différentes. Nous commençons par introduire l'automate avec donnée ``downward'' (automates DD). Son exécution consiste en une transduction ré-étiquetant la partie finie de l'étiquetage de l'arbre, et une vérification des propriétés des données de chaque sous-arbre de l'arbre résultant de la transduction. Ce modèle est clos par les opérations booléennes, mais les tests autorisés sur l'ordre des noeuds ayant le même père sont très limités. Son problème du vide est dans 2ExpTime. Au contraire, les deux autres modèles d'automates que nous introduisons ont un problème du vide avec une complexité non récursive primitive, et sont clos par intersection et union, mais par par complémentation. Ils ont tous les deux un contrôle alternant ainsi qu'un registre pour stocker et comparer les données. La classe des automates ATRA(guess,spread) généralise le modèle d'automate top-down ATRA de Jurdzinski et Lazic. Nous introduisons des extensions décidables similaires à celles que nous avons étudiées dans le cas de mots de données. Cette classe d'automates généralise la notion de langage rationnel d'arbre, ---contrairement aux automates DD. Enfin, nous considérons un modèle d'automate bottom-up avec un contrôle alternant et un registre (appelé BUDA). Bien que les BUDA soient bottom-up, ils peuvent tester des propriétés sur les données en navigant dans l'arbre dans les deux directions: vers le haut et vers le bas. Au contraire de ATRA(guess,spread), ce modèle d'automate ne peut pas tester de propriétés sur la séquence des noeuds ayant le même père (comme, par exemple, l'ordre dans lequel apparaissent leurs étiquettes). Ces trois modèles d'automates ont des liens avec la logique XPath---une logique conçue pour les documents XML, qui peuvent être vus comme des arbres de données. En utilisant les automates que nous avons mentionnés ci-dessus, nous montrons que la satisfaisabilité de trois fragments naturels de XPath sont décidables. Ces fragments sont: downward XPath, où la navigation ne peut se faire que via les axes child et descendant- forward XPath, où la navigation permet également les axes next sibling ainsi que sa clôture transitive, et vertical XPath, dont la navigation est limitée aux axes child, descendant, parent et ancestor. Alors que downward XPath est ExpTime-complet, les fragments forward et vertical de XPath ont une borne inférieure de non-récursivité primitive. / A data word (resp. a data tree) is a &#64257-nite word (resp. tree) whose every position carries a letter from a &#64257-nite alphabet and a datum form an in&#64257-nite domain. In this thesis we investigate automata and logics for data words and data trees with decidable reasoning problems: we focus on the emptiness problem in the case of automata, and the satis&#64257-ability problem in the case of logics. On data words, we present a decidable extension of the model of alternating register automata studied by Demri and Lazi´c. Further, we show the decidability of the satis&#64257-ability problem for the linear-time temporal logic on data words LTL_\downarrow (X, F, U) (studied by Demri and Lazi´c) with quanti&#64257-cation over data values. We also prove that the lower bounds of non-primitive recursiveness shown by Demri and Lazi´c for LTL&#8595- (X, F) carry over to LTL&#8595- (F). On data trees, we consider three decidable automata models with di&#64256-erent characteristics. We &#64257-rst introduce the Downward Data automaton (DD automata). Its execution consists in a transduction of the &#64257-nite labeling of the tree, and a veri&#64257-cation of data properties for every subtree of the transduced tree. This model is closed under boolean operations, but the tests it can make on the order of the siblings is very limited. Its emptiness problem is 2ExpTime. On the contrary, the other two automata models we introduce have an emptiness problem with a non-primitive recursive complexity, and are closed under intersection and union, but not complementation. They are both alternating automata with one register to store and compare data values. The automata class ATRA(guess, spread) extends the top-down automata ATRA of Jurdzinski and Lazic. We exhibit similar decidable extensions as the one showed in the case of data words. This class can test for any tree regular language—in contrast to DD automata. Finally, we consider a bottom-up alternating tree automaton with one register (called BUDA). Although the BUDA class is one-way, it has features that allow to test data properties by navigating the tree in both directions: upward and downward. In opposition to ATRA(guess, spread), this automaton cannot test for properties on the the sequence of siblings (like, for example, the order in which labels appear). All these three models have connections with the logic XPath—a logic conceived for xml documents, which can be seen as data trees. Through the aforementioned automata we show that the satis&#64257-ability of three natural fragments of XPath are decidable. These fragments are: downward XPath, where navigation can only be done by child and descendant axes- forward XPath, where navigation also contains the next sibling axis and its transitive closure- and vertical XPath, whose navigation consists in the child, descendant, parent and ancestor axes. Whereas downward XPath is ExpTime-complete, forward and vertical XPath have non-primitive recursive lower bounds.