Back to Search
Start Over
Learning Deterministic Finite Automata with a Smart State Labeling Evolutionary Algorithm.
- Source :
- IEEE Transactions on Pattern Analysis & Machine Intelligence; Jul2005, Vol. 27 Issue 7, p1063-1074, 12p
- Publication Year :
- 2005
-
Abstract
- Learning a Deterministic Finite Automaton (DFA) from a training set of labeled strings is a hard task that has been much studied within the machine learning community. It is equivalent to learning a regular language by example and has applications in language modeling. In this paper, we describe a novel evolutionary method for learning DFA that evolves only the transition matrix and uses a simple deterministic procedure to optimally assign state labels. We compare its performance with the Evidence Driven State Merging (EDSM) algorithm, one of the most powerful known DFA learning algorithms. We present results on random DFA induction problems of varying target size and training set density. We also study the effects of noisy training data on the evolutionary approach and on EDSM. On noise-free data, we find that our evolutionary method outperforms EDSM on small sparse data sets. In the case of noisy training data, we find that our evolutionary method consistently outperforms EDSM, as well as other significant methods submitted to two recent competitions. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 01628828
- Volume :
- 27
- Issue :
- 7
- Database :
- Complementary Index
- Journal :
- IEEE Transactions on Pattern Analysis & Machine Intelligence
- Publication Type :
- Academic Journal
- Accession number :
- 17289420
- Full Text :
- https://doi.org/10.1109/TPAMI.2005.143