Elamur Research⌕
☰
home / papers / 2013 / Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs

Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs

Summary

Gricean implicatures require agents to reason about what others believe about their own beliefs. Such nested reasoning is hard to model computationally. Vogel, Potts and Jurafsky treat communication as a decision problem inside a Decentralized-POMDP (Dec-POMDP), in which two agents share a reward. Exact Dec-POMDP solving is NEXP complete, so they instead adopt the approximation from Vogel et al. (2013), which recasts the problem as a POMDP for a single agent. That method adds a copy of the world state to the state space for each level of belief nesting and folds the partner's possible observations into the transition model. They build listeners and speakers of increasing sophistication: literal, level-one, and level-two.

They test the approach in two settings. One is a classic three-referent reference game. The other is a simplified navigation task grounded in the Cards corpus. In both, pragmatically enriched readings such as scalar implicatures and mutual exclusivity arise naturally when agents optimize joint utility. No special pragmatic rules are needed. This links decision-theoretic planning with formal pragmatics and gives a route toward dialogue agents that act and talk together.

Key points

  • Agents assume their partner models one fewer level of belief. Policies are computed with Perseus, a point-based value iteration solver. A level-two listener L(S(L)) reasons over an S×S×S state space.
  • In the reference game, the messages are 'moustache', 'glasses' and 'hat', and the referents are r1–r3.
    • Literally, only 'hat' is unambiguous.
    • The level-two listener learns that 'glasses' picks out r2 and 'moustache' picks out r1, which yields the full one-to-one mapping.
  • The Cards corpus provides 1266 chat transcripts of a two-player maze game. The model uses nine spatial expressions, such as 'top', 'top right' and 'middle'. Each is represented as a vague distribution over grid cells.
  • Literal meanings were estimated from every token containing a term, which removes the effects of pragmatic usage. Under the level-one listener L(S), meanings become much sharper. For example, the entropy of 'middle' falls from 7.16 to 2.35, and 'top' falls from 6.68 to 3.46.
  • The corpus does not record interpretations, so direct evaluation was impossible. Instead, the predictions were compared with exact-match token distributions, which approximate speaker intent, and the two closely resembled each other. Sampling-based methods are proposed for deeper nesting.

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: Linguistics & languages

Topics: Implicature

Cited by

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

Cite

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

@inproceedings{vogel2013implicatures,
  title = {{Implicatures and Nested Beliefs in Approximate Decentralized-POMDPs}},
  author = {Vogel, Adam and Potts, Christopher and Jurafsky, Dan},
  booktitle = {Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)},
  year = {2013},
  url = {https://aclanthology.org/P13-2014/}
}

References

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

  1. Leon Bergen, Noah D. Goodman, and Roger Levy. 2012. That’s what she (could have) said: How alternative utterances affect language use. In Proceedings of the Thirty-Fourth Annual Conference of the Cognitive Science Society. find
  2. Daniel S. Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. 2002. The complexity of decentralized control of Markov decision processes. Mathematics of Operations Research, 27(4):819– 840. ↗
  3. Colin F. Camerer, Teck-Hua Ho, and Juin-Kuan Chong. 2004. A cognitive hierarchy model of games. The Quarterly Journal of Economics, 119(3):861–898, August. ↗
  4. Herbert H. Clark and Deanna Wilkes-Gibbs. 1986. Referring as a collaborative process. Cognition, 22(1):1–39. ↗
  5. Eve V. Clark. 1987. The principle of contrast: A constraint on language acquisition. In Brian MacWhinney, editor, Mechanisms of Language Acquisition, pages 1–33. Erlbaum, Hillsdale, NJ. find
  6. Robert Dale and Ehud Reiter. 1995. Computational interpretations of the Gricean maxims in the generation of referring expressions. Cognitive Science, 19(2):233–263. ↗ our card
  7. Judith Degen and Michael Franke. 2012. Optimal reasoning about referential expressions. In Proceedings of SemDIAL 2012, Paris, September. find
  8. David DeVault and Matthew Stone. 2007. Managing ambiguities across utterances in dialogue. In Ron Artstein and Laure Vieu, editors, Proceedings of DECALOG 2007: Workshop on the Semantics and Pragmatics of Dialogue. find
  9. Prashant Doshi and Piotr J. Gmytrasiewicz. 2009. Monte carlo sampling methods for approximating interactive pomdps. J. Artif. Int. Res., 34(1):297– 337, March. ↗
  10. Michael C. Frank and Noah D. Goodman. 2012. Predicting pragmatic reasoning in language games. Science, 336(6084):998. ↗ our card
  11. Michael C. Frank, Noah D. Goodman, and Joshua B. Tenenbaum. 2009. Using speakers’ referential intentions to model early cross-situational word learning. Psychological Science, 20(5):579–585. ↗
  12. Michael Franke. 2009. Signal to Act: Game Theory in Pragmatics. ILLC Dissertation Series. Institute for Logic, Language and Computation, University of Amsterdam. find
  13. Gerald Gazdar. 1979. Pragmatics: Implicature, Presupposition and Logical Form. Academic Press, New York. find
  14. Piotr J. Gmytrasiewicz and Prashant Doshi. 2005. A framework for sequential planning in multi-agent settings. Journal of Artificial Intelligence Research, 24:24–49. ↗
  15. Dave Golland, Percy Liang, and Dan Klein. 2010. A game-theoretic approach to generating spatial descriptions. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 410–419, Cambridge, MA, October. ACL. find
  16. H. Paul Grice. 1975. Logic and conversation. In Peter Cole and Jerry Morgan, editors, Syntax and Semantics, volume 3: Speech Acts, pages 43–58. Academic Press, New York. ↗
  17. Robert M. Harnish. 1979. Logical form and implicature. In Linguistic Communication and Speech Acts, pages 313–391. MIT Press, Cambridge, MA. find
  18. Julia Hirschberg. 1985. A Theory of Scalar Implicature. Ph.D. thesis, University of Pennsylvania. find
  19. Laurence R Horn. 1972. On the Semantic Properties of Logical Operators in English. Ph.D. thesis, UCLA, Los Angeles. find
  20. Gerhard Jäger. 2007. Game dynamics connects semantics and pragmatics. In Ahti-Veikko Pietarinen, editor, Game Theory and Linguistic Meaning, pages 89–102. Elsevier, Amsterdam. find
  21. Gerhard Jäger. 2012. Game theory in semantics and pragmatics. In Maienborn et al. (Maienborn et al., 2012). find
  22. Emiel Krahmer and Kees van Deemter. 2012. Computational generation of referring expressions: A survey. Computational Linguistics, 38(1):173–218. ↗
  23. Claudia Maienborn, Klaus von Heusinger, and Paul Portner, editors. 2012. Semantics: An International Handbook of Natural Language Meaning, volume 3. Mouton de Gruyter, Berlin. find
  24. Christopher Potts. 2012. Goal-driven answers in the Cards dialogue corpus. In Nathan Arnett and Ryan Bennett, editors, Proceedings of the 30th West Coast Conference on Formal Linguistics, Somerville, MA. Cascadilla Press. find
  25. Hannah Rohde, Scott Seyfarth, Brady Clark, Gerhard Jäger, and Stefan Kaufmann. 2012. Communicating with cost-based implicature: A game-theoretic approach to ambiguity. In The 16th Workshop on the Semantics and Pragmatics of Dialogue, Paris, September. find
  26. Seymour Rosenberg and Bertram D. Cohen. 1964. Speakers’ and listeners’ processes in a word communication task. Science, 145:1201–1203. ↗
  27. Matthijs T. J. Spaan and Nikos Vlassis. 2005. Perseus: Randomized point-based value iteration for POMDPs. Journal of Artificial Intelligence Research, 24(1):195–220, August. ↗
  28. Alex Stiller, Noah D. Goodman, and Michael C. Frank. 2011. Ad-hoc scalar implicature in adults and children. In Proceedings of the 33rd Annual Meeting of the Cognitive Science Society, Boston, July. find
  29. Adam Vogel, Max Bodoia, Dan Jurafsky, and Christopher Potts. 2013. Emergence of Gricean maxims from multi-agent decision theory. In Human Language Technologies: The 2013 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Atlanta, Georgia, June. Association for Computational Linguistics. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/vogel-2013-implicatures-nested-beliefs-approximate-decentralized/