| General |
| Sep 27 | Course content | | What are we covering in this course? |
| Sep 27 | AI History | | Three histories of AI (logical, neural, statistical). |
| Sep 27 | Ethics and responsibility | | How should we think about the societal impacts of AI? |
| Prerequisites |
| offline | Linear algebra | | Vectors, dot products, geometric interpretations. |
| offline | Vector calculus | | Taking gradients. |
| offline | Probability 1 | | Discrete random variables and probability distributions, mean, variance (from Khan Academy). |
| offline | Probability 2 | | Marginal and conditional distributions (from Khan Academy). |
| offline | Complexity | | Basic big-Oh notation, complexity. |
| offline | Optimization | | Continuous optimization, objective functions, gradient descent. |
| offline | Python | | Tutorial on using Python for this course. |
| Machine learning |
| Oct 2 | Overview | | Overview of machine learning. |
| Oct 2 | Linear regression | | Linear regression (with loss minimization and gradient descent). |
| Oct 2 | Linear classification | | Linear classification (with loss minimization using hinge loss and gradient descent). |
| offline | Stochastic gradient descent | | Stochastic gradient descent. |
| optional | Learning demo | | Interactive learning demo for supervised learning and k-means. |
| Oct 4 | Group DRO | | How to ensure more equitable performance. |
| offline | Non-linear features | | How to get non-linear functions from linear machinery. |
| offline | Feature templates | | How to design and organize features. |
| Oct 4 | Neural networks | | Introduction to neural networks. |
| Oct 4 | Backpropagation | | Computation graphs and backpropagation algorithm for computing gradients. |
| offline | Algorithms and distribution | | Ethical frameworks related to how algorithms distribute burdens and benefits. |
| optional | Differentiable programming | | How to build larger deep learning models by composition. |
| Oct 9 | Generalization | | Basic introduction into generalization. |
| Oct 9 | Best practices | | Best practices, cross-validation, etc. |
| Oct 9 | K-means | | K-means algorithm. |
| Search |
| Oct 11 | Overview | | Going from single action to sequences. |
| Oct 11 | Modeling | | Defining search problems. |
| Oct 11 | Tree search | | (Prerequisite) Basic exhaustive search, BFS, DFS. |
| Oct 11 | Dynamic programming | | Recurrences, practice forming states. |
| Oct 11 | Uniform cost search | | Uniform cost search (UCS). |
| Oct 11 | Uniform cost search correctness | | Programming UCS and proving correctness. |
| offline | Externalities and dual use technologies | | Explaining externalities and dual use technologies. |
| optional | Structured perceptron | | Learning the costs of a search problem. |
| offline | A-star | | Speeding up UCS with heuristics. Correctness, efficiency, and admissibility. |
| offline | A-star relaxations | | Generating heuristics using relaxed search problems. |
| offline | Recap | | Recap of search. |
| Markov Decision Processes (MDPs) |
| Oct 18 | Overview | | Motivating MDPs. |
| Oct 18 | Modeling | | Defining MDPs, Dice game, transportation problem. |
| Oct 18 | Policy evaluation | | Policy evaluation, discounting factor. |
| Oct 23 | Value iteration | | Value iteration. |
| Oct 23 | Reinforcement learning | | Introducing to reinforcement learning. |
| Oct 23 | Model-based Monte Carlo | | Model-based Monte Carlo. |
| offline | Model-free Monte Carlo | | Model-free Monte Carlo. |
| optional | SARSA | | SARSA, Model-free Monte Carlo vs SARSA. |
| offline | Q-learning | | Q-learning, on-policy vs off-policy. |
| offline | Epsilon-greedy | | Epsilon-greedy exploration. |
| offline | Function approximation | | Generalization, Function approximation. |
| offline | Recap | | Recap of MDPs and reinforcement learning, Deep RL, and applications. |
| Games |
| Oct 25 | Overview | | Overview of games. |
| Oct 25 | Modeling | | Definition of games, Halving game. |
| Oct 25 | Game evaluation | | Given two policies, what is the value of the game? |
| Oct 25 | Expectimax | | Find the optimal agent policy against a fixed (random) opponent policy. |
| Oct 25 | Minimax | | Find the optimal agent (max) policy against the worst-case (min) opponent policy. |
| Oct 30 | Expectiminimax | | Minimax with randomness in the game. |
| Oct 30 | Evaluation functions | | Limited depth DFS and bottom out with a cheap evaluation function. |
| Oct 30 | Alpha beta pruning | | Alpha-beta pruning to speed up minimax. |
| optional | AI Misalignment | | The AI Alignment problem, specifically reward hacking and negative side effects. |
| optional | TD learning | | Temporal Difference (TD) learning for learning the value function. |
| optional | Simultaneous games | | Two players go at the same time, pure and mixed strategies, minimax theorem. |
| optional | Non-zero-sum games | | Prisoner's Dilemma, Nash equilibria. |
| Oct 30 | Recap | | Recap of games, and applications. |
| Constraint satisfaction problems |
| Nov 1 | Overview | | Overview of variable-based models. |
| Nov 1 | Definitions | | Factor graphs (variables, factors, assignments, weights). |
| Nov 1 | Examples | | Examples of factor graphs. |
| Nov 6 | Dynamic ordering | | Backtracking search, re-order the variables and values. |
| Nov 6 | Arc consistency | | Prune the domains locally based on factors. AC-3 algorithm to use in the context of exhaustive search. |
| Nov 6 | Beam search | | Approximate search (pruned BFS). |
| Nov 6 | Local search | | Start with an assignment and improve each variable greedily. |
| optional | Inference demo | | Interactive inference demo for factor graphs. |
| Markov networks |
| Nov 8 | Overview | | Connect factor graphs with probability. |
| offline | Gibbs sampling | | Gibbs sampling for computing marginal probabilities. |
| offline | Encoding human values | | Encoding human values in AI systems. |
| optional | Conditional independence | | Exploit conditional independence in Markov networks (slides only). |
| Bayesian networks |
| Nov 8 | Overview | | Overview of Bayesian networks. |
| Nov 8 | Definitions | | Bayesian networks, properties, explaining away, etc. |
| offline | Probabilistic programming | | View Bayesian networks as a program, whirlwind tour of lots of models. |
| Nov 13 | Probabilistic inference | | Inference in general Bayesian networks via reduction to Markov networks. |
| Nov 13 | Forward-backward algorithm | | Efficient exact inference algorithm for HMMs. |
| Nov 13 | Particle filtering | | Approximate inference alogrithm for HMMs with large domains. |
| Nov 15 | Supervised learning | | Learning parameters of a Bayesian network when all variables are observed. Maximum likelihood = counting + normalize. |
| Nov 15 | Smoothing | | Laplace smoothing to avoid overfitting. |
| Nov 15 | EM algorithm | | Learning parameters of a Bayesian network when only a subset of variables are observed. Maximum marginal likelihood using EM. Application to decipherment. |
| Logic |
| Nov 27 | Overview | | Motivation for logic (represent and reason). |
| Nov 27 | Propositional logic syntax | | Syntax of propositional logic. |
| Nov 27 | Propositional logic semantics | | Semantics of propositional logic. General concepts such as entailment, contradiction, contingency, Ask/Tell, satisfiability, model checking. |
| Nov 27 | Inference rules | | Soundness, completeness. |
| Nov 29 | Propositional modus ponens | | Modus ponens is sound and complete for propositional logic with Horn clauses. |
| Nov 29 | Propositional resolution | | Resolution is sound and complete for propositional logic. Conversion to Conjunctive Normal Form (CNF). |
| Nov 29 | First order logic | | Syntax and semantics of first-order logic. |
| offline | First order modus ponens | | Modus ponens generalized to first-order logic requires notions of substitution and unification. |
| optional | First order resolution | | Generalizes resolution to first-order logic. Conversion to CNF, Skolem functions. |
| offline | Recap | | Recap of logic. |