Transcript November 2008_Knowledge_Representation_i

Lectures on Artificial
Intelligence (CS 364)
Khurshid Ahmad
Professor of Artificial Intelligence
Centre for Knowledge Management
September 2001
1
1
KNOWLEDGE REPRESENTATION
‘The idea of explicit representations of
knowledge, manipulated by general
purpose inference algorithms, dates back
to the philosopher Leibniz, who
envisioned a calculus of propositions that
exceed in its scope and power the
differential calculus he has developed’
(Brachman, Levesque and Reiter 1991:1)
2
KNOWLEDGE REPRESENTATION
'A representation is a set of conventions about how to
describe a class of things. A description makes use of
the conventions of a representation to describe some
particular thing.' (Winston 1992:16).
‘Good representations make important objects and
relations explicit, expose natural constraints, and bring
objects and relations together’ (ibid: 44)
The representation principle
Once a problem is described using an appropriate
representation, the problem is almost solved.
3
KNOWLEDGE REPRESENTATION
A number of knowledge representation schemes (or
formalisms) have been used to represent the knowledge
of humans in a systematic manner. This knowledge is
represented in a KNOWLEDGE BASE such that it can be
retrieved for solving problems. Amongst the wellestablished knowledge representation schemes are:
•Semantic Networks;
• Frames;
• Conceptual Dependency Grammar;
• Conceptual Graphs;
• Predicate and Modal Logic
• Conceptual or Terminological Logics
4
KNOWLEDGE REPRESENTATION
A number of knowledge representation schemes (or
formalisms) have been used to represent the knowledge
of humans in a systematic manner. This knowledge is
represented in a KNOWLEDGE BASE such that it can be
retrieved for solving problems. Amongst the wellestablished knowledge representation schemes are:
• Procedural Schemes
(Production Rules)
•Propositional Schemes
(Semantic Nets; Frames; ConceptualDependency Grammar, Conceptual Graphs; Logics)
• Analogical Schemes
•(Matrices)
5
KNOWLEDGE REPRESENTATION
A Brief History of Knowledge Representation
1960's: Taxonomy, inheritance and knowledge
'networks‘
1970's: Structuring the semantic network & the
rise of logic
1980's: 'Semantic networks' with semantics &
logic for change
1990's: Meta-knowledge representation, belief
representation
6
KNOWLEDGE REPRESENTATION
A Brief History of Knowledge Representation
1960's: Taxonomy, inheritance and knowledge 'networks‘
Semantic Nets, Frames, Predicate Logic
1970's: Structuring the semantic network & the rise of logic
Structured Semantic Networks
Logic for Problem Solving: Program = Logic + Control
Fuzzy Logic and Uncertainty Representation
1980's: 'Semantic networks' with semantics & logic for change
The 'epistemologically explicit' KL-ONE language;
Temporal Logic, Deviant Logic, Non-monotonic Logics
1990's: Meta-knowledge representation, belief representation
Theoretically well-grounded networks & Pierce movement
Representing Belief
Default Logics, Temporal reasoning
Mixed representation systems
7
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
•Ross Quillian (1966 and 1968) was among the early AI
workers to develop a computational model which
represented 'concepts' as hierarchical networks.
•This model was amended with some additional
psychological assumptions to characterise the structure
of [human] semantic memory.
8
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Collins and Quillian (1969) proposed that
• Concepts can be represented as hierarchies of inter-connected concept
nodes (e.g. animal, bird, canary)
• Any concept has a number of associated attributes at a given level ( e.g.
animal --> has skin; eats etc.)
• Some concept nodes are superordinates of other nodes (e.g. animal
>bird) and some are subordinates (canary< bird)
• For reasons of cognitive economy, subordinates inherit all the
attributes of their superordinate concepts
• Some instances of a concept are excepted from the attributes that help
[humans] to define the superordinates (e.g. ostrich is excepted from flying)
• Various [psychological] processes search these hierarchies for
information about the concepts represented
9
KNOWLEDGE REPRESENTATION
: NETWORKS& MEANING
A Hierarchical Network
•
canary
is-a
is-a
bird
can fly, has wings,
has feathers
animal
ostrich
runs fast, cannot fly,
is tall
is-a
can breathe, can eat,
has skin
is-a
can sing, is yellow
is-a
fish
can swim, has fins, has gills
salmon
lays eggs; swims upstream,
is pink, is edible
10
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
canary
is-a
can sing, is yellow
bird
is-a
can fly, has wings,
has feathers
ostrich
runs fast, cannot fly,
is tall
animal
is-a
can breathe, can eat,
has skin
is-a
is-a
fish
can swim, has fins, has gills
salmon
lays eggs; swims upstream,
is pink, is edible
•From the above taxonomic organisation of knowledge about a
number of different animals, and one can conclude, by ‘inheriting
properties down the taxonomy’, that canaries, ostriches and
salmon all have skin and can breathe.
•But we as humans can also make exceptions to inherited
properties in that we can represent an unflighted bird in a (sub-)
11
hierarchy of birds by simply noting the exception, 'can't fly'.
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
canary
is-a
can sing, is yellow
bird
is-a
can fly, has wings,
has feathers
ostrich
runs fast, cannot fly,
is tall
animal
is-a
can breathe, can eat,
has skin
is-a
is-a
fish
can swim, has fins, has gills
salmon
lays eggs; swims upstream,
is pink, is edible
Collins and Quillian showed carried out a number of test on
human subjects and found that the subjects recognise
propositions lower down the hierarchy (canary is a yellow
bird) as compared to propositions higher up the hierarchy
more readily than higher above (canary has skin).
12
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
A semantic network is a structure for representing knowledge as a
pattern of interconnected nodes and arcs. Nodes in the net
represent concepts of entities, attributes, events, values. Arcs in
the network represent relationships that hold between the concepts
•
canary
is-a
can sing, is yellow
bird
is-a
can fly, has wings,
has feathers
animal
runs fast, cannot fly,
is tall
is-a
can breathe, can eat,
has skin
is-a
ostrich
is-a
fish
can swim, has fins, has gills
salmon
lays eggs; swims upstream,
is pink, is edible
13
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Concepts labeled C111 and C112 inherit all the attributes of C11 which, in
turn, inherits all the attributes of C1; similarly C121 inherits attributes of
C12 and C12 of C1. All arcs are labeled is-a, which relates superordinates
(C1) to subordinates (C11, C12) to instances (C111, C112, C121).
•
C111
is-a
is-a
C111’s attributes
C11
C11’s attributes
C112
C1
C112’s attributes
is-a
C1’s attributes
is-a
is-a
C12
C12’s attributes
C121
C121’s attributes
14
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Quillian’s semantic network:
A graph theoretic data structure whose nodes
represent word senses and whose arcs express
binary semantic relationships between these
word senses.
Quillian gave an account, perhaps first used by
a computer scientist, of the associate features of
human memory that incorporated a spreading
activation model of computation.
15
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Type Hierarchies
Lattices: Sharon is an experimental physicist and
is a professional singer
Person
Artist
Performer
Scientist
Musician
Theorist
Singer
Experimentalist
Physicist
Lecturer
Sharon
16
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
The problem with the nets had been the interpretation associated
with the nodes which in turn relates to the two problems of
'logical' and 'heuristic' adequacy. There are five major area of
concerns here:
• First, what does or should the node represent: a class of objects or does the
node represent an instance of an object?
• Second, it is not clear whether the nodes represent the canonical instance of a
concept or does the node represent the set of all instances of the object.
• Third, the semantics of a link that define new objects and a link that relate
existing objects, particularly those dealing with 'intrinsic' characteristics of a
given object.
•Fourth, how does one deal with the problems of comparison between objects (or
classes of objects) through their attributes: essentially the problem of comparing
object instances:
•Fifth, what mechanisms there are to handle 'quantification' in semantic network
formalisms
17
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
The above five problem lead to the conclusion that the semantic
representation is beset by the twin problems of logical and
heuristic inadequacy:
• Logical inadequacy: A semantic network is
representationally inappropriate because the semantic nets
could not make many of the distinctions, even pretty simple
logical systems can make: between a specific instance of an
object, a class of objects, all objects, no object, some objects,
etc.
• Heuristic inadequacy: Semantic networks do not contain
the knowledge which helps in searching a given network
18
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Schema and Frames
The schema for the psychologist Otto Selz is a network
of concepts for 'guiding the thinking process', and for the
experimental psychologist Fredrick Bartlett it was an
active organisation of past experiences and reactions
used in thinking and in perception. In its later rendering
this notion of schema was taken over by AI researchers
during the 1950's and 1960's as a basic building block
for organising, storing and retrieving knowledge. There
are two dominant and interlinked themes to be found in
the knowledge representation literature of that time.
19
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Schema and Frames
The term frames appears to have at least five senses in
The Oxford Dictionary of Computing:
1.
The total amount of information presented in a display at any one time.
2.
……………………………………………..
5. A frame is a list of named SLOTS. Each slot can hold
a fact, a POINTER to a slot in another frame, a RULE
for deriving the value of the slot, or a PROCEDURE
for calculating the value.
Frames can be used to represent the knowledge about
a particular object or event
20
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Schema and Frames
Consider the following objects and events:
1. Bill is a cat;
2. Opus is a penguin
3. The year 2000 flood in Chichester
4. Sophie and Edward’s wedding.
21
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Schema and Frames
Living objects 1 & 2 can be described as follows:
Opus
member
Penguin
subset
Birds
subset
Animal
subset
Bill
member
Cat
subset
Mammals
22
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Schema and Frames
Events 3 & 4 can be described as follows:
Chichester
Flood
a kind of
Flood
a kind of
Disaster
a kind
of
Event
Sophie &
Edwards
Wedding
a kind of
Wedding
a kind of
Celebration
a kind
of
23
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Schema and Frames
Penguin
A semantic network
member
likes
Opus
Bill
A frame network
Penguin
member
Opus
likes
Bill
24
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Schema and Frames: Representing Instances
Birds
Penguin
subset
Legs
flight
2
Yes
Animal
subset
flight
No
Opus
subset
member
vitality
Yes
flight
No
likes
Bill
25
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Schema and Frames: Handling Exceptions
Mammals
Cats
subset
Legs
4
Feeds young
Yes
subset
Climbs trees
Yes
Bats
Animal
subset
subset
vitality
Yes
Legs
2
flight
No
flight
Yes
26
KNOWLEDGE REPRESENTATION:
NETWORKS& MEANING
Event
AKO
Time
Date
Inheritance
of
Properties
Place
Disaster
AKO
Damage
Fatalities
Flood
AKO
Fire
AKO
Earthquake
Depth
Engines
Magnitude
Area
Firemen
Fault
AKO
27