KNOWLEDGE REPRESENTATION ISSUES.ppt

this presentation is prepared from the Rich textbook.

1. Knowledge Representation Issues

2. Introduction
•Forthepurposeofsolvingcomplexproblemsencounteredin
AI,weneedbothalargeamountofknowledgeandsome
mechanismformanipulatingthatknowledgetocreate
solutionstonewproblems.
•Avarietyofwaysofrepresentingknowledge(facts)havebeen
exploitedinAIprograms.Inallvarietyofknowledge
representations,wedealwithtwokindsofentities.
A.Facts:Truthsinsomerelevantworld.Thesearethethingswe
wanttorepresent.
B.Representationsoffactsinsomechosenformalism.theseare
thingswewillactuallybeabletomanipulate.

3. •Onewaytothinkofstructuringtheseentitiesisattwo
levels:
(a)theknowledgelevel,atwhichfactsaredescribed,and
(b)thesymbollevel,atwhichrepresentationsofobjects
attheknowledgelevelaredefinedintermsof
symbolsthatcanbemanipulatedbyprograms.
•Thefactsandrepresentationsarelinkedwithtwo-way
mappings.
•Thislinkiscalledrepresentationmappings.
•Theforwardrepresentationmappingmapsfromfacts
torepresentations.
•Thebackwardrepresentationmappinggoestheother
way,fromrepresentationstofacts.

4. •Onecommonrepresentationisnaturallanguage(particularly
English)sentences.
•Regardlessoftherepresentationforfactsweuseinaprogram
,wemayalsoneedtobeconcernedwithanEnglish
representationofthosefactsinordertofacilitategetting
informationintoandoutofthesystem.
•WeneedmappingfunctionsfromEnglishsentencestothe
representationweactuallyuseandfromitbacktosentences.

5. Representations and Mappings
•Inordertosolvecomplexproblemsencounteredinartificial
intelligence,oneneedsbothalargeamountofknowledge
andsomemechanismformanipulatingthatknowledgeto
createsolutions.
KnowledgeandRepresentationaretwodistinctentities.
Theyplaycentralbutdistinguishablerolesintheintelligent
system.
Knowledgeisadescriptionoftheworld.Itdeterminesa
system’scompetencebywhatitknows.
Moreover,Representationisthewayknowledgeis
encoded.Itdefinesasystem’sperformanceindoing
something.
Differenttypesofknowledgerequiredifferentkindsof
representation.

7. Let'slookatasimpleexampleusing
mathematicallogicastherepresentational
formalism.ConsidertheEnglishsentence:
Spot is a dog.
•ThefactrepresentedbythatEnglishsentence
canalsoberepresentedinlogicas:
dog(Spot)
•Supposethatwealsohavealogical
representationofthefactthatalldogs
havetails:
•For all x: dog(x) -> hastail{x}

8. •Then,usingthedeductivemechanismsof
logic,wemaygeneratethenew
representationobject:
hastail(Spot)
•Using an appropriate backward mapping
function, we could then generate the English
sentence:
Spot has a fail.

11. Approaches to knowledge Representation
•Representationaladequacy:-theabilitytorepresentallofthe
kindsofknowledgethatareneededinthatdomain.
•InferentialAdequacy:-theabilitytomanipulatethe
representationstructuresinsuchawayastoderivenew
structurescorrespondingtonewknowledgeinferredfromold.
•InferentialEfficiency:-theabilitytoincorporateintothe
knowledgestructureadditionalinformationthatcanbeused
tofocustheattentionoftheinferencemechanisminthemost
promisingdirections.
•AcquisitionalEfficiency:-theabilitytoacquirenew
informationeasily.Thesimplestcaseinvolvesdirectinsertion
byaperson,ofnewknowledgeintothedatabase.

12. •Simple Relational knowledge
Thesimplestwaytorepresentdeclarativefactsis
asasetofrelationsofthesamesortusedindatabase
system.
Thereasonthatthisrepresentationissimpleisthat
standingaloneitprovidesveryweakinferential
capabilitiesButknowledgerepresentedinthisform
mayserveastheinputtomorepowerfulinference
engines.

14. To answer question “Whois the heaviest
player?”
Butifaprocedureforfindingtheheaviest
playerisprovided,thenthesefactswillenable
theproceduretocomputeananswer.
If,instead,weareprovidedwithasetofrules
fordecidingwhichhittertoputupagainsta
givenpitcher(basedonright-andleft-
handedness,say),thenthissamerelationcan
provideatleastsomeoftheinformation
requiredbythoserules.

15. •Inheritable Knowledge
Structuremustbedesignedtocorrespondingto
theinferencemechanismthataredesired.
One of the most useful forms of inference is
Property inheritance
–elements inherit values from being members of a
class.
–data must be organised into a hierarchy of classes.

16. Property inheritance algorithm
•The algorithm to retrieve a value for an attribute of
an instance object:
1.Find the object in the knowledge base
2.If there is a value for the attribute report it
3.Otherwise look for a value of instance. if none, fail
4.Otherwise go to that node and find a value for the
attribute and then report it

17. 5.Otherwise search through usingisauntil a value is
found for the attribute.
a)get the value of the isaattribute and move to that
node
b)see if there is a value for the attribute ,if there is ,
report it.

19. Baseball-Player
isa: Adult-Male
bats: (EQUAL handed}
height: 6-1
batting-average: 252
Fig. 4.6 Viewing a Node as a Frame

20. team(Pee-Wee-Reese) = Brooklyn-Dodgers.
batting-average(Three-Finger Brown) = .106.
height(Pee-Wee-Reese) = 6-1.(default
inheritance)
bats(Three-Finger-Brown) = Right.

21. •Inferential Knowledge
Representsknowledgeasformallogic.Basedon
reasoningfromfactsorfromotherinferential
knowledge.Uselessunlessthereisalsoasinference
procedurethatcanexploitit.
•Procedural Knowledge (Imperative Knowledge or
operational knowledge)
-specifies what to do when.
-Procedural knowledge can be represented in
programs in many ways. The most common way is
simply as code (in some programming language such as
LISP) for doing something.

22. -The machine uses the knowledge when it
executes the code to perform a task.
-Themostcommonlyusedtechniquefor
representingproceduralknowledgeinAI
programsistheuseofproductionrules.(if–
then)

23. Issues in Knowledge Representation
•Are any attributes of objects so basic that they have
been occurred in almost every problem domain?
•Are there any important relationships that exist
among attributes of objects?
•At what level should knowledge be represented?How
should sets of objects be represented?
•How can relevant part be accessed when they are
needed?

24. Important Attributes
•There are two attributes that are of very general
significance, instanceand isa
•These attributes are important because they support
property inheritance

25. Relationships among Attributes
•Theattributesthatweusetodescribeobjectsare
themselvesentitiesthatwerepresent.
•Whatpropertiesdotheyhaveindependentofthe
specificknowledgetheyenco
•There are four such properties that deserve mention
here:
i) Inverses
ii) Existence in an isa hierarchy
iii)Techniques for reasoning about values
iv)Single-valued attributes

26. Inverses
•Entitiesintheworldarerelatedtoeachotherin
manydifferentways.
•Attributesarethoserelationships.
•Thefirstistorepresentbothrelationshipsinasingle
representationthatignoresfocus.
•Logicalrepresentationsareusuallyinterpretedas
doingthis.Forexample,theassertion:
team(Pee-Wee-Reese,Brooklyn-Dodgers)
canequallyeasilybeinterpretedasastatementabout
PeeWeeReeseorabouttheBrooklynDodgers.

27. •The second approach is to use attributes that focus
on a single entity but to use them in pairs, one the
inverse of the other.
-one associated with Pee Wee Reese:
team = Brooklyn-Dodgers
-one associated with Brooklyn Dodgers:
team-members = Pee-Wee-Reese....
This is the approach that is taken in semantic net and
frame-based systems.

28. An Isa Hierarchy ofAttributes
•generalization-specialization relationships are
important for attributes

29. Techniques for Reasoning about Values
•Sometimesvaluesofattributesarespecified
explicitlywhenaknowledgebaseiscreated.
•Severalkindsofinformationcanplayaroleinthis
reasoning,including:
-Information about the type of the value. For
example, the value of Height must be a number
measured in a unit of length.
-Constraints on the value, often stated in terms
of related entities. For example, the age of a person
cannot be greater than the age of either of that
person’s parents.

30. -Rulesforcomputingthevaluewhenitisneeded.
WeshowedanexampleofsucharuleinFig.4.5for
thebatsattribute.Theserulesarecalledbackward
rules,Suchruleshavealsobeencalledif-needed
rules,
-Rulesthatdescribeactionsthatshouldbetaken
ifavalueeverbecomesknown.Theserulesare
calledforwardrules,orsometimesif-addedrules.

31. Single-Valued Attributes
•A specific but very useful kind of attribute is one that
is guaranteed to take a unique value. For example, a
baseball player can, at any one time, have only a
single height and be a member of only one team.
•If there is already a value present for one of these
attributes and a different value is asserted, then one
of two things has happened.
•Either a change has occurred in the world or there is
now a contradiction in the knowledge base that
needs to be resolved.

32. •Knowledge-representationsystemshavetaken
severaldifferentapproachestoprovidingsupportfor
single-valuedattributes,including:
-Introduceanexplicitnotationfortemporal
interval.Iftwodifferentvaluesareeverassertedfor
thesametemporalinterval,signalacontradiction
automatically.
-Assumethattheonlytemporalintervalthatisof
interestisnow.Soifanewvalueisasserted,replace
theoldvalue.
-

33. -Providenoexplicitsupport.Logic-basedsystems
areinthiscategory.Butinthesesystems,
knowledgebasebuilderscanaddaxiomsthatstate
thatifanattributehasonevaluethenitisknownnot
tohaveallothervalues.

34. Choosing the Granularity of Representation
Regardlessoftheparticularrepresentationformalism
wechoose,itisnecessarytoanswerthequestion
“Atwhatlevelofdetailshouldtheworldbe
represented?”Anotherwaythisquestionisoften
phrasedis“Whatshouldbeourprimitives?”
Shouldtherebeasmallnumberoflow-levelonesor
shouldtherebeatargetnumbercoveringarangeof
granularities?

35. •Suppose we are interested in the following fact:
John spotted Sue.
•We could represent this as!
spotted(agent(John),
object(Sue})
•Such a representation would makeit easy to answer
questions suchas:
Who spotted Sue?
•But now suppose we want to know:
Did John see Sue?

36. •The obvious answer is “yes,” but given only the one
fact we have, we cannot discover that answer.
•We could, of course, add other facts, such as
spotted(x, y) -> saw(x, y)
•We could then infer the answer to the question.
•Analternativesolutiontothisproblemisto
representthefactthatspottingisreallyaspecial
typeofseeingexplicitlyintherepresentationofthe
fact.Wemightwritesomethingsuchas
saw(agent(John),object(Sue),timespan(briefly)})

37. •Inthisrepresentation,wehavebrokentheideaof
spottingapartintomoreprimitiveconceptsofseeing
andtimespan.
•Usingthisrepresentation,thefactthatJohnsawSue
isimmediatelyaccessible.Butthefactthathe
spottedherismoredifficulttogetto.

38. •Themajoradvantageofconvertingallstatements
intoarepresentationintermsofasmallsetof
primitivesisthattherulesthatareusedtoderive
inferencesfromthatknowledgeneedbewrittenonly
intermsoftheprimitivesratherthanintermsofthe
manywaysinwhichtheknowledgemayoriginally
haveappeared.

39. •There are several arguments against the use of low-
level primitives.
i)simplehigh-levelfactsmayrequirealotof
storagewhenbrokendownintoprimitives.Muchof
thatstorageisreallywastedsincethelow-level
renditionofaparticularhigh-levelconceptwill
appearmanytimes,onceforeachtimethehigh-level
conceptisreferenced.

41. ii)ifknowledgeisinitiallypresentedtothe
systeminarelativelyhigh-levelform,suchasEnglish,
thensubstantialworkmustbedonetoreducethe
knowledgeintoprimitiveform.
iii)Inmanydomains,itisnotatallclearwhatthe
primitivesshouldbe.Andevenindomainsinwhich
theremaybeanobvioussetofprimitives,theremay
notbeenoughinformationpresentineachuseof
thehigh-levelconstructstoenablethemtobe
convertedintotheirprimitivecomponents.

42. •choosingthecorrectgranularityofrepresentationfor
aparticularbodyofknowledgeisnoteasy.
•Clearly,thelowerthelevelwechoose,theless
inferencerequiredtoreasonwithitinsomecases,
butthemoreconferencerequiredtocreatethe
representationfromEnglishandthemoreroomit
takestostore,sincemanyinferenceswillbe
representedmanytimes.
•Theanswerforanyparticulartaskdomainmust
cometoalargeextentfromthedomainitself—to
whatuseistheknowledgetobeput?

43. Representing Sets of Objects
•It is important to be able to represent sets of objects
for several reasons.
•One is that there are some properties that are true
of sets that are not true of the individual members of
a set. As examples, consider the assertions that are
being made in the sentences “There are more sheep
than people in Australia” and “English speakers
can be found all over the world.”

44. •The only way to represent the facts described in
these sentences is to attach assertions to the sets
representing people, sheep, and English speakers,
since, for example, no single English speaker can be
found al! over the world.
•Theotherreasonthatitisimportanttobeableto
representsetsofobjectsisthatifapropertyistrue
ofall(orevenmost)elementsofaset,thenitismore
efficienttoassociateitoncewiththesetratherthan
toassociateitexplicitlywitheveryelementofthe
set.

45. •There are three obvious ways in which sets may be
represented.
•The simplest is just by a name.
•There are two ways to state a definition of a set and
its elements.
•The first is to list the members. Such a specification is
called an extensional definition.
•The second is to provide a rule that, when a
particular object is evaluated, returns true or false
depending on whether the object is in the set or not.
Such a rule is called an intensional definition.

46. Ex:
•an extensional description of the set of our
sun’s planets on which people live is {Earth}.
•An intensional description is
{x : sun-planet(x) /\human-inhabited(x)}

47. •Intensionalrepresentationshavetwoimportant
propertiesthatextensionaloneslack,
•however.Thefirstisthattheycanbeusedto
describeinfinitesetsandsetsnotallofwhose
elementsareexplicitlyknown.
•Thuswecandescribeintensionallysuchsetsas
primenumbers(ofwhichthereareinfinitelymany)
orkingsofEngland(eventhoughwedonotknow
whoallofthemareorevenhowmanyofthemthere
havebeen).

48. •Thesecondthingwecandowithintensional
descriptionsistoallowthemtodependon
parametersthatcanchange,suchastimeorspatial
location.Ifwedothat,thentheactualsetthatis
representedbythedescriptionwillchangeasa
functionofthevalueofthoseparameters.

49. •To see the effect of this, consider the sentence, “The
president of the United States used to be a Democrat,”
uttered when the currentpresident is a Republican.
•This sentence can mean two things.
-The first is that the specific person who is now president was
once a Democrat. This meaning can be captured
straightforwardly with an extensional representation of “the
president of the United States.”
We just specify the individual, But there is a second meaning,
namely that there was once someone who was the president
and who was a Democrat.

50. •To represent the meaning of ‘‘the president of the
United States” given this interpretation requires
an intensional description that depends on time.
•Thus we might write president(t), where
president is some function that maps instances of
time onto instances of people, namely U.S.
presidents.

51. Finding the Right Structures as Needed
•For example, suppose we have a script (a description
of a class of events in terms of contexts, participants,
and subevents) that describes the typical sequence
of events in a restaurant. This script would enable us
to take a text such as
John went to Steak and Ale last night. He ordered a
large rare steak, paid his bill, and left.
and answer ‘‘yes” to the question
Did John eat dinner last night?

52. •NoticethatnowhereinthestorywasJohn’seating
anythingmentionedexplicitly.Butthefactthatwhen
onegoestoarestaurantoneeatswillbecontained
intherestaurantscript.
•Ifweknowinadvancetousetherestaurantscript,
thenwecananswerthequestioneasily.
•Butinordertobeabletoreasonaboutavarietyof
things,asystemmusthavemanyscriptsfor
everythingfromgoingtoworktosailingaroundthe
world.
•Howwillitselecttheappropriateoneeachtime?For
example,nowhereinourstorywastheword
“restaurant”mentioned.

53. •Infact,inordertohaveaccesstotherightstructure
fordescribingaparticularsituation,itisnecessaryto
solveallofthefollowingproblems.*
a)Howtoperformaninitialselectionofthemost
appropriatestructure,
b)Howtofillinappropriatedetailsfromthecurrent
situation.
c)Howtofindabetterstructureiftheonechosen
initiallyturnsoutnottobeappropriate.

54. d)Whattodoifnoneoftheavailable
structuresisappropriate.
e)Whentocreateandrememberanew
structure.

55. Selecting an initial structure
•Selectingcandidateknowledgestructurestomatcha
particularproblem-solvingsituationisahard
problem:
•Thereareseveralwaysinwhichitcanbedone.Three
importantapproachesarethefollowing:
-Indexthestructuresdirectlybythesignificant
Englishwordsthatcanbeusedtodescribethem.
For example, let each verb have associated
with it a structure that describes its meaning. This is
the approach taken in conceptual dependency theory.

56. For example, the word “fly” has a different meaning in
each of the following sentences:
JohnflewtoNewYork.(Herodeinaplanefrom
oneplacetoanother.)
Johnflewakite.(Heheldakitethatwasupinthe
air.)
Johnflewdownthestreet.(Hemovedvery
rapidly.)
Johnflewintoarage.(Anidiom)
•Anotherproblemwiththisapproachisthatitisonly
usefulwhenthereisanEnglishdescriptionofthe
problemtobesolved.

57. -Consider each major concept as a pointer
to all of the structures (such as scripts} in which
it might be involved, This may produce several
sets of prospective structures.
For example, the concept Steak might
point to two scripts, one for restaurant and
one for supermarket. The concept Bill might
point to a restaurant and a shopping script.
Take the intersection of those sets to get
the structure(s}, preferably precisely one, that
involves all the content words.

58. •One important problem with this method is that if
the problem description contains any even slightly
extraneous concepts, then the intersection of their
associated structures will be empty.
Ex:“JohnrodehisbicycletoSteakandAlelast
night.”
•Anotherproblemisthatitmayrequireagreatdeal
ofcomputationtocomputeallofthepossibilitysets
andthentointersectthem.However,ifcomputing
suchsetsandintersectingthemcouldbedonein
parallel,thenthetimerequiredtoproducean
answerwouldbereasonableevenifthetotal
numberofcomputationsislarge.

59. -Locate one major clue in the problem
description and use it to select an initial structure.
•Asothercluesappear,usethemtorefinetheinitial
selectionortomakeacompletelynewoneif
necessary.Foradiscussionofthisapproach,see
Charniak[1978].
•Themajorproblemwiththismethodisthatinsome
situationsthereisnotaneasilyidentifiablemajor
clue.
•Asecondproblemisthatitisnecessarytoanticipate
whichcluesaregoingtobeimportantandwhichare
not.Buttherelativeimportanceofcluescanchange
dramaticallyfromonesituationtoanother.

60. Revising the Choice When Necessary
•Once we find a candidate knowledge
structure, we must attempt to do a detailed
match of it to the problem at hand.
•Depending on the representation we are
using, the details of the matching process will
vary.
•It may require variables to be bound to
objects. It may require attributes to have their
values compared.

61. •Inanycase,ifvaluesthatsatisfytherequired
restrictionsasimposedbytheknowledgestructure
canbefound,theyareputintotheappropriate
placesinthestructure.Ifnoappropriatevaluescan
befound,thenanewstructuremustbeselected.
•Thereareavarietyofthingsthatcanbedone:
1.Selectthefragmentsofthecurrentstructurethat
docorrespondtothesituationandmatchthemagainst
candidatealternatives.Choosethebestmatch.
Ifthecurrentstructurewasatallclosetobeing
appropriate,muchoftheworkthathasbeendoneto
buildsub-structurestofitintoitwillbepreserved.

62. 2.Makeanexcuseforthecurrentstructure’s
failureandcontinuetouseit.Forexample,aproposed
chairwithonlythreelegsmightsimplybebroken.Or
theremightbeanotherobjectinfrontofitwhich
occludesoneleg.
Partofthestructureshouldcontaininformation
aboutthefeaturesforwhichitisacceptabletomake
excuses.
Also,therearegeneralheuristics,suchasthefact
thatastructureismorelikelytobeappropriateifa
desiredfeatureismissing(perhapsbecauseitishidden
fromview)thanifaninappropriatefeatureispresent.
Forexample,apersonwithonelegismoreplausible
thanapersonwithatail.

63. 3.Refer to specific stored links between
structures to suggest new directions in which to
explore.Referfig.4.11

64. 4.Iftheknowledgestructuresarestoredinanisa
hierarchy,traverseupwardinituntilastructureis
foundthatissufficientlygeneralthatitdoesnet
conflictwiththeevidence.Eitherusethisstructureifit
isspecificenoughtoprovidetherequiredknowledgeor
considercreatinganewstructurejustbelowthe
matchingone.

65. THE FRAME PROBLEM
•Sofarinthischapter,wehaveseenseveralmethods
forrepresentingknowledgethatwouldallowusto
formcomplexstatedescriptionsforasearch
program,Anotherissueconcernshowtorepresent
efficientlysequencesofproblemstatesthatarise
fromasearchprocess.
•Forcomplexill-structuredproblems,thiscanbea
seriousmatter.

66. •Consider the world of a household robot, There are
many objects and relationships in the world, and a
state description must somehow include facts like
on(Plant!2, Table34), under(Table34, Window13),
and in(Table34,Room 15).
•One strategy is to store each state description as a
list of such facts.
•Butwhathappensduringtheproblem-solving
processifeachofthosedescriptionsisverylong?
•Mostofthefactswillnotchangefromonestateto
another,yeteachfactwillberepresentedonceat
everynode,andwewillquicklyrunoutofmemory.

67. •Furthermore,wewillspendthemajorityofourtime
creatingthesenodesandcopyingthesefacts—most
ofwhichdonotchangeoften—fromonenodeto
another.Forexample,intherobotworld,wecould
spendlotoftimerecordingabove(Ceiling,Floor)at
everynode.
•AIIofthisis,ofcourse,inadditiontotherea!
Problemoffiguringoutwhichfactsshouldbe
differentateachnode.

68. •Thiswholeproblemofrepresentingthefactsthat
changeaswellasthosethatdonotisknownasthe
frameproblem[McCarthyandHayes,1969].
•Insomedomains,theonlyhardpartisrepresenting
allthefacts.
•Inothers,though,figuringoutwhichoneschangeis
nontrivial.
•Forexample,intherobotworld,theremightbea
tablewithaplantonitunderthewindow.Suppose
wemovethetabletothecentreoftheroom.
•Wemustalsoinferthattheplantisnowinthecentre
oftheroomtoobutthatthewindowisnot.

69. •Tosupportthiskindofreasoning,somesystems
makeuseofanexplicitsetofaxiomscalledframe
axioms,whichdescribeallthethingsthatdonot
changewhenaparticularoperatorisappliedinstate
ntoproducestaten+1.
•Thus, in the robot domain, we might write axioms
such as
color(x,y, s
1,;) ˄ move(x, s
1, s
2) ->color(x,y, s
2)
•“If x has colory in state s, and the operation of
moving x is applied in state s, to produce state
s3, then the colorof x in 5, is still y.”

70. •Buthowdoweknowwhatchangesintheproblem
statedescriptionneedtobeundone?
•Forexample,whatdowehavetochangetoundothe
effectofmovingthetabletothecentreoftheroom?
•Therearetwowaysthisproblemcanbesolved:

71. -Donotmodifytheinitialstatedescriptionatall.
•Ateachnode,storeanindicationofthespecific
changesthatshouldbemadeatthisnode.
•Wheneveritisnecessarytorefertothedescription
ofthecurrentproblemstate,lookattheinitialstate
descriptionandalsolookbackthroughallthenodes
onthepathfromthestartstatetothecurrentstate.
Thisiswhatwedidinoursolutiontothecrypt-
arithmeticprobleminSection3.5.
•Thisapproachmakesbacktrackingveryeasy,butit
makesreferringtothestatedescriptionfairly
complex.

72. -Modifytheinitialstatedescriptionas
appropriate,butalsorecordateachnodeanindication
ofwhatto
dotoundothemoveshoulditeverbenecessaryto
backtrackthroughthenode.
Then,wheneveritisnecessarytobacktrack,
checkeachnodealongthewayandperformthe
indicatedoperationsonthestatedescription.