Frame-Based Systems
Frame-based
systems are knowledge representation systems that use frames, a
notion originally introduced by Marvin Minsky, as their primary
means to represent domain knowledge. A frame is a structure for representing
a CONCEPT or situation such as "living
room" or "being in a living room." Attached
to a frame are several kinds of information, for instance, definitional
and descriptive information and how to use the frame. Based on the
original proposal, several knowledge representation systems have
been built and the theory of frames has evolved. Important descendants
of frame-based representation formalisms are description logics that
capture the declarative part of frames using a logic-based semantics.
Most of these logics are decidable fragments of first order
logic and are very closely related to other formalisms such
as modal logics and
feature logics.
In the seminal paper "A
framework for representing knowledge," Minsky (1975) proposed
a KNOWLEDGE REPRESENTATION scheme that was
completely different from formalisms used in those days, namely,
rule-based and logic-based formalisms. Minsky proposed organizing knowledge
into chunks called frames. These frames are supposed to
capture the essence of concepts or stereotypical situations, for
example being in a living room or going out for dinner, by clustering
all relevant information for these situations together. This includes
information about how to use the frame, information about expectations (which
may turn out to be wrong), information about what to do if expectations
are not confirmed, and so on. This means, in particular, that a
great deal of procedurally expressed knowledge should be part of
the frames. Collections of such frames are to be organized in frame systems in
which the frames are interconnected. The processes working on such
frame systems are supposed to match a frame to a specific situation,
to use default values to fill unspecified aspects, and so on. If
this brief summary sounds vague, it correctly reproduces the paper's
general tone. Despite the fact that this paper was a first approach
to the idea of what frames could be, Minsky explicitly argued in
favor of staying flexible and nonformal.
Details that had been left out in
Minsky's 1975 paper were later filled in by knowledge representation
systems that were inspired by Minsky's ideas -- the
most prominent being FRL and KRL (Bobrow and Winograd 1977). KRL
was one of the most ambitious projects in this direction. It addressed
almost every representational problem discussed in the literature. The
net result is a very complex language with a very rich repertoire
of representational primitives and almost unlimited flexibility.
Features that are common to FRL,
KRL, and later frame-based systems (Fikes and Kehler 1985) are:
(1) frames are organized in (tangled) hierarchies; (2)
frames are composed out of slots (attributes) for which fillers (scalar
values, references to other frames or procedures) have to be specified
or computed; and (3) properties (fillers, restriction on fillers,
etc.) are inherited from superframes to subframes in the hierarchy
according to some inheritance strategy. These organizational
principles turned out to be very useful, and, indeed, the now popular
object-oriented languages have adopted these organizational principles.
From a formal point of view, it was
unsatisfying that the semantics of frames and of inheritance
was specified only operationally. So, subsequent research in the
area of knowledge representation addressed these problems. In the
area of
defeasible inheritance, principles based on nonmonotonic logics
together with preferences derived from the topology of the inheritance
network were applied in order to derive a formal semantics (Touretzky
1986; Selman and Levesque 1993). The task of assigning
declarative semantics to frames was addressed by applying methods
based on first order LOGIC.
Hayes (1980) argued that "most
of frames is just a new syntax for parts of first order logic." Although
this means that frames do not offer anything new in expressiveness,
there are two important points in which frame-based systems may
have an advantage over systems using first-order logic. Firstly,
they offer a concise way to express knowledge in an object-oriented way
(Fikes and Kehler 1985). Secondly, by using only a fragment of first
order logic, frame-based systems may offer more efficient means for
reasoning.
These two points are addressed by
the so-called description logics (also called terminological
logics, concept languages, and attributive description languages; Nebel
and Smolka 1991), which formalize the declarative part of frame-based
systems and grew out of the development of the frame-based system KL-ONE
(Brachman and Schmolze 1985). In description logics, it is possible
to build up a concept hierarchy out of atomic concepts (interpreted
as unary predicates and denoted by capitalized words) and attributes,
usually called roles (interpreted as binary predicates
and denoted by lowercase words). The intended meaning of atomic
concepts can be specified by providing concept descriptions made
up of other concepts and role restrictions, as in the following
informal example:
Woman = Person
and Female
Parent = Person with some child
Grandmother = Woman with
some child who is a Parent
One of the most important
reasoning tasks in this context is the determination of subsumption
between two concepts, that is, determining whether all instances
of one concept are necessarily instances of the other concept taking
into account the definitions. For example, "Grandmother" is subsumed
by "Parent" because everything that is a "Grandmother" is -- by
definition -- also a "Parent." Similar to
the subsumption task is the instance-checking task, where
one wants to know if a given object is an instance of the
specified concept.
Starting with a paper by Brachman
and Levesque (1984), the COMPUTATIONAL COMPLEXITY of subsumption
determination for different variants of description logics has extensively
been analyzed and a family of algorithms for solving the subsumption
problem has been developed (Schmidt-Schauss and Smolka 1991).
Although in most cases subsumption
is decidable, that is, easier than inference in full first order
logic, there are cases when subsumption becomes undecidable (Schmidt-Schauss
1989). Aiming for polynomial-time decidability, however, leads to very
restricted description logics, as shown by Donini et al. (1991).
Further, if definitions of concepts as in the example above are
part of the language, even the weakest possible description logic
has an NP-hard subsumption problem (Nebel 1990). Although these
results seem to suggest that description logics are not usable because
the computational complexity of reasoning is too high, experience
with implemented systems shows that moderately expressive description
logics are computationally feasible (Heinsohn et al. 1994). In fact,
current frame-based systems are efficient enough to support large
configuration systems that are in everyday use at AT&T
(Brachman 1992).
In the course of analyzing the logical
and computational properties of frame-based systems, it turned out
that description logics are very similar to other formalisms used
in computer science and COMPUTATIONAL LINGUISTICS (Nebel
and Smolka 1991). First of all, the declarative part of object-oriented
database languages bears a strong resemblance to description
logics, and it is possible to apply techniques and methods developed
for description logics in this area (Buchheit et al. 1994). Second,
there is a very strong connection to modal logics and to dynamic
logics (Schild 1991). In fact, the "standard" description
logic ALC (Schmidt-Schauss and Smolka 1991) is simply a notational
variant of the MODAL LOGIC K with multiple
agents. Third, feature logics, which are the constraint
logic part of so-called unification grammars such as HPSG, are very
similar to description logics. The only difference is that attributes
in feature logics are single-valued, whereas they are multivalued
in description logics. Although this seems to be a minor difference,
it can make the difference between decidable and undecidable reasoning
problems (Nebel and Smolka 1991).
See also
KNOWLEDGE-BASED SYSTEMS
KNOWLEDGE ACQUISITION
NONMONOTONIC LOGICS
SCHEMATA
-- Bernhard
Nebel
References
Bobrow, D. G., and T. Winograd. (1977). An overview
of KRL-0, a knowledge representation language. Cognitive Science 1(1):
3 - 46.
Brachman, R. J. (1992). Reducing CLASSIC to
practice: knowledge representation theory meets reality. In B. Nebel,
W. Swartout, and C. Rich, Eds., Principles of Knowledge Representation
and Reasoning: Proceedings of the 3rd International Conference (KR-92). Cambridge,
MA, pp. 247 - 258.
Brachman, R. J., and H. J. Levesque. (1984).
The tractability of subsumption in framebased description languages.
In Proceedings of the 4th National Conference of the American
Association for Artificial Intelligence (AAAI-84). Austin,
TX, pp. 34 - 37.
Brachman, R. J., and J. G. Schmolze. (1985).
An overview of the KL-ONE knowledge representation system. Cognitive
Science 9(2): 171 - 216.
Buchheit, M., M. A. Jeusfeld, W. Nutt, and M.
Staudt. (1994). Subsumption between queries to object-oriented databases.
In K. Jeffery, M. Jarke, and J. Bubenko, Eds., Advances
in Database Technology -- EDBT-94. 4th International
Conference on Extending Database Technology. Cambridge, pp.
15 - 22.
Donini, F. M., M. Lenzerini, D. Nardi, and W.
Nutt. (1991). Tractable concept languages. In Proceedings
of the 12th International Joint Conference on Artificial Intelligence
(IJCAI-91). Sydney, pp. 458 - 465.
Fikes, R. E., and T. Kehler. (1985). The role
of frame-based representation in knowledge representation and reasoning. Communications
of the ACM 28(9): 904 - 920.
Hayes, P. J. (1980). The logic of frames. In
D. Metzing, Ed., Frame Conceptions and Text Understanding. Berlin:
deGruyter, pp. 46 - 61.
Heinsohn, J., D. Kudenko, B. Nebel, and H.-J.
Profitlich. (1994). An empirical analysis of terminological representation
systems. Artificial Intelligence 68(2): 367 - 397.
Minsky, M. (1975). A framework for representing
knowledge. In P. Winston, Ed., The Psychology of Computer
Vision. New York: McGraw-Hill, pp. 211 - 277.
Nebel, B. (1990). Terminological reasoning is
inherently intractable. Artificial Intelligence 43:
235 - 249.
Nebel, B., and G. Smolka. (1991). Attributive
description formalisms . . . and the rest of the world. In O. Herzog
and C.-R. Rollinger, Eds., Text Understanding in LILOG.
Berlin: Springer, pp. 439 - 452.
Schild, K. (1991). A correspondence theory for
terminological logics: preliminary report. In Proceedings
of the 12th International Joint Conference on Artificial Intelligence
(IJCAI-91). Sydney, pp. 466 - 471.
Schmidt-Schauss, M. (1989). Subsumption in KL-ONE
is undecidable. In R. Brachman, H. J. Levesque, and R. Reiter, Eds., Principles
of Knowledge Representation and Reasoning: Proceedings of the 1st International
Conference (KR-89). Toronto, pp. 421 - 431.
Schmidt-Schauss, M., and G. Smolka. (1991).
Attributive concept descriptions with complements. Artificial
Intelligence 48: 1 - 26.
Selman, B., and H. J. Levesque. (1993). The
complexity of path-based defeasible inheritance. Artificial
Intelligence 62: 303 - 339.
Touretzky, D. S. (1986). The Mathematics
of Inheritance Systems. Los Altos, CA: Morgan Kaufmann.