FACILE: Classifying Texts Integrating Pattern Matching and Information Extraction

1 Introduction

Knowledge is nowadays the key source for competitive advantage. The success or failure of a company can depend on the ability to find the right info~matio~ at the right time. The www explosion (and the mcreasmg us­ age of Internet technologies as a core c~annel f?r com­ munication) multiplies the sources of mformatwn and increases by orders of magnitude the amount of infor­ mation available. However, while raising the opportu­ nities for gaining competitive advant~ges, this. also i~­ creases the information glut. The mam value IS not m the information itself, but in the capability of managing it successfully to derive knowledge that is critical to an organisation's objectives. Successfully m~naging i~­ formation means being able to correctly mtegrate It

1 This work was partially funded by the European Union in the framework of the Language Engineering Sector, project FACILE (LE 2440). OFAI is supported by the Austrian BMWV.

Luca Gilardoni Silvia Mazza

Massimo Ferraro

Quinary SpA Via Fara 35 20124 Milan Italy William J. Black Fabio Rinaldi David Mowatt UMIST - PO Box 88 Manchester M60 1 QD United Kingdom

with existing structured information, to facilitate com­ munication and knowledge sharing and to support knowledge-based organisations.

The role of natural language processing and artificial intelligence is fundamental in this respect as: i)_ the va_st majority of this information is textual and avatlable m different languages; ii) the development of new tools for structuring textual data starting from its content rep­ resents one of the fundamental steps in successfully managing information.

This is particularly evident in the business arena, where on-line textual information from news providers has long since been available and heavily used. Recent re­ ports from Gartner Group [Bair, 1998] explicit~y men­ tion advanced classification systems charactensed by semantic technologies as the most strategically relevant element to support effective knowledge management. However, technology available on the market still mainly resorts to information retrieval-derived syste~s and techniques (IR). This technology does not provtde adequate accuracy when coping with rich and complex classification structures. This is because IR systems do not take into account linguistic features. More linguisti­ cally oriented text classification can be achieved by _the use of pattern matching (PM). PM can produce a fatrly accurate and fast categorisation over a large number of classes [Hayes and Weinstein, 1991; Jacobs and Rau, 1990]. Resource development does not require linguis­ tic expertise and can be done by trained users. But PM is still weak on the analysis of linguistic structures and cannot be used for fine-grained categorisation.

Information extraction (IE) techniques can be also used for text classification (e.g., the Text filtering subtask of the ST task in [MUC6]). IE systems perform very well in detecting texts relevant for a single class (e.g. , man­ agement succession) with results ranging between 80-95 for both precision and recall. But IE cannot be per­ formed on a large number of classes: it is an expensive technology as it requires a large amount of time of lin­ guistically aware personnel [Grishman, 1997] . Attemp~s at separating linguistic knowledge (e.g., syntactic knowledge) from domain dependent knowledge (e.g., the domain patterns) [Grishman, 1997; Hobbs et al.,

1997] simplified the task, but did not solve the general problem. Moreover IE systems are still not efficient enough to cope with large amount of texts.

This paper proposes the integration of PM and IE as a method for providing classification highly adaptable to different user needs. Pattern-based (shallow) classifica­ tion performs broad-band text filtering, comparable to that done by a human quickly skimming texts, i.e. rec­ ognising main topics without careful reading. IE is used to provide more fine-grained classification, comparable to that produced by a careful human reading. IE is used to cope with only some of the classes, i.e. those on which shallow classification results need to be refined.

Classification provided in this way is very adaptable to user needs as it provides flexibility in different direc­ tions: broad/fine-grained classification, large/restricted number of classes, high/low efficiency in the process. It is also flexible in terms of application development. PM rules take less time to develop than IE resources: a PM­ based application can be provided as a first (although not complete) answer, waiting for a more complete in­ tegrated PM+IE application to be developed.

The FACILE system (Fast and Accurate Categorization of Information by Language Engineering) is based on this two-tiered approach. It is able to categorise in de­ tail business texts such as agency news, newspaper ar­ ticles and analysis reports from different sources and written in different languages (currently English, Ger­ man, Italian, and - to some extent - Spanish). The sys­ tem has been developed as an applied research project, bringing together researchers and end-user organisa­ tions. It was delivered as a pre-engineered prototype and evaluated by three users participating in the project (an Italian rating agency, a Spanish savings bank, and a German information broker). The system has been adopted by the main Italian financial news agency for production use. It currently provides classified news both for internal work organisation and as an external pay-to-view service.

In this paper we describe the system, focusing on archi­ tectural and evaluation issues. We believe that our ap­ proach is interesting because, although it does not pro­ pose completely new technologies, it demonstrates that innovative technologies can be profitably integrated to build applications providing high added-value services.

2 System architecture

The system architecture has been driven by the idea of providing classification highly adaptable to user needs. The first need addressed is that of providing a refinable classification strategy, resorting to information extrac­ tion only when needed. In general classification is ob­ tained via a multi-step process, where each step adds information to the input. A control module activates the different modules in order to assign the appropriate level of classification needed by the user for each text. To do that the control module uses the information progressively augmented by the different modules to each text. It is this module that decides whether or not IE is to be performed on a specific text. The other modules in the architecture are the preprocessor, the shallow ana­ lyser, the deep analyser and a group of application­ specific modules. From the point of view of flexible classification the preprocessor implements tasks that are to a large degree application independent, such as segmentation, normalisation of numbers, dates and ab­ breviations, as well as morphological analysis, part of speech tagging, preliminary unknown word guessing and named entity recognition. It does not require major adaptation for new applications. The shallow analyser performs a preliminary classification by exploiting techniques that can be easily tailored to new applica­ tions by trained personnel; it is based on pattern matching and assigns a set of classes to each text. The deep analyser performs more fine-grained classifica­ tion via IE. It produces filled templates pertaining to the categories selected by the shallow analyser. It can be ported to new classes by linguistically-trained per­ sonnel only. Application layers are constituted by an additional group of modules that permits the adaptation of the system to different user environments. In the rest of this section we will analyse each module separately.

2.1 Preprocessor

The preprocessor transforms a stream of characters into analysed tokens. It provides morpho-syntactic informa­ tion and a disambiguated syntactic tag for each token in the input, treating proper names as single tokens and assigning them a (disambiguated) semantic tag. The key steps are the same for all the languages considered (currently English, Italian, German and Spanish) and use the same machinery with language-specific re­ sources. The steps are: (1) tokenisation (splitting of in­ put text, assignment of orthographic features); (2) mor­ phological analysis (stemming and assignment of mor­ pho-syntactic information); (3) part of speech tagging (disambiguation of multiple morpho-syntactic catego­ ries); (4) database lookup (assignment of semantic features); (5) named entity analysis (NEA). Steps 2 and 3 integrate generic resources and machinery provided by InXight Inc. LinguisticX. Database lookup adds seman­ tic features (e.g. person, organisation, location etc., but also auxiliary categories, such as verb-of-speech, used as clues in NEA) for (possibly multi-word) tokens in the database. The information in the database is to be re­ garded as provisional and necessarily incomplete. For example, while "Pearl" may be in the database as a first name, "Pearl Harbor" is not a person name. Therefore more informed methods for correctly identifying named entities are needed. NEA uses non-deterministic chart parsing. The approach used has been partially suggested by [Coates-Stevens, 1992]. NEA recognises complete names as well as numbers or time expressions. Unlike other approaches (e.g., [Mikheev et al., 1998]), a high­ level language is used for the definition of the patterns. NEA uses language-specific context-sensitive rules that can take into account any information placed in the chart by preceding modules. NEA employs a weighting mechanism that enables it to either return all competing analyses or to select the most plausible one [Black et al, 1998]. The preprocessor input is a zoned text, i.e. with parts to be analysed identified and marked up. Its output is a text where each (group of) word(s) is associated with orthographic and morphological features, normal­ ised form and semantic labels (e.g. "John Smith" is a "proper name" with orthographic class "capitalised", feature "masculine" and semantic tag "person") .

2.2 Shallow Classifier Module

The shallow classifier (SCM) is based on pattern matching. It operates in two stages: first it recognises domain relevant concepts mentioned in texts, and then assigns categories to the text. The first step is per­ formed by the shallow analyser. It is based on a refined version of the model presented in [Gilardoni et al., 1994], in turn derived from seminal work by [Hayes and Weinstein, 1991]; the shallow analyser models both domain objects (e.g., shares, market sectors, balance sheet items) and domain events (e.g., joint ventures, public offers, financial transactions). Its pattern match­ ing techniques are integrated with a knowledge repre­ sentation system. Concepts are associated with a set of weighted linguistic patterns. The pattern language is similar in spirit to those implemented by search engines (e.g., use of Boolean operators, proximity, optionality), but is augmented to enable testing of lexical variants, exploiting information from the preprocessing stage. It is also tightly coupled with the knowledge representa­ tion language, allowing references to concepts in pat­ terns, exploiting inheritance and relations to reduce complexity. The result of shallow analysis is a set of matches of text portions with concepts with scores, ex­ pressing confidence factors. Matches maintain reference to the part of text matched enabling them to be used for annotation of texts. The second step is performed by a rule-based categorizer. The text's main topic is determined using application-specific heuristics (based on both concept matches and context), as well as domain knowledge. The shallow analysis and categorizer use similar but distinct concept lattices, implemented in the same KR formalism. The categorizer' s lattice directly reflects the end-user's perception of the application­ specific conceptual space. Both are domain-dependent, but application specificity is kept confined in the cate­ gory lattice, resulting in a domain model largely shara­ ble by different applications coping with different clas­ sification structures. The patterns that characterise con­ cepts are obviously language dependent. But they are kept associated to concepts, i.e. they are domain moti­ vated and not linguistically motivated. Developing a multilingual application they can be handled in an ho­ mogeneous way.

The whole machinery is supported by modular declara­ tive resources to describe concepts, patterns, categories and classification rules. The modularization of these resources allows easy development, maintenance and portability across both languages and applications. It also diminishes the major drawback of a knowledge­ based approach (i.e., the complexity in building the knowledge base), while retaining the major benefits (i.e., attainable accuracy and consistency).

On the other side, alternative classification criteria or a different category lattice imply modification to the categorizer' s resources (rules) but not necessarily to the domain knowledge encoded in the concepts network or in the associated patterns.

2.3 Deep Analyser Module

The Deep Analyser Module (DAM) performs informa­ tion extraction to achieve fine-grained classification. It classifies texts by their content, for example by allow­ ing the user to express a query such as "send me any texts concerning bonds issued by European-based fi­ nancial institutions whose amount exceeds 1 million Euro". DAM's task is similar to the ST task in MUC conferences ([MUC, 1998]), but the kind of templates needed for classification are generally flatter than those used in MUC (see the section on evaluation for an ex­ ample). DAM is based on cascades of Finite State Transducers (FSTs). The global architecture is depicted in figure 2. DAM receives as input the pre-processed and classified text and produces filled templates. The whole architecture uses the same formalism, and the same set of primitives for all FSTs. Each FST operates on string of tokens. Tokens are abstract representations of lexical elements that have three types of realisations accessible at any time during analysis: lexical (strings, NEs, etc.), syntactic (parse trees, Typed Feature Struc­ tures) and semantic (Quasi Logical Forms, QLFs) [Ciravegna and Lavelli, 1999]. The first module ap­ plied is the parser. It assumes that there is one and only one possible correct parse tree for each sentence. Its goal is to produce a sufficient approximation of such a parse tree, i.e. a tree that captures all the relations useful for information extraction, while leaving the others implicit. Parsing is performed in three steps: identifica­ tion of NPs, VGs and PPs (chunking), A-structure rec­ ognition (i.e., recognition of subcategorization frames of verbs, some NPs, etc.), and modifier attachment. The output of the parser is a parse tree with the relevant modifiers attached, a Typed Feature Structure represent­ ing relations among constituents in the parse tree and a QLF. The accuracy in producing the correct A-structure reached P=95%, R=71% in a blind text on 62 texts [Ciravegna and Lavelli, 1998]. Following parsing, de­ fault reasoning is applied to introduce in the QLF addi­ tional information not explicitly contained in the text, but needed for template filling (e.g., "if a person work­ ing for company X is hired by company Y, s/he is no longer employee of X").

After this, discourse processing is performed: (pro)nominal references are resolved for both objects (people, organisations, physical objects) and events (e.g., hiring/firing); implicit relations are also captured (e.g., "The Bank of Japan decided ... . The president said .... "). High accuracy is reached in discourse proc­ essing as the amount of available information (i.e., parse tree with associated information in the Typed Feature Structures and in the QLF) allows reliable choices among candidates. Templates are finally filled by using the final QLF (as produced by an additional default reasoning step). Template merging and recovery actions cope with missing information.

Portability was a main requirement for DAM. The module can be ported to new domains by just modifying declarative resources: the lexicon, the knowledge base and the FST grammars. The grammars are sequences of cascades of FSTs. All grammars use the same formal­ ism and primitives (15 in all). This uniformity is an important advantage, allowing new applications to be developed · by a single person. The distinction between domain dependent and domain independent resources simplifies the porting; currently there are 14 FST cas­ cades: 6 are domain independent, 7 are domain depend­ ent and one is user dependent (i .e., the template presen­ tation module). Porting to new applications required one to three man months, depending on the application.

2.4 Around the Kernel: Application Layer

One of the main user-needs is the integration of the system directly into the user environment. For this rea­ son the system architecture is divided in two main blocks: the Classification Kernel (composed by the four modules mentioned above) and the application layer.

The Classification Kernel is currently deployed as a standalone Unix module, configurable within a full de­ velopment environment or stripped down to a runtime executable, accessible by application layers using dif­ ferent communication protocols, including sockets and http. An NT version is currently in an alpha release.

The classification kernel is concerned only with text analysis, expecting as input a normalised, tagged text and providing as output an annotated text. Input and output tagging is currently based, due to historical rea­ sons, on HTML extended to carry structural informa­ tion, with work on XML support ongoing. Both formats are dynamically configurable to support different text sources . The application layer is responsible for inter­ action with the real world, i.e. of feeding the catego­ rizer and of handling categorisation results to make them available to final users. Application can be exten­ sively customised or modified to properly integrate within different Information Technology infrastructures. Four applications have been so far implemented with the system, spanning four languages and with different scopes over the classification domains. All of them are different in terms of IT integration, but all share a common model with a source and annotated text reposi­ tory (based on Oracle, Fulcrum and in two cases on flat files in a shared file system) residing on either Unix or NT systems, simple feeders alimenting the kernel run­ ning on connected Spare, and different intra/internet interfaces towards annotated text repository.

3 EVALUATION

The system was evaluated on different corpora for dif­ ferent languages in different application environments. It was subject to extensive albeit informal tests during development using corpora composed by (in at least one case) several thousands texts. The three analysis mod­ ules were formally evaluated against user tagged cor­ pora by using automatic tools either acquired, such as the MUC scorer, or internally developed. In the follow­ ing we will focus on the formal evaluation first, discuss­ ing each module separately. Results are not independ­ ent, as the modules operate in a chain: e.g. results of the shallow classifier discount the errors introduced by the preprocessor. However, as soon as former modules start to deliver reasonable results (e.g. in line with those re­ ported below), chain effects become negligible and, in some case, could be recovered at a later stage. The ad­ vantage given by the integration of pattern matching and IE techniques is moreover not measurable in terms of percentage gains. Being able, for example to dis­ criminate bond issue story depending on amount threshold is currently completely out of reach without IE techniques - while on the other side not being able to properly drive IE has generally dramatic effect as well on both precision and recalL

3.1 Preprocessor

Formal evaluation of the preprocessor was done for named entity recognition in three languages (English, Italian, German). Two corpora of newswire messages were selected for each language, one used for building and enhancing the NE rules, the other one used as the corpus for a blind test. For Italian and German the cor­ pus has been selected from sources in normal use at user's sites. For English, the test corpus chosen was the MUC-7 Dry-Run corpus, which gave better compara­ bility with the procedure adopted with the other lan­ guages than the Formal Run, in which domain differed between training and testing. Annotation of these cor­ pora was performed manually in the form of SGML markup using appropriate tools. Preprocessor results were delivered by the system in SGML-annotated form; these results were compared to the pre-annotated ver­ sion using the MUC scoring scheme. See Table 3 for evaluation results

3.2 Shallow Categorizer Module

The shallow categorizer has been evaluated formally in a blind test for Italian and German, on two specific applications. For both languages a test set was selected by end users from usual text sources the system was expected to analyse (agency news and financial news­ paper); the blind test was performed on 75 texts for Italian and 50 for German. An English version of the Italian application was also evaluated with comparable results, albeit in a less formal way using material from Reuters corpus (http://www.research.att.comriewis/) re-annotated with respect to the category structure handled by the system. The Italian application was re­ quired to classify texts against a set of about 100 cate­ gories arranged in a hierarchy. The classification ranged over several financial domain topics. Top-level ele­ ments were company news (especially company results, capital and stake operations, ratings, bond issues, man­ agement changes and meetings), sector news (refined by specific market sectors and behaviours), and stock mar­ ket related news. The German application classified over a hierarchy describing country economic indicators (inflation, employment, etc.) also discriminating by country and by whether the indicator figures were men­ tioned as measured data or as forecast.

A first measure for precision and recall was taken, con­ sidering each category in isolation, i.e. independently of its position in the hierarchy. On this basis, whenever a superordinate category is assigned by the system, this is marked as an error for both the most specific ones (lowering the recall) and for the more general assigned (lowering the precision). The table below summarises the results obtained; please note that English figures were o b . d "hi I d d d tame Wit argely un er evelooe resources:

As categories are defined hierarchically they do not induce disjoint partitions. This means that whenever the system 'takes risks' in assigning more specific catego­ ries, e.g. wrongly assigning 'annual results' whenever the correct category should have been the more general 'economic results' this is not an error with respect the more general one. Analogously, if the application 'stays conservative' and misses a more specific category, the assignment of an ancestor should count as evidence for the more specific category anyway. Taking this into account, as in [Gilardoni and Rocca, 1995], higher pre­ cision and recall than above are obtained for interme­ diate categories. Although less significant from the point of view of system comparison, it is however far more significant from the user point of view, as when­ ever the hierarchy is, as in our case, structured and deep, the user would likely exploit the structure query­ ing at intermediate levels.

3.3 Deep Analyser Module

For Italian, one template filling was fully developed (Bond-issue) and two others have reached the level of demonstration (management succession in companies and company annual results). For English a demonstra­ tor for the field of economic indicators was developed. Here we will focus on bond issues in Italian. The in­ formation to be extracted for each bond issue included: issuer, kind of bond, amount, currency, placement date, interest date, maturity, average duration, global rate and first rate. The corpus (used both for training and test) included 95 texts (agency news and newspaper articles, globally 10,472 words). Number of slot fills per text: 6.4. The test was performed as follows: first the direc­ tives for the annotator were developed and the texts tagged by a person; then DAM was instructed to operate in the domain (by just modifying declarative resources) and run on the corpus . Finally DAM results were com­ pared against the user defined answers by using the MUC scorer [Douthat, 1998]. The development cycle was organised as follows: DAM resources were devel­ oped by carefully inspecting the first 30 texts of the corpus. Then the system was compared against the whole corpus (95 texts): results were Recall=.51, Pre­ cision=.74, F(l)=.60. Then the resources were tuned on the whole corpus, focusing on the texts that did not reach sufficient results in terms of R&P. The final re­ sults on the whole corpus were P=.80, R=.72, F(1)=.76.

3.4 User Validation

Formal evaluation enables system comparison and also provides useful information for technical development. Nevertheless, real evaluation comes by user validation (is this the right system?) and by real usage. End users from financial institutions were involved at each stage in development, with feedback incorporated in proto­ types released. The adoption of the system for produc­ tion use by a major Italian news agency, not involved in development and moreover putting the system at work already when only a preliminary and largely incomplete prototype was available, is a clear proof of the validity and usefulness of the approach.

4 Conclusion

We have described the design and evaluation of an ad­ vanced system for fine-grained text categorisation. The system is highly modular, both in its processing filters and in its declarative resources. This has permitted it to be applied to a range of application domains in four European languages. The architecture brings together PM and IE. The system has been a considerable suc­ cess story: it has been adopted by the main Italian fi­ nancial news agency for providing a pay-to-view inter­ net service. The system integrated many heterogeneous software components. It has been running continuously in the user environment since January 1998. Applica­ tions at user sites involved in the consortium are also available. We contend that this shows that state-of-the­ art AI techniques are mature enough to provide real world applications. The architecture is designed in or­ der to separate knowledge intensive resources (DAM's), from less knowledge intensive modules (SCM's), from domain independent modules (preprocessor's). This approach simplifies resource development both in terms of required expertise and in terms of task complexity. In the future we will continue working in the direction of the time-to-market reduction, in order to considerably enlarge the market for fine grained classification sys­ tems. In particular we will investigate the use of ma­ chine learning techniques for resource development.

Acknowledgements

Participants to the FACILE project were: Quinary SpA, ITC-IRST, Italrating SpA (IT), OFAI, Serna SAE (ES), Caja de Segovia (ES), Sis (DE), UMIST-CCL. The authors would like to thank all the project team, in par­ ticular P. Prunotto, V. ·Fiorentino and K. Schirmer.