Artificial Intelligence A Textbook

✍ Scribed by Charu Aggarwal

• Year: 2021
• Tongue: English
• Leaves: 496
• Category: Library

✦ Table of Contents

Preface
Acknowledgments
Contents
Author Biography
1 An Introduction to Artificial Intelligence
1.1 Introduction
1.2 The Two Schools of Thought
1.2.1 Induction and Deduction: A Historical View
1.3 Artificial General Intelligence
1.3.1 The Turing Test
1.4 The Concept of Agent
1.4.1 Types of Environments
1.5 Deductive Reasoning in Artificial Intelligence
1.5.1 Examples of Deductive Reasoning in Artificial Intelligence
1.5.1.1 Constraint Satisfaction Problem
1.5.1.2 Solving NP-Hard Problems
1.5.1.3 Game Playing
1.5.1.4 Planning
1.5.1.5 Expert Systems
1.5.2 Classical Methods for Deductive Reasoning
1.5.2.1 Search-Based Methods
1.5.2.2 Logic Programming
1.5.3 Strengths and Limitations of Deductive Reasoning
1.6 Inductive Learning in Artificial Intelligence
1.6.1 Types of Learning
1.6.2 Unsupervised Learning Tasks
1.6.3 Supervised Learning Tasks
1.7 Biological Evolution in Artificial Intelligence
1.8 Summary
1.9 Further Reading
1.10 Exercises
2 Searching State Spaces
2.1 Introduction
2.1.1 State Space as a Graph
2.2 Uninformed Search Algorithms
2.2.1 Case Study: Eight-Puzzle Problem
2.2.2 Case Study: Online Maze Search
2.2.3 Improving Efficiency with Bidirectional Search
2.3 Informed Search: Best-First Search
2.3.1 Greedy Best-First Search
2.3.2 A*-Search
2.4 Local Search with State-Specific Loss Functions
2.4.1 Hill Climbing
2.4.1.1 The Problem of Local Optima
2.4.2 Tabu Search
2.4.3 Simulated Annealing
2.5 Genetic Algorithms
2.6 The Constraint Satisfaction Problem
2.6.1 Traveling Salesperson Problem as Constraint Satisfaction
2.6.2 Graph Coloring as Constraint Satisfaction
2.6.3 Sudoku as Constraint Satisfaction
2.6.4 Search Algorithms for Constraint Satisfaction
2.6.5 Leveraging State-Specific Loss Values
2.7 Summary
2.8 Further Reading
2.9 Exercises
3 Multiagent Search
3.1 Introduction
3.2 Uninformed Search: AND-OR Search Trees
3.2.1 Handling More than Two Agents
3.2.2 Handling Non-deterministic Environments
3.3 Informed Search Trees with State-Specific Loss Functions
3.3.1 Heuristic Variations
3.3.2 Adaptation to Adversarial Environments
3.3.3 Prestoring Subtrees
3.3.4 Challenges in Designing Evaluation Functions
3.3.5 Weaknesses of Minimax Trees
3.4 Alpha-Beta Pruning
3.4.1 Importance of Branch Evaluation Order
3.5 Monte Carlo Tree Search: The Inductive View
3.5.1 Enhancements to the Expected Outcome Model
3.5.2 Deductive Versus Inductive: Minimax and Monte Carlo Trees
3.5.3 Application to Non-deterministic and Partially ObservableGames
3.6 Summary
3.7 Further Reading
3.8 Exercises
4 Propositional Logic
4.1 Introduction
4.2 Propositional Logic: The Basics
4.2.1 Truth Tables
4.3 Laws of Propositional Logic
4.3.1 Useful Properties of Implication and Equivalence
4.3.2 Tautologies and Satisfiability
4.3.3 Clauses and Canonical Forms
4.4 Propositional Logic as a Precursor to Expert Systems
4.5 Equivalence of Expressions in Propositional Logic
4.6 The Basics of Proofs in Knowledge Bases
4.7 The Method of Proof by Contradiction
4.8 Efficient Entailment with Definite Clauses
4.8.1 Forward Chaining
4.8.2 Backward Chaining
4.8.3 Comparing Forward and Backward Chaining
4.9 Summary
4.10 Further Reading
4.11 Exercises
5 First-Order Logic
5.1 Introduction
5.2 The Basics of First-Order Logic
5.2.1 The Use of Quantifiers
5.2.2 Functions in First-Order Logic
5.2.3 How First-Order Logic Builds on Propositional Logic
5.2.4 Standardization Issues and Scope Extension
5.2.5 Interaction of Negation with Quantifiers
5.2.6 Substitution and Skolemization
5.2.7 Why First-Order Logic Is More Expressive
5.3 Populating a Knowledge Base
5.4 Example of Expert System with First-Order Logic
5.5 Systematic Inferencing Procedures
5.5.1 The Method of Proof by Contradiction
5.5.1.1 Conversion to Conjunctive Normal Form
5.5.1.2 Resolution Procedure
5.5.2 Forward Chaining
5.5.3 Backward Chaining
5.6 Summary
5.7 Further Reading
5.8 Exercises
6 Machine Learning: The Inductive View
6.1 Introduction
6.2 Linear Regression
6.2.1 Stochastic Gradient Descent
6.2.2 Matrix-Based Solution
6.2.3 Use of Bias
6.2.4 Why Is Regularization Important?
6.3 Least-Squares Classification
6.3.1 Problems with Least-Squares Classification
6.4 The Support Vector Machine
6.4.1 Mini-Batch Stochastic Gradient Descent
6.5 Logistic Regression
6.5.1 Computing Gradients
6.5.2 Comparing the SVM and Logistic Regression
6.5.3 Logistic Regression as a Probabilistic Classifier
6.6 Multiclass Setting
6.6.1 One-Against-Rest and One-Against-One Voting
6.6.2 Multinomial Logistic Regression
6.6.2.1 Stochastic Gradient Descent
6.7 The Naïve Bayes Model
6.8 Nearest Neighbor Classifier
6.9 Decision Trees
6.9.1 Training Phase of Decision Tree Construction
6.9.2 Splitting a Node
6.9.3 Generalizing Decision Trees to Random Forests
6.10 Rule-Based Classifiers
6.10.1 Sequential Covering Algorithms
6.10.1.1 Learn-One-Rule
6.10.2 Comparing Rule-Based Classifiers to Logical Rulesin Expert Systems
6.11 Evaluation of Classification
6.11.1 Segmenting into Training and Testing Portions
6.11.1.1 Hold-Out
6.11.1.2 Cross-Validation
6.11.2 Absolute Accuracy Measures
6.11.2.1 Accuracy of Classification
6.11.2.2 Accuracy of Regression
6.11.3 Ranking Measures
6.11.3.1 Receiver Operating Characteristic
6.12 Summary
6.13 Further Reading
6.14 Exercises
7 Neural Networks
7.1 Introduction
7.2 An Introduction to Computational Graphs
7.2.1 Neural Networks as Directed Computational Graphs
7.2.2 Softmax Activation Function
7.2.3 Common Loss Functions
7.2.4 How Nonlinearity Increases Expressive Power
7.3 Optimization in Directed Acyclic Graphs
7.3.1 The Challenge of Computational Graphs
7.3.2 The Broad Framework for Gradient Computation
7.3.3 Computing Node-to-Node Derivatives Using Brute Force
7.3.4 Dynamic Programming for Computing Node-to-NodeDerivatives
7.3.4.1 Example of Computing Node-to-Node Derivatives
7.3.5 Converting Node-to-Node Derivatives into Loss-to-WeightDerivatives
7.3.5.1 Example of Computing Loss-to-Weight Derivatives
7.3.6 Computational Graphs with Vector Variables
7.4 Application: Backpropagation in Neural Networks
7.4.1 Derivatives of Common Activation Functions
7.4.2 The Special Case of Softmax
7.4.3 Vector-Centric Backpropagation
7.4.4 Example of Vector-Centric Backpropagation
7.5 A General View of Computational Graphs
7.6 Summary
7.7 Further Reading
7.8 Exercises
8 Domain-Specific Neural Architectures
8.1 Introduction
8.2 Principles Underlying Convolutional Neural Networks
8.3 The Basic Structure of a Convolutional Network
8.3.1 Padding
8.3.2 Strides
8.3.3 Typical Settings
8.3.4 The ReLU Layer
8.3.5 Pooling
8.3.6 Fully Connected Layers
8.3.7 The Interleaving between Layers
8.3.8 Hierarchical Feature Engineering
8.4 Case Studies of Convolutional Architectures
8.4.1 AlexNet
8.4.2 VGG
8.4.3 ResNet
8.5 Principles Underlying Recurrent Neural Networks
8.6 The Architecture of Recurrent Neural Networks
8.6.1 Language Modeling Example of RNN
8.6.1.1 Generating a Language Sample
8.6.2 Backpropagation Through Time
8.6.3 Multilayer Recurrent Networks
8.7 Long Short-Term Memory (LSTM)
8.8 Applications of Domain-Specific Architectures
8.8.1 Application to Automatic Image Captioning
8.8.2 Sequence-to-Sequence Learning and Machine Translation
8.9 Summary
8.10 Further Reading
8.11 Exercises
9 Unsupervised Learning
9.1 Introduction
9.2 Dimensionality Reduction and Matrix Factorization
9.2.1 Symmetric Matrix Factorization
9.2.2 Singular Value Decomposition
9.2.2.1 Example of SVD
9.2.2.2 Alternate Optima via Gradient Descent
9.2.3 Nonnegative Matrix Factorization
9.2.3.1 Interpreting Nonnegative Matrix Factorization
9.2.4 Dimensionality Reduction with Neural Networks
9.2.4.1 Linear Autoencoder with a Single Hidden Layer
9.2.4.2 Nonlinear Activations
9.3 Clustering
9.3.1 Representative-Based Algorithms
9.3.2 Bottom-up Agglomerative Methods
9.3.2.1 Group-Based Statistics
9.3.3 Top-down Divisive Methods
9.3.3.1 Bisecting k-Means
9.3.4 Probabilistic Model-based Algorithms
9.3.5 Kohonen Self-Organizing Map
9.3.6 Spectral Clustering
9.4 Why Unsupervised Learning Is Important
9.4.1 Feature Engineering for Machine Learning
9.4.2 Radial Basis Function Networks for Feature Engineering
9.4.3 Semisupervised Learning
9.4.3.1 Self-Training
9.4.3.2 Co-Training
9.4.3.3 Unsupervised Pretraining in Multilayer Neural Networks
9.5 Summary
9.6 Further Reading
9.7 Exercises
10 Reinforcement Learning
10.1 Introduction
10.2 Stateless Algorithms: Multi-Armed Bandits
10.2.1 Naïve Algorithm
10.2.2 ε-Greedy Algorithm
10.2.3 Upper Bounding Methods
10.3 Reinforcement Learning Framework
10.4 Monte Carlo Sampling
10.4.1 Monte Carlo Sampling Algorithm
10.4.2 Monte Carlo Rollouts with Function Approximators
10.4.3 Connections to Monte Carlo Tree Search
10.5 Bootstrapping and Temporal Difference Learning
10.5.1 Q-Learning
10.5.2 Using Function Approximators
10.5.3 Example: Neural Network Specifics for Video Game Setting
10.5.4 On-Policy Versus Off-Policy Methods: SARSA
10.5.5 Modeling States Versus State-Action Pairs
10.6 Policy Gradient Methods
10.6.1 The Likelihood Ratio Principle
10.6.2 Combining Supervised Learning with Policy Gradients
10.6.3 Actor-Critic Methods
10.6.4 Continuous Action Spaces
10.6.5 Advantages and Disadvantages of Policy Gradients
10.7 Revisiting Monte Carlo Tree Search
10.8 Case Studies
10.8.1 AlphaGo: Championship Level Play at Go
10.8.1.1 AlphaZero: Enhancements to Zero Human Knowledge
10.8.2 Self-Learning Robots
10.8.2.1 Deep Learning of Locomotion Skills
10.8.2.2 Deep Learning of Visuomotor Skills
10.8.3 Self-Driving Cars
10.9 Weaknesses of Reinforcement Learning
10.10 Summary
10.11 Further Reading
10.12 Exercises
11 Probabilistic Graphical Models
11.1 Introduction
11.2 Bayesian Networks
11.3 Rudimentary Probabilistic Models in Machine Learning
11.4 The Boltzmann Machine
11.4.1 How a Boltzmann Machine Generates Data
11.4.2 Learning the Weights of a Boltzmann Machine
11.5 Restricted Boltzmann Machines
11.5.1 Training the RBM
11.5.2 Contrastive Divergence Algorithm
11.5.3 Practical Issues and Improvisations
11.6 Applications of Restricted Boltzmann Machines
11.6.1 Dimensionality Reduction and Data Reconstruction
11.6.2 RBMs for Collaborative Filtering
11.6.2.1 Making Predictions
11.6.3 Conditional Factoring: A Neat Regularization Trick
11.7 Summary
11.8 Further Reading
11.9 Exercises
12 Knowledge Graphs
12.1 Introduction
12.2 An Overview of Knowledge Graphs
12.2.1 Example: WordNet
12.2.2 Example: YAGO
12.2.3 Example: DBpedia
12.2.4 Example: Freebase
12.2.5 Example: Wikidata
12.2.6 Example: Gene Ontology
12.3 How to Construct a Knowledge Graph
12.3.1 First-Order Logic to Knowledge Graphs
12.3.2 Extraction from Unstructured Data
12.3.3 Handling Incompleteness
12.4 Applications of Knowledge Graphs
12.4.1 Knowledge Graphs in Search
12.4.2 Clustering Knowledge Graphs
12.4.3 Entity Classification
12.4.4 Link Prediction and Relationship Classification
12.4.5 Recommender Systems
12.5 Summary
12.6 Further Reading
12.7 Exercises
13 Integrating Reasoning and Learning
13.1 Introduction
13.2 The Bias-Variance Trade-Off
13.2.1 Formal View
13.3 A Generic Deductive-Inductive Ensemble
13.3.1 Inductive Ensemble Methods
13.4 Transfer Learning
13.4.1 Image Data
13.4.2 Text Data
13.4.3 Cross-Domain Transfer Learning
13.5 Lifelong Machine Learning
13.5.1 An Instructive Example of Lifelong Learning
13.6 Neuro-Symbolic Artificial Intelligence
13.6.1 Question Answering on Images
13.7 Summary
13.8 Further Reading
13.9 Exercises
Bibliography
Index