FASTUS: A Finite-state Processor for Information Extraction from Real-world Text

1 Introduction

There are many reasons t.o want t.o IHOC<'SS large nunr­ bers of natural-language texts aut.omat.ically with high speed aJHl accuracy. The best informatiou r·et.ri<·val sys­ tems can ret.reive t. <~xt.s that. have a reasonable like! ihood of beiug relevant t.o one's general concerns. However, getting the information out. of the text that. is required for solving someone's problem still requires a human to actually read the texts -- a time consuming process that can easily swamp t.he available resources. We have de­ veloped the FAST US system ( t.he acronym is a slight. permutat.ion of Fi11itc St.ate Automata-based Text. UH­ derst.anding System) to address the need for a system that. extract-s prespecified information from a text. with high speed and accuracy. This system has been t.ested in the MUC-4 evaluation of text processing systems [Sund­ heim, 1992] and has demonstrated

• High Performance (44% Recall and 55% Precision on a blind test. of 100 Texts, which wa.'l among the best. scores in the f)Valuat.ion)
• Short. domain-specifie development t.ime {t.hree and a half weeks for the domain of terrorist. incidents)

·This research was funded by the Defense Advanced Re­ search Project.s Agency under Office of Naval Research con­ tracts N00014-90-C-0220, a.nd by an int.ernal research and development. grant from SRI Int.erna.t.ional.

• ft'a.<>t processing time (texts were process<·d at. the l'a.te of more than 2,000 words per miuut.c)

1.1 Two Types of System

One can distinguish between two types of natural lan­ guage systems: information ( :drarlion systems a11d ltJ:t ·~tnder.standing systems. In informatiou ext.ract.ioll ,

• Only a. fraction of the text. is relevant.; in t.lw case of the MUC-1 terrorist reports, probably only about. 10% of the text. is rdevant .
• Information is mapped into a predefined, rdat.ivPiy simple, rigid target. l'epresent.ation; t.his condition holds whenever ent.ry of information int.o a database is the t.a.'lk.
• The subtle nuances of meaning and t.he writer's goals in writing t.lw text. are of no int., ~ rPst ..

This contrasts with t.ext. undPrst.anding, wher<'

• The aim is to make sense of the ent.in· text ..
• The target. rcpreSt>nt.ation must. arcormnodat.e the full cornplexit.i<>.s of language.
• One wants to recognize t.he nuance:;; of meaning and the writer's goals.

FASTUS is designed for the former ca.'le. Although the t.a.'lk is limited, it is nevert.heless an import.ant. t.a.<>k that has many real-world applications.

Lt is tempting to view the information extrad.ion ta.<>k as a simple special ca.<re of the text understanding ta.'>k, and approac.h the problem by applying a system designed for text. understanding t.o the simpler task .. We originally at.t.empted to apply the TACITUS system [Hobbs et al., 1993] to this task. TACITUS is a text-understanding syst.em that. attempts to recover all implicit. information from t.he text. by abductive inference, using a semantic analysis of each sentence as the statement t.o be abduc­ t.ively proved, and the as8umpt.ions necessary to com­ plete the proof comprising the additions to the system's knowl~dge base from understanding the sentence. This at.tempt. was mildly successful (we managed t.o achieve 24% Recall and 40% Precision in an objedive evaluation on the same t.a.'lk), however, the system was slow, since it spent. much time on irrelevant. text.

The TACITUS experience demonstrates why it was wrong to approach t.lw information ext.ract.ion t.a.<;k a.~ a

"traditional" computational linguistics problem. Even though many techniques t.o increase the robustness of the system were employed [Hobbs et al., 1993), the fact remains that parsing of context-free grammars is rela­ tively slow, and this slowness is evident when encoun­ tering sent.en<:es that. are 60 to I 00 words in length, as happens not. infrequently in real-world t.ext.s. Although TACITUS employed lwuristics t.o guide the parsing of such long sentences, and statist.ies wuld be t~mployed by a parser to find the most. likely analysis first. [Magerman and Weir, 19~J2), the fact. remains that mistakes will be made, and t.llf~Y will have an in1pad. on pt>rformanee. A further problem was f.hat the system had to apply com­ putationally intensive reasoning t.eehniques to every sen­ tence. Sinw much of the t.ext was irrelevant this meant. that mueh of this effort. was wasted. A statistical rele­ vanee filter was employt~d, but. this filter had to have high recall and hence low precision t.o avoid exdnding truly relevant text from wnsideration , and therefore admitted much irrelevant text. to further proc.essing.

1.2 Finite-State Models of English

If there are prohlems in applying context.-free parsing to real-world text , then an f'ffi<:ient text. processor might make use of weaker language models, i.e., regular or finite-state grammars. Every comput.at.ional linguistics graduate student. knows, from t.hf' first. textbook that. in­ troduces the Chomsky hierarc.hy, that. English has con­ struct.s, e.g., cenl.er emhc~dd i ng, t.hat. c.an not. he descri heel by any finite-state grammar. This fad. has uo douht biased researchers away fron1 serious ronsidt'rat.ion of possible applications of finit.t·-st.a.l.t' granunars t.o diffirult problems.

Church [1980) was t.he first. t.o advocate finite-st.at.e grammars as a processing model for language under­ standing. He contended that., although English is dearly not a regular language, nwn1ory li1uitat.ions 111ake it. im­ possible for people to exploit. that. cont.ext.-fn~eness in its full generality, and t.herefore a finite-st.ate me('.hanism might be adequate in practice' as a model of human linguistic performance. A ron1put.at.ional realization of memory limitation as a depth cutoff was implemented by Black [1989) .

More recently, Pereira and Wright [ 1991) have de­ veloped met.hods for constructing finite-state grammars from context free grammars that. overgenerate in certain systematic ways. The finite-state grammar could be ap­ plied in situations, e.g. as the language model in a speech understanding system, where comput.at.ional ('Onsidera­ tions are paramount ..

At this point, the limitations of t.he application of finite-state grammars to nat.ural-language processing have not yet been determined. We believe this research establishes that. these simple mechanisms can achieve more than has previously been thought. possible.

2 A Description of the Task

SRI International participated in the recent. MUC-4 eval­ uation of text-understanding syst.ems [Sundheim, 1992) , the fourth in a series of evaluations. The methodology chosen for this evaluat.ion was t.o score a system's ability to fill in slots in templates surnmarizing the rontent of newspaper articles on Latin American terrorism. The articles ranged from one t.hird of a page t.o two pages in length. Many art.icles descril)(·d mult.iple incidents, while other texts were completely irrel<~vant ..

The following are some rd<'vanl. t>X<"c'rpt.s from a sam­ ple terrorist report, whi(~h is th<~ sou1·re of most. of the examples in this paper.

San Salvador, Hl Apr IHl (ACAN-EFE) -· [TEXT) Salvadoran President.-dcd. Alfredo Cristiani condemned t.lw terrorist. killing of At.­ t.orney General Roberto Garcia. Alvarado and accused t.he Farabundo Ma1·t.i National Libera­ t.ion Front (FMLN) of tlw rrinw.

Garcia Alvarado, 56, was killed wlwn a bomb placed by urban guerrillas on his vehide exploded as it. c.ame to a halt at. an intNsedion in downtown San Salvador.

Vi<:e President.-eled. Franr isr.o Merino said that. when the attorney general's rar stopped at a light on a street in downtown San Salvador, an individual placed a bomb on !.he roof of t.he armored vehicle.

Guerrillas att.aeked Meriuo's honw in San Salvador !) days ago wit.h explosives. 'l'lwre were seven children, induding rour of t.hf' viee president's children, in t.he home at t.he t.ime. A 15-year·old niece of Mt~rino's was injured .

According to the police and Garcia Al­ varado's driver, who escaped unsrat.lwd, the attorney general was traveling with t.wo hody­ guards. One of them was injured.

This text. is taken from a set. of one hundred 111essages used in t.he final evaluation of M UC-:3 in May 199 L.

Some of the corresponding database ent.ries for the killing of Garcia Alvarado are as follows:

The principal measures in the MUC-4 evaluation were recall and precision . Recall is the number of answers the system got. right. divided by the number of possible right answers. It measures how comprehensive the system is in its ext.rart.ion of relevant information. Preci8ion is l.he Hllmlwr of answt~rs t.he system got right divided by the mnuher of a11swers the system gave. It measures tlw system's an·uracy. For example, if there are 100 possible answers and t.he system gives 80 answers and gets 60 of t.hem right., it.s recall is ()0% and it.s pr.ecis.ieu is 7!)%.

3 Overview of the FASTUS Architecture

The input. l.l'xt. is first preprocessed to ensure that. the t.(~xt. is in a standardized format for the remainder of the processing. Spelling correction is done at. this point as well. 'l'hc preprocessed text is then given to t.he FASTlfS syst.em propnr.

Tlw operation of FASTlJS is composed of four steps:

• I . Triggering
• :2 . Rf·cogniziHg Phrases
• :l . Re<·ognizing Patterns
• Merging Incidents

These steps are described in the next four sections. A post.processing phase then converts the incident. struc­ t.un's generated by ~'ASTUS into the format. required for t.he M (JC-4 templates.

The system is implemented in CommonLisp and runs 011 both Su11 aJl(l Symbolics machines.

3 .1 Triggering

In the first pass over a sentence, t.rigger words ar<~ sParclu··d for. There is at least. one trigger word for each pat.tern of interest that. has been defined. Gen­ erally, these an' the least frequent. words required by the pat.teru. For example, in the pattern

take <HumanTarget> hostage

"hostage" rather than "take'' is the trigger word. Tht>rt> are at. present 253 trigger words.

In addition, the names of people identified in previous sent.ences as victims are also treated, for t.he remainder of t.lw text., as trigger words. This allows us, for example, to pick up occupations of victims when t.hey occur 111 St>nt.enc.es with no other triggers, as in

Hector Oqueli and Gilda Flores were assasst­ nat.ed yesterday.

Gilda Flores was a member of the Democratic. Socialist Party (PSD) of Guatemala.

Finally, on this pass, full names are searched for, so that subsequent references to surnames c.an be linked to the corresponding full names. Thus, if one sentence refers t.o "Ricardo Alfonso Castellar" but. does not men­ t.iou his kidnapping, whill:' the next sent.ence mentions the kidnapping but. only uses his surname, we c.an (~nter Cast.ellar 's full name into the template.

The performance of FASTUS on the example message is illustrat.iv(' of its performance in general. In that mes­ sage, 21 of :10 sent.t>nct>S Wf'ff' t.riggt>red. Thirt.een of tlw

21 triggered sentences were relevant. Two of the 9 seu­ t.enr.c>s not. t.riggered were actually relevant..

3.2 R.e(:ognizing Phrases

Tlw problem of synt.act.ic ambiguity is AI-complete. That. is, W«' will not. have systems t.hat. reliably parse l·:uglish st~nt.enn's correctly until we have encoded much of t.lw rPal-world knowledge that. people bring to bear iu t.lwir language rornprehension. For t>xample, noun phrnses <·a.unot. he reliably identified because of the prf'posit.ional phras«" at.tarhment problem. However, cer­ t.ain synt.adic const.rud.s can be reliably identified . One ol' t . hes(~ is t.lw noun group, that is, the head noun of a. uoun phrase together with its determiners and other ldi. ntodifiet·s. Another is what we are calling the "verb group", t.hat is, tlw verb together with its auxiliaries a.nd a.ny int(·rvening adverbs. Moreover, an analysis that ident.ifks t.lwse dt·ntents gives us exactly the units we most. 1wed fOI' recognizing patterns of interest.

Pass Two in FASTUS identifies noun groups, verb groups, and S('Vera.l critical word classes, includiug prepositions, <'onjund.ious, relative pronouns, and the words "ago" and "that". Phrase.'! t.hat are subsumed by larger phrnses a.w discarded . Overlapping phrases are rem', but. where t.hey occnt· they are kept.

( :lwosing tlw longest. subsuming phrase could lead to incon"f'<'t analys<>s in some cases involving lexic.al ambi­ gui t.y lwt. we( ~n nouns a.nd verbs. The present tense forms ol' surh w·rhs are the sa.me a.<; the corresponding nouns; t.herei'OI'e a noun ph ra.c;c could be constructed taking t.he 111isideutifit>d verb ns it.s h<>ad . This ambiguity problem was solved l>y t.lw simple expedient. of assigning a lower pn·ferenc(' t.o any c.oust.it.ucnt. with a present-tense verb fonn. Becaus(~ t.lw sourc(~ of texts for this task was news­ paper art.iclns ahout. pnst. events, the use of present tense V('rh ph rases i 1i. rt>lt>vant sentences was quite rare.

In do111ains in which t.his expiedient solution to lex­ ical ambiguity is inapplic.able, a part of speech tagger could lw employed t.o help resolve the ambiguity. We intplf·nwut.ed and considered using a part-of-speech tag­ g<'r, but. we found that. there was no dear improvement in performance, and it. would have doubled the t.ime the syst.e1 n took t.o process a message.

Noun groups are recognized by a 37-state nondeter­ ministic finite st.ate automaton. This enc.ompasses most of t.he complexity that can occur in English noun groups, indudiug numbers, numerical modifiers like ''approxi­ mately", other quantifiers and determiners, participles in adj<~ct.ival position, comparative and superlative adjec­ t.ivPs, conjoined adjectives, a.nd arbitrary orderings and conjunc.tions of prenominal nouns and noun-like adjec­ tivt>s. Thus, among the noun groups recognized are

approximately !) kg more than :~o pensant.s t.lw newly elected president t.h(' largest lert.ist polit.ieal for<"e a. govemment. and military reaction

Ved) groups art' recognized by au 18-st.ate nondeter­ ministic finite state machine. They are tagged a.'! Act.ive, Pnssive, Gerund, and Infinitive. Verbs are somet.imes lo­ cally ambiguous het.wt>en ac.t.ive and pa.c;sive senses, as the verb "kidnapped" in the two sente11<·.es, Several men kidnapped the mayor today. Several men kidnapped yesterday were reh~ased today.

These are tagged as Active/Passive, !\lid Pass Tlm~e rf'­ solves the ambiguity if necessary.

Certain relevant predicate adject.ives, such as "dead" and "responsible", are recognized, as are n~rtaiu adverhs, rmch as "apparently" iu "apparently by''. llowf'ver, most. adverbs and predicate adjectives and rnany other classes of words are ignored altogether. ll nkuowu words are ignored unless they occur in a context t.hat. could iu­ dicate they are surnames. The complete gram111ars of noun groups and verb groups are given hy Hobhs d . a.l., [l992b].

Lexical information is read at compile tinw, and a hash table associating words with their transitions in the finite-state machines is constructed. There is a hash table entry for every morphological variaut. of a word. The TACITUS lexicon of 20,000 words is used for lexical information. Morphological expansion of these words r·e­ sults in 43,000 morphological variants in the hash table. During the actual running of the system on t.he text.s, only the state transitions accessed through the hash t.a­ hle are seen.

In the example message, 243 of 252 phras·~s. or !Jfi.4%, were correctly recognized. Of the 9 mistakes, 5 were drw to IIOtms being .misidentified as verbs or verbs as nouns. The other 4 mist.akes were due to simple bugs of t.Ju· t.ypt' that. frequent.ly creep into code during developnu~ ut. .

3.3 Recognizing Patterns

ThP input to Pa.<5.~ Three of FASTUS is a list of phra.<>es in the order in which they occur. Anything that. is not. included in a phrase in the second pa.<>s is ignored in the third pass. Pat.t.ems of interest. are encoded as finit.P state machines, where state transitions are effect.ed hy phrases. The state transitions are driven off t.he head words in the phra.<>es. That is, a set. of state t.ransi­ tions is associated with each relevant head word-phra.<>e type pair, such a.<; "mayor-NounGroup", "kidnapped­ PassiveVerbGroup", "killing-NounGroup'', and "killing­ GerundVerbGroup". In addition, some nonhead words can trigger state transitions. For example, "bomb bla.<>t" is recognized as a bombing.

We implemented 95 patterns for the MUC-4 applica­ tion. Among the patterns are the following ones that. are relevant. to the example message:

killing of <HumanTarget> <GovtOfficial> accused <PerpOrg> bomb was placed -by ~Perp> on <PhysicalTarget> <Perp> attacked <HumanTarget>'s <PhysicalTarget> with <Device> <HumanTarget> wa.~ injured <HumanTarget> 's body

As patterns are rer.ognized, incident. st.rud.ures are bniJt, up. For example, the sentence

Guerrilla.<> attacked Merino's home in San Sal­ vador 5 days ago with explosives.

matches the pattern

<Perp> attacked <HumanTarget> 's <PhysicaiTarget> in <Location> <Date> with <Device>

This causes the following incident to be construd.·~<L

Incident:

Dat.e:

Locat.ion:

lnst.r:

Perp:

PTarg:

HTarg:

ATTACK/BOMBING

14 Apr 89

El Salvador: San Salvador

"explosives"

"guerri II a.<>"

"Merino's home"

''Merino"

The incident. type is an attack or a bombing, depend­ ing on the Device.

A certain amount of "pseudo-syntax" is done while pat.terus are being recognized. In the first. place, t.he material lwt.weeu the end of t.he subject noun group and the l>t>ginning of the main verb group must. be read over. There are patterns to acr.omplish this. Two of them are <ts follows:

Subject {Preposition NounGroup}* VerbGroup

Suhjed. Relpro {NounGroup I Other}* Verh(:roup {NounGroup I Other}* VerbGI'Onp

Tlw first. of th··St' patterns reads over prepositional phrast·s. The S!"cond over relat.ive clauses. The verb group at. the f'nd of t.hese pat.t.erns takes t.lte subject. noun group as its subjed .. There is another pattern for rap­ turing the cont.ent encoded in n~lative clauses:

Subject. Rdpro {NounGroup I Other}* VerbGroup

Since t.lu' finit.e-st.at.e lll!'cha.nism is nondeterminist.ic, the full content. can be extract.ed from the sentence

The mayor, who wa.<; kidnapped yesterday, wa.<; found dead today.

One branch discovers the incident encoded in the relative clause. Another branch marks t.ime through the relative dause and then disr.overs t.he incident in the main clause. These incidents arc then merged.

A similar device is US!"d for conjoined verb phra.<>es. The pattern

Subject. VerbGroup {NounGroup I Other}* Conjunction VerbGroup

allows the machine to nondeterministically skip over the first conjunct and associate the subject with the verb group in the second conjunct. Thus, in the sentence

Salvadoran President-elect. Alfredo Cristiani condemned the terrorist killing of Attorney General Roberto Garcia Alvarado and ac­ cused t.Jw Farabundo Marti Nat.ional Liher­ at.ion Front. (FMLN) of the crime.

one branch will recognize the killing of Garcia and au­ other the fact. t.hat. Cristiani accu~d the FMLN.

The second sort of "pseudo-syntax" t.hat. is done while recognizing pat.t.erns is at.t.arhing gPnit.ives, "of' comple­ ments, and appositives t.o LIH~ir heads, and recognizing noun group conjund.ions. Thus, in

seven c.hildrf'n, including four of t.he vicepresident's childn~n

the genitive~ "vi<'e-president.'s" willlw at.t.adwd to "chil­ dren". The "of" rompl<·~ment. willlw a.t.t.arhed t.o ''four", and since "including" is t.rf'a.I.Pd as a. conjunction, the en­ tire phrase will he recognized as <·onjoinPd noun groups.

ln the example llH'ssag<', t.hen· were I~ rdevant. pat.­ t.t·rns. FASTlJS rerogni"'< ~d l:l of t.lw111 romplet.ely. Be­ cause of hugs in iHiplt·nwnt.NI pal.t.Pms, :1 more patterns were recogni.,<'d only part.ia.lly.

A rudimentary sort of pronoun resolution is done by FASTUS. If (and only if) a pronoun appears as a Human Target., an a.utP.<'<'Cient. is sought .. First. t.he noun groups of the current. seut.t>n<·e arc· seaiTiwd fro111 l<~ft to right, up to four phrases hefore the pronoun . Then the previous sentences a.n· sea.rdwd si111ilarly for a.n arceptable noun group in a. ld't.-t.o-right. fashion, t.he IIIOst. recent. scn_t.ence first.. This is cont.inu<'Cl unt.il a paragraph break IS en­ countered , and if not.hing is found by t.hen, the system gives up. A nouu gmup is an a<'.<'<'pt.a.ble ant.ecPdent. if it. is a possible human t.argd. and agr<'es wit.h the pro­ noun in mJJIIIwr. This algorithm work<~d in lOO% of the relevant. rases in t.h<~ lirst. :lOO nwssa.g<'s of the develop­ ment. sd. llow<'ver, ill it.s Oil<' applira.t.ion the example message, it. failt·d . Tlw exa111pl<' is

According t.o tlw polin· and Garcia Alvarado's driwr, who escaped unsra.t.lwd, t.he at.tor­ ney ge1wral was t.ra.v<'ling wit.h t.wo body­ guards. On<' of t.hem wa;; iujun·d.

Tlw algorith111 inrorre<"l.ly ident.ifiPs "t.lwrn" as "t.ht> po­ lice" .

3.4 Merging In<:idents

As incident.s are found t.lwy art> merg<'d wit.h other in­ cidents fouud in t.lw same sent.ence. Those remaining at. the end of the processing of t.he sentence are t.hen merged, if possible, wit.h t.lw inri<ient.s found in previous sentences.

For example, in the first. s<·nt.ence of Messagf' 48 of TST2, t.he incident.

Incident: KILLING

Perp:

Confid:

HTarg:

"Roberto Garcia Alvarado"

is generated from t.he phrase

killing of At.t.orney General Rohert.o Garcia Al­ varado

while the incident.

Incident:

Perp:

Confid :

HTarg:

INCIDENT

FMLN

Suspt>d.ed or Arcnst>d hy Ant.horit.ies

is generated from t.lw clause

Salvadoran President.-clt·<·t. Alfredo Crist.iani . .. accused the Farabundo Marti National Lib­ eration f'wnt. (FM LN)

The.se two i ncidPnt.s <U'<' nwrgPd, by merging t.he KILLING ami t.he INCIDI~:NT into a 1\ILLJNn, and by t.aking t.he union of t.lw ot.lwr slot.s.

Incident. :

Perp:

Confid :

IITarg:

KILLING

FMLN

Susp<'d.Pd or Accust·d by A nt.horit.ies

"Rob<>rto (;ar<"ia Alvarado"

Merging is blocked if the incidents have iucompatible types, such as a KlONAPPINC ami a. BOMBING. It is also blocked if they have incon1pat.ihle dal.t·s or lo<"a.t.ions.

There ar<' fairly elabora.t.e mles for 111nging t.he noun groups t.hat. appear in tlw P<·qwt.rator, Physiral Targ_et, and Human Targd slots. A namf' ··.an he nwrged wJt.h a description, as "Garcia" with "at.t.orney general", pro­ vided the description is consistent. wit.h the ot.her descrip­ tions for that. name. A pr<>rist' description can he merged with a vague description, such as "pt·rson", with t.he pre­ cise description as the result . Two precis<' descriptions can be merged if t.hey are selllant.i<"a.lly ronlpat.ible . The descriptions "priest." and ".)<'suit." an· <·ompa.tihl<\ while "priest" and "peasant." are not.. Wheu pr<'cis< ~ descrip­ tions are merged, tlw longest. st.ring is t.akPn as l.hc result.. If merging is impossihle, hot.h 1101111 groups ar<' listed in the slot.

There were 1:3 merges a.lt.oget.lu~r in t.hP pro<'Pssing of the example rnessag<'. Of t.lws<', II wt·re valid.

One of the two bad nwrg<·s was part.icularly unfortu­ nate. The phra.<;e

... Garcia Alvamdo's d1·iw·r, who es<'ap<~d 1111scathed, . . .

correctly generated an att.ack incident. wit.h no injury t.o the human target., the drivPr:

Incident. :

Perp:

PTarg:

HTarg:

HEffect:

ATTACK

"Garcia Alvarado's driver"

No Injury

This was merged with the attack on MPriHo 's home

Incident. :

Perp:

PTarg:

HTarg:

HEtfect.:

BOMBING

"guerrilla.<;"

"Merino's home"

"Merino"

to yield t.he combined incidPnt.

lnrid~~ut.:

Perp:

PTarg:

HTarg:

fl r·:m·<:t:

HOM BING

"guerri lias"

"Merino's home"

"Merino": ''Garria Alvarado's driver"

No Injury

That. is, it. was a.<.;sllllled that Merino was the driver . Tlw reason for this 1nistake was that while a certaiu amount of consist.enry checking is done before merg­ ing vid.ims, and whil<· the system knows that. drivers and vir<' prcsident.s-dert are disjoint sets, the fact. that Merino was t.h(' vir<' president-elect wa.<J reeorded only in a t.ahle of t.it.I<'S, and consistency cheeking did not. consult. t.hat. t.ahle.

4 Controlling the FASTUS System

In t.he ('.ours<' of dt~signing the system, we parameteri:.wd a number of rha.racl.t·ristics of the system's operation be­ cause W<' bdi('ved t.ha.t. the parameterized behavior would reflect. t.radeoffs in rerall versus precision . Subsequent. testing revealed that. many of these parameters result in bot.h higher r<'<:all and higher precision when in one st.at.e or t.h<' ot.lwr, and therefore we left them perma­ nently in tlwir most. advantageous state. Those param­ eters t.ha.t. S<'NII<'d t.o affect. recall at. the expense of pre­ cision W<'rt' s<'t. to produce an optional test run in whir.h we at.t.empt.cd t.o nmximize the system's recall . The ef­ £ect. of t.lws<~ paranwl.t'rs could be described in general as clist.rust.ing the syst.em's filt.ers' ability to eliminate templat.Ps for inrident.s that were defined by the MlJC-4 rules as ht)ing of 110 int.<~rest, including military incidents, incidents in unint.<~ resting eount.ries, and inrident.s that. o<·.cum·d more than t.wo months before the date of the article. Wf' ohscrVf~d a small but mea.<>urable increa.<Je in n~r.all at. the <'Xpt·use of precision by distrusting our filters .

Here we StlllllmHi)f,e some of the more interesting re­ sults we oht.ainNI regarding optimizing our parameter ~~ettings for the M UC-1 evaluatron.

• ConM:r-t>ali't>e Merging. A major empha.<Jis of MUC4, largely b<~cause of its sroring algorithm, wa.<J the proper individuation of inridents. When the Con­ Sf'rvat.ive Merging option is selected in FASTUS, the system would not. merge incidents that had nonoverlapping targets with proper names. When not sdPded, any merges consistent with the inci­ dent. types were permitted. Testing revealed that. merging should always be eonservative.
• Cit>ilian Targfi Req·uirement. Inddents that in­ volved only t.he milit.ary were of no interest in MUC4. The ( :ivilian Target Requirement filter would rt~ed. any t.e111plate that. did not have at lea.<Jt one nonmilit.ary target., induding templates that iden­ tified a perpet.rat.or, but no physical or human tar­ get at all. This option appears t.o produce a recall­ prerision t.radeoff of about one or two point.s. That is, rerall improvt~d at the expense of precision if we distrust.<~d our syst.e111 and assumed that. t.here really

were civiliau t.arget.s but. that they were missed by t.lw syst.f'JII .

• S'uhjedle.ss Vrrh Or-otws. This parameter would al­ low the sysl.<'lll t.o generate an incident structure from a v<·rh t.ogdher with its object, even if its sub­ .i<'ct. could uot. lw determined. Although early tests show<'d a recall-precisiou tradeoff, subsequent and more thorough t.esting indicated that. this should al­ ways he dow·.
• Mililftr:IJ Fillcrin_q. This heuristir causes the system t.o <'lin1inate all1nilit.ary targets from templates, on t.he lwlit>.f t.ha.t. Wt' may have incorrectly merged a military inrid<'nt. wit.h a civilian incident and incor­ rect.ly reported the union of t.he two. Tests show that. t.his filt.<oring improves precision slightly.
• Sprl/in_q Conution. This parameter controls how nHH'h spelling correct.ion the system does. Our ex­ perinu~ nt.s iudicat.<>d that. spelling correction hurts, pri1narily benuiS<' novel proper names get corrected t.o ot.lwr words, and lu~nc~> l'l.ff' lost.. Vt;'e t.ri~>d a weaker version of spelling correction which would rorrect. only misspdled words that. did not. occur on a large list. of proper names that we had assem­ blf~d . This showed an improvement, but spelling rorr<><·t.ion st.ill had a small negative effect. This was also a surprising result, and we were not. will­ ing to abandon spelling correction, and ran all tests with weak spelling ('Orredion enabled, although to some ext.ent. a complete lark of spelling · correction is rompensat.ed for by the presence of common mis~ spellings of import.ant. domain words like "guerrilla" and "assassinate" in the lexicon .
• Slftle /J11IC' Fillc1·ing. This parameter causes filtering of any template t.hat. has a date that is earlier than two months before the date of the article. Elimi­ nating this filtering produces an increase in recall at. the expense of precision, the magnitude of which depends on how well our date detection currently works. We would expert. about a one-point trade­ off.

5 Results in the MUC-4 Evaluation

On a blind test of 100 texts, we achieved a recall of 44% with precision of 55% using the most rigorous penal­ ties for missing and spurious fills. On a different blind t.est of 100 texts covering incidents from a different time span than the t.raining data, we observed, surprisingly, an identical recall score of 44%; however our precision fell to 52%. It wa.<J reas.<Juring t.o see that there was very little degradation in performance when moving to a time period over which the system had not been trained.

We also concluded a test. in which we at.t.empted to maximize the system's recall by not. filtering military tar­ gets, and allowing incidents with st.ale dates. On the first. test set., this led to a two-point iur.rea.<Je in recall at the expense of one point. in precision . On t.he second test. set, our recall did not. increa.<Je, although our precision fell by a point.. These n~sults were consist.ent. with our observations during dt'velopnwnt., although our failure to produce even a small inerease in n~call 011 t.he second l.est. set was somewhat disappointing.

Only General Electric's syst.Pm (.1 acobs et al., 199:2] performed significantly better (a. r<'call of fi2% and a pr<'­ cision of 53% on the first test. set.), and t.lwir syst.enr ha . .-,; been under development for over fivt' years . UivPrr our experience in bringing the syskm l.o il.s current. lewl of performance in three and a half wenks, wt~ feel W<' coultl achieve results in that range with a11oi.IH·r month or l.wo of effort. It is unlikely that. human codPrs would achieve an agreement of more than around 80% on t.his !.ask. Thus, we believe this t.eehnology call JWrfonn 7!i% as well as humans, and considerably fast.t~r .

The system is extremely fast .. Tlw ('llt.ire set. of 100 messages, ranging from a third of a pagt~ t.o t.wo pa.gt·s in length, required 11.8 minutes of CPU t.ime on a Su11 SPARC-2 processor. The elapsed real t.i11w was L!i.!) min­ utes, but observed time depends on t.he partieular hard­ ware configuration involved.

In more concrete terms, this mm1.11s t.hat. f'ASTUS ca11 read 2,375 words per minute. H <'all a.naly;.r,t~ om· t.Pxt. in an average of 9.6 seconds .

6 Conclusions

FASTUS was more successful than WP t-wt~ r· drP<urwd when the idea was originally conct~ivP<I. In rd.rospt-'<'1., we attribute its success to the fad. t.hat. il.s pr·ocessing is extremely well suited to t.lw dema11ds of t.ll<' !.ask. Tlw system's domain-level processi11g works su<·n~ssfully he­ cause the input from phrase n·cog11it.ion is already rP­ liably processed. Phrase recognition does only t.lll' lill­ guistic processing that can be done reliably and fast., ig­ rlOring all the problems of making at.t.achnwnt. derisions, and t.he ambiguity introduced by eoordinat.ion a11d ap­ positives. This input is adequate for t.lw domai11-lt ' Vt~ l processing because the domain is sulfic.it'nt.ly cousl.ra.ined that, given this initial chunking, the relevant. infornral.iou can be reliably detected and ext.ract.ed.

The advantages of the FASTUS syst.ern are as follows:

• It is conceptually simple. It. is a sd. of cascaded finite-state automata.
• The basic system is relatively small, although the did.ionary and other lists are potentially very large.
• It is effective. Only General Electric's system per­ formed significantly bet.t.er t.han FASTUS, and it. has been under development for a number of years.
• It has very fast run time . The average time for an­ alyzing one message is less than J 0 seconds. This is nearly an order of magnit.ude faster t.han compara­ ble systems.
• In part because of the fast. run time, it. has a very fast development time. This is also true because the system provides a very direct. link between the texts being analyzed and t.h<' data IJf'ing extraet.ed.

FAST US is not a text. understanding system. It. is an information extraction system. But. for information extraction tasks, it. is perhaps t.lw most convenient. and most. effective system t.ha.t. has been developed.

One of the lessons to be learned from our FASTUS ex­ perience is that an information extraction task is much easier than anyone ever thought.. Although the full linguistic complexity of the MUC text.s is very high, with long sentences and interesting discourse st.rud.urc problems, the relative simplicity of the information­ extraction task allows much of this linguistic co111plexit.y to he bypassed- indeed much more than we had origi­ nally believed was possible. The key to the wholt' prob­ lem, as we see it from our FASTUS experience, is t.o do exactly the right. amount of syntax, so that. pra.gmaticlJ c.an t.ake over its share of the load . For t.he infomrat.ion extract.ion task, we think FASTUS displays exact.ly t.lw right mixture.