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: [directed-graph.jpg] 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: [inheritance.jpg] 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 [cube1.jpg] Consider conceptional object like a view of a cube as a composed object with relations. _____________________________________________________________________________________________________ Different Views of a Cube [cube.jpg] _____________________________________________________________________________________________________ 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 [hotel.jpg] _____________________________________________________________________________________________________ Classes vs Individuals Distinguish: + concepts (representations) and objects + individual concepts and generic concepts [concept.jpg] _____________________________________________________________________________________________________ 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 [script.jpg] -------- ------------- ------------- _________________________________________________________________________________________________________ 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 [isa-hierarchy.jpg] "isa" corresponds mathematically to the subset relation, " subset " "instance" corresponds math. to the membership relation, " in " _________________________________________________________________________________________________________ ISPART-Hierarchy [ispart-hierarchy.jpg] _________________________________________________________________________________________________________ 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 24.4.2005 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/