Generalization by Neural Networks.
The authors discuss the requirements of learning for generalization, where the traditional methods based on gradient descent have limited success. A stochastic learning algorithm based on simulated annealing in weight space is presented. The authors verify the convergence properties and feasibility of the algorithm. An implementation of the algorithm and validation experiments are described.
Introduction
Neural networks are being applied to a wide variety of applications from speech generation[1], to handwriting
recognition[2]. Last decade has seen great advances in design of neural networks for a class of problems called
recognition problems, and in design of learning algorithms[3-5, 5-7]. The learning of weights for neural network for
many recognition problem is no longer a difficult task. However, designing a neural network for generalization
problem is not well understood.
Domains of neural network applications can be classified into two broad categories- recognition and generalization
[1, 8]. For both classes, we first train the neural network on a set of input-output pairs
O 2 ),.,(I n , O n ). In recognition problems, the trained network is tested with a previously seen input I j (1  j  n)
corrupted by noise as shown in Fig.1. The trained network is expected to reproduce the output O j corresponding to
I j , in spite of the noise. Shape recognition [9, 10], and handwriting recognition[2] are examples of recognition prob-
lems. On the other hand, in generalization problems, the trained neural network is tested with input I n+1 , which is
distinct from the inputs I 1 , I 2 ,.,I n used for training the network, as shown in Fig.1. The network is expected to
correctly predict the output O n+1 for the input I n+1 from the model it has learned through training. Typical examples
of generalization problems are Bond Rating[11] and Robotics[12].
Neural networks for generalization problems are important, since there are many applications, of enormous
importance in the real world[13-15] which would benefit from this work. In many of these applications it is difficult
to successfully apply either conventional mathematical techniques (e.g., statistical regression) or standard AI
approaches (e.g., rule based systems). A neural network with generalization ability will be useful for such
domains[11], because it does not require an a priori specification of a functional domain model; rather it attempts to
learn the underlying domain model from the training input-output examples.
T r a i n e d
I 1 I 2
O 1 O 2
I n
O n

T r a i n e d
I 1 I 2
O 1 O 2
I n
O n


I n+1O n+1
I n+2O n+2

Figure

1. : Classes of Problems
The learning algorithm for generalization problems, should be different from the learning algorithm for
recognition problems. In recognition problems, the network is expected to reproduce one of the previously seen out-
puts. The network may remember the outputs and inputs by fitting a curve through the used for train-
ing. To remember the outputs, one often uses large networks with many nodes and weights. However memorization
of learning samples is not suited for generalization problems, since it can lead to worse performance during
prediction of outputs on unseen inputs. Furthermore, generalization problems allow a small amount of error in the
output predicted by the network and hence the fitted curve need not pass through any (I i , O i ) pair used for training.
Networks addressing generalization problem may instead fit a simple # curve (e.g. a low degree polynomial, or
basic analytical functions like log(x), sine(x), tangent(x) etc.) through the input-output pairs rather than fitting a
crooked curve. The neural network used in generalization problems tend to be simpler with small number of hidden
nodes, layers, and interconnection edges and weights, enabling one to use computationally sophisticated algorithms.
Most of the earlier work in neural networks [4, 9] is related to recognition problems. There has been little
research towards developing neural network models for generalization problems [16, 17].
We present a new learning algorithm, stochastic backpropagation for generalization problems. We verify the
convergence of the algorithm and provide theoretical arguments towards the capability of the proposed algorithm to
discover optimal weights. We also describe an implementation of the algorithm and our experience with the algorithms
in solving generalization problems.
2. Problem Formulation
Generalization problems for neural networks have been formulated in three different ways: (a) analytical
constructive function learning [25-27], and (c) symbolic semantic network[8]. The analytical
formalism focuses on the existence of networks with a capability to generalize. It also provide worst case time complexity
to discover such networks to solve arbitrary generalization problems. It does not provide a way to discover
the networks. The constructive function learning formalism approaches generalization problems in a complementary
fashion. It studies algorithms to discover networks which can solve a class of generalization problems. Its aims
at discovering a function f mapping the input domain to the output domain from a set of learning examples. The
function to be discovered may be defined over boolean numbers or over real numbers. The inputs and outputs are
assumed to be numbers with no symbolic meaning. The function and network do not represent symbolic meaning
beyond the numeric computation. The third approach of symbolic semantic network associates symbolic meaning to
the network. Generalization occurs by attaching a new node to an appropriate parent node in the network to inherit
the properties of the parent.
This classification of formulations of generalization problems does not include some special cases. For example,
signal detection problem can be considered as a special case. The task in signal detection problem is to learn to
recognize a parameter of the function f: I -> O, rather than learn the function. Recognizing the frequency of given
sinusoidal function is an example of signal detection problem. Backpropagation neural networks has been applied
successfully to this problem[28].
We focus on the constructive function learning formulation in terms of learning a numeric function. A simple
neural network can be described as a directed graph E). The vertex set V has three kinds of nodes: (a) input
nodes at leaves, (b) hidden nodes as internal nodes and (c) output nodes at roots. Each edge e i in E is associated
with a weight w i , j as shown in Fig.2.
The network is used to compute an output from a set of inputs. Each node i computes a function of weighted
sum of the input signals, g(
in inset
output. The function g maps from [-, ] to [-1,1]. Given any input,
the network would compute an output = f(input). The inverse problem of discovering the function f (i.e. the set of
edge weights) from a given set of input-output pairs is referred to as the learning problem, which can be stated as
follows. Given a set of example input output pairs {(I 1 ,O 1 ),.(I n ,O n )}, find the weights on each edge e i j  E, of
neural network, such that the network maps I j to O j for j=1,2,.n, as closely as possible.
I represent the possibly infinite domain of inputs, and O represent the possibly infinite range of outputs.
dimensional feature space, F 1 , ., F k , describing each of the input. Each input I j can be
considered a k-tuple in the Cartesian space F 1 F 2  . F k .
Given a learning sample I , S O ) and per sample error function E: I  O  Real with S I = { I 1 ,I 2, ., I n },
and S O = { O 1 , O 2, ., O n }, generalization involves finding the mapping function f
Neural Network Example
Symbols
Nodes
Edges
Weights
Output: O
Input: I2
Input: I1
w36

Figure

2.: Feed-forward neural network
to minimize error function E over the entire domain I. In particular f for each
learning sample.
Reducing the error function over entire domain I by looking at a small subset S I is difficult for arbitrary learning
samples S I and arbitrary input domain I . The generalization problem is often simplified by making assumptions
about the domain I and the learning sample S . We assume S I represents entire domain S adequately so that the
value of E over I can be estimated from the the value of E over S I . The function f is assumed to be smooth, continuous
and well behaved.
The domain and range of function f can be boolean sets or the set of real numbers. Usually more than one
function can fit the given set of learning samples of input-output pairs. It makes the generalization problem harder.
For example, learning a specific boolean function from a subset of domain is difficult [25] since several boolean
functions over the domain can fit the learning samples. There is little consensus on a criteria to prefer one of the
candidate boolean functions over the rest to break the tie. We restrict our attention to the functions over the set of
real numbers. We draw upon the notion of simplicity of functions over real numbers to choose one function among
the set of possible functions which fit the learning samples. Simplicity is intuitively defined in term of the number of
maxima and minima of the function. Simplicity reduces to the notion of degree of polynomials for polynomial functions

3. Stochastic Backpropagation
The general idea behind our algorithm is to use simulated annealing in the weight space. The weight space is
defined by a collection of configurations W connection weights in
the neural network. The simulated annealing procedure searches the weight space for the configuration W opt to
minimizes the error-to-fit function E(W i ). The search procedure is based on the Monte Carlo method [29]. Given
the current configuration W i of the network, characterized by the values of its weights, a small, randomly generated,
perturbation is applied by a small change in a randomly chosen weight. If the difference in error DE between the
current configuration W i and the slightly perturbed one is negative, i.e. if the perturbation results in a lower error of
fit, then the process is continued with the new state. If DE  0 then the probability of acceptance of the new configuration
is given by exp (-DE/k B T). These occasional transitions to higher error configuration help the search process
to get out of local minimas. This acceptance rule for the new configurations is referred to as the Metropolis
Criteria. Following this criteria, the probability distribution of the configurations approaches the boltzman distribution
given by Eq.A.1:
where Z(T) is a normalization factor, known as partition function, depending on temperature T and boltzman constant
. The factor exp (-E/k B T) is known as the boltzman factor.
T denotes a control parameter, which is called temperature due to historic reasons. Starting off at a high
value, the temperature is decreased slowly during the execution of algorithm. As the temperature decreases, the
boltzman distribution concentrates on the configurations with lower error and finally, when the temperature
approaches zero, only the minimum error configurations have a non-zero probability of occurring. In this way we
get the globally optimal weights for the network minimizing the error of fit with the training examples, provided the
maximum temperature is sufficiently high and the cooling is carried out sufficient slowly.
Algorithm Description: One has to define configurations, a cost function and a generation mechanism(or
equivalently, a neighborhood structure) before describing the algorithm. We assume that each weight takes discrete
values from set y = {-sd,.,-d,0,d,2d,.,sd}. The restriction of the weights to discrete values does limit # the learning
ability of neural networks for most generalization problems. The configurations can now be defined as n-tuple
of weights, where n is the number of weights in the network. The configuration space is constructed by allowing
each weight to take values from y. The cost function is defined by the error between desired outputs and network
outputs for the learning examples as shown below:
Here y j ,c refers to the j-th network output for the input from c-th training example, and d j ,c refers to the j-th
(desired) output from the c-th training example. The indices c and y refers to different outputs of the network and
various training examples respectively.
To generate the neighboring configurations, we change one randomly chosen weight element in the configuration
by d. We use uniform probability distribution to chose the weight to be changed, and thus the probability of
generating any neighboring configuration from the current configuration, is uniformly distributed over the neighbors

# One can always choose large value for s and scale the input output data value to a small range to achieve better accuracy.
Procedure
begin
while (not stop_criterion) {system is not "frozen"}
repeat
accept := false;
{where w lm was changed by PERTURB}
else if exp (- c
if accept# then UPDATE(configuration j);
until equilibrium_is_approached_sufficiently_closely;
c M+1 := f(c M );
Fig.3: Stochastic backpropagation algorithm in psuedo-Pascal
______________________________________________________________________________
A psuedo-Pascal description of the stochastic backpropagation is shown in Fig.3. The INITIALIZE routine
assigns default values to all the variables, in particular to current configuration, temperature, and
outer_iteration_count M. The loops correspond to simulated annealing in the weight space. The inner loop
represents simulated annealing at a fixed value of the control parameter T. It executes until the probability distribution
of current configuration being any of the possible configuration, becomes stable. This helps us to achieve boltzman
distribution. The outer loop changes the control parameter slowly to the final value near 0. This corresponds to
slow cooling to achieve configurations with globally minimum error. The steps inside the innermost loop combine
backpropagation with transitions for simulated annealing. We use the BACKPROP, the backpropagation algo-
rithm, [4] as a subroutine to compute the error derivatives E /w lm with respect to various weights. These derivatives
help us to estimate the change in error function, when a particular weight is changed by d. PERTURB produces
a neighboring configuration by changing a randomly chosen weight by d. The change in error function due to
the perturbation is estimated using the error derivatives obtained from the backpropagation algorithm. The new configuration
is accepted unconditionally, iff it has lower error than the current one. Otherwise the new configuration
is accepted with probability Finally the program variables are updated by UPDATE to state of the
newly chosen configuration.
# Note that the acceptance criterion is implemented by drawing random number from a uniform distribution on (0,1) and comparing
these with exp (-E(i)/T).
The basic algorithm shown in Fig.3. can be made more efficient, if one changes the function of BACKPROP
procedure. We notice that the backpropagation produces the partial derivatives of E with respect to all the weights,
whereas we use only one of the derivatives in subsequent computation. It is better to modify the backpropagation
algorithm to compute only one derivative, which is required.
Comparison with Existing Algorithms: Some of the existing learning algorithms, e.g. in Hopfield net-
works[30, 31], are based on memorizing the learning examples accurately. These cannot be used for prediction in
generalization problems. Two of the more flexible learning methods include backpropagation [9, 32] and boltzman
machine learning [33]. Both are iterative algorithms based on gradient descent on the error surface.
In backpropagation the error of fit for a given set of weights is defined by Eq. B.1 where y j ,c is the actual
state of unit j in input-output training example c and d j ,c is the desired state. Backpropagation algorithm computes
the gradient of error with respect to each weight. A hidden unit, j, in layer J affects the error via its effects on the
units, k, in the next layer K. So the derivative of the error E /y j is given by Eq. B.2 where the index c has been
suppressed for clarity.
dy k
The weights are then changed in a direction to reduce the error in the output. One may change the weights simultaneously
to avoid conflicting local weight adjustments.
The boltzman machine is stochastic in nature and the aim of learning the weights is to achieve a probability
distribution of input-output mapping. The boltzman machine learning [5] is based on a series of simulated annealing
on the state space of network. State space for the network can be characterized by defining the state of the net-
work. The state of a node is described by its output and the state of the network is a n-tuple vector with one component
for each node. The learning algorithm aims to achieve a certain probability distribution over the states, and
does a gradient descent to minimize the error in probability distribution. Our use of simulated annealing in weight
space is quite different from the boltzman machine [33], where simulated annealing is carried out in the state space
of the network.
These learning methods work only when the cost/error surface is concave. Since these algorithms are based
on a simple heuristic of gradient descent, these can get stuck in local minima. Furthermore these can get stuck at
plateaus, where the gradient is very small, as shown in Fig.4. These algorithms cannot guarantee the optimality of
discovered weights. The learning problem is NP-complete in general [34] and remains NP-complete under several
restrictions. it is not surprising that heuristic learning algorithms like backpropagation do not always work, and cannot
be trusted to find the globally optimal weights for generalization problems.
There are two ways of approaching NP-complete problems: (a) approximation methods [35], and (b) stochastic
enumeration method such as simulated annealing [36]. Since it is difficult to formulate a general approximation
method for neural network learning, we use the simulated annealing method. We extend the backpropagation algorithm
with stochastic weight changes for learning the weights. The algorithm has convergence properties and can
achieve globally optimal weights for a simple network for generalization. The implementation and performance studies
show that the algorithm performs well for many generalization problems.
Global Minima

Figure

4: Two Bad Cases for Gradient Descent
4. Modeling and Analysis of Stochastic Backpropagation
Given a neighborhood structure, stochastic backpropagation can be viewed as an algorithm that continuously
attempts to transform the current configuration into one of its neighbors. This mechanisms can mathematically be
described by means of a Markov Chain: a sequence of trials, where the outcome of each trial depends only on the
outcome of the previous one [37]. In the case of stochastic backpropagation, the trials correspond to transitions and
it is clear that the outcome of a transition depends only on the outcome of the previous one (i.e. the current confi-
guration).
A Markov chain is described by means of a set of conditional probabilities for each pair of outcomes
is the probability that the outcome of the k-th trial is j, given that the outcome of the k - 1-th
trial is i. Let a i (k) denote the probability of outcome i at the k-th trial, then a i (k) is obtained by solving the recursion

a
l
S a i (k-1).P li (k-1,k ), k=1,2.,(C.1)
where the sum is taken over all possible outcomes. Hereinafter, X(k) denotes the outcome of the k-th trial. Hence
and a i
If the conditional probabilities do not depend on k, the corresponding Markov chain is called homogeneous, otherwise
it is called inhomogeneous.
In case of stochastic backpropagation, the conditional probability denotes the probability that k-th
transition is a transition from configuration i to configuration j. Thus X(k) is the configuration obtained after k tran-
sitions. In view of this, is called the transition probability and the | R |  | R | matrix P(k-1,k) the transition
matrix. Here | R | denotes the size of the configuration space.
The transition probabilities depend on the value of the control parameter T (temperature). Thus if T is kept
constant, the corresponding Markov chain is homogeneous and its transition matrix can be defined as
l =1,li
G il (T) A il (T) forallj=i
i.e., each transition probability is defined as the product of the following two conditional probabilities: the generation
of generating configuration j from configuration i, and the acceptance probability A ij (T) of
accepting configuration j, once it has been generated from configuration i. The corresponding matrices G(T) and
A(T) are called the generation and acceptance matrices, respectively. As a result of the definition in Eq.C.4, P(T) is
a stochastic matrix, i.e.
1. G(T) is represented by a uniform distribution over the neighborhoods
since transitions are implemented by choosing at random a neighboring configuration j from the current configuration
i. A(T) is computed from the Metropolis criteria, i.e. min(1, exp(-DE/k B T)).
The stochastic backpropagation algorithm attains a global minimum, if after a (possibly large) number of
transitions, say K, the following relation hold:
where R opt is the set of globally optimal configurations with minimum error of fit. It can be shown that Eq.C.5
holds asymptotically (i.e.
lim Pr{X (k)  R opt
1. certain conditions on matrix A(T l ) and G(T l ) are satisfied
2.
3. under certain additional conditions on matrix A(T k ), the rate of convergence of the sequence {T k } is not
faster than O( | log k |
The proof is carried out in three steps: (a) showing the existence of stationary distribution for homogeneous
Markov chains, (b) showing the convergence of inner-loop of stochastic backpropagation to the stationary distribu-
tion, and (c) showing that the stationary distribution for the final "frozen system", has non-zero probabilities on the
optimal configurations only. The proof for last step is contingent on the cooling rate and provides us with a bound
on the rate.
4.1. Existence of Stationary Distribution
The following theorem establishes the existence of the stationary distribution.
Theorem 1 (Feller, [37] ): The stationary distribution q of a finite homogeneous Markov chain exists if the Markov
chain is irreducible and aperiodic. Furthermore, the vector q is uniquely determined by the following equation:
We note that q is the left eigenvector of the matrix P with eigenvalue 1.
A Markov chain is irreducible, if and only if for all pairs of configurations (i,j) there is a positive probability of
reaching j from i in a finite number of transitions, i.e.
Markov chain is aperiodic, if and only if for all configurations i R , the greatest common divisor of all integers n1,
such that
is equal to 1.
In the case of stochastic backpropagation, the matrix P is defined by Eq. C.4. Since the definition of A guarantee
that forall i,j,c it is sufficient for irreducibility to check that the Markov chain induced by G(T) is
irreducible [38],
i.e.
G lk lk+1 (T) > 0, k=0,1,.,p-1. (C.10)
To establish aperiodicity, one uses the fact that an irreducible Markov chain is aperiodic if the following condition is
satisfied [38]:
Thus for aperiodicity it is sufficient to assume that
Using the inequality of Eq. C.12 and the fact that forall i 1, we can prove the following:
l =1,liT
S | R
A iT l (T) G iT l (T)
l =1,liT , jT
S | R
A iT l (T) G iT l (T)
l =1,liT , jT
S | R
G iT l (T)
l =1,liT
S | R
G iT l (T)
l =1
S | R
G iT l
Thus P iT
l =1,liT
S | R
A iT l (T) G iT l (T) > 0 (C.14)
and thus, Eq. C.11 holds for i=i T .
Summarizing we have the following result. The homogeneous Markov chain with conditional probabilities
given by Eq. C.4. has a stationary distribution if the matrices A(T) and G(T) satisfy Eqs. C.10 and C.12, respec-
tively. Note that in the stochastic backpropagation the acceptance probabilities are defined by
and hence Eq. C.12 is always satisfied by setting, forall T > 0, i T R opt , j T  R opt .
4.2. Convergence of the Stationary Distribution
We now impose further conditions on the matrices A(T) and G(T) to ensure convergence of q(T) to the distribution
p, as given by Eq. C.5.
Theorem 2 [38]: if the two argument function y(E(i) - E opt ,T) is taken as A i0,i (T) (for an arbitrary configuration
does not depend on T, then the stationary distribution q(T) is given by
A i0,i (T)
provided the matrices A(T) and G satisfy following conditions:
The proof of this theorem is discussed elsewhere [ 39].
It is implicitly assumed that the acceptance probabilities depend only on the cost values of the configuration and not
on the configurations itself. Hence, A i0,i (T) does not depend on the particular choice for i 0 , since
To ensure that
of Eq. C.5, the following condition is sufficient [38]:
Thus the conditions (C.19)-(C.23) guarantee the convergence. It can be easily checked that the matrices G(T) and
A(T) for stochastic backpropagation meet all these conditions.
4.3. Cooling rate
Under certain conditions on matrices A(T) and G(T), the stochastic backpropagation algorithm converges to a global
minimum with probability 1 if for each value of T l of the control parameter(l = 0,1,2.), the corresponding Markov
chain is of infinite length and if the T l eventually converges too 0 for l , i.e. the validity of the following
equation is shown:
limq
| R opt |
However the cooling rate or the constraint on the sequence T l of the control parameter(l = 0,1,2.), has to satisfy
certain properties to assure convergence to the globally optimal configurations. In particular, if T k is of the form
G
then one can guarantee + the convergence to the globally optimal configurations [40].
4.4. Convergence Results
We have listed the conditions under which simulated annealing converges to globally optimal configurations.
Our formulation of stochastic backpropagation uses similar acceptance probabilities, generation probabilities, and
cooling schedule, as the simulated annealing algorithm [38]. That is we use Metropolis criteria as acceptance cri-
teria. We have a configuration generating mechanism, which has uniform distribution over neighbors. The generation
mechanism across two neighboring configuration is symmetric. One can generate any arbitrary configuration
from a given configuration in finite number of steps. Thus we satisfy the conditions of Theorem 1 and 2 and are
guaranteed convergence to global minima. We follow a cooling schedule of T n  logn
G to satisfy the conditions on
cooling rate. This guarantees the convergence to global minima provided G is greater than the depth of any local
minima.
5. Implementation
We have carried out a complete implementation of stochastic backpropagation and conducted validation stu-
dies. We implemented the algorithm on a unix platform on a sequential machine (e.g. SUN 3/60). Since generalization
often takes large amounts of computation, we plan to reimplement the algorithm on a vector processor (e.g.
Cray XMP) for speed-up.
The current prototype is based on the source code of a public domain software implementing backpropagation
algorithm[41]. We studied the software to reuse pertinent modules to implement stochastic backpropagation. The
implementation comprises of 5000 lines of C code. It required approximately seven man months to design, code and
debug. A large fraction of the effort was directed towards reading and understanding of the backpropagation
software for reuse. The effort was rewarded in reduced time of designing, coding and debugging. The code was
Provided G >= D, the maximal depth of any local minima in the error surface.
verified by walkthrough method and by extensive usage. The prototype has been used in seminar courses and
research.
The backpropagation package [41] has three modules: user interface, learning module and testing module.
User interface implements the commands by associating the commands to internal functions via a table. The commands
allow users to examine, and modify the state of the software, choose options to specify the type and speed of
computing and displays. The learning module implements the backpropagation algorithm by computing error
derivatives and weight adjustments to tune the weights iteratively for training. It repeats the weight adjustments for
fixed number of times or till the total squared error reaches a value set by the user. The learning algorithm provides
option of adjusting weights after examining each pattern or after examining all the patterns. The testing module
computes outputs for given inputs to the neural network. It also computes the total squared error between the output
produced by the network and the desired output specified for the input pattern.
We augmented the user interface module by adding commands to examine and modify the parameters of stochastic
backpropagation. The routines to process the commands were installed in the table associating commands to the
processing routines. A command to enable the user to choose between the alternative learning algorithms was also
added.
We implemented the stochastic backpropagation in C with a simplified cooling schedule. The cooling schedule is
based on expotential cooling T simplicity and efficiency. This cooling schedule has been used in
many applications [42]. The main routine in the learning module, namely trial(), was modified to adjust weight
based weight by randomly choosing a neighbor and accepting it by metropolis criteria. Testing module was not
altered for the implementation.
6. Validation
We evaluated stochastic backpropagation learning algorithm for generalization to two types of functions: (a)
monotonic functions , and (b) non monotonic functions.
The experimental setup consisted of four modules: data set generator, neural network simulator, data collection
and data analysis as shown in Fig 5. The data set generator module uses four functions : linear, quadratic, logarithmic
and trigonometric as shown in table 1. The neural network simulator implements alternative learning algorithms
of backpropagation and stochastic backpropagation. It takes the network configuration and data sets. The
module simulates learning algorithm and produces the outputs as well as the weights. The data collection module
comprises of a set of routines to sample the state of neural network simulator. It can periodically (say every 100
epochs of learning) sample the weights or collect them at the termination of learning. The data analysis module produces
graphs, and statistics.
The algorithms are monitored during the learning phase as well as during the testing phase. The performance
of algorithm during learning phase is measured by the total square error on the learning set of input-output pairs.
The performance of algorithm during testing phase is measured by the per pattern error on a new set of input-output
pairs, which is distinct from learning set. The behavior of alternative algorithms during learning are shown in Figures
6 and 7. Figure 6 shows the change in total square error along with learning steps for monotonic functions, i.e.
linear, logarithmic and quadratic functions. Stochastic backpropagation and backpropagation yield comparable total
square error. We tested the trained network with an independent set of samples. Stochastic backpropagation trained
network yielded 1.7% error per pattern. Backpropagation trained network yielded 0.9% error per pattern. Both networks
predict the outputs for all samples within 5% of desired output. Figure 7 shows the change in total square
error with epochs of learning for non-monotonic function, i.e. trigonometric function. Stochastic backpropagation
Network Configuration monotonic, non monotonic
Experimental Setup
Data Sets
Backpropagation).
(Stochastic Backprop,
Neural Network Simulator
Outputs, inputs
Finat weights,
experiment
per
Datafiles
plots, statistics
(plots, statistics, etc.)
Analysis Module
(weights, input, outpputs)
weight samples
Periodic intermediate
Data Collection
Problems
Fig. 5.: Experiment Design for the Performance Comparison Study

Table

1: Functions for controlled study
yields better total square error during learning as well as during testing. The network trained with backpropagation
network yields per pattern error of 15%, predicting the output for 14 samples out of 50 within 5% of the desired out-
put. The network trained with stochastic backpropagation yields per pattern error of 11%. It predicts the output for
samples out of 50 within 5% of the desired output.
Initial
Stochastic Backpropogation
Stochastic Backpropogation
Backpropogation2EPOCH

Figure

Learning monotonic functions
Initial
Stochastic Backpropogation
Backpropogation2EPOCH
Figure

7: Learning non-monotonic functions
7. Conclusions
Stochastic backpropagation provides a feasible learning algorithm for generalization problems. It reduces the
error of fit with the training examples, which is critical for generalization problem. Stochastic backpropagation performs
well on monotonic functions using simple networks with fewer hidden nodes. It performs better than backpropagation
algorithm on non-monotonic functions. The stochastic backpropagation learning algorithm has theoretical
property of convergence. It also provides a stochastic guarantee of finding the optimal weights. However, our
experiments did not confirm it. One needs to further tune the parameters of the implementation of stochastic back-propagation
to get better results.
8.

Acknowledgements

We acknowledge useful help from the CS 8199 class of spring 1991, UROP at the University of Minnesota,
and the backpropagation package[41]
9.



--R


Handwritten numeral recognition by multi-layered neural network with improved learning algorithm
Learning in
Learning Internal Representations by Back Propagating Errors
A Learning Algorithm for Boltzman Machine
Linear Function Neurons: Structure and Training
The ART of adaptive pattern recognition by a self-organizing neural network
Brain Style Computation: Learning and Generalization
Learning to Recognize Shapes in a Parallel Network
Learning Translation Invariant Recognition in Massively Parallel Network

The design of intelligent robot as a federation of geometric mchines
Neural Computers
Using Artificial Neural Nets for Statistical Discovery: Observations after using Back-Propagation
Beyond Regression: New Tools for Prediction and Analysis in the Behaviorial Sciences
Connectionist Expert Systems
Material Handling: A Conservative Domain for Neural Connectivity and Propagation

On the representation of continuous functions of several variablesby superposition of continuous functions of one variable and addition
Meaning of Generalization (ch.
Mapping Abilities of Three Layered
Training a 3-node neural net is NP-complete
On Complexity of Loading Shallow Networks
Neural Network Design and the Complexity of Learning
Scaling and Generalization in
A Learning Algorithm for Generalization Problems
Memorization and Generalization (Ch.
Creating Artificial
Equation of State Calculations by Fast Computing Machines
Neural networks and physical systems with emergent collective computing abilities
Neural computation of decisions in optimization problems
Parallel Distributed Processing: Explorations in the Microstructure of Cognition
Constraint Stisfaction Machines That Learn
Complexity of Connectionist Learning with Various Node Functions
Computers and Interactability: A Guide to the Theory of NP-Completeness
Optimization by simulated annealing
An Introduction to Probability Theory and Applications
Probabilistic Hill Climbing Algorithms: Properties and Applications
Theory and Applications
Cooling Schedules for Optimal Annealing
Explorations in Parallel Distributed Processing - A Handbook of Models
John Wiley
--TR
Linear function neurons: Structure and training
Connectionist expert systems
The ART of Adaptive Pattern Recognition by a Self-Organizing Neural Network
Cooling schedules for optimal annealing
On the complexity of loading shallow neural networks
Simulated annealing and Boltzmann machines: a stochastic approach to combinatorial optimization and neural computing
Neurocomputer applications
Explorations in parallel distributed processing
Neural network design and the complexity of learning
Training a 3-node neural network in NP-complete
Parallel distributed processing: explorations in the microstructure of cognition, vol. 1
Creating artificial neural networks that generalize
The design of intelligent robots as a federation of geometric machines
Brain style computation
Computers and Intractability
Learning Translation Invariant Recognition in Massively Parallel Networks
Complexity of Connectionist Learning with Various Node Functions

--CTR
V. Kumar , S. Shekhar , M. B. Amin, A Scalable Parallel Formulation of the Backpropagation Algorithm for Hypercubes and Related Architectures, IEEE Transactions on Parallel and Distributed Systems, v.5 n.10, p.1073-1090, October 1994
simulated annealing;weight space;learning;convergence properties;learning systems;stochastic learning algorithm;gradient descent;neural networks;neural nets;generalization