Generating formal-language represented by relational tuples, such as Lisp programs or mathematical operations, from natural-language input is a challenging task because it requires explicitly capturing discrete symbolic structural information implicit in the input. Most state-of-the-art neural sequence models do not explicitly capture such structural information, limiting their performance 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, in symbolic space, a sequence of relational tuples, each consisting of a relation (or operation) and a number of arguments. On two benchmarks, TP-N2F considerably outperforms LSTM-based seq2seq models, creating new state-of-the-art results: the MathQA dataset for math problem solving, and the AlgoLisp dataset for program synthesis. Ablation studies show that improvements can be attributed to the use of TPRs in both the encoder and decoder to explicitly capture relational structure to support reasoning.
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.
Major comments:
I 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.
It 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.
Especially 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.
Minor comments:
In section 2, "R is invertible" should strictly be "R has a left inverse".
In 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.
In 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.
In 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.
In 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.
Did the authors consider using a bidirectional LSTM for the encoder? This might improve performance.
In 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.
Did 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?
It would be helpful to state the rank of the tensors H, B, etc in section 3.2.2.
In 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.
What 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.
What is f_linear in (11)?
It 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.
For 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.
Based 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.
Section 3.3 refers to "predicted tokens". Where are these predicted tokens in (9), (10) or (11)?
In 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.
Section 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.
Unless 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.
It would be interesting to investigate how long input / output sequences need to be before the fixed-dimensional internal representation breaks down.
In 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.
In 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.
In 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.)
In 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.
In (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.
Usually * is used for convolution, not simple multiplication (e.g. equation (17)).
Throughout 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.