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

Tuesday and Thursday, 10-11:30 AM, Cupples II L015.

Instructor

Brendan Juba
Office Hours:   Wednesday 3:30-5 PM, Bryan 522 (or by appointment)
Email:   first initial last name at wustl

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

I recommend An Introduction to Computational Learning Theory by Kearns and Vazirani as a basic reference. 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.

Other references

You may find Artificial Intelligence: Foundations of Computational Agents by Poole and Mackworth (available online for free at the link) helpful as an introduction to Artificial Intelligence more broadly from the framework of mathematical logic. This may aid your understanding of how the theory developed here connects to the larger field of Artificial Intelligence. Keep in mind that Poole and Mackworth aim to give a much broader view of the field and do not use our framework of PAC Semantics.

PAC Semantics was originally developed by Valiant alongside the neuroidal cognitive model introduced in Circuits of the Mind. This book is focused primarily on modeling the brain, but it discusses the basic issues of learning and reasoning in the context of the model it develops.

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/spring2015/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 20% 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 three or four homework assignments, worth 40% of your final grade. You are encouraged to work in a group of up to three members. Your group may jointly prepare and submit solutions to the homework problems.

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.
The course calendar contains a tentative schedule for the homework assignments. 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.

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.

As with the homework, 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 40% 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.

Course Website

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

Calendar

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

L1: Classical Knowledge vs. Induction
Start KV 1.2.1 and 1.2.2
Notes: Unedited		 Jan 14
 Jan 15

L2: Knowledge Representations and the PAC-learning model
KV 1.2-1.3
Notes: Edited
 Jan 16
Jan 19

Holiday
 Jan 20

L3:  Basics of Algorithms and Complexity
(see Theory of Computation references)
Notes: Edited
 Jan 21
 Jan 22

L4:  NP-completeness; Representation-dependent Hardness and "Improper" Learning pt. I
start KV 1.4
Notes: Unedited
Assigned:  Homework 1
 Jan 23
Jan 26
 Jan 27

L5:  Representation-dependent Hardness and "Improper" Learning pt. II
KV 1.4-1.5
Notes: Unedited
 Jan 28
 Jan 29

L6:  Occam's Razor
KV 2.1-2.2, 2.4
Notes: Unedited
 Jan 30
Feb 02
 Feb 03

L7:  Agnostic Learning
Finish KV 2.4
Notes: Unedited
 Feb 04
 Feb 05

L8:  ERM and uniform convergence
KV 3.1
Due:  Homework 1
Assigned:  Homework 2
 Feb 06
Feb 09
 Feb 10

L9:  VC-dimension I: Introduction and No Free Lunch
KV 3.2-3.3; start 3.6
Notes: Edited
 Feb 11
 Feb 12

L10:  VC-dimension II: Epsilon-nets and Sauer's Lemma
KV start 3.4, 3.5.1, finish 3.6
Notes: Unedited
 Feb 13
Feb 16
 Feb 17

L11:  VC-dimension III: Sample complexity bound
KV finish 3.4, start 3.5.2
Notes: Unedited
 Feb 18
 Feb 19

L12: Finish VC-dimension; Representation-independent hardness
KV finish 3.5.2; start 6.2
Notes: Unedited
Due:  Homework 2
 Feb 20
Feb 23
 Feb 24

L13: Circuits are unlearnable under cryptographic assumptions
KV 6.2-6.3		 Feb 25
 Feb 26

L14: Deductive Reasoning and Proof Systems
Notes: Unedited
Assigned:  Homework 3
 Feb 27
Mar 02
 Mar 03

L15: Resolution
Notes: Unedited
 Mar 04
 Mar 05

L16: Efficient reasoning and reasoning with examples
Notes: Unedited
 Mar 06
Mar 09
Spring Break
 Mar 10
Spring Break
 Mar 11
Spring Break
 Mar 12
Spring Break
 Mar 13
Spring Break
Mar 16
 Mar 17

L17: Common sense and nonmonotonic reasoning
 Mar 18
 Mar 19

L18: Incomplete information and implicit learning
Notes: Unedited
Assigned:  Homework 4
Due:  Homework 3
 Mar 20
Mar 23
 Mar 24

L19: Analysis of implicit learning; introduction to negation-as-failure
Notes: Unedited
 Mar 25
 Mar 26

L20: Well-Founded Semantics for negation-as-failure
Notes: Unedited
 Mar 27
Mar 30
 Mar 31

L21: Algorithm for Well-Founded Semantics
Notes: Unedited
 Apr 01
 Apr 02

L22: Reasoning about actions and change: classical planning
Notes: Unedited
Due:  Homework 4
 Apr 03
Apr 06
 Apr 07

L23: Planning under uncertainty
Notes: Unedited
 Apr 08
 Apr 09

L24: Planning with learned rules
Notes: Unedited
 Apr 10
Apr 13
 Apr 14

L25: Algorithm for planning with learned rules
Apr 15

No office hours
 Apr 16

No lecture
 Apr 17
Apr 20
 Apr 21

Final Project Presentations
 Apr 22
 Apr 23

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

Tentative list of topics

Part I: PAC learning theory (~9 lectures) Part II: PAC reasoning (~9 lectures) Part III: The boundary of tractability and other advanced topics (as time permits)