| KNOWLEDGE ENGINEERING, PART A: Knowledge Representation |
index
|
Lecture 6. Conceptual
Graphs
6.1. Abstraction and Definition
-
Type definitions provide a way of
expending a concept in primitives or contracting
a concept from a graph of primitives.
-
Definitions can specify a type in
two different ways: by stating necessary
and sufficient conditions for the type, or by giving a few examples
and saying that every thing similar to these belongs to the type.
-
Definitions by genus and differentia
are logically easiest to handle.
eg. REL (Thompson & Thompson,
1975);OWL (Martin, 1979); MCHINE (Ritchie, 1980)
-
Definitions by examples or prototypes
are essential for dealing with natural
language and its applications to the real world, but their logical
status is unclear.
eg. KRL (Bobrow & Winograd,
1977); KL-ONE (Brachman, 1979); TAXMAN
(McCarty & Sridharan, 1981)
-
Conceptual graphs support type definitions
by genus and differentiae as
well as schemata and prototypes, which specify sets of family resemblances.
-
Both methods are based on abstractions,
which are canonical graphs with
one or more concepts designated as formal parameters.
-
3.6.1 Definition. An n-adic
abstraction, la1,.....,an
in u, consist of a canonical
graph u, called the body, together with a list of generic
concepts a1,....,an
in u, called formal parameters. The parameter list following
l
distinguishes the formal parameters from the other concepts
in u.
-
Example:
lx,y [SUPPLY] -
(AGNT) -> [SUPPLIER:*x]
(OBJ) -> [PART:*y] -> (COLR) -> [RED]
In this example, lx,y
identifies [SUPPLIER:*x] and [PART:*y] as formal
parameters. The concepts [SUPPLY] and [RED], which are not parameters,
are like local variables in a procedure or function.
The body of an abstraction is a conceptual
graph that asserts some proposition.
When n formal parameters are identified,
the abstraction becomes an n-adic
predicate, which is true or false only when specific referents are
assigned to its parameters.
3.6.2. Assumption. The formula
operator f
maps n-adic abstractions into
n-adic lambda expressions:
-
Let la1,.....,an
u be an n-adic abstraction.
-
Let x1,....,xm
be variables assigned to the generic concepts of u other
than the formal parameters.
-
Remove the quantifiers from the formula
f
to leave the predicate F.
Then fla1,.....,an
u is the lambda expression, la1,.....,an
$x1....$xmF
For the abstraction relating to suppliers and parts in the previous example,
the formula operator f
would generate the following l-expression
in standard logic:
lx,y$z$w(SUPPLY(z)
^ AGNT(z,x) ^ SUPPLIER(x) ^ OBJ(z,y) ^
PART(y) ^ COLR(y,w) ^ RED(w)).
3.6.3 Assumption. A generalisation hierarchy is defined over abstractions.
For a pair of n-adic abstraction, la1,...,an
u £
lb1,....,bn
v if the following conditions hold:
-
For the two bodies, u £
v.
-
There exist a projection p
of v into u, which for all i maps the parameters
bi of v into the parameters ai of u.
New type labels are defined by an
Aristotelian approach. Some type of concept
is named as the genus, and a canonical graph, called the differentiae,
distinguishes the new type from the genus.
Example:
Defines KISS with genus TOUCH
and with a differentia graph that says
that the touching is done by a person's lips in a tender manner.
-
3.6.4 Assumption. A type
definition declares that a type label t is defined
by a monadic abstraction la
u. It is written, type t(a) is u. The body u is called
the differentiae of t, and type(a) is called the genus
of t. The abstraction la
u may be written in the type field of any concept where the
type label t may be written.
-
Examples:
-
Define the label CIRCUS-ELEPHANT as subtype of ELEPHANT that perform in
a circus:
type CIRCUS-ELEPHANT(x) is
[ELEPHANT:*x]<-(AGNT)<-[PERFORM]->(LOC)->[CIRCUS].
-
If [CIRCUS] had been marked as the
formal parameter, it would define
a type of CIRCUS that had a performing elephant:
type ELEPHANT-CIRCUS(y) is
[ELEPHANT]<-(AGNT)<-[PERFORM]->(LOC)->[CIRCUS:*y].
-
If [PERFORM] had been marked as the
parameter, it would define
a type of performance that an elephant does in a circus:
type ELEPHANT-PERFORMANCE(z)
is
[ELEPHANT]<-(AGNT)<-[PERFORM:*z]->(LOC)->[CIRCUS].
-
An important use for type definition
is to describe a subrange that limits
the possible referents for a concept. The type POSITIVE, for example,
could be defined as a number that is greater than zero:
type POSITIVE(x) is [NUMBER:*x]
->(>)->[NUMBER:0]
-
To avoid the need for defining a
special type label for every subrange, the
abstraction that defines a type may be used in the type field of a
concept without associating it with
a particular label.
[lx
[NUMBER:*x]->(>)->[NUMBER:0]: 15].
-
Once a mechanism is available for
defining new types, the definitions can
be used to simplify the graphs.
-
Type contraction deletes a complete
subgraph and incorporates the equivalent
information in the type label of a single concept.
-
If some graph u happens to
contain a subgraph u' that corresponds to the
body of some type definition t = lav,
then redundant parts of u' may
be deleted. In its place, the concept of u' that corresponds to
the parameter a of
v has its type label replaced with t.
-
3.6.4 Assumption. Let u
be a canonical graph, and let the type t defined
as lav.
If u is a specialisation of v, p
is a projection of v into u, and
type(pa)
= type(a), then the operation
of type contraction may be performed
on u by the following algorithms:
replace the type label of pa with t;
leave referent(pa) unchanged;
for b in the concepts and conceptual relations of v where
b=/=a, pb identical to b, and pb not a cutpoint of u loop
if b is a concept then
detach pb from u;
else
detach pb and all its arcs from u;
end if;
end loop;
for e in the arcs left in u not linked to a concept loop
reattach the concept that had been linked to arc e in u;
end loop;
For example, let u be the graph:
[GRAY]<-(COLR)<-[ELEPHANT:Clyde] -
<-(AGNT)<-[PERFORM]->(LOC)->[CIRCUS]
Let v be the differentia for
defining CIRCUS-ELEPHANT:
[ELEPHANT:*x]<-(AGNT)<-[PERFORM]->(LOC)->[CIRCUS]
The following graph is the projection
pv
into u:
[ELEPHANT:Clyde]<-(AGNT)<-[PERFORM]->(LOC)->[CIRCUS]
The concept [ELEPHANT:Clyde] is pa,
which is the projection of the genus concept [ELEPHANT:*x] of v.
The next stage of type contraction replaces the type label of pa
to form the graph:
[GRAY]<-(COLR)<-[CIRCUS-ELEPHANT:Clyde] -
<-(AGNT)<-[PERFORM]->(LOC)->[CIRCUS].
The for loop will now detach concepts
and conceptual relations to form the
following graph:
[GRAY]<-(COLR)<-[CIRCUS-ELEPHANT:Clyde]
If type contraction is performed
on a canonical graph, the resulting graph
is also canonical. The notation [lav:i]
represents the contracted form
of the concept pa,
where the type is lav,
and the referent i is the original referent(pa).
Type contraction deletes subgraphs that can be recovered from information
in the differentia.
Type expansion replaces a concept type with its definition. The
type label of the genus replaces the defined type label, and the graph
for the differentia is joined to the concept.
3.6.6 Definition. Let u be a canonical graph containing a
concept a where type(a) = lbv.
Then minimal type expansion consist of joining the graphs u and
v on the concepts a and b.
This is achieved by restricting b
to type(a) and then doing a join.
Note that a type contraction followed
by a minimal type expansion is not
identical to the original - as it may contain a subgraph, and the
type label of concept a is
not restored.
3.6.7 Definition. A maximal
type expansion starts with a minimal type expansion
and takes the following additional steps. Let a,b,u and v
satisfy the same hypothesis as in
Definition 3.6.6.
-
Extend the join of a and b
to a maximal join.
-
Replace the type label of concept
a with the type label t, where type(a)
£
t £ type(b),
the result of replacing type(a) with t is canonical,
and there is no type s where t<s£type(b)
and the result of replacing
type(a) with s would be canonical.
Example: Consider the graph "Joe
buying a necktie from Hal for $10".
Consider the type definition graph
for BUY shown below:
-
The type expansion of the graph based
on the concept type BUY is shown
below:
-
3.6.8 Assumption. If type
t is defined as la
u, the position of t in the type hierarchy is determined
by the following conditions:
-
If the graph u consists of the single concept a, then t
= type(a).
-
If u is larger that the single concept a, then t <
type(a).
-
Type contraction is commutative; if the graph u is derivable by
joining canonical graphs v and w on the concept a,
then la
u = l[la
v]w = l[la
w]v.
-
3.6.9 Assumption. A type hierarchy T is said to be
Aristotelian if every type label t that is a proper subtype of another
type label is defined by an abstraction t = la
u.
-
3.6.10 Assumption. In an Aristotelian type hierarchy, if a type
label s is a proper subtype of t (s < t), then
there exists a type definition s = la
u, where type(a) = t. The graph u is called the
differential between s and t.
-
3.6.11 Theorem. If the type hierarchy is Aristotelian, then any
graph that is canonically derivable by restricting a type label to a subtype
could also be derived by a join followed by a type contraction.
-
3.6.12 Assumption. A relational definition, written relation
t(a1,....,an)
is u, declares that the type label t for a conceptual
relation is defined by the n-adic abstraction lai,....,an
u. The body u is called the relator of t. If
r is a conceptual relation of type t, the following conditions
must be true:
-
r has n arcs.
-
If ci is a concept linked to arc i, type(ci)
<= type(a).
-
Example 1: monadic relation
relation PAST(x) is (g1)
[SITUATION:*x]->(PTIM)->[TIME]->(SUCC)->[TIME:now]
Example 2: dyadic relation
relation QOH(x,y) is
[PART_NO:*x] -
<- (CHRC) <- [ITEM:{*}] - (g2)
-> (QTY) -> [NUMBER:*y]
-> (LOC) -> [STOCKROOM]
In an Aristotelian type hierarchy,
all relational definitions could be reduced
to a single dyadic relation type, LINK. Even linguistic relations
like (AGNT) could be defined in terms
of a concept type AGENT:
relation AGNT(x,y) is
[ACT:*x] <- (LINK) <- [AGENT]->(LINK)->[ANIMATE:*y].
3.6.13 Assumption. In an Aristotelian
type hierarchy T, there is a type
label LINK for a dyadic conceptual relation. If t is a type label
for a conceptual relation
and t ð
LINK, then there exist a definition, relation
t(a1,.....,an) is u.
3.6.14 Assumption.
The operation of relation contraction replaces a subgraph
v of a conceptual graph w with a single conceptual relation
r and the concepts linked
to its arcs. Let b1,....,bn be n distinct
concept of v, let v
have no arcs linked to concepts in w - v, and let u be a
copy of v with the
concepts b1,....,bn replaced by generic concepts
a1,.....,an where each
bi is a subtype of ai. Then relational
contraction consists of the following
steps:
-
Delete all of v from w
except for b1,....,bn.
-
Let type(r) = la1,.....,an
u.
-
For each i, link arc i
of r to concept bi.
If relational contraction is performed
on a canonical graph, the resulting
graph is canonical.
-
Example:
The relators in g2 may be contracted
to
[PART-NO] ->(QOH)->[NUMBER]. (g3)
3.7.15 Definition. The operation
of relational expansion replaces a
conceptual relation and its attached concepts with the relator of a
relational definition. Let w
be a conceptual graph containing a conceptual
relation r where type(r) = la1,....,an
u. Then relational
expansion consists of the following
steps:
-
Detach r and its arcs from
w.
-
For each i, if bi
is the concept that was linked to arc i of r, then
restrict ai to
type(bi).
-
For each i, join the restricted
form of ai to bi.
Example:
The graph g3 may be expended
to the following:
[PART_NO] -
<- (CHRC) <- [ITEM] - (g4)
-> (OTY) -> [NUMBER]
-> (LOC) -> [STOCKROOM]
6.2.
Aggregation and Individuation
-
3.7.1 Assumption. The referent
of a concept c may be a set, every element
of which must conform to type(c). If c is an individual concept
with referent i, the operation
of set coercion changes the referent of c to
the singleton set {i}.
-
3.7.2 Assumption. Let a
and b be two concepts of the same type whose
referents are sets. Then a and b may be joined by the operation
of set join: first perform a
join on the concepts a and b; then change the referent
of the resulting concept to the union of referent(a) with
referent(b).
-
3.7.3 Assumption. The symbol
{*} represents a generic set of zero or
more elements, which may occur as the referent of a concept. Set unions
with {*} obey the following rules:
-
Empty set. {} U {*} = {*}.
-
Generic set. {*} U {*} = {*}.
-
Set of individuals. {i1,....,in}
U {*} = {i1,....,in,*}.
-
The set {i1,....,in,*} is
called a partially specified set, which consists of the elements
i1,....,in plus some unspecified other.
-
Just as measure contraction and name
contraction, the operation of quantity
contraction may be used to simplify set referents.
-
The symbol @ after a set shows
that the following number represents the
count of elements or cardinality of that set.
-
3.7.4 Assumption. If the referent
of a concept is a set, it may be one of
four different kinds:
-
A collective set - all elements of
a set participate in some relationship
together.
Example: Conceptual graphs with collective
set as referent
[PERSON:liz] <- (AGNT) <- [DANCE] (f8-1)
[PERSON:kirby] <- (AGNT) <- [DANCE] (f8-2)
[PERSON: {liz,kirby}] <- (AGNT) <- [DANCE] (f8-3)
A disjunctive set - one element of
the set is the actual referent
at any particular time.
Example: Conceptual graph with
disjunctive set as referent:
[PROPOSITION:
[ELEPHANT:Clyde] -> (STAT) -> [LIVE] -> (LOC) -> [CONTINENT: africa]
]
-> (OR) -> (f9-1)
[PROPOSITION:
[ELEPHANT:Clyde] -> (STAT) -> [LIVE] -> (LOC) -> [CONTINENT: asia]
]
[ELEPHANT:Clyde] -> (STAT) -> [LIVE] -> (LOC) -> [CONTINENT: {africa | asia}] (f9-2)
A distributive set - Each element
of a set satisfies some relation,
but they do so separately.
Example: Conceptual Graph with
distributive set as referent.
[PERSON:dist{betty,jerry}] <- (AGNT) <- [LAUGH] (f9-3)
A Respective set - Each element of
an ordered sequence bears
a particular relationship to a corresponding
element of another sequence.
Example: Conceptual Graph with
respective set as referent.
[PERSON:resp{john,jack}]
<- (AGNT)<- [STUDY] -> (SUBJ) -> [COURSE:resp{scp325,scp317}] (f9-4)
English used the word together
for the collective interpretation, each for
the distributive, and respectively for the respective.
A set is a loose association between
entities. There is no inherent connection
between the elements other than the fact that they occur in the
same collection.
Aggregation is a tighter form of
association.
A composite individual is an aggregation
of components that are linked
by conceptual relations.
The basis for an aggregation is some
type definition, which sets up a pattern
of concept and relation types:
type CIRCUS-ELEPHANT(x) is
[ELEPHANT:*x] <- (AGNT) <- [PERFORM] -> (LOC) -> [CIRCUS].
A composite individual [CIRCUS-ELEPHANT:jumbo]
is defined by filling in the
referent fields of generic concepts in the body of the type definition:
individual CIRCUS-ELEPHANT(jumbo)
is
[ELEPHANT:jumbo] <- (AGNT) <- [PERFORM:{*}]
-> (LOC) -> [CIRCUS: Barnum & Bailey]
3.7.5 Definition. Let t
= la
u be a type label; and let v be a canonical graph
where v £
u, pi is a projection from u into v, and pa
is an individual concept in v.
-
The graph v is called an aggregation of basic type t.
-
The projection p
from the differentia u
into the aggregation v is called
an individuation of t.
-
The individual i = referent(pa)
is called a composite individual.
-
For any concept c in u,
referent(pc)
is called the c component of the
composite individual i.
3.7.6 Definition. Let u
be a conceptual graph with a concept a in u where
referent(a) is a composite individual with aggregation v
and basis type type(a).
Then aggregation expansion consists of joining the concept
a of u to the concept of v whose referent is the same
as referent(a).
A type definition that includes concepts
whose type labels are the same as
the one being defined is said to be directly recursive.
If the definition contains type labels
that are supertypes of the one being
defined, then it is indirectly recursive.
Example of direct & indirect
recursive definition.
type LIST(x) is
[DATA:*x] -
(HEAD) -> [DATA]
(TAIL) -> [LIST].
By repeated type expansion of the
concept [LIST], the following graph could
be derived:
[LIST] -
(HEAD) -> [DATA]
(TAIL) -> [LIST] -
(HEAD) -> [DATA]
(TAIL) -> [LIST] -
(HEAD) -> [DATA]
(TAIL) -> [LIST].
Since LIST < DATA, the three concept
of type DATA could be restricted to
LIST and then expanded to form the following graph:
[LIST] -
(HEAD) -> [LIST] -
(HEAD) -> [DATA]
(TAIL) -> [LIST]
(TAIL) -> [LIST] -
(HEAD) -> [LIST] -
(HEAD) -> [DATA]
(TAIL) -> [LIST]
(TAIL) -> [LIST] -
(HEAD) -> [LIST] -
(HEAD) -> [DATA]
(TAIL) -> [LIST]
(TAIL) -> [LIST].
Such expansion could continue indefinitely.
The expansion of type DATA could
stop by restricting the type label to some
type of data other than list.
Expansion of type LIST could stop
by reaching an individual of type LIST
that could not be expanded further:
individual LIST(nil) is
(HEAD) <- [DATA:nil] <- (TAIL)
-> ->
Dickson Lukose,