UMBC CMSC771, Spring 2000

UMBC CMSC771 Spring'00

Syllabus

Warning: There is way too much to read in this syllabus. We'll identify some as required and the others will be recommended. This syllabus is subject to change before the class begins. After it begins, too. The general plan is to have each week be devoted to a seperas

Week one, 2/3 Overview, introduction, what is KR

We will discuss the structure and content of the course.

To be discussed:
- Knowledge representation, Pat Hayes, MIT Encyclopedia of Cognitive Science (MITECS), 1999.
Presentations:
- Introduction to knowledge representation
Additional optional readings:
- R.Brachman, "The future of knowledge representation", in Proceedings of the Eighth National Conference on Artificial Intelligence, 1990.

Week two, 2/8 Logic as a representation language

To be discussed:
- What is a Knowledge Representation?, Randall Davis, Howard Shrobe, and Peter Szolovits. AI Magazine, 14(1):17-33, 1993.
  - lead: Finin
- Some Philosophical Problems from the Standpoint of Artificial Intelligence, John McCarthy and Patrick C. Hayes, Machine Intelligence 4., 1969. Seminal paper on knowledge representation, the use of logic in AI, the situation calculus, and the connection between many areas of philosophy and AI.
  - lead: Chen, Sachs
- Guide to Axiomatizing Domains in First-Order Logic , Ernie Davis. A short guide, useful for novices and experienced axiomatizers alike.
  - lead: Rong
Additional optional readings:
- Logic review
  - Sowa,chapter 1
  - Logical reasoning systems, David McAlister, MIT Encyclopedia of Cognitive Science (MITECS), 1999.
  - Modal logic, Max Cresswell, MIT Encyclopedia of Cognitive Science (MITECS), 1999.
  - Sowa's notes on mathematical background -- a revised and extended version of Appendix A from the book Sowa's Conceptual Structures book
  - Crash course in the theory of logic, Richard Thomason, University of Michigan.
- Representing common sense knowledge in logic
  - Ernest Davis: The Naive Physics Perplex, AI Magazine, Winter, 1999. A discussion of various approaches toward representing commonsense knowledge.
  - Patrick Hayes: "The Second Naive Physics Manifesto," in Jerry Hobbs and Robert Moore (Eds): Formal Theories of the Commonsense World, Ablex, pp 1-36. 1985. This is the classic work on knowledge representation, and I highly recommend reading it.
  - Hayes, P. J. (1985). Naive Physics I: Ontology for liquids. In Formal theories of the common sense world, ed. J. Hobbs and R. C. Moore, pp. 71-107. Norwood, NJ: Ablex. This classic paper gives a detailed discussion of the representation of some common sense knowledge.

Week three, 2/15 From semantic networks to frames

We will introduce the notion of a semantic network and the closely related concept of a frame based representation systems.

To be discussed
- Frame based systems, MIT Encyclopedia of Cognitive Science (MITECS), 1999.
- R. Fikes and T. Kehler, The Role of Frame-Based Representation in Reasoning., CACM Volume 28, Number 9, September 1985,904-920. Abstract: A frame-based representation facility contributes to a knowledge system's ability to reason and can assist the system designer in determining strategies for controlling the system's reasoning.
- Minsky M, A framework for representing knowledge, Memo 306, MIT AI Lab, June 1974. (A revised version appeared as: Minsky, M., A framework for representing knowledge, Chapter 6 in The Psychology of Computer Vision, Winston, P. H. (ed.), McGraw-Hill, 1975.)
Background
- Semantic Networks: Their Computation and Use for Understanding English Sentences. R. F. Simmons. In R. C. Schank and K. M. Colby (eds.), Computer Models of Thought and Language. W. H. Freeman and Co. 1973.
- On the Epistemological Status of Semantic Networks. Ronald J. Brachman. In Associative Networks: Representation and Use of Knowledge by Computers, N. V. Findler (ed.), pp. 3-50. New York, Academic Press, 1979.
- Fritz Lehmann, Editor, "Semantic Networks in Artificial Intelligence", Pergamon Press, Oxford, 1992. (Appeared as a double special issue of Computers and Mathematics with Applications 23(2-9), 1992.
- W.A. Woods, "What's in a link: Foundations for semantic networks", In D.G. Bobrow and A. Collins (Eds.), "Representation and Understanding", Academic Press, New York, 1975. Reprinted in "Readings in Cognitive Science", Collins ? Smith (eds.), section 2.2.

Week four, 2/22 ...to description logic

to discuss

to be discussed
- Sowa, sections 3.1, 3.2
- NeoClassic User's Guide, Version 0.7, Lori Alperin Resnick, Peter F. Patel-Schneider, Deborah L. McGuinness, Elia Weixelbaum, Merryll Herman, Alex Borgida, Ronald J. Brachman, Charles L. Isbell, Kevin C. Zalondek.
- Alex Borgida, Ronald J. Brachman, Deborah L. McGuinness, and Lori Alperin Resnick, ``CLASSIC: A Structural Data Model for Objects,'' in Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data , pages 59--67, June 1989.
Background
- Ronald J. Brachman and James G. Schmolze, "An overview of the KL-ONE knowledge representation system", Cognitive Science, 9:171-216, 1985.
- James G. Schmolze and William A. Woods, "The KL-ONE Family", in F. Lehmann, editor, Semantic Networks in Artificial Intelligence, Pergamon Press, 1992. Gives a history of description logics (KL-ONE style systems).
- Ronald J. Brachman, Deborah L. McGuinness, Peter F. Patel-Schneider, Lori Alperin Resnick, and Alex Borgida, ``Living with CLASSIC: When and How to Use a KL-ONE-Like Language,'' in John Sowa, ed., Principles of Semantic Networks: Explorations in the representation of knowledge , Morgan-Kaufmann: San Mateo, California, 1991, pages 401--456.
- R. Brachman and H. Levesque, "A fundamental tradeoff in knowledge representation and reasoning.", reprinted in Readings in Knowledge Representation, pp. 42-70.

Week five, 2/29 no class

Week six, Ontologies 3/7

to discuss
- Guarino N.,Understanding, Building and Using Ontologies. A Commentary to "Using Explicit Ontologies in KBS Development", by van Heijst, Schreiber, and Wielinga. International Journal of Human and Computer Studies vol. 46 n. 2/3, 1997, pp. 293-310
- Guarino N., Formal Ontology, Conceptual Analysis and Knowledge Representation. International Journal of Human and Computer Studies, special issue on The Role of Formal Ontology in the Information Technology edited by N. Guarino and R. Poli, vol 43 no. 5/6, 1995
- Guarino N., Giaretta P., Ontologies and Knowledge Bases: Towards a Terminological Clarification. In N. J. I. Mars (ed.), Towards Very Large Knowledge Bases, IOS Press 1995.
- Lenat and R. Guha, Building Large Knowledge-Based Systems: Representation and Inference in CYC, pp.82-126, 149-240.
Background
- Sowa, chapter two
- Sowa's ontology notes
- Ontology and Information Systems. In N. Guarino (ed.), Formal Ontology in Information Systems. Proc. of the 1st International Conference, Trento, Italy, 6-8 June 1998. IOS Press (amended version)

Week seven, 3/14, Knowledge sharing

To be discussed:
- R. Fikes, A. Farquhar; Large-Scale Repositories of Highly Expressive Reusable Knowledge; IEEE Intelligent Systems, Vol. 14, No. 2, March/April 1999. Also, KSL Technical Report KSL-97-02
- V. K. Chaudhri, A. Farquhar, R. Fikes, P. D. Karp, and J. P. Rice, "OKBC: A Programmatic Foundation for Knowledge Base Interoperability," in Proceedings of the AAAI-98, (Madison, WI), 1998. The technology for building large knowledge bases (KBs) is yet to witness a breakthrough so that a KB can be constructed by the assembly of prefabricated knowledge components. Most of the current KB development tools can only manipulate knowledge residing in the knowledge representation system (KRS) for which the tools were originally developed. Open Knowledge Base Connectivity (OKBC) is an application programming interface for accessing KRSs, and was developed to enable the construction of reusable KB tools. OKBC improves upon its predecessor, the Generic Frame Protocol (GFP), in several significant ways. In this paper, we discuss technical design issues faced in the development of OKBC, highlight how OKBC improves upon GFP, and report on practical experiences in using it.
- OKBC spec -- sections 1 and 2.
Read
- Sowa chapter seven
- R. Patil, R. Fikes, P. Patel-Schneider, D. Mckay, T. Finin, T. Gruber, R. Neches; The DARPA Knowledge Sharing Effort: a Progress Report; in Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning; Cambridge, Massachusetts; October 25-29, 1992. Also KSL Technical Report KSL 93-23.
- The Ontolingua server: a tool for collaborative ontology construction

Week eight 3/21 Spring break

Sowa: chapter two. This is fun reading.

Week nine, 3/38 Non-monotonic reasoning, time and processes

M. Ginsberg, "Introduction" (To Nonmonotonic Reasoning, Morgan Kaufmann, 1988.)
Ronald J. Brachman, " ``I lied about the trees'', or, defaults and definitions in knowledge representation", AI Magazine 6(3):80-93, 1985.
E. Davis, Representations of commonsense knowledge. pp. 95-117.
Nonmonotonic Logics, MIT Encyclopedia of Cognitive Science (MITECS), 1999.
a TMS paper (doyle?, filman?) abduction?

Weeks ten and eleven, 4/6 Knowledge representation meets the web

XML and the Second-Generation Web, by Jon Bosak and Tim Bray, Scientific American, may 1999. "The combination of hypertext and a global Internet started a revolution. A new ingredient, XML, is poised to finish the job"
The XML FAQ
Web Architecture: Describing and Exchanging Data, Tim Berners-Lee, Dan Connolly, and Ralph R. Swick, W3C Note 7 June 1999. Abstract: he World Wide Web is a universal information space. As a medium for human exchange, it is becoming mature, but we are just beginning to build a space where automated agents can contribute--just beginning to build the Semantic Web. The RDF Schema design [RDFSchema] and XML Schema design [XMLSchema] began independently, but we explore a common model where they fit together as interlocking pieces of the semantic web technology.
The RDF FAQ
Practical Knowledge Representation for the Web, Frank van Harmelen and Dieter Fensel, IJCAI-99 Workshop on Intelligent Information Integration,
Heflin, J., Hendler, J., and Luke, S. SHOE: A Knowledge Representation Language for Internet Applications. Technical Report CS-TR-4078 (UMIACS TR-99-71), Dept. of Computer Science, University of Maryland at College Park. 1999. Abstract: It is our contention that the World Wide Web poses challenges to knowledge representation systems that fundamentally change the way we should design KR languages. In this paper, we describe the Simple HTML Ontology Extensions (SHOE), a KR language which allows web pages to be annotated with semantics. We present a formalism for the language and discuss the features which make it well suited for the Web. We describe the syntax and semantics of this language, and discuss the differences from traditional KR systems that make it more suited to modern web applications. We also describe some generic tools for using the language and demonstrate its capabilities by describing two prototype systems that use it. We also discuss some future tools currently being developed for the language. The language, tools, and details of the applications are all available on the World Wide Web at http://www.cs.umd.edu/projects/plus/SHOE.
On2broker: Semantic-Based Access to Information Sources at the WWW, Dieter Fensel, Jurgen Angele, Stefan Decker, Michael Erdmann, Hans-Peter Schnurr, Steffen Staab, Rudi Studer, Andreas Witt,
Embedding Knowledge in Web Documents, Philippe Martin and Peter Eklund, Eighth International World Wide Web Conference, Toronto, May 11-14, 1999.
Ontobroker: Or How to Enable Intelligent Access to the WWW, Dieter Fensel, Stefan Decker, Michael Erdmann, and Rudi Studer, Eleventh Workshop on Knowledge Acquisition, Modeling and Management, Voyager Inn, Banff, Alberta, Canada, Saturday 18th to Thursday 23rd April, 1998.
The Semantic Web (Tim Berners-Lee's thoughts on the future of the Web):

Week *** , 3/23 Representing time and processes

Sowa: chapter four
Temporal reasoning, MIT Encyclopedia of Cognitive Science (MITECS), 1999..
Allen, J.F. ``Maintaining Knowledge about Temporal Intervals.'' Communications of the ACM 26, 11, 832-843, November 1983.
Allen, J.F. "Time and time again: The many ways to represent time," Int'l. Jr. of Intelligent Systems 6, 4, 341-356, July 1991.
E. Davis, Representations of commonsense knowledge, Chapter 5.
something on PSL? workflow? Petri nets? CPN?

Week twelve, 4/18 Representing and reasoning with constraints

To read
- Sowa chapter four
- Constraint Satisfaction, MIT Encyclopedia of Cognitive Science (MITECS), 1999..
- Fruhwirth T. et al., Constraint Logic Programming: An Informal Introduction, 1992.
- Constraint Logic Programming, Dick Pountain. BYTE magazine, February 1995.
- Dechter, R., "Constraint Networks (Survey)." In Encyclopedia of Artificial Intelligence, 2nd edition, 1992, John Wiley & Sons, Inc., pp. 276-285.
Background
- V. Kumar, "Algorithms for Constraint-Satisfaction Problems: A Survey", AI Magazine 13(1):32-44, 1992.
- Constraint Logic Programming over Finite Domains, Sictus prolog manual. The clp(FD) solver described in this chapter is an instance of the general Constraint Logic Programming scheme introduced in [Jaffar & Michaylov 87]. This constraint domain is particularly useful for modeling discrete optimization and verification problems such as scheduling, planning, packing, timetabling etc.
- David McAllester's lecture notes on constraint satisfaction search [postscript , pdf].
- Overview of CSP tools including CHIP, CHARME, and ILOG SOLVER, Tim Duncan .

Week thirteen 5/2 Uncertainty and time

Sowa chapter six
Baysean networks, MIT Encyclopedia of Cognitive Science (MITECS), 1999..
Eugene Charniak: Bayesian Networks without Tears, AI Magazine, (Winter 1991), 12(4): Winter 1991, 50-63 I give an introduction to Bayesian networks for AI researchers with a limited grounding in probability theory. Over the last few years, this method of reasoning using probabilities has become popular within the AI probability and uncertainty community. Indeed, it is probably fair to say that Bayesian networks are to a large segment of the AI-uncertainty community what resolution theorem proving is to the AIlogic community. Nevertheless, despite what seems to be their obvious importance, the ideas and techniques have not spread much beyond the research community responsible for them. This is probably because the ideas and techniques are not that easy to understand. I hope to rectify this situation by making Bayesian networks more accessible to the probabilistically unsophisticated.
Sowa chapter four
Temporal reasoning, MIT Encyclopedia of Cognitive Science (MITECS), 1999..
Allen, J.F. ``Maintaining Knowledge about Temporal Intervals.'' Communications of the ACM 26, 11, 832-843, November 1983.