Elamur Research⌕
☰
home / papers / 2017 / From Language to Programs: Bridging Reinforcement Learning and Maximum Marginal Likelihood

From Language to Programs: Bridging Reinforcement Learning and Maximum Marginal Likelihood

Summary

The paper tackles weakly supervised semantic parsing, where natural language instructions must be turned into executable programs but training data provide only the correct execution outcome, not the program itself. The central difficulty is spurious programs, which reach the correct result through a wrong interpretation of the utterance. The authors show that reinforcement learning (REINFORCE-style expected reward) and maximum marginal likelihood (MML) optimize closely related objectives, and they explain why both tend to lock onto short spurious programs. They propose RANDOMER, which combines two components. Randomized beam search mixes MML's systematic beam search with RL-style random off-policy exploration. A β-meritocratic update reweights the gradient so that all reward-earning programs are boosted more evenly. They use RANDOMER to train a new neural encoder-decoder parser that emits programs in a stack-based postfix language. Evaluated on the context-dependent SCONE dataset, the method outperforms standard RL and MML training and sets a new state of the art. This matters because learning from outcomes alone is cheaper than annotating programs.

Key points

  • SCONE (Long et al., 2016) covers three domains, ALCHEMY, TANGRAMS and SCENE, which test ellipsis, action anaphora and entity anaphora respectively. Each domain has about 3,700 training and 900 test examples, with 5 utterances per example.
  • Spurious programs are pervasive: the authors find at least 1,600 programs per example on average that yield the correct final state. SCENE alone admits more than 10^15 well-formed programs.
  • The parser uses a bidirectional LSTM over fixed GloVe embeddings, attention, and a feed-forward decoder. Execution history is represented either as the last k=4 tokens (TOKENS) or as an embedding of the program stack (STACK).
  • RANDOMER beats Long et al. (2016) in all three SCONE domains, with a gain of over 30% accuracy on the hardest domain. Beam-search MML, by contrast, tends to overfit a single spurious program.
  • Code is released at github.com/kelvinguu/lang2program, with reproducible experiments on CodaLab.

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

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/p17-1097 · arXiv 1704.07926

@inproceedings{guu2017language,
  title = {{From Language to Programs: Bridging Reinforcement Learning and Maximum Marginal Likelihood}},
  author = {Guu, Kelvin and Pasupat, Panupong and Liu, Evan and Liang, Percy},
  booktitle = {Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2017},
  doi = {10.18653/v1/p17-1097},
  eprint = {1704.07926},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/p17-1097}
}

References

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

  1. M. Abadi, A. Agarwal, P. Barham, E. Brevdo, Z. Chen, C. Citro, G. S. Corrado, A. Davis, J. Dean, M. Devin, S. Ghemawat, I. J. Goodfellow, A. Harp, G. Irving, M. Isard, Y. Jia, R. Józefowicz, L. Kaiser, M. Kudlur, J. Levenberg, D. Mané, R. Monga, S. Moore, D. G. Murray, C. Olah, M. Schuster, J. Shl… find our card
  2. Y. Artzi and L. Zettlemoyer. 2011. Bootstrapping semantic parsers from conversations. In Empirical Methods in Natural Language Processing (EMNLP). pages 421–432. find
  3. Y. Artzi and L. Zettlemoyer. 2013. Weakly supervised learning of semantic parsers for mapping instructions to actions. Transactions of the Association for Computational Linguistics (TACL) 1:49–62. find our card
  4. D. Bahdanau, K. Cho, and Y. Bengio. 2015. Neural machine translation by jointly learning to align and translate. In International Conference on Learning Representations (ICLR). find our card
  5. M. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos. 2016. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems (NIPS). pages 1471–1479. find
  6. S. Bengio, O. Vinyals, N. Jaitly, and N. Shazeer. 2015. Scheduled sampling for sequence prediction with recurrent neural networks. In Advances in Neural Information Processing Systems (NIPS). pages 1171– 1179. find
  7. S. Branavan, H. Chen, L. S. Zettlemoyer, and R. Barzilay. 2009. Reinforcement learning for mapping instructions to actions. In Association for Computational Linguistics and International Joint Conference on Natural Language Processing (ACL-IJCNLP). pages 82–90. find
  8. K. Clark and C. D. Manning. 2016. Deep reinforcement learning for mention-ranking coreference models. arXiv preprint arXiv:1609.08667 . find our card
  9. J. Clarke, D. Goldwasser, M. Chang, and D. Roth. 2010. Driving semantic parsing from the world’s response. In Computational Natural Language Learning (CoNLL). pages 18–27. find
  10. R. Coulom. 2006. Efficient selectivity and backup operators in Monte-Carlo tree search. In International Conference on Computers and Games. pages 72–83. find
  11. A. P. Dempster, L. N. M., and R. D. B. 1977. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B 39(1):1–38. find
  12. L. Dong and M. Lapata. 2016. Language to logical form with neural attention. In Association for Computational Linguistics (ACL). find
  13. M. O. Duff. 2002. Optimal Learning: Computational procedures for Bayes-adaptive Markov decision processes. Ph.D. thesis, University of Massachusetts Amherst. find
  14. X. Glorot and Y. Bengio. 2010. Understanding the difficulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Statistics. find
  15. R. Jia and P. Liang. 2016. Data recombination for neural semantic parsing. In Association for Computational Linguistics (ACL). find
  16. M. Kearns and S. Singh. 2002. Near-optimal reinforcement learning in polynomial time. Machine Learning 49(2):209–232. find
  17. D. Kingma and J. Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 . find
  18. J. Krishnamurthy and T. Mitchell. 2012. Weakly supervised training of semantic parsers. In Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP/CoNLL). pages 754–765. find
  19. S. Levine. 2014. Motor Skill Learning with Local Trajectory Methods. Ph.D. thesis, Stanford University. find
  20. J. Li, W. Monroe, A. Ritter, D. Jurafsky, M. Galley, and J. Gao. 2016. Deep reinforcement learning for dialogue generation. In Empirical Methods in Natural Language Processing (EMNLP). find our card
  21. C. Liang, J. Berant, Q. Le, and K. D. F. N. Lao. 2017. Neural symbolic machines: Learning semantic parsers on Freebase with weak supervision. In Association for Computational Linguistics (ACL). find
  22. P. Liang, M. I. Jordan, and D. Klein. 2011. Learning dependency-based compositional semantics. In Association for Computational Linguistics (ACL). pages 590–599. find
  23. R. Long, P. Pasupat, and P. Liang. 2016. Simpler context-dependent logical forms via model projections. In Association for Computational Linguistics (ACL). find
  24. O. Nachum, M. Norouzi, and D. Schuurmans. 2016. Improving policy gradient by exploring under-appreciated rewards. arXiv preprint arXiv:1611.09321 . — [arXiv:1611.09321](https://arxiv.org/abs/1611.09321) find
  25. K. Narasimhan, T. Kulkarni, and R. Barzilay. 2015. Language understanding for text-based games using deep reinforcement learning. arXiv preprint arXiv:1506.08941 . find
  26. A. Neelakantan, Q. V. Le, and I. Sutskever. 2016. Neural programmer: Inducing latent programs with gradient descent. In International Conference on Learning Representations (ICLR). find
  27. M. Norouzi, S. Bengio, N. Jaitly, M. Schuster, Y. Wu, D. Schuurmans, et al. 2016. Reward augmented maximum likelihood for neural structured prediction. In Advances In Neural Information Processing Systems. pages 1723–1731. find
  28. F. J. Och. 2003. Minimum error rate training in statistical machine translation. In Association for Computational Linguistics (ACL). pages 160–167. find
  29. I. Osband, C. Blundell, A. Pritzel, and B. V. Roy. 2016. Deep exploration via bootstrapped DQN. In Advances In Neural Information Processing Systems. pages 4026–4034. find
  30. I. Osband, B. V. Roy, and Z. Wen. 2014. Generalization and exploration via randomized value functions. arXiv preprint arXiv:1402.0635 . — [arXiv:1402.0635](https://arxiv.org/abs/1402.0635) find
  31. A. Venkatraman, M. Hebert, and J. A. Bagnell. 2015. Improving multi-step prediction of learned time series models. In Association for the Advancement of Artificial Intelligence (AAAI). pages 3024–3030. find
  32. R. J. Williams. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning 8(3):229–256. find
  33. R. J. Williams and J. Peng. 1991. Function optimization using connectionist reinforcement learning algorithms. Connection Science 3(3):241–268. find
  34. P. Yin, Z. Lu, H. Li, and B. Kao. 2015. Neural enquirer: Learning to query tables. arXiv preprint arXiv:1512.00965 . — [arXiv:1512.00965](https://arxiv.org/abs/1512.00965) find
  35. A P. Pasupat and P. Liang. 2015. Compositional semantic parsing on semi-structured tables. In Association for Computational Linguistics (ACL). find
  36. P. Pasupat and P. Liang. 2016. Inferring logical forms from denotations. In Association for Computational Linguistics (ACL). find
  37. J. Pennington, R. Socher, and C. D. Manning. 2014. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP). find
  38. M. Ranzato, S. Chopra, M. Auli, and W. Zaremba. 2015. Sequence level training with recurrent neural networks. arXiv preprint arXiv:1511.06732 . find our card
  39. S. Reddy, M. Lapata, and M. Steedman. 2014. Large-scale semantic parsing without question-answer pairs. Transactions of the Association for Computational Linguistics (TACL) 2(10):377–392. find
  40. S. Riedel, M. Bosnjak, and T. Rocktäschel. 2016. Programming with a differentiable forth interpreter. CoRR, abs/1605.06640 . find
  41. S. Ross, G. Gordon, and A. Bagnell. 2011. A reduction of imitation learning and structured prediction to no-regret online learning. In Artificial Intelligence and Statistics (AISTATS). find
  42. S. Shen, Y. Cheng, Z. He, W. He, H. Wu, M. Sun, and Y. Liu. 2015. Minimum risk training for neural machine translation. arXiv preprint arXiv:1512.02433 . find our card
  43. D. A. Smith and J. Eisner. 2006. Minimum risk annealing for training log-linear models. In International Conference on Computational Linguistics and Association for Computational Linguistics (COL-ING/ACL). pages 787–794. find
  44. R. Sutton, D. McAllester, S. Singh, and Y. Mansour. 1999. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems (NIPS). find
  45. Hyperparameters in Table 2 System REINFORCE BS-MML find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/guu-2017-language-programs-bridging-reinforcement-learning/