Elamur Research⌕
☰
home / papers / 2000 / Exploiting a Probabilistic Hierarchical Model for Generation

Exploiting a Probabilistic Hierarchical Model for Generation

Paper · 2000 · Srinivas Bangalore and Owen Rambow

Summary

Bangalore and Rambow ask whether a statistical sentence generator does better when it uses explicit syntactic trees and a grammar, not only an n-gram model over strings. Earlier stochastic generators, such as Langkilde and Knight's Nitrogen, use no tree representation. The authors built Fergus, which has three stages:

  • Tree Chooser: assigns XTAG supertags to the nodes of an input dependency tree, using a stochastic tree model built from about one million words of Wall Street Journal derivations taken from the Penn Tree Bank.
  • Unraveler: uses the XTAG grammar to expand the supertagged tree into a lattice of allowed word orders.
  • LP Chooser: picks the best path through the lattice with a WSJ trigram model.

They compared three tree models on 100 WSJ sentences, using string-edit-based metrics. Ranked from weakest to strongest:

  1. a baseline learned from unannotated text
  2. a model learned from treebank annotation
  3. a supertag model tied to the hand-crafted grammar

The main finding is that syntactic knowledge, both annotated and hand-written, measurably helps stochastic generation. It supports a hybrid design: use grammar where it is reliable and statistics where it is not.

Key points

  • Fergus works within lexicalized tree-adjoining grammar (LTAG) and uses the wide-coverage XTAG grammar of English. Adjunct trees state only their valency. Where and in which direction an adjunct attaches is stored in a separate adjunction table.

  • The input is an unlabeled dependency (derivation) tree. In these experiments every word, including function words, had to be supplied already fully inflected.

  • Results on 100 random WSJ sentences (average length 16 words):

    ModelSimple accuracyGeneration accuracyTime per sentence
    Baseline LR Model41.2%56.2%186ms
    Treebank derived LR Model52.9%66.8%129ms
    Supertag-based Model58.9%72.4%517ms

  • The tree model was extracted from the Penn Tree Bank with heuristics, because the treebank lacks full head-dependent information. The model is therefore not fully correct.

  • The authors attribute the gains partly to long-distance effects that n-grams miss, such as collocation parts separated by adjuncts, and to agreement handled by the grammar.

Interesting ideas

  • I1. Supertagging over a tree: assigning supertags to nodes of a tree rather than to a linear word sequence is a reusable trick. A top-down dynamic program, where each node's choice depends on its daughters and must be compatible with its mother, keeps the search tractable.
  • I2. Overgenerate, then rank: produce a lattice of every grammatical linearization, compose it with a finite-state language model, and decode with Viterbi. This cleanly separates hard constraints from soft preferences. It could suit word-order-flexible languages like Ukrainian.
  • I3. Adjunction table outside the trees: keeping adjunct attachment information separate from the elementary trees leaves word placement deliberately underspecified, so a statistical model can resolve it. Examples include adjective ordering and the attachment site.
  • I4. Generation Accuracy metric: this edit-distance metric counts a token moved to a different position as one error instead of a deletion plus an insertion. That makes it fairer for evaluating reordering tasks such as linearization or MT.
  • I5. Hybrid back-off design: pair knowledge-based and stochastic components for the same subtask, such as morphology, function words or punctuation, and let one serve as a fallback for the other. This is attractive when only a minimal grammar exists for a new language.

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

🏢AT&TBedminster · United States29 works · 15,393 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

Cite

Cite as Srinivas Bangalore and Owen Rambow. 2000. Exploiting a Probabilistic Hierarchical Model for Generation. COLING 2000 Volume 1: The 18th International Conference on Computational Linguistics.

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

@inproceedings{bangalore2000exploiting,
  title = {{Exploiting a Probabilistic Hierarchical Model for Generation}},
  author = {Srinivas Bangalore and Owen Rambow},
  booktitle = {COLING 2000 Volume 1: The 18th International Conference on Computational Linguistics},
  year = {2000},
  doi = {10.3115/990820.990827},
  url = {https://doi.org/10.3115/990820.990827}
}

References

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

  1. Hiyan Alshawi, Srinivas Bangalore, and Shona Douglas. 1998. Automatic acquisition of hierarchical transduction models for machine tr anslation. In Proceedings of the 36th Annual Meeting Association for Computational Linguistics , Montreal, Canada. find
  2. Srinivas Bangalore and Aravind Joshi. 1999. Supertagging: An approach to almost parsing. Computational Linguistics , 25(2). our card
  3. Srinivas Bangalore, Owen Rambow, and Steve Whittaker. 2000. Evaluation Metrics for Generation. In Proceedings of International Conference on Natural Language Generation , Mitzpe Ramon, Isreal. find
  4. Aravind K. Joshi. 1987a. An introduction to Tree Adjoining Grammars. In A. Manaster-Ramer, editor, Mathematics of Language , pages 87{115. John Benjamins, Amsterdam. find
  5. Aravind K. Joshi. 1987b. The relevance of tree adjoining grammar to generation. In Gerard Kempen, editor, Natural Language Generation: New Results in Arti cial Intelligence, Psychology and Linguistics , pages 233{252. Kluwer Academic Publishers, Dordrecht/Boston/Lancaster. find
  6. Irene Langkilde and Kevin Knight. 1998a. Generation that exploits corpus-based statistical knowledge. In 36th Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics (COLING-ACL'98) , pages 704{ 710, Montreal, Canada. our card
  7. Irene Langkilde and Kevin Knight. 1998b. The practical value of n-grams in generation. In Proceedings of the Ninth International Natural Language Generation Workshop (INLG'98) , Niagara-on-the-Lake, Ontario. find
  8. Irene Langkilde and Kevin Knight. 2000. Forest-based statistical sentence generation. In Proceedings of First North American ACL , Seattle, USA, May. find
  9. Robert Malouf. 1999. Two methods for predicting the order of prenominal adjectives in english. In Proceedings of CLIN99 . find
  10. David D. McDonald and James D. Pustejovsky. 1985. Tags as a grammatical formalism for generation. In 23rd Meeting of the Association for Computational Linguistics (ACL'85) , pages 94{103, Chicago, IL. find
  11. Owen Rambow and Tanya Korelsky. 1992. Applied text generation. In Third Conference on Applied Natural Language Processing , pages 40{47, Trento, Italy. find
  12. Adwait Ratnaparkhi. 2000. Trainable methods for surface natural language generation. In Proceedings of First North American ACL , Seattle, USA, May. find
  13. Ehud Reiter. 1994. Has a consensus NL generation architecture appeared, and is it psycholinguistically plausible? In Proceedings of the 7th International Workshop on Natural Language Generation , pages 163{170, Maine. find
  14. The XTAG-Group. 1999. A lexicalized Tree Adjoining Grammar for English. Technical Report http://www.cis.upenn.edu/~xtag/tech-report/tech-report.html , The Institute for Research in Cognitive Science, University of Pennsylvania. ↗ our card

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bangalore-2000-exploiting-probabilistic-hierarchical-model-generation/