Elamur Research⌕
☰
home / papers / 2018 / Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis

Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis

Paper · 2018 · Rudy Bunel, Matthew Hausknecht, Jacob Devlin et al.

Summary

This paper addresses neural program synthesis: producing an explicit program from a handful of input-output examples. The authors identify two weaknesses of seq2seq synthesizers trained by maximum likelihood. First, they suffer from Program Aliasing: many programs can fit the same few examples, yet training rewards only the single reference program. Second, they ignore that program syntax is strict and cheap to check. To fix the first problem, a supervised model is fine-tuned with reinforcement learning so that any program consistent with the examples is rewarded. The paper also introduces beam-search-based objectives that score a set of candidate programs. To fix the second problem, the decoder masks out syntactically invalid tokens. This uses either a handwritten syntax checker or a separate LSTM that learns the grammar jointly with the synthesizer when no grammar specification exists. Experiments use the Karel educational language, which includes loops and conditionals. Both contributions improve accuracy, with the largest gains when training data is limited. This matters for any domain where correct outputs are many but annotated references are few.

Key points

  • Target domain: the Karel DSL (Pattis, 1981). Programs act on grid worlds with a hero, obstacles and markers, using while, repeat, if/ifelse and five actions. The vocabulary has 52 tokens.
  • Training methods: plain supervised learning; REINFORCE with 100 rollouts per sample; and beam-search objectives with beam size 64. One beam objective rewards the best program among C = 5 samples and has a closed-form expectation.
  • Syntax handling: grammar constraints are applied over terminal tokens rather than production rules. This allows the grammar to be learned when no formal specification is available. The syntax scores are added to the decoder logits before the softmax.
  • Architecture: each grid state is a 16×18×18 tensor. Each IO pair is encoded by a CNN with residual blocks into a 512-d vector. The decoder is a two-layer LSTM with hidden size 256, and per-pair decoder outputs are combined by max-pooling.
  • Optimization uses Adam with a learning rate of 10⁻⁴. The batch size is 128 for supervised training and 16 for RL.

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

🏢GoogleMountain View · United States533 works · 443,885 citations🏢MicrosoftRedmond · United States403 works · 162,838 citations🎓University of OxfordOxford · United Kingdom138 works · 161,448 citations

 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.Code & programming languages · 194 works

Cite

Cite as Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh and Pushmeet Kohli. 2018. Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis. arXiv:1805.04276.

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

@misc{bunel2018leveraging,
  title = {{Leveraging Grammar and Reinforcement Learning for Neural Program Synthesis}},
  author = {Rudy Bunel, Matthew Hausknecht, Jacob Devlin, Rishabh Singh and Pushmeet Kohli},
  year = {2018},
  doi = {10.48550/arxiv.1805.04276},
  eprint = {1805.04276},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1805.04276}
}

References

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

  1. Stanford CS106A course page. https://see.stanford.edu/Course/CS106A. Accessed: 2017-05-16. ↗
  2. Hour of Code. http://hourofcode.codehs.com/. Accessed: 2017-05-16. ↗
  3. Pytorch. http://pytorch.org/. Saul Amarel. Representations and modeling in problems of program formation. Rutgers University. Livingstone College. Department of Computer Science, 1970. ↗
  4. Dzmitry Bahdanau, Philemon Brakel, Kelvin Xu, Anirudh Goyal, Ryan Lowe, Joelle Pineau, Aaron Courville, and Yoshua Bengio. An actor-critic algorithm for sequence prediction. ICLR, 2017.
  5. Matej Balog, Alexander L Gaunt, Marc Brockschmidt, Sebastian Nowozin, and Daniel Tarlow. Deepcoder: Learning to write programs. In ICLR, 2017. find
  6. Rudy R Bunel, Alban Desmaison, Pawan K Mudigonda, Pushmeet Kohli, and Philip Torr. Adaptive neural compilation. In NIPS, 2016. find
  7. Jonathon Cai, Richard Shin, and Dawn Song. Making neural programming architectures generalize via recursion. In ICLR, 2017. find
  8. Jacob Devlin, Rudy R Bunel, Rishabh Singh, Matthew Hausknecht, and Pushmeet Kohli. Neural program meta-induction. 2017a. find
  9. Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy I/O. In ICML, 2017b. find
  10. Alexander L Gaunt, Marc Brockschmidt, Rishabh Singh, Nate Kushman, Pushmeet Kohli, Jonathan Taylor, and Daniel Tarlow. Terpret: A probabilistic programming language for program induction. arXiv preprint arXiv:1608.04428, 2016. find
  11. Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recurrent neural networks. In ICASSP, 2013. find
  12. Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint arXiv:1410.5401, 2014. find
  13. Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska-Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 2016. find
  14. Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. In NIPS, 2015. find
  15. Sumit Gulwani, William R Harris, and Rishabh Singh. Spreadsheet data manipulation using examples. Communications of the ACM, 2012. find
  16. Kelvin Guu, Panupong Pasupat, Evan Zheran Liu, and Percy Liang. From language to programs: Bridging reinforcement learning and maximum marginal likelihood. In ACL, 2017.
  17. Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 1997. find
  18. Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Judy Hoffman, Fei-Fei Li, C. Lawrence Zitnick, and Ross B. Girshick. Inferring and executing programs for visual reasoning. 2017.
  19. Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In NIPS, 2015. find
  20. Łukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. In ICLR, 2016. find
  21. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In NIPS, 2012.
  22. Karol Kurach, Marcin Andrychowicz, and Ilya Sutskever. Neural random-access machines. In ICLR, 2016.
  23. Matt J Kusner, Brooks Paige, and José Miguel Hernández-Lobato. Grammar variational autoencoder. In ICML, 2017. find
  24. Chengtao Li, Daniel Tarlow, Alexander L. Gaunt, Marc Brockschmidt, and Nate Kushman. Neural program lattices. In ICLR, 2017. find
  25. Percy Liang, Michael I Jordan, and Dan Klein. Learning programs: A hierarchical bayesian approach. In ICML, 2010. find
  26. Henry Lieberman. Your wish is my command: Programming by example. 2001. find
  27. Stephen Muggleton. Inductive logic programming. New generation computing, 1991. find
  28. Stephen H Muggleton, Dianhuan Lin, Niels Pahlavi, and Alireza Tamaddoni-Nezhad. Meta-interpretive learning: application to grammatical inference. Machine learning, 2014. find
  29. Arvind Neelakantan, Quoc V Le, and Ilya Sutskever. Neural programmer: Inducing latent programs with gradient descent. In ICLR, 2016. find
  30. Emilio Parisotto, Abdelrahman Mohamed, Rishabh Singh, Lihong Li, Denny Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. In ICLR, 2017.
  31. Richard E Pattis. Karel the robot: a gentle introduction to the art of programming. John Wiley & Sons, Inc., 1981. find
  32. Marc’Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojciech Zaremba. Sequence level training with recurrent neural networks. In ICLR, 2016.
  33. Scott Reed and Nando de Freitas. Neural programmer-interpreters. In ICLR, 2016. find
  34. Sebastian Riedel, Matko Bosnjak, and Tim Rocktäschel. Programming with a differentiable forth interpreter. In ICML, 2017.
  35. Phillip D Summers. A methodology for lisp program construction from examples. Journal of the ACM, 1977. find
  36. Richard J Waldinger and Richard CT Lee. Prow: A step toward automatic program writing. In IJCAI, 1969. find
  37. Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 1992. find
  38. Sam Wiseman and Alexander M Rush. Sequence-to-sequence learning as beam-search optimization. In EMNLP, 2016. find
  39. Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144, 2016. find
  40. Pengcheng Yin and Graham Neubig. A syntactic neural model for general-purpose code generation. In ACL, 2017.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bunel-2018-leveraging-grammar-reinforcement-learning-neural/