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

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

Final project presentations:

December 6, 2016, 1-2:30 PM

December 8, 2016, 1-2:30 PM

(also in Cupples I 115)

Instructor

Brendan Juba
Office Hours: Tuesday 2:30-4 PM, Jolley 508
Email:

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.

Monday	Tuesday	Wednesday	Thursday	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)

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: