Elamur Research⌕
☰
home / papers / 2014 / A Discriminative Graph-Based Parser for the Abstract Meaning Representation

A Discriminative Graph-Based Parser for the Abstract Meaning Representation

Summary

The authors present JAMR, the first published system that automatically converts English sentences into Abstract Meaning Representation (AMR) graphs. In such a graph, vertices denote concepts, and labeled directed edges denote semantic relations between them. Parsing proceeds in two stages. First, a semi-Markov model segments the sentence into spans and maps each span to a concept graph fragment or to a null value. Then the system searches for the connected subgraph with the maximum total edge weight. For this purpose, the authors proposed a new algorithm, MSCG, similar to MST approaches in dependency parsing. The system enforces the constraint that a predicate has at most one argument of each type through Lagrangian relaxation. Both stages are discriminatively trained linear models with features derived from POS tagging, NER and syntactic parsing. They are trained on the AMR Bank corpus, in which words and concepts are aligned automatically. The full system achieves 58% F1 on the Smatch metric. This is the first baseline for subsequent AMR parsers, and the system's code is open.

Key points

  • JAMR is distributed as open source on GitHub (jflanigan/jamr). Quality was evaluated with the Smatch v1.0 metric on the AMR Bank corpus.
  • The concept identification stage achieves 84% F1 on the test data. About 20% of fragments consist of multiple nodes, and the algorithm runs in O(n²) time.
  • The MSCG algorithm has a complexity of O(|V|² log |V|). The graph must satisfy four conditions: it must preserve the concept fragments (preserving), be simple (simple), connected (connected), and deterministic with respect to the labels ARG0–ARG5. In the experiments, Lagrangian relaxation always converged.
  • With automatically identified concepts, the system achieves 58% F1 on Smatch, and with gold concepts, 80% F1. For comparison, inter-annotator agreement is 83%. The 22-point gap suggests that the two stages should be trained jointly.
  • Graph acyclicity was not explicitly required, yet the system produced no cycles on the test data. Sentences of up to 40 words are processed in less than 0.5 s.

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: Linguistics & languages · Machine translation

Topics Semantic parsing & meaning representation

Institutions

🎓Carnegie Mellon UniversityPittsburgh · United States278 works · 138,810 citations

Cite

Cite as Jeffrey Flanigan, Sam Thomson, Jaime Carbonell, Chris Dyer and Noah A. Smith. 2014. A Discriminative Graph-Based Parser for the Abstract Meaning Representation. Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.3115/v1/p14-1134

@inproceedings{flanigan2014discriminative,
  title = {{A Discriminative Graph-Based Parser for the Abstract Meaning Representation}},
  author = {Jeffrey Flanigan, Sam Thomson, Jaime Carbonell, Chris Dyer and Noah A. Smith},
  booktitle = {Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2014},
  doi = {10.3115/v1/p14-1134},
  url = {https://doi.org/10.3115/v1/p14-1134}
}

References

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

  1. Hiyan Alshawi, Pi-Chuan Chang, and Michael Ringgaard. 2011. Deterministic statistical mapping of sentences to underspecified semantics. In Proc. of ICWS. find
  2. Galen Andrew. 2006. A hybrid markov/semi-markov conditional random field for sequence segmentation. In Proc. of EMNLP. find
  3. Laura Banarescu, Claire Bonial, Shu Cai, Madalina Georgescu, Kira Griffitt, Ulf Hermjakob, Kevin Knight, Philipp Koehn, Martha Palmer, and Nathan Schneider. 2013. Abstract meaning representation for sembanking. In Proc. of the Linguistic Annotation Workshop and Interoperability with Discourse. our card
  4. Shu Cai and Kevin Knight. 2013. Smatch: an evaluation metric for semantic feature structures. In Proc. of ACL. find
  5. Jaime G. Carbonell, Teruko Mitamura, and Eric H. Nyberg. 1992. The KANT perspective: A critique of pure transfer (and pure interlingua, pure transfer, . . . ). In Proc. of the Fourth International Conference on Theoretical and Methodological Issues in Machine Translation: Empiricist vs. Rationalist Methods in MT. find
  6. David Chiang, Jacob Andreas, Daniel Bauer, Karl Moritz Hermann, Bevan Jones, and Kevin Knight. 2013. Parsing graphs with hyperedge replacement grammars. In Proc. of ACL. find
  7. Y. J. Chu and T. H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396– 1400. find
  8. Michael Collins. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proc. of EMNLP. our card
  9. Dipanjan Das, André F. T. Martins, and Noah A. Smith. 2012. An exact dual decomposition algorithm for shallow semantic parsing with constraints. In Proc. of the Joint Conference on Lexical and Computational Semantics. find
  10. Dipanjan Das, Desai Chen, André F. T. Martins, Nathan Schneider, and Noah A. Smith. 2014. Frame-semantic parsing. Computational Linguistics, 40(1):9–56. our card
  11. Donald Davidson. 1967. The logical form of action sentences. In Nicholas Rescher, editor, The Logic of Decision and Action, pages 81–120. Univ. of Pittsburgh Press. find
  12. Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In Proc. of LREC. our card
  13. Bonnie Dorr, Nizar Habash, and David Traum. 1998. A thematic hierarchy for efficient generation from lexical-conceptual structure. In David Farwell, Laurie Gerber, and Eduard Hovy, editors, Machine Translation and the Information Soup: Proc. of AMTA. find
  14. Frank Drewes, Hans-Jörg Kreowski, and Annegret Habel. 1997. Hyperedge replacement graph grammars. In Handbook of Graph Grammars, pages 95– 162. World Scientific. find
  15. John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121–2159, July. find
  16. Jack Edmonds. 1967. Optimum branchings. National Bureau of Standards. find
  17. Marshall L. Fisher. 2004. The Lagrangian relaxation method for solving integer programming problems. Management Science, 50(12):1861–1871. find
  18. Arthur M Geoffrion. 1974. Lagrangean relaxation for integer programming. Springer. find
  19. Daniel Gildea and Daniel Jurafsky. 2002. Automatic labeling of semantic roles. Computational Linguistics, 28(3):245–288. ↗ our card
  20. Jacques Janssen and Nikolaos Limnios. 1999. Semi-Markov Models and Applications. Springer, October. find
  21. Bevan Jones, Jacob Andreas, Daniel Bauer, Karl Moritz Hermann, and Kevin Knight. 2012. Semantics-based machine translation with hyperedge replacement grammars. In Proc. of COLING. our card
  22. Rohit J. Kate, Yuk Wah Wong, and Raymond J. Mooney. 2005. Learning to transform natural to formal languages. In Proc. of AAAI. find
  23. Dan Klein and Christopher D. Manning. 2003. Accurate unlexicalized parsing. In Proc. of ACL. our card
  24. Joseph B. Kruskal. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. of the American Mathematical Society, 7(1):48. find
  25. Tom Kwiatkowski, Luke Zettlemoyer, Sharon Goldwater, and Mark Steedman. 2010. Inducing probabilistic CCG grammars from logical form with higher-order unification. In Proc. of EMNLP. find
  26. Percy Liang, Michael I. Jordan, and Dan Klein. 2011. Learning dependency-based compositional semantics. In Proc. of ACL. find
  27. André F. T. Martins, Noah A. Smith, and Eric P. Xing. 2009. Concise integer linear programming formulations for dependency parsing. In Proc. of ACL. find
  28. 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
  29. 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. our card
  30. Ryan Mcdonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proc. of EACL, page 81–88. our card
  31. Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proc. of EMNLP. our card
  32. Terence Parsons. 1990. Events in the Semantics of English: A study in subatomic semantics. MIT Press. find
  33. Robert C. Prim. 1957. Shortest connection networks and some generalizations. Bell System Technology Journal, 36:1389–1401. find
  34. Vasin Punyakanok, Dan Roth, and Wen-tau Yih. 2008. The importance of syntactic parsing and inference in semantic role labeling. Computational Linguistics, 34(2):257–287. our card
  35. Lev Ratinov and Dan Roth. 2009. Design challenges and misconceptions in named entity recognition. In Proc. of CoNLL. our card
  36. Sebastian Riedel and James Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proc. of EMNLP. find
  37. Frank Rosenblatt. 1957. The perceptron–a perceiving and recognizing automaton. Technical Report 85-460-1, Cornell Aeronautical Laboratory. find
  38. Alexander M. Rush and Michael Collins. 2012. A tutorial on dual decomposition and Lagrangian relaxation for inference in natural language processing. Journal of Artificial Intelligence Research, 45(1):305—-362. find
  39. Mark Steedman. 1996. Surface structure and interpretation. Linguistic inquiry monographs. MIT Press. find
  40. John M. Zelle and Raymond J. Mooney. 1996. Learning to parse database queries using inductive logic programming. In Proc. of AAAI. our card
  41. Luke S. Zettlemoyer and Michael Collins. 2005. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proc. of UAI. our card
  42. Luke S. Zettlemoyer and Michael Collins. 2007. Online learning of relaxed CCG grammars for parsing to logical form. In In Proc. of EMNLP-CoNLL. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/flanigan-2014-discriminative-graph-based-parser-abstract/