Representing Implicit And Explicit Time Relations In Narrative

I Introduction

An understanding of time relations is essen­ tial to understanding narrative. For a computer program to "understand" narrative, it must process these time relations; this requires both a repre­ sentation of the types of time information that in­ terconnect narrated events, and an algorithm to ex­ tract this information from the natural language

text.

The representation of time relations in narra­ tive raises a number of complex problemS. On the one hand, there are a multitiude of time words: prepositions (e.g., dbSing, before), adJectives (current, prior), adver (then, ~), and nouns (durat1on, week). These various words oanbine into time expressions (generally adverbial expressions) which must be analysed and reduced to a systemat1c

representation.

On the other hand, most events in a narrative do not have an explicit time stated in the form of

an adverbial expression. Nonetheless the reader of a narrative can determine the sequence of events even in the absence of explicit time information for each event. To do this, the reader makes use of certain characteristics of narrative discourse, in order to assign time relations to events whose time is not explicitly given. One characteristic of connected discourse is reference: by identify­ ing various mentions of an event as referring to the same event, the reader associates these men­ tions with the same time. The conventions of nar­ rative discourse also provide certain default time relations between consecutive clauses and/or sen­ tences. For exaJll>le, the convention of "narrative time progression" provides that in narrative, time does not move backward unless an explicit time marker is provided. An algorithm for capturing time relations in narrative must make use both of the explicit time information and of the time in­ formation conveyed implicitly by reference and by the default time relations. This paper will pre­ sent such an algorithm and outline its application to a SaJll>le text.

* This research was supported in part by the Na­ tional Library of Medicine grant number LM-02616, awarded by the National Institutes of Health; in part by the National Science Foundation grant number Isr-7920788; and in part by the National Science Foundation grant MCS-~002453.

I I Background

There have been several previous investiga­ tions of the representation of time relations, all within the context of question-answering syst~ns. [1) focused on the specification of the temporal information provided by tense and described a pro­ gram c~ that accepted a restricted set of En­ glish-like input, stored this information and answered sirrple time-related questions based on the input. Since the input was provided on a sentence-by-sentence basis, the issue of implicit time relations in narrative discourse did not arise in this work. [2) described a representation of time relations between sets of events · The repre­ sentation was used in querying a data base consist­ ing of events whose times were specified (sometimes incompletely) in terms of their duration and in terms of beginning and ending times in relation to another event. From this information, the program could determine whether an event preceded, . over­ lapped, or followed another event.

More recently, [5) and [6) described a "time specialist" program which accepted time information about events in a LISP-like form; the specialist stored this information, checked it for consisten­ ~, and answered queries about the events described in the input. Although the time specialist handled only explicit time information provided in the input, there is a discussion in [5) about 1ts application to a narrative-like situat1on, nanely the specification of the time course of a disease and the matching of input data to the specified time course.

In contrast to the question-answering context of the work described above, this paper is based on research at the Linguistic String Project on the creation of a data base from natural language input. In our initial experiments using medical narrative , it quickly became clear that time rela­ tions between various medical events (e.g., symp­ toms, therapies) were of central importance in cap­ turing the significant information. The time al­ gorithm described here is a modification of an ear­ lier algorithm L3] developed for the analysis of medical records, and the exarrples in the paper are drawn from actual hospital discharge summaries. The algorithm should, however, be equally applica­ ble to time relations in other narrative domains.

In the automatic analysis of the medical nar­ rative material, various stages of natural language processing preceded the analysis of time informa­ tion. These stages included 1) a parse, identify­ ing (surface) syntactic relations; 2) transforma- . tiona! regularization, mapping rrore crnplex sen­ tence types into a "canonical set" of simple s~ ject-verb-object sentence types; 3) a "formatting" CCII'pC>nent, mapping the analysed sentence into a ta­ bular representation of the medical information. (See [7] for a rrore detailed description of the stages of natural language processing).

These earlier stages of processing are rele­ vant to the time algorithm because the time algor­ ithm assumes that each sentence is broken down into syntactic units consisting of subject-verb-object combinations corresponding to events; these units are connected l:rj binary connectives, with the main clause preceding the clause subordinated or conjo­ ined to it. Binary connectives include, anvng oth­ ers, subordinate conjunction (e.g., while in She devel~ dyspnea while she was in Maryland); co-orlilate conJunctlon (e.g., ana ln Her elbOw became infected and she was treated ... Ji"'-and re­ lative clauses ~g~ She was treated with erythranycin which she took for Z, days. ) · As part of the syntactic analysis, each tense and each ex­ plicit time expression is identified and associated with the unit that it lt'Odifies. The output of the syntactic processing is thus a sequence of events with associated time information, connected l:rj bi­ nary connectives. The time algorithm operates se­ quentially on the set of connected events obtained for a document; it starts at the beginning of the narrative and assigns to each event a time in terms of an already processed event, before going on to the next event ·

The enphasis in developing this algorithm has been to use the available syntactic information to its fullest. We have not explored the question of whether the incorp:>ration of domain-specific. extra-linguistic knowledge would improve the pro­ cessing of time (it alrrost certainly would), and whether the kinds of extra-linguistic knowledge needed to do this can be clearly delimited (a dif­ ficult task). It is our hope that the full utilization of linguistic techniques will bring into sharper focus the kinds of information needed to supplement a linguistically based analysis.

III '~_!l~ Representation ~£ r~

It is convenient to analyse the time of an event in terms of its relation to the time of another event (the "reference point") adjusted l:rj an optional time quantity (see [6] and [3] ). The reference point may be a date, which anchors the time to a fixed external scale, or it may be anoth­ er event within the narrative. This analysis has a natural representation as a directed graph, where the oodes of the graph are the time points associ­ ':lted with the events and the edges represent the 1ntervals between events. The time graph for a short three sentence text let is shown in Fig. 1.

An event generally has a single time point as­ sociated with it, although events with duration have both a beginning and an ending point. If two events occur at the same time, they will both be associated with the same time point. Thus in the exarrple of Fig. 1, if admission to the hospital occurs on 1/27 and the patient develops a fever on 1/27, then these two events will both be associated with the same time point (point A in the graph of Fig. 1).

The time graph is useful in determining the relative order of the events displayed in the graph: an event I precedes an event J iff there is a path from the time point associated with event I to the time point associated with event J. The sum of the edges along the path gives the time interval between I and J. For exarrple, in the graph of Fig. 1, B precedes A. There are, in fact, two paths from B to A. In this case, the sum of the edges of the two paths rrust be equal: BA = oc + CA. ( If the ~ength of the two paths were not equal, an in­ conslstency would be detected). Since BAhasa ler¥Jth of 3 weeks, OC + CA = 3 weeks; therefore OC arxl CA are both less than or equal to 3 weeks. In this way it is {X>ssible to deduce further time i~ formation fran the time graJ;tl, such as an upper limit for an edge ler¥Jth.

IV Explicit ~ Information

we can distir¥Juish three sources of time ~ formation in narrative: 1) explicit information, generally in the form of adverbial time expressions arxl tense; 2) time information derived fran d~ fault values based oo a snall set of assllllptions about how events within a narrative are connected temp:>rally; and 3) time derived by the identifica­ tion of an event with a previous mention of the same event (and its associated time).

The IroSt obvious source of explicit time ~ formation is time adverbials expressions. These inclooe dates (2/8(74) and time . e~pres~ions that give the time of an event expl1c1tly 1n terms of its relation to another event, e.g., during the first ~of hospitalization. Figure 2 shows sa:ne sample adverbial phrases and tense. Note that 1n certain cases, the reference {X>int may not be ex­ plicit; for exanple, in the adverbial phrase then (example 4, Fig. 2) the implicit reference {X>l~t is taken to be the time of the last narrated top1c (namely the precedir¥J main clause). For tense, as for sane adverbial expressions, the implied refer­ ence {X>int must be made explicit; for example, for the present tense, it is the time of speaking.

The same analysis is used for the time infor­ mation conveyed by a subordinate conjunction. For example, in the sentence Throat cultures we~e obtained only after IV ampicillin was s_!:arted, the subonhnate clause event (IV ampiclli~ was started) precedes the time of the main clause event (throat ... . .

1.

3.

4 .

5cultures were obtained by an unspecified amount:

t1me (IV ampicillin) =

time (ETiroat cUltures) - ?

Verbs (such as the verbs precede arxl foll~) can also specify temp:>ral connections between events. One i.sntx>rtant class of veros is the class of aspec­ tual verbs: verbs of beg innir¥J, erxl ing, chang ir¥J, etc. These verbs carry time in format ion about a state in relation to an earlier implicit state: fever subsided implies that at an earlier point in t1me, a fever existed. Once the earlier implied event is located, the time relation between it and the event rocdified by the aspectual can also be r~ corded within the framework sketched above.

V Default Values for Time Connectives .;.__;....;;.__..;_..;;.. ---- -- ----- ---

There art:! several basic assllllptions about how time progresses in narrative that enable the time algorithm to capture time relations implicit in the narrative. The IroSt i.sntx>rtant of these assllllptions is that time does· not 100\Te backwards in narrative unless an explicit time marker is provided. The time of an event relative to the time of a previ­ ously mentioned event is assumed to be equal or later than the time of the previous event. The folla...rir¥J sequence of sentences fran Fig. 1 illus­ trates the usefulness of this hypothesis:

1. 3 weeks prior to the current admission, a bright red patch appeared under the patient's eye.
2. The patient developed a maculopapular rash over harxls arxl knees.
3. On 1/27 she began havir¥J a fever to 104.

Sentence 1 describes an event occuring three weeks prior to admission; sentence 2 would have a d~ fault time greater than or equal to the time of sentence 1, using the hypothesis of narrative time

. -

R£l.A'l'l0H: AT indicates time-po int FROM } iJLdi cates bebiunirL,; anJ enJir1~ TO points of a Jw-a t i on

Rt:f'-l'f = Rt:FEHENCE POINT

DIR = DIRt:CTION Q = (IUA::Tl1'Y

FIG. 2 ANALYSIS OF EXPLICIT TIME EXPRESSIOOS

progression. Sentence 3 has an explicit time (1/27), but narrative time progression also applies; this provides the information that the time of sentence 3 is later than or equal to the time of sentence 2. As a result, a lower and an upper bound on the time of sentence 2 are obtained from the discourse context, although sentence 2 has no explicit time. These relations are represent~~ by the graph in Fig. 1.

A secord hypothesis states that the time of a subordinate clause is equal to the tilne of its main clause, provided that no explicit time information occurs in the subordinate clause or in the subord i­ nate conjunction. For example, in the sentence A spinal ~ ~ performed which revealed 806 red blood cellS, the subordinate clause (which revealed 806 red blood cells) is assigned a tilne equal to that of the main clause (~ spinal ~ was performed) ·

Co-ordinate conjunction poses some special and difficult problems for interpreting time informa­ tion. The algorithm distinguishes t\roQ main cases. When the subject or object contains a conjoined ooun or adjective t*lrase, the conjoined t*lrase is expanded during the transformational stage to yield t\roQ events; however, the algorittJn assigns them the same tilne (specifically the secord conjunct is assigned the time of the first conjunct). Thus in the sentence The macul~~lar rash and the patch under her right.~ graduay disa~~red-;-the t\roQ events rash d1satpeared and ~ disatpeared are assigned the same time.

When there are t...o distinct predicates con­ nected by a co-ordinate conjunction, then the t\roQ conjoined events behave 1 ike t\roQ independent sen­ tences, ard the algorithm assigns to the secord a tilne later than or equal to the tilne of the first, as in narrative time progression. For example, in the sentence~ The maculopapular rash and the patch under her nght ~gradually disatpeared and were ~after the first twelve hours ~ theraer, the default t ilne information is used (together w1 th the tilne information from the explicit adverbial after the first twelve hours ~ therapy) to determine that the tilne of the secord conjunct (rash and ~ ~ gone) is later than the time of the m conjunct. (rash and patch gradually dlsatpeared); 1n fact, the secord conjunct marks the end point of the tilne period of the first con­ junct.

VI Time Information from Resolution of Reference

If a single event is mentioned several times within a discourse, it is ilnportant to identify these mentions of the event and to equate the tilnes associated with each mention (igooring, for a~ ment, descriptions of states which can have a dura­ tion). For example, the events currynt hospitalization and ·current hospital stay have a special signifcance in a hospital discharge summa­ ry. They are associated with specific dates {pro­ vided in the header information) and atpear as reference points in many time ex~essions, for ex­ ample, she again spiked fevers on the 4th ~ of tJ<;>spitalization, or eatient was afebrile on d1scharge. If a g1ven mention of admission, discharge, or hospitalization can be associated with the current hospitalization, then its tilne can be set equal to the date given in the header. For example, if the hospital admission occurred on l/27, then~ 4th ~.£f hospitalization will be l/31, prov1ded that th1s is a reference to the cur­ rent hospitalization. Despite tl~ fact that ana­ phoric reference is more difficult to detect in the note-taking style of the discharge si..B11JT\aries (arti­ cles, both definite and irdefinite are commonly om­ itted), these references to the current hospitali­ zation are generally easy to resolve because they are the default reference; there are occasional references to previous hospitalizations, but these are flagged by various modifiers, as ·in the previous hospitalization.

The original program implemented to process· time relations [3) did anat*lora resolution only when an event atpeared as the reference point in a time expression. However, the current algorithm extracts more complete time information by compar­ ing each new mention of an event (regardless of whether it occurs as a reference point) to previ­ ously mentioned events of the same type. When it identifies t\roQ mentions as referring to the same event, then it equates their times.

A simple technique is used for ·determining sameness of reference: a backward search is per­ formed for events of the appropriate type, namely, events in the same synonym class. When a candidate event is fourd and its factuality is checked (ne­ gated events canoot be antecedents), then its tilne is canpared to the time of the current event. If the times are canpatible (that is, no contradiction arises from assuning that these events are the "same"), then they are taken as referring to the same event; otherwise, the backwards search is continued until all events of the appro~iate type

have been tested.

This procedure has been adequate to identify s.::u.1eness of reference in the hospital discharge summaries, which have a relatively simple referen­ tial structure. For more complex texts, it is clear that a more sophisticated technique for rescr lution of anaphora \roQuld have to be used.

VII Capturing Time Relations in ~ Samp.l,_~ Text

The t\roQ sentences below are the third and fourth sentences (events 9-15) from a paragrat*l of a hospital discharge si..B11JT\ary.

1. The patient became afebrile during the
2. first day of hospitalization.
3. She again spiked fevers on the 3rd and 4th day of hospitalization, but then became afebrile and remained afebrile for the remainder of her hospitalization.

We will use these sentences to illustrate how the algorithm extracts and represents tilne information from a narrative. In the first sentence she became afebrile, there is an implicit reference-Tcarried by the change-of-state verb becane) to a state when the patient was not afebrile. This earlier ilnplied

state is entered as event E9; the state of becaming afebrile is event ElO. The secooo sentence states that she ag~in ~iked fevers on the 3rd ard 4th ~ of hospltall~tion (events Ell and El2). Here, the word again is arx>ther reference to the earlier mention of fever (E9). Finally the word Pe<:ane in 1 she] becane afebrile (event El3) is an unpllcit reference-Ito the preceding fever events (she spiked fevers, Ell and El2) · Each of these change-of-state words triggers an antecedent search as described al:x:J'Je. Figure 3 shows the two sen­ tences as a sequence of connected events, with their associated times.

In detail, the algorittJn proceeds as follOws:

E9: beoane afebrile in the first sentence is an implic1t reference to an event be rot afebrile rrt found by an antecedent search in the paragraF(1; therefore this implied event is entered as E9, with time preceding ElO.

ElO: There are two sources of time informa­ tion for this event. The explicit adverbial ex­ pression during t~ fi~~ ~ of ~~~pitalizati~n gives rise to a beginning (f'IOot) time {X>int = AI:'MISSIOO and an end (TO) p:>int ~ISSIOO ~ !_ IY\Y. (In this case, this represents the lower ard ~r bounds of a time-{X>int, rather than the be­ ginning ard ending {X>ints of a continoous state; the current algorittJn does not distinguish these two uses of durational expressions). Narrative time progression relates ElO to the main clause of the previous sentence in the paragraF(1, namely Etl (rot shown) ·

Ell: The word again triggers a search for a preceding occurrence of fever, found in E9; this generates the time information «r E9 +. The expli­ cit time expression on the 3rd ~ of hospitalization provides the t"Iilie informatwn «r ArMISSIOO + 3 IY\Y. The fact that Ell is derived fran a separate pr~icate conjoined to ElO provides the third relation, time (Ell)>= time (ElO).

El2: There is an explicit .time expression (on the 4th ~ of hospitalization); El2 also refers to the earlier fever (E9) by the use of again. Time progression from conjoined predicates is ig­ nored here because it provides redundant informa­ tion; an explicit time relation between Ell and El2 can be established by subtraction: time (El2) time (Ell) + 1 IY\Y,

El3: There are two sources of time informa­ tion here: the adverb then, which provides the in­ formation that El3 occurred after the last narrated topic, namely El2 (time (El3) =time (El2) + ?). It also has time progression fran conjunction with El2, but this is anitted because it is redundant; then provides more explicit information.

El4: There is an explicit duration expression here: for the remainder of her hospitalization. This provides a starting (FROM) time = time of last

TEXT ( t hird a nd fourth senten\!CS o f a para15raph from a hospital discharge summary)

Date of admissi on l /27 /xx Date of discharge 2/8/xx

.·. The patient became a febrile duri11g the fi r st day of hospitalization. She again spiked fevers on the 3rd auJ 4th day of hospitalization, but then became afebrile and remained afebrile and a symtornatic for the remainde r o f her hospita l ization · · · .

s~.:opt> of conjunction in,H cated by bra\..·es {

[ ] i nd i cate words fille ,J i u by tro.rwformationo. l r eiJ:uta. J·L·.a t.iun

· ~rlier sentences in paragraph contain events El- EH ; Etl = last narrated topi c from preceding sentence (not shown). FIG. 3 C~EX:TED EVENI'S AND THEIR TIME RELATIOOS

narrated topic, namely El3; and it provides an ending (TO) time = date of discharge. The time derived from conjoined predicate time progression (time (El4) >= time (El3) is therefore redundant and is omitted.

El5: This event is derived from El4 by expan­ sion of a conjoined adjective in the object: afebrile and asymptomatic; it is therefore taken as havi~ the same time as El4.

The time graJ;tl for these sentences is shown il"' Fig. 4.

In the course of canputing the time relations, all events of a given type (for example, fever events) are collected into a set, in order to fa­ cilitate determination of sameness of reference. This grouping has an additional advantage in that it makes it possible to graph a set of fever events against time. Figure 5 shows a graph of fever aga­ inst time for the sentences analysed in Figs. 3 and 4. Although it is not possible to determine the exact shape of the curve (or its height, since a numerical temperature is·not always given), the graph nonetheless provides an approximate picture of the patient's periods of fever during the hospi­ tal stay.

VIII Conclusion

In this brief discussion, only the broa:i out­ line of an algoritl'ln to extract time information from narrative can be sketched. The algoritl'ln des­ cribed in this paper is a modification of a previ­ ously developed algorittln (3) that was implemented arrl successfully tested on a set of eight hospital d1scharge summaries, each containing approximately 50 sentences of text [ 4) · The original program contained an extensive treatment of explicit time expressions, covering sane 50 time words. The ~ ifications to the original program have been mainly in the handling of implicit time relations.

We are OClW in the process of implementing the new version of the algorittJn arrl are still investi­ gating several problems in this regard. These are: 1) maintaining a canpact representation that per­ mits detection of inconsistencies when a new time relat ion is added to the set of known time rela­ tions; 2) representing continuous states as op­ p::>sed to time-p::>int events: a state may change over time, but can still be identified as a single state (e.g., a fever may rise and fall but it is still referred to as a single continuing fever); 3) irnplernening a 100re sophisticated procedure for anafilora resolution, including the haOOling of references to continuous states; and 4) distin­ guishing between the two uses of durational expres­ sions: 1) to define the lower and upper 1 imits of a single time-p::>int, as in she had a transfusion during her hospitalization;or 2lto-define begin­ n1ng arrl end p::>mts of a continuous state: she was afebrile ~ her hospitalization. In addltion, there are a nunber of issues that we have not yet touched on, for example, the representation of ~ precision in time specifications or the use of extra-linguistic knowledge to determine time rela­ tions. Nonetheless, the general principles out­ lined in this paper appear to constitute an imp::>r­ ~ant first step in extracting time information from narrative in a way that captures many of the imp::>r­ tant relations between the narrated events.