Pattern Recognition and Machine Learning Yuichiro Anzai Department of Electrical Engineering Keio University Yokohama, Japan ACADEMIC PRESS, INC. Harcourt Brace Jovanovich, Publishers Boston San Diego New York London Sydney Tokyo Toronto This book is printed on acid-free paper. Θ Copyright © Iwanami Shoten Publishers 1989 English translation copyright © 1992 by Academic Press, Inc. All rights reserved. No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher. ACADEMIC PRESS, INC. 1250 Sixth Avenue, San Diego, CA 92101 United Kingdom edition published by ACADEMIC PRESS LIMITED 24-28 Oval Road, London NW1 7DX Library of Congress Cataloging-in-Publication Data Anzai, Yuichiro, 1946— [Ninshiki to gakushu. English] Pattern recognition and machine learning / Yuichiro Anzai. p. cm. Translation of: Ninshiki to gakushu. Includes bibliographical references and index. ISBN 0-12-058830-7 1. Pattern perception. 2. Machine learning. I. Title. Q327.A5813 1992 006.37—dc20 92-7073 CIP Printed in the United States of America 92 93 94 95 BB 9 8 7 6 5 4 3 2 1 Preface Both pattern recognition and machine learning belong to the most ad- vanced areas of software science. Numeric methods combined with artificial intelligence techniques have been especially successful for pattern recogni- tion. Research in the area of learning is now recognized as a basic part of software science as well as having application to knowledge acquisition in artificial intelligence systems and contributing to understanding human cognition. We wrote this book to provide a basic knowledge of pattern recognition, learning notions, and the models and learning of neural net- works. This book has the following three properties: (1) It explains both recognition using a computer and the basic methods of learning in one book. (2) The first half of the book describes various methods of representing information and ways of transforming these representations that are necessary to recognize patterns and learn. (3) Each chapter is self-contained so that a reader can start reading the book anywhere. Let us explain these characteristics in more detail. Traditionally, pattern recognition and machine learning have been stud- ied as individual fields. For this reason Chapters 4 and 5 of this book are primarily about recognition, whereas Chapters 6-10 explain learning. However, if we are interested in the representation of knowledge in a com- puter, we can think of both recognition and learning as a transformation of representation. Chapters 1-3 discuss various forms of representing in- formation and their transformations in preparation for such a unified view. IX X Pattern Recognition and Machine Learning The idea of looking at recognition and learning as the transformation of one representation into another has not been developed enough to unify individual algorithms; however, this idea suggests one way of looking at these ideas. We have stated that each chapter is an independent unit, and in each chapter we have not described how it is related to the others or to another field of study. For example, generalization in the study notions and learn- ing using a discrimination tree are related, and generalization based on explanation is related to partial evaluation in programming language pro- cessing. Also, learning in neural networks relates to the relaxation method in pattern recognition. Since more advanced texts talk about such rela- tionships, this book does not include them. We also think that it is better not to systematize the basic ideas of recognition and learning since such knowledge has not yet been established. Of course, there are other meth- ods of arranging the content of this book. We would be glad to hear your opinions. Both recognition and learning have been studied in philosophy, psychol- ogy, and other fields. This book looks at recognition and learning in the traditional sense as related to the computer. In the future, we believe the meaning of recognition and learning in the field of computers will change as software science develops and we would like to contribute to such a change. Many people have helped us create this book. We first would like to thank Professor M. Nagao (Kyoto University) and the editorial boards, who gave us the opportunity to create a book on recognition and learn- ing. Professor T. Matsuyama (Tohoku University) and Professor Y. Ota (Tsukuba University) let us use the original photographs in Figure 5.14 and Figure 5.7, respectively. We also would like to thank Mr. S. Sato (Ky- oto University), who reviewed the manuscript of this book and made many valuable suggestions. We would also like to thank students in the Anzai Group at the Engineer- ing Department of Keio University. Y. Akiyama, H. Ozawa, T. Maruichi, A. Yamashita, and K. Shinozawa read parts of the manuscript and made useful comments. The output of the sample exercise in Chapter 4 has been done by Shinozawa and the exercise in Chapter 10 was done by M. Waka- matsu, Y. Yamamoto, and M. Kajiura. The programs and the examples in the Appendix have been generated by Wakamatsu, Yamamoto, and Kajiura and summarized by Nakauchi. Y. Ajioka, Yamashita, T. Nishizawa, and H. Yasui also helped me in programming the exercises. The photographs in Chapters 2-5 have been done by Wakamatsu. Yokohama, Japan Study Guide • 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 xi Xll Pattern Recognition and Machine Learning dream of engineers to make a computer recognize things that we recognize unconsciously. What made this dream come true has been the data process- ing 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 proper- ties 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, recogniz- ing 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 ex- treme 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 informa- tion 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 prob- lem 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. Study Guide xiii • 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 O's and l'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 recog- nition 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 prepara- tion 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, 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 in- XIV Pattern Recognition and Machine Learning eluded 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 represent- ing 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 recog- nition and learning, which is different from the methods explained in Chap- ters 4-9. This chapter can be read independently of Chapters 4-9. This book is structured so that readers can choose whichever chapters interest them. For your reference, Figure G.l shows the relation among chapters. c Recognition and Learning by a Computer c 31 1 [Basic 2 Representing Information Knowledge] G 3 The Generation and Transformation of Representatiioonns s/ J [Pattern [Learning and Discovery] [Parallel Recognition] Distributed Processing] Figure G.l The structure of the book. • 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. Study Guide XV 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 cal- culus 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 im- portant. 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 Infer- ence (volume 14), Natural Language Processing (volume 15), and Models and Representation (volume 17). I also recommend writing computer pro- grams. 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 XVI Pattern Recognition and Machine Learning 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 architec- ture, 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.