Results from computational learning theory are important in many aspects of machine learning practice. Understanding the behaviour of systems that learn to solve information processing problems (like pattern recognition and prediction) is crucial for the design of effective systems. In recent years, ideas and techniques in computational learning theory have matured to the point where theoretical advances are now contributing to machine learning applications, both through increased understanding and through the development of new practical algorithms.

In this book, we concentrate on statistical and computational questions associated with the use of rich function classes, such as artificial neural networks, for pattern recognition and prediction problems. These issues are of fundamental importance in machine learning, and we have seen several significant advances in this area in the last decade. The book focuses on three specific models of learning, although the techniques, results, and intuitions we obtain from studying these formal models carry over to many other situations.

The book is aimed at researchers and graduate students in computer science, engineering, and mathematics. The reader is assumed to have some familiarity with analysis, probability, calculus, and linear algebra, to the level of an early undergraduate course. We remind the reader of most definitions, so it should suffice just to have met the concepts before.

Most chapters have a ‘Remarks’ section near the end, containing material that is somewhat tangential to the main flow of the text.

Introduction

The previous chapter demonstrated that efficient SEM and approximate-SEM algorithms for graded classes F = ∪Fn give rise to efficient learning algorithms, provided the expressive power of Fn grows polynomially with n (in, respectively, the binary classification and real prediction learning models). In this chapter we show that randomized SEM and approximate-SEM algorithms suffice, and that a converse result then holds: if efficient learning is possible then there must exist an efficient randomized approximate-SEM algorithm. (Hence, for the case of a binary function class, there must be an efficient randomized SEM algorithm.) This will establish that, in both models of learning, efficient learning is intimately related to the optimization problem of finding a hypothesis with small sample error.

Randomized Algorithms

For our purposes, a randomized algorithm has available to it a random number generator that produces a sequence of independent, uniformly distributed bits. We shall assume that examining one bit of this random sequence takes one unit of time. (It is sometimes convenient to assume that the algorithm has access to a sequence of independent uniformly distributed integers in the set {0, 1, …, I}, for some I ≥ 1; it is easy to construct such a sequence from a sequence of random bits.) The randomized algorithm A uses these random bits as part of its input, but it is useful to think of this input as somehow ‘internal’ to the algorithm, and to think of the algorithm as defining a mapping from an ‘external’ input to a probability distribution over outputs.

Introduction

In this chapter we show that the consistency problem can be hard for some very simple feed-forward neural networks. In Section 25.2, we show that, for certain graded spaces of feed-forward linear threshold networks with binary inputs, the consistency problem is NP-hard. This shows that for each such family of networks, unless RP = NP, there can be no efficient learning algorithm in the restricted learning model and hence, in particular, no efficient learning algorithm in the standard model of Part 1. These networks are somewhat unusual in that the output unit is constrained to compute a conjunction. In Section 25.3, we extend the hardness result to networks with an arbitrary linear threshold output unit, but with real inputs. In Section 25.4, we describe similar results for graded classes of feed-forward sigmoid networks with linear output units, showing that approximately minimizing sample error is NP-hard for these classes. Unless RP = NP, this shows that there can be no efficient learning algorithm in the restricted learning model of Part 3.

Linear Threshold Networks with Binary Inputs

For each positive integer n, we define a neural network on n inputs as follows. The network has n binary inputs and k + 1 linear threshold units (k ≥ 1). It has two layers of computation units, the first consisting of k linear threshold units, each connected to all of the inputs.

Introduction

The general upper and lower bounds on sample complexity described in Chapters 4 and 5 show that the VC-dimension determines the sample complexity of the learning problem for a function class H. The results of Chapters 6 and 8 show that, for a variety of neural networks, the VC-dimension grows with the number of parameters. In particular, the lower bounds on the VC-dimension of neural networks described in Section 6.3, together with Theorem 6.5, show that with mild conditions on the architecture of a multi-layer network and the activation functions of its computation units, the VC-dimension grows at least linearly with the number of parameters.

These results do not, however, provide a complete explanation of the sample size requirements of neural networks for pattern classification problems. In many applications of neural networks the network parameters are adjusted on the basis of a small training set, sometimes an order of magnitude smaller than the number of parameters. In this case, we might expect the network to ‘overfit’, that is, to accurately match the training data, but predict poorly on subsequent data. Indeed, the results from Part 1 based on the VC-dimension suggest that the estimation error could be large, because VCdim(H)/m is large. Nonetheless, in many such situations these networks seem to avoid overfitting, in that the training set error is a reliable estimate of the error on subsequent examples. Furthermore, Theorem 7.1 shows that an arbitrarily small modification to the activation function can make the VC-dimension infinite, and it seems unnatural that such a change should affect the statistical behaviour of networks in applications.

Introduction

The previous chapter gave a formal definition of the learning problem, and showed that it can be solved if the class HN of functions is finite. However, many interesting function classes are not finite. For example, the number of functions computed by the perceptron with real-valued weights and inputs is infinite. Many other neural networks can also be represented as a parameterized function class with an infinite parameter set. We shall see that learning is possible for many (but not all) function classes like this, provided the function class is not too complex. In this chapter, we examine two measures of the complexity of a function class, the growth function and the VC-dimension, and we show that these are intimately related. In the next two chapters, we shall see that the growth function and VC-dimension of a function class determine the inherent sample complexity of the learning problem.

The Growth Function

Consider a finite subset S of the input space X. For a function class H, the restriction of H to the set S (that is, the set of restrictions to S of all functions in H) is denoted by H|s. If H|s is the set of all functions from S to {0, 1}, then clearly, H is as powerful as it can be in classifying the points in S. We can view the cardinality of H|s (and in particular how it compares with 2|s|) as a measure of the classification complexity of H with respect to the set S.

Introduction

Chapters 4 and 5 show that the Vapnik-Chervonenkis dimension is crucial in characterizing learnability by binary-output networks, and that it can be used to bound the growth function. Chapter 10 shows that covering numbers are a generalization of the growth function useful for analysing classification by real-output neural networks (or, more generally, by real-valued function classes). We see later in the book that covering numbers are also important in analysing other models of learning. It is natural to ask whether there is a ‘combinatorial’ measure analogous to the VC-dimension that can be used to bound the covering numbers of a class of real-valued functions, and hence to quantify the sample complexity of classification learning. This is largely true, although the definitions and proofs are more complicated than for the binary classification case. In this chapter we introduce the key ‘dimensions’ that we use in our analysis of learning with real function classes and establish some associated basic results and useful properties. In the next chapter we show how these dimensions may be used to bound the covering numbers.

The Pseudo-Dimension

The definition of the pseudo-dimension

To introduce the first of the new dimensions, we first present a slightly different formulation of the definition of the VC-dimension. For a set of functions H mapping from X to {0, 1}, recall that a subset S = {x1, x2, … xm} of X is shattered by H if H|s has cardinality 2m.