CSE 513T Theory of Artificial Intelligence and Machine Learning, Fall 2016

Tuesday and Thursday, 1-2:30 PM, Cupples I 115.

Final project presentations:

Instructor

Brendan Juba
Office Hours:   Tuesday 2:30-4 PM, Jolley 508
Email:   first initial last name at wustl

Course Staff

Golnoosh Dehghanpoor, Teaching Assistant
Office Hours:   Wednesday 4-5 PM, Jolley 513

Dingwen Li, Teaching Assistant
Office Hours:   Friday 2:30-3:30 PM, Jolley 431

Connor Basich, Grading Assistant
No Office Hours

Renee Mirka, Grading Assistant
No Office Hours

Description

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.

Pre-requisites

Formally, CSE 240 and 241. (For the present offering, CSE 247 is acceptable, but some additional background in algorithms, theoretical mathematics, or machine learning is strongly recommended.) Informally and more substantially, this class will demand "mathematical maturity." This means 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 ether Algorithms, Machine Learning, or Artificial Intelligence will also be helpful, but no particular course(s) are required or assumed.

Textbook

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 cover the basic definitions and techniques from the theory of Algorithms and Complexity that we will need in our study -- no background in these areas beyond a basic introduction to algorithms and discrete mathematics will be assumed. Some good references for the material we will develop during the semester 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.

Piazza

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/fall2016/cse513t/home

Scribing

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. This initial draft will be due within two days of the lecture. A second member of the class will arrange to edit this initial draft, filling in any gaps as well as polishing and clarifying it. This final version is due one week later. The quality of your scribing or editing will be 10% of your grade for the course. A sign-up sheet will be circulated on the first day 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.)

Scribing and/or editing 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.

Homework

Tentatively, there will be four 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 at the beginning of lecture 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 these are documented properly on each problem (including a full reference to the source) and the text is original -- verbatim copying of a source is not permitted. Students will be required to produce and submit their own, individual writeups.

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/f16.

Calendar

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

L1: Classical Knowledge vs. Induction
Start KV 1.2.1 and 1.2.2
Notes: edited
Aug 31
Sep 1

L2: Knowledge Representations and the PAC-learning model
KV 1.2-1.3
Notes: edited
Sep 2
Sep 5

Holiday
Sep 6

L3:  Basics of Algorithms and Complexity
(see Theory of Computation references)
Notes: edited
Sep 7
Sep 8

L4:  NP-completeness
(see Theory of Computation references)
Notes: edited
Assigned:  Homework 1
Sep 9
Sep 12
Sep 13

L5:  Representation-dependent Hardness and "Improper" Learning
KV 1.4
Notes: edited
Sep 14
Sep 15

L6:  Finish improper learning; Occam's Razor
KV 1.5,2.1-2.2
Sep 16
Sep 19
Sep 20

L7:  Learning decision lists
KV 2.4
Notes: edited
Sep 21
Sep 22

L8:  Agnostic learning, ERM, and uniform convergence
Notes: edited
Due:  Homework 1
Sep 23
Sep 26
Sep 27

L9: Circuits are unlearnable under cryptographic assumptions
KV 6.2-6.3
Notes: edited
Sep 28
Sep 29

L10:  VC-dimension I: Introduction and No Free Lunch
KV 3.1-3.3; 3.6
Notes: unedited
Assigned:  Homework 2
Sep 30
Oct 3
Oct 4

L11:  VC-dimension II: Epsilon-nets and Sauer's Lemma
KV 3.4, 3.5.1
Notes: edited
Oct 5
Oct 6

L12:  VC-dimension III: Sample complexity bound
KV 3.5.2
Notes: edited
Oct 7
Oct 10
Oct 11

L13:  Finish VC-dimension; start deductive reasoning
Notes: unedited
Oct 12
Oct 13

L14: Chaining and resolution
Notes: edited
Due:  Homework 2
Assigned:  Homework 3
Oct 14
Oct 17
Fall Break
Oct 18
Fall Break
Oct 19
Oct 20

L15: SAT solvers and fragments of resolution
Notes: edited
Oct 21
Oct 24
Oct 25

L16: Efficient reasoning and reasoning with examples
Notes: unedited
Oct 26
Oct 27

L17: Common sense and nonmonotonic reasoning
Notes: unedited
Oct 28
Oct 31
Nov 1

L18: Incomplete information and implicit learning
Notes: unedited
Due:  Homework 3
Nov 2
Nov 3

L19: Analysis of implicit learning; introduction to negation-as-failure
Notes: unedited
Assigned:  Homework 4
Nov 4
Nov 7
Nov 8

L20: Well-Founded Semantics for negation-as-failure
Notes: unedited
Nov 9
Nov 10

L21: Algorithm for Well-Founded Semantics
Notes: unedited
Nov 11
Nov 14
Nov 15

L22: Reasoning about actions and change: classical planning
Notes: unedited
Nov 16
Nov 17

L23: Planning under uncertainty
Due:  Homework 4
Notes: unedited
Nov 18
Nov 21
Nov 22

L24: Planning with learned rules
Notes: unedited
Nov 23

Thanksgiving break
Nov 24

Thanksgiving break
Nov 25

Thanksgiving break
Nov 28
Nov 29

L25: Algorithm for planning with learned rules
Notes: unedited
Nov 30
Dec 1

L26: Analysis of algorithm for planning with learned rules
Notes: unedited
Dec 2
Dec 5
Dec 6

Final Project Presentations

Dec 7
Dec 8

Final Project Presentations
Due:  Final Project Write-up
Dec 9

Tentative list of topics

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