jmlr jmlr2005 jmlr2005-8 jmlr2005-8-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Josh Bongard, Hod Lipson
Abstract: This paper describes an active learning approach to the problem of grammatical inference, specifically the inference of deterministic finite automata (DFAs). We refer to the algorithm as the estimation-exploration algorithm (EEA). This approach differs from previous passive and active learning approaches to grammatical inference in that training data is actively proposed by the algorithm, rather than passively receiving training data from some external teacher. Here we show that this algorithm outperforms one version of the most powerful set of algorithms for grammatical inference, evidence driven state merging (EDSM), on randomly-generated DFAs. The performance increase is due to the fact that the EDSM algorithm only works well for DFAs with specific balances (percentage of positive labelings), while the EEA is more consistent over a wider range of balances. Based on this finding we propose a more general method for generating DFAs to be used in the development of future grammatical inference algorithms. Keywords: grammatical inference, evolutionary computation, deterministic finite automata, active learning, system identification
D. Angluin. A note on the number of queries needed to identify regular languages. Information and Control, 51:76–87, 1981. D. Angluin. Learning regular sets from queries and counterexamples. Information and Computation, 75:87–106, 1987. D. Angluin. Queries revisited. Theoretical Computer Science, 313:175–194, 2004. Y. Baram, R. E. Yaniv, and K. Luz. Online choice of active learning algorithms. Journal of Machine Learning Research, 5:255–291, 2004. 1676 ACTIVE C OEVOLUTIONARY L EARNING OF D ETERMINISTIC F INITE AUTOMATA T. Berg, B. Jonsson, M. Leucker, and M. Saksena. Insights to Angluin’s learning. Technical Report 2003-039, Uppsala Universitet, 2003. F. Bergadano and D. Gunetti. Inductive Logic Programming: From Machine Learning to Software Engineering. MIT Press, Cambridge, MA, 1995. J. Bongard and H. Lipson. Automated robot function recovery after unanticipated failure or environmental change using a minimum of hardware trials. In Proceedings of the NASA/DoD Conference on Evolvable Hardware, pages 169–176. IEEE Computer Society, 2004a. J. Bongard and H. Lipson. Automating genetic network inference with minimal physical experimentation using coevolution. In Proceedings of the 2004 Genetic and Evolutionary Computation Conference (GECCO), pages 333–345. Springer, 2004b. J. Bongard and H. Lipson. Automating system identification using co-evolution. IEEE Transactions on Evolutionary Computation, 9(4):361–384, 2005. S. Brave. Evolving deterministic finite automata using cellular encoding. In Genetic Programming 96: Proceedings of the First Annual Conference on Genetic Programming, pages 39–44. MIT Press, 1996. O. Cicchello and S. C. Kremer. Inducing grammars from sparse data sets: A survey of algorithms and results. Journal of Machine Learning Research, 4:603–632, 2003. P. Dupont. Incremental regular inference. In L. Miclet and C. Higuera, editors, Proceedings of the Third ICGI-96, Lecture Notes in Artificial Intelligence 1147, pages 222–237, 1996. P. Dupont, L. Miclet, and E. Vidal. What is the search space of the regular inference? In Proceedings of the Second International Colloquium on Grammatical Inference (ICGI’94), pages 25–37, 1994. K. J. Lang, B. A. Pearlmutter, and R. A. Price. Results of the Abbadingo One DFA learning competition and a new evidence-driven state merging algorithm. In Grammatical Inference (Lecture Notes in Artificial Intelligence 1433), pages 1–12. Springer-Verlag, 1992. K. J. Lang, B. A. Pearlmutter, and R. A. Price. Results of the Abbadingo One DFA learning competition and a new evidence-driven state merging algorithm. In V. G. Honavar and G. Slutzki, editors, Proceedings of the Fourth International Colloquium on Grammatical Inference: ICGI 1998, pages 1–12, London, UK, 1998. Springer-Verlag. L. Ljung. System Identification: Theory for the User. Prentice-Hall, Inc., Englewood Cliffs, NJ, 1999. S. M. Lucas and T. J. Reynolds. Learning deterministic finite automata with a smart state labelling evolutionary algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27: 1063–1074, 2005. S. Luke, S. Hamahashi, and H. Kitano. “Genetic” programming. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 1098–1105. Morgan Kaufmann, 13-17 1999. 1677 B ONGARD AND L IPSON S. W. Mahfoud. Niching methods for genetic algorithms. PhD thesis, Urbana, IL, USA, 1995. J. Oncina and P. Garci´ . Inferring regular languages in polynomial update time. In Pattern Recoga nition and Image Analysis, pages 49–61. World Scientific, 1992. T. Pao and J. Carr. A solution of the syntactic induction-inference problem for regular languages. Computer Languages, 3:53–64, 1978. R. G. Parekh and V. G. Honavar. Efficient learning of regular languages using teacher supplied positive examples and learner generated queries. In Proceedings of the Fifth UNB Conference on AI, pages 195–203, 1993. R. G. Parekh and V. G. Honavar. An incremental interactive approach for regular grammar inference. In Proceedings of the Third ICGI-96 (Lecture Notes in Artificial Intelligence 1147), pages 238– 250. Springer Verlag, 1996. L. Pitt. Inductive inference, DFAs and computational complexity. In Proceedings of the International Workshop on Analogical and Inductive Inference (Lecture Notes in Artificial Intelligence 397), pages 18–44. Springer Verlag, 1989. S. Porat and J. Feldman. Learning automata from ordered examples. Machine Learning, 7:109–138, 1991. J. M. Sempere and P. Garcia. A new regular language learning algorithm from lexicographically ordered complete samples. In IEEE Colloquium on Grammatical Inference: Theory, Applications and Alternatives, pages 6/1–6/7, 1993. H. S. Seung, M. Opper, and H. Sompolinsky. Query by committee. In Proceedings of the Fifth Workshop on Computational Learning Theory, pages 387–294, San Mateo, CA, 1992. Morgan Kauffman. M. Tomita. Dynamic construction of finite automata from examples using hill climbing. In V. G. Honavar and G. Slutzki, editors, Proceedings of the Fourth Annual Cognitive Science Conference, pages 105–108, 1982. B. A. Trakhtenbrot and Y. M. Barzdin. Finite Automata Behavior and Synthesis. North-Holland Publishing Company, Amsterdam, 1973. 1678