Generalization Ability of Folding Networks.
AbstractThe information theoretical learnability of folding networks, a very successful approach capable of dealing with tree structured inputs, is examined. We find bounds on the VC, pseudo-, and fat shattering dimension of folding networks with various activation functions. As a consequence, valid generalization of folding networks can be guaranteed. However, distribution independent bounds on the generalization error cannot exist in principle. We propose two approaches which take the specific distribution into account and allow us to derive explicit bounds on the deviation of the empirical error from the real error of a learning algorithm: The first approach requires the probability of large trees to be limited a priori and the second approach deals with situations where the maximum input height in a concrete learning example is restricted.
Introduction
One particular problem of connectionistic methods dealing with structured objects is to find a
possibility which makes the processing of data with a priori unlimited size possible. Connectionistic
methods often use a distributed representation of the objects in a vector space of some fixed
dimension, whereas lists, trees, logical formulas, terms, graphs, etc. consist of an unlimited number
of simple elements which are connected in a structured way. The possibly unlimited size does not
admit a direct representation in a finite dimensional vector space. Often, structured data possesses a
recursive nature. In this case processing these structures is possible with standard neural networks
which are enlarged by recurrent connections which mimic the recursive nature of the structure
[9, 10]. Such networks are capable of dealing with trees or lists of arbitrary height and length, for
example. This dynamics have been proposed in a large number of approaches dealing with adaptive
processing of structured data as the RAAM, the LRAAM, and folding networks to name just a few
[11, 24, 28]. The methods differ in how a single processing step looks and how they are trained but
they share the method of how an entire tree is processed: A simple mapping is applied recursively
to the input tree according to the tree structure. A tree is encoded recursively into a distributed
representation such that this code can be used in standard connectionistic methods. Regarding
folding networks the encoding is trained simultaneously with some classification of the trees which
is to be learned using a modification of back-propagation [11]. This approach has been used very
successfully in several areas of application [7, 11, 21, 22, 25]. The RAAM and LRAAM train the
encoding simultaneously with a dual decoding such that the composition yields the identity [24, 28].
The classification of the encoded trees is trained separately.
Here we focus on the capability of learning with these dynamics in principle. We consider
information theoretical learnability, i.e. the question as to whether a finite number of examples
contains enough information for learning: Given a finite set of data, a function with the above
dynamics can be identified which mirrors the underlying regularity - or it can be decided that the
underlying regularity if any cannot be modeled with such a function. This is the question as to
whether valid generalization from a finite set of examples to the underlying regularity is possible in
the function class. For standard feed-forward networks this question is answered in the affirmative:
Because a combinatorial quantity called the VC dimension is finite for a fixed architecture so-called
PAC learnability can be guaranteed, moreover, any learning algorithm with small empirical error
generalizes well. One can find explicit bounds on the accuracy of the generalization which depend
on the number of parameters and the number of training patterns but which are independent of
the concrete distribution [3].
In order to use folding networks as a learning mechanism it is necessary to establish analogous
results in the recurrent case, too. If the question whether valid generalization with such an architecture
is possible is answered negatively then none of the above approaches can learn in principle.
If the question is answered positively then any learning algorithm with small empirical error is
a good learning algorithm from an information theoretical point of view. Of course there may
exist differences in the efficiency of the algorithms - some algorithm may turn out computationally
intractable whereas another approach yields a good solution after a short time. However, this is
mainly a difference in the empirical error optimization. The number of examples necessary for valid
generalization at least in some cases depends on the function class which is used for learning and
not on the learning algorithm itself.
Unfortunately the situation turns out to be more difficult in the recursive case than for standard
feed-forward networks. There exists some work which estimates the VC dimension of recurrent and
folding networks [14, 19], the combinatorial quantity finiteness of which characterizes distribution
independent learnability. For arbitrary inputs this dimension is infinite due to the unlimited input
length. I.e. the ability of dealing with inputs of arbitrary size even leads to the ability of storing
arbitrary information with a finite number of parameters since the unlimited input space can be
used for this purpose in some way. As a consequence, distribution independent bounds on the
generalization error cannot exist in these situations. In order to take the specific distribution into
account we modify two approaches from the literature which guarantee learnability even for infinite
VC dimension but an adequate stratification of the function class instead [2, 27]. These approaches
are only formulated for binary valued function classes and consider the generalization error of an
algorithm with zero empirical error. We generalize the situation to function classes and arbitrary
error such that it applies to folding networks and standard learning algorithms as well. This allows
us to establish the information theoretical learnability of folding networks, too.
Now we first define the dynamics of folding networks formally. We mention some facts from
learning theory and add the above mentioned two formalisms which allow us to obtain concrete
bounds for the deviation of the empirical error and the real error in some concrete situations.
Estimations for the so-called VC, pseudo-, and fat shattering dimension of folding architectures
These quantities play a key role concerning learnability. The bounds tell us that distribution
independent learnability cannot be guaranteed in principle. But we derive concrete distribution or
data dependent bounds for the generalization error.
Folding networks
For completeness we recall the definition of a standard feed-forward network: A feed-forward
neural network consists of a finite set of neurons which are connected in an acyclic
graph. Each connection equipped with a weight w ij 2 R. The input neurons
are the neurons without predecessor. All other neurons are called computation units. A nonempty
subset of the computation units is specified, the output units. All computation units, which are
not output neurons, are called hidden neurons. Each computation unit i is equipped with a bias
and an activation function inputs and n outputs computes
the function
are the output units and defined recursively for any neuron i as
ae x i if i is an input unit,
The term
is called the activation of neuron i.
An architecture is a network where the weights and biases are not specified and allowed to
vary in R. In an obvious way, an architecture stands for the set of networks that results specifying
the weights and biases. As a consequence, a network computes a mapping which is composed
of several simple functions computed by the single neurons. The activation functions f i of the
single computation units are often identical. We drop the subscript i in these cases. The following
activation functions will be considered: The identity id the perceptron
activation
ae
the standard sigmoidal function
polynomial activation functions.
Feed-forward networks can handle real vectors of a fixed dimension. More complex objects are
trees with labels in a real vector space. We will assume in the following that any tree has a fixed
fan-out k, which means that any nonempty node has exactly k successors. Consequently, a tree is
either the empty tree ? or it consists of a root which is labeled with some value a
subtrees t 1 , . , t k . In the latter case we denote the tree by a(t The set of trees which
can be defined as above is denoted by (R m )
k .
One can use the recursive nature of trees to construct an induced mapping which deals with
trees as inputs from any vector valued mapping with appropriate arity: Assume R l is used for the
encoding, the labels are taken from R m . Any mapping g : R m \Theta R k \Deltal ! R l and initial context y 2 R
induce a mapping ~
l , which is defined recursively as follows:
~
~
This definition can be used to formally define recurrent and folding networks:
folding network consists of two feed-forward networks which compute the functions
respectively, and an initial context y 2 R l . It computes the
mapping
A folding architecture is given by two feed-forward architectures with inputs and l
outputs and with l inputs and n outputs, respectively. The context y is not specified, either.
The input neurons m+ 1, . , m+ k \Delta l of g are called context neurons. g is referred to as the
recursive part of a network, h is the feed-forward part. The input neurons of a folding network
or architecture are the neurons 1, . , m of g. In the following we will assume that the network
contains only one output neuron in h.
To understand how a folding network computes a function value one can think of the recursive
part as an encoding part: A tree is encoded recursively into a real vector in R l . Starting at the
empty tree ?, which is encoded by the initial context y, a leaf encoded via g by
using the code of ?. Proceeding in the same way, a subtree a(t
y
y
y
y
y
y
y
d
a
c
e
f
c
f
a
recurrence
context-
neurons
recurrent part feed-forward part
input of the tree leads to
the computation

Figure

1: Example for the computation of a folding network: If a specific tree serves as input the
network is unfolded according to the structure of the input tree and the output value can be simply
computed in this unfolded network.
via g using the already computed codes of the k subtrees t 1 , . , t k . The feed-forward part maps
the encoded tree to the desired output value. See Fig. 1 as an example for a computation.
lists are dealt with, folding networks reduce to recurrent networks. Except
for the separation in feed-forward and recurrent part this definition coincides with the standard
definition of partial recurrent neural networks in the literature [12].
In practice, recurrent and folding networks are trained with a gradient descent method like
back-propagation through structure or back-propagation through time, respectively [11, 30]. They
have been used successfully in several areas of application including time series prediction, control
of search heuristics, and classification of chemical data and graphical objects [7, 22, 25].
A similar mechanism proposed for the processing of structured data is the LRAAM. It is possible
to define in analogy to the encoding function ~ g y for any mapping
\Deltal and set Y ae R l an induced decoding -
k where
ae
That means a complementary dynamics decodes a value t recursively in order to obtain the label
of the root via G 0 and codes for the k subtrees via G 1 , . , G k .
Definition 2 The LRAAM consists of two feed-forward networks which compute g : R m+k \Deltal ! R l
respectively, and some vector y 2 R l and some set Y ae R l . It computes the
mapping
Frequently, the LRAAM is used in the following way: One chooses fixed architectures for the
networks g and G and trains the weights such that the composition -
y yields the identity
on the considered trees. Afterwards, -
G Y or ~ g y can be combined with standard networks in order
to approximate mappings from trees into a real vector space or vice versa. In the second step,
the feed-forward architectures are trained while the encoding or decoding of the LRAAM remains
fixed.
Although the LRAAM is trained in a different way the processing dynamics is the same if it
is used for the classification of structured data: The encoding part of the LRAAM is combined
with a standard network which is trained for the specific learning problem. Considering the entire
process, we obtain the same function class as represented by folding networks if we restrict to
the learning of functions from trees into a real vector space. Hence the following argumentation
applies to the LRAAM and other mechanisms with the same processing dynamics as well. However,
the situation changes if we fix the encoding and learn only the feed-forward network which is to
be combined with the neural encoding of the LRAAM. Then the situation reduces to learning of
standard feed-forward networks because the trees are identified with fixed real input vectors.
3 Foundations from learning theory
Learning deals with the possibility of learning an abstract regularity if a finite set of data is given.
We fix an input space X (for example, the set of lists or trees) which is equipped with a oe-algebra.
We fix a set F of functions from X to [0; 1] (a network architecture, for example). An unknown
is to be learned with F . For this purpose a finite set of independent,
identically distributed data drawn according to a probability distribution P on
X.
A learning algorithm is a mapping
(X \Theta [0; 1])
which selects a function in F for any pattern set such that this function - hopefully - nearly coincides
with the function that is to be learned. We write hm (f; x) for hm That
is, the algorithm tries to minimize the real error d P (f; hm (f; x)) where
d P (f;
Z
Of course, this error is unknown in general since the probability P and the function f that is to be
learned are unknown. A concrete learning algorithm often simply minimizes the empirical error
dm (f; hm (f; x); x) where
dm (f;
For example, a standard training algorithm for a network architecture fits the weights by means of
a gradient descent on the surface representing the empirical error in dependence on the weights.
We first consider the distribution dependent setting, i.e. there is given a fixed probability distribution
P on X. An algorithm is called probably approximately correct or PAC if
sup
holds for all ffl ? 0. This is the weakest condition such that the following holds: bounds for
the number of examples which guarantee valid generalization exist for some learning algorithm
and these bounds are independent of the unknown function that is to be learned. In practice a
somewhat stronger condition is desirable: The existence of just one maybe inefficient algorithm
is not satisfactory, we want to use any learning algorithm which is efficient and yields a small
empirical error. The property that for any learning algorithm the empirical error is representative
for the real error is captured by the property of uniform convergence of empirical distances
or UCED for short, i.e.
dm (f;
holds for all ffl ? 0. If F possesses the UCED property then any learning algorithm with small
empirical error is highly probably a good algorithm concerning the generalization. The UCED
property is desirable since it allows us to use any algorithm with small empirical error and to rank
several algorithms in dependence on their empirical errors.
The quantity ffl is referred to as the accuracy. If the above probability is explicitly bounded
by some ffi we refer to ffi as the confidence. Then there exists an equivalent characterization of
the UCED property which allows us to test the property for concrete classes F and, furthermore,
allows us to derive explicit bounds on the number of examples such that the empirical and real
error deviate by at most ffl with confidence at least ffi.
For a set S with pseudometric d the covering number N(ffl; d) denotes the smallest number
n such that n points x 1 , . , x n in S exist such that the closed balls with respect to d with radius
ffl and center x i cover S. Now a characterization of the UCED property is possible. The UCED
property holds if and only if
lim
dm )))
where F jx denotes the restriction of F to inputs x and -
dm refers to the empirical distance. An
explicit bound on the deviation of the empirical error and the real error is given by the inequality
f;g2F
jd P (f;
dm (f;
See [29](Example 5.5, Corollary 5.6, Theorem 5.7).
Now we need a possibility of estimating the so-called empirical covering number of F which
occurs in the above inequality. Often this is done estimating a combinatorial quantity associated
with F which measures in some sense the capacity of the function class. We first assume that F
is a concept class, i.e. the function values are contained in the binary set f0; 1g. The Vapnik-Chervonenkis
dimension or VC dimension VC(F) of F is the largest number of points which
can be shattered by F , i.e. any binary mapping on these points can be obtained as a restriction of
a function in F . For a real valued function class F the ffl-fat shattering dimension fat ffl (F) is the
largest size of a set that is ffl-fat shattered by F , i.e. for the points x 1 , . x n there exist reference
points r 1 , . , r n 2 R such that for any binary mapping d on these x i some function f 2 F exists
with for every i. For
quantity is called the pseudodimension PS(F).
For holds that
for an arbitrary P [29] (Theorem 4.2). Consequently, finite VC or pseudodimension, respectively,
ensure the UCED property to hold and bounds on these terms lead to bounds on the number of
examples that guarantee valid generalization. Moreover, they ensure the distribution independent
UCED property as well, i.e. the UCED property holds even if prefixed with a sup P . The fat
shattering dimension which may be smaller than the pseudodimension yields the inequality
even a finite fat shattering dimension guarantees the distribution
independent UCED property and leads to bounds on the generalization error. In the following we
assume that the constant function 0 is contained in F . This is usually the case if F is a function
class computed by a folding architecture. It has been shown that finiteness of the VC dimension if
F is a concept class or finiteness of the fat shattering dimension if F is a function class, respectively,
is even necessary for F to possess the distribution independent UCED property [1, 18]. In general,
only the class of so-called loss functions which is correlated to F has a finite fat shattering dimension
if F possesses the UCED property. However, if the constant function 0 is contained in F the class
of loss functions contains F itself, such that F has a finite fat shattering dimension as well.
Because of the central role of these combinatorial quantities we will estimate the VC and fat
shattering dimension of a folding architecture in the next paragraph. It will turn out that they are
infinite in general. In order to ensure the UCED property the above argumentation needs to be
refined. Fortunately, the input space X can be divided as
are the trees of
height at most t in the case of a folding architecture and the VC dimension of the architecture is
finite if restricted to inputs in X t . This allows us to derive bounds if the probability of high trees
is restricted a priori. For this purpose we will use the following theorem.
Theorem 3 Assume F is a function class with inputs in X and outputs in [0; 1]. Assume
is measurable for any t 2 N and X t ae X t+1 . Assume P is a probability measure
on X, ffl; ffi 2 [0; 1], and t is chosen such that p
f;g2F
jd P (f;
dm (f;
for
is finite this holds even for
Proof: We can estimate the deviation of the real error and the empirical error by
dm (f;
at most m(1 \Gamma ffl=4) points in x are contained in X t )
where P t is the probability induced by P on X t and m This holds because d P differs
from d P t by at most 3ffl=8. If a fraction ffl=4 is dropped in x then -
dm changes by at most ffl=2. Using
the Chebychef inequality we can limit the first term by
As mentioned earlier the second term can be limited by
The expected covering number is limited by' 512e
The entire term is limited by ffi for
"oe
or
respectively 2
However, it is necessary to know the probability of high trees a priori in order to get bounds
on the number of examples which are sufficient for valid generalization. This holds even if the
maximum input height of the trees in a concrete training set is restricted and therefore it is not
very likely for larger trees to occur. Here the luckiness framework [27] turns out to be useful. It
allows us to substitute the prior bounds on the probability of high trees by posterior bounds on
the maximum input height. Since we want to get bounds for the UCED property we generalize the
approach of [27] to function classes in the following way:
Assume that F is a [0; 1]-valued function class with inputs in X and
is a function, the so-called luckiness function. This function measures some quantity, which
allows a stratification of the entire function class into subclasses with some finite capacity. If L
outputs a small value, we are lucky in the sense that the concrete output function of a learning
algorithm is contained in a subclass of small capacity which needs only few examples for correct
generalization. In our case it will simply measure the maximum height of the input trees in a
concrete training set. Define the corresponding function
which measures the number of functions that are at least as lucky as f on x. Note that we are
dealing with real outputs, consequently a quantization according to some value ff of the outputs is
necessary to ensure the finiteness of the above number: F ff refers to the function class with outputs
in f0; ff; which is obtained if all outputs of f 2 F in [kff \Gamma ff=2; kff + ff=2[ are identified
with kff for k 2 N. The luckiness function L is smooth with respect to j and \Phi, which are both
mappings N \Theta (R
indicates that a fraction deleted in x and in y to obtain
x 0 and y 0 . This is a technical condition which we will need in the proof. The smoothness condition
allows us to estimate the number of functions which are at least as lucky as g on a double sample
xy (or a large part of it) if we only know the luckiness of g on the first half of the sample x. Since
in a lucky situation the number of functions which are to be considered is limited and hence good
generalization bounds can be obtained, this condition characterizes some kind of smoothness if we
enlarge the sample set. It is a stronger condition than the smoothness requirement in [27] because
the consideration is not restricted to functions g that coincide on x. Since we want to get results
for learning algorithms with small empirical error, but which are not necessarily consistent, this
generalized possibility of estimating the luckiness of a double sample knowing only the first half is
appropriate in our case.
Now in analogy to [27] we can state the following theorem which guarantees some kind of UCED
property if the situation has turned out to be lucky in a concrete learning task. For this purpose the
setting is split into different scenarios which are more or less lucky and occur with some probability
. Depending on the concrete scenario generalization bounds can be obtained.
Theorem 4 Suppose p t (t 2 N) are positive numbers with
and L is a luckiness function
for a class F which is smooth with respect to j and \Phi. Then the inequality
is valid for any learning algorithm h, real values ffi, ff ? 0, and
ffl(m; t; ffi;
s
Hence if we are in a lucky situation such that \Phi can
be limited by some 2 t 0 +1 , the deviation of the real error from the empirical error can be limited by
some term of order O
with high probability.
Proof: For any f 2 F we can bound the probability
which is fulfilled for ffl as defined above [29] (Theorem 5.7, step 1). It is sufficient
to bound the probability of the latter set for each single t by (p t ffi )=2. Intersecting such a set
for a single t with a set that occurs at the definition of the smoothness of l and its complement,
respectively, we obtain the bound
Denote the above event by A. Consider the uniform distribution
U on the group of permutations in that only swap elements
j. Thus we have
R
where x oe is the vector obtained by applying the permutation oe [29] (Theorem 5.7, step 2). The
latter probability can be bounded by
sup xy
is the length of x 0 and y 0 . f ff denotes the quantized version of f , where outputs
in are identified with kff. Now denote the event of which the probability U is
measured by B, and define equivalence classes C on the permutations such that two permutations
belong to the same class if they map all indices to the same values unless x 0 and y 0 both contain
this index. We find that
If we restrict the events to C we definitely consider only permutations which swap elements in x 0
and y 0 such that we can bound the latter probability by
where U 0 denotes the uniform distribution on the swappings of the common indices of x 0 and y 0 .
The latter probability can be bounded using Hoeffding's inequality for random variables with values
in f\Sigma(error on x 0
by the term
In total, we can therefore obtain the desired bound if we choose ffl such that
jm
which is fulfilled for
r
:Note that the bound ffl tends to 0 for are decreasing, j in such a way
that becomes small. Furthermore, we have obtained bounds on the difference between the
real and empirical error instead of dealing only with consistent algorithms as in [27]. We have
considered functions instead of concept classes which causes an increase in the bound by ff due to
the quantization, and a decrease in the convergence because we have used Hoeffding's inequality in
the function case.
Furthermore, a dual formulation with an unluckiness function L 0 is possible, too. This corresponds
to a substitution of - by - in the definition of l; the other formulas hold in the same
manner. We will use the unluckiness framework later on.
Generalization ability of folding networks
We want to apply the general results from learning theory to folding networks. For this purpose
we first estimate the combinatorial quantities VC(F jX t ), PS(F jX t ), and fat ffl
folding architecture F which is restricted to the set X t of input trees of height at most t. Denote by oe
the activation function of the architecture, by W the number of adjustable parameters, i.e. weights,
biases, and components of the initial context, by N the number of neurons, and by h the depth of
the feed-forward architecture which induces the folding architecture, i.e. the maximum length in a
path of the graph defining the network structure. Upper bounds on the VC or pseudodimension
d t of F jX t can be obtained by first substituting each input tree by an equivalent input tree with
a maximum number of nodes, unfolding the network for these inputs, and applying the bounds
from the feed-forward case to these unfolded networks. For details see [14, 15]. This leads to the
following bounds some of which can be found in [8, 14, 19]
O(W ln(th)) if oe is linear,
O(W th ln d) if oe is a polynomial of degree d - 2,
O(WN +W ln(W t)) if
2:
Note that the bounds do not differ for a polynomial activation function and
respectively. Some lower bounds can be found in [8, 14, 19]
oe is a nonlinear polynomial,
Since a standard feed-forward perceptron architecture exists
points and the
sigmoidal function can approximate the perceptron activation arbitrarily well we can combine
the architecture in the sigmoidal case with this feed-forward architecture to obtain an additional
summand
in the lower bounds for sgd. The detailed construction is described in
[14] (Theorem 11). The following theorem yields a further slight improvement in the sigmoidal
case.
Theorem 5 For an input set (R 2 )
sgd an architecture exists shattering
Proof: We restrict the argumentation to the case 2. Consider the t(t trees of depth
which contain all binary numbers
to
of length t in the first component
of the labels of the leaves, all binary numbers of length in the labels of the next layer, . ,
the numbers 0 and 1 in the first layer, and the number 0 in the root. In the tree T ij (i 2
the second component of the labels is 0 for all except one layer
is 1 at all labels where the already defined coefficient has a 1 as the jth digit. t 2;1 is the tree
(0; 0)((0; 0)((00; 0); (01; 0)); (1; 0)((10; 1); (11; 1))) if the depth t
The purpose of this definition is that the coefficients which enumerate all binary strings are
used to extract the bits number 1, . , t(t + 1)=2 in an efficient way from the context vector: We
can simply compare the context with these numbers. If the first bits correspond, we cut this prefix
by subtracting the number from the context and obtain the next bits for the next iteration step.
The other coefficient of the labels specify the digit of the context vector which is responsible for the
input tree T ij , namely the digit. With these definitions a recursive architecture
can be constructed which just outputs for an input T ij the responsible bit of the initial context and
therefore shatters these trees by an appropriate choice of the initial context.
To be more precise, the architecture is induced by the mapping f
0:1
which leads to a mapping which computes in the third component the responsible bit of y for T ij with
an initial context 0). The role of the first context neuron is to store
the remaining bits of the initial context, at each recursive computation step the context is shifted by
multiplying it by y 2 and dropping the first bits by subtracting an appropriate label of the tree in the
corresponding layer. The second context neuron computes the value 10 height of the remaining tree .
Of course, we can substitute this value by a scaled version which is contained in the range of sgd.
The third context neuron stores the bit responsible for To obtain an output 1 the first bits of
an appropriate context have to coincide with a binary number which has an entry 1 at the position
that is responsible for the tree. This position is indicated by x 2 . f can be approximated arbitrarily
well by an architecture with the sigmoidal activation function with a fixed number of neurons. It
shatters trees.
Now we combine W of these architectures obtaining an architecture shattering W t(t
trees with O(W ) weights. This proceeds by first simulating the initial context with additional
weights, and adding W of these architectures, which is described in [14] (Theorem 11) in detail.
The additional summand W ln W can be obtained as described earlier. 2
Unfortunately, this lower bound still differs from the upper bound by an exponential term in t.
Nevertheless it is interesting due to the following reason: The bounds in the linear or polynomial
case do not differ comparing 2. In the sigmoidal case the 'real upper bound' is
expected to be of order WN t for But the lower bound we obtained is of order t 2
consequently, the capacity increases for tree structured inputs in the sigmoidal case
compared to lists in contrast to the linear or polynomial case.
For all activation functions the bounds become infinite if arbitrary inputs are allowed. For the
perceptron activation function this can be prohibited by restricting the inputs to lists or trees with
nodes in a finite alphabet [19]. In general one could restrict the absolute values of the weights
and inputs and consider the fat shattering dimension instead of the pseudodimension. This turns
out to be useful when dealing with the SVM or ensembles of networks, for example [4, 13, 27].
Unfortunately, even if the activation function coincides with the identical function a lower bound
\Omega\Gammaun ln t) can be found for the fat shattering dimension and restricted weights and inputs [15]. For
the sigmoidal activation a lower
can be found for the fat shattering dimension [15].
The following theorem generalizes this result to a large number of activation functions.
Theorem 6 For any activation function oe which is twice continuously differentiable with non-vanishing
second derivative in the neighborhood of at least one point we obtain the lower bound
fat 0:1 recurrent architecture F with 3 computation neurons with activation
function oe in the recursive part and one linear neuron in the feed-forward part, input lists with
entries in a unary alphabet, and weights restricted by some constant which depends on the activation
function oe.
Proof: The function
has the property
for any x. Therefore the function class f ~
0:1-shatters all sets of sequences with
mutually different length. Starting with the longest sequence in some set and a value in ]0:1; 0:4[
or ]0:6; 0:9[, respectively, corresponding to the desired output of the sequence, one can recursively
choose an inverse image in ]0:1; 0:4[ or ]0:6; 0:9[ because of ( ) in order to get outputs for shorter
sequences and, finally, an appropriate initial context y. Since even ]0; 1[ is entirely contained in
0:9[) the same holds for any continuous function which differs from
f by at most 0:1.
oe is twice continuously differentiable with non-vanishing second derivative in the neighborhood
of at least one point, consequently, points x 0 and x 1 and ffl ? 0 exist with
and
with a maximum deviation of 0:007 for any y 2 [0:1]. Consequently, g(x;
differs from f(x; y) by at most 0:1 for any input y from [0; 1]. Hence f~g y j y 2]0; 1[g shatters all
sequences with mutually different length as well.
g can be implemented by a folding network without hidden layers, 3 context neurons and
activation function oe in the recursive part, and one linear neuron in the feed-forward part, and
some context in a closed set which depends on the activation function oe. This holds because
g is a linear combination of neurons with activation function oe and a constant. The identity
holds for any mappings A and f 1 of appropriate arity, vectors
Therefore the linear mapping in g can be integrated in
the network structure. Except for the initial context which is to be chosen in a compact set the
weights in the architecture are fixed for any set to be shattered and only depend on the activation
function oe. 2
Hence the distribution independent UCED property does not hold and a fixed folding architecture
is not distribution independent PAC learnable under realistic condition for a large number
of activation functions including the standard sigmoidal function. This fact does not rely on the
learning algorithm which is used but is a characteristic of the function class. Because it is possible
to deal with inputs of arbitrary size this unlimited size can be used to store in some sense all
dichotomies of the inputs. Regarding the above argumentation the situation is even worse. The
architecture is very small and only uses the different length of the inputs. In particular, training
sets which typically occur in time series prediction are shattered, i.e. a table-lookup is possible on
those inputs.
However, it is shown in [14] that distribution dependent PAC learnability is guaranteed. More-
over, the arguments from the last section allow us to derive bounds on the deviation of the empirical
error from the real error for any learning algorithm.
Corollary 7 Denote by F a fixed folding architecture with inputs in X and by X t the set of trees
of height at most t. Assume P is a probability measure on X. Assume t is chosen such that
learning algorithm h
jd P (f; hm (f;
is valid if the number of examples m is chosen as specified in Theorem 3. The bound is polynomial
in 1=ffl and 1=ffi if P (X t ) is of order
fat ffl=512
Proof: The bounds follow immediately from Theorem 3. They are polynomial in 1=ffl and 1=ffi if
the VC, pseudo-, or fat shattering dimension is polynomial in 1=ffl and 1=ffi. Because of the condition
the above inequality can be derived. 2
This argumentation leads to bounds if we can limit the probability P (X t ). Furthermore, these
bounds are polynomial if the probability for large trees tends to 0 sufficiently fast where the
necessary rate of convergence depends on the folding architecture which is considered. We can
substitute this prior information using the luckiness framework: We can learn with a concrete
training sample and derive bounds which only depend on the maximum height of the trees in the
training sample and the capacity of the architecture.
Corollary 8 Assume F is a [0; 1]-valued function class on the trees X, P is a probability distribution
on X, and d trees of height - t) is finite for every t; then
for
trees of height - t x being the maximum height of trees in the sample x.
Proof: We want to apply Theorem 4. We use the same notation as in the theorem. The unlucki-
ness function L 0 (x; f) = maxfheight of a tree in xg is smooth with respect to \Phi(m; L 0 (x; f); ffi;
trees of height - L 0 (x; f)) and j(m; L 0 (x; f); ffi;
2), as can be seen as follows:
because the number of functions in jfgjx 0 y height is at most L 0 (x; f ),
can be bounded by \Phi(m; L 0 (x; f); ffi; ff) because the number is bounded from above by the quantity
length of x 0 y 0 . The latter probability equals
Z
where U is the uniform distribution on the swapping permutations of 2m elements and A is the
above event. We want to bound the number of swappings of xy such that on the first half no tree
is higher than a fixed value t, whereas on the second half at least mj trees are higher than t. We
may swap at most all but mj indices arbitrarily. Obviously, the above probability can be bounded
by 2 \Gammamj , which is at most ffi for j - lg(1=ffi)=m.
We choose Now we can insert these values into the inequalities obtained
by the luckiness framework and get the bound
sm
where t is chosen such that \Phi(m; L(x; f); ffi; ff) - 2 t+1 . Hence, it is sufficient to choose t at least
. 2
Conclusions
The information theoretical learnability of folding architectures has been examined. For this purpose
bounds on the VC, pseudo-, and fat shattering dimension which play a key role in learnability
have been cited or improved, respectively. Since the fat shattering dimension is infinite even for
restricted weights and inputs there cannot exist bounds on the number of examples which guarantee
valid generalization and which are independent of the special distribution. Since the results do not
depend on the concrete learning algorithm but only on the dynamics this is in principle a drawback
of many mechanisms proposed for learning of structured data. If a list or tree structure is processed
recursively according to the recursive structure of the data then the a priori unlimited length or
height of the inputs offers the possibility of using this space to store any desired dichotomy on the
inputs in some way.
Upper bounds on the VC and pseudodimension can be given in terms of the number of parameters
in the network and the maximum input height. We have proposed two approaches which allow
a stratification of the situation via the input space or the output of a concrete learning algorithm.
Concerning folding networks a division of the input space in sets of trees with restricted height fits
to the first approach. It allows us to derive bounds on the deviation of the empirical and the real
error for any learning algorithm and any probability distribution for which the probability of high
trees can be restricted a priori. The second approach has been applied to training situations where
the height of the input trees is restricted in a concrete learning example. It allows us to derive
bounds on the deviation of the empirical error and the real error which depend on the concrete
learning set, that means the maximum height of the input trees. Note that in both approaches
the bounds are rather conservative because we have not yet tried to improve the constants which
occur.
As a consequence the structural risk of a learning algorithm can be controlled for folding networks
and other methods with the same processing dynamics as well. The real error of a learning
algorithm can be estimated if the empirical error, the network architecture, the number of patterns,
and additionally, the probability of high trees or the maximum input height in the training set are
known.
Although this fact holds for any learning algorithm some algorithms are to be preferred compared
to others: Since any algorithm with small empirical error generalizes well and needs the
same number of examples, the question arises as to whether a learning algorithm is capable of
minimizing the empirical error in an efficient way. An algorithm is to be preferred if it manages
this task efficiently. Here the folding architecture seems superior to the RAAM, for example, if
used for classification of structured data because it does not try to find encoding, decoding, and
an appropriate classification but only encoding and classification. That means, the same function
class is considered when dealing with the LRAAM instead of folding networks, but a more difficult
minimization task is to be solved. Furthermore, algorithms which start from some prior knowledge
if available for example in form of automata rules [23] highly probably find a small empirical error
faster than an algorithm which has to start from scratch because the starting point is closer to an
optimum value in the first case. Again, the function class remains the same but the initialization
of the training process is more adequate. Actually, training recurrent networks with a gradient
descend method has been proven to be particularly difficult [5, 16] and the same holds for folding
networks dealing with very high input trees as well. This makes further investigation of alternative
methods of learning necessary as the already mentioned method to start from an appropriate
initialized network rather than from scratch [20, 23] or to use appropriate modifications of the architecture
or the training algorithm [6, 16]. But for all algorithms the above bounds on the number
of training samples apply and no algorithm however complicated is able to yield valid generalization
with a number of examples independent of the underlying regularity.



--R


A sufficient condition for polynomial distribution-dependent learnability
Probabilistic analysis of learning in artificial neural networks: The PAC model and its variants.
For valid generalization
Learning long-term dependencies with gradient descent is difficult
Credit assignment through time: Alternatives to backpropagation.
A topological transformation for hidden recursive models.
Sample complexity for learning recurrent perceptron mappings.
A general framework for adaptive processing of data sequences.
Adaptive Processing of Sequences and Data Structures.
Learning task-dependent distributed representations by backpropagation through structure
Special issue on recurrent neural networks for sequence processing.
Approximation and learning of convex superpositions.
On the learnability of recursive data.
On the generalization of Elman networks.
Long short-term memory
Polynomial bounds for the VC dimension of sigmoidal neural networks.
Efficient distribution-free learning of probabilistic concepts

On the correspondence between neural folding architectures and tree automata.
Inductive learning symbolic domains using structure-driven neural networks
Neural net architectures for temporal sequence processing.
Constructing deterministic finite-state automata in recurrent neural networks
Recursive distributed representation.
Relating chemical structure to activity with the structure processing neural folding architecture.
Some experiments on the applicability of folding architectures to guide theorem proving.
Structural risk minimization over data dependent hierarchies.
Labeling RAAM.
A Theory of Learning and Generalization.
The roots of backpropagation.
--TR

--CTR
M. K. M. Rahman , Wang Pi Yang , Tommy W. S. Chow , Sitao Wu, A flexible multi-layer self-organizing map for generic processing of tree-structured data, Pattern Recognition, v.40 n.5, p.1406-1424, May, 2007
Barbara Hammer , Alessio Micheli , Alessandro Sperduti, Universal Approximation Capability of Cascade Correlation for Structures, Neural Computation, v.17 n.5, p.1109-1159, May 2005
Barbara Hammer , Peter Tio, Recurrent neural networks with small weights implement definite memory machines, Neural Computation, v.15 n.8, p.1897-1929, August
luckiness function;folding networks;VC dimension;UCED property;recurrent neural networks;computational learning theory