Elamur Research⌕
☰
home / papers / 2010 / Dependency Tree-based Sentiment Classification using CRFs with Hidden Variables

Dependency Tree-based Sentiment Classification using CRFs with Hidden Variables

Paper · 2010 · Tetsuji Nakagawa, Kentaro Inui and Sadao Kurohashi

Summary

The paper addresses sentence-level polarity classification (positive vs. negative) of subjective sentences in Japanese and English. Bag-of-words models handle this poorly because some words flip the polarity of the material they govern. For example, "prevents" turns a negative phrase about disease into a positive statement. The authors propose Tree-CRF, a conditional random field whose structure follows the syntactic dependency tree. Each phrase gets a latent polarity variable describing the subtree it heads, and a virtual root node carries the observed sentence label. The model combines node features (prior polarity from dictionaries, reversal cues, surface and base forms, POS) with edge features linking head and modifier polarities. Because the graph is a tree, sum-product belief propagation computes marginals exactly. Training uses MAP estimation with L-BFGS, with only sentence-level labels available. Across eight Japanese and English corpora, Tree-CRF beat voting-based and bag-of-features baselines. This shows that compositional, syntax-aware reasoning can be learned without phrase-level annotation.

Key points

  • Polarity is modelled for every dependency subtree, but only the root variable (s₀ = sentence polarity) is observed. All other variables stay hidden during training.
  • Inference is exact via sum-product belief propagation on the tree-shaped factor graph. Training maximises a non-convex MAP objective with a Gaussian prior (σ = 1.0) using L-BFGS, similar to Latent-Dynamic CRF training.
  • Features are split into node features (a)–(h) and edge features (A)–(E). The basic units are phrases rather than words; for English, phrases come from simple POS- and head-based merging rules.
  • Tree-CRF scored best on the evaluated corpora. Its margin over the runner-up was significant (paired t-test, p < 0.05) on six of eight corpora, and the gains were larger for Japanese than for English.
  • The Japanese polarity-reversing word dictionary was built semi-automatically from the ACP corpus (Kaji and Kitsuregawa, 2006), followed by manual checking.

Interesting ideas

  • I1. Latent intermediate labels: The model treats the polarity of each subtree as a hidden variable, so it can learn compositional behaviour using only sentence-level labels. The same trick could apply to other tasks where only the whole structure is annotated, such as document stance or toxicity.
  • I2. Exact inference by matching the graph to syntax: The model graph copies the dependency tree, so it has no loops and belief propagation gives exact marginals. This avoids approximate inference while keeping rich structure.
  • I3. Learning reversers instead of listing them: Edge features that pair opposite head/modifier polarities with the head's words picked up reversers such as "protect" and "withdraw", which were missing from the dictionary. This suggests that hand-built lexicons can serve as a seed while the model discovers more entries.
  • I4. Robustness to noisy lexicons: Error analysis showed that a baseline relying on dictionary votes broke on wrong lexicon entries. Tree-CRF stayed stable because prior polarity was only one of many features, which is a useful design lesson for low-resource languages with imperfect sentiment dictionaries.
  • I5. Mining a lexicon from mismatches: The reversal dictionary was built from sentences where a single polar phrase disagreed with the sentence label, and words in the governing head phrase were taken as candidates. This cheap mining method could bootstrap negator or shifter lists for new languages.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 1Research subjects and languages the work is about.Sentiment & emotion · 972 works

Cite

Cite as Tetsuji Nakagawa, Kentaro Inui and Sadao Kurohashi. 2010. Dependency Tree-based Sentiment Classification using CRFs with Hidden Variables. Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{nakagawa2010dependency,
  title = {{Dependency Tree-based Sentiment Classification using CRFs with Hidden Variables}},
  author = {Tetsuji Nakagawa, Kentaro Inui and Sadao Kurohashi},
  booktitle = {Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
  url = {https://aclanthology.org/N10-1120/}
}

References

21 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Alina Andreevskaia and Sabine Bergler. 2008. When Specialists and Generalists Work Together: Overcoming Domain Dependence in Sentiment Tagging. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 290–298. find
  2. Soumen Chakrabarti. 2002. Mining the Web: Discovering Knowledge from Hypertext Data. Morgan-Kauffman. find
  3. Yejin Choi and Claire Cardie. 2008. Learning with Compositional Semantics as Structural Inference for Subsentential Sentiment Analysis. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 793–801.
  4. Masahiko Higashiyama, Kentaro Inui, and Yuji Matsumoto. 2008. Acquiring Noun Polarity Knowledge Using Selectional Preferences. In Proceedings of the 14th Annual Meeting of the Association for Natural Language Processing, pages 584–587. (in Japanese). find
  5. Daisuke Ikeda, Hiroya Takamura, Lev-Arie Ratinov, and Manabu Okumura. 2008. Learning to Shift the Polarity of Words for Sentiment Classification. In Proceedings of the 3rd International Joint Conference on Natural Language Processing, pages 296–303. find
  6. Lifeng Jia, Clement Yu, and Weiyi Meng. 2009. The Effect of Negation on Sentiment Analysis and Retrieval Effectiveness. In Proceeding of the 18th ACM Conference on Information and Knowledge Management, pages 1827–1830. find
  7. Nobuhiro Kaji and Masaru Kitsuregawa. 2006. Automatic Construction of Polarity-Tagged Corpus from HTML Documents. In Proceedings of the COL-ING/ACL 2006 Main Conference Poster Sessions, pages 452–459. find
  8. Nozomi Kobayashi, Kentaro Inui, and Yuji Matsumoto. 2007. Opinion Mining from Web Documents: Extraction and Structurization. Journal of the Japanese Society for Artificial Intelligence, 22(2):227–238. find
  9. Dong C. Liu and Jorge Nocedal. 1989. On the limited memory BFGS method for large scale optimization. Mathematical Programming, 45(3):503–528. find
  10. David J. C. MacKay. 2003. Information Theory, Inference, and Learning Algorithms. Cambridge University Press. find
  11. Karo Moilanen and Stephen Pulman. 2007. Sentiment Composition. In Proceedings of the Recent Advances in Natural Language Processing International Conference, pages 378–382. find
  12. Louis-Philippe Morency, Ariadna Quattoni, and Trevor Darrell. 2007. Latent-Dynamic Discriminative Models for Continuous Gesture Recognition. In Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. find
  13. Tetsuji Nakagawa, Takuya Kawada, Kentaro Inui, and Sadao Kurohashi. 2008. Extracting Subjective and Objective Evaluative Expressions from the Web. In Proceedings of the 2nd International Symposium on Universal Communication. find
  14. Bo Pang and Lillian Lee. 2008. Opinion Mining and Sentiment Analysis. Foundations and Trends in Information Retrieval, 2(1-2):1–135. find
  15. Bo Pang, Lillian Lee, and Shivakumar Vaithyanathan. 2002. Thumbs up? Sentiment Classification using Machine Learning Techniques. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing, pages 79–86.
  16. Adwait Ratnaparkhi. 1996. A Maximum Entropy Model for Part-of-Speech Tagging. In Proceedings of the 1996 Conference on Empirical Methods in Natural Language Processing Conference, pages 133–142.
  17. Yohei Seki, David Kirk Evans, Lun-Wei Ku, Hsin-His Chen, Noriko Kando, and Chin-Yew Lin. 2007. Overview of Opinion Analysis Pilot Task at NTCIR-6. In Proceedings of the 6th NTCIR Workshop, pages 265–278. find
  18. Yohei Seki, David Kirk Evans, Lun-Wei Ku, Le Sun, Hsin-Hsi Chen, and Noriko Kando. 2008. Overview of Multilingual Opinion Analysis Task at NTCIR-7. In Proceedings of the 7th NTCIR Workshop. find
  19. Xu Sun, Louis-Philippe Morency, Daisuke Okanohara, and Jun’ichi Tsujii. 2008. Modeling Latent-Dynamic in Shallow Parsing: A Latent Conditional Model with Improved Inference. In Proceedings of the 22nd International Conference on Computational Linguistics, pages 841–848. find
  20. Theresa Wilson, Janyce Wiebe, and Paul Hoffmann. 2005. Recognizing Contextual Polarity in Phrase-Level Sentiment Analysis. In Proceedings of the 2005 Joint Conference on Human Language Technology and Empirical Methods in Natural Language Processing, pages 347–354.
  21. Livia Polanyi Annie Zaenen. 2004. Contextual Lexical Valence Shifters. In Proceedings of the AAAI Spring Symposium on Exploring Attitude and Affect in Text. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/nakagawa-2010-dependency-tree-based-sentiment-classification/