Graduate Artificial Intelligence

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.

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.

Name | 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 |

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 conferenceNeural Information Processing Systems: Natural and Synthetic (NIPS) . 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 |

Topic | Files | Due Dates |
---|---|---|

Homework 1 | hw1.pdf (files: problems.py, sample.py) | 2/4 |

Homework 2 | hw2.pdf (files: hw2_handout.tar) | 2/16 |

Homework 3 | hw3.pdf (files: hw3_handout.tar) | 2/28 |

Homework 4 | hw4.pdf (files: hw4_handout.tar) | 3/4 |

Homework 5 | hw5.pdf (files: hw5_handout.tar) | 3/23 |

Homework 6 | hw6.pdf (files: hw6_handout.tar) | 4/19 |

Homework 7 | hw7.pdf (files: hw7_handout.tar) | 4/28 |

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.