Simple deductive reasoning tests and numerical data sets for exposing limitation of today's deep neural networks
Authors: Kalidas Yeturu
Manish Kumar Srivastava
Venue:  (2021)
Keywords: inductive reasoning
deductive reasoning
neural network
memory
feature engineering

Abstract: Learning for Deductive Reasoning is an open problem in the machine learning world today. 
Deductive reasoning involves storing facts in memory and generation of newer facts over time. 
The concept of memory, processor and code in deduction systems is fundamentally different from the purpose and formulation of weights in a deep neural network. 
A majority of the machine learning models are inductive reasoning models including state of the art deep neural networks which are effectively tensor interpolation based models.
A step towards realization of memory is through recurrent neural networks and its variants, however the formal representation is not sufficient enough to capture a complex mapping function between input and output patterns.
Deep neural networks are positioned to do away with feature engineering which is essentially deductive reasoning methodology.
There are existing works in deductive reasoning in neural networks that require learning of syntax, unification and deduction and operate on text data as sequence of tokens.
However the performance of deductive reasoning networks is far from perfection which may be either due to syntax or deduction aspects.
In this context, we have proposed a suite of completely numeric data sets which do not require parsing as with text data.
The 10 data sets are for - (a) selection (3 data sets) - minimum, maximum and top 2nd element in an array of numbers; (b) matching (3 data sets) - duplicate detection, counting and histogram learning; (c) divisibility tests (2 data sets) - divisibility of two numbers and divisibility by 3; (d) representation (2 data sets) - binary representation and parity. 
Though extremely simple in terms of feature engineering, in all of these tests, simple deep neural networks, random forest and recurrent neural networks have failed with very low accuracies. 
We propose these as numerical test-bed for testing learning models for deductive reasoning.

Under review as a conference paper at ICLR 2021
SIMPLE DEDUCTIVE REASONING TESTS AND NUMER- ICAL DATA SETS FOR EXPOSING LIMITATION OF TO- DAY'S DEEP NEURAL NETWORKS
Anonymous authors
Paper under double-bling brindd review
ABSTRACT
Learning for Deductive Reasoning is open problem in the machine learning world today. Deductive reasoning involves storing facts memory and gener- ation of newer facts over time. The concept of memory, processor and code in deduction systems is fundamentally different from the purpose and formulation of weights in a deep neural network. A majority of the machine learning mod- els are inductive reasoning models including state of the art deep neural networks which are effectively tensor interpolation based models. A step towards realiza- tion of memory is through recurrent neural networks and its variants, however the formal representation is not sufficient enough to capture a complex mapping func- tion between input and output patterns. Deep neural networks are positioned to do away with feature engineering which essentially deductive reasoning method- ology. There are existing works in deductive reasoning in neural networks that require learning of syntax, unification and deduction and operate on text data as sequence of tokens. However the performance of deductive reasoning networks is far from perfection which may be either due to syntax or deduction aspects. this context, have proposed suite of completely numeric data sets which do not require parsing as with text data. The 10 data sets are for (a) selection (3
data sets) minimum, maximum and top 2nd element in an array of numbers; (b)
matching (3 data sets) duplicate detection, counting and histogram learning; (c)
divisibility tests (2 data sets) divisibility of two numbers and divisibility by 3; (d)
representation (2 data sets) binary representation and parity. Though extremely simple in terms of feature engineering. in all of these tests, simple deep neural networks, random forest and recurrent neural networks have failed with very low accuracies. We propose these as numerical test-bed for testing learning models for deductive reasoning.
INTRODUCTION
Deductive reasoning is branch of artificial intelligence where inferences represented tions or facts over data (Khemani] 2013). Starting with a set of given facts, the system combines facts based on rules to generate newer facts and update the knowledge store. On the other hand machine learning algorithms employ induction based approaches which are predominantly pattern mapping methods (McClelland al. 1986). Fundamentally, are arithmetically combined, logically filtered, scaled up scaled down and mapped to the target vector of interest. tensor is a more generalization of the vector representation mathematically. However typically even a tensor is internally represented as an array of contiguous storage locations with a data structure indicating dimensions. These tensors undergo a pipeline of transformations minimizing eтгог function there by mapping a tensor the other side. Deep neural networks have demonstrated their performance almost at the level of human even better in computer vision and other domains (Bengio et al. 2017).
pipeline of operations, the vectors
side of the pipeline the tensor
Although promising to see the success of deep neural networks (Dargan et al. 2019) (DNN) there seems to be popular belief and false opinion that they suitable for all types of problems. is important to note here that problem statements solved by DNNs are of mainly of interpolation in nature where tensors are combined along the pipeline to produce the output tensor. The vanilla

---

Under review as a conference paper at ICLR 2021
DNNs not directly suitable for deductive reasoning type of problem statements. A knowledge base in a deductive reasoning methodology is a storage for facts which are modified over time. For instance, counting number of ones in binary representation of the input, the current count is fact and as the algorithm iterates over input, the count value gets updated. Most of the iterations input, be represented in declarative style first order logic statements such pro- log (Bratko) 2001). The weight space representation of deep neural network is not a convenient formulation to capture the facts, unification and inference mechanism as required by a deductive reasoning methodology. However, earlier version of machine learning formulations required feature engineering which itself accommodates for deductive reasoning in the form of outputs of human crafted programs which are added as features.
There are on-going research efforts this direction on modification of neural network architectures to enable them for performing deduction reasoning. A small step in the direction of storage of past information data is recurrent neural network formulation and its several variants (Mikolov al.] 2011). Most of the existing works employ recurrent neural network based formulation and its variations due to the fundamental need of the notion of memory in a deductive reasoning setting. We have tabulated the observations in the form of Table
Citation (Nangia
Data
Processing
&
Input a string list operations and elements such minimum and maxi- mum. Output is the result of list opera- tions. They have released ListOps data set.
TreeLSTM (Tai et al. 2015b
Bowman
2018)
(Saxton et al. 2019)
Input is stream of sequences tokens. A specific sequence is defined ques- tion. The output is again sequence of tokens corresponding to answer.
They have used an RNN based formulation for question question-answer answer system.
(Wu
et
al. Irving
Input is a string of tokens corresponding truth statements of theorem. Out- put is a string of tokens corresponding proof for the theorem identification of top few premises.
They have used a variation of RNN formula- tion.
2020
et al.
2016
Gauthier al.
et
2020
Bansal
al.
2019;
Polu
Sutskever
2020;
Evans
et al.
2018
Lample
&
Charton
2019)
Yang
&
Input is a string of knowledgebase and theorem. Output is string of proof statements. They also release CoqGym data set 71K proofs.
A TreeLSTM (Tai et al. 2015b) formulation used.
Deng
2019
(Huang et al. 2018)
Imput string representation of theo- rem. Output is estimation of number of
RNN based formulation.
steps required to finish and prediction of the next expression.
(Piotrowski
Input is string of tokens corresponding to polynomial coefficients in symbolic form before normalization. Output is a
They have used RNN based formulation.
al. 2019
normalized equivalent expression.
Paliwal et al.
Input is string of tokens correspond- ing theorem. Output is string of to- kens corresponding to the first step of
The authors have used Graph Neural Net-
2020)
works (Zhou et al. 2018).
the proof.
2

---

Under review as a conference paper at ICLR 2021
(Hahn
ct al.
Input a string of tokens correspond- ing representation of arithmetic and logical expression. Output is an equiv- alent expression in another representa- tion.
Sequence to sequence mapping using RNN based formulation. In (Rabe et al. (2200) they introduce Skip-tree architecture.
2020:
Rabe
et al.
2020
(Xu
al.
Input: Zt. ys as numeric, Process: The- oretical study of what neural networks can and cannot do, Output: theoret- ical study, Contribution: They suggest max(, subset sumO problems.
2019)
(Wang
al.
Input is string of tokens corresponding to logical expression. Output is boolean for satisfiability a string of tokens
Some of the architectures proposed are (Xu
2019;
Xu
et al. 2018) CSP-CNN, (Amizadeh et al.
al.
2018
2018 DG-DAGRNN, (Selsam et al. 2018
Amizadeh al.
corresponding to value assignments of
NeuroSAT and RNN based formulations.
2018
variables.
Selsam
al.]
2018
Rocktäschel &
Riedel 2016)
(Vinyals al.
Input is set of tokens in tuple format (position,token). Output is a sequence of tokens.
RNN based formulation is used to carry out sorting and copy operations. The idea is to represent sequence
2015)
set.
(evvlin
Input is sequence of tokens corre- sponding to 'question'. Output an- other sequence of tokens conrrespond- ing to 'answer'.
Variants of RNN based formulation such as (Devlin et al., 2018) BERT, (Gers et al. 1999) TreeLSTM
al.
2018
Sukhbaatar
cet al.] 2013
Tai et al.
2015a Weston
al.
2014)
Grefenstette
Input and output are vector sequences.
An RNN based formulation with notion of memory the form of a stack or queue of hidden vectors. The output is generated as weighted combination these memory vec- tors (Neural stack and queue).
al. 2015)
Graves et al. Input and output are vector sequences.
An RNN to include a controller network and memory network for function selection and operand selection towards building a Neural Turing Machine.
2014)
Table 1: Literature review of the state of the art methods for deductive reasoning in deep learning.
The symbolic reasoning neural networks (Table I obtain the input is variable length string of tokens and the output is also a variable length string of tokens. Some tokens have special meaning corresponding to syntactic and semantic interpretations such opening and closing brackets, func- tion call and data. While this problem formulation is more generic in nature, the onus of parsing the input token list rests with the DNN addition to interpretation and output generation.
In a deductive reasoning setting, the concept of memory becomes critical. Some of the deductive reasoning tasks can be easily accomplished by simple computer program to result in numeric features or truth value statements. However the effect of a free form neural network do the same and without tweaking is far from reach. Basic notion of memory in an RNN formulation is the hidden vector formulation. In order to perform symbolic unification, logical operations and learn generic function from data, the hidden vector concept is reformulated for a stack or queue of vectors (Grefenstette al. 2015). The Neural Turing Machine (Graves et al. 2014) includes controller network and memory network to mimic a Turing machine and attempts to learn generic function that maps input output from data.
3

---

Under review as a conference paper at ICLR 2021
Code a cfinstrutt a;, >> P Pand b2 NtN, instruction data pairs C= [(t,,b)) h.). (*,(%): bx,)
here, ? deeenotes any metch.
Code
Instruction Queue
Deep Neural
Memory
Processor
(P)
Network?
Data (D)
Fleed set N; instructions
Data list memary Ny locationsanc values
P [< -) (V) E 1 .l,
[M) (V) My)
M the memory ocation
Values themselves pointers other locations
modif instruction or data allke
Figure 1: This picture depicts the three critical components of general purpose mapping function processor, memory and code. A deep neural network attempts model all three components in its weight space representation.
In order to learn generic mapping function from one pattern to another patter, it is important to see a basic computational model. In (Figure D we have indicated a conceptual processor, code and data. A symbolic reasoning network tries model the three entities simultaneously in the form of weights of the network. A processor has a fixed set of instructions that operate on memory, = (V) 1... .p) where Np denotes number of instructions, 1, denotes jth instruction, M denotes a memory location. The data is indicated by. D = { [M,, Vi. (vvk E 1....N NM) where NM is the number of locations, MM is the ttth memory location and V₂ is the value present the location. A program or code is indicated by C = {(a,. b;) (vi E 1.. .Nc) where a; is the instruction and b the memory location. We do here some back the envelope calculations on how many essential vectors need to be captured for instructions, memory value pairs and code. If we assume one hot encoding representation of all instructions, this would require an estimate Np NM pairs of instructions. For each of the memory locations, the values are typically floating point numbers or integers with large ranges, the possible numbers of memory-value pairs is an astronomical number Na X V&l where VVal denotes value range. Each term in program would correspond to one-hot- encoding Np x NM instruction and memory pairs. The number of programs of length Ne that can be generated would be Np x NM No. Even for a simple processor having 10 instructions, 10 memory locations and program of 10 steps, would require exploration of space of 100 vectors corresponding to each program. the process as is evident from low accuracies and high errors reported in state of the art symbolic reasoning frameworks.
not clear today, what is the best way to represent and model
As symbolic processing requires neural network learn text parsing and also learn inference from data. There are two moving parts in order to understand low accuracies observed in deductive tasks. In order specifically identify issue, have provided numerie data sets that does not require text parsing. It is also important at this stage of the state of the art, to clearly call out limitations of the existing deep neural networks and machine learning formulations on what and what not possible in more specific way. As machine learning systems operate over data sets, the first step in demonstrating what not possible via simple data sets for pattern mapping. We have created some very simple data sets where single engineered feature is sufficient enough to capture the pattern, however deep networks fail to capture the deduction patterns. The data sets are for (a) selection (3 data sets) minimum, maximum and top 2nd element in array of numbers; (b) matching (3 data sets)- - duplicate detection, counting and histogram learning; (c) divisibility tests (2 data sets) divisibility of two numbers and divisibility by 3; (d) representation (2 data sets) binary
4

---

Under review as a conference paper at ICLR 2021
S.No
Data set
Algorithm invocation
(N=100000, K=50)
MIN
SEL("min", N, K)
MAX
SEL("max", N. K)
TOP2
SEL("top 2", N. K)
BINARY
REP("parity .N,K)
SORT
SORT(N,K)
COUNT
MAT("count" .N.)
DIV
DIV3
by_3",,,,K REP("parity .N,,) MAT("duplicate" .N.K)
PARITY
DUP
Table 2: Data set name and algorithm that generated the data set are shown here.
representation and parity. We demonstrate that in all these data sets, the deep neural networks fail with very low accuracies.
The efforts in the state of the art for symbolic neural networks mainly include on parsing of the textual input, unification and deduction. These works try address based tweaking the architec- ture of the network for bringing in memory. The RNN based formulation addresses processing part. However, observe and propose for research there is additional component which is the type of neuron used. In current networks, a single neuron performs only simple arithmetic operations and a comparison against zero as ReLU, We conjecture here there is scope for innovation in increasing the computational capability of a neuron and ad-hoc connections as proposed in Webster (2012).
METHODS
In order present how deductive reasoning is fundamentally different from interpolation based reasoning, we have created ten data sets which are described in this section. Data sets are generated by invoking the algorithm as shown in the (Table
2.1 DATA SETS FOR SELECTION PROBLEMS
Identification of maximum minimum element in array of numbers, requires facts be recorded in storage, infer on top of them in the current iteration and update the storage with newer facts. The data consists D (æt, 9:) tuples E [1..N] where N 100000. Each x; R is K dimensional vector where K = 50 in our case and contains the value of an element of interest in the array, i.e. y1 mox (æ;,1, ... k.
The data set is generated as shown in the schematic (Algorithm
Algorithm Selection Data Set Generation Algorithm SEL(T.N,K)
Require: T, J.N K
(Vi E [1..N]), (Vj [[.,,])= = RAND()
* RAND()) D() function generates a random number */
** T: Type of selection, N: Number of elements in data set, K: Dimensionality of each point */
if i "max" then
(Vi E [I..N]) y1 max(x;)
else if "min" then
(Vi E [1..N]) y: min(x;)
else 7 is "top 2" then
(Vi E [1..N]) y/ mar(sel(1)) {mar((x:))
end
return (x,
5

---

Under review as a conference paper at ICLR 2021
2.2 DATA SETS FOR MATCHING PROBLEMS
The data set is almost same as for the selection problem, however here, duplicate detection and histogram learning carried out. This requires the numbers to be remembered and compared against other elements. The Duplicate data set contains of D = (T))))) tuples i E [1..N] where N 100000. Each 2; R is a K dimensional vector where K 50 in our case and yı contains either or O. 1 if a element j E I; is present more than once. The Histogram data set contains of of
100000. Each RK is K dimensional vector where K 50 in our case and contains the count of elements
(ar, y/) tuples
[1..N] where
which lies between and 10. The data set is generated as shown in the schematic (Algorithm 2
Algorithm 2 Matching Data Set Generation Algorithm MAT(..N.K
Require: T. K
(Vi E [1,,,]], (vj E [I..K])a,, = RANDO
7 RAND() D)) function generates random number*/
1 T:Type of Matching, N: Number of elements in data set, K: Dimensionality of each point */
if is "duplicate" then
(vi E [I..N]). y/ = 0, [L.K], k & & abbi = = xx(4)) y =
for (Vi E [1..NN] do
/ check if a element is present more than one time */
y/4 0
for v/j E [1..K] do
for (4k E [1..K]) do
(j + & & Figj == ti,k)
+ 3/4
end for
end for end for end if if T is "count" then
for E e (Vi'(1..NV) do
/couunt number of vector elements i= 10
for (j E [1) do
Fy.J <= 10 - 9: yt +
end for
end for
end if
return (x. 3)
2.3
DATA SETS FOR DIVISIBILITY PROBLEMS
For divisibility tests the facts are to be recorded in storage and new element is processed based on this fact and after processing, update the storage with the new fact. For example if want to perform divisibility test if 1342 is divisible by 11. At first 13 will be evaluated against 11 will give remainder 2 which new fact that we need to store and move on to next element and that's 4. Combining this element with our fact we should get 24 and that will be evaluated against 11 and will give remainder or new fact as 2. And this keeps on going until no element is left.
The Divisibility data set contains of D = (Iz; yi) tuples E [1..N] where N 100000. Each contains a tuple of two elements x; = a, and ys contains either 0 and 1, if (a mod = 0) and 0, if (a mod b + 0).
The data set is generated as shown in the schematic (Algorithm
2.4
DATA SETS FOR REPRESENTATION PROBLEMS
This contains two data sets parity data set and úi) binary representation data set. The parity data set contains of D (z,, y:) tuples where x; E R and y; denotes the parity of the w, Parity of a number is based on the number of present in it's binary representation. If number of is even then

---

Under review as a conference paper at ICLR 2021
Algorithm 3 Divisibility tests Data Set Generation Algorithm (I,(
Require: N if I''' is "divisible" then for (Vi [I..N]) do
(a. [RAND() RAND()
y1 =
(#r.0 mod 2i,1 == 0) =
end for end if
if "divisibility_bb by then
for (Vi E [1..N]), 2; RANDO) do y1 = 0
(2g mod = 0) y:
end for
end return (z,
parity of that will O. And if the number of 1 is odd then parity of that will be 1. For example we take 17. It's binary representation is 10001. It contains 2 one's 's in its binary representation so
parity of 17 O. The binary representation data set contains of D (at, ys) tuples where 2; E R and y 0, K where K is 20 in our case denotes its binary representation. For example if z; is 20
and K is then will be 0010100.
The data is generated shown in the schematic (Algorithm
Algorithm 4 Representation Data set Generator- REP(T, K)
Require: T,N,K K if "binary" then for Vi E [1..N] do
24 RAN //single number
y is binary representation of z; in K bits.
end for end if
is "parity" then
for (Vi E [1..N]] do
R7 = RAND()
binary representation x; in K bits.
r =count number of 1 in s.
/1
(r mod 2 + 0) =
end for
end if
return (2,
2.5 DATA SET FOR SORTING PROBLEM
This data set consists of 2; as a list of numbers, mapped to its sorted equivalent yi- The idea is sorting is very prominent pattern humans, however basic neurons not able to capture all of the the element to element relationships. The algorithm for sorting is shown (Algorithm 5). For example, if x; [1,3, 3, 2, 1, -9) then sorted y, - 1,,,,,,,,,33)

---

Under review as a conference paper at ICLR 2021
Algorithm 5 Sorting Test Data Set Generation Algorithm (O,
for Vi [..N] do
Vj E [1..K] m4.5 = RAND()
IN = (ORT(T.)
**Sotted version of z; in ascending order*/
(vj, k) (j < k) > (Vi. < yc,e))
end for
return (2.
2.6
MACHINE LEARNING MODELS USED IN THE STUDY
2.6.1 1 DEEP NEURAL NETWORK
The Deep Neural Networks model used for testing the datasets of layers each consisting of 100 neurons. This model was implemented Google Tensorflow et al.) 2016)
2.6.2 RANDOM FOREST
The Random forest (Liaw et al., 2002) was implemented Sci-kit LearnnPedregosa et al. 2011)
Python based library. The configuration in which we use Random forest is (max-depth=5, criterion=gini, momi-ssmlles-sppitee n-estimators=10).
2.6.3 RECURRENT NEURAL NETWORK
The RNN model we used for testing the datasets was of three layers. First layer is a LSTM (Gers et al. 1999) cell followed by two layers of RNN cell. We used Relu as activation function. The model was implemented in Google Tensorflow(Abadi al. 2016).
2.7 TRAIN AND TEST DATA SET PARTITIONS
The machine learning model is tested based bit lenient train and test partitions of 90% and 10% respectively. The training data size has been increased so as to allow the classifier to make use of more number of patterns the data sets tough for any induction based classification formulation today.
RESULTS
The performance of machine learning models on each the data sets is computed in two forms regression and classification. For those problems where the final output is numeric quantity, the problem is posed as regression and Root Mean Squared Deviation (RMSD) values are reported. The problems posed regression
selection problems, binary representation of number, sorting and count of numbers between 0 and 10 and presented in (Table 3}. For the problems where the output decision, they are posed as classification problem in our setting. The problems posed as classification are divisibility of two numbers, divisibility by 3, parity and detection of duplicate and presented in the (Table
Except for the parity problem where random forest has performed with > 92% accuracy, in rest of the places the three methods chosen for evaluation have all failed give 100% accuracies although the data sets are quite simple.
worth discussing, the parity problem in more detail on which random forest appeared to have worked (the marked observation). however we can readily observe that anything less than 100% would not be any practical use and not reliable. Consider binary representation length K elements. The total number of variations of the input is 2k In this case, the input dimensionality is
input of
50, which corresponds to a data set 20 elements amounting to a total storage of 50 x 4 20 200 peta bytes, considering floating point representation for each input element of the vector. When the input dimensionality becomes 1000, which is not uncommon, the storage requirement for data grows 1000 4 x 21000 which is astronomical number. A
8

---

Under review as a conference paper at ICLR 2021
S.No
Dataset Name
RMSD of RF
RMSD NN
RMSD of RNN
MIN
7.2788
28.2572
20.378
2
MAX
7.2788
28.398
24.397
3
TOP2
3.912
28.455
62.81
4
BINARY
30
5
SORT
00
00
0O
COUNT
10.90
28.50
4.4312
Table 3: Performance of data sets on RNN, NN and RF based on regression formulation. Root Mean
Squared Deviation (RMSD) values are computed on the output predictions.
S.No
Dataset Name
Accuracy of RF
Accuracy of NN
Accuracy of RNN
7
DIV
0.691
0.5133
0.5015
8
DIV3
0.6668
0.5279 0.6566
0,6668
9
PARITY
0.926*
0.6836
10
DUP
0.4962
0.67
0.5427
Table Performance of data sets on RNN, NN and RF based on classification formulation. Aceu- racy values are reported on the output predictions.
decision tree to successfully learn with 100% certainty requires all input patterns to be available in training. The size of the tree terms of the number of nodes is 2 1. Storing tree having 251 - nodes has practical limitations for the problem it is trying to address, as simple as parity computation. However a simple for loop through the data requires only one pass through the input and requires only constant space storage of a couple of floating point variables and predicts with 100% certainty. Having an additional feature in the input, feature engineered to compute parity (i.e. K+1 dimensional input), would reduce the amount of training data requirement to just K + points to result in 100% accuracy of any standard classifier.
Each of these problems require at least one pass through the input elements and computing logical inferences. Given multiple possible permutations of the elements of the input vector, any single pass neural network would need accommodate in some form for those many variations. However, recurrent neural networks do attempt to remember the state
4 CONCLUSIONS
We have presented here an issue with limitations of the present day deep neural networks to address deduction based inferences. Today deep neural networks are positioned to do away with feature engineering however we have demonstrated that this is not truc. is an open area of research to configure neural networks to carry out deductive reasoning. however the data sets mainly sequence of tokens in text where parsing, symbolic unification and deduction abilities come into picture. We have created simplistic data set that is purely numeric and can be directly consumed by neural networks without a need to learn parsing as well. The notion of knowledge representation storage of facts and deductive reasoning not thoroughly captured by the weight space formal representation of neural networks. We have demonstrated failure of typical multi layer perceptron deep neural networks, random forest and recurrent neural network formulations on data sets which require deduction reasoning based features. The data sets are for (a) selection (3 data sets) mini- mum, maximum and top 2nd element in an array of numbers; (b) matching data sets) - duplicate detection, counting and histogram learning; (c) divisibility tests (2 data sets). divisibility of two numbers and divisibility by 3; (d) representation (2 data sets) binary representation and parity. We also discussed the parity problem and impracticality of storage and computation to achieve full accuracy by strong classifier such as a decision tree unless a simple computation friendly feature is engineered. We have presented case for novel models for learning deductive reasoning from examples. These novel models can be combination of deduction and induction systems operating together model on top of evolutionary computational framework.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, al. Tensorflow: system for large- scale machine learning. In /2th {USENIX} symposium on operating systems design and imple- mentation ((OSDI} 16), pp. 265-283, 2016.
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer. Learning to solve circuit-sat: An un- supervised differentiable approach. In International Conference on Learning Representations, 2018.
Kshitij Bansal, Sarah Loos, Markus Rabe, Christian Szegedy, and Stewart Wilcox. Holist: An envi- ronment for machine learning of higher order logic theorem proving. In International Conference on Machine Learning, pp. 454-463, 2019.
Yoshua Bengio, Ian Goodfellow, and Aaron Courville. Deep learning, volume 1. MIT press Mas- sachusetts, USA:, 2017.
Ivan Bratko. Prolog programming for artificial intelligence. Pearson education, 2001.
Shaveta Dargan, Munish Kumar, Maruthi Rohit Ayyagari, and Gulshan Kumar. A survey of deep learning and its applications: A new paradigm to machine learning. Archives of Computational Methods in Engineering, pp. 1-22, 2019.
Jacob Devlin, Ming-Woo Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805, 2018.
Richard Evans, David Saxton, David Amos, Pushmeet Kohli, and Edward Grefenstette. Can neural networks understand logical entailment? arXiv preprint arXiv: 1802. 08535, 2018.
Thibault Gauthier, Cezary Kaliszyk, Josef Urban, Ramana Kumar, and Michael Norrish. Tactictoe: Learning prove with tactics. Journal of Automated Reasoning, pp. 1-30, 2020.
Felix A Gers, Jürgen Schmidhuber, and Fred Cummins. Learning to forget: Continual prediction with lstm. 1999.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. arXiv preprint arXiv:1410.5401, 2014.
Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. In Advances in neural information processing systems, pp. 1828-1836, 2015.
Christopher Hahn, Frederik Schmitt, Jens U Kreber, Markus N Rabe, and Bernd Finkbeiner. Trans- formers generalize to the semantics logics. arXiv e-prints, pp. arXiv-2003, 2020.
Daniel Huang, Prafulla Dhariwal, Dawn Song, and llya Sutskever. Gamepad: A learning environ- ment for theorem proving. arXiv preprint arXiv: 006.00068. 2018.
Geoffrey Irving, Christian Szegedy, Alexander A Alemi, Niklas Eén, François Chollet, and Josef Urban. Deepmath-deep sequence models for premise selection. Advances in neural information 2016.
processing systems,
Deepak Khemani. first course in artificial intelligence. McGraw-Hill Education, 2013.
Guillaume Lample and François Charton. Deep learning for symbolic mathematics. arXiv preprint 1r1.4:191..01412. 2019.
Andy Liaw, Matthew Wiener, et al. Classification and regression by randomforest. R news, 2(3): 18-22, 2002.
James L McClelland, David Rumelhart, PDP Research Group, et al. Parallel distributed process- ing. Explorations in the Microstructure of Cognition, 2:216-271, 1986.
10

---

Under review as a conference paper at ICLR 2021
Tomáš Mikolov, Stefan Kombrink, Lukáš Burget, Jan Černocký, and Sanjeev Khudanpur. Exten- sions of recurrent neural network language model. In 2011 IEEE international conference on acousties, speech and signal processing (ICASSP), pp.
IEEE, 2011.
Nikita Nangia and Samuel Bowman. Listops: diagnostic dataset for latent tree learning. arXiv preprint arXiv:1804.0600 06028, 2018.
Aditya Paliwal, Sarah M Loos, Markus N Rabe, Kshitij Bansal, and Christian Szegedy. Graph representations for higher-order logic and theorem proving. In AAAI, pp. 2967-2974, 2020.
Fabian Pedregosa, Gaël Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit-leam: Machine learning in python. the Journal of machine Learning research, 12:2825- 2830, 2011.
Bartosz Piotrowski, Josef Urban, Chad E Brown, and Cezary Kaliszyk. Can neural networks learn symbolic rewriting? arXiv preprint arXiv:1911.0044 1.04873, 2019.
Stanislas Polu and Ilya Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.03:: 03393, 2020.
Markus Rabe, Dennis Lee, Kshitij Bansal, and Christian Szegedy. Mathematical reasoning via self-supervised skip-tree training. arXiv preprint wrXiv:2006.0475/ 2020.
Tim Rocktäschel and Sebastian Riedel. Learning knowledge base inference with neural theorem provers. In Proceedings of the 5th Workshop on Automated Knowledge Base Construction, pp- 45-50, 2016.
David Saxton, Edward Grefenstette, Felix Hill, and Pushmeet Kohli. Analysing mathematical rea- soning abilities of neural models. arXiv preprint
2019.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David Dill. Learning a sat solver from single-bit supervision. arXiv preprint arXiv: arXiv:1802.00 1802.0368, 2018.
Sainbayar Sukhbaatar, Jason Weston, Rob Fergus, al. End-to-end memory networks. In Advances in neural information processing systems, pp. 2440-2448, 2015.
Kai Sheng Tai, Richard Socher, and Christopher D) Manning. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint arXiv:1503.000 00075, 2015a.
Kai Sheng Tai, Richard Socher, and Christopher Manning. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprini arXiv: 1503. 5503000075 2015b.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence sequence for sets. arXiv preprint ar 15166693), 2015.
Po- Ro-Wei Wang. Priya L Donti, Bryan Wilder, and Zico Kolter. Satnet: logical reasoning using a differentiable satisfiability solver. arXiv preprint arXiv:1905. 12149, 2019.
Bridging deep learning and
Craig S Webster. Alan turing's ' unorganized machines and artificial neural networks: his remarkable early work and future possibilities. Evolutionary Intelligence, 5(1):35-43, 2012.
Jason Weston, Sumit Chopra, and Antoine Bordes. Memory networks.
arXiv preprint
arXiv: 1410.3916, 2014.
Yuhuai Wu, Albert Jiang, Jimmy Ba, and Roger Grosse. Int: An inequality benchmark for evaluating generalization in theorem proving. arXiv preprint arXiv:2007.02924, 2020.
Hong Xu, Sven Koenig, and TK Satish Kumar. Towards effective deep learning for constraint satisfaction problems. In International Conference on Principles and Practice of Constraint Pro- gramming, pp. 588-597. Springer, 2018.
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What neural networks reason about? arXiv preprint arXiv: 132/1, 2019.
11

---

Under review as a conference paper at ICLR 2021
Kaiyu Yang and Jia Deng. Learning to prove theorems via interacting with proof assistants. arXiv preprint arXiv:1905.093: 2019.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint arXiv: 1r1.vv:8/2.084444 2018.
12


Reviews:
[{"review_id": "rNdfLvwfBmR", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper's contribution is introducing a set of tasks and datasets that require deductive approaches as opposed to common induction-based models. The paper tackles an important and interesting problem that helps to shape the future of the neuro-symbolic research area. My main concern however is, the paper ignores and does not cover the current state-of-the-art techniques and their corresponding datasets and by just introducing some datasets fail to give a correct image of the current efforts in this area. For example, the variation of Neural Turing Machine and Memory Networks has been successfully applied to the sorting problem (which has been proposed as one of the tasks of interest in deductive reasoning in this paper as well) [1], however, the authors have not discussed these class of networks at all. In fact, the authors mention the gap in the current models by talking about the need for models that can store the facts and the intermediate results for being able to conduct deductive reasoning but do not talk about the role and shortcomings of Memory Networks and Neural Turing based models or  Neural\nStacks/Queues. Similarly, there are no arguments in the paper about why Neural Theorem Provers [2] cannot be used to emulate the deductive inference mechanism. \nIn summary, the authors have initiated a good step toward defining the simple deductive reasoning tasks; However, the work has not placed well on the body of current neural and neuro-symbolic techniques, tasks, and datasets and therefore the contribution is not enough for the publication in ICLR.\n\nMinor comments:\n- 3rd sentence of the introduction needs rewriting.\n- Section 2.2: of of ---> of\n- Results: 2^5 0 ---> 2^50\n\n\n1) Vinyals, Oriol, Samy Bengio, and Manjunath Kudlur. \"Order matters: Sequence to sequence for sets.\" arXiv preprint arXiv:1511.06391 (2015).\n2) Rocktäschel, Tim, and Sebastian Riedel. \"Learning knowledge base inference with neural theorem provers.\" Proceedings of the 5th Workshop on Automated Knowledge Base Construction. 2016.", "extra_scores": {}, "extra_text": {}}, {"review_id": "p-N7Z2BZFgK", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper \"Simple deductive reasoning tests and data sets for exposing limitation of today's deep neural networks\" describes several datasets for deep learning to test deductive reasoning abilities of neural networks. The paper tests several neural network architectures (as well as random forests) on these datasets and concludes that neural networks are generally not able to perform deductive reasoning.\n\nMy main critique is that the authors do not seem to be aware of any of the research that is going on in the area. The opening statement of the paper is as follows: \"Learning for Deductive Reasoning is an open problem not yet explicitly called out in the machine learning world today.\" I'm afraid such a statement is simply not true. Reasoning (including deductive reasoning) is a very active research area in the machine learning communities. See below for a very partial list of works.\n\nSecond, the paper contains many assertions that neural networks are incapable of reasoning. For example: \"The deep neural networks with today’s notion of a neuron are not suitable for deductive reasoning\" The main reason the authors give for this claim is that \"neurons\" perform only simple arithmetic operations. However, consider that computers only perform simple boolean operations and yet can perform the tasks described in this paper.\n\nThese claims are also contradictory to some findings in the literature, which the authors do not seem to be familiar with. Here is a bunch related work that the authors might want to take a look at. (And there are plenty more papers in the area.)\n\nDatasets with similar objectives:\n\n    Nikita Nangia and Samuel R Bowman. Listops: A diagnostic dataset for latent tree learning. arXiv preprint arXiv:1804.06028, 2018.\n\n    \"ANALYSING MATHEMATICAL REASONING ABILITIES OF NEURAL MODELS\", by Saxton, Grefenstette, Hill, Kohli, ICLR 2019\n\n    \"INT: An Inequality Benchmark for Evaluating Generalization in Theorem Proving\" Wu, Jian, Ba, Grosse, https://arxiv.org/abs/2007.02924\n\n\nDatasets and theorem proving with neural networks:\n\n    \"DeepMath - Deep Sequence Models for Premise Selection\" Alemi et al. https://arxiv.org/pdf/1606.04442.pdf\n\n    \"Learning to Prove with Tactics\" Gauthier et al. 2018\n\n    \"HOList: An Environment for Machine Learning of Higher-Order Theorem Proving\", Bansal et al, ICML 2019\n\n    \"Learning to Prove Theorems via Interacting with Proof Assistants\" Yang, Deng, ICML 2019\n\n    \"GamePad: A Learning Environment for Theorem Proving\", Huang, Dhariwal, Song, Sutskever, ICLR 2018\n\n    \"Generative Language Modeling for Automated Theorem Proving\", Polu, Sutskever, arxiv 2020\n\n    \"Can Neural Networks Learn Symbolic Rewriting?\" Piotrowski et al., 2019\n\nNeural network architectures for reasoning, including (Tree)RNNs, GNNs:\n\n    \"Can Neural Networks Understand Logical Entailment?\", Evans et al. 2018 https://arxiv.org/abs/1802.08535\n\n    \"Graph Representations for Higher-Order Logic and Theorem Proving\" Paliwal et al, AAAI 2021\n\n    Also, plenty of pre-deep learning work by Joseph Urban on how to turn logical formulas into features.\n\nRecently, Transformers have been shown to be good at logical reasoning:\n\n    \"Deep Learning for Symbolic Mathematics\", Lample and Charton, ICML 2020.\n\n    \"Transformers Generalize to the Semantics of Logics\", Hahn et al, 2020. https://arxiv.org/abs/2003.04218\n\n    \"Mathematical Reasoning via Self-supervised Skip-tree Training\", Rabe et al, 2020, https://arxiv.org/abs/2006.04757\n\n\nMy third point is that the paper does not specify the experiments precisely. What are the hyperparameters of the neural networks?\n\nFourth, the paper claims to consider \"today's deep neural networks\" but does not consider modern neural architectures, such as GNNs and Transformers. These have been shown much better reasoning abilities than RNNs.\n\nIn summary: The paper addresses an important question and I encourage the authors to continue to follow this path. But this work does not consider the existing literature at all and a does not make significant contributions beyond the state-of-the-art as far as I can see.\n\n\nMinor comments:\n\n\"A majority of the machine learning models are inductive reasoning models\"\n\nI believe by \"inductive reasoning\" the authors here refer to the learning process. I think the learning phase has to be contrasted with the inference phase.\n\n\"However for the sake of convenience and interpretation, a vector is typically represented as a tensor\"\n\nThe notion of tensor is a generalization of vector.", "extra_scores": {}, "extra_text": {}}, {"review_id": "RZ1vM3gQnyO", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary:*\nThe paper argues that deductive reasoning is an open problem in current machine learning scenarios where features are learned rather than hand-crafted. To highlight the limitations of current approaches, the paper proposes a benchmark suite of 10 simple tasks (finding the minimum, divisibility test, etc.) that are trivial with some feature engineering, but are shown to be very hard without it. Experiments are performed with random forests, neural networks (MLP?), and recurrent neural networks.\n\n*Strengths:*\n1. Important to highlight limitations of current neural network based methods. The proposed tasks are very simple for humans, but are discrete and deductive, rather than the inductive setups NNs typically work with.\n2. Experiments (although quite limited) show that recent ML approaches exhibit performance close to random.\n\n*Weaknesses:*\n1. While I agree that highlighting the drawbacks of current inductive ML approaches is important and that the proposed tasks are hard to do, I don't necessarily see the problem with small feature engineering. Almost every neural approach that is proposed has some engineering - architecture, hyperparameters, data augmentations, etc. that benefit from knowledge about the task or data. For example, CNNs trained on ImageNet use a lot of knowledge: convolutions better than standard linear layers; random crop of the image during train, 5 crops + flips at test time to further improve spatial understanding; image rotation or intensity variation as data augmentation strategies, etc.\n2. The paper has a lot of space (is only 6 pages), but does very little to explain the models. No details about the RF, NN, or RNN are mentioned. Is the NN an MLP? How many layers? What are the hidden sizes? How is the RNN used? How is the output produced, last time step hidden state? What is hidden size dimensionality? Details like this matter, and performance metrics without them do not say much.\n3. Since the paper takes the stand that feature engineering is key, it would be nice to show improved results with little feature mapping. While it seems that most tasks should be solvable, it is nice to prove that nevertheless. For example, what feature engineering strategy should be used for finding the maximum (when feature engineering already solves the task)? Or would it be enough to represent the real number as a binary sequence for the parity problem?\n\n*Overall rating:*\nWhile the premise is interesting, the work needs to be developed further and presented in much more detail than the current state. In addition, I would like to see some discussion on how some of these deductive reasoning tasks are required as part of an overall intelligent system, rather than just a set of tasks specifically built to break NNs.\n\n*Post-rebuttal*\nAll reviewers agree that this paper is not up to the mark. While the revision does include several additional related works, they are not very well integrated with the rest of the discussion on the paper. For example, how would some of these memory networks perform? How would Neural Turing Machine do? Considering this, I am hesitant to improve my rating for the paper, even if the collection of related works will certainly help in the re-submission.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "PC38LFQ_z71", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the limitations of deep neural networks to model deduction based inferences. This is done by crafting simple datasets and experimentally showing that some (details are not provided) RF, NN and RNN models fail on these.\n\nThe paper is hard to follow at places. The main contribution seems to be Algorithms 1-5, which can be used to generate 10 different dataset \"benchmarks\". The listings of the algorithms seem quite redundant considering the simple types of datasets one wishes to generate, when this would often be achievable using mathematical formula or code \"one-liner\" (the algorithms are also missing information what is returned and the fonts are used inconsistently). The experimental evaluation gives no details of the trained models.\n\nI agree with the authors, that feature engineering is very relevant when it comes to using ML models and in recent years there has been some tendency to consider neural networks as simple plug-in solutions to all scenarios. However, it seems hardly surprising that the crafted benchmarks proposed here are difficult or even impossible to learn for random forest or neural networks. I might be missing something crucial here, but the paper's contribution seems not really warrant publication.\n\nPros:\nRaising awareness that deep learning is not a plug-in solution for every occasion\n\nCons:\nSignificance and novelty seem questionable\n\nQuestions:\nPlease address and clarify the con above \n\nMinor:\n\nThis structure is repeated in several places and is hard to parse, consider clarifying it:\n\" - (a) selection (3 data sets) - minimum, maximum and top 2nd element in an array of numbers; (b) matching (3 data sets) - duplicate detection, counting and histogram learning; (c) divisibility tests (2 data sets) - divisability of two numbers and divisability by 3; (d) representation (2 data sets) - binary representation and parity.\"\n\nRegarding the statement \"However to the best of our knowledge and exploration, today there is no RNN formulation which is meant to learn facts, unification and deductive inferences.\", have the authors checked the recent approaches to use deep learning to learn to solve combinatorial problems (e.g., SAT, CSPs) and using GNNs. This is a currently very active area of research that might be interesting to the authors, see e.g., \nhttps://arxiv.org/abs/1905.13211\nhttps://arxiv.org/abs/1905.12149\nhttps://arxiv.org/abs/1904.01557\nhttps://link.springer.com/chapter/10.1007/978-3-319-98334-9_38\nhttps://openreview.net/forum?id=BJxgz2R9t7\nhttps://openreview.net/forum?id=HJMC_iA5tm\nfor some recent examples.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is not suitable for publication at ICLR. The paper contains a useful message, that neural networks are not a silver bullet, and are especially not well suited to deductive problems. However, as several reviewers pointed out, the claims of the paper are undermined by the fact that it ignores a lot of relevant work on using neural networks in the context of logic reasoning. Reviewer 2 provides a particularly useful list of relevant works on the topic. 
Decision: Reject