Copyright © 1999 Massachusetts Institute of Technology
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).
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.
Copyright © 1999 Massachusetts Institute of Technology