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 metadatas

https://hal-ujm.archives-ouvertes.fr/ujm-00144194
Contributor : Frédéric Tantini <>
Submitted on : Wednesday, May 2, 2007 - 11:37:38 AM
Last modification on : Wednesday, July 25, 2018 - 2:05:30 PM
Long-term archiving on : Tuesday, April 6, 2010 - 11:48:17 PM

Files

bhjt07Long.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ujm-00144194, version 1

Collections

Citation

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

Share

Metrics

Record views

156

Files downloads

155