2022

Sub-Task Decomposition Enables Learning in Sequence to Sequence Tasks

Wies, Noam, Levine, Yoav, Shashua, Amnon

Understand

The field of Natural Language Processing has experienced a dramatic leap in capabilities with the recent introduction of huge Language Models.

Despite this success, natural language problems that involve several compounded steps are still practically unlearnable, even by the largest LMs.
This complies with experimental failures for end-to-end learning of composite problems that were demonstrated in a variety of domains.
An effective mitigation is to introduce intermediate supervision for solving sub-tasks of the compounded problem.

Built on

Reinforcement today
Burrhus F Skinner · 1958
Earlier work this paper cites.
A theory of the learnable
Leslie G Valiant · 1984
Earlier work this paper cites.
How to construct random functions
Oded Goldreich, Shafi Goldwasser, and Silvio Micali · 1986
Earlier work this paper cites.
A learning algorithm for continually running fully recurrent neural networks
Ronald J Williams and David Zipser · 1989
Earlier work this paper cites.
Finding structure in time
Jeffrey L Elman · 1990
Earlier work this paper cites.
Task decomposition in reinforcement learning
Jonas Karlsson · 1994
Earlier work this paper cites.
Efficient noise-tolerant learning from statistical queries
Michael Kearns · 1998
Earlier work this paper cites.
Policy invariance under reward transformations: Theory and application to reward shaping
Andrew Y Ng, Daishi Harada, and Stuart Russell · 1999
Earlier work this paper cites.
A day of great illumination: Bf skinner’s discovery of shaping
Gail B Peterson · 2004
Earlier work this paper cites.
Automatic shaping and decomposition of reward functions
Bhaskara Marthi · 2007
Earlier work this paper cites.
Flexible shaping: How learning in small steps helps
Kai A Krueger and Peter Dayan · 2009
Earlier work this paper cites.
Introduction to the theory of computation. 3th
M Sipser · 2013
Earlier work this paper cites.
Understanding machine learning: From theory to algorithms
Shai Shalev-Shwartz and Shai Ben-David · 2014
Earlier work this paper cites.
Sharp nonasymptotic bounds on the norm of random matrices with independent entries
Afonso S Bandeira and Ramon Van Handel · 2016
Earlier work this paper cites.
Complexity theoretic limitations on learning dnf’s
Amit Daniely and Shai Shalev-Shwartz · 2016
Earlier work this paper cites.
Knowledge matters: Importance of prior information for optimization
Çağlar Gülçehre and Yoshua Bengio · 2016
Earlier work this paper cites.
On the sample complexity of end-to-end training vs. semantic abstraction training
Original
Shai Shalev-Shwartz and Amnon Shashua · 2016
Earlier work this paper cites.

Similar

Limits of end-to-end learning
Tobias Glasmachers · 2017
Cited alongside, same era.
Program induction by rationale generation: Learning to solve and explain algebraic word problems
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom · 2017
Cited alongside, same era.
Failures of gradient-based deep learning
Shai Shalev-Shwartz, Ohad Shamir, and Shaked Shammah · 2017
Cited alongside, same era.
Attention is all you need
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin · 2017
Cited alongside, same era.
Neural tangent kernel: Convergence and generalization in neural networks
Arthur Jacot, Franck Gabriel, and Clément Hongler · 2018
Cited alongside, same era.
Distribution-specific hardness of learning neural networks
Ohad Shamir · 2018
Cited alongside, same era.
On the convergence rate of training recurrent neural networks
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song · 2019
Cited alongside, same era.
BERT: pre-training of deep bidirectional transformers for language understanding
Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova · 2019
Cited alongside, same era.
Explain yourself! leveraging language models for commonsense reasoning
Nazneen Fatema Rajani, Bryan McCann, Caiming Xiong, and Richard Socher · 2019
Cited alongside, same era.
Satnet: Bridging deep learning and logical reasoning using a differentiable satisfiability solver
Po-Wei Wang, Priya Donti, Bryan Wilder, and Zico Kolter · 2019
Cited alongside, same era.
On the universality of deep learning
Emmanuel Abbe and Colin Sandon · 2020
Cited alongside, same era.
Language models are few-shot learners
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei · 2020
Cited alongside, same era.

Then

Training verifiers to solve math word problems
Original
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman · 2021
Later among the works it cites.
Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies
Mor Geva, Daniel Khashabi, Elad Segal, Tushar Khot, Dan Roth, and Jonathan Berant · 2021
Later among the works it cites.
How much coffee was consumed during EMNLP 2019? fermi problems: A new reasoning challenge for AI
Ashwin Kalyan, Abhinav Kumar, Arjun Chandrasekaran, Ashish Sabharwal, and Peter Clark · 2021
Later among the works it cites.
Measuring and improving BERT’s mathematical abilities by predicting the order of reasoning
Piotr Piękos, Mateusz Malinowski, and Henryk Michalewski · 2021
Later among the works it cites.
Grokking: Generalization beyond overfitting on small algorithmic datasets
Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin, and Vedant Misra · 2021
Later among the works it cites.
Scaling language models: Methods, analysis & insights from training Gopher
Jack Rae, Sebastian Borgeaud, Trevor Cai, Katie Millican, Jordan Hoffmann, Francis Song, John Aslanides, Sarah Henderson, Roman Ring, Susannah Young, Eliza Rutherford, Tom Hennigan, Jacob Menick, Albin Cassirer, Richard Powell, George van den Driessche, Lisa Anne Hendricks, Maribeth Rauh, Po-Sen Huang, Amelia Glaese, Johannes Welbl, Sumanth Dathathri, Saffron Huang, Jonathan Uesato, John Mellor, Irina Higgins, Antonia Creswell, Nat McAleese, Amy Wu, Erich Elsen, Siddhant Jayakumar, Elena Buchatskaya, David Budden, Esme Sutherland, Karen Simonyan, Michela Paganini, Laurent Sifre, Lena Martens, Xiang Lorraine Li, Adhiguna Kuncoro, Aida Nematzadeh, Elena Gribovskaya, Domenic Donato, Angeliki Lazaridou, Arthur Mensch, Jean-Baptiste Lespiau, Maria Tsimpoukelli, Nikolai Grigorev, Doug Fritz, Thibault Sottiaux, Mantas Pajarskas, Toby Pohlen, Zhitao Gong, Daniel Toyama, Cyprien de Masson d’Autume, Yujia Li, Tayfun Terzi, Igor Babuschkin, Aidan Clark, Diego de Las Casas, Aurelia Guy, James Bradbury, Matthew Johnson, Laura Weidinger, Iason Gabriel, William Isaac, Ed Lockhart, Simon Osindero, Laura Rimell, Chris Dyer, Oriol Vinyals, Kareem Ayoub, Jeff Stanway, Lorrayne Bennett, Demis Hassabis, Koray Kavukcuoglu, and Geoffrey Irving · 2021
Later among the works it cites.
Teaching autoregressive language models complex tasks by demonstration
Original
Gabriel Recchia · 2021
Later among the works it cites.
On the provable generalization of recurrent neural networks
Lifu Wang, Bo Shen, Bo Hu, and Xing Cao · 2021
Later among the works it cites.
Which transformer architecture fits my data? a vocabulary bottleneck in self-attention
Noam Wies, Yoav Levine, Daniel Jannai, and Amnon Shashua · 2021
Later among the works it cites.
The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks
Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz · 2022
Closest in time.
Generated knowledge prompting for commonsense reasoning
Jiacheng Liu, Alisa Liu, Ximing Lu, Sean Welleck, Peter West, Ronan Le Bras, Yejin Choi, and Hannaneh Hajishirzi · 2022
Closest in time.
Show your work: Scratchpads for intermediate computation with language models
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena · 2022
Closest in time.
Measuring and narrowing the compositionality gap in language models, 2022
Original
Ofir Press, Muru Zhang, Sewon Min, Ludwig Schmidt, Noah A. Smith, and Mike Lewis · 2022
Closest in time.
Chain of thought prompting elicits reasoning in large language models
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou · 2022
Closest in time.
Star: Bootstrapping reasoning with reasoning, 2022
Original
Eric Zelikman, Yuhuai Wu, and Noah D. Goodman · 2022
Closest in time.
Computational benefits of intermediate rewards for goal-reaching policy learning
Yuexiang Zhai, Christina Baek, Zhengyuan Zhou, Jiantao Jiao, and Yi Ma · 2022
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…