Pattern Recognition and Machine Learning

Y. Anzai

• Publisher: Morgan Kaufmann
• Year: 2012
• ISBN:
  9780080513638
• Topic: Computer Science
• Subtopic: Artificial Intelligence (AI) & Semantics
• Index: Computer Science

This is the first text to provide a unified and self-contained introduction to visual pattern recognition and machine learning. It is useful as a general introduction to artifical intelligence and knowledge engineering, and no previous knowledge of pattern recognition or machine learning is necessary. Basic for various pattern recognition and machine learning methods. Translated from Japanese, the book also features chapter exercises, keywords, and summaries.

1

Recognition and Learning by a Computer

KEYWORDS

pattern recognition

learning

representation

underconstrained problem

generalization

transformation

recognition/learning system

In the past computers have been used mainly as tools for data processing. As the processing speed and the amount of data that can be processed by a computer have increased, we have discovered that we can use computers as more intelligent information processing tools. With this idea in mind, we can look at how a computer could be used for recognizing patterns and learning new information. This book is based on the idea that recognition and learning by a computer can be looked at as the process of generating an appropriate representation for information and transforming it into another representation using both the high speed of modern computers and their ability to process a large amount of data. In this chapter, we describe what we mean by the representation, generation, and transformation of information on a computer.

1.1 What Is Recognition by a Computer?

Many academic fields, like philosophy and psychology, use the word “recognition.” In each field it has a slightly different meaning. The literal meaning of recognition is to know again what has been known before. In computer science we use the word “recognition” to mean that a computer can recognize that the patterns of objects are ones that it has seen before. By the pattern of an object we mean any chronological or spatial data received from the object by an input device and entered into the recognition system. Although it is important to study the meaning of “recognition” in fields other than computer science, in this book we will use the computer science meaning of this word.

Suppose we have a pattern consisting of an object A and a background B as shown in Figure 1.1. In order to distinguish A from the background B in this pattern, we need to find the boundary that separates A from B. Usually, patterns such as Figure 1.1 include not only the object A and the background B but also noise (input information other than the data that are directly obtained from the object). Furthermore, the boundary may not be a continuous line. So, in order to find the boundary of A, we not only need to check the light and shading of each point on the boundary but also need to estimate the shape of the whole boundary.

Figure 1.1 A pattern consisting of an object A and a background B.

If we can estimate where to find the boundary line between A and B, we can determine the region encompassed by the boundary, and, as a result, we will be able to distinguish A from B. However, we still do not know what the object A is. In order to know whether A is a glass, a vase, or a coffee cup, that is, in order to know A conceptually, we need to have some knowledge about the shape and function of a glass, a vase, and a coffee cup. Only after we look at the pattern using such knowledge will we be able to figure out that Figure 1.1 consists of a coffee cup and a wall.

This means that we need at least two kinds of algorithms in order to do recognition by computer. They are

(1) algorithms for extracting the boundary and region of a pattern, and

(2) algorithms for recognizing the original object conceptually based on knowledge of the object, its patterns, and how it is used.

In the above description of Figure 1.1, we used (1) and then (2). In other cases (2) can come before (1) or (1) and (2) can be executed alternately.

In addition to visual patterns, like that in Figure 1.1, there are many other types of patterns, such auditory or tactile, that can be recognized by a computer. This book, however, will discuss only visual patterns.

1.2 Representation and Transformation in Recognition

Frequently, a pattern is represented as a function. For example, the pattern of the coffee cup in Figure 1.1 could be represented using a pattern function whose input is coordinates of a point and whose value is the image density at each point. For visual patterns, we also call this a (visual) image function. A pattern function usually contains noise and often does not contain complete data.

Once we have estimated the boundary and region of a pattern and we have used general knowledge to recognize it conceptually, the information about this pattern will have a different structure than the original pattern function. For example, once a pattern has been recognized conceptually, it might include symbolic information describing the object such as “coffee cup” and “table” or symbols representing a relation between objects such as “the coffee cup A is on the table.” Figure 1.2 shows sample representations for a coffee cup.

Figure 1.2 Various representations for the coffee cup shown in Figure 1.1.

As you can see, the process of pattern recognition can use many different representations including pattern functions, sets of regions divided by boundary lines, symbols describing an object, and relations among objects. These representations can be represented in a computer using many different data structures. For example, symbols and relations among symbols can be represented using graph theory (see Section 2.3). We call the data structures used to describe these representations in a computer the representation of the information.

Now we can say that the process of pattern recognition is either to create a new representation or to change one representation into another, starting from an object’s representation as a pattern function. We can also say that the purpose of pattern recognition by a computer is to generate and transform useful representations of information using the high speed and the massive data processing capability of the computer.

Based on the above, the study of pattern recognition needs to consider the following two problems:

(A) What methods of representation are available for patterns?

(B) What methods are available for transforming one representation into another?

Since the algorithms (1) and (2) mentioned earlier are for transforming representations, they belong to (B). We will describe this kind of algorithm in Chapter 3 and in ...