Implicit n-grams Induced by Recurrence (2022)

Abstract: Although self-attention based models such as Transformers have achieved remarkable successes on natural language processing (NLP)tasks, recent studies reveal that they have limitations on modeling sequential transformations (Hahn, 2020), which may promptre-examinations of recurrent neural networks (RNNs) that demonstrated impressive results on handling sequential data. Despite manyprior attempts to interpret RNNs, their internal mechanisms have not been fully understood, and the question on how exactly they capturesequential features remains largely unclear. In this work, we present a study that shows there actually exist some explainable componentsthat reside within the hidden states, which are reminiscent of the classical n-grams features. We evaluated such extracted explainable features from trained RNNs on downstream sentiment analysis tasks and found they could be used to model interesting linguistic phenomena such as negation and intensification. Furthermore, we examined the efficacy of using such n-gram components alone as encoders on tasks such as sentiment analysis and language modeling, revealing they could be playing important roles in contributing to the overall performance of RNNs. We hope our findings could add interpretability to RNN architectures, and also provide inspirations for proposing new architectures for sequential data.

## introduction modern recurrent neural networks (rnns), including long short-term memory (lstm) @xcite and gated recurrent units (gru) @xcite , have demonstrated impressive results on tasks involving sequential data. they have proven to be capable of modeling formal languages @xcite @xcite and capturing structural features @xcite @xcite @xcite on nlp tasks. although transformers @xcite have achieved remarkable performances on nlp tasks such as machine translation, it is argued that they may have limitations on modeling hierarchical structure @xcite and cannot handle functions requiring sequential processing of input well @xcite @xcite . furthermore, a recent work shows that combining recurrence and attention @xcite can result in strong modeling capacity. another recent work incorporating recurrent cells into transformers @xcite substantially improved performance on language modeling involving very long sequences, prompting re-investigations of rnns. on the other hand, it was observed in prior work that rnns were able to capture linguistic phenomena such as negation and intensification @xcite , but the question why they could achieve so still largely remains unanswered. in this work, we focus on better understanding rnns from a more theoretical perspective. we demonstrate that the recurrence mechanism of rnns may induce a linear combination of interpretable components. these components reside in their hidden states in the form of the iterated matrix-vector multiplication that is based on the representations of tokens in the (reverse) order they appear in the sequence. such components, solely depending on inputs and learned parameters, can be conveniently interpreted and are reminiscent of those compositional features used in classical ngram models @xcite . they may also provide us with insights on how rnns compose semantics from basic linguistic units. our analysis further shows that, the hidden state at each time step includes a weighted combination of components that represent all the "n-grams" ending at that specific position in the sequence as shown in figure 1 . we gave specific representations for the n-gram components in elman rnns @xcite , grus and lstms. we investigated the interpretability of those ngram components on trained rnn models, and found they could explain phenomena such as negation and intensification and reflect the overall polarity on downstream sentiment analysis tasks, where such linguistic phenomena are prevalent. our experiments also revealed that the gru and lstm models are able to yield better capabilities in modeling such linguistic phenomena than the elman rnn model, partly attributed to the gating mechanisms they employed which resulted in more expressive n-gram components. we further show that the linear combination of such components yields effective context representations. we explored the effectiveness of such n-gram components (along with the corresponding context representations) as alternatives to standard rnns, and found they can generally yield better results than the baseline compositional methods on several tasks, including sentiment analysis, relation classification, named entity recognition, and language modeling. we hope that our work could give inspirations to our community, serving as a useful step towards proposing new architectures for capturing contextual information within sequences. 1 2 related work interpretability of rnns: a line of work focuses on the relationship between rnns and finitestate machines @xcite @xcite @xcite , providing explanation and prediction on the expressive power and limitations of rnns on formal languages both empirically and theoretically. @xcite investigated conditions that could prevent gradient explosions for gru based on dynamics. @xcite and maheswaranathan and sussillo (2020) linearized the dynamics of rnns around fixed points of hidden states and elucidated contextual processing. our work focuses on studying a possible mechanism of rnns that handles exact linguistic features. another line of work aims to detect linguistic features captured by rnns. visualization approaches @xcite were initially used to examine compositional information in rnn outputs. @xcite assessed lstms' ability to learn syntactic structure and 1 our code is available at https://github.com/ richardsun-voyager/inibr . @xcite gave rigorous explanations on the standard rnns' ability to capture long-range dependencies. decomposition methods @xcite @xcite @xcite were proposed to produce importance scores for hierarchical interactions in rnn outputs. our work can be viewed as an investigation on how those interaction came about. compositional models: a variety of compositional functions based on vector spaces have been proposed in the literature to compose semantic meanings of phrases, including simple compositions of adjective-noun phrases represented as matrix-vector multiplication @xcite and a matrix-space model @xcite based on matrix multiplication. @xcite introduced a recursive neural network model that assigns every word and longer phrase in a parse tree both a vector and a matrix, and represents composition of a non-terminal node with matrix-vector multiplication. @xcite employed convolutional and recurrent neural networks to model compositionality at the sentence and discourse levels respectively. those models are designed in an intuitive manner based on the nature of languages thus being interpretable. we can show that rnns may process contextual information in a way bearing a resemblance to those early models. ## a theory on n -gram representation first, let us spend some time to discuss how to represent n-grams. various approaches to representing n-grams have been proposed in the literature @xcite @xcite @xcite @xcite @xcite . we summarize in although empirically it has been shown that different approaches can lead to different levels of effectiveness, the rationales underlying many of the design choices remain unclear. in this section, we establish a small theory on representing n-grams, which leads to a new formulation on capturing the semantic information within n-grams. let us assume we have a vocabulary v that consists of all possible word tokens. the set of ngrams can be denoted as v * (including the special model n -gram context l representative work representation representation vector multiplicative vi:@xmath0:t t mitchell and lapata (2008) (vm) matrix multiplicative mi:@xmath1:t t yessenalina and cardie (2011) (mm) vector additive (weighted) vi:@xmath2:t m bengio et al. (2003) under some mild compositional assumptions related to the principle of compositionality @xcite foot_0 , it is reasonable to expect that there exists some sort of rule or operation that allows us to compose semantics of longer n-grams out of shorter ones. let us use ⊗ to denote such an operation. we believe a good representation system for ngrams shall satisfy several key properties. first, the semantics of the n-gram abc shall be determined through either combining the semantics of the two n-grams a and bc or through combining the semantics of ab and c. the semantics of abc is unique, regardless of which of these two ways we use. second, for the empty string ϵ, it should not convey any semantics. formally, we can write them as: foot_1 this essentially shows that the representation space for all n-grams under the operation ⊗, denoted as (v * , ⊗), forms a monoid, an important concept in abstract algebra @xcite , with significance in theoretical computer science @xcite . on the other hand, it can be easily verified that the space of all d × d (where d is an integer) real square matrices under matrix multiplication, denoted as (r d×d , •), also strictly forms a monoid (i.e., it is associative and has an identity, but is not commutative). we can therefore establish a homomorphism from this essentially means that we may be able to rely on a sub-space within r d×d as our mathematical object to represent the space of n-grams, where the matrix multiplication operation can be used to compose representations for longer n-grams from shorter ones. thus, for a unigram x (a single word in the vocabulary), we have: r(x) := ax (1) however, the conventional wisdom in nlp has been to use vectors to represent basic linguistic units such as words, phrases or sentences @xcite @xcite . this can be achieved by a transform: next, we will embark on our journey to examine the internal representations of rnns. as we will see, interestingly, our developed n-gram representations can emerge within such models. ## interpretable components in rnns an rnn is a parameterized function whose hidden state can be written recursively as: let g(x t ) = f (x t , 0) and a(x t ) = ∇f (x t , 0). note that g(x t ) ∈ r d and a(x t ) ∈ r d×d are both functions of x t . therefore, the equation above can be written as: if the hidden state has a sufficiently small norm, it can be approximated by the first-order taylor expansion as follows 4 : next we illustrate how this recurrence relation can help us identify some salient components. ## experiments in our experiments, we focus on the following aspects: 1) understanding the effectiveness of the proposed n-gram (and context) representations when used in practice, as compared to baseline models; 2) examining the significance of the choice of context representation; 3) interpreting the proposed representations by examining how well they could be used to capture certain linguistic phenomena. we employ the sentiment analysis, relation classification, named entity recognition (ner) and language modeling tasks as testbeds. the first task is often used in investigating n-gram phenomena @xcite while the others are often used in examining how capable an encoder is when extracting features from texts @xcite @xcite . datasets for sentiment analysis, we considered the stanford sentiment treebank (sst) @xcite , the imdb @xcite , and the ag-news topic classification foot_5 @xcite , ## conclusion in this work, we focused on investigating the underlying mechanism of rnns in terms of handling sequential information from a theoretical perspective. our analysis reveals that rnns contain a mechanism where each hidden state encodes a weighted combination of salient components, each of which can be interpreted as a representation of a classical n-gram. through a series of comprehensive empirical studies on different tasks, we confirm our understandings on such interpretations of these components. with the analysis coupled with experiments, we provide findings on how rnns learn to handle certain linguistic phenomena such as negation and intensification. further investigations on understanding how the identified mechanism may capture a wider range of linguistic phenomena such as multiword expressions @xcite could an interesting future direction.