Bigger is Not Always Better: on the Quality of Hypotheses in Active Automata Learning
Rick Smetsers, Michele Volpato, Frits Vaandrager, Sicco Verwer · International Colloquium on Grammatical Inference · 2014
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 modication 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 ultrametric. Preliminary experimental evidence suggests that our algorithm speeds up learning in practical applications by reducing the number of equivalence queries.