MACHINE INTELLIGENCE QUO VADIS?
ADVANCES IN FUZZY SYSTEMS
-
APPLICATIONS AND THEORY
Honorary Editor: Lotfi A. Zadeh (Univ. of California, Berkeley) Series Editors: Kaoru Hirota (Tokyo lnsf. of Tech.), George J. Klir (Binghamfon Univ.-SUNY), Elie Sanchez (Neurinfo), Pei-Zhuang Wang (West Texas A&M Univ.), Ronald R. Yager (lona College)
VOl. 7:
Vol. 8: VOl. 9: Vol. 10:
VOl. 11: VOl. 12: Vol. 13: Vol. 14:
Vol. 15: Vol. 16: Vol. 17: Vol. 18: VOl. 19:
VOl. 20: Vol. 21:
Genetic Algorithms and Fuzzy Logic Systems: Soft Computing Perspectives (Eds. E. Sanchez, T. Shibata and L. A. Zadeh) Foundations and Applications of Possibility Theory (Eds. G. de Cooman, D. Ruan and E. E. Kerre) Fuzzy Topology (Y. M. Liu and M. K. Luo) Fuzzy Algorithms: With Applications to Image Processing and Pattern Recognition (Z. Chi, H. Yan and T. D. Pham) Hybrid Intelligent Engineering Systems (Eds. L. C. Jain and R. K. Jain) Fuzzy Logic for Business, Finance, and Management (G. Bojadziev and M. Bojadziev) Fuzzy and Uncertain Object-Oriented Databases: Concepts and Models (Ed. R. de Caluwe) Automatic Generation of Neural Network Architecture Using Evolutionary Computing (Eds. E. Vonk, L. C. Jain and R. P. Johnson) Fuzzy-Logic-Based Programming (Chin-Liang Chang) Computational Intelligence in Software Engineering (W. Pedrycz and J. F. Peters) Non-additive Set Functions and Nonlinear Integrals (Forthcoming) (Z. Y. Wang) Factor Space, Fuzzy Statistics, and Uncertainty Inference (Forthcoming) (P. Z. Wang and X. H. Zhang) Genetic Fuzzy Systems, Evolutionary Tuning and Learning of Fuzzy Knowledge Bases (0. Cordon, F. Herrera, F. Hoffmann and L. Magdalena) Uncertainty in Intelligent and Information Systems (Eds. B. Bouchon-Meunier, R. R. Yager and L. A. Zadeh) Machine Intelligence: Quo Vadis? (Eds. P. SinEak, J. VaSEak and K. Hirota)
Advances in Fuzzy Systems - Applications and Theory - Vol. 21
MACHINE INTELLIGENCE QUO VADIS? Peter Sincak Jan Vascak Echnical University of Kosice, Slovakia
Kaoru Hirota Tokyo Institute of Technology,Japan
NEW JERSEY ' LONDON
s World Scientific 1 ; SINGAPORE
BElJlNG * SHANGHAI
HONG KONG
TAIPEI * CHENNAI
Published by World Scientific Publishing Co. Pte. Ltd. 5 Toh Tuck Link, Singapore 596224
USA oflce: Suite 202, 1060 Main Street, River Edge, NJ 07661 UK oflce: 57 Shelton Street, Covent Garden, London WC2H 9HE
British Library Cataloguing-in-PublicationData A catalogue record for this book is available from the British Library.
MACHINE INTELLIGENCE: QUO VADIS? Copyright 0 2004 by World Scientific Publishing Co. Re. Ltd.
All rights reserved. This book, or parts thereoj may not be reproduced in any form or by any means, electronic or mechanical, including photocopying, recording or any information storage and retrieval system now known or to be invented, without written permission from the Publisher.
For photocopying of material in this volume, please pay a copying fee through the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, USA. In this case permission to photocopy is not required from the publisher.
ISBN 981-238-751-X
Printed in Singapore by World Scientific Printers (S) Pte Ltd
FOREWORD
More than fifty years ago, Norbert Wiener published his seminal book Cybernetics or Control and Communication in the Animal and Machine. The significance of this book is twofold. Firstly, it contains the first serious and comprehensive examination of the important unifying role of transdisciplinary concepts in science and technology; these are concepts such as information, control, organization, learning, adaptability, complexity, and the like. Secondly, it examines the various capabilities of living organisms as role models for technology, in particular computer-based technology. At this time, the heritage of cybernetics is perhaps most visible in a recently emerging branch of artificial intelligence, for which three names have alternatively been used: machine intelligence, computational intelligence, and intelligent systems. This branch of artificial intelligence is concerned with human-made systems (machines) that are capable of achieving highly complex tasks in a human-like, intelligent way. The qualifier “human-like” is crucial, and it distinguishes this branch from the current mainstream in the broader area of artificial intelligence. In machine intelligence (computational intelligence, intelligent systems), the human mind is viewed as a role model and the aim is to understand and emulate its various cognitive capabilities, which allow human beings to perform remarkably complex tasks. These capabilities include: 0
0
perceiving a given environment, recognizing in it features that are relevant for accomplishing a given task, and acting upon them; predicting changes in the environment on the basis of its model as well as additional knowledge, which is often expressed in natural language; using information about environment and other available knowledge to reason, often in terms of natural language, about the task to be performed; coordinating perception, planning, and action in a purposeful way; using natural language to communicate and collaborate with other human beings; learning and generalizing from previous experience; adapting behavior as needed to successfully complete the given task.
Achieving these capabilities in machines is contingent upon advanced computer technology, advanced instrumentation technology, and significant progress in cognitive science. In addition, however, it is also contingent upon the development of appropriate computational tools for making it possible for machines to emulate the remarkable capability of humans to perform a
V
vi
Foreword
wide variety of physical and mental tasks by using perceptions in a purposeful way and approximating perceptions in natural language. The ultimate aim in developing these computational tools, which are referred to as tools of sop computing, is to compute with perceptions. The basic thesis of soft computing is that the requirement of high precision and certainty carry a high computational cost. When the cost becomes prohibitive, the requirement needs to be softened. The principal aim of soft computing is to exploit the tolerance for imprecision and uncertainty to achieve tractability, robustness, and low cost. Precision and certainty are thus utilized in soft computing as commodities that are traded for reduction in computational complexity and for enhancing robustness. This recognition that imprecision and uncertainty play a useful role in taming unmanageable complexity is an important paradigmatic change in science and engineering. Imprecision and uncertainty are no longer viewed as an unavoidable plague, but rather as a valuable resource. Using perceptions in purposeful ways and approximating perceptions by statements in natural language are remarkable capabilities of the human mind. Studying these and other capabilities of the human mind and emulating them via the various tools of soft computing in machines is the primary focus of research in the area of machine intelligence. For a quick orientation, it is useful to recognize the following six categories of tools subsumed under soft computing: (i) The first category consists of the various properties of fuzzy set theory and the associated fuzzy logic. These are formalized languages with great expressive power. They are capable of capturing linguistic imprecision embedded in natural language and, as a consequence, they allow us to represent knowledge and formalize reasoning in terms of statements expressed in natural language. These statements are, in turn, capable of approximating perceptions. (ii) The second category contains all recognized types of artificial neural networks, which were inspired by their biological counterparts. Their distinctive characteristics are the capability of learning from experience and the capability of recognizing patterns in data. (iii) The third category is formed by the various types of evolutionary algorithms, which were originally inspired by the processes of biological evolution. They are surprisingly efficient in searching for approximate solutions of many complex problems, in particular optimization problems, in which exact solutions are difficult or impossible to obtain. (iv) The fourth category contains theories of rough sets of various types. The aim of these theories is to capture uncertainty that is caused by the limited resolution power of our measuring instruments and sensors. They allow
Foreword
vii
us to formalize and deal with approximations of given sets via lower-level resolution capabilities. (v) The fifth category is based on the theory of monotone measures, which is a generalization of classical measure theory. In monotone measures, the requirement of additivity of classical measures is replaced with a weaker requirement of monotonicity with respect to subset ordering. This theory allows us to measure and deal with properties that, due to some synergetic or inhibitory effects, do not satisfy the requirement of additivity of classical measures. (vi) The sixth category consists of the various theories of uncertainty and principles based upon them. Included are theories of precise as well as imprecise probabilities. This class may also be viewed as a generalized uncertainty-based information theory, in which the amount of information obtained by some action is measured by the amount of uncertainty reduced by this action. These various components of soft computing are often combined. By each combination, some new capabilities are gained. Combining, for example, fuzzy sets with rough sets, we obtain mathematical structures considerably more expressive than those of fuzzy sets or rough sets alone. While fuzzy sets are capable of capturing linguistic imprecision, which is characteristic of natural language, the aim of rough sets is to capture uncertainty caused by limited resolution power of our measuring instruments and sensors. Moreover, there are two possible ways of combining these two types of sets, which are very different from one another. One leads to fuzzy rough sets, which are rough sets based on fuzzy equivalence relations. The other leads to rough fuzzy sets, which are rough approximations of fuzzy sets. This example is mentioned here just to illustrate the enormous scope of soft computing. Machine intelligence covers a broad spectrum of intelligence. Among machines that require a relatively low level of intelligence are those that have lately been employed in various consumer products. The best known of these are perhaps intelligent washing machines, which are capable of selecting the best washing method based on the amount of clothes, quality of clothes, type of dirt, and amount of dirt by reasoning in fuzzy logic that emulates the reasoning of an experienced user. Much higher intelligence is needed in a machine that is capable of controlling a helicopter without a pilot by simple commands in natural language via wireless communication. Such a sophisticated machine, heavily based on soft computing, was designed, implemented and successfully tested by Michio Sugeno in Japan a few years ago. Examples of machines with an even higher level of intelligence are the prospective mobile home robots. These robots, which we are not able to build as yet, will be required to be highly adaptable for performing a broad variety of tasks in varying environments
viii
Foreword
according to requests expressed in natural language by their human users. Such machines will have to be equipped with highly sophisticated visual and auditory perception capabilities, as well as all the other requisite capabilities of intelligent machines mentioned earlier. In order to be able to compare the level of intelligence of various machines, it has already been suggested to introduce a suitable measure of machine intelligence, analogous to the intelligent quotient that is routinely used for measuring human intelligence. Although some ways of measuring machine intelligence have already been suggested in the literature, no consensus has been obtained on this issue thus far. Machine intelligence cannot be successfully studied within any single discipline. It requires cooperation of experts from multiple disciplines. The primary disciplines include computer science, mathematics, electrical engineering, mechanical engineering, cognitive science, biology, linguistics, and systems science. To facilitate cooperation among the disciplines involved, multidisciplinary research centers for machine intelligence (computational intelligence, intelligent systems) have lately been established in numerous places. This is an indicator that the importance of the relatively new area of machine intelligence, an unorthodox branch in the broader field of artificial intelligence, is already recognized. The editors of Machine Intelligence: Quo Vadis? should be congratulated for preparing this excellent and timely book on a subject whose importance is likely to grow significantly over the years. The book covers almost all aspects of machine intelligence and will undoubtedly become a benchmark against which future progress in machine intelligence will be measured.
George J. Klir State University of New York Binghamton, New York, USA
FOREWORD Intelligence - Science and Technology in the 21st Century
Intelligence is a fundamental feature of humans. It emerges from the activities of our brain and evolves during our life and social interactions. Even though much progress has been made in brain research and understanding, very challenging questions remain in the 21st century. For example, how is intelligence generated in the brain, and how are we to build intelligent systems using modern technology? The book Machine Intelligence: Quo Vadis? contends with these problems, providing state of the art research results with the integration of various approaches. The 20th century can be characterized by a number of important developments and inventions in science and technology. The progress was led by a revolution in physics which resulted in our surprisingly rich modern technology. Mathematics has also achieved a number of new results and a high level of abstract mathematics. In the middle of the century new results were revealed in biological research. Molecular biology emerged from the efforts to further understand the secrets and origin of life based on molecular principles. Since then, progress has brought us to where we now understand and study the genetic make-up of man. Information and computer science have also progressed since the middle of the 20th century. The achievements in computer technology have been so remarkable that we’re now facing a new civilization, the Information Society, supported by computers and Internet technology. It must be said that until now we have not been very successful in understanding how our brain works and how to design and build intelligent systems. This is the biggest challenge remaining to us in the 21st century: how to embed intelligence into a man-made machine. What are to be the main principles for approaching this challenge? For the last century the sciences have been divided into specific areas or disciplines and were partially isolated. However, today we are facing very fundamental important global problems which cannot be solved in one area by a single discipline, e.g. environmental protection, energy production, various illnesses, global communications and many others. We need to approach these problems by integrating all our knowledge and scientific disciplines. Modelling human intellect and creating Artificial Intelligence is one of these important and fundamental problems. Dynamic activities of the brain are evolving our
ix
x
Foreword
intelligence. The brain is a biological organ composed of biological subsystems. However, it functions as an information processor, on which our mind depends. This situates brain science between the biological and information sciences. Artificial Intelligence is a synthetic approach to modelling the intellect of living systems. Its goal is to build functional, human-like intelligent systems based on modern computer technology, not necessarily based on the physical model of the brain. While building a system that will behave like the brain we have to keep in mind the global functional analysis of the brain, which is not a simple task. This again is the reason to include various disciplines which may be helpful in this analysis. There have been a number of proposed approaches based on neural networks, fuzzy systems, evolutionary computation and the new agent technologies. Following the isolated development of the above-mentioned approaches, now is the time to integrate all of them, understand the brain and build an intelligent system. The time has come to fill the gap between the functional biological brain and computer science oriented technology.
Shun-ichi Amari RIKEN Brain Science Institute Saitama, Japan
PREFACE
Machine Intelligence (MI) is very important in building intelligent systems with various degrees of autonomous behavior. These groups of tools support features such as the learning ability and adaptability of intelligent systems in various types of environments and situations. The current and future Information Society is expected to come into technology and everyday life using the Ambient Intelligence ( A d ) approach. This will provide a wide range of potential applications for Machine Intelligence tools to support the implementation of the Am1 concept. A number of studies indicate that this approach is inevitable and will play an essential and central role in the development of the Information Society in the near future. The important role of Machine Intelligence in this historic challenge highlights the responsibility the MI community has to include all the different fields such as brain-like research and applications, fuzzy logic, neural networks, evolutionary computation, multi-agent systems, artificial life, expert systems, symbolic approaches based on logic reasoning, knowledge discovery, mining, replication and many other related fields in the support, development, and creation of an intelligent system. The important embedding of these systems in various types of technology should be profitable us and bring a different role for mankind in production and everyday life. We expect to see intelligent technology, solutions, and even humanoid robots to help mankind improve and preserve the ideals of humanity and democracy. The Machine Intelligence Quotient will play an important role in the future ability to evaluate a specific system’s degree of autonomy. It is believed that it will be a domain-oriented problem and it will be important for humans to use this information in decision-making, e.g. in the evaluation of information systems in the commercial world, to choose the system with the highest MIQ. The usefulness of this parameter will depend on many influences including technological, domain-oriented and also the commercial aspect of the MI application in various systems. The commercial demand for “intelligent” solutions and products should increase the interest for MI tools. One of the most challenging fields is brain science and the application of this research in technology and man-made products. There is much important research being done into biologically inspired systems but the problems of knowledge acquisition, storage, replication and integration into “superknowledge” systems seem to be very important. The solutions for these problems could lead to many new technological applications within the Am1 concept. Many fields within MI are supportive of this effort. This could lead to
xi
xii
Preface
a system with a multi-accessible knowledge database with incremental learning ability, which would revolutionize the application potential of MI man-made solutions and products. This multi-author book includes contributions from several leading authorities in the field of Machine Intelligence including the areas of fuzzy logic, neural networks, evolutionary computation and hybrid systems, which are all generally believed to play an important role in the field of Machine Intelligence. There is no longer a dispute over specific fields of technology, but there are still questions about the most effective way to achieve the solution to the task within the means of MI. Only the cooperation of all the MI tools will yield profitable research and applications for creating Intelligent Technology and Systems and their applications in technology and everyday life. We can see through history that the differences between the classical Artificial Intelligence communities and Computational Intelligence communities are slowly diminishing. This era of cooperation seems to be opening the way to achieving the common goal of support development for Machine Intelligence tools and their role in the Am1 concept. This book is a contribution to the pooled knowledge and presentation of important problems and advances in Machine Intelligence theory and its application. The secondary goal of this book is to bring to mind the question L L Q Vadis ~ ~Machine Intelligence?” in the sense of “where is MI going?” We want to do this by considering the possible misuse of these technologies. We are living in a very complex time especially after September 11, 2001. It is important therefore to study MI’S potential to benefit mankind while being conscious of, or at least discussing, the potential misuse of MI in Am1 in an Information Society. We are thankful for the interesting forewords written by Prof. George Klir from the University of Binghamton, New York, USA and Prof. S. Amari from RIKEN, Japan pointing out the interesting aspects of Machine Intelligence. We’d also like to thank all the contributors to this book as well as the students from the Center for Intelligent Technology at the Technical University in KoSice, Slovakia for their many hours contributed preparing and formatting the manuscript for publication. Finally, we’d like to thank our publisher World Scientific Publishing for their encouragement and for helping to spread these ideas to the global scientific community. March, 2002
Dr. Peter SinEBk and Dr. JBn VaSEBk Center for Intelligent Technologies Technical University of Kosice Kosice, Slovakia
Dr. Kauro Hirota Hirota Laboratory Tokyo Institute of Technology Tokyo, Japan
CONTENTS
Forewords
J . Klir S. Amari
ix
P. Sin&%, J . VaSCa'lc and K. Hirota
xi
V
Preface
Chapter 1
Chapter 2
INTRODUCTION
1
Quo Vadis Computational Intelligence? W. Duch and J. Ma7idziulc
3
MATHEMATICAL TOOLS FOR MACHINE INTELLIGENCE
29
Mappings between High-dimensional Representations in Connectionistic Systems V. Kiirlcova'
31
The Stimulating v of Fuzzy Set Theory in Mathematics and its Applications E. E. Kerre and D. van der Welcen
47
K-order Additive Fuzzy Measures: A New Tool for Intelligent Computing R. Mesaar
65
On-line Adaptation of Recurrent Radial Basis Function Networks using the Extended Kalman Filter B. Todorouik, M . StankoviC and C. Moraga
73
Iterative Evaluation of Anytime PSGS Fuzzy Systems 0. Taka'cs and A . R. Vdrkonyi-Kdczy
93
xiii
xiv
Contents
Chapter 3
Kolmogorov's Spline Network B. Igelnik and N . Parikh
107
Extended Kalman Filter Based Adaptation of Time-varying Recurrent Radial Basis Function Networks Structure B. TodoroviC, M. StankoviC and C. Moraga
115
A Multi-NF Approach with a Hybrid Learning Algorithm for Classification D. Rutkowska and A . Starczewski
125
A Neural Fuzzy Classifier Based on MF-ARTMAP P. SinEhk, M. Hric, R. Valo, P. Horansky and P. Karel
141
Mathematical Properties of Various Fuzzy Flip-flops as a Basis of Fuzzy Memory Modules K . Hirota and S. Yoshida
161
Generalized T-operators I. J. Rudas
179
Fuzzy Rule Extraction from Input/Output Data L. T. Kdczy, J. Botzhiem, A. B. Ruano, A. Chong and T. D. Gedeon
199
Knowledge Discovery from Continuous Data Using Artificial Neural Networks R. Setiono and J. Zurada
217
ADVANCED APPLICATIONS WITH MACHINE INTELLIGENCE
233
Review of Fuzzy Logic in the Geological Sciences: Where We Have Been and Where We Are Going R. V. Demicco
235
Bayesian Neural Networks in Prediction of Geomagnetic Storms G. Andrejkova'
251
Contents xv
Chapter 4
Adaptation in Intelligent Systems: Case Studies from Process Industry K . Leiviska
259
Estimation and Control of Non-linear Process Using Neural Networks A . Jadlovska'
275
The Use of Non-linear Partial Least Square Methods for On-line Process Monitoring as an Alternative to Artificial Neural Networks P. F. Fantoni, M. Hoffmann, W. Hines, B. Rasmussen and A . Kirschner
283
Recurrent Neural Networks for Real-time Computation of Inverse Kinematics of Redundant Manipulators J . Wang and Y . Zhang
299
Towards Perception-based Fuzzy Modeling: An Extended Multistage Fuzzy Control Model and its Use in Sustainable Regional Development Planning J . Kacprzyk
32 1
MACHINE INTELLIGENCE FOR HIGH LEVEL INTELLIGENT SYSTEMS
339
Neural Network Models for Vision K. Fukushima
34 1
Humanoid Robot for Kansei Communication: Computer Must Have Body S. Hashimoto
357
Intelligent Space and Human Centered Robotics T . Yamaguchi and N . Ando
371
Evolution of Unconscious Cooperation in Proportional Discrete-time Harvesting J. Pospichal
385
Artificial Chemistry, Replicators, and Molecular Darwinian Evolution in Silico V. KvasniEka
403
xvi
Contents
Index
Human Centered Support System Using Intelligent Space and Ontological Neural Networks T. Yamaguchi, H. Murakami and D. Chen
427
The K.E.I. (Knowledge, Emotion and Intention) Based Robot Using Human Motion Recognition T. Yamaguchi, T. Saito and N . Ando
435
Auditory and Visual-based Signal Processing with Interactive Evolutionary Computation H. Takagi
443 455
Introduction
This page intentionally left blank
QUO VADIS, COMPUTATIONAL INTELLIGENCE? WLODZISLAW DUCH’ AND JACEK MANDZIUK~ Department of Informatics, Nicholas Copemicus University, ul. Grudziqdzka 5, 87-I00 Toruri, Poland E-mail:
[email protected]. torun.pl Faculty of Mathematics and Information Science, Warsaw University of Technology, Plac Politechniki I , 00-661 Warsaw, Poland. I
What are the most important problems of computational intelligence? A sketch of the road to intelligent systems is presented. Several experts have made interesting comments on the most challenging problems.
Keywords: computational intelligence, artificial intelligence, cognition, neural networks, evolution
1
Introduction.
In the introduction to the “MIT Encyclopedia of Cognitive Sciences” M. Jordan and S. Russell [33. ] used the term “computational intelligence” to cover two views of artificial intelligence (AI): engineering and empirical science. Traditional A1 started as an engineering discipline concerned with the creation of intelligent machines. Computational modeling of human intelligence is an empirical science. Both are based on computations. Artificial Intelligence (AI) has established its identity quite early, during the Dartmouth conference in 1956 [6. 1. It had clearly defined goals, exemplified by great early projects, such as the General Problem Solver of Simon and Newell. There are many definitions of A1 [48. ,64. 1, for example: “... the science of making machines do things that would require intelligence if done by humans” (Marvin Minsky), “The study of how to make computers do things at which, at the moment, people are better” [48. 1. In essence A1 tries to solve problems for which effective algorithms do not exist, using knowledge-based methods. In the 1970-ties A1 has contributed to the development of cognitive science and to the goal of creating “unified theories of cognition”, as Allen Newell called it. Ambitious theories of high cognitive functions were formalized by John Anderson in his Act* theory [ 3 . 1, and by Newell and his collaborators in the Soar theory [43. 1. Both were very successful and led to many practical (and commercial) applications. In the last decade intelligent agents become the focus of AI, entities that can perceive and act in a rational goal directed way to achieve some objectives. Machine learning has been important from the beginning in AI. Samuel’s checker-playing system (1959) learned to play far superior checkers than its creator. Although initially research on perceptrons has developed as a part of A1 in the late
3
4
W. Duch and J. Maddziuk
1950-ties machine learning became preoccupied with inductive, rule based knowledge [50. 1. A1 development has always been predominately concerned with highlevel cognition, where symbolic models are appropriate. In 1973 the book of Duda and Hart on pattern recognition appeared [ 18. 1. The authors wrote that “pattern recognition might appear to be a rather specialized topic”. It is obviously a very broad topic now, including good part of neural networks research [5. ]. In 1982 Hopfield network [26. ], in 1986 the backpropagation algorithm [49. 1, and a year later the PDP books [7. ] brought the neural network field to the center of attention. Since that time the field of neural computing has been growing rapidly in many directions and became very popular in the early 90ties. Computational neuroscience, connectionist systems in psychology and neural networks for data analysis are very different branches with rather different goals. The last of these branches gained solid foundations in statistics and Bayesian theory of learning [5. ,25. 1. Soft computing conferences started to draw people from neural, fuzzy sets and evolutionary algorithms communities. Applications of these methods overlap with those dealt with by pattern recognition, A1 and optimization communities. Computational Intelligence (CI) is used as a name to cover many existing branches of science. This name is used sometimes to replace artificial intelligence, both by book authors [47. ] and some journals (for example, “Computational Intelligence. An International Journal”, by Blackwell Publishers). There are several computational intelligence journals dedicated to the theory and applications of artificial neural networks, fuzzy systems, evolutionary computation and hybrid systems. In our opinion it should be used to cover all branches of science and engineering that are concerned with understanding and implementing functions for which effective algorithms do not exist. From this point of view some areas of A1 and a good part of pattern recognition, image analysis and computational neuroscience are subfields of CI. What is the ultimate goal of computational intelligence and what are the shortterm and the long term challenges to the field? What is it trying to achieve? Without setting up clear goals and yardsticks to measure progress on the way, without having a clear sense of direction many efforts will end up nowhere, going in circles and repeating the same problems. We hope that this paper will start a discussion about the future of CI that should clarify some of the issues involved. First we shall make some speculations about the goals of computational intelligence, think how to reach them, and raise some questions worth answering. Then we will write about some challenges. We have asked several experts what they consider to be the greatest challenges in their field. Finally some conclusions will be given.
Quo Vadis Computational Intelligence?
2
5
The ultimate goals of CI.
From the perspective of cognitive sciences artificial intelligence is concerned with high level cognition, dealing with such problems as understanding of language, problem solving, reasoning, planning and knowledge engineering at the symbolic level. Knowledge has complex structure, the main problems are combinatorial in nature and their solution requires heuristic search techniques. Learning is used to gain knowledge that expert systems may employ for reasoning, and is frequently based on logic. Other branches of computational intelligence are concerned with lower level problems, are more on the pattern recognition side, closer to perception, are at the subsymbolic level. Complex knowledge structures do not play important role, most methods work in fixed dimensional feature spaces. Combinatorial character of problems and knowledge-based heuristic search are not an issue. Numerical methods are used more often than discrete mathematics. The ultimate goal of A1 is to create a program that would pass the Turing test, that is would understand human language and be able to think in a similar way to humans. The ultimate A1 project is perhaps CYC, a super-expert system with over a million of logical assertions describing all aspects of the world. The ultimate goal of other CI branches may be to build an artificial rat (this was the conclusion of a discussion panel on the challenges to CI in the XXI century, at the World Congress on Computational Intelligence in Anchorage, Alaska, in 1998). Problems involved in building an artificial animal that may survive in a hostile environment are rather different than problems related to the Turing test. Instead of symbolic knowledge problems related to perception, direction of attention, orientation, motor control and motor learning have to be solved. Behavioral intelligence that is embodied in the Cog project is perhaps the most ambitious project of this kind[1. 1. Each branch of CI has its natural areas of application and the overlap between them is sometimes small. For example, with very few exceptions A1 experts are separated from communities belonging to other CI branches, and vice versa. Even neural networks and pattern recognition communities, despite a considerable overlap in applications, tend to be separated. Is there a common ground where the two fields could meet? The ultimate challenge for CI seems to be a robot that combines high behavioral competence with human-level higher cognitive competencies. Building creative systems of such kind all branches of CI will be required, including symbolic A1 and lower level pattern recognition methods. At the one end of the spectrum we have neurons, at the other brains and societies.
6
3
W . Duch and J . Maridriuk
A roadmap to creative systems.
The brain is not a homogenous, huge neural network, but has quite specific modular and hierarchical structure. Neural network models are inspired by processes at a low level of this hierarchy, while symbolic A1 works at the highest level. Little work has been devoted to the description and understanding of intermediate levels, although investigation of connections between them can be quite fruitful [9. 1. Below we have sketched a roadmap from the level of single neurons to the highest level of creative societies of brains, presenting some speculations and research directions that seem unexplored. Cooperation of individual elements that have some local knowledge leads to emergence of a higher-order unit that should be regarded at its own footing. The same principles may operate at different scales of complexity. A major challenge for CI is to create models and learn how to scale up systems to reach higher level. 3.I
Threshold neurons and perceptrons
Neurons in simple perceptrons have only one parameter, the threshold for their activity, and the synaptic weights that determine their interactions. Combined together perceptrons create the popular multi-layer perceptron (MLP) networks that are quite powerful, able to learn any multidimensional mapping starting from examples of required input/output relations. Usually the network aspect is stressed while learning processes are discussed: the whole, with interacting elements, is bigger than its parts. Real biological networks involve a huge number of neurons with thousands of connections each. Instead of looking at the fixed architecture of neural network it may be better to imagine that synaptic connections define interactions between subsets of individual elements. Clusters of activity, or forming subnetworks, has been observed in networks of spiking neurons [24]. Similar effects have not been investigated in MLP networks. Perceptron neural networks may be regarded as collections of primitive processing elements (PEs). Individual element do not understand the task the whole collection is faced with, but are able to adjust to the flow of information, performing local transformations of the incoming data and being criticized or corrected by other members of the team (i.e. network). Hebb principle provides reinforcement for PE, regulating the level of their activity in solving different cooperative problems. Backpropagation procedure provides another kind of critique of the activity of single neurons. Some parameters are internal to the neural units (thresholds), while other parameters are shared, allowing for interactions between units during the learning procedure. Neural networks use many units (neurons) that cooperate to solve problems that are beyond the capabilities of a single unit. Interactions and local knowledge of a simple PEs determine the type of problems that networks of such elements may solve.
Quo Vadis Computational Intelligence? 7
Networks are able to generalize what has been learned, creating a model of states of local environment they are embedded in. Generalization is not yet creativity, but is a step in the right direction.
3.2
Increasing complexity of internal PE states
Next step beyond the single parameter (threshold) describing internal state of a neuron is to add more internal parameters, allowing each PE to realize a bit more than a hyperplane discrimination. Perceptrons are not able to solve the famous connectedness and other problems posed by Minsky and Papert [39] as a challenge for neural networks. Adding more network layers does not help (see the second edition of [39. I), the problem scales exponentially with the growing size of images. This problem may be solved with neural oscillator networks in a biologically plausible way [61. 1, but rather complex networks are required. Adding one additional internal parameter (phase) is sufficient to solve this problem [32]. What is the complexity class of problems that may be solved this way? Can all problems of finding topological invariants be solved? What can be gained by adding more parameters? The answers are not clear yet. Computational neuroscience investigates models of cortical columns or Hebbian cell assemblies. Modular neural networks may be regarded as networks with super PEs that adapt to requirements of the complex environment. Instead of simple units with little internal knowledge and fixed relations (fixed architecture of MLP networks), more powerful PEs dynamically forming various configurations (virtual networks) should be used. More complex internal knowledge and interaction patterns of PEs are worth investigation. The simplest extension of network processing elements that adds more internal parameters requires abandoning the sigmoidal neurons and using a more complex transfer functions. A Gaussian node in a Radial Basis Function network [5] has at least N internal parameters, defining position of the center of the function in N dimensional space. Weights define the inverse of dispersions for each dimension, determining interaction with other network nodes through adaptation of parameters to the data flow. Although research efforts have been primarily devoted to improvement of neural training algorithms and architectures there are good reasons to think that transfer functions may significantly influence the rate of convergence, complexity of the network and the quality of solution it provides [ 161. What do these more complex PEs represent? If their inputs are values of some features they model areas of the feature space that may be associated with some objects, frequently appearing input patterns. Recurrent neural networks, including networks of spiking neurons, are used as autoassociative memories that store prototype memories as attractors of network dynamics [2. 1. Basins of these attractors define areas of the feature space associated with each attractor. A single complex PE, or a combination of a few PEs, represent such areas directly, replacing a subnetwork of simpler neurons.
8
W. Duch and J . Malidzauk
This was the original motivation for the development of the Feature Space Mapping (FSM) networks [13,9. 1. Nodes of FSM networks use separable transfer functions G(X)=lIiG,(xi),instead of radial functions (the only separable radial function is Gaussian). Their outputs model the probability of recognizing a particular combination of input features as some object. Each PE may be treated as a fuzzy prototype of an object, while each component Gi(xi)may be treated as a membership function for feature xi. Thus FSM is a neurofuzzy system that allows for control of the decision borders around each prototype by modifying the internal parameters of the PEs (transfer functions). Precise control of basins of attractors in dynamical networks is usually impossible. In contrast to MLP neural networks many types of functions with different internal parameterizations are used. First steps towards neural networks with heterogonous PEs were made [11,17. ,29. 1. Theoretically they should allow for discovery of an inductive bias in the data, selecting or adapting transfer functions to the data using minimal number of parameters. Creation of efficient algorithms for networks with heterogonous PEs is quite challenging task. Each complex PE represents a module that adapts to the data flow adjusting its basin of influence in the feature space. Is this approximation sufficient to replace dynamical networks with spiking neurons or recurrent networks? What are the limitations? Many questions are still to be answered.
3.3
Increasing complexity of PE interactions
Rigorous transition from attractor networks to equivalent FSM networks may be based on fuzzy version of symbolic dynamics [4. ] or on the cell mapping method [28. 1. It should be possible to characterize not only the asymptotic properties of dynamical models, but also to provide simplified trajectories preserving sufficient information about basins of attractors and transition probabilities. This level of description is more detailed than the finite state automata, since each state is an objected represented in the feature space. Such models are a step from neural networks to networks representing lowlevel cognitive processes. They are tools to model processes taking place in feature spaces. FSM networks use clusterization-based procedures to create initial model of the input data and then learn by adaptation of parameters. Adding knowledge to the feature space is easy by creating, deleting and merging nodes of the network. FSM may work as associative memory, unsupervised learning, pattern completion system or a fuzzy inference system. Constraints on variables, such as arithmetic relations, or laws Y=F(XI,..XN) may be directly represented in feature spaces. Although using complex PEs in networks adds internal degrees of freedom interactions between the nodes are still fixed by the network architecture. Even if nodes are added and deleted the initial feature space is fixed. An animal has a very large number of receptors and is able to pay attention to different combinations of sensory stimuli. Attractor networks are combinatorially productive, activating many
Quo Vadis Computational Intelligence? 9
combinations of neural modules. Feedforward networks, even with complex PEs, have fixed path of data flow. Although internal representations of PEs go beyond logical predicates they are not dynamic. Thus they are not able to model networks of modules that interact in a flexible way depending on the internal states of their modules. One reason for changes in the internal states of cortical brain modules is due to the recent history (priming effects), another is due to changes in neuromodulation controlled by a rough recognition and emotional responses in the limbic areas. A simplified model of interacting modules should include the fact that all internal parameters should depend either directly on inputs P ( X ) , or indirectly on hidden parameters P(H(X)) characterizing internal states of other modules. Each module should estimate how competent it is in a given situation and add its contribution to the interaction with other modules only if its competence is sufficient. Recently this idea has been applied to create committees of competent classifiers [lS. 1. A committee is a network of networks, or a network where each element has been replaced by a very complex PE, made from individual network. Outputs O(X;M,) from all network modules (classifiers) M , are combined together with weights W, in the perceptron-like architecture. The weights of these combinations are modulated (multiplied) by factors F(X;M,) that are small in the feature space areas where the model MI makes many errors and large where it works well. Thus the effective weights depend on the current state of the network, W,(X) = W, F(X;M,). This method may be used to create virtual subnetworks, with different effective path of information flow. Modulation of the activity of modules is effective only if the information about the current state is distributed to all modules simultaneously. In the brain this role may be played by the working memory (cf. Newman and Baars [42]). The step from associations to sequential processing is usually modeled by recurrent networks. Here we have networks of modules adjusting their internal states (local knowledge that each module has learned) and their interactions (modulations of weights) to the requirements of the information flow through this system. At this level systematic search processes may operate. In [ 131 we have shown that a complex problem requiring combinatorial approach may be solved quite easily by search processes that activate simple FSM modules. The electrical circuit example from the PDP book has been used [7. ] to demonstrate it. Each FSM module has learned qualitatively to analyze relations between the 3 variables, such as the Ohm’s law U=ZR etc. The amazing result is [9. ] that almost any relation AA=f(AB, AC) representing changes of variables leads to the same objects in the feature space model. In the electric circuit example there are 7 variables and S laws that may be applied to this circuit. If values of some variables are fixed activity of the 5 FSM modules (each corresponding to a 3-term relation, and each identical) that are competent to add something new to the solution is sufficient to specify the behavior of the remaining variables.
10
W . Duch and J . Ma7idziuk
Thus modular networks, such as the FSM model, may be used as powerful heuristics to solve problems requiring reasoning. The solution is found by systematic search, as in the reasoning systems, but each logical (search) step is supported by the intuitive knowledge of the whole system (level of activity of the competent modules). Such systems may be used for simple symbolic processing, but creating flexible modular networks of this type that could compete with experts systems is still a challenge. 3.4
Beyond the vector space concept
Feature space representation lies at the foundation of pattern recognition [18. 1, but it is doubtful that it plays such an important role in the brain. Even at the level of visual perception similarity and discrimination may be sufficient to provide the information needed for visual exploration of the world [44. 1. At the higher cognitive levels, in the abstract reasoning or sentence analysis processes, vector spaces with fixed number of features are of little use. In such applications complex knowledge structures are created and manipulated by knowledge-based A1 expert systems. Although a general framework for processing of structural data, based on recurrent neural networks and hidden Markov models, has been introduced [20. ], it is rather difficult to implement and use. Perhaps a simpler approach could be sufficient. The two most common knowledge representation schemes in A1 are based on the state or the problem description [48. ,64. 1. The initial state and the goal state are also represented in the same way, the goal being usually a desired state, or a simple problem that has known solution. A set of operators is defined, transforming the initial object (state, problem), into the final object (goal). Each operator has some costs associated with its use. Solutions are represented by paths in the search graph. The best solution has lowest costs of transforming the initial object into the final object. An efficient algorithm to compute such distances may be based on dynamical programming [36. I. Lowest costs of transformation that connect two complex objects are a measure of similarity of these objects. Mental operations behind evaluations of similarity are rather complex and are not modeled directly at this level. Similarity is sufficient for categorization and once it has been evaluated original features are not needed any more. At the level of perception sensory information is of course feature-based, but different types of higher-level features are created for different objects from the raw sensory impressions. At the higher cognitive level “intuitive thinking” is probably based on similarity evaluation that cannot be analyzed by logical rules. Crisp or fuzzy rules have limited expressive powers [ 12. 1, prototype-based rules that evaluate similarity are more powerful alternative [ 14. I. General framework for similarity-based systems includes most types of neural networks as special cases [lo. ]. Pattern recognition methods that are based on similarity or dissimilarity matrices and do not require vector spaces based on features have been published (cf. [45. I).
Quo V a d i s C o m p u t a t i o n a l Intelligence?
11
Another research direction may be inspired by Lev Goldfarb’s criticism of the vector space as a foundation for inductive class generalization [23. 1. His system of evolving transformations tries to synthesize new operators for object transformation and similarity functions, allowing for evaluation of similarities between two objects that have quite different structure. This is necessary for example in chemistry, comparing molecules that have different structure although they belong to the same class (have the same activity or other high-level properties). In other words some kind of a measure of functional isomorphism or similarity (not necessarily corresponding to the structural one) is required in such applications.
3.5
Flexible incremental approaches
One of the fundamental impediments in building large, scalable learning systems based on neural networks is the problem of catastrophic forgetting. In order to alleviate this problem several ideas concerning both the network structures and the training algorithms have been introduced. The main approaches reported in the literature include modular networks [60,52,41], constructive approaches [ 19,211. In modular networks the problem to be learned is divided into subproblems, each of which is learned independently by a separate module and then the solution for the whole problem is obtained as a proper combination of subproblem solutions. In constructive approaches the network starts off with a small number of nodes and its final structure is being built systematically by adding nodes and links whenever necessary. Both types of methods are well known in the community so their advantages and weak points will not be discussed here. Other examples of flexible incremental approaches are the lifelong learning methods [57,58] in which learning new tasks becomes relatively easier when the number of already learned tasks increases. One possible approach of that type is to start training procedure based on very simple, “atomic” problems. Structures developed while solving these atomic problems are frozen and consequently will not be obliterated in subsequent learning only fine tuning would be permitted. These small atomic networks will serve as building blocks for solving more complicated problems - say level 1 problems. Larger structures (networks) obtained in the course of training for solving level 1 problems will serve as blocks of building even larger structures capable of solving more complex problems (level 2 ones), etc. Once in a while the whole system is tested based on the previously learned (or similar to them) atomic, level 1, level 2, etc. problems. The above scheme can be viewed as an example of constructive approach, however - unlike in typical constructive approaches - it is postulated that the network starts off with the number of nodes and links a few times exceeding the number of actually required ones (i.e. “enough’ spare nodes and links is available in the system). Hence the potential informational capacity of the system is available right from the beginning of the learning process (similarly to biological brains). After
12
W. Duch and J . Malidziuk
completion of the training process the nodes and links not involved in the problem representation are pruned unless the system is going to be exposed to another training task in future. We have used similar to the above scheme to solving supervised classification problem. The training scheme called Incremental Class Learning (ICL) was successfully applied to unconstrained Handwritten Digit Recognition problem [34,35] . The system was trained digit by digit (class by class) and atomic features developed in the course of learning were frozen, and available in subsequent learning. These frozen features were shared among several classes. The ICL approach not only takes advantage of existing knowledge when learning a new problem, it also offers a large degree of immunity from the catastrophic interference problem. The ICL idea can possibly be extended to the case of multimodal systems performing several learning tasks where different tasks are characterized by different features. This would require adaptation of the above scheme to the case of multimodal feature spaces. The above mentioned incremental learning methods are suitable for supervised, off-line classification tasks in which multi-pass procedure is acceptable. Alternative approaches - probably based on unsupervised training - must be used in problem domains requiring real-time learning ability. Ideally, large, scalable network structures should be suited to immediate, one pass incremental learning schemes. An examples - to some extent - of such fast trainable networks are Probabilistic Neural Networks [53] and General Regression Neural Networks [54] often applied to financial prediction problems [51]. However the cost of fast training ability is a tremendous increase of memory requirements since all training patterns must be memorized in the network. The other disadvantage is relatively slow response of the system in the testing phase. The search for efficient, fast incremental training algorithms and suitable network architectures is regarded as one of the challenges in computational intelligence.
3.6
Evolution of networks
Another important research direction is changing from static (deterministic) networks into evolving (context dependent) ones. Possible approaches here include networks composed of nodes with local memory that process information step-wise, depending on the previous state(s). Evolving networks should be capable of adding and pruning nodes and links along with the learning process. Moreover, the internal knowledge representation should be based on redundant features sets as opposed to highly distributed representations. Non-determinism and context dependence can, for example, be achieved by using nodes equipped with simple fuzzy rules (stored in their local memories) that would allow for intelligent, non-deterministic information processing. These fuzzy rules should take into account both local parameters (e.g. the number of active incoming links, the degree of local weights density, etc.)
Quo Vadis Computational Intelligence?
13
as well as global ones (e.g. the average level of global activation - “temperature of the system”, global level of wiring of the system, etc.). Knowledge representation should allow for off-line learning, which will be performed by separate parts of the systems - not involved in the very fast, on-line learning. The off-line learning should allow for fine tuning of the knowledge representation and also would be responsible for implementation of appropriate relearning schemes. One of the possible approaches are the ECOS (Evolving COnnectionist Systems) introduced by Kasabov [3I], which implement off-line re-training schemes based on internal representation of the training examples in the system. Similar idea was also introduced in our paper [35] where the network was trained layer by layer and the upper layer was trained based on the feature representation developed in the lower layer. Another claim concerning flexible learning algorithms and network structures is that structures of network modules as well as training methods should have some degree of fuzziness or randomness. Ideally, several network modules starting with exactly the same structure and internal parameters after some training period should diverge from one another though still stay functionally isomorphic. Some amount of randomness in the training procedure would allow for better generalization capabilities and higher flexibility of these modules. Flexibility and hierarchy of information (knowledge) can be partly realized by the use of multidimensional links. Very simple associations will be represented by classical one dimensional links (form one neuron to another neuron). More complex facts will be represented by groups of links joint together and governed by sophisticated fuzzy rules taking into account context information. In other words multidimensional link will be a much more complex and powerful structure than the simple sum of all one dimensional links being their parts. A dimension of the link will be proportional to the degree of complexity of information it represents. This idea has its roots in the design of associative memories where depending on the nature and complexity of stored associations suitable type of memory can be used (autoassociative, bidirectional or multidirectional). 3.7
Transition to symbolic processing
A1 has concentrated on symbolic level of information. Problems related to perception, analysis of visual or auditory scenes, analysis of olfactory stimuli are solved by real brains working on spatiotemporal patterns. There are many challenges facing the computational cognitive neuroscience field that deals with modeling such brain functions. Spiking networks may have some advantages in such applications [61. 1. Several journals specialize in such topics and a book with subtitle “Towards Neuroscience-inspired computing” appeared recently [63], discussing modular organization, timing and synchronization, learning and memory models inspired by understanding of the brain.
14
W. Duch and J . Malidziuk
We are interested here only in identification of promising routes to simplified models that may be used for processing of dynamic spatiotemporal patterns, going from low to high-level cognition. One mechanism proposed by Hopfield and Brody [27] is based on recognition of the spatiotemporal pattern via transient synchrony of the action potentials of a group of neurons. The recognition is in their model invariant to uniform time warp and uniform intensity change of the input events. Although modeling of recognition in feature spaces is rather straightforward invariance is rather difficult to obtain. Recognition or categorization of spatiotemporal patterns allows for their symbolic labeling, although such labeling may sometimes be a crude approximation. Transition from recurrent neural networks (RNNs) to finite state automata rules and symbols may be done in several ways: extracting transition rules from dynamics of RNNs, learning finite state behavior by RNNs, or encoding finite-state automata in neural networks [63,22]. Although a lot of effort has been devoted to this subject most papers assume only two internal states (active or not) for automata and for network PEs, severely restricting their possibilities. Relations between more complex PEs and automata with complex internal states are very interesting but not much is known about them. Sequential processes in modular networks, composed of subnetworks with some local memory, should roughly correspond to the information processing by neocortex. These processes could be approximated by probabilistic multi-state fuzzy automata. Complex network processing elements with local memory may process information step-wise, depending on their history. Modules, or subnetworks, should specialize in solving fragments of the problem. Such approach may be necessary to achieve the level of non-trivial grammar that should emerge from analysis of transitions allowed in finite state automata corresponding to networks.
3.8
Up to the bruins and the societies of bruins
The same scheme may be used at higher levels: modular networks described above are used to process information in a way that roughly corresponds to functions of various brain areas, and these networks become modules that are used to build nextlevel “supernetworks”, functional equivalents of whole brains. The principles at each level are similar: networks of interacting modules adjust to the flow of information changing their internal knowledge and their interactions with other modules. Only at quite low level, with very simple interaction and local knowledge of PEs, efficient algorithms for learning are known. The process of learning leads to emergence of novel, complex behaviors and competencies. Maximization of system information capacity may be one guiding principle in building such systems: if the supernetwork is not able to model all relations in the environment then it should recruit additional members that will specialize in learning facts, relations or behaviors that have been missing.
Quo Vadis Computational Intelligence?
15
At present all systems that reach the level of higher cognitive functions and are used for commonsense reasoning and natural language understanding are based on artificial intelligence expert system technology. The CYC system (www.cyc.com) with over one million assertions and tens of thousands of concepts does not use any neural technology or cognitive inspirations. It is a brute-force symbolic approach. Other successful A1 models, such as the Soar [43] or Act [3] systems, have developed also quite far remaining at the level of purely symbolic processing. Can such technology be improved using subsymbolic computational intelligence ideas? Belief networks may be integrated in such systems in relatively easily, but it is still a big challenge for neural systems to scale up to such applications. DISCERN was the only really ambitious project that used neural lexicon for natural language processing [38], but it did not go too far and has been abandoned. Very complex supernetworks, such as the individual brains, may be further treated as units that co-operate to create higher-level structures, such as groups of experts, institutions, think-tanks or universities, commanding huge amounts of knowledge that is required to solve the problems facing the whole society. Brainstorming is an example of interaction that may bring ideas up that are further evaluated and analyzed in a logical way by groups of experts. The difficult part is to create ideas. Creativity requires novel combination, generalization of knowledge that each unit has, applying it in novel ways. This process may not fundamentally differ from generalization in neural networks, although it takes place at much higher level of complexity. The difficult part is to create a system that has sufficiently rich, dense. representation of useful knowledge to be able to solve the problem by combining or adding new conceptslelements.
4
Problems pointed out by experts
Certainly, the statements presented in the previous sections, reflecting authors’ point of view on the subject, do not pretend to be a complete and comprehensive answer to the question “Quo vadis, computational intelligence?”. The field of CI is very broad and still expanding, so - in a sense - even listing all of its branches or subfields may be considered a challenge itself. Having that in mind we had an idea that a good way to make the real and efficient search for the challenging problems is to post this question to a group of the well known experts in several branches of CI. Therefore, we asked a few leading scientists working in the field of computational intelligence (understood in a very broad sense) what - according to them - would be the most challenging problems for the next 5-10 years in their area of expertise, and what solutions (if known) are at the horizon. CI disciplines represented by the experts included neural networks, genetic algorithms, evolutionary computing, swarm optimization, artificial life, Bayesian methods, brain sciences, neuroinformatics, robotics, computational biology, fuzzy
16
W. Duch and J . Malidziuk
systems, rough sets, mean field methods, control theory, and related disciplines. Both theoretical as well as applicative challenges were asked for. Our first idea was to collect the answers and then try to identify some number of common problems that may be of general interest for computational intelligence community. However, after collecting the responses we decided that presentation of individual experts’ opinions with some comments from us will be more advantageous to potential readers. In order to precisely express views and opinions provided by the experts we have decided to present several citations from their responses. For the sake of clarity of the presentation in the following text all citations of experts’ opinions will be distinguished by italic font. Problems posted by the experts can be divided into two main categories: general CI problems related to human-type intelligence, specific problems within various CI disciplines. 4.1
General CI problems related to human-like intelligence
Among general problems envisioned by the experts two were proposed by Lee Giles. The first one concerns bringing robotics into the mainstream world. Probably the effective way of bringing robotics (and CI in general) into the mainstream world will require the development of CI-based user-friendly everyday applications able to convince people of the usefulness and practical value of CI research. Several devices of that kind already exist, e.g. intelligent adaptive fuzzy controllers installed in public lifts or various household machines. These bottom-level, practical successes of CI are however not well advertised and therefore not well known (or actually not at all known) to general public. Paradoxically, events which seem to be much more “abstract” achievements of A1 (at least for non-professionals) became recently very influential signs of A1 successes. These include the defeat of Kasparov by Deep Blue supercomputer or design of artificial dogs - Aibo and Poo-Chi. The other challenge pointed out by Giles is integrating the separate successes of A1 - vision, speech, etc - into an intelligent SYSTEM. In fact building of intelligent agents has been of primary concern for A1 experts for about a decade now. Development of new robotic toys, such as the Aibo dogs, requires integration of many branches of CI. What capabilities will such toy robots show in 20 years? Perhaps similar progress as in the case of personal computer hardware (for example graphics) and software (from DOS to Windows XP) should be expected here. Several advanced robotics projects are being currently developed in the industrial labs. The most ambitious one concerning humanoid robots - developed from and around the Cog project at MIT - demanded integration of several perceptual and motor systems [ 11. Social interaction with humans demands much more: identification and analysis of emotional cues during interactions with humans, speech prosody, shared attention and visual search, learning through imitation, and building theory of mind. Similar challenge concerning the design of the advanced user intefaces using natural language, speech, and visualizations is listed by Erkki Oja. According to
Quo Vadis Computational Intelligence?
17
Oja realization of such integrated, human friendly interfaces requires very advanced and robust pattern recognition methods. As a possible approach to tackle these tasks Oja proposes application of some kind of machine learning, as well as probabilistic modeling methods aimed at finding - in unsupervised manner - a suitable compressed representation of the data. The underlying idea is that when models are learned from the actual data, they are able to explain the data, and meaningful inferences and decisions can be based on the compressed models. These issues are also connected with the questions about functioning of the learning algorithms in human brains. If we can really find out the learning algorithms that the brain is using, this will have an enormous impact on both neuroscience and on the artificial neural systems (Oja). A related challenge from the domain of intelligent human-like interfaces is also stated by John Taylor: how is human language understanding achieved? This is needed to be answered to enable language systems to improve and to allow humanmachine interaction. Before answering this questions two other major challenges in the area of building intelligent autonomous systems need to be considered. The first one is concerned with the problem of how is attention-controlled processing achieved to create (by learning) internal goals for an autonomous system? This requires a reward learning structure, but more specifically a way of constructing (prefrontal-like) representations of goals of actiodobject character at the basis of schema development. Current research on reinforcement learning draws little inspiration from brain research. Perhaps the subject is not understood well enough. On the other hand considerable progress has been achieved by Ai Enterprises in building a “child machine”, trained by reinforcement learning to respond to symbols like an infant [39]. The transcripts from the program have been evaluated by a developmental psychologist as a healthy bubbling of 18-month old baby. This is still only bubbling and it will be fascinating to see how far can one go in this way. The other challenging problem is answering the question of how is automatisation of response achieved by learning? Initial controlled response needs to be ‘put on automatic’ in order to enable an autonomous system to concentrate on other tasks. This may be solved by further understanding of the processes occurring in the frontal lobes in their interaction with the basal ganglia. At the same time episodic and working memory are clearly crucially involved (Taylor). In other words, how is the task initially requiring conscious decisions taken by the brain at the highest level, such as learning to drive, becomes quite automatic? What is the role of working memory here? Perhaps it is needed only to provide reinforcement by observing and evaluating the actions that the brain has planned and executed? Is this the main role of consciousness? Relating one’s own performance to memorized episodes of performance observed previously requires evaluation and comparison followed by emotional reactions that provide reinforcement and increase neuromodulation, facilitating rapid learning. Working memory is essential to perform such complex task, and after the skill is learned there is no need for reinforcement and it becomes
18
W. Duch and J . Maddziuk
automatic (subconscious). Unfortunately working memory models are not well developed. Similarly to Oja, the need for appropriate data (state) representation is also stressed by Christoph von der Malsburg: In the classical field of AI, this question is left entirely open, a myriad of different applications being dealt with by a myriad of different data formats. In the field of Artificial Neural Networks, there is a generic data format - neurons acting as elementary symbols - but this data format is too empoverished, having no provision for representing hierarchical structures, and having no provision of the equivalent of the pointers of AI. A related challenging problem pointed out by von der Malsburg is design of autonomous self-organization processes in the (hierarchical) state organization - the state of an intelligent system must be built up under the control of actual inputs and of short-term and long-term stored information. The algorithmic approach to state construction ... must be overcome and be replaced by autonomous organization. State organization must be conformed to a general underlying idea of the ability of intelligent systems to generalize based on the current state: Intelligent systems relate particular situations to more general patterns. This is the basis for generalization, the hall-mark of intelligence. Each situation we meet is new in detail. It is important to recognize general patterns in them so that known tools and reactions can be applied. To recognize a specific situation as an instance of a general pattern, the system must find correspondences between sub-patterns, and must be able to represent the result by expressing these correspondences as a set of links. Finding such sets of links is an exercise in network self-organization (von der Malsburg). On the other hand self-organization alone seems to be not powerful enough it order to create intelligent systems (behaviors) in limited time and with limited resources. Therefore some kind of learning with a teacher seems to be indispensable. An important sub-category of learning is guided by teaching. Essential instruments of teaching are: showing of examples, pointing, naming and explanation. To provide the necessary instruments that underlay these activities constitutes an considerable array of sub-problems. Human intelligence is a social phenomenon and is based on teaching. The alternative is evolution, but we will hardly have the patience to create the intelligence if only of a mouse or a frog by purely evolutionary mechanisms (von der Malsburg). Another problem stressed by von der Malsburgh is the ability of intelligent autonomous systems to learn from natural environments: Intelligent systems must be able to pick up significant structure from their environment. Machine learning in AI is limited to pre-coded application fields. Artificial neural networks promise learning from input, finding significant structure on the basis of input statistics, but that concept fails beyond a few hundred bits of information per input pattern, requiring astronomical learning times. Animals and humans demonstrate learning from one or a few examples. To emulate this,mechanisrns must be found for identifying significant structure in single scenes. Similarly to Oja, von der Malsburg underlines the role of interaction with natural environment - intelligent systems must be able to
Quo Vadis Computational Intelligence?
19
autonomously interact with their environment, by interpreting the signals they receive and closing the loop from action to perception. The next step on the way of building intelligent systems is the stage of hierarchical integration of separate modules or operational paradigms into one, coherent organizational structure. Two major challenges concerning this issue were put forward by von der Malsburg. The first problem is the subsystem integration. An intelligent system is to be composed of (a hierarchy of) individual modules, each representing an independent source of information or computational process, and problems are to be solved by coupling these modules in a coherent way. This process may be likened to a negotiation process, in which the different players try to reach agreement with each other by adjusting internal parameters. If there is suficient redundancy in the system, a globally coherent state of the system arises by seEforganization. This process is the basis for the creativity of intelligent systems. The problem is to find the general terms and laws which make subsystem integration possible. The other - closely related - challenge is structuring of general goal hierarchies. Whatever intelligent systems do, they are pursuing goals, which they themselves set out with or recognize as important for a given scene or application area. To organize goal-oriented behavior, a system starts with rather generally defined goals (survive, don’t get hurt, feed yourself,..) and must be able to autonomously break those goals down to specific settings, and to self-organize consistent goal hierarchies. The key issues in development of computational intelligence field according to Harold Szu lie in the area of unsupervised learning. The CI science is now in the cross road of taking the advantage of the exponential growth of information sciences modeling and linear growth of neurosciences experiments. The key is to find the proper representation of the complex neuroscience experiment data that can couple the two together. The idea of learning without a teacher has a “natural” support in biological world, since we - people have pairs of eyes, ears, etc. Therefore, the proper representation is a vector time series whose components are input of a pair of eyes, ears, etc. - smart sensor pairs. Szu believes that the unsupervised learning Hebb rule results from the thermodynamics Helmholtz free energy (see [56] for mathematical formulation). According to Szu one of the intermediate problems that need to be solved on the way is developing of appropriate and efficient procedures for sampling information from the environment. One of the key sub-issues are the redundancy problem and the problem of dimensionality reduction. Another central challenge is stated by Paul Werbos in his recent paper [62]1: Artificial neural networks offer both a challenge to control theory and some ways to help meet that challenge. We need new efforts/proposals from control theorists and 1 Submitted to IEEE CDC02 conference by invitation.
20
W. Duch and J. Maridziuk
others to make progress towards the key long-term challenge: to design generic families of intelligent controllers such that one system (like the mammal brain) has a general-purpose ability to adapt to a wide variety of large nonlinear stochastic environments, and learn a strategy of action to maximize some measure of utility across time. New results in nonlinear function approximation and approximate dynamic programming put this goal in sight, but many parallel efforts will be needed to get there. Concepts from optimal control, adaptive control and robust control need to be unified more effectively. The above citation presents the general statement concerning the need for new ideas/proposals that might influence research in the intelligent control area. Going further Werbos states several goals and suggests possible approaches to achieve them. In fact the paper [62] was written with the similar intention as our work and we encourage anybody interested in the subject to read it. Since we are unable to present all ideas from this paper we have chosen only two problems that appear to us to be very important. One of them addresses the problem of appropriate balance between problem independent approach to learning in intelligent systems versus methods taking advantage of problem specific knowledge. In the most challenging applications, the ideal strategy may be to look for a learning system as powerful as possible, a system able to converge to the optimal strategy without any prior knowledge at all - and then initialize that system to an initial strategy and model as close as possible to the most extensive prior knowledge we can find. Another suggestion is to regard artificial intelligent systems in the rational framework which means defining our goals and expectations towards them in the realistic way. We cannot expect the brain or any other physical device to guarantee an exact optimal strategy of action in the general case. That is too hard for any physically realizable system. We will probably never be able to build a device to play a perfect game of chess or a perfect game of Go. ... We look for the best possible approximations, trying to be as exact as we can, but not giving up on the true nonlinear problems of real interest. We would definitely agree with that. In any real situation when non-trivial goals are to be achieved the optimal strategy cannot be “calculated” in a reasonable time. We believe that one of the main obstacles on the way of developing intelligent autonomous systems were - right from the beginning - too high expectations regarding their abilities and the lack of properly defined, achievable, realistic goals. The brains are not all-powerful devices, but have been prepared by millions of years of evolution to make reasonable decisions in situations that are natural from the environmental point of view. In many unnatural situations humans suffer from “cognitive illusions” [46].
4.2
General problems within certain CI disciplines
Several problems stated by the experts concerned particular disciplines that constitute computational intelligence. In the context of neural networks two of the pro-
Quo Vadis Computational Intelligence? 21
posed problems were connected with the reduction of data dimension in both theoretical as well as applicative aspects. One of them known as the curse of dimensionality is pointed out by Vera Kurkova: for some tasks implementation of theoretically optimal approximation procedures becomes unfeasible because of unmanageably large number of parameters. In particular, high-dimensional tasks are limited by the “curse of dimensionality”, i.e., an exponentially fast scaling of the number of parameters with the number of variables. One of the challenges of mathematical theory of neurocomputing is to get some understanding what properties make high-dimensional connectionist models efficient, what attributes of multivariable mappings guarantee that their approximation by certain types of neural networks guarantee does not exhibit the “curse of dimensionality”. Similar challenging problem concerned with unmanageable data dimensionality is put forward by Lip0 Wang: which features are relevant and which of them are important for a task at hand? In several application domains high-dimensional data, except for being computationally infeasible, is also difficult to be properly interpreted. In other words when data dimensionality is high, information can be obscured, because of the presence of irrelevant features. This is important for many data mining tasks, such as classification, clustering, and rule extraction. In most practical problems estimation of relative importance of particular data properties comes out from experts’ knowledge or experience. Quite rarely it becomes available as a result of theoretical analysis. In neural networks domain some general methods supporting that kind of analysis have been already developed. The most popular examples include the Principal Component Analysis - allowing reduction of data dimensionality based on its orthogonalisation and defining the most relevant dimensions. The other well known method is Independent Component Analysis - allowing for blind source separation in case of multi-source and noisy data. Both methods perform well in many cases however their applicability is not unconditional. For example application of PCA method in case of highly interrelated data (e.g. when sampled from multidimensional chaotic systems) may lead to degradation of performance compared to using data that was not pre-processed by PCA [30]. The need for reliable identification of relevant features in multidimensional data is especially important within popular, fast growing disciplines where the increase of the amount of available data is enormous. Indeed, in bioinformatics - for example - tens or even hundreds of thousands of features are defined for some problems, and the selection of information becomes a central issue. One possible approach is to use feature aggregation instead of feature selection. Such hierarchical processing of information allows for integration of very rich input data into simpler, but more informative, higher-level structures. Integration of distributions of timedependent input (sensory) signals creates distributions at the higher levels. Although interval arithmetic is known, relevant mathematics for computing with arbitrary distributions has not yet been formulated. The other promising idea - similar to the way in which attention facilitates control - is selecting subsets of relevant features.
22
W. Duch and J . Malidziuk
This results in a dynamical process, serving the short and long-term goals of the system. Another challenging issue connected with data processing is design and construction of intelligent systems capable of providing a focused search through the huge amount of available data (e.g. published over the Internet). According to Oja in short and medium term, we will have a great demand for fast and reliable computer systems to manage and analyze the vast and ever increasing data masses (text, images, measurements, digital sound and video, etc.) available in databases and the Web, How to extract information and knowledge, to be used by humans, from this kind of scattered data storages? The problem is well known and various solutions are being proposed. One group of solutions is based on visualization techniques, for example using the Web-SOM variant of Kohonen’s networks. Many other clusterization methods and visualization techniques are certainly worth using. Data mining techniques for modeling the user interest and extracting knowledge from data are in the experimental stage. Latent Semantic Indexing [8] is based on the analysis of the terms-document frequency matrix using singular Value Decomposition to find Principal Components that are treated as “concepts”. Unfortunately these concepts are vector coefficients and are only useful for estimation of similarity of documents but they are not understandable concepts interesting to humans. The Interspace Research Project is aimed at semantic indexing of multimedia information and facilitating communication between different communities of experts that use similar concepts. Only a few CI methods have been applied to this field so far. Certainly, the problem of explosive growing of the amount of accessible data has a great impact on artificial systems’ (and also humans’) ability to preprocess and analyze this data and consequently make optimal (or at least efficient) decisions. Gathering a compact set of relevant and complete information concerning a given task requires much more efficient search engines than those available now. One of the underlying features of these “future” search engines must be ability to analyze the data contextually. Ultimately understanding of texts requires sophisticated natural language processing techniques. At this stage the best programs for natural language understanding (NLU) are based on huge ontologies, human created hierarchical description of concepts and their interrelations. The release of the OpenCyc tools by CycCorp in 2001 made such applications easier, but hybrid systems, combining NLU techniques developed by A1 experts with the data mining techniques developed by CI experts, have not yet been created. One of the possible directions on the way to design intelligent decision support systems capable of extracting useful information and knowledge form large data repositories is distributive multi-agent approach in which a set of agents automatically searches various databases and professional services (e.g. the Internet ones) in real time in order to provide an up-to-date, relevant information. This would also require the soft mechanisms for checking information reliability. Furthermore, efficient mechanisms of automated reasoning based on CI techniques need to be applied in such systems.
Quo V a d i s C o m p u t a t i o n a l Intelligence?
23
Another challenge was identified in the area of combinatorial optimization (Lip0 Wang): evolutionary computation and neural networks are effective approaches to solving optimization problems. How can we make them more powerful? This question is really hard to answer. In the framework of neural networks two main approaches to solving constraint optimization problems exist: evolving template matching and Hopfield-type networks. Both of them suffer from serious intrinsic limitations. Template matching methods require that the problem to be solved has appropriate geometrical representation. Hopfield-type approaches suffer from gradient minimization scheme and the lack of general recipes for defining constraints coefficients in the energy function. Despite enormous number of papers devoted to the above two types of approaches and despite the development of various modifications to their original formulations it seems that the efficacy of neural network-based optimization methods - although significantly increased compared to the initial approaches - cannot be proven for the problems exceeding a certain level of complexity. Similar situation exists in evolutionary computation domain where, for example, no general rules were yet developed concerning the efficient coding scheme or choosing a priori a suitable form of crossover operation or appropriate mutation probability. In most cases the above very basic choices are still being decided by trial and error methods. Consequently, in complex problem domains the time required to achieve reasonably good solutions is prohibitive. Similar problems concerning scalability of evolutionary computation algorithms are pointed out by Xin Yao: There have been all kinds of evolutionary techniques, methods and algorithms published in the literature which appear to work very well for certain classes of problems with a relatively small size. However, few can deal with large and complex real world problems. It is well known that divideand-conquer is an effective and often the only strategy that can be used to tackle a large problem. It is unclear, though, how to divide a large problem and how to put the individual solutions back together in a knowledge-lean domain. Automated approaches to divide-and-conquer will be a challenge, as well as an opportunity to tackle the scalability issue, for evolutionary computation researchers. An issue closely related to scalability problem is the lack of theoretical estimations of computational complexity of evolutionary methods: We still know very little about the computational time complexity of evolutionary algorithms on various problems. It is interesting to observe that a key concern in the analysis of algorithms in the mainstream computer science is computational time complexity, while very f e w complexity results have been established f o r evolutionary algorithms. It is still unclear where the real power, if any, of evolutionary algorithms is (Yao). Another problem emphasized by Yao is the need for suitable mechanisms that allow promotion of a "team work" rather than the best (highest scored) individuals: Evolutionary computation emphasizes populations. While one can use a very large population size, it is often the best individual that we are after. This is in sharp contrast to our own (human) experience in problem solving, where we tend to use a group of people to solve a large and complex problem. Clearly, we need to rethink
24
W. Duch and J . Malidziuk
our endeavour in finding the best individual. Instead, we need the best team to solve a large and complex problem. This challenges us to think about questions such as how to evolve/design the best team and how to scale up the team to deal with increasingly large and complex problems.
5
Conclusions
In this short article only a few challenges facing various branches of computational intelligence may obviously be identified. According to several suggestions the underlying issues are related to - generally speaking - emulation of human-type intelligent behavior. Within this research area several specific goals and challenges are identified, e.g. flexible data (state) representations and suitable, context (state) dependent training methods, training methods involving both supervised and unsupervised paradigms allowing to combine learning from examples with self-organizing evolutionary development of the system, further investigation of the working mechanisms of biological brains, integration of solutions achieved for partial (individual) problems into more complex, efficiently working systems, theoretical investigations on the complexity, potential applicability and limitations of explored ideas. We have tried to show some promising directions that should allow to model certain brain-like functions, going beyond the current applications of neural networks in pattern recognition. UCI repository of data for machine learning methods [37] has played a very important role in providing the pattern recognition problems to be solved. Collection of more ambitious problems for testing new approaches going beyond classification and approximation is urgently needed. We hope that the issues pointed out by professionals and by ourselves will serve as useful pointers - especially for young and less experienced researchers looking for interesting problems - in developing computational intelligence in promising directions.
Acknowledgments We would like to thank our expert colleagues who supported this project by sending descriptions of problems that according to them are the most challenging issues in the field of computational intelligence. We gratefully acknowledge the helpful comments from C. Lee Giles (The Pennsylvania State University), Vera Kurkova (Academy of Science of the Czech Republic), Christoph von der Malsburg (RuhrUniversitat Bochum), Erkki Oja (Helsinki University of Technology), Harold Szu (Naval Research Laboratory), John G. Taylor (King’s College London), Lip0 Wang
Q u o V a d i s C o m p u t a t i o n a l Intelligence? 25
(Nanyang Technical University), Xin Yao (University of Birmingham) and Paul Werbos (National Science Foundation). W.D. would like to thank the Polish State Committee for Scientific Research for suppport, grant no. 8 T1 IC 006 19. References 1. Adams, B., Breazeal C., Brooks, R., Scassellati, B.: Humanoid Robots: A New Kind of Tool, IEEE Intelligent Systems 15 (2000) 25-31 2. Amit D.J.: The Hebbian paradigm reintegrated: local reverberations as internal representations. Brain and Behavioral Science 18 (1995) 617-657 3. Anderson, J.R.: Rules of the Mind. Erlbaum, Hillsdale, N.J. (1993) 4. Bedford, T., Keane M., Series, C.: Ergodtc theory, symbolic dynamics and hyperbolic spaces. Oxford University Press, Oxford, UK (1991) 5. Bishop, C.M.: Neural Networks for Pattern Recognition. Oxford University Press (1995) 6. Crevier, D.: AI: The Tumultuous History of the Search for Artificial lntelligence. Basic Books, New York (1993) 7. McClelland, J.L, Rumelhart D.E. and the PDP research group.: Parallel distributed processing. The MIT Press, Cambridge, MA (1987) 8. Deerwester, Dumais, Landauer, Furnas, Harshman (1990) Indexing by latent semantic analysis, Journal of the American Society for Information Science 41(6): 391-407 9. Duch, W.: Platonic model of mind as an approximation to neurodynamics. In: Brain-like computing and intelligent information systems, ed. S. Amari, N. Kasabov. Springer, Singapore (1997) 491-5 12 10. Duch, W.: Similarity-Based Methods. Control and Cybernetics 4 (2000) 937968 11. Duch, W., Adamczak, R., Diercksen, G.H.F.: Constructive density estimation network based on several different separable transfer functions. 9th European Symposium on Artificial Neural Networks (ESANN), Brugge. De-facto publications (2001) 107-112 12. Duch, W., Adamczak, R., Grabczewski, K.: Methodology of extraction, optimization and application of crisp and fuzzy logical rules. IEEE Transactions on Neural Networks 12 (2001) 277-306 13. Duch, W., Diercksen, G.H.F.: Feature Space Mapping as a universal adaptive system. Computer Physics Communications 87 (1995) 341-37 1 14. Duch, W., Grudzinski, K., Prototype based rules - new way to understand the data. Int. Joint Conference on Neural Networks, Washington D.C., July 2001, 1858-1863 15. Duch, W., Itert, L., Grudzinski, K.: Competent undemocratic committees. Int. Conf. on Neural Networks and Soft Computing, Zakopane, Poland (in print, 2002)
26
W . Duch and J . Maridziuk
16. Duch W., Jankowski, N.: Survey of neural transfer functions. Neural Computing Surveys 2 (1999) 163-213 17. Duch, W., Jankowski, N.: Transfer functions: hidden possibilities for better neural networks. 9th European Symposium on Artificial Neural Networks (ESANN), Brugge. De-facto publications (2001) 8 1-94 18. Duda, R . 0 , Hart, P.E, Stork, D.G.: Pattern Classification, 2nd Ed, John Wiley & Sons, New York (2001) 19. Fahlman, S.E., Lebiere, C.: (1990) The cascade-correlation learning architecture, In D. Touretzky (Ed.), Advances in Neural Information Processing Systems, 2, Morgan Kaufmann, 524-532 20. Frasconi, P., Gori, M., Sperduti, A.: A General Framework for Adaptive Processing of Data Structures. IEEE Transactions on Neural Networks 9 (1998) 768-786 21. Frean, M.: (1990) The upstart algorithm: a method for constructing and training feedforward neural networks, Neural Computation 2: 198-209 22. Giles, L.C., Gori, M. (Eds): Adaptive procesing of sequences and data structures. Springer, Berlin (1998) 23. Goldfarb, L. Nigam, S.: The unified learning paradigm: A foundation for AI. In: V.Honovar, L.Uhr, Eds. Artificial Intelligence and Neural Networks: Steps Toward Principled Integration. Academic Press, Boston (1994) 24. Golomb, D., Hansel, D., Shraiman, B, Sompolinsky, H.: Clustering in globally coupled phase oscilators. Phys Rev. A 45 (1992) 35 16-3530 25. Hasti, T, Tibshirani, R, Friedman J.: The Elements of Statistical Learning. Springer Series in Statistics, New York (2001) 26. Hopfield, J.J.: Neural networks and physical systems with emergent collective computational abilities, Proc. National Academy of Science USA, 79 (1982) 2554-2558 27. Hopfield, J.J., Brody, C.D.: What is a moment? Transient synchrony as a collective mechanism for spatiotemporal integration. PNAS 98 (2001) 1282-1287 28. Hsu C.S.: Global analysis by cell mapping, J. of Bifurcation and Chaos 2 (1994) 727-77 1 29. Jankowski, N., Duch W.: Optimal transfer function neural networks. 9th European Symposium on Artificial Neural Networks (ESANN), Brugge. De-facto publications (2001) 101-106 30. Jaruszewicz, M., Mandziuk, J. (2002) Short-term weater forecasting with neural nets, International Conference on Neural Networks and Soft Computing, Zakopane. Poland, (submitted) 31. Kasabov, N. (1988) ECOS - A framework for evolving connectionist systems and the 'eco' training method, Proc. of ICONIP'98 - The Fifth International Conference on Neural Information Processing, Kitakyushu, Japan, 3: 12321235
Quo Vadis Computational Intelligence? 27
32. Kunstman, N., Hillermeier C., Rabus, B., Tavan P.: An associative memory that can form hypotheses: a phase-coded neural network. Biological Cybernetics 72 (1994) 119-132 33. MIT Encyclopedia of Cognitive Sciences. Ed. M.A. Wilson, F.C. Keil, MIT Press, Cambridge, MA (1999) 34. Mandziuk, J., Shastri, L. (1999) Incremental Class Learning - an approach to longlife and scalable learning, Proc. International Joint Conference on Neural Networks (IJCNN'99), Washington D.C., USA, (6 pages on CD-ROM) 35. Mandziuk, J., Shastri, L. (2002) Incremental Class Learning approach and its application to Handwritten Digit Recognition problem, Information Sciences (in press) 36. Marczak, M,, Duch, W., Grudzinski, K., Naud, A.: (2002) Transformation Distances, Strings and Identification of DNA Promoters. Int. Conf. on Neural Networks and Soft Computing, Zakopane, Poland (in print, 2002) 37. Mertz, C.J., Murphy, P.M.: UCI repository of machine learning databases, http://www.ics.uci. eddpublmachine-learningdatabases 38. Miikkulainen, R. Subsymbolic natural language processing: an integrated model of scripts, lexicon and memory. MIT Press,Cambridge, MA (1993) 39. Minsky M., Papert S.: Perceptrons. MIT Press, Cambridge, MA (1969), 2"d ed. (1988) 40. Mitchell T.: Machine learning. McGraw Hill (1997) 41. Mitra, P., Mitra, S., Pal, S.K.: (2000) Staging of cervical cancer using Soft Computing, IEEE Transactions on Biomedical Engineering, 47(7): 934-940 42. Newman J, Baars B.J.: Neural Global Workspace Model. Concepts in Neuroscience 4 (1993) 255-290 43. Newell, A,: Unified Theories of Cognition. Cambridge, MA: Harvard University Press (1990) 44. O'Regan, J.K., Noe, A.: A sensorimotor account of vision and visual consciousness. Behavioral and Brain Sciences 24(5) (2001, in print) 45. PGkalska, E., Pacilik, P., Duin, R.P.W.: A generalized kernel approach to dissimilarity-based classification. J. Machine Learning Research 2 (2001) 175-2 11 46. Piattelli-Palmarini, M.: Inevitable Illusions: How Mistakes of Reason Rule Our Minds. John Wiley & Sons (1996) 47. Poole D., Mackworth, A., Goebel, R.: Computational Intelligence. A Logical Approach. Oxford University Press, New York (1998) 48. Rich E., Knight K.: Artificial Intelligence. McGraw Hill Inc, Int'l Edition (1991) 49. Rumelhart, D.E., Hinton, G.E., Williams R.J.: Learning representations by back-propagating errors, Nature 323 (1986) 533-536 50. Russell, S. J., Norvig, P.: Artificial Intelligence: A Modern Approach. PrenticeHall, Englewood Cliffs, N.J. (1995)
28
W. Duch and J . Maridziuk
51. Saad, E.W., Prokhorov, D.V., Wunsch 11, D.C.: (1998) Comparative study of stock trend prediction using time delay, recurrent and probabilistic neural networks, IEEE Transactions on Neural Networks, 9(6): 1456-1470 52. Shastri, L., Fontaine, T.: (1995) Recognizing handwritten digit strings using modular spatio-temporal connectionist networks, Connection Science 7(3): 21 1-235 53. Specht, D.: (1990) Probabilistic neural networks, Neural Networks 3: 109-118 54. Specht, D.: (1991) A general regression neural network, IEEE Transactions on neural Networks 2: 568-576 55. Sun, R., Giles, L. (Eds): Sequence learning. Springer Verlag, Berlin (2001) 56. Szu, H., Kopriva, I (2002) Constrained equal a priori entropy for unsupervised remote sensing, IEEE Transactions on Geoscience Remote Sensing 57. Thrun, S., Explanation based neural network learning. A lifelong learning approach. Kluwer Academic Publishers, Boston / Dordrecht / London, 1996 58. Thrun, S., Mitchell, T.M.: (1994) Learning one more thing, Technical Report: CMU-CS-94-184 59. Treister-Goren, A., Hutchens, J.L.: Creating AI: A unique interplay between the development of learning algorithms and their education. Technical Report, A1 Enterprises, Tel-Aviv 2000. Available from http://www.a-i.com 60. Waibel, A.: (1989) Consonant recognition by modular construction of large phonemic time-delay neural networks, In D. Touretzky (Ed.), Advances in Neural Information Processing Systems, 1, Morgan Kaufmann, 2 15-223 61. Wang, D.: On Connectedness: A Solution Based on Oscillatory Correlation. Neural Computation 12 (2000) 131-139 62. Werbos, P., Neural Networks for Control: Research Opportunities and Recent Developments, IEEE CDC’02 Conference, (submitted, 2002) 63. Wermter, S., Austin, J., Willshaw, D., (Eds.): Emergent neural computational architectures based on neuroscience. Towards Neuroscience-inspired computing. Springer, Berlin (2001) 64. Winston P.: Artificial Intelligence. 3rd ed, Addison Wesley (1992)
Mathematical Tools for Machine Intelligence
This page intentionally left blank
MAPPINGS BETWEEN HIGH-DIMENSIONAL REPRESENTATIONS I N CONNECTIONISTIC SYSTEMS VERAK~JRKOVA Institute of Computer Science Academy of Sciences of the Czech Republic Pod uoddrenskou ~ 6 %2, 182 07 Prague 8, the Czech Republic e-mail
[email protected] Approximation of high-dimensional mappings by neural networks is investigated in the context of nonlinear approximation theory. It is shown that the “curse of dimensionality” can be avoided when certain norms are kept low. There are described properties and methods of derivation of estimates of such norms. The results are applied to perceptron and RBF networks.
1
Introduction
Classical artificial intelligence has modeled cognitive tasks using rule-based manipulation of symbols. Typically, symbolic representations has been discrete and low-dimensional, which had both conceptual and computational advantages. In contrast t o classical AI, connectionistic computational models employ learning in systems of distributed representations. Such representations tend to be high-dimensional as they describe objects in terms of many parameters. Connectionistic systems map one type of a distributed representation to another one. The primary computational technique used in such systems is approximation of high-dimensional mappings implemented in neural networks of various types. For example NETtalk 33 , which performs “reading aloud”, maps binary vectors of length over 200 (coding segments of written text) to vectors with 26 real entries (coding phonemes). A vowel-recognizer performing “lip-reading” 34 transforms vectors of length 500 (corresponding to pixels from video) t o a phonetic code of length 32. One of the goals of research in computational intelligence is to understand what properties make such high-dimensional connectionistic models efficient and flexible. A theoretical understanding can provide guidelines for a design of computationally feasible procedures that are flexible in the sense that they are capable of performing a variety of high-dimensional tasks by merely changing procedures parameters. Since 19th century, mathematics studied families of mappings, such as polynomials, rational functions and trigonometric sums, which are sufficiently flexible so that with a proper choice of coefficients, they are able to approx-
31
32
V. KGrtova‘
imate arbitrarily well any continuous or measurable mapping defined on a compact (closed and bounded) subset of a multidimensional space. Later, it has been shown that also splines, sums of waveletes and many types of feedforward networks posses this flexibility, which is sometimes called the “universal approximation capability”. However for some tasks, implementation of theoretically optimal approximation procedures becomes unfeasible because of unmanageably large number of parameters. In particular, high-dimensional tasks are limited by the “curse of dimensionality” 4 1 i.e., an exponentially fast scaling of the number of parameters with the number of variables. However, some mappings between high-dimensional representations have been successfully implemented using connectionistic systems of moderate complexity (see, e.g., 33, 34). Approximation theory offers some explanation of feasibility of such implementations. It has derived various upper bounds on complexity of approximating systems depending on the number of variables of functions to be approximated together with their other characteristics. Inspection of such bounds shows that we can cope with the curse of dimensionality by constraining the characteristics involved. For example, upper bounds on worst-case errors in linear approximation are of the form 0 ( n p s l d )where , d is the number of variables, s degree of smoothness of the functions to be approximated, while n is the number of parameters of the linear approximating family (see, e.g., 29). Thus in linear approximation, the curse of dimensionality can be avoided by increasing smoothness together with the number of variables. In this paper, we describe ways how to cope with the curse of dimensionality in nonlinear approximation schemes corresponding to connectionistic systems. We study such systems in the framework of variable-basis approximation, which includes feedforward networks as well as other nonlinear systems with free parameters. We show that for variable-basis approximation, the role of the characteristics to be kept low to cope with the curse of dimensionality is played by a norm tailored t o t h e particular basis. In the case of feedforward networks, such a basis corresponds to the type of computational units (e.g., perceptrons or radial units). We show that in contrast to linear approximation, where with increasing number of variables the sets of functions that do not exhibit the curse of dimensionality are more and more constrained (as the requirements on the degree of their smoothness are increasing), in the case of feedforward networks, such sets of d-variable functions can be embedded into corresponding sets of d 1-variable functions. We derive properties of such sets and methods of estimation of norms that define them. The paper is organized as follows. In section 2, there are introduced concepts and notation concerning fixed and variable-basis approximation (that
+
Mappings between High-dimensional Representations
33
includes feedforward neural networks), while in section 3, upper bounds on rates of these two types of approximation are stated in terms of norms of functions to be approximated: Sobolev norms and variation with respect to a set of functions. In section 4, the concept of variation is illustrated by examples of real-valued Boolean functions with “small” variation with respect to perceptron networks. In sections 5 and 6, there are presented methods of estimation of variation from above and from below. Section 7 is a brief discussion. 2
Fixed and variable-basis approximation
Tasks representable as mappings can be performed by devices computing functions depending on two vector variables: an input vector (corresponding to a coded pattern to be recognized or transformed) and a parameter vector (to be adjusted during learning mode). Due to error-correcting afterprocessing (such as best guess 33) it is sufficient when such devices compute mappings that perform the tasks only approximately. Classical linear approximation theory has explored properties of parametrized sets formed by linear combinations of the first n elements of a set of basis functions with a fixed ordering (e.g., polynomials ordered by degree or sines ordered by frequencies). Thus it can be called fixed-basis approximation. Connectionistic systems exploit parametrized families with a flexible choice of basis functions that belong to a nonlinear approximation scheme called variable-basis approximation. Formally, such scheme is defined for any subset G of a real linear space X as the set of all linear combinations of at most n elements of G, which is denoted span,G. With proper choices of G it includes feedforward networks with a single linear output unit and any number of hidden layers as well as other nonlinear families with free inner parameters such as free-nodes splines, rational functions with free poles, and trigonometric sums with free-frequencies. Since in applications all parameters are bounded, we shall also consider variable-basis approximation schemes with constraints on coefficients of linear combinations of basis functions. If such a constraint is defined in terms of a norm on the space R” of coefficient vectors, then the set of functions computable by such a scheme is, for a proper scalar, contained in the set of all convex combinations of at most n elements of the scaled set G(c) = {wg : g E G, (201 5 c), i.e., in conw,G(c). This can be easily checked for a constraint defined in terms of 11-norm on R” and as all norms on R” are equivalent, it can be further extended to a general norm.
34
V. KGrkovci
A computational unit can be formally described as a function $ : A x K -+ R, where A C R q is the set of “inner” parameters of the unit, while K C Rd is the set of its inputs (we shall restrict our considerations to inputs in either the Euclidean cube [0, lIdor the Boolean one (0, l}d). Denote G # ( K ,A) = {$(a, .) : K -+ R : a E A } the set of functions on K computable by a computational unit C$ with all possible choices of parameters a E A. For A = Rd,we shall write only G # ( K ) ,while for A = Rd and K = [ O , l I d , we shall write only G4. The set of functions computable by a neural network with n hidden units computing C$ is spun,G+ if all coefficients in linear combinations are allowed, i.e., output weights are unconstrained) or it is a subset of conv,G($) if a constraint in the form of a norm on output weights is imposed. Standard types of computational units used in neurocomputing are perceptrons and RBF units, but this formalism also includes other types of parametrized mappings like trigonometric functions with frequencies playing the role of parameters. A perceptron with an activation function $ : R + R computes $ ( ( v , b ) , z )= $(w . z + b) : A x K + R and R B F unit with radial function R+ -+ R (R+ denotes the set of positive reals) computes C$((v,b ) , z ) = $(b(llz - vII) : A x K -+ R. Standard types of activation functions are sigmoidal functions, i.e., nondecreasing functions u : R + R with limt,-, a ( t ) = 0 and limt++oo a ( t ) = 1. Heaviside activation function 6 is defined as 6 ( t ) = 0 for t < 0 and 6 ( t )= 1 for t 2 0. A standard radial function is the Gaussian function y ( t ) = e P t 2 . We shall denote by P d ( $ ) the set of functions computable by perceptrons with activation $, i.e., I‘d($) = G$ for 4((v, b ) , z ) = $(v . z + b) : Rd+’ x [0, lId -+ R. Similarly, by Fd($, 11. 1 1) is denoted the set of f u n c tions computable by R B F - u n i t s with radial function $, i.e., Fd($) = G# for $((w, b ) , z ) = $(b(llz - ~ 1 1 ) : Rd+’x [0, lId-+ R. Since the set of functions cornputable by perceptrons with Heaviside activation Pd(6) is equal to the set of characteristic functions of closed half-spaces of Rd restricted t o [ O , l l d , we shall denote it by Hd.
3
Upper bounds on rates of approximation of multivariable functions
For many types of computational units 4, the sets UnE~+spun,G@ are dense in the space of all continuous functions C([O, lid) with the supremum norm or C,([O, lid) with ,&-norms, p E [l,co) (see, e.g., 19, 30). Although density guarantees arbitrarily close approximation of all functions from C( [ O , l l d ) , L,([O, lid), resp., for practical purposes, its implications are limited to func-
Mappings between High-dimensional Representations 35
tions for which a sufficient accuracy can be achieved by span,G@ with n small enough t o allow implementation. Thus it is useful to study speed of decrease of errors in approximation by span,G and cmu,G with n increasing. Maurey 31, Jones l2 and Barron derived an upper bound on approximation by conu,G that allows to describe conditions on d-variable functions that guarantee approximation without the curse of dimensionality. For a subset M of a normed linear space ( X , [1.11), cl M denotes the closure of M in the norm-induced topology, for f E X the distance of f from M is denoted by 11 f - Mil, conu G = UngN+COTIVnG and span G = UnEN+span,G, where N+ denotes the set of positive integers. The following theorem presents a slightly modified version of Maurey-Jones-Barron's upper bound. Theorem 3.1 Let G be a bounded subset of a Hilbert space ( X , 11. 1 1) and SG = supoFG11g11. Then f o r every f E cl c m v G and f o r every positive integer n , For simplicity, we present here upper bounds on variable-basis approximation only for Hilbert spaces, however similar upper bounds as in Theorem 3.1 have been derived in for Lp-spaces, p E (l,co), and in 2 , 9 , lo, 28, 24 for spaces of continuous functions with the supremum norm. For certain sets G, tight improvements of Maurey-Jones-Barron's bound have been obtained (e.g., for G orthonormal in 24, 21 and for G = Pd(a) in 2 , 28, 2 3 ) . Since conv,G C span,G, the upper bound from Theorem 3.1 also applies t o rates of approximation by span,G. Replacing the set G by G(c) = { w g : g E G,IwI 5 c } , we can apply Theorem 3.1 to all elements of U c ~ ~ +conu c l G(c) (as cunv,G(c) c span,G(c) = span,G for any c E R). This approach can be mathematically formulated in terms of a norm tailored to a set G. Let ( X , 11.11) be a normed linear space and G lie its subset, then Gvariation (variation with respect to G) is defined as the Minkowski functional of the set cl conu(G U -G), i.e.,
l l f l l ~ = inf{c > 0 : f / c
E
cZconv(G U -G)}.
X . It G-variation is a norm on the subspace {f E X : l l f l l ~ < I X I } was introduced in as an extension of the concept of variution with respect to half-spaces (Hd-variation) introduced in '. For functions of one variable, variation with respect to half-spaces coincides, up to a constant, with the notion of total variation studied in the integration theory '. Moreover in Lpspaces, Hd-variation is equal to Pd(cT)-variation for any sigmoidal activation function CJ 20. Thus t o derive consequences of Maurey- Jones-Barron's theorem for sigmoidal perceptron networks, it is sufficient to study properties of H d variation.
36
V. KGrkovd
When a set of functions has to be approximated, it is useful to estimate worst-case error which is mathematically formalized by the concept of deviation 6 ( B , Y ) = supfEBIlf - YI(. The following theorem from l8 is a corollary of Theorem 3.1 formulated in terms of G-variation. If ( X , 11.11) is a normed linear space and b > 0 , then ~ b ( ~ ~ s.b (~l l .~l l ) , denote the ball, sphere, resp., of radius b centered at zero, i.e., Bb(ll.11) = {f E X : l l f l l 5 b} and Sb(ll.ll) = {f E : llfll = b}. Theorem 3.2 Let G be a bounded subset of a Hilbert space ( X , 11.11), SG = s u p g E1~ 1g11, b > 0, 0 5 T I SGb and n be a positive integer. Then
x
(i) f o r every f E X ,
[If
- span,Gll
5
d
m
;
%.
(iai) h(Bb(II.IIG),sWnnG) I
This upper bound shows how to cope with the curse of dimensionality in variable-basis approximation. If {Gd C & ( [ O , lid) : d E N+} is a sequence of sets of functions of d variables, we can keep rate of approximation by spanned within the order of O ( l / f i ) for all d by restricting approximation to functions from balls in Gd-variation. Thus Gd-variation plays a similar role in variable-basis approximation as the Sobolev norm of the order d does in linear approximation. Recall that for R an open subset of Rd,p E [l,oo), the Sobolev space Ws,p(R) is the subspace of L,(R) formed by all functions f : R + R such that for every multi-index a = ( a ~. . .,, a d ) satisfying 0 5 la1 5 s, oafE L,(O), where Da = DF1 . . .D:d is a partial derivative in weak (distributional) sense (see
1. The norm of f E ws,p(R) is defined as llfllf,p= (Coslalss llDafIl;)l’p. The worst-case error in approximation of the unit ball in WS,,(R) with [0, lId C R by an n-dimensional linear subspace X , of Lp(f2)is of the order of O(n-’/‘) 29. More precisely, infx, ~(BI(II.II~,~),X,)O(n-s ld ),where the infimum is taken over all n-dimensional subspaces of L,(R). So if we are free to choose for each n an “optimal” n-dimensional subspace, then we can approximate all functions from Sobolev balls of the order s 2 d within the accuracy O(n-l). So in linear approximation, one can achieve rates of the order of O(n-l) by restricting approximation of functions of d variables only to functions with bounded by a fixed constant. With d increasing, balls Sobolev norms Il.l :,p in these norms are “shrinking” as they are defined by bounds on the sum of L,-norms of all iterated partial derivatives up to the order d. Note that some ~ ~ ~be, extended p to functions in the unit ball in the Sobolev norm ~ ~ . cannot
-
Mappings between High-dimensional Representations
37
+
functions of d 1 variables from the unit ball in the Sobolev norm ~ ~ In contrast to balls in Sobolev norms of degree d, balls in Gd-variation need not to be shrinking with d increasing. Proposition 3.3 L e t d be a positive integer, Gd and Gd+l be bounded subsets of L2([0,lId) and L2([0,lId+’, resp., such t h a t f o r ever9 g € Gd, g : [O, lId+l + k ‘! defined as g(x1,. ..,q + 1 ) = g(x1,. . .,a) belongs t o Gd+l. T h e n there exists a n embedding Vd : B~(ll.ll~,) 4& ( ~ ~ . ~ ~ G d + l ) . Proof. Define Ud on &(ll.ll~,> = cZmv(Gd U Gd) as Ud(g) = g, where g(x1,... ,xd+l) = g(xl,. . . ,xd). As ud on Gd is an embedding, it is also an 0 embedding on cl wnv(Gd U -Gd).
It is easy to check that balls in variation with respect to perceptrons (Pd(q)-variation) and RBF (Fd($)-variation) with any activation or radial function satisfy the assumptions of Proposition 3.3. So in neural network approximation, there exist families of sets of functions of d-variables approximable with rates (3(r1-’/~), which are not shrinking with d increasing. Sets of functions computable by networks with n sigmoidal perceptrons are much larger than a single n-dimensional subspace (they are formed by the union of all n-dimensional subspaces spanned by n-tuples of elements of G). However upper bounds on linear approximation cannot be automatically extended to such unions of n-dimensional subspaces as they may not contain the “optimal” n-dimensional subspaces for linear approximation of balls in Sobolev norms. Nevertheless, for a sufficiently large radius (depending on both d and s), a ball in Hd-variation contains the unit ball in the Sobolev norm of the order s. It was shown in that for a bounded open set R such that [0, lId c R and s > d / 2 1, Br(11.11$,2) is contained in B2rb,(II.JI~d(~) where $J
+
b.3 = ( J R I ( 1 + l l v l l 2(s-1))-1dy)1’2 2 (note that for 2(s - 1) > d , b, is finite). So for s > d/2 + 1, the unit balls in Sobolev norms 11. 1 1f, 2 are contained in balls in Hd-variation of the radius 2bs. The worst-case errors in approximation by n-dimensional linear subspaces of such Sobolev balls bounded from above by C3(n-(1/2+1/d)),while worst-case errors in approximation by neural networks with n sigmoidal perceptrons are by the improvement of MaureyJones-Barron’s bound from 28 bounded from above by b,n-(1/2f1/d). So both upper bounds imply the estimates of rates of approximation of the same order. However, there exist sets of functions with considerably faster rates of approximation by neural networks than rates achievable by linear approximation methods (see 3 , 22). Also properties of projection operators in linear and neural network approximation are quite different - due to geometrical prop-
38
V. K I ~ T ~ O V ~
erties of sets span,G (nonconvexity) they cannot be continuous (see 17).
4
14, 15,
Rates of approximation of real-valued Boolean functions
One of the simplest cases where Maurey-Jones-Barron's theorem gives description of sets of functions that can be approximated by neural networks without curse of dimensionality is space of real-valued Boolean function. This space, denoted by B((0, l}d)and endowed with the inner product defined for f , g E fi({o, as f - g = f(x)g(x), is afinite-dimensional Hilbert space isomorphic t o the 2d-dimensional Euclidean space R2dwith the Z2-norm. Let H d denotes the set of functions on {O,l}d computable by signum -+ R : f(x) = sgn(v. x b),v E R ~b E, perceptrons, i.e., H d = {f : (0, R}. From technical reasons we consider perceptrons with the signum (bipolar) activation function, defined as sgn(t) = -1 for t < 0 and sgn(t) = 1 for t 2 0, instead of more common Heaviside function that assigns zero to negative numbers. For an orthonormal basis G, G-variation can be more easily estimated because it is equivalent to Z1-norm with respect to G (see 22). Expressing elements of such a basis as a linear combination of signum perceptrons, we can obtain description of subsets of B({O,l}d) which can be approximated by preceptron networks without curse of dimensionality. We can use two orthonormal bases. The first one is the Euclidean orthonormal basis defined as E d = {e, : u E { O , l } d } , where e,(u) = 1 and for every x E { o , l } d with x # u, e,(x) = 0. The second one is the Fourier orthonormal basis (see, e.g., 3 5 ) defined as F d = {&(-l)u'z : u E {O,l}d}. Every
xzE(O,lld
+
&
f E fi({0,1)~) can be represented as f(x) = CuE{O,lld f(u)(-~)".~, where f ( u ) = CzE(O,lld f(z)(-l)"'". The Zl-norm with respect to the Fourier basis, llflll,Fd= Ilf^llll = CuE{O,lld lf(u)l, called the spectra2 norm, is equal to Fd-variation ( 21, 24). For a subset I C (0, l}d,I-parity is defined by p l ( u ) = 1 if &I u;is odd, and p I ( u ) = 0 otherwise. If we interpret the output 1 as -1 and 0 as 1, then the elements of the Fourier basis F d correspond to the generalized parity functions. As Fd and Ed are orthonormal, for all f E a({(), I l f l I 1 , E d = llfllEd and Ilf^lll = I!flll,Fd = IlfllFd. It is easy t o see that spun,Fd c qmndn+lHd (as f,(z) = ( - 1 ) ~ - x= + C,d,l(-l)jsgn(u . x - j + f ) and that span,+lEd C spannHd (as e,(x) = Ygn(v';+b)+l for appropriate 2) and b). Thus by Maurey-Jones-
&
Mappings between High-dimensional Representations
39
JT. LLfast17 rates of approximation are guaranteed for functions SO
with either L‘small”variation with respect to signum perceptrons, “small” spectral norm, or “small” norm with respect to the Euclidean basis More interesting classes of functions that can be well approximated by a “moderate” number of Boolean signum perceptrons, are functions with only a “small” number of nonzero Fourier coefficients. The following estimate can be obtained from the embedding of span,Fd into spn,d+lHd combined with the Cauchy-Schwartz inequality (see 2 4 ) . Proposition 4.1 Let d , n, and m be positive integers, m 5 2 d , c > 0 and f E B ( ( 0 ,l}d)be a function with at most m Fourier coeficients nonzero and with l l f l l 5 c. Then [If - spand,+1 H d l l 5 Another example of functions that can be efficiently approximated by perceptron networks are functions representable by “small” decision trees (such trees play an important role in machine learning, see, e.g., A decision tree is a binary tree with labeled nodes and edges. The size of a decision tree is the number of its leaves. A function f : ( O , l } d + R is representable by a decision tree if there exists a tree with internal nodes labeled by variables X I , . . . ,X d , all pairs of edges outgoing from a node labeled by 0s and Is, and all leaves labeled by real numbers, such that f can be computed by this tree as follows. The computation starts at the root and after reaching an internal node labeled by xi, continues along the edge whose label coincides with the actual value of the variable xi; finally a leaf is reached and its label is equal to f ( x 1 , . . . , xd). The following proposition is a corollary of a results from 24. Proposition 4.2 Let d, s be positive integers, b 2 0 , f E B ( ( 0 ,l } d ) be representable b y a decision tree of size s such that for all x E ( 0 , l } d , f ( 2 ) # 0
gE.
and 5
max,~{o,l]d
If(l)l
min,~{a,i}d
if(x)l
5 b. Then 1l.f - spandn+l Bdll 5
&.
Upper bounds on variation
Besides of being a generalization of the concept of total variation, G-variation is also an extension of the notion of Z1-norm: for G a countable orthonormal basis of x,l l f l l ~ = IlfllG,l = lf.gl 2 2 . Thus for G countable orthonormal, the unit ball in G-variation is equal to the unit ball in Z1-norm. Even for some nonorthonormal G, properties of balls in G-variation can be investigated using images of balls in Zl or Ll-norms under certain linear operators. The following proposition shows that when G is finite, balls in G-variation are images of balls in ll(R”),where m = cardG. By 11.111 is denoted El-norm.
xgEG
40
V. Kfirkovd
Proposition 5.1 Let G = (91,.. . ,gm} be a subset of a normed linear space ( X ,11.11) and T : R” + X be a linear operator defined for every w = (w1,...,w,) E R” as T(w)= wigi. T h e n for every T > 0 , B~(1 1. IIG ) = T ( B(1 ~I -1 111) . Proof. By Proposition 2.3 from 24, l l f l l ~ = min{llwlll : w E Rm,f= T(w)}.Thus T(BT(ll.lll))c B,.(ll.lla). To show the opposite inclusion, consider f E BT(ll.ll~). By the definition of G-variation, f = limj+,oofj, where fj = ELl wjigi and llwjlll = lwjil 5 T . Hence there exist w = ( ~ 1 ,... ,w,) E R” such that for all i = 1,... ,m, the sequences {wji : j E N+}converge to wi subsequentially. So the sequence {fj : j E N+} converges subsequentially to f’ = wigi. Since every norm-induced topol0 ogy is Hausdorff, f = f’ and so f = T(w).
ELl
ELl
Even when G is infinite, in some cases G-variation can be estimated in terms of L1-norm. Let q5 E L2(A x K ) , where A C Rq, K c Rd and w E & ( A ) , then Tq defined as Tq(w)= JAw(a)q5(a,x)da is a bounded linear operator Tq : &(A) + L 2 ( K ) (see ). When A, K are compact, Tq is a compact operator and when q5 E C(A x K ) , then Tq : C(A)+ C ( K ) . Intuitively, any function in T+(&(A))can be represented as a “neural network with a continuum of hidden units computing $”, w ( a ) 4 ( a x)da. , Gq-variation of such functions can be estimated from above by ,C1-norm of the “output weight function” w. Theorem 5.2 Let d , m be positive integers, A C R”, K C Rd be compact, q5 E & ( A x K ) and f E & ( K ) be such that f = Tq(w)for some w E & ( A ) . Then IlfllG, 5 IIwIIL1(A) = JA Iw(a)Ida. The proof of this theorem is a modification of an argument used in 2o t o derive a similar result for C(K). Integral representations of the form of a “neural network with a continuum of hidden units” has been originally studied as a tool for derivation of the universal approximation property of various types of neural networks (see, e.g., 5, ll). Fourier representation was combined with Maurey- Jones-Barron’s bound in to derive an upper bound on approximation by sigmoidal perceptrons via estimates for cosine activation. For functions with compactly supported Fourier transforms and continuous partial derivatives of the order s > d / 2 , an integral representation of the form of a neural network with Gaussian RBF units was derived in a. The following theorem from l6 (see also 2 0 ) gives an integral representation of the form of Heaviside perceptron network. For e E Sd-l and b E R,we denote He,b = { x E Rd : e . x b = 0 ) . The half-spaces bounded by this hyperplane are denoted H:6 = { x E Rd : e . x b 2 0 ) and HeTb= {x E Rd :
sA
+
+
Mappings between High-dimensional Representations
e . z + b < 0 ) . By A is denoted the Laplacian operator A ( h ) =
d
41
a2h
w.
Theorem 5.3 Let d be a positive integer and let f : Rd + R be compactly supported and d 2-times continuously diflerentiable. T h e n
+
w f ( e ,b)19(e . z
+ b)dedb,
d-lxR
where ford odd, w f ( e ,b) = a d
sH-Akdf ( y ) d y , e,b
kd
independent of f , while f o r d even, w f ( e ,b) = a d
+
t for t where q ( t ) = -tlogltl constant independent of f . 6
y,and
=
sH-
A k d
e.b
# 0 and ~ ( 0=) 0,
kd
=
ad
is a constant
f ( y ) V ( e .y
+ b)dy,
F,and a d i s a
Lower bounds on variation
The following theorem from 24 gives a geometric characterization of Gvariation in a Hilbert space. By G I is denoted the orthogonal complement of G, i.e., G’- = {f E X : (Vg E G)(f - 9= 0 ) ) . Theorem 6.1 Let ( X , 11-11) be a Hilbert space, G be its bounded non-empty subset and f E X be such that l l f l l ~ < 00. T h e n Ilf IIG = S U P h ~ ~ - G L .h ig.hl. Theorem 6.1 implies a lower bound on G-variation of the form
sup,Efc
So functions that have small inner products with all elements of G (are “almost orthogonal” t o G) have large G-variation. This bound was used in 24 to show that certain Boolean functions have &-variation at least of the order of 0 (2 d /6 ). The proof was based on properties of rather special Boolean functions called bent functions. They can be extended t o functions defined on [0,lld with Hd-variation of the same order. It was shown in 28 that for G = H d , Maurey-Jones-Barron’s upper Ud- H d ) ) 5 r / f i , can be slightly improved to bound, ~ ( B T ( ( ( . ( ( H d ) , C 0 7 1 2 ) 1 2 ( H a tight bound of the form r/n1/2+1/d(see 23 for extension t o other sets G). So in the ball BT(ll.II~d), where T is of the order of 0(2d/6), there must be a function, for which the worst-case error r/n1/2+1/din approximation by cOnV,(Hd(r) U - - H ~ ( T ) ) is achieved. Such function cannot be approximated by perceptron networks efficiently. Another method of demonstrating existence of functions with large variation is based on comparison of cardinality of G with certain covering numbers.
42
V. KZirkova’
Define a binary relation p on the unit ball Sl(ll.ll) of a Hilbert space ( X , 11-11) by p ( f , g) = arccos I f .g[. It is easy to see that p is a pseudometrics measuring distance as the minimum of the two angles between f and g and between f and -g (it is a pseudometrics as the distance of antipodal vectors is zero). For a subset G of S1(11.11) define extent of G as aG
=inf{a E [ o , r / 2 ]: (vf E s1(ll-11))(3g E G ) ( p ( f , g )
5 a)]-
Note that QG is the infimum of all a for which G is an €-net in &(lI.\l), i.e., balls of radius E centered at elements of G cover S1(11.11). For G compact, we can replace inf in the definition of GIG by min. This is the case of Hd which is compact in LP([O,lid) for any p E [l,00) and any positive integer d lo. When QG is small, G is “almost dense” in S1(11.11), while when a~ is large, G is “sparse” in S l ( ~ ~If. ~ QIG ~is) .close to f , then there exists an element in Sl(ll.ll)which has a large “angular distance” from all elements of G (is almost orthogonal t o G) and hence it has a large G-variation. Metric entropy studies “size” of sets in Banach spaces in terms of covering numbers. The size of the smallest a-net in &(((.I\) is the covering number cOv,S1(((.I() (see 25). When for some a close to ~ / 2 the , cardinality of G is smaller than a-covering number of S1(11.11), then there exists a function in S 1(1 1. I I) with “large” G-variation. Proposition 6.2 Let G be a subset of the unit sphere S1(ll.ll) in a Hilbert space ( X , 11. 1 1) and a E [ O , T / ~ ] be such that cardG < c ~ v ~ S ~ Then ( ~ ~there . ~ exists f E Sl(lI.[l)for which llfllG 2 l l c o s a . Proof. If cardG < cosa, then LYG 5 a. So there exists f E Sl(ll.ll) such that for all g E G, p( f lg ) 2 a and hence 1 f . g1 5 C O S ~ .So by Theorem 6.1, l\fllG 2 l/cOsa0 Covering numbers of S”-l with the angular pseudometrics p grow for fixed a asymptotically exponentially with the dimension m 13. So if a subset G of the space of real-valued Boolean functions has cardinality that depends on 2d only polynomially, then there exists a function with “large” G-variation.
7 Discussion We have shown that it is possible to cope with the curse of dimensionality when approximation is restricted to functions with certain norms bounded by a fixed constant independent of the number of variables. For linear approximation, such norms are Sobolev norms of order increasing with the dimension while for neural networks, such norms are variations with respect to computational units. For sigmoidal perceptrons they are all equal to variation with
Mappings between High-dimensional Representations 43
respect to half-spaces and for RBF units, they are variations with respect to spherical waves of the shape corresponding to radial functions. However, examples of functions with variations depending exponentially on the number of variables show that interpretations of Maurey-JonesBarron’s theorem as proof of “dimension-independent” approximation capabilities of neural networks are misleading. It is not possible to approximate all &variable functions by neural networks with rates of the order C J ( T X - ~ To achieve such rates, approximation has to be restricted to functions from balls in variation with respect to the type of computational units. We have described methods of estimation of such variations. Upper bounds can be derived from integral representations of the form of a neural network with a (‘continuum of hidden units” of a given type and lower bounds from geometrical considerations (angular relationships to hidden unit functions). Existence and properties of the norms described in this paper partially explain efficiency of neural networks in performing high-dimensional tasks.
Acknowledgement This work was partially supported by GA CR grant number 201/00/1489.
References 1. Adams, R. A. (1975). Sobolev Spaces, New York: Academic Press. 2. Barron, A. R. (1992). Neural net approximation. In Proceedings of the 7th Yale Workshop on Adaptive and Learning Systems (pp. 69-72). 3. Barron, A. R. (1993). Universal approximation bounds for superposition of a sigmoidal function. IEEE Transactions on Information Theory, 39, 930-945. 4. Bellman, R. (1957). Dynamic Programming. Princeton: Princeton University Press. 5. Carroll, S. M. & Dickinson, B. W. (1989). Construction of neural nets using the Radon transform. In Proceedings of IJCNN’89 (pp. I. 607-611). New York: IEEE Press. 6. Darken, C., Donahue, M., Gurvits, L. & Sontag, E. (1993). Rate of approximation results motivated by robust neural network learning. In Proceedings of the 6th Annual ACM Conference on Computational Learning Theory (pp. 303-309). New York: ACM. 7. F’riedman, A. Foundations of Modern Analysis. New York: Dover, 1992. 8. Girosi, F., & Anzellotti, G. (1993). Rates of convergence for radial basis function and neural networks. In Artificial Neural Networks for Speech and Vision (pp.97-113). London: Chapman & Hall.
44
V. Kfirkovd
9. Girosi, F. (1995). Approximation error bounds that use VC-bounds. In Proceedings of ICANN’95 (pp. 295-302). Paris: EC2 & Cie. 10. Gurvits, L. & Koiran, P. (1997). Approximation and learning of convex superpositions. Journal of Computer and System Sciences, 55, 161-170. 11. Ito, Y. (1991). Representations of functions by superpositions of a step or sigmoid function and their applications to neural network theory. Neural Networks, 4, 385-394. 12. Jones, L. K. (1992). A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training. Annals of Statistics, 20, 608-613. 13. Kainen, P. C., KdrkovB, V. (1993). Quasiorthogonal dimension of Euclidean spaces. Applied Math. Letters, 6,7-10. 14. Kainen, P. C., KdrkovB, V. & Vogt, A. (1999). Approximation by neural networks is not continuous. Neurocomputing, 29, 47-56. 15. Kainen, P. C., Kdrkovb, V. & Vogt, A. (2000). Best approximation by Heaviside perceptron networks. Neural Networks, 13, 645-647. 16. Kainen, P. C., Kirkovi, V. & Vogt, A. (2000). An integral formula for Heaviside neural networks. Neural Network World, 10, 313-319. 17. Kainen, P. C., Kirkovb, V. & Vogt, A. (2001). Continuity of approximation by neural networks in &-spaces. Annals of Operational Research, 101, 143-147. 18. KdrkovB, V. (1997). Dimension-independent rates of approximation by neural networks. In Computer-Intensive Methods i n Control and Signal Processing: Curse of Dimensionality (Eds. Warwick, K., KArnjr, M.) (pp. 261-270). Boston: Birkhauser. 19. Kirkovb, V. (2002). Universality and complexity of approximation of multivariable functions by feedforward networks. In Softcomputing in Industrial Applications - Recent Advances (Eds. R. Roy, M. Koeppen, S. Ovaska, T. F’uruhashi, F. Hoffmann). London: Springer-Verlag (to appear). 20. KdrkovB, V., Kainen, P. C. & Kreinovich, V. (1997). Estimates of the number of hidden units and variation with respect to half-spaces. Neural Networks, 10, 1061-1068. 21. Kfirkovb, V. & Sanquinetti, M. (2001). Bounds on rates of variable-basis and neural network approximation. IEEE Trans. on Information Theory, 47, 26592665. 22. KilrkovB, V. & Sanquineti, M. (2002). Comparison of worst-case errors in linear and neural network approximation. IEEE Trans. on Information Theory, 48, 264-275. 23. Kdrkovb, V. & Sanquineti, M. (2002). Tight bounds on rates of variable-basis approximation via estimates of covering numbers. Research Report ICS-02-865. 24. KdrkovB, V., Savickjr, P. & HlavBEkovb, K. (1998). Representations and rates of approximation of real-valued Boolean functions by neural networks. Neural Networks, 11, 651-659. 25. Kolmogorov, L.N. (1956). Asymptotic characteristics of some completely
Mappings between High-dimensional Representations 45
bounded metric spaces. Dokl. Akad. Nauk, 108,385-389. 26. Kushilewicz, E. & Mansour, Y. (1993). Learning decision trees using the Fourier spectrum. S I A M J . o n Computing, 22, 1331-1348. 27. Milman, V. D., Schechtman, G. (1986). Asymptotic Theory of Finite Dirnensional Normed Spaces. Berlin: Springer, 1986. 28. Makovoz., Y. (1996). Random approximants and neural networks. J . of A p proximation Theory, 8 5 , pp. 98-109. 29. Pinkus, A. (1986). n - W i d t h in Approximation Theory. Berlin: Springer. 30. Pinkus, A. (1998). Approximation theory of the MLP model in neural networks. Acta Numerica, 8 , 277-283. 31. Pisier, G. (1981). Remarques sur un resultat non publiC de B. Maurey. In Seminaire d’AnaZyse Fonctionelle I., n.12. 32. Rudin, W. (1973). Functional Analysis. New York: McGraw-Hill. 33. Sejnowski, T. J. & Rosenberg, C. (1987). Parallel networks that learn t o pronounce English text. Complex Systems 1, 145-168. 34. Sejnowski, T. J. & Yuhas, B. P. (1991). Mappings between high-dimensional representations of acoustic and visual speech signals. In Computation and Cognition (pp.52-68). Philadelphia: Siam. 35. Weaver, H. J. (1983). Applications of Discrete and Continuous Fourier Analysis
This page intentionally left blank
THE STIMULATING ROLE OF FUZZY SET THEORY IN MATHEMATICS AND ITS APPLICATIONS ETIENNE E. KERRE - DIETRICH VAN DER WEKEN Fuzziness and Uncertainty Modelling Research Unit Department of Applied Mathematics and Computer Science Ghent University, Krijgslaan 281 (Building S9), 9000 Gent, Belgium E-mail: etienne.kerre, dietrich.vanderweken@rug. ac. be In order to cope with the incapability of classical yes-or-no mathematics to capture with incomplete information, several mathematical models to represent and to process imprecise and uncertain information were introduced. We mention explicitly : fuzzy set theory, flou set theory, L-fuzzy set theory, rough set theory, intuitionistic fuzzy set theory, twofold fuzzy sets, ... As fuzzy set theory being the most developed one, we will focus on the enrichment of the existing mathematical structures and their domains of applications by the introduction of fuzzy set theory. More precisely we will give some examples of the basic and applied research performed at the Fuzziness & Uncertainty Modelling research unit of Ghent University.
Keywords: f u z z y set theory, fuzzification, fuzzy topology, fuzzy image processing. 1
Introduction
Nowadays the scientific community widely recognizes the need for appropriate mathematical models to represent and to process imprecise and uncertain information. At the same time one agrees about the incapability of classical yes-or-no mathematics to capture with incomplete information. During the past three decennia many new theories have been initiated and developed to model the colourful real world and extend in this way the black-or-white model of classical mathematics. We mention explicitly : fuzzy set theory, flou set theory, L-fuzzy set theory, rough set theory, intuitionistic fuzzy set theory, twofold fuzzy sets, .... Undoubtly fuzzy set theory being the most developed one. Let us note that this model is all but fuzzy : a better name should have been : theory of fuzziness, mathematics of fuzziness, logic of fuzziness. As nowadays science in general and mathematics in particular heavily are based on Cantors set theory, one may expect that the enlargement of the basis by means of fuzzy set theory, will remarkably enrich the exciting mathematical structures and their domains of application. Indeed it is hard to find a domain of mathematics (pure and applied) that has not been infiltrated by fuzzifications. There exists already an extensive literature on fuzzy topology,
47
48
E. E. Kerre and D. van der Weken
fuzzy algebraic structures, fuzzy measure theory, fuzzy relational calculus, fuzzy reliability theory, fuzzy relational databases, fuzzy control, fuzzy decision making. For more than a quarter century basic and applied research has been performed at the Fuzziness & Uncertainty Modelling research unit of the Ghent University, resulting in about 250 scientific papers. In this contribution we want to show the enrichment of mathematics by the introduction of fuzzy set theory. We will consider three stages in the process of fuzzification. The first stage has been mainly developed during the seventies and consists of a moreor-less straightforward fuzzification of the classical mathematical structures. The second stage, mainly developed during the eighties reveals an explosion of the possible generalizations of the classical structures. The current third stage started in the nineties consists on the one hand of modes of standardization, axiomatizations and characterizations and on the other hand of some successful applications of fuzzy set theory. We will provide some examples from our own research group in each of these stages. 2
The stage of straightforward fuzzification
Fuzzy sets have been introduced in 1965 in the most cited seminal paper of L. Zadeh '. Very soon after its introduction fuzzy sets started their infiltration in the domain of fuzzy topology by the paper of C.L. Chang '. A fuzzy topological space (XIT) consists of a universe X together with a subclass T of the fuzzy powerclass F ( X ) of X satisfying : (0.1)0 E
T
and X E
T;
+ O1 n O2 E T; ( 0 . 3 ) (b'j E J ) ( O j E T) + u Oj E T; (0.2)
01
E
T
and
0 2
ET
j€J
where J denotes an arbitrary index set. The elements of T are called 7-open fuzzy sets or simply open fuzzy sets. A fuzzy set A on X is called closed iff coA is open. The class of all closed fuzzy sets in ( X ,T) is denoted as T'. The interior of a fuzzy set A on X, denoted IntA, is defined as the greatest open fuzzy set contained in A , i.e
IntA = u(O10 E
T
and 0 C A } .
The closure of a fuzzy set A on X , denoted clA, is defined as the smallest
The Stimulating Role of Fuzzy Set Theory 49
closed fuzzy set which contains A , i.e.
cZA = n{FIF E
T’
and A C_ F } .
Straightforward verifications show that a fuzzy topology may be characterized in terms of closed fuzzy sets, in terms of interior and in terms of closure as in the crisp case. Problems arise when one tried to obtain a characterization of a fuzzy topology in terms of neighbourhood systems. In it has been shown that straightforward fuzzification of the classical axioms for neighbourhood systems applied to fuzzy singletons didn’t Iead to a characterization of a fuzzy topology. So let p be a fuzzy singleton on a universe X , i.e. a fuzzy set on X whose support is a crisp singleton in X . A fuzzy set A on X is called a neighbourhood of a fuzzy singleton p on X in a fuzzy topological space ( X ,T ) iff (30 E ~ ) ( Cp 0 C_ A ) . The class of all neighbourhoods of p , denoted U p ,satisfies the following fuzzy equivalents of the crisp neighbourhoods :
(N.1) UP # 0; (N.2) A1 E Up and A2 E U p + A1 n A2 E U p ; (N.3) A1 E Up and A1
C A2
* A2 E U p ;
(N.4) (YAl E Up)(3A2E Up)(A2C_ A1 and (Yq C &)(A1 E u,)). But conversely, starting with a system of neighbourhoods for each fuzzy singleton p on X satisfying (N.l)-(N.4) and defining a class T as T
=
(010 E
F(X)and
(Yp C 0)(0E U p ) }
does not necessarily lead to a fuzzy topology on X. The main reason for this deviation from classical topology is that only the implication
(3E
J)(P
G O j ) =+ P c
u
0j
j€J
holds, and no longer the reverse. Another example concerns the fuzzification of the notion of Cartesian product of a finite number of sets. Starting from A1 E F ( X ) and A2 E F(X), the Cartesian product A1 x A2 is defined as: Al
In
A2(27
y) = min(Al(z),A z ( y ) ) .
the following deviations from classical set theory have been outlined:
50
E. E. Kerre and D. v a n der W e k e n
Al x A2 = A2 x Al +? A1 = A2; (A1 x Az)\(AI x A3) $ AI x (A2\A3); A1 x A2 5 A’, x A$ +? A1 C A: and A2 C A;. for Al, A‘,, Az, A$,A3 fuzzy sets on X and \ the fuzzy generalization of the set substraction operation. So in the first stage direct or straightforward fuzzifications of many classical mathematical notions have been introduced and their deviations have been studied.
3
T h e stage of explosion of possible fuzzifications
Due to the introduction of the triangular norms and conorms from the domain of probalistic metric spaces ‘, the intersection and union of fuzzy sets could be extended to a 7-intersection and S-union, as for A E F(X), B E F(X), 7 a triangular norm and S a triangular conorm :
A nT B ( z ) = 7 ( A ( z )B(z)),b!’~: , EX A Us B ( z ) = S ( A ( z )B(z)),b”z , EX. During the eighties we have noticed a deep study of the alternative operations on a logical level (conjunction, disjunction, negation, implication) and on a set-theoretic level (intersection, union, complementation, inclusion). Many researchers among them Bellman, Zadeh, Giertz, Weber, Yager, Dubois, Prade, Klir, Zimmermann, Zysno, Bandler, Kohout have obtained interesting and deep results on these issues. Another characteristic of the second stage lies in the enrichment of the classical structures due to the non-equivalency of the possible generalizations. Let’s provide some examples. For Fl and Fz two crisp subsets of a universe X we have : F1
n Fz
= 0 @ FI
C COFZ,
but for fuzzy sets on X we only have: F1
n Fz
=0
=+ Fl
CCOF~
and hence not the reverse of this implication. It is well-known that many theorems in classical mathematics involve disjoint sets. So one can imagine that the disappearance of the above equivalency leads to different notions in fuzzy set theory. As an example we considered the concept of normality in a fuzzy topological space. A (crisp) topological space (X, T ) is called normal iff
( ~ ( F Fz) I , E T”)(Fi n Fz
=8
* (3(01,02) E T Z ) ( O ln
0 2 =
0 and FI C 0
1
and FZ 2
02),
T h e Stimulating Role of Fuzzy Set Theory 51
or equivalently, stating the famous Urysohn’s lemma, (YO E T ) ( V F ,F E T‘ and F
0)(3V X ) ( F C IntV and clV C 0), where again T’ denotes the class of all closed sets in ( X ,7’). In 1975 B. Hutton defined a normal fuzzy topological space ( X ,T ) as: (VO E r)(V’F,F E r’ and F
C 0)(3V E F ( X ) ) ( F
IntV and clV
C 0),
and hence a straightforward fuzzification of the Urysohn’s form of normality. We wondered why the usual form of crisp normality was not been taken for fuzzification. The answer lies in the choice of the definition of disjointness. So in we defined: (X,r ) is normal
’
0
(VJ(Fi,F2) E T ’ ~ ) ( FCI cop2 + ( 3 ( 0 1 , 0 2 )E T ~ ) ( CO coo2 ~ and F1 C ( X ,T ) is weakly normal
0 1
and F2
C02))
Q
( V ( F l ,F ~ E) T’W~ n F~ # 0 + ( ~ ( O I0 ,2 ) E r2)(OI C coo2 and
F1 C 0 1 and F 2 C 0 2 ) ) . We also have shown that our definition of normality completely coincides with the one of Hutton and that weakly normality is a weaker concept, i.e. the fuzzy Sierpinski space is weakly normal but not normal. In we introduced an even stronger concept of normality: ( X ,T ) is completely normal
Q
(V(A1,Az) E F ( X ) 2 ) ( ( A 1C co(clA2) and A2 C co(clA1) ( 3 ( 0 1 , 0 2 )E r2)(A1C 0 1 and A2 C 0 2 and 01 C ~ 0 0 2 ) ) .
We however found that the well-known Tietze characterization theorem no longer holds in fuzzy set theory, i.e., only the following implication holds: ( X ,r ) is completely normal + every fuzzy subspace of ( X ,T ) is normal. A second example of the huge amount of possible fuzzifications concerns the concept of neighbourhood in a fuzzy topological space. Here the basic notions are the fuzzification of the notions ”point” and ”membership relation”. Some authors have defined the concept neighbourhood for a crisp point in the underlying universe while authors used ”fuzzy points” and ”fuzzy singletons”. A fuzzy singleton in a universe X , denoted x, where 6 ~ ] 0 , 1and ] x E X is defined as: x, : x 4 [0,1] X
W
E
y
H
0,ifyfx.
E. E. Kerre and D. van der Weken
52
while a fuzzy point, also denoted x , , where E E]O,l[ and x E X is defined in the same way. The different membership relations are defined for A E F ( X ) and: - for fuzzy singletons: x , C A H E 5 A(%) x,qA H ~ ( z C , COA)H
+
A ( x ) E > 1. The first relation is Zadeh’s inclusion relation g , while the second one is P u and Liu’s quasi-coincidence relation q .
- for fuzzy points:
x, 5A H
E
< A(%).
Note that fuzzy singletons and fuzzy points reveal a complementary attitude towards Zadeh’s fuzzy set theoretic operations. Indeed, let (Aj)jEJ be a family of fuzzy sets on X , s a fuzzy singleton in X and p a fuzzy point in X . Then we obtain 0
for the Zadeh intersection:
but the converse only holds for finite J .
but the converse only holds for finite J . for the Zadeh union: (3j E
J)(s
Aj) + s
C
UAj, j€J
but the converse only for finite J .
The Stimulating Role of Fuzzy Set Theory 53
Based on these notions several neighbourhood concepts have been introduced. Suppose ( X ,T ) being a fuzzy topological space, IC E X , s a fuzzy singleton in X and p a fuzzy point in x. Then we have: A is a Ludescher lo neighbourhood of x ( 3 0 E T ) ( I CE supp 0 and 0 E A ) .
A is a Kerre3 neighbourhood of s H (30 E r ) ( s C 0 C A). l1 neighbourhood of x 0 and 0 C A and O(x) = A ( x ) ) .
A is a Warren H ( 3 0 E T ) ( I CE supp
A is a Pu l2 neighbourhood of s H (30 E T)(S q 0 and 0 C A ) . A is a Mashhour l 3 neighbourhood of p (30 E ~ ) ( p s and O 0 C A). The resulting neighbourhood systems will be denoted as: C, ( T ) , Ic, (T), wz(~), Ps(7)and M p ( 7 ) . In a series of papers we could prove the following results concerning the characterization of a fuzzy topology by means of the different neighbourhood systems. (1) All neighbourhood systems, except Warren’s, satisfy the purely formal translated properties of a classical neighbourhood system. See section 2 as illustrated for the Kerre neighbourhood system. (2) A Ludescher neighbourhood system defines a fuzzy topology which is however not necessarily unique, i.e. different fuzzy topologies can lead t o the same Ludescher neighbourhood system and hence Ludescher’s definition gives no characterization. (3) A Kerre neighbourhood system defines no fuzzy topology but only a base for a fuzzy topology. Hence Kerre’s definition gives no characterization, contradicting the conjecture made by P u and Liu in 12. (4) A Pu and Liu neighbourhood system defines a unique fuzzy topology and
hence it provided a characterization. ( 5 ) A Mashhour-Ghanim-Kerre neighbourhood system defines a unique fuzzy topology and hence provided a characterization.
Due to a lattice-theoretic study of the different approaches to the concept of a neighbourhood we could introduce a skala of fuzzy topological spaces :
54 E. E. K e r r e and D. v a n d e r W e k e n
surjective spaces, conditionally closed Kerre spaces, conditionally closed P u spaces, conditionally closed Mashhour spaces, fuzzy co-countable spaces, fuzzy Sierpinski spaces and the 2-space. Moreover we could partly fill up the gap between Chang fuzzy topological spaces and Lowen spaces. For more details we refer to l6 and *. A third example concerns the fuzzification of a real number and the ordertheoretic structure of the real numbers. A walk through the fuzzy literature reveals the existence of many different definitions for this fundamental notion. We mention explicitly : the original definition of Mizumoto and Tanaka imposing a convexity condition, the different concepts introduced by Dubois and Prade using a monotonicity property and several forms of continuity and the approach of Rodabaugh related to probability distributions. The diversity of concepts is dangerous since the corresponding calculus of fuzzy quantities highly depends on the definition. In l8 we gave a theoretic consistent description of fuzzy numbers and their properties and we made an attempt to link the different definitions. As a final example of the extension of classical mathematics by fuzzy mathematics we would like to mention the fuzzy relational calculus. Relations are considered as one of the basic concepts in science and in particular in mathematics. Due to the pioneering work of Bandler and Kohout in the eighties, the machinery of relational calculus has been substantially extended, theoretically as well as practically in databases, information retrieval and preference modelling in decision making. For an extensive overview of fuzzy relational calculus and its applications we refer t o l9 or '. 4
4.1
The current stage Standardization, axiomatization and L-fuzzification
During the nineties up to now a major part of the ongoing research has been dedicated to more fundamental issues such as standardization, axiomatization and L-fuzzification. Problems of standardization concern the motivated choice of a standard for basic notions: fuzzy point versus fuzzy singleton as the most primitive building-stone; which concept of neighbourhood should be choosen as standard; what is the most suitable t-norm for modelling intersection of fuzzy sets; which definition should be choosen for the fuzzification of a subgroup and other basic algebraic structures. As a result of this process of standardization one should clear up the papers entitled "fuzzy ... redefined". Once a standard has been agreed, the use of deviations from the standard should be stated explicitly and thorougly motivated.
The Stimulating Role of Fuzzy Set Theory 55
A second important topic of research in the third stage concerns axiomatization in order to reach a consensus with respect t o the desirable properties of typical fuzzy concepts such as: fuzzy implication, measures of fuzziness, fuzzy measures, fuzzy preference relations, fuzzy ranking methods, fuzzy similarity relations, defuzzification methods. A third characteristic of the fuzzy research in the nineties is the so-called L-fuzzification, where L denotes a complete lattice. In the original fuzzy set theory the membership degrees are taken from the unit interval [0,1] and hence no incomparability could be taken into account. In order t o represent incomparable elements, states, systems, ..., Goguen introduced in 1967 the extension t o L-fuzzy sets. Now a huge amount of research results exists on L-fuzzy groups, L-fuzzy topology, L-fuzzy modifiers. Let’s give some concrete examples of these important directions of the latest fuzzy research. The first example stews from fuzzy topology. Let f be a mapping between two crisp topological spaces ( X I ,T I )and ( X 2 , T z ) . Then the following equivalent formulations for the continuity of f are well-known: f is continuous
(YO2 E T 2 ) W 1 ( 0 2 ) E TI) (VFZ E Td)(f-l(Fz) E Ti) @ P A 1 E R X l ) ) ( f ( C h ( A l ) ) c_ clz(f(A1)) e (VAz E P(X2))(f-1(intz(A2)) intl(f-l(A2)) @
w
c
It has been shown that not all of these equivalencies are kept in the framework of fuzzy topology. As a consequence a huge number of continuity concepts have been introduced in the eighties : fuzzy continuous, fuzzy weak continuous, fuzzy almost continuous, fuzzy semi continuous, fuzzy weak semi continuous, fuzzy 8-semi continuous, fuzzy almost semi continuous, fuzzy almost semi continuous, fuzzy S-continuous, fuzzy semi irresolute continuous, fuzzy strongly irresolute continuous, fuzzy irresolute continuous, fuzzy &continuous, fuzzy strong @-continuous,fuzzy almost strong 8-continuous, fuzzy super continuous, fuzzy weak 8-continuous, fuzzy weak precontinuous, fuzzy semi strongly 8-continuous, fuzzy weak X-continuous, fuzzy (8, S)-continuous, fuzzy quasi irresolute continuous, fuzzy semi weak continuous. Due to the introduction of the notions of an operation, we have been able 2o to unify all these concepts, i.e., to propose a general form of fuzzy continuity, such that all the foregoing concepts are special instances of this general form. A second example concerns axiomatization of fuzzy implication operators. In 21 Smets and Magrez introduced the following axioms for a fuzzy implication operator Z on the unit interval. Let 1 be a [0, 112- [0, I] mapping and
E. E. Xerre and D. van der Weken
56
(z, y, 2) E
[o, 113:
(A.l) Axiom of contraposition : Z(x, y) = Z(1 - y, 1 - z); (A.2) Exchange principle: Z(z,z(Y,.))
= W(z,y),z);
(A.3) Axiom of hybrid monotonicity: Z(., z) is decreasing and Z(z, .) is increasing;
(A.4) Boundary conditions: z 5 y =+ Z(z, y) = 1; (A.5) Neutrality principle: Z(1,z) = s; (A.6) Axiom of continuity: Z is continuous. In 22 we have tested 19 widely used fuzzy implication operators w.r.t. these axioms and we have built a fuzzy set of good fuzzy implication operators. Other examples of the stimulating role of fuzzy set theory in the development of pure and applied mathematics are:
- a critical comparison of the fuzzy model and other recently developed uncertainty models such as : rough sets, twofold fuzzy sets, flou sets, intuitionistic fuzzy sets 23;
- an overview of fuzzy quantifiers - a unified method
24J5;
for ranking fuzzy quantities
26,27;
- axiomatization and classification of the different methods for defuzzification 4.2
28.
Applications of fuzzy set theory
In this section we will focus on possible applications of fuzzy set theory, more precisely fuzzy techniques in image processing. We will illustrate how fuzzy techniques are used in establishing measures for image quality evaluation and in constructing fuzzy filters for image noise reduction. An important problem in image processing constitutes the comparison of images: if different algorithms are applied to an image, we need an objective measure to compare the different output images. It is well-known that
The Stimulating Role of f i z z y Set Theory
57
classical measures, such as the MSE (mean square error), do not always give convincing results. Since gray-scale images can be identified with fuzzy sets, it is interesting to investigate whether similarity measures, i.e. measures that are developed to express the degree of similarity between fuzzy sets, can also be applied in image processing. In the literature a lot of measures that express the similarity between two fuzzy sets can be found. In most cases, a similarity measure is formally defined as a fuzzy binary relation in F(X), i.e. a F ( X ) x F ( X ) + [O, 11 mapping that is reflexive, symmetric and min-transitive. However, not every measure in the literature satisfies this definition. Therefore, we give a larger interpretation to the notion of a similarity measure: a similarity measure is any measure to compare two fuzzy sets. We investigated 33 similarity measures 29 w.r.t. their applicability for image quality evaluation. In order to do this, we evaluated the similarity measures w.r.t. a list of relevant properties. For example: a similarity measure needs to be reflexive and symmetric. Furhtermore, a good similarity measure should not be affected too much due to noise, and should be decreasing with respect to an increasing noise-percentage. From a total of the 33 similarity measures, only six similarity measures satisfied the list of relevant properties. A complete overview of the appropriate similarity measures can be found in 30. Let’s give the following two examples:
where A, B E F ( X ) ,with X = {(z, y)l0 of image points.
5 z 5 M , 0 5 1~ 5 N } a discrete set
Another illustration of the application of fuzzy techniques in image processing is the construction of fuzzy filters for image noise reduction. Already several fuzzy filters for noise reduction have been developed, e.g. the well-known FIRE-filter from Russo the weighted fuzzy mean filter from Lee 3 3 , and the iterative fuzzy control based filter from Farbiz and Menhaj 34. However, most techniques are not specifically designed for gaussian(-like) noise or do not show convincing results when applied to this type of noise. The GOA filter 35 (named after the research project it was developed in) is, in contrast to most other fuzzy filters, specifically designed for the reduction 31y32,
58
E. E. K e r r e and D. v a n d e r W e k e n
of gaussian-like noise. The general idea is to average a pixel using other pixels from its neighbourhood, but simultaneously t o take care of important image structures such as edges. To accomplish this goal, two important features are presented. First, to distinguish between local variations due to noise and due to image structure the filter estimates a fuzzy gradient for each direction; second, the membership functions are adapted accordingly to the noise level t o perform fuzzy smoothing. The filter is applied iteratively.
Figure 1. Pixels involved in the calculation of
vEw(i,j)
First, a value og(i,j) that expresses the degree in which the gradient in the direction D is small is derived. For each direction D (see Fig. 1 for an example), this is done by using the classical gradient values in the processed pixel and the two neighbouring pixels perpendicular to direction D (gradient values denoted by ~ ~ ( i , v j ~ ) ,( i l , j land ) v ~ ( i z , j z ) and ) , the following fuzzy rule: IF ( vo(i,j)is s m a l l AND v ~ ( i l , jisl )s m a l l ) OR ( ~ ~ ( i is, js m) a l l AND v ~ ( i 2 , j ais) small ) OR ( v ~ ( i 1 , jisl ) s m a l l AND o ~ ( i z , j 2is) s m a l l ) THEN vg(i,j)is s m a l l , where small is a triangular fuzzy number. The membership function p s m of this fuzzy set is adapted in each iteration] depending upon the residual amount of noise. The principle behind this is similar to the one behind the EIFCF filter: a compression of the fuzzy set s m a l l keeps the filtering capacity of the filter preserved. The further construction of the filter is based on the observation that a small fuzzy gradient most likely is caused by noise, while a large fuzzy gradient most likely is caused by an edge in the image (this is due t o the fact that the fuzzy gradient is derived from 3 classical gradient values, perpendicular t o the considered direction). Consequently, for each direction the following fuzzy rules that take this observation into account are applied:
The Stimulating Role of Fuzzy Set Theory 59
~ g ( i , jis)small AND ~ ~ ( i is, jp o) s i t i v e THEN y A ( i , j ) is p o s i t i v e , IF vg(i,j)is small AND v ~ ( i ,isjn)e g a t i v e THEN y i ( i , j ) is n e g a t i v e ,
IF
where p o s i t i v e and n e g a t i v e are linear fuzzy sets with membership functions ppOs and pneg. The truth values y$(i,j) and y;(i,j) of both rules are calculated for each direction, e.g. yi(i,j) = m i n ( ~ ~ m ( o ~ ( i , j ) ) , ~ L p , s ( ~and ~ ( the i , j )correction )), term is then given by: Y ( i 7 j ) = 255.
c
(YA(i,j) - Y&,j)),
DEdir
with dir the set of all directions. To illustrate the performance of the GOA filter, we have applied the filter to a noisy “cameraman” image. For comparison, we have also applied the classical Wiener filter, and the weighted fuzzy mean filter. The numerical results are displayed in Table 1. Besides the MSE-values, we have also calculated the values of the similarity measures S1 ( r = 1) and SZ.
Table 1. Numerical results corresponding t o the images in Fig. 2.
The results not only confirm the good performance of the new filter, but also illustrate that similarity measures (in particular the used measures S1 and ,572) are a better tool for image comparison. Our new filter performs best w.r.t. both the MSE and the similarity measures. Regarding the WFM filter: performs worst (MSE much higher, similarity measure lower). Regarding the Wiener filter: performs bad w.r.t. MSE, but shows an improvement w.r.t. the similarity measures S1 and S,. The latter is in accordance with the visual result, and illustrates that the similarity measures better reflect the visual observations than the MSE measure. The previously discussed applications are only two of many successful applications of fuzzy set theory in the area of image processing. Other possible applications are: fuzzy image enhancement, fuzzy edge detection, fuzzy image segmentation, fuzzy processing of color images, and applications in medical imaging and robot vision. We refer to 36 for an up-to-date and state-of-the-art coverage of diverse aspects related to fuzzy techniques in image processing.
60 E. E. Kerre and D. van der W e k e n
Figure 2. Top row: from left to right: original “cameraman” image and “cameraman” image with gaussian noise (u = 5.7); bottom row: from left to right: result of the GOA filter, result of the classical Wiener filter, result of the weighted fuzzy mean filter.
References
1. L.A. Zadeh, Fuzzy sets, in : Information and Control 8 (1965), pp. 338353. 2. C.L. Chang, Fuzzy Topological Spaces, in: J. Math. Anal. Appl. 24 (1968), pp. 182-192.
The Stimulating Role of f i z z y Set Theory 61
3. E.E. Kerre, Fuzzy topologizing with preassigned operations, in: Intermational Congress for Mathematicians (Helsinki, 1978), pp. 61-62. 4. E.E. Kerre, Introduction to the Basic Principles of Fuzzy Set Theory and some of its Applications, second revised edition, Communication and Cognition, Gent, (1993). 5. B. Schweizer, A. Sklar, Probabilistic Metric Spaces, Elsevier Science Publishing Company, New York, (1983). 6. B. Hutton, Normality in fuzzy topological spaces, in: J . Math. Anal. Appl. 50 (1975), pp. 74-79. 7. E.E. Kerre, Characterization of normality in fuzzy topological spaces, in: Simon Stevin 53 (1979), pp. 239-248. 8. E.E. Kerre, Fuzzy Sierpinski space and its generalizations, in: J. Math. Anal. Appl. 74 (1980), pp. 318-324. 9. E.E. Kerre, P. Ottoy, Fuzzy subspace of a fuzzy topological space, in: S. Ovchinnikov, Ed. Proceedings NAFIPS 88 (San Francisco, 1988), pp. 141-146. 10. H. Ludescher, E. Roventa, Sur les topologies floues definies I’aide des voisinages, in: C.R. Acad. Sci. Paris 283 (1976), pp. 575-577. 11. R.H. Warren, Fuzzy topologies characterized by neighbourhood systems, Rocky Mountain J. Math. 9 (1979), pp. 761-764. 12. Fuzzy Topology I, in: J. Math. Anal. Appl. 76 (1980), pp. 571-599. 13. M. Ghanim, E.E. Kerre, A. Mashhour, Separation axioms, subspaces and sums in fuzzy topology, in: J. Math. Anal. Appl. 102 (1984), pp. 189202. 14. E.E. Kerre, P. Ottoy, On the different notions of neighbourhood systems in Chang-Goguen fuzzy topological spaces, in: Simon Stevin 61 (1987), pp. 131-146. 15. E.E. Kerre, P. Ottoy, On the characterization of a Chang fuzzy topology by means of a Kerre neighbourhood system, in: J.L. Chameau, J . Yao, Eds., Proceedings of NAFIPS 87 (Purdue University Press, Purdue 1987), pp. 302-307. 16. E.E. Kerre, P. Ottoy, Lattice properties of neighbourhood systems in Chang fuzzy topological spaces, in: Fuzzy Sets and Systems 30 (1989), pp. 205-213. 17. E.E. Kerre, P. Ottoy, A comparison of the different notions of neighbourhood systems for Chang topologies, in: J. Kacprzyck, A. Straszak, Eds., Proceedings of the First Joint IFSA-EG EURO- WG Workshop on Progress in Fuzzy Sets in Europe, Prace ibs pan, Warsaw, vol. 169 (1989), pp. 241-251. 18. E.E. Kerre, A. Van Schooten, A deeper look on fuzzy numbers from a the-
62
E. E. Kerre and D. van der Weken
19. 20. 21.
22.
23. 24. 25. 26. 27. 28. 29.
30.
31.
32.
33. 34.
oretical as well as a practical point of view, in: M. Gupta, T . Yawakawa, Eds., Fuzzy Logic in Knowledge-Based Systems, Decision and Control, North-Holland, Amsterdam, (1988), pp. 173-196. B. De Baets, E.E. Kerre, Fuzzy relations and applications, in: Advances in Electronics and Electron Physics 89 (1994), pp. 255-324. A. Kandil, E.E. Kerre, A. Nouh, Operations and mappings on fuzzy topological spaces, in: Annales de la Socie'te' Scientzjique de Bruxelles, T.105, 4 (1991), pp. 167-188. Ph. Smets, P. Magrez, Implication in fuzzy logic, in: Internat. J. App. Reasoning 1 (1987), pp. 327-347. Ruan Da, E.E. Kerre, Fuzzy implication operators and generalized fuzzy method of cases, in: Fuzzy Sets and Systems 54 (1993), pp. 23-37. E.E. Kerre, A First View on the Alternatives of Fuzzy Set Theory, in : B. Reusch, K.-H. Temme, Eds. Computational Intelligence in Theory and Practice, Physica Verlag, Heidelberg (2001), pp. 55-72. Y. Liu, E.E. Kerre, An overview of fuzzy quantifiers, Part I : Interpretations, in: Fuzzy Sets and Systems 95 (1998), pp. 1-22. Y. Liu, E.E. Kerre, An overview of fuzzy quantifiers, Part I1 : Reasoning and applications, in: Fuzzy Sets and Systems 95 (1998), pp. 135-146. X. Wang, E.E. Kerre, Reasonable properties for the ordering of fuzzy quantities, Part I, in: Fuzzy Sets a n d Systems 118 (2001), pp. 375-386. X. Wang, E.E. Kerre, Reasonable properties for the ordering of fuzzy quantities, Part 11, in: Fuzzy Sets and Systems 118 (2001) pp. 387-406. W. Van Leekwijck, E.E. Kerre, Defuzzification: criteria and classification, in: Fuzzy Sets and Systems 108 (1999), pp. 159-178. D. Van der Weken, M. Nachtegael, E.E. Kerre, The applicability of similarity measures in image processing, in: Proceedings of the 8th International Conference on Intelligent Systems and Computer Science, Moskou, december 2000. D. Van der Weken, M. Nachtegael, E.E. Kerre, An overview of similarity measures for images, Accepted for the 2002 IEEE International Conference on Acoustics, Speech, and Signal Processing, May 13-17, 2002, Orlando, USA. F. RUSSO,G. Ramponi, A fuzzy filter for images corrupted by impulse noise, in: IEEE Signal Processing Letters 3 (1996), pp. 168-170. F. RUSSO, Fire Operators for image processing, in: Fuzzy Sets and Systems 109 (1999), pp. 265-275. K. Lee, Chang-Shing, Yau-Hwang, P.T. Yu, Weighted fuzzy mean filters for image processing, in: Fuzzy Sets and Systems 89 (1997), pp. 157-180. F. Farbiz, M.B. Menhaj, A fuzzy logic control based approach for image
The Stimulating Role of Fuzzy Set Theory 63
filtering, in: E.E. Kerre, M. Nachtegael, Eds., Fuzzy Techniques in Image Processing, Springer Verlag (2000), pp. 194-221. 35. D. Van De Ville, M. Nachtegael, D. Van der Weken, E.E. Kerre, W. Philips, I. Lemahieu, Noise reduction by fuzzy image filtering, in: IEEE Transactions on Fuzzy Systems, submitted. 36. E.E. Kerre, M. Nachtegael, Eds., Fuzzy Techniques in Image Processing, Springer Verlag (2000).
This page intentionally left blank
K-ORDER ADDITIVE FUZZY MEASURES: A NEW TOOL FOR INTELLIGENT COMPUTING RADKO MESIAR Department of Mathematics, Fac. of Civil Engineering, Slovak University of Technology, RadlinskGho 11, 819 68 Bratislava, Slovakia e-mail:
[email protected],stuba.sk Several classes of fuzzy measures are recalled and characterized. A new class of Ic-order additive fuzzy measures offering new perspectives for intelligent computing is discussed, including some construction and identification methods. Several examples are given.
Keywords 1
: Additivity,
belief function, Choquet integral, fuzzy measure.
Introduction
Fuzzy measures (monotone set functions vanishing in the empty set, premeasures) extend the concept of additive set functions (measures, probabilities), see, e.g., For a recent overview of the topic we recommend 1 4 . Recall that for a fixed measurable space (X, A),the class P of all probabilities on (XIA) is a convex set. Dealing with the case when X = {XI,. . . , 2,) is a finite space and A = 2x, P is a simplex with vertices h i z i ) (Dirac measures). Moreover, P is closed under duality of set functions since any probability P is self-dual. However, P is not closed under many other aggregations, e.g., under min, Prod, max, etc. The smallest class of set functions closed under any aggregation in the spirit of 15,? is just the class of all fuzzy measures. The smallest convex class containing P and closed under min is the class of all belief functions (the same holds when Prod is taken for the aggregation). Again, B is a simplex with vertices BA (generalized Dirac measure), 31135726,?.
dA
= min ( d i z i ) I xi E A ) =
dlzi}. xi € A
Note that generalized Dirac measures are known in the game theory as unamity games 7&13 and they can be characterized by the set function 6A(B)
=
if A c B , 0 otherwise.
{1
Observe that similarly we can discuss the fuzzy measures linked to some pseudo-addition @ 3 2 , e.g., linked to max operator V (possibility measures).
65
66
R. Mesiar
2
k-order additive belief functions
Dempster-Shafer theory was successfully applied in several important areas linked to the intelligent computing, especially in multicriteria decision making However, the identification of a relevant belief function (fuzzy measure) fitting the modeled situation is a problem with high complexity, practically inaccessible in reality. Hence, a specific subclass of belief functions (fuzzy measures) , with acceptable complexity but sufficiently large applicability was proposed recently by Grabisch 1 2 . Grabisch’s concept of k-order additivity can be easily formulated by means of generalized Dirac functions. The class 131, of all k-order additive belief functions on X = (x1,. . . , xn} with k < n, is just the simplex with vertices b ~cardA , 5 k. 353?.
We have shown recently that equivalently, m E Dk if and only if m(A) = P(Ak) for some probability measure P on X k ,see, e.g., Recall also that then 20321123.
where fk(xtl , . . . , x i k ) = min ( f ( x i l ) ,. . . , f(qk)). Similarly, k-order additive fuzzy measures can be introduced 20,21,23. In the case k = 1, the standard additivity is recovered, and then we have two equivalent characterizations of 1-additive belief functions (fuzzy measures), namely (i) VA, B with A n B
=0 :
m(A U B ) = m(A)
+ m(B),
(additivity)
(ii) V A , B : m ( A U B ) + m ( A n B ) = m ( A ) + m ( B ) , (valuation property) For a general k we have the next two equivalent characterizations
21134:
(i’) V A 1 , . . . ,Ak+l pairwise disjoint :
(k-additivity) (ii’) VA1, . . . ,A k + l denote Bi =
Ai
\ U Aj, j#i
i = l,...,k
+ 1, and Bo
=
K - o r d e r Additive Fuzzy M e a s u r e s kfl
U Ai \
i=l
67
‘$ Bi: i=l
(I(odd
lJl even
j €J
(k-valuation property).
3
Construction a n d identification of 2-order additive belief functions
To construct a 2-order additive belief function m on (X,A), we need first
to construct a probability P on (X,A)’. However, any such probability is determined by the marginal probabilities PI and P 2 on (X,A) by means of some copula C 2 5 . If PI = P 2 are uniform and C is the product copula then the corresponding m = Pf is a symmetric belief function,
m ( A )=
card A
2
(7 I
and the relevant Choquet integral is the OWA operator induced by quantifier q(x) = x2,see 3 6 . To identify a 2-order additive belief function m we have to determine the weights wi corresponding to b{zil and wi,j linked to 6{2,,z3}1 that is, weights constrained by the non-negativity and the sum equal to 1. Because of (1) for any input function f : X -+ R, the Choquet integral output (that is, the global evaluation of f ) is given by
(c> -
/
c n
f dm =
i=l
wif(xi)
+
c
wi,j min
( f ( z i > ,f(xj>)
i<j
where the weights are constrained by the normalization condition: i
i<j
Now, having a training data, we estimate the weights by means of the least square method, leading to a quadratic programming problem, see also 24.
As an illustration we present an example for n = 2, that is, with two inputs x and y only. The corresponding Choquet integral based output will be denoted by z . The observed data are given in Table 1.
68
R. Mesiar
2 0 3
5 5 0
9 25 9 47
3 2 1
6 15 3 26
Suppose we want to find the best fitting probability measure describing observed data, that is, we look for p E [0,1] such that z=pz+(l-p)y
Following the least squares method, p should minimize the value
c 4
LP(P) =
c 4
(Zi - pzz
- (1 - p)y,)2 =
i=l
((Zi
2
- yz) - p ( z i - yi)) ,
i=l
that is, L$(p) = 0 yielding
26
-
1363
-
29
Note that then Lp ( E ) - T T - A. Now, let us model our data by means of a 2-order additive believe function m, that is, we need to determine the weights w1, w2, 1 - w1 - w2 = w1,2 so that
z = w1z
+ w2y + (I - w1
-
w2)
min(z,y).
Now we have t o optimize the value 4
L,(w~, w2) =
C (zi -
wlxi
- w2yi - (1 - w1 - w2) min(zi, yi))2
i= 1
c 4
=
((zi- min(zi, yi)) - w1 max(0, zi - yi) - w2 max(yi - xi,0))2
i=l
We have to solve the system of equations
dLm -= 0, awl
dLm = 0. aw2
K-order Additive Fuzzy Measures
69
Due t o the fact that max(0,xi - yi) max(yi - xi, 0) = 0 for all i = 1 , . . . , 4 , the relevant solution to the system is, see Table 2, 4
C (zi- min(zi, yi)) max(0, xi - yi)
w1 =
i= 1
c (max(o,xi 4
i=l
-
1 3
-_ -
and
Table 2 Note that an analytical solution for w1,wq and W I , ~= 1 - w1 - wz need not fulfill the non-negativity requirement, in general. Then the quadratic programming should be applied. However, in our case the weights 1 15 31 w1 = 3 ' w 2 = - and w1,2 = 114 38 fulfill all requirements and hence determine the optimal 2-order additive belief function m. Note that now the sum of square differences is efficiently smaller, 114
3
= 0.079
< 0.617 =
Further recall that the best approximation of a belief function m by means of a probability measure P in the sense C ( m ( A )- P(A))' = min, is called a pignistic probability and denoted by P*. Due t o results in concerning the Mobius transform, it can be shown that if m is a 2-order additive belief function with weights wi and wi,j, for i , j E ( 1 , . . . , n } , i < j , then P" = ( P l , . . . , P n ) with pi = wi
+ -21 ( g w k , i +
2
j=i+l
Wij)
70
R. Mesiar
In the case discussed above, we have n = 2 and for m optimizing our training data given in Table 1, we get 121 107 -15+ - 1 -31 = P I = -1 + -1- 31 - - p2 3 2'114 228' 38 2'114 228' that is ,
s)
As we have already shown, the best probability measure P fitting our training data is given by P = (%, , verifying the fact that the optimal belief function is not linked to the optimal probability measure. 4
Conclusions
The concept of k-order additivity of fuzzy measures allows to model the interaction which can never be caught by an additive set function, but still several additivity advantages are preserved. Therefore several interesting applications in the framework of uncertainty modeling are expected. The included example has shown 87% improvement of the sum of square differences when applying 2-order additive belief function instead of a probability measure, which supports our expectations.
Acknowledgement The support of the grants VEGA 1/8331/01 and 1/7146/20 is kindly announced. References 1. Benvenuti, P. and Mesiar, R.: Integrals with respect t o a general fuzzy measure. In: Fuzzy Measures and Integrals. Theory and Applications, M. Grabisch, T. Murofushi, M. Sugeno, eds., Physica-Verlag, Heidelberg, 2000, pp. 205-232. 2. Calvo T., Kolesarova A., Komornikova M. and Mesiar R.: A Review of Aggregation Operators. Univ. of AlcalA, AlcalA de Henares, Spain, 2001. 3. Chateauneuf, A. and Jaffray, J.Y.: Some characterizations of lower probabilities and other monotone capacities through the use of Mobius inversion. Mathematical Social Sciences 17 (1989) 263-283.
K-order Additive Fuzzy Measures
71
4. Choquet, G.: Theory of capacities. Ann. Inst. Fourier 5 (1953/54) 131-295. 5. De Finetti, B.: Sull’impostazione assiomatica del calcolo delle probabilit8. Annali Uniu. Trieste 19 (1949) 3-55. 6. Dempster, A.P.: Upper and lower probabilities induced by a multivalued mapping. Annals of Mathematical Statistics 38 (1967) 325-339. 7. Denneberg, D.: Non-additive Measure and Integral, Kluwer Academic Publishers, Dordrecht, 1994. 8. Denneberg, D.: Non-additive measure and integral, basic concepts and their role for applications. In: Fuzzy Measures and Integrals. Theory and Applications, M. Grabisch, T. Murofushi, M. Sugeno, eds., PhysicaVerlag, Heidelberg, 2000, pp. 42-69. 9. Dubois, D. and Prade, H.: Possibility Theory, Plenum Press, New York, 1988. 10. Grabisch M.: Fuzzy integral in multicriteria decision making. Fuzzy Sets and Systems 69 (1995) 279-298. 11. Grabisch, M.: k-order additive fuzzy measures. Proceedings IPMU’96, Granada, 1996, pp. 1345-1350. 12. Grabisch, M.: k-order additive discrete fuzzy measures and their representation. Fuzzy Sets and Systems 92 (1997) 167-189. 13. Grabisch, M.: The interaction and Mobius representation of fuzzy measures on finite spaces, k-additive measures. In: Fuzzy Measures and Integrals. Theory and Applications, M. Grabisch, T. Murofushi, M. Sugeno, eds., Physica-Verlag, 2000, pp. 70-93. 14. M. Grabisch, T . Murofushi, M. Sugeno, eds.: Fuzzy Measures and Integrals. Theory and Applications, Physica-Verlag, 2000. 15. Klir, G.J. and Folger, T.: Fuzzy Sets, Uncertainty and Information. Prentice Hall, Englewood Cliffs, 1988. 16. Koleskov6, A.: Mobius fitting aggregation operators. Kybernetika, submitted. 17. Marichal, J.L.: Aggregations operators for multicriteria decision aid, PhD. thesis, University of Liege, 1998. 18. Marinacci, M.: Decomposition and representation of coalition games. Mathematics of Operations Research 21 (1996) 1000-1015. 19. Mesiar, R.: k-order Pan discrete fuzzy measures. Proceedings IFSA ’97, Prague, 1997, pp. 488-490. 20. Mesiar, R.: k-order additive measures. Int. Jour. of Uncertainty, Fuzziness and Knowledge-Based Systems 6 (1999) 561-568. 21. Mesiar, R.: Three alternative definitions of k-order additive fuzzy measures. Busefal 83 (2000) 57-62.
72
R. M e s i a ~
22. Mesiar, R.: Maxitive and k-order maxitive measures. Proceedings IFA C, Prague, 2001. 23. Mesiar R.: Generalized Mobius transform and k-order additive fuzzy measures. Int. J. Gen. Syst, submitted. 24. Miranda P. and Grabisch M.: Optimization issues for fuzzy measures. Proceedings IPMU’98, Paris,1998, pp. 1204-121 1. 25. Nelsen R. B.: An Introduction to Copulas. Lecture Notes in Statistic 139, Springer Verlag, 1999. 26. Pap, E.: Null-additive Set Functions, Kluwer, Dordrecht, 1995. 27. Rota, G.C.: On the foundations of combinatorial theory I. Theory of Mobius functions. Zeitschrifi fur Wahrscheinlichkeitstheorie und verwandte Gebiete 2 (1964) 340-368. 28. Shafer, G.: A Mathematical Theory of Evidence. Princeton University Press, Princeton, 1976. 29. Shafer, G.: Allocations of probability. Ann. Probab. 7 (1979) 827-839. 30. Shilkret, N.: Maxitive measures and integration. Indag. Math. 33 (1971) 109-116. 31. Sugeno, M. Theory of Fuzzy Integrals and Applications, PhD. thesis, Tokyo Inst. of Technology, 1974. 32. Sugeno, M. and Murofushi, T.: Pseudo-additive measures and integrals. J. Math. Anal. Apll. 122 (1987) 197-222. 33. SipoS, J.: Non-linear integrals. Math. Slovaca 29 (1979) 257-270. 34. ValBSkovB, L.: A note to the 2-order additivity. Proc. MAGIA’ 2001, KoCovce 2001, pp. 53-55. 35. Wang, Z. and Klir, G.J.: Fuzzy Measure Theory, Plenum Press, New York, 1992. 36. Yager R.R.: On ordered weighted averaging operators in multicriteria decisionmaking. IEEE Trans. Syst., Man Cybern. 18 (1988) 183-190. 37. Zadeh, L.A.: Fuzzy sets as a basis for the theory of possibility. Fuzzy Sets and Systems 1 (1978) 3-28.
ON-LINE ADAPTATION OF RECURRENT RADIAL BASIS FUNCTION NETWORKS USING THE EXTENDED KALMAN FILTER BRANIMIR TODOROVIC’*, MIOMIR STANKOVIC’, CLAUDIO MORAGA~** I Faculty of Occupational Safety, University of Nii, 18000 NiS, Yugoslavia E-mail:
[email protected] Department of Artificial Intelligence, Polytechnical University of Madrid, Spain Department of Computer Science, University of Dortmund, Germany E-mail:
[email protected] We have applied the extended Kalman filter to the parameter, state and structure estimation of a recurrent radial basis function network. The architecture of a recurrent radial basis function network implements a nonlinear autoregresive model with exogenous inputs. The on-line structure adaptation of the network is achieved by combining growing and pruning of the hidden units and connections of the network. Statistical criteria for growing and pruning were derived using the Kalman filter’s innovation statistics and state estimation error. Examples of non-stationary dynamic system modeling are given to illustrate the proposed algorithm.
Keywords: recurrent RBF, on-line learning, structure adaptation, network growing, pruning, extended Ka fmanfilter
1
Introduction
The fundamental property of any learning system including neural networks, is adaptation in a changing environment. In most real world applications the process or environment to be modeled or controlled is non-stationary, that is, the underlying dynamics changes over time. An algorithm for continuous adaptation of a learning system in a non-stationary environment should resolve the following dilemmas: a) Biadvaraince dilemma: sequential adaptation should maintain the optimal complexity of the learning system. b) Stability/plasticity dilema: while the system should be able to follow changes of the non-stationary environment as quickly and accurately as possible (i.e. optimal plasticity), previously acquired information should not be “forgotten” (ie. stability).
* The work of B. TodoroviC was supported by a Scholarship of the German Academic Exchange Service (DAAD) under the Stability Pact for South East Europe. ** The work of C. Moraga was supported by the Spanish State Secretary of Education and Universities of the Ministry of Education, Culture and Sports (Grant SAB2000-0048), and by the Social Fund of the European Community.
73
74
B. TodorouiC, M . StankoviC and C. Moraga
c) Noisehon-stationarity dilemma: a new data sample which significantly differs fiom the aquired knowledge is either an outlier or the evidence of non-stationarity of the task. Our paper discusses a problem of continuous neural network adaptation (often called on-line learning or sequential adaptation) in non-stationary environment. We shall consider the supervised learning scenario where at each time step k an input/output data sample is presented to the network. After that the sample is discarded and cannot be used again for adaptation. The joint inputloutput data distribution is unknown and varies with time. The network should learn the deterministic dependence between the input and output. The knowledge in aneural network is represented by parameters - weights of the connections between neurons. The complexity of the neural network as a model is defined as the number of adaptable parameters, which in turn depends on the number of neurons in the network. The biashariance dilemma is a well known problem in the neural network community, whether the task of interest is stationary or not. A neural network with a small number of adaptable (free) parameters (weightshodes) is biased in the sense that it is unable to model a desired dependence. The network that is too large for the problem suffers from poor generalization, because estimated parameters tend to have a large variance. Also, such a network is more susceptible to noise and error in the training data. There are several approaches for aiming at solving the biashariance dilemma. Constructive approaches start with small number of units and add new units during adaptation until some performance criterion is satisfied [2,6]. Destructive approaches start with a large number of neurons (possibly too large for a given task) and prune connections and neurons as long as deterioration of network performance is not significant [ 1,3]. Combined approaches switch between constructive and destructive phase [9,10]. In order to track changes in non-stationary environment, parameters and structure of the neural network must be time-varying. The ratio between plasticity and stability must be tuned by suitable forgetting factor so as to reject the knowledge that has become invalid due to the non-stationarity. The networks of neurons with localized activation functions are better suited for learning in the nonstationary environment than networks of neurons with global activation functions such as sigmoidal. When data sample in a particular area of the input space is presented, the nonlinear mapping represented by neurons with sigmoidal activation functions may change in other regions of the input space, thus forgetting still valid knowledge. Such behaviour is known as “catastrophic interference”. In this paper we consider the on-line learning of the Recurrent Radial Basis Function (RRBF) network by applying the Extended Kalman Filter (EKF). Among first, the applications of the EKF to recurrent neural network (RNN) learning were described by Matthews[S] and Williams[ll]. In [ l l ] dynamic of the neuron outputs and parameters of the RNN were represented by the state-space model, and the EKF is applied to the resulting nonlinear estimation problem. In this paper we extend this
On-line Adaptation of Recurrent Radial Basis f i n c t i o n Networks
75
idea by applying the EKF to the simultaneous estimation of states, time-varying parameters and structure of the RRBF network. The on-line structure adaptation of the RRBF network is achieved by combining the growing and pruning of the hidden neurons and connections. The Kalman filter consistency test is used as the criterion for adding new hidden neurons - network growing. The on-line pruning algorithm is derived based on a criterion similar to the off-line pruning method Optimal Brain Surgeon (OBS). It uses the statistics estimated by the EKF to determine the significance of the connections and neurons in order to decide whether to prune or not. As a solution to noiselnonstationarity dilemma we propose “add first - confirm later” paradigm. A new data sample which significantly differs from the aquired network knowledge, will cause the addition of a new hidden neuron. However, at the moment of the data arrival the cause of its novelty is not known. Only upcoming data may confirm or negate the fact that current data sample contains significant information, or it is an outlier. If it is an outlier, the hidden neuron that is generated will become insignificant and consequently pruned. Otherwise, it will become specialized, and permanent in the network structure. The remainder of the paper is organized as follows. In Section 2 we give the short description of a RRBF network as the nonlinear autoregressive model of dynamic system with exogenous inputs. Noise filtering and time-varying parameter adaptation of the RRBF network are put in the framework of nonlinear state estimation applying the EKF in Section 3. In Section 4, we derive the criteria for growing and pruning, in order to obtaine the on-line algorithm for structure adaptation of the RRBF network. Examples of nonstationary nonlinear dynamic system modeling in Section 5 are followed by conclusions in Section 6. 2
Dynamic system modeling using the RRBF networks
Let us consider the nonlinear autoregressive model of dynamic system with exogenous inputs and additive observation noise:
~ ( k=)f ( s(k-l) ,..., ~ ( k - A ~ ) , ~ ( k,... - lu(k-A,),w) ) Y ( k )=
+v(k)
(1)
where s ( k ) corresponds to the true (noiseless) output of the system, ~ ( k is) the input at time step k, An and As are the input and the output order, and f ( . ) is a nonlinear function parametrized by w. The only available measurement y ( k ) contains additive noise v(k) . We apply the RRBF network to implement this model by approximating the function f(.).Without loss of generality we shall consider the system with a one-dimensional output (see Fig. 1). In that case the output of the RRBF network is given by:
76
B. TodomwiC, M. StankowiC and C. Moraga
f(S(k-l),u(k-l),w)
"H
+ Cqh(s(k-l),u(k-l),w) .
(2)
i=l
We have used w to denote the n , dimensional vector of unknown parameters (bias a o , weights a;,centers m i l , mij7 and widths o;, , o i j T )and , nH is the number of hidden neurons. The output of the i-th hidden neuron is given by:
where ~ ( -1) k
= [s(k -i)...s(k
and u(k - 1) = [u(k -
...u(k -
-
a,)]fA,is the vector of previous network outputs is the vector of previous inputs.
In the remainder of this paper we will develop the algorithm for simultaneous sequential estimation of noiseless outputs (filtering) and sequential estimation of weights and structure (learning) of the RRBF network by applying the extended Kalman filter.
Fig. 1. Recurrent Radial Basis Function Network
3
State and parameter estimation applying EKF
Kalman Filter (KF) is an optimal linear minimum-mean-square-error state estimator for stochastic linear systems in a state form. In the case of a nonlinear model, the Extended Kalman Filter (EKF) is a suboptimal estimator, obtained by linearizing the model arround current state estimate, and applying the KF equations to the resulting time-varying linear model.
On-line Adaptation of Recurrent Radial Basis Function Networks
77
Let us consider the state estimation of the nonlinear dynamic sistem represented by the following state-space model:
where d ( k ) and v ( k ) are the zero mean Gaussian noise processes. The state vector x(k) evolves according to a nonlinear, non-stationary Markov dynamics driven by input vector u(k) and process noise d ( k ) . Non-stationarity means that fk and the covariance of the process noise are time variant. The Markov property implies that the probability density function of x(k + 1) depends on the knowledge of the current state x(k) and not previous statesx(k-I), I = l,Z,.... The measurement (observation) vector y ( k ) is a nonlinear, nonstationary and noisy mapping of the current state x(k) and current input u ( k ) . The RRBF network parameter estimation can be put in the framework of nonlinear state estimation using the EKF by augmenting the base state s, which is in our case defined as the previous As outputs of the RRBF network, with the vector of network parameters w. The state space representation of the RRBF network parameter and output dynamics is given by:
x(k)= @(x(k-l),u(k-l))+d,(k-I), Y W
=f
w k ) + v ( k ) v(k) 9
d,(k-l)-N(O,Q,(k-l)),
(5a)
- N(O,R(k))
(5b)
The process noise d,(k) and observation noise
78
B. TodorovaC, M. StankoviC and C. Moraga
where the pdf p ( y ( k ) / x ( k ) ) represents the likelihood, the pdf p ( y ( k ) / Y ( k- 1)) is the evidence, and the prior is given by the pdf p ( x ( k ) / Y ( k- 1)) . In order to obtain an analytic solution of (8), the dynamic equation (6) is linearized: x ( k ) = cD(i(k - l), u(k - 1)) + F(k - l)(x(k) - i ( k - 1)) + d,(k - 1) ,
(7)
where F(k - 1) = [V,@(i(k- l), u(k - l))T]T and 2(k - 1) is the estimate of x(k - 1) given observations Y ( k - 1). The relevant pdfs are approximated by Gaussians. The estimate i ( k ) of the augmented state x ( k ) can be computed by maximizing the posterior p ( x ( k ) / Y ( k ) ) or equivalently by minimizing the cost function defined as the negative logarithm of the likelihood and prior product: 1 J ( x ( k ) )= T { ( y ( k -) H ~ ( k ) ) ~ R ( k ) - ' ( y (-Hx(k))+x-(k)TP-(k)-'x-(k)} k)
(8)
where x - ( k ) = x ( k ) - i - ( k ) and i - ( k ) is the prediction of x ( k ) given observations Y ( k - 1) . The obtained equations of the extended Kalman filter can be grouped into two sets, time update and measurement update equations. Note that the state estimate i ( k ) is obtained from V x J ( i ( k ) = ) 0.
Time update equations Augmented state prediction: 2- ( k ) = cD(i(k - l), u(k - 1)) Prediction error covariance: F ( k ) = F(k - 1)P(k - 1)F(k- 1f
+ Q,(k
(9a) - 1) : (9b)
Measurement update equations Innovation: e(k) = y ( k ) - H . i - ( k ) Innovation covariance: S ( k ) = H P - ( k ) H
(10a)
+R(k)
( 1Ob)
Kalman gain: K ( k ) = P - ( k ) H T S ( k ) - ' :
(10c)
Augmented state estimation: i ( k ) = i - ( k ) + K ( k ) e ( k )
(1 0 4
Estimation error covariance: P ( k ) = ( I - K ( k ) H ) .P - ( k )
(loel
While deriving the previous equations we have assumed that the process and observation noise covariances are known. However, for real data applications this is not true. The use of wrong estimates of covariances Q, ( k - 1) and R ( k ) can lead to large estimation errors and even to divergence. In addition, growing and pruning
On-line Adaptation of Recurrent Radial Basis Function Networks
79
criteria for RRBF network, derived in the next section, depend on the process and measurement nose covariances. The wrong estimates can cause unnecessary addition of neurons, or unnecessary pruning, or can stop the addition of new neurons. A number of approaches to the estimation of unknown process and observation noise statistics is considered in [6]. We have considered the covariance-matching technique by making innovations consistent with their theoretical covariance. The theoretical innovation covariance S ( k ) was matched with the actual covariance E[e(k)e(k)T]in order to obtain the estimates Qx ( k - 1) and &k) :
H ( F ( k - 1)P(k- 1)F(k - l)T + &(k
-
l))HT + &k) = IJe(k)e(kf]
(11)
However, simultanous estimation of Q and R from (1 1) did not gave the reliable results. Therefore, we have approximated the Q with diagonal matrix, and let diagonal elements (variances) exponentially decay between given limits. In that case the estimation of the R ( k ) based on the covariance-matching: R(k)= a . R(k - 1) + (1 - a).max(e(k)2 - HF(k/k - l)HT,0)
(14
where 0 < a < 1 , was successful (see examples in Section 5). 4
On-line adaptation of the RRBF network structure
In this section we derive an algorithm for the on-line adaptation of the RRBF network structure using statistics estimated by the extended Kalman filter. the structure adaptation is achieved by combining growing and pruning of the hidden neurons and connections. We have used the Kalmanf filter consistency test to derive the growing criterion. The on-line pruning method estimates the change of the cost (8) when the particular connection or neuron is eliminated, in order to decide whether to prune or not. 4.1
RRBF network growing
If the time-variation of parameters is not sufficient to track changes of the dynamics, the complexity of the network has to be enlarged, by adding new hidden neurons. Formally, the test for adding a new neuron can be obtained from the Kalman filter consistency test. There are two consistency criteria that could be tested in real time: a) the innovations should be acceptable as zero mean and have magnitude commensurate with the theoretical covariance as yielded by the filter and b) the innovations should be acceptable as white.
80
B. TodomwiC, M. StankoviC and C . Moraga
Criterion a) can be tested with the fading memory average normalized innovation squared statistic:
vP(k) = (1 - p>vP(k- 1) + pe(k)TS(k)-'e(k).
(13)
where 0 < p < 1 . If the innovations are white, zero mean and with covariance
S(k) then the distribution of (13) is approximately the scaled chi-square v p ( k )- CX,,2 . The scaling factor is given as c = p/(2 - p) and the number of degrees of freedom is n = no (2 - P)/P where no is the number of the network outputs. Hypothesis H , , that innovations are zero mean and consistent with their theoretical covariance, is accepted if v p ( k ) E [ 4 , b 2 ] .The acceptance interval [b,,b2] is a two-sided (1 -a).loo% probability concentration region for v p ( k ) E [b,9 1 , that is, P { v p ( k ) E [b,, bZ]/Ho} = 1-a . Note that the observation noise covariance R ( k ) was estimated by making
innovations e(k) consistent with their theoretical covariance S ( k ). Therefore, if we have vP(k) > b-2, it is because the innovations have mean different from zero. That is exactly the reason why a new hidden neuron should be added to the network. However, in the case of multidimensional network output ( n o >1), the test
v p ( k ) > b2 cannot identify the source of the problem. In that case, the separate bias test, whether the mean of each component of the innovation e(k) is nonzero or not, has to be carried out. This can be done by dividing each component of the innovation e(k): el(k), I = 1,2,...,no by its standard deviation, which makes it normal N(0,l) , and testing to see if its mean can be accepted as nonzero. The hypothesis that the mean of the 1-th compoment of the innovation is zero H o : E[e(k)]= 0 is tested using the folowing sample mean:
where &(k) is the I-th diagonal element of the innovation covariance S ( k ) . It can be shown that the variance of the sample mean (14 is 1/N . Under the hypothesis H , and for large enough N , the variable ( k ) should be normal with zero mean and variance equal to one. We shall accept that the mean of the I-th innovation component is not zero if the following criterion is satisfied:
dil
On-line Adaptation of Recurrent Radial Basis Function Networks 81
Threshold
y~
is
determined
based
on
the
probability
P{Jf i & ( k ) I< T ~ / H=~1-a } and a is usually chosen to be 0.05. A Kalman filter is not consistent if at least one of the innovation components has mean not equal to zero. Note that one can also use the test (15) if N = 1 . A new hidden neuron should be added if a) the consistency test is not satisfied and b) only specialized hidden neurons are activated by the current network input. A hidden neuron is referred to as specialized if its input and output parameters have accumulated certain level of knowledge, and new observations cannot significantly improve it. The moment of neuron specialization is determined based on the number of samples that have activated the neuron above certain threshold. By applying criterion b) in adition to the consistency test, we insure that some period of time (i.e. some number of samples) is given to the parameters of existing non-specialized neurons to adapt before a new neuron is added. A new hidden neuron will be added if the current input to the network activates only specialized hidden neurons and if at least one of no criteria (15) is satisfied. Initially a new hidden neuron will be connected to all input neurons and to those output neurons whose innovations satisfy (15).
4.2
RRBF network pruning
During adaptation to a time-varying environment some connections or hidden neurons may become insignificant and should be pruned. A connection is insignificant if its parameter and the parameter change are both insignificant. In a RRBF network the significance of the input connection is determined based on the width o u r ,the significance of the recurrent connections, based on the width o i l , and the significance of the output connection, based on the weight a , . The wellknown pruning method OBS [ 11, ranks parameters according to the saliency, which is defined as the change in the training error when the particular parameter is eliminated. The parameter with the smallest saliency is pruned. However, OBS was developed for the off-line trained networks with fixed training and test set. We have derived an analogous on-line pruning method for RRBF network [lo], by establishing the relation between the parameter saliency and the statistical significance of the parameter. Additional criterion is introduced in order to test the the significance of time-varying parameters. The inverse of the Hessian of the cost function, needed for the significance test, is recursively updated by the EKF. Therefore, the pruning method does not significantly increase the overall computation complexity of the learning algortihm.
82
B. TodoroviC, M. StankoviC and C. Moraga
Parameter saliency Saliency of the parameters, estimated using an extended Kalman filter, is defined as the minimal change of the EKF cost function (8) if the particular parameter is pruned. The change of the cost function a ( x ( k ) ) when the current a posteriori estimate i(k) is changed to i ( k ) + & ( k ) , can be obtained from the local1 approximaton of the cost (8) using the Taylor series expansion around i ( k ) . Taking into account that V , J ( i ( k ) ) = 0 , we obtain:
1 a(i(k))=-Gx(k).V,(VJ(i(k)))T 2
.6x(k)
(16)
The estimate of the change 6 i ( k ) should minimize (16), subject to the constraint: & ( k ) T U P = -i(k)
T
up
(17)
where u p is the unit vector for the p-th parameter. The minimum of (16), obtained under the constraint (17) by applying the Lagrangian multiplier approach, represents the saliency coefficient of the p-th parameter:
The matrix T ( k ) = V,(V,J(~(X)))~denotes the Hessian of the cost function (8). The saliency (18) is obtained for the parameter change: &(k) = -
i ( k ) Tu p
T (k)-' u p
u;T(k)-i u p
In order to obtain (1 8) and (I 9), the inverse of the Hessian should be calculated. The Hessian of the cost function (8) is given by: T ( k ) = P-(k)-'
+ HTR(k)-!H .
(20)
It can be shown that the inverse of the Hessian (20) is P ( k ) = T ( k ) - ' . Therefore, the saliency coefficient of the p-th parameter can be rewritten as:
On-line Adaptation of Recurrent Radial Basis Function Networks
83
Parameter significance Assuming that the process and measurement noise are normal with zero mean and known variances, the estimate of the p-th component of the parameter vector is normal with the mean equal to the unknown true value xp(k), and with variance Ppp( k ) .The
hypothesis
that
the
parameter
is
statistically
insignificant
H o : x p ( k ) = 0 , is accepted as true if the folowing criterion is satisfied:
The P( 1 i ; ( k )
test
threshold
is
obtained
from
the
probability
constraint
I< y / H o ) = 1-a .
Comparing the saliency coefficient S,(k) of the p-th parameter, and the i i ( k ) we conclude that I $ i ( k ) /= therefore the parameter insignificance test can be rewritten as: -/, <
Time varying parameter significance For the nonstatinary problems, which are of our primary concern, the parameters of a neural network are time varying. During the adaptation, some parameters may become insignificant, but only in a short time period. To avoid pruning of such parameters, an additional criterion is introduced. This criterion is based on the parameter change significance test. The following fading memory sum for the p-th parameter is considered:
where Qpp(k- 1) is the parameter's process noise variance, and + ; ( k ) is the activity of the i-th hidden neuron, to which the parameter belongs. The distribution of (23) is approximated by the scaled chi-square distribution 6 , ( k ) - cx$ where c = 1/(2 - p) represents the scaling factor and n' = (2 - p ) / p is the number of degrees of freedom. The hypothesis H , , that the estimated parameter changes are consistent with the process noise covariance, is accepted if 6,(k) E [b,b2], where
the acceptance interval is chosen to be (1 - a ) . l o o % probability concentration
84 B. TodoroviC, M. Stankovie' and C. Moraga
region for 6 , ( k ) . The parameter is assumed insignifficant and consequently pruned, if both its estimate and its change are statistically insignificant.
State estimation error update Parameter pruning demands the elimination of the corresponding rows and columns in the Hessian T ( k / k ) . The Hessian and its inverse, can be rearranged as:
where T b ( k ) , T , ( k ) , Td(k) are the rows and columns corresponding to the parameters that should be deleted. Applying the partitioned matrix inversion lemma, a new covariance matrix P*( k ) = T, (k)-' is obtained: P*(k)= P,(k)
-
Pj(k)Pd(k)-'P,(k)
(25)
Neuron pruning The specialized or rarely activated hidden neuron should be pruned if all of its output connections have statistically insignificant parameters or at least one of its input connections has insignificant, small width. Statistically insignificant width of any connection between the input and hidden neuron, as the result of parameter adaptation, reflects the tendency to diminish as much as possible the area of the input space for which the hidden neuron is active. Often such neurons degrade the continuity of the RBF network output, and because of that they should be pruned.
5
Experiments
The following examples show that our algorithm for on-line adaptation of the RRBF netowrk produces very compact networks with small number of hidden neurons and adaptable parameters. In all examples statistical tests for adding or pruning had the size a = 0.05. Neurons were added with the following initial parameters:
=E(k), m,,+l = [ ~ ( k - l )~~( k - l ) ~and ] ~ on,,+l=OO, where 00 is the initial width. The initial variances of parameters were chosen so that initial parameter values were statistically insignificant: P~~(O)-~/*;~((O) < 7 . A hidden neuron is u,,,~
considered rarely activated if the ratio between the number of data samples that
On-line Adaptation of Recurrent Radial Basis Function Networks
85
have activated a neuron above $min = 0.1 , and the total number of data samples from the moment when the neuron was added, is less then 0.05. 5. I
Non-stationary Mackey-Glass time series prediction
An EKF trained RRl3F was applied to prediction of the non-stationary MackeyGlass time series, defined by the differential delay equation: i ( t ) = -bs(t) + a
s(t - T)
1- s(t - 7 )10 '
with a = 0.2, b = 0.1. We integrated the equation (26) for 0 < t < 3 100s using the fourth order Runge Kutta method with step size 0.1, and the history initialized to 1.2. During integration, the delay r was varied according to: t = 23.5+
6.5(0.7sin(27ct/3100) + 0.3sin(57ct/3100)),
(27)
Every tenth sample was used, and samples from the first 100s were discarded, leaving s(k),k = 1,..,3000 samples for training. The observations were obtained according to y ( k ) = s ( k ) - cos(3nk/3000) + v (k ), where the v(k) was Gaussian white noise with a variance which gave the signal to noise ratio SNR=40dB. The RRBF network was trained to predict x(k + 6) from x ( k ) , x ( k - 6), x(k - 12), x(k - 18), x ( k - 24), where x (k ) was the output of the RRBF network at time step k, and observations y ( k ) ,k = 30,...,3000 were used for training. At the end of data sequence the learning algorithm produced a RRBF network with 5 recurrent connections and 4 hidden neurons (3 significant), i.e. 45 adaptable parameters. The root-mean-square-error, measured on the last 1000 data samples was RMSE=0.0209. Note that learning was sequential with each training sample presented only once to the network. The network was always asked for prediction before the parameter or structure adaptation. Therefore we can consider that the given RMSE is a test error measure.
5.2
Non-stationary Lorenz time series prediction
This example illustrates the influence of the process noise covariance Q, ( k - 1) on the network performance. We will show that a correct ratio of network parameter and structure variation must be found in order to track non-stationary dynamic. We consider the chaotic system described by Lorenz equations [3]:
B. TodoroviC, M. StanlcoviC and C. Moraga
86
2.5, 2
p
u
= 'Y
=
i 1
1.5
s
I =
1.5
y
1
.5
6
0 5
0
0.5 -0.5
I 2600
2700 2800 Time sltsps: k
2900
3000
500
a) Comparison
1000 1500 2000 Time steps: k
I
2500
3000
2500
3000
b) Comparison
0 5
0
'<&Q ,._"
2
-0 5
500
1000Tirnerlepr 1500 k2000
2500
3000
-.. 0'
c) Innovation
500
1000 1500 2000 Time rlepr: k
d) Growth and pruning pattern
Fig. 2. Results of non-stationary Maekey-Glass time series prediction
where p , (J and p are adjustable parameters. Equations (28) were integrated for 0 < t < 75s using the fourth order Runge Kutta method with step size 0.01. Parameters p , (J and p were varied according to: /3 = (1+3.5(1+sin(O. l t ) ) ) / 3 , CJ = 10, p = 17+ 6.5(cos(2d/t-7q), 0 I t 5 75 (29)
The time series from the variable x1 (sampled at a period of 0.05 seconds) was scaled between [-1,1] and Gaussian white noise v(k) was added to obtain the observations y ( k ) , k = 1,...,1500 with SNR=40dB. The RRBF network was trained to predict s ( k + 2 ) from s(k) , s ( k - 2 ) , s ( k - 4 ) , s ( k - 6 ) , where s(k) is the output of the RRBF network at time step k. In the first case, the diagonal elements of proces noise covariance Q(k-1) were exponentialy decaying : from 5.e-3 to 1.e-5 for the state and from 5.e-3 to 5.e5 for the paremeters). The prediction results are given in Fig. 3. The root-meansquare-error, measured on the last 1000 data samples was RMSE=0.0367.
On-line Adaptation of Recurrent Radial Basis l h n c t i o n Networks
a) Network prediction
87
b) Measurement noise variance estimation 10
1-
8~ I
;6P
c
B
.-"l"__"_
4~
P
1
c) Innovation (prediction error)
d) Growth and pruning patteern
Fig. 3. Results of non-stationary Lorene time series prediction (Good estimate of process noise variances)
a) Network prediction
b) Measurement noise variance estimation 8~
1-
0.5
-5
2 0
6-
P
r "6
4~
z
-0 5
2~
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
O L
c) Inovation (prediction error)
d) Growth and pruning pattern
Fig. 4. Results of the non-stationary Lorenc time series prediction for the overestimated proces noise variances
88
B. TodoroviC,
M. StankoviC and C. Moraga
1000
500
1500
0
500
1000
1500
Time s t e p s : k
Time steps: k
a) Network prediction
b) Measurement noise variance estimation
1
0.5
2 0 -0.5
1
500
1000
1500
Time steps: k
c) Innovation (prediction error)
1000
500
1500
Time steps: k
d) Growth and pruning pattern
Fig. 5. Results of the non-stationary Lorenc time series prcdiction for the underestimated proccs noise variances
The prediction results for the second case, when the process noise variances were equal to 5.e-1, are given in Fig. 4. Because of the large variances, only one neuron was added, but never proved to be significant. The growing criterion was not satisfied ever again. In addition, the final estimate of the measurement noise variance was extremely small. The root-mean-square-error, measured on the last 1000 data samples was RMSE=0.074 1. In the last case, the state and parameter process noise variances were exponentially decaying from 5.e-4 to 1.e-6. The rate of parameter variation was not sufficient to track the nonstationarity (Fig. 5). The algorithm added a significant number of hidden neurons, but the prediction was not improved. The root-meansquare-error, measured on the last 1000 data samples was RMSE=0.074 1.
5.3 Resolving noisehon-stationarity dilemma This example will illustrate the ability of the algorithm to resolve noiselnonstationarity dilemma. We consider the identification of the plant described by difference equation:
where unknown function has the form (modified from [7]):
On-line Adaptation of Recurrent Radial Basis Function Networks
89
The parameters a and p are equal to zero for the first 800 observations. For the next 400 observations ( 800 < k < 1200 ) they are varied according to: a = P = 0 . 0 0 5 k - 4 , and for the last 1300 observations a = p = 2 . The observations of the plant output are obtained for input: u ( k )=
sin(2&/250), 0.8 sin(2&/250)
{
2mN < k I (2m + l)N + 0.2 sin(2&/25), (2m + l)N < k I (2m + 2)N (32)
where m=0,1,2 and N=500. For the first 1500 time steps, the variance of the measurement noise was chosen to give 30dB signal-to-noise ratio (SNR), and after that the variance was chosen to give the SNR=SdB. The results of identification of dynamic system (30), obtained by sequential adaptation of the RRBF network over 2500 data samples, are shown in Fig. 6. The learning algorithm has detected the nonstationarity (for 800 < k < 1200), by adding new hidden neurons, which soon became significant. A change of the measurement noise variance at k l 5 0 1 , also caused addition of new hidden neurons. However, they did not become significant and therefore they are susceptable to pruning (Fig. 6.c). At the same time the estimate of R ( k ) is updated to track the change of the measurement noise variance (Fig. 6.d) 6
Conclusions
An extended Kalman filter is applied to the parameter, state and structure estimation of the recurrent radial basis function network. The architecture of a recurrent radial basis hnction network implements a nonlinear autoregresive model with exogenous inputs. The augmented state of the recurrent radial basis function network is the stacked vector consisting of parameters and outputs of the network. This state is estimated using an extended Kalman filter. The on-line structure adaptation of the network is achieved by combining growing and pruning of the hidden units and connections of the network. Statistical criteria for growing and pruning were derived using the state estimation error and innovation statistics. Recurrent networks trained by an extended Kalman filter have been successfuly applied in non-stationary dynamic system modeling.
90
B. Todorovid, M . Stankovid and C. Moraga
15
-r
1
-
5 05 0
: o
-m
a -0 5 I
-1'5k
500
1000
IsbO
2000
2,bO
-1.51
'
'
'
1800 1900 2000 2100
' 2200
'
2300
' 2400
b) Cornpatison
a) Comparison
I O'
500
1000
1500
1 00
Time steps: k
Time steps: k
2OW
Time steps: k
c) Growth and pruning pattern
2500
J 500
1000
1500
2000
2500
Timesteps k
d) Measurement noise variance estimation
Fig. 6 . Rcsults of the non-stationary dynamic system identification
7
References
1. Hassibi, B., Stork, D., Wolff, G. J.: Optimal Brain Surgeon and General Network Pruning, IEEE Int. ConJ Neural Networks, San Francisco (1993) 293299. 2 . Kadirkamanathan, V.: A statistical inference based growth criterion for the RBF network, In Proc. IEEE Workshop on Neural Networks for Signal Processing (1994) 3 . LeCun, Y., Denker, J., Solla, S., Howard, R. E., Jackel, L. D.: Optimal Brain Damage, In D. S. Touretzky editor, Advances in Neural Information Processing Systems II, Morgan Kauffman ,( 1990) 4. Lorenz, E. N.: Deterministic non-periodic flow, J. Atm. Science, vol. 20, (1963) 130- 141 5. Matthews, M. B.: Neural network nonlinear adaptive filtering using the extended Kalman filter algorithm, Proc. of the International Neural Networks Conference, Paris, vol. I, (1990), 115-1 19
On-lane Adaptation of R e c u m n t Radial Basis Function Networks 91
6. Mehra, R. K.:Approaches to Adaptive Filtering, IEEE, Trans. on Aut. Cont. , Oct. (1972) 693-698 7. Narendra, K., Parthasarathy, K.: Identification and control of dynamical systems using neural networks, IEEE Trans. on Neural Networks, no. 1, (1 990) 4-27 8. Platt, J.: A resource allocating network for function interpolation, Neural Computation, vol. 3 , no. 2 (1991) 213-225 9. TodoroviC, B., StankoviC, M, TodoroviC-Zarkula, S.: Structurally adaptive RBF network in non-stationary time series prediction, In Proc. IEEE AS-SPCC, Lake Louise, Alberta, Canada, Oct. 1-4 (2000) 224-229 10. TodoroviC, B., StankoviC, M : Training recurrent radial basis function network using extended Kalman filter: parameter, state and structure estimation, In Proc. South-Eastern Europe Workshop on Computational Intelligence and Information Technology, Press T. University of Nis, Yugoslavia (200 1) 11. Williams, R.J.: Some observations on the use of the extended Kalman filter as a recurrent network learning algorithm, Technical Report NUCCS-92- 1. Boston: Northeastern University, College of Computer Science (1992)
This page intentionally left blank
ITERATIVE EVALUATION OF ANYTIME PSGS FUZZY SYSTEMS ORSOLYA TAKACS, ANNAMARIA R. VARKONYI-KOCZY Dept. of Measurement and Information Systems Budapest University of Technology and Economics Magyar Tudbsok krt. 2., Budapest, H-1521 Hungary Phone: +36 1 463 2057, Fax: +36 I 463 4112 E-mail:takacs@mit. brne.hu;
[email protected] In systems, where the available time and resources are limited and even can change during the operation of the system, special algorithms, computing methods, the so called anytime techniques can be used advantageously. While fuzzy tools are wide-spreadly used in nearly every area of engineering, their usability in time-critical environment is limited, because of their exponentially increasing complexity. SVD-based complexity reduction offers a way for exact and non-exact complexity reduction of fuzzy inference systems and, furthermore, makes possible their iterative-type evaluation. Thus, the direct use of fuzzy tools in anytime applications becomes possible. Keywords; anytime applications, fuzzy inference systems, complexity reduction, Singular Value Decomposition
1
Introduction
Nowadays, most of the industrial applications can be characterized by two conflicting features: the time-critical property and the increasing sophistication and complexity of the problems to be solved. The time-critical property means that most of the tasks - measurement, monitoring, signal processing, fault detection and diagnosis, system control, etc. must be carried out ,,on-line” under prescribed, guaranteed response-time. Because usually not only the time but also the resources are limited, computing methods with low complexity are needed. Moreover, the amount of available time and resources can vary and depend on the actual circumstances: a temporal overloading of the system or an alarm signal, which needs immediate attention can cause that some modules of the system do not obtain as much resources or time, as would be optimal. These temporal shortages of processing timehesources - along with the possible fallouts of input data - can cause a critical breakdown in the performance of the system or even can cause that the data processing can not be carried out at all. To avoid these breakdowns, the so-called ,,anytime” techniques can be used advantageously, which are able to provide short response time and maintain the information processing even in cases of temporary shortage of time or computational power [ 1,2]. The aim of the use of these techniques is to maintain the
93
94
0. T a k d c s a n d A . R. Vdrkonyi-Kdczy
continuous operation of the system in cases of changing or critical circumstances and to provide optimal overall performance for the whole system. Another important tendency is the increasing complexity of the problems to be solved. While for the simpler, basically linear problems theoretically well founded methods and tools are available, there is a lack of systematic methods for solving a larger class of non-linear modelling and control problems. In practical industrial applications the - typically non-linear - processes are often too complex to be modelled by classical tools: either the exact physicaVmathematica1 description of the system is unknown or could be obtained only with too much difficulties or is too complex to be handled. For the first problem fuzzy systems and other soft computational techniques (neural networks, etc.) may offer a solution. They can be built based on expert knowledge originating from human experts and there are also known methods for the improvement of fuzzy systems by using sample data. Thus, fuzzy tools can give a solution, if the exact mathematical model cannot, but expert knowledge andor training data is available. [3,4] Another advantage of fuzzy-based systems is that they are robust and are able to handle not only imprecise data but also inexactly formulated concepts that can be expressed by classical tools only with difficulties. It results that fuzzy systems can advantageously be used in cases, when the available data is imprecise or the interpretation can depend on the context [5,6]. However, the usability of fuzzy tools in time-critical applications is limited by the lack of any systematic method to determine the required complexity of the system. Higher granularity - higher number of antecedent fuzzy sets - usually results in a better approximation. To achieve a needed accuracy, one can be tempted to overestimate the needed granularity, which results in huge and redundant systems with too many rules and too high complexity. In a lot of cases, even if we have a treatable model of the system with suitably law complexity, problems may be caused by the shortage of necessary data, recourses, or processing time. These situations seem unavoidable even in case of extremely careful design. Adaptive, flexible, anytime models, algorithms can help to overcome the breakdowns. The idea is that if there is a temporal shortage of computational power, time andor there is a loss of data, the actual operations should be continued to maintain the overall performance “at lower prize”, i.e. information processing based on algorithms and/or models of simpler complexity should provide outputs of acceptable quality to continue the operation of the complete system. The accuracy of the processing will be temporarily lower but possibly still enough to produce data for qualitative evaluations and supporting decisions. In case of fuzzy systems it means the evaluatiuon of only a subset of the rules. The problem is that the significance of the rules can be highly dependent on the actual inputs and no such method has been published up till now that could help in choosing the most pertinent part of the rules to guarantee a given accuracy.
Iterative Evaluation of Anytime PSGS Fuzzy Systems
95
In the following, the possibilities of the use of fuzzy systems in anytime environment will be discussed, along with the description of a transformation method based on the SVD-algorithm which makes possible the iterative-type evaluation of fuzzy systems. The paper is organized as follows: Section 2 gives an overview about anytime systems and the possible use of fuzzy models/algorithms in anytime systems. Section 3 summarizes the basics of Singular Value Decomposition. Section 4 is devoted to the proposed new iterative type evaluation method of PSGS fuzzy systems. In Section 5 a simple example is presented to illustrate the introduced technique, while in Section 6 the conclusions are drawn. 2
Anytime systems
Today there is an increasing number of applications where the computing must be carried out on-line, with a guaranteed response time and limited resources. Moreover, the available time and resources are not only limited but can also change during the operation of the system. Good examples are the modern computer-based diagnostic and monitoring systems, which are able to supervise complex industrial processes and determine appropriate actions in case of failures or deviation from the optimal operational mode. In these systems, for the diagnosis usually the model of the faultless system is used and the evaluation of the model must be carried out on-line, thus the model need not only be correct, but also treatable by the limited resources during limited time. Moreover, if some abnormality occurs in the system’s behavior, some kind of fault diagnostic task should also be completed meaning the reallocation of a part of the finite resources from the evaluation of the system model to this task. Also in case of an alarm signal, lower response time may be needed. In these cases, the so-called anytime algorithms and systems [2] can be used advantageously, which are able to provide guaranteed response time and are flexible in respect to the available input data, time and computational power. This flexibility makes able these systems to work in changing circumstances without critical breakdowns in the performance. Naturally, while the information processing can be maintained, the complexity must be reduced, thus the results of the computing become less accurate [7]. The algorithmdcomputing methods, which are suitable for anytime usage have to fulfill the following expectations: 0 Low complexity: for the optimized behavior the results must be produced with as little computing as possible, i.e. the redundant calculations must be omitted. Changeable, guaranteed response time/computational need and accuracy: the achievable accuracy of the results and the necessary amount of computing timehesources must be flexibly changeable and usually known in advance. 0 Known error: the error, originating from the necessary model “fitting” (e.g. complexity reduction resulting in non-exact solutions) must also be known, to
96
0. Taka'cs and A . R. Va'rkonyi-Kdczy
be able to find the optimal or at least still acceptable solution in the given circumstances, and to be able to compute the resultant error of the outputs. 2.1
Iterative algorithms
Iterative algorithms are popular tools in anytime systems, because their complexity can be easily and flexibly changed. These algorithms always give some - not accurate - result, and more and more accurate results can be obtained, if the calculations are continued. A further advantageous aspect of iterative algorithms is that we don't have to know the timehesource-need of a certain configuration in advance, the calculations can be continued until the results are needed. Then, by simply stopping the calculations, always in the given conditions achievable most accurate results are obtained. Unfortunately, the usability of iterative algorithms is limited. While there is a wide range of problems, which can be solved by iterative algorithms, adequate evaluation methods can not always be found. Not only the existence of some kind of iterative evaluation method can be a problem, even more frequently the accuracy of the results is unknown: we only know, that the algorithm gives more and more accurate results, but we do not know, how much time is needed to achieve a given accuracy or what will be the rate of error if the calculations are stopped at a given point. 2.2
Anytime systems with modular architecture
Expert System J
1
3
/
Module B Fig. 1. Anytime system with modular architecture
Besides the iterative algorithms, a widerange of other types of computing methods/algorithms can be applied in anytime systems, as well, if a modular architecture (Fig. 1.) is used [8]. The applicability of this technique is more general with a burden of lower flexibility and it needs extra planning and considerations. Using this latter solution, each module of the system offers several implementations (characterized by different attribute-values) for a certain task. The units within a given module have uniform interface (same set of inputs, output, and solve the same problem) but differ in their computational need and accuracy. At a
Iterative Evaluation of Anytime PSGS Fuzzlj Systems 97
given time, in the knowledge of the temporal conditions (tasks to complete, achievable timehesources, needed accuracy, etc.) an expert system can choose the adequate configuration, i.e. the units, which will be used. This means the optimization of the whole system instead of individual modules, i.e. in some cases it can be more advantageous to reduce the computational complexity and accuracy of some parts of the systems and rearrange the resources to the other, at the moment more important task. Although, the units implementing a certain task may have different internal structure, from several point of view (see e.g. [S]) it is advantageous if they are built of similar structure. In this case the adaptation or change between the units means only the change of some parameter set. 2.3
Fuzzy tools in anytime environment
Recently fuzzy tools have become very popular and their use has proved to be advantageous in system modeling, diagnosis, and control. They can offer a way even in cases where classical techniques fail to solve problems. Furthermore, fuzzy models offer a very challenging alternative to transform a priori knowledge available in linguistic form into computer programs. The representation of information in fuzzy systems is close to human thinking, thus fuzzy systems are usually relatively easy to survey and the knowledge, originating from human experts can easily be built into them. There are also known methods for the improvement of fuzzy systems by using sample data, thus fuzzy modeling can be used also when the exact mathematical description of the problem is not known, but expert knowledge and/or sample data is available. Moreover, fuzzy systems are robust against imprecise data and inexactly formulated concepts, as well. Despite all of these advantages, the usability of fuzzy methods is limited because of their exponentially increasing computational complexity. Behind this problem hides the fact that we do not know any universal method for the estimation of the optimal (necessary) number of antecedent fuzzy sets to achieve a desired accuracy, so in practice, they are usually overestimated which yields to large, redundant, or even inconsistent rule-bases. To be able to use fuzzy tools in anytime environment this redundancy has to be filtered out. From a lot of known complexity reduction techniques Singular Value Decomposition (SVD) based complexity reduction can be one of the most serious candidates because it can be used not only for eliminating the redundancy but also for further, non-exact complexity reduction. For anytime purposes by using the SVD technique several rule-bases can be constructed, based on the original one. These alternative rule-bases will have different complexity and (known) accuracy and can form the different units in the above described modular architecture [8]. While in this way fuzzy systems can be used in anytime environment, a more flexible method, the iterative-type evaluation could be more advantageous. We can,
98
0. T a k d c s a n d A , R. V d r k o n y i - K d c z y
of course, evaluate the rules step-by-step and stop the evaluation if the available time is over, however, in this case there is no guarantee for the accuracy and that the available result will be the most accurate one. Neither can we give any fixed ordering of the rules since the significance of the rules also depends on the actual inputs. In the following, a transformation based on the SVD-algorithm will be introduced which can offer a solution for the above problem. After applying the transformation, the transformed form of the fuzzy system can be evaluated iterativetype, step-by-step, with a known error-bound in every step. Moreover, it also ensures that the evaluation will be optimal, i.e. the error will be decreased as fast as possible. 3
SVD-based complexity reduction
SVD based complexity reduction, as a method for creating fuzzy inference systems for the approximation of functions based on grid-point sampling, was first introduced by Yam [9], and Yam and Yang [lo]. Later, the method was proposed as a method for the rule-base reduction of certain types of fuzzy inference systems. It has been extended to PSGS (Product-Sum-Gravity with Singleton consequences) [ 111, PSGN (Product-Sum-Gravity with Nonsingleton consequences) [ 121, and Takagi-Sugeno fuzzy systems, and recently even to generalized neural networks [ 14- 181. There are several complexity-reduction algorithms that can be applied on certain fuzzy systems. Most of them have limitations on the rule-bases or modify the inference algorithm. On the contrary, the SVD-based complexity reduction algorithm can be used for a wide range of fuzzy systems and also for generalized neural networks and it modifies only the rule-base, not the inference algorithm. It offers a way for the automatic elimination of the redundancy of the rule-base or neural network (exact reduction) resulting in a minimum system. Although, in many cases, the complexity-reduction obtained in this way is not enough effective to achieve realizable low computational complexity and further, non-exact reduction is needed. In case of non-exact complexity-reduction, an errorbound for the accuracy of the reduced system should be determined for the qualification of the results. SVD based reduction offers a very challenging possibility for this. Here, we have to remark that the rate or effectiveness of the reduction highly depends on the starting, exact but possibly redundant model. If there is not any redundancy in the starting model, which is possible theoretically, we will not earn anything by applying exact SVD based complexity reduction on the model. In reality, especially in case of complex systems, the lack of any systematic designing method causes that the reduced model is usually significantly smaller than the original one.
Iteratave Evaluatzon of Anytime PSGS Fuzzy Systems 99
By improving the reduction, i.e. applying non-exact complexity reduction, the higher the allowable error is, the less complex the reduced model will be, with smaller and smaller rule-base or fewer nodes. The complexity and inaccuracy of the resulted rule-bases can always be easily estimated. 3.1
The Basic SVD algorithm
The SVD-based complexity reduction algorithm of different systems is based on the fact that the equations, describing these systems can be transformed into a matrix form, and the size of the matrices in this form can be reduced. Any F matrix can be decomposed as [9]:
where Ak (k=1,2) are orthogonal matrices ( =Ak = kA T = = E ), B - is diagonal, and F in decreasing order. The maximum number of contains the 4 singular values of the nonzero singular values is nSVD= min(nl ,n2 ) . The singular values indicate the significance of the corresponding columns of
d k .Let the matrices be partitioned in
the following way [lo]:
where r denotes "reduced" and n, 5 nSvD. d ; can be dropped: contains only zero singular values, then Bd - and 4 If B -
Ed contains nonzero singular values, then the F'= =ArB'ArT I= =2 matrix is an If F and approximation of F - and the maximum difference between the values of is the sum of the discarded singular values [ 111:
The reduction can be achieved by the fact that the sizelcomplexity of the original system is in correspondence with the size of matrix F , while the size of - . the reduced system is in correspondence with matrix B'
100
0. Takdcs and A . R. V d r k o n y i - K d c z y
Further transformations can be made to ensure certain properties of the matrices, if needed (sum-normalization (SN): the sum of each row equals one; nonnegativeness (NN); normalization (NO): there is an element equal to one in every column) [ l 11. These can be required to ensure, that the reduced system will be a correct fuzzy systedgeneralized fuzzy-neural network. SVD-based reduction makes possible the use of fuzzy systems or neural systems in anytime systems with a modular architecture by creating several rulebaseslneural networks with different complexity and accuracy for the same problem, and using them as different realizations (units) of a given module. Further, the SVD algorithm can also be used to transform PSGS fuzzy systems into another form, which can be evaluated iterative type.
Iterative evaluation of PSGS fuzzy systems
4
4.1
Transformation
The SVD-based complexity reduction can be used to transform the equation, describing a fuzzy system, to a form, which can be evaluated anytime-like mode. For the case of simplicity, consider a PSGS (Product-Sum-Gravity-Singleton) fuzzy rule base with four inputs, with n j, n2, n3, and n4 antecedent fuzzy sets, respectively. The antecedent fuzzy sets are in Ruspini-partition, the consequence fuzzy sets are singletons. So the rule base contains nl*n2*nj*n4rules as:
The fuzzification method is singleton, and during the inference product T-norm and sum S-norm are used. The result of the hzzy inference in case of the (XI
*
* * * ,x2 ,x3,x4 ) input values
By transforming Eq. (2) into a matrix form one gets:
Iterative Evaluation of Anytime PSGS Fuzzy Systems
. p3,l
* [Y il ,i, ,i3,id .
* p 4 , l <xi> * = -12 p
*
*
*
101
*
,x2)z'34(x39x4)
>
(4)
*
p3,n3 (xi) ~ 4 , n (, ~ 4
where the length of the vectors
and
respectively. The size of matrix Y is
are
and
and the element
is in the position The Y matrix can be decomposed according to Eq.(1):
where =Ak are orthogonal matrices, and diagonal matrix B contains the Ai singular values of 1 - in decreasing order. Let new vectors be defined as:
where [k]denotes the kth element of the given vector. This transformation can be extended to any number of inputs. 4.2
Error estimation
The transformed form (Eq.(6)) can be evaluated in an anytime-type mode by computing and summing the terms gradually. For the practical use, the estimation of the accuracy of the computations, i. e. the deviation from the results of the original systems should be determined at any point of the evaluation. After summing up nSVD - m terms, the output is:
where
102
0. Takdcs and A . R. V d r k o n y i - K d c z y
be the upper bound for the error of the SVD based matrix reduction Let after discarding m singular values: Y-A'
=
B' ArT I E s v D , ~
(8)
=I,m=m=2,m
Thus, the error of the output after summarizing
terms:
(Here we have used the fact that the original antecedent fuzzy sets are in Ruspini-partition.) Eq. (9) results in two important things. First, if there are also zero singular values, the terms corresponding to them can be left out without any degradation of the accuracy, i.e. the complexity reduction is exact. Secondly, the error will be always equal or less, then the sum of the discarded singular values at the given point, thus the accuracy of the computations is increasing by adding more and more terms and after summing all of the terms corresponding to nonzero singular values the error will decrease to zero. Since SVD sets the singular values in the order of magnitude (starting with the highest singular values in matrix B ) , during the evaluation the most significant terms are added first ensuring that the error decreases as fast as possible. Thus, if the available time is not enough to evaluate all of the terms corresponding to nonzero singular values and some must be left out, it will cause the smallest possible error. It is worth mentioning that the effectiveness of this evaluation method depends on the properties of the original fuzzy system. If the singular values are nearly equal, which means that the terms contribute to the result in nearly the same degree, non-exact complexity reduction may cause considerable, possibly not acceptable
Iterative Evaluation of Anytime PSGS Fuzzy Systems
103
error with a magnitude more or less proportional with the number of neglected terms. Even if that is the case the results may help to make qualitative decisions. If the singular values are highly different, then the first terms have much higher contribution to the result than the last ones. The error will decrease faster and a good approximation can be generated using only those terms which have significant weights and the negligible components can be thresholded.
5
Illustrative example
In this Section, to illustrate the proposed SVD-based transformation and iterative type evaluation, a simple example with a three input-one output fuzzy model is presented. The model is a PSGS fuzzy system describing the human hearing system. The inputs are the frequency, sound intensity and age, while the output is the sound intensity felt by the person, i. e. the subjective intensity. The inputs are represented by triangular membership functions in Ruspini-partition. The grid-points for the different inputs are: frequency - [l, 1.25, 1.5, 1.8, 2, 2.25, 2.5, 2.75, 2.9, 3, 3.2, 3.4, 3.5,3.6, 3.75,4], intensity - [0, 8, 16, 25, 33,40, 50, 60, 70, 80, 100, 120, 1401, age - [O, 10, 20, 30, 40, 50, 60, 70, 80, 90, 1001. Thus, the number of antecedent fuzzy sets are 16, 13 and 11, respectively, resulting in 2288 rules. Fig. 2. shows the obtained surface of the fuzzy model as a function of frequency and sound intensity at age of 20 years. The number of terms in the transformed form ( nSVD) is 16. The singular values are (in decreasing order): [2334.1, 300.6, 76.0, 42.7, 26.1, 14.8, 12.9, 10.6, 5.8, 4.1, 3.3, 2.9, 1.8, 1.2, 0.8, 0.21, thus, the error-bounds after evaluating 1, 2, 3, ... 16 terms are: [503.8, 203.2, 127.2, 84.5, 58.4,43.5, 30.7, 20.1, 14.3, 10.2, 6.9,4, 2.2, 1, 0.2, 01. However, these are upper-bounds. By evaluating the outputs in uniformly distributed points along the frequency and objective intensity, with a fixed value of 20 for age, the maximum absolute errors (that is, the absolute differences between the result after evaluating a given number of terms and the result after evaluating all of the terms) after evaluating 1, 2, 3, ... 16 terms are [21.3298, 7.0311, 3.4041, 2.2239, 1.3348, 1.0753, 1.0701, 0.8173, 0.3410, 0.2866, 0.2864, 0.0982, 0.0932, 0.0491, 0.0207, 0, 01 and the average absolute errors are r4.6297, 1.5709, 0.7765, 0.4605, 0.3459, 0.2598, 0.2224, 0.1330, 0.0807, 0.0374, 0.0277, 0.0160, 0.0096, 0.0051, 0.0014, 0, 01. Fig. 3. shows the errors after evaluating only 2, 5, and 10 terms from 16.
104 O. Takacs and A. R. Varkonyi-Koczy
Fig. 2. Output of the model
Fig. 3. The error after evaluating,2,5, and 10 terms
6
Conclusions
In modern industrial applications the time-critical property and the complexity of the systems raise new challenges. For ensuring continuous operation of the system, even during temporal shortages of time/resources, the so called anytime techniques can be used. On the other hand, different soft computing methods - among them fuzzy systems – can advantageously be used for system modeling and control, even in cases, when classical tools mare unusable. However, their usability is usually limited because of complexity-problems. Thus, there is a neded for combining fuzzy tools with anytime techniques. With the use of the SVD-based complexity reduction not only the redundancy of the rule bases can be eliminated but further, non-exact reduction can be achieved, if a certain amount of error can be tolerated. This offers a way to apply fuzzy
Iterative Evaluation of Anytime PSGS Fuzzy Systems
105
systems - and generalized fuzzy-neural networks - in anytime systems with a modular architecture. However, the flexibility of this method is lower than in case of iterative algorithms and the amount of the available timehesources must be estimated in advance. In this paper a further improvement is presented which makes possible the iterative-type evaluation of PSGS fuzzy systems. To be able to estimate the error at a given point of the evaluation, the system model should be transformed based on the SVD-algorithm. This transformation also ensures that the most significant terms will be evaluated first, thus the error will decrease as fast as possible.
Acknowledgements This work was sponsored by the Hungarian Fund for Scientific Research (OTKA T 035 190)and the 12SIntegrated Intelligent Systems Japanese-Hungarian Laboratory.
References 1. Baron,C., J.-C Geffroy, G. Motet ed., Embedded System Applications, Kluwer
Academic Publishers, 1997. 2. S. Zilberstein, "Using Anytime Algorithms in Intelligent systems", A1 Magazine, 17(3), 1996, pp. 73-83. 3. Vascak, J., Kovacik, P., Hirota, K., Sincak, P.: "Performance-based Adaptive Fuzzy Control of Aircrafts", Proc. of the loth IEEE International Conferemce on Fuzzy Systems, Vol. 2., Melbourne, Australia, 2001. 4. Vascak, J., Kovacik, P., Hirota, K., Sincak, P.: Design of an Adaptive Fuzzybased Automatic Pilot, Proc of the 2"d International Conference on Intelligent Technologies (InTech), Bangkok, Thailand, 2001, pp. 282-291. 5. R. K. Bhatnagar and L. N. Kanal, "Handling uncertain information: a review of numeric and non-numeric methods", In Uncertainty in Artificial Intelligence, Elsevier Science Publishers, 1986, pp. 3-26. 6. 0. Takacs, A. R. Virkonyi-Koczy, "Some Aspects of Representing Uncertainty in Nonlinear Systems", In Proc. of INTCOM '98, Symposium on Intelligent Systems in Control and Measurement, pp. 168-176., Hungary, Miskolc, Nov. 21-27, 1998. 7. Virkonyi-Koczy, A.R., T. Kovicshizy, 0. Takics, Cs. Benedecsik, "Anytime Algorithms in Intelligent Measurement and Control." In Proc. of the 2000 World Automation Congress, WAC 2000, Maui, USA, June 11-16,2000, pp.. 8. Virkonyi-K&zy, A.R., A. Ruano, P. Baranyi, O.Takics, "Anytime Information Processsing Based on Fuzzy and Neural Network Models," In Proc. of the 2001 IEEE Instrumentation and Measurement Technology
106
9. 10. 11. 12. 13. 14. 15. 16. 17. 18.
0. Takcics and A . R . Vcirkonyi-Kdczy
Conference, IMTC/2001, Budapest, Hungary, May 21-23, 2001, pp. 12471252. Yam Y., "Fuzzy approximation via grid point sampling and singular value decomposition," IEEE Trans. on System, Man and Cybernetics, Dec. 1997, vol. 27, pp. 933-95 1. Y. Yam and C. T. Yang, "Singular value-based fuzzy approximator: a case study", Int. Panel Conference Soft Intelligent Computing, Budapest, Hungary, Sept. 30-Oct. 3, 1996, pp. 305-312. Yam Y., P. Baranyi, C. T. Yang, "Reduction of Fuzzy Rule Base Via Singular Value Decomposition," IEEE Trans. on Fuzzy Systems, Vol. 7, No. 2, Apr., 1999, pp.120-132. Baranyi P., Y. Yang, "Singular value-based approximation with non-singleton support," Seventh Int. IFSA World Congress, Prague, June 25-29, 1997, pp. 127-132. Baranyi, Y. Yam, "Singular Value-Based Approximation with Takagi-Sugeno Type Fuzzy Rule Base", IEEE Int. Conf. on Fuzzy Systems, 1997, pp. 265-270. Baranyi P., K.F. Lei, Y. Yam, "complexity Reduction of Singleton Based Neuro-fuzzy Algorithm," accepted to IEEE Conf on System, Man and Cybernetics 2000,2000,Nashville,Tennessee,USA, pp. 2503-2508 Tak6cs O., I. Nagy "Error bound of the SVD based neural networks," Proc. of the LFAC Symp. on Artificial Intelligence in Real Time Control, AIRTC 2000, Budapest, Hungary, Oct. 2-4,2000 pp. 139-145. Baranyi P., Y. Yam, .H. Hashimoto, P. Korondi, P. Michelberger. "Approximation and Complexity Reduction of the Generalized Neural Network", accepted to IEEE Trans. on Fuzzy Systems. Lei K., P. Baranyi, Y. Yam, "Complexity Minimalisation of Non-singleton Based Fuzzy-Neural Network", International Journal of Advanced Computational Intelligence, accepted Takbcs O., VBrkonyi-K6czy A. R., ,,Error-Bound for the Non-Exact SVDBased Complexity Reduction of the Generalized Type Hybrid Neural Networks with Non-Singleton Consequents", IEEE Instrumentation and Measurement Technology Conference, IMTC/2001, Budapest, Hungary, May 2 1-23, 200 1, pp. 1607-1613.
KOLMOGOROV’S SPLINE NETWORK BORIS IGELNIK, NEEL PARIKH Pegasus Technologies Inc., Mentor OH 44060, USA, E-mail:
[email protected] In this article a new neural-network architecture is discussed and developed. This architecture, based on the Kolmogorov’s Superposition Theorem and called the Kolmogorov’s Spline Network(KSN), utilizes more degrees of adaptation to data than currently used neuralnetwork architectures. The paper gives the theoretical justification for KSN. The main result is presented in the form of the Theorem favorably estimating the rate of convergence of the KSN to the target function compared to this rate for the currently used adaptive approximating schemes. The KSN utilizes the cubic spline technique of approximation both for the activation and the internal functions. The implementation and the training of the KSN using the Ensemble Approach are described.
Keywords: Kolmogorov ’ssuperposition theorem, cubic splines, ensemble of networks.
1
Introduction
The Kolmogorov’s Superposition Theorem (KST) provides the general and very compact representation of a multivariate continuous function through superposition and addition of univariate functions [l, 21. According to [ 2 ] , KST states that any function f of d variables xI,..., xd , defined and continuous in the standard unit hypercube, has the representation
with some continuous univariate function g depending onf, univariate functions constants &,...Ad,independent off, but possibly dependent on d. The right hand side of equation (1) is called the Kolmogorov’s network. Unlike a traditional neural-network and other adaptive modeling tools, which are approximate representations of arbitrary continuous functions, the Kolmogorov’s network formula (1) gives the exact representation of such a function by superposition of a finite number of univariate functions and additions. The number, (y,,...iydand
2d
+
[
1, of basis functions, qn(x) = g ~ ~ = , A (x8)] , v ,, in equation (1) is
independent of accuracy and of the function f and depends only on dimension of the problem, d. This is in contrast to traditional adaptive modeling tools where the number of basis functions depends on the error of approximation, E , and approaches infinity if E + 0 . From initial analysis it appears that the KST gives a very efficient and exact representation of a multivariate continuous function. The drawback,
107
108 B. Igelnik and
N. Parikh
however, is that the definition of the basis functions given in the proof of this theorem reveals that although the representation is compact, it is not efficient. The direct use of the theorem leads to an inordinate number of parameters needed for representation. Accordingly the shape of the basis functions, not only the scaling or shifting parameters, should be adjusted based on the data. Simply, the shape of basis functions should depend on a function f to be approximated. A growing number of articles on adaptive modeling with variable shape activation functions (for examples see [3 - 51) show an inclination in this direction. The use of splines [6] for activation functions seems very natural because it allows for parameterization of the function shape. It also allows for use of some existing advanced learning algorithms. We suggest an innovative spline one hidden layer feedforward network based on the KST. This network is called the Kolmogorov's Spline Network (KSN). The KSN, with N basis functions and network parameter W (a vector containing all parameters adjustable on the data), is designated as f;,w. The distinctive feature of the KSN is the use of splines not only for activation functions, but for the internal functions as well. The utilization of splines for internal functions provides an opportunity to have a continuous set of adaptive architectures, making a qualitatively new step in adaptive modeling. For training of the KSN the Ensemble Approach is suggested [7], which is a learning procedure perfectly suited for dealing with splines. The following is a short summary on cubic splines. Cubic splines naturally arise while approximating any univariate continuously twice-differentiable function, (T E C2[a,b] , defined on the interval [a,b] . Consider the
subdivision
of
[qb]
by
a
set
of
equally
spaced
points
to = a, ti = a + ih,i = 1,...n, where h = ( b - a )/ n . The cubic spline, s, is used for the
approximation of a function
CJ E
C2[a,b] and is defined so that on each interval
[ t i , t i + l ] ,=i O,l, ...n - 1 function s is a cubic polynomial. The values of s and s'
coincide with the corresponding values of CJ and of at the knots t i , i = 0,l ...n , while the values of s" and CJ" should coincide only at the knots t,,i = 1,...n -1 . It turns out that the task of finding such a spline has a unique solution. Cubic splines are defined through linear combinations of elementary cubic splines Bi,i = -1,0 ,...n + l . The elementary splines are independent of the function CJ . The unique solution for the arbitrary spline s, approximating a function (T E C2[a,b], is as follows
s ( t ) =x-lB, (t)+xoBo(t)+...+x,+,B,+,(t),
(2)
where the set of ( n + 3) values x-~,x~,...x~+~ is the unique solution of the set of ( n + 3) simultaneous linear equations
Ax=c
(3)
Kolmogorov’s Spline Network
109
r,
T
where x = ( x l , x 0,..., x n , x n + , ),C= (oA,oo ,..., on,oi
[-;o;
0 0 0 ...
1 4 1 0 0 0 ...
0 1 4 1 0 0 ...
.
A=
(4)
0 0 0 ...0
I
14 1 3 3 0 0 0 ...0-- 0 h h
The parameter Z , which characterizes the shape of a spline function, is called the shape parameter. The explicit solution of the system of equations ( 3 ) was derived, but omitted here because of the lack of space. Now we can define the KSN. The KSN is given by the following equation:
with the cubic spline univariate functions g,”,iyi,, defined on I numbers A, > 0,...Ad > 0,
2
c. A, d
(=I
= [0, 11 ,some
I 1 , and W = Z .
The Basic Theorem
For the KSN we have the following Theorem. Let the approximation
error
(.)I
be
defined
P ( f , f ~ , w ) = I l f - f ~ . w I I.El = m a ~ I f ( x ) - ~ ~ , w Then
continuously differentiable on I d , there exists the KSN,
as
for
any
the
distance
function
f,
fi,w, such that
P ( f , f i , w )= 0 ( 1 / N )
(6)
with the number of net parameters, P, satisfying the equation P=O(l/N3’2).
(7)
This statement favorably compares the KSN with the networks currently in use. Most of the existing neural networks f,,, [8, 91 provide the estimate of approximation error by the following equation
110 B. Igelnik and N . Parikh
Suppose N is the number of basis functions for KSN needed to have the error of approximation equal E > 0 . Comparison of (6) and (8) shows that the number of basis functions for existing networks, N. ,is N , their parameters,
)
= O( N 2 . Therefore
the number of
P . , is (9)
p. = O ( N 2 ) .
Obviously P, >> P for large values of N . For example if N = 100 then the e c a n be 10 times greater then P. Besides that, the class of functions to be approximated, satisfying (6) and (7), is broader than those in [8, 91, and the conditions of the theorem are always satisfied in practice. How was this theorem proved? The proof is technically rather difficult to explain in this paper, but the basic ideas are as follows. We used a combination of Kolmogorov’s ideas and the spline technique but unlike Kolmogorov, who concentrated on the number of basis functions and exact representation, we utilized approximating the number of adjustable parameters and concentrated on the number of basis functions. In the first part of the proof we built an intermediate network, approximating the target function, by employing Kolmogorov’s mappings with an arbitrary number of basis functions. In particular we have proved that there exist four-times differentiable continuous univariate functions gn,yni and a net
The complexity of the basis functions in this intermediate network was not a subject of our concern. In the second part, the intermediate network was further approximated by the KSN with a controlled number of parameters as follows. Define cubic splines g,”,n= 1, ...N approximating functions g, . We want to have the
error
is llg,
-
t,
of
approximation
1
g,” = O( 1/ N’ ) . Define
= m / M , m = O,l, ...M .
of
g,
knots
by for
g,” equal spline
that
O(l/N’),
interpolation
at
points
The error of spline interpolation for four times
continuously differentiable function is llg, -g:ll= O( 1/ M 4 ) [6]. That implies M
= O(
47).
(1 1)
Kolmogorov’s Spline Network
In a similar manner we v;,,n = 17...N,i = 1,...d approximating functions
111
define cubic splines v,, so that llty,,-t+vi,ll= O ( l / N 2 ) .
For estimation of the error of approximation of the function f by the N
KSN,fi (x) = zg: *=I
[:,z a , ~ ; , 1
(x,) ,one has
Making use of (10) and (1 1) yields
If
(x) - fi (x)) 5 0 (1/ N ) +
c N
O( 1/ N’ ) +
”=I
d
=~ A , O ( l / N = ZO ) ( l / N ’ ) . On the other hand functions g i , n = 1,...N
have
i=l
collectively bounded first derivative in [0,1], becauseffunction has continuous first derivative. That means there exists a constant L > 0 such that
l(g:l ( t ) l 5L for alln
= 1, ...N
and 0 < t 5 1 .
(12)
Indeed let xB and xc be two points from I d such that f ( x B) = tB,f ( x c) = t, . The definition of the functions g , imply g , ( t ) = f C t -ti3
t, I t I t, . Denote L = max lgradf E I d
Therefore IgL (t)15 L for t,
)I(.
]
for
. The conditions of the theorem imply L < co .
< t < t, . Making value of
7 , the length of the interval
where function g, is nonlinear, sufficiently small, and using the existence of the
112
B. Igelnik and N . Parikh
second derivative of g,
give lgL(t)l < L for O < t < I and n=1, ...N . Since
g, and g,” coincide on the nonlinear part of the graph of g: has continuous second derivative, and the value of 7 can be made sufficiently small, the inequality (12) is true. Thus
Therefore ( f ( x ) - f i (x)( = 0 (1 / N ) and
(If
-
I(
f i = 0 (1 / N ) . The number of
parameters P in the spline net can be estimated as P
=(d
+ 1)J“= 0 (N3’2)
completing the proof of the theorem. 3
The Ensemble Approach (EA)
EA is a method for training and generalizing the general class of one-hidden layer networks constituting linear expansions of basis functions (nodes), either fixed or adjustable shape, with internal adjustable parameters. Unlike the gradient methods of optimization for adjusting the parameters of a model, the task of optimization is divided into two stages in EA: the recursive linear regression (RLR) and the adaptive stochastic optimization (ASO). First an ensemble of nets with randomly chosen internal parameters is generated. Then for each net from the ensemble the values of the external parameters are optimized by RLR. After that the optimization of internal parameters is made through the stochastic search over the ensemble. Thus, the two global stages of optimization in EA are RLR and the stochastic search. The EA is very well suited to work with variable shape basis hnctions. All members of the ensemble of new nodes receive the numerical values of internal parameters independent of their origin. These can be parameters of shape, location, or scale. After receiving these numerical values, the process of training becomes universal for any type of node or architecture. Denote n-th basis function of the KSN as pn( x , u n ) ,where un is the vector-parameter of pn. Then the input to RLR is a numerical T x n design matrix
Qn
=
Kolmogorov’s Spline Network
113
where xl,xZ,...xT are the input elements of the training set. Additionally, the A S 0 operates on numerical values. It requires the end points of the intervals where the internal parameters are defined. All spline functions will be served with the same spline calculation module. Therefore the only difference between the learning of KSN by EA, compared with the task of learning traditional neural architectures already incorporated in EA, is that the learning algorithm needs the spline calculation model. The basic procedures of EA, RLR and AS0 remain unchanged.This is in sharp contrast with the popular Back Propagation, or other gradient based methods, when one should reprogram formulas for calculating gradient components for new architectures. For a large number of network parameters it is not only a programming problem but a computational problem as well. Nevertheless twice-differentiability of splines allows for use of gradient or second order learning optimization procedures if needed.
Conclusions
4
This paper lays down the theoretical foundation for innovative neural network architecture of superior efficiency. Future work will concentrate on practical implementation and testing this architecture in real applications and on developing methods of automatic choice of the shape parameter.
References 1. A. N. Kolmogorov, ”On the representation of continuous functions of many
2.
3.
4.
5.
6.
variables by superposition of continuous functions of one variable and addition,“ Translations American Mathematical Society, 2(28), 55-59, 1963. G. G. Lorentz, M. von Golitschek, Y. Makovoz, Constructive Approximation. Advanced Problems. New York: Springer, 1996. Uncini, L. Vecci, P. Campolucci, and F. Piazza, “Complex-valued neural networks with adaptive spline activation function for digital radio links nonlinear equalization,” IEEE Transactions on Signal Processing 47, 505-5 14, 1999. S. Guamieri, F. Piazza, and A. Uncini, “Multilayer feedforward networks with adaptive spline activation function,” IEEE Transactions on Neural Networks, 10,672-683, 1999. Igelnik, Some new adaptive architectures for learning, generalization, and visualization of m