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.

As Ryle laments, the initial stages of design with a new “material” often amount to solving yesterday's problems and meeting yesterday's requirements. New possibilities and problems have indeed emerged in the era of CSCW applications. CSCW research and development communities have also taken on older, better-recognized, and still-important problems, problems with their predecessors addressed in efforts to shape groups with the use of artifacts. Several salient cultural objects appear to have traveled with all of these kinds of efforts, most notably that of “efficiency.”

A number of problems are associated with efforts to define or construct a group (in terms of its membership, sphere of action, and scope of accountability). Concern with these problems has surfaced in various forms since the early part of this century (as Sibley's advice in the epigraph suggests).

This book is about virtual individuals and virtual groups. It is also about a specific set of computer system applications – groupware and other network-based systems – and the way we employ them in construction, dissemination, and manipulation of these virtual entities. To an increasing extent, management in organizational contexts has become the management of virtual individuals and groups. These virtual entities are employed in establishing the patterns and setting the standards by which we are evaluated and with which we often must conform.

Virtuality has become a common theme in American life, taking on connotations of the “imaginary,” as well as the “designed” or “engineered”: “virtual corporations” are created when corporations design sets of linkages with each other and with critical environmental factors, thus extending their effective spheres of influence (Davidow and Malone, 1992). Instead of tales about lonely teens and their imaginary companions, stories about an engineered “virtual girl” are consumed in the mass market (Thomson, 1993).

A virtual individual is a selection or compilation of various traces, records, imprints, photographs, profiles, and statistical information that pertain (or could reasonably be said to pertain) to an individual – along with writing done, images produced, sounds associated with, and impressions managed by the individual. The amalgam that results (whatever its components) is associated with the individual in the context of particular genres and artifacts.

What can “privacy,” “anonymity,” or “agency” mean for members of a collaborative workgroup? The presumption that groups are supposed to work together in harmony and close contact may seem to exclude the need for private spaces, the opportunity to make an anonymous contribution, or the capacity to have one's work done by an agent or surrogate. However, these cultural objects have served to shape CSCW and other network-based system applications.

Privacy, anonymity, and agency in the realm of the societal construction of computing applications have a number of common denominators. Each has special associations within the group level: individuals’ expectations for privacy, or the meanings they attach to a statement delivered under the cloak of anonymity, are affected by whether or not they are working in a group or team context. Roles that agents play in computing applications are also sensitive to group context; for instance, groups may set standards for the kinds of activities in which they can be utilized.

These three cultural objects have also been topics of frequent discussion within computer application design communities. “Social analogues,” system features that are intentionally linked by developers to specific cultural objects, have been formulated for each of the three. The question of whether a social analogue will be successful in maintaining a strong linkage with a certain cultural object (beyond the association that designers have attempted to make) has a number of complex dimensions.

Genres are associated with various cultural objects, objects that can attract us to the genres, make us suspicious of them, or even avoid their use. Sites for constructing, expressing, and modifying cultural objects include debate, writing, speeches, legal decisions, imagery, and design, as well as CSCW and other network-based system applications. Construction of cultural objects, like that of artifacts and other physical objects, should be considered in light of its reflexive dimensions. The objects serve to shape the cultures, individuals, and genres that are associated with them, and in turn are given shape.

Issues of dependence, autonomy, and intellectual augmentation are critical aspects of construction of the “first-person plural” – which involves the authority to attach the word “we” to a document, product, or decision. This authority is not automatically given by group members, and is often not recognized by parties outside the group. In some situations, establishment of this authority may depend on the ability of group participants and audiences to segregate the group from the “computer-mediated group.”

“Collaboration” and “cooperation” among individuals – the harnessing of people's skills and talents to conduct projects, make decisions, and create new ideas – are notions that are both commonplace and elusive. The contradiction between the two epigraphs underscores the fact that controversies concerning the value of collaboration are not new. We have all participated in meetings and team projects, in informal exchanges as well as structured games, but these activities remain only vaguely understood and nearly impossible to predict and control with any precision. Our modes of individual and group expression (our “virtual individuals” and “virtual groups”) are intimately linked with the technologies that support group interaction – technologies that have undergone dramatic change in the past decades.

Network-based computer applications designed to support joint efforts (“computer-supported cooperative work,” or CSCW, applications) have both staunch supporters and fierce critics. Promoters have characterized these systems as “coaches” and “educators” (Winograd and Flores, 1986); critics, in turn, have labeled the same systems as “oppressors” and “masters” with a “digitized whip” (Dvorak and Seymour, 1988). The terms “groupware” and “workgroup computing” can be found in many computing, management, and social science publications, along with words of high praise, condemnation, or ennui. Virtual reality (VR) applications have been incorporated into some CSCW initiatives, sometimes compounding confusion about the systems and further steepening the learning curve.

Picture a modern office setting, perhaps an insurance company headquarters. Some people are writing on sheets of paper. Others are looking into computer screens, entering numbers into a spreadsheet. Still others are conversing. Which of these individuals are working individually, and which are engaging in cooperative work? And which of the individuals engaging in cooperative activity are participating in healthy, well-working groups? Some of these issues might appear to be riddles or trick questions. Whether there are “riddles” (or linguistic puzzles) involved, the issue of how best to construe cooperative work activity is one of the most salient focal points of research and theory in CSCW applications.

In much the same manner as healthy and unhealthy forms of individual behavior have been constructed by social scientists, today's administrative theorists, network-based system developers, and CSCW researchers are attempting to construct notions of “functional” and “dysfunctional” collaborative behavior. Several of the theorists whose work is described in this chapter are attempting to segregate some kinds of work as “cooperative” and give them special forms of support. Others want to transform existing forms of work from their current, supposedly noncooperative form into cooperative work. Still others label all work as cooperative and want us to see work itself in a new light. Many have identified “right” ways of thinking about and engaging in cooperative activity, their conclusions bolstered with theoretical scaffolding, empirical research, and appeals to common sense.