Schedule

1. [M 8/29] First half: Introduction (what is AI? state of the art; future), Overview of course. Second half: Scheme part I.

2. [R 9/1] First half: Agents and environments. Second half: Scheme part II.

3. [R 9/8] First half: structuring problems for search, blind searches (BFS, DFS, DLS, UCS). Second half: Scheme parts III and V (list recursion, recursion patterns, functional vs. procedural programming),

4. [M 9/12] First half: Quiz 1, more blind searches (bidirectional search, UCS), BFS in Scheme, avoiding repeated states states. Second half: heuristic search.

5. [R 9/15] First half: Wrap-up of blind search and repeated state strategies, review of best-first searches (uniform cost, greedy, A*), properties of greedy search, A* algorithms (queue and open/closed list), admissibility of heuristics, optimality of A* (informal and formal proof), and Exercise 1. Second half: Scheme part IV (procedures as arguments, map, apply, lambda forms, implicit begins, printing).

6. [M 9/19] First half: review of A* optimality proof (revised slides), properties of A*, consistency, optimal efficiency, dominance of heuristics. Returned Quiz 1 and Exercise 1 and went over Q1 solutions. Second half: creating heuristics via subproblems and relaxed problems.

7. [R 9/22] Review and wrap-up of creating heuristics: pattern databases and learning heuristics. Local search: a different type of problem. Hill climbing and variations, local beam search, simulated annealing, genetic algorithms.

8. [M 9/26] Quiz 2, Constraint satisfaction problems: heuristic repair with the min-conflicts heuristic, "dumb" approach to constructive search, backtracking, forward checking, heuristics for selecting variables (MRV and degree heuristics) and values (least-constraining value heuristic), constraint propagation, handling higher-order constraints, decomposing CSPs by structure (tree/linear constraint graphs, cutset conditioning, and tree decomposition).

9. [R 9/29] Game playing search: two-player, perfect information, zero-sum games, minimax search, perfect versus imperfect decisions, alpha-beta pruning.

10. [M 10/3] Game playing: review of alpha-beta minimax, went over practice exercise 1, correctness of alpha-beta pruning, reduction in branching factor from alpha-beta pruning, finding all optimal moves, issues with game search. Returned Quiz 2 and went over solutions. Second half: creating evaluation functions, expectimax, real game-playing programs.

11. [R 10/6] Search wrapup: beam search (not local beam search); searching with partial information: sensorless problems (search in belief state space), contingency planning, exploration problems; A* as branch and bound with underestimates and dynamic programming; memory-limited A*: IDA* (iterative deepening A*), RBFS (recursive best-first search), SMA* (simplified memory-bounded A*).

12. [T 10/11] Quiz 3, Introduction to logic and knowledge representation, ontological and epistemological commitments, propositional logic, truth tables, inference, interpretations, models, satisfiability, entailment. Scheme Interlude 0.

13. [R 10/13] Review of logic preliminaries leading up to soundness and completeness. Inference in propositional logic: inference process, Horn normal form, forward chaining, backward chaining, conjunctive normal form (CNF), implicative normal form (INF), resolution inference rule, refutation completeness, proofs by contradiction, set of support strategy, unit preference. Scheme Interlude 1.

14. [M 10/17] Brief review of inference in propositional logic, Exercise 2, Satisfiability algorithms (DPLL and WalkSAT). Returned Quiz 3 and went over solutions, finished Scheme Interlude 1.

15. [R 10/20] Propositional logic agents, example agent for the wumpus world; First order logic (FOL): objects, predicates, quantifiers, moving negations inside quantifiers, transforming FOL sentences into CNF, Skolemization, unification.

16. [M 10/24] Additional topics in FOL inference: dealing with equality, axiomizing equality, demodulation, paramodulation.

17. [R 10/27] Logic wrap-up: answer extraction, comparison between inference in proposational logic and FOL (e.g., semidecidability of modus ponens on first order definite clases because of infinitely nested functions). Scheme interlude 2: writing regular expressions in Scheme, a non-regular-expression-based feature detector.

18. [M 10/31] Brief learning introduction: supervised, unsupervised, and reinforcement learning; hypothesis space and Ockham's razor. Learning decision trees: basic algorithm for learning a small decision tree, information gain heuristic, noise and overfitting, rule post-pruning, gain ratio, chi-squared pruning. Returned Quiz 4 and went over solutions.

19. [R 11/3] Decision trees: brief review from last time, finished chi-squared pruning and gain ratio, handling missing attributes (two approaches), handling continuous valued attributes; Ensemble learning (boosting, ADA-boost); PAC learning; learning decision lists.

20. [M 11/7] Quiz 5. Introduction to probability: discrete random events, independence, random variables, axioms of probability, joint probability distributions, conditional probabilities, Bayes' rule, marginalization (aka "summing out"), conditioning (aka "theorem of total probability"), normalization.

21. [R 11/10] Review of probability and Bayes brute force and optimal classifiers from last time, Bayesian updating, conditional independence, Bayes naive classifier, text classification example, m-estimates for estimating probabilities.

22. [M 11/14] Utilities: preferences, lotteries, properties for rational preferences, (existence of) utility functions, money and utility. Sequential decision problems (Markov decision problems): models, policies, utilities, additive utility functions (and stationarity), Bellman equation, value iteration (and relation to numerical relaxation). Returned Quiz 5 and went over solutions.

23. [R 11/17] Sequential decision problems: policy iteration, convergence of policy loss before utility values, use of value iteration in policy iteration (to solve for utilities). Reinforcement learning: active versus passive RL. Passive RL: direct utility estimation, adaptive dynamic programming, temporal differencing, use of value iteration in adaptive dynamic programming (to correct utility values). Active RL: exploration versus exploitation, optimistic utility values, exploration function, adapting a passive RL method for active RL.

24. [M 11/21] Quiz 6. Review of passive and active RL from last time, Q learning, generalization in RL (using a parameterized utility function instead of storing a value for each state).

25. [M 11/28] Exercise 5; Artificial Neural networks: perceptrons, the perceptron learning rule, linearly separable functions, sigmoid units, learning for sigmoid units, gradient descent, stochastic gradient descent. Returned Quiz 6 and went over solutions.

26. [R 12/1] Backpropagation for multi-layer feed-forward networks of sigmoid units, representational power of these networks, convergence of the backpropagation algorithm, determining the number of hidden units necessary by cross-validation or "optimal brain damage". Support vector machines: idea of functions being linearly separable in high dimensional spaces, learning the "optimal" linear classifier, (positive definite) kernel functions computing dot products in high dimensional spaces without computing the feature vectors.

27. [M 12/5] Quiz 7. Review of backpropagation and support vector machines. Instance-based learning: k-nearest neighbor, different distance metrics (Euclidean, Mahalanobis, Hamming), combining neighbors to form an estimate/classification (voting, averaging, weighed versions), cross-validation to determine k, properties (generally effective, robust to noise, "interference" by irrelevant attributes), kernel estimators (called "kernel models" in our text).

28. [R 12/8] Concept learning: learning by selecting hypotheses from the hypothesis space, generalization and specialization of hypotheses, current-best-hypothesis search, version space search (candidate elimination algorithm).