The Department of Computer Science & Engineering
cse@buffalo
CSE 463/563:
INTRODUCTION TO
KNOWLEDGE REPRESENTATION
AND REASONING
Spring 2003

SYLLABUS

(This is a living document; the latest version will always be available on the Web at:

http://www.cse.buffalo.edu/~rapaport/563/syl.html )

Last Update: 25 April 2003

Note: NEW or UPDATED material is highlighted


Index: Other Relevant Links:
  • Topics
  • CSE 463/563 homepage
  • Prerequisites
  • Directory of Documents
  • Staff
  • Class Meetings
  • Texts
  • Important Dates & Tentative Schedule
  • Reading
  • Attendance, Homeworks, Projects, Exams, Newsgroup
  • Homeworks
  • Projects
  • How to Study
  • Grading
  • Incompletes
  • Academic Integrity
  • Classroom Disruptions

  • COURSE DESCRIPTION:

    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.

    This course will be an introduction to the issues and techniques of representing knowledge and belief in a computer system and to the syntax and semantics of various representational formalisms including predicate logic, semantic networks, and frames. Classic papers will be read and current research issues discussed.

    Topics will include some or all of the following, as well as others as time permits: the knowledge representation hypothesis; classical propositional and predicate logic; non-classical logics (e.g., modal logics); non-monotonic, defeasible, and default logics; logics of knowledge and belief; truth maintenance and belief revision; semantic networks; frames; description logics (e.g., the KL-ONE family); commonsense reasoning; knowledge sharing; ontologies.

    PREREQUISITES:

    STAFF:

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

    Teaching Assistant:
    Mr. Paul V. Gestwicki; Trailer B-11, 645-3772 pvg@cse.buffalo.edu
    Office Hours: Wednesdays, 9:00-10:00 a.m.; Fridays, 12:00 noon -1:00 p.m.; and by appointment.

    CLASS MEETINGS:

    CLASS INSTRUCTOR REGIS. NO. DAYS HOURSLOCATION
    LectureRapaport463: 074848
    563: 193524
    MWF10:00 - 10:50 a.m. Norton 209
    Recitation 1 Gestwicki   W 11:00 - 11:50 a.m. Bell 242
    Recitation 2 Gestwicki   W 1:00 - 1:50 p.m. Baldy 127

    NOTE: Recitations begin Wed., January 29

    TEXTS:

    IMPORTANT DATES & TENTATIVE SCHEDULE:

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

    DAY MONTH DATE TOPICS READINGS
    M Jan 13 1. Intro; review syllabus B&L, Ch. 1
    W   15 2. What is KR?  
    F   17    
    M   20 Martin Luther King, Jr., Birthday; no class  
    W   22 3. Semantic networks and
    the SNePS Knowledge Representation
    & Reasoning System
    Shapiro & Rapaport 1987
    Shapiro & Rapaport 1995
    Martins 2002
    F   24    
    M   27    
    T   28 Prof. Randall Dipert, PHI
    informal presentation of Peirce's logic
    11:00 a.m. - 12:50 p.m., Park 280
     
    W   29   B&L, Ch. 2
    F   31 HW #1 assigned  
    M Feb   3 CSE Grad Conference
    Student Union 145 A,B,E;
    NO CLASS TODAY
    HW #1 due; HW #2 assigned
     
    W     5 SNePS ontology B&L, Ch. 3
    F     7    
    Sat     8 Workshop on Applied Ontology
    Park 280
    9:00 a.m. - 5:00 p.m.
     
    M   10 4. Syntax vs. semantics
    PROJECT 1 DUE
     
    W   12 HW #2 due B&L, Ch. 4
    F   14 6. Propositional logic: representation
    HW #3 assigned
    B&L, Ch. 5
    M   17 Propositional logic: reasoning B&L, Ch. 6
    W   19 HW #3 due  
    F   21   B&L, Ch. 7
    M   24 5. First-order logic: representation  
    W   26    
    F   28 Review for Midterm  
    M Mar   3 MIDTERM EXAM  
    W     5 Review of Midterm  
    F     7 Last Day to Resign
    Project 2 assigned
    Relation of SNePS to FOL
     
    Sat-Sun   8-16 Spring Break  
    M   17 FOL: semantics B&L, Ch. 2
    W   19    
    F   21 FOL:
    rules of inference,
    clause form
    B&L, Ch. 4
    M   24 FOL:
    clause form
    HW 5 due; HW 6 assigned
     
    W   26 FOL:
    clause form, resolution
     
    F   28 FOL:
    resolution, refutation
     
    M   31 FOL: unification
    HW 6 due
     
    W Apr   2    
    F     4    
    M     7 6. Ontology
    PROJECT 2 DUE
    OPTIONAL PROJECT 3 ASSIGNED
    HW 7 assigned
    B&L, Ch. 3
    W     9 7. Ontology: Time  
    F   11 8. CYC

    also:
    Doug Lenat,
    "Computers & Common Sense",
    CSE Distinguished Speaker Lecture Series,
    3:30 p.m.,
    330 Student Union

    Lenat, Douglas B. (1995)
    CYC: A Large-Scale
    Investment in Knowledge
    Infrastructure"
    ,
    CACM
    38 (11): 33-38.
    M   14 9. Mental Models

    HW 7 due; HW 8 assigned

    Johnson-Laird et al. 1998
    T   15 Philip N. Johnson-Laird,
    "How We Reason",
    UB Center for Cognitive Science Distinguished Speaker,
    2:30-3:45 p.m., Slee Concert Hall
     
    W   16 Discussion of CYC, SNePS-3
    9. Frames

    also:
    P.N. Johnson-Laird,
    "Naive Causality:
    A Theory of Causal Meaning & Reasoning"

    2:00-4:00 p.m.,
    Park 280

    B&L, Ch. 8
    F   18 Frames (concluded) B&L, Ch. 9
    M   21 10. Description logics;
    HW 8 due; HW 9 assigned
    B&L, Ch. 11
    W   23 11. Default reasoning & belief revision B&L, Ch. 14
    F   25 UPDATED Belief revision in SNeBR;
    course evaluation
    TBA
    M   28 Last Class:
    What is KR? Is it needed?
    Course summary;
    HW 9 due;
    PROJECT 3 DUE
    Davis et al. 1993
    Brooks 1991
    F May 2 FINAL EXAM
    3:30-6:30 p.m.
    NSC 222
     

    READING:

    ATTENDANCE, HOMEWORKS, PROJECTS, EXAMS, NEWSGROUP:

    1. You will be expected to attend all lectures and recitations, and to complete all readings and assignments on time. There will be weekly homework assignments, 3 programming projects, a mid-term exam, and a final exam (during exam week). Taking both the exams is a necessary condition for passing the course.

    2. All 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. There may be occasional extra assignments and quizzes in recitations.

    3. You should subscribe to, and regularly monitor, the newsgroup sunyab.cse.563. You may post questions and comments there that are of general interest to the entire class. From time to time, information about homeworks, etc., will be posted to the newsgroup. The newsgroup will be archived in the CSE 463/563 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--projects 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.

    4. 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.

      If they are turned in after the start of lecture, your grade will be discounted by one full letter grade (e.g., A becomes B, A- becomes B-, etc.).

      If they are turned in after the start of the next lecture, your grade will be discounted by two full letter grades (e.g., A becomes C, A- becomes C-, etc.).

      If you turn in a HW after the start of the class after that, your grade will be discounted by three full letter grades (e.g., A becomes D, etc.).

      No HWs will be accepted after that.

    5. Put your full name, date, and your recitation number (R1 or R2) at the top right-hand side of each page, and secure all pages with a staple in the top left-hand corner.

    6. Note: The lowest homework grade will be dropped. You should assume that you will fail to turn in one homework (oversleep, get stuck in traffic, etc.)--that's the one that will be dropped. If you know now that you will regularly be late, see me to make alternative arrangements for turning in your work. Your graded HW will be returned in recitation. Occasional extra assignments or quizzes from lab can be used to replace low HW grades, at your TA's discretion.

    PROJECTS:

    1. Programming Languages, Lisp, and Unix: The prerequisite for this course is knowledge of any high-level programming language.

      But you are strongly advised to (learn and) use Lisp if you intend to do any research in AI. Moreover, there are good reasons to learn Lisp even if you want to make it in the real world of e-commerce; see:

      1. Paul Graham's Lisp Resources

      2. St. Amant, Robert, & Young, R. Michael (2001), "Common Lisp Resources on the Web" (PDF), intelligence 12(3): 21-23.

      3. ... and, especially,
        Graham, Paul (2001), "Beating the Averages".

      If you decide to use Lisp: The implementation of Lisp for this course is Allegro Common Lisp (acl), which runs under the Unix operating system. You will be expected to learn the idiosyncrasies of Allegro Common Lisp on your own (the Shapiro text should be of help). For more information on Lisp, see Marty Hall's "An Introduction and Tutorial for Common Lisp" website.

      CSE 463 students will have accounts on the CSE undergraduate machines; CSE 563 students will have accounts on the Grad Lab machines. If you do not have access to these machines, please let me know as soon as possible! You will be expected to learn how to use Unix, emacs, etc., on your own. CIT offers short courses on Unix, etc. To contact CIT:

      in person:216 Computing Center
      by phone:645-3542
      by fax:645-3617
      by email:cit-helpdesk@buffalo.edu
      on the Web:http://wings.buffalo.edu/computing/Help-Desk/
      http://www.cit.buffalo.edu/students/

    2. Project Policies:

      HOW TO STUDY:

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

      GRADING:

      Undergrads (in 463) and grads (in 563) will be graded on different bases. All graded work will receive a letter grade: 'A', 'A-', 'B+', 'B', 'B-', 'C+', 'C', 'C-' (463 only), 'D+' (463 only), 'D', or 'F'. Your course grade will be calculated as a weighted average of all letter grades according to the following weights:

      Recitation grade
      (including attendance, homeworks, quizzes, etc.)
      25%
      Projects25%
      Midterm Exam25%
      Final Exam25%
      Total100%

      For further information, see my web document on "Grading Principles"

      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 Fall 2003 semester. 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 the TA or 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:

      In large classes (such as this), 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" (PDF).


      Copyright © 2003 by William J. Rapaport (rapaport@cse.buffalo.edu)
      file: 563/syl.2003.04.25.html