Elamur Research⌕
☰
home / papers / 1999 / Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars

Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars

Summary

The paper addresses syntactic analysis (parsing) for bilexical grammars. In such grammars, each word specifies which dependents it accepts, that is, the grammar takes into account the compatibility of specific word pairs. The strong parsers of the time, by Alshawi, Collins, Charniak and Eisner, are built on probabilistic variants of such grammars. Their standard chart algorithms, including CKY, run in O(n⁵) time in sentence length. As a result, they are too slow without aggressive probabilistic pruning. The authors propose a different approach to dynamic programming. It assembles not only complete constituents but also new intermediate derivation fragments. A child constituent is attached to its parent in two steps, and each step is independent of one of the positions in the sentence. This reduces the complexity to O(n⁴) for bilexical CFGs and for head automaton grammars. For a common special case, "split" automata, the complexity remains O(n³), but with a smaller grammar constant. These results show that lexicalized models can be parsed exactly and considerably faster than previously believed.

Key points

  • Bilexical CFGs in Chomsky normal form (CNF): recognition in O(n⁴·max(p, |V_D|²)) instead of O(n⁵·|V_D|³) for CKY. The quantity p denotes the largest count of productions associated with any one pair of terminal symbols. There is also a faster variant in practice, using the HALVE rule, which requires an agenda and a sparse parse chart.
  • Head automaton grammars (Alshawi, 1996): via reduction to a bilexical CFG, parsing takes O(n⁴·t³), and O(n⁴·t²) for deterministic automata. The reduction also works for stochastic versions.
  • Split HAG: an algorithm over constituent halves marked with a flip state runs in O(n³·g²·t²), and in O(n³·g²·t) for deterministic automata. The previous result (Eisner, 1997) was O(n³·g³·t²).
  • The authors note that all three models of Collins (1997) are suitable for the O(n³) method.
  • The same technique is carried over to bilexicalized tree adjoining grammars: O(n⁷) instead of the naive O(n⁸).

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: Computing & GPUs

Topics Syntax & grammar formalisms

Cite

Cite as Jason Eisner and Giorgio Satta. 1999. Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars. Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics.

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

@inproceedings{eisner1999efficient,
  title = {{Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars}},
  author = {Jason Eisner and Giorgio Satta},
  booktitle = {Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics},
  year = {1999},
  doi = {10.3115/1034678.1034748},
  url = {https://doi.org/10.3115/1034678.1034748}
}

References

14 references, 2 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, volume 1. Prentice-Hall, Englewood Cliffs, NJ. find
  2. H. Alshawi. 1996. Head automata and bilingual tiling: Translation with minimal representations. In Proc. of ACL, pages 167-176, Santa Cruz, CA. find
  3. Y. Bar-Hillel. 1953. A quasi-arithmetical notation for syntactic description. Language, 29:47-58. find
  4. E. Charniak. 1997. Statistical parsing with a context-free grammar and word statistics. In Proc. o] the l~th AAAI, Menlo Park. find
  5. C. Chelba and F. Jelinek. 1998. Exploiting syntactic structure for language modeling. In Proc. of COLING-ACL. find
  6. N. Chomsky. 1965. Aspects of the Theory o] Syntax. MIT Press, Cambridge, MA. find
  7. M. Collins and J. Brooks. 1995. Prepositional phrase attachment through a backed-off model. In Proe. of the Third Workshop on Very Large Corpora, Cambridge, MA. our card
  8. M. Collins. 1997. Three generative, lexicalised models for statistical parsing. In Proc. of the 35th A CL and 8th European A CL, Madrid, July. our card
  9. J. Eisner. 1996. An empirical comparison of probability models for dependency grammar. Technical Report IRCS-96-11, IRCS, Univ. of Pennsylvania. find
  10. J. Eisner. 1997. Bilexical grammars and a cubic-time probabilistic parser. In Proceedings of the ~th Int. Workshop on Parsing Technologies, MIT, Cambridge, MA, September. find
  11. R. C. Gonzales and M. G. Thomason. 1978. Syntactic Pattern Recognition. Addison-Wesley, Reading, MA. find
  12. M. A. Harrison. 1978. Introduction to Formal Language Theory. Addison-Wesley, Reading, MA. find
  13. J. E. Hopcroft and J. D. Ullman. 1979. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading, MA. q (a) find
  14. (h \< j, q E Qdh) q (i \<_ h, q E Qdh U {F}, s E (~dh) i4 q (h \< h', q E Qdh, s' E Qd h,) h q s:6 h (h' \< h, q • Qdh, s • Qd~, s' • Q. dh) h (b) START: - - q q E Ida MID: - - h 'h find

This page in Markdown → https://md.research.elamur.ai/free/en/papers/eisner-1999-efficient-parsing-bilexical-context-free/