A new, additional goal is needed: appropriateness. This paper explains appropriateness and discusses how it might be achieved. It proposes an ontological approach, leading to the idea of irreducible aspects of knowledge. This idea has explanatory power concerning the deficiencies of current formalisms. It also has implications for design of knowledge representation systems, for integration and for evaluation metrics.
KR offers an alternative to programming. Both are means of encapsulating knowledge of a domain in a computer, but with KR, the job should be easier. With KR knowledge of a domain can be encapsulated in a computer by a lay person, whereas with programming there is a need to attend to programming constructs that have no direct relevance to the domain. The difference arises not so much from the issue of declarative versus procedural, but rather that genuine KR allows one to focus largely on issues at what Newell (1982, 1993) calls the knowledge level while programming requires one to focus on issues at the lower symbol level that have no real meaning at the knowledge level.
It is in this sense that the issue of KR will be discussed in this paper: as a means of expressing knowledge in order to easily encapsulate it in the computer, and its difference from programming will be a key theme.
Various knowledge representation formalisms have been proposed by the AI community, most stemming from pioneering work in the 1970s - production rules, logic, frames, etc. In this paper we use the term knowledge representation formalism (KRF) to denote the basic KR idea, such as first order predicate logic (FOPL), KR language (KRL) to denote the style of syntax and operational semantics employed to give life to the idea (e.g. PROLOG), and KR system (KRS) to denote particular software packages that implement the language (e.g. Quintus PROLOG). The KRS is what the knowledge engineer experiences, but it embodies the KRL and reflects the underlying KRF, so when I use the term, KRS, I assume considerations of KRL and KRF as well. Following Brachman (1990), KR will include reasoning - but not just deductive reasoning. While the main emphasis will be on KR that comes from AI, other approaches exist that can allow representation of knowledge, such as spreadsheets, object orientation and procedural languages like C or COBOL.
One response to such limitations has been to produce hybrid KRSs which seek to integrate two or more KRFs in one package. Rule based systems excel at inference, but it is difficult to model a problem situation in rules - for instance, a housing scheme comprising several different types of house, each on a slightly different soil and with a slightly different shape and size of garden. Not only is it a tedious business to apply rule sets to each house individually, but it is not easy to represent the relationships among the houses, even such simple types of relationship as the set. The object oriented approach, on the other hand, is good at handling sets, but is rather weak at inference. So when they are brought together in one KRS, as in Kappa-PC, the knowledge engineer should have the right KR formalism for the knowledge at hand. Rules can be used for IF-THEN inference, and objects (and classes, methods, etc.) for modelling the problem situation.
But such integration has not really succeeded. Reports from the late 1980s suggest that to make use of KEE for real life applications means that between 30% and 50% of the code is raw LISP. The author's own experience in a project using Kappa-PC is that it requires a programmer to use it. The KRF seems even more remote from the knowledge engineer in usefulness than the humble production rule. This contrasts markedly with his experience some years before of using Savoir, when a domain expert was able to build his own complete Expert Systems (Basden, 1989). Savoir allowed more genuine knowledge representation and required less programming. It is ironic, moreover, that Savoir on a 286 PC proved to be faster than the more 'powerful' Kappa on a 486.
Experiences like this - and they are not uncommon - suggest that KR research and development has been aiming in the wrong direction. One clue was given by Brachman (1990), who calls these attempts at integration 'stitching together'; they merely involve bringing together extant KRFs in one package. As Brachman complains, little thought was given to what uses the KRS will be put.
Brachman (1990) suggests that usability is an important requirement and he identifies knowledge presentation, browsing, querying and explanation as the elements of usability. We see here the influence of the Human Computer Interaction community. While these features are useful (albeit making the KR system more complex to use) they do not attack the basic point: the process of expressing your knowledge may still require you to engage in programming. These issues of usability are characteristics of the KRS, but go no deeper. We still need to examine the KRF because it is at this deeper layer that the requirements emerge.
The first and probably most basic requirement of a KRF is that of sufficiency. The KRF should provide at least some way of representing and manipulating or reasoning with all types of knowledge that will be encountered. This way might involve some programming, aggregating more primitive facilities into a complex whole. But if the KRF is not sufficient - and most are today - there will be certain types of knowledge that cannot be represented at all or certain types of reasoning or manipulation that are impossible. For instance, a KRF based on pure propositional logic cannot increment Fred's age on his birthday, except by throwing away one knowledge base and building a new one. Sufficiency is a basic necessity, but it is not itself sufficient to yield KR as we have defined it.
The second is efficiency. The KRS should be able to make its inferences in reasonable time and hold its knowledge without consuming unreasonable resources. An important consideration in efficiency is tractability; FOPL is intractable in the worst case. A number of attempts are being made to address this problem, most involving either logics of reduced expressive power or incomplete inference. See Crawford and Kuipers (1991) and Selman and Kautz (1991). Russell and Wefald (1989) tackle tractability by means of meta reasoning. Wider issues of efficiency are often tackled on a pragmatic basis, but Rosenschein (1990) has suggested the use of mechanisms with in-built world knowledge to increase efficiency. While efficiency and tractability are important in KR they are not sufficient to reduce the amount of programming needed.
The third requirement that has attracted a lot of attention is expressive power. Levesque and Brachman (1985) give two benefits of expressive power. One is to encapsulate a lot of knowledge with few keystrokes. Inheritance mechanisms increase expressive power in that we can encapsulate in our knowledge base the fact that 'all cats have whiskers' in one sentence, rather than having to enter such knowledge about every cat. The subroutining capability of third generation languages likewise increases expressive power. The other is to express incomplete knowledge (such as saying 'Either John or Jill is tall' without saying who). FOPL provides both types of benefit. Sorted logics increase expressive power still further and also aid the deductive process (Frisch, 1989). But expressive power has its dangers. It shifts the knowledge engineer's attention away from the specific cases - those cats that have lost their whiskers. Also, it often has the opposite effect we are aiming for here. Expressive power often implies terse and powerful syntax, and thus restricts KR activity to an elite who know how to wield such power.
Minsky (1981) proposed that we should concentrate on sufficiency and efficiency in the enterprise of defining a good KRF. Levesque and Brachman (1985) agreed with most that expressive power is desirable, but showed that there is a tradeoff between it and tractability. But even if we were able to achieve all three of these, we would still not have a means of ensuring that lay people can easily encapsulate knowledge in a computer without programming. While sufficiency, efficiency and some measure of expressive power are desirable in a KR system, something else is needed - what we will call appropriateness.
In order to determine what the missing ingredient is, let us look at some examples in which programming is required and examine some of the problems that arise.
struct Field {
...
struct LapwingNest *Contains;
...
};
struct LapwingNest {
...
struct Field *IsIn;
struct LapwingNest *NextNest;
...
};
The IsIn pointer allows us to find the Field, given the LapwingNest. The Contains and NextNest pointers form a linked list which allows us to find any of the Nests in a given Field. Using pointers in this manner, even though sufficient, efficient and adequately expressive, leads to problems. First, it is well known that pointers are a major source of bugs. Second, for a one-to-many relationship of this kind, the knowledge engineer has to shoulder all the responsibility of maintaining the linked list - and of remembering the extra NextNest pointer in the first place. Sometimes it is advisable to have a doubly linked list, and the task becomes even more complex. For many-to-many relationships the programming task is worse still. Third, pointers do not have the richness of real relationships. For instance, to add types (IsIn, Contains) that are accessible at run time rather than at compile time, the knowledge engineer must not only know how to add the required type data, but must know where to put it. Pointers are not a truly appropriate way of expressing relationships.
Appropriateness thus appears to be a necessity, along with sufficiency, efficiency and some measure of expressive power, if we are to achieve our aim of what Brachman (1990) called 'KR to the People'.
But can we define appropriateness? Ultimately it may be an intuitive rather than rationalizable concept, but we can at least characterize it by examining the problems that lack of appropriateness generates. First, it increases the sheer volume of symbol level effort required of the knowledge engineer. (Knowledge level effort is to be expected by virtue of the degree of complexity in the knowledge itself.) Second, it can mean imposing arbitrary restrictions on how knowledge can be expressed. Third, it means that there is no mapping between primitive concepts in real life and primitives in representation. Fourth, it makes it more likely that errors will be made or other dangers encountered. Fifth, it means that the task becomes more and more expert, as the knowledge engineers are required to remember what dangers exist, what specialized symbol level techniques are needed, and how to perform them. Sixth, it has led to much research effort being possibly mis-directed.
How are we to identify all the primitives needed? Does it require a large research programme to ensure that none have been missed? Ultimately it will probably be a long time before all have been discovered, but our task may be made easier because it seems that primitives are grouped. Some primitives are to do with relationships, some with spatial knowledge, etc. Our research therefore can be aided if we identify irreducible aspects of knowledge around which these primitives are grouped.
But there are two types of ontology. The first is ontology of the real world used for instance in the construction of class hierarchies. Rosenschein (1990) uses it in a different way, suggesting incorporation of knowledge of the world into the deduction engine. This, he claims, improves run-time efficiency. This type of ontology tells us that there are such things as rabbits, that they are mammals, that there are or are not laws pertaining to the the physical, social, aesthetic or juridicial worlds, etc. But it cannot help identify aspects of knowledge. What we need is not knowledge of the world as such, but to establish world-friendly structures and mechanisms.
What we need is ontology of knowledge itself, of the world of symbolic communication and manipulation. It is this that can help us identify genuine irreducibility among aspects of knowledge and the primitives that relate to them. Sadly, the intellectual climate over the past few decades has mitigated against even asking ontological questions about the structure of knowledge, so there are as yet very few firm answers.
Items (entities, objects) have attributes (slots), and form relationships with each other. They are persistent. Values can be the contents of attributes, but are not persistent. Functions can be seen as a kind of relationship among values or a generator of values. Spatial knowledge includes not only simple concepts like direction and distance, but also concepts like surrounding, illustrated above. The word, change, are used in preference to time since the emphasis is not on temporal sequence but the fact that things change. The KB is embedded in the world and part of it, rather than just being a detached reasoner (Winograd and Flores, 1986). Change can be discrete or continuous. Primitives in each of these aspects can be aggregated to form more complex structures; for instance a number of primitive changes can be grouped to form a subroutine or method.
I do not claim that this is in any way an exhaustive list. But it does seem that KRFs that are deficient in one or more of these prove more difficult to use for wide-ranging knowledge, and that the difficulties correlate to these deficiencies. PROLOG is (nearly) appropriate for items and relationships but is less appropriate for values, change or space. LISP is appropriate for values but less so for items, change or space. C is appropriate for values and change, but inappropriate for handling items, relationships and space. Object oriented languages are good with items, values and change, but are weak when it comes to relationships and cannot handle space. To handle an aspect for which a KRF is inappropriate will involve programming rather than knowledge representation.
Relationships are typed. They can be created and destroyed. They can be one-to-one, one-to-many or many-to-many. There can be constraints on what relationships can be formed between what items. They can be expressed syntactically either as predicates, or as frame slots, or as arrows linking boxes (among other ways). As Woods (1975) pointed out, many relationships can have variable semantics. Many KRSs and database management systems offer good support for these primitives, but not for the ones that follow. Many relationships are binary, but some are of greater arity, and few KRSs can easily support this without extra programming (Schmolze, 1989). As discussed above, most binary relationships have inverses, but very few KRSs give direct support. Relationships, with items, form graphs, and these are of different types: sets, lists, hierarchies, directed acyclic graphs (DAG), etc. In each of these the relationships can be followed in various ways, and each of these ways should be made available to the knowledge engineer. Finally, it should be possible to treat all relationships as items from time to time, allowing them to have attributes (including methods), and even to form relationships with other items or relationships.
Such an analysis is, of course, incomplete, and will be required for all the aspects if we are to move towards appropriate KRFs, KRLs and KRSs that can offer 'KR to the People'. Very few seem to have attempted such an analysis. Kent (1978) is worth reading, and Sowa (1984) moved a little in this direction.
What is important here is that each aspect of knowledge, and each primitive within each aspect, requires all three elements of the KRS.
The aspects of knowledge must be integrated at a more fundamental level. But an ontological understanding of them actually helps in such an integration. By acknowledging, for instance, that rules operate on values - any values - then those found in the attributes of items can be operated on by means of rules, and general appropriateness is enhanced. Further, values can also be operated on by procedural statements, by predicate statements, etc. so by ensuring that these too can operate on any values, we have a more complete integration of rules, procedures and predicates around values. The knowledge engineer then does not encounter the divisions found in Kappa-PC.
Such an approach also clearly identifies what design issues are likely to be important in building a KR system. It ensures, for instance, that the value mechanism is designed and implemented in such a way that changing a value by means of a procedural statement leads to some forward chaining of the change through any rules and predicates that refer to that value. The technology to achieve this is available today, having been developed in the traditional KRFs.
The KRS I am after does not offer maximum expressive power, as defined above. Indeed, it recognises that high expressive power can have drawbacks. My aim in KR is not to solve all logic problems in a short time, but rather to provide a high level of appropriateness so that lay people can do their own knowledge engineering. I want, as Brachman rightly points out, to bring 'KR to the People'.
This paper has discussed the need for appropriateness, has illustrated what it is and has discussed how it might be achieved.
Fundamental to achieving appropriateness is an ontological approach. An ontology of knowledge will identify irreducible aspects of knowledge, and primitives of those aspects. Each of these primitives should be supported in the KRS as primitive facilities for KB, engine and interface. Then the need for programming of symbol level operations is reduced. Examples were given of where such programming is often needed, and of the problems it generates. In particular spatial knowledge needs better support.
Such an approach has a number of benefits. First, it can explain the limitations encountered in most KRSs available today. Second, the elucidation of primitives may offer the metric of quality and scope that Brachman (1990) has called for. Third, it can provide guidance on the design of KR system by virtue of specifying what each primitive is and what is therefore required of the KB, engine and interface. Fourth, since the types of primitive envisaged are ontologically fundamental they form a basis for a fundamental integration not only of the KRFs found in AI but also with those found in mainstream computer science.
Work on such an approach is underway, and will be reported in due course.
Basden A, (1989), "On the use of Expert Systems to handle Corrosion Knowledge", in Jovanovic A S, Kussmaul K F, Lucia A C, Bonissone P P (eds.), "Expert Systems in Structural Safety Assessment; Lecture Notes in Engineering", Springer Verlag.
Brachman R J, (1990), "The Future of Knowledge Representation", AAAI-90, Proc. Eighth National Conference on Artificial Intelligence, pp. 1082-92.
Crawford J M, Kuipers B J, (1991), "Negation and Proof by Contradiction in Access-Limited Logic", AAAI-91, Proc. Ninth National Conference on Artificial Intelligence, pp. 897-903.
Frisch A M, (1989), "A General Framework for Sorted Deduction: Fundamental Results on Hybrid Reasoning", in Brachman R J, Levesque H J, Reiter R (eds.), KR-89: Proc. of the First International Conference on Principles of Knowledge Representation and Reasoning, pp. 126-36
Kent W, (1978), "Data and Reality", North Holland.
Levesque H J, Brachman R J, (1985), "A Fundamental Tradeoffin Knowledge Representation and Reasoning (Revised Version)", in Brachman R J, Levesque H J, (eds.), "Readings in Knowledge Representation", Morgan Kaufmann, Los Altos, California.
McCarthy J, Hayes P J, (1969), "Some Philosopical Problems from the Standpoint of Artificial Intelligence", pp. 463-502, in Meltzer B, Michie D (eds.), Machine Intelligence 4, Edinburgh University Press.
Minsky M, (1981), "A framework for representing knowledge", in Haugeland J (ed.), "Mind Design", MIT Press, pp. 95-128.
Newell A, (1982), "The Knowledge Level", Artificial Intelligence, 18, p.87- 127.
Newell A, (1993), "Reflections on the knowledge level", Artificial Intelligence, v. 59, pp. 31-38.
Ringland G A, Duce D A, (1988), "Approaches to Knowledge Representation", Wiley, New York.
Rosenschein S J, (1990), "Reasoning and Acting in Real Time", AAAI-90, Proc. Eighth National Conference on Artificial Intelligence.
Schmolze J G, (1989), "Terminological Knowledge Representation Systems Supporting N-ary Terms", in Brachman R J, Levesque H J, Reiter R (eds.), KR-89: Proc. of the First International Conference on Principles of Knowledge Representation and Reasoning, pp. 432-43
Russell S, Wefald E, (1989), "Principles of Metareasoning", in Brachman R J, Levesque H J, Reiter R (eds.), KR-89: Proc. of the First International Conference on Principles of Knowledge Representation and Reasoning, pp. 400-11.
Selman B, Kautz H, (1991), "Knowledge Compilation using Horn Approximations", AAAI-91, Proc. Ninth National Conference on Artificial Intelligence, pp. 904-9.
Sowa J F, (1984), "Conceptual structures: information processing in minds and machines", Addison Wesley, Reading, MA, USA.
Winograd T, Flores F, (1986), "Understanding computers and cognition", Addison Wesley.
Woods W A, (1975), "What's in a Link: Foundations for Semantic Networks", in Bobrow D G, Collins A M (eds.), "Representation and Understanding: Studies in Cognitive Science", Academic Press, New York.
Last updated: