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

Office Hours: Wednesday 3:30-5 PM, Bryan 522 (or by appointment)

Email:

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.

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

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.

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.

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.

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

- 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

- Logic and PAC-Semantics

- Reasoning with examples

- Nonmonotonic effect of conditioning

- Incomplete information

- Propositional proof systems -- Resolution and its fragments

- Algorithms for resolution

- Restrictions and implicit learning

- Learning reductions

- Boosting

- Abductive reasoning

- The proof complexity landscape and feasible interpolation

- Cryptographic hardness of reasoning

- SAT-Solvers and resolution

- Hardness of random k-SAT for resolution

- k-SAT conjectures and hardness of learning DNF