What we can do and what we want to do on a computer?

The high speed and memory capacity of computers have been changing our lives. Computers can now do many things that were once possible only in dreams. We want people who study software science to have even bigger dreams. We want people to dream about what new things we could do on a computer if we understood the technology better.

One of these dreams is to improve our information processing ability by building a system that can recognize objects in the world and learn new information about them. In fact, many researchers and engineers have already started working on this dream and part of the dream has already been implemented. The effort of these researchers and progress in computer science and computer technology mean that even college students are now in a position to study the problems of recognition and learning by computer.

We hope people will learn the basics of pattern recognition and learning by computer and go on to challenge the capabilities of future computers in these areas. This book is intended to help such students.

Pattern recognition

In order to recognize an apple in front of us, we need to be able to determine the edge of the apple and its background. We also need to be able to tell an apple from an orange using our knowledge of fruit. It was a dream of engineers to make a computer recognize things that we recognize unconsciously. What made this dream come true has been the data processing capability and speed of modern computers. These capabilities, which include both basic computer operations and symbolic processing, like high-speed inference, have made it possible for us to build sophisticated pattern recognition systems.

Today, in visual pattern recognition, a computer can interpret properties of an image by using knowledge to understand what objects appear in a pattern. This technology and other basic methods are currently applied in various everyday information processing tasks like reading characters, numbers, and illustrations automatically, analyzing photographs, recognizing three-dimensional patterns, understanding moving objects, etc. The fields requiring sophisticated pattern understanding technology have been expanding and they now include medical diagnosis, library information, knowledgeable robots, space technology, and support for working in extreme environments.

This book explains methods of pattern recognition that are the bases of such technology for visual patterns.

Learning new information

If we could arrange data in a new way and adjust a system so it could handle input of unknown form, the value of the computer as an information processing tool would improve substantially. The study of making a computer have the ability to incorporate new information is motivated not only by the simple desire to reduce the complexity of computer programs but also by the possibility of usefulness in actual applications.

For systems that use artificial intelligence technology, i.e., the technology of doing inference using large amounts of structured knowledge, one problem is how to input and manage large amounts of knowledge. Some people have been studying tools for making computers acquire knowledge semi-automatically. The basic methods of learning are important in improving knowledge acquisition technology.

There are several methods a computer can use to learn; it can remember the input information as it is received, remember input information in an internal machine representation, learn using examples, learn using analogy by creating new information similar to already known information, etc. There are also methods of learning using different forms of representation for the learned information and using different methods to display the input information.

This book describes representative methods of learning by computer.

Generation and transformation of representation

There are many representation methods. For example, at the lowest level machine language programs are represented as bit arrays of 0’s and 1’s. Information in high-level computer programs is expressed using numbers and letters. A computer can be thought of as a machine for generating and transforming these information representations.

This interpretation of a computer is especially applicable in the area of pattern recognition and learning. Pattern recognition can be thought of as the representation of properties of the input data using a representation that is different from the input data. Learning can be thought of as the creation of a new representation of the data using the input and some information already stored in the computer. Using this interpretation, we can think of both pattern recognition and learning on a computer as highly sophisticated examples of creating and manipulating the representation of information.

This book is based on the idea that the generation and transformation of information representations can be used to explain both pattern recognition and learning, problems that have traditionally been studied as different subjects.

The structure of this book

This book describes the details of the basic methods of pattern recognition and learning. You will be able to understand the main points by careful reading. It can be used as a textbook for a half-year or one-year undergraduate course or a beginning graduate course.

Chapter 1 defines recognition and learning on a computer from the point of view of the generation and transformation of information. Chapters 2 and 3 describe different methods of representing information that will be used in pattern recognition and learning and also gives methods for creating and manipulating such representations. Chapters 1, 2, and 3 are preparation for the rest of the book and are also useful as basic information for learning about artificial intelligence as a whole. We recommend reading these chapters first even if you are only interested in pattern recognition or in learning.

Since pattern recognition and learning use different algorithms, you can learn the individual algorithms independently. Chapters 4 and 5 explain pattern recognition and Chapters 6–9 explain learning. Chapter 10 explains methods of a type different from those in Chapters 4–9. Readers can turn to either Chapters 4 and 5, Chapters 6–9, or 10 after reading Chapters 1–3.

Chapter 4 describes methods for extracting the properties of patterns and Chapter 5 discusses methods for understanding what objects are included in a pattern once these properties have been extracted. These two chapters are the main chapters on learning to recognize patterns.

Chapters 6–9 describe methods of learning using symbols for representing information. Chapter 6 covers the basics of learning on a computer. Chapters 7, 8, and 9 describe different learning methods. Readers can turn to any of these chapters after reading Chapter 6.

Chapter 10 describes a method of learning using a distributed pattern representation. It goes on to describe a method that unifies pattern recognition and learning, which is different from the methods explained in Chapters 4–9. This chapter can be read independently of 4–9.

This book is structured so that readers can choose whichever chapters interest them. For your reference, Figure G.1 shows the relation among chapters.

Exercises

At the end of each chapter there are exercises to help readers understand the main ideas and algorithms better. Some exercises contain important representation methods and algorithms that this book could not cover.

Answers for all the exercises are available. We hope you make good use of these problems.

Knowledge necessary to read this book

We have designed this book so that readers with the mathematical knowledge of a sophomore in engineering or science can understand it well. It does not require any higher mathematics. Although the representation of information in this book includes diverse subjects like infinitesimal calculus and formal logic, one of the nice things about pattern recognition and learning is that we can treat representations that look totally different in a uniform way. In this sense, we think the study of recognition and learning on a computer can provide knowledge and tools that are applicable in many areas.

What this book does not cover

Since the problems of pattern recognition and learning stretch over wide areas of knowledge, it is impossible to gather them together in one book. This book describes the things that we think are basic. Specialists in this field may find that this book lacks some important research problems. For example, this book covers recognition only for image patterns. It does not describe voice pattern recognition, which is also an important topic. It also does not cover three-dimensional image patterns, which are a popular research topic. In learning, we do not talk about solving logical problems using inductive inference, learning grammars, or the problem of bias due to differences in expression. Each of these is an important topic. We have also omitted descriptions of genetic algorithms.

The reason for not including these subjects is that the book’s purpose is to supply basic and useful knowledge for students who are going to study software science. This book minimizes the number of topics in order to include as many concrete examples as possible. Subjects that this book does not cover belong in an advanced textbook, although they are all important. To learn about the things that are not included here, please refer to the list of references at the end of this book. These include other books in the Iwanami Software Science Series, especially Knowledge and Inference (volume 14), Natural Language Processing (volume 15), and Models and Representation (volume 17). I also recommend writing computer programs.

This book does not pay much attention to which programming language is used. (It includes examples in C, Lisp, Pascal, and Prolog, but you can understand them without knowing about such languages.) This is because we have limited our explanation of the algorithms to the conceptual level so that the reader can understand the point of the method more clearly. However, it is important to learn programming languages. You should study recognition and learning while you acquire a basic understanding of software science as a whole. This includes knowledge of computer architecture, operating systems, programming languages, algorithms, knowledge models and their representation, etc. Otherwise, you will understand only the surface of software science. We recommend that you read other books of this series along with this book.