2.1 Problem statement

The problem of NER can be formulated as follows. Let $\mathcal {E}$ be the set of all entities of a particular type (e.g. person names, countries, dates), and let $\mathsf {P}$ be a pattern capable of recognizing all these entities. That is, $\mathcal {E}=L(\mathsf {P})$ where $L(\mathsf {P})$ is the language recognized by $\mathsf {P}$ , and thus the pattern recognizes the language of the particular entity type we are looking for and nothing else. The goal is to generate a pattern $\hat{\mathsf {P}}$ that estimates $\mathsf {P}$ from a set $\mathcal {E}^+\subseteq \mathcal {E}$ of positive examples (i.e. known entities) and possibly a set $\mathcal {E}^-\nsubseteq \mathcal {E}$ of negative examples (i.e. text fragments that are not entities of the target type).

These patterns are based on different combinations of features that characterize entities in $\mathcal {E}$ and differentiate them from the rest of the text. These features have different degrees of granularity. They are often found at the character level (e.g. character classes) and at the token level (e.g. POS tag, morphological category), though we can also find discourse features. Let Σ be the alphabet of all characters. A character feature $f^\mathcal {C}$ is a function $f^\mathcal {C}:\Sigma \rightarrow \Sigma ^\mathcal {C}$ that maps a character onto a symbol of a certain alphabet $\Sigma ^\mathcal {C}$ specific of the feature. A token feature $f^\mathcal {T}$ is a function $f^\mathcal {T}:\Sigma ^*\rightarrow \Sigma ^\mathcal {T}$ that maps a sequence of characters (i.e. a token) onto a symbol in the feature output alphabet. Different NER systems can of course use different sets of features.

For our purposes, a pattern learning method for NER is thus defined as a function that estimates $\mathsf {P}$ from the sets $\mathcal {E}^+$ and $\mathcal {E}^-$ of positive and negative examples, sets $\mathcal {F}^\mathcal {C}$ and $\mathcal {F}^\mathcal {T}$ of character and token features, and a corpus $\mathcal {D}$ of documents. In this paper, we propose a semi-automatic method to learn $\hat{\mathsf {P}}$ , such that $L(\hat{\mathsf {P}})\approx L(\mathsf {P})$ . The accuracy of the pattern is measured in terms of precision and recall, that is, its ability to generate the same language as $\mathsf {P}$ .

2.2 Pattern learning methods

Different machine learning approaches can be found in the literature for the automatic creation of NER patterns. According to Sarawagi (Reference Sarawagi2008), these can be broadly categorized as rule based and statistical. While the former may produce a customized model designed to exploit specific characteristics of the task, the latter try to map the NER problem to some generic theoretical model that has to be fitted. Rule-based methods are easier to develop and interpret, while statistical methods are more robust to noisy unstructured text. Nonetheless, both rule-based and statistical learning methods are still used depending on the specificities of the extraction task (Sarawagi, Reference Sarawagi2008). Chiticariu and Reiss (Reference Chiticariu and Reiss2013) show that rule-based methods are more frequent in industrial settings, while statistical methods are used more often in academia, probably because the former are easier to adopt, understand, debug and maintain in scenarios where requirements are changing.

We find several rule-based approaches in the literature. Whisk (Soderland, Reference Soderland1999) and Amilcare (Ciravegna and Wilks, Reference Ciravegna, Wilks, Handschuh and Staab2003) calculate combinations of feature values and select the ones that best identify entities. RAPIER (Thompson, Califf and Money Reference Thompson, Califf and Mooney1999) computes possible alignments between feature values and selects the ones with the best trade-off between accuracy and complexity of the pattern. Wu and Pottenger (Reference Wu and Pottenger2005) learn patterns by identifying sequences of features and iteratively expanding patterns from the most common feature value across entities. Li et al. (Reference Li, Krishnamurthy, Raghavan, Vaithyanathan and Jagadish2008) adapt regular expressions from annotated examples. Brauer, Rieger, Moca and Barczynski’s method (Reference Brauer, Rieger, Mocan and Barczynski2011) analyzes the prefixes and suffixes of the entities in order to determine character patterns. Finally, Nagesh and Chiticariu (Reference Nagesh and Chiticariu2012) induce rules by applying a subset of operators from the declarative language AQL with basic features previously identified in the text.

Regarding statistical learning approaches, we find the use of Markov Models (Bikel et al. Reference Bikel, Miller, Schwartz and Weischedel1997; Hachey, Alex and Becker Reference Hachey, Alex and Becker2005), Maximum Entropy Models (Borthwick et al. Reference Borthwick, Sterling, Agichtein and Grishman1998), Conditional Random Fields (McCallum and Li Reference Culotta and Mccallum2003; Finkel, Grenager and Manning Reference Finkel, Grenager and Manning2005; Tomanek, Wermter and Hahn Reference Tomanek, Wermter and Hahn2007), Support Vector Machines (Asahara and Matsumoto Reference Asahara and Matsumoto2003; Shen et al. Reference Shen, Zhang, Su, Zhou and Tan2004; Vlachos Reference Vlachos2008; Li, Bontcheva and Cunningham Reference Li, Bontcheva and Cunningham2009), Neural Networks (Kazama and Torisawa, Reference Kazama and Torisawa2007; Ratinov and Roth, Reference Ratinov and Roth2009) and Decision Trees (Sekine, Grishman and Shinnou Reference Sekine, Grishman and Shinnou1998).

Some other works have studied the application of bootstrapping techniques for NER (Etzioni et al. Reference Etzioni2005; Jones Reference Jones2005; Pasca et al. Reference Pasca, Lin, Bigham, Lifchits and Jain2006; Nadeau Reference Nadeau2007; Gupta and Manning Reference Gupta and Manning2014;), as well as other unsupervised techniques (Alfonseca and Manandhar Reference Appelt and Onyshkevych2002; Shinyama and Sekine Reference Shinyama and Sekine2004; Ritter et al. Reference Ritter, Clark and Etzioni2011). Finally, some recent works have studied hybrid approaches (Irmak and Kraft Reference Irmak and Kraft2010; Nouvel et al. Reference Nouvel, Antoine, Friburger and Soulet2012; Fersini et al. Reference Fersini, Messina, Felici and Roth2014; Liu et al. Reference Liu, Wei, Zhang and Zhou2013).

2.3 Annotations

The initial sets $\mathcal {E}^+$ and $\mathcal {E}^-$ are usually part of the corpus, where these entities are already annotated. Statistical learning algorithms require a large number of such annotations (Settles, Reference Settles2012), which often requires the user to review very large amounts of text. As a result, these algorithms are seldom practical when there are none or just a few annotations available. Unfortunately, this is usually the case in NER when facing non-traditional types of entities (e.g. apparel brands, software applications, years of experience) or simply a brand new corpus for which known patterns are not suitable (Marrero et al. Reference Marrero, Sánchez-Cuadrado, Morato and Andreadakis2009; Marrero et al. Reference Marrero, Urbano, Sánchez-Cuadrado, Morato and Gómez-Berbís2013). In addition, these algorithms may generate patterns biased toward precision because $\mathcal {E}^+$ is normally outnumbered by $\mathcal {E}^-$ , that is, there are many more negative examples than positive examples (Li et al., Reference Li, Bontcheva and Cunningham2009).

Active learning techniques can reduce annotation costs, asking users to annotate only certain documents or text snippets throughout the learning process. The sets $\mathcal {E}^+$ and $\mathcal {E}^-$ are initially smaller, and they are augmented with the new annotations made during the learning process. Overall annotation costs are reduced by identifying the most informative or relevant text snippets to annotate. Active learning has been previously applied to both rule-based (Soderland, Reference Soderland1999; Thompson et al., Reference Thompson, Califf and Mooney1999; Wu and Pottenger, Reference Wu and Pottenger2005) and statistical learning methods (Shen et al., Reference Shen, Zhang, Su, Zhou and Tan2004; Hachey et al., Reference Hachey, Alex and Becker2005; Tomanek et al., Reference Tomanek, Wermter and Hahn2007; Vlachos, Reference Vlachos2008; Li et al., Reference Li, Bontcheva and Cunningham2009). However, even with active learning it is still necessary in many cases to have many initial annotations to obtain satisfactory results.

Some studies discuss different approaches to measure the effort required from the user (Settles, Reference Settles2012). For instance, Vijayanarasimhan and Grauman (Reference Vijayanarasimhan and Grauman2009) estimates annotation cost from the time it takes the user to annotate a few examples. Nevertheless, the most common measures of required user effort are the number of elements to review (e.g. number of tokens), and the number of actions required (e.g. change a label). A very important aspect in the first case is the length of the text units that users are given to annotate. In the case of NER, RAPIER (Thompson et al., Reference Thompson, Califf and Mooney1999) uses full documents, Whisk (Soderland, Reference Soderland1999) and Wu and Pottenger (Reference Wu and Pottenger2005) use predefined text snippets (assuming previous knowledge about the type of documents and the boundaries of the entities), Hachey et al. (Reference Hachey, Alex and Becker2005) and Tomanek et al. (Reference Tomanek, Wermter and Hahn2007) use sentences, Shen et al. (Reference Shen, Zhang, Su, Zhou and Tan2004) use the entities themselves, and Vlachos (Reference Vlachos2008) and Jones (Reference Jones2005) use tokens. Li et al. (Reference Li, Bontcheva and Cunningham2009) compare the use of documents, text fragments and tokens with active learning. They observed that when the annotation units are text fragments or tokens instead of full documents, the performance of algorithms is significantly lower. But large documents do not necessarily contain more entities, so using full documents makes both overall annotation costs and algorithm performance more variable across document types.

Regarding the measurement of effort as the number of actions taken by the user, Culotta and Mccallum (Reference Culotta and Mccallum2005) consider the actions of correcting the start boundary, end boundary, and type of an entity, as well as choosing from a list of suggestions with various boundaries. Others try to combine the number of elements to review and the number of actions. For instance, Ringger et al. (Reference Ringger2008) and Haertel et al. (Reference Haertel, Seppi, Ringger and Carroll2008) apply an hourly cost model to the labeling of POS that depends on the number of tokens per sentence reviewed by the user, and the number of words whose label needs correcting.

2.4 Features

Entities may be recognized with regular expressions when their patterns respond to sequences of characters, such as in e-mail addresses, phone numbers and names of some genes and proteins. However, not even the typical NER entities (e.g. location, organization, person) can be recognized with only these features; custom token features are needed as well to describe more complex patterns. It is therefore important that a pattern learning method permits generality (i.e. to employ a diverse set of features to be able to recognize various entity types, even in different types of document) as well as retargetability (i.e. to include custom features, even at different granularity levels, to recognize specific or novel types of entities) (Freitag, Reference Freitag1998; Marrero et al., Reference Marrero, Urbano, Sánchez-Cuadrado, Morato and Gómez-Berbís2013). These capabilities have a direct impact on the learning method, which needs to deal with an arbitrarily large number of features and alphabet symbols. This is especially troublesome with features at the character level, because they are applied to each of the individual characters of the entities and lead to a high degree of variability. This is often the case with statistical learning methods, which very rarely work with character-level features and, when they do, they usually employ n-grams instead of single characters.

2.5 Representation of patterns

An important difference between rule-based and statistical learning approaches is the transparency of the generated patterns. Statistical learning patterns are used as a black box, because they are based on statistical models that are hard to interpret by humans. On the other hand, rule-based patterns can be more easily interpreted and analyzed, even during the learning process (Siniakov, Reference Siniakov2008). This further allows users to edit and refine patterns, possibly aided by computer tools (Chiticariu et al. Reference Chiticariu, Krishnamurthy, Li, Reiss and Vaithyanathan2010). The need to represent features at different levels of granularity gave rise to a number of different ways and syntaxes to specify rule-based patterns in NER, from formal patterns such as regular expressions to ad-hoc patterns that represent predefined features. Unfortunately, neither regular expressions nor higher level grammars allow more than one input alphabet at once. On the other hand, languages for ad-hoc patterns, except maybe for recent developments like the UIMA language, lack standardization (Marrero and Urbano, Reference Marrero, Urbano, Hanbury, Kazai, Rauber and Fuhr2015).

Cascade grammars do allow us to use several types of features in the same pattern. The Common Pattern Specification Language (CPSL) (Appelt and Onyshkevych, Reference Appelt and Onyshkevych1998) standardizes this representation, and it is widely used in Information Extraction tasks. It has been adopted and customized to different extents by different platforms (Boguraev Reference Boguraev2004; Drozdzynski et al. Reference Drozdzynski, Krieger, Piskorski, Schäfer and Xu2004; Rinaldi et al. Reference Rinaldi2005), GATE (Cunningham et al., Reference Cunningham2013) being one of the most successful ones with its JAPE notation, which provides finite state transduction over GATE’s document annotations. Each transducer consists of a set of pattern-action rules, the actions being new annotations over the matched text (see Figure 1). The rule-based methods described in Section 2.2 are in principle capable of generating some valid rules for this standard, but they usually employ only character features to generate regular expressions (Li et al., Reference Li, Krishnamurthy, Raghavan, Vaithyanathan and Jagadish2008; Brauer et al., Reference Brauer, Rieger, Mocan and Barczynski2011), or only token features, predefined (Soderland, Reference Soderland1999; Thompson et al., Reference Thompson, Califf and Mooney1999) or not (Ciravegna and Wilks, Reference Ciravegna, Wilks, Handschuh and Staab2003; Nagesh and Chiticariu, Reference Nagesh and Chiticariu2012). There are some approaches like (Wu and Pottenger, Reference Wu and Pottenger2005) that use both types of features, but they can-not be customized. The method we present in this paper is capable of generating cascade grammars with features that are more customizable than in other rule-based methods for NER, making it more general and retargetable.

Fig. 1.

Sample cascade grammar in JAPE notation. Each phase represents a finite state transducer, whose input alphabet is specified after Input. Each rule contains a left-hand side with a pattern, the separator –>, and a right-hand side with an action. The text matched by the pattern can be identified with a label (e.g. :pname), which is used in the action to add certain annotations to that specific string. In the above example, the first phase recognizes person first names, made up of a token with morphosyntactic category NNP, whose initial character is A (==^~ indicates that the right-hand side is a regular expression), and is also included in the person_first gazetteer. The text matched by this pattern is annotated as Person.type=”first”. The second phase uses these annotations to recognize first names that are preceded by a token matching the regular expression Dr\\.?, and annotates them as Person.title=”doctor”.

3.1 Sequential patterns

The most common criterion to recognize textual entities is the occurrence of the same symbol in all entities. For instance, the two entities in Figure 2(a) contain digits and a time expression (am or pm). The declarative languages UIMA, AQL or JAPE include operators to specify this type of conditions in the elements to analyze (e.g. CONTAINS), but patterns for NER are usually much more complex. They can be combined with other conditions to create sequential patterns, which are far more common in Natural Language Processing. These patterns consist of sequences of symbols that repeat in all the items of interest (Srikant and Agrawal, Reference Srikant and Agrawal1996). These symbols may appear next to each other or with a number of symbols in between, which may be fixed or vary across items. In our example, if we represent the hour and time expressions as symbols, then they respond to a sequential pattern where those symbols are at a distance of 1 from each other. Note that patterns that rely only on one symbol could also be dealt with as sequences of two symbols, where one of them is the starting or the end symbol.

Markov Models and CRF implicitly model these dependencies among symbols in a sequence. Other statistical models such as SVM or Decision Trees rely on the features to add sequence information to the model (e.g. n-grams, left/right context features). Declarative languages include sequence conditions such as AFTER or BEFORE. Implicitly, systems based on regular expressions and transducers also search for sequences of symbols with the use of automata.

Examples of rule-based systems that learn sequential patterns are Whisk and Amilcare, which enumerate possible sequences of symbols and select the best ones based on several statistics. However, these techniques may not be scalable in large search spaces, so domain information is usually employed to maintain the problem tractable. For instance, the search space could be pruned, as Amilcare does, or constrained with certain conditions as part of a known, customized model. For example, RAPIER looks for features that appear in the exact same position in all the entities. In that case, when two entities have the same value for a specific feature (string, POS and semantic) and at the same position, that value gets fixed. Otherwise, all the values appearing in the known entities at that position are accepted by the pattern. Using a customized model rather than a general classification model is specially relevant when, in addition to the scalability problem, we do not have enough data to statistically validate the patterns. In the latter case, the user could provide some kind of feedback by means of active learning techniques, as we will see in Section 4.2.2, but the learning method should keep the interaction at a minimum, finding the most relevant patterns to ask based on the model we know.

3.2 Rule vectors

Our pattern search space is composed of what we will call rule vectors. A rule vector is associated with a particular symbol from some feature, and it contains the positions of that symbol in all the known entities. In particular, if $\vec{z}$ is a rule vector related to a symbol α, each component $z_i\in \vec{z}$ is the position of α in the ith known entity. At this point, let us assume that the symbol α is present just once in all entities; this restriction is relaxed in Section 4.2.1.

Example: With the entities in Figure 2, a possible rule vector would be (4, 2) for symbol 0, meaning that the fourth character of the first entity and the second character of the second entity are both 0. That vector suggests fixing those specific symbols in those specific positions as rules of the final pattern. □

We identify sequential patterns by comparing pairs of rule vectors, trying to determine how well they are aligned with each other. For two arbitrary vectors $\vec{u}$ and $\vec{v}$ that contain positions of two symbols α and β (not necessarily from the same feature), the ideal case would be such that $\vec{u}=\vec{v}+\delta$ , meaning that all entities contain symbols α and β in the same order and at a distance of δ from each other. However, in practice, the distance between sequential symbols is not always the same, so we define the following distance function between two rule vectors:

$$\begin{equation*} \Delta (\vec{u},\vec{v})= \sum _i{\left| (v_{i+1}-u_{i+1})-(v_i-u_i) \right|} \end{equation*}$$

Pairs of vectors with small distances are more likely to get fixed in the final pattern. Symbols that always appear at similar positions from the beginning or from the end of the entity can be identified by introducing two additional vectors. The first one, $\vec{z}_b$ , contains only zeros to detect patterns with respect to the beginning of entities, that is, symbols that appear at a similar distance from the first symbol in each entity. The second vector, $\vec{z}_e$ , contains the length of each entity and allows us to detect patterns with respect to their end, that is, symbols that appear at a similar distance from the last symbol of each entity.

For each feature, we iteratively calculate all rule vectors and compute their distance Δ with each of (i) all other possible rule vectors, (ii) vectors $\vec{z}_b$ and $\vec{z}_e$ , (iii) all vectors already fixed in the final pattern and from the same feature, and (iv) all vectors already fixed in the final pattern but from previous features. In the end, we select the rule vectors whose distance with other vectors was minimal in the whole set, as they are most likely to produce valid rules. We note that for two vector rules to actually define a sequential pattern, the symbols they represent must always appear in the same order in all entities. This means that if in any entity the symbols are swapped, the vectors are not even paired to compute their distance.

In addition, it generally does not make sense to fix a rule vector involving for instance the same character found in the body of some entities and in the context of some others. Because we do not force symbols to appear in the exact same position across entities, we look for rule vectors separately within the entities and within their contexts. The identification of rule vectors within the contexts is made by joining together the left and right context, so we are able to find sequential patterns involving matching symbols from both contexts. This approach would help finding symbols that appear sequentially in the left and right context of an entity, such as < and >, and would also let us identify symbols that could appear indistinctly in the left or right contexts in each entity.

3.3 Feature matrices

As mentioned, a rule vector contains the positions of a certain symbol in all entities. These symbols are computed with different feature functions, which in our case are either at the character level or at the token level. The set $\mathcal {F}^\mathcal {C}$ of character features is fixed to three feature functions similar to Brauer (Reference Brauer, Rieger, Mocan and Barczynski2011). The first feature simply maps a character onto the character itself. The second feature maps characters onto their Unicode category, except for alphabetic characters, which are represented in case-insensitive form. The third one maps characters onto a custom group of Unicode symbols (see Table 1). The method allows the use of an arbitrary set $\mathcal {F}^\mathcal {T}$ of features at the token level.

Table 1.

Custom groups of Unicode categories in the third character feature

All these features are represented in what we will call feature matrices (see Figure 2(b)). The character feature values for an arbitrary entity e _i are represented by a matrix $A^\mathcal {C}_i$ , such that each row corresponds to a feature and each column corresponds to a character of the entity, that is, $a^\mathcal {C}_{ijk}\in A^\mathcal {C}_i$ is the value of the jth feature with the kth character of entity e _i . Similarly, a matrix $A^\mathcal {T}_i$ represents the token feature values of the entity.

Example: In our main example in Figure 2, the fourth column of $A^\mathcal {C}_2$ represents the fourth character of the second entity. Because this character is 5, the character feature values are $a^\mathcal {C}_{2,1,4}=\texttt {5}$ , $a^\mathcal {C}_{2,2,4}=\texttt {Nd}$ and $a^\mathcal {C}_{2,3,4}=\texttt {D}$ . As for tokens, the example uses two features: $f^\mathcal {T}_1$ assigns a semantic tag from a gazetteer, and $f^\mathcal {T}_2$ assigns a font style tag. Similarly, the second token of the second entity is am, which is represented as $a^\mathcal {T}_{2,1,2}=\texttt {<time>}$ and $a^\mathcal {T}_{2,2,2}=\texttt {<italics>}$ in the token feature matrix $A^\mathcal {T}_2$ . From these feature matrices, we may identify rule vectors. For example, with the first feature, we may identify rule vector (5, 6) for the space symbol $\texttt {_{\sqcup}}$ , and with the second feature we could identify vector (7, 8) for symbol [Mm], among others. With the first token feature, we would have vector (2, 2) for symbol <time>.

□

In the initialization step of the learning method, we first compute all character feature matrices of the known entities, and group them together in a set $\mathcal {A}^\mathcal {C}=\lbrace A^\mathcal {C}_1,A^\mathcal {C}_2,\dots \rbrace$ . In order to detect patterns involving the context of the entities as well, we also include in these matrices a fixed number of characters to the left and to the right of the entities; let these be the contexts for learning. In particular, we use a window of size θ _wc characters on each side, so the k indexes have an offset of θ _wc . The set $\mathcal {A}^\mathcal {T}$ with all token feature matrices is created similarly, but with an offset window of θ _wt tokens. In Figure 2, we have set θ _wc = θ _wt = 0 for simplicity and therefore do not use any context in that example.

3.4 Pattern matrices

Similarly to the feature matrices, we also use two pattern matrices for each known entity, in order to save the rule vectors that have been fixed during the process as part of the patterns. For each known entity e _i , matrix $B^\mathcal {C}_i$ will contain the symbols that have been fixed from the character features, and matrix $B^\mathcal {T}_i$ will contain the symbols fixed from the token features. Each component of these matrices corresponds to a rule vector learned for a particular feature and character (or token) of the entity. For instance, $b^\mathcal {C}_{ijk}=\alpha \in \Sigma ^\mathcal {C}_j$ means that a rule was fixed for the kth character of the ith entity, forcing it to be α with the jth character feature function. If no rule is found for some particular character (or token) and feature, the corresponding component is set to the wildcard •.

Example: Figure 2(c) shows the character pattern matrices $B^\mathcal {C}_1$ and $B^\mathcal {C}_2$ in our main example. Row 1 indicates that the fifth character must be a space ␣ in positions 5 for e ₁ and 6 for e ₂, as a result of fixing rule vector (5, 6) in the previous example. The second row contains the values fixed by the rules found with the second feature, such as (7, 8). In particular, they indicate that we have a sequence of one or two digits (Nd), followed by a punctuation mark (Po), two more digits and the character M in upper or lowercase at the end. Regarding the token features, we have that in both cases the second token of the entity must evaluate to <time> and <italics> with features one and two, respectively. The pattern also indicates that there is no specific rule for the first token with the first feature. □

After creating sets $\mathcal {A}^\mathcal {C}$ and $\mathcal {A}^\mathcal {T}$ with the feature matrices, the method also creates the set $\mathcal {B}^\mathcal {C}$ containing all character patterns, and then the set $\mathcal {B}^\mathcal {T}$ containing all token patterns. At that point, the patterns just contain • everywhere, meaning that no specific rule has been found yet. Learning of patterns can thus be seen here as the specialization of a wildcard matrix by means of rules that fix specific symbols from the feature matrices. In the end, these pattern matrices will be converted to regular expressions or JAPE rules as detailed in Section 4.3.

5.1 Corpus, features and performance measures

To evaluate our method with a varied range of entity types, we used the Software Jobs Corpus Footnote ¹ (Califf, Reference Califf1998). It contains 300 documents in English, of about 313 tokens each, describing software-related job postings. There are seventeen different types of entities already annotated: ID, title, salary, company, recruiter, state, city, country, language, platform, application, area, required years of experience, desired years of experience, required degree, desired degree and post date. For the third experiment, we annotated ourselves all the entities of type phone number. Table 2 shows the number of instances per entity in this corpus.

Table 2.

Number of entities in the 300 documents of the jobs postings corpus

The Jobs corpus is widely used in Information Extraction (Lavelli et al., Reference Lavelli, Califf, Ciravegna, Freitag, Giuliano, Kushmerick and Romano2004), because it contains a well defined and more varied selection of entity types than other corpora. In addition, some of these entities are recognizable with regular expressions, and many of them can be recognized fairly well without gazetteers. This is particularly relevant when evaluating a novel learning method, because the success of information extraction methods can be notably increased by using domain-specific knowledge resources such as gazetteers, dictionaries and taxonomies. Therefore, we explicitly do not use such resources in our experiments in order to center the evaluation on the performance of the proposed learning method and not on the performance of a specific set of knowledge resources, whose existence can-not be presupposed and whose growth is seldom traceable (Siniakov, Reference Siniakov2008). Instead, we use a basic set of token features obtained with the ANNIE tool in the GATE framework, namely string, stem, POS tag, token type (<word>, <number> or <punctuation>) and case. Recall that the set of three character features is fixed in our method (see Section 3.3).

In all three experiments, we measure the effectiveness of the learning method with Precision, Recall and the F-measure. Because it learns patterns for each entity type separately, we compute the effectiveness for each of those types and then report the average across types (i.e. macro-average). In terms of cost, we follow the standard approach of reporting the number of elements that the user would have to review, which in our case are text fragments to validate as entities or not. Specifically, we report the number of entities and the number of tokens they contain. We include the initial set of seed entities in the annotation cost, as well as the 2 · θ _wv characters in the validation contexts of each match, rounded up to the next token, in order to help the user validate potential entities and adjust their boundaries if needed.

The goal in the first and third experiments is to generate effective patterns, so the method will be run on a training corpus to learn the patterns and they will then be evaluated on a test corpus. The goal in the second experiment is to fully annotate a new corpus, so the method will be trained and evaluated on the full corpus. Regarding the initial seeds, random selections of various sizes are made for each entity type separately. Note that the annotations in the training set, except for these initial seeds, are not used by the method in any way; they are iteratively discovered by the active learning process.

5.2 Initial configuration and baselines

As seen in Sections 3 and 4, our method depends on several parameters that control various aspects of the learning process, such as context windows, thresholds, etc. Table 3 summarizes the values of the parameters used in the three experiments. For details on the selection of these values, the reader is referred to the Appendix.

Table 3.

Parameters configured for evaluation of the learning method

Given that the objective is to learn JAPE patterns of reasonable effectiveness at a low cost, we compare our learning method with a semi-supervised baseline that maximizes effectiveness while reducing cost, and an unsupervised baseline that minimizes cost. The semi-supervised baseline is a pattern learning method based on Support Vector Machines, adapted to deal with imbalanced training data and combined with active learning techniques (Li et al., Reference Li, Bontcheva and Cunningham2009). In terms of features, they use the same basic set of token features we use. Their method also contains a post-processing step that discards entities of infrequent length, and chooses the sequence of entity types with the highest probability for a sequence of tokens (e.g. one entity type often preceded by another one). We note that our method can-not apply the second correction because it is run separately for each entity type, so patterns are independent of other types that might be irrelevant to the user (and hence need not be annotated) or might not appear at all in the target corpus. To our knowledge, theirs are the best results to date of an active learning method, whether rule-based or statistical, applied to the Jobs corpus and without the use of gazetteers or dictionaries.

The unsupervised baseline is a rule-based bootstrapped method part of the Stanford CoreNLP framework (Gupta and Manning, Reference Gupta and Manning2014). This method builds a dictionary from a set of initial seeds, and then iteratively learns patterns without any user intervention, adding to the dictionary the recognized fragments that ranked best according to a scoring function. In terms of features, they use the lemma and POS tag of the entity and its context, as well as their edit distance and distributional properties in the sets of positive and negative examples. In the end, all text fragments in the corpus that are found in the dictionary are labeled as entities.

In the remainder of the paper, we will refer to our method as RB-AL (for Rule-Based Active Learning) to the semi-supervised method of Li et al. (Reference Li, Bontcheva and Cunningham2009) as SVM-AL (for SVM Active Learning), and to the unsupervised method of Gupta and Manning (Reference Gupta and Manning2014) as BOOT (for Bootstrap).

6.1 Design

We randomly split the full corpus in an unlabeled training set (two thirds) and a test set (one third) that remains unseen by the algorithm; results are reported over five such splits. In terms of initial seeds, we run the method with random sets of 2, 5, 10, 20, 50 and 100 entities from the training set and for each of the seventeen entity types separately. Finally, we run ten random trials in each case, leading to a total of 5,100 trials. Note that the annotations in the training set, except for the seeds, are not used by the method in any way; they are iteratively discovered by the active learning process.

For the assessment of effectiveness, we force the patterns to recognize the exact boundaries of the entities in order to be considered correct; if there is any discrepancy whatsoever the identification of the entity is considered incorrect regardless of how close it is to the true boundaries of the entity. For the assessment of cost, we report the total number of text fragments validated by the user during active learning and the number of tokens they contained, including their validation context. Recall that the seeds are included in these costs.

In the case of the SVM-AL baseline, we compare with the results reported by Li et al. (Reference Li, Bontcheva and Cunningham2009), though we must note two differences. First, they always use two fully annotated documents as seeds, so that all unannotated tokens are used as negative examples. Second, they train with the full corpus, using to test whatever (variable) portion is left without user validation. For the BOOT baseline, we ran their code with the same corpus splits and random sets of seeds as our method, for a total of 5,100 trials as well. Note that, because it is unsupervised, its annotation cost is due only to the seeds.

7.1 Design

This experiment is run in two phases. First, the method is given the initial seeds to learn patterns, which are then run over the whole corpus. Second, the user would have to review all text fragments matched by the patterns to ensure that they are correct. In this case, we do not need separate training and test sets, because we actually want to annotate all documents in the corpus. As in the previous experiment, we use random sets of 2, 5, 10, 20, 50 and 100 entities for each of the seventeen entity types separately. This is replicated ten times, leading to a total of 1,020 trials. Again, the annotations in the corpus, except for the seeds, are not used by the method in any way.

Our goal this time is a high recall rate over all entities of the corpus. We thus report two annotation costs: the cost required to learn the patterns (learning cost), which includes the seeds, and the cost required to review the fragments captured by those patterns (review cost). Because of this review process, here we will also consider a partial match as correct because it will be reviewed, and possibly corrected, by the user anyway. For completeness, we still report the precision and F-scores obtained by the learning algorithm before the review process. Note that at the end of the review process, the recall is the same, but the practical precision is actually hundred per cent, that is, there will not be false positives.

For the BOOT baseline, we ran the code by Gupta and Manning (Reference Gupta and Manning2014) with the same random sets of seeds as our method. The learning cost of BOOT is still due only to the seeds, but in this experiment, there is also a review cost because the user would similarly check all labeled fragments. In this case, we do not include the SVM-AL baseline because the experiments in Li et al. (Reference Li, Bontcheva and Cunningham2009) do not provide information to compare with.

8.1 Design

The target entity types must be exclusively recognizable with character features, so we only consider the post date of the job offer, and the contact phone and fax numbers. As usual, we run the method separately for each entity type, and the full corpus is again randomly split in two-thirds for training and one-third for testing; results are reported over five such splits. We always use three randomly selected seeds, either all found in the corpus (internal) or none (external). In the latter case, they are randomly chosen from the ones listed in Table 6; note that some of these follow a pattern that does not match any entity in the corpus. Finally, we run ten random trials in each case, leading to a total of 200 trials.

Table 6.

Entities used as external seeds in the third experiment; none of them are found in the corpus. Entities in the last two columns do not correspond to the same pattern as the entities in the corpus (e.g. months in post date entities always contain three letters, the first one in uppercase)

We require the patterns to recognize the exact boundaries of the entities. For the assessment of cost, we report the total number of text fragments and the corresponding number of tokens validated during learning, including the validation contexts and the seeds.

Neither the SVM-AL nor the BOOT baselines can work exclusively with character features, and in particular BOOT does not allow the use of external seeds. Therefore, in this experiment, we do not compare with baselines, but rather limit the analysis to how our method is affected by the use of internal or external seeds for the generation of regular expressions.