\documentstyle[epsf,jair,twoside,11pt,theapa]{article}
%\input epsf %% at top of file

\jairheading{2}{1994}{89-110}{3/94}{8/94}
\ShortHeadings{Pattern Matching and Discourse Processing}%
{Kitani, Eriguchi, \& Hara}
\firstpageno{89}

%\newcommand{\TEXTRACT}{{\sc textract}}

\begin{document}

\title{Pattern Matching and Discourse Processing in Information 
       Extraction from Japanese Text}

\author{\name Tsuyoshi Kitani \email tkitani@cs.cmu.edu \\
       \addr Center for Machine Translation \\
       Carnegie Mellon University \\
       Pittsburgh, PA 15213 USA
       \AND
       \name Yoshio Eriguchi \email eriguchi@rd.nttdata.jp \\
       \name Masami Hara \email masami@rd.nttdata.jp \\
       \addr Development Headquarters \\
       NTT Data Communications Systems Corp. \\
       66-2 Horikawa-cho, Saiwai-ku, Kawasaki-shi,
       Kanagawa 210 JAPAN}

\maketitle

\begin{abstract}
%\baselineskip = 2\baselineskip

Information extraction is the task of automatically picking up
information of interest from an unconstrained text.  Information of
interest is usually extracted in two steps.  First, sentence level
processing locates relevant pieces of information scattered throughout
the text; second, discourse processing merges coreferential
information to generate the output.  In the first step, pieces of
information are locally identified without recognizing any
relationships among them.  A key word search or simple pattern search
can achieve this purpose.  The second step requires deeper knowledge
in order to understand relationships among separately identified
pieces of information.  Previous information extraction systems
focused on the first step, partly because they were not required to
link up each piece of information with other pieces.  To link the
extracted pieces of information and map them onto a structured output
format, complex discourse processing is essential.  This paper reports
on a Japanese information extraction system that merges information
using a pattern matcher and discourse processor.  Evaluation
results show a high level of system performance which approaches human
performance.

\end{abstract}

%\baselineskip = 2\baselineskip

\section{Introduction}
\label{Introduction}

In recent information extraction systems, most individual pieces of
information to be extracted directly from a text are usually
identified by key word search or simple pattern search in the
preprocessing stage \shortcite{lehnert-muc5,weischedel,cowie,jacobs93b}.
Among the systems presented at the
Fifth Message Understanding Conference ({\sc muc-5}), however, the main
architectures ranged from pattern matching to full or fragment parsing
\shortcite{onyshkevych}.  Full or fragment parsing systems, in which
several knowledge sources such as syntax, semantics, and domain
knowledge are combined at run-time, are generally so complicated that
changing a part of the system tends to affect the other components.
In past information extraction research, this interference has slowed
development \shortcite{jacobs93a,hobbs}.  A pattern matcher, which
identifies only patterns of interest, is more appropriate for
information extraction from texts in narrow domains, since this task
does not require full understanding of the text.

{\sc textract}, the information extraction system described here, uses a
pattern matcher similar to {\sc sri}'s {\sc fastus} pattern matcher \shortcite{hobbs}.  
The matcher is implemented as a finite-state automaton.  Unlike other 
pattern matchers, {\sc textract}'s matcher deals with word matching problems 
caused by the word segmentation ambiguities often found in Japanese 
compound words.  

The goal of the pattern matcher is to identify the {\em concepts}
represented by words and phrases in the text.  The pattern matcher
first performs a simple key-word-based {\em concept search}, locating
individual words associated with concepts.  The second step is a {\em
template pattern search} which locates phrasal patterns involving
critical pieces of information identified by the preprocessor.  The
template pattern search identifies relationships between matched
objects in the defined pattern as well as recognizing the concept
behind the relationship.  One typical concept is the relationship of
``economic activity'' which companies can participate in with each other.

It is usually difficult to determine the relationships among pieces of
information which have been identified in separate sentences.  These
relationships are often stated implicitly, and even if the text
explicitly mentions them the descriptions are often located far enough
apart to make detection difficult.  Although the importance of
discourse processing for information extraction has been emphasized in
the Message Understanding Conferences \shortcite{lehnert,hirschman}, 
no system presented has satisfactorily addressed the issue.

The discourse processor in {\sc textract} is able to correlate individual
pieces of information throughout the text.  {\sc textract} merges concepts
which the pattern matcher has identified separately (and usually in
different sentences) when the concepts involve the same companies.
{\sc textract} can unify multiple references to the same company even when the
company name is missing, abbreviated, or pronominalized.  Furthermore,
the processor segments the discourse to isolate portions of text
relevant to a particular conceptual relationship.  The discourse
segmentation lessens the chance of merging unrelated information
\shortcite{kitani-caia}.

This paper analyzes some evaluation results for {\sc textract}'s discourse
module and describes the {\sc tipster}/{\sc muc-5} evaluation results in order to
assess overall system performance.

\section{{\sc tipster} information extraction task}
\label{tipster-task}

The goal of the {\sc tipster} project sponsored by {\sc arpa} is to capture
information of interest from English and Japanese newspaper articles
about corporate joint ventures and microelectronics.  A system must
fill a generic template with information extracted from the text by a
fully automated process.  The template is composed of several objects,
each containing several slots.  Slots may contain pointers to related
objects \shortcite{tipster}.  Extracted information is to be stored in an
object-oriented database.

In the joint ventures domain, the task is to extract information
concerning joint venture relationships which organizations form and
dissolve.  The template structure represents these relationships with
tie-up-relationship objects, which contain pointers to organization
entity objects representing the organizations involved.  Entity
objects contain pointers to other objects such as person and facility
objects, as shown in Figure \ref{template}.
%\footnote{Figure \ref{template} shows only major objects.}

In the microelectronics domain, extraction focuses on layering,
lithography, etching, and packaging processes in semiconductor
manufacturing for microchip fabrication.  The entities extracted
include manufacturer, distributor, and user, in addition to detailed
manufacturing information such as materials used and microchip
specifications such as wafer size and device speed.  The
microelectronics template structure is similar to that of the joint
ventures but has fewer objects and slots.

Both of these extraction tasks must identify not only individual
entities but also certain relationships among them.  Often, however, a
particular piece of extracted information describes only part of a
relationship.  This partial information must be merged with other
pieces of information referring to the same entities.  For merging to
produce correct results, therefore, correct identification of entity
references is crucial.

\begin{figure}
\begin{center}
\leavevmode
%\epsfile{file=template.ps,height=90mm,width=140mm}
\epsfxsize 140mm
\epsfysize 90mm
\epsfbox{template.ps}
\end{center}
\caption{Object-oriented template structure of the joint ventures domain}
\label{template}
\end{figure}

\section{Problem definition}
\label{problem-definition}

This section first describes word matching problems caused by the 
word segmentation ambiguities.  Difficulties of reference resolution
of company names are then explained.  Issues of discourse segmentation 
and concept merging are also discussed using an example text.

\subsection{Word segmentation}

Japanese word segmentation in the preprocessor gives rise to a 
subsequent {\it under-matching\/} problem.  When a key word in the text
is not found in the word segmentor's lexicon, the segmentor tends to
divide it into separate words.  With our current lexicon, for example, 
the compound noun ``$@Ds7H2r>C(J'' ({\it teikei-kaisyo}), consisting of 
two words, ``$@Ds7H(J'' ({\it teikei}: joint venture) and ``$@2r>C(J'' 
({\it kaisyo}: dissolve), is segmented into the two individual nouns.  
Thus a key word search for ``$@Ds7H2r>C(J'' ({\it teikei-kaisyo}) does not 
succeed in the segmented sentence.

On the other hand, the pattern matching process allows, by default,
partial matching between a key word and a word in the text.
``$@Ds7H(J'' ({\it teikei}) and ``$@6HL3(J\underline{$@Ds7H(J}'' ({\it gyoum-teikei}),
both meaning ``a joint venture'', can both be matched against the
single key word \mbox{``$@Ds7H(J''} ({\it teikei}).  This flexibility
creates an {\it over-matching\/} problem.  For example, the key word
``$@%7%j%3%s(J'' ({\it silicon}) matches ``$@Fs;@2=(J\underline{$@%7%j%3%s(J}''
({\it nisanka-silicon}: silicon dioxide), although they are different
materials to be reported in the microelectronics domain.  These
segmentation difficulties for compound nouns also cause major problems
in word-based Japanese information retrieval systems \shortcite{fujii}.

\subsection{Company name references}

In the corporate joint ventures domain, output templates mostly
describe relationships among companies (as described in Section
\ref{tipster-task}).  Information of interest is therefore found in
sentences which mention companies or their activities.  It is
essential for the extractor to identify topic companies---the main
concern of the sentences they appear in---in order to correlate other
information identified in the sentence.  There are three problems
which make it difficult to identify topic companies.

\begin{enumerate}
\item Missing subject\\
Topic companies are usually the subject of a sentence.  Japanese
sentences frequently omit subjects, however---even in formal newspaper
articles.
The {\sc veniex} system which {\sc nec} presented at {\sc muc-5} can identify the
company implied by a missing subject if there is an explicit reference
to it in the immediately preceding sentence \shortcite{doi,muraki}.
It is not clear whether {\sc veniex} can resolve the missing reference when
the explicit reference appears in a sentence further separated from
the subjectless sentence.

\item Company name abbreviations\\
As is also seen in English, company names are often abbreviated in a
Japanese text after their first appearance.  A variety of ways to 
abbreviate company names in Japanese is given in \shortcite{karasawa}.
The following examples show some typical abbreviations of Japanese company 
names:%

\begin{enumerate}
\item a partial word\\
\fussy
``$@%a%k%;%G%9!&(J\underline{$@%Y%s%D(J}'' $\rightarrow$ ``$@%Y%s%D(J'' \\
 (Mercedes-Benz)$@!!!!!!!!(J(Benz)
\item an English abbreviation\\
``$@F|K\EE?.EEOC!J(J\underline{$@#N#T#T(J}$@!K(J'' $\rightarrow$ ``$@#N#T#T(J''\\
(Nippon Telegraph and Telephone)
\item the first Katakana character $+$ ``$@<R(J''\\
``\underline{$@%"(J}$@%a%j%+%s!&%(%-%9%W%l%9(J\underline{$@<R(J}'' $\rightarrow$ ``$@%"<R(J''\\
(American Express Corp.)
\item the first character of each primitive segment\\
``\underline{$@F|(J}$@K\(J\underline{$@9R(J}$@6u(J'' $\rightarrow$ ``$@F|9R(J''%
\footnote{``$@F|K\(J'' ({\it nihon}: Japan) and ``$@9R6u(J'' ({\it koukuu}: airlines)
are the primitive segments in this example.}\\
 (Japan Airlines)
\item some randomly selected characters\\
``\underline{$@?7F|(J}$@K\@=(J\underline{$@E4(J}'' $\rightarrow$ ``$@?7F|E4(J'' \\
 (Shin-nihon Steel)
\sloppy
\end{enumerate}

Locating company name abbreviations is difficult, since many are not
identified as companies by either a morphological analyzer or the name
recognizer in the preprocessor.  Another problem is that the variety
of ways of abbreviating names makes it difficult to unify multiple
references to one company.

Almost all {\sc muc-5} systems include a string matching mechanism to
identify company name abbreviations.  These abbreviations are
specified in an aliases slot in the company entity object.  To the
authors' knowledge, none of the systems other than {\sc textract} can detect
company name abbreviations of type (d) or (e) above without using a
pre-defined abbreviation table.

\item Company name pronouns\\
Company name pronouns are often used in formal texts.  Frequently used
expressions include \, ``$@N><R(J'' ({\it ryosya}: both
companies), ``$@F1<R(J'' ({\it dosya}: the company), and
``$@<+<R(J'' ({\it jisya}: the company itself).  As shown in
the following examples, resolving the references is particularly
important for full understanding of a text.  Direct English
translation follows the Japanese sentences.

\begin{enumerate}
\item ``$@#X<R$O#Y<R$HDs7H$7!"(J\underline{$@F1<R(J}$@$N@=IJ$r(J\underline{$@<+<R(J}$@%V(J
$@%i%s%I$GHNGd$9$k!#(J'' \\
\hspace*{35mm}$@!J#Y<R!K!!!!(J\,\,$@!J#X<R!K(J\\
``X Corp. has tied up with Y Corp. and sells products of
\underline{the company} by \underline{its own} brand name.''
\hspace{72mm}(Y Corp.)$@!!(J(X Corp.)
\item ``$@#X<R$O$3$NJ,Ln$G$O:GBg<j!#(J\underline{$@F1<R(J}$@$N<RD9$ONkLZ;a!#(J'' \\
\hspace*{44mm}$@!J#X<R!K(J\\
``X Corp. is the biggest company in this field. The president of
\underline{the company} is Mr. Suzuki.''
\hspace{89mm}(X Corp.)
\end{enumerate}

Reference resolution for ``$@F1<R(J'' ({\it dosya}: the company)
is implemented in {\sc veniex} \shortcite{doi}.  {\sc veniex} resolves the pronominal
reference in the same way as it identifies missing company references.
The {\sc crl/brandeis} {\sc diderot} system presented at {\sc muc-5} simply chooses the
nearest company name as the referent of ``dosya''.  This algorithm was
later improved by Wakao using corpus-based heuristic knowledge
\shortcite{wakao}.  These systems do not handle pronominalized company
names other than ``dosya''.

\end{enumerate}

The three problems described in this section often cause individual
information to be correlated with the wrong company or
tie-up-relationship object.  To avoid this error, the topic companies
must be tracked from the context, since they can be used to determine
which company objects an information fragment should be assigned to.
Abbreviated and pronominalized company names must be unified as
references to the same company.

\subsection{Discourse segmentation and concept merging}

In the joint ventures domain, a tie-up-relationship object contains
pointers to other objects such as economic activities (as shown in
Figure \ref{template}).  When a company is involved in multiple
tie-ups, merging information into a tie-up relationship according to
topic companies sometimes yields incorrect results.  Consider the
following example:

\begin{verbatim}
      "X Corp. has tied up with Y Corp. X will start selling products 
       in Japan next month. Last year X started a similar joint venture 
       with Z Inc."
\end{verbatim}

Obviously, the sale in the second sentence is related to the tie-up
relationship of X and Y. However, since the topic company, which is
the subject of a sentence, is X in all three sentences, the sale could also
be related to the X and Z tie-up relationship. This incorrect merging
can be avoided by separating the text into two blocks: the first two
sentences describe the X and Y tie-up, and the last sentence describes
the X and Z tie-up.  Thus, discourse segmentation is necessary to
identify portions of text containing related pieces of information.
The {\sc crl/brandeis} {\sc diderot} system segments the joint ventures text into
two types of text structures \shortcite{cowie}.  It is not known how well
their discourse segmentation performed, however.

Once the text is segmented, concepts or identified pieces of 
information can be merged within the same discourse segment. For example, 
the expected income from a joint venture is often stated in a sentence
which does not explicitly mention the participating companies; they
appear in the previous sentence.  In this case, the joint venture
concept identifying the companies and the income concept identifying
the expected income must be merged so that the latter will be linked
to the correct entity objects.

\section{The solution}
\label{solution}

This section describes details of {\sc textract}'s pattern matcher
and discourse processor as well as the system architecture. 

\subsection{{\sc textract} architecture}

{\sc textract} is an information extraction system developed for the {\sc tipster}
Japanese domains of corporate joint ventures and microelectronics 
\shortcite{jacobs93a,jacobs93b}.  As shown in Figure \ref{architecture}, 
the {\sc textract} joint ventures system comprises four major components: 
preprocessor, pattern matcher, discourse processor, and 
template generator.
Because of its shorter development time, the {\sc textract} microelectronics
system has a simpler configuration than the joint ventures system.  It
does not include the template pattern search in the pattern matcher,
or the discourse segmentation and concept merging in the discourse
processor, as also shown in Figure \ref{architecture}.

\begin{figure}
\begin{center}
\leavevmode
%\epsfile{file=architecture.ps,height=75mm,width=120mm}
\epsfxsize 120mm
\epsfysize 75mm
\epsfbox{architecture.ps}
\end{center}
\caption{{\sc textract} system architecture}
\label{architecture}
\end{figure}

In the preprocessor, a Japanese segmentor called {\sc majesty} segments
Japanese text into primitive words tagged with their parts of speech
\shortcite{kitani91}.  Next, the name recognizer identifies proper
names and monetary, numeric, and temporal expressions.  
{\sc majesty} tags proper names which appear in its lexicon; the name
recognizer identifies additional proper names by locating name
designators such as ``$@<R(J'' ({\it sya}, corresponding to
``Inc.'' or ``Corp.'') for company names.  The recognizer extends the
name string forward and backward from the designator until it meets
search stop conditions \shortcite{kitani93}.
The name segments 
are grouped into units which are meaningful to the pattern matching
process \shortcite{kitani-ipsj}.  Most strings to be extracted directly
from the text are identified by {\sc majesty} and the name recognizer.

Details of the pattern matcher and discourse processor are
given in the following sections. The template generator assembles the
extracted information and creates the output described in Section
\ref{tipster-task}.

\subsection{Pattern matcher}
%\subsubsection{Overview of the pattern matcher}

The following subsections describe 
the {\em concept search} and the {\em template pattern search} in the
pattern matcher which identify concepts in the sentence.  Whereas the
former simply searches for key words, the latter searches for phrasal
patterns within a sentence.  The template pattern search also
identifies relationships between matched objects in the defined
pattern.  In the course of {\sc textract} development, key words and
template patterns were obtained manually by a system developer using a
{\sc kwic} (Key Word In Context) tool and referring to a word frequency list
obtained from the corpus.

\subsubsection{Concept search}

Key words representing the same concept are grouped into a list and
used to recognize the concept in a sentence. The list is written in 
a simple format: {\it (concept-name word1 word2 ...)}. For example, 
key words for recognizing a dissolved joint venture concept can be 
written in the following way:

\begin{verbatim}
                 (DISSOLVED $@Ds7H2r>C(J $@@0M}(J $@>CLG(J) 
                                or
                 (DISSOLVED dissolve terminate cancel).
\end{verbatim}

The concept search module recognizes a concept when it locates one of
the associated words in a sentence.  This simple procedure sometimes
yields incorrect concepts.  For example, the concept ``dissolved'' is
erroneously identified from an expression such as ``{\em cancel} a hotel
reservation''.  Key-word-based concept search is most successful when
processing text in a narrow domain in which words are used with
restricted meanings.

The {\it under-matching} problem occurs when a compound noun in the
key word list of a concept fails to match the text because the
instance of the compound in the text has been segmented into separate
primitive words.  To avoid the problem, adjacent nouns in the text are
automatically concatenated during the concept search process,
generating compound nouns at run-time.  The {\it over-matching}
problem, on the other hand, arises when a key word successfully
matches {\em part} of a compound noun which as a whole is not
associated with the concept.  Over-matching can be prevented by
anchoring the beginning and/or end of a key word pattern to word
boundaries (with the symbol ``$>$'' at the beginning and ``$<$'' at the
end).  For example, ``$>$$@%7%j%3%s(J$<$'' ({\it silicon}) must be
matched against a single complete word in the text.  Since this
problem is rare, its solution is not automatic: system developers
attach anchors to key words which are likely to over-match.

\subsubsection{Template pattern search}

{\sc textract}'s pattern matcher is implemented as a finite-state
recognizer.  This choice of implementation is based on the assumption
that a finite-state grammar can efficiently handle many of the inputs
that a context-free grammar covers \shortcite{pereira}.  The pattern
matcher is similar to the pattern recognizer used in the {\sc muc-4}
{\sc fastus} system developed at {\sc sri} \shortcite{hobbs}.

Patterns for the {\sc textract} template pattern matcher are defined with
rules similar to regular expressions.  Each pattern definition
specifies the concept associated with the pattern.  (For the joint
ventures domain, {\sc textract} uses eighteen concepts.)

In the matcher, state transitions are driven by segmented words or
grouped units from the preprocessor.  The matcher identifies all
possible patterns of interest in the text that match defined patterns,
recognizing the concepts associated with the patterns.  For some
inputs, the matcher must skip words that are not explicitly defined in
the pattern.
%\\{\bf Pattern matching rules}

Figure \ref{pattern} shows definitions of equivalent Japanese and
English patterns for recognizing the concept {\sc *joint-venture*}.
This English pattern is used to capture expressions such as 
``XYZ Corp. created a joint venture with PQR Inc.''  The notation
``@string'' represents a variable matching an arbitrary string.
Variables whose names begin with ``{\sc @cname}'' are called company-name
variables and are used where a company name is expected to appear.  In
the definitions shown, a string matched by ``{\sc @cname\_partner\_subj}''
is likely to contain at least one company name referring to a joint
venture partner and functioning as the subject in a sentence.

The pattern ``$@$O!C$,(J:strict:P'' matches the grammatical particles 
``$@$O(J'' ({\it wa\/}) and \mbox{``$@$,(J''} ({\it ga\/}), which serve as 
subject case markers.  The symbol ``strict''
specifies a full string match (the default in case of template
pattern search), whereas ``loose'' allows
a partial string match.  Partial string matching is useful for
matching a defined pattern to compound words.  The verbal nominal
pattern \mbox{``$@Ds7H(J: loose:VN''} matches compound words such as
``$@4k6H(J\underline{$@Ds7H(J}'' ({\it kigyo-teikei}:
a corporate joint venture) as well as ``$@Ds7H(J'' ({\it
teikei}: a joint venture).

\begin{figure}
\begin{minipage}[t]{70mm}
\begin{verbatim}
     (a)  (JointVenture1 6
              @CNAME_PARTNER_SUBJ
              $@$O!C$,(J:strict:P
              @CNAME_PARTNER_WITH
              $@$H(J:strict:P
              @SKIP
              $@Ds7H(J:loose:VN)
\end{verbatim}
\end{minipage}
\begin{minipage}[t]{70mm}
\begin{verbatim}
     (b)  (JointVenture1 3
              @CNAME_PARTNER_SUBJ
              create::V
              a joint venture::NP
              with::P
              @CNAME_PARTNER_WITH)
\end{verbatim}
\end{minipage}
\caption{A matching pattern for (a) Japanese and (b) English}
\label{pattern}
\end{figure}

The first field in a pattern is the pattern name, which refers to the
concept associated with the pattern.  The second field is a number
indexing a field in the pattern.  This field's contents are used to
decide quickly whether or not to search within a given string.  The
matcher only applies the entire pattern to a string when the string
contains the text in the indexed field.  For efficiency, therefore,
this field should contain the least frequent word in the entire
pattern (in this case, ``$@Ds7H(J'' ({\it teikei}) for
Japanese and ``a joint venture'' for English).
%\\{\bf Pattern selection}

The order of noun phrases is relatively unconstrained in a Japanese
sentence.  Case markers, usually attached to the ends of noun phrases,
provide a strong clue for identifying the case role of each phrase
(subject, object, etc.).  Thus pattern matching driven mainly by
case markers recognizes the case roles well without parsing the
sentence.

Approximately 150 patterns are used to extract various concepts in the
Japanese joint ventures domain.  Several patterns usually match a
single sentence.  Moreover, since patterns are often defined with case
markers such as ``$@$O(J'' ({\it wa}), ``$@$,(J'' ({\it ga}), and
``$@$H(J'' ({\it to}), a single pattern can match a sentence in more than 
one way when
several of the same case markers appear in the sentence.  The template
generator accepts only the best matched pattern, which is chosen by
applying the following three heuristic rules in the order shown:

\begin{enumerate}
\item select patterns that include the largest number of matched
company-name variables containing at least one company name;
\item select patterns that consume the fewest input segments (the
shortest string match); and
\item select patterns that include the largest number of variables
and defined words. 
\end{enumerate}

These heuristic rules were obtained from an examination of matched
patterns reported by the system.  To obtain more reliable heuristics,
a large-scale statistical evaluation must be performed.  Heuristics
for a similar problem of pattern selection in English are discussed in
\shortcite{rau}.  Their system chooses the pattern which consumes the most
input segments (the longest string match), as opposed to {\sc textract}'s
choice of the shortest string match in its second heuristic
rule.\footnote{In Rau and Jacobs' system, the third heuristic rule
seems to be applied before the second rule.  In this case, there should
be little difference in performance between the heuristic rules of the
two systems.}

Another important feature of the pattern matcher is that rules can be
grouped according to their concept.  The rule name ``JointVenture1''
in Figure \ref{pattern}, for example, represents the concept
{\sc *joint-venture*}.  Using this grouping, the best matched pattern can be
selected from matched patterns of a particular concept group instead
of from all the matched patterns.  This feature enables the discourse
and template generation processes to narrow their search for the best
information to fill a particular slot.

\subsection{Discourse processor}

The following subsections describe the algorithm of company name 
reference resolution throughout the discourse.  Discourse 
segmentation and concept merging processes are also discussed.

\subsubsection{Identifying topic companies}

Since no syntactic analysis is performed in {\sc textract}, topic companies
are simply identified wherever a subject case marker such as
``$@$,(J'' ({\it ga}), ``$@$O(J'' ({\it wa}), or ``$@$b(J''
({\it mo}) follows company names.
If no topic companies are found in a sentence, the previous sentence's
topic companies are inherited (even if the current sentence contains a
non-company subject).  This is based on the supposition that a
sentence which introduces new companies usually mentions them
explicitly in its subject.

\subsubsection{Abbreviation detection and unification}

Company name abbreviations have the following observed characteristics:

\begin{itemize}
\item {\sc majesty} tags most abbreviations as ``unknown'', ``company'', 
``person'', or ``place'';
\item a company name precedes its abbreviations;
\item an abbreviation is composed of two or more characters from the
company name, in their original order;
\item the characters need not be consecutive within the company name; and
\item English word abbreviations must be identical with an English
word appearing in the company name.
\end{itemize}

Thus the following are regarded as abbreviations: ``unknown'', ``company'', 
``person'', and ``place'' segments composed of two or more 
characters which also appear in company names previously identified in
the text.  When comparing possible abbreviations against known company
names, the length of the longest common subsequence or LCS
\shortcite{wagner} is computed to determine the maximum number of
characters appearing in the same order in both strings.\footnote{For
example, the LCS of ``abacbba'' and ``bcda'' is ``bca''.}

To unify multiple references to the same company, a unique number
is assigned to the source and abbreviated companies.  Repeated company
names which contain strings appearing earlier in the text are treated
as abbreviations (and thus given unique numbers) by the algorithm
described in Figure \ref{algorithm}.
In the pseudocode shown, all identified company names are stored in 
an associative array named $C$. ``Unknown'', ``company'', ``person'', and 
``place'' segments are also stored in the array as possible abbreviations.  
Company names are sorted in ascending order of their starting position 
in the text and numbered from 1 to $cmax$ (Step 1).  A company name 
string which is indexed $i$ can be addressed by 
$C[i,\,\mbox{{\em ``string''}}]$.  A flag $C[i,\,\mbox{{\em ``eg''}}]$ 
records whether the company name is an English word abbreviation or not.  

\begin{figure}
\begin{enumerate}
\item Step 1: Initialization to assign each entity in $C$ a unique number.\\
for $i$ in $C$ do $(1 \leq i \leq cmax)$\\
\hspace*{4mm}  $C[i,\, \mbox{{\em ``id''}}] \leftarrow i$\\
%\hspace*{4mm}  $C[i,\, \mbox{{\em ``eg''}}] \leftarrow \mbox{{\em ``NO''}}$\\
done
\item Step 2: Search abbreviations and give unique numbers\\
for $i$ in $C$ do $(1 \leq i \leq cmax)$ \\
\hspace*{4mm}  if $C[i,\, \mbox{{\em ``id''}}] \neq i$ then \hspace{20mm} \# {\bf already recognized as an abbreviation}\\
\hspace*{8mm}    continue $i$ loop\\
\hspace*{4mm}  $LENSRC$ $\leftarrow$ length of $C[i,\, \mbox{{\em ``string''}}]$\\
\hspace*{4mm}  for $j$ in $C$ do $(i+1 \leq j \leq cmax)$\\
\hspace*{8mm}    if $C[j,\, \mbox{{\em ``id''}}] \neq j$ then \hspace{15mm} \# {\bf already recognized as an abbreviation}\\
\hspace*{12mm}      continue $j$ loop\\
\hspace*{8mm}    $LEN$ $\leftarrow$ length of $C[j,\, \mbox{{\em ``string''}}]$\\
\hspace*{8mm}    $LCS$ $\leftarrow$ length of the LCS of $C[i,\, \mbox{{\em ``string''}}]$ and $C[j,\, \mbox{{\em ``string''}}]$\\
\hspace*{8mm}      if $LCS \geq 2$ then do \\
\hspace*{12mm}        if $C[i, \mbox{{\em ``eg''}}] = \mbox{{\em ``YES''}}$ and
$LENSRC = LCS = LEN$ then \\
\hspace*{16mm}          $C[j,\, \mbox{{\em ``id''}}] \leftarrow C[i,\, \mbox{{\em ``id''}}]$ \hspace*{6mm} \# {\bf an English word abbreviation}\\
\hspace*{12mm}        else if $C[i, \mbox{{\em ``eg''}}] = \mbox{{\em ``NO''}}$ and $LCS = LEN$ then \hspace{8mm} \# {\bf an abbreviation}\\ 
\hspace*{16mm}          $C[j,\, \mbox{{\em ``id''}}] \leftarrow C[i,\, \mbox{{\em ``id''}}]$\\
\hspace*{8mm}      done\\
\hspace*{4mm}    done\\
done\\
\end{enumerate}
\caption{Algorithm to unify multiple references to the same company}
\label{algorithm}
\end{figure}

Step 2 compares each company name in the array $C$ with all names
higher in the array (and thus later in the text).  When the LCS of a
pair of earlier and later company names is equal to the length of the
later company name, the later company name is recognized as an
abbreviation of the earlier company name.  Then, the ``id'' of the
later company name is replaced with that of the earlier company name.
The LCS must be two or more characters, and if the
abbreviation is an English word, the LCS must be equal to the length
of the earlier company name.

At the end of execution, a number is given in 
$C[i,\,\mbox{{\em ``id''}}]$.  If $C[i,\,\mbox{{\em ``id''}}]$ was
changed during execution, $C[i,\,\mbox{{\em ``string''}}]$ was 
recognized as a company name abbreviation.

\subsubsection{Anaphora resolution of company name pronouns}

The approach for reference resolution described in this section is
based on heuristics obtained by corpus analysis rather than linguistic
theories.  Three company name pronouns are the target of reference
resolution: ``$@N><R(J'' ({\it ryosya}), ``$@F1<R(J''
({\it dosya}), and ``$@<+<R(J'' ({\it jisya}), meaning ``both
companies'', ``the company'', and ``the company itself''.  They are
three of the most frequent company name pronouns appearing in our 
corpus provided by {\sc arpa} for the {\sc tipster} information extraction
project.  ``Ryosya'',
``dosya'', and ``jisya'' appeared 456, 277, and 129 times,
respectively, in 1100 newspaper articles containing an
average of 481 characters per article.

The following heuristics, derived from analysis of pronoun reference
in the corpus, were used for reference resolution:

\begin{itemize}
\item ``ryosya'' almost always referred to the ``current'' tie-up 
company, with one exception in a hundred occurrences;
\item about ninety percent of ``dosya'' occurrences referred to the
topic company when there was only one possible referent in the same
sentence, but:
\item when more than two companies, including the
topic company, preceded ``dosya'' in the same sentence, about
seventy-five percent of the pronoun occurrences referred to the
nearest company, not necessarily the topic company; and
\item about eighty percent of ``jisya'' occurrences referred to the
topic company. 
\end{itemize}
Two additional heuristic rules were discovered but not implemented in {\sc textract}:
\begin{itemize}
\item about four percent of ``jisya'' occurrences referred to more
than one company; and
\item about eight percent of ``jisya'' occurrences referred to
entities which are general expressions about a company such as
``$@2q<R(J'' ({\it kaisya}: a company).
\end{itemize}
As a result of the discourse processing described above, every company
name, including abbreviations and pronominal references, is given a
unique number.

\subsubsection{Discourse segmentation and concept merging}

In the 150 articles of the {\sc tipster}/{\sc muc-5} joint ventures test set,
multiple tie-up relationships appeared in thirty-one articles which
included ninety individual tie-up relationships.  The two typical
discourse models representing the discourse structures of tie-up
relationships are shown in Figure \ref{discourse-structure}.
\begin{figure}
\begin{center}
\leavevmode
%\epsfile{file=discourse-structure.ps,height=60mm,width=75mm}
\epsfxsize 75mm
\epsfysize 60mm
\epsfbox{discourse-structure.ps}
\end{center}
\caption{Discourse structure of tie-up relationships}
\label{discourse-structure}
\end{figure}

\begin{itemize}
\item Type-I: tie-ups are described sequentially \\
Descriptions of tie-ups appear sequentially in this model.  One
tie-up is not mentioned again after a new tie-up has been described.

\item Type-II: a main tie-up reappears after other tie-ups are
mentioned\\ 
A major difference from the Type-I model is that a description of
a main tie-up reappears in the text after other tie-up relationships
have been introduced. Non-main tie-ups are usually mentioned briefly.
\end{itemize}
Eleven Type-I structures and thirteen Type-II structures appeared 
in the thirty-one articles.  Seven of the articles contained complicated 
discourse structures regarding the tie-up relationships.  

The two types of text structure described above are similar to 
the ones implemented in the {\sc crl/brandeis} {\sc diderot} joint ventures 
system.  The difference is only in the Type-II structure: 
{\sc diderot} processes all tie-up relationships which reappear in the text,
not just the reappearing main tie-up focused on by {\sc textract}.

{\sc textract}'s discourse processor divides the text when a different
tie-up relationship is identified by the template pattern search.  A
different tie-up relationship is recognized when the numbers assigned
to the joint venture companies are not identical to those appearing in
the previous tie-up relationships.  {\sc diderot} segments the discourse if
any other related pieces of information such as date and entity
location are different between the tie-up relationships.  Such strict
merging is preferable when the pieces of information in comparison are
correctly identified.  The merging conditions of discourse segments
should be chosen according to the accuracy of identification of the
information to be compared.

After the discourse is segmented, identified concepts and extracted
words and phrases are merged.  Figure \ref{merging} shows the merging
process for the following text passage which actually appeared in the
{\sc tipster}/{\sc muc-5} test set (a direct English translation follows):

\vskip 5mm
\hspace*{5mm}
\begin{minipage}{125mm}
``$@EDJU@=Lt$O#8F|!"@>FH$N0eLt%a!<%+!<!"%(!<!&%a%k%/<R$N?7Lt$NF|K\9qFb$G(J
$@$N3+H/!"HNGd$r$9$kDs7H7@Ls$r7k$s$@!#?7Lt$NHNGd$,$G$-$k$h$&$K$J$k#5!"(J
$@#6G/@h$K$O!"N><R$,@^H>=P;q$7$F9gJ[2q<R$r@_N)$9$k$3$H$b9g0U$7$?!#(J''
\vskip 3mm
``On the eighth (of this month), Tanabe Pharmaceuticals
made a joint venture contract with a German pharmaceutical 
maker, Merck and Co. Inc., to develop and sell its new medicine 
in Japan.  They also agreed that both companies would invest 
equally to establish a joint venture company in five or 
six years when they start selling new medicine.''
\end{minipage}
\vskip 5mm

\begin{figure}
\begin{center}
\leavevmode
%\epsfile{file=merging.ps,height=80mm,width=130mm}
\epsfxsize 130mm
\epsfysize 80mm
\epsfbox{merging.ps}
\end{center}
\caption{Example of concept merging}
\label{merging}
\end{figure}

The two company names in the first sentence, ``$@EDJU@=Lt(J''
({\it tanabe seiyaku}: Tanabe Pharmaceuticals) and
``$@%(!<!&%a%k%/<R(J'' ({\it ei meruku sya}: Merck and Co. Inc.),
are identified by either {\sc majesty} or the name recognizer during
preprocessing.  Next, the template pattern search locates in the first
sentence the ``economic activity'' pattern shown in Figure 
\ref{pattern2} (a).  The 
{\sc *economic-activity*} concept relating the two companies has 
now been recognized.  The template pattern search also recognizes 
the {\sc *establish*} concept in the second sentence by the 
template pattern shown in Figure \ref{pattern2} (b).

\begin{figure}[b]
\begin{minipage}[t]{70mm}
\begin{verbatim}
   (a)  (EconomicActivityE 6
            @CNAME_PARTNER_SUBJ
            $@$O!C$,(J:strict:P
            @CNAME_PARTNER_SUBJ
            $@$N(J:strict:P
            @SKIP
            $@3+H/(J:loose:VN)
\end{verbatim}
\end{minipage}
\begin{minipage}[t]{70mm}
\begin{verbatim}
   (b)  (Establish3 6
            @CNAME_PARTNER_SUBJ
            $@$O!C$,(J:strict:P
            @CNAME_CREATED_OBJ
            $@$r(J:strict:P
            @SKIP
            $@@_N)(J:loose:VN)
\end{verbatim}
\end{minipage}
\caption{Economic activity pattern (a) and establish pattern (b)}
\label{pattern2}
\end{figure}

After sentence-level processing, discourse processing recognizes that
``$@N><R(J'' ({\it ryosya}: both companies) in the second sentence
refers to Tanabe Pharmaceuticals and Merck in the first sentence
because they are the current tie-up companies.  Since the second
sentence does not introduce a new tie-up relationship, both sentences
are in the same discourse segment.  Concepts separately identified in
the two sentences can now be merged because the subjects of the two
sentences are the same.  The {\sc *establish*} concept is therefore joined
to the {\sc *economic-activity*} concept.

\section{Performance evaluation}

This section shows some evaluation results for {\sc textract}'s 
discourse module.  {\sc muc-5} evaluation metrics and overall 
{\sc textract} performance are also discussed.

\label{evaluation}

\subsection{Unique identification of company name abbreviations}

A hundred joint ventures newspaper articles used for the {\sc tipster} 
18-month evaluation were chosen as a blind test set for this 
evaluation.  The evaluation measures were {\em recall}, the 
percentage of correct answers extracted compared to possible 
answers, and {\em precision}, the percentage of correct answers 
extracted compared to actual answers.  {\sc majesty} and the name recognizer 
identified company names in the evaluation set with recall of seventy-
five percent and precision of ninety-five percent when partial matches 
between expected and recognized strings were allowed, and with recall 
of sixty-nine percent and precision of eighty-seven percent in an 
exact matching condition.

Company names that appeared in a form different from their first
appearance in an article were considered to be company name
abbreviations.  Among 318 abbreviations, the recall and precision of
abbreviation detection were sixty-seven and eighty-nine percent,
respectively. Most importantly, detected abbreviations were unified
correctly with the source companies as long as the source companies
were identified correctly by {\sc majesty} and the name recognizer.

The evaluation results clearly show that company name abbreviations
were accurately detected and unified with the source companies as long
as company names were correctly identified by the preceding processes. 
It is possible, however, that the simple string matching algorithm
currently used could erroneously unify similar company names, which
are often seen among family companies.

\subsection{Anaphora resolution of company name pronouns}

The accuracy of reference resolution for ``ryosya'', ``dosya'', and
``jisya'' is shown in Table \ref{ref-accuracy}.  The numbers in 
parentheses were obtained by restricting 
attention to pronouns which referred to companies identified correctly 
by the preceding processes.  Since companies
referred to by ``ryosya'' (both companies) were usually ``current''
tie-up companies in the joint ventures domain, reference resolution
accuracy depended on the accuracy with which tie-up relationships were
identified.

\begin{table}[b]
\begin{center}
\begin{tabular}{|l|c|c|} \hline
company name pronouns                  & number of  & resolution \\ 
		                           & references & accuracy \\ \hline \hline
``$@N><R(J'' ({\it ryosya}: both companies)    & 101 (93)   & 64\% (70\%) \\ \hline
``$@F1<R(J'' ({\it dosya}: the company)        & 100 (90)   & 78\% (87\%) \\ \hline
``$@<+<R(J'' ({\it jisya}: the company itself) & \ 60 (53)  & 78\% (89\%) \\ \hline
\end{tabular}
\end{center}
\caption{Accuracy of reference resolutions}
\label{ref-accuracy}
\end{table}

A major cause of incorrect references of ``dosya'' was the failure to
locate topic companies. The simple mechanism of searching for topic
companies using case markers did not work well. A typical problem can
be seen in the following example:
``$@Ds7H@h$O#X<R!#(J'' (A joint
venture partner is X Corp.).  Here X Corp is a topic company, but the
subject \mbox{``$@#X<R(J''} (X Corp.) is not followed by a subject
case marker.  Other errors can be attributed to the fact that
``dosya'' did not always refer to a topic company as discussed in the
heuristic rules of ``dosya'' reference resolution.

Regarding ``jisya'' resolutions, five instances which should have
referred to multiple companies were bound to a single company.  Since
multiple companies are usually listed using conjunctions such as
``$@$H(J'' ({\it to}: and) and ``$@!"(J'' (comma), they can be
identified easily if a simple phrase analysis is performed.

It became clear from this evaluation that resolving ``dosya''
references to a non-topic company required intensive text
understanding.  Forty-seven percent of the occurrences of ``dosya''
and ``jisya'' were bound to topic companies inherited from a previous
sentence. This result strongly supported the importance of keeping
track of topic companies throughout the discourse.

\subsection{Discourse segmentation}

Thirty-one of the 150 {\sc tipster}/{\sc muc-5} evaluation test 
articles included ninety multiple tie-up relationships.  {\sc textract}'s 
discourse processor segmented the thirty-one articles into 
seventy-one individual tie-up relationship blocks. 
Only thirty-eight of the blocks were correctly segmented.  
Main tie-up relationships which reappeared in Type-II discourse 
structures were not detected well, which caused the structures to 
be incorrectly recognized as Type-I.  This error was caused by the 
fact that the joint venture relationships were usually mentioned 
implicitly when they reappeared in the text.  For example, a noun
phrase, \mbox{``$@:#2s$NDs7H$O(J''} (the joint venture this time), which 
was not detected by the template patterns used, brought the focus back 
to the main tie-up.  As a result, {\sc textract} identified eight percent 
fewer tie-up relationships than the possible number expected in the 
{\sc tipster}/{\sc muc-5} evaluation.  This merging error must have affected 
system performance since the information in the reappearing main tie-up 
segment would not have been correctly linked to the earlier main
tie-up segment.

This preliminary study suggested that recognizing segmentation points 
in the text should be regarded as crucial for performance.  The template
pattern matching alone was not good enough to recognize the segmentation 
points.  The discourse processor simply segmented the text when it 
found a new tie-up relationship.  The discourse models, currently 
unused at run-time in {\sc textract}, could be used to help infer the discourse 
structure when the system is not sure whether to merge or separate  
discourse segments.  Reference resolution of definite and indefinite noun 
phrases must also be solved for accurate discourse segmentation in future 
research.

The accuracy of discourse segmentation might be improved by checking
the difference or identity of date and entity location, as well as
entity name, when deciding whether or not to merge a tie-up
relationship.  {\sc textract} did not take date and location objects into
account in making segmentation decisions, because {\sc textract}'s
identification of these objects was not considered reliable enough.
For example, the date object was identified with recall of only
twenty-seven percent and precision of fifty-nine percent.  On the
other hand, entities were identified with over eighty percent accuracy
in both recall and precision.  To avoid incorrect discourse
segmentation, therefore, {\sc textract}'s merging conditions included only
entity names as reliable information.

\subsection{Overall {\sc textract} performance}

250 newspaper articles, 150 about Japanese corporate joint
ventures and 100 about Japanese microelectronics, were provided by
{\sc arpa} for use in the {\sc tipster}/{\sc muc-5} system evaluation.  Six joint
ventures systems and five microelectronics systems, including
{\sc textract} developed at {\sc cmu} as an optional system of {\sc ge-cmu}
{\sc shogun}, were presented in the Japanese system evaluation 
at {\sc muc-5}.  A scoring program automatically compared the
system output with answer templates created by human analysts.  When a
human decision was necessary, analysts instructed the scoring program
whether the two strings in comparison were completely matched,
partially matched, or unmatched.  Finally, the scoring program
calculated an overall score combined from all the newspaper article
scores.  Although various evaluation metrics were measured in the 
evaluation\,\shortcite{chinchor}, only the following 
error-based and recall-precision-based metrics are discussed in 
this paper. The basic 
scoring categories used are: correct (COR), partially correct (PAR), 
incorrect (INC), missing (MIS), and spurious (SPU), counted as the 
number of pieces of information in the system output compared to the 
possible information. 

\vskip 3mm
\parindent 0mm
(1) Error-based metrics
\parindent 1pc
\begin{itemize}
\item Error per response fill (ERR):
\[
\frac{wrong}{total} = 
\frac{INC + PAR/2 + MIS + SPU}{COR + PAR + INC + MIS + SPU}
\]
\item Undergeneration (UND):
\[
\frac{MIS}{possible} = 
\frac{MIS}{COR + PAR + INC + MIS}
\]
\item Overgeneration (OVG):
\[
\frac{SPU}{actual} = 
\frac{SPU}{COR + PAR + INC + SPU}
\]
\item Substitution (SUB):
\[
\frac{INC + PAR/2}{COR + PAR + INC}
\]
\end{itemize}
\vfill \newpage
\parindent 0mm
(2) Recall-precision-based metrics
\parindent 1pc
\begin{itemize}
\item Recall (REC):
\[
\frac{COR + PAR/2}{possible}
\]
\item Precision (PRE):
\[
\frac{COR + PAR/2}{actual}
\]
\item P\&R F-measure (P\&R):
\[
\frac{2 * REC * PRE}{REC + PRE}
\]
\end{itemize}

The error per response fill (ERR) was the official measure of {\sc muc-5} 
system performance. Secondary evaluation metrics were undergeneration 
(UND), overgeneration (OVG), and substitution (SUB). 
The recall, precision, and F-measure metrics were used as unofficial 
metrics for {\sc muc-5}.

Table \ref{scores} shows scores of {\sc textract} and two other top-ranking 
official systems taken from the {\sc tipster}/{\sc muc-5} system evaluation results.%
\footnote{The {\sc textract} scores submitted to {\sc muc-5} were unofficial. 
It was scored officially after the conference.  Table \ref{scores} shows 
{\sc textract}'s official scores.}  {{\sc textract} processed only Japanese 
domains of corporate joint ventures (JJV) and microelectronics (JME), 
whereas the two other systems 
processed both English and Japanese text.  {\sc textract} performed as well 
as the top-ranking systems in the two Japanese domains. 

\begin{table}[t]
\begin{center}
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|} \hline
$@!!!!(Jdomain     & ERR & UND & OVG & SUB & REC & PRE & P\&R \\ \hline \hline
{\sc textract} (JJV) & 50  & 32  & 23  & 12  & 60  & 68  & 63.8 \\ \hline
System A (JJV) & 54  & 36  & 27  & 12  & 57  & 64  & 60.1 \\ \hline
System B (JJV) & 63  & 51  & 23  & 12  & 42  & 67  & 52.1 \\ \hline \hline
{\sc textract} (JME) & 59  & 43  & 28  & 12  & 51  & 63  & 56.4 \\ \hline
System A (JME) & 58  & 30  & 38  & 14  & 60  & 53  & 56.3 \\ \hline
System B (JME) & 65  & 54  & 24  & 12  & 40  & 66  & 50.4 \\ \hline
\end{tabular}
\vskip 2mm
\hspace*{30mm}
\begin{minipage}{15cm}
\end{minipage}
\end{center}
\caption{Scores of {\sc textract} and two other top-ranking official systems in 
{\sc tipster}/{\sc muc-5}}
\label{scores}
\end{table}

The human performance of four well-trained analysts was reported to be
about eighty percent in both recall and precision in the English
microelectronics domain \shortcite{will}.  This is about thirty percent
better than the best {\sc tipster}/{\sc muc-5} systems' performance in P\&R
F-measure in the same language domain.  In the Japanese joint ventures
domain, {\sc textract} scored recall of seventy-five percent and precision
of eighty-one percent with a core template comprising only essential
objects.  This result suggests that the current technology could be
used to support human extraction work if the task is well-constrained.
Running on a SUN SPARCstation IPX, {\sc textract} processed a joint
ventures article in about sixty seconds and a microelectronics article
in about twenty-four seconds on average.  The human analysts took
about fifteen minutes to complete an English microelectronics template
and about sixty minutes for a Japanese joint ventures template
\shortcite{will}.  Thus a human-machine integrated system would be the best
solution for fast, high quality, information extraction.

Some {\sc tipster}/{\sc muc-5} systems processed both Japanese and English
domains.  These systems generally performed better in the Japanese
domains than in the corresponding English domains.  One likely reason
is that the structure of Japanese articles is fairly standard,
particularly in the Japanese joint ventures domain, and can be readily
analyzed into the two discourse structure types described in this
paper.  Another possible reason is a characteristic of writing style:
expressions which need to be identified tend to appear in the first
few sentences in a form suitable for pattern matching.

The {\sc textract} Japanese microelectronics system copied the preprocessor,
the concept search of the pattern matcher, and the company name unification of
the discourse processor used in the {\sc textract} Japanese joint ventures
system.  The microelectronics system was developed in only three weeks
by one person who replaced joint ventures concepts and key words with
representative microelectronics concepts and key words.  The lower
performance of the {\sc textract} microelectronics system compared to the
joint ventures system is largely due to the short development time.
It is also probably due to the less homogeneous discourse structure
and writing style of the microelectronics articles.


\section{Conclusions and future research}
\label{conclusion}

This paper has described the importance of discourse processing in three
aspects of information extraction: identifying key information
throughout the text, i.e.\ topic companies and company name references
in the {\sc tipster}/{\sc muc-5} domains; segmenting the text to select relevant
portions of interest; and merging concepts identified by the sentence 
level processing.  The basic performance of the system depends on
the preprocessor, however, since many pieces of identified information
are put directly into slots or are otherwise used to fill slots during
later processing.  {\sc textract}'s pattern matcher solves the
matching problem caused by the segmentation ambiguities often found in
Japanese compound words.  The pattern matching system based on a
finite-state automaton is simple and runs fast. These factors are
essential for rapid system development and performance improvement.

To improve system performance with the pattern matching architecture,
an increase in the number of patterns is unavoidable.  Since matching
a large number of patterns is a lengthy process, an efficient pattern
matcher is required to shorten the running time.  Tomita's new
generalized LR parser, known to be one of the fastest parsers for
practical purposes, skips unnecessary words during parsing
\shortcite{bates}.  The parser is under evaluation to investigate if it is
appropriate for information extraction from Japanese text
\shortcite{eriguchi}.  Pattern matching alone, however, will not be able to
improve the system performance to human levels in a complicated
information extraction task such as {\sc tipster}/{\sc muc-5}, even if the task is
well-defined and suitable for pattern matching.  More efforts should
be made in discourse processing such as discourse segmentation and
reference resolution for definite and indefinite noun phrases.

The research discussed in this paper is based on an
application-oriented, domain-specific, and language-specific approach
relying on patterns and heuristic rules collected from a particular
corpus.  It is obvious that the patterns and heuristic rules described
in this paper do not cover a wide range of applications, domains, or
languages.  The empirical approach described here is worth
investigating even for an entirely new task, however, since it can
achieve a high level of system performance in a relatively short
development time.  
While linguistic theory-based systems tend to become complex and
difficult to maintain, especially if they incorporate full text
parsing, the simplicity of an empirically-based, pattern-oriented
system such as {\sc textract} keeps the development time short and the
evaluation cycle quick.

Corpus analysis is a key element in this corpus-based paradigm.  It is
estimated that corpus analysis took about half of the development time
for {\sc textract}.  Statistically-based corpus analysis tools are necessary
to obtain better performance in a shorter development time.  Such
tools could help developers not only extract important patterns and
heuristic rules from the corpus, but also monitor the system
performance during the evaluation-improvement cycle.

%this is how to do an unnumbered subsection
\subsection*{Acknowledgements}

The authors wish to express their appreciation to Jaime Carbonell, who
provided the opportunity to pursue this research at the Center for
Machine Translation, Carnegie Mellon University.  Thanks are also due
to Teruko Mitamura and Michael Mauldin for their many helpful
suggestions.

\vskip 0.2in
\bibliography{jair}
\bibliographystyle{theapa}

\end{document}
