Knowledge Extraction from Transducer Neural Networks.
Previously neural networks have shown interesting performance results for tasks such as classification, but they still suffer from an insufficient focus on the structure of the knowledge represented therein. In this paper, we analyze various knowledge extraction techniques in detail and we develop new transducer extraction techniques for the interpretation of recurrent neural network learning. First, we provide an overview of different possibilities to express structured knowledge using neural networks. Then, we analyze a type of recurrent network rigorously, applying a broad range of different techniques. We argue that analysis techniques, such as weight analysis using Hinton diagrams, hierarchical cluster analysis, and principal component analysis may be useful for providing certain views on the underlying knowledge. However, we demonstrate that these techniques are too static and too low-level for interpreting recurrent network classifications. The contribution of this paper is a particularly broad analysis of knowledge extraction techniques. Furthermore, we propose dynamic learning analysis and transducer extraction as two new dynamic interpretation techniques. Dynamic learning analysis provides a better understanding of how the network learns, while transducer extraction provides a better understanding of what the network represents.
Introduction
There has been a lot of interest lately in knowledge
structures and their representation in articial
neural networks [Holldobler, 1990, Kurfe, 1991,
Sperduti et al., 1995, Wermter, 1995, Hallam,
1995, Medsker, 1995, Sun, 1995, Wermter et al.,
1996, Elman et al., 1996, Craven, 1996, Wermter,
1999]. Articial neural networks (or connectionist
networks) have already demonstrated interesting
learning results for various classication tasks.
However, it continues to be very di-cult to understand
the underlying representations within the
connectionist networks which lead to this perfor-
mance. A better understanding of the connectionist
representations learned is not only important
for improving the credibility of a computational
technique, but also for improving the net-work
performance and the integration possibilities
with symbolic representations.
Several attempts have been made to interpret
connectionist networks, focusing on feedforward
networks in particular [Andrews and Diederich,
1996, Abe et al., 1993, Shavlik, 1994]. For in-
stance, visualizations of internal activations or
weight strengths can be used to get an impression
of the internal knowledge [Hinton, 1986, Gorman
and Sejnowski, 1988]. Some eort has also
been made to reduce the network size in order to
simplify the knowledge expressed therein by elimi-
28 Wermter
nating very small weights. Furthermore, groups of
similar weights can be replaced with their average
strength [Shavlik, 1994]. In addition, techniques
such as hierarchical cluster analysis have been
used to interpret connectionist networks. Never-
theless, often the interpretation of the dynamics
of the learning process and the underlying knowledge
has been neglected, especially in the case of
dynamic recurrent neural networks.
The interpretation of recurrent networks is more
di-cult than that of non-recurrent feedforward
networks, since the previous context in recurrent
networks has an important dynamic in
uence
within these networks. The internal states in recurrent
networks do not only depend on the input
but also on the internal state of the local memory
based on previous inputs [Elman, 1995, Giles
and Omlin, 1993, Omlin and Giles, 1996]. For
this reason, to date the focus has been primarily
on smaller recurrent networks and articially generated
data. For instance, an interesting current
approach interprets the training of a SRN network
that has two input, two output and two internal
elements in learning the sequence a n b n [Wiles and
Elman, 1996]. It has been discovered that the net-work
behaved like a spiral which moved to and
from a x point. Whereas this seems to be a plausible
interpretation of the behavior of recurrent
networks trained for the learning of the sequences
a n b n , dierent interpretations are required when
we move to dierent tasks and data sets closer to
real-world scenarios.
In the past, we have developed a large \real-
world" system for spoken language analysis which
makes extensive use of SRN networks [Wermter
and Weber, 1997, Wermter and Meurer, 1997].
The spoken input is recognized by a speech recognizer
and analyzed at the syntactic, semantic
and dialog levels based on an incremental analy-
sis, parallel syntactic and semantic interpretation,
and robust processing of errors. To date, however
it is not yet possible to focus on the interpretation
of the learning process and the interpretation
of the connectionist knowledge. In this
paper, we are primarily concerned with a detailed
interpretation of the learning behavior as well as a
symbolic interpretation of the learned knowledge
after training. In order to carry out such a detailed
analysis we will concentrate on a syntactic
transformation task as a representative task for
our large-scale speech/language system. The task
for the recurrent network is to process sentences
and associate their syntactic classes at the phrasal
level, e.g. noun phrase, prepositional phrase etc.
Using this task, we analyze a recurrent neural
network using many dierent techniques. We have
structured the paper as follows. First, we introduce
our representative syntactic transformation
task. Then, we dene and illustrate a) dynamic
learning analysis, b) weight analysis, c) hierarchical
activation analysis, d) component activation
analysis, and e) transducer extraction. We rigorously
compare these techniques on the same net-work
and the same data set and argue that these
dierent techniques provide mutually complementary
interpretations. The contribution of this paper
is a particularly broad and concrete analysis
of the knowledge extraction process which has not
been done before. Furthermore, we propose dynamic
learning analysis and transducer extraction
as two new interpretation techniques. Dynamic
learning analysis provides a better understanding
of how the network learns while transducer extraction
provides a better understanding of what the
network represents.
2. Extracting structured knowledge using
syntactic analysis task
In order to examine a number of dierent techniques
for extracting structured knowledge from
connectionist networks in a rigorous manner, we
will focus on a particular task. In our spoken
language environment [Wermter and Lochel,
1996, Wermter and Weber, 1997, Wermter and
Meurer, 1997], we have trained many variations
of SRN networks [Elman, 1991] with many sentences
using various corpora of several thousand
words each.
Based on a corpus of sentences from the domain
of scheduling appointments (2355 words), table 1
summarizes the accuracy of label assignment on
the unknown test set. The related experiments
and results have been reported elsewhere in detail
[Wermter and Lochel, 1996, Wermter and Weber,
1997, Wermter and Meurer, 1997, Wermter, 1998].
Here we just want to illustrate the real-world net-work
performance in table 1. The focus, how-
Knowledge Extraction from Transducer Neural Networks 29
ever, is on an analysis of the process of extracting
explicit knowledge from implicitly learned knowl-
edge. In this paper, we concentrate on syntactic
phrasal assignment (marked by *) in table 1.

Table

1. Performance of some networks on the test set of
the appointment scheduling corpus
Task Accuracy on test set
Basic syntactic disambiguation 89%
Basic semantic disambiguation 86%
Syntactic phrasal assignment* 84%
Semantic phrasal assignment 83%
Dialog act assignment 79%
Word repair detection 94%
Phrase repair detection 98%
To demonstrate this process of knowledge ex-
traction, we will here use 15 of these sentences
(containing 76 words) from the domain of appointment
scheduling. For illustration purposes, we
concentrate on the learning of a syntactic phrasal
assignment task where a sequence of basic categories
of words is associated with a sequence of abstract
syntactic categories. The actually occurring
syntactic basic categories are noun (n), verb (v),
adverb (a), adjective (j), preposition (r), determiner
(d) and pronoun (u). The abstract phrasal
categories are noun group (ng), verb group (vg),
and prepositional group (pg). The task of the recurrent
network is to learn to assign phrasal categories
on the basis of basic syntactic categories
in order to support a robust
at understanding
of spontaneously spoken language. Below, we
show some example utterances from the corpus,
together with the syntactic categories at the basic
and the phrasal level.
1. I (u ! ng) thought (v ! vg) in (r ! pg) the
2. That (u ! ng) is (v ! vg) the (d ! ng)
Thursday (n ! ng) after (r ! pg) Easter (n
Based on these seven basic syntactic and three
phrasal syntactic categories, we use an SRN net-work
with seven input units, three internal units
and three output units (the networks in the actual
system contain more categories and have been
trained with several thousand words, but for illustration
purposes we restrict ourselves to this
smaller network). The learning rate was 0.05 and
momentum 0.9. The weight updates were performed
incrementally after each training pattern.
Each training pattern consisted of the basic syntactic
category at the input layer and the abstract
phrasal category at the output layer.

Figure

1 shows a simplied example of such a
recurrent network for the task of syntactic phrase
assignment.
Output
Input
Context-
layer
AAAA
AAAA
AAAA
Noun
group
Prepositional
group
Verb
group
Pronoun Noun
Adjective
Verb
Adverb
Preposition
Determiner
Fig. 1. Recurrent network for knowledge extraction for
syntactic phrase assignment
The activation of an output element O j (t) at
time t in SRN networks is computed on the basis
of the weighted activation H i (t) of all incoming
connections limited by the logistic function f .
O
The activation of an element on the internal
layer H l (t) is computed in a similar manner. Here
the activation of the input layer I k (t) at time
t is used as the activation of the internal layer
at the previous time step t 1.
Wermter
3. Dynamic learning analysis: knowledge
structuring during lazy learning
In the past, most work on knowledge structures
and connectionist networks has focused on static
connectionist network representations. However,
important insights can be gained by examining
how certain knowledge structures emerge and develop
time before a certain task is learned
completely.
Frequently, the interpretation of the learning
behavior is just demonstrated by means of the
learning curve of the overall error reduction over
time. However, the learning curve is just the rst
step in a more detailed analysis and can only provide
preliminary hints about the performance of
a network over the training time. Figure 2 shows
the learning curve with the overall sum squared
error over time.
patterns 50000 100000 150000 2000000.20.6Error
Fig. 2. Learning curve for syntactic phrasal assignment
The learning curve shows that the speed of
learning diers substantially over time. Further-
more, we can see dierent stages during the learning
process. In the beginning, learning proceeds
fast, but later learning is slower and it takes longer
to make signicant improvements. For instance,
between 70000 and 140000 it seems that learning
is about to nish before there is a nal signicant
improvement.
We will now examine how the network reaches
its performance. We start the analysis directly after
the random initialization of the weights. This
is the state before learning starts. We want to
give an overview of the overall performance for all
input patterns at dierent time steps. To this ef-
fect, we show the error for each of the 76 patterns
of the demonstration set at dierent time steps.

Figure

3 shows the individual error for each of the
76 patterns before training.Individual patterns
Fig. 3. Performance for individual patterns before learn-
ing
Based on the random initialization, all patterns
show a relatively high error. At this point, it
is to be expected that the values of each output
element dier from the desired value 0 or
1 by 0:5. Therefore the expected error for an
individual pattern for three output elements is
expected error
value is conrmed in this gure.
As shown in gure 2, the error decreases quickly
at the start of the training. The state after 100
patterns of the training set is shown in gure 4.
First, we can observe that after 100 training pat-
terns, the error for some of the 76 patterns shown
could be reduced signicantly. Other patterns still
show a high error. Obviously, the network has
started to learn patterns selectively.
Knowledge Extraction from Transducer Neural Networks 31
Individual patterns
patterns
other patterns
Fig. 4. Performance for individual patterns after 100
training patterns
A more detailed analysis revealed that the patterns
with a lower error are exactly those patterns
which belong to the noun group NG. After only
100 patterns, the network has recognized that the
global error can be minimized signicantly by focusing
on the NG patterns, since these patterns
occur more frequently than, for instance, prepositional
groups or verb groups. Therefore, at rst
the network has learned a constant mapping of all
patterns to the noun group, since this reduces the
overall error most at this stage. This explains why
certain patterns in gure 4 still exhibit a high error
and others a low error. The patterns with a
low error are exactly the patterns which have been
classied correctly as noun groups.

Figure

5 shows the detailed performance after
patterns. After the network has learned a constant
mapping to NG, we can observe that the
performance for the NG patterns has improved
even further. However, we also observe that V G
patterns have been learned. A more detailed analysis
of the output preferences reveals that at this
stage, in addition to all NG, all V G patterns have
also been learned correctly. This is also demonstrated
in gure 5. All the remaining error patterns
at this stage are those patterns which should
belong to a prepositional group PG but which are
still categorized as noun groups NG. All NG patterns
and all V G patterns are classied correctly.
After the network has learned the most frequent
NG patterns, the second most frequent V G patterns
are learned. Thus, one could state that the
network pursues a conservative lazy learning strategy
and learns frequently occurring and simple
regularities rst.
Individual patterns
patterns
patterns
patterns
Fig. 5. Performance for individual patterns after 600
training patterns
Afterwards, the network attempts to improve
all patterns, especially the remaining patterns for
prepositional groups PG. The occurring nouns,
pronouns, determiners, and adjectives can either
be part of PG patterns or NG patterns. In order
to resolve this potential for ambiguity, previous
context must be used to learn the correct class
assignment. Again, we have an example of the
conservative lazy learning strategy of the network,
Individual patterns
3 exceptions of PG patterns
patterns
NG patterns, VG patterns
Fig. 6. Performance for individual patterns after 3000
training patterns
Wermter
since at rst the network has learned patterns
which do not need previous context knowledge for
the category assignment. Only after the simple
non-context-dependent category assignments have
been learned, are those patterns learned which require
the context of previous pattern assignments.
The state of the network after 3000 patterns is
shown in gure 6. All patterns are classied correctly
with the exception of three. Comparing g-
ures 5 and 6, the remaining error for the individual
patterns could be reduced signicantly. For the
learning of the PG patterns, it was necessary for
the network to integrate the local preceding con-
text. After 150000 patterns all regularities have
been learned as shown in gure 7. In comparison
with gure 6 we point out the smaller scaling of
the vertical axis. At this stage all patterns have
been learned, even though there are dierences between
the error rates of individual patterns. In order
to reach this 100% correctness on the training
set, it may be necessary to give up a reasonably
good state at a certain stage in order to reach an
even better stage later. This is also re
ected in
the global learning curve in gure 2.
Individual patterns
all NG patterns,VG patterns,
PG patterns correct
Fig. 7. Performance for individual patterns after 150000
training patterns
In general, the network pursues a conservative
lazy learning strategy. First, simple and frequently
occurring generalizations of one category
are learned. Only when the network cannot minimize
its error signicantly any more, are other
frequently occurring categories integrated. Fur-
thermore, only when all those patterns have been
learned that do not require previous local context,
are those patterns learned that require context for
the correct category assignment of otherwise ambiguous
input. Finally, any remaining exceptions
are learned. During this conservative learning process
it may be possible that the overall error increases
brie
y in order to reach a better overall
state later.
4. Weight analysis for knowledge extrac-
tion
Visualizations of internal weight strengths can be
used to get an impression of the internal knowl-
edge. In our experiments, the training set was
learned correctly after 150000 patterns and this is
where we start our analysis. We start with such
a weight analysis since weights provide the lowest
level of interpretation of a connectionist represen-
tation. Figure 8 shows the weights of the network
for three dierent time steps. It is illustrated how
the weights change over time during learning.
In this gure the identiers of the source connectionist
elements are shown horizontally and the
identiers of the goal connectionist elements are
shown vertically. We start with the horizontal
axis. From left to right, we can see the weights
from the threshold element (S), from the input
connectionist elements for the syntactic basic categories
(n, j, v, a, r, u, d), from the three internal
elements and from the three context
elements c3). In the vertical axis from
top to bottom, we see the weights to the three
internal elements and to the output
elements representing the abstract syntactic categories
(VG, NG, PG).
Knowledge Extraction from Transducer Neural Networks 33
after 100 patterns
after 600 patterns
after 150000 patterns
Fig. 8. Weight analysis at the beginning of training (100 patterns), during training (600 patterns) and after training
(150000 patterns)
White boxes represent positive weights, black
boxes negative weights. The size of the boxes
corresponds to the size of the weights. The copy
connections from the internal layer to the context
layer are not changed. Therefore, they are not
shown since they are always equal to 1.
We start with the analysis of the rst third of
gure 8. After random initialization, this rst
third shows all weights of the network after 100
patterns. At this point, all NG patterns can be
classied correctly, but no other patterns have
been learned yet. The network has learned a constant
output in order to reduce the overall error
as much as possible. We can see in gure 8 why
the network produced this constant NG class.
34 Wermter
We can see that the weights from the input elements
of the syntactic basic categories (n, j, v, a,
u, d) to the internal elements are
relatively small and similar. The same holds for
the weights from the context elements (c1, c2, c3)
to the internal elements. This is due to the random
initialization at the beginning of the train-
ing. The weights from the internal elements to
the output elements of the abstract syntactic categories
are negative for V G and
PG; those from the internal elements to NG are
close to 0. This is the reason why the network produces
constantly the NG category at this stage.
Now we focus on the state of the network after
presenting 600 patterns, also shown in gure 8.
At this point, all NG and all V G patterns are
assigned correctly. This is also re
ected in the
weights. We observe positive weights from n,
and d to the internal elements and positive weights
from the internal elements to NG. However, we
see negative weights from v to the internal elements
and from the internal elements to V G. The
PG patterns are not categorized correctly at this
point. One reason for this is that the PG patterns
depend signicantly on the previous con-
text. However, at this point, the network has
just learned the obvious preferences and is only
just starting to change the weights of the context
layer.
The network state after 150000 patterns is
shown at the bottom of the gure. In the internal
layer, a distributed representation has developed.
Therefore, a direct interpretation is not easily pos-
sible. However, it is observed that the rst internal
element is primarily important for PG detec-
tion, the second internal element plays an important
role in V G assignment and the third internal
element is important for NG. Nevertheless, this
is a distributed rather than a local representation
and there is additional in
uence from other ele-
ments. Furthermore, the weights of the context
layer (from c to h) have changed. This is necessary
in order to learn the PG group assignment.
Generally speaking, we can explain certain phenomena
using this type of weight analysis at the
lowest interpretation level of a network. However,
it is di-cult to extract explicit knowledge and a
deeper understanding of the behavior of the net-work
directly from the weights. Reasons for this
di-culty include (1) the static representation of
the weights which does not show the dynamics of a
recurrent network, (2) the distribution of weights
and activation, and (3) the number of weights,
especially in the case of larger networks. There-
fore, some eort could be made to reduce the size
of the network by eliminating very small weights.
Furthermore, groups of similar weights could be
replaced with their average strength. Nonethe-
less, weight analysis is still too detailed for larger
networks.
5. Component activation analysis for
knowledge extraction
Weight analysis focuses on the weights and provides
a very low-level analysis. One way to address
this problem is to move towards activation analysis
where the activations of internal elements are
analyzed. Since internal elements receive activation
from a number of weighted connections, the
activation of an internal element integrates several
weighted connections and provides a higher
abstraction level of analysis.
In order to demonstrate how such an analysis is
performed, we will use the same SRN network we
have introduced in the previous section and store
all vector representations of the internal layer for
each pattern. These vector representations constitute
the input to a cluster algorithm which provides
a hierarchical representation in the form of
a dendrogram. Vectors with similar vector representations
will end up in the same cluster.

Figure

9 shows the initial part of patterns as
they were clustered according to their internal
activations. It can be clearly observed that the
internal representations re
ect the classication
according to the three classes
PG. That is, based on the weights, the internal
layer has learned representations which particularly
support this classication. A single word can
appear in dierent contexts and can lead to different
internal representations. For instance, the
word \the" is shown with two dierent represen-
tations. One representation is its use as part of
the NG class, and the other as part of the PG
class. Therefore, we nd both representations at
dierent positions within the dendrogram.
Knowledge Extraction from Transducer Neural Networks 35
ALL$U$NG
I$U$NG
I$U$NG
US$U$NG
WE$U$NG
WEDNESDAY$N$NG
MORNING$N$NG
IN$R$PG
WEEK$N$PG
IS$V$VG
COME$V$VG
MUST$V$VG
IS$V$VG
Fig. 9. Hierarchical cluster analysis of internal classication representations (for visibility purposes, only a portion is shown
6. Principal component analysis for
knowledge extraction
Another kind of analysis which can be used for
interpreting the internal representations of clas-
sications is principal component analysis. Figure
shows the result of this analysis for our
current task. All vectors from the internal layer
and the corresponding identiers provide the input
for the principal component analysis. Vectors
which dier substantially from each other are
depicted in the gure with a large distance. It
can also be observed that the internal representations
re
ect the preference mappings learned for
the three category classes. NG, V G, and PG patterns
are distributed across dierent areas. Thus,
the classication of the internal representations
can be clearly seen. This shows that the network
has actually learned the classication task well.
After learning has been completed, the internal
representation characterizes the preference map-
ping. According to cluster analysis or principal
component analysis, similar internal vector representations
are responsible for the representation
of similar preference assignments to equal cate-
gories. However, the interpretation of the weights
by means of Hinton diagrams and of the activations
via cluster analysis and principal component
analysis only provides a limited form of structuring
to the extracted knowledge.
36 Wermter
I$U$NG
IN$R$PG
THURSDAY$N$NG*
MORNING$N$NG
WE$U$NG
UNS$U$NG
ON$A$PG
THE$D$NG*
IS$V$VG
WEDNESDAY$N$NG
I$U$NG*
COME$V$VG MUST$V$VG
I$U$NG*
THAT$U$NG*
IS$V$VG
ALL$U$NG*
TUESDAY
COULD$V$VG
US$U$NG
LET$V$VG*
US$U$NG
DAS$U$NG*
IS$V$VG
MAKE$V$VG*
TILL$R$PG*
WE$U$NG
IN$R$PG
MARCH$N$PG
OTHER$J$NG
THAT$U$NG*
IS$V$VG
Fig. 10. Principal component analysis of internal classication representations
7. Transducer extraction
Words and sequences of words can be represented
as syntactic, semantic, and pragmatic category
preferences. Then they can be input, for instance,
to SRN networks. Each input representing a sequence
of category preferences is associated with
a sequence of corresponding output preferences.
This simple description of sequence analysis is
similar to the function of synchronous sequential
machines [Booth, 1967, Kohavi, 1970, Shields,
1987], although preferences and learning are not
yet considered in such machines. Therefore, we
shall focus on extensions of synchronous sequential
machines for representing sequential knowl-
edge, especially synchronous Moore machines. We
start with the basic denition of a synchronous sequential
machine which is also called a transducer:
Denition of a Synchronous Sequential Ma-
chine, Transducer
A synchronous sequential machine M is a tuple
1. I , O nite, nonempty sets of input and output
2. S nonempty set of states
3. The function f s : I S ! S is state transition
function
4. The function f o is an output function. If the
output depends on the state and the input,
the machine is a so-called Mealy machine with
the output function f O. If the
output only depends on the state the machine,
the later is a so-called Moore machine with
the output function f These synchronous
sequential machines are sometimes
called transducers.
A sequential machine assigns an output and a
new state to an input and an old state. This can
be done for a whole sequence of inputs and states
in discrete time. The set S is not necessarily -
nite [Booth, 1967], although this is assumed in
the case of nite machines. Whereas automata
Knowledge Extraction from Transducer Neural Networks 37
or acceptors of languages decide whether a certain
input belongs to the corresponding grammar,
these sequential machines are transducers which
change their internal states dynamically, depending
on the inputs and the previous states, while
also providing an output for each input.
Mealy and Moore machines are slightly dier-
ent from each other. Moore machines determine
the state rst and afterwards this state is used to
provide the output. In contrast, the output in a
Mealy machine depends also directly on the current
input. However, it can be shown that for each
Moore machine there is an equivalent Mealy machine
and vice versa [Booth, 1967, Hopcroft and
Ullman, 1979].
In our case, we concentrate on Moore machines
since the output in certain neural networks is
based on the internal state. This holds, for in-
stance, for feedforward networks or SRN networks.
Whereas sometimes [Sun, 1995] a sequential machine
has been used to model a single element of
a neural network, we want to use a sequential machine
as a description for a whole network. This
is also motivated by the fact that real neuron systems
can be seen as physical entities which perform
state transitions [Churchland and Sejnowski,
1992].
Now we can specify language knowledge by describing
Moore machines and their state transition
function f s and output function f o . We can also
integrate f s and f o to a function f : IS ! OS.
Then f corresponds for instance to the transformation
within a SRN network. The specication
of a Moore machine could be performed by using
state tables. A potential entry for the task of
assigning syntactic phrasal categories to syntactic
basic categories could be:
If verb and current state = prep. group
then new state = verbal group and output = verbal
group
It may not be possible to assign a direct interpretation
to a state. For this reason, simple
identiers may be used:
If verb and current state = 4
then new state = 5 and output = verbal group
It is possible to dene state transition tables
which assign each combination of input and current
state an output and a new state. In this
way, a symbolic synchronous sequential machine
is specied. If clear regularities are known beforehand
and the number is limited, such tables can
be composed manually. However, the number of
input and state combinations quickly gets so large
that automatic procedures become necessary.
The above-mentioned state transition tables are
discrete symbolic. Therefore, they do not support
gradual representations. For instance, the input
or the state could be ambiguous and dierent
gradual preferences could exist for dierent inter-
pretations. For instance \meeting" could have a
stronger preference for its syntactic interpretation
as a noun and a smaller preference for a verb form.
Consequently, we want to use preferences for the
input, output, and states of such machines. Preferences
of this type should be able to take values
from [0; 1] m so that multiple preferences can be
represented and integrated.
If we extend a single category (as in: if
verb) to an n-dimensional preference for the input
and an m-dimensional preference for the output
then we obtain a new synchronous machine
which we will call a preference Moore machine.
Now we want to describe such a synchronous sequential
preference Moore machine which transforms
sequential input preferences to sequential
output preferences. We will see that simple recurrent
networks or feedforward networks can be
interpreted as neural preference Moore machines.
Furthermore, we will show how symbolic and neural
knowledge can be integrated quite naturally
using preference Moore machines.
38 Wermter
Denition of a Preference Moore Machine
A preference Moore machine PM is a synchronous
sequential machine which is characterized
by a 4-tuple
and S being non-empty sets of inputs, outputs and
states. O  S is the sequential preference
mapping and contains the state transition
function f s and the output function f o . Here I ,
O and S are n-, m- and l-dimensional preferences
with values from [0; 1] n , [0; 1] m and [0; 1] l , respectively

A generalized version of a preference Moore machine
is shown in gure 11 on the left. The preference
Moore machine realizes a sequential preference
mapping, which uses the current state preference
S and the input preference I to assign an
output preference O and a new state preference.
Preference mapping
States
AAAA
AAAA
Output
Input
Fig. 11. Neural preference Moore machine and its relationship to a SRN network
Now we describe a new technique of extracting
the knowledge within a recurrent network in the
form of a transducer. A symbolic transducer can
be extracted from our recurrent network which
assigns to each input vector of basic syntactic
categories a new output vector of phrasal categories
depending on the previous context. In our
network, the internal state and the context were
represented by a three-dimensional vector. For
simplicity, each strict symbolic interpretation of
a three-dimensional vector can take 2 3 , that is 8
states. In order to acquire a symbolic interpretation
of the network, we presented all patterns
from the training set and stored the internal state
vectors at the hidden layer of the network. For
each output vector and for each state vector the
next corner preference was determined using the
Euclidean distance metric. Thus the Euclidean
distance metric assigned one of three symbolic abstract
syntactic phrase categories to each output
vector and one of eight state number identiers to
each state vector.
Knowledge Extraction from Transducer Neural Networks 39000 100010 110011
n:ng
r:pg
v:vg
d:ng
d:ng
n:ng
r:pg
u:ng
d:ng
n:ng
n:ng
d:pg
j:pg
n:pg
v:vg
d:ng
a:ng
a:pg
j:ng
n:ng
v:vg
v:vg
r:pg v:vg
u:ng
r:pg
n:ng
n:ng
d:ng
u:ng
n:ng
r:pg
a:pg
v:vg
v:vg
u:ng
Fig. 12. Transducer extraction from a recurrent network for the example sentence \That (u:ng) is (v:vg) the (d:ng)
Thursday (n:ng) after (r:pg) Easter (n:ng)".

Figure

12 shows the knowledge learned by the
network as an extracted symbolic transducer. The
corner nodes represent the eight strict states, the
center node represents the start state of the trans-
ducer. At the edges we nd the symbols for the
single transductions. Input and output categories
are separated by a colon, e.g. d : ng means that -
starting from the source state of this edge - a determiner
preference d is assigned to a noun group
preference ng and the transduction is made to the
end state of this edge. In the extracted transducer
we can see some clear regularities at certain
states. For instance, the transductions to state
100 are primarily responsible for the assignments
to the prepositional group pg. Other examples
are the transductions to state 010 and to state
000, which are primarily responsible for the verbal
group (vg) assignment. Furthermore, gure 12
shows the example transductions for the sentence
\That is the Thursday after Easter". Beginning
with the start state at the center, we see the transduction
ng for the word \That" which assigns
the noun group ng to the pronoun u. Then,
assigns a verb group vg to the verb \is". Then the
transductions ng ng assign the noun group
ng to \the Thursday". Finally the transductions
assign the prepositional group pg
to the sequence \after Easter". Dierent abstract
syntactic categories (ng, pg) can be assigned to
the same category (n) depending on the learned
previous context.
n:ng
r:pg
v:vg
d:ng
d:ng
n:ng
r:pg
u:ng
d:ng
n:ng
n:ng
d:pg
j:pg
n:pg
v:vg
d:ng
a:ng
a:pg
j:ng
n:ng
v:vg
v:vg
r:pg
v:vg
u:ng
r:pg
n:ng
n:ng
d:ng
u:ng
n:ng
r:pg
a:pg
v:vg
v:vg
u:ng
Fig. 13. Transducer extraction from a recurrent network for the example sentence \I (u:ng) thought (v:vg) in (r:pg) the
(d:pg) next (j:pg) week (n:pg)".
More detailed (less detailed) transducers can
be obtained if the state and output vectors are
mapped to more (fewer) nodes. Thus, the general
abstraction level of such a symbolic transducer
can be quite variable. The symbolic transducer
represents an abstraction of the detailed network
knowledge but this abstraction also hides some of
the numerical complexity and allows a direct symbolic
interpretation which provides a summary of
the network behavior.
To give an example, gure 13 shows the transductions
for the example sentence \I thought in
the next week". Beginning with the start state
at the center, we see the transduction ng
for the word \I", which assigns the noun group
ng to the pronoun u. Then, assigns a
verb group vg to the verb \thought". Finally
the transductions r : pg d :
assign the prepositional group \pg" to the word
sequence \in the next week". One advantage of
this transducer extraction is the higher abstraction
level used for the representations of the recurrent
network which leads to a better understanding
of its function. The original network contains
more detailed knowledge in the numerical weights
and activations, but it is not possible to see the
declarative sequential symbolic knowledge which
this network represents. The extraction of a symbolic
transducer allows a better understanding of
the learned sequential knowledge which is represented
in a more explicit manner.
Knowledge Extraction from Transducer Neural Networks 41
8. Discussion and Analysis
8.1. Comparison of knowledge extraction technique

There has been some previous work on using individual
techniques in isolation for interpreting neural
networks and extracting structural knowledge
from them. In this paper, we have analyzed ve
such dierent techniques using the same trained
network in order to interpret the network knowl-
edge. Such extensive comparisons of detailed net-work
knowledge are needed in order to gain a
better understanding of the knowledge extraction
represented in neural networks.
We have also introduced two new techniques
here: dynamic learning analysis and transducer
extraction. Dynamic learning analysis examines
the formation and development of categories over
time during learning. Thus, it provides a much
deeper understanding of how the neural network
arrives at its learned representation. Transducer
extraction was developed to represent the sequential
processing in a recurrent network at a higher
level of abstraction.
In general, we found that dierent interpretation
techniques provide dierent views of the
knowledge contained in a neural network. Thus,
there is not a single best technique for all dier-
ent aspects of knowledge extraction. The use of
a particular technique depends rather on the requirements
of the interpretation. In table 2, we
illustrate and summarize the general properties of
the ve dierent techniques.
Dynamic Learning Analysis (DLA) is based on
the output representations and provides a high
level of understanding based on these known output
representations. This technique is easy to
interpret and can be used with other network
types. On the other hand, it does not particularly
support recurrent networks, symbolic integration,
and
exible knowledge structuring. Furthermore,
structural relationships cannot be extracted.
Transducer extraction (TE) is a new technique
which uses output representations as well as internal
activations. The main advantages of this
technique are the high level of understanding in
the form of an extracted symbolic transducer, the
specic support for the sequentiality of recurrent
networks and the possibility for extracting structural
relationships. Such an extracted transducer
can be integrated with other symbolic knowledge,
e.g. other coded symbolic transducers. Further-
more, dierent transducers can be generated with
exibility, based on the number of states used in
the internal activation layer. This leads to a relatively
straightforward interpretation of the net-work
involved compared to the other techniques,
but it also requires the additional eort of extracting
this symbolic transducer from the internal activations
and the output representations.
If we compare DLA and
and CAA, we can see that DLA and are techniques
that specically provide high level interpretations
for dynamic learning and processing. We
argue that WA, HAA, and CAA are techniques
with a tendency towards a general, detailed, but
low-level interpretation. DLA and TE, however,
are techniques for specialized, high-level, dynamic
interpretation. Focusing on output interpretations
and the dynamics of recurrent networks provides
a new level of understanding. Whereas a lot
of previous work has focused on low-levels of in-
terpretation, we believe that in the future, higher
levels of interpretation and knowledge extraction
will be required.
8.2. Related work on transducer extraction and
related work
Finite state automata and transducers have been
widely used in various forms within traditional
e.g. [Hopcroft and Ullman,
1979]. Basically, automata and transducers are always
in a certain context state and they analyze a
certain word (symbol). Then they move to a new
state and potentially generate a new word (sym-
bol). By using changing states, it is possible to
encode the sequential context.
Although nite automata or regular languages
are not su-cient to describe all possible constructions
of natural language completely (see e.g.
[Winograd, 1983]), automata still constitute a central
minimal requirement for the representation
of natural language. Thus, they occupy the lowest
level in the Chomsky hierarchy of languages
[Hopcroft and Ullman, 1979]. Furthermore, it is
possible to design e-cient realizations of nite automata
for dierent domains [Kaplan, 1995], e.g.
42 Wermter

Table

2. Comparison of dierent knowledge extraction techniques: Dynamic Learning Analysis (DLA), Weight Analysis
(WA), Hierarchical Activation Analysis (HAA), Component Activation Analysis (CAA), Transducer Extraction (TE).
Further abbreviations: Activations/Weights/Outputs and Low/Medium/High.
Network representations used O W A A AO
General level of understanding H L M M H
Specic support for recurrent networks L L L L H
Degree of structural relationships L L M M H
Integration with symbolic knowledge L L M M H
Flexibility in level of knowledge structuring L L M M H
Computational eort L L M M M
Easiness of interpretation H L M M H
Generality and portability to other networks H H H H M
for morphology, lexicon access, information extraction
from sentences, syntactic tagging, etc.
Recurrent networks have the potential to learn
a sequential preference mapping f
automatically, based on input and output examples
(see gure 11), whereas traditional Moore
machines or Fuzzy-Sequential-Functions [Santos,
1973] involve manual encoding. It has been recently
illustrated how SRN networks can emulate
each symbolic Moore machine and each nite automaton
[Kremer, 1995, Kremer, 1996]. It has
also been shown however [Goudreau and Giles,
1995, Goudreau et al., 1994] that a recurrent net-work
with only a single input layer, one context
layer, and one output layer, the so-called Single-
layer-rst-order-network, is not su-cient for the
realization of arbitrary nite automata.
In natural language processing, representations
have to be at least as powerful as nite au-
tomata. Consequently, Single-layer-rst-order-
networks are not appropriate, which is why we
have used SRN networks here. These recurrent
networks contain nite transducers as a special
case, but also support much more powerful properties
based on their gradual m-dimensional preference
representations. For instance, it could be
shown that SRN networks can emulate certain restricted
properties of a pushdown automaton, in
particular the recursive representation of structures
with a limited depth [Elman, 1991, Wiles
and Elman, 1996].
Apart from traditional symbolic regular rep-
resentations, gradual and learned representations
can also be represented. Furthermore, the number
of input, state, and output preferences is not necessarily
nite. Therefore, neural preference Moore
machines are more powerful than nite transduc-
ers. Our recurrent neural networks can be seen as
learning augmenting
a simple nite symbolic transducer with
respect to learning within a gradual preference
space. From this perspective, symbolic knowledge
is a special abstract region in a neural preference
space.
An important line of research on automata and
recurrent networks has been reported in [Giles
et al., 1992, Goudreau and Giles, 1995, Tino et al.,
1995]. Giles and colleagues studied both nite
state automata and neural networks, but there are
substantial dierences with our research. They
started often with a known nite state automaton,
which was used to generate sequences for it. Then
these sequences were used for training a second-order
neural network. Using a partition algorithm,
a nite state automaton was extracted from the
network activations, minimized and compared to
the original known nite state automaton. In this
way, Giles and colleagues could study the computational
properties of the extraction particularly
well, but the nite state automata also frequently
relied on relatively simple 1/0 sequences.
Knowledge Extraction from Transducer Neural Networks 43
Our motivation and methodology is dierent
from theirs in several respects. We assume that
the initial nite state automaton or transducer is
not known. Especially for real-world problems,
the interesting case is the one where such an automaton
is not known in advance. Whereas it
is interesting for comparison and sequence gen-
eration, generating sequences with a nite state
automaton already introduces certain regularities
into the training set. Thus, sequence generation
has an important in
uence on the learning behav-
ior, something which we want to rule out. In
fact, we are more interested in situations where
we do not know the machine which has to be ex-
tracted. Especially with noisy real-world learning
data, the underlying regularities may be quite disparate
from regularly generated sequences.
Furthermore, the task of our networks is quite
dierent. The second-order networks employed by
Giles and colleagues are trained for recognition.
The output layer represents state representations
which can be fed back to the input layer at the
next step. Our recurrent networks perform an assignment
task, where a sequence of inputs is associated
with a sequence of outputs. We are not determining
whether a certain sequence belongs to a
certain automaton, but what the simple
at structure
of this sequence is. That is, we are interested
in transducer extraction rather than recognizer ex-
traction. In general, there are no designated nal
states in our networks, since the network - and the
extracted symbolic transducer - produce output
as long as input is provided. This transducer behavior
is therefore quite dierent from the recognition
performance reported in [Giles and Omlin,
1993], which is based on acceptors for articial
languages.
9. Conclusion
The main contribution of this paper is a particularly
broad analysis of knowledge extraction
for recurrent networks. In addition, we propose
dynamic learning analysis and transducer extraction
as two new dynamic interpretation tech-
niques. Dynamic learning analysis provides a
better understanding of how the network learns,
while transducer extraction provides a better understanding
of what the network represents. After
learning, a conservative \lazy learning" strategy
leads to connectionist representations which
can be described as symbolic transducers. These
transducers allow for a much better interpretation
of the sequential network knowledge compared to
the standard analysis using hierarchical clustering
or Hinton diagrams. Weight analysis, cluster
analysis, and principal component analysis are detailed
but static. In contrast, our new method
for extracting symbolic transducers can describe
the learned classication performance much bet-
ter, since transducer extraction considers the sequential
character of the learned representations
in a recurrent network and allows a better symbolic
inspection. Possibilities for direct integration
with symbolic classiers can be explored in
future work. We conclude that dynamic learning
analysis and transducer extraction have a lot
of potential for improved knowledge structuring
based on recurrent networks.



--R

Extracting algorithms from pattern classi
Rules and Networks.
Sequential Machines and Automata Theory.
The Computational Brain.
Extracting Comprehensible Models from Trained Neural Networks.
Distributed repre- sentations
Language as a dynamical system.

Learning and extracted


On recurrent neural networks and representing

Hybrid Prob- lems
Learning distributed representations of concepts.

Introduction to Automata Theory
Finite state technology.
Switching and Finite Automata Theory.
On the computational power of Elman-style recurrent networks
A theory of grammatical induction in the connectionist paradigm.

Hybrid Intelligent Systems.
Extraction of rules from discrete-time recurrent neural networks
Fuzzy sequential func- tions
A framework for combining symbolic and neural learning.
An Introduction to Automata Theory.
Learning distributed representations for the classi

Finite state machines and recurrent neural networks.
Hybrid Connectionist Natural Language Processing.
The hybrid approach to arti
Preference moore machines for neural fuzzy integration.

Building lexical representations dynamically using arti

SCREEN: Learning a at syntactic and semantic spoken language analysis using arti
Learning to count without a counter: A case study of dynamics and activation landscapes in recurrent net- works
Language as a Cognitive Process.
--TR
symbolic interpretation;SRN networks;analysis of connectionist learning;knowledge extraction;neural network learning