CMSC771 2004 Living 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 seperat topic.
Week one, Jan 27& 29, Overview, introduction, what is KR
We will discuss the structure and content of the course.
- To read and discuss:
- Knowledge
representation, Pat Hayes, MIT Encyclopedia of Cognitive Science
(MITECS), 1999.
- What is a Knowledge Representation?,
Randall Davis, Howard Shrobe, and Peter Szolovits. AI Magazine,
14(1):17-33, 1993.
- R.Brachman, The future of
knowledge representation, in Proceedings of the Eighth National
Conference on Artificial Intelligence, 1990.
- Presentations:
Week two, Feb 3& 5, review of logic
- Read chapter two and three of Computational Intelligence
- Presentations:
- Background:
Weeks three-four, Jan 11-20, Logic as a knowledge representation language
- We'll also cover logic programming languages including prolog and
XSB.
- Resources:
Week five, Introduction to Ontologies
Week six, 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.
- Read: Sowa chapter three
- To read and discuss
- 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.
- 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.
- Background
- 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.)
- 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.
-
Week seven, ...to description logic
- to read and discuss
- 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.
Weeks eight-nine, More on Ontologies
- 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
- 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 ten, 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
Week eight, 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?
Week nine Spring break
Weeks ten-twelve, 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 *** , 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, 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, 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.
|