Artificial Intelligence A Textbook

Description

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