Learning n-ary Node Selecting Tree Transducers from Completely Annotated Examples

Aurélien Lemay 1 Joachim Niehren 1 Rémi Gilleron 1
1 MOSTRARE - Modeling Tree Structures, Machine Learning, and Information Extraction
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We present the first algorithm for learning n-ary node selection queries in trees from completely annotated examples by methods of grammatical inference. We propose to represent n-ary queries by deterministic n-ary node selecting tree transducers (NSTTs), that are known to capture the class of MSO-definable n-ary queries. Despite of this highly expressive, we show that n-aryy queries, selecting a polynomially bounded number of tuples per tree, represented by deterministic NSTTs can be learned from polynomial time and data while allowing for efficient enumeration of query answers. An application to wrapper induction in Web information extraction yields encouraging results.
Type de document :
Communication dans un congrès
8th International Colloquium on Grammatical Inference, Sep 2006, Tokyo, Japan. Springer Verlag, 4201, pp.253-267, 2006, Lecture Notes in Artificial Intelligence
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00088077
Contributeur : Joachim Niehren <>
Soumis le : dimanche 13 août 2006 - 21:42:21
Dernière modification le : jeudi 11 janvier 2018 - 01:49:33
Document(s) archivé(s) le : lundi 20 septembre 2010 - 16:08:09

Fichier

Identifiants

  • HAL Id : inria-00088077, version 2

Collections

Citation

Aurélien Lemay, Joachim Niehren, Rémi Gilleron. Learning n-ary Node Selecting Tree Transducers from Completely Annotated Examples. 8th International Colloquium on Grammatical Inference, Sep 2006, Tokyo, Japan. Springer Verlag, 4201, pp.253-267, 2006, Lecture Notes in Artificial Intelligence. 〈inria-00088077v2〉

Partager

Métriques

Consultations de la notice

262

Téléchargements de fichiers

192