Page 276 -

264 6 Structural Pattern Recognition

For the situation shown in Figure 6.13, with string dU, one would probably
consider the application of further criteria for discriminating negative P waves
from Q waves before making any definite decision.

6.3.7 Grammatical Inference

Until now the grammar rules were supposed to be known beforehand. Grammatical
inference is the learning process that extracts from a training set of classified
examples the grammatical rules that are able to syntactically describe those
examples. It is therefore a concept-driven approach, which bears some resemblance
to the supervised classification methods. Instead of parameter learning we are here
interested in rule learning.
Many algorithms have been proposed for grammatical inference; a good survey
on these is given in (Miclet, 1990). Particular simple and efficient methods have
been devised for inferring regular grammars. One of these methods, called the
successor method, starts by building a state diagram with a node corresponding to
each different production symbol, and then merges the nodes that have the same
successors. Let us imagine that we were given the following set of examples of
FHR accelerations: T = {ud, uhd, uud, uuhuud, uhud}. From these examples we
start listing all the successors of each symbol in T:

State S - Successors of h in T: {u)
State q, - Successors of u in T: {u, h, d)
State qh - Successors of h in T: (u, d)
State qd - Successors of d in T: 0

With this information we can now build the finite-state automaton of Figure
6.15, where each node corresponds to a symbol, and the arcs are labelled in
correspondence with the successors of the symbol. As a matter of fact, the
automaton of Figure 6.15 is the same as the one shown in Figure 6.12, with qd= F.

Figure 6.15. Finite-state diagram of an example-inferred automaton for FHR
accelerations.