UIUC CS 497, Section EA
Reasoning in Artificial Intelligence
Spring 2004
Tentative Course Syllabus

Approximate Schedule

Session Date Topic Readings Sample Application
Reading
Assignment
1
Jan 20
Introduction: Knowledge Representation and Reasoning Mobile Robotics:
[Amir & Maynard-Reid '99]
Signup for paper presentations begins
2
Jan 22
Propositional logic: DPLL & Resolution Formal Verification:
[McFarland '93] [Barrett '03]
 
3
Jan 27
Resolution in First-Order Logic Temporal reasoning:
[Russell & Norvig '03], ch. 10
 
4
Jan 29
Resolution in First-Order Logic Temporal reasoning:
[Russell & Norvig '03], ch. 10
 
5
Feb 3
Restricted language: description logics Medical informatics: [OpenGalen '03] NLP/NLG and Adventure Games:
[Gadsil, Koller, & Striegnitz '01]
Semantic Web: [Horrocks '02]
 
6
Feb 5
Treewidth-based methods Spatial reasoning:
[MacCartney etal. '03]
Planning:
[Amir & Engelhardt '03]
 
7
Feb 10
Probabilistic inference Sensor Networks:
[Crick & Pfeffer '03]
 
8
Feb 12
Exact and Approximate Inference Vision:
[Tu & Zhu '02]
Medical Diagnosis:
[Wei & Altman '97] Molecular Biology:
[Segal etal. '03]
 
9
Feb 17
Monte Carlo Methods Vision:
[Tu & Zhu '02]
 
10
Feb 19
First-order probabilistic models Citation matching:
[Pasula & Russell '01], [Pasula etal. '02]
 
11
Feb 24
Dynamic Bayesian Networks
[Russell & Norvig '03], ch. 15 or [Jordan '04] ch. 20 (available next to my office door (Siebel 3314)), slides lec. 9 (based on AIMA2e slides on DBNs from Stuart Russell),
Speech recognition:
[Rabiner '89]
 
12
Feb 26
Logical filtering Adventure games:
TBA
 
13
Mar 2
Logical Filtering, and projects Adventure Games Signup for paper presentations ends
14
Mar 4
Paper presentation: logic: Resolution strategies TBA Bill Davis
15
Mar 9
Paper presentation: logic: prime implicates/implicants and consequence finding TBA Proposal 1 due
Alex Klementiev
16
Mar 11
Paper presentation: (a) logic: SAT via stochastic local search
(b) logic & probabilities: equational reasoning
Planning via SAT:
(a) [Kautz etal '96], [Kautz & Selman '96]
(b) Co-reference resolution:
TBD
(a) Geoffrey Levine and
(b) Arthur Kantor
17
Mar 16
Paper presentation: probabilities: (a) Particle Filtering Sensor Networks: [Coates '04]
Mobile Robots: [Fox etal '01]
Presentation by Hanning Zhou
18
Mar 18
Paper presentation: probabilities: (a) Loopy belief propagation [McEliece, MacKay & Cheng '98] Extended proposal due
Presentation by Jakob Metzler
19
Mar 30
Paper presentation: probabilities: (a) resolution with probabilistic relational models (b) logic & probabilities: equational reasoning TBA (a) Rodrigo Braz, (b) Arthur Kantor
20
Apr 1
Paper presentation: probabilities: (a) Survey propagation TBA Hannaneh Hajishirzi
21
Apr 6
Paper presentation: logic: (a) dynamic backtracking/ordering for SAT
(b) clause/variable ratio in SAT
TBA (a) Phil Oertel
(b) Xiaoxin Yin
22
Apr 8
Projects mid-semester review
 
  3-5 min. presentations in class
23
Apr 13
Paper presentation: dynamic systems SLAM:
[Paskin '03]
Shiau Hong Lim
(if time permits: Phil Oertel)
24
Apr 15
Paper presentation: probabilistic reasoning: (a) continuous variables, (b) Kalman filtering SLAM
(b) SLAM2.0
(a) Michael Simon and
(b) Joseph Tucek
25
Apr 20
Paper presentation: constraint satisfaction problems TBA Kenton McHenry
(if time permits: Phil Oertel)
26
Apr 22
Paper presentation: dynamic probabilistic relational models TBA Anna Yershova
27
Apr 27
Paper presentation: logic: decidable fragments of FOL
TBA
TBA Deepak Ramachandran
28
Apr 29
Paper presentation: logic: Binary Decision Diagrams TBA Afsaneh Shirazi
29
May 4
Posters session (5pm-7pm) Biology: [Xing etal '03]
information retrieval: [Blai etal '02]
Presentation by Vince Horrell
final project submission

Papers for Presentations

Number Topic Paper/s Sample Application
Reading
Presenter
1
SAT via stochastic local search Planning via SAT:
[Kautz etal '96], [Kautz & Selman '96]
Geoffrey Levine
2
Binary Decision Diagrams TBA
TBA
Afsaneh Shirazi
3
Consequence finding TBA
TBA
 
4
Prime implicates/implicants TBA
TBA
 
5
Constraint satisfaction problems TBA
TBA
Kenton McHenry
6
Equational reasoning in FOL Commonsense reasoning
TBA
 
7
DPLL in FOL TBA
TBA
 
8
FOL: decidable fragments Formal verification
TBA
Deepak Ramachandran
9
Treewidth-finding algorithms TBA
TBA
 
10
Probabilistic inference with continuous variables TBA
TBA
Michael Simon
11
Metropolis-Hastings: Theory and examples
TBA
TBA
TBA
 
11
Dynamic Probabilistic Relational Models TBA
TBA
Anna Yershova
12
Variational approximations for probabilistic inference Biology: [Xing etal '03]
information retrieval: [Blai etal '02]
Vince Horrell
13
Loopy belief propagation Turbo Coding
[McEliece, MacKay & Cheng '98]
Jakob Metzler
14
Resolution in first-order probabilistic models TBA
TBA
Rodrigo Braz
15
SAT via probabilistic reasoning TBA
TBA
Hannaneh Hajishirzi
16
Dynamic Bayes networks and particle filtering Sensor Networks: [Coates '04]
Mobile Robots: [Fox etal '01]
Hanning Zhou
17
Kalman filtering SLAM
SLAM2.0
Joseph Tucek
18
Factored inference with DBNs SLAM:
[Paskin '03]
Shiau Hong Lim
19
Resolution strategies TBD
TBD
Bill Davis
20
Probabilistic equational reasoning Co-reference resolution
TBD
Arthur Kantor
21
Dynamic backtracking for SAT TBD
TBD
Phil Oertel
22
Clauses/Variables ratio in SAT TBD
TBD
Xiaoxin Yin
23
Dynamic ordering strategies for SAT (*NOTE: SAME AS 21) TBD
TBD
(taken)  
24
Decayed MCMC Tracking
[Khan etal. '03]
 

Projects

Number Topic Presenter
1
Logical filtering with a first-order language Afsaneh Shirazi
2
Combining logical filtering and stochastic filtering Joseph Tucek
3
A system for the control of a robotic arm Anna Yershova
4
Image segmentation using MCMC: Implementation Vince Horrell
5
Factored DBN for car tracking Shiau Hong Lim
6
Comparing CSP algorithms Kenton McHenry
7
Identity Uncertainty for NL Meaning Arthur Kantor
8
Kriegspiel Jakob Metzler
9
SAT search for stochastic planning Geoffrey Levine
10
Multi-relational correlation analysis Xiaoxin Yin/td>
11
Poole's PRMs inference is correct Rodrigo de Salvo Braz
12
Interactive game observation and retention Deepak Ramachandran
13
Survey propagation for dynamic settings Hannaneh Hajishirzi
14
Commonsense knowledge retrieval Phil Oertel
15
PCFGs vs BNs Michael Simon
16
Orienting polygonal parts using filtering Alexandre Klementiev
17
Resolution on reconfigurable hardware William B. Davis
18
Inference with mixture of uniforms Hanning Zhou

Bibliography
Key Authors
Title
[McCarthy '58] John McCarthy
Programs with Common Sense
[Amir & Maynard-Reid '99] Eyal Amir and Pedrito Maynard-Reid II
Logic-Based Subsumption Architecture
[Russell & Norvig '03] Stuart Russell and Peter Norvig
Artificial Intelligence, a Modern Approach
[Genesereth & Nilsson '87] Michael R. Genesereth and Nils J. Nilsson
Logical Foundations for Artificial Intelligence
[McFarland '93] Michael C. McFarland
Formal verification of sequential hardware: a tutorial
[Biere etal. '99] A. Biere, A. Cimatti, E.M. Clarke, M. Fujita, Y. Zhu
Symbolic model checking using SAT procedures instead of BDDs
[Barrett '03] Clark Barrett
Logic in Computer Science, NYU, Fall 2003
[OpenGalen '03] OpenGALEN, by Kermanog
GALEN common reference model, version 1.02, and software
[Baader & Nutt '03] Franz Baader & Werner Nutt
Basic Description Logics, Ch.2 in the Description Logic Handbook
[Franconi '03] Enrico Franconi
Natural Language Processing, Ch.15 in the Description Logic Handbook
[Gadsil, Koller, & Striegnitz '01] M. Gabsdil, A. Koller, and K. Striegnitz
Building a Text Adventure on Description Logic
[Horrocks '02] Ian Horrocks
DAML+OIL: a Description Logic for the Semantic Web
[Amir & McIlraith '03] Eyal Amir and Sheila McIlraith
Partition-Based Reasoning for First-Order and Propositional Theories
[MacCartney etal. '03] B. MacCartney, S. McIlraith, E. Amir, & T. Uribe
Practical Partition-Based Theorem Proving for Large Knowledge Bases
[Amir & Engelhardt '03] Eyal Amir and Barbara Engelhardt
Factored Planning
[Rish & Dechter '00] Irina Rish and Rina Dechter
Resolution versus Search: Two Strategies for SAT
[Doucet etal '00] Arnaud Doucet, Nando de Freitas, Kevin Murphy, Stuart Russell
Rao-Blackwellised Particle Filtering for Dynamic Bayesian Networks, Tutorial, and slides
[Doucet etal '00b] Arnaud Doucet, Simon Godsill, and Christophe Andrieu
On sequential Monte-Carlo sampling methods for Bayesian filtering
[Coates '04] Mark Coates
Distributed particle filters for sensor networks
[Fox etal '01] Dieter Fox, Sebastian Thrun, Wolfram Burgard, Frank Dellaert
Particle Filters for Mobile Robot Localization
[Moskewicz etal '01] M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, and S. Malik
Chaff: engineering an efficient SAT solver
[Ginsberg and McAllester '94] M. Ginsberg and D. McAllester
GSAT and Dynamic Backtracking
[Selman, Mitchell, and Levesque '97] B. Selman, D. Mitchell, and H. Levesque
Generating hard satisfiability problems
[MacKay '98] David MacKay
Introduction to Monte Carlo methods
[Crick & Pfeffer '03] Christopher Crick and Avi Pfeffer
Loopy belief propagation as a basis for communication in sensor networks
[Yedidia etal. '03] J.S. Yedidia, W.T. Freeman and Y. Weiss
Bethe free energy, Kikuchi approximations and belief propagation algorithms
[McEliece, MacKay & Cheng '98] R.J. McEliece, D. J. C. MacKay, and J. F. Cheng
Turbo decoding as an instance of Pearl's `belief propagation
[Poole '03] David Poole
First-order probabilistic inference
[Braunstein etal '03] A. Braunstein, M. Mezard, R. Zecchina
Survey propagation: an algorithm for satisfiability
[Amir & Russell '03] E. Amir and S. Russell
Logical Filtering
[Jaakola '00] T. Jaakola
Tutorial on variational approximation methods (slides)
[El-Hay & Friedman '01] T. El-Hay and N. Friedman
Incorporating Expressive Graphical Models in Variational Approximations: Chain-Graphs and Hidden Variables
[Tu & Zhu '02] Zhuowen Tu and Song-Chun Zhu
Image Segmentation by Data-Driven Markov Chain Monte Carlo
[Wei & Altman '97] L. Wei and R. B. Altman
An Automated System for Generating Comparative Disease Profiles and Making Diagnoses
[Segal etal. '03] E. Segal and R. Yelensky and D. Koller
Genome-wide Discovery of Transcriptional Modules from DNA Sequence and Gene Expression
[Baumgartner '00] Peter Baumgartner
FDPLL - A First-Order Davis-Putnam-Logeman-Loveland Procedure
[Khan etal. '03] Z. Khan, T. Balch, and F. Dellaert
An MCMC-based Particle Filter for Tracking Multiple Interacting Targets
[Marthi etal. '03] B. Marthi, H. Pasula, and S. Russell
Decayed MCMC Filtering
[Pfeffer '00] A. Pfeffer
Probabilistic Reasoning for Complex Systems
[Pasula & Russell '00] H. Pasula and S. Russell
Approximate Inference For First-Order Probabilistic Languages
[Pasula etal. '02] H. Pasula, B. Marthi, B. Milch, S. Russell, I. Shpitser
Identity Uncertainty and Citation Matching
[del Val '99] A. del Val
A New Method for Consequence Finding and Compilation for Restricted Languages
[de Kleer '92] J. de Kleer
An Improved Incremental Algorithm for Generating Prime Implicates
[Slagle etal. '70] J.R. Slagle, C.-L. Chang and R. Lee
A new algorithm for generating prime implicants
[Groote & Zantema '00] J.F. Groote and H. Zantema
Resolution and binary decision diagrams cannot simulate each other polynomially
[Groote & Tveretina '03] J.F. Groote and O. Tveretina
Binary decision diagrams for first-order predicate logic
[Sanghai, Domingo, & Weld '03] S. Sanghai, P. Domingo, and D. Weld
Dynamic Probabilistic Relational Models
[Rabiner '89] L.R. Rabiner
A tutorial on hidden Markov models and selected applications in speech recognition
[Lerner & Parr '01] U. Lerner and R. Parr
Inference in Hybrid Networks: Theoretical Limits and Practical Algorithms
Key Authors
Title
Key Authors
Title
Key Authors
Title
Key Authors
Title
Key Authors
Title
Key Authors
Title

Viewing PostScript and PDF

Depending on the computer you are using, you may be able to download a PostScript viewer or PDF viewer for it if you don't already have one.


Comments to Eyal Amir