Bigger is Not Always Better: on the Quality of Hypotheses in Active Automata Learning
Proceedings of the 12th International Conference of Grammatical Inference
JMLR: Workshop and Conference Proceedings 34:167-181, 2014

2014

Abstract

In Angluin's L* algorithm a learner constructs a sequence of hypotheses in order to learn a regular language. Each hypothesis is consistent with a larger set of observations and is described by a bigger model. From a behavioral perspective, however, a hypothesis is not always better than the previous one, in the sense that the minimal length of a counterexample that distinguishes a hypothesis from the target language may decrease. We present a simple modification of the L* algorithm that ensures that for subsequent hypotheses the minimal length of a counterexample never decreases, which implies that the distance to the target language never increases in a corresponding ustrametric. Preliminary experimental evidence suggests that our algorithm speeds up learning in practical applications by reducing the number of equivalence queries.

PDF

Radboud University
Mercator 1 building
Room 01.02
Toernooiveld 212
6525EC Nijmegen
The Netherlands

Radboud University
Institute for Computing and Information Sciences
Attn. Rick Smetsers
Toernooiveld 212
6525EC Nijmegen
The Netherlands

rick AT cs.ru.nl