Table of Contents
Preface v
Chapter 1 Introduction to Expert Systems 1
1.1 Artificial Intelligence 1
1.2 Basic Expert System Concepts 2
1.2.1 The knowledge base 4
1.2.2 The inference engine 5
1.2.3 Input/output interface and explanation 6
1.2.4 Uncertainty in the knowledge base 6
1.3 Knowledge Engineering 8
1.3.1 Knowledge elicitation and representation 8
1.3.2 The knowledge acquisition bottleneck 9
1.4 First and Second Generation Expert Systems 10
1.4.1 Evolution from the first to the second generation 10
1.4.2 Development as a modeling activity, knowledge level, generic tasks 11
1.4.3 Second generation expert systems 13
1.5 Advantages and Disadvantages of Expert Systems 14
1.6 Expert System Shells, Programming Environments 15
1.7 Expert System Applications 17
References 20
Chapter 2 Theoretical Foundations 23
2.1 Introduction 23
2.2 Propositional Logic 24
2.3 First Order Predicate Calculus and Predicate Logic 25
2.3.1 First order predicate calculus 25
2.3.2 First order predicate logic, functions 27
2.3.3 Well formed formulas 29
2.4 Inference 30
2.5 Proof by Refutation Resolution 32
2.5.1 Conversion of axioms into clause form 32
2.5.2 Unification 36
2.5.2.1 Finding the most general unifier 37
2.5.2.2 Unification examples 38
2.5.3 Resolution proofs by refutation 38
2.6 Green's Answer Term 41
2.7 Knowledge Acquisition Bottleneck 43
2.8 Search Strategies 43
2.9 Non-Monotonic Reasoning 45
2.10 The Closed World Assumption, Horn Clauses 49
2.11 Forward, Backward Chaining 50
Summary 53
Exercises 53
References 54
Chapter 3 Knowledge Representation 57
3.1 Representation of Knowledge 57
3.2 Rules 60
3.2.1 Production systems and the Rete matching algorithm 61
3.2.1.1 Production systems 61
3.2.1.2 The Rete matching algorithm 62
3.3 Semantic Networks 64
3.3.1 Definitions, examples 64
3.3.2 Semantic nets in Prolog* 66
3.3.3 Advantages of semantic networks 67
3.3.4 Exception and multiple inheritance 68
3.3.4.1 Evidential reasoning 69
3.3.5 Conceptual graphs 69
3.4 Frames 71
3.4.1 Basic concepts 71
3.4.2 Frames in Prolog* 74
3.5 Object Oriented Systems 76
3.5.1 Object oriented concepts, examples 76
3.5.2 Object oriented paradigm in Prolog* 79
3.5.3 An application 82
3.6 Petri Nets 86
3.6.1 Definitions 86
3.6.2 Petri Net model for prepositional calculus 88
3.6.3 Petri Net model for predicate calculus 90
3.7 Hybrid Representations 91
3.8 The Frame Problem 93
3.9 Semantic Primitives 94
Summary 94
Exercises 95
References 96
Chapter 4 Knowledge Acquisition, Verification and Validation 99
4.1 The Expert System Development Process 99
4.2 Knowledge Elicitation 100
4.2.1 The elicitation process and the bottleneck 100
4.2.1.1 Procedural versus declarative knowledge 101
4.2.2 Interviews 102
4.2.3 Repertory Grids 104
4.2.3.1 Repertory grid analysis using NICOD 107
4.2.3.2 Repertory grid analysis using clustering 108
4.2.4 Protocol analysis 112
4.3 The Knowledge Level 113
4.3.1 Separation of domain and control knowledge, the knowledge level 113
4.3.2 Neomycin 116
4.4 Explanation in Second Generation Expert Systems 116
4.5 The Problem Solving Methods and Generic Tasks Approach 118
4.5.1 Introduction and analysis 118
4.5.2 Knowledge acquisition tools for the generic tasks, methods approach 119
4.6 Verification and Validation 123
4.6.1 Introduction 123
4.6.2 Verification 124
4.6.2.1 Inconsistencies 124
4.6.2.2 Completeness 127
4.6.2.3 Verification using Petri Nets 128
4.6.3 Validation 131
4.6.3.1 Validation of MYCIN 131
4.6.3.2 Testing 132
Summary 133
Exercises 134
References 134
Chapter 5 Uncertainty 141
5.1 Uncertainty in Expert Systems 141
5.2 The Bayesian Approach 142
5.2.1 Bayes' Theorem 143
5.2.2 An example of applying the Bayesian approach 144
5.2.3 Weaknesses 146
5.3 Certainty Factors 146
5.3.1 Definitions 146
5.3.2 Updating the CFs of hypotheses for disjunctive evidence 148
5.3.2.1 Example on disjunctive updating of CFs 148
5.3.3 Updating the CFs of hypotheses for conjunctive evidence 149
5.3.3.1 Example of CF propagation in a rule base 150
5.3.4 Comparison of the CF and Bayesian approaches 151
5.3.5 Certainty factors using Prolog* 152
5.4 Dempster-Shafer Theory of Evidence 156
5.4.1 Basic concepts of DS theory 156
5.4.2 Updating belief, the combination rule 158
5.4.3 An example on the Dempster-Shafer approach 158
5.4.4 Comparisons 160
5.5 Fuzzy Sets and Fuzzy Logic 162
5.5.1 Introduction 162
5.5.2 Fuzzy set theory 163
5.5.3 Fuzzy implications 167
5.5.4 Rules with relational conditions 170
5.5.5 Example 171
5.5.6 Fuzzy logic in Prolog* 173
5.5.7 Fuzzy logic programming environments 175
5.6 Bayesian Belief Networks 175
5.6.1 Weaknesses of probabilistic approaches 175
5.6.2 Belief networks, definitions 177
5.6.3 Propagating probabilities through a tree belief network 179
Summary 181
Exercises 181
References 184
Chapter 6 Machine Learning 187
6.1 Introduction 187
6.1.1 Inductive, analogical and explanation based learning 188
6.2 Decision Trees and the Ids Algorithm 190
6.2.1 The ID3 algorithm 191
6.2.2 Entropy 195
6.2.3 Using entropy to optimize the classification tree 197
6.3 Learning from Noisy Data 199
6.3.1 Construction time pruning 200
6.3.2 Post pruning 201
6.4 Version Space Search and Conceptual Clustering 203
6.5 Case Based Reasoning 208
6.6 Evolutionary Machine Learning 209
6.6.1 Genetic algorithms 209
6.6.2 Classifier systems 213
6.6.3 Deriving or improving rule sets with genetic algorithms, BEAGLE 214
6.6.4 Deriving a knowledge base for insurance underwriting using genetic algorithms 216
Summary 218
Exercises 219
References 219
Chapter 7 Neural Networks 223
7.1 Introduction 223
7.2 Artificial Neural Networks 224
7.2.1 The artificial neuron 224
7.2.2 ANN topologies 226
7.2.3 Activation functions 226
7.2.4 Learning algorithms 227
7.3 Perceptron 228
7.4 Hidden Layers, Multilayer Perceptrons 230
7.5 Hopfield Networks 231
7.5.1 Hopfield learning algorithm 233
7.5.2 Net evolution 233
7.5.3 Energy function 233
7.5.4 Stochastic Hopfield networks 234
7.5.5 Solving optimization problems with Hopfield nets 235
7.6 Multilayered Nets and Backpropagation 238
7.6.1 Backpropagation learning algorithm 240
7.6.2 An example on backpropagation 240
Summary 242
Exercises 242
References 243
Chapter 8 Hybrid Expert Systems 245
8.1 Introduction 245
8.2 Macie: A Connectionist Expert System 246
8.3 Generating Rules from Neural Nets 250
8.4 A Hybrid Expert System for Investment Advising 252
8.4.1 System architecture 253
8.4.2 The neural network module 254
8.4.3 Neural network training using genetic algorithms 255
8.4.4 An investment advice session with the expert system 256
8.5 A Hybrid Expert System for Insurance Policy Underwriting 258
Summary 259
References 260
Appendix A An Introduction to Prolog* 263
A.1 Prolog Basics 263
A.2 The Prolog Inference Engine 267
A.3 Negation 271
A.4 Arithmetic 272
A.4.1 The assignment operator 273
A.4.2 The comparison operator 274
A.4.3 Recursive arithmetic 274
A.5 Lists 275
A.5.1 Some basic list processing functions 277
A.6 Extra-Logical Predicates 282
A.6.1 The cut 282
A.6.2 Other extra-logical predicates 285
A.6.2.1 Built in predicates 285
A.6.2.2 Updating the knowledge base 287
A.7 A Prolog question answering system 288
A.8 Procedural Programs in Prolog 290
A.8.1 If-then-else 290
A.8.2 Linked lists 291
A.8.3 Stacks 292
A.8.4 Queues 292
A.8.5 Loops 292
A.8.6 Graph search algorithms 293
A.8.7 The farmer, fox, goose and grain 295
A.8.8 Towers of Hanoi 297
A.9 Optimization of Prolog Programs 297
A.9.1 Optimization of sequential processing in Prolog 298
A.9.2 Parallel logic programs and languages 299
Summary 300
Exercises 301
References 302
Appendix B The Expert System Shell Exsys 305
B.1 Validation Testing 305
B.2 Linkable Object Modules and Command Language 305
B.3 Rules 306
B.4 Creating and Editing a Rule Base 308
B.5 Implementing Mycin's Confidence Factors Approach in Exsys 312
Appendix C Prolog and Expert System Products 317
I Internet Access 317
II Expert system shells 317
III Prolog compilers* 325
Index 327
