Microposts are small fragments of social media content that have been published using a lightweight paradigm (e.g. Tweets, Facebook likes, foursquare check-ins). Microposts have been used for a variety of applications (e.g., sentiment analysis, opinion mining, trend analysis), by gleaning useful information, often using third-party concept extraction tools. There has been very large uptake of such tools in the last few years, along with the creation and adoption of new methods for concept extraction. However, the evaluation of such eorts has been largely consigned to document corpora (e.g. news articles), questioning the suitability of concept extraction tools and methods for Micropost data. This report describes the Making Sense of Microposts Workshop (#MSM2013) Concept Extraction Challenge, hosted in conjunction with the 2013 World Wide Web conference (WWW'13). The Challenge dataset comprised a manually annotated training corpus of Microposts and an unlabelled test corpus. Participants were set the task of engineering a concept extraction system for a dened set of concepts. Out of a total of 22 complete submissions 13 were accepted for presentation at the workshop; the submissions covered methods ranging from sequence mining algorithms for attribute extraction to part-of-speech tagging for Micropost cleaning and rule-based and discriminative models for token classication. In this report we describe the evaluation process and explain the performance of dierent approaches in dierent contexts.
Since the rst Making Sense of Microposts (#MSM) workshop at the Extended Semantic Web Conference in 2011 through to the most recent workshop in 2013 we have received over 60 submissions covering a wide range of topics related to interpreting Microposts and (re)using the knowledge content of Microposts. One central theme that has run through such work has been the need to understand and learn from Microposts (social network-based posts that are small in size and published using minimal eort from a variety of applications and on dierent devices), so that such information, given its public availability and ease of retrieval, can be reused in dierent applications and contexts (e.g. music recommendation, social bots, news feeds). Such usage often requires identifying entities or concepts in Microposts, and extracting them accordingly. However this can be hindered by: (i) the noisy lexical nature of Microposts, where terminology diers between users when referring to the same thing and abbreviations are commonplace; (ii) the limited length of Microposts, which restricts the contextual information and cues that are available in normal document corpora.
The exponential increase in the rate of publication and availability of
Microposts (Tweets, FourSquare check-ins, Facebook status updates, etc.), and
applications used to generate them, has led to an increase in the use of third-party
entity extraction APIs and tools. These function by taking as input a given
text, identifying entities within them, and extracting entity type-value tuples.
Rizzo & Troncy [
This prompted the Concept Extraction Challenge held as part of the Making Sense of Microposts Workshop (#MSM2013) at the 2013 World Wide Web Conference (WWW’13) . The rationale behind this was that such a challenge, in an open and competitive environment, would encourage and advance novel, improved approaches to extracting concepts from Microposts. This report describes the #MSM2013 Concept Extraction Challenge, collaborative annotation of the corpus of Microposts and our evaluation of the performance of each submission. We also describe the approaches taken in the systems entered using both established and developing alternative approaches to concept extraction, how well they performed, and how system performance diered across concepts. The resulting body of work has implications for researchers interested in the task of extracting information from social data, and for application designers and engineers who wish to harvest information from Microposts for their own applications. 2
We begin by describing the goal of the challenge and the task set, and the process we followed to generate the corpus of Microposts. We conclude this section with the list of submissions accepted.
The challenge required participants to build semi-automated systems to identify concepts within Microposts and extract matching entity types for each concept identied, where concepts are dened as abstract notions of things. In order to focus the challenge we restricted the classication to four entity types: (i) Person PER, e.g. Obama; (ii) Organisation ORG, e.g. NASA; (iii) Location LOC, e.g. New York; (iv) Miscellaneous MISC, consisting of the following: lm/movie, entertainment award event, political event, programming language, sporting event and TV show.
Submissions were required to recognise these entity types within each Micropost, and extract the corresponding entity type-value tuples from the Micropost.
8 7 0 , 0 0 0 p e o p l e i n canada depend on #f o o d b a n k s
25% i n c r e a s e i n t h e l a s t 2 y e a r s p l e a s e g i v e g e n e r o u s l y The fourth token in this Micropost refers to the location Canada ; an entry to the challenge would be required to spot this token and extract it as an annotation, as:
The complete description of concept types and their scope, and additional examples can be found on the challenge website 5, and also in the appendices in the challenge proceedings.
To encourage competitiveness we solicited sponsorship for the winning submission. This was provided by the online auctioning web site eBay 6, who oered a $1500 prize for the winning entry. This generous sponsorship is testimony to the growing industry interest in issues related to automatic understanding of short, predominantly textual posts Microposts; challenges faced by major Social Web and other web sites, and increasingly, marketing and consumer analysts and customer support across industry, government, state and not-for-prots organisations around the world. 2.2
The dataset consists of the message elds of each of 4341 manually annotated Microposts, on a variety of topics, including comments on the news and politics, collected from the end of 2010 to the beginning of 2011, with a 60% / 40% split between training and test data. The annotation of each Micropost in the training dataset gave all participants a common base from which to learn extraction patterns. The test dataset contained no annotations; the challenge task was for
participants to provide these. The complete dataset, including a list of changes and the gold standard, is available on the #MSM2013 challenge web pages 7, accessible under the Creative Commons Attribution-NonCommercial-ShareAlike
To assess the performance of the submissions we used an underlying ground truth, or gold standard. In the rst instance, the dataset was annotated by two of the authors of this report. Subsequent to this we logged corrections to the annotations in the training data submitted by participants, following which we release an updated dataset. After this, based on a recommendation, we set up a GitHub repository to simplify collaborative annotation of the dataset. Four of the authors of this report then annotated a quarter of the dataset each, and then checked the annotations that the other three had performed to verify correctness. For those entries for which consensus was not reached, discussion between all four annotators was used to come to a nal conclusion. This process resulted in better quality and higher consensus in the annotations. A very small number of errors was reported subsequent to this; a nal submission version with these corrections was used by participants for their last set of experiments and to submit their nal results.
Figure 1 presents the entity type distributions over the training set, test set and over the entire corpus.
0 0 5 2 0 0 5 1 0 0 5 0 train test all MISC
PER
ORG
LOC
Twenty-two complete submissions were received for the challenge; each of which
consisted of a short paper explaining the system’s approach, and up to three
dierent test set annotations generated by running the system with dierent
settings. After peer review, thirteen submissions were accepted; for each, the
submission run with the best overall performance was taken as the result of the
system, and used in the rankings. The accepted submissions are listed in Table 1,
with the run taken as the result set for each.
Participants approached the concept extraction task with rule-based, machine
learning and hybrid methods. A summary of each approach can be found in
Figure 2, with detail in the author descriptions that follow this report. We compared
these approaches according to various dimensions: state of the art (SoA) named
entity recognition (NER) features employed (columns 4-11) ([
From the results and participants’ experiments we make a number of observations. With regard to the strategy employed, the best performing systems (from the top, 14, 21, 15, 25), based on overall F 1 score (see Section 3), were hybrid. ,,# ssSp L Sp sea , is
e ,@ iM ,RU issM reCw tcnuP ltiaap a lS R uP ] 7 []8g ][4 I[PA lireen LTNK lteeN F b a B t e N l e iad i ab ep ik ,B B W ia D ed p B
D s s s le le le u u u R R R s s le le leN SD u u R R ab W t e
B s m e t s y S l a n r e t x E . p e r P s er re th tu
a O e
F ic eg t s ed iu l g w n o i n L K n o ti d ca e i s if u ss r la ie C f i s n s o la itc
a C tr x E tonC tex p u k o o l t s i
L se lca tax r oL syn u t a e f t n r o -a itc e n h u t F f o e t a t S S O
P . p r o M n e k o T n i a r T h r x on tu t u e i
t t t ea y a n c b e o a F
f ed tr (
C tr r
e x
h y a e e t o l e iz t
O p h s p ( m t e
c s e f w n r
o o o s o t e e d c c i n g t i r a
a r te t w fo t
s x a t r , x d e t ) s n te se e
i e a n u th h r o t e r
T C g o o ( , d f t s
p le r d d o u w e n t k o s o c o n u sp ra lo k s e t e
c r r x ts i r e i t u co t L is ta
p , u e s e t g f n c x n l
n e il a m o t n lu c n l
o o a i o e c n it .C th l io d n n ca it d
o d a o i i d , t ra L a .) ca t , , p
n o t t i o x t i P
t ( E d c
a e n t s
c a u i
s t
F s a p u e c a , a d n t ) l
c e o a S d
h C O d t .
e n ) 3 h (P a n s 1 t o
) 0 2 ,) ch n d te
o e s e i M m e t m y S te p c r S M s -s ra fo l
y f t r a # (S -o x e n r
m P n p x s e E e te , io t (
M a f ( o y t o e d i r e d gy t p s t i
c m n e o e r m e l
p te om th oh th , s t p o ) y
e s , u ) r A y o
g r d le . e M fo le s 2 t ,
w e lloo FW F 1 1 0 2 s o P w T m e t S ,ix ix f f
f reP uS p p a a C C Is Is agY tfsoo roW
F F+ RB CR VM
S 1 1 0 2 s o P w T ,ap ap sC llC I A W T ,P P isN isV W T a i d e p B D F R C ia th epd lit
g
B po
D S
2
,
re re
e e
tt t
e te
az az
G G
iad IE
epBD LBA
,IsapC ,llapCA reoLw seaC
m
ra
g
N
W
T
The success of these models appears to rely on the application of o-the-shelf
systems (e.g. AIDA [
Among the rule-based approaches, the winning strategy was also similar. Submission 20 achieved the fourth best result overall, by taking an existing rule-based system (ANNIE), and simply increasing the coverage of captured entities by building new gazetteers 15. We also nd that for entity extraction the participants used both rule-based and statistical approaches. Considering current state of the art approaches, statistical models are able to handle this task well.
Looking at features, the gazetteer membership and part-of-speech (POS)
features played an important role; the best systems include these. For the gazetteers,
a large number of dierent resources were used, including Yago, WordNet,
DBpedia, Freebase, Microsoft N-grams and Google. Existing POS taggers were trained
on newswire text (e.g. ANNIEPos [
Considering pre-processing of Microposts, we nd the following:
removal of Twitter-specic markers, e.g. hashtags ( #), mentions (@), retweets
(RT),
removal of external URL links within Microposts ( URL),
removal of punctuation marks ( Punct), e.g. points, brackets,
removal of well-known slang words using dictionaries 16 (Slang), e.g. lol,
tmr, unlikely to refer to named entities,
8 http://opennlp.apache.org
9 http://alias-i.com/lingpipe
10 http://www.opencalais.com
11 http://wikipedia-miner.cms.waikato.ac.nz
12 http://www.alchemyapi.com
13 http://dbpedia.org/spotlight
14 http://www.zemanta.com
15 Another o-the-shelf entity extractor employed was BabelNet API [
With respect to the data used for training the entity extractors, the majority
of submissions utilised the challenge training dataset, containing annotated
Micropost data (TW) alone. A single submission, (3, the sixth best system overall),
made use of a large silver dataset (CoNLL 2003 [
The evaluation involved assessing the correctness of a system ( S), in terms of the performance of the system’s entity type classiers when extracting entities from the test set ( T S). For each instance in T S, a system must provide a set of tuples of the form: (entity type, entity value). The evaluation compared these output tuples against those in the gold standard ( GS). The metrics used to evaluate these tuples were the standard precision ( P ), recall (R) and f-measure (F1), calculated for each entity type. The nal result for each system was the average performance across the four dened entity types.
To assess the correctness of the tuples of an entity type t provided by a system S, we performed a strict match between the tuples submitted and those in the GS. We consider a strict match as one in which there is an exact match, with conversion to lowercase, between a system value and the GS value for a given entity type t. Let (x; y) 2 St denote the set of tuples extracted for entity type t by system S, (x; y) 2 GSt denote the set of tuples for entity type t in the gold standard. We dene the set of True Positives ( T P ), False Positives ( F P ) and False Negatives ( F N ) for a given system as:
T Pt = f(x; y) j (x; y) 2 (St \ GSt)g F Pt = f(x; y) j (x; y) 2 St ^ (x; y) 2= GStg
F Nt = f(x; y) j (x; y) 2 GSt ^ (x; y) 2= Stg
Therefore T Pt denes the set of true positives considering the entity type and value of tuples; F Pt is the set of false positives considering the unexpected results for an entity type t; F Nt is the set of false negatives denoting the entities that were missed by the extraction system, yet appear within the gold standard. As we require matching of the tuples (x; y) we are looking for strict extraction matches, this means that a system must both detect the correct entity type ( x) 17 the ACE Program: http://projects.ldc.upenn.edu/ace (1) (2) (3) and extract the correct matching entity value ( y) from a Micropost. From this set of denitions we dene precision ( Pt) and recall (Rt) for a given entity type t as follows:
As we compute the precision and recall on a per-entity-type basis, we dene the average precision and recall of a given system S, and the harmonic mean,
Pt = Rt =
jT Ptj jT Pt [ F Ptj
jT Ptj jT Pt [ F Ntj P = PP ER + PORG + PLOC + PMISC
4 R =
RP ER + RORG + RLOC + RMISC
4 (4) (5) (6) (7) (8) We report the dierences in performance between participants’ systems, with a focus on the dierences in performance by entity type. The following subsections report results of the evaluated systems in terms of precision, recall and
Precision. We begin by discussing the performance of the submissions in terms of precision. Precision measures the accuracy, or ‘ purity ’, of the detected entities in terms of the proportion of false positives within the returned set: high precision equates to a low false positive rate. Table 3.2 shows that hybrid systems are the top 4 ranked systems (in descending order, 14, 21, 30, 15), suggesting that a combination of rules and data-driven approaches yields increased precision. Studying the features of the top-performing systems, we note that maintaining capitalisation is correlated with high precision. There is, however, clear variance in other techniques used (classiers, extraction methods, etc.) between the systems.
Fine-grained insight into the disparities between precision performance was obtained by inspecting the performance of the submissions across the dierent concept types (person, organisation, location, miscellaneous). Figure 3a presents the distribution of precision values across these four concept types and the macro average of these values. We nd that systems do well (above the median of average precision values) for person and location concepts, and perform worse than the median for organisations and miscellaneous. For the entity type ‘ miscellaneous ’, this is not surprising as it features a fairly nuanced denition, including lms and movies, entertainment award events, political events, programming languages, sporting events and TV shows. We also note that several submissions used gazetteers in their systems, many of which were for locations; this could have contributed to the higher precision values for location concepts. Recall. Although precision aords insight into the accuracy of the entities identied across dierent concept types, it does not allow for inspecting the detection rate over all possible entities. To facilitate this we also report the recall scores of each submission, providing an assessment of the entity coverage of each approach. Table 3 presents the overall recall values for each system and for each and across all concept types. Once again, as with precision, we note that hybrid systems (21, 15, 14) appear at the top of the rankings, with a rule-based approach (20) and a data driven approach (3) coming fourth and fth respectively.
Looking at the distribution of recall scores across the submissions in Figure 3c we see a similar picture as before when inspecting the precision plots. For instance, for the person and location concepts we note that the submissions exceed the median of all concepts (when the macro-average of the recall scores is taken), while for organisation and miscellaneous lower values than the median are observed. This again comes back to the nuanced denition of the miscellaneous category, although the recall scores are higher on average than the precision score. The availability of person name and place name gazetteers also benets identication of the corresponding concept types. This suggests that additional eort is needed to improve the organisation concept extraction and to provide information to seed the detection process, for instance through the provision of organisation name gazetteers. Interestingly, when we look at the best performing system in terms of recall over the organisation concept we nd that submission 14 uses a variety of third party lookup lists (Yago, Microsoft ngrams and Wordnet), suggesting that this approach leads to increased coverage and accuracy when extracting organisation names. F-Measure (F1). By combining the precision and recall scores together for the individual systems using the f-measure (F 1) score we are provided with an overall assessment of concept extraction performance. Table 4 presents the f-measure (F1) score for each submission and performance across the four concept types. We note that, as previously, hybrid systems do best overall (top-3 places), indicating that a combination of rules and data-driven approaches yields the best results. Submission 14 records the highest overall F 1 score, and also the highest scores for the person and organisation concept types; submission 15 records the highest F1 score for the location concept type; while submission 21 yields the highest F 1 score for the miscellaneous concept type. Submission 15 uses Google Gazetteers together with part-of-speech tagging of noun and verb phrases, suggesting that this combination yields promising results for our nuanced miscellaneous concept type.
Figure 3e shows the distribution of F 1 scores across the concept types for each submission. We nd, as before, that the systems do well for person and location and poorly for organisation and miscellaneous. The reasons behind the reduced performance for these latter two concept types are, as mentioned, attributable to the availability of organisation information in third party lookup lists. The aim of the MSM Concept Extraction Challenge was to foster an open initiative for extracting concepts from Microposts. Our motivation for hosting the challenge was born of the increased availability of third party extraction tools, and their widespread uptake, but the lack of an agreed formal evaluation of their accuracy when applied over Microposts, together with limited understanding of how performance diers between concept types. The challenge’s task involved the identication of entity types and value tuples from a collection of Microposts. To our knowledge the entity annotation set of Microposts generated as a result of the challenge, and thanks to the collaboration of all the participants, is the largest annotation set of its type openly available online. We hope that this will provide the basis for future eorts in this eld and lead to a standardised evaluation eort for concept extraction from Microposts.
The results from the challenge indicate that systems performed well which: (i) used a hybrid approach, consisting of data-driven and rule-based techniques; and (ii) exploited available lookup lists, such as place name and person name gazetteers, and linked data resources. Our future eorts in the area of concept extraction from Microposts will feature additional hosted challenges, with more complex tasks, aiming to identify the dierences in performance between disparate systems and their approaches, and inform users of extraction tools on the suitability of dierent applications for dierent tasks and contexts.