Finite-state transducers (FSTs) are finite-state machines (FSMs) that map strings in a source domain into strings in a target domain. While there are many reports in the literature of evolving FSMs, there has been much less work on evolving FSTs. In particular, the fitness functions required for evolving FSTs are generally different from those used for FSMs. In this paper, three string distance-based fitness functions are evaluated, in order of increasing computational complexity: string equality, Hamming distance, and edit distance. The fitness-distance correlation (FDC) and evolutionary performance of each fitness function is analyzed when used within a random mutation hill-climber (RMHC). Edit distance has the strongest FDC and also provides the best evolutionary performance, in that it is more likely to find the target FST within a given number of fitness function evaluations. Edit distance is also the most expensive to compute, but in most cases this extra computation is more than justified by its performance. The RMHC was compared with the best known heuristic method for learning FSTs, the onward subsequential transducer inference algorithm (OSTIA). On noise-free data, the RMHC performs best on problems with sparse training sets and small target machines. The RMHC and OSTIA offer similar performance for large target machines and denser data sets. When noise-corrupted data is used for training, the RMHC still performs well, while OSTIA performs poorly given even small amounts of noise. The RMHC is also shown to outperform a genetic algorithm. Hence, for certain classes of FST induction problem, the RMHC presented in this paper offers the best performance of any known algorithm

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.

Learning deterministic finite automata (DFA) is a hard task that has been much studied within machine learning and evolutionary computation research. This paper presents a new method for evolving DFAs, where only the transition matrix is evolved, and the state labels are chosen to optimize the fit between final states and training set labels. This new procedure reduces the size and in particular, the complexity, of the search space. We present results on the Tomita languages, and also on a set of random DFA induction problems of varying target size and training set density. The Tomita set results show that we can learn the languages with far fewer fitness evaluations than previous evolutionary methods. On the random DFA task we compare our methods with the evidence driven state merging (EDSM) algorithms, which is one of the most powerful known DFA learning algorithms. We show that our method outperforms EDSM when the target DFA is small (less than 32 states) and the training set is sparse.

We have been investigating the possible advantages of a modular/ensemble neural network for acoustic modelling. We report experiments with ensembles of networks trained on data provided by different front-end preprocessing methods. As for previous work we train a network ensemble for each individual phone and combine the outputs of the ensemble using a further trained network. The combined system provides significant improvements for phone recognition and classification on the TIMIT corpus. Our results are now better than the best context-independent systems in the literature and close to the best context-dependent systems.