Sentiment Classification using Automatically Extracted Subgraph Features

Proceedings of the NAACL HLT 2010 Workshop on Computational Approaches to Analysis and Generation of Emotion in Text, pages 131–139, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Sentiment Classification using Automatically Extracted Subgraph Features Shilpa Arora, Elijah Mayfield, Carolyn Penstein-Ros´e and Eric Nyberg Language Technologies Institute Carnegie Mellon University 5000 Forbes Avenue, Pittsburgh, PA 15213 {shilpaa, emayfiel, cprose, ehn}@cs.cmu.edu Abstract In this work, we propose a novel representa- tion of text based on patterns derived from lin- guistic annotation graphs. We use a subgraph mining algorithm to automatically derive fea- tures as frequent subgraphs from the annota- tion graph. This process generates a very large number of features, many of which are highly correlated. We propose a genetic program- ming based approach to feature construction which creates a fixed number of strong classi- fication predictors from these subgraphs. We evaluate the benefit gained from evolved struc- tured features, when used in addition to the bag-of-words features, for a sentiment classi- fication task. 1 Introduction In recent years, the topic of sentiment analysis has been one of the more popular directions in the field of language technologies. Recent work in super- vised sentiment analysis has focused on innovative approaches to feature creation, with the greatest im- provements in performance with features that in- sightfully capture the essence of the linguistic con- structions used to express sentiment, e.g. (Wilson et al., 2004), (Joshi and Ros´e, 2009) In this spirit, we present a novel approach that leverages subgraphs automatically extracted from linguistic annotation graphs using efficient subgraph mining algorithms (Yan and Han, 2002). The diffi- culty with automatically deriving complex features comes with the increased feature space size. Many of these features are highly correlated and do not provide any new information to the model. For ex- ample, a feature of type unigram POS (e.g. “cam- era NN”) doesn’t provide any additional informa- tion beyond the unigram feature (e.g. “camera”), for words that are often used with the same part of speech. However, alongside several redundant fea- tures, there are also features that provide new infor- mation. It is these features that we aim to capture. In this work, we propose an evolutionary ap- proach that constructs complex features from sub- graphs extracted from an annotation graph. A con- stant number of these features are added to the un- igram feature space, adding much of the represen- tational benefits without the computational cost of a drastic increase in feature space size. In the remainder of the paper, we review prior work on features commonly used for sentiment anal- ysis. We then describe the annotation graph rep- resentation proposed by Arora and Nyberg (2009). Following this, we describe the frequent subgraph mining algorithm proposed in Yan and Han (2002), and used in this work to extract frequent subgraphs from the annotation graphs. We then introduce our novel feature evolution approach, and discuss our experimental setup and results. Subgraph features combined with the feature evolution approach gives promising results, with an improvement …

Content truncated to 500 words