Title: PATH SPACE FOR RECURRENT NEURAL NETWORKS WITH RELU ACTIVATIONS

Abstract: It is well known that neural networks with rectified linear units (ReLU) activation functions are positively scale-invariant (i.e., the neural network is invariant to positive rescaling of weights). Optimization algorithms like stochastic gradient descent that optimize the neural networks in the vector space of weights, which are not positively scale-invariant. To solve this mismatch, a new parameter space, called path space, has been proposed for feedforward and convolutional neural networks. The path space is positively scale-invariant and optimization algorithms operating in path space have been shown to be superior than that in the original weight space. However, the theory of path space and the corresponding optimization algorithm cannot be naturally extended to more complex neural networks, like Recurrent Neural Networks (RNN) due to the recurrent structure and the parameter sharing scheme over time. In this work, we aim to construct path space for RNN with ReLU activations so that we can employ optimization algorithms in path space. To achieve the goal, we propose leveraging the reduction graph of RNN which removes the influence of time-steps, and prove that all the values of paths in the reduction graph can serve as a sufficient representation of the RNN with ReLU activations. We then prove that the path space for RNN is composed by the basis paths in reduction graph, and design a Skeleton Method to identify the basis paths efficiently. With the identified basis paths, we develop the optimization algorithm in path space for RNN models. Our experiments on several benchmark datasets show that we can obtain more effective RNN models in this way than using optimization methods in the weight space.

1. INTRODUCTION:

Over the past ten years, ReLU activations have become increasingly popular in various types of neural networks such as Multilayer Perceptron(MLP) (Nair & Hinton, 2010; Glorot et al., 2011; Neyshabur et al., 2015a) , Convolutional Neural Networks (CNN) ( (Krizhevsky et al., 2012; He et al., 2016) ) and Recurrent Neural Networks (RNN) (Le et al., 2015; Neyshabur et al., 2016) . Theoretical studies on the MLP and CNN with ReLU activations, particularly on its positively scale-invariant (PSI) property have also been conducted (Neyshabur et al., 2016; 2015a; Dinh et al., 2017; Meng et al., 2018) . Specifically, PSI property means if the incoming weights of a hidden node (or a feature map for CNN) are multiplied by a positive scalar c, and the outgoing weights of this hidden node (or the feature map) are divided by c, the output for arbitrary input will keep unchanged. However, conventional algorithms like stochastic gradient descent optimize the neural networks in the vector space of weights, which are not positively scale-invariant. This mismatch may lead to problems during the optimization process (Neyshabur et al., 2015a; Meng et al., 2018) , e.g., in an unbalanced network (i.e., the norm of incoming weights to different units have relatively large differences), the training process of vanilla stochastic gradient descent will be significantly slowed down.

To solve the above mismatch, some recent studies have been conducted on paths of ReLU neural networks (Neyshabur et al., 2015a; Meng et al., 2018) . The value of a path is defined as the multiplication of weights along the path which starts from an input node, successively crosses a hidden node at every layer, and finally ends at an output node. Obviously, the value of a path is positively scale-invariant. Thus, a new parameter space, called path space, for MLP and CNN have been proposed. Path space is a vector space constituted by the values of given paths called basis paths, whose values are sufficient to calculate the output of the MLP and CNN with ReLU activations.

In a word, path space is a PSI parameter space and can sufficiently represent MLP and CNN with ReLU activation. In the work (Meng et al., 2018) , an algorithm is designed to identify the basis paths for MLP and CNN. Efficient optimization algorithms in path space have also been proposed, which iteratively update the values of basis paths according to the gradient of loss with respect to basis paths. Optimizing MLP or CNN with ReLU activations in this way can achieve better performances compared with traditional optimization methods in the weight space.

However, the studies of path space especially the identification of basis paths depend on the network structure, so it cannot be naturally extended to more complex network structures, like recurrent neural network (RNN). RNN is a powerful neural network model to process sequential data and show excellent performance in various domains such as language modeling (Mikolov et al., 2010; Jozefowicz et al., 2016) , machine translation (Bahdanau et al., 2014) and speech recognition (Graves et al., 2013; Miao et al., 2015) . RNN with ReLU activations (abbrev. ReLU RNN) is also positively scale-invariant (Neyshabur et al., 2016) . Considering the superiority of optimizing MLP or CNN with ReLU activations in their path space, the path space for RNN is worth studying.

In this work, we aim to construct path space for ReLU RNN so that we can employ the optimization algorithm in path space. Due to the recurrent structure, the paths in RNN depend on the time-steps. That means, if the sequence length of the input is not pre-given, the number of paths in RNN cannot be determined. It makes the identification of basis paths from the undetermined number of paths difficult. To handle this, we propose leveraging the reduction graph of RNN to remove the influence of time-steps and theoretically develop path space for RNN in the following three steps. First, we define paths on reduction graph, whose number is fixed and not influenced by the sequence length. Second, we prove that the paths on reduction graph can serve as a sufficient representation of the RNN with ReLU activations. Third, we define path space for RNN which is composed by the values of basis paths in the reduction graph.

Next, we design Skeleton Method to identify basis paths in reduction graph of RNN efficiently. Compared with MLP and CNN, the skeleton method for RNN needs extra steps to handle the recurrent weights. Specifically, the skeleton method for RNN contains two steps: it first identifies the basis paths in the reduction graph of RNN without recurrent weights; then it constructs the basis paths that contain recurrent weight. We prove that paths selected by Skeleton Method are basis paths, and the number of basis paths which is also the dimension of the path space is #(weights)-#(hidden nodes) in the reduction graph of RNN.

Finally, with the identified basis paths, we employ optimization algorithm in path space for RNN models, which operates update on basis paths according to the gradient of loss w.r.t basis paths. Our experiments on several benchmark datasets show that we can obtain significantly more effective RNN models in this way than using optimization methods in the weight space. It indicates that optimizing ReLU RNN in path space can solve the optimization problem brought by positively scale-invariant property and can indeed help optimization. To the best of our knowledge, our work is the first to construct the new parameter space, path space, for the RNN model and the first to optimize RNN in its path space.

The paper is organized as follows: in Section 2, we introduce the background about the path representation of ReLU RNN and related works; in Section 3, we formally define the basis path for ReLU RNN and propose using reduction graph as a tool to handle the difficulty when identifying the basis paths in ReLU RNN; in Section 4, we present our the basis path identification algorithm and the optimization algorithm in the path space; in Section 5, we show the experiment results to verify the effectiveness of our proposed algorithm; finally, we conclude this paper in Section 6.

2. BACKGROUND:

In this section, we briefly review the path representation of recurrent neural networks with ReLU activations and the related works in this direction.

2.1. PATH REPRESENTATION OF RELU RNN:

As shown in Figure 1 , the network structure of RNN can be regarded as a directed graph G(N , E), where N = ∪ t N t denotes the set of nodes and E denotes the set of edges, where

N t = {N I,(t) 1 , N I,(t) 2 • • • , N H,(t) d+1 , N H,(t) d+2 , • • • , N O,(t) d+h+1 , N O,(t) d+h+2 • • • N O,(t)

d+h+K } denotes the set of nodes at the t-th time-step, the superscripts I, H, O means the input, hidden and output node, respectively. Here, d, h, K denote the dimension of input, hidden nodes and output, respectively, and the superscript t denotes the time-step. In the graph G(N , E), there must be an edge between an input node and a hidden node that are at the same time step, a hidden node and an output node that are at the same time-step, and two hidden nodes whose time-steps are adjacent. A Path on the G(N , E) is defined in Definition 1. Definition 1 (Paths in RNN). A path in the recurrent neural network is defined as a list of nodes and the corresponding edges between adjacent nodes, which starts from an input node N I,(t) i 0 to one output node N O,(t+s) i s+1 with s ≥ 0 by successively crossing hidden nodes. Specifically, a path can be expressed as N I,(t)

i 0 → N H,(t) i 1 → • • • → N H,(t+s) i s+1 → N O,(t+s) i s+2

, and there must be an edge between the adjacent nodes, where i . is the index of node along the path. For example, the red line in Figure 1 shows an example of the paths. For simplicity, we omit the explicit expression of paths and use p to denote the index of paths in the following context. The value of a path is defined as the multiplication of the values of weights on edges contained in the path. Specifically, for an edge e k ∈ E, we use w k to denote the weight on edge e k , then the value of path p is v p = e k ∈p w k .

Using W i , W o and W r to denote three weight matrices, use x (t) to denote the input and use n H,(t) , n O,(t) to denote the corresponding hidden and output values at nodes N H,(t) and N O,(t) , recurrent neural network computes the output vector n O,(t) at t-th time-step by a recurrent formulation as: (t) .

EQUATION

n O,(t) = W o n H,

(2)

If the activation σ(•) is ReLU, i.e., σ(z) = max(z, 0), we can get n O,(t

) = W o • (W i x (t) + W r n H,(t-1) ) • diag(I(n H,(t) 1 > 0), • • • , I(n H,(t) h > 0)

) by combining Eq.(1) and Eq.( 2).1 According to the definition of value of a path, the output of ReLU RNN can be calculated using the values of paths and its activation status as follows,

EQUATION

where the set P T,k,i,t consists of the paths that connects the k-th output at time-step T and the i-th input at time-step t with length T + 1 -t, v p is the value of path p, and ap(w; x) = N H,(t) i ∈p I(n H,(t) i (w; x) > 0) is the activation status of path p.

2.2. RELATED WORKS:

In recent years, researchers have started to conduct theoretical studies on optimization and generalization of ReLU neural network by leveraging paths instead of weights. In the aspect of generalization, the works (Neyshabur et al., 2015b; 2017; Zheng et al., 2018) show that the generalization error of feedforward ReLU network is related to the path-norm. The work (Weinan et al., 2019) also leverages the path representation to analyze the generalization error of ReLU neural networks. Except for the generalization analysis, optimization algorithms based on paths are also designed. Neyshabur, et al. propose Path-SGD algorithm, which optimizes the loss function regularized by path-norm (Neyshabur et al., 2015a; 2016) . Path-SGD algorithm does not directly optimize ReLU RNN using the loss function composed by the path-represented output but optimizes the regularized loss defined in the original weight space. The work (Meng et al., 2018) proposes G-SGD algorithm to optimize the ReLU MLP and CNN directly by updating the values of paths according to the gradient of loss w.r.t basis paths. However, G-SGD is only designed for MLP and CNN. To the best of our knowledge, the path space constituted by basis paths for ReLU RNN has not been studied yet.In this paper, we will investigate the path space for RNN so that we can apply G-SGD to RNN.

3. PATH SPACE FOR RELU RNN:

In this section, we investigate the path space, a vector space constituted by values of basis paths for ReLU RNN. We first formally define the basis paths for ReLU RNN. Then we propose using reduction graph as a tool to define the path space for ReLU RNN.

3.1. DEFINITION OF BASIS PATHS FOR RNN:

As stated in the introduction, it has been shown in (Neyshabur et al., 2016) (cf. Theorem 1 and Figure 1 ) that the output of RNN is positively scale-invariant (PSI) i.e., if all the incoming weights(including the shared weights) of a hidden node are multiplied by a positive scalar c and all the outgoing weight (including the shared weights) of this hidden node are multiplied by 1/c, ReLU RNN will generate the same output for arbitrary input. Because the values of paths are also positively scale-invariant, which matches the PSI property of ReLU RNN, we are motivated to directly represent and optimize the RNN model according to the path representation (Eq.( 3)).

However, we cannot directly optimize the values of all the paths by regarding each of them to be an independent parameter, because they are correlated with each other. We use Figure 1 to show an example. For simplicity, we denote the weight of the edge that connects node i and node j as w ij .2 We denote the red path in Figure 1 as p1 :

N I,(1) 2 → N H,(1) 3 → N H,(2) 3 → N O,(2) 6 whose value is vp 1 = w23 • w33 • w36.

We can show that the value of path p 1 can be calculated by the values of following four paths through multiplication and division.

p2 : N I,(1) 2 → N H,(1) 3 → N O,(1) 5 vp 2 = w23 • w35 p3 : N I,(1) 1 → N H,(1) 3 → N H,(2) 3 → N O,(1) 5 vp 3 = w13 • w33 • w3,5 p4 : N I,(1) 1 → N H,(1) 3 → N O,(1) 6 vp 4 = w13 • w36 p5 : N I,(1) 1 → N H,(1) 3 → N O,(1) 5 vp 5 = w13 • w35.

It is easy to verify that:

EQUATION

)

Because v p1 can be calculated using v p2 , • • • , v p5 , we only need to know v p2 , • • • , v p5 and the relation in Eq.( 4) when to represent the output of RNN.

For any given recurrent neural network, we need to first investigate and decouple the correlation among their values so that we can identify a subset of paths whose values can be directly optimized. Motivated by the example, we formally define basis paths as follows.

Definition 2 (Basis Paths). A set of paths P b are called basis paths if they satisfy the following properties: (1) for any path p ∈ P/P b , there exists non-zero coefficient vector α The first item in the definition ensures the sufficiency to use basis paths to calculate the values of other paths, and the second item ensures that the values of basis paths are independent, i.e., the values of basis paths cannot be calculated by each other. In the work (Meng et al., 2018) , basis paths have been defined for MLP, however, it is no longer suitable for RNN. Here, the definition 2 for basis paths is more general and can be generalized to many kinds of network structures.

= (α 1 , • • • , α z ) to make v p (w) = j∈P b v j (w

3.2. DEFINING PATH SPACE FOR RELU RNN THROUGH REDUCTION GRAPH:

Although basis paths have been defined in the previous section, given an RNN, it is difficult to identify the basis paths because: (1) the number of paths exponentially depends on the time-steps, which is very large in general;

(2) if the sequence length of input is not pre-given, the exact number of paths in RNN cannot be determined. To handle this, we study the paths in reduction graph of ReLU RNN.

Here, we give the definition of the reduction graph for RNN and show an example in the Figure 2 . Given a directed graph of RNN, we use G r (N r , E r ) to denote its corresponding reduction graph, where

N r = {N I 1 , N I 2 • • • , N H d+1 , N H d+2 , • • • , N O d+h+1 , N O d+h+2 • • • N O d+h+K }

denotes the set of nodes and E r denotes the set of edges. There must be an edge between an input node and a hidden node, a hidden node and an output node and two hidden nodes, respectively. We call the edges that connect two hidden nodes as recurrent edges.

Definition 4 (Path in Reduction Graph). A path in the reduction graph for RNN is a list of nodes that satisfies the following conditions: (1) it starts from an input node and end at an output node of the reduction graph;

(2) it can at most cross one recurrent edge.

According to the definition, the paths in reduction graph are classified into two categories: the paths does not contain recurrent edge denoted as

N I i 0 → N H i 1 → N O i 2 ; contain one recurrent edge denoted as N I i 0 → N H i 1 → N H i 2 → N O i 3 .

Hence, the paths in reduction graph is not related to the time-steps. That means, no matter how long the sequence length of the input, the number of paths in reduction graph is fixed. The next theorem shows that the values of paths in the reduction graph are sufficient to represent RNN. Theorem 1. All the values of paths in directed graph of RNN can be calculated using the values of paths in the reduction graph of RNN through multiplication and division operators.

We put the proof of Theorem 1 in Appendix and only deliver the techniques used in the proof here. We index the trained weights as w 1 , • • • , w i , • • • , w m , and represent each path using an m-dimensional

vector c p = (c p1 , • • • , c pm ) where c p satisfy vp = m i=1 w c pi i .

We prove that the vectors of all paths can be calculated through linear combinations of vectors of paths in reduction graph. Thus, we can get the result in Theorem 1.

We use P to denote the set constituted by all paths of RNN, P r to denote the set constituted by paths in reduction graph and P b to denote the set constituted by basis paths of RNN. According to Definition 2 and Theorem 1, we have P b ⊂ Pr ⊂ P. Thus, the basis paths in the reduction graph of RNN is the basis paths of RNN model. Paths in reduction graph of RNN is totally determined by the model and not influenced by the time-steps, and as well as the basis paths.

Next, we show that basis paths are sufficient to represent the output of ReLU RNN. According to Eq.(3) and item (1) in the definition of basis paths, we only need to prove that the activation status of paths can also be determined by the values of basis paths. Theorem 2. The activation status of the paths in ReLU RNN can be calculated using the values of basis paths and the signs of the selected elements in W o if for each column in matrix W o with dimension K × h, we randomly select one element whose sign is pre-given and fixed.

Using the basis paths, we can construct a new vector space, called path space, for ReLU RNN as :

EQUATION

where p i , i = 1, • • • , z are the basis paths for RNN.

Till now, we have defined path space for ReLU RNN and proved that path space is sufficient to represent ReLU RNN in Theorem 2. In next section, we will introduce how to optimize ReLU RNN in its path space including that how to identify basis paths for given reduction graph.

4. OPTIMIZATION ALGORITHM IN PATH SPACE FOR RNN:

In this section, we design Skeleton Method to identify the basis paths in reduction graph of RNN efficiently. Then, we introduce the update rule of optimization algorithm in path space for RNN.

We decompose the reduction graph of recurrent neural network into two parts: the feedforward part and the recurrent edges part. The feedforward part contains all nodes in reduction graph and the non-recurrent edges, and the recurrent edges part contains only the recurrent edges. In Skeleton Method, we first define the skeleton edges in the feedforward part and then use the skeleton edges to construct the basis paths. We prove that the paths that contains at most one non-skeleton edges are basis path.

The Skeleton Method for RNN is described in the following box.

Skeleton Method (1) For each hidden node in the feedforward part, we randomly select one edge that pointing to this hidden node and randomly select one edge that starts from this hidden node. Putting the selected edges of all hidden nodes together, all the selected edges are called skeleton edges. All other edges are called non-skeleton edges.

(2) The paths that contain at most one non-skeleton edges in the feedforward part are selected into set P b1 .

(3) The paths containing only skeleton edges and one recurrent edge are selected into set P b2 . (4) The final selected path set is P b1 ∪ P b2 .

We illustrate the Skeleton Method in Figure 3 (b). The red edges are the skeleton edges selected in step (1). Left three basis paths are in P b 1 and the last one is in P b 2 . For the paths in P b 1 , we further denote the set constituted by paths only contain skeleton edges as P s and the set constituted by paths contain one non-skeleton edges as P ns .

In the following theorem, we prove that the paths selected by Skeleton Method are basis paths. Theorem 3. The set of paths P b1 ∪ P b2 selected by the Skeleton Method are basis paths. The number of basis paths (or equivalently the dimension of the path space) for recurrent neural networks is #(weights)-#(hidden nodes), where "#" means "the number of".

After identifying the basis path using Skeleton Method, we aim to optimize the loss function L(v) by following the negative direction of the gradients of loss w.r.t basis paths as below,

EQUATION

where p i is the index of the basis paths. G-SGD algorithm has been designed in work (Meng et al., 2018) , which can efficiently implement the above update rule in path space for MLP. Here, we apply G-SGD to RNNs. Due to space limitation, we only introduce the high-level idea as below and the update rule in Alg. 2. For more details about its derivation, please refer to the Appendix B.1. or Eq.( 4) and Eq.( 5) in (Meng et al., 2018) .

First, we construct mask matrices to distinguish the skeleton edge and non-skeleton edge according to step (1) in skeleton method. As shown in Alg.1, it generates mask matrices M i , M o which have the same size with W i and W o , respectively, and using elements 1 and 0 in the mask matrices to denote skeleton and non-skeleton edge, respectively. Second, G-SGD calculates the gradient w.r.t basis path by using the fact that the value of basis path is multiplication of weights on this path. So it first calculates the gradient w.r.t weights (Line 3-4 in Alg.2) and then using the relation between paths and weights to obtain the gradients w.r.t basis paths Gp s , Gpo ns and Gpr ns where footnotesizep s ∈ P s , p o ns ∈ P ns , p r ns ∈ P b2 (Line 6 in Alg.2). This step is called Inverse-Chain-Rule. Third, after updating the basis paths according to Eq.( 6), it calculates the ratio Ri = v t+1 p i /v t p i for p i ∈ P s . Fourth, it allocates the ratio to weights to obtain new weights (Line 9-10 in Alg.2) in order to implement forward process in next iteration3 . Detailed derivation can be referred to Appendix B.1.

Algorithm 1: Mask-Matrix-Constructor Input: weight matrices of RNN model W i , W o M i = zeros like(W i ), M o = zeros like(W o ) ; n out = shape(W i )[0] ; n in = shape(W i )[1] ; for j = 1 to n out do M i [j][j % n in ] = 1 ; end n out = shape(W o )[0] ; n in = shape(W o )[1] ; for j = 1 to n in do M o [j][j % n out ] = 1 ; end Output: Mask Matrix M i , M o Algorithm 2: G-SGD for RNN Input: RNN model FRNN (W i , W r , W o ), data X, Y , loss function loss f unc, learning rate η M i , M o = Mask-Matrix-Constructor(W i , W o ) ; repeat

Sample a batch of data x, y, compute the loss function loss = loss f unc(FRNN (x), y) ; Using Back-Propagation to compute the gradient w.r.t the weight:

G W i , GW r , GW o = BP (loss, W i , W r , W o ) ;

### Using Inverse-Chain-Rule to obtain the gradient w.r.t basis paths:

Gp s = G W i -(W r •G W r ).sum(0)+(W o •G W o ).sum(0) (W i •M i ).sum(0) ; Gpo ns = G W o W o ; Gpr ns = G W r W r ; ### Calculate the Update Ratio: R = 1 -η • Gp s (W i •M i ).sum(0) ;

### Weight-Allocation and update weight matrices as:

W i = W i • diag(R) + (W i -η • G W i ) • (1 -M i ); W o = W o • M o + W o -η• G p o ns W i diag(R) • (1 -M o ); W r = W r -η• G p r ns W i diag(R)

until stopping criterion is met;

Output: Weights of RNN model W i , W r , W o

Computational Cost Analysis.

(1)The Mask-Matrix-Calculator(Algorithm 1) only run once at the beginning. So the extra cost can be ignored.

(2)As shown in the Algorithm 2, the forward and backward phase in G-SGD for RNN is the same as traditional SGD algorithm (Line 3-4). The extra computational cost is in Inverse-Chain-Rule and Calculate the update ratio(Line 5-7). Please note that we only need to calculate the ratio R for basis paths in P s whose number equals to the number of hidden nodes, which is small compared with the number of weights. Thus the computational cost of step 5-10 is much less than the backward process. In realistic experiments, the extra time cost is less than 10% compared to vanilla SGD. We list the running time of each algorithm in Appendix(Tab. 4).

Remark::

The skeleton method and the update rule of G-SGD can be generalized to stack RNN and recurrent convolutional neural networks (RCNN), which can be referred to Appendix. Besides, according to Definition 2, the selection of basis paths is not unique. Every selection can serve as a sufficient representation of the model. Skeleton Method only provides one selection of them. In this work, we employ G-SGD based on this fixed selection. For other selections, the update rule of G-SGD can also be derived similarly.

5. EXPERIMENT:

In this section, we verify the effectiveness of the optimization algorithms in path space for ReLU RNN.

We train ReLU RNN on several tasks and show that we can obtain significantly more effective RNN models in path space than using conventional optimization methods in the weight space. Specifically, we take vanilla SGD and Path-SGD (Neyshabur et al., 2016) to be our baselines.

5.1. SEQUENTIAL MNIST:

In this section, we optimize the ReLU RNN for the Sequential MNIST (LeCun, 1998; Neyshabur et al., 2016; Le et al., 2015; Arjovsky et al., 2015; Bai et al., 2019) . In Sequential MNIST, each digit image is reshaped into a sequence, turning the digit classification task into a sequence classification task with long-term dependencies. To make the task even harder, we also use a fixed random permutation on the pixels of the MNIST digits.

MNIST dataset is download from the official site (LeCun). The sequence length is set to 28 and 98. (Hutter, 2012) . The first two datasets are word level and the last two datasets are character level. For all tasks, we train a stacked ReLU RNN with 4 layers. The learning rate is turned in the range {10, 7.5, 5, 2.5, 1, 0.75, 0.5, 0.1}. Performance is evaluated using the perplexity (PPL) metric for the word level datasets and bits-per-character (BPC) metric for the character level datasets. The detailed experiment settings including the description of the datasets and hyper-parameters are put into the Appendix A. 

5.3. RECURRENT CONVOLUTIONAL NEURAL NETWORK:

In this section, we optimize the Recurrent CNN(RCNN) for the image classification tasks (Liang & Hu, 2015) . The model structure is similar to the RNN. The main difference is that the full connection in RNN is replaced by convolution layer. 4We evaluate the algorithms on three benchmark image classification datasets, MNIST(LeCun & Cortes, 2010), CIFAR-10 and CIFAR-100 (Krizhevsky & Hinton, 2009) . For CIFAR-10 and CI-FAR100, we use (96,128,160) feature maps. Since MNIST is much easier, we use (32, 64, 96) feature maps. In general, We follow the experiment setup in (Liang & Hu, 2015) . Most of the hyper-parameters is same as previous work such as the network structure, weight decay, scheduling of learning rate, etc . The detailed experiment setting is put in Appendix A.3.

Table 2 shows the test classification error rate. We can see that optimizing RCNN in path space outperforms the conventional optimization algorithms SGD that in weight space consistently. 

6. CONCLUSION:

In this paper, we construct a new parameter space, called path space, for the RNN with ReLU activations and employ optimization algorithms in path space on benchmark experiments. To achieve this, we propose reduction graph method to deal with the difficulty brought by the parameter-sharing scheme, and propose a new Skeleton Method to identify the basis path for RNN in reduction graph efficiently. We conduct several experiments to verify that we can obtain significantly more effective RNN models in path space than using conventional optimization methods in the weight space. We would like to highlight the following conclusions: (1) Basis paths are crucial in the ReLU RNN.

We have proved that the values of basis paths serve as a sufficient representation of ReLU RNN.

Compared with the weights, the values of basis paths are positively rescaling-invariant, which match the PSI property of the output of ReLU RNN. Moreover, the number of basis paths is even less than the number of weights of the recurrent neural network. ( 2) Reduction graph is a powerful tool.

Reduction graph and its paths are introduced to simplify the identification of basis paths in ReLU RNN. It is a novel technique specially designed for RNN models.

(3) Optimizing ReLU RNN in path space is efficient. The algorithm G-SGD can achieve better performances than SGD with only a little extra computational cost. In the future, we will investigate the power of path view on other neural network structures such as LSTM and Transformer.

Performance is evaluated using the perplexity (PPL) metric for the word level datasets and bits-percharacter (BPC) metric for the character level datasets. The code of this experiment is adapted from the Salesforce Language Model Toolkit(salesforce ( 2019)).

The implementation is based on the Salesforce Language Model Toolkitsalesforce (2019) and we only change the optimizer.

A.3 RECURRENT CNN EXPERIMENT:

The CIFAR-10, CIFAR-100 and MNIST datasets are downloaded from the official site and then normalized by subtracting the mean value and dividing the standard deviation of the training set. The code of this experiment is based on this repository (Github, 2019) which is consistent with the previous paperLiang & Hu (2015) .

The RCNN network has 5 layers. There is one RCNN block in each layer and each RCNN block unfolds 3 times. As many recent code-base suggested, we using BN hear instead of LRN (Github, 2019; 2018) and removing dropout layers except the last linear layer (Github, 2019) . We show all the testing error rate in the table 4 .

The initial learning rate of both baseline and our method is searched in then range { 0.5, 0.2, 0.1, 0.07, 0.05, 0.01 } and then divided by 10 after 1/2, 3/4 and 7/8 epoch of all epochs. Momentum parameter is set to 0.9. Weight decay is set to 0.0001. Dropout rate is set to 0.5. Batch size is 64. Each experiment is run for 200 epoch and the test accuracy of the last epoch is reported. In this section, we review the process of Inverse-Chain-Rule and Weight-Allocation designed in the work Meng et al. (2018) and apply it to RNN.

Denote the non-skeleton weight as w ns and the skeleton weight as w s . We select the skeleton weight in the first layer as special skeleton weights and denote as w s0 and the non-skeleton weight in this layer is denoted as w ns0 . Denote all the basis path set as P b . Denote the basis path that pass the non-skeleton weight w ns as p ns and the basis path that compose by all-skeleton weight and pass the skeleton weight w s0 as p s0 . Note that there is a 1-1 mapping between non-skeleton weights and the basis paths in set P ns . Similarly, there is also a 1-1 mapping between skeleton weights w s0 and the basis paths in set P s0 . Here, for simplicity, we can view recurrent weight as a non-skeleton weight w ns . Thus P b2 ∈ P ns .

Inverse-chain-rule calculates the gradient with respect to basis paths according to the following equation:

EQUATION

By solving this equation, the gradients w.r.t basis paths can be derived as:

For v pns we have: We write the result into matrix manipulation forms and we can derive line 6 in Algorithm 2 in the main paper. The detailed derivation is put at the end of this section for clarity.

Weight-Allocation projects the update on basis paths back to the update of weight. Notation C s0 is the production of weights in path p s0 except for w s0 . Specifically, v ps 0 = w s0 • C s0 . Notation D ns is the production of weights in path p ns except for w ns . Specifically, v pns=wns•Dns . We have:

EQUATION

Solving this equation, the update rule for weight can be derived as:

EQUATION

EQUATION

w t+1 ns 0 = w t ns 0 -ηt • ∂L ∂w t ns 0 (12)

We write the result into matrix manipulation forms and we can derive line 9-10 in Algorithm 2 in the main paper. The detailed derivation is put at the end of this section for clarity.

We give the derivation details in the following:

According to the chain rule, we have: Eq. ( 20) and ( 22) is the definition of the basis path. Note that we only update the skeleton weight in the special layer w s0 and the non-skeleton weight w ns . Therefore, Return the size of matrix w w.sum(0)

Return sum of the matrix w along axis 0. If w is a weight matrix of NN , this operation sums the weight that connect to the same input and returns the vector with the same size as input node size.

B.3 COMPUTATIONAL COST:

Here, we provide the training time per epoch of our algorithm and the baselines in Table 6 . We implement all experiments on a single GPU. It shows that the real training time of G-SGD is also comparable with that of plain SGD. For convolutional layer, we view one feature map as a hidden node as in MLP structure. So we select one of the edges in the convolutional kernel that connect two feature maps in two layers as the skeleton weights. Thus the Mask-Matrix-Constructor algorithms can construct the mask matrix by selecting one element in one convolutional weight matrix that connects one input feature maps and one output feature maps as 1.

C PROOF OF THEOREMS:

C.1 PROOF OF THEOREM 1

To ease the presentation of the proof, we give the path a vector representation as follows. We index the edges in the reduction graph of neural network as e 1 , • • • , e i , • • • , e m . We define the counting vector for a path p either in the directed graph or in the reduction graph as

C p = (c pe 1 , • • • , c pe m )

, where c pe i is equal to the times that path p passes the edge e i . Please note that, if path p is in the directed graph, c pe i may be larger than 1 for some i because of weight sharing. Theorem 1 is proved if we show the counting vector of any path in the directed graph is a linear combination of the counting vectors of the paths in the reduction graph.

Consider an arbitrary path in the directed graph with counting vector C p = (c p1 , • • • , c pm ). For each edge e i , we choose a path in reduction graph that contains this edge, which is denoted as p(i) and its counting vector is C p(i) . We claim that the term ei∈p c pi • C p(i) -C p equals to the linear combination of counting vectors of paths in reduction graph. Without loss of generality, we suppose that p contains nodes and edges

N I 1 e1 → N H 2 e2 → • • • e k → N O k+1

, where e 1 is the edge connecting an input node and a hidden node and e k is the edge connecting a hidden node and an output node, and other edges are recurrent edges. For edge e j , j = 3, • • • , k -1, we choose a path

N I ij ei j → N H j-1 ej → N H j ez j → N O

zj that contains e j , where i j denotes the index of selected edge in the input-to-hidden layer for e j and z j denote the index of selected edge in the hidden-to-output layer for e j . For edge e j-1 , we choose a path N

I ij-1 ei j-1 → N H j-2 ej-1 → N H j-1 ez j-1 → N O zj-1

that contains e j-1 . Furthermore, for the edge e 1 , we select an edge connecting with e 1 at the hidden-to-output layer, denoted as e z1 . And for the edge e k , we select an edge connecting with e k at the input-to-hidden layer, denoted as e i k . We claim that the edge e ij and edge e zj-1 compose a path in reduction graph because they both connect node N H j-1 . This claim is right for all j = 2, • • • , k. Thus the linear combination of the paths that contain e ij and e zj-1 equals to ei∈p c pi • C p(i) -C p . 

→ N H,(1) 3 → N H,(2) 3 → N H,(3) 3 → N H,(4) 3 → N O,(4) 4

whose counting vector is C p = (1, 0, 3, 1, 0). It can be calculated as C p = 1 • (1, 0, 0, 1, 0) + 3 • (1, 0, 1, 1, 0) + 1 • (1, 0, 0, 1, 0) -4 • (1, 0, 0, 1, 0), where (1, 0, 0, 1, 0) and (1, 0, 1, 1, 0) are paths in the reduction graph.

C.2 PROOF OF THEOREM 2:

Recall the definition of the activation status a p (w; x) = N H,t i ∈p I(N H,t i (w; x) > 0), We will first prove that every indicator function of the node can be calculated by the values of paths. Then using the definition of the basis paths we can know that the values of paths can be calculated using the values of basis paths. Combine the conclusion above, we can prove the theorem.

Denote the weights connect the node with index i and the node with index j as W i ij , consider the hidden node N H,(t) j , we define the value of the node as the sum of all incoming value before the activation and denote it using lower case letter o is the pre-activated hidden output of time-step t -1. The corresponding weights W i ji and W r jj is in the W i and W r respectively the same as the notations in preliminaries. For simplicity, we denote the activation status of nodes as a We prove the theorem by using the induction method. Specifically, we will prove that the value of hidden node can be expressed by the following formulation. And thus the activation of the hidden node can be calculated by the value of path and the sign of skeleton weights in matrices W o , which we call it outgoing skeleton weight and denote it as w s . 

where F (x, v p , sign(w s )) is a function that only related on the input x, values of paths v p and the signs of outgoing skeleton weights w s . W o kj is also an outgoing skeleton weight that connect to the hidden node o H j and o O k . Firstly, we prove Equation 24 is satisfied in time-step 1. For an arbitrary hidden node with index j Then, using induction method, the induction assumpution is that o t-1 can be represented by the function of path value divided by the weights on the skeleton edges, The second term in third equality is from the induction assumption. The fourth equality is the definition of activation function. It is obvious that for arbitrary functions F (x, v p , sign(w s )),

W o kj W o k j

W r jj F (x, v p , sign(w s )) is also a function of input, value of paths and the sign of weight on skeleton edges. The reason is that the paths in function F both contain the weight W O k j . And an arbitrary value of path in RNN multiplies the weight on the recurrent edge is also the value of a path.

So we prove that if the equation 24 is satisfied in time-step t -1, it will also be satisfied in time-step t. And the equation is proved through the induction method.

Next, recall the definition of the activation status of paths: a p (w; x) = N H,t i ∈p I(o H,t i (w; x) > 0). By using Equation ( 24), we can know that the sign of o H,(t) j can be calculated using the value of basis paths given the sign of weights on skeleton edges. Combine it with that the value of path can be calculated by the value of basis path, we can easily prove the theorem.

C.3 PROOF OF THEOREM 3:

As we mentioned, the structure of ReLU RNN can be decomposed into a feedforward part and the recurrent edges part. For the feedforward part, the number of basis paths has been proved to be #(weights)-#(hidden nodes) in Meng et al. (2018) . According to our Skeleton Method for RNN, each recurrent weight can only be contained in one basis paths. Thus, the total number of recurrent neural networks is #(weights of MLP)+#(recurrent weights)-#(hidden nodes). Thus, we finish the proof. 

:

Here, diag(a1, • • • , a h ) denotes a diagonal matrix whose diagonal elements are a1, • • • , a h .

The weights are shared for all time-steps, so we don't use the subscript of time-step t in the weight matrices.

Operations such as shape(•), zero like, .sum(0) in Alg. 1 and 2 is similar to the function in the numpy packages of python language. The exact definition are listed in Appendix B.2.

Path-SGD algorithm is not implemented to CNN in its original papers(Neyshabur et al., 2015a; 2016), and it is not clear how to extend it to CNN. Thus we do not use Path-SGD as a baseline for experiments on RCNN.

Figures and Tables:

Figure 1: DAG of RNN

) αj for any w ∈ W, where z denotes the cardinal number of P b , i.e., z = |P b |; (2) among all the sets that satisfy property (1), P b has the smallest cardinal number.

Figure 2: Reduction Graph of RNN

Figure 3: (a) An example of reduction graph. (b) An example of Skeleton Method

2. The results are shown in Figure 4. The perplexity of G-SGD algorithm on the PTB and Wikitext-2 datasets are lower than that of Path-SGD and SGD. The bits-per-character metric of G-SGD algorithm on the PTB-c and enwik8 data sets are significantly lower than that of Path-SGD and SGD. It means that G-SGD are more effective than Path-SGD and SGD, which shows the superiority of optimization RNN with ReLU activations in the path space.

Figure 4: Test metric for language tasks. The number means PPL in PTB and Wikitext-2 datasets. The number means BPC for PTB-c and enwik8 datasets.

For the non-skeleton weight not in the special layer,

Figure 5: An example of reduction graph of RNN

where I is the indicator function. We use notation sign(•) to denote the sign function(sign(a) = 1 if a > 0 and sign(a) = -1 if a < 0)

o H,(t) j = F (x, vp, sign(ws)) • 1 W o kj ,

(x, vp, sign(ws)) + j F (x, vp, sign(ws))I sign(W o kj ) • F (x, vp, sign(ws)) (x, vp, sign(ws))

Figure 6: Test Error Rate for Sequential MNIST experiments. x axis is the epoch index, y axis is the Error Rate(%)

The hidden nodes size of ReLU RNN are 100. We search the best learning rate in a reasonable range. The size of minibatch is 64. More detailed experimental settings can refer to the Appendix A.1.Every experiment is run 3 times with different random seeds. The averaged test accuracy is shown in the Table1. It can be observed that the classification error rates of G-SGD algorithm on the tasks are significantly lower than that of Path-SGD and SGD. It indicates that optimizing RNN with ReLU activations in the path space can consistently obtain more effective RNN models for all settings. Averaged testing classification error rate(%) of the sequential MNIST experiment.

Table content: <table><tr><td/><td>G-SGD</td><td>SGD</td><td>Path-SGD</td></tr><tr><td>Non-Permutation</td><td colspan="3">sMNIST-28 1.50 ± 0.03 1.59 ± 0.06 1.75± 0.03 sMNIST-98 2.70 ± 0.09 3.07 ± 0.18 2.99± 0.08</td></tr><tr><td>Permutation</td><td>sMNIST-28 3.80± 0.09 sMNIST-98 5.42± 0.05</td><td colspan="2">4.19± 0.13 4.12 ± 0.24 5.70± 0.16 5.47± 0.03</td></tr><tr><td>5.2 LANGUAGE MODELING</td><td/><td/></tr></table>

Classification error rate(%) of experiments on recurrent convolutional neural networks.

Table content: <table><tr><td/><td/><td>MNIST</td><td/><td/><td>CIFAR-10</td><td/><td/><td>CIFAR-100</td><td/></tr><tr><td/><td colspan="4">RCNN-32 RCNN-64 RCNN-96 RCNN-96</td><td>RCNN-128</td><td colspan="4">RCNN-160 RCNN-96 RCNN-128 RCNN-160</td></tr><tr><td>G-SGD (our method)</td><td>0.36</td><td>0.31</td><td>0.31</td><td>7.38</td><td>6.61</td><td>6.52</td><td>31.52</td><td>29.64</td><td>28.78</td></tr><tr><td>SGD</td><td>0.38</td><td>0.37</td><td>0.39</td><td>7.47</td><td>7.53</td><td>7.54</td><td>33.34</td><td>31.51</td><td>29.67</td></tr></table>

Classification error rate(%) of experiments on recurrent convolutional neural networks.

Table content: <table><tr><td/><td/><td>MNIST</td><td/><td/><td>CIFAR-10</td><td/><td/><td>CIFAR-100</td><td/></tr><tr><td/><td colspan="9">RCNN-32 RCNN-64 RCNN-96 RCNN-96 RCNN-128 RCNN-196 RCNN-96 RCNN-128 RCNN-196</td></tr><tr><td>G-SGD (our method)</td><td>0.36</td><td>0.31</td><td>0.31</td><td>7.38</td><td>6.61</td><td>6.52</td><td>32.02</td><td>29.64</td><td>28.78</td></tr><tr><td>SGD ( Liang(2015) )</td><td>0.42</td><td>0.32</td><td>0.31</td><td>7.37</td><td>7.24</td><td>7.09</td><td>34.18</td><td>32.59</td><td>31.75</td></tr><tr><td>SGD (our implementation)</td><td>0.38</td><td>0.37</td><td>0.39</td><td>7.47</td><td>7.53</td><td>7.54</td><td>33.34</td><td>31.51</td><td>29.67</td></tr><tr><td colspan="2">B ALGORITHMS</td><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td colspan="4">B.1 DERIVATION OF THE ALGORITHM</td><td/><td/><td/><td/><td/><td/></tr></table>

According to the skeleton method, each non-skeleton weight w ns can only exists in one basis path p ns . Besides, if w ns not in p, Finally, we project the new basis path value into the weight. Notation C s0 is the production of weights in path p s0 except for w s0 . Specifically, v ps 0 = w s0 • C s0 . Notation D ns is the production of weights in path p ns except for w ns . Specifically, v pns = w ns • D ns .

Table content: <table><tr><td colspan="17">Above equation is right according to the gradient decent update rule of the path value v t+1 p</td><td>=</td></tr><tr><td>v t p -η t • ∂L ∂v t p</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td/><td/><td/><td colspan="3">w t+1 s 0 w t s 0</td><td>•</td><td/><td colspan="3">C t+1 s 0 C t s 0</td><td/><td>=</td><td>v t+1 ps 0 ps 0 v t</td><td/><td>(20)</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="3">w t+1 s</td><td/><td colspan="4">= R(v t ps 0 ) • w t s 0 •</td><td>C t s 0 s 0 C t+1</td><td>(21)</td></tr><tr><td/><td/><td/><td/><td colspan="3">w t+1 ns w t ns</td><td>•</td><td colspan="4">D t+1 ns D t ns</td><td/><td>=</td><td>v t+1 pns pns v t</td><td/><td>(22)</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td colspan="8">w t+1 ns = R(v t pns ) • w t ns •</td><td>D t ns ns D t+1</td><td>(23)</td></tr><tr><td>∂L ∂wns</td><td>=</td><td colspan="2">p∈P b</td><td colspan="3">∂L ∂vp</td><td>•</td><td colspan="4">∂vp ∂wns</td><td colspan="2">=</td><td colspan="2">∂L ∂vp ns</td><td>•</td><td>∂vp ns ∂wns</td><td>(13)</td></tr><tr><td>∂L ∂ws 0</td><td>=</td><td colspan="2">p∈P b</td><td colspan="3">∂L ∂vp</td><td>•</td><td colspan="4">∂vp ∂ws 0</td><td colspan="2">=</td><td>∂L ∂vp s</td><td>•</td><td>∂vp s ∂ws 0</td><td>+</td><td>p∈P b /ps</td><td>∂L ∂vp</td><td>•</td><td>∂vp ∂ws 0</td><td>(14)</td></tr><tr><td/><td/><td/><td colspan="14">∂vp ∂wns = 0 Thus Eq. (13) is right Thus, we can derive the gradient of</td></tr><tr><td>the basis path as:</td><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/></tr><tr><td/><td colspan="3">∂L ∂vp ns</td><td>=</td><td colspan="5">∂L ∂wns</td><td>/</td><td colspan="4">∂vp ns ∂wns</td><td/><td>(15)</td></tr><tr><td/><td colspan="3">∂L ∂vp s 0</td><td>=</td><td colspan="6">  ∂L ∂ws 0</td><td colspan="2">-</td><td colspan="3">p∈P/ps 0</td><td>∂L ∂vp</td><td>•</td><td>∂vp ∂ws 0</td><td>  /</td><td>∂vp s 0 ∂ws 0</td><td>(16)</td></tr><tr><td>Let s[w s0 ] = p∈P/ps 0</td><td colspan="2">∂L ∂vp •</td><td colspan="3">∂vp ∂ws 0</td><td colspan="11">. We can then calculate the update ratio for the basis paths as:</td></tr><tr><td>R(v t ps 0 )</td><td colspan="2">v t+1 ps 0 v t ps 0</td><td colspan="6">= 1 -ηt</td><td colspan="4">∂L ∂v t ps 0 v t ps 0</td><td colspan="4">= 1 -ηt(</td><td>∂L ∂w t s 0</td><td>-s[ws 0 ])/(</td><td>∂v t ps 0 ∂w t s 0</td><td>• v t ps 0 )</td><td>(17)</td></tr><tr><td>R(v t pns )</td><td colspan="2">v t+1 pns v t pns</td><td colspan="6">= 1 -ηt</td><td colspan="4">∂L ∂v t pns v t pns</td><td colspan="4">= 1 -ηt</td><td>∂L ∂w t ns</td><td>/(</td><td>∂v t pns ns ∂w t</td><td>• v t pns )</td><td>(18)</td></tr><tr><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td/><td>(19)</td></tr></table>



Table content: <table><tr><td>: Notations</td></tr></table>

Training Time of 1 epoch (seconds) in different experiments

Table content: <table/>

Averaged testing classification error rate(%) of the sequential MNIST experiment.

Table content: <table><tr><td/><td>G-ADAM</td><td>ADAM</td></tr><tr><td>Non-Permutation</td><td colspan="2">sMNIST-28 1.50 ± 0.07 1.72 ± 0.07 sMNIST-98 2.49 ± 0.08 3.10 ± 0.10</td></tr><tr><td>Permutation</td><td>sMNIST-28 3.73± 0.05 sMNIST-98 5.42± 0.1</td><td>4.06± 0.1 5.57± 0.09</td></tr></table>

Peer review (iclr2020):
Motivation: The authors motivate their work with the observation that neural networks with ReLU activations are positively scale invariant. Recent works have proposed parameter space called path space to leverage this insight for feedforward as well as CNNs, but this is not really the case for Recurrent Neural Networks (due to the recurrent structure and the parameter sharing). Contribution: The authors construct path space for RNN to employ optimization algorithms in path space. The intuition is to leverage the reduction graph of RNN to removes the influence of time-steps. Reduction graph only contains information about the weight connectivity patterns and not about the time steps. Hence, the number of paths in reduction graph is fixed (i.e independent of number of time steps. Clarity: The clarity of the paper can be improved a bit. It might be useful to give a *top-down* introduction somewhat at the end of introduction. Experimental Results: In order to validate the proposed method, the authors conduct experiment on sequential MNIST tasks, as well as language modelling task. The results are a bit weak in general, and improvements are very minor over the vanilla RNN baseline. It might be interesting to compare to other baselines as in PathSGD paper.