
CITIDEL >
Syllabus Collection >
Syllabus >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10117/6049

Title:  Introduction to Knowledge Representation and Reasoning 
Authors:  
Issue Date:  
Publisher:  
Citation:  http://wwwfaculty.cs.uiuc.edu/~eyal/classes/f04/cs498ea/syllabus.html 
Abstract:  UIUC CS 498, Section EA
Introduction to Knowledge Representation and Reasoning
Autumn 2004
Tentative Course Syllabus
Approximate Schedule
Session Date Topic Readings Sample Application
Reading Assignment
1
Aug 26
Knowledge Representation and Reasoning
[McCarthy '58], Slides lec.1
Mobile Robotics:
[Amir & MaynardReid '99] Homework #0 out
2
Aug 31
Propositional logic: DPLL & Resolution
[Russell & Norvig '03], ch. 7
[Rish & Dechter '00], Slides lec.2
Formal Verification:
[McFarland '93] [Barrett '03]
3
Sep 2
Prime implicates/implicants and consequence finding
[del Val '99] [Slagle etal '70], [de Kleer '92], slides lec. 15
TBA Homework #0 due
4
Sep 7
Binary Decision Diagrams
[Groote & Tveretina '03] [Groote & Zantema '00]
TBA Homework #1 out
5
Sep 9
FirstOrder Logic
[Genesereth & Nilsson '87], ch. 3 or
[Russell & Norvig '03], ch. 8, Slides lec.3
Temporal reasoning:
[Russell & Norvig '03], ch. 10
6
Sep 14
Resolution in FirstOrder Logic
[Genesereth & Nilsson '87], ch. 4 or
[Russell & Norvig '03], ch. 9, Slides lec.3
Temporal reasoning:
[Russell & Norvig '03], ch. 10 Homework #1 due
7
Sep 16
Resolution strategies
[Genesereth & Nilsson '87] ch.45, slides lec. 14, based on slides by Daniel Lehmann and Leo Joskowicz
TBA
8
Sep 21
Resolution with equality
[Chang & Lee '73] ch.??, slides lec. 14, based on slides by Daniel Lehmann and Leo Joskowicz
TBA
9
Sep 23
Partitioning and Treewidthbased methods
[AmirMcIlraith '03], Slides lec.5, and Supplementary slides
Spatial reasoning:
[MacCartney etal. '03]
Planning:
[Amir & Engelhardt '03] Homework #2 out
10
Sep 28
Probabilistic Graphical Models
[Russell & Norvig '03], pp. 462510 (ch. 1314), Slides lec. 6 (revised) (based on slides by Lise Getoor), and alternate slides (based on AIMA2e slides from Stuart Russell),
Sensor Networks:
[Crick & Pfeffer '03]
11
Sep 30
Probabilistic inference
[Russell & Norvig '03], pp. 462510 (ch. 1314), Slides lec. 6 (revised) (based on slides by Lise Getoor), and alternate slides (based on AIMA2e slides from Stuart Russell),
Sensor Networks:
[Crick & Pfeffer '03] Homework #2 due
12
Oct 5
Exact and Approximate Inference
[Russell & Norvig '03], pp. 511528,
[MacKay '98] and demo, Slides lec.6 (based on slides by Lise Getoor) Slides lec.7 (based on slides by Gal Elidan)
Vision:
[Tu & Zhu '02]
Medical Diagnosis:
[Wei & Altman '97] Molecular Biology:
[Segal etal. '03]
13
Oct 7
Sampling & Monte Carlo Methods
[Russell & Norvig '03], pp. 511528,
[MacKay '98] and demo, Slides lec.7 (based on slides by Gal Elidan)
Vision:
[Tu & Zhu '02]
14
Oct 12
BN Inference: hybrid networks, local structure
[Russell & Norvig '03], pp. 511528,
[MacKay '98] and demo, Slides lec.6 (based on slides by Lise Getoor) Slides lec.7 (based on slides by Gal Elidan)
Vision:
[Tu & Zhu '02]
Medical Diagnosis:
[Wei & Altman '97] Molecular Biology:
[Segal etal. '03] Homework #3 out
15
Oct 14
Representation of Time: Situation Calculus
[Russell & Norvig '03], ch. 10, Slides lec.3
Temporal reasoning
16
Oct 19
Representation of Time: Event Calculus and Action Languages
[Russell & Norvig '03], ch. 10, Slides lec.3
Temporal reasoning Homework #3 due
17
Oct 21
Situation Calculus: continuous time, ramifications, concurrent events, nondeterministic effects
[Russell & Norvig '03], ch. 10, Slides lec.3
Temporal reasoning
18
Oct 26
Decision making with situation calculus
SATPlan for various conditions, Golog, Slides lec.3
Temporal reasoning Homework #4 out
19
Oct 28
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]
20
Nov 2
Approximate inference in DBNs
[Boyen & Koller '98] [Doucet etal '00], [Doucet etal '00b]
Sensor Networks: [Coates '04]
Mobile Robots: [Fox etal '01]
SLAM:
[Paskin '03] Homework #4 due
21
Nov 4
Logical filtering
[Amir & Russell '03], slides lec. 10
Adventure games:
TBA Homework #5 out
22
Nov 9
Logical Representation of Space: RCC8 and others
???, Slides lec.3
Spatial reasoning
23
Nov 11
Probabilistic Representation of Shape
???, Slides lec.3
Spatial reasoning Homework #5 due
24
Nov 16
Shape and Time
???, Slides lec.3
Spatial reasoning Homework #6 out
25
Nov 18
Restricted language: frame systems
[Baader & Nutt '03], Slides lec.4
Medical informatics: [OpenGalen '03] NLP/NLG and Adventure Games:
[Gadsil, Koller, & Striegnitz '01]
Semantic Web: [Horrocks '02]
26
Nov 23
Restricted language: description logics
[Baader & Nutt '03], Slides lec.4
Medical informatics: [OpenGalen '03] NLP/NLG and Adventure Games:
[Gadsil, Koller, & Striegnitz '01]
Semantic Web: [Horrocks '02] Homework #6 due
27
Nov 25
Firstorder probabilistic models
[Pfeffer '00] ch.56, Slides lec.8 (based on slides by Lise Getoor)
Citation matching:
[Pasula & Russell '01], [Pasula etal. '02]
28
Nov 30
(a) Resolution with probabilistic relational models (b) probabilistic equational reasoning
(a) [Poole '03], (b) [Pasula etal. '02], [McCallum etal. '03]
TBA Homework #7 out
29
Dec 2
Modal Logics: Knowledge and Belief
[Amir & Russell '03], slides lec. 10
Adventure Games
30
Dec 7
Sensing and Knowledge
Posters session (5pm7pm)
Biology: [Xing etal '03]
information retrieval: [Blai etal '02] Homework #7 due
Final project submission
31
Dec 14 (tentative)
Final Exam
Possible Projects
Number Topic Presenter
1
extension of lock resolution using craig's interpolation theorem
2
hybrid reasoning of logic and probabilities via partitioning (requires knowledge of FOPL, at least Halpern's work)
3
logical filtering with a firstorder language
4
logical filtering with BDDs
5
activity detection using filtering (any method)
6
SLAM2.0 improved and applied to a mobile robot
7
Combining logical filtering and stochastic filtering
8
Survey propagation for dynamic settings (e.g., planning via SAT)
9
Approximation algorithm for hypertreewidth
10
Implementation of an algorithm for planar treewidth
11
Filtering in an adventure/strategy game
12
Labeling image segments with words (using a probabilistic graphical model)
13
Implementation of MessagePassing as a restriction strategy for reasoning in FOL
14
Complete ``holes'' in Poole's paper on resolution in firstorder probabilistic models
15
Equational reasoning in firstorder probabilistic models
16
FirstOrder DPLL with equality
17
LSAlike robot control architecture with probabilities
18
Learning action models via filtering
19
MCMC for image segmentation
20
Robot localization for a basketball game
21
LSAbased control system for a robotic arm
Bibliography
Key Authors
Title
[McCarthy '58] John McCarthy
Programs with Common Sense
[Amir & MaynardReid '99] Eyal Amir and Pedrito MaynardReid II
LogicBased 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
PartitionBased Reasoning for FirstOrder and Propositional Theories
[MacCartney etal. '03] B. MacCartney, S. McIlraith, E. Amir, & T. Uribe
Practical PartitionBased 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
RaoBlackwellised Particle Filtering for Dynamic Bayesian Networks, Tutorial, and slides
[Doucet etal '00b] Arnaud Doucet, Simon Godsill, and Christophe Andrieu
On sequential MonteCarlo 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
Firstorder 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)
[ElHay & Friedman '01] T. ElHay and N. Friedman
Incorporating Expressive Graphical Models in Variational Approximations: ChainGraphs and Hidden Variables
[Tu & Zhu '02] Zhuowen Tu and SongChun Zhu
Image Segmentation by DataDriven 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
Genomewide Discovery of Transcriptional Modules from DNA Sequence and Gene Expression
[Baumgartner '00] Peter Baumgartner
FDPLL  A FirstOrder DavisPutnamLogemanLoveland Procedure
[Khan etal. '03] Z. Khan, T. Balch, and F. Dellaert
An MCMCbased 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 FirstOrder 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 firstorder 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 
URI:  http://www.citidel.org/handle/10117/6049 
Appears in Collections:  Syllabus

Files in This Item:
File 
Size  Format 
24syllabus.html  48Kb  HTML  View/Open 

All items in DSpace are protected by copyright, with all rights reserved.
