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:	furniture
number-of-legs:	an integer (default=4)
style-of-back:	straight, cushioned, ...
number-of-arms:	0,1,2

John's-chair frame
a-kind-of:	furniture
number-of-legs:	4
style-of-back:	cushioned
number-of-arms:	0

Knowledge represented by frame

1. properties inheritance hierarchies
   e.g. a-kind-of slot (similar to is-a link in semantic net)

2. expectation, e.g. a special "range" slot which specifies what you expect the value of the slot be.

3. attached procedure:
   a procedure knowledge which will fill-in the slot if needed, or perform other tasks.

Example:

• 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:

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:

1. 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:

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:

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)

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

1. Filling-in Slots

• primary process in a frame-based reasoning system is often just filling in the detail called for by its slots

  1. directly inherited (through is-a link or a-kind-of slot)

  2. by the default slot

  3. computed using the procedure attached through if-needed slots
     (Lisp is particularly suitable as Lisp codes and data are of the same form)

• Advantages:

  1. new frame can have values determined from experiences, without re-compute every time.

  2. slot specific heuristic: general problem solving method can be augmented by domain specific knowledge.

  3. 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.

2. 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

1. When-constructed procedure

• to fill-in default values of a slot by tracing the class hierarchy.

2. When-requested procedure

• to override slot values, e.g.

  1. when a value for the hobby slot of an athlete is requested, return exercise.

  2. 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:

1. Agent: cause the action to occur.

   • Subject or a prepositional phrase in passive sentences.

2. Coagent: a partner to the principal agent

   • usually follows "with".

   e.g. Robbie played tennis with Suzie.

3. Beneficiary: for whom an action is performed

   • usually follows "for".

   e.g. Robbie bought the ball for Suzie

4. 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

5. Instrument: a tool used by the agent.

   • Usually follows "with"

   e.g. Robbie hit a ball with a racket.

6. Source and destination: change in physical location

   • usually follows "from" and "to"

   e.g. Robbie went from the dining room to the kitchen

   

7. 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.

8. Conveyance: on which one travels.

   • Usually follows "by"

   e.g. Robbie always go by train.

9. Trajectory: Motion from source to destination.

   e.g. Robbie and Suzie went in through the front door.

10. 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.

11. Time: specifies when an action occurs.

    • Usually signaled by "at", "before", "after" etc.

12. 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.
    
    
    
    

• 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:

    1. 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.

    2. 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.

    3. 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:

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.