About the Book
The SP theory - which has been under development since 1987 - is a radical synthesis of ideas across human perception, cognition and development, artificial intelligence, computer science, theoretical linguistics, neuroscience, mathematics, logic, and epistemology. It is a theory of information processing in all kinds of system, both natural and artificial, a new paradigm for information processing which incorporates principles of minimum length encoding pioneered by Solomonoff, Kolmogoroff, Wallace, Rissanen, and others, but which is built from new foundations and differs at a fundamental level from any existing theory or system. The SP theory has a dual role. It is a theory of engineering, the basis for a proposed SP machine with applications in artificial intelligence and in data storage and retrieval. At the same time, it is a theory of information processing in brains and nervous systems both at an abstract level and at the more concrete level of neurons and neural processing.
The theory and its applications - which are the subject of this book - will be of interest to a wide range of researchers, academics, professionals and students in computer science (especially artificial intelligence), cognitive science, human perception, cognition and development, theoretical and computational linguistics, neuroscience, mathematics, logic, and the philosophy of mind and language. The SP theory has a sound mathematical framework but the ideas are presented in a way that will be accessible to a wide audience, without being overburdened with mathematical equations or logical notations. After the Introduction, Chapter 2 describes ideas and observations on which the SP theory is founded, that have provided some motivation for the development of the theory, or are simply part of the background thinking for the theory. Chapter 3 describes the theory itself and one of the main computer models in which the theory is embodied. And Chapter 4 shows how the SP theory can model the operation of a universal Turing machine and describes advantages of the theory compared with earlier theories of computing.
In Chapters that follow, applications of the SP theory are explored: in the processing of natural languages, in pattern recognition and information retrieval, in various kinds of probabilistic reasoning, in planning and problem solving, in the unsupervised learning of new knowledge (with a second computer model), and in the interpretation of concepts in mathematics and logic. Further chapters describe how the abstract theory may be realised with neural structures and neural processes, how the SP theory relates to some current themes in cognitive psychology and how the SP theory and projected 'SP machine' may be developed in the future. An Appendix describes the version of dynamic programming that forms the core of the SP computer models, with significant advantages compared with standard forms of dynamic programming.
Table of Contents:
1 Introduction 1 1.1 Beginnings ... 2 1.2 Goals of the research and potential benefits . . 3 1.3 Creating a good theory ... 5 1.4 The SP theory and related research ... 15 1.5 How to read this book ...17 1.6 Presentation ... 18 2 Computing, Cognition and IC 20 2.1 Introduction ... 20 2.2 Information, redundancy, compression of information and probabilities ... 20 2.3 Coding for reduced redundancy in computing and cognition ... 43 2.4 Searching for redundancy in computing and cognition ... 60 2.5 Conclusion ... 69 3 The SP Theory 72 3.1 Introduction ... 72 3.2 The overall framework ...72 3.3 Representation of knowledge ...75 3.4 Multiple alignments ...79 3.5 Coding and the evaluation of an alignment in terms of compression ...92 3.6 Realisation of the three compression techniques in the SP system ...98 3.7 Calculation of probabilities associated with alignments ... 100 3.8 Decompression by compression ... 104 3.9 Outline of computer models ... 106 3.10 Detailed description of SP61 ...108 3.11 Conclusion ...119 4 The SP Theory as a Theory of Computing 120 4.1 Introduction ... 120 4.2 Universal Turing machine and Post canonical system ...121 4.3 SP and the operation of a Post canonical system ...125 4.4 Discussion ... 132 4.5 Conclusion ... 139 5 Natural Language Processing 140 5.1 Introduction ... 140 5.2 Ambiguities and recursion ...142 5.3 Syntactic dependencies in French ... 148 5.4 Dependencies in the syntax of English auxiliary verbs ... 153 5.5 Cross serial dependencies ...164 5.6 The integration of syntax with semantics ... 166 5.7 Conclusion ... 172 6 Recognition and Retrieval 173 6.1 Introduction ... 173 6.2 Scene analysis, fuzzy pattern recognition, best-match information retrieval and multiple alignment ...174 6.3 Best-match information retrieval ... 177 6.4 Class-inclusion relations, part-whole relations and inheritance of attributes ... 179 6.5 Medical diagnosis1 ... 186 6.6 Conclusion ... 198 7 Probabilistic Reasoning 200 7.1 Introduction ... 200 7.2 Probabilistic reasoning, multiple alignment and information compression ... 202 7.3 One-step 'deductive' reasoning ... 206 7.4 Abductive reasoning ...208 7.5 Reasoning with probabilistic decision networks and decision trees 210 7.6 Reasoning with 'rules' ... 217 7.7 Nonmonotonic reasoning and reasoning with default values ... 220 7.8 Explaining away 'explaining away': the SP system as an alternative to Bayesian networks . 224 7.9 Causal diagnosis ... 236 7.10 Reasoning which is not supported by evidence . .243 7.11 Conclusion ...245 8 Planning and Problem Solving 247 8.1 Introduction ... 247 8.2 Planning ... 247 8.3 Solving geometric analogy problems ... 254 8.4 Conclusion ... 256 9 Unsupervised Learning 257 9.1 Introduction ... 257 9.2 SP70 ... 258 9.3 Evaluation of the model ...273 9.4 Examples ... 276 9.5 Discussion ... 281 9.6 Conclusion ... 289 10 Mathematics and Logic 290 10.1 Introduction ...290 10.2 Preliminaries ... 291 10.3 Information compression and structures in mathematics and logic ...296 10.4 Information compression and processes in mathematics and logic ...308 10.5 Discussion ...318 10.6 Conclusion ...324 11 Neural Mechanisms 325 11.1 Introduction ...325 11.2 Global considerations: arguments from biology and engineering ... 326 11.3 Neural realisation of the SP concepts ... 329 11.4 Discussion ...338 11.5 Comparison with alternative proposals ... 366 11.6 Conclusion ...374 12 SP and Cognitive Psychology 378 12.1 Introduction ...378 12.2 Recognition and categorisation ...379 12.3 Reasoning ... 387 12.4 Associative learning ...392 12.5 'Rules', 'similarity' and artificial grammar learning ...395 12.6 Language learning ... 401 12.7 Analogy and structure mapping ... 408 12.8 Conclusion ...412 13 Future Developments and Applications 413 13.1 Introduction ...413 13.2 Development of the theory ... 413 13.3 Development of an 'SP' machine ...424 13.4 Applications of the SP theory and machine ... 428 13.5 Conclusion ...445 14 Conclusion 446 14.1 Is the SP theory a good theory? ... 446 A Finding Good Matches 449 A.1 The hit structure ...449 A.2 Probabilities ...452 A.3 Discussion of the search technique ... 455 A.4 Computational complexity ... 456 B The SP Computer Models 460
About the Author :
Dr Gerry Wolff PhD CEng MBCS (CITP), is Director of CognitionResearch.org.uk. Previously, he held academic posts in the School of Informatics, University of Wales, Bangor, the Department of Psychology, University of Dundee, and the University Hospital of Wales, Cardiff. He has held a Research Fellowship with IBM in Winchester, UK, and he has worked for four years as a Software Engineer with Praxis Systems plc in Bath, UK. His first degree at Cambridge University was in Natural Sciences (specialising in Experimental Psychology) and his PhD at the University of Wales, Cardiff, was in the area of Cognitive Science. He is a Chartered Engineer and Member of the British Computer Society (Chartered IT Professional). Since 1987 his research has focussed on the development of the SP theory. Previously, his main research interests were in developing computer models of language learning. He has numerous publications in a wide range of journals, collected papers and conference proceedings. Further information may be found at: www.cognitionresearch.org.uk.
