Pattern Recognition
Pattern Recognition
Pattern recognition is a branch of science that helps develop "classifiers" that can recognize unknown instances of objects. In this context, to recognize an object means to classify it, or to assign it to one of a set of possible classes or labels. This class assignment of objects is based on an analysis of the values of one or more features of the object. Pattern recognition techniques are used in a wide variety of commercial applications. Common examples include character recognition, such as the scanning of a printed page of text into a word processor; natural language recognition, such as using voice commands to relay a set of possible responses to a computer system over the phone; analysis of fingerprint, face, or eye images in order to verify a person's identity; analysis of images taken from airplanes or satellites, perhaps in order to detect and track oil spills in the ocean; or analysis of medical images in order to scan for abnormalities, such as cancer vs. normal tissue.
Humans have a powerful ability to classify objects based on sensory input. They can easily read documents printed in a wide variety of type fonts, including handwritten documents. Such ability is all the more amazing because it often seems to require little conscious effort. Although humans have the ability to read patterns, there are at least two potential advantages to using computer systems for pattern recognition. Even if a person with minimal training could perform a certain task, he or she might not be able to handle the volume of work in a timely fashion, or without becoming bored and error-prone. For example, reading handwritten addresses on pieces of mail is a simple task in principle, but is made difficult by the repetitive nature of handling a large number of pieces of mail. In other cases, such as recognizing signs of cancer in x-ray images, the task requires specialized training, and there simply may not be as many human experts as needed.
Another difficulty in pattern recognition is ambiguity . That is, a particular pattern may have multiple possible interpretations, each of which is equally reasonable. Sometimes this problem can be resolved by considering the local context of the pattern. A common illustration of ambiguity and context is presented in Figure 1. The interpretation of the middle object is ambiguous. In the context of the column, the object could reasonably be interpreted as a "B," and yet in the context of the row, it could reasonably be interpreted as a "13."
Construction of a classifier typically requires the use of some examples whose class label is already known by some other means. The examples used in constructing the classifier are referred to as labeled data because their classification is already known. They may also be referred to as training data because they will be used to train the classifier. Acquiring the appropriate amount and type of training data is one of the secrets to building a successful pattern recognition system.
Consider the example of labeling regions in an x-ray image—each region is classified as either cancerous or normal tissue. The following example of an x-ray (mammogram) image shows a cancerous region. Note that many different regions in the image could be identified as possibly representing an abnormality. The cancerous region is distinguished from the other possible regions by being larger, brighter overall, and having an irregular boundary.
This suggests that useful features for classifying a region might include its size, average brightness, and degree of smoothness of its boundary. To construct the classifier, some example image regions would be identified and their class label determined. The true class label for a region might be determined, for example, by performing a lab test on a tissue sample corresponding to the region. The values of some features of the training samples would be computed. Then the classifier would be constructed by finding some rule for examining the feature values to separate the normal samples from the cancer samples. Then, in use, the classifier would compute the feature values for an unknown region and assign it to either the normal class or the cancer class using the rule "learned" from the training samples. Commercial systems that recognize signs of cancer or other diseases in medical images are more complex than this simple example suggests, but the basic idea is the same.
The essence of constructing a good classifier for a given problem is generally to:
- Select the pattern recognition approach whose assumptions best match the characteristics of the problem;
- Use a set of training data that is large enough and representative of the problem;
- Decide on the "right" features.
Deciding which pattern recognition approach best matches the characteristics of the problem requires an understanding of both the assumptions implicitly made by each approach and a characterization of the problem. Acquiring a set of training data that is large enough, and that is representative of the examples the classifier will see in operation, requires experimental and statistical expertise. Deciding on the right features tends to rely on good intuition about the important properties of objects, and also on experimental analysis to select the better-performing features.
At the highest level, pattern recognition techniques can be divided into structural techniques and statistical techniques. A simplified explanation is that structural techniques assume that the parts of an object are known and look at how the parts fit together to form the whole, whereas statistical approaches simply assume that some properties of the whole can be measured and that the values of properties vary between classes. Of the two approaches, statistical pattern recognition techniques are perhaps more widely used. A few of the many possible approaches under the general umbrella of statistical pattern recognition are Gaussian classifiers , k-nearest-neighbors , and decision trees . The approach known as neural networks is also sometimes considered as a part of statistical pattern recognition. Neural networks have come to be widely used. The use of the word "neural" tends to invoke the idea that the classifier is working like a human brain. However, the structure and operation of the typical neural network classifier are only very loosely inspired by the structure and operation of neurons in the human brain.
Pattern recognition technology has many important uses beyond those already mentioned. It can be used in the area of "data mining" to sift through large amounts of data and spot important trends. For example, pattern recognition techniques might be used to spot credit card fraud, or to detect attempts to break into computer systems. Pattern recognition techniques can also be used in the area of robotics to help robots interpret visual input and move from one place to another. In summary, it should be clear that pattern recognition technology lies at the core of many applications that involve "intelligent" decisions made by computer.
see also Artificial Intelligence; Computer Vision; Data Mining; Neural Networks; Robotics; Robots.
Kevin W. Bowyer
Bibliography
Bunke, Horst, and Alberto Sanfeliu. Syntactic and Structural Pattern Recognition: Theory and Applications. Teaneck, NJ: World Scientific, 1990.
Duda, Richard O., Peter E. Hart, and David G. Stork. Pattern Classification. New York: John Wiley and Sons, 2001.
Fischler, Martin A., and Oscar Firschein. Intelligence: The Eye, the Brain, and the Computer. Reading, MA: Addison-Wesley, 1987.
Jain, Anil K., Ruud Bolle, and Sharath Pankanti, eds. Biometrics: Personal Identification in a Networked Society. Boston: Kluwer, 1999.
Mitchell, Tom M. Machine Learning. Boston: McGraw-Hill, 1997.
Shapiro, Linda G., and George C. Stockman. Computer Vision. Upper Saddle River, NJ: Prentice Hall, 2001.
ambiguity the quality of doubtfulness or uncertainty; often subject to multiple interpretations
labeled data a data item whose class assignment is known independent of the classifier being constructed
training data data used in the creation of a classifier
Gaussian classifiers classifiers constructed on the assumption that the feature values of data will follow a Gaussian distribution
k-nearest-neighbors a classifier that assigns a class label for an unknown data item by looking at the class labels of the nearest items in the training data