La segmentation de page est l'une des étapes les plus importantes de l'analyse d'images de documents. Idéalement, une méthode de segmentation doit être capable de reconstituer la structure complète de toute page de document, en distinguant les zones de textes, les parties graphiques, les photographies, les croquis, les figures, les tables, etc. En dépit de nombreuses méthodes proposées à ce jour pour produire une segmentation de page correcte, les difficultés sont toujours nombreuses. Le chef de file du projet qui a rendu possible le financement de ce travail de thèse (*) utilise une chaîne de traitement complète dans laquelle les erreurs de segmentation sont corrigées manuellement. Hormis les coûts que cela représente, le résultat est subordonné au réglage de nombreux paramètres. En outre, certaines erreurs échappent parfois à la vigilance des opérateurs humains. Les résultats des méthodes de segmentation de page sont généralement acceptables sur des documents propres et bien imprimés; mais l'échec est souvent à constater lorsqu'il s'agit de segmenter des documents manuscrits, lorsque la structure de ces derniers est vague, ou lorsqu'ils contiennent des notes de marge. En outre, les tables et les publicités présentent autant de défis supplémentaires à relever pour les algorithmes de segmentation. Notre méthode traite ces problèmes. La méthode est divisée en quatre parties : - A contrario de ce qui est fait dans la plupart des méthodes de segmentation de page classiques, nous commençons par séparer les parties textuelles et graphiques de la page en utilisant un arbre de décision boosté. - Les parties textuelles et graphiques sont utilisées, avec d'autres fonctions caractéristiques, par un champ conditionnel aléatoire bidimensionnel pour séparer les colonnes de texte. - Une méthode de détection de lignes, basée sur les profils partiels de projection, est alors lancée pour détecter les lignes de texte par rapport aux frontières des zones de texte. - Enfin, une nouvelle méthode de détection de paragraphes, entraînée sur les modèles de paragraphes les plus courants, est appliquée sur les lignes de texte pour extraire les paragraphes, en s'appuyant sur l'apparence géométrique des lignes de texte et leur indentation. Notre contribution sur l'existant réside essentiellement dans l'utilisation, ou l'adaptation, d'algorithmes empruntés aux méthodes d'apprentissage automatique de données, pour résoudre les cas les plus difficiles. Nous démontrons en effet un certain nombre d'améliorations : sur la séparation des colonnes de texte lorsqu'elles sont proches l'une de l'autre~; sur le risque de fusion d'au moins deux cellules adjacentes d'une même table~; sur le risque qu'une région encadrée fusionne avec d'autres régions textuelles, en particulier les notes de marge, même lorsque ces dernières sont écrites avec une fonte proche de celle du corps du texte. L'évaluation quantitative, et la comparaison des performances de notre méthode avec des algorithmes concurrents par des métriques et des méthodologies d'évaluation reconnues, sont également fournies dans une large mesure.(*) Cette thèse a été financée par le Conseil Général de Seine-Saint-Denis, par l'intermédiaire du projet Demat-Factory, initié et conduit par SAFIG SA / Document page segmentation is one of the most crucial steps in document image analysis. It ideally aims to explain the full structure of any document page, distinguishing text zones, graphics, photographs, halftones, figures, tables, etc. Although to date, there have been made several attempts of achieving correct page segmentation results, there are still many difficulties. The leader of the project in the framework of which this PhD work has been funded (*) uses a complete processing chain in which page segmentation mistakes are manually corrected by human operators. Aside of the costs it represents, this demands tuning of a large number of parameters; moreover, some segmentation mistakes sometimes escape the vigilance of the operators. Current automated page segmentation methods are well accepted for clean printed documents; but, they often fail to separate regions in handwritten documents when the document layout structure is loosely defined or when side notes are present inside the page. Moreover, tables and advertisements bring additional challenges for region segmentation algorithms. Our method addresses these problems. The method is divided into four parts:1. Unlike most of popular page segmentation methods, we first separate text and graphics components of the page using a boosted decision tree classifier.2. The separated text and graphics components are used among other features to separate columns of text in a two-dimensional conditional random fields framework.3. A text line detection method, based on piecewise projection profiles is then applied to detect text lines with respect to text region boundaries.4. Finally, a new paragraph detection method, which is trained on the common models of paragraphs, is applied on text lines to find paragraphs based on geometric appearance of text lines and their indentations. Our contribution over existing work lies in essence in the use, or adaptation, of algorithms borrowed from machine learning literature, to solve difficult cases. Indeed, we demonstrate a number of improvements : on separating text columns when one is situated very close to the other; on preventing the contents of a cell in a table to be merged with the contents of other adjacent cells; on preventing regions inside a frame to be merged with other text regions around, especially side notes, even when the latter are written using a font similar to that the text body. Quantitative assessment, and comparison of the performances of our method with competitive algorithms using widely acknowledged metrics and evaluation methodologies, is also provided to a large extend.(*) This PhD thesis has been funded by Conseil Général de Seine-Saint-Denis, through the FUI6 project Demat-Factory, lead by Safig SA

Un système de dialogue permet de doter la Machine de la capacité d'interagir de façon naturelle et efficace avec l'Homme. Dans cette thèse nous nous intéressons au développement d'un système de dialogue reposant sur des approches statistiques, et en particulier du cadre formel des Processus Décisionnel de Markov Partiellement Observable, en anglais Partially Observable Markov Decision Process (POMDP), qui à ce jour fait office de référence dans la littérature en ce qui concerne la gestion statistique du dialogue. Ce modèle permet à la fois une prise en compte améliorée de l'incertitude inhérente au traitement des données en provenance de l'utilisateur (notamment la parole) et aussi l'optimisation automatique de la politique d'interaction à partir de données grâce à l'apprentissage par renforcement, en anglais Reinforcement Learning (RL). Cependant, une des problématiques liées aux approches statistiques est qu'elles nécessitent le recours à une grande quantité de données d'apprentissage pour atteindre des niveaux de performances acceptables. Or, la collecte de telles données est un processus long et coûteux qui nécessite généralement, pour le cas du dialogue, la réalisation de prototypes fonctionnels avec l'intervention d'experts et/ou le développement de solution alternative comme le recours à la simulation d'utilisateurs. En effet, très peu de travaux considèrent à ce jour la possibilité d'un apprentissage de la stratégie de la Machine de part sa mise en situation de zéro (sans apprentissage préalable) face à de vrais utilisateurs. Pourtant cette solution présente un grand intérêt, elle permet par exemple d'inscrire le processus d'apprentissage comme une partie intégrante du cycle de vie d'un système lui offrant la capacité de s'adapter à de nouvelles conditions de façon dynamique et continue. Dans cette thèse, nous nous attacherons donc à apporter des solutions visant à rendre possible ce démarrage à froid du système mais aussi, à améliorer sa capacité à s'adapter à de nouvelles conditions (extension de domaine, changement d'utilisateur,...). Pour ce faire, nous envisagerons dans un premier temps l'utilisation de l'expertise du domaine (règles expertes) pour guider l'apprentissage initial de la politique d'interaction du système. De même, nous étudierons l'impact de la prise en compte de jugements subjectifs émis par l'utilisateur au fil de l'interaction dans l'apprentissage, notamment dans un contexte de changement de profil d'utilisateur où la politique préalablement apprise doit alors pouvoir s'adapter à de nouvelles conditions. Les résultats obtenus sur une tâche de référence montrent la possibilité d'apprendre une politique (quasi-)optimale en quelques centaines d'interactions, mais aussi que les informations supplémentaires considérées dans nos propositions sont à même d'accélérer significativement l'apprentissage et d'améliorer la tolérance aux bruits dans la chaîne de traitement. Dans un second temps nous nous intéresserons à réduire les coûts de développement d'un module de compréhension de la parole utilisé dans l'étiquetage sémantique d'un tour de dialogue. Pour cela, nous exploiterons les récentes avancées dans les techniques de projection des mots dans des espaces vectoriels continus conservant les propriétés syntactiques et sémantiques, pour généraliser à partir des connaissances initiales limitées de la tâche pour comprendre l'utilisateur. Nous nous attacherons aussi à proposer des solutions afin d'enrichir dynamiquement cette connaissance et étudier le rapport de cette technique avec les méthodes statistiques état de l'art. Là encore nos résultats expérimentaux montrent qu'il est possible d'atteindre des performances état de l'art avec très peu de données et de raffiner ces modèles ensuite avec des retours utilisateurs dont le coût peut lui-même être optimisé. / A dialogue system should give the machine the ability to interactnaturally and efficiently with humans. In this thesis, we focus on theissue of the development of stochastic dialogue systems. Thus, we especiallyconsider the Partially Observable Markov Decision Process (POMDP)framework which yields state-of-the-art performance on goal-oriented dialoguemanagement tasks. This model enables the system to cope with thecommunication ambiguities due to noisy channel and also to optimize itsdialogue management strategy directly from data with Reinforcement Learning (RL)methods.Considering statistical approaches often requires the availability of alarge amount of training data to reach good performance. However, corpora of interest are seldom readily available and collectingsuch data is both time consuming and expensive. For instance, it mayrequire a working prototype to initiate preliminary experiments with thesupport of expert users or to consider other alternatives such as usersimulation techniques.Very few studies to date have considered learning a dialogue strategyfrom scratch by interacting with real users, yet this solution is ofgreat interest. Indeed, considering the learning process as part of thelife cycle of a system offers a principle framework to dynamically adaptthe system to new conditions in an online and seamless fashion.In this thesis, we endeavour to provide solutions to make possible thisdialogue system cold start (nearly from scratch) but also to improve its ability to adapt to new conditions in operation (domain extension, new user profile, etc.).First, we investigate the conditions under which initial expertknowledge (such as expert rules) can be used to accelerate the policyoptimization of a learning agent. Similarly, we study how polarized userappraisals gathered throughout the course of the interaction can beintegrated into a reinforcement learning-based dialogue manager. Morespecifically, we discuss how this information can be cast intosocially-inspired rewards to speed up the policy optimisation for bothefficient task completion and user adaptation in an online learning setting.The results obtained on a reference task demonstrate that a(quasi-)optimal policy can be learnt in just a few hundred dialogues,but also that the considered additional information is able tosignificantly accelerate the learning as well as improving the noise tolerance.Second, we focus on reducing the development cost of the spoken language understanding module. For this, we exploit recent word embedding models(projection of words in a continuous vector space representing syntacticand semantic properties) to generalize from a limited initial knowledgeabout the dialogue task to enable the machine to instantly understandthe user utterances. We also propose to dynamically enrich thisknowledge with both active learning techniques and state-of-the-artstatistical methods. Our experimental results show that state-of-the-artperformance can be obtained with a very limited amount of in-domain andin-context data. We also show that we are able to refine the proposedmodel by exploiting user returns about the system outputs as well as tooptimize our adaptive learning with an adversarial bandit algorithm tosuccessfully balance the trade-off between user effort and moduleperformance.Finally, we study how the physical embodiment of a dialogue system in a humanoid robot can help the interaction in a dedicated Human-Robotapplication where dialogue system learning and testing are carried outwith real users. Indeed, in this thesis we propose an extension of thepreviously considered decision-making techniques to be able to take intoaccount the robot's awareness of the users' belief (perspective taking)in a RL-based situated dialogue management optimisation procedure.

En planification théorique de la décision, le cadre des Processus Décisionnels Markoviens Factorisés (Factored Markov Decision Process, FMDP) a produit des algorithmes efficaces de résolution des problèmes de décisions séquentielles dans l'incertain. L'efficacité de ces algorithmes repose sur des structures de données telles que les Arbres de Décision ou les Diagrammes de Décision Algébriques (ADDs). Ces techniques de planification sont utilisées en Apprentissage par Renforcement par l'architecture SDYNA afin de résoudre des problèmes inconnus de grandes tailles. Toutefois, l'état-de-l'art des algorithmes d'apprentissage, de programmation dynamique et d'apprentissage par renforcement utilisés par SDYNA, requière que le problème soit spécifié uniquement à l'aide de variables binaires et/ou utilise des structures améliorables en termes de compacité. Dans ce manuscrit, nous présentons nos travaux de recherche visant à élaborer et à utiliser une structure de donnée plus efficace et moins contraignante, et à l'intégrer dans une nouvelle instance de l'architecture SDYNA. Dans une première partie, nous présentons l'état-de-l'art de la modélisation de problèmes de décisions séquentielles dans l'incertain à l'aide de FMDP. Nous abordons en détail la modélisation à l'aide d'DT et d'ADDs.Puis nous présentons les ORFGs, nouvelle structure de données que nous proposons dans cette thèse pour résoudre les problèmes inhérents aux ADDs. Nous démontrons ainsi que les ORFGs s'avèrent plus efficaces que les ADDs pour modéliser les problèmes de grandes tailles. Dans une seconde partie, nous nous intéressons à la résolution des problèmes de décision dans l'incertain par Programmation Dynamique. Après avoir introduit les principaux algorithmes de résolution, nous nous attardons sur leurs variantes dans le domaine factorisé. Nous précisons les points de ces variantes factorisées qui sont améliorables. Nous décrivons alors une nouvelle version de ces algorithmes qui améliore ces aspects et utilise les ORFGs précédemment introduits. Dans une dernière partie, nous abordons l'utilisation des FMDPs en Apprentissage par Renforcement. Puis nous présentons un nouvel algorithme d'apprentissage dédié à la nouvelle structure que nous proposons. Grâce à ce nouvel algorithme, une nouvelle instance de l'architecture SDYNA est proposée, se basant sur les ORFGs ~:~l'instance SPIMDDI. Nous testons son efficacité sur quelques problèmes standards de la littérature. Enfin nous présentons quelques travaux de recherche autour de cette nouvelle instance. Nous évoquons d'abord un nouvel algorithme de gestion du compromis exploration-exploitation destiné à simplifier l'algorithme F-RMax. Puis nous détaillons une application de l'instance SPIMDDI à la gestion d'unités dans un jeu vidéo de stratégie en temps réel. / In decision theoretic planning, the factored framework (Factored Markovian Decision Process, FMDP) has produced several efficient algorithms in order to resolve large sequential decision making under uncertainty problems. The efficiency of this algorithms relies on data structures such as decision trees or algebraïc decision diagrams (ADDs). These planification technics are exploited in Reinforcement Learning by the architecture SDyna in order to resolve large and unknown problems. However, state-of-the-art learning and planning algorithms used in SDyna require the problem to be specified uniquely using binary variables and/or to use improvable data structure in term of compactness. In this book, we present our research works that seek to elaborate and to use a new data structure more efficient and less restrictive, and to integrate it in a new instance of the SDyna architecture. In a first part, we present the state-of-the-art modeling tools used in the algorithms that tackle large sequential decision making under uncertainty problems. We detail the modeling using decision trees and ADDs. Then we introduce the Ordered and Reduced Graphical Representation of Function, a new data structure that we propose in this thesis to deal with the various problems concerning the ADDs. We demonstrate that ORGRFs improve on ADDs to model large problems. In a second part, we go over the resolution of large sequential decision under uncertainty problems using Dynamic Programming. After the introduction of the main algorithms, we see in details the factored alternative. We indicate the improvable points of these factored versions. We describe our new algorithm that improve on these points and exploit the ORGRFs previously introduced. In a last part, we speak about the use of FMDPs in Reinforcement Learning. Then we introduce a new algorithm to learn the new datastrcture we propose. Thanks to this new algorithm, a new instance of the SDyna architecture is proposed, based on the ORGRFs : the SPIMDDI instance. We test its efficiency on several standard problems from the litterature. Finally, we present some works around this new instance. We detail a new algorithm for efficient exploration-exploitation compromise management, aiming to simplify F-RMax. Then we speak about an application of SPIMDDI to the managements of units in a strategic real time video game.