Unified Integration of Explicit Knowledge and Learning by Example in Recurrent Networks.
AbstractWe propose a novel unified approach for integrating explicit knowledge and learning by example in recurrent networks. The explicit knowledge is represented by automaton rules, which are directly injected into the connections of a network. This can be accomplished by using a technique based on linear programming, instead of learning from random initial weights. Learning is conceived as a refinement process and is mainly responsible for uncertain information management. We present preliminary results for problems of automatic speech recognition.
Introduction
The resurgence of interest in connectionist models has led several researchers to investigate
their application to the building of "intelligent systems". Unlike symbolic models proposed
in artificial intelligence, learning plays a central role in connectionist models. Many
successful applications have mainly concerned perceptual tasks (see e.g. [2, 6, 10, 20]),
This research was partially supported by MURST 40% and CNR Grant 90.01530.CT01.
1 The authors are with Dipartimento di Sistemi e Informatica, Universit'a di Firenze, Via di Santa
Italy, Tel. (39) 55-4796265 - Telex 580681 UNFING I - Fax (39) 55-4796363,
where discovering explicit rules does not seem either natural, or easy. Connectionist models
appear better suited for low level tasks than symbolic ones. Like humans, they rely
on learning for perceptual tasks. On the other hand, the learning by example paradigm
cannot be stressed too much for emulating any intelligent behavior. In many cases an
intelligent behavior follows explicit rules. As a matter of fact, any machine conceived for
these situations should not ignore this knowledge.
In order to prove the potential power of the learning by example paradigm, for problems
of learning sequences, some researchers have recently shown that explicit rules can
also be discovered by learning from tabula rasa configurations. In particular Cleeremans
[3], Elman [5], and Williams [22] have demonstrated that a full connected recurrent net-work
is capable of learning small automata. These investigations are very interesting,
since they show that connectionist models can learn rules only relying on presentation
of examples. However, a closer investigation shows that we cannot stress too much the
learning by example paradigm for any problem. Complex tasks may give raise to local
minima, and ordinary gradient descent learning algorithms are likely to fail in these cases.
At least for feedforward nets, an analysis of this problems has been carried out which allows
us to understand the success of Backpropagation [18] in several problems of pattern
recognition [11]. However, using the same theory, it can be easily proven that simple
examples exist in which the learning algorithm fails to discover the optimal solution.
The integration of explicit knowledge and learning by example appears to be a natural
way of evolving intelligent systems based on connectionist models. Our hypothesis is that
for a model to be effective, this integration should be uniform. As a consequence, explicit
and learned rules should be represented in the same way by the weight connections of a
neural network.
In this paper we address the problem of learning sequences and we assume that the
explicit knowledge on such problem is available in terms of automaton rules. Our basic
assumption for implementing automata is that of relying on their state equations. In so
doing, all the efforts are focussed on finding out a method for injecting automaton rules
into the connections of a recurrent network. In section II we demonstrate that automaton
states can be coded with neuron activities and, in section III, that each automaton rule
can be realized in terms of constraints on the weights. In particular, all the automaton
rules can be translated into a set of inequalities according to the linear programming
framework.
On the basis of these remarks, in section IV we propose a unified approach for integrating
explicit knowledge and learning by example paradigm in recurrent neural networks.
We propose an architecture composed of two cooperating subnets. The first one is designed
in order to inject the available explicit knowledge, whereas the second one is mainly
responsible of uncertain information.
The effectiveness of the proposed model is currently under evaluation for problems of
automatic speech recognition. In section V we report preliminary results for a problem
of isolated word recognition. The chosen test, based on our own Italian speech database,
is quite difficult, since all the words are composed of nasals and vowels. The purpose
of the experiments is mainly that of providing material to discuss on the behavior of
the proposed model in practice. Unlike many suggested solutions proposed in literature,
which are based only on learning by example [4, 13, 17], the proposed model is likely to
scale up very well when increasing the lexicon.
II Information latching
Let N and U be the set of neurons and external network inputs, respectively. Each
neuron receives inputs from N
S U . The recurrent network model we consider is based
on the following equations:
a
(1)
where
I
being is the network status which contains all the outputs of the
neurons. We also denote with W i
the vector of weights towards neuron
feeding the network with a sequence of inputs, the status
represents a codification of the information extracted from that sequence.
Let us investigate the possibility of latching the information of a given state. As we
will show in the next section, this is very useful in order to investigate the automaton
realization.
Definition 1.
We say that a given dynamic hidden neuron latches the information @ t 0 , represented by
its activation a the following inequalities hold:
a
a
(2)
The concept of information latching has been introduced in [8] for discussing the properties
of Local Feedback Multi-Layered Networks. This definition suggests the interpretation
a i
I

Figure

1: Graphical interpretation of information latching.
of the neuron output as a boolean status, in that only x b
relevant.
Henceforth, when referring to state and state transition in the network, we will assume
tacitly that x b
i (t) is involved and not the actual output x i (t).
Theorem 1.
Given a generic neuron i, the following facts hold:
1. if I i latching occurs provided that w ii ? 1=f
2. if w ii ? 2 then the latching condition also holds if jI i (t)j ! I
being
I
3. if w i;i ? 2 then a state transition occurs in a finite number of steps if
I
i low to high transition
I
i high to low transition:
Proof
Let us consider the of the generic neuron i 2 N which follows
the equation:
a
Because of the hypothesis w ii ? 2, equation (3) has three equilibrium points (see line (1)
in fig. 1). One of them corresponds with a Both the other points are asymptotically
stable. We prove this fact for the point a
which satisfies
a
Let us define the Lyapunov function ([14] pp. 166-221) V (a i ) as
Because of the hypothesis w ii ? 2 it follows:
If a i ? g(a
. As a result the first factor is positive and consequently
. Therefore, the
first factor is negative and we have \DeltaV ! 0 again. Hence the stability of a
each a i 2 (0; 1). A similar proof can be provided for the stability of the other non null
solution of (3). The equilibrium point a In fact, starting from any point
in the neighborhood of zero, the state trajectory goes to one of the two stable points a
according to the initial sign.
The same proof is also valid if the neuron receives a constant input I 0 suchthatjI
I
i . This has the effect of translating the input line in fig. 1. When jI
i such line
becomes tangent to the curve f(a i ). This situation corresponds to a degeneration of two
equilibrium points. A straightforward analysis allows us to check the relationship given
for I
i in the second statement of the theorem. 2
Now let us consider the effect of adding a time-variant forcing term I i (t) bounded in
module by a constant I 0 such that
. As previously done, let us limit the
analysis to the positive solution. From the previous discussion, it follows that the system
has a stable equilibrium point ff
. We can easily prove that the activation a i (t) of the
system
a
satisfies the inequality
a
By assuming null initial state, eq. (9) is obviously valid for us suppose that
is valid @t; then:
a
Because of the previous considerations on the stability of ff
(see eq. (7)), the activation
ff i (t), and therefore a i (t), cannot change their sign, and then information latching occurs.
Just remember thatf 0 (a i
No. steps neuron input I
9 0.593 2.008 3.637 4.493 6.255 8.063
I

Table

1: Relationship between transient duration L and neuron input I i , for different
values of w ii . For example, if w using I leads to a state transition in
three steps.
In order to prove the third theorem's statement let us consider the case of neuron
latched in high state. When an input I i ! \GammaI
i is applied, the input line has only one
intersection with the curve f(a i ) (see fig. 1, line(2)). Therefore, a i (t)'s evolution follows
the attractive trajectory towards the unique equilibrium point (see dotted lines in fig. 1),
which corresponds to a low state boolean value. A similar proof can be given for the low
to high transition. 2
This theorem indicates under which conditions information latching occurs. It makes
it clear that the more the local weights increase, the more the latching is related to
saturated configurations. Moreover, Theorem 1's second statement defines the conditions
under which the current state is latched. It indicates the limit condition which guarantees
information latching, and consequently the state transitions. If we increase w ii then I
increases, thus indicating more robustness in latching information.
The value of w ii also affects the transient duration L when a state transition occurs:
the greater is w ii , the longer is the transient. This behavior is summarized in table 1 for
the case of low to high transition. The table was created by assuming a
I The transient duration is evaluated assuming I i
For each column, all the I i values belonging to the interval with extremes given by two
subsequent row values determine the number of steps specified by first row value.
III K algorithm: learning by linear programming
As pointed out in the introduction, an "intelligent behavior" often follows rules that can
be explicit to some extent. In order to limit the complexity of the learning phase, any
intelligent system should exploit these rules. As we will show in section V, the input
information is sometimes represented by a continuous signal. However, in these cases, we
can derive a symbolic representation of that information by means of an input quanti-
zation. The string obtained in such way may contain subsequent repetitions of symbols
(e.g. "nnuuummaaa"). In problems of automatic speech recognition these repetitions are
related to the phoneme duration. Since we consider uncertain information, the number of
repetitions can help detecting low level errors. We assume that a sequence fU(t)g belongs
to a certain class c if it is accepted by the particular automaton A c representing class c.
In order to understand how such automaton operates, think of this machine as a
cascade of two blocks. The first one has the task of modeling the duration, and provides a
sort of filtering of the input sequence. It produces an instance of a symbol provided that
it is repeated at least for a given number of steps (e.g. if that number of steps is 2, then
processing of "nnmnuumummaaa" would produce "numa"). The second block is simply
a Finite State Automaton (FSA), and represents the basic knowledge we assume on the
problem. We notice that, unlike the above mentioned FSA, the cascade of the two blocks
may be regarded as a nondeterministic automaton [19].
In this section we demonstrate how such automaton rules can be realized by net-work
(1) in terms of weight boundaries. This turns out to be very useful for integrating
these rules with learning by example [7].
The first step is to choose a proper coding of the automaton states by means of the
boolean states x b
i (t) of neurons in the recurrent network (1). We assume that, for each pair
of present and next-state of the FSA, the Hamming distance between the corresponding
codifications is one. Thereafter, for each neuron i it is straightforward to derive the set
R i of neuron switching rules from the automaton rules. For each rule r 2 R i we denote
3 with x b
i;r and - x b
i;r respectively the present and the next boolean state of neuron i. The
neuron switching rules are implemented by using the results contained in Theorem 1. Let
~
be a vector of weights such that rules R i hold. The input to neuron i,
fulfilling rule r is:
I i;r ( ~
~
~
3 In the sequel, the index t may be omitted for the sake of simplicity.
Because of the coding assumption, I i is constant during the state transition. As a result
we can directly apply Theorem 1, and then the following linear constraints on the weights
must hold:
i;r I i;r ( ~
where oe a boolean state switching is required, otherwise oe \Gamma1. For example,
let us consider a rule r which requires a low to high switching for the boolean state of
neuron i. In this case - x b
equation (12) becomes I i;r ( ~
according to theorem 1's result.
Equations (12) are in the framework of linear programming. A feasible solution is
a point ~
W i of the weight space which lies in the convex region bounded by the set of
hyperplanes H i;r (W i
Any solution of (12) satisfies the requirements arisen from the FSA. It is important to
remember that each network state transition in ( 1) may need more than one step, and
that the number of these steps depends strictly on the relationship between I i and I
This fact is shown clearly in Table 1.
These considerations make it clear that the evaluation of a region in the weight space in
which the automaton rules are valid is very important. A parametric weight representation
of this space is quite difficult to achieve. Although more restrictive, a spherical subset of
this space can be easily determined by changing equations (12). The basic idea relies on
the computation of the distance d i;r between the weight solution ~
W i and the hyperplanes
This distance can be written as:
i;r I i;r ( ~
c r
We can put together equations (12) and (13) to setup the following optimization problem,
which can still be solved in the framework of linear programming.
ffl By solving, for each neuron i, the following set of equations:
i;r I i;r ( ~
we obtain the optimal spherical regions in the weights space, having center coordinates
~
The above described procedure is referred to as K algorithm. The recurrent network
(1), with the weights belonging to that spheres, is actually a nondeterministic automaton
[19]. Once the weights are specified, this automaton becomes deterministic. In section
.
(b)
Input symbol
Neuron i
(a)

Figure

2: a) Chain automaton of example; b) neural implementation.
IV the determination of these weights will be proposed by using supervised learning.
Example
Let us consider a very simple automaton with ordered states having a chain structure
(see fig. 2a). Basically from each state only a transition to the next-state is permitted.
The generic state S i is coded as follows:
The neural realization can be based on a recurrent network composed of dynamic neurons
with w ii ? 2. It is worth mentioning that, because of the particular codification adopted,
the network of fig. 2b can be used, instead of a full connected net. Equations (12) for
this case follows: 8
\Gammaw
An exclusive binary coding is chosen for the inputs and each neuron only receives one bit
of the input coding. We can determine the maximum sphere included in the weight space
by solving equations (14) in terms of W i
We found that the sphere had a
radius ae with center in ~
. The latching condition was imposed
by choosing w
IV Integration of rules and learning
NO
Output network
Inputs
rules
Learned
rules
A priori

Figure

3: K-L network.
As shown in the previous section, the neural realization of the nondeterministic automaton
leads to a network whose weights belong to specific regions of the weight space. The choice
of a particular point in that space is associated with the modeling of symbol duration.
Moreover, we must remember that the explicit knowledge, defined by the automaton, is
based on the input quantization. If the information is conveyed by a continuous signal,
then the quantization just represents an approximated view of the original problem. We
can model the duration by using a supervised learning scheme, based on presentation
of examples. That learning scheme can also prove useful for dealing with the continuous
nature of the input information. In many problems, however, the priori-knowledge injected
into the network connections may limit the possibility of learning new rules not specified in
the explicit model. For this reason, we propose the K-L (priori-Knowledge and Learning)
architecture shown in fig. 3, which is based on two cooperating subnets, NK and NL ,
devoted to explicit and learned rule representation, respectively. A third subnet NO takes
as input a subset of NK and NL neurons and provides the external output. In the simplest
case NO consists of just a single output neuron (see for example section V).
The weights of the first subnet NK are quickly initialized thanks to the method shown
in section III, which permits to begin learning from a configuration that already represents
the problem explicit knowledge. Learning the uncertain information is mainly
accomplished by the second subnet of the K-L architecture. It is a full-connected recurrent
network, randomly initialized, which has the task of discovering hidden rules.
The weights optimization is carried out by means of a modified version of Pearlmutter's
learning algorithm [16], adapted for discrete time. A formal definition of the procedure
may be found, for example, in [23]. The algorithm has to discover a solution which
optimizes the cost function:
i2NO
where the flag oe i means that a supervision request takes place on neuron i at time
t, and T is the length of the input sequence. Ordinary gradient descent is accomplished in
order to optimize all the weights. A relevant difference is that NK weights are constrained
in the spherical region described in section III, which guarantees that the automaton rules
are not destroyed.
In the proposed model, learning by example is essentially conceived as a refinement
process and it is relieved from the problem of discovering complex deterministic rules. In
these cases the only use of learning by example paradigm is likely to fail because of the
presence of local minima. These failures can be understood in the framework of complexity
theory, where, at least for feedforward nets, it has been proven that the loading problem
is NP-complete [12].
A particular class of automata, and consequently of recurrent nets, is of interest for
the application we are going to propose. In the following these nets are referred to as
chain-like nets. In the next section we discuss of chain-like nets bearing in mind their
application to speech recognition.
V Applications to automatic speech recognition
In order to validate our theoretical hypotheses and to better understand the proposed
model, we carried out several preliminary experiments of automatic speech recognition.
One of our primary goals, for applications in this area, is that of demonstrating the
capability of the proposed model to deal with isolated word recognition (IWR) in large
lexicons. So far, many attempts to build neural-based classifiers for (IWR) have assumed
"small" lexicons (see e.g.: [4, 13, 17]). Neural classifiers have succeeded in problems of
acoustic feature extraction, but have not exhibited significant results for applications to
large lexicons. Basically, this is due to the intrinsic limitations of all the methods which
only rely on learning by examples. Although some solutions have been proposed for
building modular architectures [21, 13], the scaling up to large lexicons appears to a be
a very serious problem. In order to overcome these difficulties, we propose to model each
word of a given dictionary with a K-L net. Each one must detect the word for which it
is built, and reject all the other words of the dictionary. During the recognition phase,
any word to be recognized is presented at all the nets. Simple decision criteria, such as
choosing the highest output value, can be used for performing word prediction.
An Experiment of isolated word recognition
Henceforth, we propose an experiment for discriminating 10 Italian words only composed
of vowels and nasals. In order to accomplish this task, we selected a hierarchical network
architecture in which a first net N P was devoted to perform phoneme hypotheses, while
A
A
A
A
U
A
U

Figure

4: Automaton devoted to detect the Italian word /Numa/. The table shows the
codification of the automaton states.
other nets NW i
fed by N P 's outputs, are used for modeling the words, as
indicated in section IV. A detailed description of the phonetic network N P can be found
in [9].
Each net NW i
was devoted to detect a word of the dictionary and the highest network
output criterion was used to perform word prediction. Fig. 5b shows the particular net
chosen for modeling the Italian word /Numa/. The subnet for priori rule representation
had a chain-like structure. It was conceived for representing the automaton of Fig. 4.
For each state, subsequent occurrences of the same phonetic symbol do not produce state
transitions. The automaton is capable of dealing with phoneme skips. It behaves like
a string parser, whose final accepted states are reached only if the right phoneme string
is applied. Basically, automata of this kind solve directly the problem of insertions and
deletions of phonetic symbols, which is very important in IWR.
In practice, we want K-L nets to consider state transitions only after 2 or 3 speech
frames in order to avoid several noisy predictions of phoneme net N P (see fig. 5a and 6a).
This feature is particularly useful to decrease the cross-talk from the other words. Moreover
it should not be forgotten that nets NW i
have to deal with analog values representing
the evidence for a given phoneme.
A full-connected network composed of two neurons was adopted as net NL . We investigated
the effect of learning, particularly on NL 's neurons. As we expected from theoretical
considerations, rules which were not included in NK automaton net were automatically

Figure

5: a) Phoneme outputs for the word /Numa/; b) the network which models the
word /Numa/ when fed with the word /Numa/. Both the input level and the activation
of the neurons are proportional to the gray level (black: high value).

Figure

a) Phoneme outputs for the word /inumano/; b) the network which models the
word /Numa/ when fed with the word /inumano/
learned. For example, this fact can be clearly understood by inspecting the behavior of
the network associated with the word /Numa/ when the words /Numa/ and /inumano/
are presented at its input, respectively. It is worth mentioning that no discrimination between
these words is possible if we consider only the first subnet, since /inumano/contains
/Numa/ as "sub-string". This fact comes out also by inspecting network's state of the
first subnet. However, learning by example makes it possible to develop an internal rep-
resentation, for neurons of the subnet NL , which permits the discrimination of these two
words. A quick glance to fig. 5b and fig. 6b suggests that the word discrimination is
gained thanks to the different information coding created in NL 's neurons. This is an
explicit example that shows how new rules can be discovered which were not included in
the net NK initialized with priori-knowledge. Obviously in this case the discrimination
between these words could be attained also directly by using more complex automata
injected in NK , since the difference is quite explicit. In practice we want the learning
process to develop rules which do not appear explicit or which are affected heavily by
uncertainty.
A preliminary speaker independent small test based on 284 words was performed. The
maximum output decision criterion was adopted. We found a recognition rate as high as
92.3 % [7]. The task is not simple, since the words considered are only composed of vowels
and nasals. We notice that although the dictionary is small (only 10 words), the model
proposed is likely to scale up much better than others suggested in literature [4, 13, 17].
This is mainly due to subnet NK , which only accept acoustic strings corresponding to the
words that it models. It is worth mentioning that if only a learning by example approach
is used for modeling each word, no guarantee at all can be provided to ensure that a given
word net do not reacts to other words.
VI Conclusions
In this paper we propose a novel method for integrating "priori-knowledge" with learning
by example in recurrent networks. We show that the behavior of nondeterministic automata
can be injected into the network's connections. This behavior can be very difficult
to learn by using only the learning by example approach, because of the presence of local
minima. In the proposed model these optimization procedures must not discover the solution
beginning from tabula rasa, but must rather produce a refinement, or to find out
some additional regularities which were not captured by the explicit rules. The preliminary
applications to problems of automatic speech recognition are very promising. Most
importantly, unlike many proposals for IWR with neural nets, the proposed model scales
up very well when increasing the lexicon dimension. Finally, it is worth mentioning that,
although mainly conceived for speech recognition and understanding tasks, this model
can turn out to be useful for other applications as well.



--R

"Approximation of Boolean Functions by Sigmoidal Networks: Part I: XOR and other Two-Variable Functions"
"Speech Pattern Discrimination and Multi-Layered Perceptrons"
"Finite State Automata and Simple Recurrent Networks"
"On the Use of Neural Networks for Speaker Independent Isolated Word Recognition"
"Finding Structure in Time"
"Learning the hidden structure of the speech"
"An Unified Approach for Integrating Explicit Knowledge and Learning by Example in Recurrent Networks"
"Local Feedback Multi-Layered Networks"
"Recurrent Networks for Continuous Speech Recognition"
"BPS: A Learning Algorithm for Capturing the Dynamical Nature of Speech"
"On the Problem of Local Minima in BackPropagation"
Neural Network Design and the Complexity of Learning
"Design of Hierarchical Perceptron Structures and their Application to the Task of Isolated Word Recognition"
Stability of Motion
"A logical calculus of the ideas immanent in nervous activity"
"Learning State Space Trajectories in Recurrent Neural Net- works"
"The Multi-Layer Perceptron as a Tool for Speech Pattern Processing Research"
"Learning internal representation by error propagation"
Formal Languages and Their Relation to Automata
"Phoneme Recognition Using Time-Delay Neural Networks"
"Modularity in Neural Networks for Speech Recognition"
"A Learning Algorithm for Continually Running Fully Recurrent Networks"
"An Efficient Gradient-Based Algorithm for On-Line Training of Recurrent Networks Trajectories"
--TR

--CTR
Ben Choi, Applying Learning by Examples for Digital Design Automation, Applied Intelligence, v.16 n.3, p.205-221, May-June 2002
Christian W. Omlin , C. Lee Giles, Rule Revision With Recurrent Neural Networks, IEEE Transactions on Knowledge and Data Engineering, v.8 n.1, p.183-188, February 1996
Barbara Hammer , Peter Tio, Recurrent neural networks with small weights implement definite memory machines, Neural Computation, v.15 n.8, p.1897-1929, August
Pasquale Foggia , Roberto Genna , Mario Vento, Symbolic vs. Connectionist Learning: An Experimental Comparison in a Structured Domain, IEEE Transactions on Knowledge and Data Engineering, v.13 n.2, p.176-195, March 2001
Steve Lawrence , C. Lee Giles , Sandiway Fong, Natural Language Grammatical Inference with Recurrent Neural Networks, IEEE Transactions on Knowledge and Data Engineering, v.12 n.1, p.126-140, January 2000
Stefan C. Kremer, Spatiotemporal Connectionist Networks: A Taxonomy and Review, Neural Computation, v.13 n.2, p.249-306, February 2001
Michael Berthold , David J. Hand, References, Intelligent data analysis, Springer-Verlag New York, Inc., New York, NY,
automatic speech recognition;recurrent neural networks;learning automata