Artificial Intelligence

Auteur
Alan Dix is Director of the Computational Foundry at Swansea University, a 30 million pound initiative to boost computational research in Wales with a strong focus on creating social and economic benefit. Previously Alan has worked in a mix of academic, commercial and government roles. Alan is principally known for his work in human-computer interaction, and is the author of one of the major international textbooks on HCI as well as of over 450 research publications from formal methods to intelligent interfaces and design creativity. Technically, he works equally happily with AI and machine learning alongside traditional mathematical and statistical techniques. He has a broad understanding of mathematical, computational and human issues, and he authored some of the earliest papers on gender and ethnic bias in black box-algorithms.

Texte du rabat

This new edition expands and revises the book throughout, with new material added to existing chapters, including short case studies, as well as adding new chapters on explainable AI, and big data.

Contenu

List of Figures xxv

Preface xxxv

Author Bio xxxvii

Chapter 1 Introduction 1

1.1 WHAT IS ARTIFICIAL INTELLIGENCE? 1

1.1.1 How much like a human: strong vs. weak AI 1

1.1.2 Top-down or bottom-up: symbolic vs. sub-symbolic 2

1.1.3 A working definition 3

1.1.4 Human intelligence 3

1.1.5 Bottom up and top down 4

1.2 HUMANS AT THE HEART 4

1.3 A SHORT HISTORY OF ARTIFICIAL INTELLIGENCE 5

1.3.1 The development of AI 6

1.3.2 The physical symbol system hypothesis 8

1.3.3 Sub-symbolic spring 9

1.3.4 AI Renaissance 10

1.3.5 Moving onwards 11

1.4 STRUCTURE OF THIS BOOK A LANDSCAPE OF AI 11

Section I Knowledge-Rich AI

Chapter 2 Knowledge in AI 15

2.1 OVERVIEW 15

2.2 INTRODUCTION 15

2.3 REPRESENTING KNOWLEDGE 16

2.4 METRICS FOR ASSESSING KNOWLEDGE REPRESENTATION SCHEMES

19

2.5 LOGIC REPRESENTATIONS 20

2.6 PROCEDURAL REPRESENTATION 23

vii

viii Contents

2.6.1 The database 23

2.6.2 The production rules 23

2.6.3 The interpreter 24

2.6.4 An example production system: making a loan 24

2.7 NETWORK REPRESENTATIONS 26

2.8 STRUCTURED REPRESENTATIONS 28

2.8.1 Frames 29

2.8.2 Scripts 29

2.9 GENERAL KNOWLEDGE 31

2.10 THE FRAME PROBLEM 32

2.11 KNOWLEDGE ELICITATION 33

2.12 SUMMARY 33

Chapter 3 Reasoning 37

3.1 OVERVIEW 37

3.2 WHAT IS REASONING? 37

3.3 FORWARD AND BACKWARD REASONING 39

3.4 REASONING WITH UNCERTAINTY 40

3.4.1 Non-monotonic reasoning 40

3.4.2 Probabilistic reasoning 41

3.4.3 Certainty factors 43

3.4.4 Fuzzy reasoning 45

3.4.5 Reasoning by analogy 46

3.4.6 Case-based reasoning 46

3.5 REASONING OVER NETWORKS 48

3.6 CHANGING REPRESENTATIONS 51

3.7 SUMMARY 51

Chapter 4 Search 53

4.1 INTRODUCTION 53

4.1.1 Types of problem 53

4.1.2 Structuring the search space 57

4.2 EXHAUSTIVE SEARCH AND SIMPLE PRUNING 63

4.2.1 Depth and breadth first search 63

4.2.2 Comparing depth and breadth first searches 65

4.2.3 Programming and space costs 67

4.2.4 Iterative deepening and broadening 68

Contents ix

4.2.5 Finding the best solution branch and bound 69

4.2.6 Graph search 70

4.3 HEURISTIC SEARCH 70

4.3.1 Hill climbing andbest first goal-directed search 72

4.3.2 Finding the best solution the A algorithm 72

4.3.3 Inexact search 75

4.4 KNOWLEDGE-RICH SEARCH 77

4.4.1 Constraint satisfaction 78

4.5 SUMMARY 80

Section II Data and Learning

Chapter 5 Machine learning 85

5.1 OVERVIEW 85

5.2 WHY DO WE WANT MACHINE LEARNING? 85

5.3 HOW MACHINES LEARN 87

5.3.1 Phases of machine learning 87

5.3.2 Rote learning and the importance of generalization 89

5.3.3 Inputs to training 90

5.3.4 Outputs of training 91

5.3.5 The training process 92

5.4 DEDUCTIVE LEARNING 93

5.5 INDUCTIVE LEARNING 94

5.5.1 Version spaces 95

5.5.2 Decision trees 99

5.5.2.1 Building a binary tree 99

5.5.2.2 More complex trees 102

5.5.3 Rule induction and credit assignment 103

5.6 EXPLANATION-BASED LEARNING 104

5.7 EXAMPLE: QUERY-BY-BROWSING 105

5.7.1 What the user sees 105

5.7.2 How it works 105

5.7.3 Problems 107

5.8 SUMMARY 107

Chapter 6 Neural Networks 109

6.1 OVERVIEW 109

x Contents

6.2 WHY USE NEURAL NETWORKS? 109

6.3 THE PERCEPTRON 110

6.3.1 The XOR problem 112

6.4 THE MULTI-LAYER PERCEPTRON 113

6.5 BACKPROPAGATION 114

6.5.1 Basic principle 115

6.5.2 Backprop for a single layer network 116

6.5.3 Backprop for hidden layers 117

6.6 ASSOCIATIVE MEMORIES 117

6.6.1 Boltzmann Machines 119

6.6.2 Kohonen self-organizing networks 121

6.7 LOWER-LEVEL MODELS 122

6.7.1 Cortical layers 122

6.7.2 Inhibition 123

6.7.3 Spiking neural networks 123

6.8 HYBRID ARCHITECTURES 124

6.8.1 Hybrid layers 124

6.8.2 Neurosymbolic AI 125

6.9 SUMMARY 126

Chapter 7 Statistical and Numerical Techniques 129

7.1 OVERVIEW 129

7.2 LINEAR REGRESSION 129

7.3 VECTORS AND MATRICES 132

7.4 EIGENVALUES AND PRINCIPAL COMPONENTS 134

7.5 CLUSTERING AND K-MEANS 136

7.6 RANDOMNESS 138

7.6.1 Simple statistics 138

7.6.2 Distributions and long-tail data 140

7.6.3 Least squares 142

7.6.4 Monte Carlo techniques 142

7.7 NON-LINEAR FUNCTIONS FOR MACHINE LEARNING 144

7.7.1 Support Vector Machines 144

7.7.2 Reservoir Computing 145

7.7.3 Kolmogorov-Arnold Networks 146

7.8 SUMMARY 147

Contents xi

Chapter 8 Going Large: deep learning and big data 151

8.1 OVERVIEW 151

8.2 DEEP LEARNING 152

8.2.1 Why are many layers so difficult? 153

8.2.2 Architecture of the layers 153

8.3 GROWING THE DATA 156

8.3.1 Modifying real data 157

8.3.2 Virtual worlds 157

8.3.3 Self learning 157

8.4 DATA REDUCTION 158

8.4.1 Dimension reduction 159

8.4.1.1 Vector space techniques 159

8.4.1.2 Non-numeric features 160

8.4.2 Reduce total number of data items 161

8.4.2.1 Sampling 161

8.4.2.2 Aggregation 161

8.4.3 Segmentation 162

8.4.3.1 Class segmentation 162

8.4.3.2 Result recombination 162

8.4.3.3 Weakly-communicating partial analysis 163

8.5 PROCESSING BIG DATA 164

8.5.1 Why it is hard distributed storage and computation 164

8.5.2 Principles behind MapReduce 165

8.5.3 MapReduce for the cloud 166

8.5.4 If it can go wrong resilience for big processing 167

8.6 DATA AND ALGORITHMS AT SCALE 169

8.6.1 Big graphs 169

8.6.2 Time series and event streams 170

8.6.2.1 Multi-scale with mega-windows 170

8.6.2.2 Untangling streams 171

8.6.2.3 Real-time processing 171

8.7 SUMMARY 171

Chapter 9 Making Sense of Machine Learning 175

9.1 OVERVIEW 175

9.2 THE MACHINE LEARNING PROCESS 175

xii Contents

9.2.1 Training phase 176

9.2.2 Application phase 177

9.2.3 Validation phase 177

9.3 EVALUATION 178

9.3.1 Measures of effectiveness 178

9.3.2 Precisionrecall trade-off 180

9.3.3 Data for evaluation 182

9.3.4 Multi-stage evaluation 182

9.4 THE FITNESS LANDSCAPE 183

9.4.1 Hill-climbing and gradient descent / ascent 183

9.4.2 Local maxima and minima 184

9.4.3 Plateau and ridge effects 185

9.4.4 Local structure 186

9.4.5 Approximating the landscape 186

9.4.6 Forms of fitness function 187

9.5 DEALING WITH COMPLEXITY 188

9.5.1 Degrees of freedom and dimension reduction 188

9.5.2 Constraints and dependent features 189

9.5.3 Continuity and learning 191

9.5.4 Multi-objective optimisation 193

9.5.5 Partially labelled data 194

9.6 SUMMARY 196

Chapter 10 Data Preparation 199

10.1 OVERVIEW 199

10.2 STAGES OF DATA PREPARATION 199

10.3 CREATING A DATASET 200

10.3.1 Extraction and gathering of data 200

10.3.2 Entity reconciliation and linking 201

10.3.3 Exception sets 202

10.4 MANIPULATION AND TRANSFORMATION OF DATA 202

10.4.1 Types of data value 203

10.4.2 Trans…