Elamur Research⌕
☰
home / papers / 2013 / Ubertagging: Joint Segmentation and Supertagging for English

Ubertagging: Joint Segmentation and Supertagging for English

Paper · 2013 · Rebecca Dridan

Summary

The English Resource Grammar (ERG) is a hand-built HPSG grammar with a highly ambiguous lexicon. That lexicon includes multi-token entries ("words-with-spaces") such as all of a sudden or for example, so the input segmentation into meaning-bearing units is itself ambiguous, and parsing is slow. Earlier ERG supertagging work either assumed gold tokenisation or forced multi-token tags onto single tokens through heuristics such as ditto tags or copied tags.

Dridan instead tags directly over the lattice of candidate lexical items (lexitems) produced by the PET parser's lexical stage. One sequence model chooses the segmentation and the fine-grained supertags together, a process she calls ubertagging. Three tag granularities were compared: lexical types alone (LTYPE), types plus inflection (INFL), and full lexitems (FULL). The model was trained on DeepBank 1.0, Redwoods and automatically parsed NANC text.

Unlikely lexitems are pruned before syntactic parsing. This gives roughly 4–8× potential speedups and also raises parser accuracy, including out of domain. The result is the first heuristic-free, fully integrated supertagging setup for the ERG.

Key points

  • Data:

    • Training used DeepBank 1.0 (an HPSG annotation of the WSJ/PTB text, Sections 00–19), Redwoods training portions, and the parsed but unannotated WSJ part of NANC.
    • Section 20 served as the development set and WSJ 21 as the test set.
    • Two extra test sets came from Redwoods: WeScience 13 (Wikipedia) and CatB (an open-source essay, out of domain).

  • Pipeline: The ubertagger sits in PET between lexical parsing and syntactic parsing. It removes low-probability lexitems according to a threshold ρ.

  • Chosen configuration: INFL with ρ = 0.001.

    • INFL was slightly less accurate than FULL as a standalone tagger, but it gave better parse F1 at every efficiency level.
    • On the development set it brought +1.75 F1 in 27% of the parsing time.

  • Test results (labelled bracket F1, seconds per sentence):

    Test setUnpruned F1 / timePruned F1 / time
    WSJ 2188.12 / 6.0689.93 / 1.77
    WeScience 1386.25 / 4.0987.14 / 1.48
    CatB86.31 / 5.0087.11 / 1.78

  • Related setups: Earlier systems used tag sets of the following sizes:

    • about 300 LTAG trees;
    • 425 CCG categories (C&C);
    • 1361 ENJU tags;
    • up to 2392 ALPINO tags;
    • just over 1000 ERG lexical types.

Interesting ideas

  • I1. Treat segmentation and tagging as one decision by scoring paths through a lattice of candidate multi-token units, rather than fixing tokens first and patching multiword expressions with ditto-style tags.
  • I2. Prune candidates before the expensive stage instead of committing to a single tag, using a probability threshold tuned for "maximum speed without hurting accuracy". This can raise accuracy, because the downstream search no longer runs out of resources.
  • I3. Choose tag granularity by the downstream metric, not by isolated tagger accuracy. The slightly weaker INFL tagger produced better parses than FULL.
  • I4. Uncorrected output of a constraint-heavy parser is good training data for a sequence tagger, because the grammar forces the sequences to be at least well-formed.
  • I5. Tagging errors were traced back to inconsistencies in the grammar and treebank, which were then reported to the developers.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (tokens): The en tagger could take a lattice of candidate fixed expressions such as as well or for example and pick the segmentation and tag jointly, keeping the rejected alternatives inspectable.
  • I2 (tree): The perceptron parser or gparse could receive a threshold-pruned set of lexical analyses per token, with ρ chosen on dev data by plotting F1 against time.
  • I3 (learn): Evaluation of the tagger should report end-to-end parse and frame accuracy, so that a tag-set change is accepted only if downstream stages improve.
  • I4 (learn): Silver data agreed by the witness parsers can be filtered by grammatical well-formedness checks and used in bulk to train the en tagger.
  • I5 (learn): Systematic tagger disagreements on silver data could be clustered and turned into candidate repair rules, or into flags on the treebank and UD dialect conversion.

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

 Institutions

🎓University of OsloOslo · Norway51 works · 4,155 citations

 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 2Research subjects and languages the work is about.English · 2,263 worksSyntax & grammar formalisms · 214 works

Cite

Cite as Rebecca Dridan. 2013. Ubertagging: Joint Segmentation and Supertagging for English. Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing.

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

@inproceedings{dridan2013ubertagging,
  title = {{Ubertagging: Joint Segmentation and Supertagging for English}},
  author = {Rebecca Dridan},
  booktitle = {Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing},
  year = {2013},
  doi = {10.18653/v1/d13-1120},
  url = {https://doi.org/10.18653/v1/d13-1120}
}

References

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

  1. Srinivas Bangalore and Aravind K. Joshi. 1999. Supertagging: an approach to almost parsing. Computational Linguistics, 25(2):237 – 265.
  2. Srinavas Bangalore and Aravind Joshi, editors. 2010. Supertagging: Using Complex Lexical Descriptions in Natural Language Processing. The MIT Press, Cambridge, US. find
  3. Ezra Black, Steve Abney, Dan Flickinger, Claudia Gdaniec, Ralph Grishman, Phil Harrison, Don Hindle, Robert Ingria, Fred Jelinek, Judith Klavans, Mark Liberman, Mitch Marcus, S. Roukos, Beatrice Santorini, and Tomek Strzalkowski. 1991. A procedure for quantitatively comparing the syntactic coverage of English grammars. In Proceedings of the Workshop on Speech and Natural Language, page 306 – 311, Pacific Grove, USA. find
  4. Philip Blunsom. 2007. Structured Classification for Multilingual Natural Language Processing. Ph.D. thesis, Department of Computer Science and Software Engineering, University of Melbourne. find
  5. Thorsten Brants. 2000. TnT — a statistical part-of-speech tagger. In Proceedings of the Sixth Conference on Applied Natural Language Processing ANLP-2000, page 224 – 231, Seattle, USA. ↗
  6. Ulrich Callmeier. 2000. PET. A platform for experimentation with efficient HPSG processing techniques. Natural Language Engineering, 6(1):99 – 108, March. find
  7. Stephen Clark and James R. Curran. 2007. Formalism-independent parser evaluation with CCG and Dep-Bank. In Proceedings of the 45th Meeting of the Association for Computational Linguistics, page 248 – 255, Prague, Czech Republic. find
  8. Rebecca Dridan and Stephan Oepen. 2012. Tokenization. Returning to a long solved problem. A survey, contrastive experiment, recommendations, and toolkit. In Proceedings of the 50th Meeting of the Association for Computational Linguistics, page 378 – 382, Jeju, Republic of Korea, July.
  9. Rebecca Dridan, Valia Kordoni, and Jeremy Nicholson. 2008. Enhancing performance of lexicalised grammars. page 613 – 621. find
  10. Rebecca Dridan. 2009. Using lexical statistics to improve HPSG parsing. Ph.D. thesis, Department of Computational Linguistics, Saarland University. find
  11. Murhaf Fares, Stephan Oepen, and Yi Zhang. 2013. Machine learning for high-quality tokenization. Replicating variable tokenization schemes. In Computational Linguistics and Intelligent Text Processing, page 231 – 244. Springer. find
  12. Murhaf Fares. 2013. ERG tokenization and lexical categorization: a sequence labeling approach. Master’s thesis, Department of Informatics, University of Oslo. find
  13. Dan Flickinger, Yi Zhang, and Valia Kordoni. 2012. DeepBank. A dynamically annotated treebank of the Wall Street Journal. In Proceedings of the 11th International Workshop on Treebanks and Linguistic Theories, page 85 – 96, Lisbon, Portugal. Edições Colibri. find
  14. Dan Flickinger. 2000. On building a more efficient grammar by exploiting types. Natural Language Engineering, 6 (1):15 – 28.
  15. Taku Kudo, Kaoru Yamamoto, and Yuji Matsumoto. 2004. Applying conditional random fields to japanese morphological analysis. In Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, page 230 – 237.
  16. Jonathan K. Kummerfeld, Jessika Roesner, Tim Daw-born, James Haggerty, James R. Curran, and Stephen Clark. 2010. Faster parsing by supertagger adaptation. In Proceedings of the 48th Meeting of the Association for Computational Linguistics, page 345 – 355, Uppsala, Sweden. find
  17. Mitchell Marcus, Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpora of English: The Penn Treebank. Computational Linguistics, 19:313 – 330. find
  18. Takuya Matsuzaki, Yusuke Miyao, and Jun’ichi Tsujii. 2007. Efficient HPSG parsing with supertagging and CFG-filtering. In Proceedings of the International Joint Conference on Artificial Intelligence (IJ-CAI 2007), page 1671 – 1676, Hyderabad, India. find
  19. Kevin P. Murphy. 2002. Hidden semi-Markov models (HSMMs). find
  20. Stephan Oepen and John Carroll. 2000. Ambiguity packing in constraint-based parsing. Practical results. In Proceedings of the 1st Meeting of the North American Chapter of the Association for Computational Linguistics, page 162 – 169, Seattle, WA, USA. find
  21. Stephan Oepen, Daniel Flickinger, Kristina Toutanova, and Christopher D. Manning. 2004. LinGO Redwoods. A rich and dynamic treebank for HPSG. Research on Language and Computation, 2(4):575 – 596.
  22. Robbert Prins and Gertjan van Noord. 2003. Reinforcing parser preferences through tagging. Traitement Automatique des Langues, 44(3):121 – 139. find
  23. Laura Rimell and Stephen Clark. 2008. Adapting a lexicalized-grammar parser to contrasting domains. page 475 – 484. find
  24. Kristina Toutanova and Colin Cherry. 2009. A global model for joint lemmatization and part-of-speech prediction. In Proceedings of the 47th Meeting of the Association for Computational Linguistics, page 486 – 494, Singapore.
  25. Gisle Ytrestøl. 2012. Transition-based Parsing for Large-scale Head-Driven Phrase Structure Grammars. Ph.D. thesis, Department of Informatics, University of Oslo. find
  26. Gisle Ytrestøl, Stephan Oepen, and Dan Flickinger. 2009. Extracting and annotating Wikipedia subdomains. In Proceedings of the 7th International Workshop on Treebanks and Linguistic Theories, page 185 – 197, Groningen, The Netherlands. find
  27. Yue Zhang and Stephen Clark. 2010. A fast decoder for joint word segmentation and POS-tagging using a single discriminative model. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, page 843 – 852, Cambridge, MA, USA. find
  28. Yi Zhang, Stephan Oepen, and John Carroll. 2007. Efficiency in unification-based n-best parsing. In Proceedings of the 10th International Conference on Parsing Technologies, page 48 – 59, Prague, Czech Republic, July. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/dridan-2013-ubertagging-joint-segmentation-supertagging-english/