Elamur Research⌕
☰
home / papers / 2018 / Planning, Inference and Pragmatics in Sequential Language Games

Planning, Inference and Pragmatics in Sequential Language Games

Summary

The paper models how people talk in cooperative games where each partner holds hidden information. To win, a player must reason about three things. It must guess what the partner knows from their messages (inference). It must pick messages with future turns in mind (planning). It must account for the fact that the partner is also reasoning strategically (pragmatics).

The authors built a game called InfoJigsaw to study this. Two players see a shared grid of shapes, but one sees only the letters on the objects and the other sees only the digits. They exchange messages of at most two English words until one of them clicks on the object matching a target letter–digit pair. Pairs of Amazon Mechanical Turk workers played the game.

The proposed model, PIP, links the three kinds of reasoning through a two-dimensional system of recurrences. These rest on a plain, context-independent literal semantics, and the model has only four (hyper)parameters. PIP predicts human moves better than a baseline that maximizes per-turn information and better than its own ablations. The paper shows that rich, context-dependent meaning can arise from simple word meanings combined with explicit strategic reasoning.

Key points

  • Corpus: 200 player pairs started and 168 completed all 10 scenarios, giving 1680 games and 4967 actions. The mean score was 7.5 correct clicks per 10 games, and performance did not improve across rounds.
  • Filtering: games were kept only if every message contained "yes"/"no" or one of the top 12 words by frequency, which together cover 73% of tokens. This left 1259 games.
  • Scenario design: grids were 2×3 or 3×2, with color and shape public and letter and digit private. Clicking on the first turn was not allowed.
  • Main results: PIP achieves higher log-likelihood than the information-maximizing baseline. It also beats ablations that remove planning or pragmatics.
  • Inference ablation: a version that forgets the distant past does better on short games, while full PIP wins on longer games.

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

Cited by

8 papers of our library cite it (of the 140673 whose bibliographies we read); 2 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. DOI 10.1162/tacl_a_00037 · arXiv 1805.11774

@article{khani2018planning,
  title = {{Planning, Inference and Pragmatics in Sequential Language Games}},
  author = {Khani, Fereshte and Goodman, Noah D. and Liang, Percy},
  journal = {Transactions of the Association for Computational Linguistics},
  year = {2018},
  doi = {10.1162/tacl\_a\_00037},
  eprint = {1805.11774},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1162/tacl_a_00037}
}

References

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

  1. which defines recurrences capturing how one agent reasons about another. Similar ideas were explored in the precursor work of Golland et al. (2010), and much work has ensued (Smith et al., 2013; Qing and Franke, 2014; Monroe and Potts, 2015; Ullman et al., 2016; Andreas and Klein, 2016). Most of this work is restricted to production and comprehension of a single utterance. find
  2. Hawkins et al. (2015) extend these ideas to two utterances (a question and an answer). find
  3. Vogel et al. (2013b) in-Learning to communicate. There is a rich literature on multi-agent reinforcement learning (Busoniu et al., 2008). Some works assume full visibility and cooperate without communication, assuming the world is completely visible to all agents (Lauer and Riedmiller, 2000; Littman, 2001); others assume a predefined convention for communication (Zhang and Lesser, 2013; Tan, 1993). There is also some work that learns the convention itself (Foerster et al., 2016; Sukhbaatar et al., 2016; Lazaridou et al., 2017; Mordatch and Abbeel, 2018). find
  4. Lazaridou et al. (2017) puts humans in the loop to make the communication more human-interpretable. In comparison to these works, we seek to predict human behavior instead of modeling artificial agents that communicate with each other. Dialogue. There is also a lot of work in computational linguistics and NLP on modeling dialogue. find
  5. Allen and Perrault (1980) provides a model that infers the intention/plan of the other agent and uses this plan to generate a response. find
  6. Clark and Brennan (1991) explains how two players update their common ground (mutual knowledge, mutual beliefs, and mutual assumptions) in order to coordinate. Recent work in task-oriented dialogue uses POMDPs and end-to-end neural networks (Young, 2000; Young et al., 2013; Wen et al., 2017; He et al., 2017). In this work, instead of learning from a large corpus, we predict human behavior without learning, albeit in a much more strategic, stylized setting (two words per utterance). find
  7. Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. 2016. Learning to compose neural networks for question answering. In Association for Computational Linguistics (ACL), pages 1545–1554. ↗ our card
  8. B. Douglas Bernheim. 1984. Rationalizable strategic behavior. Econometrica: Journal of the Econometric Society, pages 1007–1028. ↗
  9. Lucian Busoniu, Robert Babuska, and Bart De Schutter. 2008. A comprehensive survey of multiagent reinforcement learning. IEEE Trans. Systems, Man, and Cybernetics, Part C, 38(2):156–172. ↗
  10. Herbert H. Clark and Susan E. Brennan. 1991. Grounding in Communication. Perspectives on Socially Shared Cognition. ↗
  11. Eddie Dekel and Marciano Siniscalchi. 2015. Epistemic 7 Conclusion game theory, volume 4. Handbook of Game Theory with Economic Applications. In this paper, we started with the observation that hu- Jakob Foerster, Yannis M. Assael, Nando de Freitas, and mans use language in a very contextual way driven Shimon Whiteson. 2016. Learning to communi-by their goals. We identified three salient aspects— cate with deep multi-agent reinforcement learning. In planning, inference, pragmatics—and proposed a Advances in Neural Information Processing Systems (NIPS), pages 2137–2145. unified model, PIP, that captures all three aspects si-Michael C. Frank and Noah D. Goodman. 2012. Predict-multaneously. Our main result is that a very simple, ing pragmatic reasoning in language games. Science, context-independent literal semantics can give rise 336:998–998. via the recurrences to rich phenomena. We study Michael Franke. 2009. Signal to act: Game theory in these phenomena in a new game, InfoJigsaw, and pragmatics. Institute for Logic, Language and Com-show that PIP is able to capture human behavior. putation. find
  12. Dave Golland, Percy Liang, and Dan Klein. 2010. A Reproducibility game-theoretic approach to generating spatial descriptions. In Empirical Methods in Natural Language Pro-All code, data, and experiments for this paper are cessing (EMNLP), pages 410–419. available on the CodaLab platform at https:// ↗
  13. Noah D. Goodman and Michael C. Frank. 2016. Pragmatic language interpretation as probabilistic infer-worksheets.codalab.org/worksheets/ ence. Trends in Cognitive Sciences, 20(11):818–829. 0x052129c7afa9498481185b553d23f0f9/. find
  14. Herbert P. Grice. 1975. Logic and conversation. Syntax and Semantics, 3:41–58. ↗
  15. Acknowledgments Robert X. D. Hawkins, Andreas Stuhlmüller, Judith Degen, and Noah D. Goodman. 2015. Why do you ask? We would like to thank the anonymous reviewers Good questions provoke informative answers. In Pro-and the action editor for their helpful comments. We ceedings of the Thirty-Seventh Annual Conference of also thank Will Monroe for providing valuable feed-the Cognitive Science Society. back on early drafts. find
  16. Robert X. D. Hawkins. 2015. Conducting real-time multiplayer experiments on the web. Behavior Research Methods, 47(4):966–976. ↗
  17. He He, Anusha Balakrishnan, Mihail Eric, and Percy References Liang. 2017. Learning symmetric collaborative dia-James F. Allen and C. Raymond Perrault. 1980. Analogue agents with dynamic knowledge graph embed-lyzing intention in utterances. Artificial Intelligence, dings. In Association for Computational Linguistics 15(3):143–178. (ACL), pages 1766–1776. find
  18. Jacob Andreas and Dan Klein. 2016. Reasoning about Simon M. Huttegger, Brian Skyrms, Rory Smead, and pragmatics with neural listeners and speakers. In Kevin J.S. find
  19. Zollman. 2010. Evolutionary dynamics Empirical Methods in Natural Language Processing of Lewis signaling games: Signaling systems vs. (EMNLP), pages 1173–1182. partial pooling. Synthese, 172(1):177–191. find
  20. Jayant Krishnamurthy and Thomas Kollar. 2013. Jointly learning to parse and perceive: Connecting natural language to the physical world. Transactions of the Association for Computational Linguistics (TACL), 1:193– 206. ↗
  21. Martin Lauer and Martin Riedmiller. 2000. An algorithm for distributed reinforcement learning in cooperative multi-agent systems. In International Conference on Machine Learning (ICML), pages 535–542. find
  22. Angeliki Lazaridou, Alexander Peysakhovich, and Marco Baroni. 2017. Multi-agent cooperation and the emergence of (natural) language. In International Conference on Learning Representations (ICLR). ↗
  23. David Lewis. 2008. Convention: A philosophical study. John Wiley & Sons. find
  24. Michael L. Littman. 2001. Value-function reinforcement learning in Markov games. Cognitive Systems Research, 2(1):55–66. ↗
  25. Cynthia Matuszek, Nicholas FitzGerald, Luke Zettlemoyer, Liefeng Bo, and Dieter Fox. 2012. A joint model of language and perception for grounded attribute learning. In International Conference on Machine Learning (ICML), pages 1671–1678. ↗
  26. Will Monroe and Christopher Potts. 2015. Learning in the Rational Speech Acts model. In Proceedings of 20th Amsterdam Colloquium. ↗
  27. Richard Montague. 1973. The proper treatment of quantification in ordinary English. In Approaches to Natural Language, pages 221–242. ↗
  28. Igor Mordatch and Pieter Abbeel. 2018. Emergence of grounded compositional language in multi-agent populations. In Association for the Advancement of Artificial Intelligence (AAAI). ↗
  29. Martin A. Nowak, Joshua B. Plotkin, and David C. Krakauer. 1999. The evolutionary language game. Journal of Theoretical Biology, 200(2):147–162. ↗
  30. David G. Pearce. 1984. Rationalizable strategic behavior and the problem of perfection. Econometrica: Journal of the Econometric Society, pages 1029–1050. ↗
  31. Andr’es Perea. 2012. Epistemic game theory: reasoning and choice. Cambridge University Press. find
  32. Christopher Potts. 2012. Goal-driven answers in the Cards dialogue corpus. In Proceedings of the 30th West Coast Conference on Formal Linguistics, pages 1–20. find
  33. Ciyang Qing and Michael Franke. 2014. Gradable adjectives, vagueness, and optimal language use: A speaker-oriented model. In Semantics and Linguistic Theory, volume 24, pages 23–41. ↗
  34. Yoav Shoham and Kevin Leyton-Brown. 2008. Multi-agent Systems: Algorithmic, Game-Theoretic, and Logical Foundations. Cambridge University Press. find
  35. Nathaniel J. Smith, Noah D. Goodman, and Michael C. Frank. 2013. Learning and using language via recursive pragmatic reasoning about other agents. In Advances in Neural Information Processing Systems (NIPS), pages 3039–3047. find
  36. Sainbayar Sukhbaatar, Rob Fergus, et al. 2016. Learning multiagent communication with backpropagation. In Advances in Neural Information Processing Systems (NIPS), pages 2244–2252. ↗
  37. Ming Tan. 1993. Multi-agent reinforcement learning: Independent vs. cooperative agents. In International Conference on Machine Learning (ICML), pages 330– 337. ↗
  38. Tomer D. Ullman, Yang Xu, and Noah D. Goodman. 2016. The pragmatics of spatial language. In Proceedings of the 38th Annual Conference of the Cognitive Science Society. find
  39. Adam Vogel, Max Bodoia, Christopher Potts, and Daniel Jurafsky. 2013a. Emergence of Gricean maxims from multi-agent decision theory. In North American Association for Computational Linguistics (NAACL), pages 1072–1081. find
  40. Adam Vogel, Christopher Potts, and Dan Jurafsky. 2013b. Implicatures and nested beliefs in approximate decentralized-POMDPs. In Association for Computational Linguistics (ACL), pages 74–80. find our card
  41. Tsung-Hsien Wen, Milica Gasic, Nikola Mrksic, Lina M. Rojas-Barahona, Pei-Hao Su, Stefan Ultes, David Vandyke, and Steve Young. 2017. A network-based end-to-end trainable task-oriented dialogue system. In European Association for Computational Linguistics (EACL), pages 438–449. ↗
  42. Ludwig Wittgenstein. 1953. Philosophical Investigations. Blackwell, Oxford. find
  43. Steve Young, Milica Gašić, Blaise Thomson, and Jason D. Williams. 2013. POMDP-based statistical spoken dialog systems: A review. In Proceedings of the IEEE, number 5, pages 1160–1179. ↗
  44. Steve J. Young. 2000. Probabilistic methods in spoken-dialogue systems. Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, 358(1769):1389–1402. ↗
  45. Chongjie Zhang and Victor Lesser. 2013. Coordinating multi-agent reinforcement learning with limited communication. In Proceedings of the 2013 International Conference on Autonomous Agents and Multi-agent Systems, pages 1101–1108. ↗

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/khani-2018-planning-inference-pragmatics-sequential-language/