Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 6: Weak Accept
review_content: This paper proposes generating feature representations for set elements using weighted multiset automata. Experiments show that this leads to better generalization performance in some tasks.

I am leaning to reject this paper. The proposed algorithm for generating features seems relevant and correct, but there are shortcomings in the presentation and the experiments are not entirely convincing.

In particular, the paper begins by introducing weighted multiset automata quite clearly, but it fails to explain how exactly these automata would be used to generate set representations. I assumed that the set would be represented as the state of the automaton after processing a string (where each element of the set is a symbol from the alphabet in the string) but in section 4 the different states of the automaton while processing a string are used instead. If this paper proposes a new way of learning representations for sets, I would like to see a general recipe for the application of this idea.

Reading the paper it is not entirely clear what theoretical results are novel and which proofs are restatements of existing proofs. It would be useful to guide the reader a bit more clearly here.

The second statement in section 4.1 is not clear to me: In what sense is the diagonal with alternating complex conjugate entries fully general?

The experimental results are difficult to interpret. Since there are no confidence intervals it is impossible to draw conclusions from table 1. I am also not entirely convinced by figure 2. The "unit digit of a sum" task seems slightly artificially constructed to be suitable for a network which uses complex numbers. Although this is not a bad thing, it doesn't necessarily validate that complex weighted automata have better representational power. If that was the case, wouldn't we expect better results for other tasks that don't explicitly have a cyclic nature?

The main questions I would like to see answered (and adjusted in the paper) for me to accept this paper would be:

* What is the general recipe for applying this technique to get representations of a multiset?
* How do the experimental results validate the increased representational power of complex-weighted diagonal automata?
review_title: Official Blind Review #1

final_score: rating: 6: Weak Accept
review_content: This paper proposed a complex weights based multiset automata designed to represent unordered data. The main idea of multiset automata is that the transition matrices of the automata is pairwise commutative. To achieve this property, the authors proposed to restrict the transition matrices to be diagonal and shows that the latter is a close approximation of the former. The authors proceed to give two practical applications of the multiset automata: position encoding of the transformer and deepset networks. For the former, the authors showed that the position encodings from Vaswani et al. can be written as a weighted unary automaton and therefore it is a generalization of the original position encodings. For the latter, the authors extended the classical deepset networks into its complex domain, allowing more efficient representation of the data. 

I think this paper overall did a good job, and I really like the construction of the multiset automata and the theoretical guarantees the authors derived and the two applications are straight-forward to see. However I do find the motivation of this paper is a bit weak,  and I’m having a hard time finding the highlight of the paper. Therefore, I’m giving this paper a weak accept.

Here are some general comments:
How is the multiset automata learnt? For weighted automata, one classical way is to use spectral learning algorithm (see Balle et. al. 2014). In this paper, the learning aspect of the multiset automata was not mentioned. I assume that the authors use some kind of gradient descent to optimize the weights w.r.t the whole networks. However, I do think it’s important to let the readers know this key step.

For the first experiment on the position encoding. I really like the derivation here and it seems that theoretically, multiset automata should be a generalization of the position encodings. However, the experiments didn’t show much difference. Is there any potential explanation here? Moreover, what is the advantage of using multiset automata in transformers instead of the original position encoding? Is it the runtime is faster? Cause you only need to compute the diagonal parameters and thus drastically reduce the number of parameters? If so, a comparison of runtime might be useful here to further showcase the advantage of the multiset automata. 

For the first application, it is great that the authors shows the connection, but it seems that it just stops at the level of showing the position encodings can be viewed as a multiset automata. For example, what happens if you don’t restrict it to be sinusoidal functions? e.g. set the transitions to be diagonal and directly optimize with gradient descent? 
For the second experiment, I’m a little confused about the experiment setup and the baselines. First how do the authors incorporate multiset automata into the deepset models? In Figure 1, every neural architectures have this embedding layers with diagonal transition matrices, does this mean the multiset automata is applied to encode the input for every architecture? If so is it possible that the use of multiset automata in LSTM, GRU and deepset, is actually hurting the performance? Maybe a comparison with vanilla LSTM, GRU and deepset is also needed. 

Moreover, for the second experiment, the size of LSTM, GRU, deepset seems to be smaller comparing to the complex product layer in the authors’ architecture (about half of the size). It is true that the authors mentioned that with non-unary automata, the size of the automata is significantly larger, but is this set-up fair for the baselines, e.g. if you use 150 size of LSTM, will it perform equally well to the multiset automata?

In addition, I have a bit of difficulty understanding why three embedding layers are needed to learn the complex number, is it possible to learn r, a, b jointly with one embedding?

Is there some real data experiment done for the second application (the extension to deepset), to further showcase the significance of using complex domain?

Here are some writing comments (did not affect the decision):
In page 6, the bullet point “Diagonal polar”, what does (#1 above) mean? Same goes for (#2 above) in the latter point. 
In “Full matrix”, the sentence “…, and transition matrix using orthogonal initialization…” does not have a verb and is a bit confusing to read. 

Page 7, second paragraph, line 4, in the brackets. There are two sentences in the brackets, and it feels a bit heavy and it actually says something important. Maybe either put it out or leave it as a footnote?

Overall, I like the concept of the multiset automata, but I feel there is a lack of highlights to further showcase this paper. I feel maybe a further investigation of either of these application could make a great paper. 
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: This work presents an encoding approach for unordered set input to neural networks. The authors base their approach on weighted finite automata, where in order to absorb unordered sets, they enforce multiplicative commutativity on transition matrices by approximating them as complex diagonal matrices. The authors furthermore provide mathematical references and results to derive bounds for their approximation. They show that positional encoding in Transformer network can be seen as a special case of their multiset encoding scheme, which also generalizes DeepSets encoding from real to complex numbers.

The paper is well-written and easy to follow. The work tries to unify positional encoding in Transformers and Deepsets by establishing a different view to multiset encoding. My major concern however is that the authors do not provide any reasoning as to why do we need the weighted automata machinery behind their approach? Effectively what they do can simply be seen as embedding of inherently periodic multiset elements using periodic functions, which are parameterized by non-linear transformations of data. Such encoding schemes have long been used in signal processing. 

I might have missed something, but in my opinion the theoretical contribution of the work is rather tangential to the empirical analysis and results presented in the paper. 
review_title: Official Blind Review #3

Meta-review: Main summary: Paper is about generating feature representations for set elements using weighted multiset automata

Discussion:
reviewer 1: paper is well written but experimental results are not convincing
reviewer 2: well written but weak motivation
reviewer 3: well written but reviewer has some questions around the motivation of weighted automata machinery. 
Recommendation: all the reviewers agree its well written but the paper could be stronger with motivation and experiments, all reviewers agree. I vote Reject.
Decision: Reject