Fundamentals of Artificial Intelligence

Preface
Acknowledgements
Contents
About the Author
Acronyms
1 Introducing Artificial Intelligence
	1.1 Introduction
	1.2 The Turing Test
	1.3 Goals of AI
	1.4 Roots of AI
		1.4.1 Philosophy
		1.4.2 Logic and Mathematics
		1.4.3 Computation
		1.4.4 Psychology and Cognitive Science
		1.4.5 Biology and Neuroscience
		1.4.6 Evolution
	1.5 Artificial Consciousness
	1.6 Techniques Used in AI
	1.7 Sub-fields of AI
		1.7.1 Speech Processing
		1.7.2 Natural Language Processing
		1.7.3 Planning
		1.7.4 Engineering and Expert Systems
		1.7.5 Fuzzy Systems
		1.7.6 Models of Brain and Evolution
	1.8 Perception, Understanding, and Action
	1.9 Physical Symbol System Hypothesis
		1.9.1 Formal System
		1.9.2 Symbols and Physical Symbol Systems
		1.9.3 Formal Logic
		1.9.4 The Stored Program Concept
	1.10 Considerations for Knowledge Representation
		1.10.1 Defining the Knowledge
		1.10.2 Objective of Knowledge Representation
		1.10.3 Requirements of a Knowledge Representation
		1.10.4 Practical Aspects of Representations
		1.10.5 Components of a Representation
	1.11 Knowledge Representation Using Natural Language
	1.12 Summary
	References
2 Logic and Reasoning Patterns
	2.1 Introduction
	2.2 Argumentation Theory
	2.3 Role of Knowledge
	2.4 Propositional Logic
		2.4.1 Interpretation of Formulas
		2.4.2 Logical Consequence
		2.4.3 Syntax and Semantics of an Expression
		2.4.4 Semantic Tableau
	2.5 Reasoning Patterns
		2.5.1 Rule-Based Reasoning
		2.5.2 Model-Based Reasoning
	2.6 Proof Methods
		2.6.1 Normal Forms
		2.6.2 Resolution
		2.6.3 Properties of Inference Rules
	2.7 Nonmonotonic Reasoning
	2.8 Hilbert and the Axiomatic Approach
		2.8.1 Roots and Early Stages
		2.8.2 Axiomatics and Formalism
	2.9 Summary
	References
3 First Order Predicate Logic
	3.1 Introduction
	3.2 Representation in Predicate Logic
	3.3 Syntax and Semantics
	3.4 Conversion to Clausal Form
	3.5 Substitutions and Unification
		3.5.1 Composition of Substitutions
		3.5.2 Unification
	3.6 Resolution Principle
		3.6.1 Theorem Proving Formalism
		3.6.2 Proof by Resolution
	3.7 Complexity of Resolution Proof
	3.8 Interpretation and Inferences
		3.8.1 Herbrand\'s Universe
		3.8.2 Herbrand\'s Theorem
		3.8.3 The Procedural Interpretation
	3.9 Most General Unifiers
		3.9.1 Lifting
		3.9.2 Unification Algorithm
	3.10 Unfounded Sets
	3.11 Summary
	References
4 Rule Based Reasoning
	4.1 Introduction
	4.2 An Overview of RBS
	4.3 Forward Chaining
		4.3.1 Forward Chaining Algorithm
		4.3.2 Conflict Resolution
		4.3.3 Efficiency in Rule Selection
		4.3.4 Complexity of Preconditions
	4.4 Backward Chaining
		4.4.1 Backward Chaining Algorithm
		4.4.2 Goal Determination
	4.5 Forward Versus Backward Chaining
	4.6 Typical RB System
	4.7 Other Systems of Reasoning
		4.7.1 Model-Based Systems
		4.7.2 Case-Based Reasoning
	4.8 Summary
	References
5 Logic Programming and Prolog
	5.1 Introduction
	5.2 Logic Programming
	5.3 Interpretation of Horn Clauses in Rule-Chaining
	5.4 Logic Versus Control
		5.4.1 Data Structures
		5.4.2 Procedure-Call Execution
		5.4.3 Backward Versus Forward Reasoning
		5.4.4 Path Finding Algorithm
	5.5 Expressing Control Information
	5.6 Running Simple Programs
	5.7 Some Built-In Predicates
	5.8 Recursive Programming
	5.9 List Manipulation
	5.10 Arithmetic Expressions
	5.11 Backtracking, Cuts and Negation
	5.12 Efficiency Considerations for Prolog Programs
	5.13 Summary
	References
6 Real-World Knowledge Representation and Reasoning
	6.1 Introduction
	6.2 Taxonomic Reasoning
	6.3 Techniques for Commonsense Reasoning
	6.4 Ontologies
	6.5 Ontology Structures
		6.5.1 Language and Reasoning
		6.5.2 Levels of Ontologies
		6.5.3 WordNet
		6.5.4 Axioms and First-Order Logic
		6.5.5 Sowa\'s Ontology
	6.6 Reasoning Using Ontologies
		6.6.1 Categories and Objects
		6.6.2 Physical Decomposition of Categories
		6.6.3 Measurements
		6.6.4 Object-Oriented Analysis
	6.7 Ontological Engineering
	6.8 Situation Calculus
		6.8.1 Action, Situation, and Objects
		6.8.2 Formalism
		6.8.3 Formalizing the Notions of Context
	6.9 Nonmonotonic Reasoning
	6.10 Default Reasoning
		6.10.1 Notion of a Default
		6.10.2 The Syntax of Default Logic
		6.10.3 Algorithm for Default Reasoning
	6.11 Summary
	References
7 Networks-Based Representation
	7.1 Introduction
	7.2 Semantic Networks
		7.2.1 Syntax and Semantics of Semantics Networks
		7.2.2 Human Knowledge Creation
		7.2.3 Semantic Nets and Natural Language Processing
		7.2.4 Performance
	7.3 Conceptual Graphs
	7.4 Frames and Reasoning
		7.4.1 Inheritance Hierarchies
		7.4.2 Slots Terminology
		7.4.3 Frame Languages
		7.4.4 Case Study
	7.5 Description Logic
		7.5.1 Definitions and Sentence Structures
		7.5.2 Concept Language
		7.5.3 Architecture for mathcalDL Knowledge Representation
		7.5.4 Value Restrictions
		7.5.5 Reasoning and Inferences
	7.6 Conceptual Dependencies
		7.6.1 The Parser
		7.6.2 Conceptual Dependency and Inferences
		7.6.3 Scripts
		7.6.4 Conceptual Dependency Versus Semantic Nets
	7.7 Summary
	References
8 State Space Search
	8.1 Introduction
	8.2 Representation of Search
	8.3 Graph Search Basics
	8.4 Complexities of State-Space Search
	8.5 Uninformed Search
		8.5.1 Breadth-First Search
		8.5.2 Depth-First Search
		8.5.3 Analysis of BFS and DFS
		8.5.4 Depth-First Iterative Deepening Search
		8.5.5 Bidirectional Search
	8.6 Memory Requirements for Search Algorithms
		8.6.1 Depth-First Searches
		8.6.2 Breadth-First Searches
	8.7 Problem Formulation for Search
	8.8 Summary
	References
9 Heuristic Search
	9.1 Introduction
	9.2 Heuristic Approach
	9.3 Hill-Climbing Methods
	9.4 Best-First Search
		9.4.1 GBFS Algorithm
		9.4.2 Analysis of Best-First Search
	9.5 Heuristic Determination of Minimum Cost Paths
		9.5.1 Search Algorithm A*
		9.5.2 The Evaluation Function
		9.5.3 Analysis of A* Search
		9.5.4 Optimality of Algorithm A*
	9.6 Comparison of Heuristics Approaches
	9.7 Simulated Annealing
	9.8 Genetic Algorithms
		9.8.1 Exploring Different Structures
		9.8.2 Process of Innovation in Human
		9.8.3 Mutation Operator
		9.8.4 GA Applications
	9.9 Summary
	References
10 Constraint Satisfaction Problems
	10.1 Introduction
	10.2 CSP Applications
	10.3 Representation of CSP
		10.3.1 Constraints in CSP
		10.3.2 Variables in CSP
	10.4 Solving a CSP
		10.4.1 Synthesizing the Constraints
		10.4.2 An Extended Theory for Synthesizing
	10.5 Solution Approaches to CSPs
	10.6 CSP Algorithms
		10.6.1 Generate and Test
		10.6.2 Backtracking
		10.6.3 Efficiency Considerations
	10.7 Propagating of Constraints
		10.7.1 Forward Checking
		10.7.2 Degree of Heuristics
	10.8 Cryptarithmetics
	10.9 Theoretical Aspects of CSPs
	10.10 Summary
	References
11 Adversarial Search and Game Theory
	11.1 Introduction
	11.2 Classification of Games
	11.3 Game Playing Strategy
	11.4 Two-Person Zero-Sum Games
	11.5 The Prisoner\'s Dilemma
	11.6 Two-Player Game Strategies
	11.7 Games of Perfect Information
	11.8 Games of Imperfect Information
	11.9 Nash Arbitration Scheme
	11.10 n-Person Games
	11.11 Representation of Two-Player Games
	11.12 Minimax Search
	11.13 Tic-tac-toe Game Analysis
	11.14 Alpha-Beta Search
		11.14.1 Complexities Analysis of Alpha-Beta
		11.14.2 Improving the Efficiency of Alpha-Beta
	11.15 Sponsored Search
	11.16 Playing Chess with Computer
	11.17 Summary
	References
12 Reasoning in Uncertain Environments
	12.1 Introduction
	12.2 Foundations of Probability Theory
	12.3 Conditional Probability and Bayes Theorem
	12.4 Bayesian Networks
		12.4.1 Constructing a Bayesian Network
		12.4.2 Bayesian Network for Chain of Variables
		12.4.3 Independence of Variables
		12.4.4 Propagation in Bayesian Belief Networks
		12.4.5 Causality and Independence
		12.4.6 Hidden Markov Models
		12.4.7 Construction Process of Bayesian Networks
	12.5 Dempster–Shafer Theory of Evidence
		12.5.1 Dempster–Shafer Rule of Combination
		12.5.2 Dempster–Shafer Versus Bayes Theory
	12.6 Fuzzy Sets, Fuzzy Logic, and Fuzzy Inferences
		12.6.1 Fuzzy Composition Relation
		12.6.2 Fuzzy Rules and Fuzzy Graphs
		12.6.3 Fuzzy Graph Operations
		12.6.4 Fuzzy Hybrid Systems
	12.7 Summary
	References
13 Machine Learning
	13.1 Introduction
	13.2 Types of Machine Learning
	13.3 Discipline of Machine Learning
	13.4 Learning Model
	13.5 Classes of Learning
		13.5.1 Supervised Learning
		13.5.2 Unsupervised Learning
	13.6 Inductive Learning
		13.6.1 Argument-Based Learning
		13.6.2 Mutual Online Concept Learning
		13.6.3 Single-Agent Online Concept Learning
		13.6.4 Propositional and Relational Learning
		13.6.5 Learning Through Decision Trees
	13.7 Discovery-Based Learning
	13.8 Reinforcement Learning
		13.8.1 Some Functions in Reinforcement Learning
		13.8.2 Supervised Versus Reinforcement Learning
	13.9 Learning and Reasoning by Analogy
	13.10 A Framework of Symbol-Based Learning
	13.11 Explanation-Based Learning
	13.12 Machine Learning Applications
	13.13 Basic Research Problems in Machines Learning
	13.14 Summary
	References
14 Statistical Learning Theory
	14.1 Introduction
	14.2 Classification
	14.3 Support Vector Machines
		14.3.1 Learning Pattern Recognition from Examples
		14.3.2 Maximum Margin Training Algorithm
	14.4 Predicting Structured Objects Using SVM
	14.5 Working of Structural SVMs
	14.6 k-Nearest Neighbor Method
		14.6.1 k-NN Search Algorithm
	14.7 Naive Bayes Classifiers
	14.8 Artificial Neural Networks
		14.8.1 Error-Correction Rules
		14.8.2 Boltzmann Learning
		14.8.3 Hebbian Rule
		14.8.4 Competitive Learning Rules
		14.8.5 Deep Learning
	14.9 Instance-Based Learning
		14.9.1 Learning Task
		14.9.2 IBL Algorithm
	14.10 Summary
	References
15 Automated Planning
	15.1 Introduction
	15.2 Automated Planning
	15.3 The Basic Planning Problem
		15.3.1 The Classical Planning Problem
		15.3.2 Agent Types
	15.4 Forward Planning
	15.5 Partial-Order Planning
	15.6 Planning Languages
		15.6.1 A General Planning Language
		15.6.2 The Operation of STRIPS
		15.6.3 Search Strategy
	15.7 Planning with Propositional Logic
		15.7.1 Encoding Action Descriptions
		15.7.2 Analysis
	15.8 Planning Graphs
	15.9 Hierarchical Task Network Planning
	15.10 Multiagent Planning Systems
	15.11 Multiagent Planning Techniques
		15.11.1 Goal and Task Allocation
		15.11.2 Goal and Task Refinement
		15.11.3 Decentralized Planning
		15.11.4 Coordination After Planning
	15.12 Summary
	References
16 Intelligent Agents
	16.1 Introduction
	16.2 Classification of Agents
	16.3 Multiagent Systems
		16.3.1 Single-Agent Framework
		16.3.2 Multiagent Framework
		16.3.3 Multiagent Interactions
	16.4 Basic Architecture of Agent System
	16.5 Agents\' Coordination
		16.5.1 Sharing Among Cooperative Agents
		16.5.2 Static Coalition Formation
		16.5.3 Dynamic Coalition Formation
		16.5.4 Iterated Prisoner\'s Dilemma Coalition Model
		16.5.5 Coalition Algorithm
	16.6 Agent-Based Approach to Software Engineering
	16.7 Agents that Buy and Sell
	16.8 Modeling Agents as Decision Maker
		16.8.1 Issues in Mental Level Modeling
		16.8.2 Model Structure
		16.8.3 Preferences
		16.8.4 Decision Criteria
	16.9 Agent Communication Languages
		16.9.1 Semantics of Agent Programs
		16.9.2 Description Language for Interactive Agents
	16.10 Mobile Agents
	16.11 Social Level View of Multiagents
	16.12 Summary
	References
17 Data Mining
	17.1 Introduction
	17.2 Perspectives of Data Mining
	17.3 Goals of Data Mining
	17.4 Evolution of Data Mining Algorithms
		17.4.1 Transactions Data
		17.4.2 Data Streams
		17.4.3 Representation of Text-Based Data
	17.5 Classes of Data Mining Algorithms
		17.5.1 Prediction Methods
		17.5.2 Clustering
		17.5.3 Association Rules
	17.6 Data Clustering and Cluster Analysis
		17.6.1 Applications of Clustering
		17.6.2 General Utilities of Clustering
		17.6.3 Traditional Clustering Methods
		17.6.4 Clustering Process
		17.6.5 Pattern Representation and Feature Extraction
	17.7 Clustering Algorithms
		17.7.1 Similarity Measures
		17.7.2 Nearest Neighbor Clustering
		17.7.3 Partitional Algorithms
	17.8 Comparison of Clustering Techniques
	17.9 Classification
	17.10 Association Rule Mining
	17.11 Sequential Pattern Mining Algorithms
		17.11.1 Problem Statement
		17.11.2 Notations for Sequential Pattern Mining
		17.11.3 Typical Sequential Pattern Mining
		17.11.4 Apriori-Based Algorithm
	17.12 Scientific Applications in Data Mining
	17.13 Summary
	References
18 Information Retrieval
	18.1 Introduction
	18.2 Retrieval Strategies
	18.3 Boolean Model of IR System
	18.4 Vector Space Model
	18.5 Indexing
		18.5.1 Index Construction
		18.5.2 Index Maintenance
	18.6 Probabilistic Retrieval Model
	18.7 Fuzzy Logic-Based IR
	18.8 Concept-Based IR
		18.8.1 Concept-Based Indexing
		18.8.2 Retrieval Algorithms
	18.9 Automatic Query Expansion in IR
		18.9.1 Working of AQE
		18.9.2 Related Techniques for Query Processing
	18.10 Using Bayesian Networks for IR
		18.10.1 Representation of Document and Query
		18.10.2 Bayes Probabilistic Inference Model
		18.10.3 Bayes Inference Algorithm
		18.10.4 Representing Dependent Topics
	18.11 Semantic IR on the Web
	18.12 Distributed IR
	18.13 Summary
	References
19 Natural Language Processing
	19.1 Introduction
	19.2 Progress in NLP
	19.3 Applications of NLP
	19.4 Components of Natural Language Processing
		19.4.1 Syntax Analysis
		19.4.2 Semantic Analysis
		19.4.3 Discourse Analysis
	19.5 Grammars
		19.5.1 Phrase Structure
		19.5.2 Phrase Structure Grammars
	19.6 Classification of Grammars
		19.6.1 Chomsky Hierarchy of Grammars
		19.6.2 Transformational Grammars
		19.6.3 Ambiguous Grammars
	19.7 Prepositions in Applications
	19.8 Natural Language Parsing
		19.8.1 Parsing with CFGs
		19.8.2 Sentence-Level Constructions
		19.8.3 Top-Down Parsing
		19.8.4 Probabilistic Parsing
	19.9 Information Extraction
		19.9.1 Document Preprocessing
		19.9.2 Syntactic Parsing and Semantic Interpretation
		19.9.3 Discourse Analysis
		19.9.4 Output Template Generation
	19.10 NL-Question Answering
		19.10.1 Data Redundancy Based Approach
		19.10.2 Structured Descriptive Grammar-Based QA
	19.11 Commonsense-Based Interfaces
		19.11.1 Commonsense Thinking
		19.11.2 Components of Commonsense Reasoning
		19.11.3 Representation Structures
	19.12 Tools for NLP
		19.12.1 NLTK
		19.12.2 NLTK Examples
	19.13 Summary
	References
20 Automatic Speech Recognition
	20.1 Introduction
	20.2 Automatic Speech Recognition Resources
	20.3 Voice Web
	20.4 Speech Recognition Algorithms
	20.5 Hypothesis Search in ASR
		20.5.1 Lexicon
		20.5.2 Language Model
		20.5.3 Acoustic Models
	20.6 Automatic Speech Recognition Tools
		20.6.1 Automatic Speech Recognition Engine
		20.6.2 Tools for ASR
	20.7 Summary
	References
21 Machine Vision
	21.1 Introduction
	21.2 Machine Vision Applications
	21.3 Basic Principles of Vision
	21.4 Cognition and Classification
	21.5 From Image-to-Scene
		21.5.1 Inversion by Fixing Scene Parameters
		21.5.2 Inversion by Restricting the Problem Domain
		21.5.3 Inversion by Acquiring Additional Images
	21.6 Machine Vision Techniques
		21.6.1 Low-Level Vision
		21.6.2 Local Edge Detection
		21.6.3  Middle-Level Vision
		21.6.4 High-Level Vision
	21.7 Indexing and Geometric Hashing
	21.8 Object Representation and Tracking
	21.9 Feature Selection and Object Detection
		21.9.1 Object Detection
	21.10 Supervised Learning for Object Detection
	21.11 Axioms of Vision
		21.11.1 Mathematical Axioms
		21.11.2  Source Axioms
		21.11.3  Model Axioms
		21.11.4 Construct Axioms
	21.12 Computer Vision Tools
	21.13 Summary
	References
Appendix  Further Readings
		
Index