Chart Generation
What it is about
A conceptual paper on whether chart parsing can serve as a single architecture for both parsing and generation. Chart parsing merges equivalent partial structures, so an analysis is built once however many structures a string has. In generation the input is a logical form, not a string, so string positions cannot index the edges. Kay proposes indexing edges by the variables of the logical form instead: two edges can interact only if they share an index. He also needs a rule that a phrase may not be built if it makes an index internal while a predicate that refers to it stays uncovered. The paper shows that without such a rule, a modifier-rich phrase yields 2^k variants for k modifiers, and that the chart must keep active and inactive edges apart even with binary rules. The paper works through an example with several adjectives and an adverb, and gives no benchmark numbers.
Ideas
- I1. Index the encoder's chart by meta-token identity, not by position. Two candidate chunks interact only if they share a meta token. Count the candidate combinations on verses with many modifiers before and after the change, run twice.
- I2. Adopt Kay's internal-index rule as a check: reject a chunk that drops a meta token whose dependents are partly in the chunk. This should cut the modifier explosion without losing output. Measure the number of candidates per verse.
- I3. Coverage as a bit vector. Each candidate lists the meta tokens it covers, and no two chunks may cover the same token. Make "every meta token is spelled exactly once" an exact-mode invariant, with a test that must fail on a deliberately duplicated token (the negative control).
- I4. Keep active and inactive edges apart in the encoder even when all rules are binary, as Kay argues. This matters only if the encoder turns into a chart, so treat it as a later step.
For Mova
The encoder in tools/translate/src/profile.rs is today a context table, not a chart, so the paper applies only if the encoder moves to chart search over meta-token sets. The ideas touch open problem 3 (the encoder should write trees). The invariant in I3 is cheap and fits the exact-mode residual, so it is the first thing to take.
Cite
@inproceedings{kay1996chart,
title = {{Chart Generation}},
author = {Kay, Martin},
booktitle = {34th Annual Meeting of the Association for Computational Linguistics},
year = {1996},
doi = {10.3115/981863.981890},
url = {https://doi.org/10.3115/981863.981890}
}References
- Copestake, A., Dan Flickinger, Robert Malouf, and Susanne Riehemann, and Ivan Sag (1996). Translation Using Minimal Recursion Semantics. Proceedings of The Sixth International Conference on Theoretical and Methodological Issues in Machine Translation, Leuven (in press). find our card
- Davidson, D. (1980). Essays on Actions and Events. Oxford: The Clarendon Press. find
- Hobbs, J. R. (1985). Ontological Promiscuity. 23rd Annual Meeting of the Association for Computational Linguistics, Chicago, ACL. find
- Kay, M. (1970). From Semantics to Syntax. Progress in Linguistics. Bierwisch Manfred, and K. E. Heidolf. The Hague, Mouton: ! 14-126. find
- Kay, M. (1989). Head-driven Parsing. Proceedings of Workshop on Parsing Technologies, Pittsburgh, PA. find
- Parsons, T. (1990). Events in the Semantics of English. Cambridge, Mass.: MIT Press. find
- Shieber, S. (1988). A Uniform Architecture for Parsing and Generation. COLING-88, Budapest, John yon Neumann Society for Computing Sciences. find
- Shieber, S. M. et al. (1989). A Semantic-Head-Driven Generation Algorithm for Unification Based Formalisms. 27th Annual Meeting of the Association for Computational Linguistics, Vancouver. find
- B.C. Whitelock, P. (1992). Shake and-Bake Translation. COLING-92, Nantes. find our card
This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/kay-1996-chart-generation/