Year: 2019

Abstract:
Unordered, variable-sized inputs arise in many settings across multiple fields. The ability for setand multisetoriented 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.

heading: 1 INTRODUCTION
text: 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 (Pevný 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.

heading: 2 WEIGHTED MULTISET AUTOMATA
text: We define weighted finite automata below using a matrix formulation. Throughout, let K be either R or C. Definition 1. A K-weighted finite automaton (WFA) over Σ is a tuple M = (Q,Σ, λ, µ, ρ), where Q = {1, . . . , d} is a finite set of states, Σ is a finite alphabet, λ ∈ K1×d is a row vector of initial weights, µ : Σ → Kd×d assigns a transition matrix to every symbol, and ρ ∈ Kd×1 is a column vector of final weights.
(We do not use the final weights ρ in this paper, but include them for completeness.)
We extend the mapping µ to strings: If w = w1 · · ·wn ∈ Σ∗, then µ(w) = µ(w1) · · ·µ(wn). Then, the vector of forward weights of a string w is fwM (w) = λ (∏n p=1 µ(wp) ) .
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, fwM (w), with respect to some weighted multiset automatonM . 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.

heading: 3 TRAINING
text: 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).

heading: 3.1 UNARY AUTOMATA
text: 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 = PJP−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 = PDP−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 −An‖ ≤ rn if A nilpotent, ‖(A+ E)n −An‖
‖An‖ ≤ n otherwise.
For the proof, please see Appendix A.

heading: 3.2 GENERAL CASE
text: 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 A1, . . . , Am are simultaneously diagonalizable if there exists an invertible matrix P such that PAiP−1 is diagonal for all i ∈ {1, · · · , n}. We say thatA1, · · · , Am are approximately simultaneously diagonalizable (ASD) if, for any > 0, there are matrices E1, . . . , Em such that ‖Ei‖ ≤ and A1 + E1, . . . , Am + Em 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 A1, . . . , Ak are commuting n × n matrices over an algebraically closed field F . Then there exists an invertible matrix C such that C−1A1C, . . . , C−1AkC 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 n = n1 + · · ·+ nr of n such that
C−1AiC = Bi =  Bi1 Bi2 . . .
Bir  , (1) where each Bij is an nj × nj matrix having only a single eigenvalue for i = 1, . . . , k and j = 1, . . . , r. Moreover, if B1j , . . . , Bkj are ASD for j = 1, . . . , r, then A1, . . . , Ak are ASD.
Furthermore, O’Meara and Vinsonhaler (2006) observe that each block can be written as Bij = λijI +Nij where Nij is nilpotent, so A1, . . . , Ak are ASD iff N1j , . . . , Nkj 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.

heading: 4 POSITION ENCODINGS
text: 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,
ep2j−1 = sin 10000 −2(j−1)/d(p− 1)
ep2j = cos 10000 −2(j−1)/d(p− 1)
(2)
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.

heading: 4.1 AS A WEIGHTED UNARY AUTOMATON
text: 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):
λ′ = [ cosφ1 sinφ1 cosφ2 sinφ2 · · · ]
µ′ =  cos θ1 sin θ1 0 0 · · · − sin θ1 cos θ1 0 0 · · · 0 0 cos θ2 sin θ2 . . .
0 0 − sin θ2 cos θ2 · · · ... ... ... ... . . .
 (3)
Then, for any string prefix u (making use of the angle sum identities): fwM ′(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 automatonM ′ 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.

heading: 4.2 EXPERIMENTS
text: 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.
1https://github.com/tnq177/witwicky
case-insensitive BLEU Model Training En-Vi∗ Uz-En Ha-En Hu-En 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 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.

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

heading: 5.1 MODELS
text: 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 er(a+bi) where r, a, and b are real and a and b are normalized such that a2+b2 = 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.
2https://github.com/manzilzaheer/DeepSets/blob/master/DigitSum/text_sum.ipynb

heading: 5.2 EXPERIMENTS
text: 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.

heading: 6 CONCLUSION
text: 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.

heading: A PROOF OF PROPOSITION 2
text: Lemma 5. If J is a Jordan block with nonzero eigenvalue, then the bound of Proposition 2 holds for J .
Proof. Note that for any δ, ≥ 0, we have
(1− δ)(1− ) ≥ 1− δ − ≥ 1− 2 max{δ, } (1− )n ≥ 1− n
The powers of J look like
Jn =  ( 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,
[Jn]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 = cjk[J n]jk
where
cjk ≥ (1− )n−k+j
≥ 1− (n− k + j) ≥ 1− n .
Finally, form their difference:
[(J +D)n − Jn]jk = (cjk − 1)[Jn]jk |[(J +D)n − Jn]jk| ≤ n |[Jn]jk| ‖(J +D)n − Jn‖ ≤ n ‖Jn‖ ‖(J +D)n − Jn‖
‖Jn‖ ≤ 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 −Mn‖ ≤ rn .
Proof. In this case, we have to perturb the diagonal elements to nonzero values. For any δ ≤ 12 , let D be a diagonal matrix whose elements are in (0, δ] and are all different. Then the elements of ((J + D)n − Jn) are:
[(J +D)n − Jn]jk ≤ ( n
k − j
) δn−k+j (0 ≤ k − j < min{n, d})
< 2nδmin{0,n−d}+1
so the error is at most 2d−1d(2δ)min{0,n−d}+1. Let δ = min{ 12 , r, ( r 2 )d d}.
Now we can prove Proposition 2.
Proof. Form the Jordan decomposition M = PJP−1, where
J =  J1 J2 . . .
Jp  . We begin with the non-nilpotent case. Let κ(P ) = ‖P‖‖P−1‖ be the Frobenius condition number of P . For each Jordan block Jj :
• If Jj has nonzero eigenvalue, perturb it so that the absolute error of the nth power is at most n
κ(P )2 ‖Jnj ‖ 2p , by Lemma 5.
• If Jj has zero eigenvalue, perturb it so that the absolute error is at most n κ(P )2 ρ(J)n 2p , by Lemma 6.
Then the total absolute error of all the blocks with nonzero eigenvalue is at most n κ(P )2 ‖Jn‖ 2 . And since ρ(J)n ≤ ‖Jn‖, the total absolute error of all the blocks with zero eigenvalue is also at most n κ(P )2 ‖Jn‖
2 . So the combined total is
‖(J + E)n − Jn‖ ≤ n κ(P )2 ‖Jn‖.
Finally,
‖(M + E)n −Mn‖ = ‖P ((J +D)n − Jn)P−1‖ ≤ κ(P )‖((J +D)n − Jn)‖
≤ n κ(P ) ‖Jn‖
≤ n κ(P ) ‖P−1MnP‖
≤ n ‖Mn‖ ‖(M + E)n −Mn‖
‖Mn‖ ≤ n .
If M is nilpotent, the above argument does not go through, because ρ(J) = 0. Instead, use Lemma 6 to bound the absolute error of each block by r
n p , so that the total absolute error is at most r n .

heading: B MAKING AUTOMATA ASD
text: In 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 B = A⊗ I + I ⊗B. (This is known as the Kronecker sum and is sometimes notated ⊕, but we
use that for direct product.) These operations extend naturally to weighted multiset automata and correspond roughly to union and concatenation, respectively:
λ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 ⊗ ρB
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 M2 has ASD transition matrices.
Proof. First consider the ⊕ operation. Let µ1(a) (for all a) be the transition matrices of M1. For any > 0, let E1(a) be the perturbations of the µ1(a) such that ‖E1(a)‖ ≤ /2 and the µ1(a) + E1(a) (for all a) are simultaneously diagonalizable. Similarly for M2. Then the matrices (µ1(a) + E1(a)) ⊕ (µ2(a) + E2(a)) (for all a) are simultaneously diagonalizable, and
‖(µ1(a) + E1(a))⊕ (µ2(a) + E2(a))− µ1(a)⊕ µ2(a)‖ = ‖E1(a)⊕ E2(a)‖ ≤ ‖E1(a)‖+ ‖E2(a)‖ = .
Next, we consider the operation. Let d1 and d2 be the number of states in M1 and M2, respectively. This time, we choose ‖E1(a)‖ ≤ /(2d2) and ‖E2(a)‖ ≤ /(2d1). Then the matrices (µ1(a) + E1(a)) (µ2(a) + E2(a)) (for all a) are simultaneously diagonalizable, and
(µ1(a) + E1(a)) (µ2(a) + E2(a)) = (µ1(a) + E1(a))⊗ I + I ⊗ (µ2(a) + E2(a)) = µ1(a)⊗ I + E1(a)⊗ I + I ⊗ µ2(a) + I ⊗ E2(a) = (µ1(a) µ2(a)) + (E1(a) E2(a))
‖(µ1(a) + E1(a)) (µ2(a) + E2(a))− µ1(a) µ2(a)‖ = ‖E1(a) E2(a)‖ = ‖E1(a)⊗ I + I ⊗ E2(a)‖ ≤ ‖E1(a)⊗ I‖+ ‖I ⊗ E2(a)‖ ≤ ‖E1(a)‖d2 + d1‖E2(a)‖ ≤ .
Proposition 8. IfM 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(d2|Σ|+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 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 a1, . . . , am be the symbols of Σ. For all a ∈ Σ, q, r ∈ Q, define Mq,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 λq0Mq0,a1,q1 · · · Mqm−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 Mq,a,r has no more than d states, M ′ has at most d2|Σ|+1 states.

Review summaries:
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.

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.