Apprentissage des boules de mots avec des requêtes de correction

Résumé : Dans les années 80, Angluin a développé un paradigme d'apprentissage actif basé sur un oracle, capable de répondre à des requêtes d'appartenance et des requêtes d'équivalence. Or, si dans les différentes applications de l'apprentissage actif, les réponses aux premières sont souvent faciles à obtenir, avoir droit aux secondes n'est pas toujours réaliste. Pour contourner cette difficulté, nous proposons un nouveau type de requêtes, appelées requêtes de correction, que l'on étudie ici dans un contexte d'inférence grammaticale. Quand un mot est soumis à l'oracle, ce dernier le valide s'il appartient au langage cible, ou bien propose une correction de ce mot. Une telle correction est un mot du langage qui est proche de la requête (au sens de la distance d'édition). Nous introduisons ensuite une classe non triviale de langages, celle des boules topologiques de mots. Nous montrons que cette classe n'est pas apprenable dans le modèle d'Angluin, mais qu'elle l'est, avec un nombre linéaire de requêtes de correction, voire logarithmique sous certaines hypothèses. Enfin, nous étudions le bon comportement expérimental de nos algorithmes.
Complete list of metadatas

https://hal-ujm.archives-ouvertes.fr/ujm-00161778
Contributor : Frédéric Tantini <>
Submitted on : Wednesday, July 11, 2007 - 3:39:21 PM
Last modification on : Wednesday, July 25, 2018 - 2:05:31 PM

Identifiers

  • HAL Id : ujm-00161778, version 1

Collections

Citation

Leonor Becerra Bonache, Colin de la Higuera, Jean-Christophe Janodet, Frédéric Tantini. Apprentissage des boules de mots avec des requêtes de correction. CAp'07, Jul 2007, France. pp.55-70. ⟨ujm-00161778⟩

Share

Metrics

Record views

76