Learning Balls of Strings with Correction Queries

Colin de La Higuera (1) , Leonor Becerra Bonache (2) , Jean-Christophe Janodet (1) , Frédéric Tantini (1)

1 LHC - Laboratoire Hubert Curien
2 Universitat Rovira i Virgili

During the 80's, Dana Angluin developed an active learning paradigm, based on the use of an Oracle, able to answer different sort of queries, of which the best known are the membership and equivalence queries. However, practical evidence tends to show that if the former are often available, this is usually not the case of the latter. To get round this problem, we propose to use a new kind of queries, called correction queries, which we study in the framework of grammatical inference. When a string is submitted to the Oracle, either she validates it if it belongs to the target language, or she proposes a correction, that is to say, a string of the language close to the query w.r.t. the edit distance. Then we introduce a non-standard class of languages, that of topological balls of strings. We show that this class is not learnable in Angluin's MAT model, but that it is learnable with a linear number of correction queries. Finally, we conduct several experiments with an Oracle simulating the behaviour of a human Expert, and show that our algorithm is resistant to approximate answers.

Mots clés: Grammatical Inference; Oracle Learning; Correction Queries; Edit Distance; Balls of Strings

Domaines: Apprentissage [cs.LG]; Informatique et langage [cs.CL]

Colin de La Higuera, Leonor Becerra Bonache, Jean-Christophe Janodet, Frédéric Tantini. Learning Balls of Strings with Correction Queries. 2007. ⟨ujm-00144194⟩