Venue: ICLR 2017 conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The goal of this paper is to learn vector representation of boolean and polynomial expressions, such that equivalent expressions have similar representations.

The model proposed in the paper is based on recursive neural network, as introduced by Socher et al. (2012). Given the syntactic parse tree of a formula (either boolean or polynomial), the representation for a node is obtained by applying a MLP on the representation of the children. This process is applied recursively to obtain the representation of the full expression. Contrary to Socher et al. (2012), this paper proposes to use more than one layer (this is especially important to capture XOR operation, which is not surprising at all). The paper also introduces a reconstruction error (called SubexpForce), so that the expression of children can be recovered from the expression of the parent (if I understood correctly). The model is trained using a classification loss, where the label of a given expression corresponds to its equivalence class. The method is then evaluated on randomly generated data, and compared to baselines such as tf-idf, GRU RNN or standard recursive neural network.

While I do agree with the authors that learning good representation for symbolic expressions (and to capture compositionality) is an important task, I am not entirely convinced by the experimental setting proposed in this paper. Indeed, as stated in the paper, the task of deciding if two boolean expressions are equivalent is NP-hard, and I do not understand if the model can do better than implicitly computing the truth table of expressions. While sometimes a bit hard to follow, the paper is technically sound. In particular, the proposed model is well adapted to the problem and outperforms the baselines.

pros:
 - the model is relatively simple and sound.
 - using a classification loss over equivalence classes (should be compared with using similarity).

cons:
 - not convinced by the setting: I do not believe that you can really do better than the truth table for boolean expr (or computing the value of the polynomial expression for randomly chosen points in [0, 1]^n).
 - some part of the paper are a bit hard to follow (e.g. justification of the SubexpForce, discussion of why softmax does not work, etc...).
 - comparison between classification loss and similarity loss is missing.
review_title: borderline: not convinced by the setting.

final_score: rating: 6: Marginally above acceptance threshold
review_content: 
This work proposes to compute embeddings of symbolic expressions (e.g., boolean expressions, or polynomials) such that semantically equivalent expressions are near each other in the embedded space.  The proposed model uses recursive neural networks where the architecture is made to match that of the parse tree of a given symbolic expression.  To train the model parameters, the authors create a dataset of expressions where semantic equivalence relationships are known and minimize a loss function so that equivalent expressions are closer to each other than non-equivalent expressions via a max-margin loss function.  The authors also use a “subexpression forcing” mechanism which, if I understand it correctly, encourages the embeddings to respect some kind of compositionality.

Results are shown on a few symbolic expression datasets created by the authors and the proposed method is demonstrated to outperform baselines pretty convincingly.  I especially like the PCA visualization where the action of negating an expression is shown to correspond roughly to negating the embedding in its vector space — it is a lot like the man - woman + queen = king type embeddings that we see in the word2vec and glove style papers.  

The weakest part of the paper is probably that the setting seems somewhat contrived — I can’t really think of a real setting where it is easy to have a training set of known semantic equivalences, but still more worth it to use a neural network to do predictions.   The authors have also punted on dealing with variable names, assuming that distinct variables refer to different entities in the domain.  This is understandable, as variable names add a whole new layer of complexity on an already difficult problem, but also seems high limiting.  For example, the proposed methods would not be useable in an “equation search engine” unless we were able to accurately canonicalize variable names in some way.

Other miscellaneous points:
* Regarding problem hardness, I believe that the problem of determining if two expressions are equivalent is actually undecidable — see the “word problem for Thue systems”.  Related to this, I was not able to figure out how the authors determine ground truth equivalence in their training sets.  They say that expressions are simplified into a canonical form and grouped, but this seems to not be possible in general, so one question is — is it possible that equivalent expressions in the training data would have been mapped to different canonical forms?  Would it have been easier/possible to construct and compare truth tables?
* The “COMBINE” operation uses what the authors describe as a residual-like connection.  Looking at the equations, the reason why this is not actually a residual connection is because of the weight matrix that is multiplied by the lower level l_0 features.  A true residual connection would have passed the features through unchanged (identity connection) and would have also been better at fighting gradient explosion…. so is there a reason why this was used rather than an identity connection?
* In table 3, the first tf-idf entry: a + (c+a) * c seems equivalent to a + (c * (a+c))
* Vertical spacing between Figure 4 caption and body of text is very small and looks like the caption continues into the body of the text.


review_title: Intuitive and effective model for predicting semantic equivalence, but what the practical use of this approach is, is unclear.

final_score: rating: 7: Good paper, accept
review_content: The authors propose a new model to learn symbolic expression representations. They do a reasonably extensive evaluation with similar approaches and motivate their approach well.

As expressed in the preliminary questions, I think the authors could improve the motivation for their subexpforce loss.

At the top of page 6 the authors mention that they compare to two-layer MLP w/o residual connections. I think having a direct comparison between a model with and w/o the subexpforce loss would be helpful too and should be included (i.e. keep the residual connections and normalization).

My main concern is the evaluation "score". It appears to be precision on a per query basis. I believe a more standard metric, precision-recall or roc would be more informative. In particular the chosen metric is expected to perform better when the equivalence classes are larger, since this isn't taken into account in the denominator, but the likelihood of a random expression matching the query increases.
review_title: Symbolic Expression Representations.

final_score: rating: null
review_content: I am not sure to get why maximizing the likelihood of the data (Eq. 1) would lead to bad performance. The output of TreeNN is normalized, but not q_ei, is that correct? So couldn't high probabilities be achieved with large q_ei?

I also do not get why the supervised objective is different from classification at train time (I understand that at test time, unseen equivalence classes are considered).

Finally, in the introduction, the authors state that the goal of the paper is to develop models that will capture "inductive biases" from the data. What kind of biases are considered? It seems to me that the generated data lead to hard problems: it would probably be hard for a human to solve the boolean tasks, without computing the truth table of the expressions. Is this what the model is implicitly doing?
review_title: Inductive biases

final_score: rating: null
review_content: Hi,
could you please motivate the intuition behind subexpforce better. I am having trouble following the end of section 2.1.
review_title: Clarification of SubExpForce

Meta-review: As part of this meta-review, I read the paper and found some surprising claims, such as the somewhat poorly motivated claim that coercing the output of a sub-network be a unit vector my dividing it by its L2 norm is close to layer normalisation which is mathematically almost true, if the mean of of the activations is 0, and we accept a fixed offset in the calculation of the stddev, but conceptually a different form of normalisation. It is also curious that other methods of obtaining stable training in recursive networks, such as TreeLSTM (Zhu et al. 2015, Tai et al. 2015), were not compared to. None of these problems is particularly damning but it is slightly disappointing not to see these issues discussed in the review process.

Overall, the reviews, which I found superficial in comparison to the other papers I am chairing, found the method proposed here sound, although some details lacked explanation. The consensus was that the general problem being addressed is interesting and timely, given the attention the topics of program induction and interpretation have been receiving in the community recently. There was also consensus that the setting the model was evaluated on was far too simple and unnatural, and that there is need for a more complex, task involving symbolic interpretation to validate the model. It is hard to tell, given all the design decisions made (l2-normalisation vs layer norm, softmax not working), whether the end product is tailored to the task at hand, and whether it will tell us something useful about how this approach generalises. I am inclined, on the basis of the reviewer's opinions of the setting and my own concerns outlined above, to recommend redirection to the workshop track.
Decision: Invite to Workshop Track