Wednesday, May 6, 2015

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




Friday, May 1, 2015

Warning: Connection timeout. Retrying... in Vagrant

I got this error when trying to ssh connect to Vagrant instance.

slave01: SSH auth method: private key
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying...
    slave01: Warning: Connection timeout. Retrying…

This is how I resolved that.

Check the running VMs using the command below:
vboxmanage list runningvms

"Cluster_master_1425452823416_28694" {5b4505cb-2b48-45c1-a941-8e4b2d36f29b}
"Cluster_slave01_1425452852606_67792" {740aa005-6666-43e0-9631-a2f2d6e4caa5}
"Cluster_slave02_1425452882392_41607" {888cf959-1978-4474-86ef-ddfaaf3491f5}

Provide the required keyboard input (enter in this case) using following command:
vboxmanage controlvm Cluster_slave01_1425452852606_67792 keyboardputscancode 1c

Progress state: NS_ERROR_FAILURE in Vagrant

I got the following error when trying to start Vagrant instance.

There was an error while executing `VBoxManage`, a CLI used by Vagrant

for controlling VirtualBox. The command and stderr is shown below.

Command: ["hostonlyif", "create"]

Stderr: 0%...

Progress state: NS_ERROR_FAILURE

VBoxManage: error: Failed to create the host-only adapter

VBoxManage: error: VBoxNetAdpCtl: Error while adding new interface: failed to open /dev/vboxnetctl: No such file or directory

VBoxManage: error: Details: code NS_ERROR_FAILURE (0x80004005), component HostNetworkInterface, interface IHostNetworkInterface

VBoxManage: error: Context: "int handleCreate(HandlerArg*, int, int*)" at line 68 of file VBoxManageHostonly.cpp

I could get this resolved by following action.

I have set up Vagrant cluster and there was one VM that is not running on Vagrant opened and running in VirtualBox. Issue might be due to that as well.

Restart Virtualbox using the following command:

sudo /Library/StartupItems/VirtualBox/VirtualBox restart