Abstract
Inferring the sentiment of social media content, for instance blog posts and forum threads, is both of great interest to security analysts and technically challenging to accomplish. This paper presents two computational methods for estimating social media sentiment which address the challenges associated with Webbased analysis. Each method formulates the task as one of text classification, models the data as a bipartite graph of documents and words, and assumes that only limited prior information is available regarding the sentiment orientation of any of the documents or words of interest. The first algorithm is a semisupervised sentiment classifier which combines knowledge of the sentiment labels for a few documents and words with information present in unlabeled data, which is abundant online. The second algorithm assumes existence of a set of labeled documents in a domain related to the domain of interest, and leverages these data to estimate sentiment in the target domain. We demonstrate the utility of the proposed methods by showing they outperform several standard techniques for the task of inferring the sentiment of online movie and consumer product reviews. Additionally, we illustrate the potential of the methods for security informatics by estimating regional public opinion regarding two events: the 2009 Jakarta hotel bombings and 2011 Egyptian revolution.
Keywords:
sentiment analysis; social media; security informatics; machine learning1. Introduction
There is increasing recognition that the Web represents a valuable source of securityrelevant intelligence and that computational analysis offers a promising way of dealing with the problem of collecting and analyzing data at Web scale [e.g., [14]]. As a consequence, tools and algorithms have been developed which support various security informatics objectives [3,4]. To cite a specific example, we have recently shown that blog network dynamics can be exploited to provide reliable early warning for a class of extremistrelated, realworld protest events [5].
Monitoring social media to spot emerging issues and trends and to assess public opinion concerning topics and events is of considerable interest to security professionals; however, performing such analysis is technically challenging. The opinions of individuals and groups are typically expressed as informal communications and are buried in the vast, and largely irrelevant, output of millions of bloggers and other online content producers. Consequently, effectively exploiting these data requires the development of new, automated methods of analysis [3,4]. Although helpful computational analytics have been derived for traditional forms of written content, less has been done to develop techniques that are wellsuited to the particular characteristics of the content found in social media.
This paper considers one of the central problems in the new field of social media analytics: deciding whether a given document, such as a blog post or forum thread, expresses positive or negative opinion toward a particular topic. The informal nature of social media content poses a challenge for languagebased sentiment analysis. While statistical learningbased methods often provide good performance in unstructured settings like this [e.g., [613]], obtaining the required labeled instances of data, such as a collection of "exemplar" blog posts of known sentiment polarity, is usually an expensive and timeconsuming undertaking.
We present two new computational methods for inferring sentiment orientation of social media content which address these challenges. Each method formulates the task as one of text classification, models the data as a bipartite graph of documents and words, and assumes that only limited prior information is available regarding the sentiment orientation of any of the documents or words of interest. The first algorithm adopts a semisupervised approach to sentiment classification, combining knowledge of the sentiment polarity for a few documents and a small lexicon of words with information present in a corpus of unlabeled documents; note that such unlabeled data are readily obtainable in online applications. The second algorithm assumes existence of a set of labeled documents in a domain related to the domain of interest, and provides a procedure for transferring the sentiment knowledge contained in these data to the target domain. We demonstrate the utility of the proposed algorithms by showing they outperform several standard methods for the task of inferring the sentiment polarity of online reviews of movies and consumer products. Additionally, we illustrate the potential of the methods for security informatics through two case studies in which sentiment analysis of Arabic, Indonesian, and Danish (language) blogs is used to estimate regional public opinion regarding the 2009 Jakarta hotel bombings and 2011 Egyptian revolution.
2. Preliminaries
We approach the task of estimating the sentiment orientations of a collection of documents as a text classification problem. Each document of interest is represented as a "bag of words" feature vector x∈ℜ^{V}, where the entries of × reflect some measure of the frequency with which the words in the vocabulary set V appear in the document. For example, the elements of × can be simple wordcounts, or × can be normalized in various ways [6]. In this paper the elements x_{i }of × are defined to indicate the presence (x_{i }= 1) or absence (x_{i }= 0) of the corresponding words in the document; however, specifying × using wordcounts yields similar results.) We wish to learn a vector c∈ℜ^{V }such that the classifier orient = sign(c^{T}x) accurately estimates the sentiment orientation of document x, returning +1 (1) for documents expressing positive (negative) sentiment about the topic of interest.
Knowledgebased classifiers leverage prior domain information to construct the vector c. One way to obtain such a classifier is to assemble lexicons of positive words V^{+}⊆V and negative words V^{}⊆V, and then to set c_{i}= +1 if word i∈V^{+}, c_{i}= 1 if i∈V^{}, and c_{i}=0 if i is not in either lexicon; this classifier simply sums the positive and negative sentiment words in the document and assigns document orientation accordingly. While this scheme can provide acceptable performance in certain settings, it is unable to improve its performance or adapt to new domains, and it is usually laborintensive to construct lexicons which are sufficiently complete to enable useful sentiment classification performance to be achieved.
Alternatively, learningbased methods attempt to generate the classifier vector c from examples of positive and negative sentiment. To obtain a learningbased classifier, one can begin by assembling a set of n_{l }labeled documents {(x_{i}, d_{i})}, where d_{i}∈{+1, 1} is the sentiment label for document i. The vector c then can be learned through "training" with the set {(x_{i}, d_{i})}, for instance by solving the following set of equations for c:
where matrix X∈ℜ^{nl×V }has document vectors for rows, d∈ℜ^{nl }is the vector of document labels, I_{V }denotes the V×V identity matrix, and gγ0 is a constant; this corresponds to regularized least squares (RLS) learning [14]. Many other strategies can be used to compute c, including Naïve Bayes (NB) statistical inference [6]. Learningbased classifiers have the potential to improve their performance and to adapt to new situations, but standard methods for realizing these capabilities require that fairly large training sets of labeled documents be obtained and this is usually expensive.
Sentiment analysis of social media content for security informatics applications is often characterized by the existence of only modest levels of prior knowledge regarding the domain of interest, reflected in the availability of a few labeled documents and small lexicon of sentimentladen words, and by the need to rapidly learn and adapt to new domains. As a consequence, standard knowledgebased and learningbased sentiment analysis methods are typically illsuited for security informatics. In order to address this challenge, the sentiment analysis methods developed in this paper enable limited labeled data to be combined with readily available "auxiliary" information to produce accurate sentiment estimates. More specifically, the first proposed method is a semisupervised algorithm [e.g., [9,10]] which leverages a source of supplementary data which is abundant online: unlabeled documents and words. Our second algorithm is a novel transfer learning method [e.g., [11]] which permits the knowledge present in data that has been previously labeled in a related domain (say online movie reviews) to be transferred to a new domain (e.g., reviews of consumer products).
Each of the algorithms proposed in this paper assumes the availability of a modest lexicon of sentimentladen words. This lexicon is encoded as a vector w∈ℜ^{Vl}, where V_{l }= V^{+}∪V^{ }is the sentiment lexicon and the entries of w are set to +1 or 1 according to the polarity of the corresponding words. The development of the algorithms begins by modeling the problem data as a bipartite graph G_{b }of documents and words (see Figure 1). It is easy to see that the adjacency matrix A for graph G_{b }is given by
Figure 1. Cartoon of bipartite graph model Gb, in which documents (red vertices) are connected to the words (blue vertices) they contain and the link weights (black edges) can reflect word frequencies.
where the matrix X∈ℜ^{n×V }is constructed by stacking the document vectors as rows, and each '0' is a matrix of zeros. In both the semisupervised and transfer learning algorithms, integration of labeled and "auxiliary" data is accomplished by exploiting the relationships between documents and words encoded in the bipartite graph model. The basic idea is to assume that, in the bipartite graph G_{b}, positive documents will tend to be connected to (contain) positive words, and analogously for negative documents/words.
3. SemiSupervised Sentiment Analysis
We now derive our first sentiment estimation algorithm for social media content. Consider the common situation in which only limited prior knowledge is available about the way sentiment is expressed in the domain of interest, in the form of small sets of documents and words for which sentiment labels are known, but where abundant unlabeled documents can be easily collected (e.g., via Web crawling). In this setting it is natural to adopt a semisupervised approach, in which labeled and unlabeled data are combined and leveraged in the analysis process. In what follows we present a novel bipartite graphbased approach to semisupervised sentiment analysis.
Assume the initial problem data consists of a corpus of n documents, of which n_{l }<< n are labeled, and a modest lexicon V_{l }of sentimentladen words, and suppose that this label information is encoded as vectors d∈ℜ^{nl }and w∈ℜ^{Vl}, respectively. Let d_{est}∈ℜ^{n }be the vector of estimated sentiment orientations for the documents in the corpus, and define the "augmented" classifier c_{aug }= [d_{est}^{T }c^{T}]^{T}∈ℜ^{n+V }which estimates the polarity of both documents and words. Note that the quantity c_{aug }is introduced for notational convenience in the subsequent development and is not directly employed for classification. More specifically, in the proposed methodology we learn c_{aug}, and therefore c, by solving an optimization problem involving the labeled and unlabeled training data, and then use c to estimate the sentiment of any new document of interest with the simple linear classifier orient = sign(c^{T}x). We refer to this classifier as semisupervised because it is learned using both labeled and unlabeled data. Assume for ease of notation that the documents and words are indexed so the first n_{l }elements of d_{est }and V_{l} elements of c correspond to the labeled data.
We wish to learn an augmented classifier c_{aug }with the following three properties: 1.) if a document is labeled, then the corresponding entry of d_{est }should be close to this ±1 label; 2.) if a word is in the sentiment lexicon, then the corresponding entry of c should be close to this ±1 sentiment polarity; and 3.) if there is an edge X_{ij }of G_{b }that connects a document × and a word v∈V and X_{ij }possesses significant weight, then the estimated polarities of × and v should be similar. These objectives are encoded in the following minimization problem:
where L = D  A is the graph Laplacian matrix for G_{b}, with D the diagonal degree matrix for A (i.e., D_{ii }= ∑_{j }A_{ij}), and β_{1}, β_{2 }are nonnegative constants. Minimizing (3) enforces the three properties we seek for c_{aug}, with the second and third terms penalizing "errors" in the first two properties. To see that the first term enforces the third property, observe that this expression is a sum of components of the form X_{ij}(d_{est,i } c_{j})^{2}. The constants β_{1}, β_{2 }can be used to balance the relative importance of the three properties.
The c_{aug }which minimizes the objective function (3) can be obtained by solving the following set of linear equations:
where the L_{ij }are matrix blocks of L of appropriate dimension. The system (4) is sparse because the data matrix × is sparse, and therefore largescale problems can be solved efficiently. Note that in situations where the set of available labeled documents and words is very limited, say less than a couple hundred documents, sentiment classifier performance can be improved by replacing L in (4) with the normalized Laplacian L_{n}=D^{1/2}LD^{1/2}, or with a power of this matrix L_{n}^{k }(for k a positive integer). The Appendix of this paper demonstrates that replacing L with L_{n}^{k }serves to "smooth" the polarity estimates assigned to the vertices of G_{b}, thereby reducing the possibility for overfitting and increasing the capability for generalization.
We summarize this discussion by sketching an algorithm for learning the proposed semisupervised classifier:
Algorithm SS
1. Construct the set of equations (4), possibly by replacing the graph Laplacian L with L_{n}^{k}.
2. Solve equations (4) for c_{aug }= [ d_{est}^{T }c^{T }]^{T }(for instance using the Conjugate Gradient method).
3. Estimate the sentiment orientation of any new document × of interest as: orient = sign(c^{T}x).
The utility of Algorithm SS is now examined through a case study involving a standard sentiment analysis task: estimation of the sentiment polarity of online movie reviews (an exercise which is known to be difficult).
4. Case Study One: Movie Reviews
This case study examines the performance of Algorithm SS for the problem of estimating sentiment of online movie reviews. The data used in this study is a publicly available set of 2000 movie reviews, 1000 positive and 1000 negative, collected from the Internet Movie Database and archived at the website [15]. The Lemur Toolkit [16] was employed to construct the data matrix × and vector of document labels d from these reviews. A lexicon of ~1400 domainindependent sentimentladen words was obtained from [17] and employed to build the lexicon vector w.
This study compares the movie review orientation classification accuracy of Algorithm SS with that of three other schemes: 1.) lexicononly, in which the lexicon vector w is used as the classifier as summarized in Section II, 2.) a classical NB classifier obtained from [18], and 3.) a welltuned version of the RLS classifier (1). Algorithm SS is implemented with the following parameter values: β_{1 }= 0.1, β_{2 }= 0.5, and k = 10. A focus of the investigation is evaluating the extent to which good sentiment estimation performance can be achieved even if only relatively few labeled documents are available for training; thus we examine training sets which incorporate a range of numbers of labeled documents: n_{l }= 50, 100, 150, 200, 300, 400, 600, 800, 1000.
Sample results from this study are depicted in Figure 2. Each data point in the plots represents the average of ten trials. In each trial, the movie reviews are randomly partitioned into 1000 training and 1000 test documents, and a randomly selected subset of training documents of size n_{l }is "labeled" (i.e., the labels for these reviews are made available to the learning algorithms). As shown in Figure 2, Algorithm SS outperforms the other three methods. Note that, in particular, the accuracy obtained with the proposed approach is significantly better than the other techniques when the number of labeled training documents is small. It is expected that this property of Algorithm SS will be of considerable value in security informatics applications that involve social media data.
Figure 2. Results for the movie reviews case study. The plot shows how sentiment estimation accuracy (vertical axis) varies with number of available labeled movie reviews (horizontal axis) for four different classifiers: lexicon only (black), NB (magenta), RLS (blue), and Algorithm SS (red).
5. Transfer Learning Sentiment Analysis
This section develops the second proposed sentiment estimation algorithm for social media content. Many security informatics applications are characterized by the presence of limited labeled data for the domain of interest but ample labeled information for a related domain. For instance, an analyst may wish to ascertain the sentiment of online discussions about an emerging topic of interest, and may have in hand a large set of labeled examples of positive and negative posts regarding other topics (e.g., from previous studies). In this setting it is natural to adopt a transfer learning approach, in which knowledge concerning the way sentiment is expressed in one domain, the socalled source domain, is transferred to permit sentiment estimation in a new target domain. In what follows we present a new bipartite graphbased approach to transfer learning sentiment analysis.
Assume that the initial problem data consists of a corpus of n = n_{T }+ n_{S }documents, where n_{T }is the (small) number of labeled documents available for the target domain of interest and n_{S }>> n_{T }is the number of labeled documents from some related source domain; in addition, suppose that a modest lexicon V_{l }of sentimentladen words is known. Let this label data be encoded as vectors d_{T}∈ℜ^{nT}, d_{S}∈ℜ^{nS}, and w∈ℜ^{V}, respectively. Denote by d_{T,est}∈ℜ^{nT}, d_{S,est}∈ℜ^{nS}, and c∈ℜ^{Vl }the vectors of estimated sentiment orientations for the target and source documents and the words, and define the augmented classifier as c_{aug }= [d_{S,est}^{T }d_{T,est}^{T }c^{T}]^{T }∈ ℜ^{n+V}. Note that the quantity c_{aug }is introduced for notational convenience in the subsequent development and is not directly employed for classification.
In what follows we derive an algorithm for learning c_{aug}, and therefore c, by solving an optimization problem involving the labeled source and target training data, and then use c to estimate the sentiment of any new document of interest via the simple linear classifier orient = sign(c^{T}x). This classifier is referred to as transfer learningbased because c is learned, in part, by transferring knowledge about the way sentiment is expressed from a domain which is related to (but need not be identical to) the domain of interest.
We wish to learn an augmented classifier c_{aug }with the following four properties: 1.) if a source document is labeled, then the corresponding entry of d_{S,est }should be close to this ±1 label; 2.) if a target document is labeled, then the corresponding entry of d_{T,est }should be close to this ±1 label, and the information encoded in d_{T }should be emphasized relative to that in the source labels d_{S,}; 3.) if a word is in the sentiment lexicon, then the corresponding entry of c should be close to this ±1 sentiment polarity; and 4.) if there is an edge X_{ij }of G_{b }that connects a document × and a word v∈V and X_{ij }possesses significant weight, then the estimated polarities of × and v should be similar.
The four objectives listed above may be realized by solving the following minimization problem:
where L = D  A is the graph Laplacian matrix for G_{b}, as before, and β_{1}, β_{2}, β_{3}, k_{S}, and k_{T }are nonnegative constants. Minimizing (5) enforces the four properties we seek for c_{aug}. More specifically, the second, third, and fourth terms penalize "errors" in the first three properties, and choosing β_{2 }>β_{1 }and k_{T }>k_{S }favors target label data over source labels. To see that the first term enforces the fourth property, note that this expression is a sum of components of the form X_{ij }(d_{T,est,i } c_{j})^{2 }and X_{ij }(d_{S,est,i } c_{j})^{2}.The constants β_{1}, β_{2}, β_{3 }can be used to balance the relative importance of the four properties.
The c_{aug }which minimizes the objective function (5) can be obtained by solving the following set of linear equations:
where the L_{ij }are matrix blocks of L of appropriate dimension. The system (6) is sparse because the data matrix × is sparse, and therefore largescale problems can be solved efficiently. In applications with very limited labeled data, sentiment classifier performance can be improved by replacing L in (6) with the normalized Laplacian L_{n }or with a power of this matrix L_{n}^{k}.
Note that developing systematic methods for characterizing how similar the source and target domains must be to enable useful transfer learning, or for selecting an appropriate source domain given a target set of interest, remain open research problems. Some helpful guidance for these tasks is provided in [12].
We summarize the above discussion by sketching an algorithm for constructing the proposed transfer learning classifier:
Algorithm TL
1. Construct the set of equations (6), possibly by replacing the graph Laplacian L with L_{n}^{k}.
2. Solve equations (6) for c_{aug }= [d_{S,est}^{T }d_{T,est}^{T }c^{T}]^{T}.
3. Estimate the sentiment orientation of any new document × of interest as: orient = sign(c^{T}x).
The utility of Algorithm TL is now examined through a case study involving online consumer product reviews.
6. Case Study Two: Product Reviews
This case study examines the performance of Algorithm TL for the problem of estimating sentiment of online product reviews. The data used in this study is a publicly available set of 1000 reviews of electronics products, 500 positive and 500 negative, and 1000 reviews of kitchen appliances, 500 positive and 500 negative, collected from Amazon and archived at the website [19]. The Lemur Toolkit [16] was employed to construct the data matrix × and vectors of document labels d_{S }and d_{T }from these reviews. A lexicon of 150 domainindependent sentimentladen words was constructed manually and employed to form the lexicon vector w.
This study compares the product review sentiment classification accuracy of Algorithm TL with that of four other strategies: 1.) lexicononly, in which the lexicon vector w is used as the classifier as summarized in Section II, 2.) a classical NB classifier obtained from [18], 3.) a welltuned version of the RLS classifier (1), and 4.) Algorithm SS. Algorithm TL is implemented with the following parameter values: β_{1 }= 1.0, β_{2 }= 3.0, β_{3 }= 5.0, k_{S }= 0.5, k_{T }= 1.0, and k = 5. A focus of the investigation is evaluating the extent to which the knowledge present in labeled reviews from a related domain, here kitchen appliances, can be transferred to a new domain for which only limited labeled data is available, in this case electronics. Thus we assume that all 1000 labeled kitchen reviews are available to Algorithm TL (the only algorithm which is designed to exploit this information), and examine training sets which incorporate a range of numbers of labeled documents from the electronics domain: n_{T }= 20, 50, 100, 200, 300, 400.
Sample results from this study are depicted in Figure 3. Each data point in the plots represents the average of ten trials. In each trial, the electronics reviews are randomly partitioned into 500 training and 500 test documents, and a randomly selected subset of reviews of size n_{T }is extracted from the 500 labeled training instances and made available to the learning algorithms. As shown in Figure 3, Algorithm TL outperforms the other four methods. Note that, in particular, the accuracy obtained with the transfer learning approach is significantly better than the other techniques when the number of labeled training documents in the target domain is small. It is expected that the ability of Algorithm TL to exploit knowledge from a related domain to quickly learn an effective sentiment classifier for a new domain will be of considerable value in security informatics applications involving social media data.
Figure 3. Results for the consumer product reviews case study. The plot shows how sentiment estimation accuracy (vertical axis) varies with number of available labeled electronics reviews (horizontal axis) for five different classifiers: lexicon only (orange), NB (black), RLS (magenta), Algorithm SS (blue), and Algorithm TL (red).
7. Case Study Three: Jakarta Hotel Bombings
On 17 July 2009 the JW Marriott and RitzCarlton Hotels in Jakarta, Indonesia were hit by suicide bombing attacks within five minutes of each other. A little over a week later, on 26 July 2009, a document claiming responsibility for the attacks and allegedly written by N.M. Top was posted on the blog [20]; see Figure 4 for a screenshot of a portion of this blog post. In subsequent discussions we will refer to this post as the "Top post" for convenience, with the understanding that the authorship of the post is uncertain. At this time, senior U.S. intelligence and security officials expressed interest in understanding sentiment in the region regarding the bombings and the alleged claim of responsibility by a wellknown extremist [personal communications, Senior U.S. Intelligence and Security Officials, July 2009]. Among other things, officials felt that characterizing this sentiment might provide insight into Indonesian public opinion concerning violent extremist organizations.
Figure 4. Screenshot of blog post, allegedly by N.M. Top, claiming responsibility for the July 2009 bombings of two hotels in Jakarta, Indonesia.
To enable a preliminary assessment along these lines, we collected two sets of social media data related to the Top post: 1.) the ~3000 comments made to the post during the two week period immediately following the post, and 2.) several hundred posts made to other Indonesian language blogs in which the Top post was discussed. We manually labeled the sentiment of a small subset of these documents, and also translated into Indonesian the generic sentiment lexicon used in Case Study One (in this paper all language translation was performed using the tool available at http://translate.google.com webcite). Observe that this approach to constructing a sentiment lexicon is far from perfect. However, because our proposed algorithms employ several sources of information to estimate the sentiment of content, it is expected that they will exhibit robustness to imperfections in any single data source. This study therefore offers the opportunity to explore the utility of a very simple approach to multilingual sentiment analysis: translate a small lexicon of sentimentladen words into the language of interest and then apply Algorithm SS or Algorithm TL directly within that language (treating words as tokens). The capability to perform automated, multilingual content analysis is of substantial interest in many securityrelated applications.
We implemented Algorithm SS to estimate the sentiment expressed in the corpus of comments made to the Top post [20] and in the set of related discussions posted at other blogs. Sample sentiment estimation results for the comments made to the Top post are shown at the top of Figure 5. These comments are almost universally negative, condemning both the bombings and the justification for the bombings given in the Top post. Manual examination of a subset of the comments confirms the results provided by Algorithm SS. For example, a typical negative comment reads, in part (translated from the Indonesian):
Figure 5. Sample results for blog analysis case study. The top plot shows the estimated sentiment of comments made directly to the blog [20] in response to the Top post (blue is negative, red is "conspiracyrelated", with red data multiplied by a factor of 10 to be visible on the graph). The bottom plot gives estimated sentiment of blog posts discussing the Top post (total is blue, positive is red, olive is neutral, and purple is negative, respectively).
" ... a savage kind  Noordin M. Top does not deserve to live in this world, he only claims to serve Islam but actually he is in truth a disbeliever. You are all cowards, you terrorists reversing Islam, and Noordin Top is just a stupid terrorist who escaped Malaysia just to inflict violence and hatred ... ."
Interestingly, by slightly reformulating the classifier it is possible to discover that while almost all comments are negative, there is a thread of comments which puts forth various conspiracies associated with the origins of the bombings and/or the Top post. The following comment is illustrative of this theme:
" ... the only explanation for the sophistication of the attacks is that the bombers were aided by the CIA or Mossad."
Sample results obtained through sentiment analysis of relevant posts made to other blogs are presented at the bottom of Figure 5. These posts also express largely negative sentiments about the Top post, although they are not as consistently negative as are the comments made directly on the Top post blog site. It should be noted that the "neutral" post sentiment depicted in the plot at the bottom of Figure 5 are mainly news articles. Again, manual evaluation of a subset of these posts confirm the results obtained via automated classification with Algorithm SS.
8. Case Study Four: Egyptian Revolution
Beginning on 25 January 2011, a popular uprising swept across Egypt in the form of massive demonstrations and rallies, labor strikes in various sectors, and violent clashes between protestors and security forces, ultimately leading to the resignation of Egyptian President Hosni Mubarak on 11 February. National security analysts and officials have expressed interest in understanding public sentiment regarding the Egyptian revolution generally and Mubarak specifically, especially 1.) in the weeks before the protests and 2.) for different regions of the globe.
To enable a preliminary assessment along these lines, we collected three sets of blog posts which are related to Egyptian unrest and Mubarak and were posted during the two week period immediately before the protests began on 25 January: 1.) 100 Arabic posts, 2.) 100 Indonesian posts, and 3.) 100 Danish posts. We manually labeled the sentiment of a small subset of these documents, and translated into the appropriate language the generic sentiment lexicon used in Case Study One for implementation in this study (using the translation tool available at http://translate.google.com webcite). Observe that this approach to constructing a sentiment lexicon is far from perfect. However, because lexical information is only one of the data sources used in the proposed approaches to sentiment estimation, it is expected that overall performance will exhibit robustness to imperfections in any one source of data; indeed, this study provides a simple test of this expected robustness.
We used Algorithm SS to estimate the sentiment expressed in the three sets of blog posts noted above, classifying the posts as either 'negative' or 'positive/neutral'. The analysis reveals that, while the sentiment expressed by the bloggers in the sample is largely negative toward Mubarak, the fraction of negative posts varies by post language (and thus possibly by geographic region). In particular, as shown in Figure 6, Arabic language posts are the most negative, followed by Indonesian posts, with the Danish posts in our sample actually being slightly more positive/neutral than negative. Manual inspection of a subset of the comments confirms the results provided by Algorithm SS.
Figure 6. Results for Egyptian revolution case study. The bar chart shows that, while blog sentiment toward former Egyptian President Hosni Mubarak in the weeks leading up to the protests was largely negative, this sentiment varies with the language of posts. More specifically, the fraction of posts expressing negative sentiment regarding Mubarak is 0.80 for Arabic posts, 0.58 for Indonesian posts, and 0.44 for Danish posts.
9. Summary
Sentiment analysis of social media content for security informatics applications is often characterized by the existence of only modest levels of prior knowledge regarding the domain of interest and the need to rapidly adapt to new domains; consequently, standard content analysis methods typically perform poorly in this setting. This paper presents two new computational methods for inferring the sentiment expressed in social media which address these challenges. Each method formulates the task as one of text classification, models the data as a bipartite graph of documents and words, and enables prior knowledge concerning the sentiment orientation of documents or words of interest to be effectively combined with "auxiliary" information to produce accurate sentiment estimates. The first proposed method is a semisupervised algorithm that leverages a source of supplementary data which is abundant online: unlabeled documents and words. The second algorithm is a novel transfer learning method which permits the knowledge present in data that has been previously labeled in a related domain to be transferred to a new domain. We demonstrate the utility of the proposed algorithms by showing they outperform several standard methods for the task of inferring the sentiment polarity of online reviews of movies and consumer products. Additionally, we illustrate the potential of the methods for security informatics by estimating regional public opinion regarding two securityrelevant events: the 2009 Jakarta hotel bombings and the 2011 Egyptian revolution.
The proposed algorithms are complementary in that they exploit different sources of auxiliary information (each of which is frequently available in security informatics applications). For instance, Algorithm SS is able to extract useful information from unlabeled documents and words, which are typically abundant online. This capability is particularly valuable in applications for which it is difficult or expensive to acquire any form of labeled data. Alternatively, if previous analysis has produced labeled information in a domain related to the current domain of interest, Algorithm TL can be used to effectively leverage this related data; observe that this situation is common in intelligence analysis settings.
Competing interests
The authors declare that they have no competing interests.
Authors' contributions
KG and RC designed the research, KG and RC developed the computational algorithms, KG conducted the empirical tests, and RC wrote the paper. All authors read and approved the final manuscript.
Appendix
As summarized in Section 3, solving the optimization problem
balances three objectives:
• clustering: reducing c^{T}_{aug}L_{n}c_{aug }ensures that polarity estimates for documents, d_{est,i}, and words, c_{j}, are assigned to reduce the magnitude of terms of the form
where D_{1,ii}^{1/2 }= (∑_{j }X_{ij})^{1/2 }and D_{2,jj}^{1/2 }= (∑_{i }X_{ij})^{1/2};
• prior knowledge on documents: if document i is labeled d_{i }then the polarity estimate d_{est,i }should be close to this label;
• prior knowledge on words: if word i is labeled w_{i }then the polarity estimate c_{i }should be close to this label.
It is shown in this paper that this procedure enables accurate sentiment classifiers to be learned. However, in situations in which very little labeled data is available, this approach can produce numerous isolated polarity clusters around labeled instances on the graph G_{b}, resulting in overfitted solutions with little power for generalization. Here we show that replacing the term ϕ = c_{aug}^{T}L_{n}c_{aug }with ϕ_{k }= c_{aug}^{T}L^{k}_{n}c_{aug }, where k a positive integer, smoothes the sentiment polarity estimates on G_{b }and resolves this difficulty.
Note first that L_{n }can be expressed as
where (λ_{i}, z_{i}) are eigenvalueeigenvector pairs for L_{n}, and similarly that L_{n}^{k }can be written
Next observe that the quantity
measures the smoothness of the documentword polarity assignment specified by c_{aug}. If the eigenvalues λ_{i }are ordered so that 0 = λ_{1}≤ λ_{2}≤ ... ≤ λ_{n+V }then, because z_{j}^{T }L_{n }z_{j }= λ_{j}, it is seen that the eigenvectors z_{i }of L_{n }are ordered by their smoothness. Then, since {z_{1}, ..., z_{n+V}} is an orthonormal basis (L_{n }is symmetric), c_{aug }can be expanded as c_{aug }= ∑_{i }α_{i }z_{i }and ϕ becomes ϕ = ∑_{i }λ_{i}α_{i}^{2}.
Analogously, ϕ_{k }= c^{T}_{aug}L^{k}_{n}c_{aug }can be written
It follows that minimizing ϕ_{k }instead of ϕ results in smoother polarity specifications on G_{b}, because the former imposes a more aggressive penalization of polarity assignments that include the larger (and less smooth) eigenvalue terms.
Acknowledgements
This work was supported by the U.S. Department of Defense and the Laboratory Directed Research and Development Program at Sandia National Laboratories. Sandia National Laboratories is a multiprogram laboratory managed and operated by Sandia Corporation, a wholly owned subsidiary of Lockheed Martin Corporation, for the U.S. Department of Energy's National Nuclear Security Administration under contract DEAC0494AL85000.
References

US Committee on Homeland Security and Government Affairs, Violent Extremism, the Internet, and the Homegrown Terrorism Threat
2008.

Bergin A, Osman S, Ungerer C, Yasin N: Countering Internet Radicalization in Southeast Asia.

Chen H, Yang C, Chau M, Li S (Eds): Intelligence and Security Informatics. Lecture Notes in Computer Science, Springer, Berlin; 2009.

Proc 2010 IEEE International Conference on Intelligence and Security Informatics, Vancouver. 2010.

Colbaugh R, Glass K: Early warning analysis for social diffusion events.
Proc 2010 IEEE International Conference on Intelligence and Security Informatics, Vancouver 2010.

Pang B, Lee L: Opinion mining and sentiment analysis.
Foundations and Trends in Information Retrieval 2008, 2:1135. Publisher Full Text

Dhillon I: Coclustering documents and words using bipartite spectral graph partitioning. In Proc ACM International Conference on Knowledge Discovery and Data Mining. San Francisco; 2001.

Kim S, Hovy E: Determining the sentiment of opinions.
Proc International Conference on Computational Linguistics 2004.

Sindhwani V, Melville P: Documentword coregularization for semisupervised sentiment analysis.
Proc 2008 IEEE International Conference on Data Mining, Pisa 2008.

Colbaugh R, Glass K: Estimating sentiment orientation in social media for intelligence monitoring and analysis.
Proc 2010 IEEE International Conference on Intelligence and Security Informatics, Vancouver 2010.

Pan S, Yang Q: A survey on transfer learning.
IEEE Trans Knowledge and Data Engineering 2010, 22:13451359.

Blitzer J, Dredze M, Perieia F: Biographies, bollywood, boomboxes, and blenders: Domain adaptation for sentiment classification.

He J, Liu Y, Lawrence R: Graphbased transfer learning. In Proc 18th ACM Conference on Information and Knowledge Management. Hong Kong; 2009.

Hastie T, Tibshirani R, Friedman J: The Elements of Statistical Learning. Second edition. Springer, New York; 2009.

[http://www.cs.cornell.edu/People/pabo/moviereviewdata/] webcite
accessed 2009

[http://www.lemurproject.org/] webcite
accessed Dec 2009

Ramakrishnan G, Jadhav A, Joshi A, Chakrabarti S, Bhattacharyya P: Question answering via Bayesian inference on lexical relations. In Proc 41st Annual Meeting of the ACL. Sapporo; 2003.

[http://www.borgelt.net/bayes.html] webcite
accessed Dec. 2009

[http://www.cs.jhu.edu/~mdredze/] webcite
accessed Dec. 2010

[http://www.mediaislambushro.blogspot.com] webcite
accessed Aug. 2009