Mova0.5 pre-release⌕
☰
home / docs / papers / English / Computational Interpretations of the Gricean Maxims in the Generation of Referring Expressions

Computational Interpretations of the Gricean Maxims in the Generation of Referring Expressions

What it is about

The paper asks how to generate a definite noun phrase (the black dog) that identifies its referent without false implicatures. It compares four computational readings of Grice's Brevity: full brevity (the shortest distinguishing description, which is NP-hard), a greedy set-cover heuristic, a local brevity approximation, and an incremental algorithm. From observations of human speakers, who add redundant modifiers and start speaking before they have scanned all distractors, the authors argue that the incremental algorithm is closest to people. It goes through attributes in a preferred order and keeps one only if it rules out a distractor not yet ruled out, at a cost of about n_d × n_l. In their example, full brevity needs 6 checks for 3 attributes, 2 distractors and 2 mentioned attributes; for 10 attributes and 3 mentioned, 175; for 50 attributes and 5 mentioned, over 2,000,000.

Ideas

For Mova

Chapters: 35. Reference and coreference, 22. Phrases: noun, adjective, adverb and prepositional phrases (noun phrase structure), 11. Nouns. Code: world/src/knowledge.rs (entities and their attributes), coref/src/mention.rs. Measure: referential success (exactly one referent identified) and mean description length on the school contexts; two runs must be identical.

Topics: Implicature

Cite

The paper itself, not this card. BibTeX from the library's record of the work. arXiv cmp-lg/9504020

@misc{dale1995computational,
  title = {{Computational Interpretations of the Gricean Maxims in the Generation of Referring Expressions}},
  author = {Dale, Robert and Reiter, Ehud},
  year = {1995},
  eprint = {cmp-lg/9504020},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/cmp-lg/9504020}
}

References

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

  1. Appelt, D & Kronfeld, A (1987). A computational model of referring. In Proceedings of IJCAI-1987, volume 2, pages 640–647. find
  2. Appelt, D (1985a). Planning English Sentences. New York: Cambridge University Press. find
  3. Appelt, D (1985b). Planning English referring expressions. Artificial Intelligence, 26: 1–33. find
  4. Appelt, D (1985c). Some pragmatic issues in the planning of definite and indefinite referring expressions. In Proceedings of the 23rd Annual Meeting of the Association for Computational Linguistics, pages 198–203. find
  5. Bateman, J, Kasper, R, Moore, J & Whitney, R (1990). A general organization of knowledge for natural language processing: the Penman upper model. Technical report, Information Sciences Institute, Marina del Rey, CA 90292. find
  6. Brachman, R & Schmolze, J (1985). An overview of the KL-ONE knowledge representation system. Cognitive Science, 9: 171–216. find
  7. Cruse, D (1977). The pragmatics of lexical specificity. Journal of Linguistics, 13: 153–164. find
  8. Dale, R (1989). Cooking up referring expressions. In Proceedings of the 27th Annual Meeting of the Association for Computational Linguistics, pages 68–75. find
  9. Dale, R (1992). Generating Referring Expressions: Building Descriptions in a Domain of Objects and Processes. MIT Press. find
  10. Dale, R & Haddock, N (1991). Content determination in the generation of referring expressions. Computational Intelligence, 7(4), 1991. find
  11. Donnellan, K (1966). Reference and definite description. Philosophical Review, 75: 281–304. find
  12. Ford, W & Olson, D (1975). The elaboration of the noun phrase in children’s description of objects. Journal of Experimental Child Psychology, 19: 371–382, 1975. find
  13. Garey, W & Johnson, D (1979). Computers and Intractability: a Guide to the Theory of NP-Completeness. San Francisco: W. H. Freeman. find
  14. Goodman, B (1986). Reference identification and reference identification failure. Computational Linguistics, 12(4): 273–305. find
  15. Grice, H P (1975). Logic and conversation. In P. Cole and J. Morgan, editors, Syntax and Semantics: Vol 3, Speech Acts, pages 43–58. New York: Academic Press. find
  16. Grosz, B & Sidner, C (1986). Attention, intention, and the structure of discourse. Computational Linguistics, 12: 175–206. find
  17. Johnson, D (1974). Approximation algorithms for combinatorial problems. Journal of Computer and Systems Sciences, 9. find
  18. Kasper, R (1989). A flexible interface for linking applications to Penman’s sentence generator. In Proceedings of the 1989 DARPA Speech and Natural Language Workshop, pages 153–158, Philadelphia. find
  19. Kronfeld, A (1986). Donnellan’s distinction and a computational model of reference. In Proceedings of the 24th Annual Meeting of the Association for Computational Linguistics, pages 186–191. find
  20. Levelt, W (1989). Speaking: From Intention to Articulation. MIT Press. find
  21. McDonald, D (1981). Natural Language Generation as a Process of Decision-Making Under Constraints. PhD thesis, MIT. find
  22. McDonald, D (1983). Description Directed Control. Computers and Mathematics, 9: 111– 130. find
  23. Oberlander, J & Dale, R (1991). Generating expressions referring to eventualities. In Proceedings of the 13th Annual Conference of the Cognitive Science Society, pages 67–72. find
  24. Pechmann, T (1989). Incremental speech production and referential overspecification. Linguistics, 27: 89–110. find
  25. Reiter, E (1990a). The computational complexity of avoiding conversational implicatures. In Proceedings of the 28th Annual Meeting of the Association for Computational Linguistics, pages 97–104. find
  26. Reiter, E (1990b). Generating Appropriate Natural Language Object Descriptions. PhD thesis, Harvard University. Available as Technical Report TR-10-90, Aiken Computation Laboratory, Harvard University. find
  27. Reiter, E (1990c). Generating descriptions that exploit a user’s domain knowledge. In Robert Dale, Chris Mellish, and Michael Zock, editors, Current Research in Natural Language Generation, pages 257–285. London: Academic Press. find
  28. Reiter, E (1991). A new model of lexical choice for nouns. Computational Intelligence, 7(4): 240–251. find
  29. Reiter, E, Mellish, C & Levine, J (1992). Automatic generation of on-line documentation in the IDAS project. In Proceedings of the Third Conference on Applied Natural Language Processing, pages 64–71, Trento, Italy. find
  30. Rosch, E (1978). Principles of categorization. In E. Rosch and B. Lloyd, editors, Cognition and Categorization, pages 27–48. Hillsdale, NJ: Lawrence Erlbaum. find
  31. Sonnenschein, S (1985). The development of referential communication skills: Some situations in which speakers give redundant messages. Journal of Psycholinguistic Research, 14: 489– 508. find
  32. Whitehurst, G (1976). The development of communication: Changes with age and modeling. Child Development, 47: 473–482. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/dale-1995-computational-interpretations-gricean-maxims-generation/