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.

Inaug.-Diss.--Königl. Christian-Albrechts-Universität zu Kiel. / Cover-title. Literaturverzeichnis: p. [9]-10.

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.

Mémoire (M.Ed.)--Université du Québec à Chicoutimi, 2000. / Document électronique également accessible en format PDF. CaQCU

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.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Nous nous plaçons dans le cadre de l’inférence grammaticale probabiliste. Il s’agit, étant donnée une distribution p sur un ensemble de chaînes S∗ inconnue, d’inférer un modèle probabiliste pour p à partir d’un échantillon fini S d’observations supposé i.i.d. selon p. L’inférence gram- maticale se concentre avant tout sur la structure du modèle, et la convergence de l’estimation des paramètres. Les modèles probabilistes dont il sera question ici sont les automates pondérés, ou WA. Les fonctions qu’ils modélisent sont appelées séries rationnelles. Dans un premier temps, nous étudierons la possibilité de trouver un critère de convergence absolue pour de telles séries. Par la suite, nous introduirons un type d’algorithme pour l’inférence de distributions rationnelles (i.e. distributions modélisées par un WA), basé sur des méthodes spectrales. Nous montrerons comment adapter cet algorithme pour l’appliquer au domaine, assez proche, des distributions sur les arbres. Enfin, nous tenterons d’utiliser cet algorithme d’inférence dans un contexte plus statistique d’estimation de densité. / Our framework is the probabilistic grammatical inference. That is, given an unknown distribution p on a set of string S∗ , to infer a probabilistic model for p from a sample S of observations assumed to be i.i.d. according to p. Grammatical inference focuses primarily on the structure of the probabilistic model, and the convergence of parameter estimate. Probabilistic models which will be considered here are weighted automata, or WA. The series they model are called rational series. Initially, we study the possibility of finding an absolute convergence criterion for such series. Subsequently, we introduce a algorithm for the inference of rational distrbutions (i.e. distributions modeled by WA), based on spectral methods. We will show how to fit this algorithm to the domain, fairly close, of rational distributions on trees. Finally, we will try to see how to use the spectral algorithm in a more statistical way, in a density estimation task.

Cette thèse se place dans le cadre de l'inférence de programmes d'extraction d'information à partir du Web. Elle soutiens les deux idées suivantes: - l'ultilisation de la structure arborescente des documents du Web permet de définir des programmes d'extraction expressifs et efficaces; - les techniques d'inférences grammaticale sur les arbres sont bien adaptées pour l'inférences de programmes d'extraction d'information.

Cette thèse se place dans le cadre de l'inférence de programmes d'extraction d'information à partir du Web. Elle soutiens les deux idées suivantes: - l'ultilisation de la structure arborescente des documents du Web permet de définir des programmes d'extraction expressifs et efficaces; - les techniques d'inférences grammaticale sur les arbres sont bien adaptées pour l'inférences de programmes d'extraction d'information.

Le développement du Web a motivé l’apparition de nombreux types de formats de données semi-structurées pour les problèmes liés aux technologies du Web, comme le traitement des documents ou la gestion de base de données.Nous étudions ici la conversion des données semi-structurées d’un schéma à un autre. Pour le traitement de documents, c’est la technologie XML qui offre la solution la plus puissante à ce problème. En XML, les données semi-structurée sont des arbres de données dont les schémas peuvent être définis par des automates d’arbres avec contraintes sur les valeurs de données. Les transformations de documents sont spécifiées en XSLT, un langage fonctionnel muni de requêtes logiques XPath. Le cœur de XSLT correspond aux transducteurs d’arbres à macros avec navigation par requêtes XPath.Nous proposons de nouveaux algorithmes pour l’apprentissage des transducteurs d’arbres, basés sur des méthodes d’inférence grammaticale. Nous abordons la restriction de schéma, l’anticipation (lookahead), ou la concaténation dans la sortie.1. Nous donnons une forme normale et un algorithme d’apprentissage dans le modèle de Gold avec des ressources limitées pour les transducteurs d’arbres de haut en bas déterministes avec une inspection de domaine régulière.2. Nous montrons comment apprendre des fonctions rationnelles, décrites par les transducteurs de mots déterministes avec anticipation. Nous proposons une nouvelle forme normale qui permet un apprentissage avec des ressources polynomiales.3. Pour les transducteurs arbre-vers-mot linéaires, qui permet la concaténation dans sa sortie, nous présentons une forme normale, et montrons comment décider l’équivalence en temps polynomial. / Since the arrival of the Web, various kinds of semi-structured data formats were introduced in the areas of computer science and technology relevant for the Web, such as document processing, database management, knowledge representation, and information exchange. In this thesis, we study the conversion of semi-structured data from one schema to another.For document processing, the most powerful solutions to this problem were proposed by the XML technology. In the XML format, semi-structured data is restricted to data trees, so that schemas can be defined by tree automata, possibly enhanced by constraints on data values. Document transformations can be defined in XSLT, a purely functional programming language with logical XPath queries. The core of XSLT are macros tree transducers with navigation by XPath queries.We contribute new learning algorithms on tree transducers, that are based on methods from grammatical inference. We address three limitiations of previous approaches: schema restrictions, lookaheads, and concatenation in the output.1. For deterministic top-down tree transducers with regular domain inspection, we show a normal form and a Gold style learning algorithm in with limited resources.2. We show how to learn rational functions, described by deterministic transducers of words with lookahead. We propose a new normal form for such transducers which provides a compromise between lookahead and state minimization, that leads to a learning algorithm in Gold’s learning model with polynomial resources.3. For linear tree-to-word transducers with concatenation in the output, we present a normal form and show how to decide equivalence in polynomial time.