The key attribute that drives the unprecedented success of modern Recurrent Neural Networks (RNNs) on learning tasks which involve sequential data, is their ever-improving ability to model intricate long-term temporal dependencies. However, a well established measure of RNNs' long-term memory capacity is lacking, and thus formal understanding of their ability to correlate data throughout time is limited. Though depth efficiency in convolutional networks is well established by now, it does not suffice in order to account for the success of deep RNNs on inputs of varying lengths, and the need to address their 'time-series expressive power' arises. In this paper, we analyze the effect of depth on the ability of recurrent networks to express correlations ranging over long time-scales. To meet the above need, we introduce a measure of the information flow across time that can be supported by the network, referred to as the Start-End separation rank. Essentially, this measure reflects the distance of the function realized by the recurrent network from a function that models no interaction whatsoever between the beginning and end of the input sequence. We prove that deep recurrent networks support Start-End separation ranks which are exponentially higher than those supported by their shallow counterparts. Moreover, we show that the ability of deep recurrent networks to correlate different parts of the input sequence increases exponentially as the input sequence extends, while that of vanilla shallow recurrent networks does not adapt to the sequence length at all. Thus, we establish that depth brings forth an overwhelming advantage in the ability of recurrent networks to model long-term dependencies, and provide an exemplar of quantifying this key attribute which may be readily extended to other RNN architectures of interest, e.g. variants of LSTM networks. We obtain our results by considering a class of recurrent networks referred to as Recurrent Arithmetic Circuits (RACs), which merge the hidden state with the input via the Multiplicative Integration operation. Over the past few years, Recurrent Neural Networks (RNNs) have become the prominent machine learning architecture for modeling sequential data, having been successfully employed for language modeling (Sutskever et al., 2011; Graves, 2013) , neural machine translation (Bahdanau et al., 2014) , speech recognition (Graves et al., 2013; BID1 , and more. The success of recurrent networks in learning complex functional dependencies for sequences of varying lengths, readily implies that long-term and elaborate correlations in the given inputs are somehow supported by these networks. However, formal understanding of the influence of a recurrent network's structure on its expressiveness, and specifically on its ever-improving ability to integrate data throughout time (e.g. translating long sentences, answering elaborate questions), is lacking.An ongoing empirical effort to successfully apply recurrent networks to tasks of increasing complexity and temporal extent, includes augmentations of the recurrent unit such as Long Short Term Memory (LSTM) networks (Hochreiter and Schmidhuber, 1997) and their variants (e.g. Cho et al. (2014) ). A parallel avenue, which we focus on in this paper, includes the stacking of layers to form deep recurrent networks (Schmidhuber, 1992) . Deep recurrent networks, which exhibit empirical superiority over shallow ones (see e.g. Graves et al. (2013) ), implement hierarchical processing of information at every time-step that accompanies their inherent time-advancing computation. Evidence for a time-scale related effect arises from experiments (Hermans and Schrauwen, 2013) -deep recurrent networks appear to model correlations which correspond to longer time-scales than shallow ones. These findings, which imply that depth brings forth a considerable advantage in complexity and in temporal capacity of recurrent networks, have no adequate theoretical explanation.In this paper, we address the above presented issues. Based on the relative maturity of depth efficiency results in neural networks, namely results that show that deep networks efficiently express functions that would require shallow ones to have a super-polynomial size (e.g. Cohen et al. (2016) ; Eldan and Shamir (2016) ), it is natural to assume that depth has a similar effect on the expressiveness of recurrent networks. Indeed, we show that depth efficiency holds for recurrent networks.However, the distinguishing attribute of recurrent networks, is their inherent ability to cope with varying input sequence length. Thus, once establishing the above depth efficiency in recurrent networks, a basic question arises, which relates to the apparent depth enhanced long-term memory in recurrent networks: Do the functions which are efficiently expressed by deep recurrent networks correspond to dependencies over longer time-scales? We answer this question, by showing that depth provides an exponential boost to the ability of recurrent networks to model long-term dependencies.In order to take-on the above question, we introduce in section 2 a recurrent network referred to as a recurrent arithmetic circuit (RAC) that shares the architectural features of RNNs, and differs from them in the type of non-linearity used in the calculation. This type of connection between state-of-the-art machine learning algorithms and arithmetic circuits (also known as Sum-Product Networks (Poon and Domingos, 2011)) has well-established precedence in the context of neural networks. Delalleau and Bengio (2011) prove a depth efficiency result on such networks, and Cohen et al. (2016) theoretically analyze the class of Convolutional Arithmetic Circuits which differ from common ConvNets in the exact same fashion in which RACs differ from more standard RNNs. Conclusions drawn from such analyses were empirically shown to extend to common ConvNets (e.g. Sharir and Shashua (2017) ; Levine et al. (2017) ). Beyond their connection to theoretical models, the modification which defines RACs resembles that of Multiplicative RNNs (Sutskever et al., 2011) and of Multiplicative Integration networks (Wu et al., 2016) , which provide a substantial performance boost over many of the existing RNN models. In order to obtain our results, we make a connection between RACs and the Tensor Train (TT) decomposition (Oseledets, 2011) , which suggests that Multiplicative RNNs may be related to a generalized TT-decomposition, similar to the way Cohen and Shashua (2016) connected ReLU ConvNets to generalized tensor decompositions.We move on to introduce in section 3 the notion of Start-End separation rank as a measure of the recurrent network's ability to model elaborate long-term dependencies. In order to analyze the longterm correlations of a function over a sequential input which extends T time-steps, we partition the inputs to those which arrive at the first T /2 time-steps ("Start") and the last T /2 time-steps ("End"), and ask how far the function realized by the recurrent network is from being separable w.r.t. this partition. Distance from separability is measured through the notion of separation rank (Beylkin and Mohlenkamp, 2002) , which can be viewed as a surrogate of the L 2 distance from the closest separable function. For a given function, high Start-End separation rank implies that the function induces strong correlation between the beginning and end of the input sequence, and vice versa.In section 4 we directly address the depth enhanced long-term memory question above, by examining depth L = 2 RACs and proving that functions realized by these deep networks enjoy Start-End separation ranks that are exponentially higher than those of shallow networks, implying that indeed these functions can model more elaborate input dependencies over longer periods of time. An additional reinforcing result is that the Start-End separation rank of the deep recurrent network grows exponentially with the sequence length, while that of the shallow recurrent network is independent of the sequence length. Informally, this implies that vanilla shallow recurrent networks are inadequate in modeling correlations of long input sequences, since in contrast to the case of deep recurrent networks, the modeled dependencies achievable by shallow ones do not adapt to the actual length of the input. Finally, we present and motivate a quantitative conjecture by which the Start-End separation rank of recurrent networks grows exponentially with the network depth. A proof of this conjecture, which will provide an even deeper insight regarding the advantages of depth in recurrent networks, is left as an open problem. The notion of depth efficiency, by which deep networks efficiently express functions that would require shallow networks to have a super-polynomial size, is well established in the context of convolutional networks. However, recurrent networks differ from convolutional networks, as they are suited by design to tackle inputs of varying lengths. Accordingly, depth efficiency alone does not account for the remarkable performance of recurrent networks on long input sequences. In this paper, we identified a fundamental need for a quantifier of 'time-series expressivity', quantifying the memory capacity of recurrent networks. In order to meet this need, we proposed a measure of the ability of recurrent networks to model long-term temporal dependencies, in the form of the Start-End separation rank. The separation rank was used to quantify correlations in convolutional networks, and has roots in the field of quantum physics. The proposed measure adjusts itself to the temporal extent of the input series, and quantifies the ability of the recurrent network to correlate the incoming sequential data as time progresses.We analyzed the class of Recurrent Arithmetic Circuits, which are closely related to successful RNN architectures, and proved that the Start-End separation rank of deep RACs increases exponentially as the input sequence extends, while that of shallow RACs is independent of the input length. These results, which demonstrate that depth brings forth an overwhelming advantage in the ability of recurrent networks to model long-term dependencies, were achieved by combining tools from the fields of measure theory, tensorial analysis, combinatorics, graph theory and quantum physics.Such analyses may be readily extended to other architectural features employed in modern recurrent networks. Indeed, the same time-series expressivity question may now be applied to the different variants of LSTM networks, and the proposed notion of Start-End separation rank may be employed for quantifying their memory capacity. We have demonstrated that such a treatment can go beyond unveiling the origins of the success of a certain architectural choice, and leads to new insights. The above established observation that correlations achievable by vanilla shallow recurrent network do not adapt at all to the sequence length, is an exemplar of this potential.Moreover, practical recipes may emerge by such theoretical analyses. The experiments preformed in Hermans and Schrauwen (2013) , suggest that shallow layers of recurrent networks are related to short time-scales, e.g. in speech: phonemes, syllables, words, while deeper layers appear to support correlations of longer time-scales, e.g. full sentences, elaborate questions. These findings open the door to further depth related investigations in recurrent networks, and specifically the role of each layer in modeling temporal correlations may be better understood. Levine et al. (2017) establish theoretical observations which translate into practical conclusions regarding the number of hidden channels to be chosen for each layer in a deep convolutional network. The conjecture presented in this paper, by which the Start-End separation rank of recurrent networks grows exponentially with depth, can similarly entail practical recipes for enhancing their memory capacity. Such analyses can be reinforced by experiments, and lead to a profound understanding of the contribution of deep layers to the recurrent network's memory. Indeed, we view this work as an important step towards novel methods of matching the recurrent network architecture to the temporal correlations in a given sequential data set. We begin in section A.1 by providing a brief introduction to TNs. Next, we present in section A.2 the TN which corresponds to the calculation of a shallow RAC, and tie it to a common TN architecture referred to as a Matrix Product State (MPS) (see overview in e.g. Orús (2014)), and equivalently to the tensor train (TT) decomposition (Oseledets, 2011) . Subsequently, we present in section A.3 a TN construction of a deep RAC, and emphasize the characteristics of this construction that are the origin of the enhanced ability of deep RACs to model elaborate temporal dependencies. Finally, in section A.4, we make use of the above TNs construction in order to formally motivate conjecture 1, according to which the Start-End separation rank of RACs grows exponentially with depth. A TN is a weighted graph, where each node corresponds to a tensor whose order is equal to the degree of the node in the graph. Accordingly, the edges emanating out of a node, also referred to as its legs, represent the different modes of the corresponding tensor. The weight of each edge in the graph, also referred to as its bond dimension, is equal to the dimension of the appropriate tensor mode. In accordance with the relation between mode, dimension and index of a tensor presented in section 3.2, each edge in a TN is represented by an index that runs between 1 and its bond dimension. FIG4 shows three examples: (1) A vector, which is a tensor of order 1, is represented by a node with one leg. (2) A matrix, which is a tensor of order 2, is represented by a node with two legs. (3) Accordingly, a tensor of order N is represented in the TN as a node with N legs.We move on to present the connectivity properties of a TN. Edges which connect two nodes in the TN represent an operation between the two corresponding tensors. A index which represents such an edge is called a contracted index, and the operation of contracting that index is in fact a summation over all of the values it can take. An index representing an edge with one loose end is called an open index. The tensor represented by the entire TN, whose order is equal to the number of open indices, can be calculated by summing over all of the contracted indices in the network. An example for a contraction of a simple TN is depicted in FIG4 . There, a TN corresponding to the operation of multiplying a vector v ∈ R r 1 by a matrix M ∈ R r 2 ×r 1 is performed by summing over the only contracted index, k. As there is only one open index, d, the result of contracting the network is an order 1 tensor (a vector): u ∈ R r 2 which upholds u = M v. Though we use below the contraction of indices in more elaborate TNs, this operation can be essentially viewed as a generalization of matrix multiplication.
We propose a measure of long-term memory and prove that deep recurrent networks are much better fit to model long-term temporal dependencies than shallow ones.
{"src": "scitldr-AIC_train", "paper_id": "HJ3d2Ax0-"}