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 Precision-recall 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 Transforming to the right kind of data 204

10.5 NUMERICAL TRANSFORMATIONS 205

10.5.1 Information 205

10.5.2 Normalising data 207

Contents ¿ xiii

10.5.3 Missing values - filling the gaps 207

10.5.4 Outliers - dealing with extremes 209

10.6 NON-NUMERIC TRANSFORMATIONS 211

10.6.1 Media data 211

10.6.2 Text 212

10.6.3 Structure transformation 214

10.7 AUTOMATION AND DOCUMENTATION 214

10.8 SUMMARY 216

Section III Specialised Areas

Chapter 11 ¿Game playing 221

11.1 OVERVIEW 221

11.2 INTRODUCTION 221

11.3 CHARACTERISTICS OF GAME PLAYING 223

11.4 STANDARD GAMES 225

11.4.1 A simple game tree 225

11.4.2 Heuristics and minimax search 225

11.4.3 Horizon problems 227

11.4.4 Alpha-beta pruning 228

11.4.5 The imperfect opponent 229

11.5 NON-ZERO-SUM GAMES AND SIMULTANEOUS PLAY 229

11.5.1 The prisoner's dilemma 230

11.5.2 Searching the game tree 230

11.5.3 No alpha-beta pruning 232

11.5.4 Pareto-optimality 232

11.5.5 Multi-party competition and co-operation 233

11.6 THE ADVERSARY IS LIFE! 233

11.7 PROBABILITY 235

11.8 NEURAL NETWORKS FOR GAMES 236

11.8.1 Where to use a neural network 236

11.8.2 Training data and self play 238

11.9 SUMMARY 238

Chapter 12 ¿Computer vision 243

12.1 OVERVIEW 243

12.2 INTRODUCTION 243

xiv ¿ Contents

12.2.1 Why computer vision is difficult 243

12.2.2 Phases of computer vision 244

12.3 DIGITIZATION AND SIGNAL PROCESSING 245

12.3.1 Digitizing images 245

12.3.2 Thresholding 246

12.3.3 Digital filters 248

12.3.3.1 Linear filters 249

12.3.3.2 Smoothing 249

12.3.3.3 Gaussian filters 251

12.3.3.4 Practical considerations 252

12.4 EDGE DETECTION 252

12.4.1 Identifying edge pixels 253

12.4.1.1 Gradient operators 253

12.4.1.2 Robert's operator 253

12.4.1.3 Sobel's operator 256

12.4.1.4 Laplacian operator 257

12.4.1.5 Successive refinement and Marr's primal sketch 258

12.4.2 Edge following 259

12.5 REGION DETECTION 260

12.5.1 Region growing 261

12.5.2 The problem of texture 261

12.5.3 Representing regions - quadtrees 262

12.5.4 Computational problems 263

12.6 RECONSTRUCTING OBJECTS 263

12.6.1 Inferring three-dimensional features...