1、Chapter 5 Knowledge Representation,Xiu-jun GONG (Ph. D) School of Computer Science and Technology, Tianjin University ,Outline,Knowledge C is a proposition O = “Its October” ; O is a proposition If O then C ;if its October then its cold outside,Predicate Logic,Same connectives as propositional logic

2、 Propositions have structure: Predicate/Function + arguments. R, 2 ; Terms. Terms are not individuals, not propositions Red(R), (Red R) ; A proposition, written in two ways (southOf UnicornCafe UniHall) ;a proposition (+ 2 2) ; Term, since the function + ranges over numbers Quantifiers enable genera

3、l axioms to be written (forall ?x (iff (Triangle ?x) (and (polygon ?x) (numberOfSides ?x 3),Easy to inference,Logic as a KR language,advantages With a semantics Expressiveness Disadvantages Inefficient Undecidability Unable to express procedural knowledge Unable to do default reasoning No abduction,

4、Production System (1),Production rules are one of the most popular and widely used knowledge representation languages Production rule system consists of three components working memory contains the information that the system has gained about the problem thus far. rule base contains information that

5、 applies to all the problems that the system may be asked to solve. interpreter solves the control problem, i.e., decide which rule to execute on each selection-execute cycle. Used both for KR and Problem solving system,Production System (2),Advantages: Naturalness of expression Modularity Restricte

6、d syntax Ability to Represent Uncertain Knowledge Disadvantages Inefficient Less expressive,Semantic Nets,Intuition base: An important feature of human memory is the high number of connections or associations between the different pieces of information contained in it. There are two types of primiti

7、ve Nodes correspond to objects, or classes of objects, in the world Links are unidirectional connections between nodes and correspond to relationships between these objects,Semantic Nets,Major problem with semantic nets is that although the name of this knowledge representation language is semantic

8、nets, there is not, ironically, clear semantics of the various network representations. For the above example, it can be interpreted as the representation of a specific bird named Tweety, or it can be interpreted as a representation of some relationship between Tweety, birds and animals.,Common used

9、 links,IS-A PART-OF MODIFILES: on, down, up, bottom, moveto, Link types are set up for specific domain knowledge,Examples of Semantic Net (1),Represent a table,Analysis of Semantic Net,For a particular Domain, you make up a set of link-types create a set of nodes connect them together ascribe meanin

10、g Write Programs to manipulate the knowledge Lisp CL,Examples of Semantic Net (2),My car is tan and Johns car is green,Inference in a Semantic Net (1),Inheritance the is-a and instance-of representation provide a mechanism to implement this. Inheritance also provides a means of dealing with default

11、reasoning,A,C,A,B,C,IS-A,IS-A,IS-A,clyde,bird,bird,fly,clyde,fly,IS-A,can,can,Inference in a Semantic Net (2),Intersection search The notion that spreading activation out of two nodes and finding their intersection finds relationships among objects. Many advantages including entity-based organizatio

12、n and fast parallel implementation. However very structured questions need highly structured networks,Inference in a Semantic Net (3),car,car1,tan,car2,green,I,john,I,car1,what?,car,is-a,is-a,is-a,owner,owner,owner,color,color,color,What color is the car1?,tan,Frame representation,Frame: a knowledge

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

14、 slot names and slot fillers, and usually arranged in a hierarchy,Structure 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 maker: Epson date:

15、 1-April-2003,Structure of frame (2),Frames often allowed slots to contain procedures. “if-needed” procedures, run when value needed if-added” procedures, run when a value is added (to update rest of data, or inform user).,Class and instance frames,(frame) instance: representing” lowest-level” objec

16、t; a single object or entity (frame) class: describes different frames (either instances or classes) every instance has an “is-a” link, pointing to its class possibly more than one “is-a”,Example of frames (1),Frame Name:,Properties:,Bird,Colour,Wings,Flies,Unknown,2,True,Frame Name:,Class:,Properti

17、es:,Tweety,Bird,Colour,Wings,Flies,Yellow,1,False,Class frame,Instance frame,Example of frames (2),Capability of frame representation,Advantages Domain knowledge model reflected directly Support default reasoning Efficient Support procedural knowledge Disadvantages Lack of semantics Expressive limit

18、ations,Scripts for KR,Rather similar to frames: uses inheritance and slots; describes stereotypical 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. Somewhat out of the mainstream of expert systems work. More a development of natural-language-processing research.,Definition of scripts,A script is a remembered precedent, consisting of tightly coupled, expectation-suggesting primitive-action and state-change frames Winston, 1992 A script is a structured representation describing a