This paper presents the experiments carried out by us at Jadavpur University as part of the participation in FIRE 2015 task: Entity Extraction from Social Media Text - Indian Languages (ESM-IL). The tool that we have developed for the task is based on Trigram Hidden Markov Model that utilizes information like gazetteer list, POS tag and some other word level features to enhance the observation probabilities of the known tokens as well as unknown tokens. We submitted runs for English only. A statistical HMM (Hidden Markov Models) based model has been used to implement our system. The system has been trained and tested on the datasets released for FIRE 2015 task: Entity Extraction from Social Media Text - Indian Languages (ESM-IL). Our system is the best performer for English language and it obtains precision, recall and F-measures of 61.96, 39.46 and 48.21 respectively.
Categories and Subject Descriptors
The objective of named entity recognition is to identify and classify every word/term in a document into some predefined categories like person name, location name, organization name, miscellaneous name (date, time, percentage and monetary expressions etc.) etc.
NER is an important task, having applications in Information Extraction, Question Answering, Machine Translation, Summarization, Cross-lingual information access and other NLP applications. Over the past decade, Indian language content on various social media( twitter, facebook etc.) is rapidly increasing. When the different companies are interested to ascertain public views on their products and services, they need natural language processing software systems which identify entities and relations among the entities. So, there is a need for automatic entity extraction system.
The earliest works on named entity recognition (NER) primarily uses two major approaches to NER: Rule based (Linguistic) approaches and Machine Learning (ML) based approaches.
The rule based approaches typically use a set of hand crafted
rules [
Machine learning (ML) based techniques for NER make use of
a large amount of NE annotated training data to acquire higher
level language knowledge from the labeled data. Several ML
techniques have already been applied for the NER tasks such as
Markov Model (HMM) [
The hybrid approaches that combines different ML
approaches are also used. Srihari et al.(2000) [
NER systems also use gazetteer lists for identifying names.
Both the linguistic approach [
The NER tasks for Hindi have been presented in [
A discussion on the training data is given in Section 2. The HMM based NER system is described in Section 3. Various features used in NER are then discussed. Next we present the experimental results and related discussions in Section 5. Finally Section 6 concludes the paper. 2. TRAINING DATA PREPARATION The training data released for the FIRE shared task contains two files: one file contains the raw text file and another file contains the NE annotation file in which each row has 6 columns: tweet-id, user-id, NE-tag, NE raw string, NE-start index and NE_length. Index column is the starting character position of NE calculated for each tweet. The participants are instructed to produce the output in the same format after testing the system on the test data. Our system uses the two files supplied for training data and converts the data into the IOB format before training and the data converted in IOB (Inside, Outside and Beginning) format (a format used for the CoNLL-2003 shared task on NER) is used for training. IOB format uses a B−XXX tag that indicates the first word of an entity type XXX and I−XXX that is used for subsequent words of an entity. The tag “O” indicates the word is outside of an NE (i.e., not a part of a named entity). 3. HMM BASED NAMED ENTITY TAGGING A named entity recognizer based on Hidden Markov Model (HMM) finds the best sequence of NE tags t1n that is optimal for a given observation sequence o1n . The tagging problem becomes equivalent to searching for argtm1nax P(o1n | t1n )P(t1n ) (by the application of Bayes’ law), that is, we need to compute: (1). tˆ1n argtm1nax P(o1n | t1n )P(t1n ) Where t1n is a tag sequence and o1n is an observation sequence, P(t1n ) is the prior probability of the tag sequence and P(o1n | t n ) is the likelihood of the word sequence.
1
In general, HMM based sequence labeling tasks such as POS
tagging use words in a sentence as an observation sequence [
Unlike the traditional HMM based NER system, to use this additional information for named entity recognition task, we consider a triplet as an observation symbol: <word, POStag/gazetteer tag , meta-tag >. This is a pseudo token used as an observed symbol, that is, for a tweet of n words, the corresponding observation sequence will be as follows: (<word1, X-tag1, meta-tag1>, <word2, X-tag2, meta-tag2>, <word3, X-tag3, meta-tag3>, .........., <wordn, X-tagn, meta-tagn>) . Here an observation symbol oi corresponds to <wordi, X-tagi, meta-tagi> and X-tag can be either POS tag or gazetteer tag).
Since Equation (1) is too hard to compute directly, HMM taggers follows Markov assumption according to which the probability of a tag is dependent only on short memory (a small, fixed number of previous tags). For example, a bigram tagger considers that the probability of a tag depends only on the previous tag
special tags(meta tag and gazetteer tag)
HMM based NE tagger HMM model NE annotation file
For our proposed trigram model, the probability of a tag depends on two previous tags and thus P(t1n ) is computed as: n P(t1n ) i1 P(ti | ti1, ti2 ) (2) Depending on the assumption that the probability of a word appearing is dependent only on its own tag, P(o1n | t n ) can be 1 simplified to:
n P(o1n | t1n ) i1 P(oi | ti ) (3) Plugging the above mentioned two equations (2) and (3) into (1) results in the following equation by which a bigram tagger estimates the most probable tag sequence: tˆ1n arg max P(t1n | o1n )P(t1n ) arg max n P(oi | ti )P(ti | ti1) (4) t1n t1n i1 Where: the tag transition probabilities, P(ti | ti1) , represent the probability of a tag given the previous tag. P(oi | ti ) represents the probability of an observed symbol given a tag.
Considering a special tag tn+1 to indicate the end sentence
boundary and two special tags t-1 and t0 at the starting boundary
of the sentence and adding these three special tags to the tag set
[
n arg max [ P(oi | ti )P(ti | ti1, ti2 )]P(tn1 | tn )
t1n i1 The equation (5) is still computationally expensive because we need to consider all possible tag sequence of length n. So, dynamic programming approach is used to compute the equation (5).
At the training phase of HMM based NE tagging, observation probability matrix and tag transition probability matrix are created. Architecture of our developed NE tagger is shown in Figure 1. (5) 3.1
Computing Tag Transition Probabilities As we can see from the equation (4), to find the most likely tag sequence for an observation sequence, we need to compute two kinds of probabilities: tag transition probabilities and word likelihoods or observation probabilities.
Our developed trigram HMM tagger requires to compute tag
trigram probability, P(ti | ti1, ti2 ) , which is computed by the
maximum likelihood estimate from tag trigram counts. To
overcome the data sparseness problem, tag trigram probability is
smoothed using deleted interpolation technique [
Computing Observation Probabilities
The observation probability of a observed triplet <word, X-tag,
meta-tag >, which is the observed symbol in our case, is computed
using the following equation [
P(o | t) CC((oo,t)) (7) 3.3
The task of a decoder is to find the best hidden state sequence given an input HMM and a sequence of observations.
The Viterbi algorithm is the most common decoding algorithm
used for HMM based tagging task. This is a standard application
of the classic dynamic programming algorithm[
Given a tag transition probability matrix and the observation probability matrix, Viterbi decoding (used at the testing phase) accepts a tweet in Indian language and finds the most likely tag sequence for the test tweet which is also X-tagged and Meta tagged. Here a tweet is submitted to the viterbi as the observation sequence of triplets:
(<word1, X-tag1, meta-tag1>, <word2, X-tag2, meta-tag2>, <word3, X-tag3, meta-tag3>, .........., <wordn, X-tagn, meta-tagn>) . Here an observation symbol oi corresponds to <wordi, X-tagi, meta-tagi> and X-tag can be either POS tag or gazetteer tag). After assigning the tag sequence to the observation sequence as mentioned above, X-tag and meta-tag information are removed from the output and thus the output for an input sentence is converted to a NE-tagged sentence.
We have used the Viterbi algorithm presented in [
One of the important problems to apply Viterbi decoding
algorithm is how to handle unknown triplets in the input. The
unknown triplets are triplets which are not present in the training
set and hence their observation probabilities are not known. To
handle this problem, we estimate the observation probability of an
unknown one by analyzing X-tag, meta-tag and the suffix of the
word associated with the corresponding the triplet. We estimate
the observation probability of an unknown observed triplet in the
following ways:
The observation probabilities of unknown triplet < word, X-tag,
meta-tag> corresponding to a word in the input sentence are
decided according to the suffix of a pseudo word formed by
adding X-tag and meta-tag to the end of the word. We find the
observation probabilities of such unknown pseudo words using
suffix analysis of all rare pseudo words (frequency <=2) in the
training corpus for the concerned language [
Each token has some properties by which one token differs from another. For example, a token may only consist of digits or it may contain hash. To capture such information specific to a token, we use Meta tag. For example, if a token is consisting of only digits, meta tag that we will assign to the token is ALLDIGITS which we write ALDT in short.
The various meta tags that we use for our task are described below. Meta tag for a token is determined using the following rules which are fired in the following order.
Meta-tag=”YYYY”(default) if the first letter of the token is a capital letter then metatag = "ICAP" end if if the first token is abbreviation then metatag = "ABBR" End If if contains "#" at the begining of the token and the first character after hash is a capital letter then
metatag = "CHAS" ElseIf contains "#" at the begining of the token Then metatag = "HASH" End If if contains "@" at the begining of the token then metatag = "ATSY" If last charater is a colon(":") And the first letter is capital then metatag = "CCOL" ElseIf last charater is a colon(":") Then
metatag = "COLN" End If if contains hyphen and the first character is capital then metatag = "CHYP" ElseIf hyphen occurs after 3 characters from the begining then metatag = "HYPH" End If if the token is 4 digits then
metatag = "DFOR" ElseIf the token is two digits then
metatag = "DTWO" ElseIf the token is one digit then
metatag = "DONE" ElseIf token contains at least one digit then
metatag = "DIGT" End If If contains one comma and contains at least one digit then metatag = "DCOM" ElseIf the last character is a comma and first character is capital then metatag = "CLCO" ElseIf contains one comma at the end of the token then metatag = "LCOM" ElseIf contains more than one comma and first character is capital then
metatag = "CMCO" End If If token contains all dots then
metatag = "ALDT" End If
In earlier sections, we have mentioned that POS tag for a token is replaced by a gazetteer tag if the token is found in a particular gazetteer list. if the length of a raw word is greater than equal to 2 , before searching in the gazetteer list, we remove from the token the symbols such as ",",".",":","#" and "@". The description of gazetteer list is shown in Table 1.
facilities months days period
expressions
expressions words list of person names
extracted from location names
from a list of location names where a extracted word is not the first word of the location name
“count” A list of words indicating monetary expressions such as lakh, crore etc.
1243 257 14 12 7 34 58 18 We follow the following rules for assigning this type of tag to the token: X-tag=POS-tag (default tag) if Token is found in the BPerson list then
X-tag="BPER" elseif Token is found in the IPerson list then elseif Token is found in Blocation list then elseif Token is found in ILocation list then
X-tag = "IPER" X-tag="BLOC" X-tag = "ILOC"
X-tag="FACI" elseif Token is found in the list of facilities then elseif Token is found in the list of month names then
X-tag = "MONT" elseif Token is found in the list of day names then
X-tag= "DAYS" elseif Token is found in the list of period indicating expressions then
X-tag = "PERD" elseif Token is found in the list of expression denoting countthen
X-tag = "COUN" elseif Token is found in the list of monetary expressions then
X-tag = "MONY" End If 5. EVALUATION AND RESULTS We train separately our developed named entity recognizer based on the training data and tune the parameters of our system on the training data for the English language. After learning the tuning parameters, we test our system on the test data for the concerned language. The description of the data for English language is shown in the Table2
After getting the NE-tagged output in IOB format from the HMM model, we observed that the NE tagged output contains some occurrences of a sequence of I-XXXs where the left boundary of each such sequence is a transition from the tag “O” to I-XXXs (but, according to the IOB format, the left boundary of a named entity is a transition from any tag to B-XXX). We have also observed that the word sequence to which this type of tag sequence is assigned is not really a named entity. So, considering this as the errors of the model, we replace such a sequence of I-XXXs in the output by a sequence of “o”. After applying this post-processing on the output produced by the HMM model, the final output file is generated.
Our developed NER system has been evaluated using the traditional precision (P), recall (R) and F-measure (F). For training, tuning and testing our system, we have used the dataset for English language, released by the organizers of the ESM-IL task- FIRE 2015. The organizers of the ESM-IL task- FIRE 2015 released the data in two phases: in the first phase, training data is released along with the corresponding NE annotation file. In the second phase, the test data is released and no NE annotation file is provided. The contestants are instructed to generate NE annotation file for test data using their developed systems. NE annotation file for test data was finally sent to the organizers for evaluation. The organizers evaluate the different runs submitted by the various teams and send the official results to the participating teams.
We have shown in Table 3 the results obtained by our submitted run indicated by team id “KSarkar – JU”. As we can see from the table, our system outperforms the other systems participated in the ESM-IL task. Table 3 only shows the FIRE 2015 official results for English language only. The overall FIRE 2015 official results for ESM-IL task including all languages are shown in Table 4.
This paper describes a named entity recognition system for Entity Extraction from Social Media Text in English language. The features such as Gazetteer list, POS tag and some other word level features have been introduced into the HMM model. The experimental results show that our system is the best performer among the systems participated in the ESM-IL task for English language. The named entity recognition system has been developed using Visual Basic platform so that a suitable user interface can be designed for the novice users. The system has been designed in such a way that only changing the training corpus in a file can make the system portable to a new Indian language.
P