CSE 513T Theory of Artificial Intelligence and Machine Learning, Spring 2018

Tuesday and Thursday, 4-5:30 PM, Cupples I 215.

Final project presentations:


Brendan Juba
Office Hours:   Tuesday/Thursday 5:30-6:15 PM, Jolley 508
Email:   first initial last name at wustl

Course Staff

Alex Durgin, Teaching Assistant
Office Hours:   Fridays 3-4 PM, Jolley 431 (starting Jan. 26)

Zongyi Li, Teaching Assistant
Office Hours:   Monday 5:30-6:30 PM, Jolley 517

Rudy Zhou, Grading Assistant
No Office Hours


Mathematical foundations for Artificial Intelligence and Machine Learning. An introduction to the PAC-Semantics ("Probably Approximately Correct") as a common semantics for knowledge obtained from learning and declarative sources, and the computational problems underlying the acquisition and processing of such knowledge. We will emphasize the design and analysis of efficient algorithms for these problems, and examine for which representations these problems are known or believed to be tractable.


Formally, CSE 347 or an equivalent algorithms course. This class will demand "mathematical maturity," meaning that you should be comfortable reading and producing mathematical arguments, i.e., "proofs." A key part of this course will be coming up with and clearly presenting such proofs on the homework. A prior course in Machine Learning or Artificial Intelligence will also be helpful, but no particular course(s) are required or assumed.


An Introduction to Computational Learning Theory by Kearns and Vazirani will be required for some assignments. I will indicate which sections of the book are covered in lecture on the calendar, although the book only covers around half of the material in the course.

Theory of Computation references

In lecture, we will assume knowledge of an undergraduate algorithms course that includes an introduction to NP-completeness, e.g., at the level of CSE 347. We will build on these somewhat more abstract parts of the Theory of Computation. Some good references for this material are Introduction to the Theory of Computation by Michael Sipser (any edition will do) and/or Computers and Intractability by Garey and Johnson. If you prefer, lecture notes/slides are available for courses on this material, 6.080 and 6.045/18.400, on MIT's OpenCourseWare.


All students enrolled in the class are automatically signed up for Piazza, a website for facilitating discussions about classes. Please register as soon as you receive the e-mail, if you haven't already. All questions that are not of a personal nature should be posted to Piazza. You will find it helpful when your classmates have already asked a question for you, with an answer already posted. But, in order to sustain this, you must ask your questions to Piazza as well, and so we will strictly maintain this policy.

The Piazza page for this class is located at piazza.com/wustl/spring2018/cse513t/home


Each lecture, a member of the class will arrange to scribe lecture notes, and create a LaTeX version of these notes. You will want to use this sample file as a template, which requires the file preamble.tex to specify its commands. You will have one week to produce a polished, complete, and correct write-up of the lecture's contents. You should submit your final write-up (source files and pdf) via e-mail to Professor Juba. The quality of your scribe notes will be 10% of your grade for the course. A sign-up sheet for the remainder of the semester will be circulated in the second week of class. If you do not manage to sign up (or if you drop the class after signing up) please let me know. If you are new to LaTeX, you will likely want to either obtain one of the many GUIs available or seek out some tutorials. (Try The LaTeX wikibook as a starting point.)

Preparing these notes will help you learn to write clearly; you will find that writing clearly will in turn require you to gain a clearer understanding of the material being presented. Moreover, the scribe notes prepared by your classmates will help you. Remember, there is no text covering about half of the material in this course -- it is up to you and your classmates together to assemble the reference you will use.


Tentatively, there will be nine homework assignments, worth 40% of your final grade. You are encouraged to work in a group of up to three members. You must individually write up and submit solutions to the homework problems, however.

Homework is an essential component of this course and lectures will sometimes refer to the results of homework problems. We will be using electronic homework submissions this semester: your homeworks will need to be electronically typeset and submitted via Blackboard. Please see the E-Homework Guide for details on how to submit your homework assignments and retrieve your graded assignments. The course calendar contains a tentative schedule for the homework assignments. Homework will be due before midnight on the indicated day. You have a total of 4 late days per semester at no grade penalty. At most two days late may be used per assignment. If you have used up these four late days, your score will be reduced by 25% off of the total (not yours) score per late day. (Note that days on the weekend still count as late days!)

The homework problems will be graded on a three point scale, "check+," "check," and "check-." These roughly mean:
Check+: complete and correct.
Check  : on the right track, but missing some essential detail(s).
Check- : missed the idea.
Zero points will be awarded if no attempt has been made at the problem, or if the submission is found to be in violation of the academic integrity policy (below).

Final Project

This course has a final project. You have substantial latitude in choosing a topic for this project -- it may be to try to solve a small research problem, to survey the state of knowledge on a topic that we didn't get to discuss in class, or even to apply some of what we've learned in building a system. You will want to start thinking about what you might want to do for your project around the middle of the course. You should discuss your planned project with me before you get started, so that we can ensure that its scope is reasonable and it is appropriate to the course.

For the final project, you are strongly encouraged to work in a group of (up to) three members. Your group will be responsible for preparing a five page writeup (possibly with an Appendix of arbitrary length that I will read at my discretion) as well as a ten minute presentation. Towards the end of the course I will circulate a sign-up sheet for presentation slots. All together, the final project will count for 50% of your final grade.

Collaboration and Academic Integrity policy

On homeworks, students are highly encouraged to collaborate, and are permitted to use any sources whatsoever so long as Students should also note their collaborators on their submissions. Each student will be required to produce and submit his or her own, individual writeup.

Disability Resources

Students with disabilities or suspected disabilities are strongly encouraged to both bring any additional considerations to the attention of the instructors and make full use of the University's Disability Resource Center (http://disability.wustl.edu).

Course Website

An up-to-date version of this document appears on the web at http://www.cse.wustl.edu/~bjuba/cse513t/s18.


The schedule of lecture topics and assignments may be subject to change as the semester progresses.
MondayTuesday WednesdayThursday Friday
Jan 15

Jan 16

L1: Classical Knowledge vs. Induction
Start KV 1.2.1 and 1.2.2
Jan 17
Jan 18

L2: Knowledge Representations and the PAC-learning model
KV 1.2-1.3
Jan 19
Jan 22
Jan 23

L3:  Complexity of representations
(see Theory of Computation references)
Assigned:  Homework 1
Jan 24
Jan 25

L4:  Representing computation
(see Theory of Computation references)
Jan 26
Jan 29
Jan 30

L5:  Representation-dependent Hardness and "Improper" Learning
KV 1.4, 1.5
Due:  Homework 1
Assigned:  Homework 2
Jan 31
Feb 1

L6:  Occam's Razor
KV 2.1-2.2, start 2.4
Feb 2
Feb 5
Feb 6

L7:  VC-dimension I: introduction and examples
KV 3.1-3.3; start 3.6
Due:  Homework 2
Assigned:  Homework 3
Feb 7
Feb 8

L8:  VC-dimension II: No Free Lunch and Epsilon-nets
KV 3.6, 3.5.1, start 3.4
No scribe; see s15 version or f16 version
Feb 9
Feb 12
Feb 13

L9:  VC-dimension III: Sauer's Lemma
KV 3.4, start 3.5.2
Due:  Homework 3
Assigned:  Homework 4
Feb 14
Feb 15

L10:  VC-dimension IV: Sample complexity bound
KV 3.5.2
Feb 16
Feb 19
Feb 20

L11:  Circuits are unlearnable under cryptographic assumptions
KV 6.2-6.3
No scribe; see f16 version
Due:  Homework 4
Assigned:  Homework 5
Feb 21
Feb 22

L12:  Deductive reasoning
No scribe; see s15 version or f16 version (part 1),f16 version (part 2)
Feb 23
Feb 26
Feb 27

L13:  Resolution and SAT solvers
No scribe; see s15 version or f16 version (part 1),f16 version (part 2)
Due:  Homework 5
Assigned:  Homework 6
Feb 28
Mar 1

L14:  Fragments of resolution and efficient reasoning; reasoning with examples
No scribe; see s15 version or f16 version
Mar 2
Mar 5
Mar 6

L15:  Agnostic learning, ERM, and uniform convergence
Due:  Homework 6
Assigned:  Homework 7
Mar 7
Mar 8

L16:  Common sense and nonmonotonic reasoning
Mar 9
Mar 12
Spring Break
Mar 13
Spring Break
Mar 14
Spring Break
Mar 15
Spring Break
Mar 16
Spring Break
Mar 19
Mar 20

L17:  Incomplete information and implicit learning
Due:  Homework 7
Assigned:  Homework 8
Mar 21
Mar 22

L18:  Analysis of implicit learning; introduction to negation-as-failure
Mar 23
Mar 26
Mar 27

L19:  Well-Founded Semantics for negation-as-failure
No scribe; see s15 version (part 1), s15 version (part 2) or f16 version (part 1), f16 version (part 2)
Due:  Homework 8
Mar 28
Mar 29

L20:  Algorithm for Well-Founded Semantics; start planning
No scribe; see s15 version or f16 version
Mar 30
Apr 2
Apr 3

L21:  Reasoning about actions and change: classical planning
Due:  Project proposal
Assigned:  Homework 9
Apr 4
Apr 5

L22:  Planning under uncertainty
Apr 6
Apr 9
Apr 10

L23:  Planning with learned rules
Due:  Homework 9
Apr 11
Apr 12

L24:  DNF is not learnable unless random k-SAT is easy
Apr 13
Apr 16
Apr 17

L25:  Algorithm for planning with learned rules
No scribe; see f16 version
Apr 18
Apr 19

L26:  Analysis of algorithm for planning with learned rules
No scribe; see f16 version
Apr 20
Apr 23
Apr 24

Final Project Presentations

Apr 25
Apr 26

Final Project Presentations
Due:  Final Project Write-up
Apr 27

Course Websites from Prior Offerings

Fall 2016, Spring 2015

Tentative list of topics

Part I: PAC learning theory (~13 lectures) Part II: PAC reasoning (~13 lectures)