Skip to Main content Skip to Navigation
New interface
Preprints, Working Papers, ...

Learning Balls of Strings with Correction Queries

Abstract : 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.
Complete list of metadata
Contributor : Frédéric Tantini Connect in order to contact the contributor
Submitted on : Wednesday, May 2, 2007 - 11:37:38 AM
Last modification on : Saturday, June 25, 2022 - 10:49:49 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 11:48:17 PM


Files produced by the author(s)


  • HAL Id : ujm-00144194, version 1



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



Record views


Files downloads