Search

International audience; En suivant les principes du web des données, les fournisseurs de données ont publié desmilliards de triples en format RDF (Bizer et al., 2009; Schmachtenberg et al., 2014). Il estpossible de calculer des statistiques sur ces données en exécutant des requêtes SPARQLd’agrégation ; par exemple le nombre de propriétés par classe (Hasnain et al., 2016), ou en-core la durée de vie moyenne de scientifiques célèbres par pays. Cependant, le traitementdes requêtes d’agrégation sur les serveurs SPARQL public reste difficile. En effet, la duréed’exécution des requêtes d’agrégation dépasse généralement les limites de temps autoriséespar les serveurs SPARQL. On obtient alors des résultats partiels inutilisables dans le cadre derequêtes d’agrégation. (Polleres et al., 2018; Soulet & Suchanek, 2019; Hasnain et al., 2016).Pour surmonter les limitations de quotas, les fournisseurs de données fournissent, en plusdes serveurs SPARQL en ligne, des fichiers de sauvegarde contenant l’ensemble des données.Cependant, la ré-ingestion de milliards de faits RDF sur des ressources locales est extrême-ment coûteuse et pose des problèmes de fraîcheur des données.Récemment, des travaux de recherche ont été menés afin de construire des serveursSPARQL fonctionnant sans limite de temps comme TPF (Verborgh et al., 2016) ou SaGe (Mi-nier et al., 2019). Cependant, dans ces approches, les données à agréger sont d’abord trans-férées du serveur de données à un client intelligent qui effectue le calcul d’agrégation. Larequête d’agrégation termine, mais le transfert de données est prohibitif.Dans (Grall et al., 2020), nous montrons comment il est possible d’étendre un serveurSPARQL préemptif avec un opérateur d’agrégation. Ce résultat est basé sur les propriétés dedécomposition des fonctions d’agrégation. Dans notre approche, le serveur SPARQL préemp-tif est capable de calculer des agrégats partiels côté serveur pendant que le client intelligentcombine ces agrégats partiels de manière incrémentale pour calculer les résultats finaux. Cettestratégie permet de réduire considérablement le trafic réseau lors des calculs d’agrégation.

International audience; Finding Missing Categories in Incomplete Utterances This paper introduces an efficient algorithm (O(n 4)) for finding a missing category in an incomplete utterance by using unification technique as when learning categorial grammars, and dynamic programming as in Cocke-Younger-Kasami algorithm. Using syntax/semantic interface of categorial grammar, this work can be used for deriving possible semantic readings of an incomplete utterance. The paper illustrates the problem with running examples.; Cet article propose un algorithme efficace (en O(n 4)) pour trouver la catégorie d'un mot manquant dans un énoncé incomplet. Notre travail fait appel à l'algorithme d'unification comme lors de l'ap-prentissage des grammaires catégorielles et à la programmation dynamique comme dans l'algorithme Cocke-Younger-Kasami. En utilisant l'interface syntaxique / sémantique des grammaires catégorielles, ce travail peut être utilisé pour dériver les lectures sémantiques possibles d'un énoncé incomplet. Des exemples suivis illustrent notre propos.

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 superheterodyne 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.; L’apprentissage de modèles stochastiques générant des séquences a de nombreuses applications comme 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 représenter entre autres 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 en proposant 1) un élargissement des garanties théoriques pour les modèles compressés et 2) 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. Une application en guerre électronique est aussi proposée pour le séquencement des écoutes du récepteur superhétéordyne.

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 superheterodyne 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., L’apprentissage de modèles stochastiques générant des séquences a de nombreuses applications comme 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 représenter entre autres 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 en proposant 1) un élargissement des garanties théoriques pour les modèles compressés et 2) 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. Une application en guerre électronique est aussi proposée pour le séquencement des écoutes du récepteur superhétéordyne.

Specifying a database query using a formal query language is typically a challenging task for non-expert users. In the context of big data, this problem becomes even harder because it requires the users to deal with database instances of large size and hence difficult to visualize. Such instances usually lack a schema to help the users specify their queries, or have an incomplete schema as they come from disparate data sources. In this thesis, we address the problem of query specification for non-expert users. We identify two possible approaches for tackling this problem: learning queries from examples and translating the data in a format that the user finds easier to query. Our contributions are aligned with these two complementary directions and span over three of the most popular data models: XML, relational, and graph. This thesis consists of two parts, dedicated to (i) schema definition and translation, and to (ii) learning schemas and queries. In the first part, we define schema formalisms for unordered XML and we analyze their computational properties; we also study the complexity of the data exchange problem in the setting of a relational source and a graph target database. In the second part, we investigate the problem of learning from examples the schemas for unordered XML proposed in the first part, as well as relational join queries and path queries on graph databases. The interactive scenario that we propose for these two classes of queries is immediately applicable to assisting non-expert users in the process of query specification.; La spécification de requêtes est généralement une tâche difficile pour les utilisateurs non-experts. Le problème devient encore plus difficile quand les utilisateurs ont besoin d'interroger des bases de données de grande taille et donc difficiles à visualiser. Le schéma pourrait aider à cette spécification, mais celui-ci manque souvent ou est incomplet quand les données viennent de sources hétérogènes. Dans cette thèse, nous abordons le problème de la spécification de requêtes pour les utilisateurs non-experts. Nous identifions deux approches pour attaquer ce problème : apprendre les requêtes à partir d'exemples ou transformer les données dans un format plus facilement interrogeable par l'utilisateur. Nos contributions suivent ces deux directions et concernent trois modèles de données parmi les plus populaires : XML, relationnel et orienté graphe. Cette thèse comprend deux parties, consacrées à (i) la définition et la transformation de schémas, et (ii) l'apprentissage de schémas et de requêtes. Dans la première partie, nous définissons des formalismes de schémas pour les documents XML non-ordonnés et nous analysons leurs propriétés computationnelles; nous étudions également la complexité du problème d'échange de données entre une source relationnelle et une cible orientée graphe. Dans la deuxième partie, nous étudions le problème de l'apprentissage à partir d'exemples pour les schémas XML proposés dans la première partie, ainsi que pour les requêtes de jointures relationnelles et les requêtes de chemins sur les graphes. Nous proposons notamment un scénario interactif qui permet d'aider des utilisateurs non-experts à définir des requêtes dans ces deux classes.

This thesis exposes a practical approach for the automatic reverse engineering of undocumented communication protocols. Current work in the field of automated protocol reverse engineering either infer incomplete protocol specifications or require too many stimulation of the targeted implementation with the risk of being defeated by counter-inference techniques. We propose to tackle these issues by leveraging the semantic of the protocol to improve the quality, the speed and the stealthiness of the inference process. This work covers the two main aspects of the protocol reverse engineering, the inference of its syntactical definition and of its grammatical definition. We propose an open-source tool, called Netzob, that implements our work to help security experts in their work against latest cyber-threats. We claim Netzob is the most advanced published tool that tackles issues related to the reverse engineering and the simulation of undocumented protocols.; Cette thèse propose une approche pratique pour la rétro-conception automatisée de protocoles de communication non-documentés. Les travaux existants dans ce domaine ne permettent qu'un apprentissage incomplet des spécifications ou exigent trop de stimulation de l'implémentation du protocol cible avec le risque d'être vaincu par des techniques de contre-inférence. Cette thèse adresse ces problématiques en s'appuyant sur la sémantique du protocole cible pour améliorer la qualité, la rapidité et la furtivité du processus d'inférence. Nous appliquons cette approche à la rétro-conception des deux principaux aspects de la définition d'un protocole à savoir l'inférence de sa syntaxe et de sa grammaire. Nous proposons un outil open-source, appelé Netzob, qui implémente nos contributions pour aider les experts en sécurité dans leur lutte contre les dernières menaces informatiques. Selons nos recherches, Netzob apparait comme l'outil publié le plus avancé pour la rétro-conception et la simulation de protocoles de communications non-documentés.

This thesis exposes a practical approach for the automatic reverse engineering of undocumented communication protocols. Current work in the field of automated protocol reverse engineering either infer incomplete protocol specifications or require too many stimulation of the targeted implementation with the risk of being defeated by counter-inference techniques. We propose to tackle these issues by leveraging the semantic of the protocol to improve the quality, the speed and the stealthiness of the inference process. This work covers the two main aspects of the protocol reverse engineering, the inference of its syntactical definition and of its grammatical definition. We propose an open-source tool, called Netzob, that implements our work to help security experts in their work against latest cyber-threats. We claim Netzob is the most advanced published tool that tackles issues related to the reverse engineering and the simulation of undocumented protocols., Cette thèse propose une approche pratique pour la rétro-conception automatisée de protocoles de communication non-documentés. Les travaux existants dans ce domaine ne permettent qu'un apprentissage incomplet des spécifications ou exigent trop de stimulation de l'implémentation du protocol cible avec le risque d'être vaincu par des techniques de contre-inférence. Cette thèse adresse ces problématiques en s'appuyant sur la sémantique du protocole cible pour améliorer la qualité, la rapidité et la furtivité du processus d'inférence. Nous appliquons cette approche à la rétro-conception des deux principaux aspects de la définition d'un protocole à savoir l'inférence de sa syntaxe et de sa grammaire. Nous proposons un outil open-source, appelé Netzob, qui implémente nos contributions pour aider les experts en sécurité dans leur lutte contre les dernières menaces informatiques. Selons nos recherches, Netzob apparait comme l'outil publié le plus avancé pour la rétro-conception et la simulation de protocoles de communications non-documentés.

This thesis proposes a new approach to discover signatures of families (and superfamilies) enzymes. At first, given a sample of aligned sequences belonging to the same family, this approach infers context-free grammars characteristic of this family. To do this, new principles of generalization and new classes have been introduced based on substitutability. An algorithm has also been developed for this purpose, which produces a reduced grammar able to retain the structure of examples. In a second step, this manuscript presents a method for classification of a superfamily sequences into families with a formal concept analysis based on alignement sequences allowing detection of new families and the discovery of patterns to improve functional previous signatures., Cette thèse propose une nouvelle approche de découverte de signatures de familles (et superfamilles) d'enzymes. Dans un premier temps, étant donné un échantillon aligné de séquences appartenant à une même famille, cette approche infère des grammaires algébriques caractérisant cette famille. Pour ce faire, de nouveaux principes de généralisation et de nouvelles classes de langages ont été introduites sur la base de la substituabilité locale. Un algorithme a également été développé à cet effet qui produit une grammaire réduite, conservant la structuration des exemples, d'un langage substituable. Dans un second temps, ce manuscrit présente une méthode de classification des séquences d'une superfamille en familles à l'aide d'une analyse de concepts formels basée sur l'alignement des séquences qui permet la détection de nouvelles familles et la découverte des motifs fonctionnels pour améliorer les signatures précédentes.

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 me- chanisms 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 trans- ducers 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.; Le stockage et la gestion de données sont des questions centrales en infor- matique. 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 automati- sables. 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 norma- lisé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 à par- tir 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.

Nowadays, we have become familiar with software interacting with us using natural language (for example in question-answering systems for after-sale services, human-computer interaction or simple discussion bots). These tools have to either react by keyword extraction or, more ambitiously, try to understand the sentence in its context. Though the simplest of these programs only have a set of pre-programmed sentences to react to recognized keywords (these systems include Eliza but also more modern systems like Siri), more sophisticated systems make an effort to understand the structure and the meaning of sentences (these include systems like Watson), allowing them to generate consistent answers, both with respect to the meaning of the sentence (semantics) and with respect to its form (syntax). In this thesis, we focus on syntax and on how to model syntax using categorial grammars. Our goal is to generate syntactically accurate sentences (without the semantic aspect) and to verify that a given sentence belongs to a language - the French language. We note that AB grammars, with the exception of some phenomena like quantification or extraction, are also a good basis for semantic purposes. We cover both grammar extraction from treebanks and parsing using the extracted grammars. On this purpose, we present two extraction methods and test the resulting grammars using standard parsing algorithms. The first method focuses on creating a generalized tree transducer, which transforms syntactic trees into derivation trees corresponding to an AB grammar. Applied on the various French treebanks, the transducer’s output gives us a wide-coverage lexicon and a grammar suitable for parsing. The transducer, even if it differs only slightly from the usual definition of a top-down transducer, offers several new, compact ways to express transduction rules. We currently transduce 92.5% of all sen- tences in the treebanks into derivation trees.For our second method, we use a unification algorithm, guiding it with a preliminary clustering step, which gathers the words according to their context in the sentence. The comparision between the transduced trees and this method gives the promising result of 91.3% of similarity.Finally, we have tested our grammars on sentence analysis with a probabilistic CYK algorithm and a formula assignment step done with a supertagger. The obtained coverage lies between 84.6% and 92.6%, depending on the input corpus. The probabilities, estimated for the type of words and for the rules, enable us to select only the “best” derivation tree. All our software is available for download under GNU GPL licence., De nos jours, il n’est pas rare d’utiliser des logiciels capables d’avoir une conversation, d’interagir avec nous (systèmes questions/réponses pour les SAV, gestion d’interface ou simplement Intelligence Artificielle - IA - de discussion). Ceux-ci doivent comprendre le contexte ou réagir par mot-clefs, mais générer ensuite des réponses cohérentes, aussi bien au niveau du sens de la phrase (sémantique) que de la forme (syntaxe). Si les premières IA se contentaient de phrases toutes faites et réagissaient en fonction de mots-clefs, le processus s’est complexifié avec le temps. Pour améliorer celui-ci, il faut comprendre et étudier la construction des phrases. Nous nous focalisons sur la syntaxe et sa modélisation avec des grammaires catégorielles. L’idée est de pouvoir aussi bien générer des squelettes de phrases syntaxiquement correctes que vérifier l’appartenance d’une phrase à un langage, ici le français (il manque l’aspect sémantique). On note que les grammaires AB peuvent, à l’exception de certains phénomènes comme la quantification et l’extraction, servir de base pour la sémantique en extrayant des λ-termes. Nous couvrons aussi bien l’aspect d’extraction de grammaire à partir de corpus arborés que l’analyse de phrases. Pour ce faire, nous présentons deux méthodes d’extraction et une méthode d’analyse de phrases permettant de tester nos grammaires. La première méthode consiste en la création d’un transducteur d’arbres généralisé, qui transforme les arbres syntaxiques en arbres de dérivation d’une grammaire AB. Appliqué sur les corpus français que nous avons à notre disposition, il permet d’avoir une grammaire assez complète de la langue française, ainsi qu’un vaste lexique. Le transducteur, même s’il s’éloigne peu de la définition usuelle d’un transducteur descendant, a pour particularité d’offrir une nouvelle méthode d’écriture des règles de transduction, permettant une définition compacte de celles-ci. Nous transformons actuellement 92,5% des corpus en arbres de dérivation. Pour notre seconde méthode, nous utilisons un algorithme d’unification en guidant celui-ci avec une étape préliminaire de clustering, qui rassemble les mots en fonction de leur contexte dans la phrase. La comparaison avec les arbres extraits du transducteur donne des résultats encourageants avec 91,3% de similarité. Enfin, nous mettons en place une version probabiliste de l’algorithme CYK pour tester l’efficacité de nos grammaires en analyse de phrases. La couverture obtenue est entre 84,6% et 92,6%, en fonction de l’ensemble de phrases pris en entrée. Les probabilités, appliquées aussi bien sur le type des mots lorsque ceux-ci en ont plusieurs que sur les règles, permettent de sélectionner uniquement le “meilleur” arbre de dérivation.Tous nos logiciels sont disponibles au téléchargement sous licence GNU GPL.

Quand on cherche à situer l'Inférence Grammaticale dans le paysage de la Recherche, on la place volontiers au sein de l'Apprentissage Automatique, qu'on place lui-même volontiers dans le champ de l'Intelligence Artificielle. Ainsi, dans leur livre de référence, Laurent Miclet et Antoine Cornuéjols préfèrent-ils parler d'Apprentissage Artificiel plutôt que d'Apprentissage Automatique, et consacrent-ils un chapitre complet à l'Inférence Grammaticale. C'est l'histoire du Machine Learning qui explique cette hiérarchie. Pourtant, en 2010, elle n'est pas toujours facile à justifier : combien de chercheurs dans le domaine du Machine Learning connaissent-ils le paradigme d'identification à la limite ? Et combien de chercheurs en Inférence Grammaticale maîtrisent-ils la théorie de la régularisation utilisée en optimisation ? Il suffit de suivre des conférences comme ICGI ou ECML pour constater que les communautés sont différentes, tant sur le plan de leurs motivations que sur celui de leurs cultures scientifiques. En outre, lorsqu'on étudie l'histoire des deux domaines, on observe des points de divergence depuis longtemps déjà. D'un autre côté, plusieurs éléments consolident cette hiérarchie. En effet, tous les algorithmes d'identification fournissent in fine des grammaires qui acceptent les données positives et rejettent les données négatives. Donc les grammaires peuvent être vues comme des sortes de classifieurs, et un algorithme d'Inférence Grammaticale comme un apprenant visant à résoudre un problème de classification. De même, le but de l'Inférence Grammaticale Stochastique est d'identifier des distributions de probabilité, et c'est une thématique qu'on retrouve également en Machine Learning. Ainsi, dans ce manuscrit, nous avons choisi d'étudier, à la lumière de nos travaux, les relations entre Inférence Grammaticale et Classification Supervisée.

XML is a generic data description language originally designed for storing, processing and exchanging information on the Internet. It has raised as a standard for database, document or Web communities, and it is used in numerous applications nowadays. The data format processed by the latter is usually specified by an XML schema. This is a meta-description that constrains the structure of XML documents and their data type. Querying documents in order to extract information they contain is an essential task. Node selecting queries are for instance the basis for transforming XML documents. However, most existing tools for defining queries over XML documents require technical skills from the user. In contrast, 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 inference techniques. As regular tree languages, schemas can be easily represented by tree automata. Thus their use is especially appropriate to automata inference algorithms. We have distinguished two of them. 1. The first idea is to force 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. 2. The second idea is that information contained in XML schemas might be useful for tree pruning heuristics. Pruning is necessary when processed documents are pretty large and/or partially annotated. The counterpart is that some regular queries cannot be inferred anymore. We give a characterization of 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 developed system enables to simulate the user behavior when defining a new query. The results of our experiments supports the relevance of our approach. They indeed show that schema-guidance improves the learning process.; XML est un langage générique de description de données destiné à l'origine au stockage, au traitement et à l'échange d'informations sur Internet ; il s'agit aujourd'hui d'un format standard pour les communautés bases de données, documents ou technologies Web, qui est utilisé dans de nombreuses applications. Le format des données traitées par celles-ci est généralement spécifié par un schéma XML. Il s'agit d'une méta-description permettant de contraindre la structure et le type des données des documents XML qui le respectent. Interroger les documents afin d'en extraire des informations est une tâche essentielle en informatique. Les requêtes de sélection de nœuds sont ainsi à la base de la transformation de documents XML. Cependant, la plupart des outils existants pour définir des requêtes sur les documents XML présupposent des connaissances techniques de la part de l'utilisateur. L'induction de requêtes supervisée est au contraire un moyen d'élaborer des tâches d'extraction d'information sans 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 avons distingué deux. 1. La première idée 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 modèle d'automates permettant de représenter les DTD de façon compacte que nous avons introduit. 2. La seconde idée est que les informations contenues dans le schéma peuvent être précieuses pour élaguer les arbres correspondants à des documents annotés. L'élagage est nécessaire lorsque les documents traités sont gros et/ou annotés partiellement. En contrepartie, il n'est plus possible d'inférer toutes les requêtes régulières. Nous donnons une caractérisation de 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. Le système développé permet de simuler le comportement d'un utilisateur lors de la définition d'une nouvelle requête. Les résultats de nos expériences soutiennent la pertinence de notre approche. Ils montrent en effet que l'usage du schéma permet d'améliorer l'apprentissage.

National audience; Nous nous intéressons à la combinaison de méthodes d'apprentissage à base de moindres généralisés et de techniques d'inférence de boules de mots, appliquée à la classification de séquences. Nous montrons que cette intégration n'est pas directe et qu'elle nécessite un travail de compréhension des moindres généralisés et des algorithmes nouveaux pour produire des boules de mots. L'apprenant résultant de cette démarche est ensuite évalué expérimentalement sur des données classiques de l'inférence grammaticale et sur un jeu de données réel. Dans les deux cas, notre approche se montre compétitive avec les meilleurs algorithmes connus.

This thesis shows a new approach out of discovering protein families signatures. Given a sample of (unaligned) sequences belonging to a structural or functional family of proteins, this approach infers non-deterministic automata characterizing the family. A new kind of multiple alignment called PLMA is introduced in order to emphasize the partial and local significant similarities. Given this information, the NFA models are produced by a process stemming from the domain of grammatical inference. The NFA models, presented here under the name of Protomata, are discreet graphical models of strong expressiveness, which distinguishes them from statistical models such as HMM profiles or pattern models like Prosite patterns.The experiments led on various biological families, among which the MIP and the TNF, show a success on real data.; Cette thèse propose une nouvelle approche de découverte de signatures de familles de protéines. Etant donné un échantillon (non-aligné) de séquences appartenant à une famille structurelle ou fonctionnelle de protéines, cette approche infère des automates fini s non déterministes (NFA) caractérisant la famille.Un nouveau type d'alignement multiple nommé PLMA est introduit afin de mettre en valeur les similarités partielles et locales significativement similaires. A partir de ces informations, les modèles de type NFA sont produits par un procédé relevant du domaine de l'inférence grammaticale. Les modèles NFA, présentés ici sous le nom de Protomates, sont des modèles graphiques discrets de forte expressivité, ce qui les distingue des modèles statistiques de type profils HMM ou des motifs de type Prosite.Les expériences menées sur différentes familles biologiques dont les MIP et les TNF, montrent un succès sur des données réelles.

J'ai travaillé sur les problèmes de modélisation du vivant avec l'hypothèse fondamentale qu'il s'agit de machines symboliques et la volonté d'aider le chercheur en biologie à traiter avec le bon niveau d'abstraction ces machines. Le cœur de mes travaux considère les ensembles de séquences que forment les macromolécules du vivant comme des langages formels et cherche à approfondir les concepts nécessaires pour mener à bien leur analyse linguistique. Il faut tout d'abord étudier le contenu lexical des séquences génomiques, son vocabulaire. Au niveau élémentaire, les facteurs répétés fournissent les unités de sens de la séquence. Cependant, la notion naturelle de répétition dans l'ADN est beaucoup plus complexe et nécessite à la fois d'être formalisée et d'être accompagnée d'une algorithmique de recherche spécialisée. J'ai particulièrement développé cet aspect dans l'étude d'éléments génétiques mobiles à l'intérieur d'un génome ou entre deux génomes. J'ai également travaillé sur le niveau syntaxique, ce qui a mené à l'élaboration d'un langage, Logol, qui permet au biologiste de construire un modèle grammatical hypothétique puis de le tester sur des séquences génomiques. Le langage défini autorise en particulier une notion de variable de chaîne avec une face abstraite qui représente la chaîne d'origine et une face concrète pour les différentes instances copies de cette chaîne d'origine. Ce cadre a été validé sur plusieurs problèmes biologiques de recherche de protéines ou d'éléments génétiques, dont la découverte de récepteurs olfactifs chez le chien et la découverte de défensines humaines. Lorsqu'aucun modèle n'est disponible, il faut tenter de l'inférer à partir d'exemples de séquences. J'ai lancé une série de recherches tant théoriques que pratiques sur ce thème. Au niveau théorique, le problème difficile de l'inférence de grammaires algébriques a été abordé à partir d'ordres partiels sur les non-terminaux ou les arbres de dérivation. La classe mieux maîtrisable des langages réguliers a fait l'objet des travaux les plus approfondis, sur une représentation par automates d'états finis. L'inférence devient alors un problème d'optimisation par gestion d'un ensemble de contraintes dynamiques sur les équivalences d'états. Du point de vue pratique, nous avons tout particulièrement étudié ces problèmes d'inférence sur des séquences de protéines, par exemple en étudiant la prédiction de certaines liaisons (ponts disulfures) entre des sites distants sur la séquence. Enfin, je propose à la fin de mon document d'habilitation un projet pour aborder de façon plus transdisciplinaire la modélisation du vivant en tant que machine symbolique. Les questions que pose la biologie, science expérimentale par excellence, s'expriment majoritairement en termes de raisonnement hypothétique. Je propose de mener des recherches en vue de la mise au point d'un assistant d'expérimentation biochimique sur puce sur cultures cellulaires. Le but global est le développement d'un environnement permettant de relier en boucle expérimentation, observations et acquisition de connaissances, en utilisant un système complet de raisonnement automatique (apprentissage abductif et inductif et planification).

In this paper, we present our recent results on the acquistion of the syntax of natural languages, from the point of view of the theory of grammatical inference. Given a class of possible grammars, the objective is to identify, from a set of positive examples, a grammar in the class which produces the examples. The Gold model formalises the learning process and gives stringent criteria of its success: when does there exist an algorithm producing a target grammar ? what kind of structure should the examples have (strings of words, strings of tagged words, trees) ? From a theoretical point of view, our results establish the learnability or the unlearnability of various classes of categorial grammars. From a practical perspective, these results enable the extraction of syntactic information from real data. Finally, we discuss the interest of this approach for modelling child language acquisition and for automated induction of grammars from corpora.; Dans cet article, nous présentons nos résultats récents concernant l'apprentissage de la syntaxe des langues naturelles, en adoptant le point de vue de l'inférence grammaticale symbolique. L'objectif est d'identifier à partir d'exemples, dans une classe de grammaires connue à l'avance, une grammaire particulière qui engendre les dits exemples. Le modèle de Gold fixe les conditions et le critère de réussite d'une telle entreprise : quand un algorithme produisant une grammaire candidate existe-t-il ? quelle structure doivent contenir les exemples : suites de mots, suites de mots étiquetés, arbres d'analyse ? D'un point de vue théorique, nos résultats établissent l'apprenabilité ou la non-apprenabilité de certaines classes de grammaires catégorielles. En pratique, nos résultats permettent aussi d'acquérir automatiquement des ressources syntaxiques à partir de données réelles. Au final, nous discutons de l'intérêt de cette approche pour modéliser l'acquisition de leur langue naturelle par les enfants ainsi que pour construire automatiquement des grammaires électroniques à partir de corpus.

L'objet de ce travail est la modélisation informatique de la capacité d'apprentissage de la syntaxe de leur langue naturelle par les enfants. Une synthèse des connaissances psycho-linguistiques sur la question est donc tout d'abord proposée. Le point de vue adopté pour la modélisation accorde une place privilégiée à la sémantique, qui est supposée acquise avant la syntaxe. Le Principe de compositionnalité, éventuellement adapté, est mis à contribution pour formaliser les liens entre syntaxe et sémantique, et le modèle d'apprentissage ''à la limite'' par exemples positifs de Gold est choisi pour régir les conditions de l'apprentissage. Nous présentons dans ce contexte divers résultats d'apprenabilité de classes de grammaires catégorielles à partir de divers types de données qui véhiculent des informations sémantiques. Nous montrons que, dans tous les cas, la sémantique contribue à spécifier les structures sous-jacentes aux énoncés, et à réduire ainsi l'espace de recherche des algorithmes d'apprentissage.

The main properties of proteins may be determined from their three-dimensional structure. Bridging this ``knowledge gap'' requires automatic methods capable of inferring folds from sequences. Our contribution to this ambitious goal addresses the prediction of particular interactions inside these macro-molecules. The tertiary folds of native proteins are defined by a large number of weak interactions. Proteins are also stabilized covalently by disulfide bonds formed by a pair of cysteine residues in the folded state. We focus on the prediction of these disulfide bonds formed by a pair of cystein residues in the folded state.We propose to tackle with the problem of prediction of interactions between cysteins in the framework, in the first step, of grammatical inference, especially control sets introduced by Y. Takada and, in the second step, of inductive logic programming. A lot of experiments show that grammatical inference algorithms have to be improve to be able to work on protein sequences. On the over hand, we obtain explicit rules of prediction of oxidized state of cysteins which can be easily interpreted by biologists. We propose an heuristic induction algorithm which can be use for different problems. We obtain several rules and we can see that with only 17 rules, more than 90\% of the two data bases we use are covered, which is a very good result given the simplicity of the characterization.; Déterminer la structure 3D des protéines expérimentalement est une tâche très lourde et coûteuse, qui peut s'avérer parfois impossible à réaliser. L'arrivée massive de données provenant des programmes de séquençage à grande échelle impose de passer d'une approche biochimique à une approche bioinformatique, et nécessite en particulier de développer des méthodes de prédiction sur des séquences.Cette thèse propose l'exploration de deux nouvelles pistes pour progresser dans la résolution de prédiction de ponts disulfures dans les protéines. Cette liaison covalente stabilise et contraint fortement la conformation spatiale de la protéine et la connaissance des positions où elle intervient peut réduire considérablement la complexité du problème de la prédiction de la structure 3D. Pour cela, nous utilisons dans un premier temps, l'inférence grammaticale et plus particulièrement les langages de contrôle introduit par Y. Takada, puis dans un deuxième temps, la programmation logique inductive.Diverses expériences visent à confronter un cadre théorique d'apprentissage et des algorithmes généraux d'inférence grammaticale régulière à une application pratique de prédiction d'appariements spécifiques au sein d'une séquence protéique. D'autres expérimentations montrent que la programmation logique inductive donne de bons résultats sur la prédiction de l'état oxydé des cystéines en inférant des règles interprétables par les biologistes. Nous proposons un algorithme d'induction heuristique dont l'idée est d'effectuer plusieurs phases d'apprentissage en tenant compte des résultats obtenus aux phases précédentes permettant ainsi de diminuer considérablement la combinatoire dans les espaces d'hypothèses logiques en construisant des règles de plus en plus discriminantes.

This work has addressed the problem of the adaptation of grammatical inference algorithms for the discovery of common properties in a set of proteins. Positive grammatical inference generates a particular grammatical representation which is optimal for this language, i.e. which gathers and organises the specic properties of the words of the given language, from a set of words belonging to a given target language. We used the Taylor diagram, which classies amino acids according to their physico-chemical properties, in order to propose a specic order on groups of amino acids in the form of a lattice. During this work, we also developed an inference algorithm (SDTM) which computes best local alignments between pairs of proteins according to a score based on the order dened by the lattice and on the statistical properties of the given set of proteins. The result of the algorithm is a sequential machine close to a Mealy machine in which the outputs are reduced to accept and reject. The algorithm begins by the construction of the biggest automaton recognising exactly the words of the language. Then, it generalizes the automaton by successively merging some pairs of transitions corresponding to paired amino acids in the selected alignments. Experiments have shown the interest of this combination of pattern discovery and grammatical inference methods.; Durant cette thèse, nous avons travaillé sur l'adaptation des algorithmes d'inférence grammaticale pour la recherche des propriétés communes à un ensemble de protéines. L'inférence grammaticale positive cherche à générer, à partir d'un ensemble de mots appartenant à un langage cible particulier inconnu, une représentation grammaticale qui est "optimale" par rapport à ce langage, c'est-à-dire qui rassemble et organise les particularités des mots du langage. Nous avons utilisé le diagramme de Taylor, qui classe les acides aminés suivant leurs propriétés physico-chimiques, pour construire, sous forme de treillis, un ordre sur les groupes d'acides aminés. Nous avons aussi développé une méthode d'inférence (SDTM) qui calcule les meilleurs alignements locaux entre les paires de protéines suivant un score fondé à la fois sur cet ordre et sur les propriétés statistiques de l'ensemble de protéines donné. Le résultat est une machine séquentielle proche de celle de Mealy avec des sorties réduites à "accepte" et "rejette". L'algorithme commence par construire le plus grand automate reconnaissant exactement les mots du langage et le généralise par fusions successives des paires de transitions correspondant aux acides aminés appariés dans les alignements sélectionnés. Les expérimentations ont montré l'intérêt de cette combinaison de méthodes importées de la découverte de motifs et de l'inférence grammaticale.

Colloque avec actes et comité de lecture. internationale

International audience; Sur le plan théorique, le modèle de Gold semble adapté à l'apprentissage des langues naturelles. Cependant la mise en pratique des algorithmes d'acquisition issus de ce modèle pose de nombreux problèmes. Nous développons dans cet article des résultats obtenus à la suite des travaux de Buszkowski, Penn et Kanazawa, qui ont montré que certaines classes de grammaires catégorielles sont apprenables. L'algorithme d'origine nécessite une grande quantité d'information en entrée pour être efficace. En changeant la nature des informations en entrée, nous proposons un algorithme d'apprentissage de grammaires catégorielles plus réaliste dans la perspective d'applications aux langues naturelles. Cette méthode peut être étendue à certains formalismes grammaticaux lexicalisés, comme les grammaires de liens. L'expérimentation que nous proposons avec ce formalisme tend à montrer la faisabilité de notre approche.

Colloque avec actes et comité de lecture. internationale.; International audience; We define the class of reversible classical categorial grammars, similar in the spirit to the notion of reversible class of languages introduced by Angluin and Sakkakibara. We show that the class of reversible classical categorial grammars is identifiable from positive structured examples. For this, we provide an original algorithm, which runs in quadratic time in the size of the examples. This work extends the previous results of Kanazawa. Indeed, in our work, several types can be associated to a word and the class is still identifiable in polynomial time. We illustrate the relevance of the class of reversible classical categorial grammars with linguistic examples.

Colloque avec actes et comité de lecture. internationale.; International audience; We investigate learning dependency grammar from partial data and membership queries as a model of natural language acquisition. We define a learning paradigm based on a dialogue between the learner and a referent who knows the target language. This dialogue consists in a presentation of structured by the learner. We define an efficient algorithm corresponding to this paradigm and illustrate it on examples.

We investigate regular tree languages’ exact learning from positive examples and membership queries. Input data are trees of the language to infer. The learner computes new trees from the inputs and asks the oracle whether or not they belong to the language. From the answers, the learner may ask further membership queries until he finds the correct grammar that generates the target language. This paradigm was introduced by Angluin in the seminal work [D. Angluin, A note on the number of queries needed to identify regular languages, Information and Control 51 (1981) 76–87] for the case of regular word languages. Neither negative examples, equivalence queries nor counter-examples are allowed in this paradigm.We describe an efficient algorithm which is polynomial in the size of the examples for learning the whole class of regular tree languages. The convergence is ensured when the set of examples contains a representative sample of the language to guess. A finite subset E of a regular tree language L is representative for L if every transition of the minimal tree automaton for L is used at least once for the derivation of an element of the set E.

Colloque avec actes et comité de lecture. nationale.; National audience; Nous présentons Alfa, un algorithme d'apprentissage des grammaires catégorielles. Nous nous intéressons à l'apprentissage à la limite à partir d'exemples positifs et les exemples sont des arbres de dérivations partiellement désetiquetés. Nous montrons qu'Alfa identifie la classe des grammaires catérogielles réversibles, une classe contenant strictement les grammaires rigides. En ce sens, ce résultat constitue une extension de l'algorithme de Kanazawa d'apprentissage des grammaires rigides.

Rapport interne.; We present an efficient learning algorithm IRTL for the class of regular tree languages. IRTL is based on the learner-theacher paradigm and works in quadratic time. The teacher give a characteristic sample of an unknown language L to the learner who tries to construct a minimal automata for L with help of queries. These queries are membership questions to the theacher. We give a proof of his correctness and terminaison and develop a full example.

L'objet de cette étude est l'apprentissage automatique d'une grammaire formelle à partir d'exemples. En particulier, nous nous concentrons sur l'inférence de grammaires régulières. Nous proposons une étude détaillée des bases théoriques et de l'espace de recherche de ce problème. Nous y démontrons des propriétés originales définissant un cadre formel et des contraintes pour la consception de nouveaux algorithmes. Ensuite, nous présentons un éventail d'algorithmes d'inférence en comparant la nature des données qu'ils utilisent, leur critère de généralisation et leur complexité calculatoire. Finalement, nous étudions l'inférence régulière sur base d'une présentation séquentielle des données d'apprentissage. Une extension incrémentale d'un algorithme existant est développée. Nous en démontrons la convergence et la complexité théorique.

Nous nous intéressons dans ce rapport aux possibilités d'application d'outils classiques de modélisation du langage naturel à l'analyse de séquences génomiques. Le problème biologique auquel nous nous sommes attaqués est la modélisation de régions promotrices eucaryotes, dans un but de prédiction et d'explication. Une partie de ce rapport traite de la représentation des sites de fixation, qui jouent un rôle déterminant dans la régulation de l'expression des gènes. L'autre partie concerne la caractérisation des régions promotrices sans connaissances a priori. Plusieurs approches issues du traitement du langage naturel ont été tentées, parmi lesquelles l'inférence grammaticale, les modèles de Markov cachés, les ngrams et multigrams. Les résultats obtenus sur les sites de fixation sont comparables à ceux obtenus avec la méthode communément utilisée en biologie, et nous semblent difficilement exploitables dans un but de caractérisation des régions promotrices, en raison de la complexité des mécanismes biologiques liant ces sites à la régulation. Les résultats concernant la caractérisation des régions promotrices sont probants mais révèlent une première différence fondamentale entre langages naturel et biologique. Alors que les textes en langage naturel sont caractérisés par une grande stabilité des fréquences des différentes combinaisons de lettres, des régions fonctionnellement similaires de l'ADN peuvent être d'une grande diversité quant à leur composition. Nous pensons que la prise en compte de cette variabilité est essentielle pour l'application de modèles de langages à l'ADN. Nous décrivons une première tentative basée sur cette constatation, en adaptant une méthode simple de comparaison des fréquences. Les résultats sont concluants et suggèrent que l'adjonction de telles corrections aux techniques plus sophistiquées existantes, quoique moins directe, puisse être d'un grand intérêt.

This study deals with computer representations of musical knowledge on the basis of two real-scale experiments. The first experiment focusses on knowledge acquisition in ethnography: an expert (the musician), an analyst (the musicologist) and a machine are interacting in a learning situation. Improvisation schemata through which musicians express themselves are identified and formalized with production rules in a formalism derived from generative grammars and pattern languages. A deterministic algorithm is introduced for assessing the membership of arbitrary strings to the langage defined by a given (context-sensitive) grammar. A technique for the inductive inference of regular languages is presented, enabling automatic knowledge acquisition of syntactic and lexical knowledge. The second experiment is part of the design of a computer environment for musical composition. Here the problem is time representation in a discrete structure of “time objects”, more generally the synchronization of parallel processes. A method is outlined for the determination of a structure with incomplete data about the synchronization of its objects. The concept of “sound object” is then formally introduced. An efficient algorithm is proposed for the time-setting of objects in a structure, given the constraints arising from their metric and topological properties., Cette étude traite de la représentation informatique de connaissances en musique, abordée à partir de deux expériences en grandeur réelle. La première est une méthode d'acquisition de connaissances en ethnographie mettant en interaction un expert (le musicien), un analyste (le musicologue) et une machine dans une situation d'apprentissage. Les schémas d'improvisation des musiciens sont identifiés et exprimés à l'aide de règles de production dans un formalisme dérivé des grammaires génératives et des langages de formes. Un algorithme déterministe de test d'appartenance de chaînes arbitraires au langage défini par une grammaire (sensible au contexte) est présenté, ainsi qu'une technique d'inférence inductive de langages réguliers permettant l'acquisition automatique de connaissances lexicales et syntaxiques. La seconde expérience s'insère dans l'élaboration d'un environnement de composition musicale assistée par ordinateur. Le problème est ici la représentation du temps dans une structure discrète d'“objets temporels”, et plus généralement la synchronisation de processus parallèles. Une méthode est proposée pour la détermination d'une structure à partir de données incomplètes sur la synchronisation des objets. La notion d'“objet sonore” est ensuite explicitée formellement. Un algorithme efficace permet l'instanciation des objets sonores affectés à une structure en tenant compte des contraintes liées à leurs propriétés métriques et topologiques.

National audience; Cet exposé présente une méthode générale d'acquisition de connaissances dans un domaine formalisé à l'aide d'automates finis (langages réguliers). A partir d'un échantillon d'exemples le système construit un automate "presque minimal" qui n'est pas nécessairement déterministe. Cette construction peut être contrainte par des connaissances sur la segmentation des exemples que le système peut acquérir en questionnant l'informateur. Dans une deuxième phase, le système généralise l'automate à partir de propriétés connues du langage ou(et) à partir d'hypothèses validées à l'aide d'oracles. Une liste non exhaustive d'heuristiques générales est proposée. La démonstration s'appuie sur un cas réel de modélisation d'apprentissage de schémas d'improvisation musicale.