Abstract

This paper presents two approaches to characterize the dynamics of weight space probability density starting from a master equation. In the first, we provide a class of algorithms for which an exact evaluation of the integrals in the master equation is possible. This enables the time evolution of the density to be calculated at each time step without approximation. In the second, we expand earlier work on the small noise expansion to a complete perturbation framework. As an example application, we give a perturbative solution for the equilibrium density for the LMS algorithm. Finally, we use the perturbation framework to review annealed learning with schedules of the form μ(t) = μ0/tp.

Introduction

Several of the contributions to this volume apply order parameter techniques to describe the dynamics of on-line learning. In these approaches, the description assumes the form of a set of ordinary differential equations that describe the motion of macroscopic quantities, the order parameters, from which observables such as generalization error can be computed directly, without intermediate averaging. The (typically non-linear) differential equations are usually solved numerically to provide the dynamics throughout the training. Recently, this author and colleagues have obtained analytic results from the order parameter equations applied to the late time (asymptotic) convergence of annealed learning (Leen, Schottky and Saad, 1998). However, most of the application of these techniques has involved numerical integration. Indeed, the ability to track the ensemble dynamics at all times by solution of ordinary differential equations establishes an attractive analysis tool.

Abstract

The choice of training parameters and training rules is of great significance in on-line training of neural networks. We employ a variational method for determining globally optimal learning parameters and learning rules for on-line gradient descent training of multi-layer neural networks. The approach is based on maximizing the total decrease in generalization error over a fixed time-window, using a statistical mechanics description of the learning process. The method is employed for obtaining optimal learning rates in both realizable and noise-corrupted tasks, for determining the relation between optimal learning rates of different weights and for examining the efficacy of regularizers in noisy and over-realizable training scenarios. Scaling rules for the optimal learning rates are obtained in learning generic tasks by linearizing the dynamics around transient and asymptotic fixed points. The method is further employed for determining the globally optimal on-line learning rule, which is shown to be superior to the locally optimal rule.

Introduction

Feed-forward neural networks have been extensively applied during the last decade for a variety of classification, regression, prediction and control tasks and are the most commonly used neural network architecture. On-line learning is arguably the most efficient way of training large feed-forward networks, especially when the task to be learnt is non-stationary, and is based on instantaneous modifications of the network parameters calculated according to only the latest in a sequence of training examples. This process is inherently stochastic because a new training example is selected at random each time the training error is determined. This is to be contrasted with batch learning, in which all the training examples are used to determine the training error, leading to a deterministic algorithm.

Abstract

The convergence of online learning algorithms is analyzed using the tools of the stochastic approximation theory, and proved under very weak conditions. A general framework for online learning algorithms is first presented. This framework encompasses the most common online learning algorithms in use today, as illustrated by several examples. The stochastic approximation theory then provides general results describing the convergence of all these learning algorithms at once.

Introduction

Almost all of the early work on Learning Systems focused on online algorithms (Hebb, 1949; Rosenblatt, 1957; Widrow and Hoff, 1960; Amari, 1967; Kohonen, 1982). In these early days, the algorithmic simplicity of online algorithms was a requirement. This is still the case when it comes to handling large, real-life training sets (LeCun et al., 1989; Müller, Gunzinger and Guggenbühl, 1995).

The early Recursive Adaptive Algorithms were introduced during the same years (Robbins and Monro, 1951) and very often by the same people (Widrow and Stearns, 1985). First developed in the engineering world, recursive adaptation algorithms have turned into a mathematical discipline, namely Stochastic Approximations (Kushner and Clark, 1978; Ljung and Söderström, 1983; Benveniste, Metivier and Priouret, 1990).

Although both domains have enjoyed the spotlights of scientific fashion at different times and for different reasons, they essentially describe the same elementary ideas. Many authors of course have stressed this less-than-fortuitous similarity between learning algorithms and recursive adaptation algorithms (Mendel and Fu, 1970; Tsypkin, 1971).

The present work builds upon this similarity. Online learning algorithms are analyzed using the stochastic approximation tools. Convergence is characterized under very weak conditions: the expected risk must be reasonably well behaved and the learning rates must decrease appropriately.

Abstract

Optimization is an important operation in many domains of science and technology. Local optimization techniques typically employ some form of iterative procedure, based on derivatives of the function to be optimized (objective function). These techniques normally involve parameters that must be set by the user, often by trial and error. Those parameters can have a strong influence on the convergence speed of the optimization. In several cases, a significant speed advantage could be gained if one could vary these parameters during the optimization, to reflect the local characteristics of the function being optimized. Some parameter adaptation methods have been proposed for this purpose, for deterministic optimization situations. For stochastic (also called on-line) optimization situations, there appears to be no simple and effective parameter adaptation method.

This paper proposes a new method for parameter adaptation in stochastic optimization. The method is applicable to a wide range of objective functions, as well as to a large set of local optimization techniques. We present the derivation of the method, details of its application to gradient descent and to some of its variants, and examples of its use in the gradient optimization of several functions, as well as in the training of a multilayer perceptron by on-line backpropagation.

Introduction

Optimization is an operation that is often used in several different domains of science and technology. It normally consists of maximizing or minimizing a given function (called objective function), that is chosen to represent the quality of a given system. The system may be physical, (mechanical, chemical, etc.), a mathematical model, a computer program, etc., or even a mixture of several of these.

Abstract

The recently proposed Bayesian approach to online learning is applied to learning a rule defined as a noisy single layer perceptron with either continuous or binary weights. In the Bayesian online approach the exact posterior distribution is approximated by a simpler parametric posterior that is updated online as new examples are incorporated to the dataset. In the case of continuous weights, the approximate posterior is chosen to be Gaussian. The computational complexity of the resulting online algorithm is found to be at least as high as that of the Bayesian offline approach, making the online approach less attractive. A Hebbian approximation based on casting the full covariance matrix into an isotropic diagonal form significantly reduces the computational complexity and yields a previously identified optimal Hebbian algorithm. In the case of binary weights, the approximate posterior is chosen to be a biased binary distribution. The resulting online algorithm is derived and shown to outperform several other online approaches to this problem.

Introduction

Neural networks are adaptive systems characterized by a set of parameters w, the weights and biases that specify the connectivity among the neuronal computational elements. Of particular interest is the ability of these systems to learn from examples. Traditional formulations of the learning problem are based on a dynamical prescription for the adaptation of the parameters w. The learning process thus generates a trajectory in w space that starts from a random initial assignment w0 and leads to a specific w* that is in some sense optimal.

Abstract

We study the dynamics of supervised learning in layered neural networks, in the regime where the size p of the training set is proportional to the number N of inputs. Here the local fields are no longer described by Gaussian distributions. We show how dynamical replica theory can be used to predict the evolution of macroscopic observables, including the relevant performance measures, incorporating the theory of complete training sets in the limit p/N → ∞ as a special case. For simplicity we restrict ourselves here to single-layer networks and realizable tasks.

Introduction

In the last few years much progress has been made in the analysis of the dynamics of supervised learning in layered neural networks, using the strategy of statistical mechanics: by deriving from the microscopic dynamical equations a set of closed laws describing the evolution of suitably chosen macroscopic observables (dynamic order parameters) in the limit of an infinite system size [e.g. Kinzel & Rujan (1990), Kinouchi & Caticha (1992), Biehl & Schwarze (1992, 1995), Saad & Solla (1995)]. A recent review and more extensive guide to the relevant references can be found in Mace & Coolen (1998a).

Abstract

We analyse the dynamics of a number of second order on-line learning algorithms training multi-layer neural networks, using the methods of statistical mechanics. We first consider on-line Newton's method, which is known to provide optimal asymptotic performance. We determine the asymptotic generalization error decay for a soft committee machine, which is shown to compare favourably with the result for standard gradient descent. Matrix momentum provides a practical approximation to this method by allowing an efficient inversion of the Hessian. We consider an idealized matrix momentum algorithm which requires access to the Hessian and find close correspondence with the dynamics of on-line Newton's method. In practice, the Hessian will not be known on-line and we therefore consider matrix momentum using a single example approximation to the Hessian. In this case good asymptotic performance may still be achieved, but the algorithm is now sensitive to parameter choice because of noise in the Hessian estimate. On-line Newton's method is not appropriate during the transient learning phase, since a suboptimal unstable fixed point of the gradient descent dynamics becomes stable for this algorithm. A principled alternative is to use Amari's natural gradient learning algorithm and we show how this method provides a significant reduction in learning time when compared to gradient descent, while retaining the asymptotic performance of on-line Newton's method.

Introduction

On-line learning is a popular method for training multi-layer feed-forward neural networks, especially for large systems and for problems requiring rapid and adaptive data processing. Under the on-line learning framework, network parameters are updated according to only the latest in a sequence of training examples.

Abstract

Online learning is discussed from the viewpoint of Bayesian statistical inference. By replacing the true posterior distribution with a simpler parametric distribution, one can define an online algorithm by a repetition of two steps: An update of the approximate posterior, when a new example arrives, and an optimal projection into the parametric family. Choosing this family to be Gaussian, we show that the algorithm achieves asymptotic efficiency. An application to learning in single layer neural networks is given.

Introduction

Neural networks have the ability to learn from examples. For batch learning, a set of training examples is collected and subsequently an algorithm is run on the entire training set to adjust the parameters of the network. On the other hand, for many practical problems, examples arrive sequentially and an instantaneous action is required at each time. In order to save memory and time this action should not depend on the entire set of data which have arrived sofar. This principle is realized in online algorithms, where usually only the last example is used for an update of the network's parameters. Obviously, some amount of information about the past examples is discarded in this approach. Surprisingly, recent studies showed that online algorithms can achieve a similar performance as batch algorithms, when the number of data grows large (Biehl and Riegler 1994; Barkai et al 1995; Kim and Sompolinsky 1996).

In order to understand the abilities and limitations of online algorithms, the question of optimal online learning has been raised.

Abstract

We analyse online gradient descent learning from finite training sets at non-infinitesimal learning rates η for both linear and non-linear networks. In the linear case, exact results are obtained for the time-dependent generalization error of networks with a large number of weights N, trained on p = αN examples. This allows us to study in detail the effects of finite training set size α on, for example, the optimal choice of learning rate η. We also compare online and offline learning, for respective optimal settings of η at given final learning time. Online learning turns out to be much more robust to input bias and actually outperforms offline learning when such bias is present; for unbiased inputs, online and offline learning perform almost equally well. Our analysis of online learning for non-linear networks (namely, soft-committee machines), advances the theory to more realistic learning scenarios. Dynamical equations are derived for an appropriate set of order parameters; these are exact in the limiting case of either linear networks or infinite training sets. Preliminary comparisons with simulations suggest that the theory captures some effects of finite training sets, but may not yet account correctly for the presence of local minima.

Introduction

The analysis of online (gradient descent) learning, which is one of the most common approaches to supervised learning found in the neural networks community, has recently been the focus of much attention. The characteristic feature of online learning is that the weights of a network (‘student’) are updated each time a new training example is presented, such that the error on this example is reduced.

Abstract

On-line supervised learning in the general K Tree Committee Machine (TCM) is studied for a uniform distribution of inputs. Examples are corrupted by multiplicative noise in the teacher output. From the differential equations which describe the learning dynamics, the modulation function which optimizes the generalization ability is exactly obtained for any finite K. The asymptotical behavior of the generalization error is shown to be independent of K. Robustness with respect to a misestimation of the noise level is also shown to be independent of K.

Introduction

When looking into the properties of different neural network architectures by studying their performance in different model situations, the main objective, rather than delving into the many differences, is to search for similarities. It is from these similarities that intrinsic properties of learning, that go beyond the particular characteristics of the simple models, may be identified.

In order to develop a program of this nature several studies within the community of Statistical Mechanics of Neural Networks (Watkin, Rau and Biehl, 1993) have been pursued. Among the most important contributions that this approach brings to the study of machine learning is the possibility of dealing with networks of a very large size, that is in the thermodynamic limit (TL) and of introducing efficient techniques to average over the randomness associated to the data. The model scenarios that have been analized arise from combinations of the different learning conditioning factors. These include, among others, unsupervised versus supervised learning, realizable rules or not, learning in the presence of noise or in the more idealized noiseless case, learning in a time dependent or constant environment.

A great deal of hyperbole has been devoted to neural networks, both in their first wave around 1960 (Widrow & Hoff, 1960; Rosenblatt, 1962) and in their renaissance from about 1985 (chiefly inspired by Rumelhart & McClelland, 1986), but the ideas of biological relevance seem to us to have detracted from the essence of what is being discussed, and are certainly not relevant to practical applications in pattern recognition. Because ‘neural networks’ has become a popular subject, it has collected many techniques which are only loosely related and were not originally biologically motivated. In this chapter we will discuss the core area of feed-forward or ‘back-propagation’ neural networks, which can be seen as extensions of the ideas of the perceptron (Section 3.6). From this connection, these networks are also known as multi-layer perceptrons.

A formal definition of a feed-forward network is given in the glossary. Informally, they have units which have one-way connections to other units, and the units can be labelled from inputs (low numbers) to outputs (high numbers) so that each unit is only connected to units with higher numbers. The units can always be arranged in layers so that connections go from one layer to a later layer. This is best seen graphically; see Figure 5.1.

Pattern recognition has a long and respectable history within engineering, especially for military applications, but the cost of the hardware both to acquire the data (signals and images) and to compute the answers made it for many years a rather specialist subject. Hardware advances have made the concerns of pattern recognition of much wider applicability. In essence it covers the following problem:

There are many examples from everyday life:

Many of these are currently performed by human experts, but it is increasingly becoming feasible to design automated systems to replace the expert and either perform better (as in credit scoring) or ‘clone’ the expert (as in aids to medical diagnosis).

Neural networks have arisen from analogies with models of the way that humans might approach pattern recognition tasks, although they have developed a long way from the biological roots. Great claims have been made for these procedures, and although few of these claims have withstood careful scrutiny, neural network methods have had great impact on pattern recognition practice.