Knowledge-Representation-and-Reasoning-Villanova-University-维拉诺瓦大学知识表示与推理

KnowledgeRepresentationandReasoningFocusonSections10.1-10.3,10.6GuestLecturer:EricEatonUniversityofMarylandBaltimoreCountyLockheedMartinAdvancedTechnologyLaboratoriesAdaptedfromslidesbyTimFininandMariedesJardins.SomematerialadoptedfromnotesbyAndreasGeyer-Schulz,andChuckDyer.1OutlineApproachestoknowledgerepresentationSituationcalculusDeductive/logicalmethodsForward-chainingproductionrulesystemsSemanticnetworksFrame-basedsystemsDescriptionlogicsAbductive/uncertainmethodsWhat’sabduction?Whydoweneeduncertainty?BayesianreasoningOthermethods:Defaultreasoning,rule-basedmethods,Dempster-Shafertheory,fuzzyreasoning2IntroductionRealknowledgerepresentationandreasoningsystemscomeinseveralmajorvarieties.Thesedifferintheirintendeduse,expressivity,features,…SomemajorfamiliesareLogicprogramminglanguagesTheoremproversRule-basedorproductionsystemsSemanticnetworksFrame-basedrepresentationlanguagesDatabases(deductive,relational,object-oriented,etc.)ConstraintreasoningsystemsDescriptionlogicsBayesiannetworksEvidentialreasoning3OntologicalEngineeringStructuringknowledgeinausefulfashionAnontologyformallyrepresentsconceptsinadomainandrelationshipsbetweenthoseconceptsUsingtheproperrepresentationiskey!ItcanbethedifferencebetweensuccessandfailureOftencostlytoformallyengineerdomainknowledgeDomainexperts(a.k.a.subjectmatterexperts)Commercialontology,e.g.Cyc(cyc/,/)4RepresentingchangeRepresentingchangeintheworldinlogiccanbetricky.OnewayisjusttochangetheKBAddanddeletesentencesfromtheKBtoreflectchangesHowdowerememberthepast,orreasonaboutchanges?SituationcalculusisanotherwayAsituationisasnapshotoftheworldatsomeinstantintimeWhentheagentperformsanactionAinsituationS1,theresultisanewsituationS2.5Situations6SituationcalculusAsituationisasnapshotoftheworldatanintervaloftimeduringwhichnothingchangesEverytrueorfalsestatementismadewithrespecttoaparticularsituation.Addsituationvariablestoeverypredicate.at(hunter,1,1)becomesat(hunter,1,1,s0):at(hunter,1,1)istrueinsituation(i.e.,state)s0.Alternatively,addaspecial2nd-orderpredicate,holds(f,s),thatmeans“fistrueinsituations.”E.g.,holds(at(hunter,1,1),s0)Addanewfunction,result(a,s),thatmapsasituationsintoanewsituationasaresultofperformingactiona.Forexample,result(forward,s)isafunctionthatreturnsthesuccessorstate(situation)tosExample:Theactionagent-walks-to-location-ycouldberepresentedby(

x)(

y)(

s)(at(Agent,x,s)^~onbox(s))->at(Agent,y,result(walk(y),s))7DeducinghiddenpropertiesFromtheperceptualinformationweobtaininsituations,wecaninferpropertiesoflocations

l,sat(Agent,l,s)^Breeze(s)=>Breezy(l)

l,sat(Agent,l,s)^Stench(s)=>Smelly(l)NeitherBreezynorSmellyneedsituationargumentsbecausepitsandWumpusesdonotmovearound8DeducinghiddenpropertiesIIWhybothcausalanddiagnosticrules?Maybediagnosticrulesareenough?However,itisverytrickytoensurethattheyderivethestrongestpossibleconclusionsfromtheavailableinformation.Forexample,theabsenceofstenchorbreezeimpliesthatadjacentsquaresareOK:(

x,y,g,u,c,s)Percept([None,None,g,u,c],t)^At(Agent,x,s)^Adjacent(x,y)=>OK(y)butsometimesasquarecanbeOKevenwhensmellsandbreezesabound.Considerthefollowingmodel-basedrule:(

x,t)(

t(Wumpus,x,t)^Pit(x))<=>OK(x)Iftheaxiomscorrectlyandcompletelydescribethewaytheworldworksandthewayperceptsareproduced,theinferenceprocedurewillcorrectlyinferthestrongestpossibledescriptionoftheworldstategiventheavailablepercepts.9DeducinghiddenpropertiesIIWeneedtowritesomerulesthatrelatevariousaspectsofasingleworldstate(asopposedtoacrossstates)Therearetwomainkindsofsuchrules:Causalrulesreflecttheassumeddirectionofcausalityintheworld:(Al1,l2,s)At(Wumpus,l1,s)^Adjacent(l1,l2)=>Smelly(l2)(Al1,l2,s)At(Pit,l1,s)^Adjacent(l1,l2)=>Breezy(l2)Systemsthatreasonwithcausalrulesarecalledmodel-basedreasoningsystemsDiagnosticrulesinferthepresenceofhiddenpropertiesdirectlyfromthepercept-derivedinformation.Wehavealreadyseentwodiagnosticrules:(Al,s)At(Agent,l,s)^Breeze(s)=>Breezy(l)(Al,s)At(Agent,l,s)^Stench(s)=>Smelly(l)10Representingchange:

TheframeproblemFrameaxiom:Ifpropertyxdoesn’tchangeasaresultofapplyingactionainstates,thenitstaysthesame.On(x,z,s)Clear(x,s)

On(x,table,Result(Move(x,table),s))

On(x,z,Result(Move(x,table),s))On(y,z,s)yxOn(y,z,Result(Move(x,table),s))Theproliferationofframeaxiomsbecomesverycumbersomeincomplexdomains11TheframeproblemIISuccessor-stateaxiom:Generalstatementthatcharacterizeseverywayinwhichaparticularpredicatecanbecometrue:Eitheritcanbemade

true,oritcanalreadybetrueandnotbechanged:On(x,table,Result(a,s))

[On(x,z,s)Clear(x,s)a=Move(x,table)]

[On(x,table,s)aMove(x,z)]Incomplexworlds,whereyouwanttoreasonaboutlongerchainsofaction,eventhesetypesofaxiomsaretoocumbersomePlanningsystemsusespecial-purposeinferencemethodstoreasonabouttheexpectedstateoftheworldatanypointintimeduringamulti-stepplan12QualificationproblemQualificationproblem:Howcanyoupossiblycharacterizeeverysingleeffectofanaction,oreverysingleexceptionthatmightoccur?WhenIputmybreadintothetoaster,andpushthebutton,itwillbecometoastedaftertwominutes,unless…Thetoasterisbroken,or…Thepowerisout,or…Iblowafuse,or…Aneutronbombexplodesnearbyandfriesallelectricalcomponents,or…Ameteorstrikestheearth,andtheworldweknowitceasestoexist,or…13RamificationproblemSimilarly,it’sjustaboutimpossibletocharacterizeeverysideeffectofeveryaction,ateverypossiblelevelofdetail:WhenIputmybreadintothetoaster,andpushthebutton,thebreadwillbecometoastedaftertwominutes,and…Thecrumbsthatfalloffthebreadontothebottomofthetoasterovertraywillalsobecometoasted,and…Someoftheaforementionedcrumbswillbecomeburnt,and…Theoutsidemoleculesofthebreadwillbecome“toasted,”and…Theinsidemoleculesofthebreadwillremainmore“breadlike,”and…Thetoastingprocesswillreleaseasmallamountofhumidityintotheairbecauseofevaporation,and…TheheatingelementswillbecomeatinyfractionmorelikelytoburnoutthenexttimeIusethetoaster,and…Theelectricitymeterinthehousewillmoveupslightly,and…14Knowledgeengineering!Modelingthe“right”conditionsandthe“right”effectsatthe“right”levelofabstractionisverydifficultKnowledgeengineering(creatingandmaintainingknowledgebasesforintelligentreasoning)isanentirefieldofinvestigationManyresearchershopethatautomatedknowledgeacquisitionandmachinelearningtoolscanfillthegap:Ourintelligentsystemsshouldbeabletolearnabouttheconditionsandeffects,justlikewedo!Ourintelligentsystemsshouldbeabletolearnwhentopayattentionto,orreasonabout,certainaspectsofprocesses,dependingonthecontext!15PreferencesamongactionsAproblemwiththeWumpusworldknowledgebasethatwehavebuiltsofaristhatitisdifficulttodecidewhichactionisbestamonganumberofpossibilities.Forexample,todecidebetweenaforwardandagrab,axiomsdescribingwhenitisOKtomovetoasquarewouldhavetomentionglitter.Thisisnotmodular!Wecansolvethisproblembyseparatingfactsaboutactionsfromfactsaboutgoals.Thiswayouragentcanbereprogrammedjustbyaskingittoachievedifferentgoals.16PreferencesamongactionsThefirststepistodescribethedesirabilityofactionsindependentofeachother.Indoingthiswewilluseasimplescale:actionscanbeGreat,Good,Medium,Risky,orDeadly.Obviously,theagentshouldalwaysdothebestactionitcanfind:(

a,s)Great(a,s)=>Action(a,s)(

a,s)Good(a,s)^~(

b)Great(b,s)=>Action(a,s)(a,s)Medium(a,s)^(~(

b)Great(b,s)vGood(b,s))=>Action(a,s)...17PreferencesamongactionsWeusethisactionqualityscaleinthefollowingway.Untilitfindsthegold,thebasicstrategyforouragentis:Greatactionsincludepickingupthegoldwhenfoundandclimbingoutofthecavewiththegold.Goodactionsincludemovingtoasquarethat’sOKandhasn'tbeenvisitedyet.MediumactionsincludemovingtoasquarethatisOKandhasalreadybeenvisited.RiskyactionsincludemovingtoasquarethatisnotknowntobedeadlyorOK.DeadlyactionsaremovingintoasquarethatisknowntohaveapitoraWumpus.18Goal-basedagentsOncethegoldisfound,itisnecessarytochangestrategies.Sonowweneedanewsetofactionvalues.Wecouldencodethisasarule:(

s)Holding(Gold,s)=>GoalLocation([1,1]),s)Wemustnowdecidehowtheagentwillworkoutasequenceofactionstoaccomplishthegoal.Threepossibleapproachesare:Inference:goodversuswastefulsolutionsSearch:makeaproblemwithoperatorsandsetofstatesPlanning:tobediscussedlater

19SemanticNetworksAsemanticnetworkisasimplerepresentationschemethatusesagraphoflabelednodesandlabeled,directedarcstoencodeknowledge.Usuallyusedtorepresentstatic,taxonomic,conceptdictionariesSemanticnetworksaretypicallyusedwithaspecialsetofaccessingproceduresthatperform“reasoning”e.g.,inheritanceofvaluesandrelationshipsSemanticnetworkswereverypopularinthe‘60sand‘70sbutarelessfrequentlyusedtoday.OftenmuchlessexpressivethanotherKRformalismsThegraphicaldepictionassociatedwithasemanticnetworkisasignificantreasonfortheirpopularity.20NodesandArcsArcsdefinebinaryrelationshipsthatholdbetweenobjectsdenotedbythenodes.john5Sueagemothermother(john,sue)age(john,5)wife(sue,max)age(max,34)...34agefatherMaxwifehusbandage21SemanticNetworksTheISA(is-a)orAKO(a-kind-of)relationisoftenusedtolinkinstancestoclasses,classestosuperclassesSomelinks(e.g.hasPart)areinheritedalongISApaths.ThesemanticsofasemanticnetcanberelativelyinformalorveryformaloftendefinedattheimplementationlevelisaisaisaisaRobinBirdAnimalRedRustyhasPartWing22ReificationNon-binaryrelationshipscanberepresentedby“turningtherelationshipintoanobject”Thisisanexampleofwhatlogicianscall“reification”reifyv:consideranabstractconcepttoberealWemightwanttorepresentthegenericgiveeventasarelationinvolvingthreethings:agiver,arecipientandanobject,give(john,mary,book32)givemarybook32johnrecipientgiverobject23IndividualsandClassesManysemanticnetworksdistinguishnodesrepresentingindividualsandthoserepresentingclassesthe“subclass”relationfromthe“instance-of”relationsubclasssubclassinstanceinstanceRobinBirdAnimalRedRustyhasPartWinginstanceGenus24Linktypes25InferencebyInheritanceOneofthemainkindsofreasoningdoneinasemanticnetistheinheritanceofvaluesalongthesubclassandinstancelinks.Semanticnetworksdifferinhowtheyhandlethecaseofinheritingmultipledifferentvalues.Allpossiblevaluesareinherited,orOnlythe“lowest”valueorvaluesareinherited26Conflictinginheritedvalues27MultipleinheritanceAnodecanhaveanynumberofsuperclassesthatcontainit,enablinganodetoinheritpropertiesfrommultiple“parent”nodesandtheirancestorsinthenetwork.Theserulesareoftenusedtodetermineinheritanceinsuch“tangled”networkswheremultipleinheritanceisallowed:IfX<A<BandbothAandBhavepropertyP,thenXinheritsA’sproperty.IfX<AandX<BbutneitherA<BnorB<Z,andAandBhavepropertyPwithdifferentandinconsistentvalues,thenXdoesnotinheritpropertyPatall.28NixonDiamondThiswastheclassicexamplecirca1980.PersonRepublicanPersonQuakerinstanceinstancesubclasssubclassFALSEpacifistTRUEpacifist29FromSemanticNetstoFramesSemanticnetworksmorphedintoFrameRepresentationLanguagesinthe‘70sand‘80s.AframeisalotlikethenotionofanobjectinOOP,buthasmoremeta-data.Aframehasasetofslots.Aslotrepresentsarelationtoanotherframe(orvalue).Aslothasoneormorefacets.Afacetrepresentssomeaspectoftherelation.30FacetsAslotinaframeholdsmorethanavalue.Otherfacetsmightinclude:currentfillers(e.g.,values)defaultfillersminimumandmaximumnumberoffillerstyperestrictiononfillers(usuallyexpressedasanotherframeobject)attachedprocedures(if-needed,if-added,if-removed)saliencemeasureattachedconstraintsoraxiomsInsomesystems,theslotsthemselvesareinstancesofframes.3132DescriptionLogicsDescriptionlogicsprovideafamilyofframe-likeKRsystemswithaformalsemantics.E.g.,KL-ONE,LOOM,Classic,…Anadditionalkindofinferencedonebythesesystemsisautomaticclassificationfindingtherightplaceinahierarchyofobjectsforanewdescription

Currentsystemstakecaretokeepthelanguagessimple,sothatallinferencecanbedoneinpolynomialtime(inthenumberofobjects)ensuringtractabilityofinference33AbductionAbductionisareasoningprocessthattriestoformplausibleexplanationsforabnormalobservationsAbductionisdistinctlydifferentfromdeductionandinductionAbductionisinherentlyuncertainUncertaintyisanimportantissueinabductivereasoningSomemajorformalismsforrepresentingandreasoningaboutuncertaintyMycin’scertaintyfactors(anearlyrepresentative)Probabilitytheory(esp.Bayesianbeliefnetworks)Dempster-ShafertheoryFuzzylogicTruthmaintenancesystemsNonmonotonicreasoning34AbductionDefinition(Encyclopedia

Britannica):reasoningthatderivesanexplanatoryhypothesisfromagivensetoffactsTheinferenceresultisahypothesis

that,iftrue,couldexplaintheoccurrenceofthegivenfactsExamplesDendral,anexpertsystemtoconstruct3DstructureofchemicalcompoundsFact:massspectrometerdataofthecompoundanditschemicalformulaKB:chemistry,esp.strengthofdifferenttypesofboundsReasoning:formahypothetical3Dstructurethatsatisfiesthechemicalformula,andthatwouldmostlikelyproducethegivenmassspectrum35MedicaldiagnosisFacts:symptoms,labtestresults,andotherobservedfindings(calledmanifestations)KB:causalassociationsbetweendiseasesandmanifestationsReasoning:oneormorediseaseswhosepresencewouldcausallyexplaintheoccurrenceofthegivenmanifestationsManyotherreasoningprocesses(e.g.,wordsensedisambiguationinnaturallanguageprocess,imageunderstanding,criminalinvestigation)canalsobeenseenasabductivereasoningAbductionexamples(cont.)36Comparingabduction,deduction,

andinductionDeduction:majorpremise: Allballsintheboxareblackminorpremise: Theseballsarefromtheboxconclusion: TheseballsareblackAbduction:rule: Allballsintheboxareblackobservation: Theseballsareblackexplanation: TheseballsarefromtheboxInduction:case: Theseballsarefromtheboxobservation: Theseballsareblackhypothesizedrule: Allballintheboxareblack

A=>BA---------BA=>BB-------------PossiblyAWheneverAthenB-------------PossiblyA=>BDeduction

reasonsfromcausestoeffectsAbductionreasonsfromeffectstocausesInductionreasonsfromspecificcasestogeneralrules37Characteristicsofabductivereasoning“Conclusions”arehypotheses,nottheorems(maybefalseevenifrulesandfactsaretrue)E.g.,misdiagnosisinmedicineTheremaybemultipleplausiblehypothesesGivenrulesA=>BandC=>B,andfactB,bothAandCareplausiblehypothesesAbductionisinherentlyuncertainHypothesescanberankedbytheirplausibility(ifitcanbedetermined)38Characteristicsofabductivereasoning(cont.)Reasoningisoftenahypothesize-and-testcycle

Hypothesize:Postulatepossiblehypotheses,anyofwhichwouldexplainthegivenfacts(oratleastmostoftheimportantfacts)Test:TesttheplausibilityofallorsomeofthesehypothesesOnewaytotestahypothesisHistoaskwhethersomethingthatiscurrentlyunknown–butcanbepredictedfromH–isactuallytrueIfwealsoknowA=>DandC=>E,thenaskifDandEaretrueIfDistrueandEisfalse,thenhypothesisAbecomesmoreplausible(supportforAisincreased;supportforCisdecreased)39Characteristicsofabductivereasoning(cont.)Reasoningisnon-monotonic

Thatis,theplausibilityofhypothesescanincrease/decreaseasnewfactsarecollectedIncontrast,deductiveinferenceismonotonic:itneverchangeasentence’struthvalue,onceknownInabductive(andinductive)reasoning,somehypothesesmaybediscarded,andnewonesformed,whennewobservationsaremade40SourcesofuncertaintyUncertaininputsMissingdataNoisydataUncertainknowledgeMultiplecausesleadtomultipleeffectsIncompleteenumerationofconditionsoreffectsIncompleteknowledgeofcausalityinthedomainProbabilistic/stochasticeffectsUncertainoutputsAbductionandinductionareinherentlyuncertainDefaultreasoning,evenindeductivefashion,isuncertainIncompletedeductiveinferencemaybeuncertain

Probabilisticreasoningonlygivesprobabilisticresult