Active Computation Outperforms the
State-of-the-Art Heuristic for Grammatical Inference
Dr. Joshua Bongard
Department of Computer Science
Date: Monday October 23, 2006
Time: 12:20 p.m. - 1:10 p.m.
Location: 367 Votey
Abstract
In this talk I will describe the application of my active learning approach to the problem of grammatical inference, specifically the inference of deterministic finite automata (DFAs). 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. I will 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 my method is more consistent over a wider range of balances. Based on this finding I propose a more general method for generating DFAs to be used in the development of future grammatical inference algorithms.