Frame-
Frames
a collection of semantic network nodes or slots that together describe a stereotyped object, act or event.
Representing knowledge about the objects and events typical to specific situations.
Organization facilitates expectation driven processing. (looking for things that are expected based on the context one thinks one is in).
Use of slots û places where knowledge fits within the larger context created by the frame.
Example:
CHAIR frame |
|
---|---|
A-kind-of: |
|
number-of-legs: |
|
style-of-back: |
|
number-of-arms: |
|
John's-chair frame |
|
---|---|
a-kind-of: |
|
number-of-legs: |
|
style-of-back: |
|
number-of-arms: |
|
Knowledge represented by frame
properties
inheritance hierarchies
e.g. a-kind-of slot (similar to is-a link
in semantic net)
expectation, e.g. a special "range" slot which specifies what you expect the value of the slot be.
attached
procedure:
a procedure knowledge which will fill-in the slot if
needed, or perform other tasks.
Example:
Generic Restaurant Frame |
|
---|---|
a-kind-of: |
|
Types: |
|
Location: |
|
Name: |
|
Food-style: |
|
Time-of-Operation: |
|
Payment form: |
|
Event-Sequence: |
|
Alternatives:: |
|
the range slot is an expectation about what kinds of things slot may contain.
the if-needed slot is an attached procedure that can be used to determine the slot's value if necessary.
Scripts: expectation about the sequences of events that are likely to take place:
Eat-at-Restaurant Script |
|
---|---|
Props: |
(Restaurant, Money, Food, Menu, Tables, Chairs) |
Roles: |
(Hungry-persons, Wait-persons, Chef-persons) |
Point-of-View: |
Hungry-persons |
Time-of-Occurrence: |
(Times-of-Operation of Restaurant) |
Place-of-Occurrence: |
(Location of Restaurant) |
Event Sequences: |
|
Class Hierarchies
2 kinds of frames:
instance frames
class frames
instance frame will inherit all slots from the class frames
class frame will inherit its superclass's slots
keep track of
class hierarchy:
e.g. when there are more than 1 superclasses
that can produce a slot û what to
use?
maintain a class-precedence list (ordered list)
Ambiguity is always resolved in favour of the most specific applicable procedure û i.e. the one that is encountered first in the class precedence list.
Requirement: a class should appear before all its superclasses.
Example:
Exhaustive Depth-first search
explore all paths, depth first, until each path reaches a leaf node or a previously encountered node
To prevent a class appear after its superclass: use up-to-join approach
Any class that is encountered more than once during the depth-first, left-to-right search is ignored until the class is encountered for the last time.
this approach may not preserve left-to-right ordering.
Add another requirement:
each direct superclass of a given class should appear on class-precedence lists before any other direct superclass that is to its right.
The depth-first, left-to-right,
up-to-join approach produces the following class-precedence lists for
Crazy and Jacque:
Crazy
Professors class
Eccentrics
class
Teachers class
Hackers class
Programmers class
Dwarfs
class
Everything class
Jacque
Weightlifters class
Athletes
class
Shotputters class
Endomorphs class
Dwarfs
class
Everything class
Suppose one is-a link and two ako links are added, as in figure 9.6, the class precedence lists for Crazy and Jacque are different:
Crazy
Professors class
Teachers
class
Hackers class
Eccentrics class
Programmers
class
Dwarfs class
Everything class
Jacque
Weightlifters class
Shotputters
class
Endomorphs class
Athletes class
Dwarfs
class
Everything class
Topological Sort
to flatten a partial order to form a total order
construct
adjacent pairs from the partial order:
e.g.
find a class that occupies the left side of a pair but that does not occupy the right side of any other pair. [leave nodes]. (*)
add it to the end of the precedence list and remove the pair.
repeat.
Note:
the class ordering is preserved
to preserve left-to-right ordering, add additional pairs:
If there is a tie in (*) i.e. more than 1 node satisfy the requirement,
choose the one that is a direct superclass of the rightmost class on the emerging class precedence list (tends to prevent erratic movement through the tree)
Node |
Fish-hook pairs |
---|---|
Crazy |
Crazy-Professors, Professors-Hackers |
Professors |
Professors-Eccentrics, Eccentrics-Teachers |
Eccentrics |
Eccentrics-Dwarfs |
Dwarfs |
Dwarfs-Everything |
Teachers |
Teachers-Dwarfs |
Hackers |
Hackers-Eccentrics, Eccentrics-Programmers |
Programmers |
Programmers-Dwarfs |
Everything |
Everything |
To
compute an instance's class-precedence list,
Create fish-hook pairs
Until all the fish-hook pairs are eliminated
Find the exposed classes
Select the exposed class that is a direct superclass of the rightmost class on the emerging class-precedence list.
Add the selected class tot he emerging class-precedence list.
Strike all fish-hook pairs that contain the newly added class.
To fill the slots in a new instance
compute the class-precedence list for the new instance using the topological sort procedure.
For each slot,
collect all when-constructed procedure for that slot
move along the class precedence list, from the most specific end. Stop when you encounter a class that is referred to by one of the slot-specific when-constructed procedure. Call this when-constructed procedure the most-specific when-constructed procedure for the slot
use that most specific when-constructed procedure.
Procedural Knowledge in Frames and Scripts
Filling-in Slots
primary process in a frame-based reasoning system is often just filling in the detail called for by its slots
directly inherited (through is-a link or a-kind-of slot)
by the default slot
computed using
the procedure attached through if-needed slots
(Lisp is
particularly suitable as Lisp codes and data are of the same form)
Advantages:
new frame can have values determined from experiences, without re-compute every time.
slot specific heuristic: general problem solving method can be augmented by domain specific knowledge.
filling in
slots provide confirmation that the frame or script is appropriate
for understanding the scene or event.
e.g. if the frame/script
is found to be inappropriate during slot filling, attached
procedure can trigger transfer of control to other frames.
Triggers
routines that are triggered when the value of a slot is found or changed.
implement
event- or data-driven processing, since they take over control when
certain event or data occur.
e.g. if-added procedure in foodstyle
slot of the generic restaurant frame: used to modify the list of
alternative restaurants once a particular cuisine is chosen.
attached to
special slots in the frame, used to decide what to do in the event
that the frame is found not to match the current situation.
e.g.
in eat-at-restaurant script, if discover a food line and a stack of
trays, it might trigger the eat-at-cafeteria script as being the
most appropriate.
Demon Procedures in a Frame System
When-constructed procedure
to fill-in default values of a slot by tracing the class hierarchy.
When-requested procedure
to override slot values, e.g.
when a value for the hobby slot of an athlete is requested, return exercise.
when a value for the hobby slot of a dwarf is requested
if the dwarf's personality slot is filled with shy, return reading
otherwise, return dancing.
3.When-read/When-written procedure
maintain
constraints
e.g. when a value is written in the physique slot of
an athlete, "if the new value is muscular, write large in the
athlete's apetite slot".
4.With-respect-to procedure
deal with
perspective and context
Example:
when a value for the
size slot of Blimpy, from the perspective of a typical dwarf, is
requested, return big.
when a value for the size slot of Blimpy,
from the perspective of a typical person, is requested, return
small.
when a value for
the mood slot of Patrick, in the context of Mountain Hiking, is
requested, return happy.
when a value for the mood slot of
Patrick, in the context of airplane travel, is requested, return
grumpy
A frame system is a presentation
That is a semantic net
In which
the language of nodes and links is replaced by the language of frames and slots
Ako slots define a hierarchy of class frames
Is-a slots determine to which classes an instance frame belongs
Various when-constructed, when requested, when-read, when-written, and with-repsect-to procedure supply default values, override slot values and maintain constraints.
A precedence procedure selects appropriate when-constructed, when-requested, when-read, when-written and with-respect-to procedures by reference tot he class hierarchy.
With constructors that
construct a class frame, given a list of superclasses, and a list of slots.
construct an instance frame, given a list of direct superclasses.
construct a when-requested, when-read, when-written, or with-respect-to procedure
With writers that
Establish a slot's value, given an instance, a slot and a value
With readers that
Produce a slot's value, given an instance and a slot.
Example: Digesting News
A net connecting frames for news stories:
Can apply the following rules to process a piece of news,
[Note that these are simple rules, and may not be always correct]
To fill the Time slot when a new Event is constructed,
Find a number with a colon in it and write it in the slot.
To fill the Fatalities slot when a new Disaster is constructed,
Find an integer near a word with a root such as kill or die, and write it in the slot
To fill the Damage slot when a new Disaster is constructed,
Find a number text to a dollar sign, and write it in the slot.
To fill the Magnitude slot when a new Earthquake is constructed,
Find a decimal number between 1.0 and 10.0, and write it in the slot.
To fill the Day slot when a new Event is constructed,
Find a word such as today, yesterday, tomorrow, or the name of one of the days of the week, and write it in the slot.
To fill the Place slot when a new Event is constructed,
Find a name that appears in a dictionary of geographical places and write that name in the slot.
To fill the Fault slot when a new Earthquake is constructed,
Find a proper name near the word fault and write it in the slot.
The above simple rules can be applied to the following piece of news:
The resulting frame structure is:
You can automatically set up a report by filling the slot to a template:
You can get the following:
The following points can usually be summarized for a good news report, which will help generating the required frame structure:
The title of a news story and perhaps the first sentence or two evoke a central frame.
Subsequent material fills slots in the central frame. The slot-filling process evoke other frames introducing more open slots.
Cause-effect relations are given explicitly. Readers do not need to deduce causes, because words such as because appear frequently.
Few pronouns, if any, are used. In political news, for example, the nations legislature may be referred to as "Congress", or "Capitol Hill", or "Washington's lawmakers", according to fancy.
Few new frames, if any, need to be constructed. Creating new frames requires reflection, and reflection is discouraged.
However, filling slots with simple, special-purpose procedure and without understanding can lead to silly results:
To summarize:
The slots in event frame make explicit what you should expect to know about them
The when-constructed procedures associated with event frames make explicit how you can try to acquire what you expect to know.
Thematic-Role Frames
In a sentence,
verb: specify actions
noun-phrase: identify the object that
participate the action
the noun-phrase's thematic role specify how it participate in the action.
Thematic roles focus on how noun phrases relate to actions.
A thematic-role system is a representation
that is a frame system
in which
the slots are, typically, verb, agent, coagent, beneficiary, thematic object, instrument, source, destination, old surroundings, new surroundings, conveyance, trajectory, time, location, and duration.
Each frame describes an action. The verb slot identifies the action. Other slots identify objects that play various roles with respect to the action.
Thematic roles:
Agent: cause the action to occur.
Subject or a prepositional phrase in passive sentences.
Coagent: a partner to the principal agent
usually follows "with".
e.g. Robbie played tennis with Suzie.
Beneficiary: for whom an action is performed
usually follows "for".
e.g. Robbie bought the ball for Suzie
Thematic object: the object with which the sentence is really all about.
Object, or subject in a passive sentence.
e.g. Robbie hit the ball
Instrument: a tool used by the agent.
Usually follows "with"
e.g. Robbie hit a ball with a racket.
Source and destination: change in physical location
usually follows "from" and "to"
e.g. Robbie went from the dining room to the kitchen
Old surroundings and new surroundings
the old surroundings is the location "out of" which something comes. The new surrounding is the location "into" which it goes.
e.g. Robbie took the cereal out of the box and put it into the bowl.
Conveyance: on which one travels.
Usually follows "by"
e.g. Robbie always go by train.
Trajectory: Motion from source to destination.
e.g. Robbie and Suzie went in through the front door.
Location: where the action occurs.
Several preposition are possible, each convey additional meanings.
e.g. Robbie and Suzie studied in the library, at a desk, by the wall, under a picture, near the door.
Time: specifies when an action occurs.
Usually signaled by "at", "before", "after" etc.
Duration: how long an action takes
usually follows "for"
e.g. Robbie and Suzie jogged for an hour.
Many questions are easy to answer once values for thematic-role slots are worked out.
E.g. consider the sentence:
Robbie made coffee for Suzie with a percolator.
There are 4 noun phrases, each of which fits into a particular role.
Four corresponding questions can be answered:
What was
made? 0 thematic object 0 coffee
Who
made it? 0 agent 0 Robbie
With
what was it made? 0 instrument 0 a
percolator
For whom was it made? 0 beneficiary 0 Suzie
Consider another example
Robbie went to the theatre with Suzie by car.
Who
went? 0 agent 0 Robbie
With
whom did he go? 0 coagent 0 Suzie
To
where did he go? 0 destination 0 the
theatre
By what means did they travel? 0 conveyance 0 car
Establish Thematic Roles
for simple English sentences, many constraints helps to establish the thematic role of any given noun phrases.
Some possible rules:
Each verb carries strong preferences about what thematic roles can appear and where the noun phrase that fill those thematic roles can be placed relative to the verb.
Prepositions
limit a noun phrases's role possibilities.
Preposition |
Allowable thematic role |
---|---|
by |
agent or conveyance or location |
with |
coagent or instrument |
for |
beneficiary or duration |
from |
source |
to |
destination |
the noun itself may limit possible role identification.
e.g. compare
Robbie was sent to the scrap heap by Parcel post. [conveyance]
Robbie was sent to the scrap heap by Marcel Proust. [agent]
Only one filler is allowed in any sentence for most thematic role [unless a conjunction is spotted].
if somehow, the thematic role of one noun phrase is determined, then the other noun phrases in the sentence are forced to fill other thematic roles.
Establishing Verb Meaning
verb can have more than one meaning.
noun phrase in the thematic-object thematic role can help establishing verb meaning.
e.g. He shot the
rabbit (by gun)
He shot the picture (by camera)
by a small family of words called particles (usually involve prepositions).
e.g. He threw some
food.
He threw away some food.
He threw up some food.
He
picked up some candy.
He picked out a nice assortment.
by a coarse categorization of life's subjects into a few world:
The Physical World
where objects change position, can acquire and lose various properties and relations to other objects
other world relate to physical world through analogy.
The Mental World
facts, ideas and concepts
actions, properties and relations borrowed from the physical world through abstraction.
e.g. The theory
was supported by facts.
The overall concept is solid.
The
idea was exposed in the class.
The Ownership World
abstract certificates of control, possession or ownership.
e.g. Robbie took
the ball away from Boze [physical]
The bank took the
house back [ownership]
Sentence Analysis
Use various constraints to establish noun phrase thematic role and the meaning of the verb.
Note that the thematic role is usually the noun phrase without preposition
If sentence is passive, thematic object is in front of the verb (subject). If sentence is active, thematic object is after the verb.
Thematic role of other noun phrase can be established by, e.g. inspection of prepositions.
To determine thematic roles,
Obtain possible verb meanings from the dictionary. Throw away those verb meanings that are inconsistent with the verb's particle, if there are any.
Find the thematic object among the preposition-free noun phrases.
Throw away the verb meanings that the dictionary says are inconsistent with the thematic object.
For each remaining noun phrase, determine the thematic role.
Throw away the verb meanings that the dictionary says are inconsistent with the observed thematic roles.
Example:
Consider a small world:
and consider the following simple constraints:
Thematic role |
Preposition |
Allowed class |
---|---|---|
agent |
by |
person |
coagent |
with |
person |
beneficiary |
for |
person |
thematic object |
- |
- |
instrument |
with |
inanimate |
source |
from |
- |
destination |
to |
- |
old surroundings |
out of |
inanimate |
new surroundings |
into |
inanimate |
conveyance |
by |
inanimate |
duration |
for |
a time |
And in the dictionary, the word take has the following meanings:
Take1 means transport. Either a source or a destination or both should appear.
Take2 means swindle. The source and destination roles are absent when this meaning is intended. Only people can be swindled.
Take3 means to swallow medicine. The available medicines include aspirin. The beneficiary is the same as the agent.
Take4 means to steal. People are not stolen.
Take5 means to initiate and execute a social event with another person. The particle out is always used.
Take6 means to remove. The particle out is always used. People cannot be removed.
Take7 means to assume control. The particle over signals this meaning.
Take8 means to remove from the body. The particle off is always used.
Robbie took aspirin
meanings Take5 to Take8 are eliminated, because there is no particle.
Evidently
Robbie is the agent and aspirin is the thematic object
[by virtue
of word order and lack of alternatives].
Take1 is unlikely, because no noun phrases that can be either the source or the destination of a transporting action.
Take2 is out, because aspirin is not a subclass of people and hence cannot be swindled.
Thus the sentences means that Robbie either swallowed or stole aspirin.
Robbie took aspirin for Suzie
Robbie is the agent and aspirin is the thematic object [by word order ...]
Only Take3 and Take4 survive particle and thematic considerations.
Preposition for can flag either beneficiary or duration.
Suzie is not time, she must be beneficiary, hence eliminating Take3 (because swallow medicine requires agent=beneficiary)
Robbie has stolen.
Robbie took out Suzie
The paritcle limits the verb meaning to Take5 ane Take6 (to date or to remove).
Take6 requires an inanimate thematic object. So Robbie dated Suzie.
Robbie took out the box
A box is inanimate, hence it is removed not dated.
Robbie took the ball to Suzie
The ball is the thematic object, so Take1 to transport, and Take4, to steal are alternatives.
Because a destination is given, Take1 is preferred.
Robbie took Suzie
Suzie is the thematic object. Hence take1 and take2, to transport and to swindle, are possible.
Because no source or destination, Robbie has probably swindled Suzie.
Robbie took Suzie to town
with a destination, the swindle conclusion is unlikely.
Robbie has transported Suzie
The bell was taken out of town by Robbie by car for a day for Suzie
sentence is passive, hence bell is thematic object.
a bell is both inanimate and not a medicine, it must be Take1 or Take4.
the compound preposition out of can flag old surroundings.
Town is a place and places are possible old surroundings.
resolves the ambiguity in favour of Take1.
Car is an unknown word (in our world), so it could be either the agent or conveyance.
Because Robbie is animate, he must be an agent.
This forces car to be a conveyance.
Suzie and day are easily resolved into beneficiary and duration because Suzie cannot be time and a day cannot be a beneficiary.
Primitive Actions Frames
Similar to Conceptual Dependency Theory, can establish a set of primitive actions.
These primitive action can help to capture the meaning of a simple sentence.
Move-body-part
Expel
Propel
See
Smell
Move-possession
Think-about
Move-object
Ingest
Speak
Hear
Feel
Move-concept
Conclude
Frame can be linked together.
Example:
Actions often imply implicit state changes and cause-effect relations.
Robbie enjoyed putting the wedge on the red block.
Suzie told Robbie to put the wedge on the red block.
Suzie comforted Robbie.
Robbie was gored by the test.
Actions often imply subactions.
Primitive action frames and state-change frames make it possible to answer certain questions directly.
How is an action done?
expand the action into primitive-actions and state-changes.
give more detail by working through sub-action slots
e.g. icecream example of fig. 10.11
What will happen if an action is done?
expand the action into primitive-actions and state-changes.
find a similar, but more complete expansion in a database of remembered precedents.
e.g. Suzie hit Robbie (by Move-body-part her fist into his body). A precedent may indicate that Robbie is likely to hit back or to cry.
Does one sentence have the same meaning as another?
expand both into primitives and check whether the result match.
e.g. Suzie
comforted Robbie
Suzie did something to make Robbie happy.
To summarize,
A primitive action system is a representation
That is a frame system, in which
Action frames contain Primitive slot that must be filled by a value drawn from a small, canonical set, such as Move-body-part, Move-object, Expel, Ingest, Propel, Speak, See, Hear, Smell, Feel, Move-possession, Move-concept, Think-about, Conclude, and Do.
State-change frames contain an Object slot that is filled with an applicataion-specific object or quantity.
An action frame may be connected to one or more other Action frames via a Subaction slot.
Action frame and State-change frames may be connected to each other via Result slots.
Other slots and slot values are application specific.
Scripts (Schank & Abelson)
a structured representation describing a stereotyped sequence of events in a particular context.
a meaning of organizing conceptual dependency structures into descriptions of typical situations.
used in Natural Language understanding system to organize a knowledge base in terms of the situations that the system is to understand.
Components of Scripts
Entry condition: descriptors of the world that must be true for the script to be called.
Results: facts that are true once the script has terminated.
Props: "things" that make up the content of the script.
Roles: actions that the individual participants perform
Scene: sequences of actions in the script.
Example (Restaurant Script)
The system reads a small story about restaurant and parses it into an internal conceptual dependency representation.
The story matches the script and the system will binds the people and things mention in the story to the roles and props mentioned in the script.
obtain an expanded representation of the story contents and use the script to fill in any missing information and default assumption.
John went to a restaurant last
night. He ordered steak. When he paid he noticed he was running out
of money. He hurried home since it had started to rain.
Using the script, the system can correctly answer questions such as:
Did John eat dinner last night?
Did John use cash or credit card?
How could John get a menu?
What did John buy?
Sue went out to lunch. She sat at a table and called a waitress, who brought her a menu. She ordered a sandwich.
Question that might reasonably be asked of this story include:
why did the waitress bring Sue a menu?
Was Sue in a restaurant?
Who paid?
Who was the
"she" who ordered the sandwich? (which is
difficult)
[Script roles help to resolve pronoun references and
other ambiguities].
Script can also be used to interpret unexpected results or breaks in the scripted activities.
Kent went to a restaurant. She was shown to a table and ordered steak from the waitress. She sat there and waited for a long time. Finally she got mad and left.
Question that can be answered:
who is the "she" who sat and waited?
why did she wait?
who was the "she" who got mad and left?
why did she get mad?
Problems:
Match problem: more than one potential scripts and no algorithm guarantee a correct choice.
John visited his favourite restaurant on the way to the concert. He was pleased by the bill because he liked Mozart.
Between the line problems: not possible to know ahead of time the possible occurrences that can break a script.
John was eating at his favourite restaurant when a large piece of plaster fell from the ceiling and landed on his date...
Question:
Was John eating a date salad?
What did John do next?
Was John's date plastered?
This examples illustrated that
structured representation can be inflexible.
Reasoning can be locked into a single script, even though his may not be appropriate.