LEARNING AND GENERALIZATION IN NEURAL NETWORKSSteve Renals27Febuary1998Contents1THE BACK-PROPAGATION ALGORITHM31.1Introduction (3)1.1.1Units and weights in ANNs (3)1.1.2Neural network architectures (4)1.1.3Learning (5)1.1.4Applications of neural networks (6)1.2Supervised learning in feed-forward networks (6)1.2.1Single layer perceptrons (6)1.2.2Linear Separability (9)1.2.3Multi-layer perceptrons—The back-propagation algorithm (9)1.3Issues in training MLPs by backprop (13)1.3.1Batch and online learning (13)1.3.2When is training complete? (13)1.3.3Will backprop alwaysfind the solution? (13)2GENERALIZATION152.1Introduction (15)2.2Evaluating Generalization:Training,Test and Validation Sets (15)2.3Training and Generalization (16)2.4Bias and Variance (19)2.5References (21)3OVERTRAINING AND HOW TO A VOID IT233.1Introduction (23)3.2Cross-Validation and Early Stopping (23)3.3Regularization (25)4CLASSIFICATION USING NEURAL NETWORKS274.1Introduction (27)4.2Estimation of Posterior Probabilities (27)4.3Practical Implications of Posterior Probability Estimation (28)4.3.1Minimum Error-Rate Decisions (29)4.3.2Compensating for Different Priors (29)4.3.3Outputs Sum to One (29)4.3.4Combining Network Outputs (29)4.3.5Confidence and Rejection (30)4.4References (30)1Chapter1THE BACK-PROPAGATION ALGORITHM1.1IntroductionIn this course we are interested in artificial neural networks—biology does not concern us!In the only analogy of the kind that I’ll use,the table below gives the correspondences between the terminology used for biological neural networks and that used for artificial neural networks(ANNs):Neuron Unit/Node/CellSynapse ConnectionSynaptic Weight WeightNeuron Firing Rate Node Output1expv(1.5)Note that in both these cases the bias of the unit can be used to shift the function along the x axis.Units in neural networks may be described as:Input units,which receive some input from the environment (e.g.a pixel map for a net-work to recognize handwritten characters);Output units may be observed from the environments (e.g.the class of character input tothe network);Hidden units which are internal to the network and do not directly interact with the envi-ronment.1.1.2Neural network architecturesThe architecture of a neural network tells us what connections between units are allowed.Many architectures have been studied and used;here we’ll characterize them in terms of some defining characteristics.Recurrent or feed-forward?In a feed-forward network there is an ordering imposed onthe nodes in a network:if there is a connection from unit a to unit b then there can-not be a connection from b to a .There is no such constraint in recurrent networks (figure 1.3(a)),in which any unit can be connected to any other,thus allowing loops or recurrences .The absence of recurrences makes feed-forward networks much eas-ier to train,but also less powerful.A feed-forward structure makes things simpler because there is a simple flow of computation through the network.In a layered feed-forward network (figure 1.3(b))the weights are organized in layers connecting groups of units together.Fully or partially connected?In a fully connected network all allowed connections areimplemented;in a partially connected network there is a structuring of connections.For example in the AT&T handwriting recognition system (part 5of these notes)the network connectivity is structured to take account of prior knowledge about the problem....1y 2y ny w nw 2w 1v =y = f(v)yΣw y + w y + ... + w y nn 2112Figure 1.1:ANN unit with weighted input summation41expv(1.8)where we have assumed that the output unit transfer function f O is a sigmoid.The activation value of output unit k is represented by v O k .Input 0always has value 1,so theweight w OI k 0corresponds to the bias of output unit k .Exercise:Rewrite the above equations in matrix-vector notation (i.e.representing theweights as a single matrix W ,the inputs as vector y I ,and so on).The key problem in supervised training is that of credit assignment :given that there is an output error (i.e.the network outputs differ from the desired outputs supplied by the training data),how do we adjust the weights of the network to minimize that output error over all the training data?The basic idea is as follows:If an output unit has the desired output value then do not adjust the weights leading into that unit;If an output unit has an output less than the desired output,then increment the weights leading into that unit by a small amount (proportional to the difference between de-sired and actual outputs);If an output unit has an output greater than the desired output,then decrement the weights leading into that unit by a small amount (proportional to the difference be-tween desired and actual outputs);This assumes that all the inputs are positive.Exercise:How do the rules change if some inputs are negative?This is rather heuristic.A more principled way of proceeding involves defining an error function for the network.For a single pattern p we define the error E p :E p12∑k d O k y O k2(1.10)e kd O ky O k(1.11)where d O k is the desired value for output unit k and e kis the local error for output unit k .We describe E p as the sum squared error.We can sum E p over all patterns to give the overall training set error:E∑pE p(1.12)E p tells us how well the network performs on pattern p .E p 0means that it is perfect for this pattern and no weights need adjusting.The larger E p the worse the network is doing.We can write e k in terms of the weights:e kd kf O ∑iw OI ki y Ii (1.13)72∑kd k f O∑iw OI ki y I i2(1.14)E p is a function of the weights w OIki ,the input values y I i and desired outputs d Ok.The inputsand desired outputs are specified by the training set;the task is to optimize the weights given that training set.Thus the learning task becomes the following:adjust the weightsw OI kiso that E is minimized.One way to minimize E(or any function)is by a process called gradient descent.Theidea of gradient descent is to look at the error surface(i.e.E in terms of all the w OI ki)and to adjust the weights in the direction of steepest descent.We can express this as:∆w OI kiη∂E p∂w OI ki ∂E∂w OI ki(1.17)∂E∂v O k∂v O k∂y O kd k y O ke k(1.19)∂y O k∂w OI kiy I i(1.21) (Exercise:Verify that each of these derivatives is correct.)Substituting(1.19),(1.20)and(1.21)into(1.18)we have the derivative we require:∂E1In one-dimensional input space it would define a point;in two-dimensional input space it would define a line; in three-dimensional input space a plane.Things get harder to visualize in higher dimensions.9NOTATIONAs for the single layer perceptron(equations(1.6–1.8))we can write down the set of equations that describe the behaviour of the network:w HI ji y I i(1.24)v H j∑iy H j f O v H j(1.25)v O k∑w OH k j y H i(1.26)jy O k f O v O k(1.27) And we’ll assume both transfer functions are sigmoids:1f O v f H v2∑ke2k1∂w OH k j∂E∂v O k∂v O k∂w HI ji∂E∂w HI ji(1.33)The second term on the right hand side can be written down simply by differentiating(1.24) and(1.25):∂y H j∂v H j∂v H j∂y H j ∑k∂E∂y H j(1.36)We must sum over all output units,since each hidden unit is connected to all output units and so affects the error of all output units.The required derivatives are now straightforward:∂E∂y H jy O k1y O k w OH k j(1.38)∂E∂w HI ji ∑kd k y O k y0k1y O k w OH k j y H j1y H j y I i(1.40)y H j1y H j∑kd k y O k y0k1y O k w OH k j y I i(1.41)∆w HI jiηy H j1y H j∑kd k y O k y0k1y O k w OH k j y I i(1.42)We can now write down the algorithm for training an MLP by back-propagation oferror:1.Initialize weight matrix to small random values2.While E is unsatisfactory(a)For each pattern p:pute hidden node activations(v H j)using equation(1.24)pute hidden node outputs(y H j)using equations(1.25)and(1.28)pute output node activations(v Ok)using equation(1.26)pute network outputs(y Ok)using equations(1.27)and(1.28)pute the local output errors(e k)and the network error for this pattern(E p)using equations(1.11)and(1.9)pute the gradient of the error E p with respect to each hidden-to-outputweight w OHk jand update the weights using equation(1.32)pute the gradient of the error E p with respect to each input-to-hidden weight w HI ji and update the weights using equation(1.42)12∂w ji ∑p ∂E pChapter2GENERALIZATION2.1IntroductionWe can regard feed-forward networks as implementing a function mapping an input vector (y I y I1y I i y I n)to an output vector(y O y O1y O i y O n).The parameters of this function are the weights.We can divide the functions implemented by an MLP into classi-fiers(which map an input vector to a discrete class)and regressors(which map a continuous input vector to a continuous output vector).In the case of classification the output vector usually has the same dimensionality as there are classes,with each element corresponding to one of the classes.In regression,the output vectors corresponds to the continuous valued quantity being estimated.The classification and regression functions that are estimated using an MLP(or other neural network)are unknown—all we have is a training set,that gives input-output ex-amples of the function.The role of neural network training is to identify this“mystery function”,given only the training data.What the training process(e.g.backprop)does is to estimate the parameters of the function(i.e.the weights of the network)so that it replicates the data as well as possible—and generalizes to new data well.It turns out that obtaining the best generalization performance on new data is not usually the same solution as replicating the training data as well as possible.Consider the case when we have very few training patterns but a large network with many patterns.It will be relatively easy to manipulate the weights to reproduce the training set,but it does not seem likely that the resulting network will have learned the charac-teristics of new data.On the other hand,if we have very many training patterns,and we manage to train the network to replicate them,then it would seem that it is more likely to respond correctly to new,unseen patterns.Our aim is to make such intuitions precise,and to develop approaches which can maximize the generalization performance of a network.2.2Evaluating Generalization:Training,Test and Valida-tion SetsThe obvious way to obtain an estimate of how well a network generalizes is to test its performance on new data.However we have to be careful which data we use—if we keep on using the same test set,then although this data isn’t being used by the training algorithm, the fact we are trying to get the best performance on this particular data set may cause other factors(e.g.choice of learning rate)to be tuned to this“test set”.To make the distinction explicit it is common to work with three data sets:Training Set This is the data that used by the training algorithm to adjust the weights of the network.15Chapter3OVERTRAINING AND HOW TO A VOID IT3.1IntroductionThe lowest generalization error is achieved by an optimal tradeoff between bias and vari-ance.A function that is too closelyfitted to the training set will tend to have a large variance and hence give a large expected error—this is called overtraining.We can decrease the variance by smoothing the function(hence increasing the bias)but if we go to far the large bias will cause the expected generalization error to become large again.One way to reduce both the bias and variance is to use moreflexible networks while simultaneously increasing the size of the training set.Increasing theflexibility of the net-work will reduce the bias,while adding more training data will decrease the variance since each extra training data point adds a new constraint in the space of functions available to the network that implement the function described by the training data.However in many situations we do not have the option of increasing the amount of training data.If we have some prior information about the unknown function we are trying to model,then using this information to constrain the network function will not necessarily increase the bias.For example,if the true function is linear,then constraining the network to linear functions will not increase the bias since the constrained functions are consistent with the true network function.The bias-variance model tells us that in some situations (with limited training data)performance will be better with a constrained model(e.g.a simple linear network)than a less constrained model(e.g.a multi-layer perceptron)even though the lessflexible model is a special case of the moreflexible one.However,if we do not have this task-specific information we can still make an attack on the bias-variance problem(or,equivalently,the problem of overtraining).We do this by methods that reduce the effective complexity of the network.Two important methods for doing this are cross validation and regularization.3.2Cross-Validation and Early StoppingThe basic idea of cross-validation is to hold out a validation set from the training data, which is used to control when to stop training.The idea of early stopping comes about from some empirical results that indicate that while the training error will monotonically decrease as training progresses,the validation set error will only decrease up to a certain point,after which it will increase again.This is illustrated infigure3.1.This result implies that generalization can be improved if the network is tested with the validation set every epoch or every few epochs(an epoch is a complete pass through the training set),and that23∂y I2iThen minimizing E W will result in a low curvature(smoother)function.The derivatives of this type of regularizer can be computed for an MLP,but curvature based regularizers haven’t been used much in practice in neural computing(although they are widely used in computer vision and other areas).Weight decay is a more commonly used regularizer.In weight decay,we define:1E Ww i∂w iRemembering that backprop training uses the negative of this derivative,we have:∂E∆w iηβ∂E W∂w iηβw i(3.5)∂w i25Chapter4CLASSIFICATION USING NEURAL NETWORKS4.1IntroductionThe pattern classification task is to classify an input vector x(y I using the notation of part1of these notes)into one of M classes(C1C2C m).This is a problem that has been studied for many years in thefield of statistical pattern recognition.A solution to this problem is to compute the Bayesian Posterior Probability P C i x for each class and to assign the input vector to the class with the largest posterior probability.The posterior probability,P C i x is the conditional probability of the class C i given the input data x.A method which directly estimates such probabilities may be thought of as a recognition model.Recognition models are discriminative—training consists of moving class boundaries to maximize the correct classification of the training data by the model.Standard statistical pattern recognition techniques do not usually estimate P C i x di-rectly as this can be difficult.Instead they use a generative model.A generative model may be thought of as a machine C i that generates pattern vectors x with a likelihood P x C i. Training consists of building a machine for each class,using the training data;recognition involves computing the likelihood of each machine generating a test example,and labelling the pattern with the class whose machine was most likely to have generated the data.Intuitively it seems that neural networks are more like recognition models than genera-tive models when used for classification.Indeed,it turns out that(given some conditions) we can show that feed-forward networks trained as a classifier directly estimate the poste-rior probability of each class given the data P C i x.4.2Estimation of Posterior ProbabilitiesWhen a feed-forward network(e.g.an MLP)is trained as a classifier a“1-from-M”output coding is usually employed.That is,if there are M classes we use M output units,1for each class.The target vector d used in training for a pattern of class i,will consist of zeros except that d i 1.If:The network is trained using a sum-squared error cost function(i.e.,the usual error function),There is enough training dataThere network isflexible enough to represent the desired function,andThe learning algorithm(e.g.backprop)is powerful tofind the global minimum,27(4.1)p xwhere P C i is the prior probability of class C i and p x is a normalizing constant.Gen-erative pattern recognition models estimate both the likelihood p x C i and the prior P C i to arrive at a posterior probability estimate.Neural networks,on the other hand,are able to estimate the posterior probability directly.The prior probability is simply the probability of each class occurring,without having seen any data.The training data estimate of the priors is simply the relative frequency of each class in the training set.This decomposition may be used if the prior probabilities are known to be different in the training and test sets.To compensate for a different prior,we simply divide each output by the relative frequency of the corresponding class,and multiply by a new estimate of the prior probability.Bishop gives the following example for when this might be useful: Consider the problem of classifying medical images into“normal”and“tu-mour”.When used for screening purposes in the general population we havea very low prior probability for tumour.To obtain a good variety of tumourimages in the training set would therefore require huge numbers of examples.An alternative is to increase artificially the proportion of tumour images in thetraining set,and then to compensate for different priors in the test data.Theprior probabilities for tumours in the general population can be obtained frommedical statistics without having to collect the corresponding images.Cor-rection of the network outputs is then a simple matter of multiplication anddivision.4.3.3Outputs Sum to OneSince the outputs of a network trained as a classifier are probability estimates they will sum to one.This fact can be used to as a measure of how well a network has trained.Further,it is possible to use this fact as a constraint in the network architecture—the outputs may be normalized in such a way so that they are forced to sum to1.It can be shown that the average posterior probability of each class in the training set will correspond to the training set estimate of the class prior probability(the relative fre-quency of that class).We can use this information as a measure of how well the network is trained by checking whether the training set posterior probability averages for each output unit do indeed tend to the prior probabilities.If they do not,this is a good indication that the network is not modelling the posterior probabilities well.4.3.4Combining Network OutputsIt has been shown by several researchers that rather than using a single network to solve a problem,there can be benefits in breaking a problem down into subunits each solved by29。
