=Paper=
{{Paper
|id=None
|storemode=property
|title=Concept Extraction Challenge: University of Twente at #MSM2013
|pdfUrl=https://ceur-ws.org/Vol-1019/paper_14.pdf
|volume=Vol-1019
|dblpUrl=https://dblp.org/rec/conf/msm/HabibKZ13
}}
==Concept Extraction Challenge: University of Twente at #MSM2013==
https://ceur-ws.org/Vol-1019/paper_14.pdf
Concept Extraction Challenge:
University of Twente at #MSM2013
Mena B. Habib and Maurice van Keulen
Faculty of EEMCS, University of Twente, Enschede, The Netherlands
{m.b.habib,m.vankeulen}@ewi.utwente.nl
Abstract. Twitter messages are a potentially rich source of continuously and
instantly updated information. Shortness and informality of such messages are
challenges for Natural Language Processing tasks. In this paper we present a
hybrid approach for Named Entity Extraction (NEE) and Classification (NEC)
for tweets. The system uses the power of the Conditional Random Fields (CRF)
and the Support Vector Machines (SVM) in a hybrid way to achieve better results.
For named entity type classification we use AIDA [8] disambiguation system to
disambiguate the extracted named entities and hence find their type.
1 Introduction
Twitter is an important source for continuously and instantly updated information. The
huge number of tweets contains a large amount of unstructured information about users,
locations, events, etc. Information Extraction (IE) is the research field which enables the
use of such a vast amount of unstructured distributed information in a structured way.
Named Entity Recognition (NER) is a subtask of IE that seeks to locate and classify
atomic elements (mentions) in text belonging to predefined categories such as the names
of persons, locations, etc. In this paper we split the NER task into two separate tasks:
Named Entity Extraction (NEE) which aims only to detect entity mention boundaries
in text; and Named Entity Classification (NEC) which assigns the extracted mention
to its correct entity type. For NEE, we used a hybrid approach of CRF and SVM to
achieve better results. For NEC, we first apply AIDA disambiguation system [8] to
disambiguate the extracted named entities, then we use the Wikipedia categories of the
disambiguated entities to find the type of the extracted mention.
2 Our Approach
2.1 Named Entity Extraction
For this task, we made use of two famous state of the art approaches for NER; CRF and
SVM. We trained each of them in a different way as described below. The purpose of
training is only for entity extraction rather recognition (extraction and classification).
Results obtained from both are unionized to give the final extraction results.
Copyright c 2013 held by author(s)/owner(s). Published as part of the
· #MSM2013 Workshop Concept Extraction Challenge Proceedings ·
available online as CEUR Vol-1019, at: http://ceur-ws.org/Vol-1019
Making Sense of Microposts Workshop @ WWW’13, May 13th 2013, Rio de Janeiro, Brazil
Conditional Random Fields CRF is a probabilistic model that is widely used for
NER [5]. Despite the successes of CRF, the standard training of CRF can be very ex-
pensive [6] due to the global normalization. In this task, we used an alternative method
called empirical training [9] to train a CRF model. The maximum likelihood estimation
(MLE) of the empirical training has a closed form solution, and it does not need iterative
optimization and global normalization. So empirical training can be radically faster than
the standard training. Furthermore, the MLE of the empirical training is also a MLE of
the standard training. Hence it can obtain competitive precision to the standard training.
Tweet text is tokenized using special tweets tokenizer [1]. For each token, the following
features are extracted and used to train the CRF: (a) The Part of Speech (POS) tag of the
word provided by a special POS tagger designed for tweets [1]. (b) If the word initial
character is capitalized or not. (c) If the word characters are all capitalized or not.
Support Vector Machines SVM is a machine learning approach used for classification
and regression problems. For our task, we used SVM to classify if a tweet segment is a
named entity or not. The training process takes the following steps:
1. Tweet text is segmented using the segmentation approach as described in [4]. Each
segment is considered a candidate for a named entity. We enriched the segments by
looking up a Knowledge-Base (KB) (here we use YAGO [3]) for entity mentions
as described in [2]. The purpose of this step is to achieve high recall. To improve
the precision, we applied filtering hypotheses (such as removing segments that are
composed of stop words or having verb POS).
2. For each tweet segment, we extract the following set of features in addition to those
features mentioned in section 2.1: (a) The joint and the conditional probability of
the segment obtained from Microsoft Web N-Gram services [7]. (b) The stickiness
of the segment as described in [4]. (c) The segment frequency over around 5 million
tweets 1 . (d) If the segment appears in WordNet. (e) If the segment appears as a
mention in Yago KB. (f) AIDA disambiguation system score for the disambiguated
entity of that segment (if any).
The selection of the SVM features is based on the claim that disambiguation clues
can help in deciding if the segment is a mention for an entity or not [2].
3. An SVM with RBF kernel is trained whether the candidate segment represents a
mention of NE or not.
We take the union of the CRF and SVM results, after removing duplicate extractions,
to get the final set of annotations. For overlapping extractions we select the entity that
appears in Yago, then the one having longer length.
2.2 Named Entity Classification
The purpose of NEC is to assign the extracted mention to its correct entity type. For
this task, we first use the prior type probability of the given mention in the training
1
http://wis.ewi.tudelft.nl/umap2011/ + TREC 2011 Microblog track collec-
tion.
18
· #MSM2013 · Concept Extraction Challenge · Making Sense of Microposts III ·
Table 1: Extraction Results
Pre. Rec. F1
Twiner Seg. 0.0997 0.8095 0.1775
Yago 0.1489 0.7612 0.2490
Twiner∪Yago 0.0993 0.8139 0.1771
Filter(Twiner∪Yago) 0.2007 0.8066 0.3214
SVM 0.7959 0.5512 0.6514
CRF 0.7157 0.7634 0.7387
CRF∪SVM 0.7166 0.7988 0.7555
Table 2: Extraction and Classification Results
Pre. Rec. F1
CRF 0.6440 0.6324 0.6381
AIDA Disambiguation
0.6545 0.7296 0.6900
+ Entity Categorization
data. If the extracted mention is out of vocabulary (does not appear in training set), we
apply AIDA disambiguation system on the extracted mentions. AIDA provides the most
probable entity for the mention. We get the Wikipedia categories of that entity from the
KB to form an entity profile. Similarly, we use the training data to build a profile of
Wikipedia categories for each of the entity types (PER, ORG, LOC and MISC).
To find the type of the extracted mention, we measure the document similarity be-
tween the entity profile and the profiles of the 4 entity types. We assign the mention to
the type of the most similar profile.
If the extracted mention is out of vocabulary and is not assigned to an entity by
AIDA we try to disambiguate the first token of it. If all those methods failed to find
entity type for the mention we just assign ”PER” type.
3 Experimental Results
In this section we show our experimental results of the proposed approaches on the
training data. All our experiments are done through a 4-fold cross validation approach
for training and testing. We used Precision, Recall and F1 measures as evaluation cri-
teria for those results. Table 1 shows the NEE results along the extraction process
phases. Twiner Seg. represents results of the tweet segmentation algorithm described
in [4]. Yago represents results of the surface matching extraction as described in [2].
Twiner∪Yago represents results of merging the output of the two aforementioned meth-
ods. Filter(Twiner∪Yago) represents results after applying filtering hypothesis. The
purpose of those steps is to achieve as much recall as possible with reasonable preci-
sion. SVM is trained as described in section 2.1 to find which of the segments represent
true NE. CRF is trained and tested on tokenized tweets to extract any NE regardless
of its type . CRF∪SVM is the unionized set of results of both CRF and SVM. Table
2 shows the final results of both extraction with CRF∪SVM and entity classification
19
· #MSM2013 · Concept Extraction Challenge · Making Sense of Microposts III ·
using the method presented in section 2.2 (AIDA Disambiguation + Entity Catego-
rization). It also shows the CRF results when trained to recognize (extract and classify)
NE. We considered it as our baseline. Our method of separating the extraction and clas-
sification outperforms the baseline.
4 Conclusion
In this paper, we present our approach for the IE challenge. We split the NER task into
two separate tasks: NEE which aims only to detect entity mention boundaries in text;
and NEC which assigns the extracted mention to its correct entity type. For NEE we
used a hybrid approach of CRF and SVM to achieve better results. For NEC we used
AIDA disambiguation system to disambiguate the extracted named entities and hence
find their type.
References
1. K. Gimpel, N. Schneider, B. O’Connor, D. Das, D. Mills, J. Eisenstein, M. Heilman, D. Yo-
gatama, J. Flanigan, and N. A. Smith. Part-of-speech tagging for twitter: annotation, features,
and experiments. In Proc. of the 49th ACL conference, HLT ’11, pages 42–47, 2011.
2. M. B. Habib and M. van Keulen. Unsupervised improvement of named entity extraction in
short informal context using disambiguation clues. In Proc. of the Workshop on Semantic Web
and Information Extraction (SWAIE), pages 1–10, 2012.
3. J. Hoffart, F. M. Suchanek, K. Berberich, E. L. Kelham, G. de Melo, and G. Weikum. Yago2:
Exploring and querying world knowledge in time, space, context, and many languages. In
Proc. of WWW 2011, 2011.
4. C. Li, J. Weng, Q. He, Y. Yao, A. Datta, A. Sun, and B.-S. Lee. Twiner: named entity recogni-
tion in targeted twitter stream. In Proc. of the 35th ACM SIGIR conference, SIGIR ’12, pages
721–730, 2012.
5. A. McCallum and W. Li. Early results for named entity recognition with conditional ran-
dom fields, feature induction and web-enhanced lexicons. In Proc. of the 7th HLT-NAACL
conference, CONLL ’03, pages 188–191, 2003.
6. C. Sutton and A. McCallum. Piecewise training of undirected models. In Proc. of UAI, pages
568–575, 2005.
7. K. Wang, C. Thrasher, E. Viegas, X. Li, and B.-j. P. Hsu. An overview of microsoft web
n-gram corpus and applications. In Proc. of the NAACL HLT 2010, pages 45–48, 2010.
8. M. A. Yosef, J. Hoffart, I. Bordino, M. Spaniol, and G. Weikum. Aida: An online tool for
accurate disambiguation of named entities in text and tables. PVLDB, 4(12):1450–1453, 2011.
9. Z. Zhu, D. Hiemstra, P. M. G. Apers, and A. Wombacher. Closed form maximum likeli-
hood estimator of conditional random fields. Technical Report TR-CTIT-13-03, University of
Twente, 2013.
20
· #MSM2013 · Concept Extraction Challenge · Making Sense of Microposts III ·