Bishop C.M. Pattern Recognition and Machine Learning (2006) (811375), страница 4
Текст из файла (страница 4)
For instance, the extensive astronomical observations of TychoBrahe in the 16th century allowed Johannes Kepler to discover the empirical laws ofplanetary motion, which in turn provided a springboard for the development of classical mechanics. Similarly, the discovery of regularities in atomic spectra played akey role in the development and verification of quantum physics in the early twentieth century. The field of pattern recognition is concerned with the automatic discovery of regularities in data through the use of computer algorithms and with the use ofthese regularities to take actions such as classifying the data into different categories.Consider the example of recognizing handwritten digits, illustrated in Figure 1.1.Each digit corresponds to a 28×28 pixel image and so can be represented by a vectorx comprising 784 real numbers. The goal is to build a machine that will take such avector x as input and that will produce the identity of the digit 0, .
. . , 9 as the output.This is a nontrivial problem due to the wide variability of handwriting. It could be121. INTRODUCTIONFigure 1.1Examples of hand-written digits taken from US zip codes.tackled using handcrafted rules or heuristics for distinguishing the digits based onthe shapes of the strokes, but in practice such an approach leads to a proliferation ofrules and of exceptions to the rules and so on, and invariably gives poor results.Far better results can be obtained by adopting a machine learning approach inwhich a large set of N digits {x1 , . . . , xN } called a training set is used to tune theparameters of an adaptive model.
The categories of the digits in the training setare known in advance, typically by inspecting them individually and hand-labellingthem. We can express the category of a digit using target vector t, which representsthe identity of the corresponding digit. Suitable techniques for representing categories in terms of vectors will be discussed later. Note that there is one such targetvector t for each digit image x.The result of running the machine learning algorithm can be expressed as afunction y(x) which takes a new digit image x as input and that generates an outputvector y, encoded in the same way as the target vectors.
The precise form of thefunction y(x) is determined during the training phase, also known as the learningphase, on the basis of the training data. Once the model is trained it can then determine the identity of new digit images, which are said to comprise a test set. Theability to categorize correctly new examples that differ from those used for training is known as generalization. In practical applications, the variability of the inputvectors will be such that the training data can comprise only a tiny fraction of allpossible input vectors, and so generalization is a central goal in pattern recognition.For most practical applications, the original input variables are typically preprocessed to transform them into some new space of variables where, it is hoped, thepattern recognition problem will be easier to solve.
For instance, in the digit recognition problem, the images of the digits are typically translated and scaled so that eachdigit is contained within a box of a fixed size. This greatly reduces the variabilitywithin each digit class, because the location and scale of all the digits are now thesame, which makes it much easier for a subsequent pattern recognition algorithmto distinguish between the different classes. This pre-processing stage is sometimesalso called feature extraction. Note that new test data must be pre-processed usingthe same steps as the training data.Pre-processing might also be performed in order to speed up computation.
Forexample, if the goal is real-time face detection in a high-resolution video stream,the computer must handle huge numbers of pixels per second, and presenting thesedirectly to a complex pattern recognition algorithm may be computationally infeasible. Instead, the aim is to find useful features that are fast to compute, and yet that1. INTRODUCTION3also preserve useful discriminatory information enabling faces to be distinguishedfrom non-faces.
These features are then used as the inputs to the pattern recognitionalgorithm. For instance, the average value of the image intensity over a rectangularsubregion can be evaluated extremely efficiently (Viola and Jones, 2004), and a set ofsuch features can prove very effective in fast face detection. Because the number ofsuch features is smaller than the number of pixels, this kind of pre-processing represents a form of dimensionality reduction. Care must be taken during pre-processingbecause often information is discarded, and if this information is important to thesolution of the problem then the overall accuracy of the system can suffer.Applications in which the training data comprises examples of the input vectorsalong with their corresponding target vectors are known as supervised learning problems.
Cases such as the digit recognition example, in which the aim is to assign eachinput vector to one of a finite number of discrete categories, are called classificationproblems. If the desired output consists of one or more continuous variables, thenthe task is called regression. An example of a regression problem would be the prediction of the yield in a chemical manufacturing process in which the inputs consistof the concentrations of reactants, the temperature, and the pressure.In other pattern recognition problems, the training data consists of a set of inputvectors x without any corresponding target values.
The goal in such unsupervisedlearning problems may be to discover groups of similar examples within the data,where it is called clustering, or to determine the distribution of data within the inputspace, known as density estimation, or to project the data from a high-dimensionalspace down to two or three dimensions for the purpose of visualization.Finally, the technique of reinforcement learning (Sutton and Barto, 1998) is concerned with the problem of finding suitable actions to take in a given situation inorder to maximize a reward. Here the learning algorithm is not given examples ofoptimal outputs, in contrast to supervised learning, but must instead discover themby a process of trial and error.
Typically there is a sequence of states and actions inwhich the learning algorithm is interacting with its environment. In many cases, thecurrent action not only affects the immediate reward but also has an impact on the reward at all subsequent time steps. For example, by using appropriate reinforcementlearning techniques a neural network can learn to play the game of backgammon to ahigh standard (Tesauro, 1994). Here the network must learn to take a board positionas input, along with the result of a dice throw, and produce a strong move as theoutput. This is done by having the network play against a copy of itself for perhaps amillion games.
A major challenge is that a game of backgammon can involve dozensof moves, and yet it is only at the end of the game that the reward, in the form ofvictory, is achieved. The reward must then be attributed appropriately to all of themoves that led to it, even though some moves will have been good ones and othersless so. This is an example of a credit assignment problem. A general feature of reinforcement learning is the trade-off between exploration, in which the system triesout new kinds of actions to see how effective they are, and exploitation, in whichthe system makes use of actions that are known to yield a high reward.
Too stronga focus on either exploration or exploitation will yield poor results. Reinforcementlearning continues to be an active area of machine learning research. However, a41. INTRODUCTIONFigure 1.2Plot of a training data set of N =10 points, shown as blue circles,each comprising an observationof the input variable x along withthe corresponding target variablet. The green curve shows thefunction sin(2πx) used to generate the data. Our goal is to predict the value of t for some newvalue of x, without knowledge ofthe green curve.1t0−10x1detailed treatment lies beyond the scope of this book.Although each of these tasks needs its own tools and techniques, many of thekey ideas that underpin them are common to all such problems.
One of the maingoals of this chapter is to introduce, in a relatively informal way, several of the mostimportant of these concepts and to illustrate them using simple examples. Later inthe book we shall see these same ideas re-emerge in the context of more sophisticated models that are applicable to real-world pattern recognition applications. Thischapter also provides a self-contained introduction to three important tools that willbe used throughout the book, namely probability theory, decision theory, and information theory.
Although these might sound like daunting topics, they are in factstraightforward, and a clear understanding of them is essential if machine learningtechniques are to be used to best effect in practical applications.1.1. Example: Polynomial Curve FittingWe begin by introducing a simple regression problem, which we shall use as a running example throughout this chapter to motivate a number of key concepts. Suppose we observe a real-valued input variable x and we wish to use this observation topredict the value of a real-valued target variable t. For the present purposes, it is instructive to consider an artificial example using synthetically generated data becausewe then know the precise process that generated the data for comparison against anylearned model.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
