Title: REPRESENTING UNORDERED DATA USING MULTISET AUTOMATA AND COMPLEX NUMBERS

Abstract: Unordered, variable-sized inputs arise in many settings across multiple fields. The ability for set-and multiset-oriented neural networks to handle this type of input has been the focus of much work in recent years. We propose to represent multisets using complexweighted multiset automata and show how the multiset representations of certain existing neural architectures can be viewed as special cases of ours. Namely, (1) we provide a new theoretical and intuitive justification for the Transformer model's representation of positions using sinusoidal functions, and (2) we extend the DeepSets model to use complex numbers, enabling it to outperform the existing model on an extension of one of their tasks.

1. INTRODUCTION:

Neural networks which operate on set-structured input have been gaining interest for their ability to handle unordered and variable-sized inputs (Vinyals et al., 2015; Wagstaff et al., 2019) . They have been applied to various tasks, such as processing graph nodes (Murphy et al., 2018) , hypergraphs (Maron et al., 2019) , 3D image reconstruction (Yang et al., 2019) , and point cloud classification and image tagging (Zaheer et al., 2017) . Similar network structures have been applied to multiple instance learning (Pevný and Somol, 2016) .

In particular, the DeepSets model (Zaheer et al., 2017) computes a representation of each element of the set, then combines the representations using a commutative function (e.g., addition) to form a representation of the set that discards ordering information. Zaheer et al. (2017) provide a proof that any function on sets can be modeled this way, by encoding sets as base-4 fractions and using the universal function approximation theorem, but their actual proposed model is far simpler than the model constructed by the theorem.

In this paper, we propose to compute representations of multisets using weighted multiset automata, a variant of weighted finite-state (string) automata in which the order of the input symbols does not affect the output. In some sense, this is the most general representation of a multiset that can be computed incrementally using only a finite amount of memory, and it can be directly implemented inside a neural network. We show how to train these automata efficiently by approximating them with string automata whose weights form complex, diagonal matrices.

Our representation generalizes DeepSets slightly, and it also turns out to be a generalization of the Transformer's position encodings (Vaswani et al., 2017) . In Sections 4 and 5, we discuss the application of our representation in both cases.

• The Transformer (Vaswani et al., 2017) models the absolute position of a word within a sentence.

This position can be thought of as a multiset over a single element, and indeed the Transformer uses a position encoding involving sinusoidal functions that turns out to be a special case of our representation. So weighted multiset automata provide a new theoretical and intuitive justification for sinusoidal position encodings. We also experiment with several variations on position encodings inspired by this justification, and although they do not yield any improvement, we do find that learned position encodings in our representation do better than learning a different vector for each absolute position.

• We extend the DeepSets model to use our representation, which amounts to upgrading it from real to complex numbers. On an extension of one of their tasks (adding a sequence of one-digit numbers and predicting the units digit), our model is able to reach perfect performance, whereas the original DeepSets model does no better than chance.

2. WEIGHTED MULTISET AUTOMATA:

We define weighted finite automata below using a matrix formulation. Throughout, let K be either R or C. , λ, µ, ρ) , where Q = {1, . . . , d} is a finite set of states, Σ is a finite alphabet, λ ∈ K 1×d is a row vector of initial weights, µ : Σ → K d×d assigns a transition matrix to every symbol, and ρ ∈ K d×1 is a column vector of final weights.

Definition 1. A K-weighted finite automaton (WFA) over Σ is a tuple M = (Q, Σ

(We do not use the final weights ρ in this paper, but include them for completeness.)

We extend the mapping µ to strings:

If w = w 1 • • • w n ∈ Σ * , then µ(w) = µ(w 1 ) • • • µ(w n ). Then, the vector of forward weights of a string w is fw M (w) = λ n p=1 µ(w p ) .

Note that, different from many definitions of weighted automata, this definition does not allow -transitions, and there may be more than one initial state. (Throughout this paper, we use to stand for a small real number.)

The analogue of finite automata for multisets is the special case of the above definition where multiplication of the transition matrices µ(a) does not depend on their order.

Definition 2. A K-weighted multiset finite automaton is one whose transition matrices commute pairwise. That is, for all a, b ∈ Σ, we have µ(a)µ(b) = µ(b)µ(a).

Our proposal, then, is to represent a multiset w by the vector of forward weights, fw M (w), with respect to some weighted multiset automaton M . In the context of a neural network, the transition weights µ(a) can be computed by any function as long as it does not depend on the ordering of symbols, and the forward weights can be used by the network in any way whatsoever.

3. TRAINING:

Definition 2 does not lend itself well to training, because parameter optimization needs to be done subject to the commutativity constraint. Previous work (DeBenedetto and Chiang, 2018) suggested approximating training of a multiset automaton by training a string automaton while using a regularizer to encourage the weight matrices to be close to commuting. However, this strategy cannot make them commute exactly, and the regularizer, which has O(|Σ| 2 ) terms, is expensive to compute.

Here, we pursue a different strategy, which is to restrict the transition matrices µ(a) to be diagonal. This guarantees that they commute. As a bonus, diagonal matrices are computionally less expensive than full matrices. Furthermore, we show that if we allow complex weights, we can learn multisets with diagonal matrices almost as well as with full matrices. We show this first for the special case of unary automata ( §3.1) and then general multiset automata ( §3.2).

3.1. UNARY AUTOMATA:

Call an automaton unary if |Σ| = 1. Then, for brevity, we simply write µ instead of µ(a) where a is the only symbol in Σ.

Let • be the Frobenius norm; by equivalence of norms (Horn and Johnson, 2012, 352) , the results below should carry over to any other matrix norm, as long as it is monotone, that is: if

A ≤ B elementwise, then A ≤ B .

As stated above, our strategy for training a unary automaton is to allow µ to be complex but restrict it to be diagonal. The restriction does not lose much generality, because any matrix can approximated by a complex diagonal matrix in the following sense (Horn and Johnson, 2012, 116) : Proposition 1. For any complex square matrix A and > 0, there is a complex matrix E such that E ≤ and

A + E is diagonalizable in C.

Proof. Form the Jordan decomposition A = P JP -1 . We can choose a diagonal matrix D such that D ≤ κ(P ) (where κ(P ) = P P -1 ) and the diagonal entries of J + D are all different. Then J + D is diagonalizable. Let E = P DP -1 ; then E ≤ P D P -1 = κ(P ) D ≤ , and A + E = P (J + D)P -1 is also diagonalizable.

Thus, for a unary automaton M with transition matrix µ, we can choose Qµ Q -1 close to µ such that µ is diagonal. So M is close to the automaton with initial weights λ = λQ and transition weights µ ≈ Q -1 µQ. This means that in training, we can directly learn complex initial weights λ and a complex diagonal transition matrix µ , and the resulting automaton (M ) should be able to represent multisets almost as well as a general unary automaton (M ) can.

It might be thought that even if µ approximates µ well, perhaps the forward weights, which involve possibly large powers of µ, will not be approximated well. As some additional assurance, we have the following error bound on the powers of µ: Proposition 2. For any complex square matrix A, > 0, and 0 < r < 1, there is a complex matrix E such that A + E is diagonalizable in C and, for all n ≥ 0,

(A + E) n -A n ≤ r n if A nilpotent, (A + E) n -A n A n ≤ n otherwise.

For the proof, please see Appendix A.

3.2. GENERAL CASE:

In this section, we allow Σ to be of any size. Proposition 1 unfortunately does not hold in general for multiple matrices (O' Meara and Vinsonhaler, 2006) . That is, it may not be possible to perturb a set of commuting matrices so that they are simultaneously diagonalizable. Definition 3. Matrices A 1 , . . . , A m are simultaneously diagonalizable if there exists an invertible matrix P such that

P A i P -1 is diagonal for all i ∈ {1, • • • , n}. We say that A 1 , • • • , A m are approximately simultaneously diagonalizable (ASD) if, for any > 0, there are matrices E 1 , . . . , E m such that E i ≤ and A 1 + E 1 , . . . , A m + E m are simultaneously diagonalizable.

O' Meara and Vinsonhaler (2006) give examples of sets of matrices that are commuting but not ASD. However, if we are willing to add new states to the automaton (that is, to increase the dimensionality of the weight matrices), we can make them ASD.

Proposition 3. Any weighted multiset automaton is close to an automaton that can be converted to a complex-weighted diagonal automaton, possibly with more states.

Proof. First we start with a fact from O' Meara and Vinsonhaler (2006) .

Lemma 4. Suppose A 1 , . . . , A k are commuting n × n matrices over an algebraically closed field F . Then there exists an invertible matrix C such that C -1 A 1 C, . . . , C -1 A k C are block diagonal matrices with matching block structures and each diagonal block has only a single eigenvalue (ignoring multiplicities). That is, there is a partition

EQUATION

where each B ij is an n j × n j matrix having only a single eigenvalue for i = 1, . . . , k and j = 1, . . . , r. Moreover, if B 1j , . . . , B kj are ASD for j = 1, . . . , r, then A 1 , . . . , A k are ASD.

Furthermore, O' Meara and Vinsonhaler (2006) observe that each block can be written as

B ij = λ ij I + N ij where N ij is nilpotent, so A 1 , . . . , A k are ASD iff N 1j , . . . , N kj are for all j.

So the transition matrices of the automaton can be rewritten in the above form, and the problem of converting an automaton to one that is ASD is reduced to the problem of converting an automaton with nilpotent transition matrices (equivalently, an automaton recognizing a finite language) to one that is ASD (possibly with more states). See Appendix B for one such construction.

This means that if we want to learn representations of multisets over a finite alphabet Σ, it suffices to constrain the transition matrices to be complex diagonal, possibly with more states. Unfortunately, the best construction we know of (Appendix B) increases the number of states by a lot. But this does not in any way prevent the use our representation; we can choose however many states we want, and it's an empirical question whether the number of states is enough to learn good representations.

The following two sections look at two practical applications of our representation.

4. POSITION ENCODINGS:

One of the distinguishing features of the Transformer network for machine translation (Vaswani et al., 2017) , compared with older RNN-based models, is its curious-looking position encodings,

EQUATION

which map word positions p (ranging from 1 to n, the sentence length) to points in the plane and are the model's sole source of information about word order.

In this section, we show how these position encodings can be interpreted as the forward weights of a weighted unary automaton. We also report on some experiments on some extensions of position encodings inspired by this interpretation.

4.1. AS A WEIGHTED UNARY AUTOMATON:

Consider a diagonal unary automaton M in the following form:

λ = exp iφ 1 exp -iφ 1 exp iφ 2 exp -iφ 2 • • • µ =         exp iθ 1 0 0 0 • • • 0 exp -iθ 1 0 0 • • • 0 0 exp iθ 2 0 . . . 0 0 0 exp -iθ 2 • • • . . . . . . . . . . . . . . .        

In order for a complex-weighted automaton to be equivalent to some real-weighted automaton, the entries must come in conjugate pairs like this, so this form is fully general.

By a change of basis, this becomes the following unary automaton M (this is sometimes called the real Jordan form):

EQUATION

Then, for any string prefix u (making use of the angle sum identities):

fw M (u) = cos(φ 1 + |u|θ 1 ) sin(φ 1 + |u|θ 1 ) cos(φ 2 + |u|θ 2 ) sin(φ 2 + |u|θ 2 ) • • • .

If we let

φ i = π 2 θ j = -10000 -2(j-1)/d

this becomes exactly equal to the position encodings defined in (2). Thus, the Transformer's position encodings can be reinterpreted as follows: it runs automaton M over the input string and uses the forward weights of M just before position p to represent p. This encoding, together with the embedding of word w p , is used as the input to the first self-attention layer.

4.2. EXPERIMENTS:

This reinterpretation suggests some potential extensions to position encodings: 1. Using the diagonal, polar form of the transition matrix (3), learn the φ i and θ i instead of keeping them fixed. 2. Learn all the initial weights and full transition matrix directly.

We carried out some experiments to see if these methods perform better or worse than the original. We used an open-source implementation of the Transformer, Witwicky. 1 The settings used were the default settings, except that we used 8k joint BPE operations and d = 512 embedding dimensions. We tested the following variations on position encodings. • Diagonal polar fixed: The original sinusoidal encodings (Vaswani et al., 2017) .

learned angles: Initialize the φ i and θ i to the original values, then optimize them (#1 above).

• Full matrix random: Randomize initial weights so that their expected norm is the same as the original, and transition matrix using orthogonal initialization (Saxe et al., 2013) , and do not optimize them. learned: Initialize λ and µ as above, and then optimize them (#2 above).

• Per position random: Choose a vector with fixed norm and random angle for each absolute position, and do not optimize them. learned: Learn an encoding for each absolute position (Gehring et al., 2017) .

Table 1 shows that no method is clearly the best. The only method that appears to be worse than the others is "per position, learned," which, although best on Urdu-English, does much worse than other methods on several tasks. By contrast, the learned embeddings based on multiset automata ("diagonal polar, learned angles" and "full matrix, learned") are usually close to the best, lending some support to our interpretation.

5. COMPLEX DEEPSETS:

In this sectoin, we incorporate a weighted multiset automaton into the DeepSets (Zaheer et al., 2017) model, extending it to use complex numbers.

5.1. MODELS:

The DeepSets model computes a vector representation for each input symbol and sums them to discard ordering information. We may think of the elementwise layers as computing the log-weights of a diagonal multiset automaton, and the summation layer as computing the forward log-weights of the multiset. (The logs are needed because DeepSets adds, whereas multiset automata multiply.) However, DeepSets uses only real weights, whereas our multiset automata use complex weights. Thus, DeepSets can be viewed as using a multiset representation which is a special case of ours. We conduct experiments comparing the DeepSets model (Zaheer et al., 2017) , a GRU model, an LSTM model, and our complex multiset model. The code and layer sizes for the three baselines come from the DeepSets paper.2 See Figure 1 for layer types and sizes for the three baseline models.

In our system, to avoid underflow when multiplying many complex numbers, we store each complex number as e r (a+bi) where r, a, and b are real and a and b are normalized such that a 2 +b 2 = 1 prior to multiplication. Thus, for each complex-valued parameter, we have three scalars (r, a, and b) to learn. To this end, each input is fed into three separate embedding layers of size 50 (for r, a, and b). (While the DeepSets code uses a dense layer at this point, in our network, we found that we could feed the embeddings directly into a complex multiplication layer to discard ordering information. This reduced the number of parameters for our model and did not affect performance.) The output of this is then a new r, a, and b which are concatenated and fed into a final dense layer as before to obtain the output. Since our diagonalized automata have complex initial weights (λ ), we also tried learning a complex initial weight vector λ , but this had no effect on performance.

The total number of parameters for each model was 4,161 parameters for the DeepSets model, 31,351 parameters for the LSTM model, 44,621 parameters for the GRU model, and 1,801 parameters for our model. In order to eliminate number of parameters as a difference from our model to the DeepSets model, we also tried the DeepSets model without the first dense layer and with embedding sizes of 150 to exactly match the number of parameters of our model, and the results on the test tasks were not significantly different from the baseline DeepSets model.

For all experiments, we used mean squared error loss, a learning rate decay of 0.5 after the validation loss does not decrease for 2 epochs, and early stopping after the validation loss does not decrease for 10 epochs. In task 1, the LSTM and GRU models were unable to generalize to examples larger than seen in training, while DeepSets and our model generalize to all test lengths. For task 2, only our model is able to return the correct units digit for all test lengths. The GRU, LSTM, and DeepSets models fail to learn any behavior beyond random guessing.

Task 1: Sum of digits In this task, taken from Zaheer et al. (2017) , the network receives a set of single digit integers as input and must output the sum of those digits. The output is rounded to the nearest integer to measure accuracy. The training set consisted of 100k randomly generated sequences of digits 1-9 with lengths from 1 to 50. They were fed to each network in the order in which they were generated (which only affects GRU and LSTM). This was then split into training and dev with approximately a 99/1 split. The test set consisted of randomly generated sequences of lengths that were multiples of 5 from 5 to 95. Figure 2 shows that both our model and DeepSets obtain perfect accuracy on the test data, while the LSTM and GRU fail to generalize to longer sequences.

Task 2: Returning units digit of a sum The second task is similar to the first, but only requires returning the units digit of the sum. The data and evaluation are otherwise the same as task 1. Here, random guessing within the output range 0-9 achieves approximately 10% accuracy. Figure 2 show that DeepSets, LSTM, and GRU are unable to achieve performance better than random guessing on the test data. Our method is able to return the units digit perfectly for all test lengths, because it effectively learns to use the cyclic nature of complex multiplication to produce the units digit.

6. CONCLUSION:

We have proven that weighted multiset automata can be approximated by automata with (complex) diagonal transition matrices. This formulation permits simpler elementwise multiplication instead of matrix multiplication, and requires fewer parameters when using the same number of states. We show that this type of automaton naturally arises within existing neural architectures, and that this representation generalizes two existing multiset representations, the Transformer's position encodings and DeepSets. Our results provide new theoretical and intuitive justification for these models, and, in one case, lead to a change in the model that drastically improves its performance.

The powers of J look like

J n =      n 0 λ n n 1 λ n-1 n 2 λ n-2 • • • n 0 λ n n 1 λ n-1 • • • n 0 λ n • • • . . .      More concisely, for k ≥ j, [J n ] jk = n k -j λ n-k+j .

Let D be a diagonal matrix whose elements are in [-λ, 0) and are all different. The powers of (J + D) are

[(J + D) n ] jk = c jk [J n ] jk where c jk ≥ (1 -) n-k+j ≥ 1 -(n -k + j) ≥ 1 -n .

Finally, form their difference:

[(J + D) n -J n ] jk = (c jk -1)[J n ] jk |[(J + D) n -J n ] jk | ≤ n |[J n ] jk | (J + D) n -J n ≤ n J n (J + D) n -J n J n ≤ n .

Lemma 6. If J is a Jordan block with zero eigenvalue, then for any > 0, r > 0, there is a complex matrix E such that M + E is diagonalizable in C and

(M + E) n -M n ≤ r n .

Proof. In this case, we have to perturb the diagonal elements to nonzero values. For any δ ≤ 1 2 , let D be a diagonal matrix whose elements are in (0, δ] and are all different. Then the elements of ((J + D) n -J n ) are:

[(J + D) n -J n ] jk ≤ n k -j δ n-k+j (0 ≤ k -j < min{n, d}) < 2 n δ min{0,n-d}+1 so the error is at most 2 d-1 d(2δ) min{0,n-d}+1 . Let δ = min{ 1 2 , r, r 2 d d }.

Now we can prove Proposition 2.

use that for direct product.) These operations extend naturally to weighted multiset automata and correspond roughly to union and concatenation, respectively: Proposition 8. If M is a weighted multiset automaton with d states recognizing a finite language (that is, all of its transition matrices are nilpotent), there exists an equivalent automaton with O(d 2|Σ|+1 ) states whose transition matrices are ASD.

λ A⊕B = λ A ⊕ λ B µ A⊕B (a) = µ A (a) ⊕ µ B (a) ρ A⊕B = ρ A ⊕ ρ B λ A¡B = λ A ⊗ λ B µ A¡B (a) = µ A (a) ¡ µ B (a) ρ A¡B = ρ B ⊗

Proof. Because any set of commuting matrices can be simultaneously triangularized by a change of basis, assume without loss of generality that M 's transition matrices are upper triangular, that is, there are no transitions from state q to state r where q > r.

The idea is that M should simulate a run of M in which the symbols are read in lexicographic order. It does so by building up partial runs, one for each symbol in Σ, and then stitching them together.

Let Q be the states of M , and let a 1 , . . . , a m be the symbols of Σ. For all a ∈ Σ, q, r ∈ Q, define M q,a,r to be the automaton which simulates M starting from state q, reading only a's, and ending in state r. Then

M = q0∈Q • • • qm∈Q λ q0 M q0,a1,q1 ¡ • • • ¡ M qm-1,am,qm

(where the multiplication by the scalar λ q0 means scaling the initial weight vector by λ q0 ). By Proposition 7, M is ASD, and because each of the M q,a,r has no more than d states, M has at most d 2|Σ|+1 states.

:

https://github.com/tnq177/witwicky

https://github.com/manzilzaheer/DeepSets/blob/master/DigitSum/text_sum.ipynb

Figures and Tables:

Figure 1: Neural architecture for (left to right) LSTM, GRU, DeepSets, and our model. Each cell indicates layer type and output dimension. Color indicates which part of a multiset automaton it corresponds to, though only our model is fully general for multiset automata.

Figure2: Results for task 1 (left) and task 2 (right). In task 1, the LSTM and GRU models were unable to generalize to examples larger than seen in training, while DeepSets and our model generalize to all test lengths. For task 2, only our model is able to return the correct units digit for all test lengths. The GRU, LSTM, and DeepSets models fail to learn any behavior beyond random guessing.

ρ B They are of interest here because they preserve the ASD property: Proposition 7. If M 1 and M 2 are multiset automata with ASD transition matrices, then M 1 ⊕ M 2 has ASD transition matrices, and M 1 ¡ M 2 has ASD transition matrices.Proof. First consider the ⊕ operation. Let µ 1 (a) (for all a) be the transition matrices of M 1 . For any > 0, let E 1 (a) be the perturbations of the µ 1 (a) such that E 1 (a) ≤ /2 and the µ 1 (a) + E 1 (a) (for all a) are simultaneously diagonalizable. Similarly for M 2 . Then the matrices (µ1 (a) + E 1 (a)) ⊕ (µ 2 (a) + E 2 (a))(for all a) are simultaneously diagonalizable, and(µ 1 (a) + E 1 (a)) ⊕ (µ 2 (a) + E 2 (a)) -µ 1 (a) ⊕ µ 2 (a) = E 1 (a) ⊕ E 2 (a) ≤ E 1 (a) + E 2 (a) = .Next, we consider the ¡ operation. Let d 1 and d 2 be the number of states in M 1 and M 2 , respectively. This time, we choose E 1 (a) ≤ /(2d 2 ) and E 2 (a) ≤ /(2d 1 ). Then the matrices (µ1 (a) + E 1 (a)) ¡ (µ 2 (a) + E 2 (a)) (for all a) are simultaneously diagonalizable, and(µ 1 (a) + E 1 (a)) ¡ (µ 2 (a) + E 2 (a)) = (µ 1 (a) + E 1 (a)) ⊗ I + I ⊗ (µ 2 (a) + E 2 (a)) = µ 1 (a) ⊗ I + E 1 (a) ⊗ I + I ⊗ µ 2 (a) + I ⊗ E 2 (a) = (µ 1 (a) ¡ µ 2 (a)) + (E 1 (a) ¡ E 2 (a)) (µ 1 (a) + E 1 (a)) ¡ (µ 2 (a) + E 2 (a)) -µ 1 (a) ¡ µ 2 (a) = E 1 (a) ¡ E 2 (a) = E 1 (a) ⊗ I + I ⊗ E 2 (a) ≤ E 1 (a) ⊗ I + I ⊗ E 2 (a) ≤ E 1 (a) d 2 + d 1 E 2 (a) ≤ .

Machine translation experiments with various position encodings. Scores are in case-insensitive BLEU, a common machine translation metric. The best score in each column is printed in boldface.

Table content: <table><tr><td>case-insensitive BLEU</td></tr></table>

Peer review (iclr2020):
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.