Ling Zhang - Quotient Space Based Problem Solving: A Theoretical Foundation of Granular Computing

Morgan Kaufmann is an imprint of Elsevier

The Boulevard, Langford Lane, Kidlington, Oxford OX5 1GB, UK

225 Wyman Street, Waltham, MA 02451, USA

First edition 2014

Copyright 2014 Tsinghua University Press Limited. Published by Elsevier Inc. All rights reserved.

No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means electronic, mechanical, photocopying, recording or otherwise without the prior written permission of the publisher

Permissions may be sought directly from Elsevier's Science & Technology Rights Department in Oxford, UK: phone (+44) (0) 1865 843830; fax (+44) (0) 1865 853333; email: , and selecting Obtaining permission to use Elsevier material

British Library Cataloguing in Publication Data

A catalogue record for this book is available from the British Library

Library of Congress Cataloging-in-Publication Data

A catalog record for this book is availabe from the Library of Congress

ISBN: 978-0-12-410387-0

For information on all Morgan Kaufmann publications visit our web site at store.elsevier.com

Printed and bound in the US

14 15 16 17 18 10 9 8 7 6 5 4 3 2 1

The term problem solving is used in many disciplines, sometimes with different perspectives. As one of the important topics in artificial intelligence (AI) research, it is a computerized process of human problem-solving behaviors. So the aim of problem solving is to develop techniques that program computers to find solutions to problems that can properly be described.

In the early stage of AI, symbolists play a dominant role. They believe that all human cognitive behaviors, including problem solving, can be modeled by symbolic representation and reasoning and do not advocate the use of strict mathematical models. The most general approach to tackle problem-solving processes is generation and test. Applying an action to an initial state, a new state is generated. Whether the state is the goal state is tested; if it is not, repeat the procedure, otherwise stop and the goal is reached. This principle imitates human trial-and-error behaviors in problem solving sufficiently. The principle has widely been used to build AI systems such as planning, scheduling, diagnosis, etc. and to solve a certain kind of real problems. Therefore, the heuristic and scratch method is misunderstood as a unique one in AI for many people. We believe that more and more modern sciences such as mathematics, economics, operational research, game theory and cybernetics would infiltrate into AI when it becomes mature gradually. Over the years, we devoted ourselves to introducing mathematics to AI. Since 1979 we have introduced statistical inference methods to heuristic search, topological dimension reduction approach to motion planning, and relational matrix to temporal planning. Due to the introduction of these mathematical tools, the efficiency and performance of AI algorithms have been improved significantly. There are two main trends in AI research recently. One is attaching importance to the usage of modern scientific methods, especially mathematics; the other is paying attention to real-world problem solving. Fortunately, our efforts above are consistent with these new trends.

Based on these works, we explored further the theoretical framework of problem solving. Inspired by the following basic characteristics in human problem solving, that is, the ability to conceptualize the world at different granularities, translate from one abstraction level to the others easily and deal with them hierarchically, we establish an algebraically quotient space model to represent the multi-granular structures of the world so that its easy for computers to deal with them hierarchically. Certainly, this model can simulate the above characteristics of human problem-solving behaviors in a certain extent. We expect more human characteristics to merge into the model further. The system is used to describe the hierarchical and multi-granular structure of objects being observed and to solve the problems that are faced in inference, planning, search, etc. fields. Regarding the relation between computers and human problem solvers, our standpoint is that the computer problem solver should learn some things from human beings but due to the difference between their physical structures they are distinguishing.

Already 20 years has passed since the English version of the book published in 1992. Meanwhile, we found that the three important applied mathematical methods, i.e., fuzzy mathematics, fractal geometry and wavelet analysis, have a close connection with quotient space based analysis. Briefly, the representational method of fuzziness by membership functions in fuzzy mathematics is equivalent to that based on hierarchical coordinates in the quotient space model; fractal geometry rooted in the quotient approximation of spatial images; and wavelet analysis is the outcome of quotient analysis of attribute functions. The quotient space theory of problem solving has made new progress and been applied to several fields such as remote sensing images analysis, cluster analysis, etc. In addition, fuzzy set and rough set theories have been applied to real problems for managing uncertainty successively. The computational model of uncertainty has attracted wide interest. Therefore, we expanded the quotient space theory to non-equivalent partition and fuzzy equivalence relation. We explored the relation between quotient space theory and fuzzy set (rough set) theory. The quotient space theory is also extended to handling uncertain problems. Based on these works, we further proposed a new granular computing theory based on the quotient space based problem solving. The new theory can cover and solve problems in more domains of AI such as learning problems so as to become a more general and universal theoretical framework. The above new progress has been included in the second version of the book.

The quotient space based problem solving that we have discussed mainly deals with human deliberative behaviors. Recently, in perception, e.g., visual information processing, the multi-level analysis method is also adopted. So the quotient space model can be applied to these fields as well. But they will not be involved in the book.

There are seven chapters and two addenda in the book. In , the original equivalence relation based theory is expanded to including tolerant relations and relations defined by closure operations. Also, a more general quotient space approximation principle is presented. Finally, the basic concepts and theorems of mathematics related to the book are introduced in addenda, including point set topology and statistical inference.