Reading plan

Work in progress: this part of the notes is still being revised.

Courses

The order below follows the chapters of this module. Each block lists the material to cover and its primary lectures; further reading and exercises provide additional depth. Blocks 1–13 form the main plan; 14–15 are optional extensions. Timing is flexible.

CS188 slide links are original PDFs and the notes are the course’s own; the videos are the Spring 2024 recordings. Markov decision processes, bandits, and reinforcement learning, which CS188 teaches between games and probability, belong to the RL module; its machine-learning lectures repeat material from ML and DL. Foundations covered probability, Bayes’ rule, and Monte Carlo integration, and ML covered naive Bayes, Gaussian mixtures, and EM; review those chapters as needed in place of CS188’s probability review.

Topic list

Reference books used below

Topics: Agents, environments, and rationality; performance measures; properties of environments; search problems as states, actions, transitions, goals, and costs; the search tree and the state graph; breadth-first, depth-first, uniform-cost, and iterative-deepening search; completeness, optimality, and time and space complexity; tree search versus graph search.

Further reading: AIMA chapters 2 and 3.1–3.4; AIFCA chapters 1 and 3.1–3.5. Foundations’ terminology chapter places AI among the neighboring disciplines.

Topics: Best-first search; greedy search and A; admissible and consistent heuristics; optimality of A for tree and graph search; dominance and the effective branching factor; heuristics from relaxed problems and pattern databases; memory-bounded search with IDA; weighted A and bounded suboptimality.

Further reading: AIMA 3.5–3.6; AIFCA 3.6–3.8. Amit Patel’s notes on A* for games cover heuristics, tie-breaking, and implementation details for grid maps.

Topics: Variables, domains, and constraints; constraint graphs and factor graphs; backtracking search; forward checking and arc consistency (AC-3); variable and value ordering; tree-structured CSPs and cutset conditioning; local search with min-conflicts, hill climbing, simulated annealing, and beam search; the phase transition in random problems.

Further reading: AIMA chapter 6 and 4.1–4.2; AIFCA chapter 4.

4. Adversarial search and games {#4-adversarial-search-and-games}

Topics: Games as search problems; minimax and its optimality against an optimal opponent; alpha–beta pruning and move ordering; depth-limited search and evaluation functions; expectimax for chance and for imperfect opponents; multiplayer games; Monte Carlo tree search and the UCT rule.

Further reading: AIMA chapter 5. The survey by Browne et al. (2012) catalogues Monte Carlo tree search variants.

5. Propositional logic and satisfiability {#5-propositional-logic-and-satisfiability}

Topics: Knowledge-based agents; syntax and semantics of propositional logic; models, entailment, validity, and satisfiability; inference by model checking; proof rules and resolution; conjunctive normal form; Horn clauses with forward and backward chaining; DPLL, conflict-driven clause learning, and WalkSAT; hardness and the satisfiability threshold.

Further reading: AIMA chapter 7; AIFCA chapter 5.

6. First-order logic and knowledge representation {#6-first-order-logic-and-knowledge-representation}

Topics: Objects, relations, and functions; terms, quantifiers, and models; translating knowledge into first-order sentences; propositionalization; unification and generalized modus ponens; forward chaining and Datalog; backward chaining and logic programming; resolution and its completeness; semidecidability; ontologies, categories, and description logics; the closed-world assumption and negation as failure.

Further reading: AIMA chapters 8–10; AIFCA chapters 15–16 on individuals, relations, knowledge graphs, and ontologies.

7. Automated planning {#7-automated-planning}

Topics: Planning tasks in STRIPS and PDDL; forward (progression) and backward (regression) search; the complexity of planning; planning as satisfiability; the delete relaxation and the heuristics \(h^{\max}\), \(h^{\text{add}}\), and \(h^{\text{FF}}\); landmarks; partial-order and hierarchical planning; where planning under uncertainty begins.

Further reading: AIMA chapter 11; AIFCA chapter 6.

8. Bayesian networks and Markov networks {#8-bayesian-networks-and-markov-networks}

Topics: Joint distributions and the cost of tables; directed graphical models and their factorization; conditional independence and d-separation; the Markov blanket; I-maps and perfect maps; undirected models, potentials, and the Hammersley–Clifford theorem; factor graphs; converting between representations.

Further reading: AIMA 13.1–13.2; PGM chapters 3–4; CS188 textbook 6.3–6.5.

9. Exact inference {#9-exact-inference}

Topics: Inference by enumeration; variable elimination and factor operations; elimination orderings, induced width, and treewidth; the hardness of inference; sum-product message passing on trees; the junction tree algorithm; MAP inference with max-product; exact inference as a baseline for approximation.

Further reading: AIMA 13.3; PGM chapters 9–10 and 13.

10. Approximate inference {#10-approximate-inference}

Topics: Prior sampling, rejection sampling, and likelihood weighting; importance sampling and effective sample size; Markov chains and their stationary distributions; Gibbs sampling and Metropolis–Hastings; mixing and diagnostics; variational inference as optimization, the evidence lower bound, and mean field; loopy belief propagation and the Bethe approximation.

Further reading: AIMA 13.4; PGM chapters 11–12. Blei, Kucukelbir, and McAuliffe, Variational Inference: A Review for Statisticians, is the standard introduction to modern variational methods; Wainwright and Jordan’s monograph (listed with the books) develops the theory.

11. Temporal probabilistic models {#11-temporal-probabilistic-models}

Topics: Markov chains and stationarity; hidden Markov models; filtering with the forward algorithm, prediction, and smoothing with forward–backward; the most likely sequence and the Viterbi algorithm; learning with Baum–Welch; linear-Gaussian models and the Kalman filter; dynamic Bayesian networks; particle filtering.

Further reading: AIMA chapter 14; Rabiner’s tutorial on hidden Markov models; Thrun, Burgard, and Fox, Probabilistic Robotics, chapters 2–4, for Bayes filters in robotics.

12. Decision theory and the value of information {#12-decision-theory-and-the-value-of-information}

Topics: Preferences, lotteries, and the axioms of rationality; the von Neumann–Morgenstern utility theorem; utility of money and risk attitudes; multiattribute utility; decision networks and their evaluation; the value of perfect information and its properties; limits of the expected-utility model.

Further reading: AIMA chapter 16; AIFCA 12.1–12.3. Foundations’ statistics chapter treats losses, risk, and Bayes decisions for estimation; this block adds where utilities come from and how to decide what to observe.

13. Causal inference {#13-causal-inference}

Topics: Association and causation; potential outcomes; structural causal models and interventions; the do-operator and the truncated factorization; confounding, the backdoor and frontdoor criteria; the rules of do-calculus; estimation by adjustment and inverse propensity weighting; instrumental variables; counterfactuals; causal discovery from independence tests.

Further reading: ECI chapters 1–7; AIFCA chapter 11; Hernán and Robins, Causal Inference: What If, for the potential-outcomes view used in epidemiology.

14. Learning graphical models — optional {#14-learning-graphical-models-optional}

Topics: Maximum likelihood for Bayesian networks with complete data; Dirichlet priors and Bayesian estimation; log-linear models and the moment-matching gradient; pseudolikelihood; missing data and EM in Bayesian networks; structure learning by score (BIC, the Chow–Liu tree) and by independence tests; conditional random fields.

Further reading: PGM chapters 17–20; AIMA chapter 20.

15. Game theory and multiagent systems — optional {#15-game-theory-and-multiagent-systems-optional}

Topics: Normal-form games; dominance and best responses; pure and mixed Nash equilibria; zero-sum games, the minimax theorem, and linear programming; correlated and coarse correlated equilibria; no-regret learning and its convergence to equilibrium; extensive-form games and subgame perfection; mechanism design, auctions, and the VCG mechanism; the price of anarchy.

Further reading: Shoham and Leyton-Brown, Multiagent Systems (free PDF), chapters 3–5 and 10–11; AIMA chapter 18; AIFCA chapter 14.

Exercises and local references

Connections to later modules

Markov decision processes, dynamic programming, bandits, and reinforcement learning belong in RL, which extends the search, games, and decision theory of this module to sequential decisions with learned values. Variational autoencoders and diffusion models in Generative AI build on the variational inference of block 10. Language models in NLP and LLMs replace the hand-built knowledge of blocks 5–6 with learned representations, and their decoding uses the search of blocks 1–2. Safety and Frontier returns to rational agency, utility, and causal reasoning. Search, logic, planning, graphical models, decisions, and causality remain in this module.