Named Entity Recognition

One challenge of building an entity-aware system is the task of Named Entity Recognition (NER). NER has been well studied, and there are a number of open source implementations using a variety of approaches. There are broadly three categories of NER: probabilistic, gazetteer, and rule-based.

Probabilistic approaches rely on machine learning techniques to identify features in text which signal the existence of an entity. This often goes hand in hand with Part of Speech (POS) tagging, which is also a well studied problem. Using a probabilistic approach to NER requires a model is trained on an annotated training set, which can be tedious to produce.

Gazetteer approaches rely on a dictionary of known entities and some form of string matching to identify where any of these entities exist in text. Exact string matching tends to produce low recall in most scenarios, so there exist a number of approximate string matching techniques in the literature for gazetteer NER. Though gazetteer NER can be quite powerful, a complete and accurate dictionary of known entities can be difficult to produce.

Rule-based approaches are quite similar to probabilistic approaches in that they rely on contextual features to identify entities. The difference is that these features are not learned, they are specified by the user. Though this can work very well in some cases, it generally requires deep domain knowledge and can be prohibitively tedious.

There are hybrid systems in existence. Stanford’s Conditional Random Field NER classifier has the option of including a gazette during training of the probabilistic model. This gazette is used as additional features for training the model, and does not guarantee that an exact string match in the gazette will result in the associated entity tag. This is a very interesting concept, as it may help to mitigate the need for a complete gazette, though its required labeled training data may present an issue for a large number of entity types.

Generally, not one NER approach is sufficient for all cases. Domain and application specific NER configuration is a must for enabling entity search, and has thus been one focus of this research.

Index Design

Another challenge of building an entity aware system is the design of the index itself. There can be a number of ways to represent entities within the index, and each has benefits and drawbacks.

One approach would be to treat entity instances as documents. This is intuitive because entities are search targets. However, this requires a good deal of preprocessing since one entity instance can appear in a large number of documents. It may further complicate things when the index is updated with new documents, as all of the entity instances in the new document require changes be made to their corresponding entity documents. Additionally, there can be many ways to store the context of each entity instance in an entity document so that the entity can be searched; it is not unreasonable that these entity documents can become very large.

Another approach would be to simply tag entities within each document. This would allow for a lighter preprocessing phase, though more work is required at query time to convert document results into entity results.

Another approach would be to create a document for every appearance of an entity instance. While this trivializes the problem of updating the index with new documents, it requires aggregation be done at query time, which may be slow. Additionally, this can lead to a very large number of entity occurrence documents in the index.

A final approach is to leverage the information stored in the index for each term to document matching. If a term maps to a document, typically additional information such as frequency of that term in the document is recorded. Entity instances near a term in that document could be stored along with this information. This lessens the preprocessing requirements, but makes search quite unnatural to implement. It is also counterintuitive.

The goal for this summer was set to create a demo system which can build and search an entity aware inverted index, and is adaptable to a variety of corpuses and applications. As one of three undergraduates on the team, my specific focus was on enabling NER and the indexing process.

Named Entity Recognition System Design

To preserve Lucene’s indexing procedure, it was first decided that NER would be performed during analyzation. Later, however, this presented problems. To build an index, Lucene requires the use of an “IndexWriter.” Each IndexWriter has its own analyzation process for the documents passed to it. This means that to write the same document to two indexes, that document must pass through the analyzation process of each IndexWriter. As NER is generally expensive, this work duplication is not ideal. Additionally, this makes any aggregation between documents impossible since the analyzation process is strictly sequential. For these reasons, a NER preprocessing module was created outside of Lucene’s indexing process. The analyzation phase is now simply to parse the formatted output of the NER preprocessing into terms and entities.

Because the system should be flexible to multiple applications and domains, it is essential that multiple types of NER are supported. To this end, the NER annotation module can be configured to use any number of techniques in a defined order.

Each technique, regardless of implementation details, must generate a list of “EntityAnnotations.” These annotations simply represent a token, which may or may not be an entity. For each document, the EntityAnnotations from each NER technique are stored in an ordered list of trees. The idea is that the root EntityAnnotations represent the longest tokens, and all children of an EntityAnnotation represent tokens which are a sub-string of their parents. These root EntityAnnotations are ordered by appearance in the input text. Each NER technique has access to all of these annotations generated before it incase it could make use of them in its own technique.

The reason for this structure is to allow for different NER techniques to return conflicting annotations. At the completion of all NER techniques, a special set of rules can be defined to reconcile these annotations. The EntityAnnotation trees do not need to be flattened, however. It is possible to store multiple tokens at the same position in Lucene, so these differing annotations can live together if that is desired.

A final consideration of the NER system is the structure of the entity types. It is intuitive that entities can form a hierarchy - e.g. an “Actor” is an “Artist” is a “Person”. It is also intuitive that entities can be of multiple types - an “Actor” may also be a “MovieDirector”. With these insights in mind, the system allows users to specify an entity hierarchy, and for entities to take on multiple types. During indexing, a token with multiple entity types will be recorded once for each type, and once for any super types of its defined types. In this way, an entity such as “Tommy Wiseau” may be found by searching any of “Person”, “Actor”, “Artist”, “MovieDirector”, “ScreenWriter”, “Writer”, and “Agent”.

Index Design

Once NER has been completed, the approach for storing entities in the inverted index did not utilize any aggregation. Instead, documents in the corpus represented as Lucene documents remained the principle component indexed. For the keys of the index, entities tagged in the documents were replaced by their entity type.

For example, the document:

Kathryn Aulabaugh goes to school at UIUC.

With tags (not actually formatted like this):

(“Kathryn Aulabaugh”, PERSON) (“goes”, O) (“to”, O) (“school”, O) (“at”, O) (“UIUC”, PLACE).

Would generate the following terms: “entity_person”, “goes”, “to”, “school”, “at”, “entity_place”. All of these terms would map to the document in the inverted index.

However, the information about which person and which place these are is not lost. Lucene has the concept of a “payload,” which is additional information stored about a term. A Lucene postings file is of the format:

term absurd
doc 18
freq 1
pos 45
startOffset 254
endOffset 260
doc 70
freq 1
pos 8
startOffset 43
endOffset 49

A payload would be stored along with the frequency, position, and offset information. We leveraged this to store instance information of an entity. For example:

term entity_person!
doc 0
freq 1
pos 0
startOffset 0
endOffset 14
payload "Kathryn Aulabaugh"

This allows a search of the index to determine in which documents entities of a particular type are located, and what the value for each is.

For storing entities as the values of the index, we again leveraged Lucene’s payload concept. For a particular term’s appearance in a document, we can determine what entities are in that term’s context. Context here means a token window of variable size. Going back to our original document, the term “goes” could have the person entity “Kathryn Aulabaugh” in its context, as well as the place entity “UIUC”. To map “goes” to “Kathryn Aulabaugh,” we structure the postings as follows:

term goes
doc 0
freq 1
pos 1
startOffset 15
endOffset 19
payload [PERSON “Kathryn Aulabaugh” at pos 0], [PLACE “UIUC” at pos 5]

This allows entities to essentially be the values of the index. This does come with a number of serious limitations, discussed in the “Reflection” section.

Named Entity Recognition Technique Evaluation

In addition to constructing a system to handle various NER techniques, several NER techniques were surveyed and integrated into the demo. These techniques were then evaluated to determine if using them for a web-scale corpus was feasible. Those evaluated included JFlex pattern matching, Stanford’s Conditional Random Field Classifiers, DBPedia Spotlight, Stanford’s TokensRegex, and an in-house gazetteer approach. Results are discussed below.

Stanford Conditional Random Field NER Classifiers

Stanford provides some pre-trained Conditional Random Field (CRF) classifiers for NER tasks. There is a three class classifier, which tags people, locations, and organizations - and there is a seven class classifier, which tags people, locations, organizations, money, percents, dates, and times. It is also possible to train your own CRF classifiers with custom entity types, though a annotated training data is required.

The evaluation of Stanford’s CRF classifiers is below. The runtimes represent the time to perform NER annotation and add the documents to the index. To keep the evaluation consistent with others, no non-entity tokens are recorded into the index.

Extrapolating from the linear best-fit lines, using the three class classifier to index one billion documents would take 31 days, and using the seven class classifier would take 32 days.

In addition to supplying an entity type hierarchy and a large number of named entities, DBPedia offers a NER web service called DBPedia Spotlight. They host this web service, but it can also be run on a local machine to reduce latency. Unfortunately my machine could did not have the required specs to run the web service locally, so it was evaluated with DBPedia’s hosting. Results are below.

To index one billion documents, this process would take 669 days, which is too long for our purposes.

JFlex pattern matching was also employed to identify entities which follow a well defined pattern such as emails and phone numbers. Few entities follow patterns such as this, but evaluating runtime using JFlex for just emails and phone numbers shows that it is effective while not contributing to the overall runtime in an appreciable way. It is not capable of handling a large number of patterns, however.

Gazetteer methods are also important for many applications, and were evaluated. Stanford's TokensRegex enables exact string matching through regular expressions. With ~1.1 million Named Entities from DBPedia, this was evaluated below.

To index one billion documents would take 7.1 years, so it does not seem TokensRegex was designed for such a large number of patterns.

We also created a simple exact string matching NER technique by building a prefix tree from the DBPedia Named Entities. However, upon inspection of the tagging it was clear that there existed a high recall with low precision problem. This was especially an issue for very short Named Entities, and those which were common english words. In an attempt to correct this issue, Part of Speech (POS) tagging was employed to restrict entities to noun phrases. Results of measuring the number of tagged entities in 10000 documents while varying the gazetteer size are shown below.

It seems that limiting the entities to noun phrases does improve precision. However, there is a significant runtime cost of using POS tagging, as shown below (Entity Instances refers to the number of Named Entities in the gazetteer).

Interestingly, runtime for using POS tagging remains relatively constant when increasing the number of Entity Instances. A hypothesis for why this may be is because storing a large number of EntityAnnotations (as with not using POS tagging) may be a major factor in increasing runtime. To index one billion documents with a POS-enabled prefix tree gazetteer with 1.1 million Named Entities would take 521 days.

Interestingly, Stanford allows the inclusion of a gazetteer when training a custom CRF classifier. This gazetteer is used as an additional feature for the classifier, and it is not guaranteed that an exact string match with a gazetteer entry will produce the associated tag if other features have “higher weights” (see https://nlp.stanford.edu/software/crffaqshtml#gazette. ). Unfortunately, in order to include a gazetteer for an entity type, that entity type must be labelled in the training data. This is limiting, since labelled training data is expensive to produce. Still, using Named Entities of type PERSON from DBPedia and a small provided labeled training file, three new CRF classifiers were produced and evaluated. They had ~6k, ~250k, and ~550k gazetteer entries each. Results are below.

To index one billion documents with the 6k entries gazetteer would take 14 days, with the 250k entries gazetteer would take 128 days, and with the 550k entries gazetteer would take 313 days. It is worth noting that all of these classifiers tag very few entities. This may be due to the small training data, or due to not many names appearing in the dataset.

They also all tag roughly the same number of entities.

One of the first questions tested was the space usage of the index. In our demo we create two index types, Entity-Inverted (E-Inverted) and Document-Inverted (D-Inverted). The EInverted index uses both entities and terms as keys to the index, and both documents and entities as values. The method for this is described in the previous section. The D-Inverted index uses both entities and terms as keys to the index, but only documents as values. The justification for these types of indexes can be found in Cheng, T., Chang, K.: Beyond Pages: Supporting Efficient, Scalable Entity Search with Dual-Inversion Index (2010). Space usage for these indexes is shown below.

The exact figures for this chart should be considered with skepticism since the space usage is not fully optimized, and this evaluation was done before the demo system was complete. The main takeaway should be that the E-Inverted index uses much more space than D-Inverted. That said, to index one billion documents our E-Inverted index would require 7.2 TB, and our D-Inverted index would require 2.7 TB.