Ambiguities in company names are omnipresent. This is not accidental, companies deliberately chose ambiguous brand names, as part of their marketing and branding strategy. This procedure leads to new challenges, when it comes to nding information about the company on the Web. This paper is concerned with the task of classifying Twitter messages, whether they are related to a given company: for example, we classify a set of twitter messages containing a keyword apple, whether a message is related to the company Apple Inc. Our technique is essentially an SVM classi er, which uses a simple representation of relevant and irrelevant information in the form of keywords, grouped in speci c \pro les". We developed a simple technique to construct such classi ers for previously unseen companies, where no training set is available, by training the meta-features of the classi er with the help of a general test set. Our techniques show high accuracy gures over the WePS-3 dataset.
Twitter 1 is a popular service where users can share short messages (a.k.a. tweets)
on any subject. Twitter is currently one of the most popular sites of the Web, as
of February 2010, Twitter users send 50 million messages per day 2. As users are
sharing information on what matters to them, analyzing twitter messages can
reveal important social phenomena, indeed there are number of recent works,
for example in [
In this paper, we focus on how to relate tweets to a company, in the context of the WePS-3 challenge, where we are given a set of companies and for each company a set of tweets, which might or might not be related to the company (i.e. the tweets contain the company name, as a keyword). Constructing such a classi er is a challenging task, as tweet messages are very short (maximum 140 characters), thus they contain very little information, and additionally, tweet messages use a speci c language, often with incorrect grammar and speci c abbreviations, which are hard to interpret by a computer. To overcome this problem, we constructed pro les for each company, which contain more rich information. For each company, in fact, we constructed several pro les, some of them automatically, some of them manually. The pro les are essentially sets of keywords, which are related to the company in some way. We also created pro les, which explicitly contains unrelated keywords. Our technique is essentially an SVM classi er, which uses this simple representation of relevant and irrelevant information in the \pro les". We developed a simple technique to construct such classi ers for previously unseen companies, where no training set is available, by training the meta-features of the classi er with the help of a general test set, available in WePS-3. Our techniques show high accuracy gures over the WePS-3 dataset.
The rest of the paper is organized as follows. Section 2 gives a more precise problem de nition. Section 3 presents our techniques, while Section 4 gives more details on the classi cation techniques we used. Section 5 gives details on the experimental evaluation of our methods. Section 6 summarizes related work and nally Section 7 concludes the paper. 2
In this section we formulate the problem and our computational framework more formally. The task is concerned to classify a set of Twitter messages = fT1; : : : ; Tng, whether they are related to a given company C. We assume that each message Ti 2 contains the company name as a sub-string. We say that the message Ti is related to the company C, related(Ti; C), if and only if the Twitter message refers to the company. It can be that a message refers both to the company and also to some other meaning of the company name (or to some other company with the same name), but whenever the message Ti refers to company C we try to classify as TRUE otherwise as FALSE. The task has some other inputs, such as the URL of the company url(C), the language of the webpage, as well as the correct classi cation for a small number of messages (for some of the companies). 3
The tweet messages and company names alone contain very little information to realize the classi cation task with good accuracy. To overcome this problem, we created pro les for the companies, several pro les for each company. These set of pro les can be seen as a model for the company. In this section, we discuss how we represent tweet messages and companies and we also discuss how we obtained these pro les. In the the classi cation task we eventually compare a tweet against the pro les representing the company (see Section 4). 3.1
We represented a tweet as a bag of words (unigrams and bigrams). We do not access the tweet messages directly in our classi cation algorithm, but apply a preprocessing step rst, which removes all the stop-words, emoticons, and twitter speci c stop-words (such as, for example, RT,@username). We store a stemmed3 version of keywords (unigrams and bigrams), i.e.
Ti = setfwrdj g. 3.2
We represent each company as a collection of pro les, formally
Ek = fP1k; P2k; : : : ; Pnkg.
Each pro le is a set of weighted keywords i.e. Pik = fwrdj : wtj g, with wtj 0 for positive evidence and wtj < 0 for negative evidence.
For the tweets classi cation task, we eventually compare the tweet with the entity (i.e. company) pro le. For better classi cation results, the entity pro le should have a good overlap with the tweets. Unfortunately, we do not know the tweet messages in advance, so we tried to create such pro les from alternative sources, independently of the tweet messages. The entity pro le should not be too general, because it would result many false positives in the classi cation and also not too narrow, because then we could miss potential relevant tweets.
We generated most of our pro les automatically, i.e. if one would like to construct a classi er for a previously unseen company, one can automatically generate the pro les. Further, small, manually constructed pro les could further improve the accuracy of the classi cation, as we explain in Section 5.
In the following we give an overview of the pro les we used, and their construction.
Homepage Pro le For each company name, the company homepage URL was provided in the WePS-3 data. To construct the homepage pro le, we crawled all the relevant links up to a depth of level d(=2), starting from the given homepage URL. We extracted all the keywords present on the relevant pages, then we removed all the stopwords, nally we stored in the pro le the stemmed version of these keywords. From this construction process one would expect that homepage-pro le should capture all the important keywords related to the company. However, since the construction is 3 Porter stemmer from python based natural language toolkit available at http://www.nltk.org an automated process, it was not always possible to capture good quality representation of the company, for various reasons: the company Webpages use java-scripts, ash, some company pages contain irrelevant links, there are non-standard homepages etc.
Metadata Pro le HTML standards provides few meta tags4, which enables a webpage to list set of keywords that one could associate with the webpage. We collect all such meta keywords in this pro le whenever they are present. If these meta-keywords are present in the HTML code, they have high quality, the meta-keywords are highly relevant for the company. On the negative side, only a fraction of webpages have this information available. Category Pro le The category, to which the company belongs, is a good source of relevant information of the company entity. The general terms associated with the category would be a rich representation of the entity. One usually fails to nd this kind of keywords in the homepage pro le. We make use of wordnet, a network of words, to nd all the terms linked to the category keywords. This kind of pro le helps us assign keywords like: software,install, update, virus, version, hardware, program, bugs etc to a software company.
taining \common knowledge" about the company. We make use of GoogleSets5 to get words closely related to the company name. This helps us identify companies similar to the company under consideration, we get to know the products, competitor names etc. This kind of information is very useful, especially for twitter streams, as many tweets compare companies with others. With this kind of pro le, we could for example associate Mozilla, Firefox, Internet Explorer, Safari keywords to Opera Browser entity.
UserFeedback Positive Pro le The user himself enters the keywords which he feels are relevant to the company, that we store in the manually constructed UserFeedback pro le. In case of companies where sample ground truth is available, we can infer the keywords from the tweets (in the training set) belonging to the company.
UserFeedback Negative Pro le The knowledge of the common entities with which the current company entity could be confused, would be a rich source of information, using which one could classify tweets e ciently. The common knowledge that \apple" keyword related to \Apple Inc" company could be interpreted possibly as the fruit, or the New York city etc. This particular pro le helps us to collect all the keywords associated with other entities with similar keyword. An automated way of collecting this information would be very helpful, but it is di cult. For now we make use of few sources as an initial step to collect this information. The user himself provides us with this information. Second, the wiki disambiguation pages6 contains this information, at least for some entities. Finally this information could be 4 http : ==www:w3schools:com=html=html meta:asp 5 http://labs.google.com/sets 6 http://en.wikipedia.org/wiki/Apple (disambiguation) page contains apple entities gathered in a dynamic way i.e., using the keywords in all the tweets, that do not belong to the company. This information could also be obtained if we have training set for a particular company with tweets that do not belong to the company entity. WebPage iphone, ipod, mac, safari, ios, iphoto, iwork, leopard, forum, items, employees, itunes, credit, portable, secure, unix, auditing, forums, marketers, browse, dominicana, music, recommend, preview, type, tell, notif, phone, purchase, manuals, updates, fa, 8GB, 16GB, 32GB,: : : HTML Metatag femptyg
Category opera, code, brainchild, movie, telecom, cruncher, trade, cathode-ray, paper, freight, keyboard, dbm, merchandise, disk, language, microprocessor, move, web, monitor, diskett, show, gure, instrument, board, lade, digit, good, shipment, food, cpu, moving-picture, uid, consign, contraband, electronic, volume, peripherals, crt, resolve, yield, server, micro, magazine, dreck, byproduct, spiritualist, telecommunications, manage, commodity, ick, vehicle, set, creation, procedure, consequence, second, design, result, mobile, home, processor, spin-o , wander, analog, transmission, cargo, expert, record, database, tube, payload, state, estimate, intersect, internet, print, factory, contrast, outcome, machine, deliver, e ect, job, output, release, turnout, convert, river,: : : GoogleSet itunes, intel, belkin, 512mb, sony, hp, canon, powerpc, mac, apple, iphone, ati, microsoft, ibm,: : : User Positive ipad, imac, iphone, ipod, itouch, itv, iad, itunes, keynote, safari, leopard, tiger, iwork, android, droid, phone, app, appstore, mac, macintosh User Negative fruit, tree, eat, bite, juice, pineapple, strawberry, drink 4
In machine learning literature, the learning tasks could be broadly classi ed as supervised and unsupervised learning. The problem scenario for the WePS-3 task, classi cation of tweets with respect to a company entity can be seen as a problem where one needs a machine learning technique between supervised and unsupervised learning, since we have no training set for the actual classi cation task, but a test training set is provided for a separate set of companies. Here we brie y discuss the di erent classes of machine learning techniques, and outline our classi cation method. 7 http://www.apple.com
chine learning technique for deducing a function from training data. The training data consist of pairs of input objects (typically vectors), and desired outputs. The output of the function can predict a class label of the input object (called classi cation). The task of the supervised learner is to predict the value of the function for any valid input object after having seen a number of training examples (i.e. pairs of input and target output). To achieve this, the learner has to generalize from the presented data to unseen situations in a "reasonable" way. An example of supervised learning in our current setting is: given a training set of tweets for a particular company(XYZ company), with example of tweets belonging to and not belonging to the company, one learns a classi er for this particular company(XYZ company). Using this classi er the new unseen tweets related to this company(XYZ company) can be classi ed as belonging or not belonging to that company.
Unsupervised Learning In machine learning, unsupervised learning is a class of problems in which one seeks to determine how the data are organized. Many methods employed here are based on data mining methods used to preprocess data. It is distinguished from supervised learning in that the learner is given only unlabeled examples. In broad sense, the task of classifying tweets of an unknown company, without seeing any relevant examples can fall into this category. Generic Learning For the current scenario (WePS-3 - challenge 2), we are provided with training sets corresponding to few companies (CT R). Finally we have to classify test sets corresponding to new companies(CT est), with CT R T CT est = 0. This particular scenario can be seen as in-between supervised and unsupervised learning. It is unsupervised as we are not given any labeled tweets corresponding to the test set. At the same time it is also related to supervised learning as we have access to few training sets, with labeled tweets corresponding to the companies. This kind of generic learning needs the classi er to identify the generic features from the general training set, based on which one can make accurate classi cation of tweets corresponding to the unseen companies. The classi ers based on the features of the tweet decides if it belongs to a company or not. In the following section 4.1, we discuss the features which our classi ers take as input. After the features are introduced, we propose di erent ways of developing a generic classi er in section 4.2 4.1
We de ne a feature extraction function, which compares a tweet Ti to the company entity representation Ek and outputs a vector of features. Here the Gi are generic/meta features, which are entirely based on the quality of the entity pro les and do not depend on Tweet message Ti. One could use di erent ways of quantifying the quality of the pro les.
{ Boolean: In this work we make use of boolean metrics to represent if a pro le
is empty or has su cient keywords.
{ Other possibility is that a human can inspect the pro les and assign a metric
of x 2 [
The Fi features are tweet speci c features, i.e. they quantify how close a tweet overlaps with the entity pro les. We use a comparison function to compare the tweet message Ti, which is a bag of words, with jth pro le Pjk, which is also a bag of weighted keywords, to get the F th feature. In this work we make use j of a simple comparison function, which compares two bags of words looking for exact overlap of keywords, and for all such keywords the sum of their weights quantify how close the tweet message is to the entity pro le. Formally with Ti = Setfw1t; w2t; : : : ; wktg and Pjk = Setfw1p : wt1; w2p : wt2; : : : ; wmp : wtmg, we compute the Fj feature using the simple comparison function as: Fj = CmpF n(Ti; Pjk) =
X wtq, where q such that
q wqp 2 Setfw1t; w2t; : : : ; wktg \ Setfw1p; w2p; : : : ; wmpg (1) The above comparison function is simple and easy to realize, but it may miss out some semantically equivalent words. One could make use of cosine similarity, or semantic similarity based comparison functions.
The Ui features encapsulate some user based rules, for example, presence of the company URL domain in the tweet URL list, is a big enough evidence to classify the tweet as belonging to the company. 4.2
The classi er is a function which takes the feature vector as input and classi es the tweet as fT RU E; F ALSEg, with TRUE label if the tweet is related to the company and as FALSE otherwise. We are provided with training data corresponding to a set of companies (CT R). Based on the training data we have the task of training a generic classi er, which should be used to classify the tweets corresponding to a new set of companies (CT est). We present here two possible ways of designing this generic classi er.
Ensemble of Naive Bayes Classi ers: We adapt the Naive Bayes Classi er model for this task. For each company in the training set(CT R), based on the company tweets we nd the conditional distribution of values over features for two classes i.e. a class of tweets which are related to the company and another class of tweets which are not related to the company. With these conditional probabilities, shown in equations(2,3) and by applying Bayes theorem, we can classify an unseen tweet whether it is related to the company or not.
Let us denote the probability distribution of features of the tweets that are related to a given company with
P (f1; f2; : : : ; fn j C);
P (f1; f2; : : : ; fn j C): and the probability distribution of features of the tweets that are not related to the company with
Then, for an unseen tweet t, using the features extraction function we compute the features values:(f1; f2; : : : ; fn). The posterior probabilities of whether the tweet is related to the company or not, are calculated as in equations (4, 5). (2) (3) (4) (5) P (C j t) = P (C j t) =
P (C) P (t j C)
P (t) P (C) P (t j C)
P (t) = =
P (C) P (f1; f2; : : : ; fn j C)
P (f1; f2; : : : ; fn) P (C) P (f1; f2; : : : ; fn j C)
P (f1; f2; : : : ; fn)
Depending on whether P (C j t) is greater than P (C j t) or not, the naive Bayes classi er decides whether the tweet t is related to the given company or not, respectively.
Corresponding to each company ci 2 CT R, we train a naive Bayes
classi er[
The generic classi er makes use of ensemble function which either chooses
the best classi er or combines the decision of classi ers from this set, to classify
an unseen tweet corresponding to a new company i.e. ci 2 CT est. The ensemble
function would make use of the meta-features and accuracy measures to pick up
the right classi er or the right combination of classi ers. We refer to [
SVM Classi er: Alternatively one could train a single classi er based on all
the features: meta-features, tweet-speci c features and heuristics-features. This
single classi er can be seen as using an ensemble function implicitly in either
picking an apt classi er or aptly combing the classi er decisions. In the current
work, we train an SVM Classi er [
Our experimental setup was the following. We are given a general training set, which consists tweets related to about 50 companies (we denote this set as CT R). For each company c 2 CT R we are provided around 400 tweets with their corresponding ground truth, i.e. if the tweet is related to the company or not. For each company, we are provided with the following meta-information: URL, Language, Category. We have trained a generic classi er based on this training set. The test set for this task consisted tweets of around 50 new companies. We denote this set of companies as CT est. There was no overlap with the training set, CT R T CT est = 0. For each company c 2 CT est there are about 400 Tweets, which are to be classi ed. We classi ed them with our trained generic classi er, as explained in Section 4. The WePS-3 dataset is available at http://nlp.uned.es/weps/weps-3/data.
The task is of classifying the tweets into two classes: one class which represents the tweets related to the company (positive class) and second class represents tweets that are not related to the company (negative class). For evaluation of the task, the tweets can be grouped into four categories: true positives (T P ), true negatives (T N ), false positives (F P ) and false negatives (F N ). The true positives are the tweets that belong to positive class and in fact belong to the company and the other tweets which are wrongly put in this class are false positives. Similarly for the negative class we have true negatives which are correctly put into this class and the wrong ones of this class are false negatives.
We use the following metrics to study the performance of our classi cation process.
The results show high accuracy gures for our classi er. The precision and recall values corresponding to positive class can be further increased by re ning the pro les corresponding to positive evidence, for example by using more sources to accumulate more relevant keywords and by using e cient quality metrics for rejecting irrelevant keywords. In spite of using very few sources for populating the negative pro le of a company, we are still able to have high precision and decent recall values for the negative class. Similarly, by using more sources for negative evidences we can further improve these performance measures.
Next we study the impact of the di erent pro les, we have used in the entity representation, on the classi cation task. We study the importance of the negative-keywords-pro le and the category-based pro le on the performance of the classi cation process. We considered the following cases: LSIR.EPFL 1 (ALL) We make use of all the pro les of a company for the classi cation process.
LSIR.EPFL 2 (No-Neg) We make use of all the pro les except the negativeevidence pro le, of a company to classify unseen tweets.
LSIR.EPFL 3 (No-Cat) To study the impact of using the category-related pro le in the classi cation process, we make an experiment which uses all the pro les of a company except the pro le corresponding to category and common-sense-keywords pro le.
LSIR.EPFL 4 (Only-HP) Company homepage URL is provided as a representation of the entity. We want to study how accurate the classi er performs when a pro le is built only based on the keywords, extracted through crawling the homepage.
From the results shown in table 3, it is clear that the homepage URL does provide us some very relevant information for the classi cation task, however the accuracy is low. The accuracy can be improved if one uses also other sources of information, like negative evidence, category and common sense based keywords. 6
The classi cation of tweets has already been addressed in the literature, in
different contexts. Some of the relevant works include [
In [
The authors in [
In [
The paper [
Many works based on entity identi cation and extraction, for example in [
Bishop [
There are many ways to represent entities. In Okkam[
Twitter is a real time pulse of the opinions of the people. Researchers have analyzed the twitter streams for di erent purposes: nding in uential tweeters, opinion mining, categorizing tweets, summarizing tweets, etc. In some of these tasks, like opinion and sentiment mining, the classi cation of the twitters based on entities forms an important preprocessing step, as the accuracy of further analysis depends on this step. In this paper we address the task of classifying tweets based on entities, for which we use a simple entity representation. We realized an e cient classi cation process with the help of entity pro les, which we constructed using di erent information sources.
One can observe that the accuracy of our classi cation technique depends
on the quality of the entity pro les. As future work, we would like to explore
other techniques to further improve the quality of the entity pro les, including
ensemble techniques[