We study the classifier quantification problem in the context of the topical opinion retrieval, that consists in estimating proportions of the sentiment categories in the result set of a topic. We propose a methodology to circumvent individual classification allowing a real-time sentiment analysis for huge volumes of data. After discussing existing approaches to quantification, the novel proposed methodology is applied to Microblogging Retrieval and provides statistically significant estimates of sentiment category proportions. Our solution modifies Hopkins and King's approach in order to remove manual intervention, and making sentiment analysis feasible in real time. Evaluation is conduced with a test collection made up of about 3,2M tweets.
Sentiment analysis for social networks is one of the most popular and mature research problem in Information Retrieval and Machine Learning. Several companies already provide services aimed to detect, estimate, and summarize opinions of social network users on different topics. As a consequence, a “gold rush” is started on finding scalable solutions to perform real-time analysis on huge volumes of data.
In general, real-time content analysis should accomplish different tasks:
distilling high-quality samples about populations under investigation, labeling
samples by concepts and taxonomies, and providing accurate estimation of
sizes and proportions of category populations. Although accurate
classification of single documents and high precision retrieval are important desiderata
of real time content analytics, decision making often requires quantitative
analysis, that consists in computing accurately the estimates of populations size
or the proportion of individuals that fall into a predefined category. For
example, what is important in sentiment analysis or topical opinion retrieval [
We propose a methodology that provides statistically significant estimates
of sentiment category proportions in social science, and in particular in the
Microblogging Retrieval that is for the result set of tweets of a topic. In
particular, we revisit the classifier quantification problem in the context of
topical opinion retrieval. Classifier quantification was introduced earlier in
the 70s in epidemiology [
k The actual categories proportions P (Dk) are then solutions of all k (adjustedCC) linear equations. Since a sentiment classifier is trained independently from queries, and the collection C contains millions of documents, P (D^ jjDk) can be observed only on a small sample C0 of the collection. To accept these adjusted-CC solutions as correct sentiment category proportions among a subset Rq of relevant documents for a query q, we need to assume that P (D^ jjDk) are conservative on the subset of relevant documents of the query, even if the intersection Rq \ C0 might result empty. Alternatively, we need to introduce relevance as an extra category (actually irrelevance as a mutually exclusive extra category), and train the classifier on each query. The conservative assumption is unrealistic, because there always is a bias of sentiment distribution between relevant and non-relevant information, and sentiment analysis quantifies such a bias. On the other case, training the classifier on each query would be time consuming and requires a manual intervention. Notice that since the adjusted-CC approach uses misclassification proportions P (D^ jjDk), it works with any classifier accuracy. What is important for a statistically significant prediction is how large the random sample of the query is. Therefore, if the training set is a large random sample of the query population, then a query-by-query approach becomes de facto a manual evaluation of sentiment. Although the retrieving process is fast, classification task is instead time consuming so that the adjusted-CC approach is not feasible for real-time analytics.
In topical opinion retrieval, the strategy of filtering by sentiment the relevance
ranking always degrades retrieval performance with respect to other reranking
strategy [
We instead follow more closely the model proposed by Hopkins & King [
P(s 2 S0) = X P(s 2 S0jDj) P(Dj) j (1) Then P(Dj ) are obtained as regression coefficient of a linear regression set of equations.
The advantage of Hopkins & King’s methodology is that of estimating P(Dj ) without the intermediate step of computing the individual classifications. Unfortunately for each query, a manual classification is required for a quite large number of individuals of the population. Hopkins & King’s methodology is thus manual and provides only an automatic smoothing technique to make the manually labeled proportions statistically significant.
We now adapt Hopkins and King’s basic model to a topical opinion retrieval. The main difference with Hopkins and King’s methodology is the use of a set Sk of learned (biased) features for the set S0 (and not a random word profile sample), one for each category Dk. Also we do not count the features in the true category distribution of a query, but we use an information theoretic approach that instead counts the number of bits necessary to code all the features Sk that occurs in the result set of a query. The code is obtained with respect to the true distribution of a query-independent training set. We then assume that all these aggregated numbers of bits are linearly correlated to the number P(D^ kjDj ; q). In such a way we avoid the classification step as in Hopkins and King’s but we also avoid to use a manual evaluation for the specific query q.
In the next sections we present this approach in order to handle arbitrary queries without training on single queries. 2
First we exploit the theorem of total probability:
P(D^ kjq) = X L(D^ kjDj ; q) j
(Dj jq) where D^ k is the k-th category set with the chosen classifier, Dj is the true j-th category set, q the query, L(Dj jDk; q) is the likelihood, and (Dkjq) is the unknown prior on the set of categories (the actual category proportions). The non diagonal elements L(D^ ijDj ; q) of the matrix L, with i 6= j, are the errors due to all misclassified individuals.
The estimation problem can be thus restated to how to find estimates ^(Dkjq) for (Dkjq) that predict the proportions in the population for the categories Dk.
We now define population size prediction in terms of features of a textual
classifier. A textual classifier D^ can be defined as a set of features S (or a
weighting function from D^ to S) that assigns individuals to single categories.
For text classifiers D^ , S in particular is a set of words, each word having a
probability L(s 2 SjDi; q) of occurrence in the i-th category. S can be thus
chosen as a set of words spanning over the population of individuals, and
thus S is simply a function of the classifier D^ . For weighting function wsq;i,
such as the SVM classifier or IR weighting models such as standard tf-idf
model or other topic-specific lexicon [
q ws;i (2) (3) where the parameter is just a normalizing factor. The theorem of total probability spanning over a set S of features is
n P(s 2 Sjq) = X L(s 2 SjDi; q) (Dijq)
i=1 P(Sjq) = L(SjD; q) jSj 1 jSj jDj (Djq) jDj 1 where L(sjDi; q) is the likelihood and (Dijq) is the prior over the set of categories.
We may rewrite the Equality (4) in matrix form: Our problem formulation then can be restated as the problem of finding best fitting values ^(Dijq) for the vector (Dijq) in a set of linear equations. To learn the likelihood matrix L(D^ jD; q) on the entire population one can use instead a likelihood matrix LXq over a sample Xq of retrieved tweets with respect to the query q and error (L LXq ), that is (4) (5) P(D^ jq) = LXq (D^ jD; q)
(Djq) P(Sjq) = LXq (SjD; q) jSj 1 jSj jDj (Djq) jDj 1 Passing through the set S of spanning features we get the latent regression matrix L0Xq such that jDj jSj We may use the linear regression with the two matrices LXq and P. Therefore the estimates ^(Dkjq) of (Dkjq) becomes the coefficient for the k-th category of the linear regression and provide the estimated proportion for the category Dk.
The main computational cost of this methodology is that S should be learned by the chosen classifier D^ , that is S is a function of D^ and the topic q. A sentiment textual classifier has at least the following categories: fS+; S ; SNO; SMix; SNRg In presence of a query or a set of queries q, SNR contains all non relevant elements, SNO relevant but without opinions, S+ (S ) relevant and strictly positive (negative) opinions, whilst the individuals containing mixed opinions fall into the remaining category SMix. To learn S, and thus to build LXq , a manual inspection is required and this is the main drawback of this methodology to perform any real time analytics. Hopkins & King suggest to use a random sample of word profiles and manually annotate about 500 blog posts to achieve 99% of statistical significance of the estimates ^(Dijq). In case of an adjusted-CC approach with individual classifiers, such as SVM, there is a highly time intensive tuning phase. Hopkins and King reports that each run of their estimator based on SVM took 60 seconds of computer time, and a total of five hours for 300 bootstrapped runs, for a collection of 4k blog posts for a total number of 47k tokens.
We now want to get statistics on the sentiment polarity for the entire population relatively to an arbitrary query q at retrieval time.
LXq (si 2 SjDk; q) can be interpreted as the percent of times the sentiment term si occurs in the set Xq of evaluated tweets in Dk and retrieved by the query q, and P(si 2 Sjq) is the percent of times the sentiment term si occurs in the retrieved set. Once we have the evaluation on the query q the input matrices of LXq and P can be computed quite fast. A sentiment dictionary even when containing many thousand of elements is submitted to the system as a query and would be feasible to build the input matrices in seconds, or much less within a distributed system. However regression algorithm would require additional computation time, even though it would require still reasonable computational time in presence of a relatively small result set. 3.1
We now describe in details the approach. In the training phase we pool all relevant documents irrespective to the query by which they were retrieved and then we select the opinionated documents from the rest. Therefore we formed two collections the sentiment sample included into a document sample. The reason we use only relevant information is to use a fully evaluated collection, and thus reject from the sentiment dictionary words that occur randomly in both collections. The collection of relevant documents provides a prior distribution for the terms s (see s below). We then use the features s 2 Si of a classifier learned by the sentiment category Di. We apply the linear regression algorithm of Equation (5) and learn the regression coefficients. Each coefficient will be then multiplied by the sum of sentiment scores of the retrieved documents to obtain the number of tweets in a category for any new query q.
Training phase In the training phase we make the following assumptions: – (Multiple binary dictionaries reduction) We first assume a binary classifier for each category k. In particular for the sentiment analysis, we learn from only the positive and negative result sets, that is producing two distinct dictionaries S+ and S . We have thus two Equations (4), each therefore restricted to one of the two chosen categories. The likelihood for that category k is thus: LX (si 2 SkjDk; q). – We use information theoretic arguments to compute LX (SkjDk; qj) (but it is not necessarily a theoretical limit since any other score weighting formula or classifier can be similarly used here). We pool the result sets DQk for a category k from a set of training queries Q and extract frequencies of terms for that category Sk, and build the classifier for the k-th category
I(s 2 Sk) =
which is given by a binomial P with prior distribution s and frequencies
in DQk.
– The proportion of documents LXq (D^ kjDk; q) falling in a given category
with respect to the result set of a query q is proportional to the amount of
sentiment information for that category in the result set of that query [
I(Skjq) =
X s2Sk;d2Xq where P(D^ kjq) is the percent of observed individuals in the category Dk with respect to the query q. The errors in prediction between observed and predicted are given by the residuals P(D^ kjq) ^ I(Skjq) ^(Dk). Retrieval phase In the retrieval phase we assume that the number of tweets in the category k with respect to any query q is:
jDkj = ^ I(Skjq) ^(Dk) and proportions are given by jDkj where jCqj is the result set size of the query.
jCqj Notwithstanding that the ranking will contain both irrelevant and misclassified tweets for the k-th category that have a positive score I(s 2 Skjq), the predicted number of relevant tweets falling into the k-th category is very close to the actual number. (6) (7) 4 4.1
The evaluation of category size and category proportions for sentiment analysis is not trivial. Forman suggests to use the Kullback-Leibler distance between category distribution of CC-adjusted values and true values in the test set to measure effectiveness of the prediction, irrespective of the population size. This measure however though very simple does not comply with evaluation of quantification in social science or in statistics where residuals between predicted and observed values are measured. Also KL measures the distance between two distribution irrespective to the test set size. More precisely, to validate classifier effectiveness for individual classification an average value of different test sets smaller than their training sets is usually used, for example through a k-fold cross validation, so that the accuracy (which is a percentage of decision successes of the classifier) may not be statistically significant with respect to the actual population size. For example if a query has millions of relevant tweets and the evaluation is done on a few hundreds of them, then the true accuracy can falls into a very large confidence interval of the observed accuracy at 95% or higher confidence level. As an example, the third row of Table 2 shows a prediction of 45% positives within a population of 251K tweets, but the manual inspection on a sample shows 41% which falls into the confidence interval [37:1%; 52%] at the 95% confidence level. In such a case, it is required more evaluation of tweets to reject or accept that proportion prediction.
In addition, when quantification is not performed with a variant of a CC approach, such as our method which is not based on individual classification, then we cannot compute the accuracy of the classifier but may only study the residuals between the predicted and the observed values.
Here, we use the R-squared (sum of the squares of the residuals) regression analysis to assess the goodness of fit between observed and estimates of the category sizes, the number of queries (minus 1) being the degrees of freedom. Notice that, when individual classifier is used in quantification, the residual of the aggregated statistics is
Obs+
P red+ = tp + f p (tp + f n) = f p f n = (Obs
P red ) Therefore, the misclassification errors in quantification or in aggregated classification are less severe than in individual classification, because the missing counting of the false negatives is partially balanced by the counting of the false positives.
This observation does not complete evaluation issues. Relevance and sentiment polarity cannot be split in the evaluation. Therefore the true distribution of a test set can be only given for a sample of the population of a specific user query. However, the sentiment polarity of a non-relevant retrieved document always contribute to size prediction, and for difficult queries there are many non-relevant documents. How the difficulty of a query impacts sentiment category size prediction must be studied, though we may conjecture that the sentiment noise brought by irrelevant data maximizes the entropy of the probabilities over the sentiment vocabulary in the result set. The entropy maximization smooths the predicted sizes of a polarity skewed set of a large result set towards the polarity means in the collection, that is predicted sizes converge to milder values.
As final remark, in classification it is also assumed that the test set was randomly built from the entire population. In general this is not the case, especially in order to remove imbalance between positive and negative category sizes. On the contrary, in IR we easily have imbalance due to the sparsity of the terms over the collection. We may be accurate on some queries less on others so that the set of predictions xq; q 2 Q, must be assessed by standard statistical tests, that is studying the distribution of residuals to show how good was the fit (R-squared) or to single out possible query outliers (Cook’s distance or Normal Q-Q distributions etc.).
As a consequence of the above considerations, we have to distinguish proportion estimates from population size estimates, because they can largely vary. When the result set of a query is very small then proportions can be meaningless and not significant, whilst for large populations with small evaluated samples population size prediction can fall into a very large confidence level.
Sanremo
Sanremo
Bal aro TheVoiceOfItaly TREC Twitter Collection Tweets2011 is the only publicly available very large collection to test retrieval performance of models, but there is not yet a test collection on Twitter to conduct sentiment analysis. Obviously, nothing exists for the Italian language. However, Twitter’s policy for distribution requires the redistribution of only tweet IDs (or user IDs) not their content, and this restriction together with the limitation of a few hundreds for the maximum number of API requests by hour (by the GET statuses/show/:id or users/lookup :id methods) makes the actual distribution of a very large collection prohibitive. In order to test our methodology, especially for the Italian language, we have thus conducted a sentiment analysis campaign about the Italian TV broadcasting. From December 2012 up to April 2013, we collected about 3,2 million tweets related to 30 TV programs. More than 6300 tweets have been evaluated by a team of 5 assessors. For each TV program a random selection of tweets have been manually annotated in terms of: Relevance, that is: – highly relevant (R+), if the main topic of the tweet was about the TV program itself;
Residuals vs Fitted
ServizioPubblico CheTempoCheFa
Scale−Location
Bal aro
ServizioPubblico
CheTempoCheFa Residuals vs Leverage
ServizioPubblico s l a u id 2 s e r d 0 e z irda 2− CheTempoCheFa tdnaS 4− BCaloarook’s distance Although, the test phase is still preliminary, because of the small number of training queries and number of evaluated tweets for each query to learn dictionaries and test the classifiers, the 5-fold cross validation worked well (see Figure 3). To notice that the amount of overall positive information in the training set is much less than the negative one, and therefore a number of 30 0 0 0 0 5 T 1 _ S _SG 000 O 0 EN 01 0 0 0 0 5 0 0 0
queries for both testing and training is extremely small to learn a satisfactory vocabulary for positive polarity.
The quantile plots of Figures 1 and 2 (the Q-Q plots) show a normal distribution around a line with some outliers in the right upper corner. These outliers are caused by difficult queries, that is the queries with many relevant documents. For such queries the cumulative sentiment score becomes a less precise indicator for the prediction of the size of the category population, especially when there is a large bias of the positive (negative) opinions from their mean. Indeed, the outliers of the Figures 1 and 2 are those that receive the highest number of tweets with respect to the rest of the training queries. Also they have a relatively larger number of negative and positive tweets respectively with respect to others (the TV talk show called “Servizio Pubblico” has a very few percent of positive tweets, whilst the singer contest called “Sanremo” has a percent number of positive tweets that is larger than the mean 27.5%). In our opinion big national and international events (when the result set is very large) may require a specific classifier and not necessarily a linear regression classifier. Further investigation on how relevance (the number of irrelevant tweets in the results set) affects performance of sentiment predictions is thus required. 5
We have shown that sentiment estimation can be conducted in real time. For an arbitrary query, plot on Figure 4 shows the projected number of positive and negative tweets at different instant of time. At the moment, the two classifiers (positive and negative) are independent and do not interact. It can thus happen that sentiment quantification can produce inconsistent statistics when category proportions are compared.Relaxing the multiple binary dictionaries reduction assumption that handles separately positive and negative classifiers is thus required.
Ret POS POS NEG NEG
(pred) (obs) (pred) (obs)
Sanremo 825,596 23.2%* [29.3%, 38.4%] (33.7%) 33.4% [34.9%,44.3%] (39.5%) Servizio Pubb. 659,264 18.7%* [21.0%, 31.3%] (25.9%) 50.5%* [62.0%, 72.9%] (67.7%) VoiceOfItaly 251,296 45.7% [37.1%, 52.3%] (41.1%) 26.7%* [28.5%, 43.1%] (30.7%)
Ballarò 344,683 19.9%* [8.4%, 15.3%] (11.4%) 43.1%* [44.1%, 54.8%] (49.4%) CheTempoCheFa 134,455 27.3% [28.8%, 38.6%] (33.5%) 34.3% [29.5%, 39.4%] (36.6%) Work carried out under Research Agreement with Almawave.