Introduction & Logic [Geoff ~3 Lectures]
Reading: Russell & Norvig Chapters 7-9
- Propositional Logic
- First-order Logic
- Proofs
- resolution
- unification
- Satisfiability
Tues., Jan. 13:
- Lecture: Introducton to AI and Logic. [Slides] [Annotated]
Thurs., Jan. 15:
- Lecture: Proofs and First Order Logic. [Slides] [Annotated]
Tue., Jan. 20:
- Lecture: FOL proofs, completeness, and SAT [Slides] [Annotated]
Thurs., Jan. 22:
- First Half of Lecture: Satisfiability (Geoff) [Slides] [Updated]
- Second Half of Lecture: Search (Tuomas) [Slides(.ppt)] [Slides(.pdf)]
[Top]
Search & Optimization [Tuomas ~9 Lectures]
Topics:
- Theorem Proving as Search
- Constraint Satisfaction Problems
- variable and value ordering heuristics
- forward checking
- arc consistency
- conflict-directed backjumping
- constraint/clause learning
- cutsets
- tree decomposition
- phase transitions
- iterative refinement
- DPLL
- Optimization
- informed search (i.e. with an objective and h-function)
- MIP including Gomory mixed integer cut
- pseudo-boolean inequalities
- relating CSP, (Max)SAT, and MIP
- binary search on objective value
- relating clause learning & cuts
- relating resolution, LP relaxation, and cuts
- Optional Topic: RRTs/spatial search (Geoff)
Tues., Jan. 27:
- Constraint Satisfaction Problems [Slides(.ppt)] [Slides(.pdf)]
Thurs., Jan. 29:
- Constraint Satisfaction Problems (continued) [Slides(.ppt)] [Slides(.pdf)]
Tues., Feb. 3:
- Constraint Satisfaction Problems (continued) [Slides(.ppt)] [Slides(.pdf)]
Thurs., Feb. 5:
- Constraint Satisfaction Problems (continued) [Slides(.ppt)] [Slides(.pdf)]
- Russell & Norvig Chapter 5
- "GRASP: A Search Algorithm for Propositional Satisfiability", Marques-Silva & Sakallah, IEEE Trans. Computers, C-48, 5:506-521,1999
- "Chaff: Engineering an Efficient SAT Solver", Moskewicz, Madigan, Zhao, Zhang & Malik, 2001
- "BerkMin: A Fast and Robust Sat-Solver", Goldberg & Novikov, Proc. DATE 2002, pp. 142-149
- The slides on efficient boolean satisfiability here
- "Conflict-directed backjumping revisited", by Chen and van Beek, Journal of AI Research, 14, 53-81, 2001
Tues., Feb. 10:
- Informed Search [Slides(.ppt)] [Slides(.pdf)]
Thurs., Feb. 12:
- Informed Search [Slides(.ppt)] [Slides(.pdf)]
- Advanced Informed Search [Slides(.ppt)] [Slides(.pdf)]
- Sandholm, T. 2006. "Optimal Winner Determination Algorithms", Chapter 14 of the book Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press.
Tues., Feb. 17:
- Advanced Informed Search [Slides(.ppt)] [Slides(.pdf)]
Thurs., Feb. 19:
- Advanced Informed Search [Slides(.ppt)] [Slides(.pdf)]
[Top]
Linear Programs, Convex Programs, Duality [Geoff ~2 Lectures]
Reading:
- Boyd & Vandenberghe. Convex Optimization Sec 4.3.
- V. Vazirani. Approximation Algorithms. Ch 12.
Tues., Feb. 24:
- Optimization, Duality [Slides(.pdf)]
Thurs., Feb. 26:
- Duality [Slides(.pdf)]
- Multiple ways to write TSP as MIP [see lectures 1, 3]
- Lift and project cuts
- Another recent family of cuts
- Smoothed analysis
- MINISAT+ (software for solving PBIs)
[Top]
Planning [Geoff ~2 Lectures]
Reading: Russell & Norvig Ch 11-12
- Partial order planning
- Graphplan / SATplan
Tues., March 3rd:
- Duality and Planning [Slides(.pdf)]
Thurs., March 5th:
- Spatial Search; Uncertainty [Slides(.pdf)]
[Top]
Probabilistic Inference [Geoff ~4 Lectures]
Reading:
- (Optional) Factor graphs and the sum-product algorithm (2001) Frank R. Kschischang, Brendan J. Frey, Hans-Andrea Loeliger
- Basic Probability
- marginals
- conditionals
- integration/summation
- Maximum Likelihood
- relation to optimization
- partition function
- natural/expectation parameters
- Undirected Graphical Models (MRFs)
- relation to SAT
- variable elimination
- factor graph inference
- Gradient Descent Learning
- MCMC
- MH
- Gibbs
- particle filters
- Optional Topics (if we have time)
- HMMs/POMDPS/RL
- EM algorithm
Tues., March 9th:
- Uncertainty, Inference [Slides(.pdf)]
Tues., March 17th:
- Inference [Slides(.pdf)]
Thurs., March 19th:
- Inference, Learning [Slides(.pdf)]
Tues., March 24th:
- Learning [Slides(.pdf)]
Thurs., March 26th:
- Learning [Slides(.pdf)]
Tues., March 31th:
- Learning [Slides(.pdf)]
[Top]
Game Playing, Equilibrium Finding [Tuomas ~6 Lectures]
- Game Types, Normal Form, Extensive Form, Solution Concepts, Solution Complexity
- Algorithms for Solving Normal Form Games
- Lemke-Howson
- PNS
- MIP Nash
- LP for zero sum games
- Complete Information Sequential Games
- Case: Deep Blue for chess
- Incomplete Information Sequential Games
- sequence form
- Gameshrink for automated (lossless) abstraction
- Case: Poker
- Correlated Equilibrium (Geoff)
Thurs., April 2nd:
- Game Theory [Slides1(.pdf)] [Slides1(.ppt)] [Slides2(.pdf)] [Slides2(.ppt)]
Tues., April 7th:
Tues., April 21st:
- Sequential Games [Slides(.pdf)] [Slides(.ppt)]
Thurs., April 23rd:
- Sequential Games [Slides(.pdf)] [Slides(.ppt)]
Tues., April 28th:
- Sequential Games [Slides(.pdf)] [Slides(.pptx)] [Slides(.ppt)]
[Top]
Multiagent Learning [Geoff ~2 Lectures]
- No-external-regret
- No-Phi-regret
[Top]
Mechanism Design [Tuomas 1 Lecture]
- Mechanism Design Setting
- Gibbard-Satterthwaite Impossibility
- Vickrey-Clarke-Groves Mechanism
- Auctions
- Automated Mechanism Design
[Top]