In this paper we describe a semi-automatic approach to generating event extraction patterns for free texts. The algorithm is composed of four steps: we automatically extract possible events from a corpus of free documents, cluster them using dependency-based parse tree paths, validate random samples from each cluster and generate linear patterns using positive event clusters. We compare our algorithm with the system that uses manually created patterns.
The event extraction (EE) task is formulated as “to automatically identify the events in free texts and derive detailed information about them, ideally identifying who did what to whom, when, with what methods, where and why”. Events involve entities and relations between them and imply a change of state. For instance, the sentence “Palm was acquired by Hewlett-Packard for $1.2 billion two days ago” mentions an event of the type Mergers & Acquisitions (M&A) with four arguments - acquirer (Hewlett-Packard), acquiree (Palm), monetary expression ($1.2 billion) and temporal expression (two days ago). There is also an event indicator (was acquired). An event indicator is a word or a sequence of words that clearly signal about the possible presence of an event.
EE has been the subject of active research for more than twenty years since the series of MUC conferences started in 1987. Initially, EE task was limited to several domains and had small-sized corpora at its disposal. Nowadays, with the rapid evolution of socially-oriented Internet, it is becoming a crucial task for businesses to analyze millions of documents with multilingual content each day with minimal latency in order to get insight and provide critical decisions in time. We believe that modern and effective solutions to EE task would allow businesses to dramatically minimize the time required to start making use of new sources of information and reduce the operating costs of such systems.
One of the popular approaches to information extraction (IE), and EE as a sub-problem of IE in particular, is in the use of domain specific extraction patterns such as linear extraction patterns for annotation graphs and patterns for dependency-based parse tree (DPT) structures. In this paper we present our approach to semiautomatic generation of linear extraction patterns for annotation graphs while using DPT patterns in the process of constructing the first ones.
The paper is structured as follows. In the next section we briefly outline related work, in particular, we give an overview of the papers that propose algorithms minimizing human efforts required to build extraction patterns. In section 3 we describe in details four steps of the algorithm. Section 4 presents the results of experiments. We conclude in section 5 by summarizing the results and outlining current and future work. 2
One of the most known algorithms that learn multi-slot extraction patterns for free texts is Whisk [10]. It requires an annotated corpus of documents and syntactic parse data provided with it.
The problem of learning conventional character-based regular expressions from annotated corpora is described in [8]. The authors demonstrate the applicability of their method in extracting such structured entities as software names, URLs, phone and course numbers. It is still an open question if their approach can be effectively applied for extracting higher level structures such as relations or events.
Snowball [
ExDisco uses a different approach to deal with the problem of absence of annotated corpora. It divides a corpus into two parts (relevant and irrelevant documents) and uses the following assumption: relevant documents contain relevant events and relevant events are present in relevant documents. ExDisco uses a small seed of 2 or 3 known patterns to first divide documents, then it does the syntactic analysis of every sentence and uses its results for pattern generation.
As opposed to conventional IE from relatively small
annotated corpora, Open Information Extraction (OIE)
deals with large Web-sized unannotated sets of
documents. The two most known information extraction
systems that do OIE are KnowItAll [
The algorithm requires the documents to be annotated with named entities that might be the arguments of events. They include not only such named entities as persons, companies, positions and event indicators, but also temporal and monetary expressions. A complete set of required named entities depends on the types of events to be extracted. We use available NERs (in particular, we use OpenNLP library) which we trust. It means that we consider texts annotated by appropriate NERs as the gold standard and we do not consider confidence of extracted entities (if NERs provide such information) during the process of evaluating the extraction patterns.
We also assume that if two events are extracted by the same DPT pattern, they both are either true or false. More generally, a group of N events all extracted by the same DPT pattern contains only either true or false events. A verity of the group is determined by the verity of a random sample drawn from it. This is the main assumption that allows us to minimize human efforts required to produce extraction rules by validating only such a small random sample but not the whole entire group that might contain tens of thousands of events.
As we have mentioned, the algorithm is composed of four steps. At the first step we extract possible events from an unannotated corpus of documents. 3.1
Any event type is described by an indicator (a word that most clearly signals about the event presence, usually, a verb) and arguments together with their semantic types. For instance, an event of the type M&A is described by an event indicator of the type AcquisitionIndicator and two arguments: acquirer of the type Company and acquiree of the type Company as well. Another example is an event of the type PersonAnnouncement that is described by an indicator of the type AnnouncementIndicator and one argument announcer of the type Person. Formally, an event is defined as the following triple:
E T; I; fAiN ; AiT gim=1 (1) where T is the event type, I is the type of event indicator,the event has m arguments and the i-th argument has a name AiN and type AT .
i
The core idea at the first step is to generate all possible events for every sentence in the corpus. To do it, we have built the processing pipeline presented at fig. 1. The primary task of this pipeline is to recognize instances of event indicators and named entities that might be arguments of events.
The pipeline has a typical architecture intended for extracting named entities. Initially, it splits text into sentences and tokens. After that, it uses Named Entity and Event Indicator Recognizers to extract named entities and event indicators. We use OpenNLP library to extract named entities and a dictionary-based recognizer to extract event indicators.
The last component of the pipeline (Possible Event Extractor) uses previously extracted information together with the description of events in order to extract possible events. First, this component determines if a sentence may contain at least one event of any type. To do it, it iterates over the description of event types. For each event type, it determines if a sentence contains (1) an indicator of the appropriate type, and if so (2) a minimal number of the appropriate named entities. For instance, for the event of the type PersonAnnouncement a sentence must contain at least one indicator of the type AnnouncementIndicator and at least one named entity of the type Person. For the event of the type M&A, a sentence must contain at least one indicator of the type AcquisitionIndicator and at least two named entities of the type Company. If a sentence cannot contain a mention of at least one event, it is not processed further.
If there can be at least one event mention in the sentence, we apply the Stanford parser to obtain DBT. For every type of the event T, for which there can be at least one event mention, we generate all possible events. At the first step, we construct a list of all appropriate event indicators fIgin=1 found in the sentence. Then we construct a set of named entities that will be a part of possible events. We compute the shortest paths in DPT from indicators to every named entity in this set. We then generate all possible events around each event indicator. For every possible event, we construct its pattern id - a non unique string that is composed of the event type information and DPT paths. Two events of the same type having the same paths from indicators to arguments will have the same pattern id. The format of the pattern id is the following: Indicator Attribute1T ype (CoveredT ext1):P ath1, Attribute2T ype (CoveredT ext2):P ath2, ... For instance, the event mentioned in the sentence “Google acquires Neotonic Software” has the pattern id AcquisitionIndicator Company(Google):nsubj, Company(Neotonic Software):dobj.
It is possible to count the number N of the events that are generated around each indicator. Let us denote the number of distinct types of arguments as m=, and for each j-th distinct type let Sj be the number of arguments in the event definition of this type, and let Nj be the number of named entities of this type in a sentence. Then there can be Pj (Nj ; Sj ) = Nj !=(Nj Sj )! variants to fill Sj arguments with Nj named entities. To compute the number of possible events, we need to multiply all these values N = Qm=
j=1 Pj (Nj ; Sj ).
Due to limitations of the Stanford parser, only those sentences that have less than 80 tokens are processed. 3.2
Once the input corpus has been processed and all possible events have been identified, at the second step we group the events according to their pattern id. All events inside every group have the same pattern id. In other words, they are all extracted by the same DPT pattern. We sort the groups by cardinality and generate a random subset for each group. 3.3
At the third step an assessor validates a small random subset of each cluster using UIMA Cas editor1 inside Eclipse IDE. This editor (fig. 2) highlights text fragments that mention possible events. For every possible event, this tool provides detailed information such as its indicator and arguments that are also highlighted in the text. The assessor should iterate through every possible event, decide if a particular event is true or false and in case it is true, set its verity flag to true. Finally, the system annotates the groups of events as positive or negative based on the subsets validated by the assessor at the previous step. This is done by counting the number of true and the number of false events in the subset. If there are more positive events in the subset, the whole group is annotated as positive, and vice versa. Positive groups are used further to generate and generalize event extraction patterns.
The input data for the pattern generation algorithm is the sentence annotation graph. The graph contains such annotations as events, their indicators and arguments (named entities) and sentence context which is presented as types of tokens in the notation of the TextMARKER[7] type system (fig. 3). We use the bottom-up generalization strategy and start with the most specific version of a pattern. We generalize patterns until the F1-measure of the new ones increases.
1: procedure GENERALIZERULE(rule) 2: 0 3: 4: 5: 6: 7: 8: 9: 10: 11: newF 1 12: rule 13: end if 14: end while 15: return (rule) 16: end procedure curF 1 newF 1 TESTRULE(rule) while (newF 1 curF 1) > 0 do curF 1 newF 1 rules empty list rules:add(BESTRULE(BOTTOMUPGEN(rule))) rules:add(BESTRULE(QUANTMODIF(rule))) if NEWRULESUNKNOWN(rules) then newRule BESTRULE(rules)
TESTRULE(newRule) newRule (a) generalizing a word to its type: “recently” ! SW; “May” ! CW; “INC” ! CAP (b) generalizing the type of a word to its immediate parent type:
SW, CW, CAP ! W (c) generalizing the types of punctuation marks to their parent type:
COLON, COMMA, SEMICOLON ! PM (d) generalizing the types to their parent types:
W, PM ! ANY
2. QuantModif : quantifier modification
(expansion/restriction of a quantifier)
(a) Expansion: SW[
Using these two operations, we iteratively generalize the patterns. At every step we select the best pattern and we stop the generalizing process when the F1-measure stops improving (newF 1). We keep a list of previously generalized patterns. If the current pattern has already been processed, it is not generalized further. This corresponds to line 9 of the algorithm (fig. 4). 4
Sentences annotated by the assessor with true events are considered as the gold standard and are used to measure the performance of event extraction patterns. Once the generated patterns had been applied over the gold standard, we compared the gold event annotations with the event annotations created by the patterns under evaluation. Two event annotations are considered to be the same if they cover the same event indicators and arguments (named entities).
We ran preliminary experiments on the English part of
Reuters (RCV2)2 dataset [
In the first experiment, we created 2 train/test splits. In each split, we constructed rules on the train set and validated them on the test one. Table 2 provides split details as well as the number of patterns that have been constructed automatically in each case. Tables 3-5 give an overview of the results of experiments. For M&A event, automatically constructed patterns outperformed 2Initially, we wanted to use RCV1 that is much bigger. However, due to performance characteristics of the first implementations of the algorithm in terms of execution time, we decided to user smaller corpus and experiment on RCV1 after we optimize the algorithm. manually created ones in terms of precision, recall and F1-measure on both the train and test sets in all splits (table 3), thought the number of automatically constructed patterns (8) is smaller than the number of manually created ones (10). Note that in the first split on the test data and in the second split on the train data manually constructed patterns did not extract any events, that is why we do not provide the performance for these cases.
In case of MPC events, in the first split we got higher results using automatically constructed patterns (see table 4). In the second split, manually and automatically constructed patterns demonstrated the same results, however, our algorithm constructed 8 patterns as opposed to 3 patterns constructed by a human.
Automatically constructed patterns for Res events also outperformed those manually created in terms of F1measure in the first and second splits. However, the precision of manually constructed patterns was higher in both splits.
In the second experiment, we tried to get more realistic comparison results of manually and automatically constructed patterns. What we did was validation of manually constructed patterns on the entire dataset (table 7) and ran the algorithm through a 5-fold cross validation 5 times (due to the fact that we used a relatively small dataset). The results are presented in table 6.
Afterwards, we tested manually constructed patterns on the entire dataset. The results are given in table 7. As it can be seen, we got quite varying results for different partitions (F1-measure: 0.4523-0.8333 for M&A, 0.5428-0.7023 for MPC and 0.5000- 0.6764 for Res events). A conclusion that can be made from these results is that we need a larger and more representative dataset to construct and evaluate comprehensive event extraction patterns.
In this paper we gave an overview of the current progress in developing the algorithm for semi-automatic generation of linear event extraction patterns for free texts and presented our preliminary experimental results. Our next steps are to enhance the algorithm with additional capabilities, optimize it in terms of execution performance and validate it on a larger dataset.
Currently, we extract only mandatory events’ arguments. We will add capability to generalize patterns that will include optional arguments as well (such as temporal and monetary expressions). We plan to explore the possibility to improve and optimize the algorithm. We will work on enhancing the generalization algorithm by providing additional operations as well as an intelligent selection of operations to apply at each iteration. We will also explore the possibility to employ negative examples. We have a dataset of approximately 110 000 news articles that we will use for validating the algorithm. We will also use Reuters RCV1 dataset for this purpose. We will study in much more details theoretical properties of the proposed algorithm. [5] Oren Etzioni, Michele Banko, Stephen Soderland, and Daniel S. Weld. Open information extraction from the web. Commun. ACM, 51(12):68–74, December 2008. [9] Ryan McDonald. Extracting relations from unstructured text. Technical report, 2005. [10] Stephen Soderland. Learning information extraction rules for semi-structured and free text. Mach.
Learn., 34(1-3):233–272, February 1999. [12] Alexander Yates, Michele Banko, Matthew Broadhead, Michael J. Cafarella, Oren Etzioni, and Stephen Soderland. Textrunner: Open information extraction on the web. In HLT-NAACL (Demonstrations)’07, pages 25–26, 2007.