The Pattern Recognition Basis of Artificial Intelligence

by Tveter, Donald

• ISBN13: 9780818677960
• ISBN10: 0818677961
• Edition: 1st
• Format: Paperback
• Copyright: 1998-03-13
• Publisher: Wiley-IEEE Computer Society Pr

Summary

This book takes the viewpoint that plain symbol processing techniques have little hope of reproducing the depth and breadth of capabilities found in human beings. The book introduces new foundational principles to AI: connectionist/neural networking methods, case based and memory based methods and picture processing.The book looks at methods of AI as different ways of doing pattern recognition. One way to do pattern recognition is to compare a problem to stored cases. At the other end of the spectrum, Classical Symbol Processing AI compresses cases down to a small set of rules and then works only with this condensed knowledge. In between these two extremes are neural networks, especially backprop type networks. As much as possible the book compares these three basic methods using actual AI programs.The structure of the book starts at the bottom of human abilities with vision and other simple pattern recognition abilities and moves on to the higher levels of problem solving and game playing and finally to the level of natural language and understanding of the world. At the higher levels more complex computer architectures are needed that include methods for structuring thoughts.The book is organized in a manner in which the reader will get an intuitive feeling for the principles of AI. Throughout the book applications of basic principles are demonstrated by examining some classic AI programs in detail. The book can serve as a text for juniors, seniors and first year graduate students in Computer Science or Psychology and includes sample problems and data for exercises and a list of frequently asked questions.

Author Biography

Donald Tveter is the author of The Pattern Recognition Basis of Artificial Intelligence, published by Wiley.

Table of Contents

Preface	xiii
1 Artificial Intelligence	1	(22)
1.1 Artificial Intelligence and Intelligence	1	(4)
1.1.1 Intelligence	1	(1)
1.1.2 Thinking	2	(1)
1.1.3 The Turing Test for Thinking	3	(1)
1.1.4 The Chinese Room Argument	3	(1)
1.1.5 Consciousness and Quantum Mechanics	4	(1)
1.1.6 Dualism	4	(1)
1.2 Association	5	(4)
1.3 Neural Networking	9	(3)
1.3.1 Artificial Neural Networks	9	(2)
1.3.2 Biological Neural Networks	11	(1)
1.4 Symbol Processing	12	(4)
1.5 Heuristic Search	14	(2)
1.6 The Problems with AI	16	(1)
1.7 The New Proposals	16	(4)
1.7.1 Real Numbers	17	(1)
1.7.2 Picture Processing	18	(1)
1.7.3 Memories	18	(1)
1.7.4 Quantum Mechanics	19	(1)
1.8 The Organization of the Book	20	(1)
1.9 Exercises	20	(3)
2 Pattern Recognition I	23	(32)
2.1 A Simple Pattern Recognition Algorithm	23	(3)
2.2 A Short Description of the Neocognitron	26	(7)
2.2.1 Detecting Short Lines	27	(2)
2.2.2 A Typical Neocognitron	29	(1)
2.2.3 Training the Neocognitron	29	(4)
2.2.4 Some Results	33	(1)
2.3 Recognizing Words	33	(10)
2.4 Expanding the Pattern Recognition Hierarchy	43	(5)
2.4.1 Hearing	43	(1)
2.4.2 Higher Levels	44	(1)
2.4.3 The Hierarchy	45	(3)
2.4.4 On the Hierarchy	48	(1)
2.5 Additional Perspective	48	(2)
2.5.1 Other Systems	48	(1)
2.5.2 Realism	49	(1)
2.5.3 Bigger Problems	49	(1)
2.6 Exercises	50	(5)
3 Pattern Recognition II	55	(48)
3.1 Mathematics, Pattern Recognition, and the Linear Pattern Classifier	55	(4)
3.1.1 The Linear Pattern Classifier	55	(4)
3.1.2 ADALINEs and MADELINEs	59	(1)
3.1.3 Perceptrons	59	(1)
3.2 Separating Nonlinearly Separable Classes	59	(4)
3.2.1 The Nearest Neighbor Algorithm	59	(1)
3.2.2 Learning Vector Quantization Methods	60	(3)
3.3 Hopfield Networks	63	(11)
3.3.1 The Hopfield Network	63	(2)
3.3.2 Storing Patterns	65	(2)
3.3.3 The Boltzman Machine	67	(5)
3.3.4 Pattern Recognition	72	(1)
3.3.5 Harmony	72	(1)
3.3.6 Comparison with Human Thinking	72	(2)
3.4 Back-Propagation	74	(7)
3.4.1 History	74	(1)
3.4.2 The Network	74	(2)
3.4.3 Computing the Weights	76	(3)
3.4.4 Speeding Up Back-Propagation	79	(1)
3.4.5 Dealing with Local Minima	80	(1)
3.4.6 Using Back-Propagation to Train Hopfield/Boltzman Networks	80	(1)
3.5 Pattern Recognition and Curve Fitting	81	(3)
3.5.1 Pattern Recognition as Curve Fitting	81	(3)
3.5.2 Approximating Real-Valued Functions	84	(1)
3.5.3 Overfitting	84	(1)
3.6 Associative Memory and Generalization	84	(8)
3.6.1 Associative Memory	86	(4)
3.6.2 Local and Distributed Representations	90	(1)
3.6.3 Reasoning within a Network	91	(1)
3.7 Applications of Back-Propagation	92	(5)
3.7.1 Interpreting Sonar Returns	93	(1)
3.7.2 Reading Text	94	(1)
3.7.3 Speech Recognition	95	(1)
3.7.4 Detecting Bombs	95	(1)
3.7.5 Economic Analysis	96	(1)
3.7.6 Learning to Drive	97	(1)
3.7.7 DNA Analysis	97	(1)
3.8 Additional Perspective	97	(1)
3.9 Exercises	98	(5)
4 Rule-Based Methods	103	(44)
4.1 Introduction	103	(1)
4.2 Some Elementary Prolog	103	(12)
4.2.1 Stating Facts	104	(1)
4.2.2 Syntax	104	(1)
4.2.3 Asking Questions	105	(3)
4.2.4 Rules	108	(1)
4.2.5 Recursion	109	(1)
4.2.6 List Processing	110	(4)
4.2.7 Other Predicates	114	(1)
4.3 Rules and Basic Rule Interpretation Methods	115	(5)
4.3.1 A Small Rule-Based System	116	(2)
4.3.2 Forward Chaining	118	(1)
4.3.3 Backward Chaining	119	(1)
4.4 Conflict Resolution	120	(4)
4.5 More Sophisticated Rule Interpretation	124	(3)
4.5.1 Dealing with Incomplete Data by Asking Questions	124	(1)
4.5.2 Other Activation Functions	125	(1)
4.5.3 Uncertain Input	126	(1)
4.5.4 Extra Facilities for Rule Interpreters	126	(1)
4.6 The Famous Expert Systems	127	(12)
4.6.1 DENDRAL	127	(2)
4.6.2 MYCIN	129	(2)
4.6.3 PROSPECTOR	131	(2)
4.6.4 ACE	133	(1)
4.6.5 XCON	133	(6)
4.7 Learning Rules in SOAR	139	(2)
4.7.1 A Searching Example	139	(1)
4.7.2 The Power Law of Practice	140	(1)
4.8 Rules versus Networks	141	(2)
4.9 Exercises	143	(4)
5 Logic	147	(20)
5.1 Standard Form and Clausal Form	147	(4)
5.2 Basic Inference Rules	151	(3)
5.2.1 Inference Rules	151	(1)
5.2.2 Clauses with Variables	152	(2)
5.3 Controlling Search	154	(5)
5.3.1 The Problem with Blind Searching	154	(1)
5.3.2 Proof by Contradiction	155	(1)
5.3.3 The Set-of-Support Strategy	156	(1)
5.3.4 Weighting	157	(1)
5.3.5 Prolog's Strategy	158	(1)
5.4 An Example Using Otter	159	(4)
5.4.1 The Problem	159	(4)
5.5 The Usefulness of Predicate Calculus	163	(1)
5.6 Other Reasoning Methods	163	(1)
5.7 Exercises	164	(3)
6 Complex Architectures	167	(26)
6.1 The Basic Human Architecture	167	(2)
6.2 Flow of Control	169	(3)
6.3 The Virtual Symbol Processing Machine Proposal	172	(1)
6.4 Mental Representation and Computer Representation	173	(4)
6.4.1 A Problem with Symbolic Representation	173	(2)
6.4.2 Symbol Grounding as a Solution	175	(1)
6.4.3 Structure and Operations on Structures	176	(1)
6.5 Storing Sequential Events	177	(4)
6.5.1 The Symbolic Solution	177	(1)
6.5.2 Neural Solutions	178	(3)
6.6 Structuring Individual Thoughts	181	(6)
6.6.1 The Symbolic Methods	181	(2)
6.6.2 Neural Methods	183	(4)
6.7 Frames and Scripts	187	(3)
6.7.1 Schemas and Frames	187	(2)
6.7.2 Scripts	189	(1)
6.8 Exercises	190	(3)
7 Case-Based and Memory-Based Reasoning	193	(20)
7.1 Condensed versus Uncondensed Knowledge	193	(6)
7.1.1 Arguments For Condensed Knowledge	195	(1)
7.1.2 Arguments Against Condensed Knowledge	196	(1)
7.1.3 Problems with Condensed Representations	197	(2)
7.2 Memory-Based Reasoning	199	(5)
7.2.1 A Simple Example	199	(1)
7.2.2 MBRtalk	200	(1)
7.2.3 A HERBIE Solution to Reading	201	(1)
7.2.4 JOHNNY	202	(2)
7.2.5 PACE	204	(1)
7.3 Case-Based Reasoning	204	(7)
7.3.1 Case-Based Reasoning in People	204	(3)
7.3.2 CHEF	207	(4)
7.4 Other Case-Based Programs	211	(1)
7.5 Exercises	211	(2)
8 Problem Solving and Heuristic Search	213	(24)
8.1 The 8-Puzzle	213	(7)
8.1.1 The Blind Search Methods	214	(2)
8.1.2 Heuristic Searches	216	(4)
8.1.3 Other Methods	220	(1)
8.2 A Geometry Theorem Prover	220	(8)
8.3 Symbolic Integration and Heuristic Search	228	(6)
8.3.1 SAINT	228	(3)
8.3.2 A Symbolic Program to Learn Integration	231	(1)
8.3.3 A Partial Back-Propagation Solution	231	(3)
8.4 Other Heuristic Programs	234	(1)
8.5 Exercises	235	(2)
9 Game Playing	237	(24)
9.1 General Game Playing Techniques	237	(7)
9.1.1 Minimax	237	(3)
9.1.2 More Sophisticated Searching Methods	240	(1)
9.1.3 Using Experience	241	(3)
9.2 Checkers	244	(8)
9.2.1 Rote Learning	245	(2)
9.2.2 Generalization Learning	247	(3)
9.2.3 Samuel's Later Work	250	(1)
9.2.4 Chinook	251	(1)
9.3 Backgammon	252	(6)
9.3.1 Berliner's BKG Program	252	(1)
9.3.2 Backgammon using Back-Propagation	253	(2)
9.3.3 A Second Back-Propagation Approach	255	(2)
9.3.4 Temporal Difference Learning	257	(1)
9.4 Exercises	258	(3)
10 Natural Language Processing	261	(64)
10.1 Formal Languages	262	(5)
10.2 The Transition Network Grammar	267	(9)
10.2.1 A Simple Transition Network	267	(2)
10.2.2 A Prolog Implementation	269	(2)
10.2.3 A Neural Analog	271	(4)
10.2.4 Syntax is not Enough	275	(1)
10.3 Semantics-Based Methods	276	(11)
10.3.1 Semantic Grammar	276	(1)
10.3.2 Conceptual Dependency Notation	277	(10)
10.4 Scripts and Short Stories	287	(5)
10.5 A Neural-Network-Based Approach	292	(6)
10.6 Defining Words by the Way they are Used	298	(4)
10.7 A Recurrent Network for Sentences	302	(3)
10.8 Neural-Based Scripts	305	(5)
10.9 Learning the Past Tense of Verbs	310	(7)
10.9.1 Over-Regularization	312	(1)
10.9.2 The Rumelhart and McClelland Network	312	(3)
10.9.3 The Classical Rule-Based Model	315	(2)
10.9.4 A Hybrid Model	317	(1)
10.10 Other Positions on Language	317	(2)
10.11 Exercises	319	(6)
Afterword	325	(2)
A Appendix A	327	(4)
A.1 A Derivation of Back-Propagation	327	(4)
A.1.1 The Delta Rule	327	(2)
A.1.2 The Generalized Delta Rule, or Back-Propagation	329	(2)
Glossary	331	(6)
Bibliography	337	(20)
Index	357