Learning Balls from Correction Queries
Abstract
Learning in a noisy setting is a very hard task within the field of Grammatical Inference, even if the problem has been addressed for a long time now (de la Higuera, 2005). In this work, we will try to deal with this problem, by learning balls from correction queries. A reasonable way to model noisy data is through the edit distance. But for this distance, language classes from the standard Chomsky hierarchy prove to be quite inadequate. Taking into account these two points, we will try to learn topological balls in the context of query learning. D. Angluin introduced in (Angluin, 1987) the query learning model, which allows the learner to make queries to a teacher about the target language. Although membership queries (MQs) and equivalence queries (EQs) have established themselves as the standard combination to be used, there are real grounds to believe that EQs are too powerful to exist or even be simulated. Based on the growing evidence that corrections are available to children, we propose to work with another kind of query called correction query (CQ). This idea was introduced for the first time in (Becerra- Bonache & Yokomori, 2004). We consider that CQs can play an important role in a noisy context. Thanks to a CQ, data that do not belong to the target concept are corrected. Therefore, in this paper we will explore the relevance of CQs within the Grammatical Inference framework. Since EQs are computationally costly and without correspondence in a real life setting, we will base our study on learning from only CQs or MQs. In that way, we will try to answer the following question: “are CQs more powerful than MQs?”