Elamur Research⌕
☰
home / papers / 2007 / Learning Synchronous Grammars for Semantic Parsing with Lambda Calculus

Learning Synchronous Grammars for Semantic Parsing with Lambda Calculus

Summary

Learned synchronous grammars had only been applied to semantic parsing for meaning languages without logical variables. Predicate-logic representations, which most computational semantics relies on, were therefore out of reach unless one hand-built a variable-free functional language. Wong and Mooney extend their SMT-inspired parser WASP into λ-WASP. It uses a synchronous context-free grammar whose meaning-side rules are λ-functions, so variables can be bound and passed between subformulas compositionally.

The grammar is learned from sentences paired with Prolog logical forms:

  • Rules are extracted from GIZA++ word alignments between words and MRL productions.
  • A maximum-entropy model chooses among competing derivations.
  • Further improvements include conjunct regrouping, two-level rule features and type checking.

On the GEOQUERY U.S. geography database corpus, λ-WASP reaches the best F-measure and by far the best recall among the compared systems (WASP, SCISSOR, Zettlemoyer & Collins). It needs no NL syntax annotation or language-specific templates, and it performs similarly on Spanish, Japanese and Turkish versions of the data. This shows that standard SMT machinery can learn parsers for full logical forms.

Key points

  • Formalism: λ-SCFG pairs an NL phrase with a λ-function over MR strings. Arguments attached to nonterminals let logical variables be renamed and shared correctly when the yield is computed.

  • Lexical acquisition: Rules come from the K = 5 most probable GIZA++ alignments, with variable names ignored to reduce sparsity. A variable is λ-bound only if it also occurs outside the current subtree.

  • Main results: On the larger GEOQUERY corpus, evaluated with 10-fold cross-validation and 792 training examples, λ-WASP achieved:

    SystemPrecisionRecallF-measure
    λ-WASP91.9586.5989.19
    WASP87.1974.7780.50
    SCISSOR92.0872.2780.98
    Z&C96.2579.2986.95

    Z&C's precision is the highest, but it was measured on 280 test examples only.

  • Ablations:

    • Removing conjunct regrouping lowers precision/recall to 90.73/83.07.
    • Removing two-level rules gives 88.46/84.32.
    • Additionally removing type checking collapses precision/recall to 65.45/63.18.

  • Multilingual test: A 250-example multilingual GEOQUERY subset (English, Spanish, Japanese, Turkish) yields comparable learning curves across all four languages.

Interesting ideas

  • I1. Bind only what escapes a subtree. During rule extraction, λ-abstract exactly those variables that are also used elsewhere in the logical form. This simple test for which variables to expose could help any grammar-induction or program-synthesis setup that must assemble structures containing shared variables.
  • I2. Linearize the target as grammar productions. If the target structure has an unambiguous grammar, its unique sequence of productions can be aligned to words with off-the-shelf MT aligners. This turns structured output into something SMT tools already handle.
  • I3. Use type constraints to prune derivations. Partial parses are discarded when a variable could not refer to any entity type, since users rarely ask nonsensical questions. Cheap domain-type filtering of this kind sharply raised both precision and recall, so it may pay off in other structured-prediction decoders.
  • I4. Evaluate by executed answers. A parse counts as correct when it retrieves the same database answer as the gold logical form. This credits semantically equivalent outputs, which suits any task where the meaning representation is executable.
  • I5. Test language independence with parallel data. Translating the questions into several languages while keeping the logical forms fixed checks whether a parser truly needs no language-specific resources. The same design would suit evaluations involving lower-resource languages such as Ukrainian.

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: Machine translation · Natural language processing

Topics: Machine translation

Cited by

129 papers of our library cite it (of the 140673 whose bibliographies we read); 4 of them have a page here, 125 not yet.

Cite

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

@inproceedings{wong2007learning,
  title = {{Learning Synchronous Grammars for Semantic Parsing with Lambda Calculus}},
  author = {Wong, Yuk Wah and Mooney, Raymond},
  booktitle = {Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics},
  year = {2007},
  url = {https://aclanthology.org/P07-1121/}
}

References

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

  1. A. V. Aho and J. D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling. Prentice Hall, Englewood Cliffs, NJ. find
  2. S. Bayer, J. Burger, W. Greiff, and B. Wellner. 2004. The MITRE logical form generation system. In Proc. of Senseval-3, Barcelona, Spain, July. find
  3. P. Blackburn and J. Bos. 2005. Representation and Inference for Natural Language: A First Course in Computational Semantics. CSLI Publications, Stanford, CA. find
  4. J. Bos. 2005. Towards wide-coverage semantic interpretation. In Proc. of IWCS-05, Tilburg, The Netherlands, January. find
  5. D. Chiang. 2005. A hierarchical phrase-based model for statistical machine translation. In Proc. of ACL-05, pages 263– 270, Ann Arbor, MI, June. find our card
  6. M. Collins and T. Koo. 2005. Discriminative reranking for natural language parsing. Computational Linguistics, 31(1):25–69. ↗ our card
  7. M. Galley, J. Graehl, K. Knight, D. Marcu, S. DeNeefe, W. Wang, and I. Thayer. 2006. Scalable inference and training of context-rich syntactic translation models. In Proc. of COLING/ACL-06, pages 961–968, Sydney, Australia, July. Recall (%) English Spanish Japanese Turkish 100 150 Number of training examples R. Ge and R. J. Mooney. 2005. A statistical semantic parser that integrates syntax and semantics. In Proc. of CoNLL-05, pages 9–16, Ann Arbor, MI, July. find our card
  8. H. P. Grice. 1975. Logic and conversation. In P. Cole and J. Morgan, eds., Syntax and Semantics 3: Speech Acts, pages 41–58. Academic Press, New York. ↗
  9. A. K. Joshi and K. Vijay-Shanker. 2001. Compositional semantics with lexicalized tree-adjoining grammar (LTAG): How much underspecification is necessary? In H. Bunt et al., eds., Computing Meaning, volume 2, pages 147–163. Kluwer Academic Publishers, Dordrecht, The Netherlands. ↗
  10. R. Montague. 1970. Universal grammar. Theoria, 36:373–398. find
  11. F. J. Och and H. Ney. 2003. A systematic comparison of various statistical alignment models. Computational Linguistics, 29(1):19–51. ↗
  12. K. A. Papineni, S. Roukos, and R. T. Ward. 1997. Feature-based language understanding. In Proc. of EuroSpeech-97, pages 1435–1438, Rhodes, Greece. find
  13. W. Schuler. 2003. Using model-theoretic semantic interpretation to guide statistical parsing and word recognition in a spoken language interface. In Proc. of ACL-03, pages 529– 536. find
  14. Y. W. Wong and R. J. Mooney. 2006. Learning for semantic parsing with statistical machine translation. In Proc. of HLT/NAACL-06, pages 439–446, New York City, NY. find
  15. Y. W. Wong and R. J. Mooney. 2007. Generation by inverting a semantic parser that uses statistical machine translation. In Proc. of NAACL/HLT-07, Rochester, NY, to appear. find our card
  16. D. Wu. 1997. Stochastic inversion transduction grammars and bilingual parsing of parallel corpora. Computational Linguistics, 23(3):377–403. find our card
  17. K. Yamada and K. Knight. 2001. A syntax-based statistical translation model. In Proc. of ACL-01, pages 523–530, Toulouse, France. find our card
  18. J. M. Zelle and R. J. Mooney. 1996. Learning to parse database queries using inductive logic programming. In Proc. of AAAI-96, pages 1050–1055, Portland, OR, August. find
  19. L. S. Zettlemoyer and M. Collins. 2005. Learning to map sentences to logical form: Structured classification with probabilistic categorial grammars. In Proc. of UAI-05, Edinburgh, Scotland, July. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/wong-2007-learning-synchronous-grammars-semantic-parsing/