** CIS 620: ADVANCED TOPICS IN
ARTIFICIAL INTELLIGENCE
SPRING 2002**

URL for this page:
**http://www.cis.upenn.edu/~mkearns/teaching/cis620/cis620.html**

** INSTRUCTORS **

**Prof. Michael Kearns **

mkearns@cis.upenn.edu

Office hours: Wednesday 2-4 PM in 555 Moore/GRW

**Prof. Lawrence Saul **

lsaul@cis.upenn.edu

Office hours: Wednesday 2-4 PM in 557 Moore/GRW

** COURSE DESCRIPTION **

Over the last decade, significant advances have been made in a number
of core problems of artificial intelligence (AI). These advances
share an emphasis on probabilistic models of uncertainty, compact
representations of complex environments, and efficient algorithms for
reasoning, acting, and learning from experience. We will survey the
main problems of probabilistic AI, including planning and learning in
Markovian environments, reasoning under uncertainty via probabilistic
graphical models, and interaction between rational agents in
game-theoretic settings. We will emphasize the significant
connections between these problems and the solutions proposed for
them. The course will feature a mix of theory and application, with
formal mathematical analyses of algorithms as well as frequent
in-class computer demonstrations.

** COURSE LOCATION AND TIME **

Monday and Wednesday 10:30 - 12 in Towne 321.

** PREREQUISITES **

Introduction to AI at the level of CIS 520. Some multivariable
calculus, linear algebra, and elementary probability theory would be
helpful, but not essential. This course is aimed at graduate students
and advanced undergraduates.

** COURSE REQUIREMENTS **

Problem sets and a course project; maybe occasional scribe notes
and presentations of readings.

** RECOMMENDED BOOKS **

There will also be frequent supplementary research readings made available on this page.

** COURSE NEWSGROUP **

There is a newsgroup for the course, which is upenn.cis.cis620.
Students are free to communicate with each other there, and we
will occasionally post news and information about the course and
problem sets there.

** INFORMATION ON
COURSE PROJECTS **

** PROBLEM SETS, LECTURE
NOTES, HANDOUTS **

** Note on MATLAB access:
**
The PC labs are in the Towne building. You can get full details to the
labs at
http://www.seas.upenn.edu/cets/labs.html.
The PC labs require an Eniac account for access. Anyone with a gradient
account is also entitled to an Eniac account if she or he doesn't
already have one.

** Problem Set #1 (due
Weds Jan 23, start of class) **
[Postscript]
[PDF]

** A clarifying note on definitions **
[Postscript]
[PDF]

** Solutions to Problem Set #1
**
[Postscript]
[PDF]

**
Paper: "An Upper Bound on the Loss from
Approximate Optimal-Value Functions", by Singh and Yee
**
[Postscript]
[PDF]

** Problem Set #2 (due
Weds Feb 6, start of class)
**
[Postscript]
[PDF]

**
Related paper: "A Sparse Sampling Algorithm for Near-Optimal
Planning in Large Markov Decision Processes", by MK, Mansour, Ng
**
[Postscript]
[PDF]

**
Link to Prof. Saul's lecture note directory
**
here

**
Lecture Notes on Probability
**
[Gzipped Postscript]
[PDF]

**
Lecture Notes on Regression
**
[Gzipped Postscript]
[PDF]

**
Problem Set #3 (Due Wed Feb 21, start of class)
**
[Gzipped Postscript]
[PDF]

**
Related MATLAB binary data files:
**
nasdaq_lag5.mat
digits2vs3.mat

**
Lecture Notes on Convexity
**
[Gzipped Postscript]
[PDF]

**
Lecture Notes on Iterative Scaling **
[Gzipped Postscript]
[PDF]

**
Problem Set #4 (Due Wed Feb 27, start of class) **
[Gzipped Postscript]
[PDF]

**
Lecture Notes on State Aggregation **
[Gzipped Postscript]
[PDF]

**
Lecture Notes on Sensor Fusion **
[Gzipped Postscript]
[PDF]

**
Lecture Notes on HMMs **
[Gzipped Postscript]
[PDF]
**
Problem Set #6 (Due Monday Mar 25) **
[Gzipped Postscript]
[PDF]

** Problem Set #7 (due
Mon Apr 1) **
[Postscript]
[PDF]

** MK tutorial including inference in Bayes nets,
reinforcement learning **
[Postscript]
[PDF]

** DETAILED COURSE OUTLINE **

The outline below is subject to ongoing revision. In general, we'll try
to modify the outline both in advance (to reflect anticipated changes
in material and scheduling of topics) and in retrospect (to
reflect what was actually covered in each past week). Just to
be fancy, we'll change the color of subjects we've already covered
to blue.

** WEEK 1 (Jan 7):
INTRODUCTION; PLANNING
IN MDPs **

Related Readings

** Problem Set #1 (due
Weds Jan 23, start of class) **
[Postscript]
[PDF]

** A clarifying note on definitions **
[Postscript]
[PDF]

** WEEK 2 (Jan 14):
FOUNDATIONS OF PROBABILITY; LARGE DEVIATION
THEORY; LEARNING IN MDPs **

Related Readings

** Lecture Notes for Jan 14 (Foundations of
Probability) **
[Gzipped Postscript]
[PDF]

**
Paper: "On the Complexity of Solving
Markov Decision Processes",
by Littman, Dean, and Kaelbling
**
[Postscript]
[PDF]

** WEEK 3 (Jan 21; Short week, MLK day):
LEARNING IN MDPs: TD(k) ANALYSIS **

**
Paper: " 'Bias-Variance' Error Bounds for
Temporal Difference Updates", by MK and Singh,
gives a fairly brief treatment of the TD(k) material
we covered (lots of details missing, though)
**
[Postscript]
[PDF]

** WEEK 4 (Jan 28):
Q-LEARNING;
EXPLORATION VS. EXPLOITATION;
LARGE STATE SPACES **

** Problem Set #2 (due
Weds Feb 6, start of class) **
[Postscript]
[PDF]

**
Paper: "A Sparse Sampling Algorithm for Near-Optimal
Planning in Large Markov Decision Processes", by MK, Mansour, Ng
**
[Postscript]
[PDF]

** WEEK 5 (Feb 4):
LINEAR AND LOGISTIC REGRESSION;
GRADIENT AND NEWTON METHODS **

**
Lecture Notes on Regression
**
[Gzipped Postscript]
[PDF]

**
Problem Set #3 (Due Wed Feb 21, start of class) **
[Gzipped Postscript]
[PDF]

**
Data sets in MATLAB (binary) format:
**
nasdaq_lag5.mat
digits2vs3.mat

** WEEK 6 (Feb 11):
PREDICTION AND ITERATIVE SCALING **

** WEEK 7 (Feb 18):
STATE AGGREGATION AND CLUSTERING **

**
Lecture Notes on Iterative Scaling **
[Gzipped Postscript]
[PDF]

**
Problem Set #4 (Due Wed Feb 27, start of class) **
[Gzipped Postscript]
[PDF]

**
Lecture Notes on State Aggregation **
[Gzipped Postscript]
[PDF]

** WEEK 8 (Feb 25):
DIMENSIONALITY REDUCTION AND FUSION **

**
Lecture Notes on Sensor Fusion **
[Gzipped Postscript]
[PDF]

** WEEK 9 (Mar 4):
HIERARCHY AND DYNAMICS **

**
Lecture Notes on HMMs **
[Gzipped Postscript]
[PDF]

** WEEK 10 (Mar 11):
SPRING BREAK **

** WEEK 11 (Mar 18):
GRAPHICAL MODELS FOR PROBABILISTIC INFERENCE **

** WEEK 12 (Mar 25):
INFERENCE IN BAYES NETS **

** Problem Set #7 (due
Mon Apr 1) **
[Postscript]
[PDF]

** MK tutorial including inference in Bayes nets,
reinforcement learning
**
[Postscript]
[PDF]

** WEEK 13 (Apr 1):
BAYES NETS AND MDPs **

**
Paper: An Introduction to Variational Methods for
Graphical Models. M. Jordan, Z. Ghahramani, T. Jaakkola, L. Saul.
**
[Postscript]
[PDF]

**
Paper: Variational Methods and the QMR-DT Database. T. Jaakkola and M. Jordan.
**
[Postscript]
[PDF]

**
Paper: Large Deviation
Methods for Approximate Probabilistic Inference,
with Rates
of Convergence, MK and LS.
**
[Postscript]
[PDF]

** WEEK 14 (Apr 8):
INTRODUCTION TO GAME THEORY **

** WEEK 15 (Apr 15):
STOCHASTIC AND GRAPHICAL GAMES **

www.digits.com