This thesis examines so called folding neural networks as a mechanism for machine learning. Folding networks form a
generalization of partial recurrent neural networks such that they are able to deal with tree structured inputs instead of
simple linear lists. In particular, they can handle classical formulas - they were proposed originally for this purpose. After
a short explanation of the neural architecture we show that folding networks are well suited as a learning mechanism in
principle. This includes three parts: the proof of their universal approximation ability, the aspect of information theoretical
learnability, and the examination of the complexity of training.
Approximation ability: It is shown that any measurable function can be approximated in probability. Explicit bounds on
the number of neurons result if only a finite number of points is dealt with. These bounds are new results in the case of
simple recurrent networks, too. Several restrictions occur if a function is to be approximated in the maximum norm.
Afterwards, we consider briefly the topic of computability. It is shown that a sigmoidal recurrent neural network can
compute any mapping in exponential time. However, if the computation is subject to noise almost the capability of tree
automata arises.
Information theoretical learnability: This part contains several contributions to distribution dependent learnability: The
notation of PAC and PUAC learnability, consistent PAC/ PUAC learnability, and scale sensitive versions are considered.
We find equivalent characterizations of these terms and examine their respective relation answering in particular an open
question posed by Vidyasagar. It is shown at which level learnability only because of an encoding trick is possible. Two
approaches from the literature which can guarantee distribution dependent learnability if the VC dimension of the concept
class is infinite are generalized to function classes: The function class is stratified according to the input space or
according to a so-called luckiness function which depends on the output of the learning algorithm and the concrete
training data.
Afterwards, the VC, pseudo-, and fat shattering dimension of folding networks are estimated: We improve some lower
bounds for recurrent networks and derive new lower bounds for the pseudodimension and lower and upper bounds for
folding networks in general. As a consequence, folding architectures are not distribution independent learnable.
Distribution dependent learnability can be guaranteed. Explicit bounds on the number of examples which guarantee valid
generalization can be derived using the two approaches mentioned above. We examine in which cases these bounds are
polynomial. Furthermore, we construct an explicit example for a learning scenario where an exponential number of
examples is necessary.
Complexity: It is shown that training a fixed folding architecture with perceptron activation function is polynomial.
Afterwards, a decision problem, the so-called loading problem, which is correlated to neural network training is examined.
For standard multilayer feed-forward networks the following situations turn out to be NP-hard: Concerning the
perceptron activation function, a classical result from the literature, the NP-hardness for varying input dimension, is
generalized to arbitrary multilayer architectures. Additionally, NP-hardness can be found if the input dimension is fixed
but the number of neurons may vary in at least two hidden layers. Furthermore, the NP-hardness is examined if the
number of patterns and number of hidden neurons are correlated. We finish with a generalization of the classical NP
result as mentioned above to the sigmoidal activation function which is used in practical applications.
| Identifer | oai:union.ndltd.org:uni-osnabrueck.de/oai:repositorium.ub.uni-osnabrueck.de:urn:nbn:de:gbv:700-2000091564 |
| Date | 15 September 2000 |
| Creators | Hammer, Barbara |
| Contributors | Prof. Dr. Volker Sperschneider, Prof. Dr. Mathukumalli Vidyasagar |
| Source Sets | Universität Osnabrück |
| Language | English |
| Detected Language | English |
| Type | doc-type:doctoralThesis |
| Format | application/gzip, application/gzip |
| Rights | http://rightsstatements.org/vocab/InC/1.0/ |
Page generated in 0.002 seconds