Transcript Artificial Intelligence

Artificial Intelligence – CS364
Knowledge Representation
Lectures on Artificial Intelligence – CS364
Conceptual Dependency
20th September 2005
Dr Bogdan L. Vrusias
[email protected]
Artificial Intelligence – CS364
Knowledge Representation
Contents
•
•
•
•
Definition of Conceptual Dependency Grammar
Building blocks
Advantages and disadvantages
Exercises
20th September 2005
Bogdan L. Vrusias © 2005
2
Artificial Intelligence – CS364
Knowledge Representation
Concepts and Representation
• A number of authors in AI have addressed the question of
the 'concept'-based organisation of knowledge and we use
two examples to illustrate this:
– Firstly, we consider a verb-oriented organisation of knowledge
proposed by Schank: Conceptual Dependency Grammar.
– Then we go on to discuss a highly nominalised system proposed by
Sowa: Conceptual Graphs.
20th September 2005
Bogdan L. Vrusias © 2005
3
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Dependency
• Conceptual dependency (or CD) is a theory of how to
represent the meaning of natural language sentences in a
way that:
– First, facilitates for drawing inferences from the sentences.
– Second, the representation (CD) is independent of the language in
which the sentences were originally stated.
20th September 2005
Bogdan L. Vrusias © 2005
4
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Dependency Theory
• Schank's (1975) Conceptual Dependency Theory was developed as
part of a natural language comprehension project.
• Schank's claim was that sentences can be translated into basic concepts
expressed as a small set of semantic primitives.
• Conceptual dependency allows these primitives, which signify
meanings, to be combined to represent more complex meanings.
• Schank calls the meaning propositions underlying language
"conceptualisations".
20th September 2005
Bogdan L. Vrusias © 2005
5
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Dependency Theory
• Schank’s project is the ‘representation of meaning in an
unambiguous language-free manner’ (1973:187).
• ‘Any two utterances that can be said to mean the same
thing, whether they are in the same or different languages,
should be characterised in only one way by the conceptual
structure’ (1973:191)
• Towards a representation ‘in terms that are as interlingual
and as neutral as possible’ (ibid.)
20th September 2005
Bogdan L. Vrusias © 2005
6
Artificial Intelligence – CS364
Knowledge Representation
CD Building Blocks
• CD theorists argue that
– "the CD representation of a sentence is built not out of primitives
corresponding to the words used in the sentence, but rather out of
conceptual primitives that can be combined to form the meanings
of words in any particular language"
• Building Blocks
–
–
–
–
–
Primitive conceptualizations (conceptual categories)
Conceptual dependencies (diagrammatic conventions)
Conceptual cases
Primitive acts
Conceptual tenses
20th September 2005
Bogdan L. Vrusias © 2005
7
Artificial Intelligence – CS364
Knowledge Representation
Primitive Conceptualizations
• Schank emphasises analysis of a sentence/utterance at the
conceptual level or to analyse conceptualisation.
• Conceptual dependency theory of four primitive
conceptualizations:
– actions (ACT: actions)
– objects (PP: picture producers)
– modifiers of actions (AA: action aiders)
– modifiers of objects (PA picture aiders)
20th September 2005
Bogdan L. Vrusias © 2005
8
Artificial Intelligence – CS364
Knowledge Representation
Concept can be
• An abstract or concrete object that invokes an image
– "cars" are concrete objects
– "gravity" is an abstract concept
• An object (nominal) produces a picture (PP)
• Something an animate object does.
– "running" is an action
• A modifier that modifies an object or an action.
• A modifier that specifies an action or a nominal.
– "blue" is a PA modifier (e.g. A blue car)
– "quickly" is a AA modifier (e.g. He quickly run)
20th September 2005
Bogdan L. Vrusias © 2005
9
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Dependencies
• Conceptual categories (PP, ACT, PA and AA) relate to each other in
specified ways. These relations are called dependencies by Schank.
• In a dependency relation, one partner or item is dependent and the
other dominant or governing.
• A governor  dependent is a partially ordered relationship
– A dependent must have a governor and is understood in terms of the
governor
– A governor may or may not have dependent(s) and has an independent
existence
– A governor can be a dependent
• PP and ACT are inherently governing categories.
• PA and AA are inherently dependent.
20th September 2005
Bogdan L. Vrusias © 2005
10
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Dependencies
• For a conceptualisation to exist, there must be at least two
governors:
– E.g. Sally stroked her fat cat
PP:
ACT:
PA:
Sally, cat, her [Sally]
stroke
fat
Governors:
Dependent:
Sally, stroke, cat
PP (cat) on ACT (stroke)
PA (fat) on PP (cat)
PP (cat) on PP (her[Sally])
20th September 2005
Bogdan L. Vrusias © 2005
11
Artificial Intelligence – CS364
Knowledge Representation
Building CD graphs
• E.g. Sally stroked her fat cat
– Sally and stroking are necessary for conceptualisation: there is a
two-way dependency between each other:
Sally  stroke
– Sally’s cat cannot be conceptualised without the ACT stroke  it
has an objective dependency on stroke
Sally  stroke
20th September 2005
O


cat.
Bogdan L. Vrusias © 2005
12
Artificial Intelligence – CS364
Knowledge Representation
Building CD graphs
• E.g. Sally stroked her fat cat
– The concept ‘cat’ is the governor for the modifier ‘fat’:
Sally  stroke
O


cat

fat
– The concept PP(cat) is also governed by the concept PP(Sally)
through a prepositional dependency:
Sally  stroke
O


fat
20th September 2005
cat
 POSS-BY
Sally[her]
Bogdan L. Vrusias © 2005
13
Artificial Intelligence – CS364
Knowledge Representation
I
20th September 2005
Bogdan L. Vrusias © 2005
14
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Cases
• Dependents that are required by an ACT are called Conceptual Cases:
• There are four main conceptual cases:
–
–
–
–
Objective Case (O)
Recipient Case (R)
Instrumental Case (I)
Directive Case Relation (D)
20th September 2005
Bogdan L. Vrusias © 2005
15
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Cases
– Objective Case (O): "John took the book"
PP [John]
20th September 2005
ACT [took]
o
Bogdan L. Vrusias © 2005
PP [book]
16
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Cases
– Recipient Case (R): "John took the book from Mary"
PP [John]
ACT [took]
R
o
PP [book]
PP [John]
PP [Mary]
20th September 2005
Bogdan L. Vrusias © 2005
17
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Cases
– Instrumental Case (I): "John ate the ice cream with a spoon"
PP [John]
ACT [eat]
PP [John]
I
ACT [do]
o
o
PP [ice cream]
PP [spoon]
20th September 2005
Bogdan L. Vrusias © 2005
18
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Cases
– Directive Case Relation (D) "John drove his car to London from
Guildford"
PP [John]
PP [car]
ACT [do]
ACT [drove]
D
PP [London]
PP [Guildford]
POSS-BY
PP [John]
20th September 2005
Bogdan L. Vrusias © 2005
19
Artificial Intelligence – CS364
Knowledge Representation
Prepositional Dependency
Consider the following sentences:
Possession
e.g. "This is Sally’s cat":
Cat
 POSS-BY
Sally
Location
e.g. "Sally is in London":
London
 LOC
Sally
Containment
e.g. "The glass contains water":
20th September 2005
Water
 CONT
Glass
Bogdan L. Vrusias © 2005
20
Artificial Intelligence – CS364
Knowledge Representation
Primitive ACTs
Primitive Act
Elaboration
ATRANS
Transfer of an abstract relationship such as possession ownership or
control (give)
PTRANS
Transfer of the physical location of an object (go)
PROPEL
Application of a physical force to an object (push)
MOVE
Movement of a body part of an animal by that animal (kick)
GRASP
Grasping of an object by an actor (grasp)
INGEST
Taking in of an object by an animal to the inside of that animal (eat)
EXPEL
Expulsion of an object from the object of an animal into the physical
world (cry)
MTRANS
Transfer of mental information between animals or within an animal
(tell)
MBUILD
Construction by an animal of new information of old information
(decide)
CONC
Conceptualise or think about an idea (think)
SPEAK
Actions of producing sounds (say)
ATTEND
20th September 2005
Action of attending
focusing
a sense organ towards a stimulus (listen)
Bogdan L.orVrusias
© 2005
21
Artificial Intelligence – CS364
Knowledge Representation
Primitive ACTs
e.g. I gave a book to Sally
PP [I]
ACT [gave]
R
PP [Sally]
PP [I]
o
PP [book]
I
ATRANS
R
o
Sally
I
book
20th September 2005
Bogdan L. Vrusias © 2005
22
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Tenses
• Any conceptualisation can be modified as a whole by a
conceptual tense.
• John took the book (John  took) can be denoted by
looking at the lemma take (from which the past tense took
was derived):
p
John
20th September 2005
ATRANS
Bogdan L. Vrusias © 2005
23
Artificial Intelligence – CS364
Knowledge Representation
Conceptual Tenses
Symbol
Elaboration
"John will be taking the book":
p
Past
f
Future
t
Transition
ts
Start Transition
tf
Finished Transition
k
Continuing
?
Interrogative
/
Negative
nil
Present
delta
Timeless
c
Conditional
20th September 2005
taking
John
or
f
ATRANS
John
"John is taking the book":
taking
John
or
k
John
Bogdan L. Vrusias © 2005
ATRANS
24
Artificial Intelligence – CS364
Knowledge Representation
Summarising CD Building Blocks
E.g. I took a book from Sally
p
I
ATRANS
o
R
I
Sally
book
•
Primitive conceptualizations (conceptual categories):
– Objects (Picture Producers: PP): Sally, I, book
•
Conceptual dependencies (diagrammatic conventions):
– Arrows indicate the direction of dependency
– Double arrow indicates two way link between actor and action
•
Conceptual cases:
– "O" indicates object case relation
– "R" indicates recipient case relation
•
Primitive acts:
– ATRANS indicates transfer (of possession)
•
Conceptual tenses:
– "p" indicates that the action was performed in the past
20th September 2005
Bogdan L. Vrusias © 2005
25
Artificial Intelligence – CS364
Knowledge Representation
Semantic Nets Vs CD
• Semantic Nets only provide a structure into which nodes
representing information can be placed.
•
Conceptual Dependency representation, on the other hand,
provides both a structure and a specific set of primitives
out of which representations of particular pieces of
information can be constructed.
20th September 2005
Bogdan L. Vrusias © 2005
26
Artificial Intelligence – CS364
Knowledge Representation
Advantages of CD
• The organisation of knowledge in terms of the primitives
(or 'primitive acts') leads to a fewer inference rules.
• Many inferences are already contained in the
representation itself.
• The initial structure that is built to represent the
information contained in one sentence will have holes in it
that have to be filled in:
– holes which will serve as attention focusers for subsequent
sentences.
20th September 2005
Bogdan L. Vrusias © 2005
27
Artificial Intelligence – CS364
Knowledge Representation
Disadvantages of CD
• CD requires all knowledge to be broken down into 12 primitives:
sometimes inefficient and sometimes impossible.
• CD is essentially a theory of the representation of events: though it is
possible to have an event-centred view of knowledge but not a
practical proposition for storing and retrieving knowledge.
• May be difficult or impossible to design a program that will reduce
sentences to canonical form. (Probably not possible for monoids,
which are simpler than natural language).
• Computationally expensive to reduce all sentences to the 12 primitives.
20th September 2005
Bogdan L. Vrusias © 2005
28
Artificial Intelligence – CS364
Knowledge Representation
Exercises
• Please create the conceptual dependency representation of
the following sentences:
–
–
–
–
–
–
–
John ran
John is a Doctor
John’s Dog
John pushed the cart
Bill shot Bob
John ate the egg
John prevented Mary from giving a book to Bill
20th September 2005
Bogdan L. Vrusias © 2005
29
Artificial Intelligence – CS364
Knowledge Representation
Solution 1
• "John ran" (Schank and Colby 1973)
p
John
20th September 2005
PTRANS
Bogdan L. Vrusias © 2005
30
Artificial Intelligence – CS364
Knowledge Representation
Solution 2
• "John is a doctor" (Schank and Colby 1973)
John
20th September 2005
doctor
Bogdan L. Vrusias © 2005
31
Artificial Intelligence – CS364
Knowledge Representation
Solution 3
• "John’s Dog" (Schank and Colby 1973)
dog
POSS-BY
John
20th September 2005
Bogdan L. Vrusias © 2005
32
Artificial Intelligence – CS364
Knowledge Representation
Solution 4
• "John pushed the cart" (Schank and Colby 1973)
p
John
20th September 2005
PROPEL
o
cart
Bogdan L. Vrusias © 2005
33
Artificial Intelligence – CS364
Knowledge Representation
Solution 5
• "Bill shot Bob" (Schank and Colby 1973)
p
Bill
PROPEL
o
bullet
health(-10)
R
Rob
gun
Bob
p
20th September 2005
Bogdan L. Vrusias © 2005
34
Artificial Intelligence – CS364
Knowledge Representation
Solution 6
• "John ate the egg" (Schank and Rieger 1974).
p
John
o
INGEST
D
20th September 2005
egg
INSIDE
John
MOUTH
John
Bogdan L. Vrusias © 2005
35
Artificial Intelligence – CS364
Knowledge Representation
Solution 7
• "John prevented Mary from giving a book to Bill" (Schank
and Rieger 1974).
p
John
DO
c/
Mary
o
ATRANS
book
p
R
Bill
Mary
20th September 2005
Bogdan L. Vrusias © 2005
36
Artificial Intelligence – CS364
Knowledge Representation
Closing
•
•
•
•
Questions???
Remarks???
Comments!!!
Evaluation!
20th September 2005
Bogdan L. Vrusias © 2005
37