Preface......Page 6
Acknowledgements......Page 10
Contents......Page 12
About the Author......Page 26
Acronyms......Page 27
1.1 Introduction......Page 29
1.2 The Turing Test......Page 31
1.3 Goals of AI......Page 32
1.4 Roots of AI......Page 33
1.4.2 Logic and Mathematics......Page 34
1.4.4 Psychology and Cognitive Science......Page 35
1.4.6 Evolution......Page 36
1.6 Techniques Used in AI......Page 37
1.7 Sub-fields of AI......Page 38
1.7.2 Natural Language Processing......Page 39
1.7.4 Engineering and Expert Systems......Page 40
1.7.6 Models of Brain and Evolution......Page 41
1.9 Physical Symbol System Hypothesis......Page 42
1.9.2 Symbols and Physical Symbol Systems......Page 43
1.10 Considerations for Knowledge Representation......Page 44
1.10.2 Objective of Knowledge Representation......Page 45
1.10.4 Practical Aspects of Representations......Page 46
1.10.5 Components of a Representation......Page 47
1.12 Summary......Page 48
References......Page 51
2.1 Introduction......Page 52
2.2 Argumentation Theory......Page 54
2.4 Propositional Logic......Page 55
2.4.1 Interpretation of Formulas......Page 58
2.4.2 Logical Consequence......Page 59
2.4.4 Semantic Tableau......Page 60
2.5 Reasoning Patterns......Page 62
2.5.2 Model-Based Reasoning......Page 65
2.6 Proof Methods......Page 66
2.6.2 Resolution......Page 67
2.6.3 Properties of Inference Rules......Page 68
2.7 Nonmonotonic Reasoning......Page 69
2.8 Hilbert and the Axiomatic Approach......Page 70
2.8.1 Roots and Early Stages......Page 71
2.8.2 Axiomatics and Formalism......Page 72
2.9 Summary......Page 74
References......Page 76
3.1 Introduction......Page 78
3.2 Representation in Predicate Logic......Page 79
3.3 Syntax and Semantics......Page 82
3.4 Conversion to Clausal Form......Page 84
3.5 Substitutions and Unification......Page 86
3.5.1 Composition of Substitutions......Page 87
3.5.2 Unification......Page 88
3.6 Resolution Principle......Page 89
3.6.2 Proof by Resolution......Page 91
3.7 Complexity of Resolution Proof......Page 92
3.8 Interpretation and Inferences......Page 93
3.8.1 Herbrand's Universe......Page 95
3.8.2 Herbrand's Theorem......Page 98
3.8.3 The Procedural Interpretation......Page 99
3.9 Most General Unifiers......Page 103
3.9.1 Lifting......Page 105
3.9.2 Unification Algorithm......Page 106
3.10 Unfounded Sets......Page 108
3.11 Summary......Page 110
References......Page 115
4.1 Introduction......Page 116
4.2 An Overview of RBS......Page 118
4.3.1 Forward Chaining Algorithm......Page 120
4.3.2 Conflict Resolution......Page 122
4.3.3 Efficiency in Rule Selection......Page 124
4.4 Backward Chaining......Page 125
4.4.1 Backward Chaining Algorithm......Page 126
4.5 Forward Versus Backward Chaining......Page 127
4.7 Other Systems of Reasoning......Page 129
4.7.1 Model-Based Systems......Page 130
4.7.2 Case-Based Reasoning......Page 131
4.8 Summary......Page 132
References......Page 136
5.1 Introduction......Page 137
5.2 Logic Programming......Page 138
5.3 Interpretation of Horn Clauses in Rule-Chaining......Page 140
5.4 Logic Versus Control......Page 142
5.4.1 Data Structures......Page 143
5.4.2 Procedure-Call Execution......Page 145
5.4.3 Backward Versus Forward Reasoning......Page 146
5.4.4 Path Finding Algorithm......Page 147
5.5 Expressing Control Information......Page 148
5.6 Running Simple Programs......Page 150
5.7 Some Built-In Predicates......Page 155
5.8 Recursive Programming......Page 156
5.9 List Manipulation......Page 158
5.11 Backtracking, Cuts and Negation......Page 161
5.12 Efficiency Considerations for Prolog Programs......Page 163
5.13 Summary......Page 164
References......Page 167
6.1 Introduction......Page 168
6.2 Taxonomic Reasoning......Page 169
6.3 Techniques for Commonsense Reasoning......Page 172
6.4 Ontologies......Page 173
6.5 Ontology Structures......Page 175
6.5.1 Language and Reasoning......Page 176
6.5.2 Levels of Ontologies......Page 177
6.5.3 WordNet......Page 178
6.5.5 Sowa's Ontology......Page 179
6.6.1 Categories and Objects......Page 181
6.6.4 Object-Oriented Analysis......Page 182
6.7 Ontological Engineering......Page 183
6.8.1 Action, Situation, and Objects......Page 184
6.8.2 Formalism......Page 185
6.8.3 Formalizing the Notions of Context......Page 188
6.9 Nonmonotonic Reasoning......Page 190
6.10 Default Reasoning......Page 191
6.10.1 Notion of a Default......Page 193
6.10.2 The Syntax of Default Logic......Page 194
6.10.3 Algorithm for Default Reasoning......Page 195
6.11 Summary......Page 197
References......Page 201
7.1 Introduction......Page 203
7.2 Semantic Networks......Page 204
7.2.1 Syntax and Semantics of Semantics Networks......Page 206
7.2.3 Semantic Nets and Natural Language Processing......Page 208
7.3 Conceptual Graphs......Page 209
7.4 Frames and Reasoning......Page 212
7.4.1 Inheritance Hierarchies......Page 213
7.4.2 Slots Terminology......Page 214
7.4.3 Frame Languages......Page 215
7.4.4 Case Study......Page 216
7.5 Description Logic......Page 219
7.5.1 Definitions and Sentence Structures......Page 220
7.5.2 Concept Language......Page 221
7.5.3 Architecture for mathcalDL Knowledge Representation......Page 225
7.5.4 Value Restrictions......Page 226
7.5.5 Reasoning and Inferences......Page 227
7.6 Conceptual Dependencies......Page 228
7.6.1 The Parser......Page 231
7.6.2 Conceptual Dependency and Inferences......Page 233
7.6.3 Scripts......Page 234
7.6.4 Conceptual Dependency Versus Semantic Nets......Page 235
7.7 Summary......Page 236
References......Page 239
8.1 Introduction......Page 240
8.2 Representation of Search......Page 241
8.3 Graph Search Basics......Page 242
8.4 Complexities of State-Space Search......Page 243
8.5.1 Breadth-First Search......Page 245
8.5.2 Depth-First Search......Page 247
8.5.3 Analysis of BFS and DFS......Page 248
8.5.4 Depth-First Iterative Deepening Search......Page 250
8.5.5 Bidirectional Search......Page 251
8.6.1 Depth-First Searches......Page 252
8.7 Problem Formulation for Search......Page 253
8.8 Summary......Page 255
References......Page 259
9.1 Introduction......Page 261
9.2 Heuristic Approach......Page 263
9.3 Hill-Climbing Methods......Page 264
9.4 Best-First Search......Page 266
9.4.1 GBFS Algorithm......Page 267
9.4.2 Analysis of Best-First Search......Page 269
9.5.1 Search Algorithm A......Page 271
9.5.2 The Evaluation Function......Page 273
9.5.3 Analysis of A Search......Page 275
9.6 Comparison of Heuristics Approaches......Page 276
9.7 Simulated Annealing......Page 278
9.8 Genetic Algorithms......Page 281
9.8.1 Exploring Different Structures......Page 282
9.8.4 GA Applications......Page 283
9.9 Summary......Page 285
References......Page 293
10.1 Introduction......Page 295
10.2 CSP Applications......Page 296
10.3 Representation of CSP......Page 298
10.3.1 Constraints in CSP......Page 299
10.3.2 Variables in CSP......Page 301
10.4 Solving a CSP......Page 302
10.4.1 Synthesizing the Constraints......Page 303
10.4.2 An Extended Theory for Synthesizing......Page 305
10.5 Solution Approaches to CSPs......Page 307
10.6 CSP Algorithms......Page 309
10.6.2 Backtracking......Page 310
10.6.3 Efficiency Considerations......Page 314
10.7 Propagating of Constraints......Page 315
10.7.2 Degree of Heuristics......Page 316
10.8 Cryptarithmetics......Page 317
10.9 Theoretical Aspects of CSPs......Page 320
10.10 Summary......Page 321
References......Page 324
11.1 Introduction......Page 325
11.2 Classification of Games......Page 327
11.3 Game Playing Strategy......Page 328
11.4 Two-Person Zero-Sum Games......Page 329
11.5 The Prisoner's Dilemma......Page 330
11.6 Two-Player Game Strategies......Page 332
11.8 Games of Imperfect Information......Page 334
11.9 Nash Arbitration Scheme......Page 336
11.10 n-Person Games......Page 338
11.11 Representation of Two-Player Games......Page 339
11.12 Minimax Search......Page 340
11.13 Tic-tac-toe Game Analysis......Page 343
11.14 Alpha-Beta Search......Page 346
11.14.1 Complexities Analysis of Alpha-Beta......Page 348
11.14.2 Improving the Efficiency of Alpha-Beta......Page 349
11.15 Sponsored Search......Page 350
11.17 Summary......Page 351
References......Page 357
12.1 Introduction......Page 358
12.2 Foundations of Probability Theory......Page 360
12.3 Conditional Probability and Bayes Theorem......Page 361
12.4.1 Constructing a Bayesian Network......Page 365
12.4.2 Bayesian Network for Chain of Variables......Page 366
12.4.3 Independence of Variables......Page 368
12.4.4 Propagation in Bayesian Belief Networks......Page 369
12.4.5 Causality and Independence......Page 372
12.4.6 Hidden Markov Models......Page 374
12.4.7 Construction Process of Bayesian Networks......Page 375
12.5 DempsterβShafer Theory of Evidence......Page 377
12.5.1 DempsterβShafer Rule of Combination......Page 378
12.5.2 DempsterβShafer Versus Bayes Theory......Page 379
12.6 Fuzzy Sets, Fuzzy Logic, and Fuzzy Inferences......Page 382
12.6.1 Fuzzy Composition Relation......Page 384
12.6.2 Fuzzy Rules and Fuzzy Graphs......Page 386
12.6.3 Fuzzy Graph Operations......Page 388
12.7 Summary......Page 390
References......Page 394
13.1 Introduction......Page 395
13.2 Types of Machine Learning......Page 397
13.3 Discipline of Machine Learning......Page 399
13.4 Learning Model......Page 402
13.5.1 Supervised Learning......Page 403
13.6 Inductive Learning......Page 404
13.6.1 Argument-Based Learning......Page 407
13.6.2 Mutual Online Concept Learning......Page 409
13.6.3 Single-Agent Online Concept Learning......Page 411
13.6.4 Propositional and Relational Learning......Page 412
13.6.5 Learning Through Decision Trees......Page 413
13.7 Discovery-Based Learning......Page 416
13.8 Reinforcement Learning......Page 418
13.8.1 Some Functions in Reinforcement Learning......Page 419
13.8.2 Supervised Versus Reinforcement Learning......Page 420
13.9 Learning and Reasoning by Analogy......Page 421
13.10 A Framework of Symbol-Based Learning......Page 425
13.11 Explanation-Based Learning......Page 426
13.12 Machine Learning Applications......Page 428
13.13 Basic Research Problems in Machines Learning......Page 429
13.14 Summary......Page 430
References......Page 433
14.1 Introduction......Page 434
14.2 Classification......Page 435
14.3 Support Vector Machines......Page 437
14.3.1 Learning Pattern Recognition from Examples......Page 438
14.3.2 Maximum Margin Training Algorithm......Page 440
14.4 Predicting Structured Objects Using SVM......Page 441
14.5 Working of Structural SVMs......Page 443
14.6 k-Nearest Neighbor Method......Page 444
14.6.1 k-NN Search Algorithm......Page 445
14.7 Naive Bayes Classifiers......Page 447
14.8 Artificial Neural Networks......Page 449
14.8.1 Error-Correction Rules......Page 452
14.8.2 Boltzmann Learning......Page 453
14.8.4 Competitive Learning Rules......Page 454
14.8.5 Deep Learning......Page 455
14.9.1 Learning Task......Page 456
14.9.2 IBL Algorithm......Page 457
14.10 Summary......Page 458
References......Page 461
15.1 Introduction......Page 463
15.2 Automated Planning......Page 465
15.3 The Basic Planning Problem......Page 466
15.3.1 The Classical Planning Problem......Page 467
15.3.2 Agent Types......Page 468
15.4 Forward Planning......Page 471
15.5 Partial-Order Planning......Page 472
15.6 Planning Languages......Page 473
15.6.1 A General Planning Language......Page 474
15.6.2 The Operation of STRIPS......Page 475
15.7 Planning with Propositional Logic......Page 476
15.7.1 Encoding Action Descriptions......Page 478
15.8 Planning Graphs......Page 479
15.9 Hierarchical Task Network Planning......Page 480
15.10 Multiagent Planning Systems......Page 482
15.11 Multiagent Planning Techniques......Page 483
15.11.3 Decentralized Planning......Page 484
15.12 Summary......Page 485
References......Page 488
16.1 Introduction......Page 489
16.2 Classification of Agents......Page 490
16.3 Multiagent Systems......Page 493
16.3.2 Multiagent Framework......Page 494
16.3.3 Multiagent Interactions......Page 495
16.4 Basic Architecture of Agent System......Page 497
16.5 Agents' Coordination......Page 498
16.5.1 Sharing Among Cooperative Agents......Page 499
16.5.3 Dynamic Coalition Formation......Page 500
16.5.4 Iterated Prisoner's Dilemma Coalition Model......Page 501
16.5.5 Coalition Algorithm......Page 503
16.6 Agent-Based Approach to Software Engineering......Page 504
16.7 Agents that Buy and Sell......Page 505
16.8 Modeling Agents as Decision Maker......Page 506
16.8.2 Model Structure......Page 507
16.8.3 Preferences......Page 510
16.9 Agent Communication Languages......Page 511
16.9.1 Semantics of Agent Programs......Page 513
16.9.2 Description Language for Interactive Agents......Page 515
16.10 Mobile Agents......Page 517
16.11 Social Level View of Multiagents......Page 518
16.12 Summary......Page 520
References......Page 522
17.1 Introduction......Page 524
17.2 Perspectives of Data Mining......Page 526
17.3 Goals of Data Mining......Page 528
17.4 Evolution of Data Mining Algorithms......Page 529
17.4.1 Transactions Data......Page 530
17.4.3 Representation of Text-Based Data......Page 531
17.5.1 Prediction Methods......Page 532
17.5.2 Clustering......Page 535
17.6 Data Clustering and Cluster Analysis......Page 536
17.6.1 Applications of Clustering......Page 538
17.6.2 General Utilities of Clustering......Page 539
17.6.4 Clustering Process......Page 540
17.6.5 Pattern Representation and Feature Extraction......Page 542
17.7 Clustering Algorithms......Page 543
17.7.1 Similarity Measures......Page 544
17.7.2 Nearest Neighbor Clustering......Page 545
17.7.3 Partitional Algorithms......Page 546
17.8 Comparison of Clustering Techniques......Page 548
17.9 Classification......Page 551
17.10 Association Rule Mining......Page 554
17.11 Sequential Pattern Mining Algorithms......Page 558
17.11.2 Notations for Sequential Pattern Mining......Page 559
17.11.3 Typical Sequential Pattern Mining......Page 560
17.11.4 Apriori-Based Algorithm......Page 561
17.12 Scientific Applications in Data Mining......Page 566
17.13 Summary......Page 568
References......Page 572
18.1 Introduction......Page 573
18.2 Retrieval Strategies......Page 576
18.3 Boolean Model of IR System......Page 577
18.4 Vector Space Model......Page 579
18.5.1 Index Construction......Page 581
18.5.2 Index Maintenance......Page 584
18.6 Probabilistic Retrieval Model......Page 585
18.7 Fuzzy Logic-Based IR......Page 586
18.8 Concept-Based IR......Page 590
18.8.1 Concept-Based Indexing......Page 591
18.8.2 Retrieval Algorithms......Page 594
18.9 Automatic Query Expansion in IR......Page 595
18.9.1 Working of AQE......Page 599
18.9.2 Related Techniques for Query Processing......Page 601
18.10.1 Representation of Document and Query......Page 603
18.10.2 Bayes Probabilistic Inference Model......Page 604
18.10.3 Bayes Inference Algorithm......Page 605
18.11 Semantic IR on the Web......Page 608
18.12 Distributed IR......Page 611
18.13 Summary......Page 613
References......Page 617
19.1 Introduction......Page 619
19.2 Progress in NLP......Page 622
19.3 Applications of NLP......Page 624
19.4.1 Syntax Analysis......Page 625
19.4.3 Discourse Analysis......Page 627
19.5 Grammars......Page 628
19.5.2 Phrase Structure Grammars......Page 629
19.6.1 Chomsky Hierarchy of Grammars......Page 632
19.6.2 Transformational Grammars......Page 633
19.6.3 Ambiguous Grammars......Page 635
19.7 Prepositions in Applications......Page 636
19.8 Natural Language Parsing......Page 637
19.8.1 Parsing with CFGs......Page 638
19.8.2 Sentence-Level Constructions......Page 640
19.8.3 Top-Down Parsing......Page 641
19.8.4 Probabilistic Parsing......Page 643
19.9.1 Document Preprocessing......Page 646
19.9.2 Syntactic Parsing and Semantic Interpretation......Page 647
19.9.3 Discourse Analysis......Page 648
19.10 NL-Question Answering......Page 649
19.10.1 Data Redundancy Based Approach......Page 650
19.10.2 Structured Descriptive Grammar-Based QA......Page 651
19.11 Commonsense-Based Interfaces......Page 652
19.11.2 Components of Commonsense Reasoning......Page 654
19.11.3 Representation Structures......Page 656
19.12.1 NLTK......Page 658
19.12.2 NLTK Examples......Page 659
19.13 Summary......Page 661
References......Page 665
20.1 Introduction......Page 666
20.2 Automatic Speech Recognition Resources......Page 668
20.3 Voice Web......Page 669
20.4 Speech Recognition Algorithms......Page 671
20.5.2 Language Model......Page 673
20.5.3 Acoustic Models......Page 674
20.6 Automatic Speech Recognition Tools......Page 677
20.6.1 Automatic Speech Recognition Engine......Page 678
20.6.2 Tools for ASR......Page 679
20.7 Summary......Page 681
References......Page 683
21.1 Introduction......Page 684
21.2 Machine Vision Applications......Page 686
21.3 Basic Principles of Vision......Page 687
21.4 Cognition and Classification......Page 690
21.5 From Image-to-Scene......Page 692
21.5.2 Inversion by Restricting the Problem Domain......Page 693
21.5.3 Inversion by Acquiring Additional Images......Page 694
21.6.1 Low-Level Vision......Page 695
21.6.2 Local Edge Detection......Page 696
21.6.3 Middle-Level Vision......Page 698
21.6.4 High-Level Vision......Page 700
21.7 Indexing and Geometric Hashing......Page 702
21.8 Object Representation and Tracking......Page 704
21.9 Feature Selection and Object Detection......Page 707
21.9.1 Object Detection......Page 709
21.10 Supervised Learning for Object Detection......Page 711
21.11 Axioms of Vision......Page 713
21.11.2 Source Axioms......Page 714
21.11.4 Construct Axioms......Page 715
21.12 Computer Vision Tools......Page 716
21.13 Summary......Page 718
References......Page 721
BookmarkTitle:......Page 722
Index......Page 723