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

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

Final project presentations:

April 24, 2018, 4-5:30 PM (in class)

April 26, 2018, 4-5:30 PM (in class)

Instructor

Brendan Juba
Office Hours: Tuesday/Thursday 5:30-6:15 PM, Jolley 508
Email:

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

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

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

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

Homework

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

these are documented properly on each problem (including a full reference to the source -- i.e. author, title, publication date, and so on) and

the text is original -- verbatim copying of a source is not permitted. 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.

Calendar

The schedule of lecture topics and assignments may be subject to change as the semester progresses.

Monday	Tuesday	Wednesday	Thursday	Friday
Jan 15 Holiday	Jan 16 L1: Classical Knowledge vs. Induction Start KV 1.2.1 and 1.2.2 notes	Jan 17	Jan 18 L2: Knowledge Representations and the PAC-learning model KV 1.2-1.3 notes	Jan 19
Jan 22	Jan 23 L3: Complexity of representations (see Theory of Computation references) notes Assigned: Homework 1	Jan 24	Jan 25 L4: Representing computation (see Theory of Computation references) notes	Jan 26
Jan 29	Jan 30 L5: Representation-dependent Hardness and "Improper" Learning KV 1.4, 1.5 notes Due: Homework 1 Assigned: Homework 2	Jan 31	Feb 1 L6: Occam's Razor KV 2.1-2.2, start 2.4 notes	Feb 2
Feb 5	Feb 6 L7: VC-dimension I: introduction and examples KV 3.1-3.3; start 3.6 notes 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 notes Due: Homework 3 Assigned: Homework 4	Feb 14	Feb 15 L10: VC-dimension IV: Sample complexity bound KV 3.5.2 notes	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 notes Due: Homework 6 Assigned: Homework 7	Mar 7	Mar 8 L16: Common sense and nonmonotonic reasoning notes	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 notes Due: Homework 7 Assigned: Homework 8	Mar 21	Mar 22 L18: Analysis of implicit learning; introduction to negation-as-failure notes	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 notes Due: Project proposal Assigned: Homework 9	Apr 4	Apr 5 L22: Planning under uncertainty notes	Apr 6
Apr 9	Apr 10 L23: Planning with learned rules notes Due: Homework 9	Apr 11	Apr 12 L24: DNF is not learnable unless random k-SAT is easy notes	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)

Knowledge representation

Inductive generalization in the PAC model

Computational complexity: efficient algorithms and the expressive power of representations

Representation-dependent hardness and proper vs. improper learning

Occam's razor and applications

Agnostic learning vs. realizable learning

Vapnik-Chervonenkis dimension

Cryptography and concepts that cannot be learned, independent of representation Part II: PAC reasoning (~13 lectures)

Logic and PAC-Semantics

Reasoning with examples

Nonmonotonic effect of conditioning

Incomplete information

Propositional proof systems -- Resolution and its fragments

Algorithms for resolution -- SAT-solvers

Restrictions and implicit learning

Application: