Title: GENERALIZED TENSOR MODELS FOR RECURRENT NEURAL NETWORKS

Abstract: Recurrent Neural Networks (RNNs) are very successful at solving challenging problems with sequential data. However, this observed efficiency is not yet entirely explained by theory. It is known that a certain class of multiplicative RNNs enjoys the property of depth efficiency -a shallow network of exponentially large width is necessary to realize the same score function as computed by such an RNN. Such networks, however, are not very often applied to real life tasks. In this work, we attempt to reduce the gap between theory and practice by extending the theoretical analysis to RNNs which employ various nonlinearities, such as Rectified Linear Unit (ReLU), and show that they also benefit from properties of universality and depth efficiency. Our theoretical results are verified by a series of extensive computational experiments.

1. INTRODUCTION:

Recurrent Neural Networks are firmly established to be one of the best deep learning techniques when the task at hand requires processing sequential data, such as text, audio, or video (Graves et al., 2013; Mikolov et al., 2011; Gers et al., 1999) . The ability of these neural networks to efficiently represent a rich class of functions with a relatively small number of parameters is often referred to as depth efficiency, and the theory behind this phenomenon is not yet fully understood. A recent line of work (Cohen & Shashua, 2016; Cohen et al., 2016; Khrulkov et al., 2018; Cohen et al., 2018) focuses on comparing various deep learning architectures in terms of their expressive power.

It was shown in (Cohen et al., 2016) that ConvNets with product pooling are exponentially more expressive than shallow networks, that is there exist functions realized by ConvNets which require an exponentially large number of parameters in order to be realized by shallow nets. A similar result also holds for RNNs with multiplicative recurrent cells (Khrulkov et al., 2018) . We aim to extend this analysis to RNNs with rectifier nonlinearities which are often used in practice. The main challenge of such analysis is that the tools used for analyzing multiplicative networks, namely, properties of standard tensor decompositions and ideas from algebraic geometry, can not be applied in this case, and thus some other approach is required. Our objective is to apply the machinery of generalized tensor decompositions, and show universality and existence of depth efficiency in such RNNs.

2. RELATED WORK:

Tensor methods have a rich history of successful application in machine learning. (Vasilescu & Terzopoulos, 2002) , in their framework of TensorFaces, proposed to treat facial image data as multidimensional arrays and analyze them with tensor decompositions, which led to significant boost in face recognition accuracy. (Bailey & Aeron, 2017) employed higher-order co-occurence data and tensor factorization techniques to improve on word embeddings models. Tensor methods also allow to produce more accurate and robust recommender systems by taking into account a multifaceted nature of real environments (Frolov & Oseledets, 2017) .

In recent years a great deal of work was done in applications of tensor calculus to both theoretical and practical aspects of deep learning algorithms. (Lebedev et al., 2015) represented filters in a convolutional network with CP decomposition (Harshman, 1970; Carroll & Chang, 1970) which allowed for much faster inference at the cost of a negligible drop in performance. (Novikov et al., 2015) proposed to use Tensor Train (TT) decomposition (Oseledets, 2011) to compress fully-connected layers of large neural networks while preserving their expressive power. Later on, TT was exploited to reduce the number of parameters and improve the performance of recurrent networks in long-term forecasting (Yu et al., 2017) and video classification (Yang et al., 2017) problems.

In addition to the practical benefits, tensor decompositions were used to analyze theoretical aspects of deep neural nets. (Cohen et al., 2016 ) investigated a connection between various network architectures and tensor decompositions, which made possible to compare their expressive power. Specifically, it was shown that CP and Hierarchial Tucker (Grasedyck, 2010) decompositions correspond to shallow networks and convolutional networks respectively. Recently, this analysis was extended by (Khrulkov et al., 2018) who showed that TT decomposition can be represented as a recurrent network with multiplicative connections. This specific form of RNNs was also empirically proved to provide a substantial performance boost over standard RNN models (Wu et al., 2016) .

First results on the connection between tensor decompositions and neural networks were obtained for rather simple architectures, however, later on, they were extended in order to analyze more practical deep neural nets. It was shown that theoretical results can be generalized to a large class of CNNs with ReLU nonlinearities (Cohen & Shashua, 2016) and dilated convolutions (Cohen et al., 2018) , providing valuable insights on how they can be improved. However, there is a missing piece in the whole picture as theoretical properties of more complex nonlinear RNNs have yet to be analyzed. In this paper, we elaborate on this problem and present new tools for conducting a theoretical analysis of such RNNs, specifically when rectifier nonlinearities are used.

3. ARCHITECTURES INSPIRED BY TENSOR DECOMPOSITIONS:

Let us now recall the known results about the connection of tensor decompositions and multiplicative architectures, and then show how they are generalized in order to include networks with ReLU nonlinearities.

3.1. SCORE FUNCTIONS AND FEATURE TENSOR:

Suppose that we are given a dataset of objects with a sequential structure, i.e. every object in the dataset can be written as

X = x (1) , x (2) , . . . , x (T ) , x (t) ∈ R N .

(1)

We also introduce a parametric feature map f θ : R N → R M which essentially preprocesses the data before it is fed into the network. Assumption 1 holds for many types of data, e.g. in the case of natural images we can cut them into rectangular patches which are then arranged into vectors x (t) . A typical choice for the feature map f θ in this particular case is an affine map followed by a nonlinear activation:

f θ (x) = σ(Ax + b).

To draw the connection between tensor decompositions and feature tensors we consider the following score functions (logits1 ):

EQUATION

where

EQUATION

where we have used the operation of outer product ⊗, which is important in tensor calculus. For a tensor A of order N and a tensor B of order M their outer product C = A ⊗ B is a tensor of order N + M defined as:

EQUATION

It is known that equation 2 possesses the universal approximation property (it can approximate any function with any prescribed precision given sufficiently large M ) under mild assumptions on f θ (Cohen et al., 2016; Girosi & Poggio, 1990) .

3.2. TENSOR DECOMPOSITIONS:

Working the entire weight tensor W in eq. ( 2) is impractical for large M and T , since it requires exponential in T number of parameters. Thus, we compactly represent it using tensor decompositions, which will further lead to different neural network architectures, referred to as tensor networks (Cichocki et al., 2017) .

CP-decomposition:

The most basic decomposition is the so-called Canonical (CP) decomposition (Harshman, 1970; Carroll & Chang, 1970) which is defined as follows

EQUATION

where v (t) r ∈ R M and minimal value of R such that decomposition equation 5 exists is called canonical rank of a tensor (CP-rank). By substituting eq. ( 5) into eq. ( 2) we find that

(X) = R r=1 λ r f θ (x (1) ), v (1) r ⊗ • • • ⊗ f θ (x (T ) ), v (T ) r = R r=1 λ r T t=1 f θ (x (t) ), v (t)

r . (6)

In the equation above, outer products ⊗ are taken between scalars and coincide with the ordinary products between two numbers. However, we would like to keep this notation as it will come in handy later, when we generalize tensor decompositions to include various nonlinearities.

TT-decomposition Another tensor decomposition is Tensor Train (TT) decomposition (Oseledets, 2011) which is defined as follows

EQUATION

where g

(t)

rt-1rt ∈ R M and r 0 = r T = 1 by definition. If we gather vectors g

(t)

rt-1rt for all corresponding indices r t-1 ∈ {1, . . . , R t-1 } and r t ∈ {1, . . . , R t } we will obtain three-dimensional tensors G (t) ∈ R M ×Rt-1×Rt (for t = 1 and t = T we will get matrices

G (1) ∈ R M ×1×R1 and G (T ) ∈ R M ×R T -1 ×1

). The set of all such tensors {G (t) } T t=1 is called TT-cores and minimal values of {R t } T -1 t=1 such that decomposition equation 7 exists are called TT-ranks. In the case of TT decomposition, the score function has the following form:

(X) = R1 r1=1 • • • R T -1 r T -1 =1 T t=1 f θ (x (t) ), g (t)

rt-1rt .

(8)

3.3. CONNECTION BETWEEN TT AND RNN:

Now we want to show that the score function for Tensor Train decomposition exhibits particular recurrent structure similar to that of RNN. We define the following hidden states:

EQUATION

Such definition of hidden states allows for more compact form of the score function. Lemma 3.1. Under the notation introduced in eq. ( 9), the score function can be written as

(X) = h (T ) ∈ R 1 .

Proof of Lemma 3.1 as well as the proofs of our main results from Section 5 were moved to Appendix A due to limited space.

Note that with a help of TT-cores we can rewrite eq. ( 9) in a more convenient index form:

EQUATION

where the operation of tensor contraction is used. Combining all weights from G (t) and f θ (•) into a single variable

Θ (t)

G and denoting the composition of feature map, outer product, and contraction as g : R Rt-1 × R N × R N ×Rt-1×Rt → R Rt we arrive at the following vector form:

EQUATION

)

This equation can be considered as a generalization of hidden state equation for Recurrent Neural Networks as here all hidden states h (t) may in general have different dimensionalities and weight tensors Θ

(t)

G depend on the time step. However, if we set 1) we will get simplified hidden state equation used in standard recurrent architectures:

R = R 1 = • • • = R T -1 and G = G (2) = • • • = G (T -

EQUATION

)

Note that this equation is applicable to all hidden states except for the first

h (1) = G (1) f θ (x (1)

) and for the last -1) , due to two-dimensional nature of the corresponding TT-cores. However, we can always pad the input sequence with two auxiliary vectors x (0) and x (T +1) to get full compliance with the standard RNN structure. Figure 1 depicts tensor network induced by TT decomposition with cores {G (t) } T t=1 .

h (T ) = f θ (x (T ) )G (T ) h (T

Figure 1 : Neural network architecture which corresponds to recurrent TT-Network.

4. GENERALIZED TENSOR NETWORKS:



4.1. GENERALIZED OUTER PRODUCT:

In the previous section we showed that tensor decompositions correspond to neural networks of specific structure, which are simplified versions of those used in practice as they contain multiplicative nonlinearities only. One possible way to introduce more practical nonlinearities is to replace outer product ⊗ in eq. ( 6) and eq. ( 10) with a generalized operator ⊗ ξ in analogy to kernel methods when scalar product is replaced by nonlinear kernel function. Let ξ : R × R → R be an associative and commutative binary operator (∀x, y, z ∈ R : ξ(ξ(x, y), z) = ξ(x, ξ(y, z)) and ∀x, y ∈ R : ξ(x, y) = ξ(y, x)). Note that this operator easily generalizes to the arbitrary number of operands due to associativity. For a tensor A of order N and a tensor B of order M we define their generalized outer product C = A ⊗ ξ B as an (N + M ) order tensor with entries given by:

EQUATION

Now we can replace ⊗ in eqs. ( 6) and ( 10) with ⊗ ξ and get networks with various nonlinearities. For example, if we take ξ(x, y) = max(x, y, 0) we will get an RNN with rectifier nonlinearities; if we take ξ(x, y) = ln(e x + e y ) we will get an RNN with softplus nonlinearities; if we take ξ(x, y) = xy we will get a simple RNN defined in the previous section. Concretely, we will analyze the following networks.

Generalized shallow network with ξ-nonlinearity:

• Score function:

EQUATION

• Parameters of the network:

Θ = {λ r } R r=1 ∈ R, {v (t) r } R,T r=1,t=1 ∈ R M (15)

Generalized RNN with ξ-nonlinearity

• Score function:

EQUATION

Note that in eq. ( 16) we have introduced the matrices C (t) acting on the input states. The purpose of this modification is to obtain the plausible property of generalized shallow networks being able to be represented as generalized RNNs of width 1 (i.e., with all R i = 1) for an arbitrary nonlinearity ξ. In the case of ξ(x, y) = xy, the matrices C (t) were not necessary, since they can be simply absorbed by G (t) via tensor contraction (see Appendix A for further clarification on these points).

Initial hidden state Note that generalized RNNs require some choice of the initial hidden state h (0) . We find that it is convenient both for theoretical analysis and in practice to initialize h (0) as unit of the operator ξ, i.e. such an element u that ξ(x, y, u) = ξ(x, y) ∀x, y ∈ R. Henceforth, we will assume that such an element exists (e.g., for ξ(x, y) = max(x, y, 0) we take u = 0, for ξ(x, y) = xy we take u = 1), and set h (0) = u. For example, in eq. ( 9) it was implicitly assumed that h (0) = 1.

4.2. GRID TENSORS:

Introduction of generalized outer product allows us to investigate RNNs with wide class of nonlinear activation functions, especially ReLU. While this change looks appealing from the practical viewpoint, it complicates following theoretical analysis, as the transition from obtained networks back to tensors is not straightforward.

In the discussion above, every tensor network had corresponding weight tensor W and we could compare expressivity of associated score functions by comparing some properties of this tensors, such as ranks (Khrulkov et al., 2018; Cohen et al., 2016) . This method enabled comprehensive analysis of score functions, as it allows us to calculate and compare their values for all possible input sequences X = x (1) , . . . , x (T ) . Unfortunately, we can not apply it in case of generalized tensor networks, as the replacement of standard outer product ⊗ with its generalized version ⊗ ξ leads to the loss of conformity between tensor networks and weight tensors. Specifically, not for every generalized tensor network with corresponding score function (X) now exists a weight tensor W such that (X) = W, Φ(X) . Also, such properties as universality no longer hold automatically and we have to prove them separately. Indeed as it was noticed in (Cohen & Shashua, 2016) shallow networks with ξ(x, y) = max(x, 0) + max(y, 0) no longer have the universal approximation property. In order to conduct proper theoretical analysis, we adopt the apparatus of so-called grid tensors, first introduced in (Cohen & Shashua, 2016) .

Given a set of fixed vectors X = x (1) , . . . , x (M ) referred to as templates, the grid tensor of X is defined to be the tensor of order T and dimension M in each mode, with entries given by:

EQUATION

where each index i t can take values from {1, . . . , M }, i.e. we evaluate the score function on every possible input assembled from the template vectors {x (i) } M i=1 . To put it simply, we previously considered the equality of score functions represented by tensor decomposition and tensor network on set of all possible input sequences X = x (1) , . . . , x (T ) , x (t) ∈ R N , and now we restricted this set to exponentially large but finite grid of sequences consisting of template vectors only.

Define the matrix F ∈ R M ×M which holds the values taken by the representation function f θ : R N → R M on the selected templates X:

EQUATION

)

Using the matrix F we note that the grid tensor of generalized shallow network has the following form (see Appendix A for derivation):

EQUATION

)

Construction of the grid tensor for generalized RNN is a bit more involved. We find that its grid tensor Γ (X) can be computed recursively, similar to the hidden state in the case of a single input sequence.

The exact formulas turned out to be rather cumbersome and we moved them to Appendix A.

5. MAIN RESULTS:

With grid tensors at hand we are ready to compare the expressive power of generalized RNNs and generalized shallow networks. In the further analysis, we will assume that ξ(x, y) = max(x, y, 0), i.e., we analyze RNNs and shallow networks with rectifier nonlinearity. However, we need to make two additional assumptions. First of all, similarly to (Cohen & Shashua, 2016) we fix some templates X such that values of the score function outside of the grid generated by X are irrelevant for classification and call them covering templates. It was argued that for image data values of M of order 100 are sufficient (corresponding covering template vectors may represent Gabor filters). Secondly, we assume that the feature matrix F is invertible, which is a reasonable assumption and in the case of f θ (x) = σ(Ax + b) for any distinct template vectors X the parameters A and b can be chosen in such a way that the matrix F is invertible.

5.1. UNIVERSALITY:

As was discussed in section 4.2 we can no longer use standard algebraic techniques to verify universality of tensor based networks. Thus, our first result states that generalized RNNs with ξ(x, y) = max(x, y, 0) are universal in a sense that any tensor of order T and size of each mode being m can be realized as a grid tensor of such RNN (and similarly of a generalized shallow network).

Theorem 5.1 (Universality). Let H ∈ R M ×M ×•••×M be an arbitrary tensor of order T . Then there exist a generalized shallow network and a generalized RNN with rectifier nonlinearity ξ(x, y) = max(x, y, 0) such that grid tensor of each of the networks coincides with H.

Part of Theorem 5.1 which corresponds to generalized shallow networks readily follows from (Cohen & Shashua, 2016, Claim 4) . In order to prove the statement for the RNNs the following two lemmas are used.

Lemma 5.1. Given two generalized RNNs with grid tensors Γ A (X), Γ B (X), and arbitrary ξ-nonlinearity, there exists a generalized RNN with grid tensor Γ C (X) satisfying

Γ C (X) = aΓ A (X) + bΓ B (X), ∀a, b ∈ R.

This lemma essentially states that the collection of grid tensors of generalized RNNs with any nonlinearity is closed under taking arbitrary linear combinations. Note that the same result clearly holds for generalized shallow networks because they are linear combinations of rank 1 shallow networks by definition.

Lemma 5.2. Let E (j1j2...j T ) be an arbitrary one-hot tensor, defined as

E (j1j2...j T ) i1i2...i T = 1, j t = i t ∀t ∈ {1, . . . , T }, 0, otherwise.

Then there exists a generalized RNN with rectifier nonlinearities such that its grid tensor satisfies

Γ (X) = E (j1j2...j T ) .

This lemma states that in the special case of rectifier nonlinearity ξ(x, y) = max(x, y, 0) any basis tensor can be realized by some generalized RNN.

Proof of Theorem 5.1. By Lemma 5.2 for each one-hot tensor E (i1i2...i T ) there exists a generalized RNN with rectifier nonlinearities, such that its grid tensor coincides with this tensor. Thus, by Lemma 5.1 we can construct an RNN with

Γ (X) = i1,i2,...,i T H i1i2...i d E (i1i2...i T ) = H.

For generalized shallow networks with rectifier nonlinearities see the proof of (Cohen & Shashua, 2016, Claim 4) .

The same result regarding networks with product nonlinearities considered in (Khrulkov et al., 2018) directly follows from the well-known properties of tensor decompositions (see Appendix A).

We see that at least with such nonlinearities as ξ(x, y) = max(x, y, 0) and ξ(x, y) = xy all the networks under consideration are universal and can represent any possible grid tensor. Now let us head to a discussion of expressivity of these networks.

5.2. EXPRESSIVITY:

As was discussed in the introduction, expressivity refers to the ability of some class of networks to represent the same functions as some other class much more compactly. In our case the parameters defining size of networks are ranks of the decomposition, i.e. in the case of generalized RNNs ranks determine the size of the hidden state, and in the case of generalized shallow networks rank determines the width of a network. It was proven in (Cohen et al., 2016; Khrulkov et al., 2018) that ConvNets and RNNs with multiplicative nonlinearities are exponentially more expressive than the equivalent shallow networks: shallow networks of exponentially large width are required to realize the same score functions as computed by these deep architectures. Similarly to the case of ConvNets (Cohen & Shashua, 2016) , we find that expressivity of generalized RNNs with rectifier nonlinearity holds only partially, as discussed in the following two theorems. For simplicity, we assume that T is even. Theorem 5.2 (Expressivity 1). For every value of R there exists a generalized RNN with ranks ≤ R and rectifier nonlinearity which is exponentially more efficient than shallow networks, i.e., the corresponding grid tensor may be realized only by a shallow network with rectifier nonlinearity of width at least 2 M T min(M, R) T /2 .

This result states that at least for some subset of generalized RNNs expressivity holds: exponentially wide shallow networks are required to realize the same grid tensor. Proof of the theorem is rather straightforward: we explicitly construct an example of such RNN which satisfies the following description. Given an arbitrary input sequence X = x (1) , . . . x (T ) assembled from the templates, these networks (if M = R) produce 0 if X has the property that x (1) = x (2) , x (3) = x (4) , . . . , x (T -1) = x (T ) , and 1 in every other case, i.e. they measure pairwise similarity of the input vectors. A precise proof is given in Appendix A.

In the case of multiplicative RNNs (Khrulkov et al., 2018) almost every network possessed this property. This is not the case, however, for generalized RNNs with rectifier nonlinearities.

Theorem 5.3 (Expressivity 2). For every value of R there exists an open set (which thus has positive measure) of generalized RNNs with rectifier nonlinearity ξ(x, y) = max(x, y, 0), such that for each RNN in this open set the corresponding grid tensor can be realized by a rank 1 shallow network with rectifier nonlinearity.

In other words, for every rank R we can find a set of generalized RNNs of positive measure such that the property of expressivity does not hold. In the numerical experiments in Section 6 and Appendix A we validate whether this can be observed in practice, and find that the probability of obtaining CP-ranks of polynomial size becomes negligible with large T and R. Proof of Theorem 5.3 is provided in Appendix A.

Shared case Note that all the RNNs used in practice have shared weights, which allows them to process sequences of arbitrary length. So far in the analysis we have not made such assumptions about RNNs (i.e.,

G (2) = • • • = G (T -1)

). By imposing this constraint, we lose the property of universality; however, we believe that the statements of Theorems 5.2 and 5.3 still hold (without requiring that shallow networks also have shared weights). Note that the example constructed in the proof of Theorem 5.3 already has this property, and for Theorem 5.2 we provide numerical evidence in Appendix A.

6. EXPERIMENTS:

In this section, we study if our theoretical findings are supported by experimental data. In particular, we investigate whether generalized tensor networks can be used in practical settings, especially in problems typically solved by RNNs (such as natural language processing problems). Secondly, according to Theorem 5.3 for some subset of RNNs the equivalent shallow network may have a low rank. To get a grasp of how strong this effect might be in practice we numerically compute an estimate for this rank in various settings.

Performance For the first experiment, we use two computer vision datasets MNIST (LeCun et al., 1990) and CIFAR-10 (Krizhevsky & Hinton, 2009) , and natural language processing dataset for sentiment analysis IMDB (Maas et al., 2011) . For the first two datasets, we cut natural images into rectangular patches which are then arranged into vectors x (t) (similar to (Khrulkov et al., 2018) ) and for IMDB dataset the input data already has the desired sequential structure.

Figure 2 depicts test accuracy on IMDB dataset for generalized shallow networks and RNNs with rectifier nonlinearity. We see that generalized shallow network of much higher rank is required to get the level of performance close to that achievable by generalized RNN. Due to limited space, we have moved the results of the experiments on the visual datasets to Appendix B. Expressivity For the second experiment we generate a number of generalized RNNs with different values of TT-rank r and calculate a lower bound on the rank of shallow network necessary to realize the same grid tensor (to estimate the rank we use the same technique as in the proof of Theorem 5.2).

Figure 3 shows that for different values of R and generalized RNNs of the corresponding rank there exist shallow networks of rank 1 realizing the same grid tensor, which agrees well with Theorem 5.3. This result looks discouraging, however, there is also a positive observation. While increasing rank of generalized RNNs, more and more corresponding shallow networks will necessarily have exponentially higher rank. In practice we usually deal with RNNs of R = 10 2 -10 3 (dimension of hidden states), thus we may expect that effectively any function besides negligible set realized by generalized RNNs can be implemented only by exponentially wider shallow networks. The numerical results for the case of shared cores and other nonlinearities are given in Appendix B.

7. CONCLUSION:

In this paper, we sought a more complete picture of the connection between Recurrent Neural Networks and Tensor Train decomposition, one that involves various nonlinearities applied to hidden states. We showed how these nonlinearities could be incorporated into network architectures and provided complete theoretical analysis on the particular case of rectifier nonlinearity, elaborating on points of generality and expressive power. We believe our results will be useful to advance theoretical understanding of RNNs. In future work, we would like to extend the theoretical analysis to most competitive in practice architectures for processing sequential data such as LSTMs and attention mechanisms.

A PROOFS Lemma 3.1. Under the notation introduced in eq. ( 9), the score function can be written as

(X) = h (T ) ∈ R 1 . Proof. l(X) = R1 r1=1 • • • R T -1 r T -1 =1 T t=1 f θ (x (t) ), g (t) rt-1rt = R1 r1=1 • • • R T -1 r T -1 =1 T t=2 f θ (x (t) ), g (t) rt-1rt f θ (x (1) ), g (1) r0r1 h (1) r 1 = R T -1 r T -1 =1 • • • R1 r1=1 T t=2 f θ (x (t) ), g (t) rt-1rt h (1) r1 = R T -1 r T -1 =1 • • • R2 r2=1 T t=3 f θ (x (t) ), g (t) rt-1rt r1 r1=1 f θ (x (2) ), g (2) r1r2 h (1) r1 h (2) r 2 = R T -1 r T -1 =1 • • • R2 r2=1 T t=3 f θ (x (t) ), g (t) rt-1rt h (2) r2 = . . . = R T -1 r T -1 =1 f θ (x (T ) ), g (T ) r T -1 r T h (T -1) r T -1 = h (T ) r T = h (T ) .

Proposition A.1. If we replace the generalized outer product ⊗ ξ in eq. ( 16) with the standard outer product ⊗, we can subsume matrices C (t) into tensors G (t) without loss of generality.

Proof. Let us rewrite hidden state equation eq. ( 16) after transition from ⊗ ξ to ⊗:

h (t) k = i,j G (t) ijk C (t) f θ (x (t) ) ⊗ h (t-1) ij = i,j G (t) ijk l C (t) il f θ (x (t) ) l h (t-1) j G(t) ljk = i G (t) ijk C (t) il = l,j G(t) ljk f θ (x (t) ) l h (t-1) j = l,j G(t) ljk f θ (x (t) ) ⊗ h (t-1) lj .

We see that the obtained expression resembles those presented in eq. ( 10) with TT-cores G (t) replaced by G(t) and thus all the reasoning applied in the absence of matrices C (t) holds valid.

Proposition A.2. Grid tensor of generalized shallow network has the following form (eq. ( 20)):

Γ (X) = R r=1 λ r Fv (1) r ⊗ ξ Fv (2) r ⊗ ξ • • • ⊗ ξ Fv (T ) r .

We claim that the desired grid tensor is given by the RNN with the following weight settings.

EQUATION

A ] i,:,:

0 , i ∈ {1, . . . , L A } 0 [G (1) B ] (i-L A ),:,: , i ∈ {L A + 1, . . . , L A + L B } G (t) C ∈ R (L A +L B )×(R t-1,A +R t-1,B )×(R t,A +R t,B ) , 1 < t < T [G (t) C ] i,:,: =                [G (t) A ] i,:,: 0 0 0 , i ∈ {1, . . . , L A } 0 0 0 [G (t) B ] (i-L A ),:,: , i ∈ {L A + 1, . . . , L A + L B } G (T ) C ∈ R (L A +L B )×(R t-1,A +R t-1,B )×1 [G (T ) C ] i,:,: =                a[G (T ) A ] i,:,: 0 , i ∈ {1, . . . , L A } 0 b[G (T ) B ] (i-L A ),:,: , i ∈ {L A + 1, . . . , L A + L B }.

It is straightforward to verify that the network defined by these weights possesses the following property:

h (t) C = h (t) A h (t) B , 0 < t < T,

and h

(T ) C = ah (T ) A + bh (T )

B , concluding the proof. We also note that these formulas generalize the well-known formulas for addition of two tensors in the Tensor Train format (Oseledets, 2011).

Proposition A.4. For any associative and commutative binary operator ξ, an arbitrary generalized rank 1 shallow network with ξ-nonlinearity can be represented in a form of generalized RNN with unit ranks

(R 1 = • • • = R T -1 = 1) and ξ-nonlinearity.

Proof. Let Θ = λ, {v (t) } T t=1 be the parameters specifying the given generalized shallow network. Then the following weight settings provide the equivalent generalized RNN (with h (0) being the unity of the operator ξ).

C (t) = v (t) ∈ R 1×M , G (t) = 1, t < T, G (T ) = λ.

Indeed, in the notation defined above, hidden states of generalized RNN have the following form:

Theorem 5.3 (Expressivity 2). For every value of R there exists an open set (which thus has positive measure) of generalized RNNs with rectifier nonlinearity ξ(x, y) = max(x, y, 0), such that for each RNN in this open set the corresponding grid tensor can be realized by a rank 1 shallow network with rectifier nonlinearity.

Proof. As before, let us denote by I (p,q) a matrix of size p × q such that I (p,q) ij = δ ij , and by a (p1,p2,...p d ) we denote a tensor of size p 1 × • • • × p d with each entry being a (sometimes we will omit the dimensions when they can be inferred from the context). Consider the following weight settings for a generalized RNN.

C (t) = F -1 , G (t) =    2 (M,1,R) , t = 1 1 (M,R,R) , t = 2, . . . , T -1 1 (M,R,1) , t = T

The RNN defined by these weights has the property that Γ (X) is a constant tensor with each entry being 2(M R) T -1 , which can be trivially represented by a rank 1 generalized shallow network. We will show that this property holds under a small perturbation of C (t) , G (t) and F. Let us denote each of these perturbation (and every tensor appearing size of which can be assumed indefinitely small) collectively by ε. Applying eq. ( 21) we obtain (with ξ(x, y) = max(x, y, 0)).

EQUATION

ijk (I (M,M ) + ε)

EQUATION

X) = Γ ,T (X) 1,:,:,...,: = (2(MR) T-1 + ε) ⊗ 1 • • • ⊗ 1, where we have used a simple property connecting ⊗ ξ with ξ(x, y) = max(x, y, 0) and ordinary ⊗: if for tensors A and B each entry of A is greater than each entry of B, A ⊗ ξ B = A ⊗ 1. The obtained grid tensors can be represented using rank 1 generalized shallow networks with the following weight settings.

λ = 1,

v t = F -1 ε (2(MR) T-1 + ε), t = 1, 0, t > 1,

where F ε is the feature matrix of the corresponding perturbed network.

B ADDITIONAL EXPERIMENTS:

In this section we provide the results additional computational experiments, aimed to provide more thorough and complete analysis of generalized RNNs.

Different ξ-nonlinearities In this paper we presented theoretical analysis of rectifier nonlinearity which corresponds to ξ(x, y) = max(x, y, 0). However, there is a number of other associative binary operators ξ which can be incorporated in generalized tensor networks. Strictly speaking, every one of them has to be carefully explored theoretically in order to speak about their generality and expressive power, but for now we can compare them empirically.

Table 1 shows the performance (accuracy on test data) of different nonlinearities on MNIST, CIFAR-10, and IMDB datasets for classification. Although these problems are not considered hard to solve, we see that the right choice of nonlinearity can lead to a significant boost in performance.

For the experiments on the visual datasets we used T = 16, m = 32, R = 64 and for the experiments on the IMDB dataset we had T = 100, m = 50, R = 50. Parameters of all networks were optimized using Adam (learning rate α = 10 -4 ) and batch size 250. ). We observe that similar to the case of different cores, there always exist rank 1 generalized shallow networks which realize the same score function as generalized RNN of higher rank, however, this situation seems too unlikely for big values of R. 

:

By logits we mean immediate outputs of the last hidden layer before applying nonlinearity. This term is adopted from classification tasks where neural network usually outputs logits and following softmax nonlinearity transforms them into valid probabilities.

Figures and Tables:

Figure 2: Test accuracy on IMDB dataset for generalized RNNs and generalized shallow networks with respect to the total number of parameters (M = 50, T = 100, ξ(x, y) = max(x, y, 0)).

Figure 3: Distribution of lower bounds on the rank of generalized shallow networks equivalent to randomly generated generalized RNNs of ranks 1, 2, 4, 8 (M = 10, T = 6).

Expressivity in the case of shared cores We repeat the expressivity experiments from Section 6 in the case of equal TT-cores (G(2) = • • • = G (T-1)

Figure 4: Distribution of lower bounds on the rank of generalized shallow networks equivalent to randomly generated generalized RNNs of ranks (M = 6, T = 6, ξ(x, y) = max(x, y, 0)).

Figure 5: Distribution of lower bounds on the rank of generalized shallow networks equivalent to randomly generated generalized RNNs of ranks (M = 6, T = 6, ξ(x, y) = x 2 + y 2 ).

ξ(x, y) xy max(x, y, 0) ln (e x + e y ) x + y x 2 + y 2 Performance of generalized RNN with various nonlinearities.

Table content: <table><tr><td>MNIST</td><td>97.39</td><td>97.45</td><td>97.68</td><td>96.28</td><td>96.44</td></tr><tr><td colspan="2">CIFAR-10 43.08</td><td>48.09</td><td>55.37</td><td>57.18</td><td>49.04</td></tr><tr><td>IMDB</td><td>83.33</td><td>84.35</td><td>82.25</td><td>81.28</td><td>79.76</td></tr></table>

Peer review (iclr2019):
 The authors extend the theoretical results of a paper previously presented in the last edition of ICLR (2018), where it was demonstrated that Recurrent Neural Network can be interpreted as a tensor network decomposition based on the Tensor-Train (TT, Oseledets et al, 2011). While previous results covered the multiplicative nonlinearity only, the contribution of the current paper is the extension of the analysis of universality and depth efficiency (Cohen et al, 2016) to different nonlinearities, for example ReLU (Rectified Linear Unit), which is very important from the practical point of view. The paper is well written and have a good structure. However, I found that some deep concepts are not well introduced, and maybe other more trivial results are discussed with unnecessary details. The following comments could help authors to improve the quality of presentation of their paper: - Section 3.1 (Score Functions and Feature Tensor) is a bit short and difficult to read. o Maybe, a more motivating introduction could be included in order to justify the definition of score functions (eq. 2). o It would be also nice to state that, according to eq. (3), the feature tensor is a rank-1 tensor. o I would suggest moving the definition of outer product to the Appendix, since most readers know it very well. o It is said that eq. 2 possesses the universal approximation property (it can approximate any function with any prescribed precision given sufficiently large M). It is not clear which is the approximation function. - A Connection with Tensor-Ring (TR) format, if possible, could be helpful: It is known that TR format (Zhao et al, 2016, arXiv:1606.05535), which is obtained by connecting the first and last units in a TT model, helps to alleviate the requirement of large ranks in the first and last the core tensors of a TT model reaching to a decomposition with an evenly distributed rank bounds. I think, it would be interesting to make a connection of RNN to TR because the assumption of R_i < R for all i becomes more natural. I would like to see at least some comment from the authors about the applicability of TR in the context of analysis of RNN, if possible. Maybe, also the initial hidden state defined in page 5 can be avoided if TR is used instead of TT. - Fig 2 shows that Test accuracy of a shallow network (CP based) is lower and increases with the number of parameters approaching to the one for RNN (TT based). It would be necessary to show the results for an extended range in the number of parameters, for example, by plotting the results up to 10^6. It is expected that, at some point, the effect of overfitting start decreasing the test accuracy. - When scores functions are presented (eq. 2) it is written the term "logits" between brackets. Could you please clarify why this term is introduced here? Usually, logit of a probability p is defined as L(p)=p/(1-p). What is the usage of this term in this work? - I think the theory is presented for a model with the two-classes only but used for multiple classes in the experimental sections. It should be necessary to make some comment about this in the paper. - Details about how the RNN based on TT is applied must be added. More specifically, the authors should provide answers to clarify the following questions: (i) Are patches overlapped or non-overlapped? (ii) What value of M is used? and is there any general rule for this choice? (iii) How the classification in the 10-classes is obtained? Are you using a softmax function in the last layer? Are you using one weight tensor W_c per class (c=1,2,...,10). Please provide these technical details. (iv) Please, specify which nonlinear activation sigma is used in the feature map f_.theta(x). (v) How many feature maps are used? and, Are the matrix A and vector b learned from training dataset or only the TT-cores need to be learned?