Active Coevolutionary Learning of Deterministic Finite Automata Export

@article{citeulike:4216314, 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.}, author = {Bongard, Josh and Lipson, Hod}, citeulike-article-id = {4216314}, citeulike-linkout-0 = {http://www.jmlr.org/papers/volume6/bongard05a/bongard05a.pdf}, journal = {Journal of Machine Learning Research}, keywords = {active\_learning, automata, evolution}, month = {October}, pages = {1651--1678}, posted-at = {2009-03-25 03:28:36}, priority = {2}, title = {Active Coevolutionary Learning of Deterministic Finite Automata}, url = {http://www.jmlr.org/papers/volume6/bongard05a/bongard05a.pdf}, volume = {6}, year = {2005} }

TY - JOUR ID - citeulike:4216314 L3 - citeulike-article-id:4216314 N2 - 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. JF - Journal of Machine Learning Research EP - 1678 TI - Active Coevolutionary Learning of Deterministic Finite Automata VL - 6 SP - 1651 KW - active_learning KW - automata KW - evolution AU - Bongard, Josh AU - Lipson, Hod PY - 2005/10// UR - http://www.jmlr.org/papers/volume6/bongard05a/bongard05a.pdf ER -