KNOWLEDGE ENGINEERING, PART A: Knowledge Representation

index

Lecture 3. Conceptual Graphs

3.1. Conceptual Graphs
3.2. Percepts and Concepts
3.3. Semantic Networks

3.1. Conceptual Graphs

In Conceptual Graphs,

the concept nodes represent entities, attributes, states, and events; and
the relation nodes show how the concepts are interconnected.

3.2. Percepts and Concepts

Perception is the process of building a working model that represents and interprets sensory input.
The model has two components:

a sensory part formed from a mosaic of percepts, each of which matches some aspect of the input; and
a more abstract part called conceptual graphs, which describes how percepts fit together to form a mosaic.

Perception is based on the following mechanisms:

stimulation is recorded for a fraction of a second in a form called a sensory icon;
the associative comparator searches long-term memory for percepts that match all or part of an icon;
the assembler puts the percepts together in a working model that forms a close approximation to the input. A record of the assembly is stored as a conceptual graph; and
conceptual mechanism process concrete concepts that have associated percepts and abstract concepts that do not have any associated percepts.

When a person sees a cat, light waves reflected from the cat received as a sensory icon s. The associative comparator matches s either to a single cat percept p or to a collection of percepts, which are combined by the assembler into a complete image. As the assembler combines percepts, it records the percepts and their interconnections in a conceptual graphs.
3.1.1 Assumption. The process of perception generates a structure u called a conceptual graph in response to some external entity or scene e:

the entity e gives rise to a sensory icon s;
the associative comparator finds one or more percepts p₁,p₂,...,p_n that match all or part of s;
if such a working model can be constructed, the entity e is said to be recognised by the percept p₁,p₂,...,p_n;
for each percept p_i in the working model, there is a concept ci called the interpretation of p_i; and
the concepts c₁,c₂,....,c_n are linked by conceptual relations to form the conceptual graph u.

Percepts are fragments of images that fit together like the pieces of a jigsaw puzzle.
A conceptual graph describes the way p percepts are assembled.
Conceptual relations specify the role that each percepts play.
In diagrams, a concept is drawn as a box, a conceptual relation as a circle, and an arc as an arrow that links a box to a circle.
In linear text, the boxes may be abbreviated with square brackets, and the circles with round parentheses.

[CONCEPT1] -> (REL) -> [CONCEPT2]

In English, it is read as: the REL of a CONCEPT1 is a CONCEPT2.
Conceptual relations may have any number of arcs, although most of the common ones are dyadic.
Conceptual graphs are finite, connected, bipartite graphs.

they are finite because any graph in the human brain or computer storage can have only a finite number of concepts and conceptual relations;
they are connected because two parts that were not connected would simply be called two conceptual graphs; and
they are bipartite because there are two different kinds of nodes - concepts and conceptual relations - and every arc link a node of one kind to a node of the other kind.

3.1.2 Assumption. A conceptual graph is a finite, connected, bipartite graph.

the two kinds of nodes of the bipartite graph are concepts and conceptual relations;
every conceptual relation has one or more arcs, each of which must be linked to some concept;
if a relation has n arcs, it is said to be n-adic, and its arcs are labelled 1,2,3,...,n. The term monadic is synonymous with 1-adic, dyadic with 2-adic, and triadic with 3-adic; and
a single concept by itself may form a conceptual graph, but every arc of every conceptual relation must be linked to some concept.

For concrete entities like CATS and TOMATOES, the brain has percepts for recognising the entity and concepts for thinking about it.
For abstract types like JUSTICE and HEALTH, only imageless concepts, not percepts, are available.
3.1.3 Assumption. For every percept p, there is a concept c, called the interpretation of p. The percept p is called the image of c. Some concepts have no images.

If a concept c has an image p, then c is called a concrete concept.
If the concept c has no image, then c is called an abstract concept.
The image of the interpretation of a percept p is identical to p.
Entities recognised by the image of a concrete concept c are called instances of c.

Besides using conceptual graphs for interpreting sensory icons, the brain can also use them for generating or imagining new icons that were never before seen or heard.
3.1.4 Assumption. Let u be a conceptual graph, whose concepts c₁,...,c_n are all concrete. Then the graph u can serve as a pattern for a neural excitation t called an imagined icon. The icon t is identical to a sensory icon s with the following properties:

The icon s may be matched by percepts p₁,...,p_n where p_i is the image of the concept c_i in the graph u.
In matching the percept p₁,...,p_n to s, the assembler would construct a conceptual graph v identical to u.

3.3. Semantic Networks

Although the concept types CAT and TOMATO map directly to percepts, other types like PRICE, FUNCTION, and JUSTICE have no sensory correlates.
Abstract concepts acquire their meaning not through direct associations with percepts, but through a vast network of relationships that ultimately links them to concrete concepts.
The collection of all the relationships that concepts have to other concepts, to percepts, to procedures, and to motor mechanisms is called the semantic network.
A conceptual graph has no meaning is isolation. Only through the semantic network are its concepts and relations linked to context, language, emotion, and perception.
Example: a cat sitting on a mat.

Example: a monkey eating a walnut with a spoon made out of the walnut's shell.

In linear form:

[EAT]- 
      (AGNT) -> [MONKEY} 
      (OBJ) -> [WALNUT:*x] 
      (INST) -> [SPOON] -> (MATE) -> [SHELL]] <- (PART ) <-[WALNUT:*x]

The symbol *x is called a variable.
Normally, the entire semantic network is not drawn explicitly because it is too large and unwieldy. Instead, each concept box contains a label that shows the type, and two boxes with the same type label represent concepts of the same type.
The distinction between type labels and concepts follows the distinction between types and tokens drawn by Peirce (1906): the word cat is a type, and every utterance of cat is a new token. Similarly, each occurrence of a concept is a separate token.
3.2.1 Assumption. The function type maps concepts into a set T, whose elements are called type labels. Concept c and d are the same type if type(c) = type (d).
All the things in the real world that are instances of a type constitute the denotations of that type.
3.2.2 Definition. Let t be a type label. The denotation of type t, written dt, is the set of all entities that are instances of any concept of type t.
Any percept that matches a broad range of icons is more general than one that matches only a subrange.
The image of type RED is a percept that matches an infinite variety of hues, including those matched by percepts for STRAWBERRY-RED, FIRE-ENGINE-RED, CRIMSON, and SCARLET.
Since RED is the label of a more general concept than CRIMSON, the type CRIMSON is called a subtype of RED.
The denotation of CRIMSON is a subset of the denotation of RED: dCRIMSON is contained in dRED.
The symbol £ represents subtype:

CRIMSON

RED, and RED >= CRIMSON.

Every type is a subtype of itself:

RED

3.2.3 Assumption. The type hierarchy is a partial ordering defined over the set of type labels. The symbol £ designates the ordering. Let s, t and u be type labels:

if s £ t, then s is called a subtype of t; and t is called the supertype of s, written t >= s;
if s £ t and s =/= t, then s is called a proper subtype of t, written s < t; and t is called a proper supertype of s, written t > s;
if s is a subtype of t and a subtype of u (s £ t and s £ u), then s is called a common subtype of t and u; and
if s is a subtype of t and a subtype of u (s >= t and s >= u), then s is called a common supertype of t and u.

In AI, the type hierarchy supports the inheritance of properties from supertypes to subtypes of concepts.
Corresponding to the type hierarchy for concepts is an approximation hierarchy for percepts.
A percept for a general type RED makes an approximate match to many different icons. A percept for the subtype CRIMSON matches fewer icons, but it matches them more exactly.
3.2.4 Assumption. The approximation hierarchy is a partial ordering of percepts induced by the partial ordering of concept types. If the percept p is the image of a concept of type s, and q is the image of a concept of type t where s £ t, then define p £ q. The following conditions hold:

Any entity recognised by p is also recognised by q.
Hence, the denotation of s is a subset of the denotation of t: |ds| < |dt|,
If an icon i is matched by both percepts p and q, the percept p forms a more exact match to i than the percept q.

The types CAT and DOG have many common supertypes, including ANIMAL, VERTEBRATE, MAMMAL, and CARNIVORE.

ANIMAL | VERTEBRATE | MAMMAL | CARNIVORE / \ CAT DOG

The minimal common supertype of CAT and DOG is CARNIVORE, which is a subtype of all the other supertypes.
The concept type FELINE and WILD-ANIMAL have common subtypes JAGUAR, LION, and TIGER; but none of them is a maximal common subtype.

The type hierarchy could be refined, by adding the type WILD-FELINE, which would be a maximal common subtype of FELINE and WILD- ANIMAL.

3.2.5 Assumption. The type hierarchy forms a lattice, called the type lattice:

Any pair of type labels s and t has a minimal common supertype, written s U t.

Any pair of type labels s and t has a maximal common subtype, written s ^ t.

For any type label u, if u

s and u

t, then u

s ^ t.

There are two primitive type labels; the universal type T and the absurd type ^.

For any type label t,

^ £

The types CAT, DOG, MAMMAL, and ANIMAL are natural types that relate to the essence of the entities.
The types like PET, PEDESTRIAN, and SPOUSE are role types that depend on an accidental relationship to some other entity.
Natural types and role types both occur in the same type lattice.
The maximal common subtype of CAT and PET is PET-CAT; the minimal common supertype of PET-Cat and PET-DOG is PET- CARNIVORE.
A lattice must have a minimal common supertype and maximal common subtypes. This is why we have a universal type and the absurd type.
Many people confuse types and sets.
Statements about types are analytic; they must be true by intention.
Statements about sets are synthetic; they are verified by observing the extensions.
The type lattice represents categories of thought, and the lattice of sets and subsets represent collections of existing things. (Ref to page 83 for examples).
3.2.6 Theorem. Let s and t be any type label. Then d(s U t) is a superset of ds U dt, and d(s ^ t) is a subset of ds ^ dt.

By definition, both s and t are subtypes of s U t.
Any element of ds or of dt must be an element of d(s U t).
Therefore, (ds U dt) >= d(s U t).
Since s ^ t is a subtype of both s and t, any element of d(s ^ t) must be an element of ds and of dt.

(s ^ t)

(

s ^

Conceptual relations are classified in the same way that concepts are classified. A hierarchy is also defined over type labels for conceptual relations.
Example: a general relation type LOC for location may have subtypes that specify more details about location, such as IN, ABOV, and UNDR
3.2.7 Assumption. The function type may be extended to map conceptual relations to type labels.

The relations r and s are said to be of the same type if type(r) = type(s).
If r and s are of the same type, they must have exactly the same number of arcs.
For any concept c and conceptual relation t, type(c) =/= type(r).
The partial ordering of type labels also extends to type labels of conceptual relations, but the type labels of concept have no common supertypes with the type labels of conceptual relations.

Dickson Lukose &

Rob Kremer . KNOWLEDGE ENGINEERING, PART A: Knowledge Representation. July 1996.

index