Document Detail

Learning deterministic finite automata with a smart state labeling evolutionary algorithm.
MedLine Citation:
PMID:  16013754     Owner:  NLM     Status:  MEDLINE    
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 studythe 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.
Simon M Lucas; T Jeff Reynolds
Related Documents :
23493944 - Educational achievement gaps between immigrant and native students in two "new immigrat...
24142834 - Expyriment: a python library for cognitive and neuroscientific experiments.
24292904 - Interactive mobile learning: a pilot study of a new approach for sport science and medi...
23255834 - Social-emotional factors affecting achievement outcomes among disadvantaged students: c...
23493944 - Educational achievement gaps between immigrant and native students in two "new immigrat...
24786024 - Turning down the jezebel decibels.
Publication Detail:
Type:  Comparative Study; Evaluation Studies; Journal Article; Research Support, Non-U.S. Gov't    
Journal Detail:
Title:  IEEE transactions on pattern analysis and machine intelligence     Volume:  27     ISSN:  0162-8828     ISO Abbreviation:  IEEE Trans Pattern Anal Mach Intell     Publication Date:  2005 Jul 
Date Detail:
Created Date:  2005-07-14     Completed Date:  2005-08-11     Revised Date:  2006-11-15    
Medline Journal Info:
Nlm Unique ID:  9885960     Medline TA:  IEEE Trans Pattern Anal Mach Intell     Country:  United States    
Other Details:
Languages:  eng     Pagination:  1063-74     Citation Subset:  IM    
Department of Computer Science, University of Essex, Wivenhoe Park, Colchester, Essex C04 35Q, UK.
Export Citation:
APA/MLA Format     Download EndNote     Download BibTex
MeSH Terms
Artificial Intelligence*
Cluster Analysis
Computer Simulation
Information Storage and Retrieval / methods*
Models, Statistical*
Natural Language Processing
Numerical Analysis, Computer-Assisted
Pattern Recognition, Automated / methods*
Sequence Alignment / methods
Sequence Analysis / methods*
Signal Processing, Computer-Assisted*

From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine

Previous Document:  Grammatical inference in bioinformatics.
Next Document:  Structural semantic interconnections: a knowledge-based approach to word sense disambiguation.