Knowledge Representation Introduction • Domain specific knowledge is needed to solve some problems. • Knowledge base – representation. • Inference techniques • Use to prove facts. • Use to answer queries Knowledge Representation Schemes • Logical representation schemes – logical proofs, e.g. predicate logic. • Procedural representation schemes – procedural list of instructions, e.g. production rule systems. • Network representation schemes – graphical representation, e.g. semantic networks and conceptual graphs. • Structured representation schemes –extension of network schemes, e.g. scripts and frames. • Structures for incomplete or inconsistent knowledge: Bayesian reasoning, Dempster-Shafer, fuzzy logic. . Semantic Networks • Consists of nodes and arcs. • Nodes represents objects. • Arcs represents relationships between the objects. • Relationships: – – – – is-a Instance has/has-a Others . Example 1 Clyde is an elephant. Mammal is-a Elephant instance Clyde . Example 2 has Tail is-a Great Dane Dog communicates Barks height Tall instance Pluto has has 4 Legs Spots Example 3 Mammal is-a Person has-a Nose instance Blue uniform colour Pee-Wee team Brooklyn Dodgers Reese Example 4 John’s height is 72. John height 72 John is taller than Bill. John Bill height H1 greater than height H2 Example 5 John gives Mary the book. Mary recipient Give giver object Book32 John Using Case Frames • Problems with semantic networks • Attempts to standardize semantic networks led to the development of case frames. • Each sentence is represented by a case frame. • Each case frame represents an actions. • Case frames define case relationships: agent, object, instrument, location and time. . Example: Case Frame time Sarah agent Fix object instrument past chair glue Exercises Construct semantic networks for the following statements: • Pompeian(Marcus), Blacksmith(Marcus). • Mary gave the green coloured vase to her favorite cousin. • John went downtown to deposit his money in a bank. Conceptual Graphs • Is a connected bipartite graph. • Conceptual relation nodes represent relations between concepts. • The arcs connecting nodes are not labeled. • Concepts are represented by boxes. • Relations are represented by arcs. Conceptual Graph Relations 1-ary relation bird flies 2-ary relation dog colour brown 3-ary relation mother child parents father Example Mary gave John the book. person: Mary agent person: John agent give object book Unique Markers • If an individual object is unknown a unique marker can be used in place of the name of the object. • A unique marker is comprised of a hash symbol (#) followed by a number. • Each object has its own unique marker. Example 1: Unique Markers dog: Emma dog: #1352 colour brown colour brown Example 2: Unique Marker dog: #1352 colour nam e brown ”emma” Example Her name was McGill and she called herself Lil, but everyone knew her as Nancy. name “McGill” person: #941 name “Lil” name ”Nancy” Generic Markers • A generic marker is used to represent an unspecified individual of a type. • A generic marker is represented by an asterisk *. • Name variables can also be used, e.g., *X to indicate an unspecified individual. Example: Generic Marker The dog is scratching its ear with its paw. dog: *X agent object scratch ear instrument part paw part dog: *X Display Form John is going to Boston by bus. person: John agent go instance bus destination city: Boston Linear Form John is going to Boston by bus. [Go] – (Agnt) → [Person: John] (Dest) → [City: Boston] (Inst) → [Bus] Exercises Construct conceptual graphs for the following statements: • Jane gave Tom an ice cream. • Basketball players are tall. • Paul cut down the tree with an axe. • Place all the ingredients in a bowl and mix thoroughly.