We address the problem of teaching an RNN to approximate list-processing algorithms given a small number of input-output training examples. Our approach is to generalize the idea of parametricity from programming language theory to formulate a semantic property that distinguishes common algorithms from arbitrary non-algorithmic functions. This characterization leads naturally to a learned data augmentation scheme that encourages RNNs to learn algorithmic behavior and enables small-sample learning in a variety of list-processing tasks. Since the earliest days of neural network research, some of the most important questions about neural models have focused on their ability to capture the crispness, systematicity and compositionality that characterize symbolic computation and human cognition BID2 BID11 , and to do so with a human-like number of examples BID10 . While recent studies have demonstrated promising results in training recurrent neural networks (RNNs) to approximate symbolic algorithms in domains like list manipulation BID4 BID7 , binary arithmetic BID8 , graph traversal BID3 , and planar geometry BID12 , the question of sample efficiency remains very much open. Difficult algorithmic problems may require tens or hundreds of thousands of labelled training examples, and even simple tasks on small inputs seem to require more data than should be necessary BID9 .Our goal in this paper is to teach RNNs to approximate list-processing algorithms f :: DISPLAYFORM0 . Inspired by the idea of parametricity BID13 ) from type theory and functional programming, we hypothesize that a feature that distinguishes many algorithms from arbitrary functions is that they commute with some family of element-wise changes to their inputs. We describe a method for learning this family from the training set D, and show how this learned information can be used to create an augmented training set for an RNN. Our experiments show that this augmentation scheme makes it possible to approximate algorithms from small training sets, in some cases requiring only a single example per input list length.
Learned data augmentation instills algorithm-favoring inductive biases that let RNNs learn list-processing algorithms from fewer examples.
{"src": "scitldr-AIC_train", "paper_id": "r1lQeoCVu4"}