Computing and Information Technology Interactive Digital Educational Library

 

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://www-faculty.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 & Maynard-Reid '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 First-Order 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 First-Order 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.4-5, 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 Treewidth-based 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. 462-510 (ch. 13-14), 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. 462-510 (ch. 13-14), 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. 511-528, [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. 511-528, [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. 511-528, [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 First-order probabilistic models [Pfeffer '00] ch.5-6, 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 (5pm-7pm) 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 first-order 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 hyper-treewidth 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 Message-Passing as a restriction strategy for reasoning in FOL 14 Complete ``holes'' in Poole's paper on resolution in first-order probabilistic models 15 Equational reasoning in first-order probabilistic models 16 First-Order DPLL with equality 17 LSA-like robot control architecture with probabilities 18 Learning action models via filtering 19 MCMC for image segmentation 20 Robot localization for a basketball game 21 LSA-based control system for a robotic arm 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
URI: http://www.citidel.org/handle/10117/6049
Appears in Collections:Syllabus

Files in This Item:

File SizeFormat
24-syllabus.html48KbHTMLView/Open

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

 

Valid XHTML 1.0! DSpace Software Copyright © 2002-2006 MIT and Hewlett-Packard - Feedback