Review of state of the art named entity recognition methods for different languages

1. Introduction

Name Entity Recognition (NER) is a significant method for extracting structured information from unstructured text and organise information in a semantically accurate form for further inference and decision making.

NER has been a key pre-processing step for most of the natural language processing applications such as information extraction, machine translation, information retrieval, topic detection, text summarization and automatic question answering tasks.

Due to the diverse language characteristics, NER can be declared as language/ domain specific task. For languages such as English and German, named entity recognition has been easier task when compared to asian languages due to beneficial orthographical features (E.g., nouns begin with a capital letter).

However, for most of the languages named entity recognition has been a challenging task due to lack of annotated corpora, complex morphological characteristics and homography.

Linguistic issues for South Asian languages are agglutinative nature, no capitalization, ambiguity, low POS tagging for accuracy, lack of good morphological analyzers, lack of named dictionaries, multiple ways of representing acronyms, free word order and spelling variation[2][4][9].

In NER tasks frequently detected entities are Person, Location, Organization, Time, Currency , Percentage, Phone number, and ISBN.

2. Different methods for NER

The current approaches for NER task can be categorized in to machine learning, rule based and hybrid methods.

2.1.  Machine learning based methods

Machine learning/ statistical methods require large annotated data. This is less expensive than rule based methods when it comes to maintenance aspects as less expert knowledge is required. Extension of new names is a costly task for machine learning as re-training is required.

Machine learning techniques consider NER task as a sequence tagging problem.

2.1.2. Algorithms for NER

            2.1.2.1. Supervised learning methods

Algorithm	Description
Conditional Random Fields (CRF) [2], [3], [6], [7], [9], [11], [13], [15]	Discriminative, Undirected graphical models, First order markov independence assumption, Conditional probability of labeled sequence More efficient than HMM for non-independent, diverse overlapping features  of highly inflective languages Framework: CRF++ [10]
Hidden Markov Models (HMM) [9]
Maximum Entropy (MaxEnt) [1]
Maximum Entropy Marcov Model (MEMM)
Support Vector Machines (SVM) [5]

            2.1.2.2. Semi-supervised learning methods

2.2. Rule based methods

Rule identification has to be done manually by linguistics and requires language specific knowledge. These methods include lexicalized grammar, gazetteer lists and list of trigger words. [2]

The rules generated for one language cannot be directly transferred to another language. Also, rule based methods do not perform well in ambiguous/ uncertain situations.

There can be positive and negative rules.

In [1], 36 rules are defined for time, measure and number classes. The rules contains corresponding entries for each language to act in language independent manner.  In addition, semi automatics extraction of context patterns is used to refine the accuracy.

[2] , [3] have used rule based method to find nested tags to improve recall.

Regular expressions have been utilized in [4][ 5] to identify person names and organization names. In [7], dictionaries are used to locate, if part of the word presents in the dictionary. 

Rule based NER engine is created using white list representing a dictionary of names and grammar in the form of regular expressions in [14]. Here, heuristic disambiguation technique is applied to get the correct choice when ambiguous situation arises.

2.3. Hybrid methods

It is specified in [1], [2] that hybrid system have been generally more effective in the task of NER with proven results.

In [1], a hybrid solution is suggested for NER which consist of base line NER system with MaxEnt model. To increase the performance, language specific rules and gazetteers are used. Further a set of rules have been applied to detect nested entities (E.g., district, town nested entities for location entity). Supported languages are Hindi, Bengali, Oriya, Telugu, Urdu.

Important findings of [1] suggests, if the available training set is small then using rule based methods can improve f-measure.

[2] has suggested machine learning based approach using Conditional Random Fields (CRFs) with feature induction and heuristics based rules as post processing mechanism for NER in South Asian languages.

Here, the tags which CRF has categorized as O (Other) are reconsidered for adherence to given rules and if confidence level exceeds a given threshold (E.g., 0.15) then the suggested tag is considered as the named entity instead of O. However, this approach has improved recall by 7% while causing slight decrease in precision (3%).

[3] has used hybrid approach for NER with CRFs, language rules and gazetteer lists.

CRF model is used with rule based methods in [4] for Telugu language.

In [8], 3 stage approach is suggested for NER task namely, use of NE dictionary, rules for named entity and left-right co-occurrence statistics. In the 3rd step, n-gram based named entity detection is performed. This approach is supervised method that relies in the co occurrence of left and right words.

CRF and HMM based hybrid approach is suggested in [9] for NER in Indian languages. It is concluded that when 2 statistical models are exploited, it gives better results than using only one approach.

[16] have used hybrid approach using 2 main steps. First, set of constraints are generated for each type such Person, Location and Organization. These are compiled by linguists and represented as FSA to generate most likely candidates. Then, these candidates will be assigned class probability and generative class model is created based on this. Transliteration is used to identify foreign names.

            2.4 Referencing gazetteer lists

This is most simple and fastest method of named entity recognition. However, since named entities are numerous and constantly evolving, this approach itself has not been sufficient for effective NER task. However, in [5] it is found that incorporating gazetteer list can significantly improve the performance.

Gazetteer lists has been created in [1]  using transliteration for month names, days, common locations, first name, middle name, last name etc.

[2] has used gazetteer lists of list of measures (kilogram, lacks), numerals and quantifiers (first, second) and time expressions (date, month, minutes, hours).

2.5 Other methods

A phonetic matching technique is harnessed in [12] for NER in Indian languages on the basis of similar sounding property. They have used Stanford NER as the reference entity database and have come up with a Hindi named entity database using a phonetic matcher.

In [17], external resources such as Wikipedia infobox features are used to infer entity name along with word clustering algorithm to partition words into classes based on their co occurrence statistics in a large corpera.

3. Feature Selection

When it comes to feature selection, available word and tag context plays a major role. Many systems seems to use binary features which represents the presence or absence of a given property of a word.

Static words (previous and next words), context lists (frequent words in a given window for a particular class, E.g., Location class: city, going to), dynamic NE tag (NE tag for previous word), first word, contains digit, numerical characters, affixes (word suffix, word prefix), root information of word, Part of Speech (POS) tag are used as features in [1] with MaxEnt model.

It is highlighted in [1] that window of (w-2, w+2) gives the best results. Further, it is evident in [1] that usage of complex feature set does not guarantee better result.

[2] has used language independent features such as window of the words (window size 5), statistical suffixes for person and location entities (extracted as lists and used as binary feature), prefixes (to avoid agglutinative nature/ postpositions), start of sentence and presence of digits.

Prefix and suffix information is used as features in [3] as Indian languages are highly inflected (window size 5). In addition, previous word tags, rare word (most frequent words in language) and POS tags are used. Here, Oriya, Urdu and Telingu languages have shown poor performance when compared to Hindi and Bengali due to poor language features.

In [4], “majority tag” is used as an additional feature, which uses contextual and frequency information of other tags that are literally similar, to label an unnamed tag.

In experiment results of [5], it is highlighted that [-3, +2] window size gives the optimal results and increasing the window size has decreased the f-measure.

4. Recognizing different entity types

Entity type	Method	Challenges
Person name	look up procedure, analyse local lexical context, looking at part of sequence of candidate words (name component) Features: POS tags, capitalization, decimal digits, bag of words, Left and right context Token legth	Name variations (same person referred in different names) - reuse of name parts, morphological variants prefixes etc., transliteration differences Person name can be proper noun
Organization	Use organization specific candidate words	Various ways of representing abbriviations
Place	Using gazetteer, trigger words (E.g., Newyork city)	Homographic with common names, historical variants, exonyms (foreign variants), endonyms (local variants)

5. Summary and Conclusion  

CRF based/ Hybrid/ Chain of named entity recognizers/ Rule based methods as post processing mechanism

5. References

[1] A Hybrid Approach for Named Entity Recognition in Indian Languages: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[2] Aggregating Machine Learning and Rule Based Heuristics for Named Entity Recognition: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[3] Language Independent Named Entity Recognition in Indian Language: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[4] Named Entity Recognition for Telugu: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[5] Bengali Named Entity Recognition using Support Vector Machine: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[6] Domain Focused Named Entity Recognizer for Tamil Using Conditional Random Fields: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[7] A Character n-gram Based Approach for Improved Recall in Indian Language NER: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[8] An Experiment on Automatic Detection of Named Entities in Bangla: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[9] A Hybrid Named Entity Recognition System for South Asian Languages: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[10] CRF++: Yet Another CRF toolkit: http://crfpp.googlecode.com/svn/trunk/doc/index.html

[11] Named Entity Recognition for South Asian Languages: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[12] Named Entity Recognition for Indian Languages: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[13] Experiments in Telugu NER: A Conditional Random Field Approach: NER for South and South East Asian Languages: IJCNLP-08 Workshop: 2008

[14] NERA: Named Entity Recognition for Arabic: Journal of the American Society for Information Science and Technology: Volume 60 Issue 8, August 2009 Pages 1652-1663

[15] Integrated Machine Learning Techniques for Arabic Named Entity Recognition: International Journal of Computer Science Issues (IJCSI) . Jul2010, Vol. 7 Issue 4, p27-36. 10p. 2 Charts, 11 Graphs.

[16] Chinese Word Segmentation and Named Entity Recognition: A Pragmatic Approach: Microsoft Research - China

[17] A Named Entity Labeler for German: exploiting Wikipedia and distributional clusters

Content Extraction and Context Inference based Information Retrieval

Final year research project

 Abstract

At present, most of the information retrieval mechanisms consider only exact matches of textual metadata such as topics, manual tags and descriptions etc. These methods are yet to provide the right information to match the level of human intuition driven relevance. The main contributor to such factors is due to the lack of assessing relevance of the content and context of the available data in a unified manner. 

Extracting semantic content and inferring knowledge from low level features has always been a major challenge because of the well-known semantic gap issue.

The proposed solution strives to overcome the above mentioned difficulty by providing a framework based approach using machine learning and knowledge representation where right information can be retrieved regardless of the content format or contextual discrepancies. Given that information can be embedded as any content format, the proposed framework analyzes and provides a set of content and context descriptors which can be used in any information retrieval application. 

Key Words:
Information Retrieval, Computer Vision, Ontology, Development Framework

Literature Review

In spite of exponential growth of information, which comes in various forms such as video,

image and audio, modern information retrieval mechanisms still use manual, text based

metadata such as topic, tags and description to provide relevant results to user queries. 

Actual content and its associated context are not considered by information retrieval mechanisms

when assessing relevance of the search result to the given user query. 

Accordingly, modern information retrieval systems are yet far beyond from the way human instinct would assess relevance of the information. 

Considering existing products, given a sample image or audio, Query By Example (QBE) methods have been suggested to find similar content by analyzing and matching the actual content. However, in this approach matching is done between low level features. 

It is difficult for user to match the search intention in close proximity to the respective low level features, which results in significant semantic information loss. Ontology driven methods are invented to provide semantic analysis of the information using an underlying knowledge base. However, these solutions are either text or web content based. 

Each actual content representation and its associated context hold equal value when weighing relevance of information to the user. So, due to the information loss that can incur by only considering the text, relevance of the results is greatly reduced. Further, to bridge the gap between human cognitive way of information retrieval and automatic information retrieval, machines should simulate this behavior by analyzing the obtainable audio, visual content. 

Even though it is evident that visual information such as image and video helps user to understand a particular concept more realistically with less effort, no research has been done to find a collective way of processing visual information along with text and audio and infer the associated context.

After an extensive study on the research being done on this area it is found that, extracting semantic concepts from low level observable features has always been a major challenge due to the well-known semantic gap issue. 

When it comes to feature detection and extraction of visual information, local features are preferred over global features to avoid back ground clutter. With the advent of scale invariant feature detectors and descriptors such as SIFT and SURF, object detection and recognition task has improved drastically with invariance to scale, rotation and illumination. Also, due to the high dimensionality of these descriptors, distinctiveness is greatly improved. Bag of visual Words model has adopted the above advantages in its application on semantic object detection. 

During the evaluation of different content processing mechanisms for image, video and audio, it is found that even though the processing mechanism for each content format differs from each other, all of them have a common flow namely, pre-processing, feature detection, feature extraction and semantic concept detection. 

Once the semantic concepts are extracted from the low level features, context should be inferred for a given set of concepts to further refine the solution. 

Wide range of context inferring approaches is considered namely, Natural Language Processing (NLP), Logic based methods (formal logic, predicate logic), Fuzzy reasoning, Probabilistic methods (Bayesian Reasoning) and semantic networks. 

Semantic networks are designated as the main technique to infer the context, yet no sufficient algorithm was encountered to meet the exact requirement. Further, author discovered that concept of fuzzy reasoning can be used to assess relevance in form of gradual transition between falsehood to truth during application in information retrieval. 

Considering the above given aspects, it is concluded that the suggested solution for the problem domain is unique and feasible, yet immensely challenging due to its limitations in feature extraction techniques to bridge semantic gap issue, especially for a wide domain. Further, limitation on available algorithms for context inference has made it even more time consuming and thought provoking.

 High Level Design

Rich Picture in Information Retrieval Application

High Level Architecture

Data Flow

Class Diagram (Framework Design)

Implementation

Content Negotiation

Content Extraction

• Image/ video processing tool: OpenCV (EmguCV)
• Algorithms: Bag of visual words model, SIFT/ SURF for visual feature detection and extraction, K-means for feature clustering, Naive Bayes for classification

SIFT/ SURF Algorithm comparison

Visual word histograms for similar concepts

Context Inference

Context inference for ambiguous scenarios

Semantic network: WordNet

Application in Information Retrieval

Once content and context descriptors are retrieved from the framework, they can be used in many applications. One such application is given here. 

Literal relatedness between user context and content context can be derived using relevance decision factor. 

This measure can be used to assess the relevance of the available content to a particular user. 

For example, user context can be presented in different forms such as profession, personal interests and present short term search intention. Content context can be metadata of the available content.

Testing and Evaluation

Precision and recall has been used in many information retrieval applications to assess relevance.

For testing, test cases were derived according to the given criteria for each component. Training and ground truth images were taken from Google images and Flickr. 

Accuracy of the concept detection for images with different variations such as scale, illumination and back ground clutter were tested. 

Context inference component was tested for different threshold values to get quantitative measures for relevance such as precision and recall. 

Then, non-functional testing was performed. Test results indicate that the implementation of prototype is successful. 

Further, critical evaluation was performed with participation of domain experts from academic or technical background. Participants confirmed that the suggested approach helps to improve the relevance of information retrieval and thus it is a timely need. 

Future Enhancements

• • Support different content processing mechanisms for same content type (E.g., Research papers and new paper given as text content) 
  • Different processing modules such as audio and web content can be implemented and plugged in to the framework  
  • Fusion of audio words with visual content can be used to improve the accuracy of semantic concept recognition in video content  
  • Scale and evaluate the performance on a realistic database

   

   
  
  

 

ANTLR important language syntaxes

* Rules begins with lower case

* Token types begins with upper case letter

* Lexer rules are given in upper case.

* x | y | z - match any alternative: x or y or z

* x? - x is optional

* x* - x can present zero or more times

* x+ - x can present one or more times

* Lexer rules are always tokens and should be given in upper case. Methods related to lexer rules are prefixed with 'm'.

Reference: The defenitive antlr reference - building domain specific languages

ANTLR FAQ

Does ANTLR knows about a specific language?
No. It recognizes the language using the provided grammar*.
ANTLR can generate a recognizer which will get a particular sentence or phrase as an input and apply the grammatical structure defined in grammar files for those input symbols.

These recognizers can be implemented using different language targets such as C# or Java.

What do you mean by grammar?
Using the grammar, we can tell ANTR how a particular language looks like, so that ANTLR can identify that. Grammar describes a syntax of a language.
Grammar will consist of set of language rules*. Grammar notation used is BNF*.

What is a rule?
A rule represents a phrase or sentence of the language.
Each rule may consist of one of more alternatives sub rules. Rules are invoked in a recursive manner.

Example for BNF notation?
Postal address ::= Name Route City Country
Name ::= First name Middle name? Last name
Route ::= Route name part*

What is a token file?
Token file can be considered as vocabulary for the grammar of specific language.

What is a target language?
Target language is a computer language which ANTLR can generate the recognizer from.

What are actions?
Actions are code blocks written in target language. Actions can refer tokens, rules or character reference using element labels. (x = T where x - label name, T - token)

Using ANTLR with Visual Studio 2008 (C# Target)

ANTLR can be used with different language targets such as C# and Java. This is how to use ANTLR with C# in VisualStudio IDE.

1. Install Java Runtime Environment (JRE).
2. Verify the above using "java -version" command.
3. Set the Java CLASSPATH variable to point the ANTLR package version you want to use. Ex: antlr-3.1.3.jar
4. Build the ANTLR project to verify that there are no issues using following command:
5. java -cp "path to ANTLR package" org.antlr.Tool "grammer file name"
6. Ex: java -cp "C:\antlr\antlr-3.1.3.jar" org.antlr.Tool tsqllexer.g

Some important options:

If you get "java.lang.OutofMemoryError: Java heap space" issue, use the following command to modify the JVM heap size.
Xmx750M

If you get "Multiple token rules can match input such as X, Tokens X.Y was disabled for that input" issue, use the following command to set NFA conversion timeout for each decision for a suitable value.
-Xconversiontimeout 10000

1. Create new C# project.
2. Add these dlls as references: antlr.runtime.dll, Antlr3.Runtime.dll, Antlr3.Utility, StringTemplate.dll
3. Build the C# project.

ANTLR warning "Multiple token rules can match input such as "Xa, Xi, Xe ", Tokens Xi, Xe were disabled for that input"

Have you come across the following warning when you build ANTLR grammer files?

This is due to a failure in NFA > DFA conversion. Creating DFA for the parser is not performed as expected. For NFA conversion, the default time-out value is set to 1000. You need to increase this value to fix the above issue using the following statement when you are building the grammer.

-Xconversiontimeout t (t standas for time-out value)