Summarizing Narratives

1. Introduction

While experiments using people may seem less relevant to artificial intelligence than experiments using computers, the work described 1n this paper represents more than an intellectual commitment to psychological validity in AI (although that commitment is also present). The task of text summarization is one of the most complicated challenges facing natural language processing and possibly facing AI altogether. We need all the help we can get.

We have been working in r ecent years at Yale on a story understanding system (BORIS) (2] whose theoretical roots go back to the MARGIE system [10). While an ini tial implementation toward summarization has been completed in BORIS (7) , we have not yet been able to test our most important i ntuitions using BORIS. We pro~ably won ' t be able to utilize BORIS for this purpose until it can process a large number of prototype stories. In the meantime , we have been conducting exploratory psychological experiments, to see how our ideas hold up against systems that can summar1ze a large number of stories. The results have been both surpr i sing . and encouraging .

This work was sponsored in part by the Advanc ed Re search Projects Ag ency under contract N001 4-75-C-llll and in part by the National Sci ence Foundation under contract IST7918463.

Plot units (originally called "affect units") (3,4) lead to general graphs that are typically cyclic in their structure rather than hierarchical. A plot unit is a fixed configuration of mental states and events involving one or more characters in a standard behavioral pattern or interaction. For example, there are plot units that represent honored requests, problem resolution, retaliation, broken promises, and obligations.

All plot units are constructed from smaller primitive components called "affect states." Ther e are three kinds of affect states, designed t o encode mental states, positive events, and negative events. The internal structure of a plot unit is governed by strict rules to control the various ways affect states can be linked to each other [3), but the most important property of a plot un i t representation lies in the fact that plot units can overlap with each other. Two plot units overl ap when they both contain a common affect state. For example, suppose John asks Mary to buy an artichoke, and she does so. The unit describing John's honored request will overlap with the unit describing Mary ' s success because they both shar e the same positive event of Mary buying an artichoke. This event is a critical component f or both Mary's success and John's request :

Overlapping& between top-level units provid e us with the structure of a plot unit analysis. In the representational graph, nodes represent i nstantiated plot units, and arcs join two nodes whenever the corresponding plot units share a common affect state.

F.ach plot unit is associated with generational frames. Generational frames drive the natural language expression of instantiated plot units, and all units are associated with both strong (detailed) and weak (sketchy) generational frames . Stronger frames are used when there is strong connectivity and weaker frames are used when connectivity is weak. The process of summarizing a story is partly a function of structural connectivity, and partly a function of generational frame management.

3. Three Stories and Six Story Representations

To compare story grammars with plot units, we first designed three variations on a baseline story and collected 12 summaries on each variation for a total of 36 summaries (using 36 subjects). All experimental materials were presented as typed text. After reading the text, subjects were asked to produce a written summary in one or two sentences. The three stories (see Appendix A) are very close to each other in overall content. They each involve a deeply nested set of subgoals which the main character devises and achieves. The di fferences can be summarized as follows:

( "Y" indicates the prescence of an item; "N" indicates its absence.) It is easy to generate simplified tree representations for the three stories to distinguish them structurally:

HIERARCHICAL TREE REPRESENTATION FOR STORY

HIERARCHICAL TREE REPRESENTATION FOR STORY 2

HIERARCHICAL TREE REPRESENTATION FOR STORY 3

While not all propositions appear in all stories, the pairwise ordering of all propositions remains consistent throughout. It is never the case that proposition A is higher than proposition B in one tree, and lower in another. Story grammars predict inclusion on the basis of relative tree position. For example, the story grammar model predicts that proposition Pl will appear more frequently than proposition P2 across all story versions:

Pl: get boss to send Paul away

P2: Mike makes deal with accountant

Since we will be concentrating on such hierarchicial predictions, we should mention that the "critical path" model of Black and Bower predicts that failed goals and plans will violate the hierarchical inclusion principle in the sense that failure-associated nodes are unlikely to be mentioned no matter where they reside in the tree [ 1].

Plot unit predictions are based on the plot unit graphs which reflect a somewhat different set of structural distinctions. The units needed to graph our stories are:

While space forbids going into the details of the underlying affect state maps for each story, 11 plot units are instantiated for each story: To derive the plot unit graphs, arcs were inserted between two units whenever those units shared a common mental state or event.

SUBl Mike gets Paul away to build patio

PAFl Mike's persistence after 1st hint

PAF2 Mike's persistence after 2nd hint

NSl Mike obtains boss's agency to get Paul away

NS2 Mike obtains CPA's agency to get boss's agency

NS3 Mike obtains grass so he can give grass to CPA

DRl boss says no to request (in Sl, 53)

DR2 CPA says no to request (in 52)

PAF3 Mike's persistence after denied request

RHCl Mike's deal with CPA

RHC2 Mike's deal with Joe

NAl Mike causes the accountant to cause

the boss to cause Paul"s trip

PLOT UNITS FOR STORIES Sl, 52, and 53

Plot unit predictions are based on the connectivity or degree of each unit in the plot unit graph. Highly connected units are more likely to appear in summaries than weakly connected units.

-- -

CONNECTIVITY CHART FOR PLOT UNITS

In keeping with the "critical path" hypothesis, we have omitted the failure-related units (the DR ' s and the PAF'a) since we do not expect them to show up in the summaries. (Our data supported critical path predictions).

To see exactly what these connectivities predict, we must consider the generational frames for each of the relevant units. Since plot units can be described with varying levels of detail, we will include a strong and a weak frame for each. Strong frames are more likely to appear when units are highly connected while weak frames are more likely to appear for weakly connected units.

SUB (sub goal)

Strong : X needed to do Y because X wanted to do Z Weak: X wanted to do Z.

NS (nested successes)

Strong: X did Y in order to do Z Weak: X did Z

RHC (request honored with condition)

Strong: X made a deal withY in exchange for W Weak: X made a deal with Y

NA (nested agencies)

Strong: X arranged to have Y get Z done Weak : X arranged to get Z done

The strong generational frame for nested agency is meant to include the first agent in the chain, the agent closest to X. In our stories, t his agent is the accountant (rather than Paul's boss who is further away from Hike in the successful chain).

In determining whether a given unit is present in a summary, we naturally cannot expect to find verbatim generational frames. Some flexibility is needed to recognize verbs like "bribe," "bargain," or "negotiate" as weak evidence of an RHC unit. In our stories, strong evidence of the RHCl unit is represented by mentioning what Hike gave to the CPA (grass).

Some examples of instantiated generational f rames are given below:

SUB! (strong):

"Hike needed to get Paul out of town because he wanted to build Paul a patio for his birthday."

NSl(weak):

"Mike got Paul out of town."

RHCl(weak):

"Mike had successful negotiations with an accountant_

NAl (strong):

"Mike arranged with an accountant to have Paul sent out of town."

4. Selected Data Analysis

A comprehensive analysis of all the data would show that story grammars and plot units agree on many predictions. For example, both mod7ls correctly predicted that Mike's interaction w1th the drug dealer was least likely to show up _in summaries. To tease apart the two models, we w1ll examine summary data in four "target" areas wh er e their predictions differ.

.Iu&.ll Au.l 1 : accountant." "Hike gives grass to the

The story grammar predictions for this proposition are largely uniform across all three stories. This proposition appears at level 6 in Sl and S2, and at level 5 in S3. This predicts that S3 summaries should mention Mike giving grass t o the accountant more often than Sl and S2 summaries, with Sl and S2 mentioning it with equal freqency.

The plot unit analysis relies on our availabl e generational frames. The only time the grass should appear within one of these frames is wh en the RHCl unit is strongly present. From the three connectivity graphs, we see that RHCl appears with varying strengths in the three stories :

strong = Max moderate = Max-1 weak < Max-1

These are relative strength ranking& computed with respect to the maximal connectivity within each graph (Max(Sl)· 7, Hax(S2) = 6, Max(S3) · 5). The differences in relative unit strength lead us t o expect a difference in the frequencies of our target propos1t1on for Sl, S2, and S3. _ _ s3 summaries should include the target propoa1t1on more often than S2 summaries, and S2 should exhibit a higher frequency than Sl. The data confirms the plot unit prediction:

(Note: all percentile comparisions across stori es in this paper pass the chi-square test for significance at the .OS level unless otherwise specified).

~ &_u _l: "The boss sends Paul away."

Again, the story grammar predictions are f airly uniform. Hike's goal concerning Paul's boss appears at level 3 in Sl and S2, and at level 2 in S3 . This suggests that the proposition will be mentioned most often for S3, and slightly less oft en f or Sl and S2, but with equal frequency for Sl and S2 .

The plot unit predictions are based on the connectivity of NSl and NS2. A review of our generat i onal frames and nested success unit i ns tantiations shows that the target proposition only appears when NSl is strongly present or NS2 is pr esent (either weakly or s trongly). Using the same computation of unit strength described above, we s ee that NSl and NS2 appear with varying degrees of s tength:

- --··

If t he effects of NSl and NS2 are taken into account with equal weight, we expect that summaries of S3 ar e most likely to ment i on the boss, with summar1es of Sl and S2 somewhat less likely to mention it. Since the strength values in Sl and S2 cancel each other out, we would furthermore expect Sl and S2 to exhibit equal fequencies. This ana lysis coincides perfectly with the story grammar ana lysis. But an alternative plot unit analysis points to a differ·nt prediction.

Not ice that we need a strong generational frame for NSl, and N51 appears with only moderate strength at best. If nested success units require s trong connectivity for a strong generational f rame, then all mention of the boss would be coming exc lusively from NS2. If the effects of NSl are discount ed for not being strong enough, we would expect S2 summaries to mention the boss more often than Sl summaries since NS2 is stronger in S2 than in Sl.

Both models predict that S3 summaries will describe the boss sending Paul away more often than t he Sl and S2 summaries. But only a plot unit ana lysis tan explain why S2 summaries might mention t hi s more often than Sl summaries:

~ .M.u 3: "The boss sends Paul away." vs. "Hike makes a deal with an accountant."

In addition to comparing frequency di stributions for single propos1t1ons across all t hr ee stories, we can also compare the relative f r equency distributions for two propositions within each story. To see how two propositions should compar e , we will look at their relative tree posi t ions and graph connectiv i ties :

Within each story the predictions are uniform. Story grammars predict that the deal with the accountant will be mentioned less often than the boss sending Paul away because the deal occurs at a lower level in the tree. Plot units predic t that these two propositions will be mentioned with equal frequency for each story version, since the i r connectivity rankings are identical in each story.

The data will show that the plot unit prediction is confirmed for S3, and neither model is confirmed for Sl and S2, although the plot unit predictions are closer to the data in these cases than the story grammar predictions:

In stories Sl and S2, The deal with the CPA appear s significantly more often than the boss sending Paul away. It is also significant that the deal with the CPA appears with uniform frequency across all three stories*** since a plot unit analysis comparing the RHCl unit across the three stories would not predict uniform frequency. A confounding factor which we will dub "generational subsumption" appears to be at work in Sl and S2. We will discuss this complication in section 5.

lJJ:i.tl .M.u 4: "Hike wanted to build a patio."

This proposition did not appear in S3, but it was part of Sl and S2. A story grammar analysis places this proposition at the head of the tree structure, which affords it the highest possible probability for inclusion. In the plot unit analysis, the patio goal appears only in the SUB unit which is ranked weakly for both stories. In Sl, SUB is ranked with less strength than NS2 (which showed up in only 1 summary). In S2, SUB is ranked with the same strength as NS3 (which showed up in 3 summaries).

In this case, the story grammar predictions were clearly supported by the data. All 12 51-subjects and all 12 52- subjects mentioned the patio goal in their summaries. In fact, the first sentence in 21 of the 24 summaries sound exactly like clear-cut examples of the subgoal unit generational frame :

*Since the data presented in Target Area #2 showed that NSI had no influence over the frequency for the boss sending Paul away, we will discount NSl here as well. The only unit that can carry the boss sending Paul away is NS2.

**The difference between .75 and .66 is not significant.

*** The differences in significant. .50,.58,.66 are not

"Mike wanted to make his old friend Paul leave town for a few days so that he could build him a surprise present in his backyard."

"Mike wanted to his birthday, for a couple of build his friend Paul a patio but he had to get Paul out of days to do so." for town

"Mike wants to get his old friend Paul out of towm for a few days so he can build a patio at Paul ' s house as a surprise."

While the story grammar model is one clear explanation for this overwhelming consensus, a self-containment factor could also be operating here. We will discuss this in the next section.

5. Generational Subsumption and Self-Containment

Both story grammars and plot units attempt to predict summarization behavior in terms of internal memory representations.

The plot unit graph provides an important predictive element by revealing connect1v1ty properties. But generational frames must be taken into consideration as well. For example, Mike ' s goal of getting Paul out of town was mentioned by all 36 subjects, yet the NSl unit which contains this goal in its top-level success structure is not strongly predicted in any of the plot unit graphs. However, the plot unit analysis is still consistent with the summary data since the nested agency unit (NA) is strongly predicted in all graphs, and NA cannot be expressed without describing Mike"s goal to get rid of Paul. In this case, we say that NA subsumes NSl for the purposes of generation.

A similar form of generational subsumption across plot units occurs in the summaries for Sl and S2 when the deal with the accountant is mentioned. We saw in our discussion of Target Area #3 how the deal with the accountant was mentioned with uniform frequency across all three stories. This violated the different connect1v1ty rankings that RHCl assumed in Sl, S2, and S3, along with the plot unit predictions for Sl and S2 described in Target Area #3. But generational frames provide us with an explanation for this. Consider the generational frames for a request honored with a condition and a nested agency:

NA (strong): X arranged to have Y get Z done

RHCl (weak): X made a deal withY

Since the NA unit is strongly connected in Sl and S2, we know we have a commitment to the strong NA generational frame. We also have RHCl weakly connected in Sl and moderately connected in S2. If we take the number of words involved as a rough indicator of complexity, it is no harder to generate "NA(strong) + RHCl(weak)" than i t i s to generate "NA(strong)" alone:

NA(s):

Mike arranged to have an accountant get Paul out of town.

NA(s) + RHCl(w): Mike made a deal with an accountant to get Paul out of town.

While the effort involved in generating these two concepts is not significantly different, there is a significant difference in their content. "NA + RHCl" is much more specific than "NA" by itself. This makes it optimally efficient to generate the weak frame for RHCl whenever the strong frame for NA is being generated:

The strong frame for RHCl is not pulled in by the NA unit, because it requires more effort; an additional phrase must be generated to express RHCl strongly:

NA(s) + RHCl(w):

Mike made a deal with an accountant to get Paul out of town.

NA(s) + RHCl(s):

Mike made a deal with an accountant to get Paul out of town in exchange for some grass.

Generational subsumption is not structural by nature. It is language dependent, and tightly bound up with the complexities of language generation.

Another confounding factor may be lurk i ng behind the overwhelming presence of the subgoal unit, as discussed in Target Area #4. When people evaluate summaries, they are sensitive to how self-contained a summary sounds. It seems reasonable that this sensitivity to self-containment would enter into the summarization process as well.

While the plot unit analysis for Sl and S2 tells us that getting Paul out of town is the mo s t important top-level goal, this is not a ver y self-contained goal. Why would Mike want to get his friend out of town for a weekend? Are his motives good or bad? What ' s he up t o? The goal begs for an explanation.

To see wha t role self-containment might be playing in Sl and S2, we examined data from two additional stories that are structurally identical to Sl and S2 In these new stories, a farmer replaces Mike, and a donkey replaces Paul. Inst ead of Mike wanting to build a patio, the farmer wants to go to a square dance. And instead of Mike wanting to get rid of Paul, the . farmer wants to put the donkey 1n its shed.* While the subgoal structure remains the same, the goal of wanting t o put a donkey in its shed is much mor e self-contained than the goal of wanting to get rid of Paul. Given this shift of the self-containment *Our ___ H1ke/Paul stories were inspired by t he original farmer/donkey story found in [9).

f ac t or, we can re-examine the differing story gr ammar and plot unit predictions in terms of the summar y data collected for Sla and S2a. As before, 12 subjects provided summaries for each story. This time the results were dramatically different:

Whil e the fr equencies of the SUB units in Sla and S2a ar e not quite as low as the plot unit ana lysi s might have suggested, they are significantly lower than the frequencies found for the SUB units in 51 and 52. These descrepancies are even more striking when the overall data for S1a, S2a and S3a are compared to the data for 51, 52, and 53 . All three farmer/donkey stories showed extreme l y uniform frequency distributions for most pr opositions . F.ven so, the subgoal unit was the only non-failure-re lated unit to display variant behavior. This suggests that the plot unit pred i c t ions would be further substantiated under better experimental conditions.

6. Conclus i ons

From these experiments we conclude that summa r i zation behavior is a function of internal memor y structures along with other non-structural fac t or s. By focusing on areas where plot unit pr ed i cti.ons differed from story story grammar predic tions , we saw that plot units predicted st ructural influences more effectively than story grammar s in three out of four cases. When the st ruc tually-bas ed plot unit predictions fell down, we saw how non-structural factors of generational subsumption and self-containment could have been oper a t i ng to override structural influences. In the one case where story grau®ars appeared to be a clear winner over plot units, additional exper imental data suggests that the originally unsuccessful plot unit pr ediction might have been overridden by a confounding f actor of se l f-con t ai nment which no structural model can add r ess .

All 1n all, the plot ~nit model is holding up wel l against experimental data, and appears to pr ov i de a promising basis for summarization algor i thms .