22.4.2 Finite-State Template-Filling Systems

The tasks introduced in the Message Understanding Conferences (MUC) (Sundheim, 1993), a series of U.S. Government-organized information extraction evaluations, represent a considerably more complex template-filling problem. Consider the following sentences selected from the MUC-5 materials from Grishman and Sundheim (1995).

| TIE-UP-1: | |

| --- | --- |

| RELATIONSHIP: ENTITIES: | TIE-UP “Bridgestone Sports Co.” “a local concern” “a Japanese trading house” |

| JOINTVENTURECOMPANY ACTIVITY AMOUNT | “Bridgestone Sports Taiwan Co.” ACTIVITY-1 NT$20000000 |

| ACTIVITY-1: | |

| COMPANY PRODUCT STARTDATE | “Bridgestone Sports Taiwan Co.” “iron and “metal wood” clubs” DURING: January 1990 |

Bridgestone Sports Co. said Friday it has set up a joint venture in Taiwan with a local concern and a Japanese trading house to produce golf clubs to be shipped to Japan.

The joint venture, Bridgestone Sports Taiwan Co., capitalized at 20 million new Taiwan dollars, will start production in January 1990 with production of 20,000 iron and “metal wood” clubs a month.

The MUC-5 evaluation task required systems to produce hierarchically linked templates describing the participants in the joint venture, the resulting company, and its intended activity, ownership and capitalization. Fig. 22.26 shows the resulting structure produced by the FASTUS system (Hobbs et al., 1997). Note how the filler of the ACTIVITY slot of the TIE-UP template is itself a template with slots to be filled.

The FASTUS system produces the template given above, based on a cascade of transducers in which each level of linguistic processing extracts some information from the text, which is passed on to the next higher level, as shown in Figure 22.27

Most systems base most of these levels on finite-automata, although in practice most complete systems are not technically finite-state, either because the individual automata are augmented with feature registers (as in FASTUS), or because they are used only as preprocessing steps for full parsers (e.g., Gaizauskas et al., 1995; Weischedel, 1995), or are combined with other components based on statistical methods (Fisher et al., 1995).

Let's sketch the FASTUS implementation of each of these levels, following Hobbs et al. (1997) and Appelt et al. (1995). After tokenization, the second level recognizes multiwords like set up, and joint venture, and names like Bridgestone

Sports Co.. The named entity recognizer is a transducer, composed of a large set of specific mappings designed to handle the usual set of named entities.

The following are typical rules for modeling names of performing organizations like San Francisco Symphony Orchestra and Canadian Opera Company. While the rules are written using a context-free syntax, there is no recursion and therefore they can be automatically compiled into finite-state transducers.

Performer-Org $ \rightarrow $ (pre-location) Performer-Noun+ Perf-Org-Suffix

pre-location $ \rightarrow $ locname | nationality

locname $ \rightarrow $ city | region

Perf-Org-Suffix $ \rightarrow $ orchestra, company

Performer-Noun $ \rightarrow $ symphony, opera

nationality $ \rightarrow $ Canadian, American, Mexican

city $ \rightarrow $ San Francisco, London

The second stage also might transduce sequences like forty two into the appropriate numeric value (recall the discussion of this problem in Ch. 8).

The third FASTUS stage implements chunking and produces a sequence of basic syntactic chunks, such as noun groups, verb groups, and so on, using finite-state rules of the sort discussed in Ch. 13.

The output of the FASTUS basic phrase identifier is shown in Figure 22.28; note the use of some domain-specific basic phrases like Company and Location.

Recall that Ch. 13 described how these basic phrases can be combined into more complex noun groups and verb groups. This is accomplished in Stage 4 of

| (1) | RELATIONSHIP:\nENTITIES: | TIE-UP\n“Bridgestone Sports Co.”\n“a local concern”\n“a Japanese trading house” |

| --- | --- | --- |

| (2) | ACTIVITY:\nPRODUCT | PRODUCTION\n“golf clubs” |

| (3) | RELATIONSHIP:\nJOINTVENTURECOMPANY:\nAMOUNT: | TIE-UP\n“Bridgestone Sports Taiwan Co.”\nNT$2000000 |

| (4) | ACTIVITY:\nCOMPANY:\nSTARTDATE | PRODUCTION\n“Bridgestone Sports Taiwan Co.”\nDURING: January 1990 |

| (5) | ACTIVITY\nPRODUCT | PRODUCTION\n“iron and “metal wood” clubs” |

FASTUS, by dealing with conjunction and with the attachment of measure phrases as in the following.

20,000 iron and “metal wood” clubs a month.

and prepositional phrases:

production of 20,000 iron and “metal wood” clubs a month.

The output of Stage 4 is a list of complex noun groups and verb groups. Stage 5 takes this list, ignoring all input that has not been chunked into a complex group, recognizes entities and events in the complex groups, and inserts the recognized objects into the appropriate slots in templates. The recognition of entities and events is done by hand-coded finite-state automata whose transitions are based on particular complex-phrase types annotated by particular head words or particular features like company, currency, or date.

As an example, the first sentence of the news story above realizes the semantic patterns based on the following two regular expressions (where NG indicates Noun-Group and VG Verb-Group).

• NG(Company/ies) VG(Set-up) NG(Joint-Venture) with NG(Company/ies)

VG(Produce) NG(Product)

The second sentence realizes the second pattern above as well as the following two patterns:

• NG(Company) VG-Passive(Capitalized) at NG(Currency)

NG(Company) VG(Start) NG(Activity) in/on NG(Date)

The result of processing these two sentences is the set of five draft templates shown in Fig. 22.29. These five templates must then be merged into the single hierarchical structure shown in Fig. 22.26. The merging algorithm decides whether two activity or relationship structures are sufficiently consistent that they might be describing the same events, and merges them if so. The merging algorithm must also perform reference resolution as described in Ch. 21.

22.5 ADVANCED: BIOMEDICAL INFORMATION EXTRACTION $ ^{*} $

Information extraction from biomedical journal articles has become an important application area in recent years. The motivation for this work comes primarily from biologists, who find themselves faced with an enormous increase in the number of publications in their field since the advent of modern genomics — so many that keeping up with the relevant literature is nearly impossible for many scientists. Fig. 22.30 amply demonstrates the severity of the problem faced by these scientists. Clearly, applications that can automate the extraction and aggregation of useful information from such sources would be a boon to researchers.

A growing application area for information extraction in the biomedical domain is as an aid to the construction of large databases of genomic and related information. Without the availability of information extraction-based curator assistance tools, many manual database construction efforts will not be complete for decades — a time-span much too long to be useful (Jr. et al., 2007).

A good example of this kind of application is the MuteXt system. This system targets two named entity types — mutations in proteins and two very specific types of proteins called G-coupled protein receptors and nuclear hormone receptors. MuteXt was used to build a database that drew information from 2,008 documents; building it by hand would have taken an enormously time-consuming and expensive undertaking. Mutations in G-protein coupled receptors are associated with a range of diseases that includes diabetes, ocular albinism, and retinitis pigmentosa, so even this simple text mining system has a clear application to the relief of human suffering.

Biologists and bioinformaticians have recently come up with even more innovative uses for text mining systems, in which the output is never intended for

| Semantic class | Examples |

| --- | --- |

| Cell lines | T98G, HeLa cell, Chinese hamster ovary cells, CHO cells primary T lymphocytes, natural killer cells, NK cells |

| Cell types | citric acid, 1,2-diiodopentane, C |

| Chemicals | cyclosporin A, CDDP |

| Drugs | white, HSP60, protein kinase C, L23A |

| Genes/proteins | carcinoma, breast neoplasms |

| Malignancies | amyotrophic lateral sclerosis |

| Medical/clinical concepts | LAFT, AKR |

| Mouse strains | C10T, Ala64 $ \rightarrow $ Gly |

| Mutations | judo group |

| Populations | |

viewing by humans, but rather is used as part of the analysis of high-throughput assays—experimental methods which produce masses of data points that would have been unimaginable just twenty years ago—and as part of techniques for using data in genomic data repositories. Ng (2006) provides a review and an insightful analysis of work in this vein.