Simple Strategies to Encode Tree Automata in Sigmoid Recursive Neural Networks.
AbstractRecently, a number of authors have explored the use of recursive neural nets (RNN) for the adaptive processing of trees or tree-like structures. One of the most important language-theoretical formalizations of the processing of tree-structured data is that of deterministic finite-state tree automata (DFSTA). may easily be realized as RNN using discrete-state units, such as the threshold linear unit. A recent result by Sima (Neural Network World7 (1997), pp. 679686) shows that any threshold linear unit operating on binary inputs can be implemented in an analog unit using a continuous activation function and bounded real inputs. The constructive proof finds a scaling factor for the weights and reestimates the bias accordingly. In this paper, we explore the application of this result to simulate DFSTA in sigmoid RNN (that is, analog RNN using monotonically growing activation functions) and also present an alternative scheme for one-hot encoding of the input that yields smaller weight values and, therefore, works at a lower saturation level.
Introduction
During the last decade, a number of authors have explored the use of analog
recursive neural nets (RNN) for the adaptive processing of data laid out as
trees or tree-like structures such as directed acyclic graphs. In this arena,
Frasconi, Gori and Sperduti [5] have recently established a rather general
formulation of the adaptive processing of structured data, which focuses on
directed ordered acyclic graphs (which includes trees); Sperduti and Starita
[18] have studied the classication of structures (directed ordered graphs,
including cyclic graphs) and Sperduti [18] has studied the computational
power of recursive neural nets as structure processors.
One of the most important language-theoretical formalizations of the processing
of tree-structured data is that of deterministic nite-state tree automata
(DFSTA), also called deterministic frontier-to-root or ascending tree
automata[19, 7]. may easily be realized as RNN using discrete-state
units such as the threshold linear unit (TLU). Sperduti, in fact, [17] has recently
shown that Elman-style [3] RNN using TLU may simulate DFSTA,
and provides an intuitive explanation (similar to that expressed by Kremer
[10] for the special case of deterministic nite automata) why this should
also work for sigmoid networks: incrementing the gain of the sigmoid function
should lead to an arbitrarily precise simulation of a step function. We
are, however, unaware of any attempt to establish a nite value of this gain
such that exact simulation of a may indeed be performed by an
analog RNN.
A recent result by
Sma [16] shows that any TLU operating on binary
inputs can be simulated by an analog unit using a continuous activation
function and bounded real inputs. A TLU is a neuron that computes its
output by applying a threshold or step activation function
to a biased linear combination of its binary inputs.
The corresponding analog neuron works with any activation function g(x)
having two dierent nite limits a and b when x ! 1 and for given input
and output tolerances. The constructive proof nds a scaling factor for the
weights |basically, a value for the gain of the analog activation function|
and uses the same scaling factor on a shifted value of the bias. In this
paper, we dene three possible ways of encoding DFSTA in discrete-state
RNN using TLU and then explore the application of  Sma's result to turn
the discrete-state RNN into a sigmoid RNN simulating the original
(with sigmoid meaning an analog activation function that is monotonically
growing). In addition, we present an alternative scheme for analog simulation
that yields smaller weight values than
Sma's scheme for both discrete-state
cases and therefore works at a lower saturation level; our goal is to nd
the smallest possible scaling factor guaranteeing correct behavior. This last
approach, which assumes a one-hot encoding of inputs, is a generalization
of the approach used in [2] for the stable encoding of a family of nite-
state machines (FSM) in a variety of sigmoid discrete-time recurrent neural
networks and similar in spirit to previous work by Omlin and Giles [13, 14] for
deterministic nite automata (a class of FSM) and a particular discrete-time
recurrent neural network (DTRNN) architecture (the second-order DTRNN
used by Giles et al. [6]).
In the following section, tree automata and recursive networks are intro-
duced. Section 3 describes three dierent schemes to encode recursive neural
networks in discrete-state RNN using TLU. The main result by
Sma[16] is
presented in Section 4 together with a similar construction for the case of
exclusive (also called one-hot) encoding of the input. Section 5 describes the
conversion of discrete-state RNN into and their sigmoid counterparts and the
dierent schemes are evaluated by comparing the magnitude of the resulting
weight values. Finally, we present our conclusions in the last section.
Tree automata and recursive neural net-work

Before we explore how neural networks can simulate tree automata we need
to specify the notation for trees and describe the architecture of recursive
neural networks.
2.1 Trees and nite-state machines
We will denote with  a ranked alphabet, that is, a nite set of symbols
with an associated function giving the rank
of the symbol. 1 The subset of symbols in  having rank m is denoted with
. The set of -trees,  T , is dened as the set of strings (made of symbols
in  augmented with the parenthesis and the comma) representing ordered
labeled trees or, recursively,
1.  0   T (any symbol of rank 0 is a single-node tree in  T ).
2.
having a root node with a label of f rank m and m children
which are valid trees of  T belongs to  T ).
1 The rank may be dened more generally as a relation r    N; both formulations
are equivalent if symbols having more than one possible rank are split.
A deterministic nite-state tree automaton (DFSTA) is a ve-tuple
is the nite set of states,
is the alphabet of labels, ranked by function r, F  Q is the
subset of accepting states and is a nite collection of
transition functions of the form -
the maximum rank or valence of the DFSTA.
For all trees t 2  T , the result -(t) 2 Q of the operation of DFSTA A on
a tree t 2  T is dened as
undened otherwise
(2)
In other words, the state -(t) associated to a given tree t depends on the label
of the root node (f) and also on the states that the NDFSTA associates to
its children (-(t 1
By convention, undened transitions lead to unaccepted trees. That is,
M is the maximum number of children for any node of any tree in L(A).
As usual, the language L(A) recognized by a DFSTA A is the subset of
T dened as
One may generalize this denition so that the DFSTA produces an output
label from an
at each node visited, so that it acts
like a (structure-preserving) nite-state tree transducer; two generalizations
are possible, which correspond to the classes of nite-state string transducers
known as Mealy and Moore machines[9, 15]:
Mealy tree transducers are obtained by replacing the subset of accepting
states F in the denition of a DFSTA by a collection of output functions
g, one for each possible rank,
Moore tree transducers are obtained by replacing F by a single output
function whose only argument is the new state:
Conversely, a DFSTA can be regarded as a particular case of Mealy or Moore
machine operating on trees whose output functions return only two values
2.2 Neural architectures
Here we dene two recursive neural architectures that are similar to that
used in related work as that of Frasconi, Gori and Sperduti [5], Sperduti
[17] and Sperduti and Starita [18]. We nd it convenient to talk about
Mealy and Moore neural networks to dene the way in which these networks
compute their output, using the analogy with the corresponding nite-state
tree transducers. The rst architecture is a high-order Mealy RNN and the
second one is a rst-order Moore RNN 2 .
2.2.1 A high-order Mealy recursive neural network
A high-order Mealy recursive neural network consists of two sets of single-layer
neural networks, the rst one to compute the next state (playing the role
of the collection  of transition functions in a nite-state tree transducer)
and the second one to compute the output (playing the role of the collection
of output functions in a Mealy nite-state tree transducer).
The next-state function is realized as a collection of M
single-layer networks, one for each possible rank having nX
neurons and m+1 input ports: m for the input of subtree state vectors, each
2 The remaining two combinations are high-order Moore RNN (which may easily be
shown to have the same computational power as their Mealy counterparts) and rst-order
Mealy machines (which need an extra layer to compute arbitrary output functions, see
of dimensionality nX , and one for the input of node labels, represented by a
vector of dimensionality n U .
The node label input port takes input vectors equal in dimensionality to
the number of input symbols, that is n In particular, if  is a node
in the tree with label l() and u[] is the input vector associated with this
node, the component u k [] is equal to 1 if the input symbol at node  is  k
and 0 for all other input symbols (one-hot or exclusive encoding).
For a node  with label the next state
x[] is computed by the corresponding m+ 1-th order single-layer neural net
as follows:

i represents the bias for the network of rank m and
If  is a leaf, i.e., l() 2  0 the expression above for the component x i []
reduces to

ik
that is, there is a set of jj weights of type w 0
nxk ) which play
the role of the initial state in recurrent networks [4].
The output function is realized as a collection of M
networks having n Y units and the same input structure. The output
function for a node of rank m is evaluated as
2.2.2 A rst-order Moore recursive neural network
The rst-order Moore recursive neural network has a collection of M
next-state functions (one for each rank m) of the form

ik
having the same structure of input ports as its high-order counterpart, and
a single output function of the form

taking nX inputs and producing n Y outputs.
3 Encoding tree automata in discrete-state
recursive neural networks
We will present three dierent ways to encode nite-state recursive transducers
in discrete-state RNN using TLU as activation functions. The rst
two use the discrete-state version of the high-order Mealy RNN described
in Section 2.2.1 and the third one uses the discrete-state version of rst-
order Moore RNN described in Section 2.2.2. The rst two encodings are
straightforward; the third one is explained in more detail.
All of the encodings are based on an exclusive or one-hot encoding of the
states of the nite-state transducers (n the RNN is said to be in
state i when component x i of the nX -dimensional state vector x takes a high
value all other components take a low value In
addition, exclusive encoding of inputs (n outputs (n
used.
Each one of these discrete-state RNN encodings will be converted in Section
5 into sigmoid RNN encodings by using each of the two strategies described
in Section 4.
3.1 A high-order Mealy encoding using biases
Assume that we have a Mealy nite-state tree transducer
Then, a discrete-state high-order Mealy RNN with weights
weights
and bias V m
behaves as a stable simulator for the
nite-state tree transducer (note that uppercase letters are used to designate
weights in discrete-state neural nets). This would also be the case if biases
were set to any value in (0; 1); the value 1=2 happens to be the best
value for the conversion into a sigmoid RNN.
3.2 A high-order Mealy encoding using no biases
A second possible encoding (the tree-transducing counterpart of a string-
transducer encoding described in [12, 2]), which uses no bias, has the next-state
weights
and all biases W m
and the output weights
and all biases V m
(as in the case of the biased construction,
the encoding also works if biases are set to any value in ( 1; 1), with 0 being
the optimal value for conversion into a sigmoid RNN).
3.3 A rst-order Moore encoding
Consider a Moore nite-state tree transducer of the form
Before encoding this DFSTA in a rst-order RNN we need to split its states
rst; state-splitting has been found necessary to implement arbitrary nite-
state machines in rst-order discrete-time recurrent neural networks [8, 1, 2]
and has also been recently described by Sperduti [17] for the encoding of
in RNN.
A easily be shown to be equivalent
to A is easily constructed by using the method described by Sperduti
[17] as follows:
The new set of states Q 0 is the subset of
dened as
The next-state functions in the new set
are dened as follows:
and
where the shorthand notation
has been used.
Finally, the new output function  is dened as follows:
The split encoded into a discrete-state RNN in eqs. (7)
and (8) by choosing its parameters as follows: 3
there exist q 0
jm such that - 0
and zero otherwise;
there exist q 0
and  l such that
i and zero otherwise;
i and zero otherwise;
It is not di-cult to show that the operation of this discrete-state RNN is
equivalent to that of the corresponding therefore to that
of A (as was the case with the previous constructions, dierent values for
the biases are also possible but the ones shown happen to be optimal for
conversion into a sigmoid RNN).
Stable simulation of discrete-state units on
analog units
4.1 Using  Sma's theorem
The following is a restatement of a theorem by  Sma [16] which is included
for convenience. Only the notation has been slightly changed in order to
adapt it to the present study.
3 Remember that uppercase letters are used to denote the weights in discrete-state RNN.
A threshold linear unit (TLU) is a neuron computing its output as
where g H the threshold activation function, the W j (j are real-valued
weights and is a binary input vector.
Consider an analog neuron with weights w having an activation
function g with two dierent limits a = lim x!1 g(x) and
The magnitude - max will be called the maximum input tolerance.
Finally, let also the mapping   be dened as:
undened otherwise
This mapping classies the output of an analog neuron into three categories:
low (0), high (1), or forbidden (undened). Then, let R be the
mapping r - kg.  Sma's theorem states that,
for any input tolerance - such that 0 < - max and for any output tolerance
such that 0 <   -, there exists an analog neuron with activation function
g and weights w R such that, for all x 2 f0; 1g n ,
According to the constructive proof of the theorem [16] a set of su-cient
conditions for the above equation to hold is
a
b a
and
b a
with
where  and  are such that jg(x) aj <  for all x <  and jg(x) bj <  for
all x >  and jj and jj are as small as possible. That is,
Sma's prescription
simply scales the weights of the TLU to get those of the analog network and
does the same with the bias but only after shifting it conveniently to avoid
a zero value for the argument of the activation function.
Note that inputs to the analog unit are allowed to be within - of 0 and 1
whereas outputs are allowed to be within  of a and b. When constructing a
recursive network , the outputs of one analog unit are normally used as inputs
for another analog unit and therefore the most natural choice is
and   -. This choice is compatible, for instance, with the use of the
logistic function g L whose limits are exactly a = 0 and
not with other activation functions such as the hyperbolic tangent
tanh(x). In particular, for the case eqs. (23) and (24) reduce to
and
and (25) becomes
In the following, we rederive simple su-cient conditions for stable simulation
of a TLU by an analog unit which are suitable for any strictly growing
activation function but restricted to exclusive encoding of the input (whereas
Sma's construction is valid for any binary input vector). The simplicity of
the prescriptions allows for an alternate straightforward worst-case analysis
that leads to weights that are, in most common situations, smaller than those
obtained by direct application of  Sma's theorem.
4.2 Using a simple scheme for exclusive encoding of
the input
The conditions for stable simulation of nite-state machines (FSM) in DTRNN
have been studied, following an approach related to that of
Sma[16], by Carrasco
et al. [2] (see also [12, 11]; these conditions assume the special but usual
case of one-hot or exclusive encoding of the input and strictly growing activation
functions. These assumptions, together with a worst-case analysis,
allow one to obtain a prescription for the choice of suitable weights for stable
simulation that works at lower saturation levels than the general scheme
(eqs. 23{25). Usually, the prescription can be realized as a single-parameter
scaling of all of the weights in the TLU including the bias; this scaling is
equivalent to nding a nite value of the gain of the sigmoid function which
ensures correct behavior.
Note that, in the case of exclusive encoding (as the ones used in Section 3,
there are only n possible inputs: the binary vectors b
being the
vector whose i-th component is one and the rest are zero). Therefore, the
argument
may only take n dierent values W 0 +W i
(for the binary input however, the analog neuron
with input tolerance - may receive input vectors in r - (b
ig). This property of exclusive encoding
makes it possible to formulate a condition such that (22) holds for all possible
inputs Two cases have to be distinguished:
1. In this case, (22) holds if
As g is strictly
growing, we may also write w
Obviously, the
minimum value of w
with jg. Therefore,
is a su-cient condition for the analog neuron to simulate the corresponding
TLU with input b i .
2. similar argument leads to
the su-cient condition
For instance, if we choose w
eqs. (29) and (30) are fullled either if
and In order to compare with eqs. (23{25), the last
two conditions may be written as a single, more restrictive pair of conditions
and
The simple choice w not adequate in case that W 0
this case does not appear in any of the encodings proposed in Section 3.
5 Encoding tree automata in sigmoid recursive
neural networks
As mentioned before, the theorem in section (4) leads to the natural choice
in addition to   - when applying it to neurons in recursive
neural networks. Due to its widespread use, we will consider and compare
in this section various possible encodings using the logistic function g
although results for dierent activation functions having
may also be obtained. Indeed, monotonic growth of the
function along the real line is enough for the following derivation (as it was
the case for eqs. (29) and (30)). In our case, we want to simulate a
with a sigmoid RNN.
Consider rst the high-order Mealy RNN architecture. As the input x j
in (22) is, in the case of the RNN described in (4), the product of m outputs
x jm , each one in the range (0; 1), the product is always in
the range (0; (1 In other words, there is a forbidden
region between (1 It is not di-cult to show that
with the equality holding only if
Therefore, the conditions
and - max su-ce for our purposes, as (-; 1 -)
If we want to use the same scaling factor for all weights and all possible ranks
m, we can use
Consider now the rst-order Moore RNN architecture. In this case, there
are no products, and the conditions
and - max are su-cient.
The previous section describes two dierent schemes to simulate discrete-state
neurons taking exclusive input vectors in sigmoid neurons. This section
describes the application of these two schemes to the three recursive neural
network architectures described in Section 2.2.
5.1 Using Sima's prescription
Sma's construction (Section 4.1) gives for the biased high-order Mealy RNN
in Section 3.1 the following:
and, therefore, w m
with
where the condition (35) has been applied 4 , together with 1
a condition that ensures a positive value of H. As shown in (37),
the minimum value allowed for H depends both on nX and . For a given
architecture, nX and the maximum value of m (M) are xed, so only  can
be changed. There exists at least one value of  that allows one to choose the
minimum value of H needed for stable simulation. In this sense, minimization
of H by choosing an appropriate  can be performed as in [2] and leads to
the values shown in Table 1 (minimum required H as a function of nX and
). The weights obtained grow slower than log(mn m
x
as can be seen, are inordinately large and lead therefore to a very saturated
analog RNN.
Applying  Sma's construction to the biasless high-order Mealy RNN (Sec-
tion 3.2), we get
4 We have used equations (4) and (6) have nU (nX ) m terms but, due to
the exclusive encoding of the inputs, (nU 1)(n of terms are identically zero with no
uncertainty at all.
with
together with 1 positive values of H). The weights
obtained by searching for the minimum H satisfying the conditions are shown
in

Table

2; as can be seen, weights (which show the same asymptotic behavior
as the ones in the previous construction) are smaller but still too large to
avoid saturation.
Finally, applying  Sma's construction 5 to the rst-order Moore RNN in
Section 3.3, we have, for a next-state function of rank m,
, and, accordingly, weights are:
there exist q 0
jm such that - 0
and zero otherwise;
there exist q 0
and  l such that
i and zero otherwise
with
(where (36) has been used), together with  < 1
For the output function,
, and
accordingly, weights are
i and zero otherwise;
Sma's construction can be applied provided that we consider each possible W m
ik u k [] in the next-state function as a dierent bias W 0 with u[] 2 f0; 1g n and
choose the safest prescription (valid for all possible values of the bias). In the present
case, this bias has always the value (m 1
(number of additive terms
with
provided that  < 1
where we have used - < .
If we want a single value of H to assign weights both to all of the next-state
functions and the output function, we have to use
with . The weights obtained by searching for the
minimum H satisfying the conditions are shown in Table 3; they grow slower
than log(MnX ), and, as can be seen, they are equal or smaller than the ones
for the biased high-order construction, but larger than those for the biased
construction. However, the fact that state splitting leads to larger values of
nX for automata having the same transition function has to be taken into
account.
5.2 Using the encoding for exclusive inputs
If we choose w including biases we obtain for the
biased high-order Mealy encoding in Section 3.1, by substituting in eqs. (31)
and (32),
together with 1
, which happens to be the same expression
as the one obtained in the previous section by using  Sma's construction
on the biasless encoding (Section 3.2); results are shown in Table 2. The
results for are obviously identical to those reported for second-order
discrete-time recurrent neural networks using the biased construction in [2].
If we instead apply our alternate encoding to the biasless high-order Mealy
construction in Section 3.2 we get
together with 1
suitable minimization of
H, leads to the best possible weights of all encodings. Weights grow with m
and nX slower than log(mn m
some results are shown in Table 4. As in the
previous case, the results for are obviously identical to those reported
for second-order discrete-time recurrent neural networks using no biases in
[2].
Finally, we apply our alternate encoding scheme to the rst-order Moore
construction in Section 3.3. Now
(the particular form of (33) in this case) has to be valid for all combinations
As W 0 can take any value in
and W i can take any value in
the minimum value of jW 0 exclusive values of all
state vectors, equal to 1. Therefore,
together with - < 1
, which, after suitable minimization, leads weights
that grow with m and nX slower than log(mnX ); values are shown in Table 5.
The values are smaller than the ones obtained with  Sma's construction for
the same rst-order network but are still very large, especially if one considers
that splitting leads to very large values of nX .
6 Conclusion
We have studied four strategies to encode deterministic nite-state tree automata
(DFSTA) on high-order sigmoid recursive neural networks (RNN)
and two strategies to encode them in rst-order sigmoid RNN. These six
strategies are derived from three dierent strategies to encode DFSTA in
discrete-state RNN (that is, RNN using threshold linear units) by applying
two dierent weight mapping schemes to convert each one of them into a
sigmoid RNN. The rst mapping scheme is the one described by  Sma[16].
The second one is an alternate scheme devised by us. All of the strategies
yield analog RNN with a very simple \weight alphabet" containing only
three weights all of which are proportional to a single parameter H. The best
results (i.e., smallest possible value of H, as would be desired in a derivative-based
learning setting) are obtained by appling the alternate scheme to a
biasless discrete-state high-order RNN (it has to be mentioned that  Sma's
mapping yields larger weights in all cases but is more general and would
also work with distributed encodings which allow the construction of smaller
RNN). In all of the constructions, the values of H suggest that, even though
in principle RNN with nite weights are able to simulate exactly the behavior
of DFSTA, it will in practice be very di-cult to learn the exact nite-state
behavior from examples because of the very small gradients present when
weights reach adequately large values.
Smaller weights are obtained at the cost of enlarging the size of the RNN
due to exclusive encoding of states and inputs (
Sma's result also works for
distributed encodings).

Acknowledgements

This work has been supported by the Spanish Comision
Interministerial de Ciencia y Tecnologa through grant TIC97-0941.



--R



Finding structure in time.
Learning the initial state of a second-order recurrent neural network during regular-language inference
A general framework for adaptive data structures processing.
Learning and extracted
Syntactical pattern recognition.

Introduction to automata theory
On the computational power of Elman-style recurrent net- works


Constructing deterministic
Stable encoding of large
Formal Languages.

On the computational power of neural networks for struc- tures
Supervised neural networks for the classi
Tree automata: An informal survey.
--TR

--CTR
Barbara Hammer , Alessio Micheli , Alessandro Sperduti , Marc Strickert, Recursive self-organizing network models, Neural Networks, v.17 n.8-9, p.1061-1085, October/November 2004
Barbara Hammer , Peter Tio, Recurrent neural networks with small weights implement definite memory machines, Neural Computation, v.15 n.8, p.1897-1929, August
Henrik Jacobsson, Rule Extraction from Recurrent Neural Networks: A Taxonomy and Review, Neural Computation, v.17 n.6, p.1223-1263, June 2005
neural computation;recursive neural networks;analog neural networks;tree automata