The Department of Computer Science & Engineering
cse@buffalo
CSE 663:
ADVANCED
KNOWLEDGE
REPRESENTATION
& REASONING
Fall 2008

SYLLABUS

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

http://www.cse.buffalo.edu/~rapaport/663/F08/syl.html

Last Update: 20 November 2008

Note: NEW or UPDATED material is highlighted

Index: Other Relevant Links:
  • Course Description
    		•
  • 663 homepage
  • Prerequisites
    		•
  • Directory of Documents
  • Staff
    		•
  • Email Archive
  • Class Meetings
  • Texts
  • Important Dates & Tentative Schedule
  • Reading
  • Attendance, Assignments, Listserv
  • Term Project
  • How to Study
  • Grading
  • Incompletes
  • Academic Integrity
  • Classroom Disruptions

    • COURSE DESCRIPTION:

    Knowledge representation and reasoning (KRR) is the part of artificial intelligence (AI) that is concerned with the techniques for representing and reasoning about the information to be used by an AI program.

    Official catalog description:
    A second graduate course in knowledge representation and reasoning covering such topics as automated theorem proving, semantic network implementation, etc., and surveying knowledge representation and reasoning topics not covered in other graduate-level courses. Topics will vary according to instructor and student interests.

    Fall 2008 description:
    This course is a sequel to Prof. Shapiro's CSE 563 from the Spring 2008 semester. It will be a survey of issues in, and techniques of, representing and reasoning about and with knowledge, belief, and information in a(n artificially intelligent) computer system and of the syntax and semantics of various representational formalisms. Classic papers will be read and current research issues discussed.

    I will begin with a brief review of logic and automated theorem proving (unification and resolution) and of the SNePS knowledge-representation, reasoning, and acting system. Remaining topics will include some or all of the following, as well as others as time permits: modal and epistemic logics, ontologies, semantic networks, production systems, frames, description logics, inheritance networks, default reasoning, and the situation calculus.

    PREREQUISITES:

    Official:

    Graduate standing and either CSE 563 (Knowledge Representation) or CSE/LIN 567 (Computational Linguistics); or else permission of instructor.

    Unofficial:

    Knowledge of first-order logic, and some familiarity with resolution and unification
    (such as might have been obtained in CSE 563 or—for unification, at least—in CSE 567).

    If you did not take CSE 563 in Spring 2008 and/or have no background in first-order logic, including unification and resolution theorem proving,
    then please see Prof. Rapaport before registering.

    STAFF:

    CLASS MEETINGS:

    CLASS INSTR. REG. # DAYS HOURS LOCN
    Lecture Rapaport
    457192(3 cr.)
    		 MWF 11:00—11:50 a.m. Baldy 120

    TEXT:

    IMPORTANT DATES & TENTATIVE SCHEDULE:

    Notes:

    1. In addition to the schedule below, I plan to meet with each of you individually once or twice during the semester to discuss your projects with you.

    2. I have adjusted some of the dates and assignments below to reflect what we actually did in class, rather than on what I had planned or hoped to do :-)
    DAY MTH DT TOPICS READINGS
    M Aug 25 Intro to course;
    What is KRR?    		 This syllabus;
    BL Ch.1
    W   27 Contextual Vocabulary Acquisition CVA website
    F   29 CVA Project assigned.
    What is KRR? (cont'd)    		 CVA Programming Project
    M Sep 1 (No Class: Labor Day)  
    W   3 First-order logic (review):
  • Semiotics: Syntax, Semantics, Pragmatics
    		• Recommended:
  • Syntax vs. Semantics
    • Woods 1975
    • McDermott 1981
  • Formal Systems
    • F   5 FOL review: Syntax
    CVA word choice due    		 BL, Ch.2
    M   8 Discuss CVA words;
    FOL review: Semantics of the rep'n lang.     		 
    W   10 FOL review: Semantics (cont'd)
    and Inference     		 
    F   12 Inference: Syn and Sem;
    SNePS Tutorial report due     		 
    M   15 Modal & epistemic logics Garson 2008
    W   17 Modal & epistemic logics (cont'd);
    HW #1 Assigned     		Rapaport 1992 [PDF]
    F   19 Modal & epistemic logics (cont'd) Moore 1977
    M   22 Modal & epistemic logics (concluded);
    Ontologies    		 BL Ch.3
    W   24 HW #1 due
    Ontologies (cont'd)     		Smith 2003
    F   26 Ontologies (concluded) Noy & McGuinness 2001
    M   29 HW #2 Assigned
    Semantic networks:
    SNePS    		 Shapiro & Rapaport 1995
    W Oct 1 SNePS (cont'd) Quillian 1967
    F   3 SNePS (concluded) Lytinen 1992
    M   6 HW 2 due
    Sem. nets: Quillian     		BL Ch.7
    W   8 Sem. nets: Quillian (concluded);
    Conceptual Dependency     		 
    F   10 Please use class time to prepare your reports for 10/15 Slagle 1971
    M   13 Please use class time to prepare your reports for next class.  
    W   15 Student Project Reports  
    F   17 Student Project Reports (concluded) Lehmann et al. 2006 [PDF]
    M   20 HW 2 answers;
    Conceptual dependency (concluded)
    W   22 Production systems BL Ch.8
    F   24 Production systems (concluded);
    Frames     		Minsky 1974
    M   27 Frames (continued) Fikes & Kehler 1985
    W   29 Frames (concluded);
    Description logics     		BL Ch.9
    F   31 Description logics (cont'd) Woods 1975
    M Nov 3 Description logics (concluded) Woods & Schmolze 1992
    W   5 Inheritance networks BL Ch.10
    F   7 Inheritance networks (cont'd);
    (Last R day)    		 Etherington & Reiter 1983
    M   10 Inheritance (cont'd) Thomason 1992 [PDF]
    W   12 Inheritance networks (concluded);
    Default reasoning     		BL Ch.11
    F   14 Defaults (cont'd) Selections from Ginsberg 1987
    M   17 Defaults (cont'd) Selections from Ginsberg 1987
    W   19 Defaults (cont'd) BL Ch.14
    F   21 Defaults (concluded);
    Situation calculus     		McCarthy 1959
    M   24 Situation calculus (cont'd) McCarthy & Hayes 1969
    W   26 (No Class: Thanksgiving)  
    F   28 (No Class: Thanksgiving)  
    M Dec 1 Situation calculus (concluded)  
    W   3 AI w/o KRR?! Brooks 1991a [PDF]
    Brooks 1991b [PDF]
    F   5 Summary & review Davis et al. 1993
    Shapiro 2003
    M   8 Term Projects Due  

    READING:

    "Teachers open the door, but you must enter by yourself." — Chinese Proverb

    "You can lead a horse to water, but you can't make him drink." — American Proverb

    "You can lead a horse to water, but you must convince him it is water before there is any chance he will drink." — Albert Goldfain

    "Education is not filling a bucket, but lighting a fire." — William Butler Yeats

    1. Since this is a second-year graduate course, I see its purpose to be to introduce you to some of the major topics in KRR and some of its history. I will expect you to do a great deal of reading, not all of which will be explicitly covered in class. As a graduate student, you should be able (or willing to learn how) to read—and to learn from—research papers on your own and to suggest readings that might be of interest. I see my purpose in class to be to help you to understand the material that you are studying on your own.

    2. Not all assigned readings will be covered in lecture (in lecture, we will only cover interesting or hard material, plus some material that is not in the assigned reading), but you are responsible for all assigned material in the assigned reading and lectures.

    3. Readings will not necessarily match the corresponding lecture topics, and will usually be several days in advance. However, no matter how far we stray from the tentative schedule, if you do the readings at the assigned times, you will be able to finish everything by the end of the semester.

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

      1. Minimal: Just read the chapters in the B&L text and the other required papers that I assign.

      2. Medium: Read at the minimal level, plus read the recommended-reading items that I will announce from time to time; these will typically be classic papers in KRR.

      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 or listserv, and/or that are (recursively:-) listed in the bibliographies of any of these readings.

    5. How much do you really have to read?

      "The more you read, the more intelligent you are. It's really that simple." — Ethan Hawke

      But...

      "To read critically is to read skeptically. The reader asks...not only, 'Do I understand what this means?' but 'Do I buy it?' " — Kenneth S. Goodman

    HOW TO READ and HOW TO STUDY:

    ATTENDANCE, ASSIGNMENTS, LISTSERV:

    1. You will be expected to:

      1. attend all lectures (attendance will be taken),
      2. participate in class discussions,
      3. complete all readings on time,
      4. complete any HW assignments on time, and
      5. do a term project.

    2. Any assignments and important announcements will be made in lecture.

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

      Announcements may also be posted to the course website or the email Listserv.

    3. Email Listserv:

      You will automatically be placed on an email list (a "Listserv") for the course.
      If you do not normally read email at the email address that UB has as your official address, please either do so for this course, or else have your mail forwarded.
      I will use this list as my main means of communicating with you out of class.
      And you can use it to communicate with the rest of us.

      You may send questions and comments that are of general interest to the entire class using the Listserv:
      Just send them to:

      You can also send email just to me, at:

      In any case, be sure to fill in the subject line, beginning with "CSE 663" and please use your @cse.buffalo.edu or @buffalo.edu address so that my mailer doesn't think it's spam.

      If you send email just to me that I deem to be of general interest, I will feel free to remail it to the email list along with my reply unless you explicitly tell me that you want to remain anonymous, in which case I may choose to remail it to the email list preserving your anonymity.

      The emails will be archived at the listserv website, and I will also archive them at http://www.cse.buffalo.edu/~rapaport/663/F08/EMAIL/.

      For more information, read the Listserv Information webpage.

    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.
      The project, especially, 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 that would make it difficult to carry out course work as outlined
      (requiring note-takers, readers, extended project time, etc.).

    PROJECT:

    1. The default term project for the course is to:

      1. take a paragraph of text (in most cases, to be provided by me) containing an "unfamiliar" word,
      2. represent that passage in the SNePS knowledge-representation & reasoning system, together with any background information (including "rules") that would be needed to figure out ("compute") a meaning for that word, and
      3. use our CVA software to see if its contextual meaning can be figured out.

      This is part of our Contextual Vocabulary Acquisition project. Further details will be announced in lecture and on the course website.

      This course project may be used as your master's project for the M.S. in CSE. There is additional departmental paperwork that has to be filled out if you intend to use the project for this purpose.

    2. Programming language.

      For information on Lisp, see my webpage about information on Lisp for CSE 663.

    3. SNePS.

      We will discuss the SNePS knowledge representation and re asoning system in class, but those of you who do not already know it should work through the SNePSUL Tutorial and/or the SNePSLOG Introduction at

      as soon as possible.

    4. You should have an account 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: CIT Help Desk
      Services for Students

    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.

    For information on my philosophy of grading, see my web document on "How I Grade"

    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 2009
    semester.

    For more information on Incomplete policies, see the Graduate School web page, "Incomplete Grades".

    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 assistantships, research assistantships, 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 assignments, consult Prof. Rapaport. Please be sure to read the webpage, "Probation, Academic Integrity and Discontinuance of Study", which spells out all the details of this, and related, policies.

    For some hints on how to avoid plagiarism when writing essays for courses, see my website "Plagiarism".

    CLASSROOM DISRUPTIONS:

    In large classes (but surely not ours :-), 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 PDF document "Obstruction or Disruption in the Classroom".

    Copyright © 2008 by William J. Rapaport (rapaport@cse.buffalo.edu)
    http://www.cse.buffalo.edu/~rapaport/663/F08/syl.html-20081120