Python code for Artificial Intelligence: Foundations of ...

1

Python code for Artificial Intelligence: Foundations of

Computational Agents

David L. Poole and Alan K. Mackworth

Version 0.9.11 of December 1, 2023.

?David L Poole and Alan K Mackworth 2017-2023. All code is licensed under a Creative Commons Attribution-NonCommercial-

ShareAlike 4.0 International License. See: by-nc-sa/4.0/deed.en

This document and all the code can be downloaded from or from

The authors and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research and testing of the theories and programs to determine their effectiveness. The authors and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.



Version 0.9.11

December 1, 2023

Contents

Contents

3

1 Python for Artificial Intelligence

9

1.1 Why Python? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Getting Python . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Running Python . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4 Pitfalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5 Features of Python . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.5.1 f-strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.5.2 Lists, Tuples, Sets, Dictionaries and Comprehensions . . 12

1.5.3 Functions as first-class objects . . . . . . . . . . . . . . . . 13

1.5.4 Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6 Useful Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.1 Timing Code . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.2 Plotting: Matplotlib . . . . . . . . . . . . . . . . . . . . . 16

1.7 Utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.7.1 Display . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.7.2 Argmax . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.7.3 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.7.4 Dictionary Union . . . . . . . . . . . . . . . . . . . . . . . 20

1.8 Testing Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 Agent Architectures and Hierarchical Control

25

2.1 Representing Agents and Environments . . . . . . . . . . . . . 25

2.2 Paper buying agent and environment . . . . . . . . . . . . . . 27

2.2.1 The Environment . . . . . . . . . . . . . . . . . . . . . . . 27

3

4

Contents

2.2.2 The Agent . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.3 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3 Hierarchical Controller . . . . . . . . . . . . . . . . . . . . . . . 30 2.3.1 Environment . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3.2 Body . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.3 Middle Layer . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.4 Top Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.5 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 Searching for Solutions

41

3.1 Representing Search Problems . . . . . . . . . . . . . . . . . . 41

3.1.1 Explicit Representation of Search Graph . . . . . . . . . . 42

3.1.2 Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.1.3 Example Search Problems . . . . . . . . . . . . . . . . . . 46

3.2 Generic Searcher and Variants . . . . . . . . . . . . . . . . . . . 53

3.2.1 Searcher . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.2.2 GUI for Tracing Search . . . . . . . . . . . . . . . . . . . . 55

3.2.3 Frontier as a Priority Queue . . . . . . . . . . . . . . . . . 59

3.2.4 A Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.2.5 Multiple Path Pruning . . . . . . . . . . . . . . . . . . . . 62

3.3 Branch-and-bound Search . . . . . . . . . . . . . . . . . . . . . 64

4 Reasoning with Constraints

69

4.1 Constraint Satisfaction Problems . . . . . . . . . . . . . . . . . 69

4.1.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.1.2 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4.1.3 CSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.1.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.2 A Simple Depth-first Solver . . . . . . . . . . . . . . . . . . . . 83

4.3 Converting CSPs to Search Problems . . . . . . . . . . . . . . . 84

4.4 Consistency Algorithms . . . . . . . . . . . . . . . . . . . . . . 86

4.4.1 Direct Implementation of Domain Splitting . . . . . . . . 89

4.4.2 Consistency GUI . . . . . . . . . . . . . . . . . . . . . . . 91

4.4.3 Domain Splitting as an interface to graph searching . . . 93

4.5 Solving CSPs using Stochastic Local Search . . . . . . . . . . . 95

4.5.1 Any-conflict . . . . . . . . . . . . . . . . . . . . . . . . . . 97

4.5.2 Two-Stage Choice . . . . . . . . . . . . . . . . . . . . . . . 98

4.5.3 Updatable Priority Queues . . . . . . . . . . . . . . . . . 101

4.5.4 Plotting Run-Time Distributions . . . . . . . . . . . . . . 102

4.5.5 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4.6 Discrete Optimization . . . . . . . . . . . . . . . . . . . . . . . 105

4.6.1 Branch-and-bound Search . . . . . . . . . . . . . . . . . . 106

5 Propositions and Inference

109

5.1 Representing Knowledge Bases . . . . . . . . . . . . . . . . . . 109



Version 0.9.11

December 1, 2023

Contents

5

5.2 Bottom-up Proofs (with askables) . . . . . . . . . . . . . . . . . 112 5.3 Top-down Proofs (with askables) . . . . . . . . . . . . . . . . . 114 5.4 Debugging and Explanation . . . . . . . . . . . . . . . . . . . . 115 5.5 Assumables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.6 Negation-as-failure . . . . . . . . . . . . . . . . . . . . . . . . . 122

6 Deterministic Planning

125

6.1 Representing Actions and Planning Problems . . . . . . . . . . 125

6.1.1 Robot Delivery Domain . . . . . . . . . . . . . . . . . . . 126

6.1.2 Blocks World . . . . . . . . . . . . . . . . . . . . . . . . . 128

6.2 Forward Planning . . . . . . . . . . . . . . . . . . . . . . . . . . 130

6.2.1 Defining Heuristics for a Planner . . . . . . . . . . . . . . 133

6.3 Regression Planning . . . . . . . . . . . . . . . . . . . . . . . . 135

6.3.1 Defining Heuristics for a Regression Planner . . . . . . . 137

6.4 Planning as a CSP . . . . . . . . . . . . . . . . . . . . . . . . . . 138

6.5 Partial-Order Planning . . . . . . . . . . . . . . . . . . . . . . . 142

7 Supervised Machine Learning

149

7.1 Representations of Data and Predictions . . . . . . . . . . . . . 150

7.1.1 Creating Boolean Conditions from Features . . . . . . . . 153

7.1.2 Evaluating Predictions . . . . . . . . . . . . . . . . . . . . 155

7.1.3 Creating Test and Training Sets . . . . . . . . . . . . . . . 157

7.1.4 Importing Data From File . . . . . . . . . . . . . . . . . . 157

7.1.5 Augmented Features . . . . . . . . . . . . . . . . . . . . . 160

7.2 Generic Learner Interface . . . . . . . . . . . . . . . . . . . . . 162

7.3 Learning With No Input Features . . . . . . . . . . . . . . . . . 163

7.3.1 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

7.4 Decision Tree Learning . . . . . . . . . . . . . . . . . . . . . . . 167

7.5 Cross Validation and Parameter Tuning . . . . . . . . . . . . . 171

7.6 Linear Regression and Classification . . . . . . . . . . . . . . . 175

7.7 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

7.7.1 Gradient Tree Boosting . . . . . . . . . . . . . . . . . . . . 184

8 Neural Networks and Deep Learning

187

8.1 Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

8.2 Feedforward Networks . . . . . . . . . . . . . . . . . . . . . . . 190

8.3 Improved Optimization . . . . . . . . . . . . . . . . . . . . . . 192

8.3.1 Momentum . . . . . . . . . . . . . . . . . . . . . . . . . . 192

8.3.2 RMS-Prop . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

8.4 Dropout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

8.4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

9 Reasoning with Uncertainty

201

9.1 Representing Probabilistic Models . . . . . . . . . . . . . . . . 201

9.2 Representing Factors . . . . . . . . . . . . . . . . . . . . . . . . 201



Version 0.9.11

December 1, 2023

6

Contents

9.3 Conditional Probability Distributions . . . . . . . . . . . . . . 203 9.3.1 Logistic Regression . . . . . . . . . . . . . . . . . . . . . . 203 9.3.2 Noisy-or . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 9.3.3 Tabular Factors and Prob . . . . . . . . . . . . . . . . . . 205 9.3.4 Decision Tree Representations of Factors . . . . . . . . . 206

9.4 Graphical Models . . . . . . . . . . . . . . . . . . . . . . . . . . 208 9.4.1 Showing Belief Networks . . . . . . . . . . . . . . . . . . 209 9.4.2 Example Belief Networks . . . . . . . . . . . . . . . . . . 210

9.5 Inference Methods . . . . . . . . . . . . . . . . . . . . . . . . . 216 9.5.1 Showing Posterior Distributions . . . . . . . . . . . . . . 217

9.6 Naive Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 9.7 Recursive Conditioning . . . . . . . . . . . . . . . . . . . . . . 220 9.8 Variable Elimination . . . . . . . . . . . . . . . . . . . . . . . . 224 9.9 Stochastic Simulation . . . . . . . . . . . . . . . . . . . . . . . . 227

9.9.1 Sampling from a discrete distribution . . . . . . . . . . . 227 9.9.2 Sampling Methods for Belief Network Inference . . . . . 229 9.9.3 Rejection Sampling . . . . . . . . . . . . . . . . . . . . . . 229 9.9.4 Likelihood Weighting . . . . . . . . . . . . . . . . . . . . 230 9.9.5 Particle Filtering . . . . . . . . . . . . . . . . . . . . . . . 231 9.9.6 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 9.9.7 Gibbs Sampling . . . . . . . . . . . . . . . . . . . . . . . . 234 9.9.8 Plotting Behavior of Stochastic Simulators . . . . . . . . 236 9.10 Hidden Markov Models . . . . . . . . . . . . . . . . . . . . . . 238 9.10.1 Exact Filtering for HMMs . . . . . . . . . . . . . . . . . . 240 9.10.2 Localization . . . . . . . . . . . . . . . . . . . . . . . . . . 241 9.10.3 Particle Filtering for HMMs . . . . . . . . . . . . . . . . . 244 9.10.4 Generating Examples . . . . . . . . . . . . . . . . . . . . 246 9.11 Dynamic Belief Networks . . . . . . . . . . . . . . . . . . . . . 247 9.11.1 Representing Dynamic Belief Networks . . . . . . . . . . 247 9.11.2 Unrolling DBNs . . . . . . . . . . . . . . . . . . . . . . . . 250 9.11.3 DBN Filtering . . . . . . . . . . . . . . . . . . . . . . . . . 251

10 Learning with Uncertainty

253

10.1 Bayesian Learning . . . . . . . . . . . . . . . . . . . . . . . . . 253

10.2 K-means . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257

10.3 EM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

11 Causality

267

11.1 Do Questions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

11.2 Counterfactual Example . . . . . . . . . . . . . . . . . . . . . . 269

12 Planning with Uncertainty

273

12.1 Decision Networks . . . . . . . . . . . . . . . . . . . . . . . . . 273

12.1.1 Example Decision Networks . . . . . . . . . . . . . . . . 275

12.1.2 Decision Functions . . . . . . . . . . . . . . . . . . . . . . 281



Version 0.9.11

December 1, 2023

Contents

7

12.1.3 Recursive Conditioning for decision networks . . . . . . 282 12.1.4 Variable elimination for decision networks . . . . . . . . 285 12.2 Markov Decision Processes . . . . . . . . . . . . . . . . . . . . 287 12.2.1 Problem Domains . . . . . . . . . . . . . . . . . . . . . . . 289 12.2.2 Value Iteration . . . . . . . . . . . . . . . . . . . . . . . . 297 12.2.3 Value Iteration GUI for Grid Domains . . . . . . . . . . . 298 12.2.4 Asynchronous Value Iteration . . . . . . . . . . . . . . . . 300

13 Reinforcement Learning

305

13.1 Representing Agents and Environments . . . . . . . . . . . . . 305

13.1.1 Environments . . . . . . . . . . . . . . . . . . . . . . . . . 305

13.1.2 Agents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

13.1.3 Simulating an Environment-Agent Interaction . . . . . . 307

13.1.4 Party Environment . . . . . . . . . . . . . . . . . . . . . . 308

13.1.5 Environment from a Problem Domain . . . . . . . . . . . 309

13.1.6 Monster Game Environment . . . . . . . . . . . . . . . . 310

13.2 Q Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

13.2.1 Exploration Strategies . . . . . . . . . . . . . . . . . . . . 315

13.2.2 Testing Q-learning . . . . . . . . . . . . . . . . . . . . . . 316

13.3 Q-leaning with Experience Replay . . . . . . . . . . . . . . . . 318

13.4 Stochastic Policy Learning Agent . . . . . . . . . . . . . . . . . 320

13.5 Model-based Reinforcement Learner . . . . . . . . . . . . . . . 322

13.6 Reinforcement Learning with Features . . . . . . . . . . . . . . 325

13.6.1 Representing Features . . . . . . . . . . . . . . . . . . . . 326

13.6.2 Feature-based RL learner . . . . . . . . . . . . . . . . . . 329

13.7 GUI for RL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

14 Multiagent Systems

337

14.1 Minimax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

14.1.1 Creating a two-player game . . . . . . . . . . . . . . . . . 337

14.1.2 Minimax and - Pruning . . . . . . . . . . . . . . . . . . 340

14.2 Multiagent Learning . . . . . . . . . . . . . . . . . . . . . . . . 342

14.2.1 Simulating Multiagent Interaction with an Environment 342

14.2.2 Example Games . . . . . . . . . . . . . . . . . . . . . . . . 344

14.2.3 Testing Games and Environments . . . . . . . . . . . . . 345

15 Relational Learning

347

15.1 Collaborative Filtering . . . . . . . . . . . . . . . . . . . . . . . 347

15.1.1 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

15.1.2 Loading Rating Sets from Files and Websites . . . . . . . 354

15.1.3 Ratings of top items and users . . . . . . . . . . . . . . . 355

15.2 Relational Probabilistic Models . . . . . . . . . . . . . . . . . . 357

16 Version History

Version 0.9.11

363 December 1, 2023

8 Bibliography Index

Contents 365 367



Version 0.9.11

December 1, 2023

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download