Neural Sequence to grid Module for Learning Symbolic Rules
Venue: AAAI
Year: 2021

Logical reasoning tasks over symbols, such as learning arithmetic operations and computer program evaluations, have become challenges to deep learning. In particular, even stateof the art neural networks fail to achieve out of distribution (OOD) generalization of symbolic reasoning tasks, whereas humans can easily extend learned symbolic rules. To resolve this difficulty, we propose a neural sequence to grid (seq2grid) module, an input preprocessor that automatically segments and aligns an input sequence into a grid. As our module outputs a grid via a novel differentiable mapping, any neural network structure taking a grid input, such as ResNet or TextCNN, can be jointly trained with our module in an end to end fashion. Extensive experiments show that neural networks having our module as an input preprocessor achieve OOD generalization on various arithmetic and algorithmic problems including number sequence prediction problems, algebraic word problems, and computer program evaluation problems while other state of the art sequence transduction models cannot. Moreover, we verify that our module enhances TextCNN to solve the bAbI QA tasks without external memory. Symbolic reasoning tasks such as learning arithmetic operations or evaluating computer programs offer solid standards for validating the logical inference abilities of deep learning models. Among machine learning tasks, symbolic reasoning problems are apt for testing mathematical, algorithmic, and systematic reasoning as they have strict rules mapping a given input to a well defined unique target. In particular, a large body of works on deep learning has considered sequence transduction problems for symbolic reasoning. Some symbolic problems such as copying sequences (Dehghani et al. 2018; Graves, Wayne, and Danihelka 2014; Grefenstette et al. 2015; Rae et al. 2016; Zaremba and Sutskever 2014) and arithmetic addition (Graves, Wayne, and Danihelka 2014; Joulin and Mikolov 2015; Kaiser and Sutskever 2015; Kalchbrenner, Danihelka, and Graves 2015; Saxton et al. 2019; Wangperawong 2018) can be solved after understanding simple rules regardless of the inputs. Others demand a deep learning model to discover necessary rules and apply them depending on inputs given as natural language words (Li et al. 2019; Wang, Liu, and Shi 2017; WeCopyright (c) 2021, Association for the Advancement of Artificial Intelligence (www.aaai.org) All rights reserved. ston et al. 2015) complex mathematical equations (Lample and Charton 2019) or programming snippets (Zaremba and Sutskever 2014) Among them, symbolic reasoning problems can test whether a trained deep learning model can systematically extend rules to out of distribution (OOD) data that follow a distinct distribution from the training data (Keysers et al. 2019; Lake and Baroni 2017; Saxton et al. 2019) For instance, a model for the addition problem whose training inputs are a pair of numbers up to five digits, say 5872+13, can face an OOD input of a pair of two 6 digit numbers upon the testing phase, e.g. 641436+135321. Human intelligence with algebraic mind can naturally extend learned rules (Marcus 2001) yet it is non trivial to equip deep learning models for sequence transduction problems to handle OOD generalization. However, it has been found that popular sequence transduction neural networks, such as LSTM seq2seq model (Sutskever, Vinyals, and Le 2014) and Transformer (Vaswani et al. 2017) rarely extend learned rules in that they are inclined to mimic the training data distribution (Dehghani et al. 2018; Lake and Baroni 2017) There have been significant initial efforts to improve a model's abilities to extend learned rules. However, their success has been dependent on the direct use of numerical values (Trask et al. 2018) or has been limited to rudimentary logic such as copying sequences (Dehghani et al. 2018; Graves, Wayne, and Danihelka 2014; Grefenstette et al. 2015; Rae et al. 2016; Zaremba and Sutskever 2014) and binary arithmetic (Graves, Wayne, and Danihelka 2014; Joulin and Mikolov 2015; Kaiser and Sutskever 2015) Furthermore, OOD generalization on symbolic problems for complex or contextdependent logic forms such as decimal arithmetic, algebraic word problems, computer program evaluation problems has not been tackled. Our objective is to fill this gap and design a module that helps neural networks to achieve OOD generalization in these problems. One observation from a previous study (Nam, Kim, and Jung 2019) is that typical sequence transduction neural networks cannot process OOD instances of number sequence prediction problems, such as predicting a Fibonacci sequence. However, when an input sequence is manually segmented and aligned into a grid of digits, a CNN can easily process OOD instances. This means providing the aligned ar X iv :2 10 1. 04 92 1v 1 cs .L G 1 3 Ja n 20 21 grid input enables to exploit inductive bias by the convolution's local and parallel computation. The grid, however, must be handcrafted in the study, which is inapplicable for general sequence transduction tasks. Overcoming this limitation requires a new input preprocessing module that automatically aligns an input sequence into a grid without supervision for the alignment. In this work, we propose a neural sequence to grid (seq2grid) module, an input preprocessor that learns how to segment and align an input sequence into a grid. The grid syntactically aligned by our module is then semantically decoded by a neural network. In particular, our module produces a grid by a novel differentiable mapping called nested list operation inspired by Stack RNN (Joulin and Mikolov 2015) This mapping enables a joint training of our module and the neural network in an end to end fashion via a backpropagation. Experimental results show that ResNets with our seq2grid module achieve OOD generalization on various arithmetic and algorithmic reasoning problems, such as number sequence prediction problems, algebraic word problems, and computer program evaluation problems. These are nearly impossible for other contemporary sequence to sequence models including LSTM seq2seq models and Transformerbased models. Specifically, we find that the seq2grid can infuse an input context into a grid so that doing arithmetic under linguistic instructions or selecting the true branch of if/else statements in code snippets become possible. Further, we demonstrate that the seq2grid module can enhance TextCNN to solve the bAbI QA tasks without the help of external memory. From all the aforementioned problems, we verify the generality of the seq2grid module in that it automatically preprocesses the sequential input into the grid input in a data driven way. Motivation for Sequence to grid  To demonstrate the benefits of the sequence to grid preprocessing method for symbolic reasoning tasks, we devise a toy decimal addition problem in two different setups: sequential and grid structured.  1 illustrates how the problem is defined in both setups and shows why alignment on a grid makes it easier. If the lengths of the numbers increase, the temporal distances between corresponding digits, e.g. 2 and 3, also increase in the sequential setup. However, the spatial distances between them remain constant in the grid structured setup since they are manually aligned according to their digits. Therefore, we can expect that the local and parallel nature of convolution will extend the rule to longer inputs, while sequence transduction models will struggle to handle the increased distances. To see this, we trained deep learning models1 using numbers up to five digits and validate on six separate validation sets, each of which contains only k digit (k=3, 8) numbers. Hence, the validation results from the former three sets tested in distribution (ID) generalization, whereas the latThe models had the same configurations used in arithmetic and algorithmic problems (refer to experiments) except for the CNN that was the grid decoder of the S2G CNN. 5 8 2 2 1 3 5 8 2 2 1 3 Sequential Input