Module-5

Knowledge Representation

By,

Mr. Manjunatha P B

Asst. Professor

Department of AI & ML, BIT

Introduction

2

▶ Discussed Problem solving techniques :Search graphs of Solution paths, Predicate logic for storing knowledge and inferenceing new knowledge while solving problems requiring concepts of AI.

▶ Knowledge Representation is important in cognitive science & AI.

• In cognitive science, it is concerned with the way in which information is stored and processed by humans, while in AI, the main focus is on storing knowledge or information in such a manner that programs can process it and achieve human intelligence.

• Any knowledge representation

system should possess properties such as learning, efficiency in acquisition,

representational adequacy, and inferential adequacy.

Introduction

3

▶ Learning: Refers to a capability that acquires new knowledge, behaviors, understanding etc.,

▶ It adds new classified information to avoid redundancy and replication in the existing knowledge prior to storage to enable easy retrieval.

▶ Efficiency in acquisition: Refers to ability to acquire new knowledge using automatic methods wherever possible rather than relying on human intervention.

▶ Representational adequacy: Refers to ability to represent the

required knowledge.

▶ Inferential adequacy: Refers to the ability of manipulating knowledge to produce new knowledge from existing one.

Introduction

4

▶ KR is the core component of a number of applications such as expert systems, Machine Translation Systems, Computer aided maintenance systems, information retrieval systems & DB front ends.

▶ In expert systems- Using predicate logic( in the from of rules & Facts), semantic networks, frames, conceptual dependency etc., Knowledge is represented.

▶ Knowledge representation Techniques:

1. Semantic Networks,
2. Extended Semantic net and frame systems

Approaches to Knowledge representation

5

▶ AI programs use structures known as Knowledge structures to represent Objects,facts,relationshps & Procedures.

▶ The main objective is to provide information so that program

can operate in intelligent way.

▶ Knowledge structures composed of both traditional & complex structures such as semantic work, frames, scripts etc.,

▶ Knowledge base is a special type of data base that holds knowledge of that domain and share functions such as storing, updating and retrieving information.

▶ They are organized in hierarchical structures with in–built

inheritance & inferencing capabilities.

Approaches to Knowledge representation

6

• Relational Knowledge: Relational knowledge comprises

objects consisting of attributes and associated values.

• The simplest way of storing facts is to use a relational method. In this method, each fact is stored in a row of a relational table as done in relational database.

Approaches to Knowledge representation

7

• Knowledge Represented as Logic: Inferential capability can be achieved if knowledge is represented in the form of formal logic.

Eg: knowledge regarding mortality such as All humans are mortal can not be represented using relational approach.

• It can be represented in predicate logic as (ⱯX) human(X)🡨mortal(X)

🡪The advantage of this approach are that we can represent a set of rules, derive more facts, truths and verify the correctness of new statements.

Eg: If we have fact John is human, then we can infer that John is mortal.

Approaches to Knowledge representation

8

• Procedural Knowledge: Procedural knowledge is encoded in the form of procedures which carry out specific tasks based on relevant knowledge.

Eg: An interpreter for a PL interprets a program on the basis of available knowledge (Syntax and semantic of the language).

• Advantage of this approach are that domain specific

knowledge can be easily represented.

Knowledge representation using Semantic Network

9

• The basic idea applied behind using a semantic network is that the meaning of a concept is derived from its relationship with other concepts, and that, the information is stored by interconnecting nodes with labelled arcs.

Eg: Every human, animal and bird are living things who can breath and eat.A cat has fur and is an animal. All animals have skin and can move. A giraffe is an animal and has long legs and is tall. A parrot is a bird and is green in color. John is a human.

• Such knowledge is represented using a structure called a semantic network(semantic net).
• It is represented in a graphical notation where nodes represent concept/Objects and arcs represent relation between two concepts.

Knowledge representation using Semantic Network

10

• It’s a directed graph consisting of vertices representing concepts & edges that represent semantic relations between the concepts.
• In the figure, concepts/objects related to each other by certain relations.
• Relations are represented by bold directed links.
• Isa: This relation connects two classes, where one concept is a

kind or subclass of the other concept.

Eg: Man is a human i.e Man is a sub class of the human class.

• Inst: This relation relates specific members of a class, such as

john is an instance of Man.

Knowledge representation using Semantic Network

11

Knowledge representation using Semantic Network

12

• Other relations {can,has,colour,height} are known as Property relation.
• They have been represented by dotted lines pointing to the

concept to its property.

• Property inheritance is easily achieved.

Eg: Querry-Does a parrot breath? Can be easily answered as ‘Yes’ even though this property is not associated directly with parrot.

Knowledge representation using Semantic Network

13

Knowledge representation using Semantic Network

14

• The semantic net interpreter can not understand all the attribute links unless their semantics are encoded on it.
• Since all the attributes of the class are the properties, prop link

is the name of the relations.

• In the diagram Square nodes represents concepts/objects connected with isa or inst links. Oval node represent property attributes attached to square nodes.

Knowledge representation using Semantic Network

15

• Inheritance in Semantic Net:

of knowledge representation allows

• Hierarchical structure knowledge to be

stored at the highest possible level of

abstraction which reduces the size of the knowledge base.

• Since semantic net is stored as hierachical structure, the inheritence mechanism is in-built and facilitates inferencing of information associated with nodes in semantic net.
• It is a natural tool for representing taxonomically structured information and sub-concepts of a concept share common properties.

Property Inheritance algorithm

16

Input: Object and property to be found from semantic net:

Output: Returns yes, if the object has a desired property else returns false.

Procedure:

▶ Find an object in the semantic net:

▶ Found=false

▶ while [(object ≠ root)] DO

{

If there is an attribute attached with an Object then found=true:

else {object = isa(object,class) or object=inst(object,class)}

}:

▶ If found=true then report ‘Yes’ else report ‘No’;

Inheritance in Semantic Network-Prolog facts

17

• Prolog language is used representing an entire semantic structure in

the form of facts and inheritance rules.

• Inheritance is achieved by unification of appropriate arguments

Inheritance rules in Prolog

18

• Instance rules:-
• instance(X,Y)
• instacnce(X,Y)

:- inst(X,Y)

:- inst(X,Z), subclass(Z,Y)

• Subclass rules
• subclass(X,Y)
• Subclass(X,Y)

:- isa(X,Y)

:- isa(X,Z), subclass(Z,Y)

• Property rules
• property(X,Y)
• property(X,Y)
• Property(X,Y)

:- prop(X,Y)

:- instance(Y,Z),property(X,Z)

:- subclass(Y,Z), property(X,Z)

Various queries for Inheritance Program

19

Semantic Nets

20

▶ Consider the data

▶ Tom is a cat.

▶ Tom caught a bird.

▶ Tom is owned by John.

▶ Tom is ginger in colour.

▶ Cats like cream.

▶ The cat sat on the mat.

▶ A cat is a mammal.

▶ A bird is an animal.

▶ All mammals are animals.

▶ Mammals have fur

Semantic Nets

21

Extended Semantic Networks for KR

4/20/20219:21 AM

22

▶ Two formalism that can be used for Knowledge representation are

Logic, semantic networks.

▶ Semantic network is represented as a directed graph whose nodes represent concepts/objects and arcs represent relationships between concepts /objects.

▶ Eg: Represent in semantic network the English sentences John gives an apple to mike and John and mike are human .

Extended Semantic Networks for KR

23

▶ ‘E’ represents an event which is an act of giving, whose actor is ‘John’,

the object is an apple and recipient is mike.

▶ Semantic net can hold semantic information about situation such as actor of an event giving is john and object is apple, in the sentence John gives an apple to mike.

▶ The relationship in the network can be expressed in clasual form of logic as follows :

object(E,apple)

Action(E,give)

Actor(E,John) Recipient(E,mike) Isa(john,human) Isa(mike,human)

Extended Semantic Networks for KR

24

▶ Predicate relations corresponding to labels on the arcs of semantic

networks always have two arguments.

▶ The entire semantic net can be coded using binary representation (2 arguments representation) .

▶ In first order predicate logic, predicate relation can have n arguments ,

where n >=1

Eg: John gives an apple to mike is represented in predicate logic by give( john,mike,apple) which has 3 arguments and give is predicate relation.

▶ Predicate logic representation has greater advantages

Eg: John gives an apple to everyone he likes can be expressed as

give(john,X,apple)🡨(john,X)

where X is a variable representing any

individual. 🡨 implied by, LHS=conclusion and RHS contains conditions.

Extended Semantic Networks for KR

25

▶ It is not convenient to add an n-array representation of predicate

logic.

▶ Eg: if we have 3-array relationship give(John,mike,apple) representing John gives an apple to mike and suppose additional information kitchen is added in the sentence John gives an apple to mike in the kitchen, then replace the 3-ary representation.

give(john,mike,apple) by 4-ary representation

give(john,mike,apple,kitchen)

Eg: If john gives something he likes to a person, then he also likes that

person can be expressed in clasual representation as

Likes(John,X)🡨give(john,X,Y),likes(john,Y)

▶ The sentence every human is either male or female can be expressed as

Male(X),female(X)🡨human(X)

Extended Semantic Networks for KR

26

▶ In conventional semantic network, we cannot express clausal

form of logic.

▶ To overcome this short coming, R.Kowalski and his colleagues(1979) proposed an extended semantic network(ESNet) that combines the advantages of both logic & semantic networks.

▶ ESNet has same expressive power as that of predicate logic with well defined semantics, inference rules, and a procedural interpretations.

▶ It incorporates the advantages of using binary relation as in semantic network than n-ary relations of logic.

▶ ESNet is a much powerful representation as compared to logic & Semantic network.

Extended Semantic Networks for KR

27

▶ Binary predicate symbols in clausal logic are represented by

labels on arcs of ESNet.

▶ An atom of the form love(john,mary) is an arc labelled as love

with its two end nodes representing john and mary.

▶ The direction of the arc(link) indicates the order of the

arguments of the predicate symbol.

love

john mary

▶ Conclusions(Positive atoms) are represented with continuous arrow lines called Assertion links(🡪).

▶ Conditions(Negative atoms) are represented with dotted arrow lines called denial link(------->)

Extended Semantic Networks for KR

28

Eg: Clausal representation

grandfather(X,Y)🡨father(X,Z),parent(Z,Y) for grandfather in logic can be represented in ESNet. X& Y are variables,

grandfather(X,Y) is the consequent(conclusion), father(X,Z) and parent(Z,Y) are antecedents(Conditions)

Extended Semantic Networks for KR

29

Eg: Clausal rule male(X),female(X)🡨 human(X) can be

represented using binary representation as

isa(X,male),isa(X,female)🡨isa(X,human)

▶ ESNet representation is shown below

Inference Rules

30

▶ Inference rules are embedded in the representation itself.

▶ The representation of the inference for every action of giving, there is an action of taking in clausal logic is

action(f(X),take)🡨action(X,give)

▶ The interpretation of this rule is that event of taking action is a function of the event of giving action.

▶ In ESNet representation ,functional terms, such as f(X), are represented by a single node.

▶ The representation of the statement in ESNet

action(f(X),take)🡨action(X,give)

Inference Rules

31

▶ The inference rule that an actor who perform taking action is also the recipient of this action & can be represented in clausal logic. E is the variable representing an event of an action of taking.

recipient(E,X)🡨action(E,take),actor(E,X)

Inference Rules

32

▶ Represent the following clause in ESNet recipient(E,X) 🡨 action(E,take),actor(E,X) Object(e,apple), action(e,take), actor(e,John)

Solution: ‘E’ is a variable of some event and ‘e’ is an actual event.

Inference Rules

33

▶ Partition is shown in the figure to delimit the clause pictorially

by enclosing the clausal rule in an ellipse.

▶ The hierarchy links isa, inst and part_of are shown as special case in ESNet.

▶ Part-of link has a hidden existential quantifier.

Eg: Assertion every human has two legs could be represented using part_of link.

part_of

two_legs human

Interpretation is that for every human, there exist two legs which are part of that human.

Inference Rules

34

▶ In the figure, P part_of X is conclusion and P part_of Y is

condition, where Y is linked with X via isa link.

▶ Such kind of representation is contradictory and hence is a contradiction in ESNet.

Deduction in Extended Semantic Networks

35

• In logic there are two types of inference mechanism
• Forward reasoning inference mechanism(bottom-up approach).
• Backward reasoning inference mechanism(top-down approach).

​

Forward Reasoning Inference:

▶ FRI in clausal logic derives new assertion from old ones, start with given assertions and derive new assertions using clausal rule.

• Given an ESNet, apply the reduction(resolution) using modus ponen rule of logic {i.e given(A🡨B) and B, then conclude A}

Eg: Consider set of clauses: isa(X,human) 🡨isa(X,man)

isa(john,man)

Forward Reasoning Inference

36

• Using modus ponen rule of logic, we can easily derive that

isa(john,human) holds true.

• Let us derive or inference isa(john,human) using ESNet representation.

Forward Reasoning Inference

37

• The new assertion isa(john,human) is inferred by elimination of assertion and their denial links with the help of appropriate substitution.
• isa(X,human) is a assertion link and isa(X,man) is a denial link.
• In a rectangular box the contradiction is enclosed.

Backward Reasoning Inference

38

• Prove the query from set of clauses using resolution refutation

method in clausal logic.

• Conclusion or goal from a given ESNet is proved by adding the denial of the conclusion to the network and show that the resulting set of clauses in the network gives contradiction.
• This is done by performing successive steps of resolution until an explicit contradiction is generated.

Eg: Prove isa(john,human) using ESNet given the set of clauses

represented in clausal form.

Backward Reasoning Inference

39

Backward Reasoning Inference

40

• After adding denial link in ESNet, the reduction in ESNet is shown below by elimination of assertion and their denial link with the help of appropriate substitution.

Examples illustrating Inference Methods

41

• Consider the example, represented in clausal form

🡨 isa(x,animate)

🡨 isa(X,human)

🡨isa(X,man)

isa(X,living_thing) isa(X,animate) isa(X,human) isa(john,man)

▶ Illustrate both inferencing methods for the ESNet representation

▶ John is a living_thing can be derived by binding X with John.

Examples illustrating Inference Methods

42

Forward Reasoning Inference Method

43

▶ Infer john is animate. The assertion john is a living_thing can

be inferred as follows.

Forward Reasoning Inference Method

44

Forward Reasoning Inference Method

45

Backward Reasoning Inference Method

46

▶ Prove a query isa(john,living_thing).

▶ Add a denial of the fact that John is not a living_thing in ESNet .

▶ Check whether inconsistency or an empty network can be

derived.

▶ Each part shows the reduction in the network by the elimination of assertions and their denial links with the help of appropriate substitutions.

▶ Denial links are enclosed in rectangular box to distinguish it

from rest network.

▶ Dotted lines are denial links, continuous lines are assertion links.

▶ These are removed after substitution of actual value of a variable.

Backward Reasoning Inference Method

47

Backward Reasoning Inference Method

48

Solving query isa(john,living_thing)

49

Example

50

▶ The sentences ‘Anyone who gives something he likes to a person likes that person also, John gives an apple to Mike, John likes an apple’ can be expressed in both binary clausal form and ESNet representation.

▶ Clausal Representation of the sentence can be written as

likes(X,Z)🡨action(E,give),object(E,Y),actor(E,X),recipient(E,Z),likes(X,Y) action(e,give)

object(e,apple)

actor(e,john) recipient(e,mike) likes(john,apple)

• E is a variable which will be bound to an event ‘e’ in the process of resolution.

51

ESNet representation

▶ Prove likes(john,mike) using both Forward & Backward reasoning inference

Forward Reasoning Inference

52

▶ To get the desired assertions, reduce the network by resolving clauses. Eliminate assertion and its corresponding denial with likes links by unifying Y=apple & X=John

▶

Forward Reasoning Inference

53

▶ The reduced network can be further reduced to the following conclusion by unifying E=e and Z=mike.

E=e , Z=mike

likes

john --------------------------🡪mike

​

​

▶ Link likes between john and mike is deduced after eliminating all links which are assertions and denials.

Eg: action(e,give) is an assertion and action(E,give) is a denial, which is a contradiction and is hence eliminated.

Backward Reasoning Inference

54

▶ To prove likes(john,mike), add the denial link to the network and try to reduce the network to empty.

▶ The denial link is

▶ The reduction of the network is shown step by step.

▶ Denial link is enclosed in rectangular box.

Backward Reasoning Inference

55

Backward Reasoning Inference

56

Backward Reasoning Inference

57

Inheritance

58

▶ In a conventional Semantic network, lower level nodes in isa hierarchy inherit properties from higher level nodes unless the properties are redefined in the node itself.

🡨 isa(x,animate)

🡨 isa(X,human)

🡨isa(X,man)

isa(X,living_thing) isa(X,animate) isa(X,human) isa(john,man)

▶ Show that John inherits the property of having two_legs from human.

ESNet for Inheritance

59

Addition of denial link to the network

60

Obtaining a Contradiction

61

Knowledge representation using Frames

62

▶ The knowledge representation using frames was introduced by Marvin Minsky(1975).

▶ Frames are extension to semantic nets.

▶ Each node of a semantic net is represented by a frame.

▶ A frame is a data structure consists of a collection of attributes or slots and associated values that describe an entity.

▶ There are several types of information attached to each frame.

▶ Frames are similar to concept of class in object oriented paradigm.

▶ Frames consists of attributes or slots.

Knowledge representation using Frames

63

▶ Slots are described with attribute value

pairs<slot_name,value> .

▶ Slots are complex structures that have filters describing their properties.

▶ The value of the slot can be a text string, constant or an integer or it may be another frame or contain methods.

Knowledge representation using Frames

64

Knowledge representation using Frames

65

▶ Frame may contain as many <slots-filter> pairs as required to describe

an object. Each slot may contain one or more facets given below

Knowledge representation using Frames

66

▶ Frame may contain as many <slots-filter> pairs as required to describe

an object. Each slot may contain one or more facets given below

Knowledge representation using Frames

Example: Hospital Frame

67

Knowledge representation using Frames

68

• Frames in a network of frames are connected using links.
• aka: This class connects two class frames, one of which is a kind of the other class.

Eg: The class child hospital is a kind of class hospital.

• A class may define its own slots and also inherit slot_value pair from its super class.
• Inst: This link connects a particular instance frame to a class frame.

Eg: AIIMS is an instance of the class frame hospital. An

instance class possesses the same structure as its class frame.

• Part_of: This class connects two class frames one of which is contained in the other class.

Eg: ward is part_of class hospital.

Frame Description

69

• Hospital Frame( Root of the network)

Frame Description-Continued..

70

• Child Hospital Frame

• Heart Hospital Frame

​

• Lab Frame

Frame Description-Continued..

71

• Ward Frame

• Doctor Frame

​

• Pathology Frame

Frame Description-Continued..

72

• X_Ray Frame

• Orthopaedic ward frame

Frame Instance Description

73

• Hospital Frame Instance

Frame Instance Description

74

• Lab Frame Instance

• Pathology Frame Instance

Frame Instance Description

75

• Child Hospital Frame Instance

• Heart Hospital Frame Instance

76

A simple frame System for the class ‘hospital’

⮚