La plupart des outils existants pour définir des requêtes de sélection de nœuds sur les documents XML présupposent des connaissances techniques de la part de l'utilisateur. L'induction de requêtes supervisée est un moyen d'élaborer des tâches d'extraction d'information sans ces prérequis. Dans un tel système, une interface graphique permet à l'utilisateur d'annoter des documents qui servent d'exemples. Un algorithme d'apprentissage est alors utilisé pour inférer la requête. Dans cette thèse, nous proposons d'utiliser les connaissances fournies par le schéma XML dans les algorithmes d'induction de requêtes basés sur une technique d'inférence grammaticale. En tant que langages réguliers d'arbres, les schémas peuvent être facilement représentés par des automates d'arbres. Leur utilisation dans des algorithmes d'inférence d'automates apparaît donc particulièrement appropriée. Nous en distinguons deux.- La première est de contraindre la requête inférée à être consistante avec le schéma. Pour cela, nous avons mis au point un test d'inclusion efficace dans les automates d'arbres factorisés déterministes, un nouveau modèle d'automates permettant de représenter les DTD de façon compacte.- La seconde est que les informations contenues dans le schéma peuvent être précieuses pour les heuristiques d'élagage, nécessaires en pratique. Nous caractérisons la classe de requêtes apprenables à partir d'un ensemble d'arbres annotés élagués, à savoir les requêtes stables.Nous avons implémenté et testé nos algorithmes d'induction de requêtes guidée par schéma. Les résultats de nos expériences montrent que l'usage du schéma permet d'améliorer l'apprentissage. / Most existing tools for defining node-selecting queries over XML documents require technical skills from the user. Inductive query learning is a way of designing information extraction tasks without any prior knowledge. In such a system, the user annotates some example documents with a graphical interface. A learning algorithm is then used in order to infer the query.In this thesis, we suggest to use the knowledge provided by XML schemas into query induction algorithms based on grammatical inferencetechniques. As regular tree languages, schemas can be easily represented by tree automata. Thus their use is especially appropriate to automata inference algorithms. We distinguish two of them.- The first idea is to constrain inferred queries to be consistent with the schema. For this purpose, we have designed an efficient inclusion test in deterministic factorized tree automata, a model of automata we have defined in order to represent DTDs in a compact manner.- The second idea is that information contained in XML schemas might be useful for tree pruning heuristics, which are necessary in practice. We characterize the class of queries that can be learned from a sample of pruned annotated trees, namely stable queries.We have implemented and tested our schema-guided query induction algorithms. The results of our experiments show that schema-guidance improves the learning process.

Pendant mes travaux de thèse, j'ai développé et appliqué des méthodes informatiques utilisant des données de réseaux afin d'aider l'analyse des données biologiques à haut-débit. Ma thèse consiste en trois projets : L'identification de protéines supplémentaires dans des approches de protéomique différentielle à l'aide des réseaux d'interaction protéiques, l'identification de réseaux régulatoires sous-jacents aux réponses aux stress abiotiques dans arabidopsis thaliana et l'analyse de signature transcriptomique de réponse immunitaire d'hôte spécifique à différentes étapes d'infection par shigella flexneri. / In the course of my Ph.D work, i have developed and applied methods making use of network information to adavance the analysis of high-throughput biological data. My thesis comprises three projects :- The identification of additional proteins in differential protemics using protein interaction networks. In this study, we developed a novel computational approach based on protein-protein interaction networks to identify a list of proteins that might have remained undetected in differential proteomic profiling experiments.- The transcriptional regulatory networks underlying responses to environmental stresses. Based on publicly available data, measuring the response of A. Thaliana to a set of abiotic stresses in a time-resolved manner, we applied two complimentary approaches to derive gene regulatory networks underlying the plant's response to the perceived stresses.- The analysis of transcriptional host immune response signatures specific for distinct stages of infection by shigella flexneri. During their host invasion process, shigella localize to different subcellular niches.

La reconstruction des réseaux de régulation génétique (GRNs) est une étape importante pour la compréhension des mécanismes de régulation complexes régissant le fonctionnement de la cellule. De nombreuses approches de modélisation ont été introduites pour inférer le lien de causalité entre les gênes à l'aide des données d'expression génétiques. Cependant, les performances de ces approches sont limitées principalement a causé a des données de grande dimension. En plus, ces méthodes ne restent pas généralement la réalité biologique ou l'interaction entre gêne est réalisée d'une manière coopérative mais considèrent un modèle plus simple ou seules les interactions binaires sont considérées. Dans cette thèse, nous présentons de nouvelles méthodes d'inférence de GRN coopératifs afin améliorer la stabilité et la précision de la reconstruction des GRN en utilisant des techniques d'ensemble. Pour un gêne cible donne, nous extrayons un ensemble de GRNs coopératifs a partir de données discrétisées d'expression. Les GRNs ainsi que les interactions génétiques inférés sont classés selon leur importance en utilisant la régression linéaire sur la base des données d'expression continues. Les évaluations menées sur les données du challenge Dream5 et sur des données humaines de cancer de la vessie démontrent que nos méthodes sont efficaces, tout particulièrement si la taille des données d'apprentissage est petite. / Reconstruction of Gene Regulatory Networks (GRNs) is an important step towards understanding the complex regulatory mechanisms within the cell. Many modeling approaches have been introduced ti find the causal relationship between genes using expression data. However, they surfer from the high dimensionality problem i.e., having a large number of genes but a small number of samples negatively impacts the results. Moreover, these models do not truthfully reflect the biological system where genes interactions are performed in a cooperative manner but rather simplify the problem by tackling only binary interactions. In this thesis, we present new methods for cooperative GRN inference to improve the stability and accuracy of GRNs reconstruction leveraging ensemble methods. For a given target gene, we extract an ensemble of GRNs from discretized expression data. Inferred networks are then evaluated by ranking individual regulation relationships using a regression based technique and continuous expression data. Evaluations on Dream5 challenge data as well as human cancer data demonstrate that our methods are effcient, especially when operating on a small data set.

Cette thèse présente une conception de la rationalité qui évite les idéalisations des capacités cognitives des agents logiques, typiques des conceptions statiques de la rationalité axiomatique dans laquelle un agent n’est rationnel que dans la mesure où il ne se contredit pas et ce, peu importe les capacités cognitives qui lui sont allouées par les axiomes qui énoncent les normes auxquelles il doit se conformer pour être considéré rationnel (comme dans la théorie de la décision ‘standard’ et les systèmes de preuve hilbertien). Afin d’obvier à ces idéalisations, je suggère d’utiliser l’approche dialogique de la logique (Lorenzen) dans la mesure où elle permet de délaisser la logique classique au profit d’une logique plus «faible» et de déployer une conception alternative de la rationalité «non monotone», c’est-à-dire «non cumulative» et dynamique. Dans ce contexte, je discute de la possibilité de procéder à une radicalisation des conditions d’assertabilité de la théorie anti-réaliste de la signification de Dummett qui prenne mieux en compte les actes judicatifs réellement à la portée des agents logique ainsi que les conséquences de cette radicalisation sur le choix de la logique. Sur cette base, je défends une conception de la rationalité des agents en termes de leurs capacités réelles, et non idéalisées, à justifier leurs assertions dans un cadre dialogique. Je suggère finalement de regarder du côté de la théorie de la rationalité «Socratique» de Sellars-Brandom que je compare à l’approche pragmatique de Lorenzen, car toutes les deux visent à rendre explicite ce qui est implicite dans nos jeux de langage, c’est-à-dire d’être capable de justifier ce que nous assertons. / This thesis presents a conception of rationality that steers clear of the problem of the idealization of the logical agent’s abilities, which is typical of static conceptions of axiomatic rationality, where an agent is rational only insofar as he doesn’t contradict himself, with no consideration for the cognitive abilities that are assigned to him by the set of axioms which express the standards to which he has to adhere to be considered as rational (e.g., in "standard" decision theory and in Hilbertian axiomatic proof systems). To avoid those idealizations, I suggest that one adopts the dialogical approach to logic (Lorenzen), because it allows one to abandon classical logic in favour of a "weaker" logic and to develop an alternative conception of rationality which is "non monotonic", i.e., "not cumulative" and "dynamic". I discuss in this context the possibility of proceeding to a radicalization of the assertability conditions of Dummett’s anti-realist meaning theory, in order to provide a better account of the acts of justification that fall within the scope of a real, non-idealized, logical agent, and its implications for the choice of logic. I defend, on this basis, a conception of rationality of logical agents in terms of their real, non-idealized abilities to justify their assertions in a dialogical way. At the end, I suggest that one should look at the Sellars-Brandom’s notion 'Socratic' rationality theory and compare it with Lorenzen’s pragmatic approach, as both aim to make explicit what is implicit in our language-games, that is to prove and to be able to justify what we have asserted.

L’apprentissage de modèles stochastiques générant des séquences a de nombreuses applications en traitement de la parole, du langage ou bien encore en bio-informatique. Les Automates à Multiplicité (MA) sont des modèles graphiques à variables latentes qui englobent une grande variété de systèmes linéaires pouvant en particulier représenter des langues stochastiques, des processus stochastiques ainsi que des processus contrôlés. Les algorithmes traditionnels d’apprentissage comme celui de Baum-Welch sont itératifs, lent et peuvent converger vers des optima locaux. Une alternative récente consiste à utiliser la méthode des moments (MoM) pour concevoir des algorithmes rapides et consistent avec des garanties pseudo-PAC. Cependant, les algorithmes basés sur la MoM ont deux inconvénients principaux. Tout d'abord, les garanties PAC ne sont valides que si la dimension du modèle appris correspond à la dimension du modèle cible. Deuxièmement, bien que les algorithmes basés sur la MoM apprennent une fonction proche de la distribution cible, la plupart ne contraignent pas celle-ci à être une distribution. Ainsi, un modèle appris à partir d’un nombre fini d’exemples peut renvoyer des valeurs négatives et qui ne somment pas à un. Ainsi, cette thèse s’adresse à ces deux problèmes. D’abord, nous proposons un élargissement des garanties théoriques pour les modèles compressés, ainsi qu’un algorithme spectral régularisé qui adapte la taille du modèle aux données. Puis, une application en guerre électronique est aussi proposée pour le séquencement des écoutes du récepteur superhétérodyne. D’autre part, nous dérivons de nouveaux algorithmes d’apprentissage ne souffrant pas du problème des probabilités négatives et dont certains bénéficient de garanties PAC. / Learning stochastic models generating sequences has many applications in natural language processing, speech recognitions or bioinformatics. Multiplicity Automata (MA) are graphical latent variable models that encompass a wide variety of linear systems. In particular, they can model stochastic languages, stochastic processes and controlled processes. Traditional learning algorithms such as the one of Baum-Welch are iterative, slow and may converge to local optima. A recent alternative is to use the Method of Moments (MoM) to design consistent and fast algorithms with pseudo-PAC guarantees. However, MoM-based algorithms have two main disadvantages. First, the PAC guarantees hold only if the size of the learned model corresponds to the size of the target model. Second, although these algorithms learn a function close to the target distribution, most do not ensure it will be a distribution. Thus, a model learned from a finite number of examples may return negative values or values that do not sum to one. This thesis addresses both problems. First, we extend the theoretical guarantees for compressed models, and propose a regularized spectral algorithm that adjusts the size of the model to the data. Then, an application in electronic warfare is proposed to sequence of the dwells of a super-heterodyne receiver. Finally, we design new learning algorithms based on the MoM that do not suffer the problem of negative probabilities. We show for one of them pseudo-PAC guarantees.

Le stockage et la gestion de données sont des questions centrales en informatique. La structuration sous forme d'arbres est devenue la norme (XML, JSON). Pour en assurer la pérennité et l'échange efficace des données, il est nécessaire d'identifier de nouveaux mécanismes de transformations automatisables. Nous nous concentrons sur l'étude de transformations d'arbres en mots représentées par des machines à états finies. Nous définissons les transducteurs séquentiels d'arbres en mots ne pouvant utiliser qu'une et unique fois chaque nœud de l'arbre d'entrée pour décider de la production. En réduisant le problème d'équivalence des transducteurs séquentiels à celui des morphismes appliqués à des grammaires algébriques (Plandowski, 95), nous prouvons qu'il est décidable en temps polynomial. Cette thèse introduit la notion de transducteur travailleur, forme normalisée de transducteurs séquentiels, cherchant à produire la sortie le «plus tôt possible» dans la transduction. A l'aide d'un algorithme de normalisation et de minimisation, nous prouvons qu'il existe un représentant canonique, unique transducteur travailleur minimal, pour chaque transduction de notre classe. La décision de l’existence d’un transducteur séquentiel représentant un échantillon, i.e. paires d'entrées et sorties d'une transformation, est prouvée NP-difficile. Nous proposons un algorithme d'apprentissage produisant à partir d'un échantillon le transducteur canonique le représentant, ou échouant, le tout en restant polynomial. Cet algorithme se base sur des techniques d'inférence grammaticales et sur l'adaptation du théorème de Myhill-Nerode. / Storage, management and sharing of data are central issues in computer science. Structuring data in trees has become a standard (XML, JSON). To ensure preservation and quick exchange of data, one must identify new mechanisms to automatize such transformations. We focus on the study of tree to words transformations represented by finite state machines. We define sequential tree to words transducers, that use each node of the input tree exactly once to produce an output. Using reduction to the equivalence problem of morphisms applied to context-free grammars (Plandowski, 95), we prove that equivalence of sequential transducers is decidable in polynomial time. We introduce the concept of earliest transducer, sequential transducers normal form, which aim to produce output "as soon as possible" during the transduction. Using normalization and minimization algorithms, we prove the existence of a canonical transducer, unique, minimal and earliest, for each transduction of our class. Deciding the existence of a transducer representing a sample, i.e. pairs of input and output of a transformation, is proved NP-hard. Thus, we propose a learning algorithm that generate a canonical transducer from a sample, or fail, while remaining polynomial. This algorithm is based on grammatical inference techniques and the adaptation of a Myhill-Nerode theorem.

Cette thèse traite deux problèmes importants dans le domaine du raisonnement et de la décision dans l'incertain. En premier lieu, nous développons des méthodes d'inférence basées sur la compilation pour les réseaux possibilistes. En effet, nous commençons par adapter au cadre possibiliste l'approche de base proposée, initialement, pour les réseaux Bayésiens et nous la raffinons, ensuite en utilisant la notion de structure locale. Nous proposons aussi une nouvelle stratégie de codage appelée structure locale possibiliste appropriée dans le cadre qualitatif. Nous implémentons, par ailleurs, une méthode purement possibiliste basée sur la transformation des réseaux possibilistes en bases de connaissances possibilistes. Notre deuxième contribution consiste à étendre nos approches d'inférence dans le cadre des réseaux causaux afin de calculer l'effet des observations et des interventions d'une manière efficace. Nous confrontons, en particulier, des approches basées sur la mutilation et celles basées sur l'augmentation. Finalement, nous étudionsl'aspect décisionnel sous compilation en étendant nos résultats portant sur la compilation des réseaux possibilistes afin d'évaluer les diagrammes d'influence possibilistes. Une étude expérimentale évaluant les différentes approches étudiées dans cette thèse est également présentée. / This thesis addresses two important issues in reasoning and decision making under uncertainty. At first, we have developed compilation-based inference methods dedicated to possibilistic networks. In fact, we have adapted the standard approach initially proposed for Bayesian networks into a possibilistic framework and we have refined it using local structure. We havealso proposed a new encoding strategy, called possibilistic local structure, exclusively useful in a qualitative framework. Moreover, we have implemented a purely possibilistic approach based on transforming possibilistic networks into possibilistic knowledge bases. Our second contribution consists in extending our inference approaches to possibilistic causal networks in order to efficiently compute the impact of both observations and interventions. We have confronted, in particular, mutilated-based approaches and augmented-based ones. Finally, we have explored the decision-making aspect under compilation by extending our results on compiling possibilistic networks to efficiently evaluate possibilistic influence diagrams. An experimental study evaluating the different approaches studied in this thesis is also presented.

Les Big Data mettent en évidence tous les défauts du paradigme de l'informatique classique. Au contraire, le Neuro-Inspiré traite les Big Data comme ressources pour progresser. Dans cette thèse, nous adoptons les principes de Hierarchical Temporal Memory (HTM) comme références neuroscientifiques et nous élaborons sur la façon dont le Bayesian Machine Learning (BML) mène les approches dans le Neuro-Inspiré à s’unifier et à atteindre nos objectives: (i) la simplification et l'amélioration des algorithmes de BML et (ii) l'approche au Neuro-Inspiré avec une prospective Ultra-Low-Power. Donc, nous nous efforçons d'apporter le traitement intelligent proche aux sources de données et de populariser le BML sur l'électronique strictement limitées tels que les appareils portables, mettable et implantables. Cependant, les algorithmes de BML ont besoin d’être optimisés. En fait, leur mise en œuvre en HW est ni efficaces, ni réalisables en raison de la mémoire, la puissance de calcul requises. Nous proposons un algorithme moins complexe, en ligne, distribué et non paramétrique et montrons de meilleurs résultats par rapport aux solutions de l’état de l’art. En fait, nous gagnons deux ordres de grandeur de réduction en complexité au niveau algorithmique et un autre ordre de grandeur grâce à des techniques traditionnelles d'optimisation HW. En particulier, nous concevons une preuve de concept sur une plateforme FPGA pour l'analyse en temps réel d’un flux de données. Enfin, nous démontrons d’être en mesure de résumer les ultimes découvertes du domaine du BML sur un algorithme généralement valide qui peut être mis en œuvre en HW et optimisé pour des applications avec des ressources limitées. / Big Data highlights all the flaws of the conventional computing paradigm. Neuro-Inspired computing and other data-centric paradigms rather address Big Data to as resources to progress. In this dissertation, we adopt Hierarchical Temporal Memory (HTM) principles and theory as neuroscientific references and we elaborate on how Bayesian Machine Learning (BML) leads apparently totally different Neuro-Inspired approaches to unify and meet our main objectives: (i) simplifying and enhancing BML algorithms and (ii) approaching Neuro-Inspired computing with an Ultra-Low-Power prospective. In this way, we aim to bring intelligence close to data sources and to popularize BML over strictly constrained electronics such as portable, wearable and implantable devices. Nevertheless, BML algorithms demand for optimizations. In fact, their naïve HW implementation results neither effective nor feasible because of the required memory, computing power and overall complexity. We propose a less complex on-line, distributed nonparametric algorithm and show better results with respect to the state-of-the-art solutions. In fact, we gain two orders of magnitude in complexity reduction with only algorithm level considerations and manipulations. A further order of magnitude in complexity reduction results through traditional HW optimization techniques. In particular, we conceive a proof-of-concept on a FPGA platform for real-time stream analytics. Finally, we demonstrate we are able to summarize the ultimate findings in Machine Learning into a generally valid algorithm that can be implemented in HW and optimized for strictly constrained applications.

Les relations spatiales entre les différentes régions d'une image jouent un rôle important dans les domaines de la reconnaissance des formes, vision par ordinateur, interprétation de scènes et plus particulièrement dans les tâches liées aux domaines des systèmes d'informations géographiques (GIS) et de la navigation autonome des robots mobiles. L'être humain est très habile dans l'estimation et la déduction de l'ensemble de ces relations. Nos déductions restent très précises malgré l'ambiguïté liée à la définition de ces relations. L'objectif de cette thèse est de proposer une méthode d'inférence quantitative des relations spatiales directionnelles. Nous nous sommes intéressés au problème suivant: déduire les relations spatiales entre deux régions A et C connaissant celles qui les relient à une troisième région B. On est confronté à ce genre de problèmes chaque fois qu'on doit chercher notre direction en utilisant un plan, on se positionne par rapport à certains repères pour déduire notre direction. Nous présentons tout d'abord une étude des modèles de représentation quantitative des relations spatiales directionnelles. Ces modèles reposent essentiellement sur la théorie de la logique floue pour quantifier l'ensemble de ces relations. Nous nous sommes inspirés dans la suite de l'un de ces modèles pour définir une nouvelle représentation, celle-ci nous a permis de représenter à la fois l'information angulaire nécessaire pour quantifier les différentes relations spatiales directionnelles et l'information de distance utile pour l'étape de déduction. Dans la plupart des cas, cette information métrique n'est pas disponible ou impossible à déterminer. Alors, on est amené à déduire des nouvelles relations en utilisant uniquement l'information angulaire. Pour étudier ces cas, nous avons utilisé un réseau d'agrégation floue pour déterminer les degrés des quatre relations spatiales directionnelles de base entre deux régions A et C connaissant uniquement les degrés de ces relations entre les deux régions A et B et entre les deux régions B et C. Un algorithme d'apprentissage a été proposé pour déterminer les différents paramètres du réseaux (structures et opérateurs utilisés). Dans le but de justifier les résultats obtenus, nous avons effectué une étude probabiliste du problème d'inférence. Nous avons déterminé la probabilité de trouver un point C dans la direction γ par rapport à un point A étant donné qu'il est placé dans la direction β par rapport à un autre point B, lui même situé dans la direction α par rapport au point A. Cette étude à été effectuée pour différentes distributions de points dans le plan. La probabilité de positionner le point C dans le plan étant donné les deux paramètres α et β a été déterminée pour toute distribution continue des points dans le plan. Vu que la majorité des modèles de représentation des relations reposent sur les relations spatiales entre les différents points des deux objets, ces résultats constituent la base d'une méthode d'inférence probabiliste des relations spatiales directionnelles entre objets.

Le but de ce mémoire est l'étude des méthodes d'analyse de données d'une expérience de microréseau. Nous nous intéressons au problème des tests d'hypothèses multiples, de contrôle de l'erreur de type 1 et de taux de faux positifs. Nous décrivons les techniques de Dudoit et al. (2003), de Hochberg (1988), de Benjamini et Hochberg (1995) et de Westfall et Young (1993) entre autres. Les problèmes des tests d'hypothèses multiples, les mesures différentes de l'erreur du type 1 et le contrôle de telles erreurs sont discutées ici d'après Dudoit et al. (2003). Nous nous intéressons également à la théorie des inégalités de probabilité dues à Dunn (1967), Jogdeo (1970, 1977) et Simes (1986) parce que ces inégalités forment la base de la méthodologie pour contrôler les différentes erreurs de type 1. De plus, une description d'un progiciel informatique pour faire une telle analyse de données de microréseau est aussi présentée, une analyse utilisant une des méthodes de Dudoit et al. (2003) ainsi que des données de Colub et al. (1999) avec les gènes de deux types de leucémie. Nous avons introduit la méthode de «Jackknife» comme un autre contrôle du taux des faux positifs pour cet exemple. Le mémoire termine avec une étude de simulation afin d'illustrer les différences entre les mesures de l'erreur du type 1. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Microréseaux, Génétique, Inférence statistique, Taux d'erreur, Jackknife, Simulations.