Seq2Tens: An Efficient Representation of Sequences by Low-Rank Tensor Projections
Authors: Csaba Toth
Patric Bonnier
Harald Oberhauser
Venue: ICLR 2021 Poster (2021)
Keywords: time series
sequential data
representation learning
low-rank tensors
classification
generative modelling

Abstract: Sequential data such as time series, video, or text can be challenging to analyse as the ordered structure gives rise to complex dependencies. At the heart of this is non-commutativity, in the sense that reordering the elements of a sequence can completely change its meaning. We use a classical mathematical object -- the free algebra -- to capture this non-commutativity. To address the innate computational complexity of this algebra, we use compositions of low-rank tensor projections. This yields modular and scalable building blocks that give state-of-the-art performance on standard benchmarks such as multivariate time series classification, mortality prediction and generative models for video.

Published as a conference paper at ICLR 2021
SEQ2TENS: AN EFFICIENT REPRESENTATION OF SE- QUENCES BY LOW-RANK TENSOR PROJECTIONS
Csaba Toth"
Patric Bonnier*
Harald Oberhauser*
"Matheattcaa Institute, University of Oxford (toth, bonnier, oberhauser (aaataerrr@mmmasss @maths
ox. wc.ac...... uk
ABSTRACT
Sequential data such as time series, video, or text can be challenging to analyse as the ordered structure gives rise to complex dependencies. At the heart of this is non-commutativity. in the sense that reordering the elements of sequence can completely change its meaning. We use classical mathematical object the free algebra to capture this conmutammtaaiiitty To address the innate computational complexity of this algebra, we use compositions of low-rank tensor projections. This yields modular and scalable building blocks that give state-of-the-art per- formance on standard benchmarks such as multivariate time series classification, mortality prediction and generative models for video. Code and benchmarks are available at /otpddydyyyyyyiilloooo//////oooo
INTRODUCTION
A central task of learning is find representations of the underlying data that efficiently and faith- fully capture their structure. In the case of sequential data, one data point consists of sequence of objects. This is rich and non-homogencous class of data and includes classical uni- or multi multi-variate time series (sequences of scalars vectors), video (sequences of images), and text (sequences of letters). Particular challenges of sequential data are that each sequence entry can itself be highly structured object and that data sets typically include sequences of different length which makes naive vectorization troublesome.
Contribution. Our main result is a generic method that takes a static feature map for class of objects (e.g. a feature map for vectors, images, or letters) as input and turns this into feature map for sequences of arbitrary length of such objects (c.g. feature map for time series, video, text). We call this feature map for sequences Seq2Tens for reasons that will become clear; among its attractive properties are that it (i) provides structured, parsimonious description of sequences; generalizing classical methods for strings, (ii) comes with theoretical guarantees such as universality, (iii) can be turned into modular and flexible neural network (NN) layers for sequence data. The key ingredient to our approach is to embed the feature space of the static feature map into a larger linear space that forms an algebra (a vector space equipped with multiplication). The product in this algebra is then used to "stitch together" the static features of the individual sequence entries in a structured way. The construction that allows to do all this is classical in mathematics, and known as the free algebra (over the static feature space).
formalizes the main ideas of Seq2 and introduces the free algebra T(V) over space V as well as the associated product, the so-called convolution tensor product. Section 3 shows how low rank (LR) constructions combined with sequence-to-sequenee transforms allows one to efficiently use this rich algebraic structure. Section 4 applies the results of Sections 2 and
Outline. Section 2
3 to build modular and scalable NN layers for sequential data. Section demonstrates the flexibil- ity and modularity of this approach both discriminative and generative benchmarks. Section makes connections with previous work and summarizes this article. In the appendices we provide mathematical background, extensions, and detailed proofs for theoretical results.

---

Published as a conference paper at ICLR 2021
2 CAPTURING ORDER BY NON-COMMUTNTIVE MULTIPLICATION
We denote the set of sequences of elements in a set X' by
Seq(Z)= = {x = (xx))i=....... X; E L2
where 2 is some arbitrary length. Even if X' itself linear space, c.g. R. Seq( is never a linear space since there is no natural addition of two sequences of different length.
Seq2Tens in a nutshell. Given any vector space V we may construct the so-called free algebra T(V) over V. We describe the space T(V) in detail below, but as for now the only thing that is important is that T(V) is also a vector space that includes V, and that carries a non-commutative product, which is, in precise sense, "the most general product" on V.
The main idea of Seq2Tens that any "static feature map" for elements in
Φ: V
can be used to construct algebraic structure of T(V): the non-commutative product on T(V) makes it possible to "stitch to- gether" the individual features o(xi), (())).,,,,,)))) E V c C(V) of the sequence in the larger space T(V) by multiplication in T(V). With this we may define the feature map 4xx) for sequences (x)....,LL) xL) ) (eq as follows
feature map + Seq(X) T(V) for sequences in X' by using the
(i) lift the map X V to map 9 X' + T(V),
(ii) map Seq(A)) X) + (e)(T(V)) by (x1...., xL) + (p(x))....;,$ (((L)),
(iii) map Seq(T(()) - T(V) by multiplication (((x)))...,x(xx))) + x(xx) ... pxxn).
In more concise form, we define
(eq(X) T(V),
+(x) II p(x,)
where II denotes multiplication T(V). We refer to the resulting map as the Seq2Tens map, which stands short for Sequences-2-Tensors Why is this construction good idea? First note, that step (i)is always possible since C T(V) and we discuss the simplest such lift before Theorem 2.1
well as other choices in Appendix B Further, if Φ. respectively y2, provides faithful represen-
tation of objects in X, then there is no loss of information in step (ii) Finally, since step (in) uses
"the most general product" to multiply sp( (x(x))) one expects that (xx) T(V) faithfully
represents the sequence x as an element of T(V).
Indeed in Theorem 2.1 below show map Φ X' + V contains enough non-linearities so that non-linear functions from X' to R can be approximated
stronger statement, namely that if the static feature
linear functions of the static feature map o, then the above construction extends this property to functions of sequences. Put differently, if ó is universal feature map for X. then & a universal feature map for (eq(X); that is, any non-linear function fxx of sequence x can be approximated as a linear functional of (xx), f(x) z (f. ((x)). We also emphasize that the domain of + the space (eq( of sequences of arbitrary (finite) length. The remainder of this Section gives more details about steps
(iii) for the construction of t.
The free algebra T(V) over a vector space V. Let V be a vector space. We denote by T(V) the set of sequences of tensors indexed by their degree m,
T(V) = ft = (tm)m2ol tm E V@mm
(3)
where by convention 8 IR For example, if _d and (tm (tm)m20 some element of T(R"), then its degree m 1 component d-dimensional vector t,, its degree m component is a d x d matrix tg, and its degree m 3 component is a degree 3 tensor tz. By defining addition and scalar multiplication
= (sm tm m c.
(4)
2

---

Published as a conference paper at ICLR 2021
the set T(V) becomes linear space. By identifying E V as the element (0, ........0) E T(V) we see that V is a linear subspace of T(V). Moreover, while V is only a linear space, T(V) carries product that turns T(V) into an algebra. This product is the so-called tensor convolution product, and is defined for s, t E T(V) as
m
S Σ s fm bm-i) m20 (1, + 11,82 + 81 1t t2..... T(V)
(5)
where @ denotes the usual outer tensor product; e.g. for vectors = (u:). (v.) E R' the outer tensor product u @ t is the d matrix (4.v)).j=I....d We emphasize that like the outer tensor product 69, the tensor convolution product is non-commutative, i.e. s.t t. In mathematically precise sense, T(V) the most general algebra that contains V; a "free construction", Since T(V) is realized series of tensors of increasing degree, the free algebra T(V) is also known the tensor algebra in the literature. Appendix [ contains background on tensors and further examples.
Lifting static feature maps. Step in the construction of O requires turning given feature map Φ X' + V into a map yp : X' + T(1 Throughout the rest of this article we use the lift
(xx) (1,6(x), T(V).
(6)
We discuss other choices in Appendix B but attractive properties of the lift 6 are that (a) the evalu-
ation of & against low rank tensors becomes simple recursive formula (Proposition 3.3 (b) it is
generalization of sequence sub-pattern matching as used string kernels (Appendix B.3 (c) despite its simplicity it performs exceedingly well in practice (Section
Extending to sequences of arbitrary length. Steps i and i1 in the construction specify how
the map Φ X' - T(V) behaves on sequences of length-1, that is, single observations. Step (iii)
amounts to the requirement that for any two sequences x = (xI,..... Xx),y = (y1,.... yL) E Seq(V), their concatenation defined as z (XI,.... ..... XK: k M1...., yE) Seq(V) can be understood in the feature space as (non-commutative) multiplication of their corresponding features
( = (xx) ((y).
In other words, we inductively extend the lift o to sequences of arbitrary length by starting from sequences consisting of single observation, which is given in equation Repeatedly applying the definition of the tensor convolution product equation lladds to the following explicit formula
2m (x)
Σ
Xi 8 ... Xim E vv 4(x) = =xmm(x))mm
(8)
LL
where x (x),..., xL) Seq(V) and the summation over non-contiguous subsequences of x.
generalized pattern matching. Our derivation of the feature map Φ(x) (1, (x),, (2(x.....) E T(V) was guided by general algebraic principles, but equation 8 pro- vides intuitive interpretation. It shows that for each 2 1, the entry (x. &' constructs a summary of a long sequence x = (xi,..., x1) E Seq(V) (V) based on subsequences (,.,,..,, of x of length-m. It does this by taking the usual outer tensor product x;, ② & x... E Vmam and summing over all possible subsequences. This is completely analogous to how string kernels provide structured description of text by looking at non-contiguous substrings of length-m (indeed, Ap- pendix B33 makes this rigorous). However, the main difference is that the above construction works for arbitrary sequences and not just sequences of discrete letters. Readers with less mathematical background might simply take this as motivation and regard equation 8 as definition. However, the algebraic background allows prove that Φ universal, see Theorem below.
Some intuition:
Universality. A function Φ X V is said to be universal for X' if all continuous functions on X' can be approximated as linear functions on the image of ø. One of the most powerful features of neural nets is their universality (Horiik 1991). A very attractive property of & is that it preserves universality: o : X + is universal for X. then Seq(X) - (VV) is universal for (e)( To make this precise, note that /mm is linear space and therefore any (Co, .1,...; LM, O, .....)
3

---

Published as a conference paper at ICLR 2021
T(V) consisting of M tensors fm V yields linear functional on T(V); e.g. if V IR and we identify km in coordinates as Lm = (finrrofh ( mi El then
tt,
Σ M1=
(Cms tm)
(9)
m=D 11 1m (I....dd)
Thus linear functionals of the feature map Φ; are real-valued functions of sequences. Theorem 2.1 below shows that any continuous function Seq(A)) + R can by arbitrary well approximated by a E T(V), f(x) 2 (x)).
Theorem 2.1. Let Φ X + V be universal map with lift that satisfies some mild constraints, then the following map is universal:
② : (eqe(()) T(V), x ((x).
(10)
A detailed proof and the precise statement of Theorem 2.1 is given in Appendix B
3 APPROXIMATION BY LOW-RANK LINEAR FUNCTIONALS
The combinatorial explosion of tensor coordinates and what to do about it. The universal- ity of 4 suggests the following approach to represent function f Seq(X)) R of sequences: First compute (x) and then optimize over (and possibly also the hyperparameters of () such that
fx) = (e, ((x)) .M (f.. pm (x)). Unfortunately, tensors suffer from combinatorial explo- sion complexity in the sense that even just storing 2 (x) E V C T(V) requires O (V )*)
real numbers. Below we resolve this computational bottleneck
follows: in Proposition 3.3
show that for a special class of low-rank elements & e T(V). the functional x + (E, & (x)) can be efficiently computed in both time and memory. This is somewhat analogous to kernel trick since it shows that (e, (x)) can be cheaply computed without explicitly computing the feature map (xx). However, Theorem 2. guarantees universality under
restriction on f, thus restriction to rank-1 functionals limits the class of functions f(x) that can be approximated. Nevertheless, by iterating these "low-rank functional" constructions in the form of sequence-to-sequence transformations this can be ameliorated. We give the details below but to gain intuition, we invite the reader to think of this iteration analogous stacking layers in a neural network: each layer is relatively sim- ple non-linearitg (e.g. sigmoid composed with an affine function) but by composing such layers, complicated functions can efficiently approximated.
Rank-1 functionals are computationally cheap. Degree 2 tensors are matrices and low- rank (LR) approximations of matrices are widely used in practice (Udell & Townsend (2019) to address the quadratic complexity. The definition below generalizes the rank of matrices (tensors of degree m = 2) to tensors of any degree m..
Definition 3.1. The rank (also called CP rank (Carroll & Chang 1970 of a degree-m tensor tm 700m is the smallest number such that one may write
Σ v s0 ... ......0 vV", V!.... EV.. 1=0
(11)
We say that t (tm m220 E T(V) has rank 1 (and degree-M) if each tm V0m is rank-1 tensor and t; = for > M.
Remark 3.2. For (xi,..., xx) E Seq(V), the rank I' E N of 4 (x) satisfies Tm S (h), while the rank and degree r, d E N of (xx) satisfy r S (k) for K = L and d S L.
A direct calculation shows that if l is of rank-1, then (e, ((x)) can be computed very efficiently by inner product evaluations in V. Proposition 3.3. Lei l = (Em )220 E T(V) be of rank-1 and degree-M. If cb is lifted to sp in equation then
M
m
(e, (c.)(x)) = Σ Σ
II (vE ((xx))
(12)
m=0 Si. Sm
ST.
where 8m vIT
0 t Vom, v V and m 0, .,.... M.
4

---

Published as a conference paper at ICLR 2021
Note that the inner sum is taken over all non-contiguous subsequences of x of length-m, analogously to m-mers of strings and we make this connection precise in Appendix [B.3] the proof Proposition 3.3 is given in Appendix [B..I] While equation [2 looks expensive, by casting it into a recursive formulation over time, it can be computed in O (M d. time and O(M2.
memory, where
d is the inner product evaluation time V, while is the memory footprint of a V. This can further be reduced to O(M L. d) time and O(M (L+c) c)) memory by an efficient parametrization of the rank-1 element T(V). We give further details in Appendices D.2
D.3
D.4
Low-rank Seq2Tens maps. The composition of a linear map L T(V) + RV with d can be computed cheaply in parallel using equation 12 when specified through collection of N e N rank-1 elements el eN E EV() such that
( XL. == L D(xI,...,, = (1e), D(I.. ......,,))). xt)) RRY.
(13)
We call the resulting map 63 (eq( + TR.. Low-rank Seq2Ten enns map of width-N and order-M, where M E N is the maximal degree of .!...., such that E. = 0 for i > M. The LS2T map is parametrized by (1) the component vectors v j.m E V of the rank-1 elements C = v! C.. 8....vjj.m (2) by any parameters that the static feature map Φg : X + V may depend on. jointly denote these parameters by 0 (0, ( ...... ). In addition, by the subsequent composition of & with a linear functional IR R. we get the following function subspace as hypothesis class for the LS2T
We
N age ( xt)) (xx,...,,x)))ll /=1
#= = (
E ç H = (1e, (x1, xL)
(14)
Hence, we acquire an intuitive explanation of the (hyper)parameters: the width of the LS2T, N e N specifies the maximal rank of the low-rank linear functionals of Φ that the LS2T can represent, while the span of the rank-1 elements, span(e' ...., (N)) determine an N-dimensional subspace of the dual space of T(V) consisting of at most rank-N functionals.
Recall now that without rank restrictions on the linear functionals of Seq2Tens features, Theo-
rem 2.1 would guarantee that any real-valued function / Seq(X) - I could be approximated by [x] Ri (f, ((x1,....... x))). As pointed out before, the restriction of the hypothesis class low- rank linear functionals of 4 (x11..... , xt) would limit the class of functions of sequences that can be approximated. To ameliorate this, we use LS2T transforms in a touuuncc-t--squencee fashion that allows us stack such low-rank functionals, significantly recovering expressiveness.
transforms. We can use LS2T to build sequence-te ceaeeeett--qquueuu sequence transforma- tions in the following way: fix the static map de X V parametrized by 0 and rank-1 elements such that 0 (0,e1 e ,..., ) and apply the resulting LS2T map T over expanding windows of x:
Sequence-to-sequee
Seq(X)) + (eq(R.), x (δg(x1), &x(x1, x ".....,,,(xx (x(x)....,, X1.)..
(15)
Note that the cost of computing the expanding window sequence-to-sequeeee transform in equa- tion 15 is more expensive than computing 6x(x1..... ......))).))........ itself due to the recursive nature of
our algorithms, for further details see Appendices D.2 D.3 D.4
Deep sequence-to-sequenee transforms. Inspired by the empirical successes of deep RNNs (Graves et al., 2013b Sutskever et al. 20144), we iterate the transformation[15]
Seq(X)) + () + ( (eq
(16)
Each of these mappings SRq N.) - Soq(R Mc+1) parametrized by the parameters 0, of a static feature map Φæ; and linear map L; specified by N; rank-1 elements of T(V); these parameters are
collectively denoted by 0, (0,, .!...... ..... E.......,,,.... Evaluating the final sequence in (e)(IRNa) the last observation-time i L,, we get the deep LS2T map with depth-
$ Seq(2)) R.P
(17)
Making precise how the stacking of such low-rank sequence to to-sequence transformations approx- imates general functions requires more tools from algebra, and provide a rigorous quantitative statement in Appendix C Here, we just appeal to the analogy made with adding depth in neural networks mentioned earlier and empirically validate this in our experiments in Section
5

---

Published as a conference paper at ICLR 2021
4 BUILDING NEURAL NETWORKS WITH LS2T LAYERS
The Seq2Tens map built from static feature map & is universal if universal, Theorem NNs form flexible class of universal feature maps with strong empirical success for data in X RR, and thus make a natural choice for Φ. Combined with standard deep learning constructions, the framework of Sections 2 and can build modular and expressive layers for sequence learning.
Neural LS2T layers. The simplest choice among many is to use as static feature map Φ X
R + R feedforward network with depth-P, é 6p pp.....0 Φ1 where (x o (W by) for W E Rxxd bj E R We can then lift this to map sp R2 + T(R*) prescribed in equation 6
Hence, the resulting LS2T layer x + (x), xi....;. i....= is sequeeneeto--sequenee transform Seq(Rd) + ()) that is parametrized by 0 = (W1, bi..... W., bp, ,....., (.
Bidirectional LS2T layers. The transformation in equation 15 is completely causal in the sense that each step of the output sequence depends only on past information. For generative models, it can behove us to make the output depend on both past and future information, see Graves et al. (2013a); Baldi et al. [1999); Li & Mandt (2018). Similarly to bidirectional RNNs and LSTMs (Schuster & Paliwal 1997 Graves & Schmidhuber (005)), we may achieve this by defining bidirectional layer,
bb [(6 .2)) (x) (Rq( + Seq(R-**N') X (.) (xi,.... x,), 26 (x.,..., (x),...xx)) (18)
The sequential nature is kept intact by making the distinction between what classifies as past (the first N coordinates) and future (the last N' coordinates) information. This amounts having form of precognition in the model, and has been applied in c.g. dynamics generation (Li & Mandt 2018). machine translation (Sundermeyer et al. 2014), and speech processing (Graves et al. 2013a
Convolutions and LS2T. We motivate to replace the time-distributed feedforward layers proposed in the paragraph above by temporal convolutions (CNN) instead. Although theory only requires the preprocessing layer of the LS2T to be static feature map, we find that it is beneficial to capture some of the sequential information in the preprocessing layer as well, e.g. using CNNs or RNNs. From a mathematical point of view, CNNs are a straightforward extension since they can be interpreted as ditt-distributed feedforward layers applied to the input sequence augmented with a E number of its lags for CNN kernel size p (see Appendix D.I for further discussion).
In the following, we precede our deep LS2T blocks by one or more CNN layers. Intuitively, CNNs and LS2Tss are similar in that both transformations operate subsequences of their input sequence. The main difference between the two lies in that CNNs operate on contiguous subsequences, and therefore, capture local, short-range nonlinear interactions between timesteps; while LS2Ts (equa- tion 72 use all non-contiguous subsequences, and hence, learn global, long-range interactions in time. This observation motivates that the inductive biases of the types of layers (local/global lime-interactions) are highly complementary in nature, and we suggest that the improvement in the experiments on the models containing vanilla CNN blocks are due to this complementarity
EXPERIMENTS
We demonstrate the modularity and flexibility of the above LS2T and its variants by applying it to (i) multivariate time series classification, (ii) mortality prediction in healthcare, (iii) generative mod- elling of sequential data. In all cases, we take a strong baseline model (FCN and GP-VAE, as detailed below) and upgrade it with LS2T layers. As Thm. 2. requires the Seq2Tens layers to be preceded by at least static feature map, we expect these layers to perform best as an add-on on top of other models, which however can be quite simple, such as a CNN. The additional computation time is negligible (in fact, for FCN it allows to reduce the number of parameters significantly, while retain- ing performance), but can yield substantial improvements. This is remarkable, since the original models already state-of-the on well-established (frequentist and Bayesian) benchmarks.
5.1 MULTIVARIATE TIME SERIES CLASSIFICATION
As the first task, we consider multivariate time series classification (TSC) on an archive of bench- mark datasets collected by Baydogan (2015). Numerous previous publications report results this

---

Published as a conference paper at ICLR 2021
Table 1: Posterior probabilities given by Bayesian signed-rank test comparison of the proposed methods against the baselines. {>}, { {<), {-) refer to the respective events that the row method is better, the column method is better, or that they are equivalent.
1.52T24
FCN64-L.2273 LS2T2
FCN 1.52T
MODEL
p(>)
p(=)
p(<)
p(>)
p(=)
p(<))
p[>)
p(=)
p(<)
SMTS (BAYDOGAN & RUNGER 2015A
0.180
0.000
0.820
0.010
0.000
0.990
0.008
0.000
0.992
LPS (BAYDOGAN& RUNCER 20130
0.191
0.002
0.807
0.012
0.001
0.987
0.006
0.001
0.993
MYAKF (TUNCEL & BAVDOGGNN 2018
0.011
0.140
0.849
0.000
0.126
0.874
0.000
0.088
0.912
DTW SSAOE & CHIBA, 1978
0.033
0.000
0.967
0.001
0.000
0.999
0.000
0.000
1.000
ARKERNEL (CUTURI & DOUCtr
2011
0.100
0.097
0.803
0.000
0.021
0.979
0.000
0.015
0.985
GRSF (KARLSSON ET AL.
2016
0.481
0.011
0.508
0.028
0.013
0.960
0.022
0.013
0.965
& LESER 2017
0.405
0.128
0.467
0.001
0.074
0.925
0.001
0.077
0.922
MLSTMECN (KARIM
0.916
0.043
0.041
0.123
0.071
0.807
0.055
0.110
0.835
FCN128 (WANG AL.
2017
0.998
0.002
0.000
0.363
0.186
0.451
0.169
0.011
0.820
RESNET WANGET AL. 2017
0.998
0.002
0.001
0.056
0.240
0.704
0.016
0.048
0.935
LS2T
0.000
0.001
0.999
0.000
0.001
0,999
FCNGr
0.999
0.001
0.000
0.020
0.387
0.593
archive, which makes it possible to compare against several well-performing competitor methods from the TSC community. These baselines are detailed in Appendix [E_]] This archive was also considered in a recent popular survey paper on DL for TSC (Ismail Fawaz et al. 2019), from where we borrow the two best performing models as DL baselines: FCN and ResNet. The FCN is a fully convolutional network which stacks 3 convolutional layers of kernel sizes (8,5,3) 5) and filters (128, 256, 128) followed by a global average pooling (GAP) layer, hence employing global param- eter sharing. We refer to this model as FCN12s. The ResNet is a residual network stacking FCN blocks of various widths with skip-connections in between (He et al., 2016) and final GAP layer.
The FCN is an interesting model to upgrade with LS2T layers, since the LS2T also employs pa- rameter sharing across the sequence length, and as noted previously, convolutions are only able to learn local interactions in time, that particular makes them ill-suited to picking up on long- range autocorrelations, which is exactly where the LS2T can provide improvements. As our models, we consider three simple architectures: (i) LS2T stacks 3 LS2T layers of order-2 and width-64; (ii) FCN&1-LS2T5, 64 precedes the LS2T block by an FC block; a downsized version of FCN12s; (iii) FCN uses the full FCN128 and follows it by a LS2T block as before. Also, both FCN-LS2T models employ skip skip-connections from the input to the LS2T block and from the FCN to the classification layer, allowing for the LS2T to directly see the input, and for the FCN to di- rectly affect the final prediction. These hyperparameters were only subject to hand-tuning on a subset of the datasets, and the values we considered were H,N N E (32, 64, 128), M E {2. 4] and D E {1, 2, 3). where H, N E N is the FCN and LS2T width, resp.. while M E N is the LS2T order and D E N is the LS2T depth. We also employ techniques such as time-embeddings (Liu ctt al. 2018a), sequence differencing and batch normalization, see Appendix D.I Appendix E. for further details on the experiment and Figure 2 in thereof for visualization of the architectures.
Results. We trained the models, FCN ResNet, LS2T 61. FCN 61 FCN 64 on each of the 16 datasets 5 times while results for other methods were borrowed from the cited pub- lications. In Appendix [.. Figure 3 depicts the box-plot of distributions of accuracies and a CD diagram using the Nemenyi test (Nemenyi 1963), while Table 7 shows the full list of results. Since mean-ranks based tests raise some paradoxical issues (Benavoli et al., 2016), it is customary to conduct pairwise comparisons using frequentist (Demšar (2006) or Bayesian (Benavoli et al.) 2017) hypothesis tests. We adopted the Bayesian signed-rank test from Benavoli et al. (201 4)), the poste- rior probabilities of which are displayed in Table [
while the Bayesian posteriors are visualized on Figure i in App. E The results of the signed-rank test can be summarized as follows: (1) LS2T?, already outperforms some classic TS classifiers with high probability (p 2 0.8), but it is not compet- itive with other DL classifiers. This observation is not surprising since even theory requires least static feature map precede the LS2T. (2) FCN outperforms almost all models with high probability (p 2 0.8), except for ResNet (which is stil outperformed by 2 0.7), PCN12s and 1CN12s-LS2T' 61- When compared with FCN the test is unable to decide between the two, which upon inspection of the individual results in Table 7 can be explained by that on some datasets the benefit of the added LS2T block is high enough that it outweighs the loss of flexibility incurred by reducing the width of the FCN- arguably these are the datasets where long-range autocorrelations
7

---

Published as a conference paper at ICLR 2021
present in the input time series, and picking up on these improve the performance however, on few datasets the contrary is true. (3) Lastly, FCN12s-L.S2Ter oulperforms all baseline methods with high probability (p 2 0.8), and hence successfully improves on the FCN128 via its added abil- ity to learn long-range time-interactions. We remark that FCNox-LS2Tes has fewer parameters than FCN12s by more than 50%, hence we managed to compress the FCN to a fraction of its original size, while average still slightly improving its performance, nontrivial feat by its own accord.
5.2 MORTALITY PREDICTION
We consider the PHYSIONET2012 challenge dataset (Goldberger et al. 2000) for mortality predic- tion, which is a case of medical TSC as the task is to predict in-hospital mortality of patients after their admission to the ICU. This is a difficult ML task due missingness in the data, low signal- to-noise ratio (SNR), and imbalanced class distributions with prevalence ratio of around 14%. We extend the experiments conducted in Horn et al. (202)), which we also use as very strong baselines. Under the same experimental setting, we train two models: FCN-LS2T as ours and the FCN as another baseline. For both models, we conduct a random search for all hyperparameters with 20 samples from pre-specified search space, and the setting with best validation performance is used for model evaluation on the test set over independent model trains, exactly the same way as it was done in Horn et al. (2020). We preprocess the data using the same method as in [he et al.] (2018) eq. (9)) and additionally handle static features by tiling them along the time axis and adding them extra coordinates. We additionally introduce in both models Spat i a 1 Dropout D layer after all CNN and LS2T layers with the same tunable dropout rate to mitigate the low SNR of the dataset.
Table 2: Comparison of FCN- and FCN on PHY- SIONET2012 with the results from Horn et al. (2020).
Results. Table 2 compares the perfor- mance of FCN-LS2T with that of FCN and the results from Horn et al. (2020) on
MODEL
ACCURACY
AUPRC
AUROC
3 metries: (1) ACCURACY, (2) area un- der the precision-recall curve (AUPRC),
FCN-LS2T
84.1 +11+11 1.6
53.9 0.5
85.6 0.5
FCN
80.7 1.7
52.8 1 1.3
85.6 1 0.2
(3) area under the ROC curve (AUROC). We can observe that FCN-LS2T takes on average first place according to both ACCURACY and AUPRC, ouperforming FCN and all SOTA methods, e.g. TRANS- FORMER (Vaswani al. (017)) GRU-D Che et al. (2018), SEFT (Hor et al.] 2020). and also being competitive in terms of AUROC. This very promising, and it suggests that LS2T layers might be particularly well-suited to complex and heterogenous datasets, such as medical time series, since the FCN-LS2T models significantly improved accuracy on ECG as well, another medical dataset the previous experiment.
GRU-D
2.9
58.7
86.3 0.3
GRU-SIMPLE
82.2 1::0000 0.2
42.2 0.6
80.8 1.1
IP-NETS
79.4 1.440...
51.0 0.8
86.0
PHASED-LSTM
7 5.2
38.7 1.5
79.0 1.0
TRANSPORMER
8
52.8
2.2
86.3 0.8
LATENT-ODE
76.0 0.1
50.7
4 1.7
85.7 0.6
SEFT-ATTE
75.3 1 3.5
52.4
1
1.1
85.1 1 0.4
5.3 GENERATING SEQUENTIAL DATA
Finally, we demonstrate on sequential data imputation for time series and video that LS2Tss do not only provide good representations of sequences in discriminative, but also generative models.
The GP-VAE model. In this experiment, we take as base model the recent GP-VAE (Fortuin) et al. 2020). that provides state-of-the-art results for probabilistic sequential data imputation. The GP-VAE is essentially based on the HI-VAE (Nazabal et al. 2018) for handling missing data in variational autoencoders (VAEs) (Kingma & Welling, 2013) adapted to the handling of time series data by the use of Gaussian process (GP) prior (Williams & Rasmussen 2006) across time in the latent sequence space to capture temporal dynamics. Since the VA-V is highly advances model, its in-depth description deferred to Appendix [ We extend the experiments conducted in Fortuin et al. (2020), and we make one simple change to the GP-VAE architecture without changing any other hyperparameters or aspects: we introduce a single bidirectional LS2T layer (B-LS2T) into the encoder network that is used in the amortized representation of the means and covariances of the variational posterior. The B-LS2T layer is preceded by a time-embedding and differencing block, and succeeded by channel flattening and layer normalization idea behind this experiment is to see if we can improve the performance of a highly complicated model that is composed of many interacting submodels, by the naive introduction of L.STT layers.
depicted in Figure 5 The
8

---

Published as a conference paper at ICLR 2021
Table 3: Performance comparison of GP-VAE (B-LS2T) with the baseline methods
HMNIST
SPRITES
PHYSIONET
METHOD
NLL
MSE
AUROC
MSE
AUROC
MEAN IMPUTATION
0.168 0.000
0.938 1: 0.000
0.013 1 0.000
0.703 1: 0.000
FORWARD IMPUTATION
0.177 0.000
0,935 4: 0.000
0.028 + 0.000
0.710 +: 0.000
VAE
0.599 0.002
0.232 + 0.000
0.922 0.000
0.028 = 0.000
0.677 = 0.002
HI- HI-VAE VAE
0.372 0.008
0.134 + 0.003
0.962 = 0.001
0.007 = 0.000
0.686 + 0.010
GP-VAE
0.350 0.007
0.114 + 0.002
0.960 +: 0.002 0.002
0.002 + 0.000
0.730 +: 0.006
GP-VAE (B-LS2T)
0.251 0.008
0.092 0.003
0.962 +: 0.001
0.002 + 0.000
0.743 + 0.007
BRITS
0.742 1 0.008
Results. To make the comparison, we ceteris paribus re-ran all experiments the authors originally included in their paper (Fortuin et al. 2020), which are imputation of Healing MNIST, Sprites, and Physionet 2012. The results are in Table which report the same metrics as used in Fortuin al.] (2020), i.c. negative log- likelihood (NLL, lower is better), mean squared error (MSE, lower is better) on test sets, and downstream classification performance of a linear classifier (AUROC, higher is better). For all other models beside our GP-VAE (B-LS2TT), the results were borrowed from Fortuin et al. (2020). We observe that simply adding the B-LS2T layer improved the result in almost all cases, except for Sprites, where the GP-VAE already achieved a very low MSE score. Additionally, when comparing GP-VAE to BRITS on Physionet, the authors argue that although the BRITS achieves higher AUROC score, the VAEE should not be disregarded as it fits a generative model to the data that enjoys the usual Bayesian benefits of predicting distributions instead of point predictions. The results display that by simply adding our layer into the architecture, we managed to elevate the performance of GP-VAR the same level while retaining these same benefits. We believe the reason for the improvement is tighter amortization gap in the variational approximation (Cremer et al. 20188) achieved by increasing the expressiveness of the encoder by the LS2T allowing it to pick up on long-range interactions in time. We provide further discussion in Appendix E.3
6 RELATED WORK AND SUMMARY
Related Work. The literature on tensor models in ML is vast. Related to our approach we mention pars pars-pro-toto Tensor Networks (Cichocki et al. 2016), that use classical LR decompositions, such as CP (Carroll& & Chang 1970). Tucker [Tucker 1966), tensor trains (Oseledets) 2011) and tensor rings ZZho et al., 2019);; further, CNNs have been combined with L.R tensor techniques (Cohen et al. 2016; Kossaifi et al.] 2017) and extended to RNNs (Khrulkov et al.] 2019); Tensor Fusion Networks (Zadch et al. 2017) and its LR variants (Liu et al. 2018b] Liang et al. 2019 Hou et al.) 2019); censor-based gait recognition (Tao et al., 2007). Our main contribution to this literature is the use of the free algebra T(V) with its convolution product instead of V @m with the outer product @ that is used in the above papers. While counter-intuitive to work in larger space T(V), the additional algebra structure of (T(V).)) is the main reason for the nice properties of t (universality, making sequences of arbitrary length comparable, convergence in the continuous time limit; see Appendix B which we believe are in turn the main reason for the strong benchmark performance. Stacked LR sequence transforms allow to exploit this rich algebraic structure with little computa- tional overhead. Another related literature are path signatures in ML (Lyons) 2014; Chevyrev & Kormilitzin, 2016) Graham 2013 Bonnier et al.) 2019 Toth Oberhauser 2020). These arise as special case of Seq2Tens (Appendix B) and our main contribution to this literature is that Seq2Tens resolves a well-known computational bottleneck in this literature since never needs to compute and store a signature, instead it directly and efficiently learns the functional of the signature.
Summary. We used a classical non-commutative structure to construct a feature map for se- quences of arbitrary length. By stacking sequence transforms we turned this into scalable and mod- ular NN layers for sequence data. The main novelty is the use of the free algebra T(V) constructed from the static feature space V. While free algebras are classical in mathematics, their use in ML seems novel and underexplored. We would like to re-emphasize that (T(VV,,) is not a mysterious abstract space: if you know the outer tensor product @ then you can easily switch to the tensor convolution product. by taking sums of outer tensor products, as defined in equation 5] As our ex- periments show, the henefits of this algebraic structure are not just theoretical but can significantly elevate performance of already strong proon-performing models.

---

Published as a conference paper at ICLR 2021
REFERENCES
Pierre Baldi, Søren Brunak, Paolo Frasconi, Giovanni Soda, and Gianluca Pollastri. Exploiting the past and the future in protein secondary structure prediction. Bioinformatics, 15(11)9337-946 1999.
Robert Bamler and Stephan Mandt. Dynamic word embeddings. In Proceedings of the 34th Inter- national Conference on Machine Soanning-Volume 70, pp. 380-389. JMLR. org, 2017.
Mustafa Baydogan.
Multivariate time series classification datasets.
http://
mustafabaydogan com, 2015. [Accessed: 2020-06-11].
Mustafa Gokce Baydogan and George Runger. Learning a symbolic representation for multivariate
time series classification. Data Mining and Knowledge Discovery, 29(2):400-422, 2015a.
Mustafa Gokce Baydogan and George C. Runger. Time series representation and similarity based on local autopatterns. Data Mining and Knowledge Discovery, 30:476-509, 2015b.
Alessio Benavoli, Giorgio Corani, Francesca Mangili, Marco Zaffalon, and Fabrizio Ruggeri. A bayesian wilcoxon signed-rank test based on the dirichlet process. International conference on machine learning, pp. 1026-1034, 2014.
Alessio Benavoli, Giorgio Corani, and Francesca Mangili. Should really use post-hoc tests based on mean-ranks? The Journal of Machine Learning Research, 17(1):152-161, 1,,, 2016. ISSN 1532-4435.
Alessio Benavoli, Giorgio Corani, Janez Demšar, and Marco Zaffalon. Time for change: tutorial for comparing multiple classifiers through bayesian analysis. The Journal of Machine Learning Research, (8(1):2653- 2688, 2017.
David Blei and John D Lafferty. Dynamic topic models. In Proceedings of the 23rd international conference on Machine learning, pp. 113-120, 2006.
David M Blei, Alp Kucukelbir, and Jon D McAuliffe. Variational inference: review for statisti- cians. Journal of the American statistical Association, (12(518):859-877 2017.
P Bonnier, C Liu, and H Oberhauser. Adapted topologies and higher rank signatures. arXiv preprint arXiv:2005.08887, 2020.
Patric Bonnier, Patrick Kidger, Imanol Perez Arribas, Cristopher Salvi, and Terry Lyons. Deep signature transforms. 33rd Conference on Neural Information Processing Systems, NeurIPS, 2019.
Wei Cao, Dong Wang, Jian Li, Hao Zhou, Lei Li, and Yitan Li. Brits: Bidirectional recurrent imputation for time series. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Gareett (eds.), Advances in Neural Information Processing Systems 31, pp. 6775- 6785. Curran Associates, Inc., 2018.
J Douglas Carroll and Jih-Jie Chang. Analysis of individual differences in multidimensional scaling via an n-way generalization of "Eckart-young" decomposition. Psychometrika, 35(3):283-319, 1970.
Zhengping Che, Sanjay Purushotham, Kyunghyun Cho, David Sontag, and Yan Liu. Recurrent neural networks for multivariate time series with missing values. Scientific reports, 8(1):1-12, 2018.
K. Т. Chen. Iterated integrals and exponential homomorphisms, Proc. London Math. Soc, 502- 512, 1954.
K. T. Chen. Integration of paths, geometric invariants and generalized Ann. of Math. (2), 163-1788 1957.
formula.
K. T. Chen. Integration of paths a faithful representation of paths by non-commutative formal power series. Trans. Amer. Math. Soc. 89 (1958), 395-407, 1958.
10

---

Published as a conference paper at ICLR 2021
1. Chevyrev and A. Kormilitzin. A primer on the signature method in machine learning. arXiv preprint urXvv:1633.33788, 2016.
Andrzej Cichocki, Namgil Lee, Ivan Oseledets, Anh-Huy Phan, Qibin Zhao, and Danilo P Mandic. Tensor networks for dimensionality reduction and large-scale optimization: Part low-rank tensor decompositions. Foundations and Trends& in Machine Learning, 9(4-5):249-429 2016.
Nadav Cohen, Or Sharir, and Amnon Shashua. On the expressive power of deep learning: tensor analysis. In Conference on learning theory. Pp. 698-728, 2016.
Chris Cremer, Xuechen Li, and David Duvenaud. Inference suboptimality in variational autoen- coders. In Proceedings of the 35th International Conference on Machine Learning, pp. 1078- 1086, 2018.
Cristianini and J Shawe-Taylor. An Introduction to Support Vector Machines. Cambridge, 2000.
Marco Cuturi and Arnaud Doucet. Autoregressive Kernels For Time Series. arXiv e-prints, art. arXiv: 101.0673, Jan 2011.
Janez Demsar. Statistical comparisons of classifiers over multiple data sets. Journal of Machine learning research, 7(Jan): 1-30, 2006.
J Dichl, K Ebrahimi-Fard, and N Tapia. Time-warping invariants of multidimensional time series. arXiv preprint arXiv:1906.058// 05822,, 2019.
Garoe Dorta, Sara Vicente, Lourdes Agapito, Neill DF Campbell, and Ivor Simpson. Structured uncertainty prediction networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 5477-5485, 2018.
K. Ebrahimi-Faan and F. Patras. Cumulants, free cumulants and half-shuffles. Proceedings of the Royal Society, 2015.
Vincent Fortuin, Dmitry Baranchuk, Gunnar Rätsch, and Stephan Mandt. GP-VAF: Deep probabilis- tic time series imputation. In International Conference on Artificial Intelligence and Statistics, pp. 1651-1661 PMLR, 2020.
Samuel J. Gershman and Noah D. Goodman. Amortized inference in probabilistic reasoning. Cog- nitive Science, 36, 2014.
Giles. A generalization of the strict strict topology. Transactions of the American Mathematical Society, 1971.
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pp. 249-256, 2010.
AL Goldberger, LAN Amaral, Glass, JM Hausdorff, Ch Ivanov, Mark, Mietus, GB Moody, CK Peng. and HE Stanley. Components of new research resource for complex physiologic signals. PhysioBank, PhysioToolkit, and Physionet, 2000.
Benjamin Graham. Sparse arrays of signatures for online character recognition. arXiv preprint arXiv: 333...03711 2013.
Alex Graves and Jürgen Schmidhuber. Framewise phoneme classification with bidirectional Istm and other neural network architectures. Neural Networks, 18(5):602 610, 2005.
Alex Graves, Navdeep Jaitly, and Abdel-rahman Mohamed. Hybrid speech recognition with deep bidirectional Istm. In 2013 IEEE workshop on automatic speech recognition and understanding, pp. 273-278 IEEE, 2013a.
Alex Graves, Abdel-rahman Mohamed, and Geoffrey Hinton. Speech recognition with deep recur- rent neural networks. In 2013 IEEE international conference on acoustics, speech and signal processing, pp. 6645-6649. IEEF, 2013b.

---

Published as a conference paper at ICLR 2021
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
I. Higgins, Loie Matthey, A. Pal, C. Burgess, Xavier Glorot, M. Botvinick, S. Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. In ICLR, 2017.
Max Horn, Michael Moor, Christian Bock, Bastian Rieck, and Karsten Borgwardt. Set functions for time series. In ICML, 2020.
Kurt Horiik. Approximation capabilities of multilayer feedforward networks. Neural networks, (2):251-257, 1991.
Ming Hou, Jiajia Tang, Jianhai Zhang, Wanzeng Kong, and Qibin Zhao Deep multimodal multi- linear fusion with bigh-order polynomial pooling, In Advances in Neural Information Processing Systems, pp. 12145- 2019.
Hassan Ismail Fawaz, Germain Forestier, Jonathan Weber, Lhassane Idoumghar, and Pierre-Alain Muller. Deep learning for time series classification: review. Data Mining and Knowledge Discovery, 3374)9917-963, Jul 2019. ISSN 1573-756X.
Fazle Karim, Somshubra Majumdar, Houshang Darabi, and Samuel Harford. Multivariate Istm-fens for time series classification. Neural Networks, I 16:2277 - 245, 2019. ISSN 0893-6080.
Isak Karlsson, Panagiotis Papapetrou, and Henrik Boström. Generalized random shapelet forests. Data Min. Knowl. Discov., 3065):1053-1085 September 2016. ISSN 1384-5810.
Nitish Shirish Keskar and Richard Socher. Improving generalization performance by switching from adam to SGD. arXiv preprint arXiv: arXiv:1712.07622 2017.
Valentin Khrulkov, Oleksii Hrinchuk, and Ivan Oseledets. Generalized tensor models for recurrent neural networks. arXiv preprint arXiv:1901. 2019.
Diederik P. Kingma and Jimmy Ba.
Adam: A method for stochastic optimization. CoRR,
Abs/1442.66900, 2015.
Diederik Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint
urXiv:1312.611 14, 2013.
Franz Király and Harald Oberhauser. Kernels for sequentially ordered data. Journal of Machine Learning Research, 2019.
Jean Kossaifi, Zachary C Lipton, Aran Khanna, Tommaso Furlanello, and Anima Anandkumar. Tensor regression networks. arXiv preprint arXiv: 17t.:0700000000 2017.
Serge Lang. Algebra. Springer- Verlag New York, 2002.
Leslie and R Kuang. Fast string kernels using inexact matching for protein sequences. Journal of Machine Learning Research, 2004.
Yingzhen Li and Stephan Mandt. Disentangled sequential autoencoder, 2018.
Paul Pu Liang, Zhun Liu, Yao-Hung Hubert Tsai, Qibin Zhao Ruslan Salakhutdinov, and Louis- Philippe Morency. Learning representations from imperfect time series data via tensor rank reg- 2019.
ularization. arXiv preprint arXiv:
Rosanne Liu, Joel Lehman, Piero Molino, Felipe Petroski Such, Eric Frank, Alex Sergeev, and Jason Yosinski. An intriguing failing of convolutional neural networks and the coordcony solution. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, Red Hook, NY, USA. 2018a. Curran Associates Inc.
NIPS' 18, pp.
Zhun Liu, Ying Shen, Varun Bharadhwajj Lakshminarasimhan, Paul Pu Liang, Amir Zadeh, and Louis Philipp Morency. Efficient low-rank multimodal fusion with modality-speciffe factors. arXiv preprint arXiv: 1806000044 2018h.
12

---

Published as a conference paper at ICLR 2021
Terry Lyons. Rough paths, signatures and the modelling of functions streams. arXiv preprint arXiv:1405.4537, 2014.
Wesley J Maddox, Gregory Benton, and Andrew Gordon Wilson. Rethinking parameter counting in deep models: Effective dimensionality revisited. arXiv preprint N.KV::00030023399 2020.
Dmytro Mishkin and Jiri Matas. All you need good init. arXiv preprint 2015.
James Morrill, Adeline Fermanian, Patrick Kidger, and Tenry Lyons. A generalised signature method for time series. arXiv preprint arKiv:2006.0000 00873, 2020.
Alfredo Nazabal, Pablo M Olmos, Zoubin Ghahramani, and Isabel Valera. Handling incomplete heterogeneous data using vaes. arXiv preprint arXiv:7807.03655 2018.
Daniel Neil, Michael Pfeiffer, and Shih-Chii Liu. Phased Istm: Accelerating recurrent network training for long or event-based sequences. In D. Lee, M. Sugiyama, U. Luxburg. I. Guyon, and
R. Gareett (eds.), Advances in Neural Information Processing Systems, volume 29. Curran As- sociates, Inc., 2016. URL http:::pss/ppoceeddigee
Srcee33.....obc33333322222eeeee3 neurips......................... wwtps/s..ppppppppeeeee /aaperr/011/fiee. .pdf
P. Nemenyi. Distributiion-fre Multiple Comparisons. Princeton University, 1963. URL https:
7/books wwg.oogle..//boo... http://.......ooooooooooto.o...
?i
Ivan V Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):2295-
2317, 2011.
C Reutenauer. Free Lie Algebras. Clarendon press Oxford, 1993.
Yulia Rubanova, Ricky Q. Chen, and David K Duvenaud. Latent ordinary differential equations for iregullrly-sampled time series. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances ume 32. Curran Associates, Inc., 2019. URL https:::/p.tceeeeeeeeee
Neural Information Processing Systems, vol- newrips ca/ paper/2019/Eile// htt.///11ee226645555555 T0t.000000000aa00044000333-eeee
W. Rudin. Principles of Mathematical Analysis. Cambridge University Press, 1965.
H. Sakoe and S. Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions Acoustics, Speech, and Signal Processing, 26(1):43-49, 1978.
Tim Sauer, James A Yorke, and Martin Casdagli. Embedology. Journal of statistical Physics, 65 (44))579-616.1 1991.
Patrick Schäfer and Ulf Leser. Multivariate time series classification with weasel+muse. ArXiv, abs/1711.11343, 2017.
Mike Schuster and Kuldip K Paliwal. Bidirectional recurrent neural networks. IEEE transactions on Signal Processing, 45(1 262673-66,,, 1997.
Satya Narayan Shukla and Benjamin Marlin. imerpolation-predictin networks for irregularly sampled time series. arXiv preprint arXiv: 1909.07782, 2019.
Martin Sundermeyer, Tamer Alkhouli, Joem Wuebker, and Hermann Ney. Translation modeling with bidirectional recurrent neural networks. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 14-25, 2014.
Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence sequence learning with neural networks. In Z. Ghahramani, M. Welling. C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), Advances Neural Information Processing Systems 27, pp. 3122 Curran Associates, Inc., 2014. URL
ni nips. ccppaper/ 5346 wese--seueene-etee to- sequence Learninnnnnnn seaaninn-withh neural -oieraa-neetonn nwwworks pdf
Floris Takens. Detecting strange attractors in turbulence. In Dynamical systems and turbulence, Warwick 1980, pp. 366-381. Springer, 1981.
13

---

Published as a conference paper at ICLR 2021
Dacheng Tao, Xuelong Li, Xindong Wu, and Stephen J Maybank. General tensor discriminant anal- ysis and gabor features for gait recognition. IEEE transactions on pattern analysis and machine intelligence, 29(10):1700-1115 2007.
C Toth and H Oberhauser. Bayesian learning from sequential data using gaussian processes with signature covariances. /CML, 2020.
Ledyard R Tucker. Some mathematical notes on three-mode factor analysis. Psychometrika, 31(3): 279-311, 1966.
Kerem Sinan Tuncel and Mustafa Gokce Baydogan. Autoregressive forests for multivariate time series modeling. Pattern Recognition, 73:202- 215, 2018.
Madeleine Udell and Alex Townsend. Why big data matrices approximately low rank? SIAM Journal on Mathematics of Data Science, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is you need. Advances in neural information processing systems, pp. 5998-6008, 2017.
Z. Wang, W. Yan, and T. Oates. Time series classification from scratch with deep neural networks: A strong baseline. 2017 International Joint Conference on Neural Networks (IJCNN), pp- 1578-1585, 2017.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for machine learning, volume 2. MIT press Cambridge, MA, 2006.
Amir Zadeh, Minghai Chen, Soujanya Poria, Erik Cambria, and Louis-Philippe Morency. Tensor fusion network for multimodal sentiment analysis. arXiv preprint arXiv:1707.072555 2017.
Cheng Zhang, Judith Bütepage, Hedvig Kjellström, and Stephan Mandt. Advances in variational inference. IEEE transactions pattern analysis and machine intelligence, 41(8):2008-200 -026,, 2018.
Qibin Zhao, Masashi Sugiyama, Longhao Yuan, and Andrzej Cichocki. Learning efficient tensor representations with ring- structuudd networks. In ICASSP 2019-2019 IEEE International Confer- ence on Acoustics, Speech and Signal Processing (ICASSP), pp. 8608-8612. IEEE, 2019.
14


Reviews:
[{"review_id": "N3su8ujqA09", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "The paper presents a method to map static feature space to a space containing sequences of different lengths. The idea is worth of  interest and the appendix gives large amount of information on both theoretical and experimental sides of the work.\n\nThe experiments are the main drawback for me of the paper. Indeed, the experiments for sequence discrimination are not convincing enough due to the lack of datasets and framework employed (only the multivariate time series classification problem), and the results obtained. The main results achieved during the TSC classification task are located with moderate or high prior (> 0.6). Moreover, the experiments are conduced with both small models and datasets.\n\nThe experiment for sequential data imputation for time series and videos is not clear, and the way of writing and giving explanation is quite confusing for the reader. Since the appendix is large, more details from the appendix in the paper itself will help the reader to more easily follow the idea.\n\nOverall, the experiments have to be larger and considering trickier tasks such as language processing related experiments (speech recognition, language modeling, etc.) that consider sequence mapping to extract robust features.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "HGF8wlXUw-", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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 to embed static feature maps into a larger linear space and shows that the proposed method achieves good performance on standard benchmarks. Detailed proofs and theoretical results are given in the appendices. The use of free algebras in ML seems novel and under-explored, although it is classical in mathematics. This paper shows that algebraic structure can significantly elevate the performance of existing models empirically. \n\nPros:\n+This paper shows that the free algebra T(V) can capture the non-commutativity among sequential data theoretically and experimentally, which is under-explored in ML area.\n \n+To address the heavy computational complexity of the free algebra, compositions of low-rank tensor projections(CP decomposition) are employed. \n\n\nCons:\n-The article is not clearly presented. The introduction is short and without illustrations to show the motivations. There is no intuitive explanation to show how the free algebra improve the models' performance.\n\n-Some notations used in paper are confusing.\na)In Section 3((Stacked) Seq2Tens layers.), what is the difference between D and $D^`$;\nb)In Algorithm 1, the truncation degree M and the tensor M share the same notation;\nc)In Figure 3, why have the 64$\\times$2 S2T and the Seq2Tens blocks different names and shapes? Aren't they the same module？\n\n-A lot of important information, including the details of architecture, algorithms and experiments etc, needs to be obtained from the appendix. This makes the article difficult to understand.\n\nSome typos:\nSec2: a sequences\nAppendix D.3, line 5 : be $n_l$ be rank-1 tensors.\nAlgorithm 1, line8: ·R\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EMkn4RMmPGD", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "Summary: This paper introduces the free algebra, a classical mathematical concept as a generic tool to represent sequential data of arbitrary length. The proposed method has attractive theoretical property, such as preserving universality of static feature mapping, and convergence in the continuous setting. The author further proposes using stacked rank-1 projection of the free algebra as an approximation to the sequence representation in order to make it computationally feasible neural networks layers. The author illustrated the flexibility and effectiveness of the proposed method by combining the NN implementation with FCN to benchmark on multivariate time series classification problem, and GP-VAE model to benchmark on sequential data imputation problem. The proposed methods shows improved results over previous state-of-the-art. \n\n\nSignificance: This paper provides the community an extension of the universal approximation theorem of NN on sequential data, as well as a generic method to transform static feature maps into sequence features. The experiment shows the proposed method and its implementation is flexible and effective in both discriminative and generative problems. Some questions/feedback: 1. In Proposition 2.3, while the rank-1 projection makes the method computationally feasible, taking sum over all non-contiguous subsequences of x cannot be too cheap? Would the author add analysis on computation complexity here? 2. In the experiment section, as the main motivation of stacking Seq2Tens layers is to mitigate the limitation of the representation power, how does different number of stacked Seq2Tens layers change the model performance? \n \nClarity: While the paper is highly technical, the author did a good job explaining the idea, concepts and objectives. \n\nOriginality: I am not aware of any other work explore free algebra and its usage on sequential data representation. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "BCXCn5Ax4q3", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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 an interesting low-rank tensor representation learning model called Seq2Tens for sequential data. The proposed model can be plugged into existing state-of-the-art neural network models as Seq2Tens layers to improve the performance, which has been demonstrated on several benchmark datasets in this paper. \n\nOn one hand, there are some solid contributions made in this paper. On the other hand, I do find it is difficult for the readers to appreciate its merits. Please see my detailed comments below.\n\n1. Possibly due to my limited mathematically background, \"the free algebra\" in the abstract of the PDF paper is a jargon for me (and possibly other AI/ML readers). Although I could google and learn from Wiki, I am not sure whether it is necessary. In the text abstract online, the authors use \"the tensor algebra\" in the online abstract of this paper.  Are they interchangeable? Which one is more appropriate? \n\n2. There is no citation to existing works in the first two pages, including the Introduction section. In fact, there is only one citation (on page 3) on the universality in the first three pages of this paper. Does this mean that all other materials are original? Because I am not familiar with so called free algebra, I expect some references to be provided. \n\n3. In the Introduction, after stating the problem of interest, the authors start describing the contributions immediately, without mentioning any existing approaches to solve the problems and giving proper context in judging or appreciating the claimed contributions.\n\n4. The name Seq2Tens is not properly defined, although I can tell it means \"sequence to tensors\". In fact, in the second paragraph on contributions in Sec. 1 Introduction, the authors did not mention the word \"tensor\" at all.\n\n5. Section 2 is quite abstract and mathematically, providing some visual illustrations will make the readers' life easier (e.g. cutting example frames in Fig. 3).\n\n6. Equation (3), the degree m is defined to be m>=0. Is it a user-defined hyperparameter? Is there a maximum value for m to take? If yes, what is it and how to determine it in practice? If not, does it mean that m can go to infinity (not likely)?\n\n7. Notations are not standard or consistent. A matrix is denoted as \\mathbf(t)_2 and a 3rd-order tensor as \\mathbf(t)_3, but the authors also use \\mathbf(t) without subscript, in which case I am wondering what is the order (or degree in the authors' chosen terminology). Then in Equation (7), the authors use a non-bold font ell to represent a tensor. In the equation between (1) and (2) (defining Seq2Tens), the right hand side is a capital V without bold, which I assume is a tensor. \n\n8. Acronyms are not always defined before use, e.g. TSC appears in Fig. 1 caption on page 5, but it is only defined on page 6. \n\n9. Section 4 refers too frequent to the appendix and it does not seem to be self-contained. Essential information about the data is missing so readers have to navigate through the 21-page appendix to find information necessary for them to appreciate the methods. \n\n10. Is there any hyperparameter to set? Is there a demonstration of convergence and sensitivity to hyperparameter settings? \n\n11. In Related work, the authors pointed out the vast literature on tensor-based models. However, there is no comparison against any of them. For example, many tensor-based machine learning algorithms have been applied to gait sequences for gait recognition so they model sequences as tensors too (google \"sequence tensor gait recognition\" w/o quote). These related works should be evaluated against the proposed model, many with public code available. \n\n12. As mentioned above, with many important information put in the appendix, I think the 18 frames displayed in Fig. 3 are more important than those essential information about the data, hyperparameter setting, etc. I am not sure whether human eyes can tell the improvements achieved in much less than 0.001 in MSE on Sprites and whether it matters in practice. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper uses free algebras for sequential data representation, and two of the reviewers and the AC find this highly innovative. There were numerous small issues brought up by reviewers (and reviewers disagreed some on the presentation), in particular R3 asking about the experiments, some of which were addressed in the rebuttal.  Overall, because the idea was unusual, it's a bit hard to place and judge this paper. In the end, in the opinion of this AC, the ideas are very creative and there is enough of a chance that this paper could become a very highly cited work, hence we recommend its acceptance.
Decision: Accept (Poster)