Introduction to AI - Week 6

Definition 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

• 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

Correct: "marital_status(J J ADAMS) is married"
Incorrect: "marital_status(J J ADAMS) is divorced"

Discussion of 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

Correct:
height of Three-Finger Brown is 195cm
Incorrect:
height of Three-Finger Brown is 178cm

Semantic Nets (Cont'd)

• 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

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?

"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?

To understand a situation, questions like:

ample - Representation of a View of a Cube

Consider conceptional object like a view of a cube as a composed object with relations.

---

Different Views of a Cube



---

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



---

Classes vs Individuals

Distinguish:
• concepts (representations) and objects
• individual concepts and generic concepts



---

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




-------- ------------- -------------

---

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" corresponds mathematically to the subset relation, " subset "
"instance" corresponds math. to the membership relation, " in "

---

ISPART-Hierarchy



---

Evaluation    

• 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    

• 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 http://www.cs.bham.ac.uk/~mmk/Teaching/AI/