Title: INTERPRETABLE NETWORK STRUCTURE FOR MODEL-ING CONTEXTUAL DEPENDENCY

Abstract: Neural language models have achieved great success in many NLP tasks, to a large extent, due to the ability to capture contextual dependencies among terms in a text. While many efforts have been devoted to empirically explain the connection between the network hyperparameters and the ability to represent the contextual dependency, the theoretical analysis is relatively insufficient. Inspired by the recent research on the use of tensor space to explain the neural network architecture, we explore the interpretable mechanism for neural language models. Specifically, we define the concept of separation rank in the language modeling process, in order to theoretically measure the degree of contextual dependencies in a sentence. Then, we show that the lower bound of such a separation rank can reveal the quantitative relation between the network structure (e.g. depth/width) and the modeling ability for the contextual dependency. Especially, increasing the depth of the neural network can be more effective to improve the ability of modeling contextual dependency. Therefore, it is important to design an adaptive network to compute the adaptive depth in a task. Inspired by Adaptive Computation Time (ACT), we design an adaptive recurrent network based on the separation rank to model contextual dependency. Experiments on various NLP tasks have verified the proposed theoretical analysis. We also test our adaptive recurrent neural network in the sentence classification task, and the experiments show that it can achieve better results than the traditional bidirectional LSTM.

1. INTRODUCTION:

Language modeling is a fundamental topic in natural language processing (NLP), and neural network based language models have achieved great success in many NLP tasks (Cheng et al., 2016; Ko et al., 2017; Peters et al., 2018a; b) . For instance, ELMo (Peters et al., 2018b) , as a contextualized word representation model, significantly improves the results in a broad range of NLP problems. One important reason is that the recurrent network and its variants can capture the long-range/shortrange contextual dependencies among terms in a text (Graves, 2013; Yang et al., 2017; Peters et al., 2018a) . Researchers are trying to empirically explain the relation between network hyperparameters (such as the number of layers) and the ability to represent contextual dependencies (Karpathy et al., 2015; Peters et al., 2018a) . However, the theoretical explanations are relatively insufficient.

Recently, Peters et al. (2018a) investigated the effect of network depth on the range of contextual dependencies represented in neural language models. Empirical evidences show that the bottom layer can capture short-range dependencies, while deep layers are more capable to represent longrange dependencies. It is observed that different NLP tasks require different layers of pre-trained embeddings in (Peters et al., 2018a) . Specifically, for the coreference resolution task requiring global syntax structures, long-range dependencies among words should be modeled, and thus embeddings vectors in deep layers are more useful than those in bottom layers. On the other hand, for the named entity recognition task, it requires relatively local syntax to be modeled, and then the embeddings in bottom layers can work well (Peters et al., 2018a) . However, while the empirical observations are insightful, it is challenging to theoretically derive the quantitative relation between the neural network structure and the representation ability for contextual dependency.

Our work is inspired by these studies on the relation between neural network and tensor network (Cohen & Shashua, 2016a; Levine et al., 2017) . These studies have shown that the correlation between input regions of an image can be calculated by the separation rank. Based on such a measurement and its analysis, the structure of convolutional neural network can be explained in a tensor space (Cohen & Shashua, 2016a) . Levine et al. (2017) further utilize the separation rank to measure the long-term memory capacity and analyze its relation to the network depth, by mapping the recurrent neural network to a tensor network.

In language modeling tasks, tensors have been used for text representation and language modeling (Liu et al., 2005; Socher et al., 2013; Pennington et al., 2014; Qiu & Huang, 2015) . Recently, the tensor network (as a method to model high-order tensors) has been adopted in language modeling, and a tensor space language model (TSLM) has been proposed (Zhang et al., 2019) . TSLM was proved to be a generalization of the n-gram and RNN language models. TSLM bridges the gap between the tensor network and language modeling, and then paves the way for the further theoretical analysis of neural language modeling in tensor space.

In this paper, we aim to provide quantitative analyses for explaining the mechanisms of modeling contextual dependencies in recurrent neural network (RNN) and its variants (e.g., LSTM, EMLo). We first define the concept of separation rank in the language model process, and show that this separation rank can measure the dependencies in a sentence. We further derive the lower bound of the separation rank in the tensor space language model, which is a combination number of network depth and network width, etc.

We then provide a lower bound analysis for the separation rank defined in language modeling. It shows that along with the increasing number of network layers L (representing the network depth), the lower-bound can be increased by an exponential level, while increasing the number of hidden units R (representing the network width) can improve the lower-bound by a linear level. The lower-bound is associated with the separation rank, which measures the degree of the contextual dependencies.

The method of Adaptive Computation Time (ACT) (Graves, 2016) allows recurrent neural networks to learn how many computational steps (i.e., the depth) to takes on an input. However, this method implies an assumption that the states and outputs are approximately linear, and it lacks a theoretical interpretation. The effect of depth on the ability of neural network to model contextual dependencies is more direct, as mentioned above (Levine et al., 2017; Zia & Razzaq, 2018) . For a natural language processing task, it is a challenge task to get an adaptive neural network structure (i.e., the number of layers). Inspired by this work (Graves, 2016) , we design a bidirectional adaptive recurrent neural network based on the guidance of the separation rank in language model. In order to verify our theoretical analysis, we carry out various NLP tasks that reflect different degrees/ranges of contextual dependencies. The experimental results can explain the effect of network depth (represented by network layers) on the contextual dependencies modeled in the neural language models. In addition to the network depth, our experiments show that increasing the network width (i.e., the number of the hidden units) can also increase the modeling ability for both long-range and short-range contextual dependencies. Moreover, increasing the network depth can be more effective than increasing the network width, on the tasks requiring long-range dependency. Furthermore, in order to search a minimum layers and effective modeling contextual dependency, we train the new adaptive neural network on the sentence classification task. The results show that our model achieves better results than a fixed depth recurrent neural network (i.e., BiLSTM).

2. PRELIMINARIES:

We first briefly introduce the basic language model, as well as the recently developed tensor space language model (TSLM) (Zhang et al., 2019) , which is proved to be a generalized approach to both n-gram and recurrent language models.

2.1. BASIC LANGUAGE MODEL:

Given a sentence s of n words denoted as (w 1 , w 2 , . . . , w n ), a language model computes the joint probability of a sentence. Its joint probability can be written as:

EQUATION

N -gram language model computes the joint probability of the sentence by calculating the probability of a word w i given the history (w 1 , . . . , w i-1 ).

2.2. TENSOR SPACE LANGUAGE MODEL:

Recently, a Tensor Space Language Model (TSLM) (Zhang et al., 2019) was proposed, which can consider all the combinatorial dependencies among words through the tensor product. Tensor product is a fundamental operator in tensor analysis, denoted by ⊗, which can map two low-order tensors to a high-order tensor. It is proved that TSLM is a generalization of both n-gram (when the word vectors are represented with one-hot vectors) and a recurrent language modeling process (when the word vectors are represented with a low-dimensional dense word vector).

In TSLM, for a sentence S = {w 1 , . . . , w n } with length n, each word w i can be represented by a m-dimension word vector w i (i ∈ {1, . . . , n}). The basic formulation of TSLM can be written as:

EQUATION

where A d1,...,dn are the entries from tensor A which is essentially rank-one tensor, i.e., A = w 1 ⊗ . . . ⊗ w n . T d1,...,dn are entries from tensor T , which is a higher rank tensor. T can encode the network parameters, e.g., hidden layers matrix and states matrix, after TSLM is reduced to a recurrent language modeling architecture.

3. SEPARATION RANK AS MEASUREMENT FOR CONTEXTUAL DEPENDENCY:

In this section, our aim is to define the separation rank in TSLM. In Sec. 3.1, we first describe the basic ideas for the contextual dependency and expose the variables which are related to the contextual dependencies. Then, we define the separation rank in tensor space language model in Sec 3.2. For better readability, we put detailed proofs in supplementary appendices.

3.1. BASIC IDEAS FOR CONTEXTUAL DEPENDENCY:

The separation rank measures how far a function is from being separable (Cohen & Shashua, 2016b) . p(w n 1 ) in Eq. 1 can be considered as the probability density function, given a sentence S = (w 1 , . . . , w n ), where n is the number of words. Without loss of generality, we can split a sentence into two disjoint context subsets, S 1 = (w 1 , . . . , w i ) and S 2 = (w i+1 , . . . , w n ), where i is a position for separating a sentence to S 1 and S 2 . If S 1 and S 2 is independent. The function of joint probability in Eq. 1 can be written as:

EQUATION

For considering the situation when S 1 and S 2 are not independent, we give the function as follows:

EQUATION

where y j is the conditional variable, y i ∈ Y, and Y={y 1 , . . . , y K }. When K is equal to 1, Eq. 4 can be reduced to Eq. 3, since p(y 1 ) = 1.

In language modeling, if K is equal to 1, then p(w n 1 )=p(w i 1 )p(w n i+1 ), which means that there is no dependency between two context pieces S 1 and S 2 . The higher K is, the further two context pieces (S 1 and S 2 ) are from being separable, meaning that S 1 and S 2 has stronger dependency.

3.2. SEPARATION RANK IN TSLM:

In this section, we define the separation rank based on K in TSLM. First, we consider p(w n 1 ) in Eq. 2 as a probability function. Then, the separation rank is defined on the factorization of p(w n 1 ). Such a factorization is carried on the matricization of weight tensor T in Eq. 2. The matricization process is to put the entries from a tensor into a matrix. It turns out that the factorization of p(w n 1 ) is reduced to the factorization of of the matrix form of the tensor T , as shown in the following claim.

Claim 1 The factorization of p(w n 1 ) in Eq. 2 can be obtained by the Singular Value Decomposition (SVD) on the matrix T (S1,S2) . After the decomposition, the matrix T (S1,S2) is written as follows:

T (S1,S2) = K j=1 λ j v j u T j (5)

where K is number of non-zero singular values.

Proof 1 Our proof can be found in Supplementary Appendices A.1 submitted.

In Eq. 4, each different position i corresponds to different partitions (S 1 , S 2 ) and consequent matricizations of tensor T . Thus there could be different decomposition and different numbers of non-zero singular values. In order to find a measurement for contextual dependency, we define the separation rank as the minimum value of K in TSLM. The claim is given as follows.

Claim 2 Suppose a sentence S=(w 1 , . . . , w n ) can be split into two disjoint subset S 1 =(w 1 , . . . , w i ) and S 2 =(w i+1 , . . . w n ), where i ∈ {1, . . . , n -1} is any position. The separation rank of function in Eq. 2 in tensor space language model is formulated as:

EQUATION

Proof 2 Our detailed proof can be found in Supplementary Appendices A.2 submitted.

In general,the separation rank in TSLM sep (S1,S2) (p(w n 1 ))1 have been defined in Eq. 6.

4. LOWER BOUND ANALYSIS OF SEPARATION RANK FOR RECURRENT NEURAL NETWORK STRUCTURE:

In this section, by providing the lower bound of the separation rank in TSLM, we investigate the interpretable mechanism in recurrent neural network language modeling. Specifically, we analyze the relation between the separation rank (reflecting the contextual complexity) and the network architecture (e.g., network depth and width). Recall that tensor space language model (TSLM) can derive a recurrent language modeling process from via the tensor decomposition of high-order tensors (Zhang et al., 2019) . Based on the above analysis, we will establish the relation between separation rank in TSLM (see Sec.3.2) and parameters of recurrent neural language models.

Different partition position i in Eq. 4 corresponds to different partition (S 1 , S 2 ) in Eq. 6. If the partitions (S 1 , S 2 ) are different, the values of K will be different. Without loss of generality, we set an equal partition, i.e., i = n 2 . When a sentence is partitioned equally, K value in Eq. 6 is larger than the actual separation rank since it is the minimal K.

Then, based on the equal partition criteria, step by step, we propose our theoretical results regarding the lower bound of the separation rank. Such a lower bound is expected to reflect the relation between the ability for modeling contextual dependencies and the model structure (e.g., network depth and width) in the language modeling process. Specifically, if a sentence is modeled by a recurrent network architecture, the lower bound of the separation rank in TSLM can be computed by some parameters (i.e., hidden units, the number of layers and the number of words in a sentence) in recurrent network architecture. In the following, we first show such quantitative result when the number of layers is one (i.e., L = 1), and then we provide our findings when L > 1.

Claim 3 In tensor space language model (TSLM), when the number of layer is one (i.e., L=1,) the separation rank in TSLM can be given as follows:

EQUATION

)

where R is the number of hidden units, (S 1 , S 2 ) is the case of equal partition.

Proof 3 The detailed proof can be found in Supplementary Appendices A.3 submitted. In order to show the influence of network depth, we need to further extend the tensor space language model using recurrent network with deep layers, i.e., L > 1. We derive the lower bound, i.e., the separation rank in TSLM in case of the L ≥ 2. Further details will be expound in Supplementary Appendices A.4. The lower bound will be shown as follows:

𝑥𝑥 𝑤𝑤 𝑡𝑡-1 𝑤𝑤 𝑡𝑡 𝑊𝑊 𝐼𝐼 𝑊𝑊 𝐼𝐼 𝑆𝑆 𝑡𝑡-1 1 𝑆𝑆 𝑡𝑡 1 𝑆𝑆 𝑡𝑡 2 𝑆𝑆 𝑡𝑡-1 2 ⋯ ⋯ 𝑆𝑆 𝑡𝑡-1 𝐿𝐿 𝑆𝑆 𝑡𝑡 𝐿𝐿 ⋯ 𝑆𝑆 𝑡𝑡-2 𝑊𝑊 𝐻𝐻 𝑊𝑊 𝐻𝐻 𝑊𝑊 𝐻𝐻 𝑆𝑆 𝑡𝑡-1 𝑊𝑊 𝐻𝐻 𝑊𝑊 𝐻𝐻 𝑆𝑆 𝑡𝑡 𝑊𝑊 𝐻𝐻 ⋯ ⋯ 𝑝𝑝 𝑡𝑡-1 𝐿𝐿 𝑝𝑝 𝑡𝑡-1 2 𝑝𝑝 𝑡𝑡-1 1 𝑝𝑝 𝑡𝑡 𝐿𝐿 ′ 𝑝𝑝 𝑡𝑡 2 𝑝𝑝 𝑡𝑡 1 𝑦𝑦 𝑡𝑡-1 𝑦𝑦 𝑡𝑡 𝑤𝑤 𝑡𝑡-1 𝑤𝑤 𝑡𝑡 ⋯ ⋯ Forward Backward ⊙ ⊙ ⊙ ℎ 𝑡𝑡-1 ℎ 𝑡𝑡 𝑎𝑎) 𝑏𝑏)

sep (S1,S2;i= n 2 )) (p(w n 1 )) ≥ min{ (R + F -1)! F !(R -1)! , m n 2 } (8)

where F = ( n/2 +L-2)! (L-1)!( n/2 )! ,R is the number of the hidden units, n is the number of words in a sentence, m is the dimension of a word vectors, L is the number of layers and (.)! is the symbol of factorial. (S 1 , S 2 ; i = n 2 ) is the case of equal partition. Next, we explore the relation between the lower bound and network parameters in detail. From Eq. 8, we can find that increasing both R and L can all improve the lower bound of separation rank in TSLM, i.e., the separation rank of a recurrent network language model will be increased. In order to illustrate this quantitative relationship between separation rank in TSLM and the recurrent network architecture (i.e., R and L). In Eq. 8, we see that if L was increased, it is observed that the lower bound will be increased by an exponential level. Through increasing R, the lower bound is increased by an linear level. Table 2 in supplementary appendices shows the numerical relationship.

5. BIDIRECTIONAL ADAPTIVE RECURRENT NEURAL NETWORK:

The effectiveness of neural network depth is an important research problem (Vinayakumar et al., 2017) . In Sec.4, the analysis of lower bound has described that increasing the number of layer can be more effective to improve the ability of modeling contextual dependency. In the processing for modeling a sequence of words, it is important to search an adaptive network depth. Under most circumstances, researches choose a fixed number of network layers L to model text. In this section, we describe how to construct an adaptive bidirectional recurrent neural network.

5.1. STRUCTURE CONSTRUCTION:

As in Eq. 6, we use a backward recurrent neural network language model as the right function p(w n i+1 |y j ). After that, a forward recurrent neural network network language model R f can be seen as the left function p(w i 1 |y j ). In experiment, we first train the backward function and get the hidden output. When it predicts the next words in forward language model, the hidden vectors from the backward process are used to multiply the hidden vectors from the forward process. In Figure 1 , we provide the diagram for the bidirectional adaptive RNN.

In Figure 1 a), w t-1 and w t are the inputs of word vectors. S t-2 , S t-1 and S t are some vectors from the outputs of hidden layer. Eq. 9 shows how to compute the S t . The displayed results show that the increasing of R is more helpful in short-range dependencies tasks (NER, Constituency Parsing and POS tagging), while the increasing of L is more effective for long-range dependencies tasks (WSD, Semantic classifier and Coreference Resolution), compared with the increasing of R.

S t = L i=1 p i t S i t (9)

where p i t is a scalar value and presents the probability value of S i t . The probability value can be computed as:

p i t = v T t S i t

, where v t is the trainable vector and can be initialized at the start of training. p i t is equal to the inner product of v t and S i t .

5.2. DYNAMIC HALTING:

Since we wish to explore a recurrent neural network with the minimum computational cost. Here, we first give out some basic assumptions. Since Eq. 16 is to get the minimal K, and increasing the depth L can improve the ability of modeling contextual dependency by an exponential level in Eq. 8, we can assume the computing of the depth L have a straight relation. Inspired by Adaptive Computation Time to dynamically halt changes in certain representations (Graves, 2016) , we design the condition of halting as follows. There are two kinds of halting conditional in our model. First, the times of computing is raised to the maximum number of calculations. Second, the steps of computing is satisfied as N (t)=min{l :

l i p i t ≤ 1 -} 2 .

6. EXPERIMENTS:

The about analysis has shown that improving R and L can improve the lower bound at different levels. The lower bound can imply the ability of recurrent neural network language models for modeling the contextual dependencies. For different NLP tasks, we need to choose the network structure with different modeling capabilities. We carry out six classification tasks and an intrasentence similarity experiment to verify our theoretical, respectively. Based on our analysis in the previous section, we have two hypotheses to be tested. (1) For tasks with short-range dependencies required, improving R can to some extent meet the modeling requirement, while improving the network depth L could be not necessary;

(2) For tasks requiring long-range dependencies, it is necessary to improve L to improve the ability of modeling dependencies.

These tasks be considered as classification tasks, for which the experimental results are described in Sec. 6.1.2. In language modeling process, LSTM is a commonly used recurrent network structure. Therefore, we mainly carried out experiments based on the structure of LSTM and its variants.

6.1.1. TESTING TASKS:



POS tagging:

We conduct experiments on the Wall Street Journal of the Penn Treebank dataset (PTB) (Marcus et al., 1993) We follow the language model augmented sequence taggers (TagLM) (Peters et al., 2017) .

Constituency parsing The Penn Treebank (Marcus et al., 1993) which contains phrase structure annotation is used in this application. We use the model named Reconciled Span Parser, which used the biLM representation.

Word Sense Disambiguation We follow this model (Kågebäck & Salomonsson, 2016 ) which used the bidirectional LSTMs architecture to compute a probability distribution over the possible senses corresponding to that word. The dataset of Senserval-2 (Edmonds & Cotton, 2001 ) is used.

Coreference Resolution An end-to-end coreference resolution model (Lee et al., 2017) has been proposed. We conduct experiments on the OntoNotes Release 5.0 benchmark (Pradhan et al., 2012) . Sentiment analysis We use the IMDB dataset (Maas et al., 2011) with two categories. We perform classification using a standard bidirectional LSTM with different hidden units and layers. The experimental setup of the six testing tasks can be found in Supplementary Appendices A.5.1.

6.1.2. EXPERIMENTAL RESULTS AND ANALYSIS:

The results on six NLP tasks are reported in Figure 2 . The results of short-range dependency and long-range dependency tasks are shown as the first row and second row, respectively.

In short-range dependency tasks, using 1-layer LSTM, its F 1 scores increase along the increasing of the number of hidden units R. There are similar experimental phenomenons when using 2-layer and 3-layer LSTMs. For each R, after L be increased, we observe that increasing F 1 score is not very obvious. These phenomena mean that for the increasing of F 1 , the increasing of R is more obvious than the increasing of L. Therefore, the results in the first row of Figure 2 verify our first hypothesis about short-range dependent tasks.

In the second row of Figure 2 , these trends of line charts show that the increasing for the number of hidden units R and the number of layers L can help to increase the F 1 score, while the effects of increasing L is more obvious, for long-range dependency tasks. The F 1 scores are the highest through using 3-layer LSTMs in long-range dependency tasks. In order to investigate different effects of increasing R and L on F 1 scores, we have detailed observations: When L is the largest (saying 3), the increasing of F 1 score is getting relatively slow along with the increasing of R, as shown in the results of semantic classifier (the middle in the second row in ( 2)). These phenomena and trends verify the second hypothesis. It is that increasing L can improve the network modeling ability more effectively than increasing R for long-range dependency tasks, In summary, R is more necessary to be increased for the short-range dependency tasks, while L is relatively more necessary to be increased in the long-range dependency tasks. Such experimental results and analysis are consistent with our theoretical analysis in Sec 4 and testing hypotheses in this section.

6.2. INTRA-SENTENCE SIMILARITY TASK:

In this section, we present a detailed empirical study about the effect of different network architecture (i.e., network width and the number of layers) on the representation ability of contextual word embeddings. Based on previous analysis in Sec. 4, our hypothese are as follows.

(1) Increasing R can improve the similarity between short-range words.

(2) Increasing L can improve the similarity between long-range words, (3)Increasing L is more effective for modeling the similarity between words than the increasing of R. 3 in Supplementary Appendices shows the intra-sentence contextual similarity among words in a sentence. The details of the experimental results and analysis will be discussed in Supplementary Appendices A.5.2.

1-Billion:



In this section, we test the bidirectional adaptive recurrent neural network on five text classification tasks. Text classification task is to refer to the process of automatically determining the text category based on the textual content under a given classification system. The Precision is used to evaluate the quality of the model. We test our model on MR, SST-2, CR, MPQA and TREC, respectively. The experiment results of this part is shown in Table 1 .

Table 1 shows the results about the adaptive network in sentence classification tasks. Results shows that the Adaptive-BiLSTM model achieves better accuracy (acc) in these datasets than BiLSTM. Our method achieves a larger improvement on the MPQA dataset. The adaptive bi-LSTM (bidirectional LSTM) and the model of adaptive LSTM achieve very close results.

7. CONCLUSION AND FURTHER WORK:

In this paper, we provide quantitative analysis for modeling contextual dependencies in recurrent language model and its variants. First, we define the separation rank in tensor space language model to measure the contextual dependencies of a sentence. Then, we analyze the lower bound of the separation rank in the recurrent neural network based LM. Based on the lower-bound analysis, we explain the quantitative relation between the value of separation rank and the network structure. For certain NLP tasks requiring different ranges of contextual dependencies, the lower-bound analysis will suggest different settings for the network depth and width. These suggestions based on the quantitative lower-bound analysis, are verified by various NLP tasks. In order to find the number of layers with both minimum cost and great performance results, we designed an adaptive RNN and verify the effectiveness of the method on text classification tasks.

In the future work, we can design feasible methods to calculate the contextual dependencies, and use such signals to design automatic language modeling approaches, which can be adaptively controlled for specific NLP tasks with certain requirement for the contextual dependencies. In addition, we will explore the use of tensor space to explain or advance the more recent language modeling approach, e.g., Transformer and BERT.

A SUPPLEMENTARY APPENDICES:

A.1 CLAIM 1

The factorization of p(w n 1 ) in Eq.2 (in paper) can be obtained by the Singular Value Decomposition (SVD) on the matrix T (S1,S2) . After the decomposition, the matrix T (S1,S2) is written as follows:

T (S1,S2) = K j=1 λ j v j u T j (10)

where K is the number of non-zero singular values.

Proof sketch of this claim:

In the tensor space language model, the input tensor is a rank-one tensor. To make it easy to understand, we assume that the word vector is one hot vector. The high order tensor A can be given by the operator of tensor product. Therefore, the tensor A is one hot tensor, which means that the tensor only have one element is 1 and other elements are zero. The basic form of tensor space language can be re-written an element T d1,...,dn from the tensor T . After that, the element can be consider a value in a matrix which can be given by the matricization of the tensor T . For all elements of the matrix, we can consider a method of SVD to get the value of K.

It would be helpful to understand if the definition of matricization was given. Therefore, There is the definition of matricization as follows.

Definition 1 Suppose T ∈ R m×...m is a tensor of order n, and let (S 1 , S 2 ) be a paratition of a set {1, . . . , n}, and S 1 and S 2 are disjoint subsets. The matricization of T denoted as T S1,S2 , is the m |S1| -by-m |S2| matrix holding the entries of T d1,...,dn is placed in row index 1

+ |S1| t=1 (d it - 1)m |S2|-t and column index 1 + |S2| t=1 (d jt -1)m |S2|-t

, where i ∈ S 1 and j ∈ S 2 .

Proof 4 . In subsection 2.2, Eq.2 is the basic form of tensor space language model. In Eq.2, A is a rank-one tensor A = w 1 ⊗ . . . ⊗ w n . We set each word as an one-hot vector. The tensor A is a tensor with only one entry being one and the other entries being zero. The Eq.2 can be rewritten as:

EQUATION

where

EQUATION

which means tensor A is an one-hot tensor, and index(w, V ) means the index of w in vocabulary V . k ∈ [n] also is denoted as k ∈ {1, . . . , n}. The probability of a sentence s is:

EQUATION

Therefore, the factorization of p(w n 1 ) in Eq. 2(in paper) can be achieved by two steps as follows. Firstly, the matricization of weight tensor T can be achieved by the matricization definition 1 and represented as T (S1,S2) . Secondly, we can perform singular value decomposition (SVD) on matrix T (S1,S2) .

T (S1,S2) = U SV T (14) Therefore, we can compute each element in the matrix T (S1,S2) , in other words, we can get every entry from tensor T and represent as:

EQUATION

where U v,d1,...,di is the element from the matrix U and the U v,d1,...,di is the element from the matrix V . Let V v,d1,...,di and U v,d1,...,di can be given by p(w i 1 |y v ) and p(w n i+1 |y v ), respectively. λ v is the singular value and is seed as p(y v ). We can represent Eq. 15 as Eq. 4 (in paper).

A.2 CLAIM 2:

Suppose a sentence S = (w 1 , . . . , w n ) can be split into two disjoint subset S 1 = (w 1 , . . . , w i ) and S 2 = (w i+1 , . . . w n ), the separation rank of function Eq. 2 by tensor space language model is formulated as following:

EQUATION

)

where K is the number of no-zero singular values, i is the position of separation.

Before proving the claim, we should give out a definition as reported in (Cohen & Shashua, 2016b) .

Definition 2 Let (I 1 , I 2 ) be a partition of ordered input indexes, i.e. I 1 and I 2 are disjoint subsets of [N ] whose is the set of all indexes. I 1 = i 1 , . . . , i |I1| where i 1 < . . . < i |I| , and similarly I 2 = j 1 , . . . , j |I2| where j 1 < . . . < j |J| . For a function h : (R s ) N → R, the separation rank w.r.t the partition (I 1 , I 2 ) is defined as follows:

sep(h; I 1 , I 2 ) := min{R ∈ N ∪ {0} : ∃g 1 . . . g R , g 1 . . . g R s.t. h(x 1 , . . . , x N ) = R v=1 g v (x i1 , . . . , x i |I 1 | )g v (x i1 , . . . , x i I 2 )}

It is the minimal number of summands that together give h, where each summand is separable and equal to a product of two function. g i and g i are the functions, g i :(R s ) |I1| and g i :(R s ) |I2| .

According to Eq. 15 and Definition 2, it will be easy to prove the result that the separation rank between two different inputs S 1 and S 2 is equal to the minimum value of K for different separation.

Proof 5 In Eq. 15, if we set the √ λ v U v,d1,...,di is equal to g v (w 1 , . . . , w i ) and √ λ v V v,d1,...,di is equal to g v (w i+1 , . . . , w n ). According to the definition 2, we can give the function of the separation rank in tensor space language model.

EQUATION

In a word, it is the minimal number of summands that together give p(w n 1 ), where each summand is separable and is equaltion to a product. After that, for different (S 1 , S 2 ) on a sentence, K is different. Therefore, we can define the minimum value of K as the separation rank in tensor space.

A.3 CLAIM 3:

In tensor space language model (TSLM), when the number of layer is one (i.e., L=1,) the separation rank in TSLM can be given as follows:

EQUATION

)

where R is the number of hidden units, (S 1 , S 2 ) is the case of equal partition, i.e., the position i in Eq.4(in paper) is equal to n 2 .

We can consider the RNN is a function y. In addition, the function can be re-written as a new form which is the sum of R groups of factor functions product. R is the number of hidden units, and also the separation rank in RNNLM. It meets the definition of separation rank in definition 2. holds for networks of depth L > 2, the form of which implies that the dependency capacity of deep recurrent networks grows combinatorially with the network depth:

seq(y L ) ≥ min{ R ( T /2 L-1 ) , m T /2 } L ≥ 2 (23)

where R is the number of hidden units, L is the number of layers. n is the number of words in a sentence. In language model, for easy to analysis the relation between separation rank and parameter from the recursive networks architecture. We set the R = m. We do not consider time series. Let's set the T in Eq. 23 to n. n is the numbers of words in a sentence. Considering the constraints of tensor dimensions, the maximum of TSLM separation rank is m T /2 . T is the temple in RNN, we suppose that it is the equal n, n is the length of a sentence. In the case where R and L are controllable, the value to the left of the minimum function 23 is less than the value to the right.

After that, we can get the relations as follow.

EQUATION

where the R is the number of hidden size, n is the number of words in a sentence, and L is the number of layers. Note that ! is the symbol of factorial.

A.5 EXPERIMENT A.5.1 EXPERIMENTAL SETUP Sec. 4 analyzed the relation between contextual dependencies and recurrent network architecture through L and R. Specifically, the lower bound of the recurrent language model modeling the sentence contextual dependencies will be increased by increasing L (L ∈ {1, 2, 3}) and R (R ∈ {100, 125, 150, 175, 200, 225, 250, 300}) in long-range/short-range dependency tasks. Recall that our hypotheses are: For short-range dependent tasks, increasing R is sufficient to reflect the network modeling ability, while for long-range dependent tasks, increasing L can improve the network modeling ability more effectually than increasing R. We test our hypotheses through the trend of F 1 score. F 1 is a mainly and common indicator of evaluation in these task.

A.5.2 ANALYSIS FOR INTRA-SENTENCE SIMILARITY TASK:

Our experiments focus on the changing trends of the similarity between word embeddings along with the increasing of R and L. This experiment is different from the experiments reported by Peters et al. (2018a) . They only consider the difference between upper layer and lower layer and do not consider the changing of network depth R.

Figure 3 shows the intra-sentence contextual similarity between all words in a sentence. In Figure 3 , we obtain several observations. When the number of hidden units R is fixed, we observe that the bright area is larger along with the increase of the number of layers L from 1 to 3. The bright area indicates the contextual dependency between words in our work. Relatively speaking, the larger the bright region is, the stronger the ability of a language model modeling the contextual dependency. When the number of layers is fixed, we observe that the bright area is increased along with the increasing of the number of hidden units from 256 to 512. It may mean that short-range contextual dependency can be captured by adding the number of hidden units. These experimental phenomena verify the first hypothesis and the second hypothesis.

Correspondingly, we can also observe from Table 3 that the larger the bright area is, the larger the average of contextual similarity is. In Table 3 , when the L is equal to 3 (when R=256), the average of contextual similarity is the largest. Combined Figure 3 and Table 3 , we can find that the increasing of the number of layers can more effective to capture long-range similarity information. The results in Table 3 and in Figure 3 verify the third hypothesis.

:

The separation rank can not be accuracy computed in experiments.

is generally taken as 0.001 in experiments.

Figures and Tables:

Figure 1: The diagram about a bidirectional adaptive RNN. a) is a single direction adaptive RNN, b) is a schematic diagram of bidirectional RNN.

Figure2: Results on the short-range (first row) and long-range (second row) dependencies tasks. The displayed results show that the increasing of R is more helpful in short-range dependencies tasks (NER, Constituency Parsing and POS tagging), while the increasing of L is more effective for long-range dependencies tasks (WSD, Semantic classifier and Coreference Resolution), compared with the increasing of R.

NATURAL LANGUAGE PROCESSING TASKSThis set of experiments involves six tasks including Named Entity Recognition (NER), POS tagging, Constituency parsing, Word Sense Disambiguation (WSD), Sentiment analysis and Coreference Resolution. According to previous study(Peters et al., 2018a), NER, constituency parsing and POS tagging are more required to model short-range dependency, while WSD, Semantic classifier and Coreference Resolution are required to model long-range dependency.

d e r fu l c a r s th a t p e o p le d r o v

Figure3: Visualization of contextual similarity between all words pairs in a single sentence. For the first row, we set the hidden layer units to be 256, with layers from 1 to 3. For the second row, we set the number of layers to 1, and the hidden layer units (256, 512 and 1024, respectively). The lighter yellow-colored areas indicate the higher contextual similarity.

Results on sentences classification dataset. Accuracy (acc) is used as the evaluation criterion. * represents the results achieved by ourself.

Table content: <table><tr><td>Model</td><td>MR</td><td>SST2</td><td>CR</td><td>SUBJ</td><td>MPQA</td></tr><tr><td>FastText (Joulin et al., 2016)</td><td>0.765</td><td>0.788</td><td>0.789</td><td>0.916</td><td>0.874</td></tr><tr><td>Sent2Vec (Gupta et al., 2019)</td><td>0.763</td><td>0.802</td><td>0.791</td><td>0.912</td><td>0.872</td></tr><tr><td colspan="6">Transformer (Vaswani et al., 2017) 0.731* 0.761* 0.762* 0.863* 0.723*</td></tr><tr><td>BiLSTM (Conneau et al., 2017)</td><td>0.775</td><td>0.807</td><td>0.813</td><td>0.896</td><td>0.887</td></tr><tr><td>Adaptive-LSTM</td><td colspan="4">0.784* 0.816* 0.821* 0.92*</td><td>0.898*</td></tr><tr><td>Adaptive-BiLSTM</td><td colspan="5">0.790* 0.818* 0.820* 0.917* 0.904*</td></tr></table>

Word Benchmark datasetChelba et al. (2013) is used, and it has approximately 800M tokens of news crawl data from WMT 2011. Different recurrent network architectures (i.e., using different layers and the number of hidden units) are trained in EM Lo, which uses bidirectional LSTM structure. The training of EM Lo model will be stopped when the average perplexity is 40 in test dataset. After that, we select a sentence from the test data and compute the intra-sentence similarity. We use cosine similarity, which is a popular way to measure the similarity between word vectors encoded in different layers of EM Lo. Figure

Table content: <table/>

The quantitative relation between the separation rank in TSLM and the parameters (i.e.,

Table content: <table><tr><td>R</td><td>14</td><td>15</td><td>16</td><td>17</td></tr><tr><td colspan="2">L = 1 14</td><td>15</td><td>16</td><td>17</td></tr><tr><td colspan="2">L = 2 455</td><td>560</td><td>680</td><td>816</td></tr><tr><td colspan="2">L = 3 8008</td><td>12376</td><td>18564</td><td>27132</td></tr><tr><td colspan="5">L = 4 1.9 * 10 4 4.3 * 10 4 9.2 * 10 4 3.5 * 10 5</td></tr></table>

Peer review (iclr2020):
This paper first provides a theoretical interpretation of separation rank as a measure of a recurrent network*s ability to capture contextual dependencies in natural language text. The analysis is primarily done in the context of tensor space language models (TSLM) that was demonstrated to be a generalisation of n-gram language models in earlier work. The theoretical derivations suggest that increasing a network*s depth increases its separation rank exponentially, while increasing its width only increases its separation rank linearly. Based on this finding, the paper proposes a bidirectional adaptive recurrent neural network that adapts the network depth for each task using dynamic halting. Experiments on six NLP tasks demonstrate that increasing network depth helps more for tasks that generally require many long-range dependencies, while increasing network width is generally sufficient for tasks that require mostly short-term dependencies, although I disagree with the paper*s dichotomy of tasks with long-term and short-term dependencies (see point 3 below). Overall, this paper suffers from several serious issues, as listed below. I am therefore recommending a rating of *Reject* ahead of the authors* response. 1. This paper suffers from substantial clarity issues beyond simple grammatical errors. Some examples of the most serious clarity issues are as follows: (i) Section 6.1.1 lists *sentiment analysis* as one of the tasks, but Figure 2 has no entry for *sentiment analysis*, yet instead features experimental results for *semantic classifier* which was never mentioned or introduced before; and (ii) Figure 2 shows *1st layer LSTM*, *2nd layer LSTM*, and *3rd layer LSTM*, while (based on my reading) what the paper means are *1-layer LSTM*, *2-layer LSTM*, and *3-layer LSTM*, hence highly confusing for the reader. 2. The proposed explanation about the proposed bidirectional adaptive RNN is really sparse, despite being a central part of the paper. The explanation of the proposed model is only contained in two paragraphs (Sections 5.1 and 5.2), and are not sufficient for the readers to understand the model. A more extensive explanation and intuition about what the model is like, and how it is similar or different to TSLM and standard RNNs, is required to improve this. 3. In the experiments, the paper assumes a false dichotomy of tasks that only require short-range dependencies (NER, POS tagging, and constituency parsing), and tasks that require long-range dependencies (WSD, sentiment analysis, and coreference resolution). This dichotomy is overly simplistic and ultimately false. For instance, constituency parsers often need to identify spans that are very long-distance in nature (for a recent investigation of this, see the work by Fried et al. (2019)), while sentiment analysis often only requires the model to identify a few salient words that are indicative of the sentiment, e.g. *excellent* or *terrible*, hence not requiring much contextual dependencies. 4. Related to point 3, a better evaluation is to examine the cases that require long-range dependencies within each task, rather than assuming which tasks require long-range dependencies and which ones do not. An example of this is reporting e.g. constituency parsing performance for long-range spans and coreference resolution performance for long-distance entity chains. 5. The paper mostly fails to report performance comparison with existing numbers from prior work. For instance, the coreference performance (Fig. 2) are far below the result from Lee et al. (2017) that this paper is based on (Section 6.1.1), while the constituency parsing numbers (also Fig. 2) are also far below the reconciled span parser (Joshi et al., 2018) that this paper is also based on. This discrepancy calls into question the strength of the model implementation used in this paper. 6. Some missing citations, e.g. the use of adaptive computation time and dynamic halting in Universal Transformers (Dehghani et al., 2019). 7. This paper can benefit from careful copy-editing. Some examples of grammatical errors: (i) *Eq. 16* in Section 5.2 should be *Eq. 6*, (ii) *to verify our theoretical, respectively* in Section 6 should be *to verify our theoretical [findings/derivations]*, (iii) *ourself* on the caption of Table 1 should be *ourselves*, (iv) *The model Ling et al. (2015) is used, which using bidirectional LSTMs* should be *The model [of] Ling et al. (2015) is used, which [used] bidirectional LSTMs*, etc. References Daniel Fried, Nikita Kitaev, and Dan Klein. *Cross-domain generalization of neural constituency parsers*. In Proc. of ACL 2019. Kenton Lee, Luheng He, Mike Lewis, and Luke Zettlemoyer. *End-to-end neural coreference resolution*. In Proc. of EMNLP 2017. Vidur Joshi, Matthew E. Peters, and Mark Hopkins. *Extending a Parser to Distant Domains Using a Few Dozen Partially Annotated Examples*. In Proc. of ACL 2018. Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. *Universal Transformers*. In Proc. of ICLR 2019.