Search

National audience; Interpretable Machine Learning models receive growing interest due to the increasing concerns in understanding the reasoning behind some crucial decisions made by modern Artificial Intelligent systems. Due to their structure, especially with small sizes, these interpretable models are inherently understandable for humans. Compared to classical heuristic methods to learn these models, recent exact methods offer more compact models or better prediction quality. In this thesis, we propose two novel exact methods via Maximum Boolean Satisfiability (MaxSAT) to learn optimal interpretable machine learning models.Our contribution starts with an original MaxSAT-based exact method to learnoptimal decision trees. This method optimizes the empirical accuracy to avoidoverfitting and also enriches the constraints to restrict the tree depth. Additionally,we integrate this MaxSAT-based method in AdaBoost, which is a classical Boostingmethod to improve the generalization performance. The experimental results showthe competitive prediction quality of this MaxSAT-based method compared to state-of-the-art heuristics and other exact methods. Additionally, clear improvements inprediction performance are observed after the integration in AdaBoost.Our second contribution is an original MaxSAT-based exact method to optimize binary decision diagrams. We introduce an initial Boolean Satisfiability (SAT) encoding to model binary decision diagrams in limited depth with perfect empirical accuracy. Next, we present how to adapt the SAT-based model into MaxSAT approach. Finally, we present a pre-processing for selecting some important features to increase the scalability of our MaxSAT-based method to optimize binary decision diagrams. The experimental results show clear advances of our MaxSAT-based method in prediction quality, compared to state-of-the-art heuristic methods. We also observe a huge shrink in encoding size and model size in comparison between our approach and state-of-the-art exact method without losing the prediction performance. In addition, great reductions in encoding size are displayed after the application of pre-processing, which boosts the scalability.; Les modèles d’apprentissage interprétables reçoivent un intérêt croissant en raisonde l’augmentation des préoccupations pour comprendre le raisonnement menantaux décisions cruciales prises par les systèmes modernes d’intelligence artificielle.En raison de leur structure, en particulier pour des petites tailles, ces modèlesinterprétables sont intrinsèquement compréhensibles pour les humains. Par rapportaux méthodes heuristiques classiques pour apprendre ces modèles, les méthodesexactes récentes offrent des modèles plus compacts ou atteingnent une meilleurequalité de prédiction. Dans cette thèse, nous proposons deux nouvelles méthodesexactes basées sur la Satisfiabilité Booléenne Maximale (MaxSAT) pour apprendredes modèles d’apprentissage interprétables optimaux.Notre contribution commence par une méthode exacte originale basée sur MaxSATpour apprendre des arbres de décision optimaux. Cette méthode optimise la précision empirique pour éviter le surapprentissage et prend également en compte des contraintes pour restreindre la profondeur de l’arbre. De plus, nous intégrons cette méthode basée sur MaxSAT à la méthode AdaBoost, qui est une méthode standard de Boosting pour améliorer les performances de généralisation. Les résultats expérimentaux montrent une qualité de prédiction compétitive de cette méthode basée sur MaxSAT par rapport à des méthodes heuristiques et exactes de l’état de l’art. En plus, des améliorations des performances de prédiction sont observées après intégration dans AdaBoost.Notre deuxième contribution est une méthode exacte originalebasée sur MaxSAT pour optimiser les diagrammes de décision binaire. Nous introduisons tout d’abord un encodage de Satisfiabilité Booléenne (SAT) pour modéliser des diagrammes de décision binaire de profondeur limitée avec une parfaite précision. Puis, nous présentons comment adapter le modèle en Satisfiabilité Booléenne Maximale. Finalement, nous présentons un pré-traitement pour la sélection de certaines caractéristiques importantes afin d’augmenter le passage à l’échelle de notre méthode MaxSAT pour optimiser les diagrammes de décision binaire. Les résultats expérimentaux montrent des avancées de notre méthode MaxSAT sur la qualité de prédiction, par rapport aux méthodes heuristiques. Nous observons également une réduction importante sur la taille d’encodage et la taille du modèle dans les comparaisons entre notre approche et une méthode exacte de l’état de l’art, sans perdre en performance de prédiction. De plus, une grande réduction sur la taille d’encodage est mise en évidence après application du pré-traitement, ce qui renforce le passage à l’échelle.

Publication LLA 8/2 2022 mais parution en ligne avril 2023; International audience; The noncausal/causal alternation is the pairing of two verb forms that refer to the same core event but differ in the absence vs. presence of a causer for this event (e.g. rise vs. raise, open (intr.) vs. open (tr.), die vs. kill). Languages differ in their overall preferences among the possible strategies for coding this alternation. This study uses machine-learning methods (clustering and tree-based computational classifiers) to investigate the predictive power of the noncausal/causal alternation for the genealogical affiliation of 38 languages belonging to the Atlantic, Mande and Mel families. The languages studied here belong to different contact areas in Senegal and its surroundings. The three families are all affiliated to the Niger-Congo phylum but display quite different typological profiles. The present paper elaborates on an earlier study that used a standard list of 18 verb pairs to establish the coding strategies in these languages. Apart from highlighting which coding strategies are favored in each family, our quantitative analyses show that the family affiliation of the 38 languages can be predicted with an accuracy above the majority baseline based on the information of the noncausal/causal alternation in the 18 verb pairs, but that the predictive power of verb pairs 1-9 is generally lower than of verb pairs 10-18. Our results confirm the hypothesis that the first group of verb pairs shows universal rather than lineage-specific tendencies concerning the noncausal/causal alternation. Furthermore, our analyses identify which of the 18 verb pairs (and their correlated coding strategies) have the highest predictive power. This study opens new avenues for identifying the relevant synchronic data for genealogical classification in historical linguistics. Future studies could replicate the same analysis in different language families to assess if our results are universal or specific to some language families.; L’alternance noncausal/causal désigne l’appariement de deux formes verbales référant à un même événement mais se distinguant par l'absence vs. présence d’un causateur de l’événement (e.g. rise vs. raise, open (intr.) vs. open (tr.) ou die vs. kill). Les langues emploient diverses stratégies pour encoder cette opposition. Cette étude utilise des méthodes d’apprentissage-machine (clustering et classificateurs computationnels fondés sur des arbres de décision) afin d’analyser le pouvoir prédictif des stratégies d’encodage sur l'affiliation généalogique de 38 langues appartenant aux familles Atlantique, Mandé et Mel. Les langues de l’enquête sont essentiellement localisées au Sénégal et dans ses environs où existent des zones de contact. Ces trois familles relèvent du même phylum Niger-Congo mais présentent des profils typologiques assez différents. Le traitement de l’alternance causale comme marqueur généalogique est traité ici à partir d’une étude antérieure utilisant une liste standardisée de 18 paires de verbes pour établir les stratégies employées dans ces langues. En plus d'indiquer quelles stratégies sont favorisées dans chaque famille, nos analyses quantitatives montrent que l'affiliation généalogique des 38 langues peut être prédite avec une grande précision à partir des stratégies de codage de l’alternance causale utilisées pour les 18 paires de verbes, mais que le pouvoir prédictif des paires de verbes 1-9 est généralement inférieur à celui des paires de verbes 10-18. Ces résultats confirment l'hypothèse selon laquelle le premier groupe de verbes montre des tendances universelles plutôt qu’une variation interlinguistique dans le marquage de l’alternance noncausal/causal. De plus, notre analyse identifie pour ces familles de langues quelles paires de verbes spécifiques parmi les 18 sélectionnées ont le pouvoir prédictif le plus élevé. Cette approche ouvre de nouvelles voies pour résoudre un problème fondamental de la linguistique historique, celui des filtres nécessaires pour trier les données synchroniques pertinentes pour la classification généalogique. Des études futures pourraient reproduire la même analyse sur différentes familles de langues pour évaluer si ces résultats sont universels ou spécifiques à certaines familles de langues.

The diagnosis of dental cracks is for the most part a difficult diagnosis. Even once identified, it is laborious for practitioners to restore the tooth with the appropriate treatment as there is no real consensus in the literature, and the type of restoration used often depends on the practitioner's interpretation. The aim of this work is through the study of literature reviews, to summarize the protocol in order to identify the crack through precise clinical elements and thus to propose treatments adapted according to the positioning, the extent of the crack and its prognosis. A decision tree has been drawn up to help the clinician manage the crack through its treatment according to its different degrees of development.; Le diagnostic des fêlures dentaires est pour la plupart du temps un diagnostic difficile. Même une fois identifiée, il est laborieux pour les praticiens de restaurer la dent avec un traitement adapté car il n’y a pas de réel consensus dans la littérature, et le type de restauration utilisée dépend souvent de l’interprétation du praticien. Ce travail a pour but à travers l’étude de revues de littérature, de résumer le protocole afin d’identifier la fêlure par le biais d’éléments cliniques précis et ainsi proposer des traitements adaptés en fonction du positionnement, de l’étendue de la fêlure et de son pronostic. Un arbre décisionnel a été rédigé afin d’aider le clinicien à la prise en charge de la fêlure par son traitement en fonction de ses différents degrés d’évolution.

Les traumatismes du poignet représentent une plainte fréquente aux urgences. À ce jour, la radiographie fait partie intégrante de l’examen du traumatisé du poignet et est à ce compte, réalisée de manière systématique. Le but de cette étude est de déterminer des critères cliniques qui permettent de déterminer la nécessité de la réalisation de la radiographie de manière systématique.MÉTHODE : Cette étude est réalisée de manière rétrospective du 01 janvier 2017 au 01 janvier 2020 au CHU de Rouen grâce à l’extraction de données issues des dossiers du service d’urgences adultes. Les 882 patients inclus sont les adultes se présentant pour un traumatisme isolé du poignet et ayant réalisé une radiographie lors de la consultation aux urgences. Les données extraites sont les données cliniques et anamnestiques reportées par les infirmiers et médecins en charge du patient. RÉSULTATS : Après analyse multivariée, les critères cliniques significatifs de lésions osseuses sont l’âge de plus de 65 ans, la douleur à la palpation, l’oedème, l’impotence fonctionnelle et la déformation. Leur absence lors de l’examen clinique réalise une valeur prédictive négative de 97%. Un algorithme décisionnel intégrant les variables issues de ces données permettrait d’éviter la réalisation d’un quart des radiographies sur les 302 patients étudiés avec un risque de sous-triage de 2%. CONCLUSION : Un algorithme de prise en charge des traumatismes du poignet isolés est possible, permettant une diminution du nombre de radiographies réalisées. Une évaluation de ce score reste à réaliser sur une population à plus grande échelle et de manière prospective.

In order to reduce herbicide use, new tools are needed to accompany farmers and crop advisors designing weed management strategies that use few or no herbicides. To this end, we developed a Decision Support System (DSS) for designing cropping systems accommodating both crop and ecosystem protection. Our approach combined development of the tool structure, with future users, with the simplification of the research model FlorSys, which simulates the impact of cropping systems on crop production and weed dynamics. FlorSys is a “virtual field” where cropping-system impacts on weeds dynamics are simulated at the field scale. The resulting DSS consists of: (1) tables listing the most influential cropping techniques, (2) decision trees presenting combinations of numerous cropping practices to reach a weed management goal (e.g. combine low herbicide use with low yield loss) and (3) a fast cropping system evaluation tool to live-test cropping systems, in particular during participatory workshops co-designing cropping systems with farmers; Afin de réduire l’utilisation d’herbicides, nous avons besoin de nouveaux outils pour aider à concevoir des stratégies de gestion des adventices économes en herbicides. Dans ce but, nous avons développé un Outil d'Aide à la Décision (OAD) pour accompagner la conception de systèmes de culture réconciliant protection des cultures et des écosystèmes. La démarche fait intervenir en parallèle le développement de la structure de l’outil en interaction avec les futurs utilisateurs (conseillers et agriculteurs) et une simplification du modèle de recherche FlorSys pour l’évaluation des impacts des adventices. FlorSys est une « parcelle virtuelle », où sont simulés les impacts des systèmes de culture sur la dynamique adventice à l’échelle de la parcelle. L'OAD résultant, DeciFlorSys, est composé : (1) de tableaux listant les techniques culturales les plus influentes, (2) d'arbres de décision proposant des combinaisons de pratiques culturales pour atteindre un objectif donné en terme d'impact de la flore adventice (ex. concilier faible perte de rendement et faible usage d'herbicide) et (3) d’un simulateur rapide permettant de tester, en direct sur ordinateur, de nouveaux systèmes de culture, notamment au cours d’un atelier de coconception de systèmes de culture avec des agriculteurs.

French people place a great trust in their pharmacists. It is therefore essential that those professionals are well trained to answer all patients’ questions. Anxiety, depression and sleep disorders play a major role in all queries coming through the counter. So what are those major questions? In which cases can the pharmacist take care of patients and for which cases should it be preferable for him to refer to doctors? What are the warning signs to look for? In addition, what are the different possibilities of existing therapeutic solutions and which ones should be adapted in each situation? This thesis highlights and provides pharmacists with decision making trees on the three pathologies mentioned above. This will allow pharmacists to best advise patients and to enhance their questioning and their medical advise. As a result, their legitimacy as a primary care provider will be strengthened, allowing them to continue to care for their patients.; Les français placent une grande confiance dans leur pharmacien, c’est pourquoi il est essentiel que celui ci soit bien formé pour répondre à l’ensemble de leurs questions. L’anxiété, la dépression et les troubles du sommeil occupent une place majeure dans leur demande au comptoir. Quelles sont les questions à poser ? Dans quel cas le pharmacien peut il prendre en charge un patient et dans quel cas doit il l’orienter vers son médecin traitant ? Quels sont les signes d’alarme à détecter ? De plus, quelles sont les différentes possibilités de prise en charge thérapeutiques existantes et lesquelles seront les mieux adaptées dans chaque situation ? Cette thèse met à disposition du pharmacien des arbres décisionnels sur ces trois pathologies pour le guider au mieux dans son interrogatoire et dans son conseil. Ainsi, sa légitimité en tant qu’acteur de soins de premiers recours sera renforcée, pour lui permettre de continuer à prendre soin de ses patients.

Il existe aujourd’hui sur le marché de très nombreux instruments endodontiques de mise en forme canalaire, tous susceptibles à la fracture. Des connaissances sur les causes de survenue de ces fractures ainsi que les types de fracture sont indispensables afin de les limiter au maximum. Le cone beam est de plus en plus présent dans les cabinets dentaires. Il est utilisé en endodontie car il permet une visualisation tridimensionnelle de l’anatomie dentaire, ce qui n’est pas possible sur une radiographie rétro-alvéolaire. Nous verrons quels sont les éléments à prendre en compte au niveau de l’instrument et au niveau dentaire sur l’analyse du cone beam afin de choisir la technique la plus appropriée (bypass, dépose, chirurgie apicale) pour le traitement endodontique.

National audience; Le rôle de la frontière intra-européenne a fortement évolué au cours du temps, notamment à travers la création de l’espace Schengen (1990) ou encore de la signature de différents traités (Maastricht 1992, etc.). Auparavant appréhendée comme une barrière empêchant et/ou contrôlant les passages, elle est devenue une zone d’intégration, un espace entre deux pays dont la culture, la langue, voire la règlementation sont différentes, mais qui tend vers la volonté d’estomper ces limites (développement de réseaux favorisant les mobilités, l’uniformisation du système monétaire, etc.). Malgré la disparition des contrôles aux frontières et une plus grande mobilité des populations, des différentiels subsistent, d’un point de vu socio-économique (Grasland & Hamez, 2005) ou encore d’un point de vue culturel. En effet, en dépit des projets transfrontaliers mis en place (EuroRégion, EuroDistrict, etc.), les systèmes d’acteurs en charge de les soutenir et mener à terme sont différents de part et d’autre des limites nationales, tant dans leurs structures que dans leurs méthodes.L’influence de la localisation d’un processus dans un pays ou un autre, au niveau d’une zone frontalière contigüe est abordée à travers la modélisation et simulation du développement urbain sur la zone transfrontalière franco-allemande centrée sur l’agglomération de Strasbourg – Kehl est abordé dans cette présentation. Les règles qui régissent les dynamiques d’urbanisation sont-elles basées sur des critères génériques, universels pouvant s’appliquer à la totalité d’une zone frontalière ou au contraire dépendent-ils de leur localisation dans un pays en particulier ?L’hypothèse de départ est la suivante : malgré une similarité relative de deux territoires composant la zone transfrontalière, la caractérisation du processus de développement urbain reste dépendante de la localisation étatique en raison de systèmes différents de part et d’autre de la frontière (institutions, temporalités, leviers d’action, réglementation, etc.).P. Torrens (2011) évoque le concept de « bonnes règles » qui, replacé dans la vision énoncée par W. Tobler (1970), seraient « simples » tout en permettant de simuler un processus complexe. C’est à travers le couplage d’un automate cellulaire et d’un arbre de décision que le jeu de règles permettant de simuler le développement urbain est élaboré. Cette présentation porte sur l’analyse thématique du produit de l’apprentissage automatique. Son exploration met en lumière une part transfrontalière du processus, mais aussi une part nationale. Une partie du processus s’affranchis donc de l’influence de la localisation géographique au regard de la frontière. L’analyse des règles permet d’observer leurs similitudes ou divergences au regard de l’occupation du sol présente dans le voisinage mais également suivant l’accessibilité aux pôles urbains principaux, favorable à l’urbanisation.

As for many classifiers, decision trees predictions are naturally probabilistic, with a frequentist probability distribution on labels associated to each leaf of the tree. Those probabilities have the major drawback of being potentially unreliable in the case where they have been estimated from a limited number of examples. Empirical Bayes methods enable the updating of observed probability distributions for which the parameters of the prior distribution are estimated from the data. This paper presents an approach of correcting decision trees predictive binary probabilities with an empirical Bayes method. The update of probability distributions associated with tree leaves creates a correction concentrated on small-sized leaves, which improves the quality of probabilistic tree predictions. The amplitude of these corrections is used here to generate predictive belief functions which are finally evaluated through the extension of three evaluation indexes of predictive probabilities., Comme pour de nombreux classifieurs, les prédictions issues d'arbres de décision sont naturellement probabilistes. A chaque feuille de l'arbre est associée une distribution de probabilité sur les labels estimée de façon fréquentiste. Ces probabilités présentent ainsi l'inconvénient majeur d'être potentiellement non-fiables dans le cas où elles sont estimées à partir d'un faible nombre d'exemples. Les approches bayésiennes empiriques permettent la mise-à-jour de distributions de probabilité en fonction des effectifs observés. Cet article présente une approche de correction des probabilités prédictives binaires issues d'arbres de décision au travers l'utilisation d'une méthode bayésienne empirique. L'ajustement des probabilités prédictives des arbres est ainsi concentré sur les feuilles de petites tailles, ce qui entraîne une nette amélioration des performances prédictives. L'amplitude de ces corrections est utilisée pour générer des fonctions de croyance prédictives qui sont finalement évaluées par l'extension incertaine de trois indices d'évaluation de probabilités prédictives.

National audience; This paper describes the systems developed at IRISA by the LinkMedia team for the challenge DeFT 2018. The challenge focuses on opinion mining in french tweets about transports. The team has participated in 3 out of the 4 tasks: (i) classification of the tweets whether they are about transports or not, (ii) classification of the tweets according to their polarity and (iii) fine grained annotation of the sentiment expression and the object about which an opinion is given. For the tasks 1 and 2, we have used a boosting algorithm as well as recurrent neural networks (RNN). For the 3rd task, we have experimented the use of recurrent neural networks combined with some CRF. All the approaches give close results, with a slight advantage when using RNN, and yields among the best results for every tasks; Cet article décrit les systèmes développés par l’équipe LinkMedia de l’IRISA pour la campagned’évaluation DeFT 2018 portant sur l’analyse d’opinion dans des tweets en français. L’équipe aparticipé à 3 des 4 tâches de la campagne : (i) classification des tweets selon s’ils concernent lestransports ou non, (ii) classification des tweets selon leur polarité et (iii) annotation des marqueursd’opinion et de l’objet à propos duquel est exprimée l’opinion. Nous avons utilisé un algorithme deboosting d’arbres de décision et des réseaux de neurones récurrents (RNN) pour traiter les tâches 1 et2. Pour la tâche 3 nous avons expérimenté l’utilisation de réseaux de neurones récurrents associésà des CRF. Ces approches donnent des résultats proches, avec un léger avantage aux RNN, et ontpermis d’être parmi les premiers classés pour chacune des tâches.

This work contributes to possibilistic decision theory and more specifically to sequential decision-making under possibilistic uncertainty, at both the theoretical and practical levels. Even though appealing for its ability to handle qualitative decision problems, possibilisitic decision theory suffers from an important drawback: qualitative possibilistic utility criteria compare acts through min and max operators, which leads to a drowning effect. To overcome this lack of decision power, several refinements have been proposed in the literature. Lexicographic refinements are particularly appealing since they allow to benefit from the expected utility background, while remaining "qualitative". However, these refinements are defined for the non-sequential decision problems only. In this thesis, we present results on the extension of the lexicographic preference relations to sequential decision problems, in particular, to possibilistic Decision trees and Markov Decision Processes. This leads to new planning algorithms that are more "decisive" than their original possibilistic counterparts. We first present optimistic and pessimistic lexicographic preference relations between policies with and without intermediate utilities that refine the optimistic and pessimistic qualitative utilities respectively. We prove that these new proposed criteria satisfy the principle of Pareto efficiency as well as the property of strict monotonicity. This latter guarantees that dynamic programming algorithm can be used for calculating lexicographic optimal policies. Considering the problem of policy optimization in possibilistic decision trees and finite-horizon Markov decision processes, we provide adaptations of dynamic programming algorithm that calculate lexicographic optimal policy in polynomial time. These algorithms are based on the lexicographic comparison of the matrices of trajectories associated to the sub-policies. This algorithmic work is completed with an experimental study that shows the feasibility and the interest of the proposed approach. Then we prove that the lexicographic criteria still benefit from an Expected Utility grounding, and can be represented by infinitesimal expected utilities. The last part of our work is devoted to policy optimization in (possibly infinite) stationary Markov Decision Processes. We propose a value iteration algorithm for the computation of lexicographic optimal policies. We extend these results to the infinite-horizon case. Since the size of the matrices increases exponentially (which is especially problematic in the infinite-horizon case), we thus propose an approximation algorithm which keeps the most interesting part of each matrix of trajectories, namely the first lines and columns. Finally, we reports experimental results that show the effectiveness of the algorithms based on the cutting of the matrices.; Ce travail contribue à la théorie de la décision possibiliste et plus précisément à la prise de décision séquentielle dans le cadre de la théorie des possibilités, à la fois au niveau théorique et pratique. Bien qu'attrayante pour sa capacité à résoudre les problèmes de décision qualitatifs, la théorie de la décision possibiliste souffre d'un inconvénient important : les critères d'utilité qualitatives possibilistes comparent les actions avec les opérateurs min et max, ce qui entraîne un effet de noyade. Pour surmonter ce manque de pouvoir décisionnel, plusieurs raffinements ont été proposés dans la littérature. Les raffinements lexicographiques sont particulièrement intéressants puisqu'ils permettent de bénéficier de l'arrière-plan de l'utilité espérée, tout en restant "qualitatifs". Cependant, ces raffinements ne sont définis que pour les problèmes de décision non séquentiels. Dans cette thèse, nous présentons des résultats sur l'extension des raffinements lexicographiques aux problèmes de décision séquentiels, en particulier aux Arbres de Décision et aux Processus Décisionnels de Markov possibilistes. Cela aboutit à des nouveaux algorithmes de planification plus "décisifs" que leurs contreparties possibilistes. Dans un premier temps, nous présentons des relations de préférence lexicographiques optimistes et pessimistes entre les politiques avec et sans utilités intermédiaires, qui raffinent respectivement les utilités possibilistes optimistes et pessimistes. Nous prouvons que les critères proposés satisfont le principe de l'efficacité de Pareto ainsi que la propriété de monotonie stricte. Cette dernière garantit la possibilité d'application d'un algorithme de programmation dynamique pour calculer des politiques optimales. Nous étudions tout d'abord l'optimisation lexicographique des politiques dans les Arbres de Décision possibilistes et les Processus Décisionnels de Markov à horizon fini. Nous fournissons des adaptations de l'algorithme de programmation dynamique qui calculent une politique optimale en temps polynomial. Ces algorithmes sont basés sur la comparaison lexicographique des matrices de trajectoires associées aux sous-politiques. Ce travail algorithmique est complété par une étude expérimentale qui montre la faisabilité et l'intérêt de l'approche proposée. Ensuite, nous prouvons que les critères lexicographiques bénéficient toujours d'une fondation en termes d'utilité espérée, et qu'ils peuvent être capturés par des utilités espérées infinitésimales. La dernière partie de notre travail est consacrée à l'optimisation des politiques dans les Processus Décisionnels de Markov (éventuellement infinis) stationnaires. Nous proposons un algorithme d'itération de la valeur pour le calcul des politiques optimales lexicographiques. De plus, nous étendons ces résultats au cas de l'horizon infini. La taille des matrices augmentant exponentiellement (ce qui est particulièrement problématique dans le cas de l'horizon infini), nous proposons un algorithme d'approximation qui se limite à la partie la plus intéressante de chaque matrice de trajectoires, à savoir les premières lignes et colonnes. Enfin, nous rapportons des résultats expérimentaux qui prouvent l'efficacité des algorithmes basés sur la troncation des matrices.

This work contributes to possibilistic decision theory and more specifically to sequential decision-making under possibilistic uncertainty, at both the theoretical and practical levels. Even though appealing for its ability to handle qualitative decision problems, possibilisitic decision theory suffers from an important drawback: qualitative possibilistic utility criteria compare acts through min and max operators, which leads to a drowning effect. To overcome this lack of decision power, several refinements have been proposed in the literature. Lexicographic refinements are particularly appealing since they allow to benefit from the expected utility background, while remaining "qualitative". However, these refinements are defined for the non-sequential decision problems only. In this thesis, we present results on the extension of the lexicographic preference relations to sequential decision problems, in particular, to possibilistic Decision trees and Markov Decision Processes. This leads to new planning algorithms that are more "decisive" than their original possibilistic counterparts. We first present optimistic and pessimistic lexicographic preference relations between policies with and without intermediate utilities that refine the optimistic and pessimistic qualitative utilities respectively. We prove that these new proposed criteria satisfy the principle of Pareto efficiency as well as the property of strict monotonicity. This latter guarantees that dynamic programming algorithm can be used for calculating lexicographic optimal policies. Considering the problem of policy optimization in possibilistic decision trees and finite-horizon Markov decision processes, we provide adaptations of dynamic programming algorithm that calculate lexicographic optimal policy in polynomial time. These algorithms are based on the lexicographic comparison of the matrices of trajectories associated to the sub-policies. This algorithmic work is completed with an experimental study that shows the feasibility and the interest of the proposed approach. Then we prove that the lexicographic criteria still benefit from an Expected Utility grounding, and can be represented by infinitesimal expected utilities. The last part of our work is devoted to policy optimization in (possibly infinite) stationary Markov Decision Processes. We propose a value iteration algorithm for the computation of lexicographic optimal policies. We extend these results to the infinite-horizon case. Since the size of the matrices increases exponentially (which is especially problematic in the infinite-horizon case), we thus propose an approximation algorithm which keeps the most interesting part of each matrix of trajectories, namely the first lines and columns. Finally, we reports experimental results that show the effectiveness of the algorithms based on the cutting of the matrices., Ce travail contribue à la théorie de la décision possibiliste et plus précisément à la prise de décision séquentielle dans le cadre de la théorie des possibilités, à la fois au niveau théorique et pratique. Bien qu'attrayante pour sa capacité à résoudre les problèmes de décision qualitatifs, la théorie de la décision possibiliste souffre d'un inconvénient important : les critères d'utilité qualitatives possibilistes comparent les actions avec les opérateurs min et max, ce qui entraîne un effet de noyade. Pour surmonter ce manque de pouvoir décisionnel, plusieurs raffinements ont été proposés dans la littérature. Les raffinements lexicographiques sont particulièrement intéressants puisqu'ils permettent de bénéficier de l'arrière-plan de l'utilité espérée, tout en restant "qualitatifs". Cependant, ces raffinements ne sont définis que pour les problèmes de décision non séquentiels. Dans cette thèse, nous présentons des résultats sur l'extension des raffinements lexicographiques aux problèmes de décision séquentiels, en particulier aux Arbres de Décision et aux Processus Décisionnels de Markov possibilistes. Cela aboutit à des nouveaux algorithmes de planification plus "décisifs" que leurs contreparties possibilistes. Dans un premier temps, nous présentons des relations de préférence lexicographiques optimistes et pessimistes entre les politiques avec et sans utilités intermédiaires, qui raffinent respectivement les utilités possibilistes optimistes et pessimistes. Nous prouvons que les critères proposés satisfont le principe de l'efficacité de Pareto ainsi que la propriété de monotonie stricte. Cette dernière garantit la possibilité d'application d'un algorithme de programmation dynamique pour calculer des politiques optimales. Nous étudions tout d'abord l'optimisation lexicographique des politiques dans les Arbres de Décision possibilistes et les Processus Décisionnels de Markov à horizon fini. Nous fournissons des adaptations de l'algorithme de programmation dynamique qui calculent une politique optimale en temps polynomial. Ces algorithmes sont basés sur la comparaison lexicographique des matrices de trajectoires associées aux sous-politiques. Ce travail algorithmique est complété par une étude expérimentale qui montre la faisabilité et l'intérêt de l'approche proposée. Ensuite, nous prouvons que les critères lexicographiques bénéficient toujours d'une fondation en termes d'utilité espérée, et qu'ils peuvent être capturés par des utilités espérées infinitésimales. La dernière partie de notre travail est consacrée à l'optimisation des politiques dans les Processus Décisionnels de Markov (éventuellement infinis) stationnaires. Nous proposons un algorithme d'itération de la valeur pour le calcul des politiques optimales lexicographiques. De plus, nous étendons ces résultats au cas de l'horizon infini. La taille des matrices augmentant exponentiellement (ce qui est particulièrement problématique dans le cas de l'horizon infini), nous proposons un algorithme d'approximation qui se limite à la partie la plus intéressante de chaque matrice de trajectoires, à savoir les premières lignes et colonnes. Enfin, nous rapportons des résultats expérimentaux qui prouvent l'efficacité des algorithmes basés sur la troncation des matrices.

National audience; This paper describes the participation the LinkMedia team from IRISA at DeFT2017. We carried out the three proposed tasks : classification of non-figurative tweets according to their polarity (task 1), identification figurative langage (task 2), classification of figurative and non-figurative tweets according to their polarity (task 3). For these three tasks, we adopt a standard supervised machine learning framework and explore the use of three methods of increasing complexity : i) k-nearest neighbors with information retrieval based techniques, ii) boosting of decision trees, iii) recurrent neural networks. Our approaches do not exploit rich external knowledge (lexicons, annotated corpora) and are chiefly based on the tweet content (and some other tweets for our latest approach). It allows us to evaluate the precise interest of each of our approach and the data representation that they use : bag-of-words for the first one, n-grams for the second and word embedding for the latest.; Cet article décrit la participation de l'équipe LinkMedia de l'IRISA à DeFT 2017. Notre équipe a participé aux 3 tâches : classification des tweets non figuratifs selon leur polarité (tâche 1), l'identifi-cation du langage figuratif (tâche 2) et la classification des tweets figuratifs et non figuratifs selon leur polarité (tâche 3). Pour ces trois tâches, nous adoptons une démarche d'apprentissage artificiel. Plus précisément, nous explorons l'intérêt de trois méthodes de complexité croissante : i) les k plus proches voisins issues de la recherche d'information, ii) le boosting d'arbres de décision, et iii) les réseaux neuronaux récurrents. Nos approches n'exploitent aucune ressource externe riche (lexiques, corpus annotés) et sont uniquement fondées sur le contenu textuel des tweets (et d'autres tweets pour la dernière approche). Cela nous permet d'évaluer l'intérêt de chacune de ces méthodes, mais aussi des représentations qu'elles exploitent, à savoir les sacs-de-mots pour la première, les n-grams pour la deuxième et le plongement de mots (word embedding) pour les réseaux neuronaux.

National audience; Le XXe Siècle a été le théâtre d’importantes mutations en matière de développement urbain. A la ville pédestre, millénaire, aura succédé sur un temps très court la ville étendue à ses faubourgs desservis par les transports en commun, puis la ville périurbaine, diffuse, parfois lointaine et zonée fonctionnellement, autorisée particulièrement par la démocratisation de l’automobile (Mumford, 1964 ; Wiel, 1999). Ville et mobilité faisant système, les révolutions récentes de l’offre de mobilité ont bouleversé les formes du développement urbain, consacrant notamment la dépendance automobile (Dupuy, 1999).

National audience; Étudier et comprendre les processus de changement d’occupation du sol en général, quel qu’en soit le contexte présente une base nécessaire à l’appréhension des divers champs de recherche (changement climatique, imperméabilisation des sols, préservation des écosystèmes, aménagement urbain,mobilité résidentielle et quotidienne, qualité du cadre vie, etc). Le développement urbain est un point particulier qui attire l’attention par les enjeux qu’il représente(socio-économiques, politiques, etc.).

La théorie de la Supersymétrie est étudiée ici en tant que théorie complémentaire au Modèle Standard, sachant que celui-ci n'explique qu'environ 5% de l'univers et est incapable de répondre à plusieurs questions fondamentales en physique des particules. Ce mémoire contient les résultats d'une recherche de Supersymétrie effectuée avec le détecteur ATLAS et utilisant des états finaux contenant entre autres une paire de leptons de même charge électrique ou trois leptons. Les données proviennent de collisions protons-protons à 13 TeV d'énergie dans le centre-de-masse produites au Grand Collisionneur de Hadrons (LHC) en 2015. L'analyse n'a trouvé aucun excès significatif au-delà des attentes du Modèle Standard mais a permis tout de même de poser de nouvelles limites sur la masse de certaines particules supersymétriques. Ce mémoire contient aussi l'étude exhaustive d'un bruit de fond important pour cette analyse, soit le bruit de fond provenant des électrons dont la charge est mal identifiée. L'extraction du taux d'inversion de charge, nécessaire pour connaître combien d'événements seront attribuables à ce bruit de fond, a démontré que la probabilité pour que la charge d'un électron soit mal identifiée par ATLAS variait du dixième de pourcent à 8-9% selon l'impulsion transverse et la pseudorapidité des électrons. Puis, une étude fut effectuée concernant l'élimination de ce bruit de fond via l'identification et la discrimination des électrons dont la charge est mal identifiée. Une analyse multi-variée se servant d'une méthode d'apprentissage par arbres de décision, basée sur les caractéristiques distinctives de ces électrons, montra qu'il était possible de conserver un haut taux d'électrons bien identifiés (95%) tout en rejetant la grande majorité des électrons possédant une charge mal identifiée (90-93%)., Since the Standard Model only explains about 5% of our universe and leaves us with a lot of open questions in fundamental particle physics, a new theory called Supersymmetry is studied as a complementary model to the Standard Model. A search for Supersymmetry with the ATLAS detector and using final states with same-sign leptons or three leptons is presented in this master thesis. The data used for this analysis were produced in 2015 by the Large Hadron Collider (LHC) using proton-proton collisions at 13 TeV of center-of-mass energy. No excess was found above the Standard Model expectations but we were able to set new limits on the mass of some supersymmetric particles. This thesis describes in detail the topic of the electron charge-flip background, which arises when the electric charge of an electron is mis-measured by the ATLAS detector. This is an important background to take into account when searching for Supersymmetry with same-sign leptons. The extraction of charge-flip probabilities, which is needed to determine the number of charge-flip events among our same-sign selection, was performed and found to vary from less than a percent to 8-9% depending on the transverse momentum and the pseudorapidity of the electron. The last part of this thesis consists in a study for the potential of rejection of charge-flip electrons. It was performed by identifying and discriminating those electrons based on a multi-variate analysis with a boosted decision tree method using distinctive properties of charge-flip electrons. It was found that we can reject the wide majority of mis-measured electrons (90-93%) while keeping a very high level of efficiency for well-measured ones (95%).

Automatic face analysis is a key to the development of intelligent human-computer interaction systems and behavior understanding. However, there exist a number of factors that makes face analysis a difficult problem. This include morphological differences between different persons, head pose variations as well as the possibility of partial occlusions. In this PhD, we propose a number of adaptations of the so-called Random Forest algorithm to specifically adress those problems. Mainly, those improvements consist in:– The development of a Pairwise Conditional Random Forest framework, that consists in training Random Forests upon pairs of expressive images. Pairwise trees are conditionned on the expression label of the first frame of a pair to reduce the ongoing expression transition variability. Additionnally, trees can be conditionned upon a head pose estimate to peform facial expression recognition from an arbitrary viewpoint.– The design of a hierarchical autoencoder network to model the local face texture patterns. The reconstruction error of this network provides a confidence measurement that can be used to weight Randomized decision trees trained on spatially-defined local subspace of the face. Thus, we can provide an expression prediction that is robust to partial occlusions.– Improvements over the very recent Neural Decision Forests framework, that include both a simplified training procedure as well as a new greedy evaluation procedure, that allows to dramatically improve the evaluation runtime, with applications for online learning and, deep learning convolutional neural network-based features for facial expression recognition as well as feature point alignement.; L'analyse automatique des expressions faciales est une étape clef pour le développement d'interfaces intelligentes ou l'analyse de comportements. Toutefois, celle-ci est rendue difficile par un grand nombre de facteurs, pouvant être d'ordre morphologiques, liés à l'orientation du visage ou à la présence d'occultations. Nous proposons des adaptations des Random Forest permettant d' adresser ces problématiques:- Le développement des Pairwise Conditional Random Forest, consistant en l'apprentissage de modèles à partir de paires d'images expressives. Les arbres sont de plus conditionnés par rapport à l'expression de la première image afin de réduire la variabilité des transitions. De plus, il est possible de conditionner les arbres en rapport avec une estimation de la pose du visage afin de permettre la reconnaissance quel que soit le point de vue considéré.- L'utilisation de réseaux de neurones auto-associatifs pour modéliser localement l'apparence du visage. Ces réseaux fournissent une mesure de confiance qui peut être utilisée dans le but de pondérer des Random Forests définies sur des sous-espaces locaux du visage. Ce faisant, il est possible de fournir une prédiction d'expression robuste aux occultations partielles du visage.- Des améliorations du récemment proposé algorithme des Neural Decision Forests, lesquelles consistent en une procédure d'apprentissage simplifiée, ainsi qu'en une évaluation "greedy" permettant une évaluation plus rapide, avec des applications liées à l'apprentissage en ligne de représentations profondes pour la reconnaissance des expressions, ainsi que l'alignement de points caractéristiques.

Automatic face analysis is a key to the development of intelligent human-computer interaction systems and behavior understanding. However, there exist a number of factors that makes face analysis a difficult problem. This include morphological differences between different persons, head pose variations as well as the possibility of partial occlusions. In this PhD, we propose a number of adaptations of the so-called Random Forest algorithm to specifically adress those problems. Mainly, those improvements consist in:– The development of a Pairwise Conditional Random Forest framework, that consists in training Random Forests upon pairs of expressive images. Pairwise trees are conditionned on the expression label of the first frame of a pair to reduce the ongoing expression transition variability. Additionnally, trees can be conditionned upon a head pose estimate to peform facial expression recognition from an arbitrary viewpoint.– The design of a hierarchical autoencoder network to model the local face texture patterns. The reconstruction error of this network provides a confidence measurement that can be used to weight Randomized decision trees trained on spatially-defined local subspace of the face. Thus, we can provide an expression prediction that is robust to partial occlusions.– Improvements over the very recent Neural Decision Forests framework, that include both a simplified training procedure as well as a new greedy evaluation procedure, that allows to dramatically improve the evaluation runtime, with applications for online learning and, deep learning convolutional neural network-based features for facial expression recognition as well as feature point alignement.; L'analyse automatique des expressions faciales est une étape clef pour le développement d'interfaces intelligentes ou l'analyse de comportements. Toutefois, celle-ci est rendue difficile par un grand nombre de facteurs, pouvant être d'ordre morphologiques, liés à l'orientation du visage ou à la présence d'occultations. Nous proposons des adaptations des Random Forest permettant d' adresser ces problématiques:- Le développement des Pairwise Conditional Random Forest, consistant en l'apprentissage de modèles à partir de paires d'images expressives. Les arbres sont de plus conditionnés par rapport à l'expression de la première image afin de réduire la variabilité des transitions. De plus, il est possible de conditionner les arbres en rapport avec une estimation de la pose du visage afin de permettre la reconnaissance quel que soit le point de vue considéré.- L'utilisation de réseaux de neurones auto-associatifs pour modéliser localement l'apparence du visage. Ces réseaux fournissent une mesure de confiance qui peut être utilisée dans le but de pondérer des Random Forests définies sur des sous-espaces locaux du visage. Ce faisant, il est possible de fournir une prédiction d'expression robuste aux occultations partielles du visage.- Des améliorations du récemment proposé algorithme des Neural Decision Forests, lesquelles consistent en une procédure d'apprentissage simplifiée, ainsi qu'en une évaluation "greedy" permettant une évaluation plus rapide, avec des applications liées à l'apprentissage en ligne de représentations profondes pour la reconnaissance des expressions, ainsi que l'alignement de points caractéristiques.

This Thesis raises the question of collective decision making under possibilistic uncertainty. We propose several collective qualitative decision rules and show that in the context of a possibilistic representation of uncertainty, the use of an egalitarian pessimistic collective utility function allows us to get rid of the Timing Effect. Making a step further, we prove that if both the agents' preferences and the collective ranking of the decisions satisfy Dubois and Prade's axioms (1995, 1998) and some additional axioms relative to collective choice, in particular Pareto unanimity, then the egalitarian collective aggregation is compulsory. The picture is then completed by the proposition and the characterization of an optimistic counterpart of this pessimistic decision rule. Our axiomatic system can be seen as an ordinal counterpart of Harsanyi's theorem (1955). We prove this result in a formalism that is based on Von NeuMann and Morgenstern framework (1948) and compares possibilisitc lotteries. Besides, we propose a first attempt to provide a characterization of collective qualitative decision rules in Savage's formalism; where decisions are represented by acts rather than by lotteries. From an algorithmic standpoint, we consider strategy optimization in possibilistic decision trees using the decision rules characterized in the first part of this work. So, we provide an adaptation of the Dynamic Programming algorithm for criteria that satisfy the property of monotonicity and propose a Multi-Dynamic programming and a Branch and Bound algorithm for those that are not monotonic. Finally, we provide an empirical comparison of the different algorithms proposed. We measure the execution CPU times that increases linearly according to the size of the tree and it remains affordable in average even for big trees. Then, we study the accuracy percentage of the approximation of the pertinent exact algorithms by Dynamic Programming: It appears that for U-max ante criterion the approximation of Multi-dynamic programming is not so good. Yet, this is not so dramatic since this algorithm is polynomial (and efficient in practice). However, for U+min ante decision rule the approximation by Dynamic Programming is good and we can say that it should be possible to avoid a full Branch and Bound enumeration to find optimal strategies.; Cette Thèse pose la question de la décision collective sous incertitude possibiliste. On propose différents règles de décision collective qualitative et on montre que dans un contexte possibiliste, l'utilisation d'une fonction d'agrégation collective pessimiste égalitariste ne souffre pas du problème du Timing Effect. On étend ensuite les travaux de Dubois et Prade (1995, 1998) relatifs à l'axiomatisation des règles de décision qualitatives (l'utilité pessimiste) au cadre de décision collective et montre que si la décision collective comme les décisions individuelles satisfont les axiomes de Dubois et Prade ainsi que certains axiomes relatifs à la décision collective, particulièrement l'axiome de Pareto unanimité, alors l'agrégation collective égalitariste s'impose. Le tableau est ensuite complété par une axiomatisation d'un pendant optimiste de cette règle de décision collective. Le système axiomatique que nous avons développé peut être vu comme un pendant ordinal du théorème de Harsanyi (1955). Ce résultat á été démontré selon un formalisme qui et basé sur le modèle de de Von NeuMann and Morgenstern (1948) et permet de comparer des loteries possibilistes. Par ailleurs, on propose une première tentative pour la caractérisation des règles de décision collectives qualitatives selon le formalisme de Savage (1972) qui offre une représentation des décisions par des actes au lieu des loteries. De point de vue algorithmique, on considère l'optimisation des stratégies dans les arbres de décision possibilistes en utilisant les critères de décision caractérisés dans la première partie de ce travail. On offre une adaptation de l'algorithme de Programmation Dynamique pour les critères monotones et on propose un algorithme de Programmation Multi-dynamique et un algorithme de Branch and Bound pour les critères qui ne satisfont pas la monotonie. Finalement, on établit une comparaison empirique des différents algorithmes proposés. On mesure les CPU temps d'exécution qui augmentent linéairement en fonction de la taille de l'arbre mais restent abordable même pour des grands arbres. Ensuite, nous étudions le pourcentage d'exactitude de l'approximation des algorithmes exacts par Programmation Dynamique: Il apparaît que pour le critère U-max ante l'approximation de l'algorithme de Programmation Multi-dynamique n'est pas bonne. Mais, ceci n'est pas si dramatique puisque cet algorithme est polynomial (et efficace dans la pratique). Cependant, pour la règle U+min ante l'approximation par Programmation Dynamique est bonne et on peut dire qu'il devrait être possible d'éviter une énumération complète par Branch and Bound pour obtenir les stratégies optimales.

Les petites pathologies buccales touchent environ trois personnes sur quatre chaque année. Elles peuvent se situer au niveau de la muqueuse buccale (aphtes, herpès, perlèches), du parodonte (gingivite, parodontite) ou de l’odonte (carie, coloration dentaire, hypersensibilité dentinaire, poussée dentaire du nourrisson). Elles se manifestent par une gêne et/ou une douleur d’intensité variable. Elles peuvent entrainer des conséquences graves si elles ne sont pas prises en charge à temps, telles qu’un déchaussement définitif des dents pour uneparodontite, ou une septicémie en cas de rage de dents. Le pharmacien d’officine est souvent sollicité, en première intention, avant même le chirurgien dentiste ou le médecin généraliste, pour prendre en charge ce type d’affection. L’importance de son rôle est illustrée par des cas cliniques. Un interrogatoire précis est indispensable pour évaluer le type et le niveau de la pathologie du patient. Si un doute persiste ou si les symptômes relèvent d’une urgence, il est important que le pharmacien sache le réorienter vers son spécialiste. Après avoir écarté ce risque, le pharmacien participe à l’amélioration de la pathologie en conseillant le traitement le plus adapté (allopathie, homéopathie, aromathérapie). Jouant un rôle dans l’éducation thérapeutique du patient, le pharmacien rappelle les règles hygiéno-diététiques à respecter à la fin de son conseil officinal. L’élaboration d’arbres décisionnels pour chaque pathologie buccale couramment rencontrée en officine, est une aide au choix du traitement pour l’équipe officinale.

Este trabajo intenta profundizar en los factores que influyen en la aparición de crisis financieras. Utilizando una amplia muestra de datos de países entre 1981 y 1999, se aplican dos metodologías del campo de la Inteligencia Artificial (la teoría Rough Set y el algoritmo C4.5) para analizar el papel de un conjunto de variables macroeconómicas y financieras (tanto de tipo cualitativo como de tipo cuantitativo) en la explicación de las crisis bancarias. Estos métodos no requieren que las variables o los datos utilizados satisfagan ningún tipo de hipótesis, al contrario que las técnicas estadísticas empleadas tradicionalmente, que presentan el inconveniente de que parten de hipótesis acerca de las propiedades distribucionales de las variables explicativas que no se suelen cumplir, lo que dificulta el análisis. Se han obtenido muy buenos resultados en términos de acierto en la clasificación (80% de clasificaciones correctas sobre una muestra independiente), lo que demuestra la precisión de ambos métodos. This paper tries to further investigate the factors behind a financial crisis. By using a large sample of countries in the period 1981 to 1999, it intends to apply two methods coming from the Artificial Intelligence (Rough Sets theory and C4.5 algorithm) and analyze the role of a set of macroeconomic and financial variables in explaining banking crises. These variables are both quantitative and qualitative. These methods do not require variables or data used to satisfy any assumptions. Statistical methods traditionally employed call for the explicative variables to satisfy statistical assumptions which is quite difficult to happen. This fact complicates the analysis. We obtained good results based on the classification accuracies (80% of correctly classified countries from an independent sample), which proves the suitability of both methods. Ce travail a pour objectif de réaliser une étude approfondie des facteurs produisant l'apparition de crises financières. A partir d'un échantillon important de données de pays entre 1981 et 1999, deux méthodologies sont appliquées dans le domaine de l'Intelligence Artificielle (la théorie Rough Set et l'algorithme C4.5) pour analyser le rôle d'un ensemble de variables macroéconomiques et financières (autant qualitatives que quantitatives) dans l'explication des crises bancaires. Suivant ces méthodes, les variables ou les données utilisées ne doivent pas correspondre à un type d'hypothèse, à l'inverse des techniques statistiques utilisées traditionnellement qui présentent l'inconvénient de partir d'une hypothèse concernant les propriétés de distribution des variables explicatives qui ne sont pas respectées, ce qui rend l'analyse difficile. De très bons résultats ont été obtenus en ce qui concerne la classification (80% de classifications correctes pour un échantillon indépendant), démontrant la précision des deux méthodes. Este trabalho tenta aprofundar sobre os fatores que influem na aparição de crises financeiras. Utilizando uma ampla mostra de dados de países entre 1981 e 1999, aplicam-se duas metodologias do campo da Inteligência Artificial (a teoria Rough Set e o algoritmo C4.5) para analisar o papel de um conjunto de variáveis macroeconômicas e financeiras (tanto de tipo qualitativo como de tipo quantitativo) na explicação das crises bancárias. Estes métodos não requerem que as variáveis ou os dados utilizados satisfaçam nenhum tipo de hipóteses, ao contrario das técnicas estatísticas empregadas tradicionalmente, que apresentam o inconveniente de que partem de hipóteses acerca das propriedades distribucionais das variáveis explicativas que geralmente não se cumprem, o que dificulta a análise. Obteve-se resultados muito bons em termos de acerto na classificação (80% de classificações corretas sobre uma mostra independente), o que demonstra a precisão de ambos os métodos.

National audience; Les yeux sont l'une des caractéristiques les plus saillantes du visage humain. La localisation de la pupille de l'oeil permet d'obtenir des informations importantes qui peuvent être utilisées dans plusieurs applications de vision par ordinateur. Plusieurs eye-trackers commercialisés aujourd'hui peuvent estimer avec précision sa position. Cependant les spécifications matérielles très complexes et l'environnement de l'utilisateur contrôlé (résolution suffisante de l'image de l'oeil, bonnes conditions d'éclairage, légères variations de la pose de la tête) rendent ces solutions impossibles à utiliser dans un environnement arbitraire. Dans cet article, nous présentons une approche basée sur les arbres de régression aléatoires projetés sur l'espace de Hough pour estimer la position de la pupille. Nous démontrons à partir de plusieurs évaluations sur des bases de données publiques références que notre approche est très robuste aux conditions d'éclairage, à l'échelle, aux mouvement des yeux et aux fortes variations de la pose de la tête, et qu'elle apporte une amélioration significative par rapport aux méthodes existantes de l'état de l'art. Eyes are one of the most salient feature of the human face. The location of the eye-pupil allows to access to important informations and can be used in several computer vision applications. Several commercial eye-trackers can estimate with a good accuracy the eye-pupil location, but need a complex hardware specifications with a controlled user environment (sufficient eye image resolution, good illumination, small head pose variations) making these solutions impossible to use on an arbitrary environment. In this paper, we present an approach based on Hough random forest, we demonstrate by several evaluations on challenging public datasets that our approach is very robust to illumination, scale, eye movements and high head pose variations and yields a significant improvement regarding to a wide range of state of the art methods

Face to face interaction is one of the most fundamental forms of human communication. It is a complex multimodal and coupled dynamic system involving not only speech but of numerous segments of the body among which gaze, the orientation of the head, the chest and the body, the facial and brachiomanual movements, etc. The understanding and the modeling of this type of communication is a crucial stage for designing interactive agents capable of committing (hiring) credible conversations with human partners. Concretely, a model of multimodal behavior for interactive social agents faces with the complex task of generating gestural scores given an analysis of the scene and an incremental estimation of the joint objectives aimed during the conversation. The objective of this thesis is to develop models of multimodal behavior that allow artificial agents to engage into a relevant co-verbal communication with a human partner. While the immense majority of the works in the field of human-agent interaction (HAI) is scripted using ruled-based models, our approach relies on the training of statistical models from tracks collected during exemplary interactions, demonstrated by human trainers. In this context, we introduce "sensorimotor" models of behavior, which perform at the same time the recognition of joint cognitive states and the generation of the social signals in an incremental way. In particular, the proposed models of behavior have to estimate the current unit of interaction ( IU) in which the interlocutors are jointly committed and to predict the co-verbal behavior of its human trainer given the behavior of the interlocutor(s). The proposed models are all graphical models, i.e. Hidden Markov Models (HMM) and Dynamic Bayesian Networks (DBN). The models were trained and evaluated - in particular compared with classic classifiers - using datasets collected during two different interactions. Both interactions were carefully designed so as to collect, in a minimum amount of time, a sufficient number of exemplars of mutual attention and multimodal deixis of objects and places. Our contributions are completed by original methods for the interpretation and comparative evaluation of the properties of the proposed models. By comparing the output of the models with the original scores, we show that the HMM, thanks to its properties of sequential modeling, outperforms the simple classifiers in term of performances. The semi-Markovian models (HSMM) further improves the estimation of sensorimotor states thanks to duration modeling. Finally, thanks to a rich structure of dependency between variables learnt from the data, the DBN has the most convincing performances and demonstrates both the best performance and the most faithful multimodal coordination to the original multimodal events., L'interaction face-à-face représente une des formes les plus fondamentales de la communication humaine. C'est un système dynamique multimodal et couplé – impliquant non seulement la parole mais de nombreux segments du corps dont le regard, l'orientation de la tête, du buste et du corps, les gestes faciaux et brachio-manuels, etc – d'une grande complexité. La compréhension et la modélisation de ce type de communication est une étape cruciale dans le processus de la conception des agents interactifs capables d'engager des conversations crédibles avec des partenaires humains. Concrètement, un modèle de comportement multimodal destiné aux agents sociaux interactifs fait face à la tâche complexe de générer un comportement multimodal étant donné une analyse de la scène et une estimation incrémentale des objectifs conjoints visés au cours de la conversation. L'objectif de cette thèse est de développer des modèles de comportement multimodal pour permettre aux agents artificiels de mener une communication co-verbale pertinente avec un partenaire humain. Alors que l'immense majorité des travaux dans le domaine de l'interaction humain-agent repose essentiellement sur des modèles à base de règles, notre approche se base sur la modélisation statistique des interactions sociales à partir de traces collectées lors d'interactions exemplaires, démontrées par des tuteurs humains. Dans ce cadre, nous introduisons des modèles de comportement dits "sensori-moteurs", qui permettent à la fois la reconnaissance des états cognitifs conjoints et la génération des signaux sociaux d'une manière incrémentale. En particulier, les modèles de comportement proposés ont pour objectif d'estimer l'unité d'interaction (IU) dans laquelle sont engagés de manière conjointe les interlocuteurs et de générer le comportement co-verbal du tuteur humain étant donné le comportement observé de son/ses interlocuteur(s). Les modèles proposés sont principalement des modèles probabilistes graphiques qui se basent sur les chaînes de markov cachés (HMM) et les réseaux bayésiens dynamiques (DBN). Les modèles ont été appris et évalués – notamment comparés à des classifieurs classiques – sur des jeux de données collectés lors de deux différentes interactions face-à-face. Les deux interactions ont été soigneusement conçues de manière à collecter, en un minimum de temps, un nombre suffisant d'exemplaires de gestion de l'attention mutuelle et de deixis multimodale d'objets et de lieux. Nos contributions sont complétées par des méthodes originales d'interprétation et d'évaluation des propriétés des modèles proposés. En comparant tous les modèles avec les vraies traces d'interactions, les résultats montrent que le modèle HMM, grâce à ses propriétés de modélisation séquentielle, dépasse les simples classifieurs en terme de performances. Les modèles semi-markoviens (HSMM) ont été également testé et ont abouti à un meilleur bouclage sensori-moteur grâce à leurs propriétés de modélisation des durées des états. Enfin, grâce à une structure de dépendances riche apprise à partir des données, le modèle DBN a les performances les plus probantes et démontre en outre la coordination multimodale la plus fidèle aux évènements multimodaux originaux.

Article dans revue scientifique avec comité de lecture. nationale.; National audience; A bagging ensemble consists of a set of classifiers trained independently and combined by a majority vote. Such a combination improves generalization performance but can require large amounts of memory and computation, a serious drawback for addressing portable real-time pattern recognition applications. We report here a compact three-dimensional multiprecision VLSI implementation of a bagging ensemble. In our circuit, individual classifiers are decision trees implemented as threshold networks -one layer of threshold logic units (TLUs) followed by combinatorial logic functions. The hardware was fabricated using $0.7 \mu m$ CMOS technology and packaged using MCM-V micro-packaging technology. The 3D chip implements up to 192 TLUs operating at a speed of up to 48GCPPS and implemented in a volume of $(w \times L \times h)=(2 \times 2 \times 0.7) cm^3$. The 3D circuit features a high level of programmability and flexibility offering the possibility to make an efficient use of the hardware resources in order to reduce the power consumption. Successful operation of the 3D chip for various precisions and ensemble sizes is demonstrated through an electronic nose application.

National audience; La qualité de l'air intérieur a un impact déterminant sur l'exposition des personnes à des polluants dans le monde moderne du fait que les populations passent beaucoup de leur temps dans différents environnements intérieurs. La société Anaximen développe un objet connecté, appelé Alima, qui mesure toutes les minutes plusieurs paramètres relatifs à la qualité de l'air : température, humidité, concentrations de COV, CO2, formaldéhyde et particules fines (pm). Au-delà de cet aspect de collecte de mesures, Alima inclut des outils d'analyse de données ayant pour but de déterminer les situations d'usages de l'habitation (présence, cuisine, ménage…) afin d'être capable de fournir des conseils à l'utilisateur dans le but d'améliorer cette qualité de l'air. Ce problème est un problème de classification de données dynamiques, et dans cet article, deux outils (réseaux de neurones et arbres de décision) sont testés et comparés pour réaliser cette tâche. Afin d'améliorer les performances du classificateur, les ensembles classificateurs sont également étudiés.

Multipartite ranking is a statistical learning problem that consists in ordering observations that belong to a high dimensional feature space in the same order as the labels, so that the observations with the highest label appear at the top on the list. This work aims to understand the probabilistic nature of the multipartite ranking problem in order to obtain theoretical guaranties for ranking algorithms. In that framework, the output of a ranking algorithm takes the form of a scoring function, a function that maps the space of the observations to the real line which order is induced using the values on the real line. The contributions of this manuscript are the following : first we focus on the characterization of the optimal solutions of multipartite ranking. A new condition on the likelihood ratios is introduced and shown to be necessary and sufficient to make the multipartite ranking well-posed. Then, we look at the criteria to assess the scoring function and propose to use a generalization of the ROC curve named the ROC surface. To be used in applications, the empirical counterpart of the ROC surface is studied and results on its consistency are stated. The second topic of research is the design of algorithms to produce scoring functions. The first procedure is based on the aggregation of scoring functions learnt from bipartite sub-problems. To the aim of aggregating the orders induced by the scoring function, we use a metric approach based on the Kendall- to find a median scoring function. The second procedure is a tree-based recursive method inspired by the TreeRank algorithm that can be viewed as a weighted version of CART. A simple modification is proposed to obtain an approximation of the optimal ROC surface using a piecewise constant scoring function. These procedures are compared to the state of the art algorithms for multipartite ranking using simulated and real data sets. The performances highlight the cases where our procedures are well-adapted, specifically when the dimension of the features space is much larger than the number of labels. Last but not least, we come back to the bipartite ranking problem in order to derive adaptive minimax rates of convergence. These rates are established for classes of distributions controlled by the complexity of the posterior distribution and a low noise condition. The procedure that achieves these rates is based on plug-in estimators of the posterior distribution and an aggregation using exponential weights., Le ranking multipartite est un problème d'apprentissage statistique qui consiste à ordonner les observations qui appartiennent à un espace de grande dimension dans le même ordre que les labels, de sorte que les observations avec le label le plus élevé apparaissent en haut de la liste. Cette thèse vise à comprendre la nature probabiliste du problème de ranking multipartite afin d'obtenir des garanties théoriques pour les algorithmes de ranking. Dans ce cadre, la sortie d'un algorithme de ranking prend la forme d'une fonction de scoring, une fonction qui envoie l'espace des observations sur la droite réelle et l'ordre final est construit en utilisant l'ordre induit par la droite réelle. Les contributions de ce manuscrit sont les suivantes : d'abord, nous nous concentrons sur la caractérisation des solutions optimales de ranking multipartite. Une nouvelle condition sur les rapports de vraisemblance est introduite et jugée nécessaire et suffisante pour rendre le problème de ranking multipartite bien posé. Ensuite, nous examinons les critères pour évaluer la fonction de scoring et on propose d'utiliser une généralisation de la courbe ROC nommée la surface ROC pour cela ainsi que le volume induit par cette surface. Pour être utilisée dans les applications, la contrepartie empirique de la surface ROC est étudiée et les résultats sur sa consistance sont établis. Le deuxième thème de recherche est la conception d'algorithmes pour produire des fonctions de scoring. La première procédure est basée sur l'agrégation des fonctions de scoring apprises sur des sous-problèmes de ranking binaire. Dans le but d'agréger les ordres induits par les fonctions de scoring, nous utilisons une approche métrique basée sur le de Kendall pour trouver une fonction de scoring médiane. La deuxième procédure est une méthode récursive, inspirée par l'algorithme TreeRank qui peut être considéré comme une version pondérée de CART. Une simple modification est proposée pour obtenir une approximation de la surface ROC optimale en utilisant une fonction de scoring constante par morceaux. Ces procédures sont comparées aux algorithmes de l'état de l'art pour le ranking multipartite en utilisant des jeux de données réelles et simulées. Les performances mettent en évidence les cas où nos procédures sont bien adaptées, en particulier lorsque la dimension de l'espace des caractéristiques est beaucoup plus grand que le nombre d'étiquettes. Enfin, nous revenons au problème de ranking binaire afin d'établir des vitesses minimax adaptatives de convergence. Ces vitesses sont montrées pour des classes de distributions contrôlées par la complexité de la distribution a posteriori et une condition de faible bruit. La procédure qui permet d'atteindre ces taux est basée sur des estimateurs de type plug-in de la distribution a posteriori et une méthode d'agrégation utilisant des poids exponentiels.

International audience; Les travaux présentés dans cet article s'inscrivent dans le paradigme des recherches visant à acquérir des relations sémantiques à partir de folksonomies (ensemble de tags attribués à des ressources par des utilisateurs). Nous expérimentons plusieurs approches issues de l'état de l'art ainsi que l'apport de l'apprentissage automatique pour l'identification de relations entre tags. Nous obtenons dans le meilleur des cas un taux d'erreur de 23,7 % (relations non reconnues ou fausses), ce qui est encourageant au vu de la difficulté de la tâche (les annotateurs humains ont un taux de désaccord de 12%).

This research deals with the task of video classification, with a particular focus on action recognition, which is essential for a comprehensive understanding of videos. In the typical scenario, there is a list of semantic categories to be modeled, and example clips are given together with their associated category label, indicating which action of interests happens in that clip. No information is given about where or when the action happens, or why the annotator considered the clip to belong to a sometimes ambiguous category.Within the framework of the bag-of-words representation of videos, we explore how to leverage such weak labels from three points of view: (1) the use of coherent supervision from the earliest stages of the pipeline; (2) the combination of heterogeneous features in nature and scale; and (3) mid-level representations of videos based on regions, so as to increase the ability to discriminate relevant locations in the video. For the quantization of local features, we propose a novel form of supervision to train random forests which explicitly aims at the discriminative power of the resulting bags of words. We show that our forests are better than traditional ones at incorporating contextual elements during quantization, and draw attention to the risk of naive combination of features. We also show that midlevel representations carry complementary information that can improve classification.Moreover, we propose a novel application of video classification to tracking. We show that weak clip labels can be used to classify videos into categories of dynamic models. In this way, we improve tracking by performing classification-based dynamic model selection.; Cette thèse porte sur la classification de vidéos -- étape importante du processus plus complet qu’est la compréhension des vidéos -- en se focalisant sur la reconnaissance d'actions. Nous nous plaçons dans le cas où des modèles des catégories sémantiques à reconnaître sont à construire automatiquement à partir de données d’entrainement. Ces données d’entrainement sont des extraits vidéo auxquelles sont associées une ou des catégories. Aucune information n'est fournie quant à la localisation spatio-temporelle de l'action dans la vidéo, ni quand aux éléments indicatifs de la catégorie qui pourrait être ambigüe.Nous explorons trois manières d'exploiter ces annotations faibles dans le cadre des représentations de vidéos dites « sacs à mots » : (1) une supervision cohérente dès les premières étapes du pipeline, (2) la combinaison d'attributs hétérogènes en nature et en échelle, et (3) des représentations intermédiaires basées sur des régions de sorte à identifier des zones pertinentes dans les vidéos. Pour la quantification de descripteurs locaux, nous proposons une nouvelle fonction objective d’entrainement de forêts aléatoires, qui vise à accroitre explicitement la capacité discriminatoire des sacs de mots obtenus. Nos forêts sont plus robustes dans l’incorporation d’éléments de contexte pendant la quantification, et nous limitons les risques qu'engendre la combinaison naïve d’attributs. Nous montrons que les représentations intermédiaires apportent des informations complémentaires qui améliorent la performance des sacs de mots.De plus, nous proposons une nouvelle application de la classification de vidéos dans le contexte du pistage. Nous montrons que des annotations faibles peuvent être utilisées pour classer des vidéos en types de modèle dynamique. Cette sélection de modèle par classification améliore la qualité du pistage.

Decision trees are popular classification methods. In paper, we extend to multi-class problems a decision tree method based on belief functions previously described for two-class problems only. We propose three possible extensions : combining multiple two-class trees together and directly extending the estimation of belief functions within the tree to the multi-class setting. We provide experiments, results and compare them to usualdecision trees., Les arbres de décision sont des classifieurs très populaires. Dans cet article, nous étendons nous une méthode de construction d'arbres de décision à deux classes, basés sur les fonctions de croyance, au cas multi-classe. Nous proposons pour cela trois extensions possibles : combiner des arbres à deux classes ou étendre directement l'estimation des fonctions de croyance au sein de l'arbre au cadre multi-classe. Des expériences sont effectuées de manìère à comparer ces arbres aux arbres de décision classiques.

Malgré des progrès constants en termes de capacité de calcul, mémoire et quantité de données disponibles, les algorithmes d'apprentissage machine doivent se montrer efficaces dans l'utilisation de ces ressources. La minimisation des coûts est évidemment un facteur important, mais une autre motivation est la recherche de mécanismes d'apprentissage capables de reproduire le comportement d'êtres intelligents. Cette thèse aborde le problème de l'efficacité à travers plusieurs articles traitant d'algorithmes d'apprentissage variés : ce problème est vu non seulement du point de vue de l'efficacité computationnelle (temps de calcul et mémoire utilisés), mais aussi de celui de l'efficacité statistique (nombre d'exemples requis pour accomplir une tâche donnée). Une première contribution apportée par cette thèse est la mise en lumière d'inefficacités statistiques dans des algorithmes existants. Nous montrons ainsi que les arbres de décision généralisent mal pour certains types de tâches (chapitre 3), de même que les algorithmes classiques d'apprentissage semi-supervisé à base de graphe (chapitre 5), chacun étant affecté par une forme particulière de la malédiction de la dimensionalité. Pour une certaine classe de réseaux de neurones, appelés réseaux sommes-produits, nous montrons qu'il peut être exponentiellement moins efficace de représenter certaines fonctions par des réseaux à une seule couche cachée, comparé à des réseaux profonds (chapitre 4). Nos analyses permettent de mieux comprendre certains problèmes intrinsèques liés à ces algorithmes, et d'orienter la recherche dans des directions qui pourraient permettre de les résoudre. Nous identifions également des inefficacités computationnelles dans les algorithmes d'apprentissage semi-supervisé à base de graphe (chapitre 5), et dans l'apprentissage de mélanges de Gaussiennes en présence de valeurs manquantes (chapitre 6). Dans les deux cas, nous proposons de nouveaux algorithmes capables de traiter des ensembles de données significativement plus grands. Les deux derniers chapitres traitent de l'efficacité computationnelle sous un angle différent. Dans le chapitre 7, nous analysons de manière théorique un algorithme existant pour l'apprentissage efficace dans les machines de Boltzmann restreintes (la divergence contrastive), afin de mieux comprendre les raisons qui expliquent le succès de cet algorithme. Finalement, dans le chapitre 8 nous présentons une application de l'apprentissage machine dans le domaine des jeux vidéo, pour laquelle le problème de l'efficacité computationnelle est relié à des considérations d'ingénierie logicielle et matérielle, souvent ignorées en recherche mais ô combien importantes en pratique., Despite constant progress in terms of available computational power, memory and amount of data, machine learning algorithms need to be efficient in how they use them. Although minimizing cost is an obvious major concern, another motivation is to attempt to design algorithms that can learn as efficiently as intelligent species. This thesis tackles the problem of efficient learning through various papers dealing with a wide range of machine learning algorithms: this topic is seen both from the point of view of computational efficiency (processing power and memory required by the algorithms) and of statistical efficiency (n umber of samples necessary to solve a given learning task).The first contribution of this thesis is in shedding light on various statistical inefficiencies in existing algorithms. Indeed, we show that decision trees do not generalize well on tasks with some particular properties (chapter 3), and that a similar flaw affects typical graph-based semi-supervised learning algorithms (chapter 5). This flaw is a form of curse of dimensionality that is specific to each of these algorithms. For a subclass of neural networks, called sum-product networks, we prove that using networks with a single hidden layer can be exponentially less efficient than when using deep networks (chapter 4). Our analyses help better understand some inherent flaws found in these algorithms, and steer research towards approaches that may potentially overcome them. We also exhibit computational inefficiencies in popular graph-based semi-supervised learning algorithms (chapter 5) as well as in the learning of mixtures of Gaussians with missing data (chapter 6). In both cases we propose new algorithms that make it possible to scale to much larger datasets. The last two chapters also deal with computational efficiency, but in different ways. Chapter 7 presents a new view on the contrastive divergence algorithm (which has been used for efficient training of restricted Boltzmann machines). It provides additional insight on the reasons why this algorithm has been so successful. Finally, in chapter 8 we describe an application of machine learning to video games, where computational efficiency is tied to software and hardware engineering constraints which, although often ignored in research papers, are ubiquitous in practice.

This research deals with the task of video classification, with a particular focus on action recognition, which is essential for a comprehensive understanding of videos. In the typical scenario, there is a list of semantic categories to be modeled, and example clips are given together with their associated category label, indicating which action of interests happens in that clip. No information is given about where or when the action happens, or why the annotator considered the clip to belong to a sometimes ambiguous category.Within the framework of the bag-of-words representation of videos, we explore how to leverage such weak labels from three points of view: (1) the use of coherent supervision from the earliest stages of the pipeline; (2) the combination of heterogeneous features in nature and scale; and (3) mid-level representations of videos based on regions, so as to increase the ability to discriminate relevant locations in the video. For the quantization of local features, we propose a novel form of supervision to train random forests which explicitly aims at the discriminative power of the resulting bags of words. We show that our forests are better than traditional ones at incorporating contextual elements during quantization, and draw attention to the risk of naive combination of features. We also show that midlevel representations carry complementary information that can improve classification.Moreover, we propose a novel application of video classification to tracking. We show that weak clip labels can be used to classify videos into categories of dynamic models. In this way, we improve tracking by performing classification-based dynamic model selection., Cette thèse porte sur la classification de vidéos -- étape importante du processus plus complet qu’est la compréhension des vidéos -- en se focalisant sur la reconnaissance d'actions. Nous nous plaçons dans le cas où des modèles des catégories sémantiques à reconnaître sont à construire automatiquement à partir de données d’entrainement. Ces données d’entrainement sont des extraits vidéo auxquelles sont associées une ou des catégories. Aucune information n'est fournie quant à la localisation spatio-temporelle de l'action dans la vidéo, ni quand aux éléments indicatifs de la catégorie qui pourrait être ambigüe.Nous explorons trois manières d'exploiter ces annotations faibles dans le cadre des représentations de vidéos dites « sacs à mots » : (1) une supervision cohérente dès les premières étapes du pipeline, (2) la combinaison d'attributs hétérogènes en nature et en échelle, et (3) des représentations intermédiaires basées sur des régions de sorte à identifier des zones pertinentes dans les vidéos. Pour la quantification de descripteurs locaux, nous proposons une nouvelle fonction objective d’entrainement de forêts aléatoires, qui vise à accroitre explicitement la capacité discriminatoire des sacs de mots obtenus. Nos forêts sont plus robustes dans l’incorporation d’éléments de contexte pendant la quantification, et nous limitons les risques qu'engendre la combinaison naïve d’attributs. Nous montrons que les représentations intermédiaires apportent des informations complémentaires qui améliorent la performance des sacs de mots.De plus, nous proposons une nouvelle application de la classification de vidéos dans le contexte du pistage. Nous montrons que des annotations faibles peuvent être utilisées pour classer des vidéos en types de modèle dynamique. Cette sélection de modèle par classification améliore la qualité du pistage.

Le but de ce travail, étant la conception et réalisation d'un logiciel permettant la modélisation de clients douteux, par l'extraction de connaissances à partir de bases de donnes. Une telle connaissance pourrait être utilisée pour permettre aux décideurs et responsables stratégiques de prendre des décisions dans des situations bien précises ; La problématique est la suivante : Lorsqu'un client se présente, à une société de crédit, pour avoir un prêt, la société de crédit est devant un embarras, surtout pour les clients qu'elle ne connaît pas encore. Va-t-elle accepter cette demande de prêt, ce qui est légitime pour toute banque, en vue d'accroître le profit ? Va-t-elle refuser cette demande pour ne pas risquer de tomber sur de mauvais payeur, dans telle cas, se sera une perte sèche pour la banque ? Pour répondre à ces questions, on propose l'utilisation des techniques de DATAMINING, pour essayer de trouver les informations cachées dans la base de données à l'aide d'algorithmes avancés. Pour extraire de la connaissance à partir de la base de données historisées de la banque. Quelle sera alors la méthode utilisée ?

In this thesis, we are interested in sequential decision problems under uncertainty. These problems concern situations of uncertainty where the decision maker has to make several decisions spread over time (i.e., establish a strategy). This problem is much studied in artificial intelligence, known as planning under uncertainty, because of its several applications in many fields (medical diagnosis, artificial players, autopilot, inventory management, ...). The economist community has provided many decision under uncertainty in order to compare strategies. However, the difficulties associated with their implementation leads in practice to use decision problems. The use of performant criteria is indeed hindered by the lake of efficient algorithms in the computer science literature. The purpose of this thesis is precisely to tackle these algorithms locks by providing algorithms for optimizing these criteria in sequential decision problems.; Dans cette thèse, nous nous intéressons aux problèmes de décision séquentielle dans l'incertain. Ces problèmes concernent les situations d'incertitude dans lesquelles le décideur est amené à prendre plusieurs décisions étalées dans le temps (i.e., établir une stratégie). Cette problématique est bien connue en intelligence artificielle, sous le nom de planification dans l'incertain, et est très étudiée du fait de ses applications multiples dans de nombreux domaines (diagnostic médical, joueurs artificiels, pilotage automatique, gestion de stocks, ...). La communauté des économistes a fournit de nombreux critères de décision permettant de raisonner dans l'incertitude afin de pouvoir comparer des stratégies entreelles. Cependant, les difficultés liées à leur mise en oeuvre conduisent en pratique à utiliser des critères moins performants dans les problèmes de décision séquentielle. L'utilisation des critères performants est en effet freinée par l'absence d'algorithmes efficaces dans la littérature informatique. L'objet de cette thèse est justement de repousser ces verrous algorithmiques en proposant des algorithmes permettant leur application dans des problèmes de décision séquentielle.

In this thesis, we are interested in sequential decision problems under uncertainty. These problems concern situations of uncertainty where the decision maker has to make several decisions spread over time (i.e., establish a strategy). This problem is much studied in artificial intelligence, known as planning under uncertainty, because of its several applications in many fields (medical diagnosis, artificial players, autopilot, inventory management, ...). The economist community has provided many decision under uncertainty in order to compare strategies. However, the difficulties associated with their implementation leads in practice to use decision problems. The use of performant criteria is indeed hindered by the lake of efficient algorithms in the computer science literature. The purpose of this thesis is precisely to tackle these algorithms locks by providing algorithms for optimizing these criteria in sequential decision problems.; Dans cette thèse, nous nous intéressons aux problèmes de décision séquentielle dans l'incertain. Ces problèmes concernent les situations d'incertitude dans lesquelles le décideur est amené à prendre plusieurs décisions étalées dans le temps (i.e., établir une stratégie). Cette problématique est bien connue en intelligence artificielle, sous le nom de planification dans l'incertain, et est très étudiée du fait de ses applications multiples dans de nombreux domaines (diagnostic médical, joueurs artificiels, pilotage automatique, gestion de stocks, ...). La communauté des économistes a fournit de nombreux critères de décision permettant de raisonner dans l'incertitude afin de pouvoir comparer des stratégies entreelles. Cependant, les difficultés liées à leur mise en oeuvre conduisent en pratique à utiliser des critères moins performants dans les problèmes de décision séquentielle. L'utilisation des critères performants est en effet freinée par l'absence d'algorithmes efficaces dans la littérature informatique. L'objet de cette thèse est justement de repousser ces verrous algorithmiques en proposant des algorithmes permettant leur application dans des problèmes de décision séquentielle.

International audience; This paper presents an HMM-based recognizer for the off-line recognition of handwritten words. Word models are the concatenation of context-dependent character models: the trigraphs. Due to the large number of possible context-dependent models to compute, a clustering is applied on each state position, based on decision trees. Our system is shown to perform better than a baseline context independent system, and reaches an accuracy higher than 74% on the publicly available Rimes database.

In this thesis, we are interested in sequential decision problems under uncertainty. These problems concern situations of uncertainty where the decision maker has to make several decisions spread over time (i.e., establish a strategy). This problem is much studied in artificial intelligence, known as planning under uncertainty, because of its several applications in many fields (medical diagnosis, artificial players, autopilot, inventory management, ...). The economist community has provided many decision under uncertainty in order to compare strategies. However, the difficulties associated with their implementation leads in practice to use decision problems. The use of performant criteria is indeed hindered by the lake of efficient algorithms in the computer science literature. The purpose of this thesis is precisely to tackle these algorithms locks by providing algorithms for optimizing these criteria in sequential decision problems., Dans cette thèse, nous nous intéressons aux problèmes de décision séquentielle dans l'incertain. Ces problèmes concernent les situations d'incertitude dans lesquelles le décideur est amené à prendre plusieurs décisions étalées dans le temps (i.e., établir une stratégie). Cette problématique est bien connue en intelligence artificielle, sous le nom de planification dans l'incertain, et est très étudiée du fait de ses applications multiples dans de nombreux domaines (diagnostic médical, joueurs artificiels, pilotage automatique, gestion de stocks, ...). La communauté des économistes a fournit de nombreux critères de décision permettant de raisonner dans l'incertitude afin de pouvoir comparer des stratégies entreelles. Cependant, les difficultés liées à leur mise en oeuvre conduisent en pratique à utiliser des critères moins performants dans les problèmes de décision séquentielle. L'utilisation des critères performants est en effet freinée par l'absence d'algorithmes efficaces dans la littérature informatique. L'objet de cette thèse est justement de repousser ces verrous algorithmiques en proposant des algorithmes permettant leur application dans des problèmes de décision séquentielle.

Une réflexion est en cours au sein de l'association Médecins de Montagne concernant la qualité des pratiques et le niveau d'équipement des plateaux techniques. La luxation d'épaule, qui fait l'objet de peu d'études validées, est emblématique de la traumatologie rencontrée en station. Afin de proposer une prise charge standardisée et adaptée aux différents cabinets de station de la luxation d'épaule antérieure, une enquête de pratiques, sous la forme d'un questionnaire écrit, a été réalisée auprès d'un échantillon de 84 médecins. Les résultats, confrontés aux données de la littérature, permettent de proposer un protocole présenté sous forme d'arbre décisionnel, qui reprend point par point la prise en charge du patient depuis sa chute sur les pistes jusqu'à sa sortie du cabinet médical. Une importance toute particulière est accordée à la précocité du geste de réduction. Certains éléments restent à préciser : technique d'immobilisation, référentiel concernant l'analgésie/sédation en ambulatoire, prise en charge des autres formes anatomiques de luxations d'épaule. La mise en pratique de ce protocole pourrait, après évaluation, contribuer à augmenter un taux de réussite de réduction déjà satisfaisant (92%), mais surtout à améliorer la rapidité et la qualité de la prise en charge, quelque soit le lieu de l'accident, pour un coût moindre qu'en structure hospitalière.

En 2009, la mise en place du guide technique définissant les règles d'évaluation de l'état écologique (Guide technique actualisant les règles d'évaluation de l'état des eaux douces de surface de métropole, MEEDDM 2009)et l'état des lieux initial du plan de gestion 2009-2015 ont montré la nécessité de nouveaux développements de modèles d'extrapolation de l'état écologique.C'est dans ce contexte qu'une collaboration a été initiée avec l'agence Seine-Normandie afin de tester l'apport de l'ajout de nouvelles variables à ces modèles d'aide à la décision. Les résultats de ce travail de modélisation montrent que l'apport des variables de population et de physico-chimie est indispensable pour améliorer la capacité prédictive des modèles d'extrapolation spatiale. Par conséquent, il semble nécessaire de pouvoir intégrer des données complémentaires à l'occupation du sol pour pouvoir produire un modèle d'extrapolation spatiale performant dans le but d'évaluer l'état des masses d'eau non suivies. Il est donc indispensable de pouvoir obtenir des valeurs modélisées de paramètres physico-chimiques en continu sur l'ensemble des masses d'eau. Pour cela, il serait souhaitable de généraliser et d'homogénéiser l'utilisation des modèles de flux (type Seneque ou Pegase) dans les différentes agences de l'eau afin d'avoir un modèle national unique permettant de produire une donnée de qualité égale sur l'ensemble du territoire.

We describe in this thesis an approach to fill missing values in decision trees during the classification phase. This approach is derived from the it ordered attribute trees (OAT) method, proposed by Lobo and Numao in 2000, which builds a decision tree for each attribute and uses these trees to fill the missing attribute values. It is based on the Mutual Information between the attributes and the class. Our approach extends this method by taking the dependence between the attributes into account when constructing the attributes trees, and provides a probability distribution as a result when classifying an incomplete object (instead of the most probable class). We present our approach and we test it on some real databases. We also compare our results with those given by the C4.5 method and OAT. We also propose a k-nearest neighbours algorithm which calculates for each object from the test data its frequency in the learning data. We compare these frequencies with the classification results given by our approach, C4.5 and OAT. Finally, we calculate the complexity of constructing the attribute trees and the complexity of classifying a new instance with missing values using our classification algorithm, C4.5 and OAT., Nous présentons dans cette thèse une approche probabiliste pour déterminer les valeurs manquantes des objets incomplets pendant leur classement dans les arbres de décision. Cette approche est dérivée de la méthode d'apprentissage supervisé appelée Arbres d'Attributs Ordonnées (AAO) proposée par Lobo et Numao en 2000, qui construit un arbre de décision pour chacun des attributs, selon un ordre croissant en fonction de l'Information Mutuelle entre chaque attribut et la classe. Notre approche étend la méthode de Lobo et Numao, d'une part en prenant en compte les dépendances entre les attributs pour la construction des arbres d'attributs, et d'autre part en fournissant un résultat de classement d'un objet incomplet sous la forme d'une distribution de probabilités (au lieu de la classe la plus probable). Nous expliquons notre méthode et nous la testons sur des bases de données réelles. Nous comparons nos résultats avec ceux donnés par la méthode C4.5 et AAO. Nous proposons également un algorithme basé sur la méthode des k plus proches voisins qui calcule pour chaque objet de la base de test sa fréquence dans la base d'apprentissage. Nous comparons ces fréquences avec les résultats de classement données par notre approche, C4.5 et AAO. Finalement, nous calculons la complexité de construction des arbres d'attributs ainsi que la complexité de classement d'un objet incomplet en utilisant notre approche, C4.5 et AAO.

International audience; Dans cet article nous présentons nos travaux sur la paramétrisation des Forêts Aléatoires (RF pour Random Forest), et plus précisément sur la paramétrisation de l'algorithme de référence Forest-RI. Dans cet algorithme, la "quantité" d'aléatoire injectée dans le processus d'induction d'un arbre est contrôlée par un hyperparamètre, noté K, qui joue a priori un rôle important pour construire un classifieur performant de type RF. Jusqu'à présent pourtant, aucune règle de paramétrisation n'a été proposée dans la littérature et seulement certaines valeurs arbitraires de K sont traditionnellement utilisées lorsque Forest-RI est expérimenté, sans justification théorique. Nous présentons donc dans cet article une étude expérimentale sur cet hyperparamètre, qui a pour but de comprendre dans quelle mesure le choix de K agit sur les performances en classification des RF. Nous comparons notamment entre elles les valeurs de K de la littérature à l'aide d'un test statistique de significativité. Nous comparons également ces valeurs à un nouvel algorithme d'induction de RF, appelé Forest-RK, pour lequel la valeur de K est choisie aléatoirement à chaque noeud de l'arbre, et n'est donc plus un hyperparamètre de la procédure d'induction. Nous montrons que quelques unes de ces valeurs particulières de K proposées dans la littérature sont statistiquement proches de l'optimalité sur la majorité des bases de données testées, à l'exception de certaines pour lesquelles elles sont significativement sous-optimales. Pour ces bases en particulier Forest-RK se montre en revanche au moins aussi performant que Forest-RI avec ces valeurs de K. Nous reportons aussi des expérimentations complémentaires qui mettent en évidence le rôle important joué par le caractère discriminant des caractéristiques pour déterminer la valeur optimale de K.

International audience; Dans cet article nous présentons une étude sur une nouvelle famille de méthodes d'Ensembles de Classifieurs, appelée Forêts Aléatoires (RF pour Random Forest). Dans un processus d'induction de forêts aléatoires "traditionnel", un nombre préalablement fixé d'arbres de décision est généré, à l'aide notamment de principes d'apprentissage partiellement aléatoires. Ce type de processus présente deux principaux inconvénients : i) le nombre d'arbres doit être fixé a priori ii) l'interprétabilité et les capacités d'analyse offertes par les classifieurs de type arbres de décisions sont perdues, du fait de l'utilisation de principes de "randomisation" au cours de leur induction. Ces constatations soulèvent alors deux questions : ce type de forêts aléatoires contientelle des arbres de décision qui détériorent les performances de l'ensemble ? Si oui, ces arbres présentent-ils des propriétés particulières qui pourraient expliquer cette perte de performances ? Pour répondre à ces questions, nous abordons cette problématique comme un problème de sélection de classifieurs, et montrons que de meilleurs sous-ensembles d'arbres de décision peuvent être obtenus en utilisant des méthodes sous-optimales de sélection de classifieurs. Les résultats prouvent notamment qu'un algorithme d'induction de forêts aléatoires "classique" n'est pas la meilleure approche pour produire des classifieurs de type forêts aléatoires qui soient performants.

Dimitri Grigoriev has shown that for any family of N vectors in the ddimensionallinear space E = (F2)d, there exists a vector in E which isorthogonal to at least N/3 and at most 2N/3 vectors of the family. Weshow that the range [N/3, 2N/3] can be replaced by the much smaller range[N/2 − √N/2,N/2 + √N/2] and we give an efficient, deterministic parallelalgorithm which finds a vector achieving this bound. The optimality of thebound is also investigated.; Dimitri Grigoriev a montré que pour toute famille de N vecteurs de l’espace vectoriel E = (F2)d de dimension d sur le corps à deux éléments, il existe un vecteur de E orthogonal à au moins N/3 et au plus 2N/3 vecteursde la famille. Nous montrons que l’intervalle [N/3, 2N/3] peut être réduit à[N/2 − √N/2,N/2+ √N/2], étudions l’optimalité de cette borne, et donnons un algorithme parallèle déterministe efficace pour trouver un vecteur dans cet intervalle.

During this PhD thesis, we have studied methods for Knowledge Discovery in Databases (KDD) applied to Geographic Information Systems (GIS). We have improved both classical KDD methods (Data Clustering, Cluster Visualization) and spatial KDD methods linked with spatial analysis methods (Spatial Smoothing, Hot Spot Extraction, Spatial Partitionning). We have worked in GÉOBS, a company expert in spatial data analysis. So our KDD methods have been implemented and tested with data sets provided by GÉOBS in relation with Economic Development, Geomarketing, Risk Analysis, Environnement, Health, etc. This report gives a wide point of view on a range of analysis methods and their related problems. It points up the complementarity between theses methods which can be connected either in a technical way or in a user way. Eventually, this work was very enriching because it has concerned many problems and as many KDD tools.; Le travail effectué durant cette thèse concerne l'étude des méthodes d'Extraction de Connaissances à partir de Données (ECD) dans le cadre des Systèmes d'Information Géographiques (SIG). Nous avons non seulement mis en œuvre et amélioré des méthodes d'ECD classique (Classification de Données, Visualisation de Classifications) mais aussi des méthodes d'ECD spatiales liées à des méthodes d'analyse spatiale (Lissage Spatial, Détermination de Pôles, Sectorisation). Nous avons effectué notre travail de recherche au sein de la société GÉOBS spécialisée dans l'analyse des données géographiques (spatiales), et nous avons donc expérimenté, appliqué et vérifié ces méthodes sur des jeux de données fournis par GÉOBS et liés à des problématiques de Développement Économique, de Géomarketing, d'Analyse de Risque, d'Environnement, de Santé, etc. Ce mémoire offre une vision globale concernant un ensemble de problématiques et de méthodes d'analyse. Il met ainsi en avant la complémentarité des méthodes utilisées qui sont souvent connectées entre elles soit du point de vue technique soit du point de vue de leur utilisation. Finalement, ce fut un travail très enrichissant car il a touché à de nombreuses problématiques et à d'aussi nombreuses méthodes d'extraction de connaissances.