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 :
24582334 - A communication skills intervention for community healthcare workers: perceived patient...
23782504 - Action 3:30: protocol for a randomized feasibility trial of a teaching assistant led ex...
24674634 - Program participation and blood pressure improvement in the heart of new ulm project, m...
23870684 - Hgsa dna day essay contest winner 60 years on: still coding for cutting-edge science.
23910924 - Reconceptualization of a doctoral ebp course from in-class to blended format: lessons l...
24356084 - The world report on disability and recent developments in south korea.
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.