The Department of Computer Science & Engineering
cse@buffalo
CSE 676:
KNOWLEDGE REPRESENTATION
Fall 2001)

SYLLABUS

(Available on the Web at: http://www.cse.buffalo.edu/~rapaport/676/F01/syl.html )

Last Modified: 26 November 2001

NEW material is highlighted
Index: Other Relevant Links:
  • Topics
    		•
  • CSE 676 homepage
  • Prerequisites
    		•
  • Directory of Documents
  • Staff
  • Class Meetings
  • Texts
  • Important Dates & Tentative Schedule
  • Reading
  • Attendance, Homeworks, Project, Newsgroup
  • Homeworks
  • Term Project
  • How to Study
  • Grading
  • Incompletes
  • Academic Integrity
  • Classroom Disruptions
    •

    TOPICS:

    Knowledge representation (KR), more properly called "knowledge representation and reasoning" (KRR), is the part of AI that is concerned with the techniques for representing and reasoning about the information to be used by an AI program. If, as Nicklaus Wirth has said, programs = algorithms + data structures, then AI programs = AI algorithms + KR techniques. Topics will include: classical logic (propositional and predicate), SNePS, modal logics (e.g., alethic and epistemic), non-monotonic reasoning (e.g., default logic, circumscription), belief revision, the frame problem, semantic networks (including conceptual dependency), frames, description logics (e.g., KL-ONE), ontologies, and general philosophical issues (e.g., to represent or not to represent, to use logic or not to use logic).

    PREREQUISITES:
    STAFF:

    Professor:
    Dr. William J. Rapaport, 214 Bell Hall, 645-3180 x 112, rapaport@cse.buffalo.edu
    Office Hours: Mondays, 10:00 a.m. - 12:00 noon; Tuesdays, 2:00 p.m. - 3:30 p.m.; and by appointment.

    CLASS MEETINGS:

    CLASS INSTRUCTOR REGIS. NO. DAYS HOURSLOCATION
    LectureRapaport287663MWF1:00 - 1:50 p.m. Knox 109

    TEXTS:

    IMPORTANT DATES & TENTATIVE SCHEDULE:

    NEW
    Note: For the record, I have adjusted some of the dates below to reflect what we actually did in class, rather than on what I had hoped to do :-)
    NEW

    DAYS DATES TOPIC READINGS
      Aug 27-Sep 5 What is KR? Martins, Ch. 1

    Brachman & Levesque, "Introduction", in Brachman & Levesque 1985 [B&L]: xiii-xix.

    Smith, Brian Cantwell (1982), "Prologue to `Reflection and Semantics in a Procedural Language'", in B&L: 31-40.
    Fri Aug 31 2 KR projects:
    • contextual vocabulary acquisition
    • hospital discharge summaries
    		 Rapaport, William J., & Ehrlich, Karen (2000), "A Computational Theory of Vocabulary Acquisition", in Lucja M. Iwanska & Stuart C. Shapiro (eds.), Natural Language Processing and Knowledge Representation: Language for Knowledge and Knowledge for Language (Menlo Park, CA/Cambridge, MA: AAAI Press/MIT Press): 347-375.

    Rapaport, William J.; Winkelstein, Peter M.; & Shapiro, Stuart C. (2000), "Intelligent Natural-Language Understanding of Computerized Patient Medical Records".
    Mon Sep 3 no class (Labor Day)  
      Sep 5-24 Classical propositional & predicate logic Martins, Ch. 2

    Rapaport, William J. (1992), "Logic, Propositional" & "Logic, Predicate", in Stuart C. Shapiro (ed.), Encyclopedia of Artificial Intelligence, 2nd edition (New York: John Wiley): 891-897, 866-873.

    McCarthy, John (1968), "Programs with Common Sense", B&L: 299-307.

    Moore, Robert C. (1982), "The Role of Logic in Knowledge Representation and Commonsense Reasoning", B&L: 335-341.
      Sep 24-Oct 3 SNePS Martins, Sect. 6.3
    (up to, but not including, 6.3.7)

    SNePS readings

    Maida, Anthony S., & Shapiro, Stuart C. (1982), "Intensional Concepts in Propositional Semantic Networks", B&L: 169-189.

      Oct 8-Oct 15 Non-classical logics
    (modal, epistemic, relevance)    		 Martins, Ch. 3

    Rapaport, William J. (1992), "Belief Representation Systems", in Stuart C. Shapiro (ed.), Encyclopedia of Artificial Intelligence, 2nd edition (New York: John Wiley): 98-110.

    Moore, Robert C. (1977), "Reasoning about Knowledge and Action", IJCAI-77: 223-227.

    McCarthy, John (1979), "First Order Theories of Individual Concepts and Propositions", B&L: 523-533.

    Fri Oct 12 term-project progress reports due  
      Oct 15-22 Non-monotonic reasoning Ginsberg, Matthew (1987), "Introduction", in Ginsberg 1987: 1-23.

    OPTIONAL: Martins, Ch. 4

    Reiter, Raymond (1980), "A Logic for Default Reasoning", in Ginsberg 1987: 67-93
    (at least the first few pages)

    EITHER:

    McCarthy, John (1980), "Circumscription--A Form of Non-Monotonic Reasoning", in Ginsberg 1987: 145-152

    OR:

    McCarthy, John, "Epistemological Problems of AI", B&L: pp. 23ff.

    Fri Oct 19 *** Last day to withdraw with a grade of R ***  
      Oct 22-31 Truth maintenance, belief revision, & the frame problem Martins, Ch. 5

    Doyle, Jon (1979), "A Truth Maintenance System", in Ginsberg 1987: 259-279.

    de Kleer, Johan (1986), "An Assumption-Based TMS", in Ginsberg 1987: 280-297.

    Martins, João, & Shapiro, Stuart C. (1988), "A Model for Belief Revision", Artificial Intelligence 35: 25-79.

    McCarthy, John, & Hayes, Patrick J. (1969), "Some Philosophical Problems from the Standpoint of Artificial Intelligence", in Ginsberg 1987: 26-45.
      Oct 31-Nov 14 Semantic networks Martins, Sects. 6.1-6.2, 6.4-6.8

    Quillian, M. Ross (1967), "Word Concepts", B&L: 97-118.

    Schank, Roger C., & Rieger, Charles J., III (1974), "Inference and the Computer Understanding of Natural Language", B&L: 119-139.

    Woods, William A. (1975), "What's in a Link: Foundations for Semantic Networks", B&L: 217-241.

    McDermott, Drew (1976), "Artificial Intelligence Meets Natural Stupidity", in John Haugeland (ed.), Mind Design: Philosophy, Psychology, Artificial Intelligence (Cambridge, MA: MIT Press, 1981): 143-160.

      Nov 19 Frames Martins, Ch. 7

    Minsky, Marvin (1981), "A Framework for Representing Knowledge", B&L: 245-262.

    Bobrow, Daniel G., & Winograd, Terry (1977), "An Overview of KRL, a Knowledge Representation Language", B&L: 263-285.

    Hayes, Patrick J. (1979), "The Logic of Frames", B&L: 287-295.

    Wed-Fri Nov 21-23 no classes (Thanksgiving)  
      Nov 26 Description logics Martins, Ch. 8

    Brachman, Ronald J., & Schmolze, James G. (1985), "An Overview of the KL-ONE Knowledge Representation System", Cognitive Science 9: 171-216.

    Woods, William A., & Schmolze, James G. (1992), "The KL-ONE Family", Computers and Mathematics with Applications 23(2-5): 133-177; reprinted in Fritz Lehmann (ed.), Semantic Networks in Artificial Intelligence (Oxford: Pergamon Press, 1992).

      Nov 28 Ontologies & levels of representation NEW Martins, Ch. 9

    Brachman, Ronald J. (1979), "On the Epistemological Status of Semantic Networks", B&L: 191-215.

    Smith, Barry, "Ontology: Philosophical and Computational"

      Dec 3 NEW Ontology: Time NEW Allen, James F. (1983), "Maintaining Knowledge about Temporal Intervals", B&L: 509-521.
      NEW Dec 5 Philosophical issues Brooks, Rodney A. (1991), "Intelligence without Representation", Artificial Intelligence 47: 139-159.

    Kirsh, David (1991), "Today the Earwig, Tomorrow Man?", Artificial Intelligence 47: 161-184.

    Brooks, Rodney A. (1991), "Intelligence without Reason", IJCAI-91 (San Mateo, CA: Morgan Kaufmann): 569-595.

    Nilsson, Nils J. (1991), "Logic and Artificial Intelligence", Artificial Intelligence 47: 31-56.

    Birnbaum, Lawrence (1991), "Rigor Mortis: A Response to Nilsson's `Logic and Artificial Intelligence'", Artificial Intelligence 47: 57-77.

    Fri Dec 7 last class  
    Mon Dec 10 term-project reports due  

    READING:

    There are 3 levels at which you can keep up with the reading assignments:

    1. Minimal: Just read the chapters in Martins's text.

    2. Medium: Read at the minimal level, plus read the other items listed in this syllabus.

    3. Maximal: Read at the medium level, plus read some or all of the other readings that I will suggest in lecture or post to the course website, and/or that are listed in the bibliographies of any of these readings.

    See "How to Read (a Computer Science Text)".

    ATTENDANCE, HOMEWORKS, PROJECT, NEWSGROUP:

    1. You will be expected to attend all lectures, and to complete all readings and assignments on time. There may be weekly homework assignments, and there will be a term project.

    2. Any homeworks will be announced in lecture. Therefore, be sure to get a classmate's phone number (for instance, 1 or 2 people sitting next to you in class, whoever they are!) so that you will not miss assignments in the unlikely event that you miss a class.

    3. You should subscribe to, and regularly monitor, the newsgroup sunyab.cse.676. You may post questions and comments there that are of general interest to the entire class. From time to time, announcements and information about homeworks, etc., will be posted to the newsgroup. This newsgroup will be archived in the CSE 676 Newsgroup Archive.

    4. Just as you cannot expect to learn how to drive a car by reading about it or by watching other people do it, the same holds true for doing computer science. Do your work on time--this is one course you simply cannot cram for at the last minute, so don't even try! I cannot stress this strongly enough. Homeworks and--especially--the project may be fairly time-consuming, so please consider your other commitments, and plan your time accordingly.

    5. Students should notify Prof. Rapaport within the first two weeks of class if they have a disability which would make it difficult to carry out course work as outlined (requiring note-takers, readers, extended test time).

    HOMEWORKS:

    1. HW assignments will be of the "paper-and-pencil" variety, to be done at home.

    2. The purposes of homeworks are:

      • to give you practice in applying the concepts covered in the course
      • to give you a chance to assess the level of your understanding

    3. There will be approximately 1 HW each week. Due dates will be announced in lecture when the homework is assigned. HWs will be collected at the start of lecture on the due date. This is so that the homework can be discussed in the class period when it is due. Homeworks will be collected, recorded, and discussed in class, but not individually graded.

    4. Put your full name and the date at the top right-hand side of each page, and secure all pages with a staple in the top left-hand corner.

    TERM PROJECT:

    1. The term project for the course is to take a paragraph of text (in most cases, to be provided by me), to choose an appropriate knowledge-representation language, and to use that language to represent the information in the text as well as any background information (including "rules") that would be needed to understand and reason about the text.

    2. Project Policies:

        For the final project report, you will be expected to hand in a conference-style paper, typed or printed from a computer file, on 8.5 by 11 inch paper (stapled in the upper left-hand corner, without sprocket holes, and with your own title page). (Please do not use folders or covers, unless your report is too thick to be stapled.) I strongly suggest that you learn to use Latex and ispell.

        Your report should include a syntax and semantics of your knowledge representations, and, if appropriate, annotated sample runs of a working program (including documented code).

        Thus, each report must consist of the following components:

        • descriptive title (not: "Project 1")

        • your name, the course number (CSE 676), and the date.

        • abstract of project (a 1-paragraph summary)

        • description of the project (the body of the paper)

        • list of references (if appropriate)

      HOW TO STUDY:

      For general advice on how to study for any course, see my web page,       "How to Study".

      GRADING:

      Your final course grade will be a weighted average (probably 50-50) of (1) your class attendance, class participation, and homeworks, and (2) your grade on the project.

      Incompletes:

      It is University policy that a grade of Incomplete is to be given only when a small amount of work or a single exam is missed due to circumstances beyond the student's control, and that student is otherwise doing passing work. I will follow this policy strictly! Thus, you should assume that I will not give incompletes :-) Any incompletes that I might give, in a lapse of judgment :-), will have to be made up by the end of the Spring 2002 semester. Note that this supersedes the more lenient make-up date published in the university catalog! For more information on Incomplete policies, see the web page,       "Incompletes".

      ACADEMIC INTEGRITY:

      While it is acceptable to discuss general approaches with your fellow students, the work you turn in must be your own. It is the policy of this department that any violation of academic integrity will result in an F for the course, that all departmental financial support including teaching assistanceship, research assistanceship, or scholarships be terminated, that notification of this action be placed in the student's confidential departmental record, and that the student be permanently ineligible for future departmental financial support. If you have any problems doing the homeworks or projects, consult Prof. Rapaport. Please be sure to read the webpage,       "Academic Integrity: Policies and Procedures", which spells out all the details of this, and related, policies.

      CLASSROOM DISRUPTIONS:

      Students have been known to be disruptive, either to the instructor or to fellow students. The university's policies on this topic, both how the instructor should respond and how students should behave, may be found in the document       "Obstruction or Disruption in the Classroom - Policies"

      William J. Rapaport (rapaport@cse.buffalo.edu)
      file: 676/F01/syl.26nv01.html