Ch 7 Knowledge Representation.pdf

Chapter 7 Knowledge Representation from Saroj Kaushik's AI book.

1. Ch7 Knowledge Representation

Knowledge representation (KR) is an important issue in
both cognitive science and artificial intelligence.
−
Incognitivescience,itisconcernedwiththewaypeoplestoreand
processinformationand
−
Inartificialintelligence(AI),mainfocusistostoreknowledgesothat
programscanprocessitandachievehumanintelligence.

There are different ways of representing knowledge e.g.
−
predicatelogic,
−
semanticnetworks,
−
extendedsemanticnet,
−
frames,
−
conceptualdependencyetc.

In predicate logic, knowledge is represented in the form of
rules and facts as is done in Prolog.
1

2. Knowledge Representation

In AI, knowledge representation is an important area
because intelligent problem solving can be achieved
and simplified choosing an appropriate KR
technique.

Representing knowledge in some specific ways
makes certain problems easier to solve.

Since knowledge is utilized to achieve intelligent
behaviour, the fundamental goal of KR is to
represent knowledge in a manner that facilitates the
process of inferencing (i.e., drawing conclusions)
from it.
2

3. Knowledge Representation

Any KR system should possess properties such as
learning, efficiency in acquisition, representational
adequacy and inferential adequacy.

Learning: by reasoning, by experience, by observation
and scientific methods.

Efficiency in acquisition: the ability to acquire new
knowledge through automatic methods without human
intervention.

Representational adequacy: the ability to represent the
required knowledge.

Inferential adequacy: the ability to infer new knowledge.
3

4. Approaches to KR

Relational Knowledge
–Database systems

Logic
–PL
–FOL

Procedural Knowledge
–Knowledge encoded in the form of procedures that carry
out specific tasks based on relevant knowledge.
•Compilers
•Interpreters
4

5. Inheritable knowledge

Having already seen logic as a knowledge
representation in chapter 4, we will now see
inheritable knowledge representation mechanisms.
–Semantic Networks
–Extended Semantic Networks
–Frames

Also known as structured knowledge representation.
5

6. Semantic Networks

The basic idea behind semantic networks is that the
meaning of a concept is derived from its relationship
with other concepts, and the information is stored by
interconnecting nodes with labeled arcs.

Inheritance in Semantic Net:
–Hierarchical structure allows knowledge to be stored at
the highest possible level of abstraction -reducing size.
–In-built inheritance mechanism.
–It is a natural tool for representing taxonomically
structured information -sub-concepts of a concept share
common properties.
6

7. Semantic Networks

The syntax of semantic net is simple. It is a network of
labeled nodes and links.
–It’sadirectedgraphwithnodescorrespondingtoconcepts,
facts,objectsetc.and
–arcsshowingrelationorassociationbetweentwoconcepts.

The commonly used links in semantic net are of the
following types.
–isasubclassofentity(e.g.,childhospitalissubclassof
hospital)
–instparticularinstanceofaclass(e.g.,Indiaisaninstance
ofcountry)
–proppropertylink(e.g.,propertyofdogis‘bark)
7

8. Representation of Knowledge in Sem
Net

“Everyhuman,animalandbirdisalivingthing
whobreathesandeats.Allbirdscanfly.Allmen
andwomenarehumanswhohavetwolegs.John
isaman.Catisananimalandhasfur.Allanimals
haveskinandcanmove.Giraffeisananimalwho
istallandhaslonglegs.Parrotisabirdandis
greenincolor”.
8

9. Representation in Semantic Net

Semantic Net
breathe, eat
Living_thing prop
isa isa
two legs isa fly
Human Animal Bird
isa isa isa isa isa
prop green
Man Woman Giraffe Cat Parrot
prop prop prop
inst fur
john skin, move tall, long legs


9

10. Another example
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.
10
inst
inst
inst
inst

11. More examples
11

12. More examples
12
john 5Sue
age
mother
34
age
father
Max
age

13. Semantic networks

It is argued that this form of representation is closer
to the way humans structure knowledge by building
mental links between things than the predicate logic
we considered earlier.

Note in particular how all the information about a
particular object is concentrated on the node
representing that object, rather than scattered around
several clauses in logic.
13

14. Inheritance

Inheritancemechanismallowsknowledgetobestoredat
thehighestpossiblelevelofabstractionwhichreducesthe
sizeofknowledgebase.
–
Itfacilitatesinferencingofinformationassociatedwith
semanticnets.
–
Itisanaturaltoolforrepresentingtaxonomicallystructured
informationandensuresthatallthemembersandsub-
conceptsofaconceptsharecommonproperties.
–
Italsohelpsustomaintaintheconsistencyofthe
knowledgebasebyaddingnewconceptsandmembersof
existingones.

Propertiesattachedtoaparticularobject(class)aretobe
inheritedbyallsubclassesandmembersofthatclass.
14

15. Property Inheritance Algorithm
Input:Object, and property to be found from Semantic Net;
Output:Yes, if the object has the desired property else return
No;
Procedure:
Find the object in the semantic net;
Found = false;
While [ (object ≠ root) AND not Found ] DO
{If there is a property attribute attached with an object
then Found = true
else if object=inst(object, class) OR isa(object, class)
then object = class};
If Found = true then Report ‘Yes’ else report ‘No’;
15

16. Inheritance
Bird
Canary
Is-a
Yellow
Tweetyyes Sylvesterinst
can-talk?
has-enemy
has-color
feathers
body-covering
Does Tweety have feathers? Yes.
How do we know? He inherits that property
from a superior node in the hierarchy.
16

17. Inheritance
Can Opus fly? No.
How do we know? He inherits that property
from its closest node in the hierarchy.
Bird
Flightless bird
is-a
Penguin
Opus
is-a
inst
fly
has-property
can’t fly
has-propertyCanary
is-a
17

18. Assigned attributes
Can Dumbo fly? Yes.
How do we know? Local (assigned) attribute
overrides inherited attribute
Animal
Mammal
is-a
Elephant
Dumbo
is-a
inst
can move
has-property
can’t fly
has-propertyBird
is-a
has-property
can fly
18

19. Coding of Semantic Net in
Prolog
Isa facts Instance facts Property facts

isa(living_thing, nil).
isa(human, living_thing).
isa(animals, living_thing).
isa(birds, living_thing).
isa(man, human ).
isa(woman, human).
isa(cat, animal).
isa(giraffe, animal)
isa(parrot, bird)
inst(john, man).


prop(breathe, living_thing).
prop(eat, living_thing).
prop(two_legs, human).
prop(skin, animal).
prop(move, animal).
prop(fur, bird).
prop(tall, giraffe).
prop(long_legs, giraffe).
prop(green, parrot).


19

20. Inheritance Rules in Prolog
Instance rules:
instance(X, Y):-inst(X, Y).
instance (X, Y):-inst(X, Z), subclass(Z,Y).
Subclass rules:
subclass(X, Y):-isa(X, Y).
subclass(X, Y):-isa(X, Z), subclass(Z, Y) .
Property rules:
property(X, Y):-prop(X, Y).
property(X, Y) :-instance(Y, Z), property(X, Z).
property(X, Y) :-subclass(Y, Z), property(X, Z).
20

21. Queries
●
Is john human?
●
Is parrot a living thing?
●
Is giraffe an aimal?
●
Is woman subclassof
living thing
●
Does parrot fly?
●
Does john breathe?
●
has parrot fur?
●
Does cat fly?
?-instance(john, humans). Y
?-subclass(parrot, living_thing). Y
?-subclass(giraffe, animal).Y
?-subclass(woman, living_thing).
Y
?-property(fly, parrot).Y
?-property (john, breathe).Y
?-property(fur, parrot).N
?-property(fly, cat). N
21

22. Advantages of Semantic nets

Easy to visualize

Formal definitions of semantic networks have been
developed.

Related knowledge is easily clustered.

Efficient in space requirements
–Objects represented only once
–Relationships handled by pointers
22

23. Problems with semantic nets

There is no standard definition of link and node names. This
makes it difficult to understand the network, and whether or
not it is designed in a consistent manner.

Initially, semantic nets were proposed as a model of human
associative memory (Quillian, 1968). But, are they an
adequate model? It is believed that human brain contains
about 10
10
neurons, and 10
15
links. Consider how long it takes
for a human to answer “NO” to a query “Are there trees on
the moon?” Obviously, humans process information in a very
different way, not as suggested by the proponents of semantic
networks.
23

24. Problems with semantic nets …

Semantic nets are logically and heuristically very
weak. Statements such as “Some books are more
interesting than others”, “No book is available on this
subject”, “If a fiction book is requested, do not
consider books on history, health and mathematics”
cannot be represented in a semantic network.

In general, semantic networks cannot represent
–negation"John does not go fishing";
–disjunction"John eats pizza or fish and chips";
–clauses
24

25. 25
Exercises

Try to represent the following two sentences into the
appropriate semantic network diagram:
–isa(person, mammal)
–instance(Mike-Hall, person)all in one graph
–team(Mike-Hall, Cardiff)
–score(Spurs, Norwich, 3-1)
–John gave Mary the book.
–John gave Mary the bookin the kitchen.

26. Extended Semantic Network

In conventional Semantic Networks, clausal form of logic cannot
be expressed.

Easy to add information to Semantic Networks (not so in logic).

Extended Semantic Network (ESNet) combines the advantages of
both logic and semantic network.

In the ESNet, terms are represented by nodes similar to semantic
networks.

Binary predicate symbols in clausal logic are represented by labels
on arcs of ESNet.
−
Anatomoftheform“Love(john,mary)”isanarclabeledas
‘Love’withitstwoendnodesrepresenting‘john’and‘mary’.

Conclusions and conditions in clausal form are represented by
different kinds of arcs.
–Conditions are drawn with two lines (or ) and
conclusions are drawn with one heavy line .
26

27. Examples
Represent‘grandfather’definition
Gfather(X,Y)Father(X,Z),Parent(Z,Y)
inESNet.
Z
Father Parent

X Y
Gfather


27

28. Another Example
Representclausalrule
“Male(X),Female(X)Human(X)”
usingbinaryrepresentationas“Isa(X,male),Isa(X,female)
Isa(X,human)”andsubsequentlyinESNetasfollows: male
Isa Isa
X human
Isa
female
28

29. Inference Rulesin ESNet

Inference rules are embedded in the representation
itself.

The inference that “for every action of giving, there
is an action of taking” in clausal logic written as
“Action(f(E),take)Action(E,give)”.
29
ESNet
Action
F(E) take

Action
E give

30. Inference Rulesin ESNet

The inference rule such as “an actor of taking action is also
the recipient of the action” can be easily represented in
clausal logic as:
Recipient(E,Y)Action(E,take),Actor(E,Y)
−
HereEisavariablerepresentinganeventwhereanactionoftaking
ishappening.
30
ESNet Action
E take
Recipient
Actor


Y

31. Example

Represent the following clauses of Logic in ESNet.
Recipient(E, Y) Acton(E, take), Actor(E, Y)
Object(e, apple).
Action(e, take).
Actor(e, john) .
31
apple

Object
e E Recipient
Actor Action Actor
Action

john take Y

32. Contradiction

The contradiction in the ESNet arises if we have the
following situation.
32

Part_of
P X

Isa
Part_of
Y

33. Deduction in ESNet

Both of the following inference mechanisms are available in
ESNet.
–Forwardreasoninginference(bottomupapproach)
•BottomUpInferencing:GivenanESNet,applythe
followingreductionusingmodusponensruleoflogic
(if{B,AB}thenA).
–Backwardreasoninginference(topdownapproach).
•TopDownInferencing:Proveaconclusionfroma
givenESNetbyaddingthedenialoftheconclusionto
thenetworkandshowthattheresultingsetofclauses
inthenetworkisinconsistent(usingresolution).
33

34. Example: forward reasoning

Given set of clauses

Isa(X, human)  Isa(X, man)
Isa(john, man).
Inferencing

Isa(john, human)


human
Isa

X
Isa

man

john Isa

Here X is bound to john



human


Isa


john





34

35. Example: backward reasoning

Given set of clauses

Isa(X, human)  Isa(X, man)
Isa(john, man).
Prove conclusion

Query: Isa(john, human)
denial of query


human
Isa

X
Isa

man

john Isa


human
Isa

X
Isa Isa

man

john Isa

35

36. Cont…



human X = john
Isa

Isa

john


Contradiction or Empty network is
generated. Hence “Isa(john, human)”
is proved.

36

37. Elaborated Example

We illustrate the forward reasoning and backward
reasoning in Extended Semantic Networks using the
following information.
–Every man is a human.
–Every human is animate.
–Every animate thing is a living thing.
–John is a man.

This can be represented in FOL as clauses
human(X) man(X)
animate(X) human(X)
living_thing(X) animate(X)
man(john)
37

38. Elaborated Example -ESNet
38
isa(X, living_thing) isa(X, animate)
isa(X, animate) isa(X, human)
isa(X, human) isa(X, man)
isa(john, man)
living_thing X
animate
john man
isa
isa
isa
isa
isa
isa
X1
X2
human
isa

39. Forward Reasoning in Esnet
39
living_thing X
animate
john man
isa
isa
isa
isa
isa
isa
X1
X2
human
isa
X2 = John

40. Forward Reasoning in Esnet
40
living_thing X
animate
isa
isa
isa
isa
X1
john
human
isa
X1 = John

41. Forward Reasoning in Esnet
41
living_thing X
animate
john
isa
isa
isa
X = John
john
isa
living_thing

42. Backward Reasoning (textbook)
42
living_thing
animate
john man
isa
isa
isa
isa
isa
isa
X1
X2
human
isa
denial
X2 = John
X

43. Backward Reasoning …
43
living_thing
animate
john
isa
isa
isa
isa
X1
human
isa
X1 = John
X

44. Backward Reasoning …
44
living_thing
animate
isa
isa
isa
X = John
X
john
johnliving_thing
isa
isa
Contradiction!!

45. Backward Reasoning –a better way
45
living_thing
animate
john man
isa
isa
isa
isa
isa
isa
X1
X2
human
isa
denial
X = John
X

46. Backward Reasoning …
46
animate
john man
isa
isa
isa
isa
isa
X1
X2
human
X1 = John

47. Backward Reasoning …
47
john man
isa
isa
isa
X2
human
X2 = John

48. Backward Reasoning …
48
john man
isa
isa
Contradiction!!

49. Elaborated Example 2

John gives an apple to Mike.

John likes an apple.

Anyone who gives away anything he likes must like
the person he gives it to.

Represented in FOL as clauses:
action(e, give)
actor(e, john)
recipient(e, mike)
object(e, apple)
likes(john, apple)
likes(X, Z) action(E, give), actor(E, X), recipient(E, Z),
object(E, Y), likes(X, Y)
49

50. Elaborated Example 2 –
forward reasoning
50
X = john
Y = apple
likes likes
give
likes
E
e
apple john mike
Y X Z

51. Elaborated Example 2 –
forward reasoning
51
E = e
Z = mike
give
E
e
apple john
mike
Z

52. Forward Reasoning in Esnet
52
john mike
E = e; Z = mike
likes

53. Backward Reasoning in Esnet
53
likes likes
give
likes
E
e
apple john mike
Y X Z
likes
X = john
Z = mike

54. Backward Reasoning in Esnet
54
likes
give
E
e
apple
john
mike
Y
Y = apple

55. Backward Reasoning in Esnet
55
give
E
e
apple
john
mike
For E = e, we get an empty clause.

56. Inheritance in ESnets
56
living_thing X
animate
john man
isa
isa
isa
isa
isa
isa
X1
X2
human
isa
part_of
two_legs
isa(X, living_thing) isa(X, animate)
isa(X, animate) isa(X, human)
isa(X, human) isa(X, man)
isa(john, man)
part_of(two_legs, human)

57. Inheritance in ESnets
57
living_thing X
animate
john man
isa
isa
isa
isa
isa
isa
X1
X2
human
isa
part_of
two_legs
denial
part_of
X2 = john

58. Inheritance in ESnets
58
living_thing X
animate
john
isa
isa
isa
isa
X1
human
isa
part_of
two_legs
part_of
contradiction

59. Ch7 Knowledge Representation

Semantic Networks
–Graphical representation (easy to visualise)
–In-built inheritance
–Easy to add new information
–Cannot represent
•Negation
•Disjunction

Extended Semantic Networks
–Extend semantic networks with clauses to get best of both
semantic networks and logic (handling negation and
disjunction).
59

60. Ch7 homework
Draw a semantic networkrepresenting:

Every vehicle is a physical object. Every car is a
vehicle. Every car has four wheels. Electrical system
is a part of car. Battery is a part of electrical system.
Pollution system is a part of every vehicle. Vehicle
is used for transportation. Suzuki is a car.

Every living thing needs oxygen to live. Every
human is a living thing. John is human.
–Answer the query whether John is a living thing and john
needs oxygen to live using inheritance.
60

61. Ch7 homework
Draw an extended semantic networkrepresenting:

Teachers who works hard are liked by students. May is a hard
working teacher. John is a student. Therefore, John likes Mary.

Everyone who sees a movie in a theatre has to buy a ticket. A
person who does not have money cannot buy a ticket. John sees
a movie. Therefore, John had money.

All senior citizens and politicians get air concession. Mary is a
senior citizen. John does not get air concession. Therefore, May
gets air concession and John is neither senior citizen nor
politician.

Every member of ROA is either retired or an officer. John is a
member of ROA. Therefore, John is either retired or an officer.
61