A Hierarchical Classifier Applied to Multi-way Sentiment Detection

Adrian Bickerstaffe, Ingrid ZukermanCOLING 2010

TL;DR

This paper introduces MCST-SVM, a novel hierarchical classifier that leverages inter-class similarity to improve multi-way sentiment detection. By organizing binary classifiers into a tree structure based on feature similarity, MCST-SVM effectively reduces feature dimensionality and training time while achieving state-of-the-art performance on movie review sentiment analysis.

What Problem Does This Paper Address?

Sentiment detection, the task of determining the emotional tone of text, has traditionally focused on binary (positive/negative) classification. However, many real-world scenarios involve more nuanced, ordinal rating scales (e.g., 1-star to 5-star reviews). Existing multi-way classification methods often treat each class independently, failing to exploit the inherent similarity between adjacent ratings (e.g., a 4-star review is more similar to a 3-star review than a 1-star review). This oversight can lead to suboptimal performance and inefficient models. Furthermore, traditional approaches often use a large set of features across all classes, increasing the risk of overfitting, especially with limited training data.

Methods

The core innovation is the MCST-SVM (Minimum Cost Spanning Tree Support Vector Machine) classifier. This approach builds a decision tree where each internal node contains a binary SVM trained to distinguish between two groups of classes. The structure of this tree is not predefined but is dynamically constructed using a Minimum Cost Spanning Tree (MCST) algorithm.

Here's how it works:

  1. Class Similarity Measurement: The algorithm first determines a "representative vector" for each sentiment class. This can be a centroid of feature vectors or a selected "typical" sample. The similarity between classes is then calculated using measures like Euclidean distance or the Tanimoto coefficient.
  2. Tree Construction: Kruskal's algorithm is used to build an MCST based on these inter-class similarities. This creates a tree structure where more similar classes are grouped closer together.
  3. Hierarchical Classification: Each internal node in the tree trains a binary SVM to differentiate between the classes in its left and right subtrees. This hierarchical decomposition allows the model to make progressively finer distinctions as it moves down the tree.
  4. Irrelevant Feature Culling: A significant advantage of this hierarchical structure is its ability to naturally reduce the feature space. At each internal node, the SVM only needs to consider features relevant to the classes it's differentiating, effectively culling irrelevant features from higher-level nodes.

Datasets

The experiments were conducted on the Sentiment Scale dataset (v1.0). This dataset comprises four sub-corpora, each containing movie reviews with associated 3-star and 4-star ratings. A key characteristic of this dataset is that each sub-corpus was written by a different author, which helps to mitigate author-specific biases and calibration issues. The review texts were pre-processed to include only subjective sentences.

Key Insights and Ideas

  • Inter-class similarity is crucial: Explicitly modeling the ordinal nature of sentiment ratings, rather than treating them as independent categories, leads to better performance.
  • Hierarchical structure as a feature selector: The tree-based approach naturally prunes irrelevant features at each decision node, combating the "curse of dimensionality" common in text classification.
  • Efficiency gains: By reducing the feature set and the number of required classifiers (k-1 SVMs for k classes), MCST-SVM significantly reduces training times and memory requirements.
  • Flexibility in similarity measures: The MCST-SVM framework is adaptable to different methods for calculating inter-class similarity, allowing for experimentation and optimization.

Key Results

  • Improved Accuracy: The MCST-SVM classifier achieved improvements of up to 7.00% and 7.72% for three-way and four-way classification problems, respectively, compared to state-of-the-art methods.
  • Significant Feature Reduction: Feature culling reduced the number of features used by non-root decision nodes by as much as 16.7%, leading to substantial memory savings.
  • Reduced Training Times: Node training times were also reduced by approximately 10% due to feature culling.
  • Competitive Performance: MCST-SVM was competitive with, and in some cases significantly outperformed, existing methods like OVA+PSP and REG+PSP from Pang and Lee (2005).

Limitations and Future Work

  • Dataset Specificity: While the Sentiment Scale dataset is valuable, future work could explore higher-discrimination datasets to further test the robustness of the approach.
  • Feature Engineering: The authors suggest incorporating improved negation tagging and part-of-speech tagging to enhance feature representation.
  • Overfitting Mitigation: Further research into different feature selection algorithms and their integration within the classifier trees is proposed to address overfitting.
  • Aspect-Based Analysis: The paper acknowledges that it doesn't currently consider different aspects of a review (e.g., service, food, ambiance), which is a planned future direction.
  • Alternative Similarity Measures: Exploring other methods for measuring class similarity, such as selecting typical instances, is also on the agenda.

Summary updated

BibTeX
@inproceedings{bickerstaffe2010hierarchical,
  author = {Adrian Bickerstaffe and Ingrid Zukerman},
  title = {{A Hierarchical Classifier Applied to Multi-way Sentiment Detection}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2010},
}
Figure