@brazovayeye

On Synchronized Evolution of the Network of Automata

. IEEE Transactions on Evolutionary Computation, 6 (2): 147--158 (April 2002)

Abstract

One of the tasks in machine learning is to build a device that predicts each next input symbol of a sequence as it takes one input symbol from the sequence. We studied new approaches to this task. We suggest that deterministic finite automata (DFA) are good building blocks for this device together with genetic algorithms (GAs), which let these automata evolve to predict each next input symbol of the sequence. Moreover, we studied how to combine these highly fit automata so that a network of them would compensate for each others weaknesses and predict better than any single automaton.We studied the simplest approaches to combine automata: building trees of automata with special-purpose automata, which may be called switchboards. These switchboard automata are located on the internal nodes of the tree, take an input symbol from the input sequence just as do other automata, and predict which subtree will make a correct prediction on each next input symbol. GAs again play a crucial role in searching for switchboard automata. We studied various ways of growing trees of automata and tested them on sample input sequences, mainly note pitches, note duration, and up/down notes of Bach s Fugue IX. The test results show that DFAs together with GAs seem to be very effective for this type of pattern learning task.

Links and resources

Tags