Knowledge Representation

KNOWLEDGE REPRESENTATION1

Gagan Deep Kaur Course – Artificial Intelligence Course Code – CSS 344 Roll No. 07408802

Knowledge Representation is the area in Artificial Intelligence that is concerned with how knowledge about the world can be represented and what kind of reasoning can be done with that knowledge. Since knowledge pre-requisite for intelligent behavior, the fundamental goal of KR is to represent knowledge in such a way that inferencing (deriving conclusion) could be achieved easily. Knowledge Representation is thus the study of how to enable a formal symbol system to represent a particular domain alongwith inference mechanism for reasoning about that domain. Major issues that are involved in any such representation are: 1. What is the nature of knowledge and how do people represent it? 2. Should a representation scheme be particular or general purpose? 3. How to represent the changing world in representation scheme, i.e. should the scheme be monotonic (static) or non-monotonic (dynamic) 4. At what level should knowledge be represented, i.e. what should be our primitives? Are there any fundamental primitives in whom all knowledge could be decomposed? E.g. If Ram feeds a Dog, then it could be represented as Feeds(Ram, Dog) If Ram gives the bone to dog, then it could be represented at Gives(Ram, dog, bone) Are both same? Perhaps not, because nowhere it has been mentioned explicitly that feeding constitutes giving food to an animal. To make them equivalent, we need an inference mechanism like give(x, food) -> feed(x). Based on the issues, there are 4 properties that any good system of knowledge representation ought to possess: 1. Representational Adequacy – the ability to represent the required knowledge in a particular domain 2. Inferential Adequacy – the ability to manipulate the represented knowledge to produce new knowledge, corresponding to that inferred from the original 3. Inferential Efficiency – the ability to direct the inference mechanism to most productive directions by storing appropriate guides. 1

This assignment is based on Elaine Rich’s “Artificial Intelligence” Part-2 – Knowledge Representation, Chapters 5-7 alongwith my own inputs, as I have understood these. For achieving clarity, however, various other sources were consulted.

1

4. Acquisitional Efficiency – the ability to acquire new knowledge in the existing database. Though, no single system optimizes all of these properties, there are various approaches to KR that can optimize some of these. Approaches to Knowledge Representation

Simple Relational

Inheritable 1. Predicate Logic 2. Conceptual Dependency 3. Semantic Net 4. Script Slot and Filler Structures 5. Frame

Simple Relational is one of the simplest ways to represent declarative facts, as in table, but having very less inference power. For example, City Information can be recorded as Place Pune Ratnagiri Vadodara Palanpur

Nature City Town City Town

State Maharashtra Maharashtra Gujarat Gujarat

Population 72 Lakh 70 thousand 16 Lakh 1 Lakh

Inheritable structures, on the other hand, have more robust inference mechanism in the form of Property Inheritance. Since relational knowledge consists of a attributes and their corresponding values, the structure is just extended by allowing inference mechanism like property inheritance. In property inheritance, the elements inherit values from being members of a class and data is organized in class-hierarchy. Above information can now be represented as: Population Geographical Area 70 Lakh

Place

City

Pune 2

In such a structure, boxed nodes are objects and valued of attributes of objects. Arrows point from object to its value. Such a structure is called slot and filler structure. The two attributes of Property Inheritance are ISA and INSTANCE. They represent class membership and class inclusion and that class inclusion is transitive. That is, if PUNE ISA CITY and CITY ISA PLACE, then it must also be the case that PUNE ISA PLACE. According to the approaches, there are thus two methods of knowledge representation in AI – Declarative and Procedural. Predicate Logic is one of the methods to represent declarative facts. Inference can be made in predicate logic by just showing that a statement logically follows from another statement. The merit of logical representation is that it provides a good way to do reasoning with the knowledge to be represented by providing a way of deducing new statements from the old ones. Though ISA and INSTANCE predicates are not used explicitly in predicate logic, the relationship they represent, i.e property inheritance, is captured fully. E.g instance(pune, city). The proof procedure in logic is given by Resolution which produces proofs by refutation. In other words, to prove a statement, resolution tries to show that the negation of the statement produces a contradiction with the known statement. In Predicate Logic, similar process is given by unification algorithm. The only problem with resolution is that we often lose valuable heuristic information that is contained in the original representation of facts. Further, people do not always think in resolution. Thus, it is difficult for a person to interact with a resolution theorem prover, for example, either to advice or get advised by it. Predicate logic duly captures static facts, but with facts that are changing over the time, are not duly captured by it. Further facts like representing degrees of heat/certainty for example, or heuristic information like “It is always useful to have something up on one’s sleeve in a game” or different belief systems like “Ram believes that Sham might have gone to the class.” To handle such problems, following techniques may prove useful: 1. Non-monotonic Reasoning - which allows which allows statements to be deleted from and added to the database and also, allows the belief in one statement to rest on a lack of belief in some other one. 2. Probabilistic Reasoning - which makes it possible to represent likely but uncertain inferences. Non-monotonic Reasoning Non-monotonic systems thus allow the statements to be added and deleted from the knowledge base unlike traditional systems based on predicate logic in which number of true systems keeps on adding to the database and neither statement cause a previously known or proven statement to be invalid. A reasoning systems is called monotonic if it derives new true facts from known facts. In these systems, the number of facts is

3

monotonically increasing over time. These systems are not adequate in situations where knowledge is incomplete or not definite. For example: If X is a dog, then X is a mammal If we add the assertion that Pluto is a dog Then, the following fact will be added: Pluto is a mammal But later on if we come to know that Pluto is a dog is not true, then what to do with the assertion Pluto is a mammal? And with other derived facts? This situation is called non-monotonic. Other types of non-monotonic reasoning are ‘the most probable choice’, ‘default reasoning’ etc. Thus, a way to overcome this situation is use of beliefs (or assumptions) i.e. hypothetical assertions on the domain which are not completely supported by evidence but are not in contrast with what is already known. From a belief, we can derive a new fact in a normal way, but if a contradiction arises, we have to be able to retract it, and to perform all the adequate bookkeeping needed. Thus, a reasoning system based on beliefs and able to manage contradictions is called nonmonotonic. TMS are practical examples of non-monotonic systems whose main functions are storing inferences, allowing assumption-based reasoning, and managing inconsistencies. But, main problem with TMS are representation of beliefs and their dependencies, identification of beliefs responsible for contradiction, and retraction of beliefs. For example, we wish to solve the problem of finding clothes to wear in the morning. 2 Using following facts, a TMS style database is made and is shown how the solution changes with relevant facts (such as time of year or dirtiness of jeans) change: 1. 2. 3. 4. 5.

Wear jeans unless either they are dirty or you have a job interview today Wear a sweater if it is cold It is usually cold in winter Wear sandals if it is warm It is usually warm in the summer

TMS style database is:

2

This question occurs in the book, chapter 6.5, Exercise No. 4, Page 198

4

Node N1

Assertion If ~dirty(jeans) and ~inter(job) Then wear(jeans)

Justification (SL ( ) ( ) )

N2 N3 N4

dirty(jeans) inter(job) If weather(cold) Then wear(sweater) ~weather(cold) If weather(warm) Then wear(sandals) ~weather(warm) It is usually cold in winter It is usually warm in summer

nil nil (SL ( ) (N5) )

N5 N6 N7 N8 N9

Comment assumption

nil (SL (N5) (N7) ) nil (SL (N7) (N5) ) (SL (N5) (N7) )

Now, the problem solver checks the rules, and encounters for example Rule 14 N10

If ….., then ~dirty(jeans) ~dirty(jeans)

Rule 15 N11 N12

If …. Then, ~inter(job) leads to ~inter(job) (SL (15) (N3) ) wear(jeans) (SL (N1, N8, N9) (N2,N3) )

Rule 16 N13 N14

If…. Then weather(cold) leads to weather(cold) (SL (16, N7, N8) justified (N5) ) wear(sweater) (SL (N4, N13) (N5) )

Rule 17 N15 N16

If…. Then weather(warm) leads to weather(warm) (SL (17, N8, N5) (N7) ) justified wear(jeans) (SL (N6, N15) (N7) )

(SL (14) (N2) )

justified justified justified

For example, it is found that N10

dirty(jeans)

(SL (14) (N2) )

Then a contradiction is found. TMS now creates a node N10

Contradiction

(SL (N2) (N1) )

5

justified

DDB procedure is invoked now. N1 being an assumption, fact is recorded by Nogood node N11 N12

Nogood-1 dirty(jeans)

(CP (N2, N1) ( ) ) (SL (N11) ( ) )

justified

Though non-monotonic systems are clearly advantageous but these are harder to deal with because it is often necessary, when one statement is deleted from the knowledge base, to go back over other statements whose proofs depend on the deleted statements and either eliminate them or find new proofs that are valid with respect to the current knowledge base. Thus, to propagate changes in the database, it is important to store with each theorem, its proof, or at least the list of other statements on which the proof depends. This requires more storage space than monotonic systems as in them, once the proof is found, it need never re-examined. Conceptual Dependency It is used to represent knowledge from natural language input. Its aim is to help drawing inference and remain independent of the words used in the original input, i.e. for any two or more sentences that are identical in meaning there should be only one representation of that meaning. CD provides a structure in to which nodes representing information can be placed alongwith a specific set of primitives. Primitive Acts of CD theory are: ATRANS - Transfer of an abstract relationship. e.g. give. PTRANS - Transfer of the physical location of an object. e.g. go. PROPEL - Application of a physical force to an object. e.g. push. MTRANS - Transfer of mental information. e.g. tell. MBUILD - Construct new information from old. e.g. decide. SPEAK - Utter a sound. e.g. say. etc. …….. Six primitive conceptual categories provide building blocks which are the set of allowable dependencies in the concepts in a sentence: PP - Real world objects. PA - Attributes of objects. T - Times.

ACT - Real world actions. AA - Attributes of actions. LOC - Locations.

The problem arises as to how to connect these two together? For example, in the sentences, John gives Mary a book (occurring in book) From R John

ATRANS

Book

6

To

Mary John

Arrows indicate the direction of dependency. Letters above indicate certain relationships: o - object. R - recipient-donor. I - instrument e.g. eat with a spoon. D - destination e.g. going home Double arrows ( ) indicate two-way links between the actor (PP) and action (ACT). The actions are built from the set of Primitive Acts. These can be modified by tense etc. like p - past , f - future , t - transition etc. The advantage of CD representation is that, using these primitives involves fewer inference rules. Many inference rules are already represented in CD structure. But, its disadvantage is that knowledge must be decomposed into fairly low level primitives and many a times, it is impossible or difficult to find correct set of primitives. A lot of inference may still be required. Representations can be complex even for relatively simple actions. For example, Ram suspects that Sham must have lost his bet on the winning of lottery. Complex representations require a lot of storage. Semantic Networks Semantic networks is a knowledge representation technique which represents semantic relations between the concepts. It is a directed or undirected graph consisting of vertices, which represent concepts, and edges. The two primitives in semantic nets are nodes and links (arcs). Links are unidirectional connection between the nodes. Nodes corresponds to objects or classes of objects whereas links corresponds to relationship between these nodes. For example, Mammal

Dog

isa has_part

head

instance Kutt There are two methods to infer anything in a semantic network. These are, Intersection Search which is a notion that spreading activation out of two nodes and finding their intersection finds relationship among objects. And Inheritance, i.e. ISA and INSTANCE. In inferences we need to distinguish between the link that defines a new entity and the link that relates two existing entities. To deal with the problem of handling quantification in semantic nets, partitioning of semantic nets was done. It is to partition the semantic net into a hierarchical set of spaces, each of which corresponds to the scope of one or more 7

variables. Partitioned Semantic Nets allow for propositions to be made without commitment to truth and expressions to be quantified. Its basic idea is to Break network into spaces consisting of groups of nodes and links and regard each space as a node. Frames Frames are typically used to represent stereotypical knowledge. When a new situation is encountered, or considerable changes are made in existing views of people, a remembered structure called frame is recalled from the memory which is adapted to fit reality according to the situation. Frame provides a complete framework with default values and can be arranged in a hierarchy. The default values are slot values that are taken to be true when no evidence to the contrary has been found. For example, chair has 4 legs etc. However, some frame slots may be left unspecified until given value for a particular instance or when they are needed for some aspect of problem solving. E.g. color of the table may be left unspecified. Frames organize knowledge into structures. Frames are recalled on as-need basis and duly support class inheritance. Frames thus extend semantic networks by providing organization and structure. Frames are essentially defined by their relationships with other frames. Relationships between frames are represented using slots. Ram - Uma Ganesh

Ramesh

The frame describing Ram would consist of Ram: Relationships

Frame(x), for example Sex: Male Spouse: Uma Values for Relationships Children: Ganesh, Ramesh

where sex, spouse, and child are slot values. This simple tree would have at least six frames, describing the following individuals: Ram, Uma, Ganesh, Ramesh, Male and Female. Scripts Script is another knowledge representation technique for describing a stereotyped sequence of events in a particular context. Scripts are used because real world events follow stereotypical patterns. Humans can use previous experiences to understand verbal accounts, computers can use scripts. Also because, people when relating events leave a large amount of assumed detail out of their accounts. People don’t find it easy to converse with a system that can’t fill in missing conversational detail. Scripts predict unobserved events. Scripts can form a coherent account from disjoint conversations. As 8

compared to Scripts, a frame is a relatively large chunk of knowledge about a particular object, even, location, situation, or other element. The frame describes the object in great detail (each frame for one detail). Script, on the other hand, is a knowledge representation scheme that instead of describing an object, describes a sequence of events. For that, it uses a series of slots containing information about the people, objects and actions that are involved in the events. Components of scripts Entry conditions – the entry conditions that must be satisfied before events in this script can be occurred. Props – objects that are used in the sequence of events that occur Roles – people involved in the script Scenes – the actual sequence of events that occur. Tracks – variations that might occur in a script. Result – conditions that exist after the events in the script have occurred. For example, a restaurant script (example occurring in book) has Entry conditions – X is hungry. X has money. Track – coffee shop Props – table, menu, food, check, money Roles – customer, waiter, cook, cashier, owner Scene1 – entering the restaurant Scene2 – ordering from the menu…. Scene.n Results – customer has less money. Customer pays. Customer is pleased (and so on).

9