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. 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 BID10 BID18 BID7 . 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 BID12 BID5 focuses on comparing various deep learning architectures in terms of their expressive power.It was shown in 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 BID12 . 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. 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 DISPLAYFORM0 Proof. DISPLAYFORM1 rt−1rt h(1) r1 DISPLAYFORM2 r1r2 h(1) r1 DISPLAYFORM3 = . . . DISPLAYFORM4 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 ⊗: DISPLAYFORM5 We see that the obtained expression resembles those presented in eq. (10) with TT-cores G (t) replaced byG (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)): DISPLAYFORM6 denote an arbitrary sequence of templates. Corresponding element of the grid tensor defined in eq. FORMULA1 has the following form: DISPLAYFORM7 Proposition A.3. Grid tensor of a generalized RNN has the following form: DISPLAYFORM8 Proof. Proof is similar to that of Proposition A.2 and uses eq. FORMULA0 to compute the elements of the grid tensor.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 DISPLAYFORM9 Proof. Let these RNNs be defined by the weight parameters DISPLAYFORM10 and DISPLAYFORM11 We claim that the desired grid tensor is given by the RNN with the following weight settings. DISPLAYFORM12 It is straightforward to verify that the network defined by these weights possesses the following property: DISPLAYFORM13 , 0 < t < T, and h DISPLAYFORM14 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. DISPLAYFORM15 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 ξ). DISPLAYFORM16 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. DISPLAYFORM17 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. FORMULA0 we obtain (with ξ(x, y) = max(x, y, 0)). 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, DISPLAYFORM18 DISPLAYFORM19 ε (2(MR) T−1 + ε), t = 1, 0, t > 1, where F ε is the feature matrix of the corresponding perturbed network.
Analysis of expressivity and generality of recurrent neural networks with ReLu nonlinearities using Tensor-Train decomposition.
{"src": "scitldr-AIC_train", "paper_id": "r1gNni0qtm"}