We propose a scheme for explicitly modeling and representing negation of word n-grams in an augmented word n-gram feature space. For the purpose of negation scope detection, we compare 2 methods: the simpler regular expression-based NegEx, and the more sophisticated Conditional Random Field-based LingScope. Additionally, we capture negation implicitly via word bi- and trigrams. We analyze the impact of explicit and implicit negation modeling as well as their combination on several data-driven machine learning-based sentiment analysis subtasks, i.e. document-level polarity classi cation, both in- and cross-domain, and sentence-level polarity classi cation. In all subtasks, explicitly modeling negation yields statistically signi cant better results than not modeling negation or modeling it only implicitly.
Negations as in example (1)
(1) Don't ask me!
are at the core of human language. Hence, negations are commonly encountered
in natural language processing (NLP) tasks, e.g. textual entailment [
Therefore, negations are frequently treated in compositional semantic approaches
to SA [4{8], as well as in bag of words-based machine learning (ML) techniques
[
Research on negation scopes (NSs) and negation scope detection (NSD) was
primarily driven by biomedical NLP, particularly research on the detection of
absence or presence of certain diseases in biomedical text. One of the most
prominent studies in this eld is [
We model NSs in word n-gram feature space systematically and adopt recent
advances in NSD. We believe this endeavor is worthwhile, as this allows machines
to learn by themselves how negations modify the meaning of words, instead of
being taught by manually de ned and often ad hoc rules. Our work focuses
on data-driven ML-based models for SA that operate in word n-gram feature
space and do not rely on lexical resources, e.g. prior polarity dictionaries like
SentiWordNet [
This paper is structured as follows: In the next section we describe our approach to modeling and representing negation in data-driven ML-based SA. In Sect. 3 we evaluate our approach in experiments for several SA subtasks and discuss their results. Finally, we draw conclusions and point out possible directions for future work in Sect. 4. 2
We now describe our approach to implicitly and explicitly modeling and representing negation in word n-gram feature space for data-driven ML-based SA. When explicitly modeling negation, we incorporate our knowledge of negation into the model; when implicitly modeling negation, we do not. 2.1
As pointed out in [
2.2
Although it is convenient, there is a drawback to solely relying on higher order word n-grams when trying to capture negations: Long NSs as in example (4) occur frequently (cf. Sect. 3.3), but typically word n-grams (n < 5) are not able to properly capture them. (4) The leather straps have never worn out or broken.
Here, a word trigram captures \never worn out" but not \never [..] broken".
While a word 5-gram is able to capture \never [..] broken", learning models using
word n-gram features with n 3 usually leads to very sparse representations,
depending on how much training data is available and how homogeneous [
Negation Scope Detection Vital to explicit negation modeling is NSD. E.g., in example (5), we need to detect that \stand up to laundering very well" is in the scope of \don't". (5) They don't stand up to laundering very well, in that they shrink up quite a bit.
For that purpose, we employ NegEx3 [
To improve NSD, we expand contractions like \can't" to \can not", \didn't"
to \did not" etc. Please note that while NegEx considers the negation itself to
be part of the NS, we do not. NegEx's NSs are adjusted accordingly.
Representation in Feature Space Once NSs are detected, negated and
nonnegated word n-grams need to be explicitly represented in feature space.
Therefore, we resort to a representation inspired by [
Let W = fwig; i = 1; : : : ; d be our word n-grams and let X = f0; 1gd be our word n-gram feature space of size d, where for xj 2 X , xjk = 1 denotes the presence of wk and xjk = 0 denotes its absence. For each feature xjk we introduce an additional feature xjk that encodes whether wk appears negated (xjk = 1) or non-negated (xjk = 0). Thus, we obtain an augmented feature space X = f0; 1g2d. In X we are now able to represent whether a word n-gram 3 http://code.google.com/p/negex/ 4 http://sourceforge.net/projects/lingscope/ { w is present (encoded as [1; 0]), { w is absent ([0; 0]), { w is present and negated ([0; 1]) or { w is present both negated and non-negated ([1; 1]).
Representing an Example Assume we employ nave tokenization that simply splits at white spaces, ignore punctuation characters like \." and \," and extract the presence and absence of the word unigrams Wuni = f\bit", \don't", \down", \laundering", \quite", \shrink", \stand", \up", \very", \well"g, i.e. Wuni is our vocabulary. Representing example (5) in X results then in a stylized feature vector as shown in Table 1.
Note the di erence between \laundering" and \up". While \laundering" is present only once and is negated and thus is represented as [0; 1], \up" is present twice|once negated and once non-negated|and thus is represented as [1; 1]. 3
We evaluate our negation modeling approach in 3 common SA subtasks: indomain document-level polarity classi cation, cross-domain document-level polarity classi cation (cf. Sect. 3.1) and sentence-level polarity classi cation (cf. Sect. 3.2).
Our setup for all experiments is as follows: For sentence segmentation and
tokenization we use OpenNLP5. As classi ers we employ Support Vector Machines
(SVMs) in their LibSVM implementation6 using a linear kernel with their cost
factor C set to 2:0 without any further optimization. SVMs were chosen because
(i) it has been shown previously that they exhibit superior classi cation power
in polarity classi cation experiments [
As features we use word uni-, bi- and trigrams extracted from the data7.
Word bi- and trigrams model negation implicitly as described in Sect. 2.1. We
5 http://opennlp.apache.org
6 http://www.csie.ntu.edu.tw/~cjlin/libsvm/
7 We also experimented with word tetragrams, but found that they do not contribute
to the models' discriminative power. This is not surprising, as in all used data sets
most word tetragrams appear only once. The word tetragram distribution's relative
entropy [
The in-domain document-level and sentence-level polarity classi cation experiments are construed as 10-fold cross validations. As performance measure we report accuracy A to be comparable to other studies (cf. Sect. 3.4). The level of statistical signi cance is determined by strati ed shu ing, an approximate randomization test [28] run with 220 = 1; 048; 576 iterations as recommended by [29]. The level of statistically signi cant di erence to the corresponding base model without negation modeling is indicated by ?? (p < 0:005) and ? (p < 0:05). 3.1
As gold standard for in- and cross-domain document-level polarity classi cation we use [30]'s Multi-domain Sentiment Dataset v2.08 (MDSD v2.0), that contains star-rated product reviews of various domains. We chose 10 domains: apparel, books, dvd, electronics, health & personal care, kitchen & housewares, music, sports & outdoors, toys & games and video. Those are exactly the domains for which a pre-selected, balanced amount of 1,000 positive and 1,000 negative reviews is available. [30] consider reviews with more than 3 stars positive, and less than 3 stars negative|they omit 3-star reviews; so do we.
In-domain The evaluation results of our in-domain document-level polarity classi cation experiments averaged over all 10 domains are shown in Table 2.
A word funi, big-gram base model, LingScope for NSD and explicitly modeling negations for word funi, big-grams yields the best overall result (A = 81:93). This result is statistically signi cant di erent (p < 0:005) from the result the corresponding base model achieves using word funi, big-grams alone (A = 81:37). Cross-domain In our cross-domain experiments, for all 10!/(10-2)! = 90 source domain{target domain pairs, there are 2,000 labeled source domain instances (1,000 positive and 1,000 negative) and 200 labeled target domain instances (100 8 http://www.cs.jhu.edu/~mdredze/datasets/sentiment/ funig positive and 100 negative) available for training, 1,800 labeled target domain instances (900 positive and 900 negative) are used for testing. This is a typical semi-supervised domain adaptation setting. If required by the method the same amount of unlabeled target domain instances is available for training as there are labeled source domain instances: 2,000.
We employ 3 methods for cross-domain polarity classi cation, Instance Selection (IS) [31], \All" and EasyAdapt++ (EA++) [32]. While \All" simply uses all available labeled source and target domain training instances for training, EA++ additionally uses unlabeled target domain instances and operates via feature space augmentation and co-regularization [33]. IS selects source domain training instances that are most likely to be informative based on domain similarity and domain complexity of source and target domain.
For \All", just like for in-domain polarity classi cation, a word funi, big-gram base model, LingScope for NSD and explicitly modeling negations for word funi, big-grams yields the best overall result (A = 77:31, p < 0:005). The same applies to IS (A = 77:71, p < 0:005). For EA++, a word funi, big-gram base model, NegEx for NSD and explicitly modeling negations for word unigrams yields the best overall result (A = 77:5, p < 0:005). A word funi, bi, trig-gram base model, LingScope for NSD and explicitly modeling negations for word unigrams performs almost as good and yields A = 77:48 (p < 0:005). 9 http://asv.informatik.uni-leipzig.de/staff/Robert_Remus funig funig funi, big As gold standard for sentence-level polarity classi cation we use [34]'s sentence polarity dataset v1.010 (SPD v1.0), that contains 10,662 sentences from movie reviews annotated for their polarity (5,331 positive and 5,331 negative).
Evaluation results are shown in Table 4. Here, a word funi, bi, trig-gram base model, LingScope for NSD and explicitly modeling negations for word funi, bi, trig-grams yields the best result (A = 78:01, p < 0:05). 10 http://www.cs.cornell.edu/people/pabo/movie-review-data/ than NegEx on biomedical data. This also applies to review data: We evaluated LingScope and NegEx on 500 sentences that were randomly extracted from SPD v1.0 and annotated for their NSs. Table 5 shows the results: LingScope clearly outperforms NegEx with respect to precision and recall. So although BioScope's genre domain which LingScope and NegEx were trained and/or tested on di ers greatly from the genre and domains of MDSD v2.0 and SPD v1.0, models learned using LingScope yield the best or almost best results for all our SA subtasks.
Compared to ordinary word n-gram models that do not model negation (n = 1) or model negation only implicitly (2 n 3), word n-gram models that additionally model negation explicitly achieve statistically signi cant improvements|given an accurate NSD method.
To shed some light on the di erences between the evaluated subtasks' and gold standards' results, we analyze how many and what kind of NSs the NSD methods detect (cf. Table 6). Generally, LingScope detects more negations than NegEx. NSs detected by LingScope are on average shorter than those detected by NegEx, hence they are more precise. While LingScope and NegEx detect negations in about 67% of all documents in MDSD v2.0, only about 20% of all sentences in SPD v1.0 contain detected negations.
It is noteworthy that only very little NSs have length 1, i.e. span 1 word unigram, but many NSs have length 4 or longer, i.e. span 4 word unigrams or more. That con rms the need for explicit negation modeling as mentioned in Sect. 2.2, but also hints at a data sparsity problem: Parts of word n-grams in the scope of negations re-occur, but the same NS basically never appears twice. E.g., for MDSD v2.0 and LingScope as NSD, on average each NS overlaps only on 0.18 positions with each other NS. Thus, overlaps as shown in example (8) and (9), where \buy" appears in both NSs, are scarce: (8) Don't buy these shoes for running! (9) Do not buy them unless you like getting blisters.
The picture is similar for SPD v1.0 with an overlap in 0.22 positions on average.
For sentence-level polarity classi cation on SPD v1.0 our best performing model
(A = 78:01) outperforms 3 state-of-the-art models: [35]'s dependency tree-based
CRFs with hidden variables (A = 77:3), [
For in-domain document-level polarity classi cation on MDSD v2.0, [
For cross-domain document-level polarity classi cation on MDSD v2.0, our best performing model (IS, A = 76:76) is inferior compared to more complex domain adaptation methods, all of which are evaluated on 4 domains (dvd, books, electronics, kitchen), i.e. 12 domain pairs: [30]'s Structural Correspondence Learning (A = 77:97), [38]'s Spectral Feature Alignment (A = 78:75) and [39]'s graph-based RANK (A = 76:9), OPTIM-SOCAL (A = 76:78) and RANK-SOCAL (A = 80:12). It only outperforms [39]'s OPTIM (A = 75:3).
In summary, purely data-driven discriminative word n-gram models with negation modeling prove to be competitive in several common SA subtasks. 4
We conclude that data-driven ML-based models for SA that operate in word n-gram feature space bene t from explicit negation modeling. In turn, explicit negation modeling bene ts from (i) high quality NSD methods like LingScope and (ii) modeling not only negation of word unigrams, but also of higher order word n-grams, especially word bigrams.
These insights suggest that explicitly modeling semantic compositions is promising for data-driven ML-based SA. Given appropriate scope detection methods, our approach may for example easily be extended to model other valence shifters [40], e.g. intensi ers like \very" or \many", or hedges [41] like \may" or \might", or even implicit negation in the absence of negation words [42]. Our approach is also easily extensible to other word n-gram weighting schemes aside from encoding pure presence or absence, e.g. weighting using relative frequencies or tf-idf. The feature space then simply becomes X = R2d.
Future work encompasses model ne-tuning, e.g. accounting for NSs in the scope of other negations as in example (10) (10) I hdon't care that they are hnot really leatherii. and employing generalization methods to tackle data sparsity when learning the e ects of negations, modeled both implicitly and explicitly.
A special thank you goes to Stefan Bordag for the fruitful discussions we had. Additional thanks goes to the anonymous reviewers whose useful comments and suggestions considerably improved the original paper. 28. Noreen, E.W.: Computer Intensive Methods for Testing Hypothesis { An Introduction. John Wiley and Sons, Inc. (1989) 29. Yeh, A.: More accurate tests for the statistical signi cance of result di erences.
In: Proceedings of the 18th International Conference on Computational Linguistics (COLING). (2000) 947{953 30. Blitzer, J., Dredze, M., Pereira, F.C.: Biographies, bollywood, boom-boxes and blenders: Domain adaptation for sentiment classi cation. In: Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics (ACL). (2007) 440{447 31. Remus, R.: Domain adaptation using domain similarity- and domain complexitybased instance selection for cross-domain sentiment analysis. In: Proceedings of the 2012 IEEE 12th International Conference on Data Mining Workshops (ICDMW 2012) Workshop on Sentiment Elicitation from Natural Text for Information Retrieval and Extraction (SENTIRE). (2012) 717{723 32. Daume III, H., Kumar, A., Saha, A.: Frustratingly easy semi-supervised domain adaptation. In: Proceedings of the 2010 Workshop on Domain Adaptation for Natural Language Processing (DANLP). (2010) 53{59 33. Daume III, H., Kumar, A., Saha, A.: Co-regularization based semi-supervised domain adaptation. In: Proceedings of Neural Information Processing Systems (NIPS). (2010) 256{263 34. Pang, B., Lee, L.: Seeing stars: Exploiting class relationships for sentiment categorization with respect to rating scales. In: Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL). (2005) 115{124 35. Nakagawa, T., Inui, K., Kurohashi, S.: Dependency tree-based sentiment classication using crfs with hidden variables. In: Proccedings of the 2010 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technology. (2010) 786{794 36. Socher, R., Pennington, J., Huang, E.H., Ng, A.Y., Manning, C.D.: Semisupervised recursive autoencoders for predicting sentiment distributions. In: Proceedings of the 16th Conference on Empirical Methods in Natural Language Processing (EMNLP). (2011) 151{161 37. Wang, S., Manning, C.D.: Baselines and bigrams: Simple, good sentiment and topic classi cation. In: Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics (ACL). (2012) 90{94 38. Pan, S.J., Ni, X., Sun, J.T., Yang, Q., Chen, Z.: Cross-domain sentiment classication via spectral feature alignment. In: Proceedings of the 19th International Conference on World Wide Web (WWW). (2010) 751{760 39. Ponomareva, N., Thelwall, M.: Do neighbours help? an exploration of graph-based algorithms for cross-domain sentiment classi cation. In: Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing (EMNLP) and Computational Natural Language Learning (CoNLL). (2012) 655{665 40. Polanyi, L., Zaenen, A.: Contextual valence shifters. In Shanahan, J.G., Qu, Y., Wiebe, J., eds.: Computing Attitude and A ect in Text: Theory and Application. Volume 20 of The Information Retrieval Series. Computing Attitude and A ect in Text: Theory and Applications. Springer, Dordrecht (2006) 1{9 41. Lako , G.: Hedging: A study in media criteria and the logic of fuzzy concepts.
Journal of Philosophical Logic 2 (1973) 458{508 42. Reyes, A., Rosso, P.: On the di culty of automatically detecting irony: Beyond a simple case of negation. Knowledge and Information Systems (2013) 1{20