Artificial Intelligence 人工智能 - 天津大學(xué)計算機科學(xué)與技 …

1、Chapter 5 Knowledge RepresentationXiu-jun GONG (Ph. D)School of Computer Science and Technology, Tianjin U http:/ OutlinepKnowledge & Knowledge representationpMethodology for KRnLogicnProduction SystemnSemantic NetnFramenScriptnObject-OrientedpSummaryKnowledge What is Knowledge ?InformationKnowledge

2、Knowledge = FactsRulesControl Strategy +(sometimes ) FaithsData Signal Taxonomy of KnowledgepFacts: declarative knowledgenthief(john), likes(john, wine)pRules: procedural knowledgenmay_steal(X, Y) if thief(X) and likes(X, Y)pControl Strategy: meta, super knowledgenreasoning strategynnote formnsearch

3、 strategyAttributes of KnowledgepRange ：Special GeneralpIntend ：Expository InstructionalpCertainty ：Certain UncertainpContain/Conflict ：Contain Conflict（in faith）Knowledge RepresentationpKnowledge representation is an issue that arises in both cognitive science and AI. nIn cognitive science it is co

4、ncerned with how people store and process information. nIn AI, the primary aim is to store knowledge so that programs can process it and achieve the verisimilitude of human intelligence. nAI researchers have borrowed representation theories from cognitive science. Some issues in KRpHow do people rep

5、resent knowledge? pWhat is the nature of knowledge and how do we represent it? pShould a representation scheme deal with a particular domain or should it be general purpose? pHow expressive is a representation scheme? pShould the scheme be declarative or procedural? Methodology of KRpLogicpProductio

6、n SystempSemantic NetpFramepScriptPropositional LogicpPropositional logic uses true statements to form or prove other true statements. nRepresentation (syntax): How to represent a proposition.nReasoning (algorithm): How to create or prove new propositions. pRepresentation of propositional logicnA pr

7、opositional symbol and connectives (!, *, +, =, )nExample:pC = “Its cold outside” ; C is a propositionpO = “Its October” ; O is a propositionpIf O then C ;if its October then its cold outsidePredicate LogicpSame connectives as propositional logicpPropositions have structure: Predicate/Function + arg

8、uments. nR, 2 ; Terms. Terms are not individuals, not propositionsnRed(R), (Red R) ; A proposition, written in two waysn(southOf UnicornCafe UniHall) ;a propositionn(+ 2 2) ; Term, since the function + ranges over numberspQuantifiers enable general axioms to be writtenn(forall ?x (iff (Triangle ?x)

9、(and (polygon ?x) (numberOfSides ?x 3)Easy to inferenceLogic as a KR language padvantages nWith a semantics nExpressiveness pDisadvantages nInefficient nUndecidability nUnable to express procedural knowledge nUnable to do default reasoning nNo abductionProduction System (1)pProduction rules are one

10、of the most popular and widely used knowledge representation languages pProduction rule system consists of three components nworking memory contains the information that the system has gained about the problem thus far. nrule base contains information that applies to all the problems that the system

11、 may be asked to solve. ninterpreter solves the control problem, i.e., decide which rule to execute on each selection-execute cycle. pUsed both for KR and Problem solving systemProduction System (2)pAdvantages: nNaturalness of expression nModularity nRestricted syntaxnAbility to Represent Uncertain

12、KnowledgepDisadvantages nInefficient nLess expressive Semantic Nets pIntuition base:nAn important feature of human memory is the high number of connections or associations between the different pieces of information contained in it. pThere are two types of primitive nNodes correspond to objects, or

13、classes of objects, in the world nLinks are unidirectional connections between nodes and correspond to relationships between these objects Semantic Nets pMajor problem with semantic nets is that although the name of this knowledge representation language is semantic nets, there is not, ironically, c

14、lear semantics of the various network representations. For the above example, nit can be interpreted as the representation of a specific bird named Tweety, or nit can be interpreted as a representation of some relationship between Tweety, birds and animals. Common used linkspIS-ApPART-OFpMODIFILES:

15、on, down, up, bottom, moveto,pLink types are set up for specific domain knowledgeExamples of Semantic Net (1)pRepresent a tableleg4leg1leg3tableleg2topSupportis-aAnalysis of Semantic NetpFor a particular Domain, you nmake up a set of link-typesncreate a set of nodes nconnect them together nascribe m

16、eaningpWrite Programs to manipulate the knowledgenLispnCLExamples of Semantic Net (2)pMy car is tan and Johns car is greencarcar1tancar2greenIjohnownerownercolorcoloris-ais-aInference in a Semantic Net (1)pInheritancenthe is-a and instance-of representation provide a mechanism to implement this.nInh

17、eritance also provides a means of dealing with default reasoningACABCIS-AIS-AIS-Aclydebirdbirdflyclyde flyIS-AcancanInference in a Semantic Net (2)pIntersection searchnThe notion that spreading activation out of two nodes and finding their intersection finds relationships among objects.nMany advanta

18、ges including entity-based organization and fast parallel implementation.n However very structured questions need highly structured networksInference in a Semantic Net (3)carcar1tancar2greenIjohnIcar1what?caris-ais-ais-a owner owner ownercolorcolorcolorWhat color is the car1?tanFrame representationp

19、Frame: a knowledge representation technique which attempts to organize concepts into a form which exploits interrelatioships and common beliefspframe-based KR is analogous to object-oriented programming; the difference is the entities encodedpA frame is similar to a record data structure or database

20、 record:pFrame has slot names and slot fillers, and usually arranged in a hierarchyStructure of frame (1)Frame name slot: value , value, . . . slot: facet: value, value, facet: value, value, Frame: printer superset: office-machine subset: laser-printer, ink-jet-printer energy-source: wall-outlet mak

21、er: Epson date: 1-April-2003 Structure of frame (2)pFrames often allowed slots to contain procedures.n“if-needed” procedures, run when value needednif-added” procedures, run when a value is added (to update rest of data, or inform user).Class and instance framesp(frame) instance: representing” lowes

22、t-level” object; a single object or entityp(frame) class: describes different frames (either instances or classes)pevery instance has an “is-a” link, pointing to its classnpossibly more than one “is-a”Example of frames (1)Frame Name:Properties:BirdColourWingsFliesUnknown2TrueFrame Name:Class:Propert

23、ies:TweetyBirdColourWingsFliesYellow1FalseClass frameInstance frameExample of frames (2)PandaType: AnimalColour: Black and whiteFood: EatFunc: .Name:Height:Age: 0SiblingBambooType: PlantGrowFunc: .Location: Height: 2JennyName: JennyHeight: 1.6Age: 5Sibling: VickyName: VickyHeight: 0.7Age: 1Sibling:

24、Capability of frame representationpAdvantagesnDomain knowledge model reflected directlynSupport default reasoningnEfficientnSupport procedural knowledgepDisadvantagesnLack of semanticsnExpressive limitationsScripts for KRpRather similar to frames: uses inheritance and slots; describes stereotypical

25、knowledge, (i.e. if the system isnt told some detail of whats going on, it assumes the default information is true), but concerned with events.pSomewhat out of the mainstream of expert systems work. More a development of natural-language-processing research. Definition of scriptspA script is a remem

26、bered precedent, consisting of tightly coupled, expectation-suggesting primitive-action and state-change frames Winston, 1992pA script is a structured representation describing a stereotyped sequence of events in a particular context Luger, Stubblefield,1998Why scripts? (1)pBecause real-world events

27、 do follow stereotyped patterns. Human beings use previous experiences to understand verbal accounts; computers can use scripts instead.pBecause people, when relating events, do leave large amounts of assumed detail out of their accounts. People dont find it easy to converse with a system that cant

28、fill in missing conversational detailWhy scripts? (2)pScripts predict unobserved events.pScripts can build a coherent account from disjointed observations.pApplicationsnThis sort of knowledge representation has been used in intelligent front-ends, for systems whose users are not computer specialists. nIt has been employed in story-understanding and news-report-understanding systems.Components of ScriptspScript namenEntry conditions:nRolesnPropsnScene 1nScene 2nnResultsScript: resta