Natural- to formal-language generation using Tensor Product Representations
Authors: Kezhen Chen
Qiuyuan Huang
Hamid Palangi
Paul Smolensky
Kenneth D. Forbus
Jianfeng Gao
Venue:  (2020)
Keywords: Neural Symbolic Reasoning
Deep Learning
Natural Language Processing
Structural Representation
Interpretation of Learned Representations

Abstract: Generating formal-language represented by relational tuples, such as Lisp programs or mathematical expressions, from a natural-language input is an extremely challenging task because it requires to explicitly capture discrete symbolic structural information from the input to generate the output. Most state-of-the-art neural sequence models do not explicitly capture such structure information, and thus do not perform well on these tasks. In this paper, we propose a new encoder-decoder model based on Tensor Product Representations (TPRs) for Natural- to Formal-language generation, called TP-N2F. The encoder of TP-N2F employs TPR 'binding' to encode natural-language symbolic structure in vector space and the decoder uses TPR 'unbinding' to generate a sequence of relational tuples, each consisting of a relation (or operation) and a number of arguments, in symbolic space. TP-N2F considerably outperforms LSTM-based Seq2Seq models, creating a new state of the art results on two benchmarks: the MathQA dataset for math problem solving, and the AlgoList dataset for program synthesis. Ablation studies show that improvements are mainly attributed to the use of TPRs in both the encoder and decoder to explicitly capture relational structure information for symbolic reasoning. 

NATURAL- TO FORMAL-LANGUACE GENERATION USING TENSOR PRODUCT REPRESENTATIONS
Anonymous authors Paper under double-bling review
ABSTRACT
Generating formal-language represented by relational tuples, such as Lisp pro- grams mathematical operations, from natural-language input is a challenging task because it requires explicitly capturing discrete symbolic structural infor- mation implicit in the input. Most tatte-of-theaat neural sequence models do not explicitly capture such structural information, limiting their performance on these tasks. In this paper propose new encoder-decoder model based on Tensor Product Representations (TPRs) for Natural- to Formal-language genera- tion, called TP-N2F. The encoder of TP-N2F employs TPR "binding' encode natural-language symbolic structure in vector space and the decoder uses TPR 'unbinding' generate, in symbolic space, sequence of relational tuples, each consisting of a relation (or operation) and a number of arguments. On two bench- marks, TP-N2F considerably outperforms LSTM-based seq2seq models, creating new state-of-the-art results: the MathQA dataset for math problem solving, and the Lig dataset for program synthesis. Ablation studies show that improve- ments can be attributed to the use of TPRs in both the encoder and decoder to explicitly capture relational structure to support reasoning.
INTRODUCTION
When people perform explicit reasoning. they can typically describe the way to the conclusion step by step via relational descriptions. There is ample evidence that relational representations are important for human cognition (e.g.. (Goldin-Meadon & Gentner] 2003 Forbus et al. 2017 Crouse cct al. 2018 Chen & Forbus, 2018 Chen et al. 2019)). Although a rapidly growing number of researchers use deep learning to solve complex symbolic reasoning and language tasks (a recent review is (Gao et al. 2019)), most existing deep learning models, including sequence models such LSTMs, do not explicitly capture human-likk like relational structure information.
In this paper we propose a novel neural architecture, TP-N2F, to solve natural- to formal-language generation tasks (N2F). In the tasks we study, math programming problems are stated in natural- language, and answers are given as programs, sequences of relational representations, to solve the problem. TP-N2F encodes the natural- lanural-language symbolic structure of the problem in an input vector space, maps this to vector in an intermediate space, and uses that vector to produce a sequence of output vectors that are decoded relational structures. Both input and output structures are modelled as Tensor Product Representations (TPRs) (Smolensky 1990). During encoding, NL-input symbolic structures are encoded as vector space embeddings using TPR 'binding' (following SaalloiigaPalangll et al. (2018)); 8)); during decoding, symbolic constituents are extracted from structure-embedding output vectors using TPR "unbinding" (following Huang et al. (2018) 2019)).
Our contributions in this work are as follows. (i) We propose role-level analysis of N2F tasks. (ii) We present a new TP-N2F model which gives a neural-network- solving the N2F task under the role-level description proposed in (i). To our knowledge, this is the first model to be proposed which combines both the binding and unbinding operations TPRs to achieve generation tasks through deep learning. (iii) State-of-the performance two recently developed N2F tasks shows that the TP-N2F model has significant structure learning ability on tasks requiring symbolic reasoning through program synthesis.
implementation model

---

2 BACKGROUND: REVIEW OF TENSOR-PRODUCT REPRESENTATION
The TPR mechanism is a method to create a vector space embedding of complex symbolic structures. The type of symbol structure is defined by set of structural positions or roles, such the left- child-of-root position in a tree, or the aecond-argument-f--1 position of a given relation R. In a particular instance of a structural type, each of these roles may be occupied by particular filler, which can be an atomic symbol or a substructure (e.g., the entire left sub-tree of binary tree can serve as the filler of the role feft-chil--of-root For now, we assume the fillers be atomic symbols
The TPR embedding of a symbol structure is the sum of the embeddings of all its constituents, each constituent comprising role together with its filler. The embedding of a constituent constructed from the embedding of a role and the embedding of the filler of that role: these are joined together by the TPR 'binding' operation, the tensor (or generalized outer) product @.
Formally. suppose symbolic type is defined by the roles {ri}, and suppose that in a particular instance of that type, S, role ry bound by filler fi- The TPR embedding of the order-2 tensor
T T-Enor. 3r, Σtir.
(1)
where } are vector embeddings of the fillers and {r;} are vector embeddings of the roles. In Eq. and below, for notational simplicity we conflate order-2 tensors and matrices.
As a simple example, consider the symbolic type string, and choose roles to be rı = first element, 12 second_element etc. Then in the specific string $ cba, the first role ri is filled by c, and 22 and ra by bs and a, respectively. The TPR for S is c @ rı + b r2 + a & T3, where a, b, c are the vector embeddings of the symbols a, b. c, and r; is the vector embedding of role r;.
A TPR scheme for embedding a set of symbol structures is defined by a decomposition of those structures into roles bound to fillers, an embedding of each role as role vector, and an embedding of each filler as a filler vector. Let the total number of roles and fillers available be 7RR, n2, respectively. Define the matrix of all possible role vectors to be R E R.da xAR, with column i, [R] : = r; E RR comprising the embedding of r;- Similarly let F E Rdexne be the matrix of all possible filler vectors. The TPR T E d xda, Below, dR. RR, de, Up will be hyper-parameters, while R, F will be learned parameter matrices.
Using summation in Eq to combine the vectors embedding the constituents of a structure risks non-recoverability of those constituents given the embedding T of the the structure as a whole. The tensor product is chosen as the binding operation in order to enable recovery of the filler of any role in structure S given its TPR T. This can be done with perfect precision if the embeddings of the roles are linearly independent. In that case the role matrix R has a left inverse U: UR I. Now define the unbinding (or dual) vector for role Ty. Uj, to be the jth column of UT: U.J- Then, since [ = R) = U, R, = [U]]T R. = u, r, r. uy, we have r. u, = 6zz. This means that, to recover the filler of ry in the structure with TPR T, we can take its tensor inner product (or matrix-vector product) with u
Tuy SST Uj Eiddy fz
In the architecture proposed here, we will make use of both TPR binding using the tensor product with role vectors r. and TPR unbinding using the tensor inner product with unbinding vectors uj. Binding will be used to produce the order-2 tensor Ts embedding of the NL problem statement. Unbinding will be used to generate output relational tuples from an order-3 tensor H. Because they pertain to different representations (of different orders in fact), the binding and unbinding vectors we will use are not related to one another.
When fillers are structures themselves. binding can be used recursively, giving tensors of order higher than In general, binding is done with the tensor product. since conflation with matrix algebra is only possible for order-2 tensors. Our unbinding of relational tuples involves the order-3 TPRs defined in Sec. Sec.3.11.2
'When the role vectors are not linearly independent, this operation performs unbinding approximately, taking U to be the left pscudo-inverse of R. Because randomly chosen vectors the unit sphere in high- dimensional space are approximately orthogonal, the approximation is often excellent (Anonymous in prep.).
2

---

3 TP-N2F MODEL
We propose general TP-N2F neural network architecture operating over TPRs to solve N2F tasks under proposed role-level description of those tasks. In this description, natural-language input is represented straightforward order-2 role structure, and formal-language relational representa- tions of outputs are represented with a new order-3 recursive role structure proposed here. Figure] shows an overview diagram the TP-N2F model. depicts the following high-level description.
Attention
W
FP-M2F en
Tuple Vecter rff. arga aarz'
TP-ar
H
arg1
cull
arg2
Attention
w
cell
Tuple Vecter'. argt
Th-ar
H²
arg1
1 &
Reasoning MLP
arg2"
Vector
w
TP-N2F Mapping
Tople Vecter and ung?
Attention
TP-NFF dec cel
rel
TP-N2F encoder
TP-N2F decoder
Figure 1: Overview diagram of TP-N2F.
As shown in Figure [ while the natural-language input is sequence of words, the output is sequence of multi-argument relational tuples such as R A₁ A2), a 3-tuple consisting of binary re- lation (or operation) R with its two arguments. The "TP-N2F encoder" uses two L.STMs to produce a pair consisting of a filler vector and role vector, which are bound together with the tensor prod- uct. These tensor products, concatenated, comprise the "context" over which attention will operate in the decoder. The sum of the word-level TPRs, flattened to vector, is treated as representation of the entire problem statement; it fed to the "Reasoning MLP", which transforms this encoding of the problem into vector encoding the solution. This is the initial state of the "TP-N2F decoder" attentional LSTM, which outputs at each time step an order-3 tensor representing relational tuple. To generate correct tuple from decoder operations, the model must learn to give the order-3 ten- sor the form of a TPR for (R A₁ A2) tuple (detailed explanation in Sec. 3.1.2). In the following sections, first introduce the details of our proposed role-level description for N2F tasks, and then present how our proposed TP-N2F model uses TPR binding and unbinding operations to create a neural network implementation of this description of N2F tasks.
3.1 ROLE-LEVEL DESCRIPTION OF N2F TASKS
In this section, we propose a role-level description of N2F tasks, which specifies the filler/role struc- tures of the input natural- language symbolic expressions and the output relational representations.
3.1.1 ROLE-LEVEL DESCRIPTION FOR NATURAL-LANGUAGE INPUT
Instead of encoding each token of sentence with non-compositional embedding vector looked up in a learned dictionary, we use a learned role-filler decomposition to compose a tensor representation for each token. Given sentence S with n word tokens {w², ? w! 2 w=11), '}. each word token wf is assigned a learned role vector r', soft-selected from the learned dictionary R, and a learned filler vector f³, soft-selecter from the learned dictionary (Sec.2). The mechanism closely follows that Palangi et al. 2018). and we hypothesize similar results: the role and filler approximately encode the grammatical role of the token and its lexical semantics. respectively Then each word token uf represented by the tensor product of the role vector and the filler vector: T' fr 2 r'. In addition
Although the TPR formalism treats fillers and roles symmetrically, in use, hyperparameters are selected so that the number of available fillers is greater than that of roles. Thus, average, each role is assigned more general function, such grammatical role.
words, encouraging it take

---

to the set of all its token embeddings (T ..... T the sentence S as whole is assigned a TPR equal the sum of the TPR embeddings of all its word tokens: Ts Σr= T
Using TPRs to encode natural language has several advantages. First, natural language TPRs can be interpreted by exploring the distribution of tokens grouped by the role and filler vectors they are assigned by trained model (as in Palangi et al. (2018)). Second, TPRs avoid the Bag of Word (BoW) confusion (Huang al. 2018): the BoW encoding of Jay saw Kay is the same the BoW encoding of Kay saw Jay but the encodings are different with TPR embedding, because the role filled by a symbol changes with context.
3.1.2 ROLE-LEVEL DESCRIPTION FOR RELATIONAL REPRESENTATIONS
In this section, we propose novel recursive role-level description for representing symbolic rela- tional tuples. Each relational tuple contains a relation token and multiple argument tokens. Given binary relation R, relational tuple can be written (rel ary1 argz) where arg1, arg2 indicate two arguments of relation rel. Let us adopt the two positional roles, p; = arg:-of-rel for i = 1,2. The filler of role p, is argi- Now let us use role decomposition recursively, noting that the role pfd can itself be decomposed into a sub-role p; = arg;-of- which has sub-filler rel. Suppose that args, rel, Pi are embedded as vectors a,, r. Pt. Then the TPR encoding of pf* is r & Pt, so the TPR encoding of filler org; bound role p, is a, 6 (r so p:). The tensor product is associative, so we can omit parentheses and write the TPR for the formal-languaa expression, the relational tuple (rel argi arg2). as:
H
P1 a2
P2-
Given the unbinding vectors pt for positional role vectors p: and the unbinding vector r' for the vector r that embeds relation rel, each argument can be unbound in two steps as shown in Eqs.
H p = [a @ r ② Pt + a2 & r 2 p2) p. = a, gr
(4)
[a. @
a
(5)
Here denotes the tensor inner product. which for the order-3 H and order-1 1 p in Eq. can be defined as [H p'lı = E [plp : in Eq. 5 is equivalent to the matrix-vector product.
Our proposed scheme can be contrasted with the TPR scheme in which (rel argı argz) is embedded as r @ a1 @ a2 (e.g., (Smolessyy et al. (2016): Schlag & Schmidhuber (2018). In that scheme, an n-ary-relation tuple is embedded as order-(n 1) tensor, and unbinding knowing all the other arguments (to use their unbinding vectors). In the scheme proposed here, an n-ary-relation tuple still embedded as an order-3 tensor: there are just n terms in the sum in Eq, 3 using n position vectors Pı..... Pai unbinding simply requires knowing the unbinding vectors for these fixed position vectors.
argument requires
In the model, the order-3 tensor H of Eq. 3 has different status than the order-2 tensor T of Sec. 3.1.1 Ts is a TPR by construction, whereas H TPR a result of successful learning. To generate the output relational tuples, the decoder assumes each tuple has the form of Eq. 3 and performs the unbinding operations which that structure calls for. In Appendix Sec. A.3] is shown that, if unbinding each of a set of roles from some unknown tensor T gives a target set of fillers, then must equal the TPR generated by those role/filler pairs, plus some tensor that irrelevant because unbinding from it produces the zero vector. In other words, if the decoder succeeds in producing filler vectors that correspond to output relational tuples that match the target, then, as far as what the decoder can see, the tensor that it operates on is the TPR of Eq.
3.1.3 THE TP-N2F SCHEME FOR LEARNING THE INPUT-OUTPUT MAPPING
To generate formal relational tuples from natural-language descriptions, learning strategy for the mapping between the two structures is particularly important. As shown in (6), we formalize the learning scheme as learning mapping function fmapping (-). which, given a structural representation of the natural-language input, Tss outputs a tensor TF from which the structural representation of the output can be generated. At the role level of description, there's 's nothing more to be said about this mapping; how it is modeled at the neural network level is discussed in Sec, 3.2.1
Tr Smapping (Ts)
4

---

3.2 THE TP-N2F MODEL FOR NATURAL- TO FORMAL-LANGUAGE GENERATION
As shown in Figure the TP-N2F model is implemented with three steps: encoding, mapping, and decoding. The encoding step is implemented by the TP-N2F natural-language encoder (TP-N2F Encoder), which takes the sequence of word tokens as inputs, and encodes them via TPR binding according to the TP-N2F role scheme for natural-languan step implemented by an MLP called the Reasoning Module, which takes the encoding produced
input given in Sec. [.1.1] The mapping by the TP-N2F Encoder input. It learns to map the input to a representation that will be processed under the assumption that it follows the role scheme for output relational-tuu -uples specified in Sec. [.1.2] the model needs to learn to produce TPRs such that this processing generates correct output programs. The decoding step is implemented by the TP-N2F relational tuples decoder (TP-N2F Decoder), which takes the output from the Reasoning Module 3Sec.3.1.3 and decodes the target sequence of relational tuples via TPR unbinding. The TP-N2F Decoder utilizes an attention mechanism over the individual-wone TPRs T' produced by the TP-N2F Encoder. The detailed implementations are introduced below.
encoding of the
3.2.1 THE TP-N2F NATURAL-LLANUAGGE ENCODER
The TP-N2F encoder follows the role scheme in Sec. 3.1.1 encode each word token wf by soft- selecting one of ny fillers and one of ra roles. The fillers and roles are embedded as vectors. These embedding vectors, and the functions for selecting fillers and roles, are learned by two LSTMs, the Filler-LSTM and the Role-LSTM. (See Figure [ At each time-step t. the Filler-LSTM and Role-LSTM take a learned word-token embedding w as input. The hidden state of the Filler- LSTM, h4. is used to compute softmax scores ux over filler slots, and a filler vector f FuF is computed from the softmax scores (recall from Sec. D F is the learned matrix filler vectors). Similarly, role vector computed from the hidden state of the Role-LSTM, fef fF and fR denote the functions that generate f and r' from the hidden states of the two LSTMs. The token w² is encoded as T the tensor product of f and r T replaces the hidden vector each LSTM and passed to the next time step, together with the LSTM cell-state vector c²: see (7) (8). After encoding the whole sequence, the TP-N2F encoder outputs the sum of all tensor products Σ. T' to the next module. We use an MLP, called the Reasoning MLP, for TPR mapping: it takes an order-2 TPR from the encoder and maps it to the initial state of the decoder. Detailed equations and implementation are provided Sec. A.2.1 of the Appendix.
h frille-LSTM(U) T (-) T f 3 r' = (ettt) @ (a(k))
hg
T cR 11
(7)
(8)
Unar
mm
2 Tensor product
Filar LSTM
Unear
TP-N2F encoder cell
Liear
Filoe
ZT
Unter
TP FP-N2F
Mapping
Model
Vector
Context
Lnee
amin
Hilee USTM
Unsea
Figure 2: Implementation of the TP-N2F encoder.
5

---

3.2.2 THE TP-N2F RELATIONAL- DECODER
The TP-N2F Decoder an RNN that takes the output from the reasoning MLP as its initial hidden state for generating a sequence of relational tuples (Figure 3 This decoder contains an attentional LSTM called the Tuple-LSTM which feeds an unbinding module: attention operates on the context vector of the encoder, consisting of all individual encoder outputs (T'). The hidden-state H of the Tuple-LSTM is treated as TPR of relational tuple and is unbound to a relation and arguments. During training, the Tuple-LSTM needs to learn way to make H suitably approximate TPR. At each time step the hidden state H' of the Tuple-LSTM with attention (The version in Luong al. (0155)
(9) is fed as input to the unbinding module, which regards H* as if it were the TPR of relational tuple with m arguments possessing the role structure described in Sec. 3.1.2 H & m
2;=1 a @ r @ p;. (In Figure 3 the assumed hypothetical form of H", as well that of B below, is shown bubble with dashed border.) To decode a binary relational tuple, the unbinding module decodes from Hi using the two steps of TPR unbinding given in 4 (5- The positional unbinding vectors P are learned during training and shared across all time steps. After the first unbinding step 44. i.e., the inner product of H' with p/, we get tensors B (10). These are treated the TPRs of two arguments af bound to a relation r'. A relational unbinding vector r"t is computed by linear function from the sum of the B; and used to compute the inner product with each B to yield a which are treated the embedding of argument vectors [1].. Based the TPR theory, r is passed to a linear function to get r' as the embedding of a relation vector. Finally, the softmax probability distribution over symbolic outputs is computed for relations and arguments separately. In generation, the most probable symbol is selected. (More detailed equations are in Appendix Sec. A.2.3)
H Atten Tuple (STM argi argz. H
)), (T)
TT
(9)
B H' p'
B
H
P/2
(10)
1 finear
B + B
a
B
a
B/2 rd
(11)
TP-N2F decoder cell
Unbinding module
vata?? agt aqe
Thale LTTH
vnd or
Unbiniiing
FaaI TP-N2F Mapping Model
Attention!
Ang ref
Toplo muste
module
Tansor inner product
Tensor product
Sum
Figure 3: Implementation of the TP-N2F decoder.
3.3 INFERENCE AND THE LEARNING STRATEGY OF THE TP-N2F MODEL
During inference time, natural language questions are encoded via the encoder and the Reasoning MIP maps the output the encoder to the input of the decoder. We use greedy decoding (selecting the most likely class) to decode one relation and its arguments. The relation and argument vectors are concatenated to construct a new vector as the input for the Tuple-LSTM in the next step.
TP-N2F is trained using back-propagation (Rumelhart et al. 1986) with the Adam optimizer Kingma & Ba 2017) and macherrforriing At each time step, the ground-truth relational tuple provided as the input for the next time step. As the TP-N2F decoder decodes relational tuple at each time step, the relation token is selected only from the relation vocabulary and the argument to- kens from the argument vocabulary. For input I that generates N output relational tuples, the loss

---

is the sum of the entropy loss C between the true labels L and predicted tokens for relations and arguments as shown in
L1
A(rel', Lires) +
Σ Σ ((arg), Largs)
(12)
==
4 EXPERIMENTS
The proposed TP-N2F model is evaluated on two N2F tasks, generating operation sequences to solve math problems and generating Lisp programs. both tasks, TP-N2F achieves state-of-the-an performance. We further analyze the behavior of the unbinding relation vectors in the proposed model. Results of each task and the analysis of the unbinding relation vectors are introduced in turn. Details of experiments and datasets are described in Sec. A.1 in the Appendix.
4.1 GENERATING OPERATION SEQUENCES TO SOLVE MATH PROBLEMS
Given natural- languagg math problem, we need to generate a sequence of operations (operators and corresponding arguments) from a set of operators and arguments to solve the given problem. Each operation is regarded as relational tuple by viewing the operator as relation, e.g., (add, nl,, n2). We test TP-N2F for this task on the MathQA dataset (Amini et al. 2019). The MathQA dataset consists of about 37k math word problems, each with a corresponding list of multi-choice options and the corresponding operation sequence. In this task, TP-N2F is deployed to generate the opera- tion sequence given the question. The generated operations are exccuted with the execution script from Amini et al. (2019) to select multi-choice answer. As there are about 30% noisy data (where the execution script returns the wrong answer when given the ground-truth program; see Sec. I of the Appendix), we report both execution accuracy (of the final multi-choice answer after running the execution engine) and operation sequence accuracy (where the generated operation sequence must match the ground truth sequence exactly). TP-N2F compared to a baseline provided by the seq2prog model in Amini et al. (2019), an LSTMd seq2seq model with attention. Our model outperforms both the original seq2prog, designated SEQ2PROG-orig and the best reimplemented Table [ presents
seq2prog after an extensive hyperparameter search, designated SEQ2PROG-hes the results. To verify the importance of the TP-N2F encoddr and decoder, we conducted experiments to replace either the encoder with standard LSTM (denoted LSTM2TP) or the decoder with stan- dard attentional LSTM (denoted TP2LSTM). We observe that both the TPR components of TP-N2F important for achieving the observed performance gain relative to the baseline.
Table 1: Results on MathQA dataset testing set
MODEL
Operation Accuracy($2) ())
Execution Accuracy( %)
SEQ2PROG-ori
59,4
51.9
SEQ2PROG-best
66.97
54.0
TP2LSTM (ours)
68.84
54.61
LSTM2TP (ours)
68.21
54.61
TP-N2F (ours)
71.89
55.95
4.2 GENERATING PROGRAM TREES FROM NATURAL-LANGUAGG DESCRIPTIONS
Generating Lisp programs requires sensitivity to structural information because Lisp code can be regarded as tree-structured. Given a natural-language query, we need to generate code containing function calls with parameters. Each function call a relational tuple, which has function as the relation and parameters as arguments. We evaluate our model on the AlgoLisp dataset for this task and achieve state-of-the-arr performance. The Algol Lisp dataset (Polosukhin & Skidanov] 2018) is program synthesis dataset. Each sample contains problem description, corresponding Lisp pro- gram tree, and 10 onput-output testing pairs. We parse the program tree into a straight-line sequence of tuples (same style as in MathQA), AlgoLisp provides execution script to run the generated program and has three evaluation metrics: the accuracy of passing all test cases (Acc), the accuracy of passing 50% of test cases (50p-Acc), and the accuracy of generating exactly matching program (M-Ace), AlgoLisp has about 10% noisy data (details in the Appendix), so we report results both on the full test set and the cleaned test set (in which all noisy testing samples are removed). TP-N2F is
7

---

Table 2: Results AlgoLisp dataset
Full Testing Set
Cleaned Testing Set
MODEL (%)
Acc
50p-Acc
M-Ace
Acc
50p-Acc
M-Ace
Seq2Tree
61.0
LSTMeLSTMMattenn
67.54
70.89
75.12
76.83
78.86
75.42
TP2LSTM (ours)
72.28
77.62
79.92
77.67
80.51
76.75
LSTM2TPR (ours)
75.31
79.26
83.05
84.44
86.13
83.43
VH-Att-256
83.80
87,45
92.98
94.15
TP-N2F (ours)
84.02
88.01
93.06
93.48
94.64
92.78
compared with an LSTM seq2seq with attention model, the Seq2Tree model in Polosukhin & Ski- danov (2018), and seq2seq model with a pre-trained tree decoder from the Tree2Tree autoencoder (SAPS) reported in [Bednarek et al. al.] (2019). As shown Table [ TP-N2F outperforms all existing models on both the full test set and the cleaned test set. Ablation experiments with TP2LSTM and LSTM2TP show that, for this task, the TP-N2F Decoder is more helpful than TP-N2F Encoder. This
may be because lisp codes rely more heavily structure representations.
4.3 INTERPRETATION LEARNED STRUCTURE
To interpret the structure learned by the model, we extract the trained unbinding relation vectors from the TP-N2F Decoder and reduce the dimension of vectors via Principal Component Analysis. K- means clustering results on the average vectors are presented in Figure and Figure 3 (in Appendix A. Results show that unbinding vectors for operators or functions with similar semantics tend to be close to each other. For example, with 5 clusters in the MathQA dataset, arithmetic operators such as add, subtruct, multiply, divide are clustered together, and operators related to square or volume of geometry are clustered together. With 4 clusters in the Algolisp dataset, partial/lambda functions and sort functions are in one cluster, and string processing functions are clustered together. Note that there is direct supervision to inform the model about the nature of the operations, and the TP- N2F decoder has induced this role structure using weak supervision signals from question/operation. sequence-anse answer pairs. More clustering results are presented in the Appendix A.6.
RELATED WORK
N2F tasks include many different subtasks such symbolic reasoning semantic parsing (Kamath
Das 2019; Cai Lam 2019 Liao et al., 2018 Amini et al. 2019) Poolouukhin & Skidanov
2018 Bednarek et al. 2019). These tasks require models with strong prructure-leaning ability.
TPR is a promising technique for encoding symbolic structural information and modeling symbolic reasoning in vector space. TPR binding has been used for encoding and exploring grammatical structural information of natural language (Palangi et al.) 2018 Huaan et al. (019)) TPR unbinding has also been used to generate natural language captions from images (Huang al.. 2018). Some researchers use TPRs for modeling deductive reasoning processes both on a rule-based model and deep learning models in vector space (Lee al. 2016, Smolensky et al. 2016 Schlag Schmid- huber 2018). However, none of these previous models takes advantage of combining TPR binding and TPR unbinding to learn structure representation mappings explicitly, as done in our model. Al- though researchers are paying increasing attention to N2F tasks, most of the proposed models either do not encode structural information explicitly or are specialized to particular tasks. Our proposed TP-N2F neural model can be applied to many tasks.
6 CONCLUSION AND FUTURE WORK
In this paper we propose a new scheme for neural-symbolic relational representations and new architecture, TP-N2F, for formal-language generation from natural-language descriptions. To our knowledge, TP-N2F is the first model that combines TPR binding and TPR unbinding in the encoder- decoder fashion. TP-N2F achieves the state-of-the-art on two instances of N2F tasks, showing significant structure learning ability. The results show that both the TP-N2F encoder and the TP- N2F decoder are important for improving natural- to lanmal-language generation. We believe that the interpretation and symbolic structure encoding of TPRs are promising direction for future work. We also plan to combine large-scale deep learning models such as BERT with TP-N2F to take advantage of structure learning for other generation tasks.
8

---

REFERENCES
Aida Amini, Saadia Gabriel, Peter Lin, Rik Koncel Kedziorski, Yejin Choi, and Hannaneh Ha- jishirzi. Mathqa: Towards interpretable math word problem solving with operation-basee for- malisms. In NACCL, 2019.
Anonymous. Unbinding compressed tensor product representations, in prep.
Jakub Bednarek, Karol Piaskowski, and Krzysztof Krawiec. Ain't nobody got time for coding: Structure-aware program synthesis from natural language. In arXiv.org, 2019.
Deng Cai and Wai Lam. arXiv: 193499999993,.,. 2019.
Core semantic first:
top-down approach for parsing. In
Kezhen Chen and Kenneth D. Forbus. Action recognition from skeleton data via analogical gener- alization over qualitative representations. In Thirty-Second AAAI Conference, 2018.
Kezhen Chen, Irina Rabkina, Matthew D. McLure, and Kenneth D. Forbus. Human-like sketch object recognition via analogical learning. In Thirty-Third AAAI Conference, volume 33, pp. 1336-1343, 2019.
Maxwell Crouse, Clifton McFate, and Kenneth D. Forbus. Learning from unannotated qa pairs to analogically disanbiguate and answer questions. In Thirty-Second AAAI Conference, 2018.
Kenneth.D. Forbus, Chen Liang, and Irina Rabkina. Representation and computation in cognitive models. In Top Cognitive System, 2017.
Jianfeng Gao, Michel Galley, and Lihong Li. Neural approaches conversational ai. Foundations and Trends() in Information Retrieval, 13(2-3); 127-299, 2019.
Susan Goldin-Meadow and Dedre Gentner. Language in mind: Advances in the study of language and thought. MIT Press, 2003.
Qiuyuan Huang, Paul Smolensky, Xiaodong He, Oliver Wu, and Li Deng. Tensor product generation networks for deep nlp modeling. In NAACI., 2018.
Qiuyuan Huang, Li Deng, Dapeng Wu, chang Liu, and Xiaodong He. Attentive tensor product learning. In Thirty-Third AAAI Conference, volume 33, 2019.
Aishwarya Kamath and Rajarshi Das. A survey on semantic parsing. In AKBC, 2019.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1412.6990, 2017.
Moontae Lee, Xiaodong He, Wen-tau Yih, Jianfeng Gao, Li Deng, and Paul Smolensky. Reasoning in vector space: An exploratory study of question answering. In ICLR, 2016.
Yi Liao, Lidong Bing, Piji Li, Shuming Shi, Wai Lam, and Tong Zhang, Core semantic first: A top-down approach for amr parsing. EMNLP, pp. 3855 1855-3864, 2018.
Minh-Thang Luong, Hieu Pham, and Christopher D. Manning. Effective approaches to attention- based neural machine translation. EMNLP, pp. 533-536 2015.
Hamid Palangi, Paul Smolensky, Xiaodong He, and Li Deng. Question-answert with coanmaticalll-intrrreeed representations. In AAAI, 2018.
Illia Polosukhin and Alex Skidanov. Neural program search: Solving programming tasks from description and examples. In ICLR workshop, 2018.
David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams, Learning internal representations by error propagation. In David E. Rumelhart, James McClelland, and the PDP Group (eds.), Parallel distributed processing: Explorations in the microstructure of cognition, volume 1, pp- 318-362. MIT press, Cambridge, MA, 1986.
Imanol Schlag and Jurgen Schmidhuber. Learning to reason with third order tensor products. In Neural Information Processing Systems, 2018.

---

Paul Smolensky. Tensor product variable binding and the representation of symbolic structures in connectionist networks. In Artificial Intelligence, volume 46, pp. 159-216, 1990.
Paul Smolensky, Moontae Lee, Xiaodong He, Wen-tau Yih, Jianfeng Gao, and Li Deng. Basic reasoning with tensor product representations. arXiv preprint arXiv:6601.02745. 2016.
A APPENDIX
A.I IMPLEMENTATIONS OF TP-N2F FOR EXPERIMENTS
In this section, we present details of the experiments of TP-N2F on the two datasets. We present the implementation of TP-N2F on each dataset.
The MathQA dataset consists of about 37k math word problems ((80/12/8)% training/dew//estinng problems), each with corresponding list of multi-choice options and an straight-line operation sequence program to solve the problem. An example from the dataset presented in the Appendix A.4. In this task, TP-N2F is deployed to generate the operation sequence given the question. The generated operations are executed generate the solution for the given math problem. We use the execution script from Amini et al. (2019) to execute the generated operation sequence and compute the multi-choice accuracy for each problem. During experiments about 30% noisy examples (on which the execution script fails to get the correct answer on the ground truth program). Therefore, we report both execution accuracy (the final multi-choice answer after running the execution engine) and operation sequence accuracy (where the generated operation sequence must match the ground truth sequence exactly).
observed that there
The AlgoLisp dataset (Polosukhin & Skidanov 2018) is a program synthesis dataset, which has 79k/9k/10K training/dewtesting samples. Each sample contains problem description, corre- sponding Lisp program tree, and 10 input-output testing pairs. We parse the program tree into a straight-lin sequence of commands from leaves root and (as in MathQA) use the symbol #, to indicate the result of the 7th command (generated previously by the model). A dataset sample with our parsed command sequence presented in the Appendix A.4. AlgoLisp provides an execution script to run the generated program and has three evaluation metrics: accuracy of passing all test cases (Acc), accuracy of passing 50% of test cases (50p-Ace), and accuracy of generating an exactly matched program (M-Ace). AlgoLisp has about 10% noise data (where the execution script fails to pass all test cases on the ground truth program), so we report results both on the full test set and the cleaned test set (in which all noisy testing samples are removed).
We use dR, AR, dp, up to indicate the TP-N2F encoder hyperparameters, the dimension of role vec- tors, the number of roles, the dimension of filler vectors and the number of fillers. d darg: dr indicate the TP-N2F decoder hyper- parameters, the dimension of relation vectors, the dimension of argument vectors, and the dimension of position vectors.
In the experiment on the MathQA dataset, we use dp = 150, AR = 50, dp 30, dR 20, dRel 20, d'Arg 10, d 5 and we train the model for 60 epochs with learning rate 15. The reasoning module only contains one layer. As most of the math operators in this dataset are binary. we replace all operators taking three arguments with a set of binary operators based on hand-encoded rules, and for all operators taking one argument, padding symbol is appended. For the baseline SEQ2PROG-orig, TP2LSTM and LSTM2TP, we use hidden size 100, single-direction, one-layer LSTM. For the TEQ2PROG-beSA size for both encoder and decoder; the best score is reported.
performed hyperparameter search on the hidden
In the experiment the AlgoLisp dataset, we use RiF 150. πR 50, dp 30, dR 30. d = 30, d'Arg = 20, d'os = 5 and we train the model for 50 epochs with learning rate 0.001 15. We also lne-layer in the reasoning module like in MathQA. For this dataset, most function calls take three arguments so we simply add padding symbols for those functions with fewer than three arguments.
10

---

A.2 DETAILED EQUATIONS OF TP-N2F
A.2.1 TP-N2F ENCODER
FiLIer-LSTM in TP-N2F encoder
This is standard LSTM, governed by the equations:
f = (UU w + V# b(T 1) + bs)
(13)
of tanh(U ig w' Vig (1² big)
(14)
1 s(U w² Vn (T bba
(15)
of (U w Vi. b(T-(T
) bto)
(16)
cj = f @ c + it ogg
(17)
h = of @ tanh(ct))
(18)
oo, tanh are the logistic sigmoid and tanh functions applied elementwise. b flattens (reshapes) matrix in Rdxx into vector in Rdr, where dr drdR. o is elementwise multiplication. The variables have the following dimensions:
fl. gi. it of cf, 14, b big bR, D bio ((T E Rdr
w/ Rd
Un. Uig. Us, Up E Rdrxd
VR, Vig Vi, Vio E Rdrxdr
Filler vector
The filler vector for input token w' is f defined through attention vector over possible fillers,
af:
a softmax (WW hT)
(19)
f === W.
(20)
(Wr is the same as F of Sec.
2 The variables' dimensions are:
Wia E Rdr
af E R"r
W E Rd
f R
the temperature factor, which is fixed 0.1. Role-LSTM in TP-N2F encoder
Similar to the Filler-LSTM, the Role-LSTM is also a standard LSTM, governed by the equations:
f = p(U, w' + V b,t)
(21)
g tun w' Vig (T' b,g)
(22)
& p(U, wt + Vn VT bu)
(23)
of (Uno w¹ Vn (T (--)+ br.)
(24)
c/ = f @ oct
+ i og
(25)
h of @ tanh(c))
(26)
The variable dimensions are:
ft, g. it, of, ct, he, bee, beg. b bro. ((' E Rd
n² E Rd
U. Ung. Un. U E Rdxxd
Vaa, Vag Va, V. ddxdd

---

Role vector
The role vector for input token w is determined analogously to its filler vector:
a = softmax((W... hT/TT)
(27)
r' =W=Wa a
W.
(28)
The dimensions are:
WT. E Ruaxdr
at E R
W. E RdaXAR
r E Rda
Binding
The TPR for the filler/role binding for token wf then:
T. r' 2 ft
(29)
where
T E dRd
A.2.2 STRUCTURE MAPPING
H f /mppping (T.)
(30)
HD E RRd,, where du = da, do, dp are dimension of argument vector, operator vector and position vector. Smapping is implemented with MLP (linear layer followed by tanh) for mapping the Tr E pe to the initial state of decoder H
A.2.3 TP-N2F DECODER
Tuple-LSTM
The output tuples are also generated via a standard LSTM:
1 > ( Re! w w-=1
Argi: w Arga)
(31)
f = (U; w + ViD(H + by)
(32)
g lun w/ + V/b((H* + bx)
(33)
1' v(U, + V1b(H* ) bi)
(34)
of ((U, w/ V. (HH11) + b.))
(35)
c' f 2 c 1 o g' himpat = 0¹ o tanh( c²)
(36)
(37)
H' Atten(hinpuss (To: Tn-1))
(38)
Here, y is the concatenation function. whrl is the trained embedding vector for the Relation of the input binary tuple, w embedding vector for the second argument. Then the input for the Tuple LSTM is the concatenation of the embedding vectors of relation and arguments, with dimension dacc-
f-1 Argl is the embedding vector for the first argument and w is the
L', i''''', c¹, Mimpues br, bg. by bo, (HH² E Bd
w/ E Rdiar
Ur. Ug. U, U. e dudxda
Vi, Vg. V, V. E Rdaxda
H' d
12

---

Atten is the attention mechanism used in Luong al. (2015), which computes the dot product between ppnt and each Tp. Then a linear function is used on the concatenation of m and the softmax scores all dot products to generate H". The following equations show the attention mechanism:
d' score imput Cr)
(39)
s² CT softmax (d')
(40)
H K> s*)
(41)
score is the score function of the attention. In this paper, the score function is dot product.
Cy E Rduxx
d, E R"
8, Rdu
K E (dax(dr+m)
Unbinding
At each timestep t, the 2-step unbinding process described in Sec. 3.1.2 operates first on an en- coding of the triple as whole, H, using two unbinding vectors p that are learned but fixed for all tuples. This first unbinding gives encoding of the two pperator-argumer bindings, B, The second unbinding operates on the B,, using generated unbinding vector for the operator, r', giving The generated unbinding vector for the operator, r', and the gener-
encodings of the arguments, ated encodings of the arguments, ag each produce probability distribution over symbolic operator outputs Rel and symbolic argument outputs Arg; these probabilities are used in the cross-entropy loss function. For generating a single symbolic output, the most poot-bprobbbl symbols are selected.
B = H' pi
(42)
B H" H' p'z
(43)
n W dual (Bi + BB)
(44)
a B nd
(45)
a B nd
(46)
t = L nd
(47)
" L ai
(48)
It = L ab
(49)
Ref argmax(softmaxx(1 (())
(50)
Argl' argmax(softmax
(51)
Arg2' argmax(softmax/ (Lg))
(52)
The dimensions are:
nd E Rdo
a ab e Rda
Pl.p', E Re
BI, B Rddx
Waual E Rdd
L' Rooxdo
L' E AAxd
1 E R
1 It. E TR
a1 02
13

---

A.3 THE TENSOR THAT IS INPUT TO THE DECODER'S UNBINDING MODULE IS TPR
Here show that, if learning is successful, the order-3 tensor H that each iteration of the decoder's will be a TPR of the form assumed
Tuple LSTM feeds to the decoder's Unbinding Module (Figure 3 in Eq. 3 repeated here:
H
Σ aj 8 8
(53)
The operations performed by the decoder are given in Eqs. and Eqs. 10 rewritten here:
H p = qi qi r' = a;
(54)
(55)
This is the standard TPR unbinding operation, used recursively: first with the unbinding vectors for positions. pl. then with the unbinding vector for the operator, r'. It therefore suffices to analyze a single unbinding; the result can then be used recursively. This in effect reduces the problem to the order-2 case. What we will show is: given a set of unbinding vectors {ri} which are dual to a set of role vectors {r.}, with i ranging over some index set if H an order-2 tensor such that
H
(56)
then
H I. +Z +Z HTPR + +Z
(57)
IEI
for some tensor Z that annihilates all the unbinding vectors:
Z-r = e
(58)
If learning is successful, the processing in the decoder will generate the target relational tuple (R, A1, A2) by obeying Eq, (4 in the first unbinding, where we have ri p',, f: q {1, and obeying Eq. (55 in the second unbinding, where we have r/ = f' = a; with 1 = the set containing only the null index.
Treat r tensors as matrices; then unbinding is simply matrix-vector multiplication. Assume the set of unbinding vectors linearly independent (otherwise there would in general be no way to satisfy Eq. 56 exactly, contrary to assumption). Then expand the set of unbinding vectors, if necessary, into a basis (rk)kek2/- Find the dual basis, with F& dual to r (so that r, r'j &ty)- Because {r Me is a basis, so is (rx JEEK so any matrix H can be expanded as H ΣKEK vari Since Hr! = fi, Vi E T are the unbinding conditions (Eq. 56). we must have v; = fū, E Let HTPR = Ever for; This is the desired TPR, with fillers f. bound to the role vectors r, which are the duals of the unbinding vectors r/ (i I). Then we have
HTPR + Z (Eq. 57 where Z- Eje v so Zr! 0, (Eq. 58 Thus, if training is successful, the model must have learned how to feed the decoder with order-3 TPRs with the structure posited in Eq. 53
The argument so far addresses the case where the unbinding vectors are linearly independent, mak- ing possible to satisfy Eq. exactly. In relatively high-dimensional vector spaces, it will often happen that even when the number of unbinding vectors exceeds the dimension of their space by a factor of 2 or (which applies to the TP-N2F models presented here). there is set of role vectors trakee approximately dual to (rí, heek. such that r, r = dt Vl.j E K holds to good approx- imation. (If the distribution of normalized unbinding vectors approximately uniform on the unit sphere, then choosing the approximate dual vectors to equal the unbinding vectors themselves will do, since they will be nearly orthonormal (Anonymous) in prep.). If the (r') (r')kee K are not normal- ized, we just rescale the role vectors, choosing = r Ir When the number of such role vectors exceeds the dimension of the embedding space. they will be overcomplete, so while it is still true that any matrix H can be expanded above (H ΣLEK U.T()), ). this expansion will no longer be unique. So while it remains true that H a TPR, is no longer uniquely decomposable into filler/role pairs. The claim above does not claim uniqueness in this sense, and remains true.)
14

---

A.4 DATASET SAMPLES
A.4.1 DATA SAMPLE FROM MATHQA DATASET
Problem: The present polulation of town is 3888. Population increase is 20%. Find the population of town after 1 year?
Options: a) 2500, b) 2100, <) 3500, d) 3600, e) 2700
Operations: multiply(n0.n 1) civide 100), add(n0,#1)
A.4.2 DATA SAMPLE FROM ALGOLISP DATASET
Problem:
Consider an array of numbers and number, decrements each element in the given array by the given number, what is the given array?
Program Nested List: (map a (partiall b b)) Command-Sequees (partiall b -), (map #0)
A.5 GENERATED PROGRAMS COMPARISON
In this section, we display some generated samples from the two datasets, where the TP-N2F model generates correct programs but LSTMMSeq2See does not.
Question: A train running at the speed 50 km per hour crosses post seconds. What the length of the train?
TP-N2F(correet);
moultiplyynO,.constiio (dooste..0..conss36600) (multiply.n1,.t) LSTM(wrong): (mulippyynnd..cost(02777)) (multiply.n1,#0)
Question: 20 is subtracted from 60 percent number, the result is 88. Find the number? TP-N2F(correct) (add,n0.n2) (divide,.l.const(000) conss1100 (divide.#O.#1) LSTM(wrong): n0dd,n0,n2) (divide,n constt10))) (divide,#O,#1) (multiply,#2,n3) (subtract,#3,nd)
Question: The population of a village is 14300. It increases annually at the rate of 15 percent. What will be its population after 2 years? (coNeF(correet):
(divide.nl.consllle (const)) (power:#1,n2) (multiply.n0.#2) LSTM(wrong): (multiply.ooms44.onst100))) (sqrt,#0)
Question: There two groups of students in the sixth grade. There are 45 students in group a, and 55 students in group b. If, on a particular day, 20 percent of the students in group forget their homework, and 40 percent of the students in group forget their homework, then what percentage of the sixth graders forgot their homework? TP-N2F(correct);
(add,n0,n1 (multiply.n0,,n2) (multiply.n1 cnciipplyln..,, _n3) (1,vide,#1.const (2ivide, (add,#3,#4) (5ivide,#5.#0) (multiply:H6..oos(1000)
LSTM(wrong): (multiply.n0.nI) (subtract,nO,n.) (O)))d),#O,#1)
Question: divided by 0.05 is equal to TP-N2F(correet)
(divide.nO.nl)
LSTM(wrong):
15

---

(divide.nO.nI) (mulltiplyn2,:#0)
Question: Consider number a, compute factorial of (P-NeF(correct))
argl1, (-,arg1,1) ) self,#1 (*,#2,arg1 ) (1f,#0,11,H3) ) (lambdal,#t) ) (invokel,#5,a)
LSTM(woogg):
aF,agg (
(-argl,,1 ) (elf,#11 ) (#,#2.argl ) (if.#0,1.43) (lambdal,#) (aaml144))llaalll...... ) (len,a) 1,55
Given an array of numbers and numbers b and c, add с to elements of the product of elements of the given array and b, what is the product of elements of the given array and b?
Question:
TP-N2F(correct):
( partial, b, paarialll,,t (map.a,t0) ) (ma.,#2.#1)
LSTM(wrong):
( (partiall,,+) ) (partiall,c,+ (map.a,#0) ) (map.#2##1)
Question:
You are given an array of numbers and numbers с and d let how many times you can replace the median in with sum of its digits before it becomes single digit number and b be the coordinates of one end and and d be the coordinates another end of segment e, your task is to find the length of segment rounded down
(c-ore(co)reet)::
( digits arg len #0) ( (== #1 1) digits arg ) reduce #3 0+) ( self #4 (+ #5 #2 #6
) ( lambddl #7 ) sort a ) ( len a ) (/ #10 2 deref #9 #11 (invokel #8 #12) #13 digits
argl (Ien #15) ) == #16 1) ( digits argl ) ( reduce #18 + self #19 ) ( + #20 ) (if 0 #21
) ( lambdal #22 ) sort a ( len a (/ #25 2 ) deref #24 #26 ) linvoee #23 #27 (-#28 c
#14 #29 (-bd) (-bd) (* #31 #32 (+ #30 #33) ) sqrt #34 ( (floor #35
LSTM(wrong): ( (digits arg] ) (len #0 (== #1 1) digits argl ) reduuee #3 0 ++) (self #4 (+1 (sorta) ( len a #1) deref #9 #11 ) invokel #8 #12c) (-
#5 ( if #2 #6) (lambdal
#13
#15 #16 #14 #17 ) #18) (sqrt #19 (floor #20)
Question: Given numbers a b e and e let be c reverse digits in d let a and the number in the range from I to b inclusive that has the maximum value when its digits are reversed be the coordinates one end and d and e be the coordinates of another end of segment f, find the length of segment f squared
(P-NeF(correet):
( digitt e ) reverse #0) (* argl 10) ( ( + #2 arg2 (lambda2 #3 (rduuee #1 0 ) (-a a (digits
c) ( reverse #7 ) ( * arg 10 ) (+ #9 arg2 lambda2 #10) ( (reduce #8 0 #11 (- #12) #6 #13
) O range #15) ) digits argl ) reverse #17 ) ( arg1 10 ) (+ #19 arg2 [lambda2 #20
) (reduce #18 0 #21 ) digits arg2 reverse #23 ) arg1 10 ) (+ #25 arg? lambda2 #26 ) (
reduce #24 #27 ) 2 #22 #28 ) ( if #29 argl arg2 ) [lambda2 #30) ( reduce #16 0 #31 ) (- @3#
O
range O #34 ) digits argl ) reverse #36) ) ( arg1 10 ( (+ #38 arg2 ) [lambda2 #39
) (reduce #37 #40 ) ( digits arg2 reverse #42 ) ( argl 10) ( ( #44 arg2 ) [aambda2 #45
reduce #43 0 #46 (2 #41 #47 if #48 argl arg2 (lambda2 #49 (reduce #35 0 #50 ) #51 e
(* #33 #52) (+ #14 )
LSTM(wrong):
( (- d) #0 #1 digits c (rveerse #3 ) ( * argl 10 ) ( + #5 arg2 ) lambdda2 #6 ) (
1) range 0 #10) ( digits arg ) reverse #12) ) ( arg] ) + #14 arg2) ( (lambda2 #15) ) reduce #13 0 #16) digits arg2 (reverse #18 ) ( arg 10 (+ #20 arg2) ) lambda2 #21 ) reduce #19 #22 (2 #17 #23 (if #24 argl arg2) (lambda2 #25 ) (reduce #11
reduce #4 0 #7 ) (- #8 e)
0 #26 ) #27 e) #9 #28
(+ #2 #29)
16

---

A.6 UNBINDING RELATION VECTOR CLUSTERING
We run K-means clustering on both datasets with k - 3, 4, 5, 6 clusters and the results are displayed in Figure 4 and Figure 5 As described before, unbinding-vectors for operators functions with similar semantics tend to be closer to each other. For example, in the MathQA dataset, arithmetic operators such add, subtract, multiply, divide are clustered together middle, and operators re- lated to geometry such as square or volume are clustered together at bottom left. In Algo dataset, basic arithmetic functions are clustered at middle, and string processing functions are clustered right.
MuthkQ4 Cusstaring Result with Cuusters
WORL
vivcre shiide
Jeandtr
MethQA Clustering Result with Custers
MathOn Clustering tngttring Result Clusters
Figure MathQA clustering results
17

---

Algouig Cltatenng Resut with Clusters
Aigel up Llontnnin Finuit with Clasters
www
Result Clusters
with Clusters
Figure 5: AlgoLisp clustering results
18


Reviews:
[{"review_id": "rkxqciuCtH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "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 considers the challenging problem of learning to generate programs from natural language descriptions: the inputs are sequences of words describing a task and the outputs are corresponding programs solving the task. The proposed approach elegantly relies on tensor product representations. Inference with the proposed model is done in 3 steps: (1) encode the symbolic information present in the text data as a TPR, (ii) maps the input TPR to an output TPR encoding the symbolic relations of the output programs (here the authors use a simple MLP), and (iii) decode the output TPR into an actual program. The parameters of the models used in the 3 steps are learned jointly. For step (iii), the authors proposes a novel way of encoding an n-ary relation into a TPR which facilitates the recovery of the relation's arguments using unbinding operations: this is a neat trick (though I think it increases the number of parameters and may limit the expressiveness of the TPR, since reaching \"full-rank\" of the TPR will occur faster than with the encoding used in [Smolensky et al., 2016]). Experiments on two datasets demonstrate the validity of the approach.\n\nThe paper is very well written and easy to follow. The idea seems original and well executed but I think the experimental section could be improved. In particular, adding/reporting stronger baselines to the comparison would straighten the paper. I also feel some relevant literature may be missing from the related work. Nonetheless, I think it is a good paper which will be relevant to the community, I thus recommend acceptance.\n\n* Comments / Questions *\n\n- Section 3.1.1: if I understand correctly, the length of the sequence affects the rank of the TPR. Could that be a problem in practice? E.g., the capacity of the TPR could likely be saturated quickly for long sequences?\n\n- Section 3.2.1: the filler vector f_t = Fu is computed as a convex combination of the learned filler vectors. Is it a design choice to choose a convex combination rather than taking the column corresponding to the argmax of the vector u? Or is it because otherwise the model can not be trained using the classical backprop approach? \n\n- The results of the Seq2Tree+Search model from (Bednarek et al. (2019)) is not reported in Table 2. Why? I believe it should be included (it is ok that it outperforms the proposed method. In addition you can maybe identify clear advantages of your method illustrating a trade-off, e.g., running time, end-to-end, scalability ...). \n\n- A more thorough ablation study could also improve the strength of the experiments. For example, do you know to which extent the attention model in the decoder is necessary to achieve good performances?\n\n- I am not very familiar with the literature but it seems some relevant work may be missing from the review. In particular, I believe there are many papers tackling the problem of learning programs from input output examples or execution traces, e.g. \"DeepCoder: Learning to Write Programs\", \"Neural Turing machines\",  \"Inferring algorithmic patterns with stack-augmented recurrent nets\", \"Inferring and Executing Programs for Visual Reasoning\", \"Learning to infer graphics programs from hand-drawn images\"... This list is by no means meant to be exhaustive in any way, just to illustrate a large body of work that seems relevant to the present paper (even though I understand that those papers do not consider natural language description as inputs).\n\n* Typos *\n\n- Eq. (5) Should be r' instead of r_i' (?)\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "N/A", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SygoAfzI9r", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 proposes a sequence-to-sequence model for mapping word sequences to relation-argument-tuple sequences. The intermediate representation (output of the encoder) is a fixed-dimensional vector. Both encoder and decoder internally use a tensor product representation. The experimental results suggest that the tensor product representation is helpful for both the encoder and the decoder. The paper is interesting and the experimental results are positive, but in my opinion the exposition could use some substantial work. Fixing the most substantial flaws in the exposition would be sufficient to warrant an accept in my view.\n\n\nMajor comments:\n\nI found the mix of levels of detail in the model specification in section 3 confusing. It would be extremely helpful to have a straightforward high-level mathematical description of the key parts of the encoder, mapping (which could be considered part of the encoder), and decoder in standard matrix-vector notation. While equations (7), (8), (9), (10), (11) and appendix A.2 go some way toward this, key high-level details seem to be missing, and I feel like the exposition would benefit from simply stating the matrix-vector operations that are performed in addition to describing their interpretation in terms of the semantics of the tensor product representation. Specific examples are noted below.\n\nIt would be helpful to be explicit about the very highest-level structure of the proposed model. If I understand correctly, it is a probabilistic sequence-to-sequence model mapping a word sequence to a probability distribution over relation-argument-tuple sequences. It uses an encoder-decoder architecture with a fixed-dimensional intermediate representation, and an autoregressive decoder using attention. Both the encoder and decoder are based on the tensor product representation described in section 2. Stating these simple facts explicitly would be extremely helpful.\n\nEspecially for the encoder, the learned representation is so general that there seems to be no guarantee that the learned roles and fillers are in any way related to the syntactical / semantic structure that motivates it in section 2. There doesn't seem to be any experimental investigation of the learned TPR in the encoder. If I understand correctly, the way encoder roles and fillers are computed and used is symmetric, meaning that the roles and fillers could be swapped while leaving the overall mapping from word sequences to relation-argument-tuple sequences unchanged. This suggests it is not possible to interpret the role and filler vectors in the encoder in an intuitive way.\n\n\nMinor comments:\n\nIn section 2, \"R is invertible\" should strictly be \"R has a left inverse\".\n\nIn section 3.1.1, the claim that \"we can hypothesize to approximately encode the grammatical role of the token and its lexical semantics\" is pretty tenuous, especially given the apparent symmetry between learned roles and fillers in the encoder and given the lack of experimental investigation of the meaning of the learned encoder roles and fillers.\n\nIn section 3.1.2, my understanding is that the relation-argument tuple (R, A_1, A_2, A_3), say, is treated as a sequence of 3-tuples: (A_1, R, 1), (A_2, R, 2), (A_3, R, 3). Each of these 3-tuples is then embedded using learned embeddings (separate embeddings for argument, relation and position). If correct, it would be helpful to state this explicitly.\n\nIn section 3.1.2, it is stated that contracting a rank-3 tensor with a vector is equivalent to matrix-vector product, which is not the case.\n\nIn section 3.1.3, both high-level and low-level details of the MLP module are omitted. High-level, I presume that the matrix output by the encoder is reshaped to a large vector, the MLP is applied to this vector to produce another vector, then this is reshaped to a rank-3 tensor to input to the decoder. It would be helpful to state this. Low-level, the number of layers, depth and activation function of the MLP should be specified somewhere, at least in the appendix.\n\nDid the authors consider using a bidirectional LSTM for the encoder? This might improve performance.\n\nIn section 3.1.2 and appendix A.2, why use the LSTM hidden state for subsequent processing rather than the LSTM output (which would be more conventional). The LSTM output is defined in appendix A.2 but appears not to be used for anything. Please clarify in the paper.\n\nDid the authors consider passing the output of the reasoning MLP into every step of the tuple LSTM instead of just using it to initialize the hidden state?\n\nIt would be helpful to state the rank of the tensors H, B, etc in section 3.2.2.\n\nIn section 3.2.2, what does \"are predicted by classifiers over the vectors...\" mean? This seems quite imprecise. What is the form of the classifier? My best guess is that the vector a_i^t is passed through a small MLP with a final softmax layer which outputs a probability distribution over the 1-of-K representation of the argument. The main text says \"more details are given in the appendix\", but appendix A.2 just has \"Classifier(a_1^t)\". Please clarify in the paper.\n\nWhat is the attention over in equation (9)? Attention needs at least two arguments, the query and the sequence being attended to. It seems that (9) only specifies one of these. It would also be helpful to be explicit about the form of attention used.\n\nWhat is f_linear in (11)?\n\nIt seems unnecessarily confusing to switch notation for the arguments from A_1 in section 3.1.2 to a r g_1 in section 3.2.2, and similarly for the relations.\n\nFor the decoder tuple LSTM, how exactly is the previous relation-argument tuple (R, A_1, A_2, A_3), say, summarized? Are each of R, A_1, A_2 mapped to a vector, these vectors concatenated, then passed into the LSTM? Or is the positional decomposition into (A_1, R, 1), ... used? Please clarify in the paper.\n\nBased on section 3.3, it seems that the model assumes that, in the decomposition of (R, A_1, A_2, A_3) into a sequence (A_1, R, 1), (A_2, R, 2), (A_3, R, 3) of 3-tuples at each decoder output step, the three 3-tuples are conditionally independent of each other and the three entries of each 3-tuple are conditionally independent of each other. Is this indeed assumed? If so, it would be helpful to state this explicitly. It seems like this is likely not true in practice.\n\nSection 3.3 refers to \"predicted tokens\". Where are these predicted tokens in (9), (10) or (11)?\n\nIn section 3.3, it seems the loss at each decoder step is the log probability of the relation-argument tuple at that step. Thus, by the autoregressive property, the overall loss is the log probability of the sequence of relation-argument tuples. If so, it would be helpful to state both these facts explicitly.\n\nSection 3 seems to be missing a section, which is how decoding is performed at inference time. For the output of the decoder at each step, is random sampling used, if so with a temperature, or is greedy decoding (selecting the most likely class, equivalent to a temperature of 0) used? Also, what is done if decoding outputs different R's for (A_1, R, 1), (A_2, R, 2), (A_3, R, 3)? The three R values here should be equal in order for this to represent a relation-argument tuple (R, A_1, A_2, A_3), but there is no guarantee the model will respect this constraint.\n\nUnless I missed it (apologies if so), many experimental architecture details were omitted. For example, how many hidden cells were used for the LSTMs, etc, etc? These should at least be stated in the appendix.\n\nIt would be interesting to investigate how long input / output sequences need to be before the fixed-dimensional internal representation breaks down.\n\nIn section 4.1.1, it was not clear to me what \"noisy examples\" means. Does this mean that the dataset itself is flawed, meaning that the reference sequence of operations does not yield the reference answer? Please clarify in the paper.\n\nIn table 1, please state the total size of the fixed-dimensional intermediate representation for all systems. This seems crucial to ensure the systems can be meaningfully compared.\n\nIn figure 4, left figure, the semantic classes don't apper to be very convincingly clustered. (And it seems like K-means clustering could easily have selected a different clustering given a different random initialization.)\n\nIn appendix A.2, mathematical symbols are essentially meaningless without describing what they mean in words. Please explain the meaning of all the symbols that are not defined in terms of other symbols, e.g. w^t, T_{t-1}, ..., f_s m (is this softmax???), f_l i n e a r (what does this mean?), C o n t e x t, C l a s s i f i e r, etc, etc. C o n t e x t in particular doesn't even have a hint of a definition.\n\nIn (19) and (27), why would a temperature parameter be helpful? This can be absorbed as an overall multiplicative factor in the weight matrix of the previous linear layer. Is this temperature parameter learned during training (I presume so)? Please clarify in the paper.\n\nUsually * is used for convolution, not simple multiplication (e.g. equation (17)).\n\nThroughout the main body and appendix, there are lots of instances of poor spacing. For example, $f_{linear}$ should be written as something like $f_\\text{linear}$ in latex to avoid it coming out as l i n e a r (which literally interpreted means l times i times n times e, etc). Please fix throughout.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "SyecPABa9S", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 authors propose a binding-unbinding mechanism for translating natural language to formal language. The idea is good and novel. As far as I know, this is indeed the first work for handling this task using binding-unbinding mechanism. The experimental results also look promising in compared with the exsiting models. However, the designed specific neural network does not support the claimed binding-unbinding theory very well. Moerover, there seem to be some errors about the correctness of the theory (See the first point below).\n\nFirstly, in the last paragraph of Section 2, the authors claim that the role matrix $R$ would be invertible such that there exists a matrix $U = R^{-1}$ such that the fillers would be recovered. However, $R$ is defined as a non-square matrix in the previous paragraph. How can a non-square matrix be invertible? \n\nSecondly, the design of the specific neural network cannot describe the theory behind proposed binding-unbinding mechanism properly. The authors try to interpret the design of the neural networks using the concepts in the proposed binding-unbinding theorybut are not convincible.  In Section 2, the basics of binding-unbinding are introduced and many mathematical properties are required to make the binding-unbinding work. However, all the parameters/variables in the neural networks are freely designated and are not correlated to each other, thus they cannot work together to meet the requirements in the binding-unbinding mechanism. According to my understanding, at least there should be some direct connections between the parameters in the encoder and decoder. For example, is there any restriction on the parameters in encoder and decoder respectively to reflect the property $UR=I$ as in Section 2.\n\nLastly, in the encoder part, the role and filler are learned in an unsupervised without any evidence. The input for the decoder is an \"assumed\" TPR, thus the only evidence from the objective function are cut-off by the assumed TPR. Given that there are no other connections between encoder and decoder, the design of the encoder cannot learn role and filler properly.\n\nOther suggestions:\nThe natural language to formal language problem is named semantic parsing in natural language processing field. In semantic parsing problem, langugae to programatic language is a typical task. I would recommend include some references in semantic parsing.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposed a new seq2seq method to implement natural language to formal language translation.  Fixed length Tensor Product Representations are used as the intermediate representation between encoder and decoder.  Experiments are conducted on MathQA and AlgoList datasets and show the effectiveness of the methods.  Intensive discussions happened between the authors and reviewers.  Despite of the various concerns raised by the reviewers, a main problem pointed by both reviewer#3 and reviewer#4 is that there is a gap between the  theory and the implementation in this paper.  The other reviewer (#2) likes the paper but is less confident and tend to agree with the other two reviewers.
Decision: Reject