This paper describes the UNED's Online Reputation Monitoring Team participation at RepLab 2013 [3]. Several approaches were tested: rst, an instance-based learning approach that uses Heterogeneity Based Ranking to combine seven di erent similarity measures was applied for all the subtasks. The ltering subtask was also tackled by automatically discovering lter keywords: those whose presence in a tweet reliably con rm (positive keywords) or discard (negative keywords) that the tweet refers to the company [16]. Di erent approaches have been submitted for the topic detection subtask: agglomerative clustering over wiki ed tweets, co-occurrence term clustering [10] and an LDA-based model that uses temporal information. Finally, the polarity subtask was tackled by following the approach presented in [14] to generate domain speci c semantic graphs in order to automatically expand the general purpose lexicon SentiSense [9]. We next use the domain speci c sub-lexicons to classify tweets according to their reputational polarity, following the emotional concept-based system for sentiment analysis presented in [8]. We corroborated that using entity-level training data improves the ltering step. Additionally, the proposed approaches to detect topics obtained the highest scores in the o cial evaluation, showing that they are promising directions to address the problem. In the reputational polarity task, our results suggest that a deeper analysis should be done in order to correctly identify the main di erences between the Reputational Polarity task and traditional Sentiment Analysis tasks. A nal remark is that the overall performance of a monitoring system in RepLab 2013 highly depends on the performance of the initial ltering step.
This paper describes the UNED Online Reputation Monitoring Team participation in RepLab 2013, which is focused on organizing and classifying tweet streams associated with an entity of interest, in order to facilitate to the analysts the labor of monitoring the reputation of an entity in Twitter. We have participated in four of the ve subtasks proposed in the evaluation campaign: ltering unrelated tweets, classifying tweets according to its reputational polarity, detecting topics discussed in tweets and the full monitoring task.
The RepLab 2013 collection consists of 61 entities from four di erent domains: automotive, banking, university and music. Each of the entities has an associated set of around 750 manually annotated tweets for training and 1,500 tweets for testing. Tweets are written in English and Spanish, following the same (unbalanced) language distribution as in Twitter. Crawling was performed during the period from the 1st June 2012 till the 31st Dec 2012 using the entitys canonical name as query (e.g. "BMW"), and training/test datasets correspond to di erent time ranges. The corpus also comprises additional background tweets for each entity (up to 50,000, with a large variability across entities).
We have applied a range of di erent approaches to each of the tasks, plus a
horizontal approach for all of them. The ltering task has been tackled with
keyword recognition based techniques learned from each entity. Polarity has been
addressed with semantic graphs for domain-speci c a ective lexicon adaptation.
In the case of topic detection, a revisited version of our three algorithms
presented in RepLab 2012 [
The paper is organized as follows. We describe the approaches and the results for the RepLab 2013 subtasks: ltering in Section 2, polarity in Section 3 and topic detection in Section 4. Then, we analyze the results for the full monitoring task in Section 5. We conclude in Section 6. 2
The ltering task in RepLab 2013 is oriented to disambiguate tweets in order to discard those that do not refer to the company (i.e., related vs. unrelated). Here we describe the two di erent approaches we have tested to tackle this problem: instance-based learning over heterogeneity based ranking and lter keywords. 2.1
The instance-based learning approach that we have tested is similar to the o cial
RepLab 2013 baseline, where each tweet inherits the (manually annotated) tags
from the most similar tweet in the training corpus of the same entity. The
difference is that, instead of using Jaccard distance to compute tweet similarity as
the baseline does, we have employed and combined multiple similarity measures.
Our measures expand the tweets with di erent sources, and then apply cosine
similarity. We have used the following sources to expand tweets: (i) the hashtags
in the tweets, (ii) the content of the URLs linked in the tweets, (iii) the rest
of tweets published by the same author and (iv) several parts of the wikipedia
entries associated with words in the tweet (e.g. title, wikipedia category, etc).
As one word can be associated with multiple Wikipedia entries, we have used
commonness probability [
In order to combine all similarity measures, we have employed an
unsupervised method called Heterogeneity Based Ranking (HBR) [
The lter keywords strategy has proved to be a competitive approach to company
name disambiguation in Twitter [
Here we explain the automatic classi cation approach, similar to [
Three families of features are de ned:
{ Collection-based features: This features are de ned to capture di erences
between keywords and skip terms. In this approach, we added two additional
speci city-based features, pseudo-document TF.IDF and KLD [
{ Web-based features: This features should discriminate between positive
and negative lter keywords. These features are: term frequency on the
representative pages (homepage and the English and Spanish Wikipedia pages),
as well as term occurrence in relevant search results in Wikipedia and in
ODP.
{ Features expanded by co-occurrence: We applied the co-occurrence
expansion described in [
Finally, the labeled instances described above are used to feed a positive-negativeskip classi er. We combine two classi ers: positive versus others and negative versus others, using the con dence thresholds learned by the classi ers (i.e., those used by default to decide the nal label of each instance). Terms which are simultaneously under/over both thresholds are tagged as skip terms. Tweet Classi cation. After classifying the terms, tweets containing at least one of those terms labeled as positive (negative) keywords are straightforwardly classi ed as related (unrelated), respectively As classi ed keywords are unlikely to cover all the tweets, we use a standard bootstrapping method to annotate the uncovered tweets. Tweets are represented as Bag-of-Words (produced after tokenization, lowercase and stop word removal) and term occurrence is used as weighting function; nally, a supervised machine learning algorithm is used to classify the tweets.
The tweet classi cation process has been carried out at the entity level, that is, for each entity we use the tweets retrieved by the keywords as seed, only using the training set of the entity, in order to classify automatically the remaining tweets of the entity. 2.3
Table 1 provides an overview of the ltering runs, showing the type of training
data used in each of them. Run UNED ORM filtering 1 is the instance-based
learning over HBR, that works at the entity level as described in 2.1. Runs
UNED_ORM_filtering_3, UNED_ORM_filtering_4 and UNED_ORM_filtering_5
follow the lter keyword approach described in Section 2.2, considering di
erent training data to build the model used in the keyword classi cation step:
UNED_ORM_filtering_3 joins all the terms from the di erent entities in the
training dataset to build a single model, while UNED_ORM_filtering_4 and
UNED_ORM_filtering_5 build a speci c model at the entity level. The di
erence between them is that, while UNED_ORM_filtering_5 only considers
entityspeci c data, UNED_ORM_filtering_4 uses exactly the complementary. The
latter run simulates the semi-supervised scenario in which the system does not use
any previously annotated data about the target entity (like in previous
evaluation campaigns [
In all the lter keywords' runs (from 2 to 5), tweets are tokenized using
a Twitter-speci c tokenizer [
Table 2 reports the scores obtained for the evaluation metrics used in the ltering subtask: Accuracy, Reliability (R), Sensitivity (S) and F1(R; S). For each of the runs, the position on the o cial F1(R; S) RepLab rank is also shown.
Even if the results obtained in terms of accuracy are competitive, the scores according to Reliability and Sensitivity measures evidence the need for a better understanding of the problem. Comparing the results obtained with the baseline, only the run UNED ORM filtering 2 outperforms it in terms of accuracy and F1(R; S), which proves that there is still room for improvement.
As expected, runs that use previously annotated data from the entity are signi cantly better than semi-supervised approaches. A deeper analysis of the machine learning steps is needed to understand the actual limitations of the lter keywords approach. UNED ORM filtering 2 0.8587 baseline 0.8714 UNED ORM filtering 1 0.8733 UNED ORM filtering 5 0.8423 UNED ORM filtering 4 0.5020 UNED ORM filtering 3 0.5026 3
Polarity Subtask Most of the approaches that aim to detect polarity in texts make use of a ective lexicons in order to identify opinions, sentiments or emotions. The main drawback of a ective lexicons' development is the manual e ort needed to generate good quality resources. Besides, these resources should be designed for a general purpose, not taking into account the peculiarities of a speci c domain. The RepLab 2013 dataset is a perfect evaluation framework to study and analyze automatic methods for domain adaptation of a ective lexicons.
Sentiment Analysis (SA) and Reputational Polarity (RP) are close but di erent tasks. While the rst is mainly focused on identifying subjective content in product/services reviews, the second one aims to measure if a text has positive or negative implications for a company's reputation. This de nition includes the well known, but less studied in SA, polar facts. Statements such as \Report: HSBC allowed money laundering that likely funded terror, drugs, ..." are clearly negative when analyzing the reputation of HSBC company, even though no opinion is expressed. The e ect of polar facts can be reasonable biased using a domain-speci c a ective lexicon. In the example, a system using a lexicon that attaches to the words money laundering, terror or drugs a negative polarity or emotion will correctly classify this fact.
Within this premise our aim in this approach is to evaluate if the use of
semantic graphs and word sense disambiguation [
The method proposed for domain adaption of a ective lexicons consists of
three steps:
{ Concept Identi cation. In order to determine the appropriate sense of
each word in WordNet we use the UKB algorithm [
Also, a list of stop words has been used to remove non-relevant words.
{ Graph generation. We have analyzed di erent relations between concepts
as studied in [
weight(Ci; Ej) = 1=(depth(hyperi) + 1) (1) { Propagating emotions to new concepts. Finally, in this step the semantic graph is used to extend the emotional categories to new concepts not labeled in SentiSense. To this end, a concept Ci not previously labeled in SentiSense is labeled as follows:
For all the incoming links that represent relations of co-occurrence, hypernymy and derived from, and that connect Ci with concepts of a same emotional category, the weights of all links are added. For the antonymy relations, the emotional categories are replaced by their antonyms, as given in the SentiSense lexicon. As a result, for the concept Ci we get a vector of 14 positions, each representing a SentiSense emotion, where the vector positions represent the weight of each emotion in the concept. It is important to note that these weights are domain-speci c, since are derived from the domain semantic graph.
The concept is nally labeled with multiple emotional categories, which weights are normalized at the concept level, so that the sum of the weights of all the emotional categories associated to the concept is 1:0.
Figure 1 shows an example of an expanded concept.
We have tested di erent approximations to generate the domain-speci c semantic graphs using the training set of RepLab 2013. Our rst approximation used all entities of the same domain to generate the graph and to adapt the a ective lexicon of SentiSense. We evaluated di erent approaches: using just related tweets of the training set, using all tweets of the test set, and using both related tweets of the training set and all tweets of the test set. We have also tested generating graphs at the entity level, that is to say, generating a graph for each entity. 3.2
The resulting domain-speci c a ective lexicons are used to identify emotions in
the tweets of RepLab 2013 dataset using the emotional concept-based system
for sentiment analysis presented in [
For each concept, Ci, labeled with an emotional category, Ej, the weight of the concept for that emotional category, weight(Ci; Ej), is set to 1.0. If no emotional category was found for the concept, and it was assigned the category of its rst labeled hypernym, hyperi, then the weight of the concept is computed as: weight(Ci; Ej ) = 1=(depth(hyperi) + 1) (2) If the concept is a ected by a negation and the antonym emotional category, Eantonj , was used to label the concept, then the weight of the concept is multiplied by = 0:6. This value has been empirically determined in previous studies. It is worth mentioning that the experiments have shown that values below 0.5 decrease performance sharply, while it drops gradually for values above 0.6.
If the concept is a ected by an intensi er, then the weight of the concept is increased/decreased by the intensi er percentage, as shown in Equation 3. weight(Ci; Ej ) = weight(Ci; Ej ) (100 + intensif ier percentage)=100 (3) Finally, the position in the VEI of the emotional category assigned to the concept is incremented by the weight previously calculated. 3.3
The polarity detection task in RepLab 2013 consists of classifying tweets as positive, negative or neutral. It is important to notice that the polarity is oriented to reputation. That is, an emotionally negative tweet is not necessarily negative from the reputation point of view (i.e. \I'm sad. Michael Jackson is dead"). Note that tweets that are unrelated according to human assessors are not considered in the evaluation.
For the individual evaluation of the reputational polarity task, performance
is evaluated in terms of accuracy (% of correctly annotated cases) over related
tweets. Reliability (R) and sensitivity (S) are also included for comparison
purposes [
As the system for reputational polarity is a supervised method, we have
tested di erent machine learning algorithms in order to determine the best
classi er for the task. In our experiments the logistic regression model (Logistic) as
implemented in Weka with default parameters has obtained the best results. As
previously mentioned we tested di erent approaches for generating the
domainspeci c semantic graph, however we only could submit the runs using the graph
generated using related tweets of the training set and at the domain level. So,
the runs submitted are:
{ UNED ORM polarity 1: This run uses the approach described in section 2.1,
which is similar to the baseline but using di erent text similarity measures
and the Heterogeneity Based Ranking approach to combine them.
{ UNED ORM polarity 2: This run uses the system presented in [
As shown in Table 3.3, the best performing con guration (UNED_ORM_polarity_
2) is that which has been trained at the entity level and that uses the original
SentiSense lexicon (without expanding it using semantic graphs). However, the
di erence with the (UNED_ORM_polarity_4) system is not signi cant. Both
approaches perform better than the baseline in terms of accuracy, while their
performance drops when evaluating with reliability and sensitivity measures. Even
if a similar approach has been tested achieving promising results in [
This subtask consists of grouping entity related tweets according to topics. The
organization does not provide any set of prede ned topics. Given that the
training corpus corresponds with a previous time range, new topics can appear in
the test set. It is assumed that each tweet belong to one topic. In the following
sections we describe the di erent approaches proposed for the topic detection
subtask: LDA-based clustering, tweet wiki ed clustering and term clustering.
Finally, we show the results obtained by the runs submitted.
We use an LDA-based model in order to obtain the topics of a collection of
tweets. It is an unsupervised machine learning technique which uncovers
information about latent topics across the corpora. The model is inspired by the
TwitterLDA model [
For the monitoring scenario there are two important characteristics that are present in TwitterLDA and TOT: tweets are about one single topic and each topic has a time distribution. We use this features in an LDA-based model with the following assumptions: (i) there is a set of topics K in the collection of tweets of an entity, each represented by a word distribution and a continuous distribution over time; and (ii) when a tweet is written, the author rst chooses a topic based on a topic distribution for the entity.
Then a bag of words is chosen one by one based on the topic. However, not all words in a tweet are closely related to the topic of that tweet; some are background words commonly used in tweets on di erent topics. Therefore, for each word in a tweet, the author rst decides whether it is a background word or a topic word and then chooses the word from the respective word distribution of the entity.
The process is described as follows: 1. Draw d Dir( ), B Dir( ), 2. For each topic z = 1; :::; K
(a) draw z Dir( ) 3. For each tweet d = 1; :::; D (a) draw a topic zd M ulti( d) (b) draw a timestamp td Beta( zd ) (c) for each word i = 1; :::; Nd i. draw ydi Bernoulli( ) ii. if ydi = 0 : draw wdi if ydi = 1 : draw wdi
M ulti( B) M ulti( zd )
Dir( ) where: zd denotes the word distribution for topic z; zd is the time distribution for the topic z; B the word distribution for background words and denotes a Bernoulli distribution that governs the choice between background words and topic words. After applying the model, a topic is represented as a vector of probabilities over the space of words and a single topic is assigned for an entire tweet. We employ Gibss sampling to perform approximate inference. The graphical model is shown in Figure 2.
The system also relies on transfer learning by contextualizing the target tweets with a large set of unlabeled \background" tweets that help improving the clustering. We include background tweets together with target tweets in the LDA model, and we set the total number of clusters. In practice, this means that the system can adapt to nd the right number of clusters for the target data, overcoming one of the limitations of using LDA-based approaches (the need of establishing a priori the number of clusters).
We train the LDA-based model simultaneously over all the tweets in the
target set and the background and x the target number of clusters (as required
by LDA) for the whole set. Note that the LDA-model labels each tweet with only
one topic, so we will have a non-overlapping clustering. Once we have obtained
the clustering, we extract all clusters that contain at least one target tweet, and
remove non-target tweets from those clusters.
This approach relies on the hypothesis that tweets sharing concepts or entities
de ned in a knowledge base {such as Wikipedia{ are more likely to be talking
about the same topic than tweets with none or less concepts in common.
Tweet Wiki cation. We use an entity linking approach to gather Wikipedia
entries that are semantically related to a tweet. To this end, the
COMMONNESS probability [
Commonness(c; q) = Pc0 jLq;c0 j where Lq;c denotes the set of all links with anchor text q and target c.
We used both Spanish and English Wikipedia dumps. Spanish Wikipedia articles are then translated to the corresponding English Wikipedia article by following the inter-lingual links, using the Wikimedia API2.
Tweet Clustering. After tweets are wiki ed, the Jaccard similarity between the sets of entities linked to the tweets is used to group them together: given two tweets d1 and d2 represented by the set of Wikipedia entities C1 and C2 respectively, if Jaccard(C1; C2) > th, then d1 and d2 are grouped together to the same cluster. 4.3
Let us assume that each topic related to an entity can be represented with a set of keywords, that allow to the expert to understand what the topic is about. Considering this, we de ne a two-step algorithm that tries to (i) identify the terminology of each topic {by clustering the terms{ and (ii) assigning tweets to the identi ed clusters.
We use Hierarchical Agglomerative Clustering (HAC) to build the term clustering. As similarity function, we use the con dence score returned by a classi er that, given a pair of co-occurrent terms, guesses whether both terms belong to the terminology of the same topic or not. 2 http://www.mediawiki.org/wiki/API:Properties
to represent each of the co-occurring pairs:
{ Term features: Features that describe each of the terms of the co-occurrence
pair. These are: term occurrence, normalized frequency, pseudo-document
TF.IDF and KL-Divergence [
In our classi cation model each instance corresponds to a pair of co-occurrent terms ht; t0i in the entity stream of tweets. In order to learn the model, we extract training instances from the RepLab 2013 training dataset, considering the following labeling function: label (ht; t0i) = clean if maxj Precision(Ct\t0 ; Lj ) > 0:9 noisy in other case where Ct\t0 is the set of tweets where terms t and t0 co-occurs and L is the set of topics in the goldstandard, and
Precision(Ci; Lj ) = jCi \ Lj j jCij
After this process, term pairs with 90% of the tweets belonging to the same cluster in the goldstandard (i.e., purity=0.9) are considered clean pairs. Otherwise, terms with less purity are labeled as noisy pairs.
Hierarchical Agglomerative Term Clustering. Using all the co-occurrence pair instances in the training set, we build a single binary classi er that will be applied to all the entities in the test set. Then, the con dence of a co-occurrence pair belonging to the clean class is used to build a similarity matrix between terms. A Hierarchical Agglomerative Clustering is then applied to cluster the terms, using the previously built similarity matrix. After building the agglomerative clustering, a cut-o threshold based on the number of possible merges is used to return the nal term clustering solution.
Tweet clustering. The second step of this algorithm consists on assigning tweets to the identi ed term clusters. Each tweet is assigned to the cluster with highest Jaccard similarity. 4.4
A total of seven runs have been submitted for the topic detection subtask. Table 4 summarizes the approaches and the parameters used for each of the runs. UNED_ORM_topic_det_1 consist of applying instance-based learning over HBR, analogously as described in Section 2.1. UNED_ORM_topic_det_2 is the wikied tweet clustering approach, using the threshold for the Jaccard similarity of th = 0:2. This threshold has been empirically optimized using the training dataset3. UNED_ORM_topic_det_3,UNED_ORM_topic_det_4 and UNED_ORM_ topic_det_5 use the term clustering approach using di erent machine learning algorithms to combine the features (Nave Bayes and Logistic Regression) and di erent thresholds applied to the HAC. A threshold of 0.30 indicates that the nal clustering considered is the one produced when the 30% of all possible merges are applied. In all the term clustering runs, the merges are carried out by the mean linkage criterion. Again, only terms after stopword removal and with occurrence greater than ve are considered. Finally, UNED_ORM_topic_det_6 and UNED_ORM_topic_det_7 use the LDA-based clustering approach, where the transfer learning step is carried out considering background tweets from the entity with a max. of 10,000 tweets or from other randomly selected entity with 10,000 tweets, respectively. 4.5
Table 5 shows the results obtained by the submitted runs in the topic detection
subtask and compared to the baselines. The table reports scores for the metrics
Reliability (R), Sensitivity (S) and F1-measure of R and S, F1(R; S). It also
reports the position of the runs in the ranking provided by the organizers. As a
clustering task, Reliability (R) corresponds to BCubed Precision and Sensitivity
(S) corresponds to BCubed Recall [
In general, all the approaches are in the top of the rank, performing signi cantly better than the baselines. The wiki ed tweet clustering gets the highest score in all the metrics. Term clustering approach seems to performs similarly when changing the HAC cut-o threshold or the machine learning algorithm. On the other hand, the LDA-based clustering approach performs better when the background collection used for transfer learning contain tweets from di erent
entities/test cases (in this run is ensures to have a collection of 10,000 tweets as background). Finally, as in the other subtasks, combining multiple similarity measures for instance-based learning slightly outperforms the baseline that only consider Jaccard similarity over the terms. 5
The full monitoring task combines the three subtasks that are typically addresses in a monitoring process: rst, the tweets that are not related to the entity of interest are ltered out ( ltering); then, the related tweets are clustered by topics (topic detection) and nally, those topics are ranked by priority (priority). Next we describe the submitted runs for the full monitoring task, as well as the obtained results. For the full monitoring task, we submitted 8 di erent runs in total. The runs combine di erent approaches for each of the three subtasks, considering the subsystem as a pipeline (e.g., topic detection is carried upon the tweets labeled as related after the ltering step). Table 6 shows the di erent combinations submitted. For instance, the run UNED_ORM_full_task_1 consists of applying instance-based learning over HBR for the three subtasks. Run UNED_ORM_full_ task_2 uses the straightforward tweet classi cation ltering system, the wiki ed tweet clustering techniques to detect topics over the related tweets and nally the baseline provided by the organizers for the priority subtask (instance-based learning over Jaccard distance). UNED ORM full task 1 UNED ORM filt 1 UNED ORM topic det 1 UNED ORM priority 1 UNED ORM full task 2 UNED ORM filt 2 UNED ORM topic det 2 baseline UNED ORM full task 3 UNED ORM filt 3 UNED ORM topic det 2 baseline UNED ORM full task 4 UNED ORM filt 2 UNED ORM topic det 3 baseline UNED ORM full task 5 UNED ORM filt 3 UNED ORM topic det 3 baseline UNED ORM full task 6 baseline UNED ORM topic det 6 baseline UNED ORM full task 7 baseline UNED ORM topic det 7 baseline UNED ORM full task 8 UNED ORM filt 3 UNED ORM topic det 2 UNED ORM priority 1 We have described and discussed here the systems submitted by UNED-ORM group to the RepLab 2013 evaluation campaign. We have participated in three of the subtasks ( ltering, topic detection and polarity), as well as in the full monitoring task.
The ltering subtask turned out to be crucial for the overall performance of a monitoring system. An in-depth analysis of the results is needed to understand the limitations of our lter keyword approach - which was initially developed for semi-supervised scenarios, not for a fully supervised scenario as in RepLab 2013.
In the reputational polarity task, an approach to generate semantic graphs for domain-speci c a ective lexicon adaptation has been tested. Even if a similar approach has been previously tested achieving promising performance in a traditional Sentiment Analysis task using news and reviews as input data, our results in the RepLab 2013 seem to be less competitive and deserve further analysis. In particular, more analysis on the di erences between Reputational Polarity and traditional sentiment analysis is needed.
Three of our topic detection approaches (LDA-based clustering, wiki ed tweet clustering and term clustering) perform competitively with respect to other RepLab submissions. Still, the room for improvement is large, and it is not easy to assess how much of the problem can be solved automatically.
Finally, in terms of instance-based learning, the results suggest that extending tweets with associated contents (tags, external links, Wikipedia entries) does not provide useful signals to improve performance, at least in our current setting.
Future work will focus on the analysis of the results and the optimization of the di erent subsystems for the monitoring task.