Paradigms

The problem of telling the guys from the gals encapsulates a large part of Pattern Recognition. It may seem frivolous to put it in these terms, but the problem has all the essential content of the general problem (and it helps to focus the mind!) In general, we have a set of objects which human beings have decided belong into a finite number of classes or categories, for example, the objects might be human beings, or letters of the alphabet. We have some choice of measuring process which is applied to each object to turn it into a point in some space, or alternatively a vector or array of numbers. (If the vectors all have length n we say they are n-dimensional: 2 and 3 dimensional vectors correspond in an obvious way to points in a plane and in the space we live in by simply setting up a co-ordinate system. Hence the terminology.) So we have a set of labelled points in ${\fam11\tenbbb R}^n$ for some n, where the label tells us what category the objects belong to. Now a new point is obtained by applying the measuring process to a new object, and the problem is to decide which class it should be assigned to.

There is a clear division of the problem of automatically recognising objects by machine into two parts. The first part is the measuring process. What are good things to measure? This is known in the jargon of the trade as the `feature selection problem', and the resulting ${\fam11\tenbbb R}^n$ obtained is called the feature space for the problem.

A little thought suggests that this could be the hard part. One might reasonably conclude, after a little more thought, that there is no way a machine could be made which would be able to always measure the best possible things. Even if we restrict the problem to a machine which looks at the world, that is to dealing with images of things as the objects we want to recognise or classify, it seems impossible to say in advance what ought to be measured from the image in order to make the classification as reliable as possible. What is usually done is that a human being looks at some of the images, works out what he thinks the significant `features' are, and then tries to figure out a way of extracting numbers from images so as to capture quantitatively the amount of each `feature', thus mapping objects to points in the feature space, ${\fam11\tenbbb R}^n$ for some n. This is obviously cheating, since ideally the machine ought to work out for itself, from the data, what these `features' are, but there are, as yet, no better procedures.

The second part is, having made some measurements on the image (or other object) and turned it into a point in a vector space, how does one calculate the class of a new point? What we need is some rule or algorithm because the data will be stored in a computer. The algorithm must somehow be able to compare, by some arithmetic/logical process, the new vector with the vectors where the class is known, and come out with a plausible guess.

Exercise!

It is a good idea to make these issues as concrete as possible, so you should, at this point, get some real data so as to focus the mind. This needs a kitchen weighing scales and a ruler, and a kitchen.

Get some eggs and some potatoes, For each egg first weigh it, write down its weight, then measure its greatest diameter, and write that down underneath. Repeat for all the eggs. This gives the egg list. Half a dozen (six) eggs should be enough.

Now do the same with a similar number of potatoes. This will give a potato list.

Plot the eggs on a piece of graph paper, just as for the guys and the gals, marking each one in red, repeat for the potatoes marking each as a point in blue.

Now take three objects from the kitchen at random (in my case, when I did this, I chose a coffee cup, a spoon and a box of matches); take another egg and another potato, make the same measurements on the five objects, and mark them on your graph paper in black.

Now how easy is it to tell the new egg from the new potatoe by looking at the graph paper? Can you see that all the other three objects are neither eggs nor potatoes? If the pairs of numbers were to be fed into a computer for a decision as to whether a new object is an egg or a potato, (or neither), what rule would you give the computer program for deciding?

What things should you have measured in order to reliably tell eggs from potatoes? Eggs from coffee-cups?

There are other issues which will cross the mind of the reflective reader: how did the human beings decide the actual categories in the first place? Don't laugh, but just how do you tell a man from a woman? By looking at them? In that case, your retinal cells and your brain cells between them must contain the information. If you came to an opinion about the best category to assign P in the problem of Fig.1.2. just by looking at it, what unarticulated rule did you apply to reach that conclusion? Could one articulate a rule that would agree with your judgement for a large range of cases of location of the new point P? Given any such rule, how does one persuade oneself that it is a good rule?

It is believed by almost all zoologists that an animal is a machine made out of meat, a robot constructed from colloids, and that this machine implements rules for processing sensory data with its brain in order to survive. This usually entails being able to classify images of other animals: your telling a man from a woman by looking is just a special case. We have then, an existence proof that the classification problems in which we are interested do in fact have solutions; the trouble is the algorithms are embedded in what is known in the trade as `wetware' and are difficult to extract from the brain of the user. Users of brains have been known to object to the suggestion, and anyway, nobody knows what to look for.

It is believed by some philosophers that the zoologists are wrong, and that minds do not work by any algorithmic processes. Since fruit bats can distinguish insects from thrown lumps of mud, either fruit bats have minds that work by non-algorithmic processes just like philosophers, or there is some fundamental difference between you telling a man from a woman and a fruit bat telling mud from insects, or the philosophers are babbling again. If one adopts the philosopher's position, one puts this book away and finds another way to pass the time. Now the philosopher may be right or he may be wrong; if he is right and you give up reading now, he will have saved you some heartbreak trying to solve an unsolvable problem. On the other hand, if he is right and if you continue with the book you will have a lot of fun even if you don't get to understand how brains work. If the philosopher is wrong and you give up, you will certainly have lost out on the fun and may lose out on a solution. So we conclude, by inexorable logic, that it is a mistake to listen to such philosophers, something which most engineers take as axiomatic anyway.

Wonderful stuff logic, even if it was invented by a philosopher.

It is currently intellectually respectable to muse about the issue of how brains accomplish these tasks, and it is even more intellectually respectable (because harder) to experiment with suggested methods on a computer. If we take the view that brains somehow accomplish pattern classification or something rather like it, then it is of interest to make informed conjectures about how they do it, and one test of our conjectures is to see how well our algorithms perform in comparison with animals. We do not investigate the comparison in this book, but we do try to produce algorithms which can be so tested, and our algorithms are motivated by theoretical considerations and speculations on how brains do the same task. So we are doing Cognitive Science on the side. Having persuaded ourselves that the goal is noble and worthy of our energies, let us return to our muttons and start on the job of getting closer to that goal.

The usual way, as was explained above, of tackling the first part, of choosing a measuring process, is to leave it to the experimenter to devise one in any way he can. If he has chosen a good measuring process, then the second part will be easy: if the height and weight of the individual were the best you can do, telling men from women is hard, but if you choose to measure some other things, the two sets of points, the X's and O's, can be well separated and a new point P is either close to the X's or close to the O's or it isn't a human being at all. So you can tell retrospectively if your choice of what to measure was good or bad, up to a point. It not infrequently happens that all known choices are bad, which presents us with interesting issues. I shall return to this aspect of Pattern Recognition later when I treat Syntactic or Structured Pattern Recognition.

The second part assumes that we are dealing with (labelled) point sets in ${\fam11\tenbbb R}^n$ belonging to two or more types. Then we seek a rule which gives us, for any new point, a label. There are lots of such rules. We consider a few in the next section.

Remember that you are supposed to be relaxed and casual at this stage, doing some general thinking and turning matters over in your mind! Can you think, in the light of eggs, potatoes and coffee-cups, of some simple rules for yourself?