Bigger is Not Always Better: on the Quality of Hypotheses in Active Automata Learning

Rick Smetsers, Michele Volpato, Frits Vaandrager, Sicco Verwer
The 12th International Conference on Grammatical Inference, PMLR 34:167-181, 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 ultrametric. Preliminary experimental evidence suggests that our algorithm speeds up learning in practical applications by reducing the number of equivalence queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v34-smetsers14a, title = {Bigger is Not Always Better: on the Quality of Hypotheses in Active Automata Learning}, author = {Smetsers, Rick and Volpato, Michele and Vaandrager, Frits and Verwer, Sicco}, booktitle = {The 12th International Conference on Grammatical Inference}, pages = {167--181}, year = {2014}, editor = {Clark, Alexander and Kanazawa, Makoto and Yoshinaka, Ryo}, volume = {34}, series = {Proceedings of Machine Learning Research}, address = {Kyoto, Japan}, month = {17--19 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v34/smetsers14a.pdf}, url = {https://proceedings.mlr.press/v34/smetsers14a.html}, 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 ultrametric. Preliminary experimental evidence suggests that our algorithm speeds up learning in practical applications by reducing the number of equivalence queries.} }
Endnote
%0 Conference Paper %T Bigger is Not Always Better: on the Quality of Hypotheses in Active Automata Learning %A Rick Smetsers %A Michele Volpato %A Frits Vaandrager %A Sicco Verwer %B The 12th International Conference on Grammatical Inference %C Proceedings of Machine Learning Research %D 2014 %E Alexander Clark %E Makoto Kanazawa %E Ryo Yoshinaka %F pmlr-v34-smetsers14a %I PMLR %P 167--181 %U https://proceedings.mlr.press/v34/smetsers14a.html %V 34 %X 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 ultrametric. Preliminary experimental evidence suggests that our algorithm speeds up learning in practical applications by reducing the number of equivalence queries.
RIS
TY - CPAPER TI - Bigger is Not Always Better: on the Quality of Hypotheses in Active Automata Learning AU - Rick Smetsers AU - Michele Volpato AU - Frits Vaandrager AU - Sicco Verwer BT - The 12th International Conference on Grammatical Inference DA - 2014/08/30 ED - Alexander Clark ED - Makoto Kanazawa ED - Ryo Yoshinaka ID - pmlr-v34-smetsers14a PB - PMLR DP - Proceedings of Machine Learning Research VL - 34 SP - 167 EP - 181 L1 - http://proceedings.mlr.press/v34/smetsers14a.pdf UR - https://proceedings.mlr.press/v34/smetsers14a.html AB - 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 ultrametric. Preliminary experimental evidence suggests that our algorithm speeds up learning in practical applications by reducing the number of equivalence queries. ER -
APA
Smetsers, R., Volpato, M., Vaandrager, F. & Verwer, S.. (2014). Bigger is Not Always Better: on the Quality of Hypotheses in Active Automata Learning. The 12th International Conference on Grammatical Inference, in Proceedings of Machine Learning Research 34:167-181 Available from https://proceedings.mlr.press/v34/smetsers14a.html.

Related Material