Social Media Research Blog

The Cost of Manual Annotation

For many machine learning tasks it can be quite difficult to get the "ground truth" data. In some cases the best way to verify the results is by a painful, laborious and mindnumbing task of labeling data manually. When Pranam and I were working on the Splog detection task, we spent a good deal of time painstakingly labeling independently if a blog from a random sample was legitimate or spam. The part that makes this task difficult is:

• Sometimes it is not clear when something is a blog is a splog
• You need to also look at the inlinks and outlinks
• Plagiarized content makes it harder to judge authenticity
• Sploggers are getting more sophisticated in the methods they are using

On an average we spent about 2-3 minutes per blog and in the end, were only able to hand label a small collection. In comparison to many other tasks this was still a relatively straightforward judgment. Consider the task of relevance ranking that NIST has to perform each year for the TREC tracks. Here the goal is for the annotators to figure out if a result is relevant for a query. The guidelines are strict and NIST has many professional annotators who are trained to perform these tasks. Even more complicated are some of the annotation that might be required in certain Natural Language Processing experiments. These can range anywhere from just verifying a parse tree or an output to actually constructing gold standards or hand crafted parse trees. Moreover, some NLP tools require tremendous amounts of linguistic resources -- be it tediously constructing an ontology, lexicon, gazetteer lists or identifying word senses. Many of these tasks require linguists or experts whose time might be quite valuable.

lets consider a simple case where the annotator was asked to label a URL with a tag. Lets also say that it takes roughly a minute to load the page, quickly glance over it, make a judgment and then type in the appropriate labels. I know from experience that this is not a minute but more like 1.5-2 minutes on an average (try it! it is a braindead boring task and if you are asked to do it continuously, you will slow down!). If say I can work 10 hours on this task without loss in quality of my annotations, it would only result in 600 URLs being tagged. UMBC pays lets say around $10/hour for on-campus jobs. That means we would spend about $100 just to label 600 URLs. Not so sure if that would be the best way I would like to spend a hundred bucks! Additionally, just one human annotator is never sufficient. You always need to answer questions like : "So, what was your inter-annotator agreement?". Well then you just blew another $200 or $300 on this task and still have just 600 URLs marked up. No wonder del.icio.us and Flickr are such amazing sources for free (yaay!), human assessed labels and annotations. It works out great if you can use these instead.

Mechanical Turk is an attempt by Amazon to make it easy for such tasks to be distributed to people who would perform them in return for small micropayments. However, it seems to me that the incentive for completing the task (or doing it well) is so minimal that there is very little enthusiasm around this product. I suspect, the only people completing these HITS are individuals in countries where the dollar still has some value. In fact, there seems to be something fishy about atleast a handful of HITS that are high paying. It looks like the system is totally getting gamed by spammers - look at this example requesting 20 backlinks to a site ($3) or creating bogus accounts ($7) and likes.

The most interesting tool for manual annotation that I have ever seen is the ESP game. It is an excellent entertaining and I must warn you totally addictive. The game works by showing you an image and asking you to label it. You are randomly paired with another player and both get a score if a word matches. This totally ingenious way of collecting annotations for images means that the annotations come absolutely free of cost!

To bring the cost of manual annotation to zero or close to it the best incentive is to provide some value to the annotator. Ofcourse some tasks are so specific or specialized that this might be truly difficult without actually paying someone to go through it. 

From a research perspective, when we build a classifier and use the UCI dataset we have a good "gold standard" and accessible body of literature that has studied the very same data. But as we are dealing with ever increasing size of datasets, access to ground truth or manually verified samples is becoming even more challenging. So is the significance of using it. What does it really mean to annotate less than 0.1% of the data (say you have a very large collection of blogs, images, graph -- whatever social media content you can imagine)?

[Image Courtesy http://www.socialfiction.org/]

Notes from DEBSM Workshop: Inferring Privacy Information via Social Relations

Inferring Privacy Information via Social Relations
Wanhong Xu, Xi Zhou Lei Li (presenter)

The presentation started with a neat quote: "Your social activities tell who you are". Social Networking are part of everyday life and for many of us a primary way in which we keep in touch with friends and family. Privacy is a huge problem in such networks. Li provided some statistics from a recent survey of British social network users: about  62 percent are concerned about the security of their personal data. 31% of the users falsify information to protect identity. This is a huge figure and definitely shows the level of concern.

This paper was motivated with applications for social advertising (which is a 2.2B US market). One can target users based on location, age gender etc. and social advertising allows advertisers to choose their audience. The problem comes up where users do not wish to disclose too much of their information online. The proposed solution is to automatically infer such missing information.

The authors use an undisclosed dataset for this study. The assumption is users fake personal information but not their activities. It is well known in offline-social networks that gender preference exist in friendship. however in online social networks this is not true (Jure Leskovec, WWW,2008). The key question that authors of this paper ask is : "Users may fake their personal information...But what about social activities?"

The insight that this paper offers is that certain group membership gives hints of user gender information. Joining groups has a gender preference. So the way in which one can infer the gender is to use a bipartite graph of users->groups with missing gender information using relation between users and groups. One approach is to use the User*Group matrix and build a classifier. However, they found that Naive Bayes does not work very well. Many social groups in fact dont have any gender preference. This can really hurt the classifier accuracy. So one approach they propose is to choose the discriminating social groups. i.e. groups that dominated by males or females. One major disadvantage that this technique suffers from is that the membership for users that dont join any of these groups can not be predicted. Once you restrict to the set of discriminating groups, now Naive Bayes performs well.

For users that cant be predicted they propose the use of an iterative algorithm to combine discriminative social groups and results from Naive Bayes classifier. Testing is performed by removing or making some data missing and then predicting the missing gender information.

My concern here is that the authors might have been able to avoid this disadvantage if they had used SVD to map the Groups to a set of lower dimensions that way it would automatically "cluster" the groups based on whatever the discriminating factor is (in their case the gender information). Secondly, while the authors had access to "verifiable" ground truth data, in real world how do we know the influence of fake profiles on these discriminative groups?

Clustering Tags and Links Simultaneously

I have a large collection of blogs that I would like to cluster. For the blogs in my collection, I have the following information:

• Text aggregated across all the posts
• A dump of the homepage of the blog
• Tags obtained from del.icio.us or "Feeds that matter"
• And finally how the blogs link to each other (aggregated across all the posts)

If we want to cluster the blogs, one can take the following approaches:

1. Cluster the blogs using only the text (Kmeans style)
2. Cluster the blogs using only the link information (By say performing NCut)
3. First cluster all the tags (so you would group "tech", "technology", "geek" etc) and then group the blogs that are categorized in each of these clusters.
4. Using a bipartite graph of the form <Blog,tag>. This is also known as co-clustering.

The problem with using the text alone is that the data can be huge (typically in Gigs) and it is almost essential to use some dimensionality reduction techniques like PCA etc. By performing NCut over the graph alone, you land up ignoring the text or the tag information that could be quite helpful. By clustering in only the tag space and then mapping the resulting clusters to the blog graph, we miss how the blogs might be interconnected. Finally, co-clustering technique too misses the fact that the blogs might link to each other and this information can be quite useful in grouping them together.

The question I was wondering about was how to cluster the blogs while using both the link and the tag information simultaneously. I think that the tags provide a reduce dimensional representation of the text. The tag space is of a much lower dimension than the complete text of the collection and it can be efficient to cluster the blogs using tags than the complete text.

Recently, I came across a very interesting piece of work that talked about "Classification Constrained Dimensionality Reduction". The idea here is that if we have a bunch of data points for which we know the true class information, we would like to classify the remaining points such that the available class information is utilized to guide the dimensionality reduction.

The above paper applied very well to our problem. One simple way to combine the two different information is to use the matrix W' shown here. C is a k*n matrix where n is the number of blogs and k is the number of tags. While W is the adjacency matrix of size n*n. I is an identity matrix of size k*k. Typically, we can get away by using only the top 200-500 most popular tags. Now, if we perform NCut using the matrix W' instead of using W alone, we can combine/fold-in the tag information with the link information. The parameter \beta controls how much importance we would like to give to the graph versus the tag information.

For example for a blog graph consisting of ~3000 blogs, I fetched the tags from del.icio.us and the link graph from the WWE/Buzzmetrics collection. Figure on the right shows 20 clusters if we use just the link information and perform NCut and the same graph using the simultaneous clustering method. Notice, how the 20 odd clusters seem nicely block diagonalized in comparison with the results using link information alone. It would be interesting to look at how these techniques compare with that using the entire text from all the blogs. I am working on this and the intuition is: we might be able to show that using just tag and link information, we can do as good (or better) than using the entire text. Afterall tags are nothing but a place holder for the "topic" of the blog.

An even more interesting extension would be to use the original paper that presented the constrained classification using dimensionality reduction and apply the same technique to our problem, such that we can perform clustering using just a small set of labeled blog and labels (matrix C).

Notes from DEBSM Workshop: Using SentiWordNet for Multilingual Sentiment Analysis

Using SentiWordNet for Multilingual Sentiment Analysis
Kerstin Denecke

Subjectivity Analysis is about identifying a set of opinions emotions and thoughts that are expressed in text. As opposed to factual statements (objective text), the goal is to identify if there are any:

• sentiment or emotions expressed in a piece of text
• type of subjectivity can be either positive/negative opinions

The question addressed in this paper is how to analyze subjectivity and sentiments in in multilingual datasets. This was a really well motivated paper and a it was great to hear this talk especially after attending the recent tutorial by Dr. Jan Weibe at ICWSM. One motivation is that a company that sells products in many different countries might want to know the sentiments of its clients. A big difficulty in aggregating across different geographies is analyzing multilingual text.

Some of the difficulties in dealing with multilingual sentiment analysis are:

• missing language specific lexical resources
• missing linguistic resources (POS Tagger, Parser)
• missing training materials

The solution proposed by Kerstin in this paper is to rely on resources available in English and use existing training sets (from English text) to identify the subjectivity in foreign language text. This is such a simple and effective idea that my first reaction was that of surprise! I am amazed that someone had not proposed it yet!

Kerstin's approach is to take the documents and translate them to English and sentiment analysis is applied on the translated version of the document to determine the polarity. One key technology being used in this work is SentiWordNet. It is a lexical resource for opinion mining that was manually created. It offers a triple of polarity scores for each wordnet synset (pos, neg, objectivity). This is an amazing resource for anyone working on Sentiment analysis. I was unaware of SentiWordNet when we were working on the TREC Blog track 2006. In retrospect, I wish I knew of it back then.

Working with the translated text, this paper identifies each word+POS and does a lookup in sentiword to obtain the scores per synset. Next, they calculate the score for each word class (adj,noun, verbs) for a given document. Finally, the score triples are averaged across the words in the sentences. The document is given a polarity score using the triples across all the sentences.

To identify the polarity there were two approaches that were used:

• Use a rule based approach by thresholding
• Use Machine Learning (WEKA) to train a logistic regression classifier.

Evaluation was done by using IMDB archive (1000 pos,neg reviews in English) and the testset was  MPQA (English) and Amazon movie reviews (German).

Some sources of errors mentioned in the presentation:

• Statistical translation errors
• "writing errors", which I think means slang usage (scaaaaade = what a pity or aaaawful)
• The system does not consider negated structures (not bad)
• mising resolution abiguities 14 synset for "bad"

Their results indicate that ML based approach is better and obtains an accuracy of around .65.

Labeling Blogs using Graph Regularization

Recently I learned about semi-supervised learning over graphs. Using a small number of labeled nodes, the task is to find the appropriate nodes that belong to the same class as the labeled, training data. This problem is typical in Web spam detection where some hosts are identified as spammers (possibly manually) and the goal is to automatically tag the rest of the hosts as either spammers/non-spammers.

A similar task can be formulated for learning the labels in blog graphs. For popular blogs, it is not hard to find good quality labels using either Bloglines or del.icio.us. Often these labels are most reliable for popular blogs that have been tagged by many readers. Now in order to find out the other blogs that share the same label, a method recently suggested is Graph Regularization. (And for an overview on label propagation methods here is a nice tutorial).

Graph regularization uses the spectral properties of the graph to find a function that satisfies the following two constraints:

• Smoothness Constraint
• Fitting Constraint

According to the smoothness constraint, nodes that are close to each other in the graph would have the same label. On the other hand the fitting constraint ensures that the final label assignments do not deviate too much from the training data. Thus imposing a penalty for misclassification of training examples. The two constraints can be formulated in terms of the graph Laplacian. For details refer Zhou et al.

As an example, for a small blog graph, I obtained the del.icio.us tags corresponding to each blog. Empirically, I find that del.icio.us tags provide very good description of the blog. Once the tags are obtained (I used the JSON API), I use just 10 blogs tagged as "sports" and use the above regularization method to find other blogs that might be similar. The final scores (see figure, right) after regularization correspond to the community structure (found using Ncut, left) as shown in the figure below.

Here is the list of some blogs that were categorized under the label "sports", starting with the training set of 10 blogs.

In my opinion, two things stand out... one the Ncut algorithm itself may be improved if it was to be using additional tag information. Secondly, label propagation for blogs is slightly more complicated than just the original binary classification (spam/not spam) problem. One could have a few hundreds different labels that might need to be propagated, moreover -- the labels themselves may be quite related ("tech","technology","Programming", etc). Adding the constraint that labels should be propagated, subject to some known distribution makes optimizing the above cost function slightly more complicated. Furthermore, a blog may be equally relevant to two very different labels -- "politics" and "sports".

Any thoughts? Other techniques that might be useful? Ideas on how inter-related, multiple labels, can be propagated over a graph?