abstract = "One of the tasks in machine learning is to build a
device which guesses 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, GA , which let these automata
{"}evolve{"} to guess each next input symbol of the
sequence. Moreover, we studied the way to combine these
highly fit automata so that the network of them would
compensate for each other's weakness and guess better
than any single automaton can. We studied the simplest
approaches to combine automata: building trees of
automata with special purpose automata, which may be
called switch-boards . These switch-board automata are
located on the internal nodes of the tree, take an
input symbol from the input sequence just like other
automata do, and guess which subtree will make a right
guess on each next input symbol. Genetic algorithms
again play a crucial role in searching for switch-board
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. The test results show that DFAs
together with GAs seem to be very effective for this
type of pattern learning task. Besides this main
finding, the tests revealed several interesting things.
For example, the sequence of the note pitches is more
predictable than the sequence of up/down notes. This is
counter intuitive. Larger alphabets mean larger numbers
of possible configurations of automata. This implies a
larger search space for genetic algorithms; therefore,
the algorithms should have difficulty finding automata
which fit the tasks. However, the tree devices built to
predict the note pitches often outperform those built
to predict the up/down notes even though the size of
the input alphabet for the former is 8 and that for the
latter is 2. This suggests the following: The genetic
search is so powerful and effective that if there are
good solutions in its search space, it will find one
when it works with a large enough population for a
large enough number of generations. Therefore, if the
search fails to find a good solution, the search space
almost certainly does not contain one.",