Elamur Research⌕
☰
home / papers / 2008 / A Generative Model for Parsing Natural Language to Meaning Representations

A Generative Model for Parsing Natural Language to Meaning Representations

Paper · 2008 · Wei Lu, Hwee Tou Ng, Wee Sun Lee et al.

Summary

This EMNLP 2008 paper by Wei Lu, Hwee Tou Ng, Wee Sun Lee and Luke S. Zettlemoyer addresses semantic parsing: mapping a sentence to a variable-free, tree-shaped meaning representation (MR). Earlier systems learn one explicit grammar with a fixed set of lexical entries and rules, so they can fail on test sentences that the grammar does not cover. The authors drop the explicit grammar. Instead, a generative model jointly produces the sentence and its MR as a single "hybrid tree", whose nodes mix MR productions and natural-language words. Each level of the tree is generated by a Markov process, in the spirit of Collins' parsing models. Training data contain no word-to-meaning alignments, so these are treated as hidden variables and learned with an inside-outside style dynamic program. The learned model scores the correct meaning highly, but not always first, so a discriminative reranker selects an answer from a k-best list. On GEOQUERY and ROBOCUP the combined system matches or beats SILT, WASP and KRISP. Its main advantage is recall, which reflects graceful degradation on inputs unlike the training data.

Key points

  • Inference and training run in O(n³m) time, with n denoting the number of words in the sentence and m the size of the MR structure.
  • Three variants differ in how much context word emission uses:
    • Model I (unigram) conditions only on the parent production and tends to favour recall.
    • Model II (bigram) also conditions on the previous token and tends to favour precision.
    • Model III interpolates the two.
  • The best system, Model III with reranking, scores as follows:
    • GEOQUERY (880 examples): precision 89.3, recall 81.5, F 85.2.
    • ROBOCUP (300 examples): precision 82.5, recall 67.7, F 74.4.
    • Both F-scores are the highest among the directly comparable systems.
  • On GEOQUERY, recall rises by 6.7 points absolute over WASP and 9.8 over KRISP. F rises by 4.1 points over KRISP, which is about a 22% error reduction.
  • On GEOQUERY-250 annotated in English, Spanish, Japanese and Turkish, results are on par with WASP. The largest gain is in Spanish (F 86.46 vs. 81.03).

Interesting ideas

  • I1. Hybrid tree as an implicit grammar. Interleaving words and meaning tokens in one tree, generated by per-level Markov processes, avoids committing to a finite rule set. This could help any structured-prediction task where a learned grammar would miss rules needed at test time.
  • I2. Binarization plus pattern inventory. Each production is limited to at most two child categories, and the model explicitly lists the allowed word/child orderings, including swapped child order. This keeps dynamic programming tractable while still allowing word-order differences, which is useful for cross-lingual or free-word-order data such as Ukrainian.
  • I3. Context size as a precision/recall dial. Less context generalizes and boosts recall, while more context sharpens precision. Interpolating the two, then reranking, is a cheap and reusable recipe for low-resource models.
  • I4. Generative k-best with a discriminative reranker. The paper observes that the correct parse is often in the k-best list but not at the top. This motivates pairing a broad-coverage generative model with a reranker, a pattern that transfers to many parsing and generation pipelines.

For Mova

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

  • Task-appropriate correctness checks. - GEOQUERY counts an MR as correct if running it on the Prolog database returns the same answers as the reference. - ROBOCUP uses string matching that ignores the order of children under commutative operators such as and/or. Both checks measure meaning rather than surface form, which is a good template for evaluating semantic outputs.

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

🎓Massachusetts Institute of TechnologyCambridge · United States159 works · 65,157 citations🎓National University of SingaporeSingapore · Singapore84 works · 32,204 citations🔬MIT Computer Science and Artificial Intelligence LaboratoryCambridge · United States54 works · 29,441 citations

📚 Shelves 4 Computer Science · 9,086 works Artificial Intelligence · 8,889 works Arts and Humanities · 9,296 works Language and Linguistics · 9,206 works

🧭 Topics 1 Semantic parsing & meaning representation · 135 works

Cite

Cite as Wei Lu, Hwee Tou Ng, Wee Sun Lee and Luke S. Zettlemoyer. 2008. A Generative Model for Parsing Natural Language to Meaning Representations. Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing.

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

@inproceedings{lu2008generative,
  title = {{A Generative Model for Parsing Natural Language to Meaning Representations}},
  author = {Wei Lu, Hwee Tou Ng, Wee Sun Lee and Luke S. Zettlemoyer},
  booktitle = {Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  doi = {10.3115/1613715.1613815},
  url = {https://doi.org/10.3115/1613715.1613815}
}

References

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

  1. J. K. Baker. 1979. Trainable grammars for speech recognition. Journal of the Acoustical Society of America, 65:S132. find
  2. P. F. Brown, S. A. D. Pietra, V. J. D. Pietra, and R. L. Mercer. 1993. The mathematics of statistical machine translation: Parameter estimation. Computational Linguistics, 19(2):263–311. find
  3. M. Collins and T. Koo. 2005. Discriminative reranking for natural language parsing. Computational Linguistics, 31(1):25–70.
  4. M. Collins. 2001. Ranking algorithms for named-entity extraction: boosting and the voted perceptron. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL 2002), pages 489–496. find
  5. M. Collins. 2002. Discriminative training methods for hidden Markov models: theory and experiments with perceptron algorithms. In Proceedings of the 2002 Conference on Empirical Methods in Natural Language Processing (EMNLP 2002), pages 1–8.
  6. M. Collins. 2003. Head-driven statistical models for natural language parsing. Computational Linguistics, 29(4):589–637.
  7. A. P. Dempster, N. M. Laird, and D. B. Rubin. 1977. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society, 39(1):1–38. find
  8. R. Ge and R. J. Mooney. 2005. A statistical semantic parser that integrates syntax and semantics. In Proceedings of the Ninth Conference on Computational Natural Language Learning (CoNLL 2005), pages 9– 16. find
  9. R. Ge and R. J. Mooney. 2006. Discriminative reranking for semantic parsing. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics (COLING/ACL 2006), pages 263–270. find
  10. R. J. Kate and R. J. Mooney. 2006. Using string-kernels for learning semantic parsers. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics (COLING/ACL 2006), pages 913–920.
  11. R. J. Kate, Y. W. Wong, and R. J. Mooney. 2005. Learning to transform natural to formal languages. In Proceedings of the Twentieth National Conference on Artificial Intelligence (AAAI 2005), pages 1062–1068. find
  12. S. Katz. 1987. Estimation of probabilities from sparse data for the language model component of a speech recognizer. IEEE Transactions on Acoustics, Speech, and Signal Processing, 35(3):400–401. find
  13. L. R. Tang and R. J. Mooney. 2001. Using multiple clause constructors in inductive logic programming for semantic parsing. In Proceedings of the 12th European Conference on Machine Learning (ECML 2001), pages 466–477. find
  14. Y. W. Wong and R. J. Mooney. 2006. Learning for semantic parsing with statistical machine translation. In Proceedings of the Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics (HLT-NAACL 2006), pages 439–446.
  15. Y. W. Wong and R. J. Mooney. 2007. Learning synchronous grammars for semantic parsing with lambda calculus. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics (ACL 2007), pages 960–967.
  16. Y. W. Wong. 2007. Learning for Semantic Parsing and Natural Language Generation Using Statistical Machine Translation Techniques. Ph.D. thesis, The University of Texas at Austin. find
  17. K. Yamada and K. Knight. 2001. A syntax-based statistical translation model. In Proceedings of the 39th Annual Meeting of the Association for Computational Linguistics, pages 523–530.
  18. L. S. Zettlemoyer and M. Collins. 2005. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proceedings of the 21st Conference on Uncertainty in Artificial Intelligence.
  19. L. S. Zettlemoyer and M. Collins. 2007. Online learning of relaxed CCG grammars for parsing to logical form. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL 2007), pages 678–687. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/lu-2008-generative-model-parsing-natural-language/