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.