La recherche de structures arborescentes fréquentes, également appelée fouille d'arbres, au sein de bases de données composées de documents semi-structurés (e.g. XML) est une problématique actuellement très active. Ce processus trouve de nombreux intérêts dans le contexte de la fouille de données comme par exemple la construction automatique d'un schéma médiateur à partir de schémas XML, ou bien l'analyse des structures des sites Web afin d'étudier son usage ou modifier son contenu.<br /><br />L'objectif de cette thèse est de proposer une méthode d'extraction d'arborescences fréquentes. Cette approche est basée sur une représentation compacte des arborescences cherchant à diminuer la consommation de mémoire dans le processus de fouille. En particulier, nous présentons une nouvelle technique de génération d'arborescences candidates visant à réduire leur nombre. Par ailleurs, nous proposons différents algorithmes pour valider le support des arborescences candidates dans une base de données selon divers types de contraintes d'inclusion d'arbres : induite, incrustée et floue. Finalement nous appliquons nos algorithmes à des jeux de données synthétiques et réels et nous présentons les résultats obtenus.

La mise en correspondance sémantique appliquée à des schémas hétérogènes dans les systèmes de partage de données est une tache fastidieuse et source d'erreurs. La thèse présente une nouvelle méthode automatique et robuste qui intègre un grand nombre de schémas sous forme arborescente et de domaine spécifique. Elle permet de découvrir des correspondances sémantiques entre eux. La méthode crée également les mappings entre des schémas sources et le schéma intégré. Puis, le manuscrit présente une technique pour découvrir d'une manière automatique des correspondances complexes entre deux schémas. <br /><br />Les outils de mise en correspondance existants utilisent des techniques semi-automatiques uniquement entre deux schémas. Dans un scénario à grande échelle, où le partage des données implique un grand nombre de sources de données, ces techniques ne sont pas adaptées. De plus, la mise en correspondance semi-automatique nécessite l'intervention de l'utilisateur pour finaliser les mappings. Bien qu'elle offre la possibilité de découvrir les mappings les plus appropriés, les performances s'en trouvent fortement dégradées. Dans un premier temps, le manuscrit présente en détails l'état de l'art sur la mise en correspondance. Nous expliquons les inconvénients des outils actuellement disponibles pour répondre aux contraintes d'un scénario à grande échelle. Notre approche, PORSCHE (Performance ORiented SCHEma mediation) évite ces inconvénients et ses avantages sont mis en évidence de manière empirique.<br /><br />Le principe de l'algorithme de PORSCHE consiste à regrouper d'abord les nœuds de l'arbre selon la similarité linguistique de leurs labels. Ensuite, des techniques de fouilles d'arbres utilisant les rangs des nœuds calculés au moyen du parcours en profondeur de l'arbre sont appliquées. Cela réduit l'espace de recherche d'un nœud cible et améliore par conséquent les performances, ce qui en fait une technique adaptée au contexte large échelle. PORSCHE implémente une approche hybride, qui crée également en parallèle et de manière incrémentale un schéma intégré qui englobe tous les schémas, tout en définissant les correspondances entre ces derniers et le schéma intégré. L'approche découvre des correspondances 1:1 dans un but d'intégration et de médiation. Finalement, des expérimentations sur des jeux de données réels et synthétiques montrent que PORSCHE passe à l'échelle avec de scénarios de grande échelle. La qualité des correspondances découvertes et l'intégrité du schéma intégré sont également vérifiées par une évaluation empirique.<br /><br />Par ailleurs, nous présentons une technique CMPV ({\bf C}omplex {\bf M}atch {\bf P}roposition et {\bf V}alidation), pour la découverte de correspondances complexes (1:n, n:1 et n:m), entre deux schémas, validée par l'utilisation de mini-taxonomies. Cette partie est une version étendue de l'aspect de mise en correspondance de PORSCHE. Les mini-taxonomies sont extraites d'un vaste ensemble de métadonnées de domaine spécifique représenté comme des structures arborescentes. Nous proposons un cadre, appelé ExSTax ({\bf Ex}tracting {\bf S}tructurally Coherent Mini-{\bf Tax}onomies) basé sur la fouille d'arbres pour appuyer notre idée. C'est l'extension de la méthode fouille d'arbres de PORSCHE. Enfin, on utilise la technique ExSTax pour extraire une taxonomie fiable spécifique à un domaine.

Ma thèse s'intitule « Contributions sur la prise de décision séquentielle basée sur des simulations dans des environnements complexes de grande dimension ». Le cadre de la thèse s'articule autour du jeu, de la planification et des processus de décision markovien. Un agent interagit avec son environnement en prenant successivement des décisions. L'agent part d'un état initial jusqu'à un état final dans lequel il ne peut plus prendre de décision. A chaque pas de temps, l'agent reçoit une observation de l'état de l'environnement. A partir de cette observation et de ses connaissances, il prend une décision qui modifie l'état de l'environnement. L'agent reçoit en conséquence une récompense et une nouvelle observation. Le but est de maximiser la somme des récompenses obtenues lors d'une simulation qui part d'un état initial jusqu'à un état final. La politique de l'agent est la fonction qui, à partir de l'historique des observations, retourne une décision. Nous travaillons dans un contexte où (i) le nombre d'états est immense, (ii) les récompenses apportent peu d'information, (iii) la probabilité d'atteindre rapidement un bon état final est faible et (iv) les connaissances a priori de l'environnement sont soit inexistantes soit difficilement exploitables. Les 2 applications présentées dans cette thèse répondent à ces contraintes : le jeu de Go et le simulateur 3D du projet européen MASH (Massive Sets of Heuristics). Afin de prendre une décision satisfaisante dans ce contexte, plusieurs solutions sont apportées :1. simuler en utilisant le compromis exploration/exploitation (MCTS)2. réduire la complexité du problème par des recherches locales (GoldenEye)3. construire une politique qui s'auto-améliore (RBGP)4. apprendre des connaissances a priori (CluVo+GMCTS) L'algorithme Monte-Carlo Tree Search (MCTS) est un algorithme qui a révolutionné le jeu de Go. A partir d'un modèle de l'environnement, MCTS construit itérativement un arbre des possibles de façon asymétrique en faisant des simulations de Monte-Carlo et dont le point de départ est l'observation courante de l'agent. L'agent alterne entre l'exploration du modèle en prenant de nouvelles décisions et l'exploitation des décisions qui obtiennent statistiquement une bonne récompense cumulée. Nous discutons de 2 moyens pour améliorer MCTS : la parallélisation et l'ajout de connaissances a priori. La parallélisation ne résout pas certaines faiblesses de MCTS ; notamment certains problèmes locaux restent des verrous. Nous proposons un algorithme (GoldenEye) qui se découpe en 2 parties : détection d'un problème local et ensuite sa résolution. L'algorithme de résolution réutilise des principes de MCTS et fait ses preuves sur une base classique de problèmes difficiles. L'ajout de connaissances à la main est laborieuse et ennuyeuse. Nous proposons une méthode appelée Racing-based Genetic Programming (RBGP) pour ajouter automatiquement de la connaissance. Le point fort de cet algorithme est qu'il valide rigoureusement l'ajout d'une connaissance a priori et il peut être utilisé non pas pour optimiser un algorithme mais pour construire une politique. Dans certaines applications telles que MASH, les simulations sont coûteuses en temps et il n'y a ni connaissance a priori ni modèle de l'environnement; l'algorithme Monte-Carlo Tree Search est donc inapplicable. Pour rendre MCTS applicable dans MASH, nous proposons une méthode pour apprendre des connaissances a priori (CluVo). Nous utilisons ensuite ces connaissances pour améliorer la rapidité de l'apprentissage de l'agent et aussi pour construire un modèle. A partir de ce modèle, nous utilisons une version adaptée de Monte-Carlo Tree Search (GMCTS). Cette méthode résout de difficiles problématiques MASH et donne de bons résultats dans une application dont le but est d'améliorer un tirage de lettres. / My thesis is entitled "Contributions to Simulation-based High-dimensional Sequential Decision Making". The context of the thesis is about games, planning and Markov Decision Processes. An agent interacts with its environment by successively making decisions. The agent starts from an initial state until a final state in which the agent can not make decision anymore. At each timestep, the agent receives an observation of the state of the environment. From this observation and its knowledge, the agent makes a decision which modifies the state of the environment. Then, the agent receives a reward and a new observation. The goal is to maximize the sum of rewards obtained during a simulation from an initial state to a final state. The policy of the agent is the function which, from the history of observations, returns a decision. We work in a context where (i) the number of states is huge, (ii) reward carries little information, (iii) the probability to reach quickly a good final state is weak and (iv) prior knowledge is either nonexistent or hardly exploitable. Both applications described in this thesis present these constraints : the game of Go and a 3D simulator of the european project MASH (Massive Sets of Heuristics). In order to take a satisfying decision in this context, several solutions are brought : 1. Simulating with the compromise exploration/exploitation (MCTS) 2. Reducing the complexity by local solving (GoldenEye) 3. Building a policy which improves itself (RBGP) 4. Learning prior knowledge (CluVo+GMCTS) Monte-Carlo Tree Search (MCTS) is the state of the art for the game of Go. From a model of the environment, MCTS builds incrementally and asymetrically a tree of possible futures by performing Monte-Carlo simulations. The tree starts from the current observation of the agent. The agent switches between the exploration of the model and the exploitation of decisions which statistically give a good cumulative reward. We discuss 2 ways for improving MCTS : the parallelization and the addition of prior knowledge. The parallelization does not solve some weaknesses of MCTS; in particular some local problems remain challenges. We propose an algorithm (GoldenEye) which is composed of 2 parts : detection of a local problem and then its resolution. The algorithm of resolution reuses some concepts of MCTS and it solves difficult problems of a classical database. The addition of prior knowledge by hand is laborious and boring. We propose a method called Racing-based Genetic Programming (RBGP) in order to add automatically prior knowledge. The strong point is that RBGP rigorously validates the addition of a prior knowledge and RBGP can be used for building a policy (instead of only optimizing an algorithm). In some applications such as MASH, simulations are too expensive in time and there is no prior knowledge and no model of the environment; therefore Monte-Carlo Tree Search can not be used. So that MCTS becomes usable in this context, we propose a method for learning prior knowledge (CluVo). Then we use pieces of prior knowledge for improving the rapidity of learning of the agent and for building a model, too. We use from this model an adapted version of Monte-Carlo Tree Search (GMCTS). This method solves difficult problems of MASH and gives good results in an application to a word game.