Elamur Research
☰
home / papers / 2014 / A Dependency Parser for Tweets

A Dependency Parser for Tweets

What it is about

Tweets break the assumptions of newswire parsers: many tokens (retweet markers, usernames, hashtags, URLs, punctuation) have no syntactic role, a tweet can hold several utterances with their own roots, and multiword names and idioms are common. The authors annotate 929 POS-tagged tweets (Tweebank, about 12,000 tokens) directly as dependencies, with a graph-fragment notation that lets annotators leave tokens unselected, group multiword expressions, and mark several roots. Their parser, TweeboParser, is a second-order TurboParser adapted to skip unselected tokens (they stay as features), to allow several roots on a wall symbol, and to use a Penn Treebank parser's arc scores as a stacking feature, with Brown clusters from tweets. On the new test set of 201 tweets the parser reaches 80.9 unlabeled F1, against 76.1 on an older Penn-style test set, and its ablations show that the parsing adaptations are worth 1.7 points and the Penn Treebank feature 0.7 points on the new test set (3.5 points on the Penn-style set).

Ideas

For Mova

Touches languages/en/38-dialogue-and-discourse-markers, 19-lexicon-mwe-register and 37-register-and-variation, and the en crate (parse.rs, morph.rs, ctx.rs), tools/treeagree and the multi-root rule of the mova dialect. Tweebank is non-commercial: test only. Measure first the effect of excluding punctuation arcs on EWT test, which costs little and tests the idea behind I1.

Library summary

The Research library's own summary of the paper, in our words — not the paper's text.

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/D14-1108.pdf

Summary

Off-the-shelf parsers trained on the Penn Treebank do poorly on tweets, and no syntactic parser built specifically for Twitter existed. The authors present TWEEBOPARSER, a dependency parser for English tweets, together with TWEEBANK, a new dependency corpus. They argue that Penn Treebank conventions fit edited news but not informal posts, so they designed annotation rules around tweet-specific problems:

  • tokens with no syntactic role (retweet markers, URLs, many hashtags, punctuation)
  • multiword expressions treated as single units
  • tweets that contain several independent utterances
  • richer structure inside noun phrases

Most of the annotation was done in a single day by about two dozen lightly trained annotators. On the modelling side, they adapted the graph-based TurboParser to handle unselected tokens and multiple roots. They also brought in Penn Treebank knowledge cheaply through stacking-style features rather than training directly on it. The parser exceeds 80% unlabeled attachment on the new test set. This shows that a small, fast, domain-aware annotation effort can beat a much larger out-of-domain treebank.

Key points

  • TWEEBANK corpus: 929 tweets (12,318 tokens) taken from the POS-tagged corpus of Owoputi et al. (2013), split roughly evenly between OCT27 and DAILY547. It was annotated with GFL-style graph fragments.
  • Token selection:
    • Annotators kept 75.6% of tokens as syntactically active.
    • A rule-based filter reproduces these choices with about 95% accuracy.
    • A first-order sequence model trained with the structured perceptron reaches 97.4%.
  • Main results: The parser scores 80.9% unlabeled attachment F1 on TEST-NEW and 76.1% on TEST-FOSTER. With gold POS tags and gold token selection, TEST-NEW rises to 83.2%.
  • Comparison with Penn Treebank training: A second-order TurboParser trained on 39,832 Penn Treebank sentences scores about 7.8 points lower on TEST-NEW. The tweet parser uses only 1,473 Twitter utterances.
  • Ablations:
    • The parsing adaptations add roughly 2–3 points.
    • Penn Treebank-derived features help on both test sets, especially TEST-FOSTER.
    • Brown cluster features did not give consistent gains with this small training set.

Interesting ideas

  • Explicit token selection: Annotators mark which tokens carry syntax, and the parser skips the rest instead of forcing arbitrary attachments. This saves annotation effort in any noisy genre (chats, forums, OCR output) where many tokens are decoration or metadata.
  • Reversible handling of multiword expressions: Annotators mark MWEs as flat units. An existing parser then fills in their internal structure, using a special arc label so the step can be undone. This keeps annotation simple while still letting you train a standard tree-based parser.
  • Multiple roots instead of sentence segmentation: Several utterances may attach to the root ("wall") symbol, so segmentation falls out of the parse itself. This is useful wherever sentence boundaries are unreliable, such as transcripts or messages.
  • Using a big out-of-domain treebank through features: Penn Treebank parser output is fed in as stacking-style features rather than as direct training data. The model can then rely on that outside knowledge only as much as it proves helpful, which is a cheap route for low-resource domains or languages.
  • Time-spread data sampling: Mixing tweets from one day with one random tweet per day over many months reduces overfitting to topics specific to a single event. This is worth copying when building any social-media dataset.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/v1/d14-1108

@inproceedings{kong2014dependency,
  title = {{A Dependency Parser for Tweets}},
  author = {Kong, Lingpeng and Schneider, Nathan and Swayamdipta, Swabha and Bhatia, Archna and Dyer, Chris and Smith, Noah A.},
  booktitle = {Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
  year = {2014},
  doi = {10.3115/v1/d14-1108},
  url = {https://doi.org/10.3115/v1/d14-1108}
}

References

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

  1. Anne Abeillé, Lionel Clément, and François Toussenel. 2003. Building a treebank for French. In Treebanks, pages 165–187. Springer. find
  2. Timonthy Baldwin and Su Nam Kim. 2010. Multiword expressions. In Handbook of Natural Language Processing, Second Edition. CRC Press, Taylor and Francis Group. find
  3. Adam Bermingham and Alan F. Smeaton. 2010. Classifying sentiment in microblogs: Is brevity an advantage? In Proc. of CIKM. find
  4. Ann Bies, Justin Mott, Colin Warner, and Seth Kulick. 2012. English Web Treebank. Technical Report LDC2012T13, Linguistic Data Consortium. URL http://www.ldc.upenn.edu/Catalog/catalogEntry.jsp?catalogId=LDC2012T13 . ↗
  5. Peter F Brown, Peter V Desouza, Robert L Mercer, Vincent J. Della Pietra, and Jenifer C. Lai. 1992. Class-based n-gram models of natural language. Computational Linguistics, 18(4):467–479. find
  6. Sabine Buchholz and Erwin Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proc. of CoNLL. find our card
  7. Marie Candito and Matthieu Constant. 2014. Strategies for contiguous multiword expression analysis and dependency parsing. In Proc. of ACL. find
  8. Xavier Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proc. of EMNLP-CoNLL. find
  9. Yoeng-Jin Chu and Tseng-Hong Liu. 1965. On shortest arborescence of a directed graph. Scientia Sinica, 14(10):1396. find
  10. Michael Collins. 2002. Discriminative training methods for Hidden Markov Models: theory and experiments with perceptron algorithms. In Proc. of EMNLP. find our card
  11. Matthieu Constant and Anthony Sigogne. 2011. MWU-aware part-of-speech tagging with a CRF model and lexical resources. In Proc. of the Workshop on Multiword Expressions: from Parsing and Generation to the Real World. find
  12. Matthieu Constant, Anthony Sigogne, and Patrick Watrin. 2012. Discriminative strategies to integrate multiword expression recognition and parsing. In Proc. of ACL. find
  13. Marie-Catherine de Marneffe and Christopher D. Manning. 2008. The Stanford typed dependencies representation. In Proc. of COLING Workshop on Cross-Framework and Cross-Domain Parser Evaluation. find our card
  14. Mark Dredze, John Blitzer, Partha Pratim Talukdar, Kuzman Ganchev, Joao Graca, and Fernando Pereira. 2007. Frustratingly hard domain adaptation for dependency parsing. In Proc. of EMNLP-CoNLL. find our card
  15. Jack Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards B, 71(233-240):160. find
  16. Jacob Eisenstein. 2013. What to do about bad language on the internet. In Proc. of NAACL-HLT. find
  17. Jason Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. of COLING. find our card
  18. Jakob Elming, Anders Johannsen, Sigrid Klerke, Emanuele Lapponi, Héctor Martínez Alonso, and Anders Søgaard. 2013. Down-stream effects of tree-to-dependency conversions. In Proc. of NAACL-HLT. find
  19. Jenny Rose Finkel and Christopher D. Manning. 2009. Joint parsing and named entity recognition. In Proc of ACL-HLT. find
  20. Jennifer Foster, Özlem Çetinoglu, Joachim Wagner, Joseph Le Roux, Stephen Hogan, Joakim Nivre, Deirdre Hogan, and Josef van Genabith. 2011a. #hardtoparse: POS tagging and parsing the Twitterverse. In Proc. of AAAI Workshop on Analyzing Microtext. find
  21. Jennifer Foster, Özlem Çetinoğlu, Joachim Wagner, Joseph Le Roux, Joakim Nivre, Deirdre Hogan, and Josef van Genabith. 2011b. From news to comment: resources and benchmarks for parsing the language of Web 2.0. In Proc. of IJCNLP. find
  22. Kevin Gimpel, Nathan Schneider, Brendan O’Connor, Dipanjan Das, Daniel Mills, Jacob Eisenstein, Michael Heilman, Dani Yogatama, Jeffrey Flanigan, and Noah A. Smith. 2011. Part-of-speech tagging for Twitter: annotation, features, and experiments. In Proc. of ACL-HLT. find
  23. Spence Green, Marie-Catherine de Marneffe, and Christopher D. Manning. 2012. Parsing models for identifying multiword expressions. Computational Linguistics, 39(1):195–227. find
  24. Stephan Greene and Philip Resnik. 2009. Syntactic packaging and implicit sentiment. In Proc. of NAACL. find
  25. Jan Hajič, Eva Hajičová, Jarmila Panevová, Petr Sgall, Silvie Cinková, Eva Fučíková, Marie Mikulová, Petr Pajas, Jan Popelka, Jiří Semeckỳ, Jana Šindlerová, Jan Štěpánek, Josef Toman, Zdeňka Urešová, and Zdeněk Žabokrtský. 2012. Prague Czech-English Dependency Treebank 2.0. Technical Report LDC2012T08, Linguistic Data Consortium. URL http://www.ldc.upenn.edu/Catalog/catalogEntry.jsp?catalogId=LDC2012T08 . ↗
  26. Rebecca Hwa. 2001. Learning Probabilistic Lexicalized Grammars for Natural Language Processing. Ph.D. thesis, Harvard University. find
  27. Richard Johansson. 2013. Training parsers on incompatible treebanks. In Proc. of NAACL-HLT. find
  28. Mark Johnson. 1998. PCFG models of linguistic tree representations. Computational Linguistics, 24(4):613–632. find our card
  29. Lingpeng Kong and Noah A. Smith. 2014. An empirical comparison of parsing methods for Stanford dependencies. ArXiv:1404.4314. ↗ our card
  30. Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple semi-supervised dependency parsing. In Proc. of ACL. find our card
  31. Terry Koo and Michael Collins. 2010. Efficient third-order dependency parsers. In Proc. of ACL. find
  32. Terry Koo, Alexander M. Rush, Michael Collins, Tommi Jaakkola, and David Sontag. 2010. Dual decomposition for parsing with non-projective head automata. In Proc. of EMNLP. find
  33. Efthymios Kouloumpis, Theresa Wilson, and Johanna Moore. 2011. Twitter sentiment analysis: The good the bad and the OMG! In Proc. of ICWSM. find
  34. Joseph Le Roux, Matthieu Constant, and Antoine Rozenknop. 2014. Syntactic parsing and compound recognition via dual decomposition: application to French. In Proc. of COLING. find
  35. Ji Ma, Yue Zhang, and Jingbo Zhu. 2014. Punctuation processing for projective dependency parsing. In Proc. of ACL. find
  36. Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational linguistics, 19(2):313–330. find our card
  37. André F.T. Martins, Miguel Almeida, and Noah A. Smith. 2013. Turning on the turbo: Fast third-order non-projective turbo parsers. In Proc. of ACL. find our card
  38. André F.T. Martins, Dipanjan Das, Noah A. Smith, and Eric P. Xing. 2008. Stacking dependency parsers. In Proc. of EMNLP. find
  39. André F.T. Martins, Noah A. Smith, Pedro M.Q. Aguiar, and Mário A.T. Figueiredo. 2011. Dual decomposition with many overlapping components. In Proc. of EMNLP. find
  40. André F.T. Martins, Noah A. Smith, and Eric P. Xing. 2009. Concise integer linear programming formulations for dependency parsing. In Proc. of ACL-IJCNLP. find
  41. André F.T. Martins, Noah A. Smith, Eric P. Xing, Pedro M.Q. Aguiar, and Mário A.T. Figueiredo. 2010. Turbo parsers: Dependency parsing by approximate variational inference. In Proc. of EMNLP. find
  42. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005a. Online large-margin training of dependency parsers. In Proc. of ACL. find our card
  43. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005b. Non-projective dependency parsing using spanning tree algorithms. In Proc. of HLT-EMNLP. find our card
  44. Ryan McDonald and Giorgio Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proc. of IWPT. Michael T. Mordowanec, Nathan Schneider, Chris. find
  45. Dyer, and Noah A. Smith. 2014. Simplified dependency annotations with GFL-Web. In Proc. of ACL, demonstration track. find
  46. Joakim Nivre and Ryan McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In Proc. of ACL-HLT. find
  47. Olutobi Owoputi, Brendan O’Connor, Chris Dyer, Kevin Gimpel, Nathan Schneider, and Noah A. Smith. 2013. Improved part-of-speech tagging for online conversational text with word clusters. In Proc. of NAACL-HLT. find our card
  48. Fernando Pereira and Yves Schabes. 1992. Inside-outside reestimation from partially bracketed corpora. In Proc. of ACL. find
  49. Slav Petrov and Ryan McDonald. 2012. Overview of the 2012 Shared Task on Parsing the Web. In Notes of the First Workshop on Syntactic Analysis of Non-Canonical Language. find
  50. Jeffrey C. Reynar and Adwait Ratnaparkhi. 1997. A maximum entropy approach to identifying sentence boundaries. In Proc. of ANLP. find
  51. Sebastian Riedel and James Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proc. of EMNLP. find
  52. Alan Ritter, Sam Clark, Mausam, and Oren Etzioni. 2011. Named entity recognition in tweets: an experimental study. In Proc. of EMNLP. find
  53. Ivan A. Sag, Timothy Baldwin, Francis Bond, Ann Copestake, and Dan Flickinger. 2002. Multiword expressions: A pain in the neck for NLP. In Proc. of CICLing. find our card
  54. Nathan Schneider, Emily Danchik, Chris Dyer, and Noah A. Smith. 2014. Discriminative lexical semantic segmentation with gaps: Running the MWE gamut. Transactions of the Association for Computational Linguistics, 2:193–206. find
  55. Nathan Schneider, Brendan O’Connor, Naomi Saphra, David Bamman, Manaal Faruqui, Noah A. Smith, Chris Dyer, and Jason Baldridge. 2013. A framework for (under)specifying dependency syntax without overloading annotators. In Proc. of the 7th Linguistic Annotation Workshop and Interoperability with Discourse. find
  56. David A. Smith and Jason Eisner. 2008. Dependency parsing by belief propagation. In Proc. of EMNLP. find
  57. Sandeep Soni, Tanushree Mitra, Eric Gilbert, and Jacob Eisenstein. 2014. Modeling factuality judgments in social media text. In Proc. of ACL. find
  58. Joseph Turian, Lev Ratinov, and Yoshua Bengio. 2010. Word representations: a simple and general method for semi-supervised learning. In Proc. of ACL. find our card
  59. David Vadas and James Curran. 2007. Adding noun phrase structure to the Penn Treebank. In Proc. of ACL. find our card
  60. Eva Maria Vecchi, Roberto Zamparelli, and Marco Baroni. 2013. Studying the recursive behaviour of adjectival modification with compositional distributional semantics. In Proc. of EMNLP. find
  61. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. of IWPT. find our card