Elamur Research⌕
☰
home / papers / 2021 / Communicating Natural Programs to Humans and Machines

Communicating Natural Programs to Humans and Machines

Paper · 2021 · Samuel Acquaviva, Yewen Pu, Marta Kryven et al.

Summary

ARC (Abstraction and Reasoning Corpus) is a set of puzzles on grids of colored cells. Given a few input–output examples, one has to infer the rule and apply it to a new input. Humans solve most of these tasks easily, while the best AI systems solve only a small fraction. The authors argue that the reason is language. People freely explain procedures in ordinary words, whereas machines are restricted to a narrow, predefined DSL. To test this, they built LARC, a corpus of natural-language descriptions. It was collected through a two-player game. The "describer" sees the examples and writes an instruction, and the "builder" has only this text and uses it to reproduce the answer for a new input. The authors call successful instructions "natural programs". They resemble code (loops, flood-fill) but draw on a much broader set of concepts. In addition, they contain many clarifications and verification phrases that are not direct commands. Standard program synthesis methods perform better with language hints, but solve only about 12% of the test tasks. The corpus is useful for building systems that understand human instructions where no ready-made DSL exists.

Key points

  • LARC (Language-complete ARC) contains verified text instructions for 354 of the 400 ARC tasks (88%). The data are open: github.com/samacqua/LARC. The paper was published at NeurIPS 2022 in the Datasets and Benchmarks track.
  • Annotation was carried out via Amazon Mechanical Turk. Of the 373 participants recruited, 323 were included in the analysis. A bandit-type algorithm was used to allocate effort across tasks efficiently.
  • Describers on average confirmed their own descriptions in 75% of cases. Builders correctly reproduced the answer in about 50% of attempts. The vocabulary of successful descriptions contains 642 unique words.
  • For the synthesis experiments, the authors built a DSL of 103 primitives. The best configuration (examples + natural language + pseudo-annotations) solved 22 of 183 test tasks. With text alone, without examples, at most one task could be solved.
  • For comparison: in the Kaggle competition the best systems solved up to 20% of ARC tasks, while humans solve over 80%. The authors propose not fixing the DSL in advance, but instead learning concepts from users and modeling communicative strategies that are absent from a direct "translation" of text into code.

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, topics and concepts

📚 Shelves 3The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksComputer Science Applications · 184 works

🧭 Topics 1Research subjects and languages the work is about.Reasoning · 1,948 works

Cite

Cite as Samuel Acquaviva, Yewen Pu, Marta Kryven, Theodoros Sechopoulos, Catherine Wong, Gabrielle E Ecanow, Maxwell Nye, Michael Henry Tessler and Joshua B. Tenenbaum. 2021. Communicating Natural Programs to Humans and Machines. arXiv:2106.07824.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2106.07824 · arXiv 2106.07824

@misc{acquaviva2021communicating,
  title = {{Communicating Natural Programs to Humans and Machines}},
  author = {Samuel Acquaviva, Yewen Pu, Marta Kryven, Theodoros Sechopoulos, Catherine Wong, Gabrielle E Ecanow, Maxwell Nye, Michael Henry Tessler and Joshua B. Tenenbaum},
  year = {2021},
  doi = {10.48550/arxiv.2106.07824},
  eprint = {2106.07824},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2106.07824}
}

References

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

  1. David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm. arXiv preprint arXiv:1712.01815, 2017.
  2. Adam Lerer, Hengyuan Hu, Jakob Foerster, and Noam Brown. Improving policies via search in cooperative partially observable games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7187–7194, 2020. find
  3. Brenden M Lake, Tomer D Ullman, Joshua B Tenenbaum, and Samuel J Gershman. Building machines that learn and think like people. Behavioral and brain sciences, 40, 2017. find
  4. François Chollet. On the measure of intelligence. arXiv preprint arXiv:1911.01547, 2019. find
  5. Michelene TH Chi, Robert Glaser, and Marshall J Farr. The nature of expertise. Psychology Press, 2014. find
  6. Harry F Harlow. The formation of learning sets. Psychological review, 56(1):51, 1949. find
  7. Brenden M Lake and Steven T Piantadosi. People infer recursive visual concepts from just a few examples. Computational Brain & Behavior, 3(1):54–65, 2020. find
  8. Frederic Charles Bartlett. Remembering: A study in experimental and social psychology. Cambridge University Press, 1932. find
  9. Lucas Tian, Kevin Ellis, Marta Kryven, and Josh Tenenbaum. Learning abstract structure for drawing by efficient motor program induction. Advances in Neural Information Processing Systems, 33, 2020. find
  10. Tania Lombrozo. The structure and function of explanations. Trends in cognitive sciences, 10(10):464–470, 2006. find
  11. Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. arXiv preprint arXiv:1611.01855, 2016.
  12. Kevin Ellis, Maxwell Nye, Yewen Pu, Felix Sosa, Josh Tenenbaum, and Armando Solar-Lezama. Write, execute, assess: Program synthesis with a repl. In Advances in Neural Information Processing Systems, pages 9165–9174, 2019.
  13. Armando Solar-Lezama, Liviu Tancau, Rastislav Bodik, Sanjit Seshia, and Vijay Saraswat. Combinatorial sketching for finite programs. In ACM Sigplan Notices, volume 41, pages 404–415. ACM, 2006. find
  14. Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. ICML, 2017. find
  15. Yoav Artzi and Luke Zettlemoyer. Weakly supervised learning of semantic parsers for mapping instructions to actions. Transactions of the Association for Computational Linguistics, 1:49–62, 2013.
  16. Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. Optimal neural program synthesis from multimodal specifications. arXiv preprint arXiv:2010.01678, 2020. find
  17. Yushi Wang, Jonathan Berant, and Percy Liang. Building a semantic parser overnight. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 1332–1342, 2015. find
  18. Alana Marzoev, Samuel Madden, M Frans Kaashoek, Michael Cafarella, and Jacob Andreas. Unnatural language processing: Bridging the gap between synthetic and natural language data. arXiv preprint arXiv:2004.13645, 2020. — [arXiv:2004.13645](https://arxiv.org/abs/2004.13645) find
  19. Kelvin Guu, Panupong Pasupat, Evan Zheran Liu, and Percy Liang. From language to programs: Bridging reinforcement learning and maximum marginal likelihood. arXiv preprint arXiv:1704.07926, 2017.
  20. Sumith Kulal, Panupong Pasupat, Kartik Chandra, Mina Lee, Oded Padon, Alex Aiken, and Percy Liang. Spoc: Search-based pseudocode to code. arXiv preprint arXiv:1906.04908, 2019.
  21. Aysja Johnson, Wai Keen Vong, Brenden M Lake, and Todd M Gureckis. Fast and flexible: Human program induction in abstract reasoning tasks. arXiv preprint arXiv:2103.05823, 2021. — [arXiv:2103.05823](https://arxiv.org/abs/2103.05823) find
  22. Elizabeth S Spelke, Karen Breinlinger, Janet Macomber, and Kristen Jacobson. Origins of knowledge. Psychological review, 99(4):605, 1992. find
  23. W. McCarthy, R.D. Hawkins, C. Holdaway, H. Wang, and J Fan. Learning to communicate about shared procedural abstractions. In Proceedings of the 43rd Annual Conference of the Cognitive Science Society, 2021. find
  24. Herbert H Clark, Robert Schreuder, and Samuel Buttrick. Common ground at the understanding of demonstrative reference. Journal of verbal learning and verbal behavior, 22(2):245–258, 1983. find
  25. Herbert H Clark and Deanna Wilkes-Gibbs. Referring as a collaborative process. Cognition, 22(1):1–39, 1986. find
  26. Yoav Artzi, Dipanjan Das, and Slav Petrov. Learning compact lexicons for ccg semantic parsing. 2014. find
  27. Sida I Wang, Percy Liang, and Christopher D Manning. Learning language games through interaction. arXiv preprint arXiv:1606.02447, 2016. find
  28. Yewen Pu, Kevin Ellis, Marta Kryven, Josh Tenenbaum, and Armando Solar-Lezama. Program synthesis with pragmatic communication. Advances in Neural Information Processing Systems, 33, 2020. find
  29. Sumit Gulwani, José Hernández-Orallo, Emanuel Kitzelmann, Stephen H Muggleton, Ute Schmid, and Benjamin Zorn. Inductive programming meets the real world. Communications of the ACM, 58(11):90–99, 2015. find
  30. Bobby R Bruce, Tianyi Zhang, Jaspreet Arora, Guoqing Harry Xu, and Miryung Kim. Jshrink: in-depth investigation into debloating modern java applications. In Proceedings of the 28th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering,… find
  31. César Soto-Valero, Nicolas Harrand, Martin Monperrus, and Benoit Baudry. A comprehensive study of bloated dependencies in the maven ecosystem. Empirical Software Engineering, 26(3):1–44, 2021. find
  32. Percy Liang. Learning executable semantic parsers for natural language understanding. Communications of the ACM, 59(9):68–76, 2016. find
  33. Richard Shin, Christopher H Lin, Sam Thomson, Charles Chen, Subhro Roy, Emmanouil Antonios Platanios, Adam Pauls, Dan Klein, Jason Eisner, and Benjamin Van Durme. Constrained language models yield few-shot semantic parsers. arXiv preprint arXiv:2104.08768, 2021. find
  34. Kevin Ellis, Catherine Wong, Maxwell Nye, Mathias Sable-Meyer, Luc Cary, Lucas Morales, Luke Hewitt, Armando Solar-Lezama, and Joshua B Tenenbaum. Dreamcoder: Growing generalizable, interpretable knowledge with wake-sleep bayesian program learning. arXiv preprint arXiv:2006.08381, 2020.
  35. John F Kelley. An iterative design methodology for user-friendly natural language office information applications. ACM Transactions on Information Systems (TOIS), 2(1):26–41, 1984. find
  36. Paweł Budzianowski, Tsung-Hsien Wen, Bo-Hsiang Tseng, Inigo Casanueva, Stefan Ultes, Osman Ramadan, and Milica Gašić. Multiwoz–a large-scale multi-domain wizard-of-oz dataset for task-oriented dialogue modelling. arXiv preprint arXiv:1810.00278, 2018.
  37. Tsung-Hsien Wen, David Vandyke, Nikola Mrksic, Milica Gasic, Lina M Rojas-Barahona, Pei-Hao Su, Stefan Ultes, and Steve Young. A network-based end-to-end trainable task-oriented dialogue system. arXiv preprint arXiv:1604.04562, 2016.
  38. Elizabeth S. Spelke and Katherine D. Kinzler. Core knowledge. Developmental Science, 10(1):89–96, 2007. find
  39. Yuan Huang, Nan Jia, Junhuai Shu, Xinyu Hu, Xiangping Chen, and Qiang Zhou. Does your code need comment? Software: Practice and Experience, 50(3):227–245, 2020. find
  40. Armando Solar Lezama. Program Synthesis By Sketching. PhD thesis, 2008.
  41. Karim Lari and Steve J Young. The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer speech & language, 4(1):35–56, 1990. find
  42. Eyal Dechter, Jon Malmaud, Ryan P Adams, and Joshua B Tenenbaum. Bootstrap learning via modular concept discovery. In Twenty-Third International Joint Conference on Artificial Intelligence, 2013. find
  43. Wong Catherine, Levin Ellis, Jacob Andreas, and Joshua Tenenbaum. Leveraging natural language for program search and abstraction learning. Thirty-eighth International Conference on Machine Learning, 2021. find
  44. Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. arXiv preprint arXiv:1910.10683, 2019.
  45. Robin Jia and Percy Liang. arXiv:1606.03622, 2016. Data recombination for neural semantic parsing. find
  46. Reginald Long, Panupong Pasupat, and Percy Liang. Simpler context-dependent logical forms via model projections. arXiv preprint arXiv:1606.05378, 2016.
  47. Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.07732, 2021. arXiv preprint
  48. Shin’ya Nakajima and James F Allen. A study on prosody and discourse structure in cooperative dialogues. Phonetica, 50(3):197–210, 1993. find
  49. Jacob Andreas, John Bufe, David Burkett, Charles Chen, Josh Clausman, Jean Crawford, Kate Crim, Jordan DeLoach, Leah Dorner, Jason Eisner, et al. Task-oriented dialogue as dataflow synthesis. Transactions of the Association for Computational Linguistics, 8:556–571, 2020.
  50. Ryan Volum, Sudha Rao, Michael Xu, Gabriel A DesGarennes, Chris Brockett, Benjamin Van Durme, Olivia Deng, Akanksha Malhotra, and Bill Dolan. Craft an iron sword: Dynamically generating interactive game characters by prompting large language models tuned on code. In The Third Wordplay: When Language… find
  51. Alane Suhr, Claudia Yan, Jacob Schluger, Stanley Yu, Hadi Khader, Marwa Mouallem, Iris Zhang, and Yoav Artzi. Executing instructions in situated collaborative interactions. arXiv preprint arXiv:1910.03655, 2019.
  52. Peter Anderson, Qi Wu, Damien Teney, Jake Bruce, Mark Johnson, Niko Sünderhauf, Ian Reid, Stephen Gould, and Anton Van Den Hengel. Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments. In Proceedings of the IEEE conference on computer vision and…
  53. Pratyusha Sharma, Antonio Torralba, and Jacob Andreas. Skill induction and planning with latent language. arXiv preprint arXiv:2110.01517, 2021.
  54. Theodore R Sumers, Mark K Ho, Robert D Hawkins, Karthik Narasimhan, and Thomas L Griffiths. Learning rewards from linguistic feedback. arXiv preprint arXiv:2009.14715, 2020. — [arXiv:2009.14715](https://arxiv.org/abs/2009.14715) find
  55. Royi Lachmy, Valentina Pyatkin, and Reut Tsarfaty. Draw me a flower: Grounding formal abstract structures stated in informal natural language. arXiv preprint arXiv:2106.14321, 2021. — [arXiv:2106.14321](https://arxiv.org/abs/2106.14321) find
  56. Anjali Narayan-Chen, Prashant Jayannavar, and Julia Hockenmaier. Collaborative dialogue in minecraft. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 5405–5415, 2019.
  57. Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde, Jared Kaplan, Harri Edwards, Yura Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. arXiv preprint arXiv:2107.03374, 2021.
  58. Jean-Baptiste Alayrac, Jeff Donahue, Pauline Luc, Antoine Miech, Iain Barr, Yana Hasson, Karel Lenc, Arthur Mensch, Katie Millican, Malcolm Reynolds, et al. Flamingo: a visual language model for few-shot learning. arXiv preprint arXiv:2204.14198, 2022.
  59. Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen. Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.06125, 2022.
  60. Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning, pages 8748–8763. PMLR, 20…
  61. Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv:1410.5401, 2014. find
  62. Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le. Finetuned language models are zero-shot learners. arXiv preprint arXiv:2109.01652, 2021.
  63. Yizao Wang, Jean-Yves Audibert, and Rémi Munos. Infinitely many-armed bandits. In Advances in Neural Information Processing Systems, 2008. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/acquaviva-2021-communicating-natural-programs-humans-machines/