2020

Compositional Generalization via Neural-Symbolic Stack Machines

Chen, Xinyun, Liang, Chen, Yu, Adams Wei et al.

Understand

Despite achieving tremendous success, existing deep learning models have exposed limitations in compositional generalization, the capability to learn compositional rules and apply them to unseen cases in a systematic manner.

To tackle this issue, we propose the Neural-Symbolic Stack Machine (NeSS).
It contains a neural network to generate traces, which are then executed by a symbolic stack machine enhanced with sequence manipulation operations.
NeSS combines the expressive power of neural sequence models with the recursion supported by the symbolic stack machine.

Built on

Universal grammar
R. Montague · 1970
Earlier work this paper cites.
Learning regular sets from queries and counterexamples
D. Angluin · 1987
Earlier work this paper cites.
Long short-term memory
S. Hochreiter and J. Schmidhuber · 1997
Earlier work this paper cites.
The syntactic process
M. Steedman · 2000
Earlier work this paper cites.
Syntactic structures
N. Chomsky and D. W. Lightfoot · 2002
Earlier work this paper cites.
An all-subtrees approach to unsupervised parsing
R. Bod · 2006
Earlier work this paper cites.
Grammatical inference: learning automata and grammars
C. De la Higuera · 2010
Earlier work this paper cites.
Neural turing machines
Original
A. Graves, G. Wayne, and I. Danihelka · 2014
Earlier work this paper cites.
Neural machine translation by jointly learning to align and translate
D. Bahdanau, K. Cho, and Y. Bengio · 2015
Earlier work this paper cites.
Learning to transduce with unbounded memory
E. Grefenstette, K. M. Hermann, M. Suleyman, and P. Blunsom · 2015
Earlier work this paper cites.
Inferring algorithmic patterns with stack-augmented recurrent nets
A. Joulin and T. Mikolov · 2015
Earlier work this paper cites.
Neural gpus learn algorithms
Original
Ł. Kaiser and I. Sutskever · 2015
Earlier work this paper cites.
Neural random-access machines
Original
K. Kurach, M. Andrychowicz, and I. Sutskever · 2015
Earlier work this paper cites.
Pointer networks
O. Vinyals, M. Fortunato, and N. Jaitly · 2015
Earlier work this paper cites.
Grammar as a foreign language
O. Vinyals, Ł. Kaiser, T. Koo, S. Petrov, I. Sutskever, and G. Hinton · 2015
Earlier work this paper cites.
Reinforcement learning neural turing machines-revised
Original
W. Zaremba and I. Sutskever · 2015
Earlier work this paper cites.
Span-based constituency parsing with a structure-label system and provably optimal dynamic oracles
J. Cross and L. Huang · 2016
Earlier work this paper cites.
Language to logical form with neural attention
L. Dong and M. Lapata · 2016
Earlier work this paper cites.

Similar

Neural shift-reduce ccg semantic parsing
D. Misra and Y. Artzi · 2016
Cited alongside, same era.
Neural programmer-interpreters
S. Reed and N. De Freitas · 2016
Cited alongside, same era.
Sequence-to-sequence learning as beam-search optimization
S. Wiseman and A. M. Rush · 2016
Cited alongside, same era.
Learning simple algorithms from examples
W. Zaremba, T. Mikolov, A. Joulin, and R. Fergus · 2016
Cited alongside, same era.
Making neural programming architectures generalize via recursion
J. Cai, R. Shin, and D. Song · 2017
Cited alongside, same era.
Clevr: A diagnostic dataset for compositional language and elementary visual reasoning
J. Johnson, B. Hariharan, L. van der Maaten, L. Fei-Fei, C. Lawrence Zitnick, and R. Girshick · 2017
Cited alongside, same era.
Building machines that learn and think like people
B. M. Lake, T. D. Ullman, J. B. Tenenbaum, and S. J. Gershman · 2017
Cited alongside, same era.
Shift-reduce constituent parsing with neural lookahead features
J. Liu and Y. Zhang · 2017
Cited alongside, same era.
Attention is all you need
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin · 2017
Cited alongside, same era.
Towards synthesizing complex programs from input-output examples
X. Chen, C. Liu, and D. Song · 2018
Cited alongside, same era.
Bert: Pre-training of deep bidirectional transformers for language understanding
Original
J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova · 2018
Cited alongside, same era.
Compositional attention networks for machine reasoning
D. A. Hudson and C. D. Manning · 2018
Cited alongside, same era.

Then

Automatically composing representation transformations as a means for generalization
M. B. Chang, A. Gupta, S. Levine, and T. L. Griffiths · 2019
Later among the works it cites.
Cnns found to jump around more skillfully than rnns: Compositional generalization in seq2seq convolutional networks
R. Dessì and M. Baroni · 2019
Later among the works it cites.
Neural logic machines
H. Dong, J. Mao, T. Lin, C. Wang, L. Li, and D. Zhou · 2019
Later among the works it cites.
Compositional generalization through meta sequence-to-sequence learning
B. M. Lake · 2019
Later among the works it cites.
Human few-shot learning of compositional instructions
Original
B. M. Lake, T. Linzen, and M. Baroni · 2019
Later among the works it cites.
Compositional generalization for primitive substitutions
Y. Li, L. Zhao, J. Wang, and J. Hestness · 2019
Later among the works it cites.
Neurally-guided structure inference
S. Lu, J. Mao, J. B. Tenenbaum, and J. Wu · 2019
Later among the works it cites.
The neuro-symbolic concept learner: Interpreting scenes, words, and sentences from natural supervision
J. Mao, C. Gan, P. Kohli, J. B. Tenenbaum, and J. Wu · 2019
Later among the works it cites.
Compositional generalization in image captioning
M. Nikolaus, M. Abdou, M. Lamm, R. Aralikatte, and D. Elliott · 2019
Later among the works it cites.
Learning compositional neural programs with recursive tree search and planning
T. Pierrot, G. Ligner, S. E. Reed, O. Sigaud, N. Perrin, A. Laterre, D. Kas, K. Beguir, and N. de Freitas · 2019
Later among the works it cites.
Compositional generalization in a deep seq2seq model by separating syntax and semantics
Original
J. Russin, J. Jo, R. C. O’Reilly, and Y. Bengio · 2019
Later among the works it cites.
Probabilistic neural symbolic models for interpretable visual question answering
R. Vedantam, K. Desai, S. Lee, M. Rohrbach, D. Batra, and D. Parikh · 2019
Later among the works it cites.
Good-enough compositional data augmentation
J. Andreas · 2020
Closest in time.
Permutation equivariant models for compositional generalization in language
J. Gordon, D. Lopez-Paz, M. Baroni, and D. Bouchacourt · 2020
Closest in time.
Measuring compositional generalization: A comprehensive method on realistic data
D. Keysers, N. Schärli, N. Scales, H. Buisman, D. Furrer, S. Kashubin, N. Momchev, D. Sinopalnikov, L. Stafiniak, T. Tihon, et al · 2020
Closest in time.
Learning compositional rules via neural program synthesis
Original
M. I. Nye, A. Solar-Lezama, J. B. Tenenbaum, and B. M. Lake · 2020
Closest in time.
A benchmark for systematic generalization in grounded language understanding
Original
L. Ruis, J. Andreas, M. Baroni, D. Bouchacourt, and B. M. Lake · 2020
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…