Overview

This course is targeted at graduate students who are interested in learning about artificial intelligence. The focus is on modern AI techniques. The course also covers techniques from the intersection of AI and other disciplines such as integer programming, continuous optimization, and game theory. The course content is profiled so as to not have too much overlap with narrower specialized AI courses offered at CMU.

Prerequisites

No formal pre-requisites. But, substantial programming background is required (assignments will be in Python). Additional background in data structures and algorithms, linear algebra, and probability will all be helpful, but not required.

Office Hours

Name	Email	Hours	Location
Tuomas Sandholm	sandholm@cs	Mon. 12-1pm. Exception: none on 2/15.	GHC 9205
Zhaohan (Daniel) Guo	zguo@cs	Mon. 3-4pm. Exception: 5-6pm on 3/14; 2-3pm on 4/18	GHC 8127
Christian Kroer	ckroer@cs	Tue. 2-3pm.	GHC 9221
J. Zico Kolter	zkolter@cs	Wed. 12-1pm. Exception: none on 2/17.	GHC 7115
Guillermo Cidre	gcidre@andrew	Thurs. 7-8pm.	GHC 4th green sofas near Rashid
Wennie Tabib	wtabib@andrew	Fri. 10-11am	NSH 1113

Schedule

Date	Topic	Readings	Due Dates
1/11	Introduction slides	RN Chapers 1 & 2
1/13	Uninformed Search slides, Constraint Satisfaction slides	RN Chapters 3.1-3.4, begin reading Chapter 6
1/18	MLK Day
1/20	Constraint Satisfaction, SAT	RN Chapter 6
1/25	Constraint Satisfaction, SAT
1/27	Informed Search slides	RN Chapters 3.5-3.7
2/1	Linear Programming slides
2/3	Linear Programming slides
2/8	Advanced Informed Search, Integer Programming slides	Sandholm, T. 2006. Optimal Winner Determination Algorithms. Chapter 14 of the book Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds., MIT Press.
2/10	Advanced Informed Search, Integer Programming
2/15	(Guest lecture) Willem-Jan van Hoeve: Binary Decision Diagrams (BDDs) in Search/MIP	Optional reading, which will be the topic of this lecture: David Bergman, Andre A. Cire, Willem-Jan van Hoeve, J. N. Hooker. 2016. Discrete Optimization with Decision Diagrams. INFORMS Journal on Computing 28(1):47-66.
2/17	(Guest lecture) Michael Trick: Benders' Decomposition in Search/MIP, sports scheduling	Optional reading, which will be the topic of this lecture: Rasmus Rasmussen and Michael A. Trick. 2007. A Benders approach for the constrained minimum break problem. European Journal of Operational Research 177: 198–213.
2/22	Probabilistic Graph Models slides
2/24	Probabilistic Inference slides
2/29	Markov Decision Processes slides
3/2	Reinforcement Learning slides
3/7	Spring break
3/9	Spring break
3/14	Continuous Optimization slides
3/16	Continuous Optimization slides
3/21	Machine Learning slides		Project Proposal Due
3/23	Machine Learning slides
3/28	Midterm
3/30	Deep Learning slides
4/4	Deep Learning Applications - Deep Reinforcement Learning slides
4/6	Game Representations, Solution Concepts, and Complexity slides
4/11	Algorithms for Sequential Complete-Information Games slides	The Nature paper on AlphaGo.
4/13	Rest of AlphaGo. THEN: Algorithms for (Tree) Games of Incomplete Information slides	Sandholm, T. 2010. The State of Solving Large Incomplete-Information Games, and Application to Poker. AI Magazine, special issue on Algorithmic Game Theory, Winter, 13-32.
4/18	Rest of Algorithms for (Tree) Games of Incomplete Information. THEN: Opponent Modeling & Exploitation slides	Ganzfried, S. and Sandholm, T. 2015. Safe Opponent Exploitation. In the Best of EC-12 special issue of ACM Transactions of Economics and Computation (TEAC), 3(2), Article 8, 1-28.
4/20	Algorithms for (Tree) Games of Incomplete Information: Recent Advances in and around the CFR Family slides	Noam Brown and Tuomas Sandholm. 2015. Regret-Based Pruning in Extensive-Form Games. In Proceedings of the Neural Information Processing Systems: Natural and Synthetic (NIPS) conference. Extended version.
4/25	Gradient-Based Algorithms for (Tree) Games of Incomplete Information, and Lossy Game Abstraction with Bounds slides1, slides2	Kroer, C. and Sandholm, T. 2014. Extensive-Form Game Abstraction With Bounds. In Proceedings of the ACM Conference on Economics and Computation (EC). Extended version that includes the appendices.
4/27	Future Directions of AI and Q&A slides1 slides2
5/2	Project Presentations		Project Writeups Due 5/4

Assignments

There will be seven sets of assignments for the course: homeworks will involve both written answers and programming assignments. Written questions will involve working through algorithms presented in the class, deriving and proving mathematical results, and critically analyzing the material presented in class. Programming assignments will involve writing code in Python to implement various algorithms presented in class.

Homework Policies

Strict honor code with severe punishment for violators. CMU’s academic integrity policy can be found here. You may discuss assignments with other students as you work through them, but writeups must be done alone. No downloading / copying of code or other answers is allowed. If you use a string of at least 5 words from some source, you must cite the source

Project

In lieu of a final exam, students will complete a course project. The project can be theoretical, experiment, or both. We encourage creativity in both the project topic choice and execution. One possible type of project is to combine techniques from AI with your own research. Projects will be accompanied by a paper due at the end of the semester and a public poster presentation session.

Proposals

Project proposals should consist of a short (2–3 pages) but well-researched summary of your project idea accompanied by a plan of execution. Students are allowed (and encouraged) to work in groups; however, the expectations we will have for your project rise proportional to the group size. As an example of a reasonable project proposal, please take a look at the following example from a previous Graduate AI (pdf). The proposal begins with motivation and a brief explanation of the problem, and then sets a series of goals. If the project is harder than expected, only the "75%" goals will be completed; if it's difficult level is as expected, the "100%" goals will be completed; finally, if it's easier than expected, the student plans to complete the ambitious "125%" goals as well. The more you plan now, the easier it will be to complete your project well and on time!

Exams

The class has a midterm but no final exam. The midterm will take place during the regular class time on 3/28. A list of the material to be covered during the midterm will be posted here prior to the exam.