Types of Structured Knowledge Representation | Artificial Intelligence

Here information is organised into more complex knowledge structures. Slots in the structure represent attributes into which values can be placed. These values are either specific to a particular instance or default. These can capture complex situation or objects, for example, eating a meal in a restaurant or the contents of a hotel room or details of a tree in a garden. Such structures can be linked together as in networks, giving property inheritance. Frames and scripts are the most common types of structured representation.

We would now discuss two knowledge representation systems of this type:

Type # 1. Frames:

In frames representation of facts are clustered around objects rather than distributing that knowledge among smaller structures like logical formulas or production rules.

This representation supports the organization of knowledge into more complex units which reflect the organization of objects in the domain.

In a 1975 paper, Minsky describes a frame:

Here is the essence of the frame theory:

When one encounters a new situation (or makes a substantial change in one’s view of a problem) one selects from memory a structure called a “frame.” This is a remembered framework to be adapted to fit reality by changing details as necessary.

According to Minsky, a frame may be viewed as a static data structure used to represent well-understood stereotyped situations. Frame like structures seem to organize our own knowledge of the world. We adjust to every new situation by calling up information structured by past experiences. We then specially fashion or revise the details of these past experiences to represent the individual differences for the new situation.

Anyone who has stayed in one or two hotel rooms has no trouble with entirely new hotels and their rooms. One expects to see a bed, a bathroom, a place to open a suitcase, a telephone, price and emergency evacuation information on the back of the door, and so on. The details of each room can be supplied when needed, colour of the curtains, location and use of light switches, etc.

There is also default information supplied with the hotel room frame: no sheets; call housekeeping; need ice; look down the hall; and so on. We do not need to build up our understanding for each new hotel room we enter. All of the pieces of a generic hotel room are organized into a conceptual structure that we access when checking into a hotel; the particulars of an individual room are supplied as needed.

We could represent these higher-level structures directly in a semantic network by organizing it as a collection of separate networks, each of which represent some stereotypic situation. Frames, as well as object-Oriented systems, provide us with a vehicle for this organization, representing entities as structured objects with named slots and attached values. Thus a frame or schema is seen as a single complex entity.

For example, the hotel room and its components can be described by a number of individual frames. In addition to the bed, a frame could represent a chair: expected height is 20 to 40 cm. number of legs is 4, a default value, is designed for sitting.

A further frame represents the hotel telephone: this is a specialization of a (land line) phone except that billing is through the room, there is a special hotel operator (default), and a person is able to use the hotel phone to get meals served in the room, make outside calls, and to receive other services. Fig. 6.22 gives a frame representing the hotel room.

Each individual frame may be seen as a data structure, similar in many respects to the traditional “record,” which contains information relevant to stereotyped entities.

The slots in the frame contain information such as:

1. Frame Identification Information.

2. Relationship of this Frame to Other Frames:

The “hotel phone” might be a special instance of “phone,” which might be an instance of a “communication device.”

3. Requirements for a Frame:

A chair, for instance, has its seat between 20 and 40 cm from the floor, its back higher than 60 cm, etc. These requirements may be used to determine when new objects fit the stereotype defined by the frame.

4. Procedural Information on Use of the Structure Described:

An important feature of frames is the ability to attach procedural code to a slot.

5. Frame Default Information:

These are slot values which are taken to be true when no evidence to the contrary has been found. For instance, chairs have four legs, telephones are pushbutton, or hotel beds are made by the staff.

6. New Instance Information:

Many frame slots may be left unspecified until given a value for a particular instance or when they are needed for some aspect of problem solving. For example, the colour of the bedspread may be left unspecified.

Frames extend semantic networks in a number of important ways. Although the frame description of hotel beds. Fig. 6.22, might be equivalent to a network description, the frame version makes it much clearer that we are describing a bed with its various attributes. In the network version, there is simply a collection of nodes and we depend more on our interpretation of the structure to see the hotel bed as the primary object being described. This ability to organize our knowledge into such structures is an important attribute of a knowledge base.

Frames make it easier to organize our knowledge hierarchically. In a network, every concept is represented by nodes and links at the same level of specification. Very often, however, we may like to think of an object as a single entity for some purposes and only consider details of its internal structure for other purposes. For example, we usually are not aware of the mechanical organization of a car until something breaks down; only then do we pull up our “car engine schema” and try to find the problem.

Procedural attachment is an important feature of frames because it supports the linking of specific pieces of code to appropriate entities in the frame representation. For example, we might want to include the ability to generate graphic images in a knowledge base. A graphics language is more appropriate for this than network language.

We use procedural attachment to create demons. A demon is a procedure which is invoked as a side effect of some other action in the knowledge base. For example, we may wish the system to perform type checks or to run consistency tests whenever a certain slot value is changed.

Frame systems support class inheritance which is more time efficient. The slots and default value of a class frame are inherited across the class/subclass and class/member hierarchy.

For instance, a hotel phone could be a subclass of a regular phone except that:

(1) All out-of-building dialing goes through the hotel switchboard (for billing) and

(2) Hotel services may be dialed directly.

Default values are assigned to selected slots to be used only if other information is not available: assume that hotel rooms have beds and are, therefore, appropriate places to go if you want to sleep; if you don’t know how to dial the hotel front desk try “zero,” the phone may be assumed (no evidence to the contrary) to be push button.

When an instance of the class frame is created, the system will attempt to fill its slots, either by querying the user, accepting the default value from the class frame or executing some procedure or demon to obtain the instance value. As with semantic nets, slots and default values are inherited across a class/subclass hierarchy. Of course, default information can cause the data description of the problem to be non-monotonic, letting us make assumption about default values which may not always prove correct.

Minsky’s own work on vision provides an example of frames and their use in default reasoning: the problem of recognizing that different views of an object actually represent the same object. For example, the three perspectives of the one cube of Fig. 6.23. actually look quite different. Minsky (1975) proposed a frame system which recognizes these as views of a single object by inferring the hidden sides as default assumptions.

The frame system of Fig. 6.23 represents four of the faces of a cube, a particular face is out of view from that perspective. The links between the frames indicate the relations between the views represented by the frames. The nodes, of course, could be more complex if there were colours or patterns which the faces contained. Indeed, each slot in one frame could be a pointer to another entire frame. Also, because given information can fill a number of different slots face E in Fig. 6.23, there need be no redundancy in the information which is stored.

Frames add to the power of semantic nets by allowing complex objects to be represented as a single frame, rather than as a large network structure. This also provides a very natural way to represent stereotypic entities, classes, inheritance, and default values.

Although frames, like logical and network representations, are a powerful tool, many of the problems of acquiring and organizing a complicated knowledge base must still be solved by the programmer’s, skill intuition. Finally, this MIT research of the 1970s as well as similar work at Xerox Palo Alto Research Center, led to the “object-oriented” programming design philosophy as well as building important implementation languages including Smalltalk, Java, C++ and ultimately CLOS.

A frame can also be described as a tree whose root is labelled by its name. The first level of the tree is that of attributes (slots), the second of facets, the third that of values.

The slots are divided into several categories:

(a) The Inherent Slots:

These are comparable with the recording field of the data and hence are characteristic of the knowledge under consideration. There is a difference, however. Since these can exist outside of their recording they can have one or more values, but also procedures associated with them. These slots are specified by the use for each class, and the values are given during the instantiating of this class to obtain an object.

(b) The Meta-Slots:

These are defined for the classes, and often have only one value, being related to the given class (these are not inherited). Such an attribute is the ako (a kind of) link mentioned in the semantic networks, which relates one class to a more general class (machine).

Each class is related by ako to at least one other class. There exists exactly one class ‘linked’ to itself, which is the vertex of the graph of ako links. The slot ako determines one of the fundamental interests of the object representation: inheritance. At the level of instanced frames, it allows, by default, a frame to inherit certain values of the classes to which it is bound (related) by ako. If this frame is bound to several others, there can be multiple inheritance (the value of ako is a set of frames).

(c) The Instantiated Slots:

These are defined for the objects which are instances of classes. As priori, their creation is automatic during instantiating, since they are ascribed to the instantiated class.

Each slot possesses an arbitrary number of facets. These are the declarations or procedures associated to the attributes.

We shall describe some of these which are currently being used:

(i) The Facet Value:

This is the simplest facet. It assigns one or more values to the father slot. For example, for the frame ‘man’ the slot ‘activities’ has a facet value which can have computer science, music, sport etc.

(ii) The Facet Default:

As the name indicates, this assigns one or more values by default to the corresponding slot when the facet value does not do so. For example, for the frame “Man” and slot ‘temperature’, if the value is not specified, the value 37°C is assigned by default.

(iii) The Demons:

The demons arc procedures which are activated at anytime during a program execution depending on conditions evaluated in demon itself.

Examples of demons used in conventional programming include error detection, default commands and end of file detection (eof).

In summary frames extend semantic networks to include structured, hierarchical knowledge. Since they can be used with semantic networks, they share the benefits of these, as well characteristics of Frames.

1. Efficiency:

They allow more complex knowledge to be captured efficiently.

2. Explicitness:

The additional structures (if-needed, if-added, if-removed) make the relative importance of particular objects and concepts explicit.

3. Expressiveness:

They allow representation of structured knowledge and procedural knowledge, the additional structure increase clarity.

4. Effectiveness:

Actions or operations can be associated with a slot and performed, for example, whenever the value for that slot is changed procure get activated. Such procedures are called demons.

In programs using demons a list of demons is created and as processing proceeds, all changes of state are recorded on a list. All demons in the demon list check the status list for each change against their network fragment. If the match is made, control immediately passes to the demon.

This feature provides the key to self modifying programs which are essential for systems which can adapt to new situations and improve their performance with experience. Such dynamic behaviour is one of the central ideas of machine learning.

In the following example:

If:

In the presence of sodium hydroxide we observe a brown precipitation this precipitate is soluble in ammonia.

Then:

The solution contains silver ions.

The last element of the subset “if” is not a fact, but a procedure, namely that the system tries to prove a stated fact of that it poses a question.

This procedure is automatically triggered if the two preceding facts are recognised by the system and is called Demon.

Comparison between Semantic Net and Frames:

Semantic Networks failed to give satisfactory answer to the following Qs:-

i. What do nodes and links (arcs) stand for?

ii. Semantic Networks are logically inadequate because they could not make many of the distinctions which logic can make.

iii. Semantic Networks are heuristically inadequate because searches for information were not themselves knowledge based that is there was knowledge is in Semantic Networks which tells us how to search for the knowledge what we wanted to find.

Frames represents real world knowledge by integrating declarations about objects and events and their properties and procedural notions about how to retrieve information and achieve goals thereby overcoming some of the problems associated with semantic nets.

iv. Frames are used for default reasoning in particular, they are useful for simulation common sense knowledge.

v. Semantic Networks are basically a 2 – D representation of knowledge, while frames add a third dimension to allow the nodes (slots) to have structures. Hence Frames are very often used in computer vision.

vi. Frame based expert systems are very useful for representing causal knowledge, because their information is organised by cause and effect.

vii. By contrast rule based expert systems generally rely on unorganised knowledge which is not casual.

viii. A Semantic Networks based expert system can deal with shallow knowledge; shallowness occurs because all knowledge in semantic net is contained in nodes and links.

Type # 2. Scripts:

Scripts like frames, are a structure used to represent stereotypical situation It also contains slots which can be filled with appropriate values. However, whereas frames typically represent knowledge of objects and concepts, scripts represent knowledge of events.

They were originally proposed as a means of providing contextual information to support natural language understanding. As script is used in predicting what will happen in a certain situation even though certain events have not been observed as yet.

Consider the following description from the real life:

Arisha and Bobby, husband and wife (the two adversaries in game playing now get married) went to the super market. When they had got every thing on their list they went home.

Although it is not explicitly stated in this description we are likely to infer that Arisha and Bobby paid for their selections before leaving. We might also be able to fill in more details about their shopping trip: they had a trolley and walked around the super market, that they selected their own purchases items, that their list contained the items which they wished to buy etc. All of this and much more can be inferred from our general knowledge concerning super market and our expectations as to what is likely to happen at super market.

It is this type of stereo typical know ledge which scripts attempt to capture, with the aim of allowing a computer to make similar inferences about incomplete stories Schank and Abelson (1977), and to answer questions about stories especially the children stories. The scripts would describe likely action-sequences and thus, provide the contextual information to understand stories.

A script consists of number of elements such as:

I. Entry Conditions:

These are the conditions which must be true for the script to be activated.

II. Results:

These are the facts which are true when the script ends.

III. Props:

These are the objects which are involved in the events described in the scripts.

IV. Roles:

These are the expected actions of the major participants in the events described in the script.

V. Scenes:

These are the sequences of events which take place. The events are described following the formalism of CD (conceptual dependency).

VI. Tracks:

These represent variations on general theme or pattern represented by a particular script.

For example, consider a script for going to a super market.

The following information will be stored:

i. Entry Conditions:

Super market open, shopper needs goods, super market has goods, shopper has money.

ii. Result:

Shopper has goods, super market has less stock, super market has more money, shopper has less (or no) money.

iii. Props:

Trolleys, goods, check-our trills.

iv. Roles:

Shopper collects goods, assistant checks out goods and super market president takes money, super market manager orders new stock.

v. Scenes:

Selecting goods, checking out goods, paying for goods, packing goods.

vi. Tracks:

Assistant packs bag, customer packs bag.

Scripts have been useful in natural language understanding in restricted domains. Problems arise when the knowledge required to interpret a story is not domain specific but general “common sense” knowledge. Charnaik (1978) used children’s stories to illustrate just how much knowledge is required to interpret even simple description.

For example, consider the following event about exchanging unwanted gifts:

Arisha and Bobby, when engaged received two toasters as gifts. After marriage they decided to keep one for their use and took the other back to the shop, for exchanging it for some other house-hold item.

To interpret this we need to know about toasters, their utility etc., and why under normal circumstances, one won’t want two toasters. We also need to know about shops from which these were purchased, their normal exchange policies. Also we need to know about engagement and their tradition of giving gifts on such occasions.

Thus, the situation is more complicated than it appears. If instead of toasters Arisha and Bobby had received two gifts cheques, or two one-thousand-rupees notes in cash would they had even then exchanged them. So the rule that one does not want ‘two’ of the same thing only applies to certain items.

Such information is not specific to engagement, the same would be true of birthday presents, wedding-presents or X-mas presents. Scripts hint towards the basic problem of artificial intelligence which is how to provide the computer with the general interpretative knowledge which we extract from our experience as well as from the specific factual knowledge about a particular domain.

The between-the-lines problem is equally difficult, it is not possible to know ahead of time the possible occurrences that can break a script. For instance.

Example:

Melissa was eating dinner at her favourite restaurant when a large piece of plaster fell from the ceiling and landed on her date.

Question:

Was Melissa eating a date salad? What did she do next? Was Melissa’s date plastered? As this example illustrates, structured representations can be inflexible. Reasoning can be locked into a single script, even though this may not be appropriate.

Memory organization packets (MOPs) address the problem of script inflexibility by representing knowledge as components (MOPs) along with rules for dynamically combining them to form appropriate to the current situation. The organization of knowledge representation is particularly important to implementations of case-based reasoning, in which solver must efficiently retrieve a relevant prior problem solution from memory.

The problem of organizing and retrieving knowledge are difficult and inherent to the modeling of semantic meaning. Eugene Charniak (1972) illustrated the amount of knowledge required to understand even simple children’s stories. Consider a statement about a birthday party. “Mary was given two kites for her birthday so she took one back to the store.” We must know about the tradition of giving gifts at a party; we must know what a kite is and why Mary might not want two of them; we must know about stores and their exchange policies.

In spite of these problems, programs using scripts and other semantic representations can understand natural language in limited domains. An example of this work is a program that interprets messages coming over the news wire services. Using scripts for natural disaster, coups, or other stereotypic stories, programs have shown remarkable success in this limited but realistic domain.

In conclusion we can say that scripts are designed for representing knowledge in a particular context, within this context the method is expressive and effective (except as we have seen in representing general knowledge) but it is limited in wider applications. Similarly it provides an efficient and explicit mechanism for capturing complex structured information within limited domain.