Intelligent Systems


Intelligent Systems: A Modern Approach (2011) .. by Grosan & Abraham


Contents

1 Evolution of Modern Computational Intelligence … 1
1.1 Introduction … 1
1.2 Roots of Artificial Intelligence … 3
1.3 Modern Artificial Intelligence … 7
1.4 Metamodern AI … 11

2 Problem Solving by Search … 13
2.1 Introduction … 13
2.2 What Is Search? … 13
2.3 Tree Based Search … 16
2.3.1 Terminology … 16
2.4 Graph Search … 17
2.5 Search Methods Classification … 19
2.6 Uninformed Search Methods … 19
2.6.1 Breadth First Search … 20
2.6.2 Depth First Search … 24
2.6.3 Backtracking Search … 26
2.6.4 Depth Bounded (Limited) Depth First Search … 27
2.6.5 Iterative Deepening Depth First Search … 29
2.6.6 Branch and Bound (or Uniform Cost Search) … 32
2.6.7 Bidirectional Search … 34
2.7 Performance Evaluation of the Uninformed Search Strategies … 36
2.7.1 Remarks and Discussions … 36
2.7.2 Repeated States … 38
Summary … 38
References … 40
Verification Questions … 42
Exercises … 43

3 Informed (Heuristic) Search … 53
3.1 Introduction … 53
3.2 Heuristics … 54
3.3 Best First Search … 56
3.4 Greedy Search … 57
3.5 A* Search … 63
3.6 Comparisons and Remarks … 70
3.7 A* Variants … 70
3.7.1 Iterative Deepening A* (IDA*) … 71
3.7.2 Simplified Memory Bounded A* (SMA*) … 71
3.7.3 Recursive Best-First Search (RBFS) … 75
3.7.4 D* Algorithm … 75
3.7.5 Beam Search … 76
Summary … 76
References … 77
Verification Questions … 79
Exercises … 79

4 Iterative Search … 83
4.1 Introduction … 83
4.2 Hill Climbing … 84
4.3 Simulated Annealing … 92
4.4 Tabu Search … 98
4.5 Means Ends … 103
4.6 Summary … 104
References … 105
Verification Questions … 107
Exercises … 108

5 Adversarial Search … 111
5.1 Introduction … 111
5.2 MIN-MAX Algorithm … 112
5.2.1 Designing the Utility Function … 113
5.3 Alpha-beta Pruning … 119
5.4 Comparisons and Discussions … 123
Summary … 123
References … 125
Verification Questions … 125
Exercises … 126

6 Knowledge Representation and Reasoning … 131
6.1 Introduction … 131
6.2 Propositional Logic … 132
6.2.1 Logical Operators … 133
6.2.2 Terminology … 135
6.2.3 Inference … 137
6.2.3.1 Introduction … 138
6.2.3.2 Elimination … 138
6.3 First Order Predicate Logic (FOPL) … 139
6.3.1 Predicate Calculus … 139
6.3.2 FOPL Alphabet … 140
6.4 Resolution in Propositional Logic and FOPL … 142
6.4.1 Resolution in Propositional Logic … 143
6.4.2 Resolution in FOPL … 144
Summaries … 145
References … 146
Verification Questions … 146
Exercises … 147

7 Rule-Based Expert Systems … 149
7.1 Introduction … 149
7.2 Elements of a Rule-Based System … 150
7.2.1 Rules … 151
7.2.1.1 Rules Classification … 152
7.3 Structure of a Rule-Based Expert System … 154
7.4 Types of Rule-Based Expert Systems … 156
7.4.1 Forward Chaining Systems … 158
7.4.2 Backward Chaining Systems … 165
7.4.3 Forward Chaining or Backward Chaining? Which One Should Apply? … 172
7.5 Conflict Resolution … 172
7.6 Benefits and Capabilities of Rule Based Expert Systems … 175
7.7 Types of Expert Systems … 176
7.8 Examples of Expert Systems … 177
Summaries … 179
References … 180
Verification Questions … 181
Exercises … 181

8 Managing Uncertainty in Rule Based Expert Systems … 187
8.1 What Is Uncertainty and How to Deal With It? … 187
8.2 Bayesian Theory … 189
8.2.1 Classical Probability Theory … 189
8.2.2 Bayes’ Rules … 191
8.2.3 Bayesian Reasoning … 193
8.2.4 Bayesian Networks … 196
8.2.4.1 Inference in Bayesian Networks … 198
8.2.4.2 Variable Ordering in Bayesian Networks … 200
8.2.4.3 Facts about Bayesian Networks … 201
8.3 Certainty Factors … 202
8.3.1 Calculating Certainty Factors … 204
8.3.1.1 Measure of Belief … 204
8.3.1.2 Measure of Disbelief … 204
8.3.2 Combining Certainty Factors … 205
8.3.2.1 Multiple Rules Providing Evidence for the Same Conclusion … 205
8.3.2.2 Multiple Rules with Uncertain Evidence for the Same Conclusion … 206
Summaries … 212
References … 213
Verification Questions … 214
Exercises … 214

9 Fuzzy Expert Systems … 219
9.1 Introduction … 219
9.2 Fuzzy Sets … 220
9.2.1 Representing Fuzzy Sets … 223
9.2.2 Operations with Fuzzy Sets … 228
9.2.2.1 Complement … 228
9.2.2.2 Containment … 229
9.2.2.3 Intersection … 230
9.2.2.4 Union … 230
9.2.2.5 Equality … 231
9.2.2.6 Algebraic Product … 231
9.2.2.6 Algebraic Sum … 231
9.2.3 Proprieties of Fuzzy Sets … 231
9.2.3.1 Associativity … 232
9.2.3.2 Distributivity … 232
9.2.3.3 Commutativity … 232
9.2.3.4 Transitivity … 233
9.2.3.5 Idempotency … 233
9.2.3.6 Identity … 233
9.2.3.7 Involution … 234
9.2.3.7 De Morgan’s Laws … 234
9.2.4 Hedges … 235
9.3 Fuzzy Rules … 238
9.4 Fuzzy Inference … 239
9.4.1 Fuzzyfication … 240
9.4.2 Rule Evaluation and Inference … 243
9.4.3 Defuzzyfication … 246
9.4.4 Mamdani Fuzzy Model … 247
9.4.5 Sugeno Fuzzy Model … 251
9.4.6 Tsukamoto Fuzzy Model … 254
Summaries … 256
References … 257
Verification Questions … 258
Exercises … 259

10 Machine Learning … 261
10.1 Introduction … 261
10.2 Terminology … 263
10.3 Learning Steps … 264
10.4 Learning Systems Classification … 265
10.4.1 Classification Based on Goal, Tasks, Target Function … 265
10.4.2 Classification Based on the Model … 266
10.4.3 Classification Based on the Learning Rules … 266
10.4.4 Classification Based on Experience … 266
10.5 Machine Learning Example … 267
References … 268

11 Decision Trees … 269
11.1 Introduction … 269
11.2 Building a Decision Tree … 271
11.2.1 Top-Down Induction of Decision Tree … 271
11.2.2 How to Chose the Best Attribute? … 273
11.3 Overfitting in Decision Trees … 276
11.3.1 Pruning a Decision Tree … 278
11.4 Decision Trees Variants … 278
Summaries … 279
References … 280
Verification Questions … 280

12 Artificial Neural Networks … 281
12.1 Introduction … 281
12.2 Similarities between Biological and Artificial Neural Networks … 282
12.3 Neural Networks Types … 284
12.3.1 Layered Feed-Forward Network … 284
12.3.2 The Perceptron … 285
12.3.3 Feedforward Radial Basis Function (RBF) Network … 285
12.3.4 Recurrent Networks … 285
12.3.4.1 Hopfield Neural Network … 285
12.3.4.2 Simple Recurrent Network (SRN) Elman Style … 286
12.3.4.3 Simple Recurrent Network (SRN) Jordan Style … 286
12.3.5 Self-Organizing Maps … 286
12.4 The Perceptron … 286
12.4.1 Activation Functions … 287
12.4.2 How the Perceptron Learns a Task? … 290
12.4.2.1 The Perceptron Rule … 292
12.4.2.2 Delta Rule … 293
12.4.3 Example: Perceptron for OR Function … 294
12.4.4 Limitations of the Perceptron … 299
12.5 Multi-layer Perceptron … 299
12.5.1 Backpropagation Learning Algorithm … 303
12.5.1.1 Backpropagation Learning: Network with One Hidden Layer … 303
12.5.1.2 Backpropagation Learning: Network with Two Hidden Layers … 310
12.5.2 Relationship between Dataset, Number of Weights and Classification Accuracy … 316
12.5.3 Improving Efficiency of Backpropagation Learning … 317
Summaries … 318
References … 319
Verification Questions … 321
Exercises … 321

13 Advanced Artificial Neural Networks … 325
13.1 Introduction … 325
13.2 Jordan Network … 325
13.3 Elman Network … 327
13.4 Hopfield Network … 328
13.5 Self Organizing Networks … 329
13.5.1 Hebb Networks … 329
13.5.2 Self Organizing Maps … 332
13.5.2.1 Kohonen Self Organizing Maps: The Algorithm … 334
13.6 Neocognitron … 335
13.7 Application of Neural Networks … 340
Summaries … 342
References … 343
Verification Questions … 344

14 Evolutionary Algorithms … 345
14.1 Introduction … 345
14.2 How to Build an Evolutionary Algorithm? … 347
14.2.1 Designing a Representation … 348
14.2.2 Initializing the Population … 348
14.2.3 Evaluating an Individual … 349
14.2.4 Selection Mechanism … 350
14.2.5 Designing Suitable Variation Operators … 350
14.2.5.1 Mutation Operator … 350
14.2.5.2 Crossover (Recombination) Operator … 350
14.2.6 Designing a Replacement Scheme … 351
14.2.7 Designing a Way to Stop the Algorithm … 351
14.3 Genetic Algorithms … 351
14.3.1 Representing the Individuals … 352
14.3.1.1 Binary Representation … 352
14.3.1.2 Real Representation … 353
14.3.1.3 Integer Representation … 354
14.3.1.4 Order-Based Representation … 354
14.3.2 Initializing the Population … 355
14.3.3 Selection Mechanisms … 356
14.3.3.1 Tournament Selection … 356
14.3.3.2 Fitness Proportional Selection … 357
14.3.3.3 Roulette Wheel Selection … 357
14.3.3.4 Stochastic Universal Sampling … 359
14.3.3.5 Rank Based Selection … 360
14.3.3.6 Local Selection … 361
14.3.4 Variation Operators … 363
14.3.4.1 Crossover or Recombination … 363
14.3.4.2 Mutation … 374
14.3.5 Population Models … 379
14.3.6 Survivor Selection and Reinsertion … 380
14.3.6.1 Local Reinsertion … 380
14.3.6.2 Global Reinsertion … 380
14.3.7 The Basic Genetic Algorithm … 381
Summaries … 382
References … 382
Verification Questions … 384
Exercises … 385

15 Evolutionary Metaheuristics … 387
15.1 Introduction … 387
15.2 Representation … 388
15.3 Mutation … 388
15.3.1 Uncorrelated Mutation with One ?? … 389
15.3.2 Uncorrelated Mutation with n ??’s … 389
15.3.3 Correlated Mutation … 390
15.4 Recombination … 390
15.5 Controlling the Evolution: Survival Selection … 391
15.5.1 P, C Strategy … 391
15.5.2 P + C Strategy … 391
15.5.3 P/R, C Strategy … 391
15.5.4 P/R + C Strategy … 392
15.6 Evolutionary Programming … 392
15.6.1 Representation … 392
15.6.2 Mutation … 392
15.6.3 Survival Selection … 393
15.7 Genetic Programming … 393
15.7.1 Representation … 394
15.7.2 Variation Operators … 397
15.7.2.1 Mutation … 397
15.7.2.2 Recombination … 397
15.7.2.3 Branch Duplication … 397
15.7.3 Fitness Function … 397
15.7.4 Parent Selection … 398
15.7.5 Survival Selection … 398
15.7.6 GP Variants … 399
15.7.6.1 Linear Genetic Programming … 399
15.7.6.2 Multi-expression Programming … 400
15.7.6.3 Gene Expression Programming … 402
15.7.6.4 Grammatical Evolution … 402
15.7.7 GP Applications … 405
Summaries … 405
References … 406
Verification Questions … 406

16 Swarm Intelligence … 409
16.1 Introduction … 409
16.2 Particle Swarm Optimization … 411
16.2.1 Parameters of PSO … 413
16.3 Ant Colonies Optimization … 415
16.3.1 Ant System … 416
Summaries … 418
References … 421
Verification Questions … 422
Exercises … 422

17 Hybrid Intelligent Systems … 423
17.1 Introduction … 423
17.2 Models of Hybrid Computational Intelligence Architectures … 425
17.2.1 Stand-Alone Systems … 425
17.2.2 Transformational Hybrid Intelligent System … 425
17.2.3 Hierarchical Hybrid Intelligent System … 426
17.2.4 Integrated Intelligent System … 427
17.3 Neuro-fuzzy Systems … 427
17.3.1 Cooperative and Concurrent Neuro-fuzzy Systems … 427
17.3.2 Fused Neuro Fuzzy Systems … 428
17.3.3 Discussions … 436
17.4 Evolutionary Fuzzy Systems … 436
17.4.1 Evolutionary – Neuro – Fuzzy (EvoNF) Systems … 438
17.5 Evolutionary Neural Networks (EANN) … 439
17.5.1 General Framework for Evolutionary Neural Networks … 440
17.5.2 Evolutionary Search of Connection Weights … 441
17.5.3 Evolutionary Search of Architectures … 442
17.5.4 Evolutionary Search of Learning Rules … 443
17.5.5 Meta Learning Evolutionary Artificial Neural Networks … 444
17.6 Hybrid Evolutionary Algorithms … 446
Summaries … 448
References … 448
Verification Questions … 450
Exercises … 450