Introduction to Artificial Intelligence (Undergraduate Topics in Computer Science)

✍ Scribed by Wolfgang Ertel

• Publisher: Springer
• Year: 2018
• Tongue: English
• Leaves: 365
• Series: Undergraduate Topics in Computer Science
• Edition: 2nd ed. 2017
• Category: Library

✦ Synopsis

This accessible and engaging textbook presents a concise introduction to the exciting field of artificial intelligence (AI). The broad-ranging discussion covers the key subdisciplines within the field, describing practical algorithms and concrete applications in the areas of agents, logic, search, reasoning under uncertainty, machine learning, neural networks, and reinforcement learning. Fully revised and updated, this much-anticipated second edition also includes new material on deep learning.

Topics and features: presents an application-focused and hands-on approach to learning, with supplementary teaching resources provided at an associated website; contains numerous study exercises and solutions, highlighted examples, definitions, theorems, and illustrative cartoons; includes chapters on predicate logic, PROLOG, heuristic search, probabilistic reasoning, machine learning and data mining, neural networks and reinforcement learning; reports on developments in deep learning, including applications of neural networks to generate creative content such as text, music and art (NEW); examines performance evaluation of clustering algorithms, and presents two practical examples explaining Bayes’ theorem and its relevance in everyday life (NEW); discusses search algorithms, analyzing the cycle check, explaining route planning for car navigation systems, and introducing Monte Carlo Tree Search (NEW); includes a section in the introduction on AI and society, discussing the implications of AI on topics such as employment and transportation (NEW).

Ideal for foundation courses or modules on AI, this easy-to-read textbook offers an excellent overview of the field for students of computer science and other technical disciplines, requiring no more than a high-school level of knowledge of mathematics to understand the material.

✦ Table of Contents

Preface to the Second Edition
Preface to the First Edition
Contents
1 Introduction
1.1 What Is Artificial Intelligence?
1.1.1 Brain Science and Problem Solving
1.1.2 The Turing Test and Chatterbots
1.2 The History of AI
1.2.1 The First Beginnings
1.2.2 Logic Solves (Almost) All Problems
1.2.3 The New Connectionism
1.2.4 Reasoning Under Uncertainty
1.2.5 Distributed, Autonomous and Learning Agents
1.2.6 AI Grows Up
1.2.7 The AI Revolution
1.3 AI and Society
1.3.1 Does AI Destroy Jobs?
1.3.2 AI and Transportation
1.3.3 Service Robotics
1.4 Agents
1.5 Knowledge-Based Systems
1.6 Exercises
2 Propositional Logic
2.1 Syntax
2.2 Semantics
2.3 Proof Systems
2.4 Resolution
2.5 Horn Clauses
2.6 Computability and Complexity
2.7 Applications and Limitations
2.8 Exercises
3 First-order Predicate Logic
3.1 Syntax
3.2 Semantics
3.2.1 Equality
3.3 Quantifiers and Normal Forms
3.4 Proof Calculi
3.5 Resolution
3.5.1 Resolution Strategies
3.5.2 Equality
3.6 Automated Theorem Provers
3.7 Mathematical Examples
3.8 Applications
3.9 Summary
3.10 Exercises
4 Limitations of Logic
4.1 The Search Space Problem
4.2 Decidability and Incompleteness
4.3 The Flying Penguin
4.4 Modeling Uncertainty
4.5 Exercises
5 Logic Programming with PROLOG
5.1 PROLOG Systems and Implementations
5.2 Simple Examples
5.3 Execution Control and Procedural Elements
5.4 Lists
5.5 Self-modifying Programs
5.6 A Planning Example
5.7 Constraint Logic Programming
5.8 Summary
5.9 Exercises
6 Search, Games and Problem Solving
6.1 Introduction
6.2 Uninformed Search
6.2.1 Breadth-First Search
6.2.2 Depth-First Search
6.2.3 Iterative Deepening
6.2.4 Comparison
6.2.5 Cycle Check
6.3 Heuristic Search
6.3.1 Greedy Search
6.3.2 A★-Search
6.3.3 Route Planning with the A★ Search Algorithm
6.3.4 IDA★-Search
6.3.5 Empirical Comparison of the Search Algorithms
6.3.6 Summary
6.4 Games with Opponents
6.4.1 Minimax Search
6.4.2 Alpha-Beta-Pruning
6.4.3 Non-deterministic Games
6.5 Heuristic Evaluation Functions
6.5.1 Learning of Heuristics
6.6 State of the Art
6.6.1 Chess
6.6.2 Go
6.7 Exercises
7 Reasoning with Uncertainty
7.1 Computing with Probabilities
7.1.1 Conditional Probability
7.2 The Principle of Maximum Entropy
7.2.1 An Inference Rule for Probabilities
7.2.2 Maximum Entropy Without Explicit Constraints
7.2.3 Conditional Probability Versus Material Implication
7.2.4 MaxEnt-Systems
7.2.5 The Tweety Example
7.3 Lexmed, an Expert System for Diagnosing Appendicitis
7.3.1 Appendicitis Diagnosis with Formal Methods
7.3.2 Hybrid Probabilistic Knowledge Base
7.3.3 Application of Lexmed
7.3.4 Function of Lexmed
7.3.5 Risk Management Using the Cost Matrix
7.3.6 Performance
7.3.7 Application Areas and Experiences
7.4 Reasoning with Bayesian Networks
7.4.1 Independent Variables
7.4.2 Graphical Representation of Knowledge as a Bayesian Network
7.4.3 Conditional Independence
7.4.4 Practical Application
7.4.5 Software for Bayesian Networks
7.4.6 Development of Bayesian Networks
7.4.7 Semantics of Bayesian Networks
7.5 Summary
7.6 Exercises
8 Machine Learning and Data Mining
8.1 Data Analysis
8.2 The Perceptron, a Linear Classifier
8.2.1 The Learning Rule
8.2.2 Optimization and Outlook
8.3 The Nearest Neighbor Method
8.3.1 Two Classes, Many Classes, Approximation
8.3.2 Distance Is Relevant
8.3.3 Computation Times
8.3.4 Summary and Outlook
8.3.5 Case-Based Reasoning
8.4 Decision Tree Learning
8.4.1 A Simple Example
8.4.2 Entropy as a Metric for Information Content
8.4.3 Information Gain
8.4.4 Application of C4.5
8.4.5 Learning of Appendicitis Diagnosis
8.4.6 Continuous Attributes
8.4.7 Pruning—Cutting the Tree
8.4.8 Missing Values
8.4.9 Summary
8.5 Cross-Validation and Overfitting
8.6 Learning of Bayesian Networks
8.6.1 Learning the Network Structure
8.7 The Naive Bayes Classifier
8.7.1 Text Classification with Naive Bayes
8.8 One-Class Learning
8.8.1 Nearest Neighbor Data Description
8.9 Clustering
8.9.1 Distance Metrics
8.9.2 k-Means and the EM Algorithm
8.9.3 Hierarchical Clustering
8.9.4 How is the Number of Clusters Determined?
8.10 Data Mining in Practice
8.10.1 The Data Mining Tool KNIME
8.11 Summary
8.12 Exercises
8.12.1 Introduction
8.12.2 The Perceptron
8.12.3 Nearest Neighbor Method
8.12.4 Decision Trees
8.12.5 Learning of Bayesian Networks
8.12.6 Clustering
8.12.7 Data Mining
9 Neural Networks
9.1 From Biology to Simulation
9.1.1 The Mathematical Model
9.2 Hopfield Networks
9.2.1 Application to a Pattern Recognition Example
9.2.2 Analysis
9.2.3 Summary and Outlook
9.3 Neural Associative Memory
9.3.1 Correlation Matrix Memory
9.3.2 The Binary Hebb Rule
9.3.3 A Spelling Correction Program
9.4 Linear Networks with Minimal Errors
9.4.1 Least Squares Method
9.4.2 Application to the Appendicitis Data
9.4.3 The Delta Rule
9.4.4 Comparison to the Perceptron
9.5 The Backpropagation Algorithm
9.5.1 NETtalk: A Network Learns to Speak
9.5.2 Learning of Heuristics for Theorem Provers
9.5.3 Problems and Improvements
9.6 Support Vector Machines
9.7 Deep Learning
9.7.1 Nature as Example
9.7.2 Stacked Denoising Autoencoder
9.7.3 Other Methods
9.7.4 Systems and Implementations
9.7.5 Applications of Deep Learning
9.8 Creativity
9.9 Applications of Neural Networks
9.10 Summary and Outlook
9.11 Exercises
9.11.1 From Biology to Simulation
9.11.2 Hopfield Networks
9.11.3 Linear Networks with Minimal Errors
9.11.4 Backpropagation
9.11.5 Support Vector Machines
10 Reinforcement Learning
10.1 Introduction
10.2 The Task
10.3 Uninformed Combinatorial Search
10.4 Value Iteration and Dynamic Programming
10.5 A Learning Walking Robot and Its Simulation
10.6 Q-Learning
10.6.1 Q-Learning in a Nondeterministic Environment
10.7 Exploration and Exploitation
10.8 Approximation, Generalization and Convergence
10.9 Applications
10.10 AlphaGo, the Breakthrough in Go
10.11 Curse of Dimensionality
10.12 Summary and Outlook
10.13 Exercises
11 Solutions for the Exercises
11.1 Introduction
11.2 Propositional Logic
11.3 First-Order Predicate Logic
11.4 Limitations of Logic
11.5 PROLOG
11.6 Search, Games and Problem Solving
11.7 Reasoning with Uncertainty
11.8 Machine Learning and Data Mining
11.9 Neural Networks
11.10 Reinforcement Learning
References
Index