# Chapter 11 - Knowledge Representation Summary

In this chapter, we review the representational schemes that have been discussed so far and we mention briefly some additional representational techniques that are sometimes useful. You may find it useful at this point to reread Chapter 4 for a review of the knowledge representation issues that we outlined there.

### 11.1 Syntactic-Semantic Spectrum of Representation

One way to review the representational sehemes we have just described is to consider an important dimension along which they can be characterized. At one extreme are purely syntactic systems, in which no concern is given to the meaning of the knowledge that is being represented. Such systems have simple, uniform rules for manipulating the representation. They do not care what information the representation contains. At the other extreme are purely semantic systems, in which there is no unified form. Every aspect of the representation corresponds to a different piece of information, and the inference rules are eorrespondingly complicated.

So far, we have discussed eight declarative structures in which knowledge can be represented:

- Predicate logic
- Production rules
- Nonmonotonic systems
- Statistical reasoning systems
- Semantic nets
- Frames
- Conceptual dependency
- scripts
- CYC

Of these, the logical representations (predicate logic and the nonmonotonic systems) and the statistical ones are the most purely syntactic. Their rules of inference are strictly syntactic procedures that operate on well-formed formulas (wff) regardless of what those formulas represent. Production rule systems are pfimarily syntactic also. The interpreters for these systems usually use only syntactic information (such as the form ofthe pattern on the left side, the positionofthe rule in the knowledge base, or the position of the matched object in short-term memory) to decide which rules to fire. Again here we see the similarity between logic and production rules as ways of representing and using knowledge. But it is possible to build production-rule systems that have more semantics embedded in them. For example, in EMYCIN and other systems that provide explicit support for certainty factors, the semantics of certainty factors are used by the rule interpreter to guide its behavior.

Slot-and-filler structures are typically more semantically oriented, although they span a good distance in this spectrum. Semantic nets, as their name implies, are designed to capture semantic relationships among entities, and they are usually employed with a set of inference rules that have been specially designed to handle correctly the specific types of ares present in the network. (For example, isa links are treated differently from most other kinds of links.) Frame systems are typically more highly structured than are semantic nets, and they contain an even larger set of specialize d inference rules, including those that implement a whole array of default inheritance rules, as well as other procedures sueh as consistency checking.

Conceptual dependency moves even further toward being a semantic rather than a syntactic representation. It provides not only the abstract structure of a representation but also a specific indication of w hat components the representation should contain (such as the primitive ACTs and the dependency relationships). Thus, although CD representations can be thought of as instances of semantic nets, they can be used by more powerful inference mechanisms that exploit specific knowledge about what they contrin. And although scripts appear very similar to frames, they are frames in which the slots have been carefully chosen to represent the information that is useful when reasoning about situations. This makes it possible for script manipulation procedures to exploit knowledge about what they are working with in order to solve problems more efficiently. CYC uses both frames and logic (depending on the level at which we view the knowledge) to encode specific types of knowledge and inference aimed at commonsense reasoning. CYC is the most semantic of the systems we have described, since it provides the most built-in knowledge of how to manipulate specific kinds of knowledge structures. It also contains a comprehensive ontology into which new knowledge can be put.

In general, syntactic representations are to knowledge representation what the weak methods of Chapter 3 are to problem-solving. They are, in principle, adeyuate for any problem. But for hard problems. their generality often means that answers cannot be found quickly. Stronger, more semantically oriented approaches make it possible to use knowledge more effectively to guide search. This does not mean that there is no place for weak or syntactic rnethods. Sometimes they are adequate, and their simplicity makes a formal analysis of programs that use them much more straightforward than a comparable analysis ofa program based on semantic methods. But powerful programs depend on powerful knowledge, some of which is typically embedded in their problem- solving proeedures and some of which is embedded in their knowledge representation mechanisms. In fact, as we have seen throughout Part II of this book, it is not usually possible to separate the two facets cleanly.

However, as we have seen in the last few chapters, knowledge representation systems can play the role of support systems that underly specific problem-solving programs. The knowledge representation system is typically expected not just to hold knowledge but also to provide a set of basic inference procedures, such as property inheritance or truth maintenance, that are defined on the knowledge. Specific problem-solving procedures can then be impfemented as a level on top of that.

When knowledge representation systems are viewed as modules that are going to be incorporated as black boxes into larger programs, a good argument can be made [Brachman and Levesque, 1984] that their functionality should be restricted to purely syntactic operations about which very precise statements can be made. Essentially, this argument follows standard software engineering principles. To use a module effectively, one must have access to precise functional specifications of that module. If a knowledge representation system performs operations that are highly semantic in nature, it is difficult or impossible to write such a set of specifications. Among the kinds of operations that pose difficulties in this regard are the following:

- Operations whose result is defined to be the first or the best object satisfying some set of specifications. One example of such an operation is the resolution of a contradiction in a default-reasoning system. These operations require heuristics to define first or best and thus cannot usually be described in a straightforward way without appealing to the heuristics.
- Operations that are given resource limitations and whose output depends on how effectively those resoucces can be used. One common example of such an operation is default reasoning, when it is stated in a form such as, "Assume x unless ±x can be shown within z inference steps." The semantics of these operations then depend on how the resources happen to be exploited.

Of course, we are not saying that operations with these properties should not be done in reasoning programs. They are necessary. We are only saying that they should be within the control of some domain-specific problem solver rather than hidden within a general-purpose black box.

### 11.2 Logic and Slot-and-Filler Structures

Slot-and-filler structures have proven very valuable in the efficient storing and retrieving of knowledge for AI programs. They are usually poor, however, when it comes to representing rule-like assertions of the form "If x, y, and z, then conclude w." Predicate logic, on the other hand, does a reasonable job of representing such assertions, although general reasoning using these assertions is inefficient. Slot-and-filler representations are usually mone semantic, meaning that their reasoning procedures are more varied, more efficient, and tied more closely to specific types of knowledge.

Hayes [1973] and Nilsson [1980] have shown how slot-and-filler structures can be translated into predicate logic. Concepts become one-place predicates, e.g., dog(x), and slots become two-place predicates, e.g., color(canary, yellow). Inference mechanisms like property inheritance can be expressed in logical notation, as a series of logical impli- cations, which can then be manipulated with resolution. Working through a translation of a slot-and-filler structure to logic helps clear up what are often imprecisely specified reasoning melhods in these structures. In practical terms. however, moving to logic means losing efficiency. For example, a typical slot-and-filler system has procedures for doing property inheritance that are much faster than doing property inheritance via resolution-basedtheorem proving. Partoftheinefficiency ofgeneralreasoning methods like resolution can be overcome by intelligent indexing schemes, but the more heavily cross-indexed predicate logic clauses are, the more they come to resemble slot-and-filler structures.

On the other hand, it is difficult to express assertions more complex than inheritance in slot-and-filler structures. Is it possible to create a hybrid representational structure that combines the advantages of slot-and-filler structures with the advantages of predicate logic? We have already seen one system (CYC) that maintains both a logical (epistemological level) and frame-based (heuristic level) version of each fact. Another system, called KRYPTON [Brachman et al.,1985], divides its knowledge into two distinct repositories, called the TBox and the ABox. The TBox is a slot-and-filler structure that contains terminological information. In it are concepts like "person," "car," and "person with three children." The ABox contains logical assertions, such as "Every person with three children owns a car." The atomic predicates used in A Box assertions refer to concepts defined in the TBox.

In logic-based systems, predicates such as triangle and polygon are primitive notions. These primitives are tied to one another via assertions, e.g., isa(triangle, polygon) and isa(rectangle, polygon). KRYPTON relates concepts like triangle and polygon terminologically, in the TBox, rather than assertionally. Thus we can do efficient terminological reasoning in the TBox and more general reasoning in the ABox. Terminological reasoning involves answering questions about subsumption and inheritance, such as "Can something be both a triangle and a rectangle?"

Consider a resolution theorem prover running with assertions in the ABox. A standard operation in resolution is determining when pairs of literals such as f(x) and f(x) are inconsistent. Standard resolution requires that the literals be textually unifiable (except for the negation sign). KRYPTON extends the idea of textual inconsistency to rerminological inconsistency in order to make the theorem prover more efficient. The TBox can tell that the two assertions triangle(x) and rectangle(x) are inconsistent and can thus be resolved against each other. The TBox can also detennine the inconsistency of triangle(x) and ±polygon(x); moreover, the two assertions ±rectangle(x) and polygon(x) can be resolved against each other as long as we add to the resolvent the fact that x must have an angle which is not 90 degrees. If TBox computations are very efficient, then A Box proofs will be generated much faster than they would be in a pure logic framework.

### 11.3 Other Representational Techniques

In the last several chapters, we have described various techniques that can be used to represent knowledge. But our survey is by no means complete. There are other ways of representing knowledge; some of them are quite similar to the ones we have discussed and some are quite different. In this section we briefly discuss three additional methods: constraints, simulation models, and subsymbolic systems. Keep in mind throughout this discussion that it is not always the case that these various representational systems are mutually inconsistent. They often overlap, either in the way they use component representational mechanisms, the reasoning algorithms they support, or the problem- solving tasks for which they are appropriate.

##### 11.3.1 Representing Knowledge as Constraints

Much of what we know about the world can be represented as sets of constraints. We talked in Section 3.5 about a very simple problem, cryptarithmetic, that can be described this way. But constraint-based representations are also useful in more complex problems. For example, we can describe an electronic circuit as a set of constraints that the states of various components of the circuit impose on the states of other components by virtue of being connected together. If the state of one of these components changes, we can propagate the effect of the change throughout the circuit by using the constraints. As a second example, consider the problem of interpreting visual scenes. We can write down a set of constraints that characterize the set of interpretations that can make sense in our physical world. For example, a single edge must be interpreted consistently, at both of its ends, as either a convex or a concave boundary. Finally, as we saw in Section 8.3, there are several kinds of relationshipsthat can be represented as sets of constraints on the likelihoods that we can assign to collections of interdependent events.

In some sense, everything we write in any representational system is a constraint on the world models or problem solutions that we want our program to accept. For example, a wff [e.g., &every;x : man(x) -> mortal(x)] constrains the set of consistent models to those that do not include any man who is not mortal. But there is a very specific sense in which it is useful to talk about a specific class oftechniques as constraint-based. Recall that in Section 3.5 we presented an algorithm for constraint satisfaction that was based on the notion of propagating constraints throughout a system until a final state was reached. This algorithm is particularly effective precisely when knowledge is represented in a way that makes it efficient to propagate constraints. This will be true whenever it is easy to locate the objects that a given object influences. This occurs when the objects in the system are represented as a network whose links correspond to constraints among the objects. We considered one example ofthis when we talked about Bayesian networks in Section 8.3. We consider other examples later in this book. For example, we retum to the problem of simulating physical processes, such as electronic circuits, in Section 19.l. We present in Section 14.3 a constraint-propagation solution (known as the Waltz algorithm) to a simple vision problem. And in Section 15.5 we outline a view of natural language understanding as a constraint satisfaction task.

##### 11.3.2 Models and Model-Based Reasoning

For many kinds of problem-solving tasks, it is necessary to model the behavior of some object or system. To diagnose faults in physical devices, such as electronic circuits or electric motors, it is necessary to model the behavior of both the conectly functioning device and some number of ill-functioning variants of it. To evaluate potential designs of such devices reyuires the same capability. Of course, as soon as we begin to think about modeling such complex entities, it becomes clear that the best we will be able to do is create an approximate model. There are various techniques that we can use to do that.

When we think about constructing a model of some entity in the world, the issue of what we mean by a model soon arises. To what extent should the structure of the model mirror the structure of the object being modeled? Some representational techniques tend to support models whose structure is very ditferent from the structure of the objects being modeled. For example, in predicate logic we write wff's such as &every;x : raven(x) --> black(x). In the real world, though, this single fact has no single realization; it is distributed across all known ravens. At the other extreme are representations, such as causal networks, in which the physical structure of the world is closely modeled in the structure of the representation.

There are arguments in favor of both ends of this spectrum (and many points in the middle). For example, ifthe knowledge structure closely matches the problem structure, then the frame problem may be easier to solve. Suppose, for example, that we have a robot-planning program and we want to know if we move a table into another room, what other objects also change location. A model that closely matches the structure of the world (as shown in Figure 1 I.1(u)) will make answering this question easy, white alternative representations (such as the one shown in Figure Il.l(b)) will not. For more on this issue, see Johnson-Laird [1983]. There are, however, arguments for representaiions whose structures do not closely model the world. For example, such representations typically do a betterjob ofcapturing generalizations and thus of making predictions about some kinds of novel situations.

##### 11.3.3 Subsymbolic Systems

So far, aIl of the representations that we have discussed are symbolic, in the sense we defined in Section 1.2. There are altemative representations, many of them based on a neural model patterned after the human brain. These systems are often called neural nets or connectionist systems. We discuss such systems in Chapter 18.

### 11.4 Summary ofthe Role of Knowledge

In the last several chapters we have focused on the kinds of knowledge that may be useful to programs and on ways of representing and using that knowledge within programs. To sum up, for now, our treatment of knowledge within A1 programs, let us return to a brief discussion of the two roles that knowledge can play in those programs.

- It may define the search space and the criteria for determining a solution to a problem. We call this knowledge essential knowledge.

  ###### Figure 11.1: Capturing Structure in Models

- It may improve the effiþciency ofa reasoning procedure by informing that procedure of the best places to look for a solution. We call that knowledge heuristic knowledge.

In formal tasks, such as theorem proving and game playing, there is only a small amount ofessential knowledge and the need for a large amount of heuristic knowledge may be challenged by several brute force programs that perform quite successfully (e.g., thechess programs HITECH [Berlinerand Ebeling,1989] and DEEP THOUGHT [Anantharaman et al., 1990]). The real knowledge challenge arises when we tackle naturally occuning problems, such as medical diagnosis, natural language processing, or engineering design. In those domains, substantial bodies of both essential and heuristic knowledge are absolutely necessary.

### 11.5 Exercises

1. Artificial intelligence systems employ a variety of formalisms for representing knowledge and reasoning with it. For each of the following sets of sentences, indicate the formalism that best facilitates the representation of the knowledge given in the statements in order to answer the question that is posed. Explain your choice brieHy. Show how the statements would be encoded in the formalism you have selected. Then show how the question could be answered.
   - John likes fruit.
   - Kumquats are fruit.
   - People eat what they like.
   - Does John eat kumquats?
   - Assume that candy contains sugar unless you know specifically that it is dietetic.
   - M&M's are candy.
   - Diabetics should not eat sugar
   - Bill is a diabetic.
   - Should Bill eat M&M's?
   - Most people like candy.
   - Most people who give parties like to serve food that their guests like.
   - Tom is giving a party.
   - What might Tom like to serve?
   - When you go to a movie theatre, you usually buy a ticket, hand the ticket to the ticket taker, and then go and find a seat.
   - Sometimes you buy popcorn before going to your seat.
   - When the movie is over, you leave the theatre.
   - John went to the movies.
   - Did John buy a ticket?
2. Give five examples of facts that are difficult to repcesent and manipulate in predicate logic.
3. Suppose you had a predicate logic-based system in which you had represented the information in Figure 4.5. What additional knowledge would you have to include in order to cause properties to be inherited downward in the hierarchy? For example, how could you answer the question of how tall a pitcher is?
4. Property inheritance is a very common form of default reasoning. Consider the semantic net

   1. How could the information in this network be represented in a JTMS?
   2. What will happen when the additional fact that the platypus lays eggs is inserted into this system?