Introduction to AI - Week 6 Knowledge Representation I * Knowledge vs Data * Different representation formalisms + Rules + Logic + Natural language + Database systems + Semantic nets + Frames _________________________________________________________________________________________________________ Definition of Knowledge "Knowledge is the symbolic representation of aspects of some named universe of discourse" [Frost, p. 11] The universe of discourse may be the actual universe or a fictional one, one in the future, or in some belief. Examples of pieces of knowledge: * John is an employee of the ACTME company. * All employees of ACTME earn more than £ 25,000. * All employees of ACTME know that they should have a good lifestyle. * John doesn't think that he has a good lifestyle. * Everybody who knows that he should have a good lifestyle and does not think that he has a good lifestyle is disappointed. _________________________________________________________________________________________________________ Definition of Data "We define `data' as `the symbolic representation of simple aspects of some named universe of discourse' " [Frost, p. 12] That is, data is a special case of knowledge. Examples of pieces of data: * John is married to Sally. * John works for the ACTME company. * The average salary of ACTME is £ 30.000. _________________________________________________________________________________________________________ Knowledge Representation in Natural Language Expressiveness of natural language: * Very expressive, probably everything that can be expressed symbolically can be expressed in natural language (pictures, content of art, emotions are often hard to express). * Probably most expressive knowledge representation formalism we have. Reasoning very complex, hard to model Problems with natural language: * Natural language is often ambiguous. * Syntax and semantics are not fully understood. * There is little uniformity in the structure of sentences. Correct: "When they left the theatre it was pouring, hence they remembered that they forget the umbrella in the cloakroom." Incorrect: "When they left the cinema the moon was shining, hence they remembered that they forget the umbrella in the cloakroom." _________________________________________________________________________________________________________ Knowledge Representation in Database Systems Example: person record = { name : max 20 characters age : 3 digits in range 000-120 sex : male or female marital status : married, bachelor, spinster, divorced, widowed, or engaged first names of children : up to 10 names each max 15 characters } _________________________________________________________________________________________________________ An Instance A record structure: -------- ------------- ------------- J J ADAMS -------- ------------- ------------- 025 -------- ------------- ------------- male -------- ------------- ------------- married -------- ------------- ------------- Sally -------- ------------- ------------- Richard -------- ------------- ------------- Bob -------- ------------- ------------- or the same as directed graph: 1 025 J J ADAMS MALE 10 0 10 00 0000 1 1 00 00 000 0 111 111 AGE 0 111 111 0 111 111 0 111 SEX 101 0 111 NAME 101 0 1111 111 0 111 111 0 1111 111 0 111 1 1 PP PP 1 0 1 11 11 FIRST NAMES OF CHILDREN MARITAL STATUS 11 111 10 0 01 111 101 11 11 10 11 11 11 11 11 0101111111111111100 SALLY 001 0 11 10 0 11 0 11 1 0 110 0 00 MARRIED 01 RICHARD BOB Correct: "marital_status(J J ADAMS) is married" Incorrect: "marital_status(J J ADAMS) is divorced" _________________________________________________________________________________________________________ Discussion of Database Systems Example: Relations R1: Person -------- ------------- ------------- J J ADAMS 025 male married -------- ------------- ------------- P K BROWN 032 male single -------- ------------- ------------- . . . . . . . . . . . . -------- ------------- ------------- R2: Employment -------- ------------- ------------- XYZ J J ADAMS -------- ------------- ------------- XYZ P K BROWN -------- ------------- ------------- ABC P K BROWN -------- ------------- ------------- . . . . . . -------- ------------- ------------- R3: Parent/child -------- ------------- ------------- J J ADAMS Sally -------- ------------- ------------- J J ADAMS Richard -------- ------------- ------------- J J ADAMS Bob -------- ------------- ------------- . . . . . . -------- ------------- ------------- Properties of trad. database systems: * only simple aspects of some universe of discourse. We can represent entities and relationships between entities, but not much more. * well-suited to efficiently represent and process large amounts of data (derivation from a data base typically in constant time). Reasoning very simple: reasoning = lookup _________________________________________________________________________________________________________ Knowledge Representation in Semantic Nets Example: 01111111111111111111111 01111111111111111111111 0 1 HANDED 0 11 0 1 0 11 0 PERSON 1 -----------------> 0 RIGHT 11 0 1 0 11 0 1 0 11 01111111111111111111111 01111111111111111111111 ^ | ISA | | | | 01111111111111111111111 11111111111 0 1 HEIGHT 1 0 0 ADULT 1 1 178 0 0 MALE 0------------->1 0 0 1 11111111110 0 1 01111111110111111111111 ^ | | 1111111111110 ISA | HEIGHT 0 0 | /---> 1 195 0 11111111111111111111111 / 11 1 0 0 1 / 1111111111111 BATS 0 BASEBALL-PLAYER 1 / 0 0 / EQUAL TO HANDED <------------------- 0 1 / ^0 1---------> 1111111111110 / 0 1 BATTING 1 0 / 11111111001001111111111 AVERAGE 1 .252 0 / 1 0 ISA / 1 0001 1111111111110 / 1 1111111111111 1111111111111111 111111111111111 1111111111111 1 1 1 0 0 0 BATTING-AVERAGE 1 1 1 0.106 1 BATTING-AVERAGE 1 PITCHER 0 0 FIELDER 0 ----------------------->1 .262 1 1 0 <--------------------- 0 0 0 0 1 1 0111111111111 0111111111111110 111111111111110 1111111111111 ^ ^ | | INSTANCE | | INSTANCE | | 11111111111111111111111 1111111111111111111111111 11111111111111111111111 11111111111111111111111 1 1 TEAM 0 1 0 1 TEAM 1 1 1 0 <--------- 1 1 0 1 ----------->1 1 1 CHICAGO-CUBS 1 0 THREE-FINGER-BROWN 1 0 PEE-WEE-REESE 1 1 BROOKLY-DODGERS 1 1 1 1 1 0 1 1 1 1 111111111111111111111 1111111111111111111111111 11111111111111111111111 11111111111111111111111 Correct: height of Three-Finger Brown is 195cm Incorrect: height of Three-Finger Brown is 178cm _________________________________________________________________________________________________________ Semantic Nets (Cont'd) Properties of semantic nets: * Allows to structure the knowledge to reflect the structure of that part of the universe which is being represented. * default values (e.g. height of a baseball player to be 195cm), very strong representation facilities by procedural attachment * Notion explained up to now quite general, for a useful tool, must be much refined. In particular clear syntax, but clear semantics has to be worked out. _________________________________________________________________________________________________________ Frames Frames: A frame consists of a collection of slots which can be filled by values or pointers to other frames. Meaning of "child's birthday party" poorly approximated by definition like "a party assembled to celebrate a birthday" with "party" defined as "people assembled for a celebration". Children know more plus default assignments: -------- ------------- ------------- Child's Birthday Party -------- ------------- ------------- -------- ------------- ------------- Dress: Sunday-Best -------- ------------- ------------- Present: Must please host. Must be bought and gift-wrapped. -------- ------------- ------------- Games: Hide and seek. Pin tail on donkey. -------- ------------- ------------- Decor: Balloons. Favours. Crepe-paper -------- ------------- ------------- Party-meal: Cake. Ice-cream. Soda. Hotdogs -------- ------------- ------------- Cake: Candles. Blow-out. Wish. Sing Birthday Song. -------- ------------- ------------- Ice-cream: Standard three-flavour -------- ------------- ------------- _________________________________________________________________________________________________________ Why Frames? Quotes from "A Framework for Representing Knowledge" [Minsky81] "It seems to me that the ingredients of most theories [...] have been on the whole too minute, local, and unstructured to account [...] common-sense thought" "When one encounters a new situation [...], one selects from memory a structure called a frame. This is a remembered framework to be adapted to fit reality by changing details as necessary. A frame is a data-structure for representing a stereotyped situation, like [...] going to a child's birthday party. Attached to each frame are several kinds of information. Some of this information is about how to use the frame. Some is about what one can expect to happen next. Some is about what to do if these expectations are not confirmed." _________________________________________________________________________________________________________ Frames - What and Why? [Minsky, 1981]: A Frame is a collection of questions to be asked about a hypothetical situation: it specifies issues to be raised and methods to be used in dealing with them. To understand a situation, questions like: ample - Representation of a View of a Cube ,ii 8 Z ISA Z 7S 111111111111111111111 CUBE . 2 : XM0 8 2 M @; @ M ; 0, M M: iXr.Sr Wr M 07 Xr: rS7 :. @ M 87 ;X; ;2: S: Z,.i 8 rZ ia ,XX ,72 ;i,Ma:i.XZXMX2,,:. ;@ .::::::::::: :. r, EE ;ii 0 2 2 2.::, iW .,::::::.WM REGION Sii EE ;:a W i;.M ; rMi i. i SX; r7; X PARALLELOGRAM M111111111 M 1111 : M Zi;;;;;;:MM r XX :X7 S 1 1: 0 0 1 i M, r rXr 7X. S ISA 1 M1 M 1 B. r 7X;7; S 1 M ISA : i.r ISA @i r 7 S i B 0 ;2 ri . 1, XX r AA S BB S LEFT-ABOVE 000000000000000000000 ir;ir2 2i: :. . ,a2 11111 RIGHT-ABOVE r AA S BB S , M 1 ,., 0 M. M,,,. Xa 1 iM ; S S 2X2. Xir2ZX:X:. W i,77722iirr :ZrX r S Z @ 00 M iWM a .XX S 77: S i: W i :X ;Xi S rXr 0X M B7, ,rr S :XS r r iX; r XX. S EE S Xr@;X r EE r Mr M8 : : AA BB AA BB Consider conceptional object like a view of a cube as a composed object with relations. _____________________________________________________________________________________________________ Different Views of a Cube Z8ZBZ XaS20 M M B0 M :M@0MM M M7 M M M M :M , M S M M@ i; M . r; rr, :Siiiiiiiiiiiii:7 :;; ;ri .r; S S :;i 7r, .SPATIAL FRAME .r; EE :X, S ; r7. :r7 a EE Z; S EE W ,;i EE ;; i r; ,7i X S EE S W: EE 7a ; r;: r7. S ; :: X ;;i rr: X ; rr :7; S X S S rr ,r7 S ; ,a S 2.iiiiiiiiiiiiiiii.a S ;i r;. S ; AA X BB S X X S . Z S ; AA S BB S S S S BB X CC S ; S S S BB S S BB S CC S ;; S :r: S BB S S S 2 ;7, S .rr S S ii; S r;: .r; 7 r7, S S ;7. S :7; ;;,Zi; 7 7 ,;7 7 ;7 ZX222SSSSSSSSSSS22X0 i:Wi: VIEW 1 VIEW 2 VIEW 3 i; S ii 7i;i ii:7. i,.i r X 2 r ..ZZ., ;@8 SM7 PICTORIAL FRAME .;i : r i;; i;:i .iir 7::i ;i Z i0:. Zi 8i iZS .;: : : ,;: i;, r ; .. S X ;. ; 7 X r ;, rXX. i;Si .iSi ia7i ,7a; ;Sr. ,X7i rar. S 2 r, i 7 7 i :. 7 S S X S S.. X X X7 S X X S 2 :r .ia: ..i222M; ,: S27. .7X: r7i iXX;. : .77; :;i rX: ;rr , .ZS2 78X78X. ,irr: 27 ....: .,:,...... . . .rSrZS 2 :, ;2ZS .Z208Xa i;:r... 2. ....: ..r.i. . . , rr2XS; M , 7a2r , : 7X2S7Zr .X,;;i.rBi , ... , arXSX 0 : i8ZZ: .X8SZMXi a2 r.. . rXXX2: ,Z a . .W0Z . .0Z0020: 7M 77ZaZ .., : : , M7 Xi M WS. : MM 8M,M . : . .r2iZM0M MMM. ,,.:, :.MM B:M DD .,. ,iiii:i0 AA .::i:,. .:iiii:. @; BB CC DD LEFT AA . LEFT BB LEFT CC M ;.,, X.., r.,, , XrS2222SXr;r7X22222222222222222227i .iXS222222222222222222222S7r;r7XS222222222222XZ LEFT _____________________________________________________________________________________________________ Example (Cont'd) | -------- ------------- ------------- View-of-a-Cube -------- ------------- ------------- Slot Filler Constraint -------- ------------- ------------- -------- ------------- ------------- Name View_1& -------- ------------- ------------- region-of A parallelogram & visible -------- ------------- ------------- region-of B parallelogram & visible -------- ------------- ------------- region-of C parallelogram & invisible -------- ------------- ------------- region-of D parallelogram & invisible -------- ------------- ------------- region-of E parallelogram(E) &visible & left-above(E,A) & right-above(E,B) -------- ------------- ------------- Part of a tabular representation of the frame for one view _____________________________________________________________________________________________________ Part of the Frame Description of a Hotel Room 1 111111 11111111111111111111111111111111111 11 0 11111111111111111111111111111111111111111110 0 0 111111110000 0 1 0 HOTEL ROOM 1 01 101 1 HOTEL CHAIR 1 01111111111111111111111111111111111111111111111 0 0111111111111111111110111000000000000000000010 0 1 0 0 1 0 SUPERCLASS: ROOM 0 0 0 SUPERCLASS: CHAIR 1 01111111111111111111111111111111111111111111110 0 0 1 0 0 0 0111111111111111111111111111111111111111111111 0 LOCATION: HOTEL 0 0 0 1 01111111111111111111111111111111111111111111 11 1 0 HEIGHT: 20-40CM 1 0 CONTAINS: (HOTEL CHAIR 1111111101000000000010 0111111111111111111111111111111111111111111111 0 1 0 1 0 1 0 LEGS: 4 1 0 HOTEL PHONE 11111010010000000000010 0111111111111111111101111111111111111111111110 0 1 0 0 1 0 HOTEL BED 111111110 1111 0 0 USE: SITTING 1 0 0 0 0 0 1 01000000000000000000111111111111111111011111101 0 0 0111111111111111111111111111111111111111111110 0 0 0 0 0 0 0 0 0 0 0 0 01000000000000000000000000000000000000000000011 0 0 11 0 0 0 100000011000 0 HOTEL PHONE 0 0 0 0 0 11111111111111111111111111111111100000000000010 0 0 0 0 0 SUPERCLASS: PHONE 0 0 01111111111111111111111111111111111111111111110 01000000000000000000000000000010 0 0 1 0 USE: CALLING ROOM SERVICE 0 00 0 0 00 01111111111111111111111111111111111111111111110 1 0 0 011111111111111111111111111111111111111110 0 BILLING: THROUGH ROOM 0 0 0 0 0 0 HOTEL BED 0 01111111111111111111111111111111111111111111110 0 0 011111111111111111111111111111111111111110 0 0 0 SUPERCLASS: BED 0 011111111111111111111111111111111111111110 0 0 0 USE: SLEEPING 0 011111111111111111111111111111111111111111111111110 0 0 0 0 011111111111111111111111111111111111111110 110000001000010 MATTRESS 0 0 0 0 0 0 0 SIZE: KING 0 0 011111111111111111000000000000010000000000000000010 0 0 0 0 0 011111111111111111111111111111111111111111 0 0 SUPERCLASS: CUSHION 0 0 PART: (MATTRESS 1111111110111111111110 0 0 0 0 011111111111111111111111111111111111111111111111110 0 FRAME) 0 0 0 0 0 0 FIRMNESS: FIRM 0 0 0 0 0 0 0 0 0 111111111111111111111111111111111111111110 011111111111111111111111111111111111111111111111111 _____________________________________________________________________________________________________ Classes vs Individuals Distinguish: + concepts (representations) and objects + individual concepts and generic concepts GENERIC CONCEPT ;rMMMMMMr iMMMM8 7aMMM@, MM ZMM MW Mr Z8 M M ARCH X7 ZZ ARCH M ZMMS MXXXXXXSSSSSSSSSS2SSSSXXSSSSSXSSXXXXXX MM ;M MMMMMMMMM: INSTANTIATION MZ8SS;iX2aaaa2S2S2ZZZZ22Z0000000000BB8 MMa @M0 MMMMM@ INSTANTIATION 8S;8MMMM8ZXra2;7 : . :;;r7X7XXS MMMM8M rWMMMMM MMM0 ZM 8S:S XZBMMMMMMMMMMMMMMMMMMW0SX2XXXXSS r MMM.i ,M MMMMMZ ZXiX .r2BBMMMMMMXXX MM MMM ar2MMMMMMMMMWBB8aaa2XXi:: :;X MW Xi MMMMMMMMMMMMMMMMMM@@MMMMMM@MMMMMMZX MMM ,MMMZ Xr M78Z8BWWWBZZaa8000MMMMMMMMMMMMMMX;X MMMM 7MMMM rr M WZ8Za27aaXXSSZZ808BBW.7X MMMMMa 8 77 @ MMMMMMMW B27;;ZSi28ZM , ,;XX M MMiB MM. XX:r MZWBZ0MZ:W;0MMMMM@72M @MMMMMM.r7X MM .MMMMMr SX;r X;:i;rXSrZMMMMMMMMMSWSM@W@@MM.;77 MM a2r8B@BWWZ2800W; 7WMMMM0 . S.,r7 a2raBB2Xr7SX8WM ;MMMMMMMMMMMMMM:r7 ZMMW X7;X @ZZ@:;X:.i;;: MMMW r , 2,;ra,7X INDIVIDUATION MM :WMMMMM0 B8,Z :7M000XS8,i;;;; MMM@ irMWB@MX;;7X INDIVIDUATION MM MMMMMM MM Z iZM2;88rX:;;rrr 8MMM r,S@rMWZi77X MM MSZMMM MM,0 ,@rW8 ZSi.7rrr7 8@MM ,i0rZ 0r,SX2 MM 7MMMM 0M i,:Z MZa00WZX 7;;ii Z0MM iZBBMMM, ZSX SMM8 00iX 2B .. 2Xa,:X:28 Z8MM 7:2i. :, SXr MMBM.MMMMMMSSB M@ZaM;Z8MM @WMWSMMMMMZ; BMM MMM@ WMi MM@SMZ88Ma i i2; MM SMMMMM aXa8MMB@@MSMM: iMM.,rW0MMM7MB7 :.MM MM MMM MM@MMMMMMMS8Z0@MMMMMMMM@MBMMMMMMMMMM@M MM DENOTATION MM@8a222a0B00WWW80MMMMMMa8@MMMMMMMMMWB WB :MMM DENOTATION MM80@MMMM@WMWZB8ZMMM@BMBZ8Zaa2S22SaZ0B XM@M2B0MMM8MMM: MMMMW MMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM :MMM. 2MWM MM Xi,,:::,..,.,...,,...,.....,,,.,.,,,:: :MW MM MM ARC-DE-TRIOMPHE Mi M ARC-DE-TRIOMPHE M INDIVIDUAL OBJECT M M Ma MW WMS .MX SMBM iMWMi .0@MMM80M00M@MMa INDIVIDUAL CONCEPT _____________________________________________________________________________________________________ Procedural Attachment General problem to balance the expressiveness of a knowledge representation formalism and the efficiency to manipulate the represented knowledge. Idea of frames: structure the knowledge, this means also restricting the expressive power in some parts, and extending in others. In order to increase expressive power: procedural attachment, i.e. allow functions to be written in a programming language to be stored instead of the value of some slot. _____________________________________________________________________________________________________ Procedural Attachment (Cont'd) | -------- ------------- ------------- rectangle -------- ------------- ------------- -------- ------------- ------------- superclass: polygon -------- ------------- ------------- (x,y)-Position: (0cm,0cm) -------- ------------- ------------- length: 5cm -------- ------------- ------------- breadth: 2cm -------- ------------- ------------- area: procedure(z) length(z)* breadth(z) -------- ------------- ------------- circumference: procedure(z) 2*( length(z)+ breadth(z)) -------- ------------- ------------- | -------- ------------- ------------- square -------- ------------- ------------- -------- ------------- ------------- superclass: rectangle -------- ------------- ------------- (x,y)-Position: (0cm,2cm) -------- ------------- ------------- length: 5cm -------- ------------- ------------- breadth: procedure(z) length(z) -------- ------------- ------------- Instead of writing explicit values, the values of the slots area, circumference (as well as breadth in the case of square) are calculated by need. Consider update of length from 5cm to 6cm! _____________________________________________________________________________________________________ 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 stereotyped sequence of events in a particular context [Luger, Stubblefield, 1998, p.324] * That is, extend frames by explicitly representing expectations of actions and state changes. * Find primitives to describe the world like PTRANS for "transfer physical location of an object (= go)" and ATRANS for "transfer a relationship (= give)". _________________________________________________________________________________________________________ A Restaurant Script (Schank and Abelson, 1977, cf. Luger-Stubblefield, p.327) -------- ------------- ------------- Script: RESTAURANT -------- ------------- ------------- Track: Coffee Shop Props: Tables Menu F=Food Check Money Roles S=Customer W=Waiter C=Cook M=Cashier O=Owner Entry cond.: S hungry S has money Results: S has less money O has more money S is not hungry S is pleased (optional) -------- ------------- ------------- _________________________________________________________________________________________________________ Restaurant Script (Cont'd) -------- ------------- ------------- Script: RESTAURANT (Cont'd) -------- ------------- ------------- Scene 1: Entering S PTRANS S into restaurant S ATTEND eyes to tables S MBUILD where to sit S PTRANS S to table S MOVE S to sitting position Scene 2: Order (MENU ON TALBE) (W BRINGS MENU) (S ASKS FOR MENU) S PTRANS MENU TO S S MTRANS SIGNAL TO W W PTRANS W TO TABLE 110 S MTRANS `NEED MENU' TO W 1 1010 W PTRANS W TO MENU 0 1001 0 10001 0 0011 0 0010 11 1001 0 0 0 0 W PTRANS W TO TABLE 1 W ATRANS MENU TO S 0 11 1 001 10 0011 11 S MTRANS FOOD LIST TO CP(S) * S MBUILD CHOICE OF F S MTRANS SIGNAL TO w W PTRANS w TO TABLE S MTRANS `I WANT F' TO w 11 10001110001 110111000111 11001000 W PTRANS W TO C W MTRANS (ATRANS F) TO C 10001 101100000 1 00011000 1 111000001111 1 001 1 C MTRANS `NO F TO W 1 W PTRANS W TO S 0 W MTRANS `NO F TO S (GO BACK TO *) OR C DO (PREPARE F SCRIPT) (GO TO SCENE 4 AT NO PAY PATH) TO SCENE 3 -------- ------------- ------------- _________________________________________________________________________________________________________ Restaurant Script (Cont'd) -------- ------------- ------------- Script: RESTAURANT (Cont'd) -------- ------------- ------------- Scene 3: Eating C ATRANS F to W W ATRANS F to S S INGEST F (Option: Return to Scene 2 to order more; otherwise, go to Scene 4) Scene 4: Exiting W MOVE (write check) W PTRANS W to S W ATRANS check to S S ATRANS tip to S S PTRANS S to M S ATRANS money to M S PTRANS S to out of restaurant -------- ------------- ------------- * Different scripts for different types of restaurants. * Script leaves details open. * Script greatly reduces search in a particular context. _________________________________________________________________________________________________________ Declarative or Procedural Representation of Knowledge How to represent knowledge? * "Knowing how": procedure that can be called The human information processor is a stored program device, with its knowledge of the world \em embedded in the programs. What a person (or a robot) knows about the English language, the game of chess, or the physical properties of his world is coextensive with his set of programs for operating with it. * "Knowing that": declarative representation which requires an interpreter. Advantages: Understandability, learnability, accessibility, communicability, flexibility, economy of storage. _________________________________________________________________________________________________________ Properties of Good Representations * They make the important objects and relations explicit: you can see what's going on at a glance. * They expose natural constraints: you can express the way one object or relation influences another. * They bring objects and relations together: You can see all you need to see at one time. * They suppress irrelevant detail: You can keep rarely used details out of sight, but still get to them when necessary. * They are transparent: You can understand what is being said. * They are complete: You can say all that needs to be said. * They are concise: You can say what you need to say efficiently. * They are fast: You can store and retrieve information rapidly. * They are computable: You can create them with an existing procedure. _________________________________________________________________________________________________________ Fundamental Properties of Representation [Winston92, p. 18ff] * A lexical part that determines which symbols are allowed in the representation's vocabulary. * A structural part that describes constraints on how the symbols can be arranged. * A procedural part that specifies access procedures that enable you to create descriptions, modify them, and to answer questions using them. * A semantic part that establishes a way of associating meaning with the description. _________________________________________________________________________________________________________ What's in a Semantic Net Semantic Nets consist of * lexical part: + nodes, denoting objects + links, denoting (binary) relations between objects + link labels, denote particular relations * structural part: directed graph, with labelled links * procedural part: + constructors to make, + readers to answer questions, + writers to alter, and + erasers to delete nodes and links * semantic part: meaning of nodes and links depends on the application _________________________________________________________________________________________________________ On Semantics Arguments about what it means to have a semantics have employed philosophers for millennia. Some alternatives: * Equivalence semantics: Let there be some way of relating descriptions in the representation to descriptions in some other representation that already has an accepted semantics. * Procedural semantics: Let there be a set of programs that operate on descriptions in the representation. That is, the meaning is defined by what the programs do. * Descriptive semantics: Let there be explanations of what descriptions mean in terms we understand intuitively. _________________________________________________________________________________________________________ Levels of Semantic Networks [Brachman79] | -------- ------------- ------------- Level Primitives -------- ------------- ------------- -------- ------------- ------------- Implementational Atoms, pointers, numbers -------- ------------- ------------- Logical Propositions, predicates, logical operators -------- ------------- ------------- Epistemological Concept types, conceptual subpieces, inheritance and structuring relations -------- ------------- ------------- Conceptual Semantic or conceptual relations (cases), primitive objects and actions -------- ------------- ------------- Linguistic Arbitrary concepts, words, expressions -------- ------------- ------------- _________________________________________________________________________________________________________ ISA-Hierarchy 111111111111111111111111111 0 1 0 LIVING THIN 1 0 1 011111111111111111111111111 1001 10001 ISA ISA 1000001 100000011 110000 00001101 1001 01100111 0101111111111111110 111111111111110 0 0 0 0 0 ANIMAL 0 0 PLANT 0 0 0 0 0 1111 10111111111110 111111111111110 10 0001 ISA 00 00 ISA ISA 100 00000 ISA 001 000 00 111 1 000 1001 00 01 001 10 101 11111111111111111111111 1111111 111111 0111111111110 0111101 110 0 0 0 0 0 1 0 PET 0 0 0 0 0 0 BUSH 1 0 0 0 LIVESTOCK 0 0 TREE 0 0 1 11001111111 0 0 0 0 0111111111111 ISA 0011 0 11111111111111111111111 11111111111111 110 11 ISA 10 10 01111000110 1011101111111 ISA 0 ISA 1 0 0 1 0 0 0 0 DOG 0 1 CAT 0 1111111111111111 1 0 0 1 0 0 0 1011111111110 11111111110 1111111111111 0 0 1 1 0 1 11 0 HORSE 0 1 OAK 0 ISA 00 0000 0 1 1 0 10 001 ISA 0111111111111111 1011111111110 0 000 01111111111111111111 101 1 1 1 GERMAN SHEPHERD 1 111111111111111 1 1 1 1 1 1 0 POODLE 1 11111111111111111111 1 0 111111111111111 "isa" corresponds mathematically to the subset relation, " subset " "instance" corresponds math. to the membership relation, " in " _________________________________________________________________________________________________________ ISPART-Hierarchy DOG ///// / \ \\\\\ ispart ispart ispart ispart //////////////////////////// / \ \\\\\\\\\\\\\\\\\\\\\\\\\\ HEAD BODY APPENDAGES TAIL ///////// / \ \\\\ / \ ispart ispart ispart ispart ispart ispart / / \ \ / \ EARS NOSE EYES MOUTH LEG PAWS _________________________________________________________________________________________________________ Evaluation notes.jpg] * There is no single most adequate knowledge representation formalism for everything. * main points for selecting a representation formalism: what should be represented, how should the knowledge be processed. Further Reading books-shelf1.jpg] * R.A. Frost: Introduction to Knowledge Base Systems, Collins, 1986. * George F. Luger: Computation & Intelligence, MIT Press, 1995. Part Two - Knowledge Representation, p.123-362. * Douglas B. Lenat and R.V. Guha: Building Large Knowledge-Based Systems, Addison-Wesley, 1990. * Ronald J. Brachman and Hector J. Levesque, eds.: Readings in Knowledge Representation, Morgan Kaufmann, 1985. _________________________________________________________________________________________________________ _________________________________________________________________________________________________________ © Manfred Kerber, 2004, Introduction to AI 22.12.2004 The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/l6.html. URL of module [1]http://www.cs.bham.ac.uk/~mmk/Teaching/AI/ References 1. http://www.cs.bham.ac.uk/~mmk/Teaching/AI/