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 work presents an encoding approach for unordered set input to neural networks. The authors base their approach on weighted finite automata, where in order to absorb unordered sets, they enforce multiplicative commutativity on transition matrices by approximating them as complex diagonal matrices. The authors furthermore provide mathematical references and results to derive bounds for their approximation. They show that positional encoding in Transformer network can be seen as a special case of their multiset encoding scheme, which also generalizes DeepSets encoding from real to complex numbers. The paper is well-written and easy to follow. The work tries to unify positional encoding in Transformers and Deepsets by establishing a different view to multiset encoding. My major concern however is that the authors do not provide any reasoning as to why do we need the weighted automata machinery behind their approach? Effectively what they do can simply be seen as embedding of inherently periodic multiset elements using periodic functions, which are parameterized by non-linear transformations of data. Such encoding schemes have long been used in signal processing. I might have missed something, but in my opinion the theoretical contribution of the work is rather tangential to the empirical analysis and results presented in the paper.