Representing Unordered Data Using Multiset Automata and Complex Numbers
Authors: Justin DeBenedetto
David Chiang
Venue:  (2020)
Keywords: sets
multisets
automata
complex numbers
position encodings

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 complex-weighted 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.  


Under review conference paper at ICLR 2020
REPRESENTING UNORDERED DATA USING MULTISET AUTOMATA AND COMPLEX NUMBERS
Anonymous authors Paper under double-blind review
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 complex- weighted multiset automata and show how the multiset representations of certain existing neural architectures can be viewed special cases of ours. Namely, (1) provide 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 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 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).
particular, the DeepSets model (Zaheer et al., 2017) computes representation each element of the set, then combines the representations using commutative function (e.g., addition) to form representation of the set that discards ordering information. Zaheer et (2017) provide 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 automala, variant of weighted stntte-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 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 generalization of the Trans- former's position encodings (Vaswani et al., 2017). In Sections 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 a position encoding involving sinusoidal functions that turns out to be special case of representation. So weighted multiset automata provide a new theoretical and intuitive justification for sinusoidal position encodings. We also experiment with several variations position encodings

---

Under review conference paper at ICLR 2020
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 to complex numbers. On an extension of one of their tasks (adding a sequence of one-digit numbers and predicting the units digit), model is able to reach perfect performance, whereas the original DeepSets model does no better than chance.
representation, which amounts to upgrading it from real
2 WEIGHTED MULTISET AUTOMATA
We define weighted finite automata below using matrix formulation. Throughout, let K be either IR or C. Definition 1. A K-weighted finite automaton (WFA) over Σ is tuple M (Q, H4, p). where Q {L...., df is a finite set of states, Σ a finite alphabet, kixd is a row vector of initial weights, # E kddd assigns transition matrix every symbol, and p KKdx is column vector of final weights.
(We do not use the final weights in this paper, but include them for completeness.)
We extend the mapping l strings: If wi Un Σ" then p(w) ((wr)) ... ...p((a)) Then, the vector of forward weights of string is fw (w))(w)
(IT== ((wp)).
Note that, different from many definitions of weighted automata, this definition does not allow e-transitions, to stand for small real
and there may be more than initial state. (Throughout this paper, number.)
The analogue of finite automata for multisets is the special case of the above definition where multiplication of the transition matrices p(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, E E, we have p()))((b) p(b)p(a).
Our proposal, then, is to represent a multiset w by the vector of forward weights, f (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 does not depend on the ordering of symbols, and the forward weights 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 multiset automaton by training a string automaton while using regularizer to encourage the weight matrices to be close to commuting. However, this strategy cannot make them commute exactly, and the regularizer, which has ( terms, is expensive to compute.
Here, pursue different strategy, which is restrict the transition matrices μuaa be diagonal. This guarantees that they commute. As a bonus, diagonal matrices are computionally less expensive than full matrices. Furthermore, we show that if allow complex weights, 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).
2

---

Under review conference paper at ICLR 2020
3.1 UNARY AUTOMATA
Call an automaton unary if |-]] = 1. Then, for brevity, we simply write instead of (u(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 monotone, that is: if A B elementwise, then
|| < |B]]
As stated above, our strategy for training a unary automaton is to allow μ to be complex but restrict 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 e > 0, there is complex matrix E such that E S and A + is diagonalizable C.
Proof. Form the Jordan decomposition A = PJP-1. We can choose a diagonal matrix D such that ||]| <
ह(P (where x(P) = |P|||P-*|| and the diagonal entries of J + D are all different. Then J + D is
diagonalizable. Let E = PDP-1; then || z ||P||| P|||| DII c, and A E = P(J D)P-1 is also diagonalizable.
Thus, for unary automaton M/ with transition matrix μ., we can choose Qp'Q=1 close to μ such that μ' is diagonal. So M is close to the automaton with initial weights x'= Q-'nQ. This means that in training, we can directly learn complex initial weights X' and 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.
= XQ and transition weights j se
It might be thought that even if μí approximates μ well, perhaps the forward weights, which involve possibly large powers of μu, 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, 6 0, and 1, there is a complex matrix E such that A + E is diagonalizable in C and, for all n 2 0,
[I(A + E)"
AA'l
S r
if A nilpotent,
(A E)" A
nc
otherwise.
|A"l
For the proof, please see Appendix A.
3.2 GENERAL CASE
In this section, allow D' to be of any size. Proposition I 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 that they are simultaneously diagonalizable.
Definition 3. Matrices Ai...., Am are simultancously diagonalizable if there exists an invertible matrix such that P A, P-1 is diagonal for all i E (1,....,)
We say that A1, ...... Am are approximately simultaneously diagonalizable (ASD) for any >> O, there are matrices Ey...., E,, such that |E|| < c and A₁ + Ei...., Am + Em are simultaneously diagonalizable.
O' Meara and Vinsonhaler (2006) give examples of sets of matrices that are commuting but not ASD. How- ever, if we are willing to add new states to the automaton (that is, to increase the dimensionality of the weight matrices), we make them ASD.
3

---

Under review conference paper at ICLR 2020
Proposition Any weighted multiset automaton is close an automaton that can be converted complex-weighted diagonal automaton, possibly with more states.
Proof. First start with fact from O'Meara and Vinsonhaler (2006).
Lemma 4, Suppose A1,--., Ag commuting
matrices over an algebraically closed field F. Then
there exists an invertible matrix C such that C,C....... - Cr are block diagonal matrices with matching block structures and each diagonal block has only a single eigenvalue (ignoring multiplicities). That is, there is partition n n2 4..4 + Tlp of To such that
Bi
B12
C- A,C =BC=B
(1)
Bir
where each Biy is an X nj matrix having only single eigenvalue for i = 1..... k and j = 1...., Moreover, if Bij:-.., Bkj are ASD for j =,...., then A1,..., A₁ are ASD.
Furthermore, O'Meara and Vinsonhaler (2006) observe that each block can be written as Bi, = Aiz No where Nij is nilpotent, so .b. are ASD , Nks are for all j.
So the transition matrices of the automaton be rewritten in the above form, and the problem of converting an automaton to one that is ASD reduced to the problem of converting an automaton with nilpotent transition matrices (equivalently, an automaton recognizing finite language) to that is ASD (possibly with more states). See Appendix B for one such construction.
This means that if want to learn representations of multisets strain the transition matrices to complex diagonal, possibly with more states. Unfortunately, the best construction know of (Appendíx B) increases the number of states by 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 learn good representations.
finite alphabet Σ, it suffices to
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 aurious-looking position encodings,
2 sin 10000 -()00000(--)///( 1)
(2)
e cos 10000 2(j-002(j-1)/6ppp 1)
which map word positions p (ranging from to the sentence length) to points in the plane and are the model's sole source of information about word order.
In this section, show how these position encodings can be interpreted the forward weights of weighted unary automaton. We also report on some experiments on some extensions position encodings inspired by this interpretation.
4

---

Under review conference paper at ICLR 2020
4.1 AS A WEIGHTED UNARY AUTOMATON
Consider diagonal unary automaton M in the following form:
i exp
exp
i01
exp idz
exp
-02
exp 101
exp -0
cxp 102
1
exp
i00
In order for a complex-weighted automaton to be equivalent to some real- wal-weighted automaton, the entries must come in conjugate pairs like this, so this form is fully general.
By change of basis, this becomes the following unary automaton M' (this is sometimes called the real Jordan form):
[cos Φ1
sin Φ1
cos Φ2
sin Φ2
...
cos 01
sin 01
0
sin 0
cos
O
(3)
0
0
cos 8₂
sin 02
0
0
sin 0g
cos O2
Then, for any string prefix (making use of the angle sum identities):
fwar (2) = (css(01 + [u(01) sin(é1 + (u(01) cos(o2 + l2(02) sin(02 + (2) ...].
we let
π Ø: 2
0 10000 10000020-1100 1(j-)/dd
this becomes exactly equal to the position encodings defined in (2). Thus, the Transformer's position encod- ings 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 Wp, 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 0; 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 worse than the original. We used an open-source implementation of the Transformer, Witwicky.' 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.
/htpps: http://ggttttttt /ttt:sas//gttttt..ommoog////////
5

---

Under review conference paper at ICLR 2020
case-insensitive BLEU
Model
Training
En-Vi'
Uz-En
Ha-En
Hu-Bn
Ur-En
Ta-En
Tu-En
diagonal polar
fixed
32.6
25.7
24.4
34.2
11.5
13.4
25.7
learned angles
32.7
25.8
25.4
34.0
11.1
14.1
25.7
full matrix
random
32.6
25.9
25.8
34.1
10.9
12.8
26.1
learned
32.5
24.5
23.6
33.5
11.4
14.5
23.8
per position
random
32.6
24.9
24.6
34.1
11.0
14.1
24.4
learned
32.1
22.6
21.2
33.0
11.7
14.4
21.1
* "tokenized references
Table I: Machine translation experiments with various position encodings. Scores are in case-insensitive BI.UU, a common machine translation metric. The best score in each column is printed boldface.
Diagonal polar
fixed: The original sinusoidal encodings (Vaswani et al., 2017).
learned angles: Initialize the o, and 0g 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 optimize them. Initialize and as above, and then optimize them (#2 above).
learned:
Per position
Choose vector with fixed and random angle for each absolute position, and do not optimize them.
random:
learned:
Learn encoding for each absolute position (Gehring al., 2017).
Table 1 shows that 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 multiset automata ("diagonal polar, learned angles" and "full matrix, learned") are usually close to the best, lending some support to our interpretation.
COMPLEX DEEPSETS
this sectoin, we incorporate a weighted multiset automaton into DeepSets (Zaheer et al., 2017) model, extending it 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 computing the log- log-weights of diagonal multiset automaton, and the summation layer as computing the forward log-weightt of the multiset. (The logs 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 special case of ours.
6

---

Under review conference paper at ICLR 2020
InputLayer
InputLayer
InputLayer
InputLayer
Embedding
Embedding n 100
Embedding n 100
Embedding x
Embeddlin x 50
Embedding
nx 100
n x 50
LSTM
GRU 80
Dense x 30
Complex Product 150
50
Dense
Dense
Sum
Dense
30
Dense
Multiset input.
Diagonal transition matrices
Forward weights
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 multiset automaton it corresponds though only our model is fully general for multiset automata.
Figure 1:
We conduct experiments comparing the DeepSets model (Zaheer al., 2017). GRU model, an LSTM model, and our complex multiset model. The code and layer sizes for the three baselines come from the DeepSets paper. See Figure/ 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 ex (a++bi) where r, a, and b are real and and are normalized such that + 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 size 50 (for т, a, and b). (While the DeepSets code uses a dense layer this point, in network, found that could feed the embeddings directly into complex multiplication layer to discard ordering information. This reduced the number parameters for our model and did not affect performance.) The output of this is then into a final dense layer as before to obtain the output. Since our diagonalized automata have complex initial weights (X),, also tried learning complex initial weight vector X' but this had effect on performance.
r, 0, and which concatenated and fed
The total number of parameters for each model was 4, 1,16 parameters for the DeepSets model, 31 31,351 pa- rameters for the L.STM model, 44,621 parameters for the GRU model, and 1,801 parameters for 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, 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 epochs.
7

---

Under review conference paper at ICLR 2020
Digit Sum
Digit Sum, Units Digit
1.0
1.0
Accuracy
0.8
Accuracy
0.8
0.6
0.6
0.4
0.4
0.2
0.2
*
0.0
x
0.0
20
40
60
80
20
40
60
80
Number of digits
Number of digits
DeepSets LSTM - GRU Our Method
Figure 2: Results for task I (left) and task 2 (right). In task 1, the LSTM and GRU models were unable generalize to examples larger than seen in training, while DeepSets and our model generalize 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.
5.2 EXPERIMENTS
Task 1: Sum of digits this task, taken from Zaheer et al. (2017), the network receives a set of single digit integers input and must output the of those digits. The output is rounded to the nearest integer to measure accuracy. The training set consisted lengths from to 50. They were fed 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 95, Figure shows that both our model and DeepSets obtain perfect accuracy on the test data, while the LSTM and GRU fail generalize longer sequences.
100k randomly generated sequences digits 1-9 with
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 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 achieve performance better than random guessing on the data. Our method able to return the units digit perfectly for all test lengths, because it effectively learns to use the cyclic nature of complex multiplication 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 multi- plication, 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 change the model that drastically improves its performance.
8

---

Under review conference paper at ICLR 2020
REFERENCES
Justin DeBenedetto and David Chiang. Algorithms and training for weighted multiset automata and regular expressions. In Cezar Câmpeanu, editor, Implementation and Application of Automata, pages 146-158. Springer, 2018.
Jonas Gchring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. Convolutional sequence to sequence learning, 2017. arXiv:1705.0312.
Roger A. Horn and Charles A. Johnson. Matrix Analysis. Cambridge Univ. Press, 2nd edition, 2012.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph net-
works. Proc. ICLR, 2019.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak A. Rao, and Bruno Ribeiro. Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs, 2018. arXiv:1811.01900.
K.C. O'Meara and C. Vinsonhaler. On approximately simultaneously diagonalizable matrices. Linear Alge- bra and its Applications, 412(1):39 2006.
Tomás Pevný and Petr Somol. Using neural network formalism to solve multiple-instance problems. In Proc. ISNN, 2016.
Andrew M. Saxe, James L. McClelland, and Surya Ganguli. Exact solutions the nonlinear dynamics of learning in deep linear neural networks, 2013. arXiv:1312.6120.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proc. NeurIPS, 2017.
Oriol Vinyals, Samy Bengio, and Manjunath Kudlur. Order matters: Sequence to sequence for sets, 2015. arXiv:1511 1.t1:1511.0631..1 1.06391.
Edward Wagstaff, Fabian B. Fuchs, Martin Engelcke, Ingmar Posner, and Michael A. Osborne. On the limitations of representing functions on sets, 2019. arXiv:1901.0900
Bo Yang, Sen Wang, Andrew Markham, and Niki Trigoni. Robust attentional aggregation of deep feature sets for multi-view 3D reconstruction. International Journal of Computer Vision, 08 2019. doi: 10. 10.1007/ s1 11166-019--1211--w
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabás Póczos, Ruslan Salakhutdinov, and Alexan- Smola. Deep sets. In Proc. NeurIPS, 2017.
A PROOF OF PROPOSITION 2
Lemma 5. If is a Jordan block with nonzero eigenvalue, then the bound of Proposition 2 holds for J.
Proof. Note that for any 5, E 2 0, we have
(1
(1 - c) 2 1 6
2 max(6,c)
(1 c)nd > 1
9

---

Under review conference paper at ICLR 2020
The powers of look like
(n) A"
1 An
2 =n
An
AT)
More concisely, for k 2 j:
[J'1sx = ( 11
A" n=
k: -)
Let D be diagonal matrix whose elements are in [-eX, 0) and are all different. The powers of (J + D) are
[(J + D = cg
where
Cyk 2 (1 c)n-k+t
2 1 (n 1s + j)c
2 1
Finally, form their difference:
[(J + D) - J jk = (cjs 1)[Ja]
[[[ DY" JJ bk
[[
[[[ + D)" - [' I ne |
(I + D)" Ja
I NE.
||
Lemma 6. If J is a Jordan block with zero eigenvalue, then for any >>> 0, 0, there is complex matrix such that M + E is diagonalizable in C and
II E) - c. sr"
Proof. In this case, have to perturb the diagonal elements nonzero values. For any 2. let D be diagonal matrix whose elements are in (0, oj and are all different. Then the elements of ((J + D)" n J")
are:
(J + D)" J" <
{-jj 8n-ktt
n
(0 k - min(n,d))
2n 2m.
so the error is at most 24-1 24=22((2)umm(0nnn44) Let min (3) z).
Now can prove Proposition 2.
10

---

Under review conference paper at ICLR 2020
Proof. Form the Jordan decomposition M PJP-1 where
J1
J2
==
Jp_
We begin with the non-nilpotent case. Let x(P) |P]||| each Jordan block Jj:
|| be the Frobenius condition number of P. For
If Jj has nonzero eigenvalue, perturb it so that the absolute error of the nith power at most
|| by Lemma 5.
x(P)² 2p
If J has zero eigenvalue, perturb that the absolute error is at most
c(P 2p by Lemma 6.
Then the total absolute error all the blocks with nonzero eigenvalue is at most p(J)" S || the total absolute error of all the blocks with zero eigenvalue is also at most the combined total is
me R(P
1| And since
2
me
2 So
x(P)
Jnl S x(P)2 ||
Finally,
(M + E)" - M" = [P[([] D)" D) J")
((P))(((J + D)" J(
||
x(P)
|P- Pl
m(P)
ne ne|| ||
[IM + EY- II
< ne.
If M is nilpotent, the above argument does not go through, because p(J) = 0. Instead, use Lemma 6 to bound the absolute error of each block by =",, so that the total absolute error is at most r'c.
B MAKING AUTOMATA ASD
this section, we give a construction for converting a multiset automaton to one that is equivalent, but possibly has more states.
Let ① stand for the direct product of vector spaces, & for the Kronecker product, and define the shuffle
product A m B A & I + I T B. (This is known the Kronecker and is sometimes notated @ but
11

---

Under review conference paper at ICLR 2020
use that for direct product.) These operations extend naturally to weighted multiset automata and correspond roughly to union and concatenation, respectively:
Agg B AA A
pA@n(a) (a) pA(a) @ (a
PA@B PA pB
AAi = Aa & An
(a) (a(a) WU (a)
PAnB pn 8 pn
They are of interest here because they preserve the ASD property:
Proposition 7. If M1 and M2 are multiset automata with ASD transition matrices. then M1 @ M2 has ASD transition matrices, and M1 W M2 has ASD transition matrices.
Proof. First consider the @ operation. Let (a) (for all a) be the transition matrices of Mr. For any c > O, let Ei (a) be the perturbations of the (a) such that [a)]] S e/2 and the μ (a) Ei (a) (for all a) are simultaneously diagonalizable. Similarly for M2. Then the matrices (Jn(a) + Ei (a)) @ (12(4) + Ea)))
(for all a) simultaneously diagonalizable, and
(a) + (i)a e (uz(a) + Ez(a)) - (1(a) @ p2(a)) = [a) @ E2(a)]
[a)] + (aal
=
Next, we consider the и operation. Let d1 and d2 be the number of states in Mj and M2, respectively. This time, we choose [a)ll & c/(2dz) and [|E](a)]] S c/(2d)). Then the matrices (μ1(a) + E1 (a)) (u)(a) + E2(a)) (for all a) are simultaneously diagonalizable, and (Mi(a) + (a)) (p²(a) E²(a)) (mi (a) (a)) (
= (a) @ 1 I ( + Eg(a))
(2(a) + T F2((a)
(a)(a) (B()) E2())
[1(1(a)) (a)) m (p2(a) Ea(a)) (
= | &2a)]
<
Ex(a)
Proposition 8. IfM M a weighted multiset automaton with states recognizing a finite language (that is, all of its transition matrices are nilpotent), there exists an equivalent aulomaton with (dd22)+1) states whose transition matrices are ASD.
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 where >
The idea is that M' should simulate run of M which the symbols are read 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 a1,..., am be the symbols of Σ. For all E g. r E Q, define Mq..,- to be the automaton which simulates M starting from state reading only a's, and ending in state r. Then
M'
Auo Myn.r.
M 9m-11
O
(where the multiplication by the scalar Ayo means scaling the initial weight vector by Aoo) By Proposition 7, M' is ASD, and because each of the Ma has no more than d states, M' has at most d states.
12


Reviews:
[{"review_id": "BkxOG9FhKr", "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 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.\n\nThe 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. \n\nI 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. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked 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": {}}, {"review_id": "BJlFL4VpFS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 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. \n\nI 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.\n\nHere are some general comments:\nHow 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.\n\nFor 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. \n\nFor 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? \nFor 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. \n\nMoreover, 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?\n\nIn 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?\n\nIs there some real data experiment done for the second application (the extension to deepset), to further showcase the significance of using complex domain?\n\nHere are some writing comments (did not affect the decision):\nIn page 6, the bullet point “Diagonal polar”, what does (#1 above) mean? Same goes for (#2 above) in the latter point. \nIn “Full matrix”, the sentence “…, and transition matrix using orthogonal initialization…” does not have a verb and is a bit confusing to read. \n\nPage 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?\n\nOverall, 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. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "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": "BJepYfMAYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 generating feature representations for set elements using weighted multiset automata. Experiments show that this leads to better generalization performance in some tasks.\n\nI 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.\n\nIn 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.\n\nReading 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.\n\nThe second statement in section 4.1 is not clear to me: In what sense is the diagonal with alternating complex conjugate entries fully general?\n\nThe 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?\n\nThe main questions I would like to see answered (and adjusted in the paper) for me to accept this paper would be:\n\n* What is the general recipe for applying this technique to get representations of a multiset?\n* How do the experimental results validate the increased representational power of complex-weighted diagonal automata?", "extra_scores": {"experience_assessment": "I do not know much about this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

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