Un système de dialogue conversationnel doit aider les utilisateurs humains à atteindre leurs objectifs à travers des dialogues naturels et efficients. C'est une tache toutefois difficile car les langages naturels sont ambiguës et incertains, de plus le système de reconnaissance vocale (ASR) est bruité. À cela s'ajoute le fait que l'utilisateur humain peut changer son intention lors de l'interaction avec la machine. Dans ce contexte, l'application des processus décisionnels de Markov partiellement observables (POMDPs) au système de dialogue conversationnel nous a permis d'avoir un cadre formel pour représenter explicitement les incertitudes, et automatiser la politique d'optimisation. L'estimation des composantes du modelé d'un POMDP-dialogue constitue donc un défi important, car une telle estimation a un impact direct sur la politique d'optimisation du POMDP-dialogue. Cette thèse propose des méthodes d'apprentissage des composantes d'un POMDPdialogue basées sur des dialogues bruités et sans annotation. Pour cela, nous présentons des méthodes pour apprendre les intentions possibles des utilisateurs à partir des dialogues, en vue de les utiliser comme états du POMDP-dialogue, et l'apprendre un modèle du maximum de vraisemblance à partir des données, pour transition du POMDP. Car c'est crucial de réduire la taille d'état d'observation, nous proposons également deux modèles d'observation: le modelé mot-clé et le modelé intention. Dans les deux modèles, le nombre d'observations est réduit significativement tandis que le rendement reste élevé, particulièrement dans le modele d'observation intention. En plus de ces composantes du modèle, les POMDPs exigent également une fonction de récompense. Donc, nous proposons de nouveaux algorithmes pour l'apprentissage du modele de récompenses, un apprentissage qui est basé sur le renforcement inverse (IRL). En particulier, nous proposons POMDP-IRL-BT qui fonctionne sur les états de croyance disponibles dans les dialogues du corpus. L'algorithme apprend le modele de récompense par l'estimation du modele de transition de croyance, semblable aux modèles de transition des états dans un MDP (processus décisionnel de Markov). Finalement, nous appliquons les méthodes proposées à un domaine de la santé en vue d'apprendre un POMDP-dialogue et ce essentiellement à partir de dialogues réels, bruités, et sans annotations. / Spoken dialogue systems should realize the user intentions and maintain a natural and efficient dialogue with users. This is however a difficult task as spoken language is naturally ambiguous and uncertain, and further the automatic speech recognition (ASR) output is noisy. In addition, the human user may change his intention during the interaction with the machine. To tackle this difficult task, the partially observable Markov decision process (POMDP) framework has been applied in dialogue systems as a formal framework to represent uncertainty explicitly while supporting automated policy solving. In this context, estimating the dialogue POMDP model components is a signifficant challenge as they have a direct impact on the optimized dialogue POMDP policy. This thesis proposes methods for learning dialogue POMDP model components using noisy and unannotated dialogues. Speciffically, we introduce techniques to learn the set of possible user intentions from dialogues, use them as the dialogue POMDP states, and learn a maximum likelihood POMDP transition model from data. Since it is crucial to reduce the observation state size, we then propose two observation models: the keyword model and the intention model. Using these two models, the number of observations is reduced signifficantly while the POMDP performance remains high particularly in the intention POMDP. In addition to these model components, POMDPs also require a reward function. So, we propose new algorithms for learning the POMDP reward model from dialogues based on inverse reinforcement learning (IRL). In particular, we propose the POMDP-IRL-BT algorithm (BT for belief transition) that works on the belief states available in the dialogues. This algorithm learns the reward model by estimating a belief transition model, similar to MDP (Markov decision process) transition models. Ultimately, we apply the proposed methods on a healthcare domain and learn a dialogue POMDP essentially from real unannotated and noisy dialogues.

Les mathématiques offrent un cadre convenable pour raisonner rigoureusement sur les systèmes et phénomènes réels. Par exemple, en génie logiciel, les méthodes formelles sont parmi les outils les plus efficaces pour détecter les anomalies dans les logiciels. Plusieurs systèmes réels sont stochastiques par nature dans le sens où leur comportement est sujet à un aspect d'incertitude. La représentation de ce genre de systèmes requiert des modèles stochastiques comme les processus de Markov étiquetés (LMP), les processus de Markov décisionnels (MDP), etc. Cette thèse porte sur la quantification de la différence entre les systèmes stochastiques. Les contributions majeures sont : 1. une nouvelle approche pour quantifier la divergence entre les systèmes stochastiques basée sur l'apprentissage par renforcement, 2. une nouvelle famille de notions d'équivalence qui se situe entre l'équivalence par trace et la bisimulation, et 3. un cadre plus flexible pour la définition des notions d'équivalence qui se base sur les tests. Le résultat principal de la thèse est que l'apprentissage par renforcement, qui est une branche de l'intelligence artificielle particulièrement efficace en présence d'incertitude, peut être utilisé pour quantifier efficacement cette divergence. L'idée clé est de définir un MDP à partir des systèmes à comparer de telle sorte que la valeur optimale de cet MDP corresponde à la divergence entre eux. La caractéristique la plus attrayante de l'approche proposée est qu'elle est complètement indépendante des structures internes des systèmes à comparer. Pour cette raison, l'approche peut être appliquée à différents types de systèmes stochastiques. La deuxième contribution est une nouvelle famille de notions d'équivalence, que nous appelons moment, qui est plus forte que l'équivalence par trace mais plus faible que la bisimulation. Cette famille se définit naturellement à travers la coïncidence de moments de variable aléatoires (d'où son nom) et possède une caractérisation simple en terme de tests. Nous montrons que moment fait partie d'un cadre plus grand, appelé test-observation-equivalence (TOE), qui constitue la troisième contribution de cette thèse. Il s'agit d'un cadre plus flexible pour la définition des notions d'équivalence basé sur les tests. / Modelling real-life systems and phenomena using mathematical based formalisms is ubiquitous in science and engineering. The reason is that mathematics offer a suitable framework to carry out formal and rigorous analysis of these systems. For instance, in software engineering, formal methods are among the most efficient tools to identify flaws in software. The behavior of many real-life systems is inherently stochastic which requires stochastic models such as labelled Markov processes (LMPs), Markov decision processes (MDPs), predictive state representations (PSRs), etc. This thesis is about quantifying the difference between stochastic systems. The main contributions are: 1. a new approach to quantify the divergence between pairs of stochastic systems based on reinforcement learning, 2. a new family of equivalence notions which lies between trace equivalence and bisimulation, and 3. a refined testing framework to define equivalence notions. The important point of the thesis is that reinforcement learning (RL), a branch of artificial intelligence particularly efficient in presence of uncertainty, can be used to quantify efficiently the divergence between stochastic systems. The key idea is to define an MDP out of the systems to be compared and then to interpret the optimal value of the MDP as the divergence between them. The most appealing feature of the proposed approach is that it does not rely on the knowledge of the internal structure of the systems. Only a possibility of interacting with them is required. Because of this, the approach can be extended to different types of stochastic systems. The second contribution is a new family of equivalence notions, moment, that constitute a good compromise between trace equivalence (too weak) and bisimulation (too strong). This family has a natural definition using coincidence of moments of random variables but more importantly, it has a simple testing characterization. moment turns out to be part of a bigger framework called test-observation-equivalence (TOE), which we propose as a third contribution of this thesis. It is a refined testing framework to define equivalence notions with more flexibility.

De manière générale, les problèmes séquentiels de décisions multiagents sont très difficiles à résoudre surtout lorsque les agents n'observent pas parfaitement ni complètement l'état de leur environnement. Les modèles actuels pour représenter ces problèmes restent à ce jour très généraux et difficilement applicables dans les multiples applications possibles. Nous proposons dans cette thèse plusieurs approches de réduction de la complexité computationnelle et en pire cas de ces modèles. Une première approche se base sur l'utilisation de contraintes sur l'espace des actions possibles que les différents agents du système peuvent entreprendre. Cette utilisation de connaissances a priori dans la modélisation au travers de modèles déjà connus, mais non appliqués à la prise de décision séquentielle permet une réduction significative d'un des facteurs de la complexité algorithmique. La seconde approche consiste à restreindre les possibilités d'observations de l'agent à un ensemble similaire à l'espace d'états utilisé pour représenter son environnement. De cette manière, nous montrons que les agents peuvent converger rapidement en probabilité vers des croyances communes sans nécessairement avoir à communiquer. Dans ce contexte, nous avons également développé un algorithme permettant alors aux agents de se coordonner au moment de l'exécution lorsqu'il n'existe pas de communication explicite. Enfin, nous avons entrepris la mise en application de telles réductions à deux problèmes. Un premier problème de patrouille multiagent est considéré et modélisé, et un second problème lié à l'apprentissage de POMDPS continus dans des cas précis de transition et d'observabilité est également abordé. Les résultats obtenus montrent que dans certains cas de problèmes de coordination, la communication ? lorsqu'elle est disponible ? est non négligeable, et que dans le cas de l'apprentissage de POMDPs, considérer le quasi-déterminisme du modèle permet l'apprentissage de converger.

Dans cette thèse, on s'intéresse à la notion de temps fort de stationnarité et à celle, étroitement liée, de dual de stationnarité forte. Ces outils permettent d'étu- dier la convergence de processus ergodiques, en déterminant un instant aléatoire où l'équilibre est atteint. Les espaces d'état des processus considérés ici sont des graphes continus ou discrets. Dans la première partie, on considère le cas discret, et on dégage une condition nécessaire et suffisante à l'existence, pour n'importe quelle loi initiale, d'un temps fort de stationnarité fini. Pour cela, on construit explicitement un dual de station- narité forte, à valeurs dans l'ensemble des parties connexes du graphe, qui évolue à chaque étape en ajoutant ou en enlevant des points de sa frontière. Lorsque cette opération sépare l'ensemble dual en plusieurs parties, afin de ne pas le déconnecter, une de ces parties est choisie au hasard, avec une probabilité proportionnelle à son poids par la mesure invariante. On s'intéresse également au comportement général d'un processus dual, et on donne quelques exemples différents de celui construit précédemment. Dans la deuxième partie, on traite le cas continu, et le processus étudié est alors une diffusion. On caractérise notamment sa mesure invariante, et on explicite un générateur infinitésimal qui devrait être celui d'un processus dual. Néanmoins, ce cas s'avère plus compliqué que le cas discret. Le processus dual n'est donc construit que pour un mouvement brownien sur un graphe particulier, comme l'unique so- lution d'un problème de martingale. Des pistes sont présentées pour traiter des diffusions sur des graphes plus généraux, notamment en utilisant la convergence d'une suite de processus de saut tels que ceux présentés dans la première partie. / In this thesis, we are interested in the notion of strong stationary time, and in that, strongly connected, of strong stationary dual. These tools allow to study the convergence of ergodic processes, by determining a random time when the equilibrium is reached. The state space of the considered processes are discrete or continuous graphs. In the first part, we consider the discrete case, and we explicit a necessary and sufficient condition to the existence, for any initial distribution, of a finite strong stationary time. To do so, we construct explicitly a strong stationary dual, with values in the set of connected subsets of the graph, which evolves at each step by adding or removing some points at its border. Whenever this operation separates the dual set in several parts, in order not to disconnect it, one of these parts is chosen randomly, with a probability proportionnal to its weight relative to the invariant distribution. We also study the general behaviour of any dual process,2 and we give some other examples. In the second part, we deal with the continuous case, and the studied process is then a diffuion. We caracterize its invariant distribution, and we explicit an infinitesimal generator, which is expected to be that of a dual process. Nevertheless, this case turns out to be a little more involved that the discrete one. The dual process is thus constructed only for a brownian motion on a particular graph, as the unique solution of a martingale problem. Some leads are given to solve the case of diffusions on more general graphs, especially by using the convergence of a sequence of jump processes such as those presented in the first part.

Le sujet principal de cette thèse de doctorat est l'étude de diverses quantités reliées aux processus de fragmentation. Ces processus sont destinés à modéliser un objet de masse unité se fragmentant au cours du temps.<br />Ce travail comporte quatre chapitres. Le premier chapitre est consacré à l'étude de la dimension de Hausdorff de l'ensemble des points ayant une décroissance exponentielle dans une fragmentation homogène en intervalles. Dans le deuxième chapitre, on construit un processus de Markov auto-similaire qui généralise les fragmentations classiques autorisant en particulier la taille des descendants à être plus grande que celle de leurs parents. On établit ensuite certains théorèmes limites en utilisant la théorie des processus auto-similaires. Dans le troisième chapitre, on s'intéresse à un problème statistique provenant de l'industrie minière avec l'estimation statistique de la mesure de Lévy du subordinateur classiquement associé à la fragmentation. Plus précisément, on observe les fragments seulement à l'instant où ils atteignent une taille inférieure à un seuil fixé. Enfin, dans un quatrième chapitre on étudie le coût énergétique d'une succession de fragmentations.

Dans de nombreux domaines, décrire l'évolution des phénomènes dans le temps est d'un intérêt capital, en particulier pour aborder les problématiques de la prédiction et de la recherche de facteurs causaux. En épidémiologie, on dispose de données de cohorte qui renseignent sur un groupe de patients suivis dans le temps. Les modèles multi-états de type Markovien proposent un outil intéressant qui permet d'étudier l'évolution d'un patient à travers les différents stades d'une maladie. Dans ce manuscrit, nous rappelons tout d'abord la méthodologie relative au modèle de Markov homogène. Ce modèle est le moins complexe, il suppose que les intensités de transition entre les états sont constantes dans le temps. Dans un second temps, nous étudions un modèle semi-Markovien homogène qui suppose que les intensités de transition dépendent du temps écoulé dans un état de santé. La théorie des processus de comptage est ensuite présentée afin d'introduire des méthodes d'estimations non-paramétriques dans le cadre d'un modèle de Markov non-homogène. Dans ce modèle, les intensités de transition dépendent du temps depuis l'inclusion dans l'étude. Les méthodes d'estimation supposent que le mécanisme de censure n'apporte aucune information sur l'évolution de la maladie. Cette hypothèse étant rarement vérifiée en pratique, nous proposons une méthode d'estimation permettant de prendre en compte une censure informative. Nous présentons également une méthode de programmation visant à faciliter la mise en œuvre des estimateurs basés sur les processus de comptage. Toutes ces méthodes sont appliquées afin d'étudier une base de données de patients asthmatiques. L'objectif est d'aider les cliniciens à mieux comprendre l'évolution de la maladie. Les résultats permettent de mettre en évidence l'impact négatif du surpoids sur l'évolution de l'asthme.

Pour obtenir des listes de mots de fréquences exceptionnelles par rapport à un modèle aléatoire, par exemple dans un contexte de biologie moléculaire, il faut quantifier la qualité de la prédiction des fréquences d'une famille de mots. Nous étudions les probabilités de grandes déviations du processus vectoriel de comptage d'une famille de mots dans des modèles de Markov et des modèles de Markov cachés. Pour démontrer ces résultats, nous établissont un développement du type Edgeworth sur les fonctionnelles additives d'une chaîne de Markov finie. Nous utilisons les théorèmes obtenus pour produire des listes de mots exceptionnels dans les génomes d'Escherichia Coli et de Bacillus Subtilis par conditionnements successifs d'un modèle statistique initial.

On étudie à la fois l'estimation de l'entropie de Shannon d'une probabilité à partir d'observations indépendantes ou markoviennes, et l'estimation du taux d'entropie d'un processus markovien de sauts d'espace d'état fini, à partir d'observations continues ou discrètes. Plusieurs problèmes connexes sont traités. Certains apparaissent en amont de l'estimation, comme l'étude de la géométrie de la divergence de Kullback-Leibler en lien avec la transformation escorte. D'autres apparaissent comme des applications des résultats d'estimation obtenus. On construit ainsi des tests sur le niveau d'entropie d'une probabilité, à partir d'un principe de grandes déviations pour la suite des estimateurs empiriques de l'entropie d'une suite de variables indépendantes. On étudie également diverses propriétés en lien avec l'estimation de l'entropie et du taux d'entropie de files d'attente modélisées par des processus markoviens de naissance et de mort.

Les travaux présentés concernent trois thématiques connexes~: Interprétation et étude probabiliste d'équations de McKean-Vlasov - propagation du chaos, - estimation quantitative de la convergence à l'équilibre, - modèles cinétiques. Inégalités fonctionnelles - inégalités fonctionnelles et concentration de la mesure pour les schémas d'Euler, - comportement en temps long de diffusions inhomogènes, - inégalités fonctionnelles et concentration de la mesure pour un mélange. Processus de Markov déterministes par morceaux - modélisation markovienne (télécomunications, biologie, chimie), - construction de couplage explicites et convergence en temps long, - propriétés de la mesure invariante. Le fil rouge de ce travail est la recherche de bornes quantitatives pour l'étude de processus de Markov issus de la modélisation (physique, biologie, etc). Souvent, ces processus possèdent des propriétés de symétrie, de régularité ou de monotonie qu'il est possible d'exploiter pour étudier finement leurs comportements. L'idée est donc ici non pas de chercher à établir des propriétés génériques et qualitatives valables pour la classe la plus large de processus mais bien d'utiliser la dynamique spécifique des processus étudiés pour décrire leur convergence à l'équilibre.

Les processus de Markov auto-similaires apparaissent souvent dans diverses parties de la théorie de probabilités comme limites de processus normalisés. La propriété de Markov ajoutée à l'auto-similarité fournit des propriétés très intéressantes comme l'avait remarqué Lamperti. La première partie de cette thèse est consacrée à l'étude de l'enveloppe inférieure et supérieure au moyen de test intégraux et de lois du logarithme itéré pour une classe suffisamment grandes des processus de Markov auto-similaires positifs et quelques processus associés, comme le minimum futur et le processus de Markov auto-similaire positif réflechi en son minimum futur. La seconde partie concernent à l'étude des forêt de Lévy stables conditionnés par leur taille et leur masse. En particulier, un principe d'invariance est établi pour la forêt de Galton-Watson conditionnée par leur taille et leur masse.