On the Relationship Between RNN Hidden-State Vectors and Semantic Structures (2024)

Abstract: We examine the assumption that hidden-state vectors of recurrent neural networks (RNNs) tend to form clusters of semantically similar vectors, which we dub the clustering hypothesis. While this hypothesis has been assumed in RNN analyses in recent years, its validity has not been studied thoroughly on modern RNN architectures. We first consider RNNs that were trained to recognize regular languages. This enables us to draw on perfect ground-truth automata in our evaluation, against which we can compare the RNN’s accuracy and the distribution of the hidden-state vectors. Then, we consider context-free languages to examine if RNN states form clusters for more expressive languages.For our analysis, we fit (generalized) linear models to classify RNN states into automata states and we apply different unsupervised clustering techniques. With a new ambiguity score, derived from information entropy, we measure how well an abstraction function maps the hidden state vectors to abstract clusters. Our evaluation supports the validity of the clustering hypothesis for regular languages, especially if RNNs are well-trained, i.e., clustering techniques succeed in finding clusters of similar state vectors. However, the clustering accuracy decreases substantially for context-free languages. This suggests that clustering is not a reliable abstraction technique for RNNs used in tasks like natural language processing.

## introduction in recent years we have seen significant advancements in the analysis and verification of artificial neural networks (anns) @xcite @xcite . the motivation has been to establish trust in the growing landscape of machine-learned systems. most of the work considered feed-forward anns that implement functions without internal states. in this work we shift the focus to recurrent neural networks (rnns) that model processes with internal states. having access to an internal memory makes rnns ideal for challenging tasks on high-dimensional sequential data, such as natural language processing (nlp) @xcite and time series forecasting @xcite . consequently, many researchers have turned to the internals of rnns in hopes of understanding the rnn decision-making process @xcite . an important, yet scarcely examined, hypothesis in this field postulates that the hidden state vectors visited by an rnn while processing data form clusters of semantically similar states. consider sentiment analysis for movie reviews as an example @xcite . the sentences "this movie is great." and "this movie is awesome." are semantically similar, but syntactically different. an rnn processing these sentences is assumed to traverse states that belong to the same state clusters. in recent years, the clustering hypothesis has been the basis of several rnn analysis methods. @xcite applied it to construct finitestate models over observed clusters. through probabilistic model checking, they identified adversarial data. @xcite developed an efficient technique for extracting deterministic finite automata from rnns, which was extended to context-free languages @xcite . while these approaches relied on some form of the clustering hypothesis, they also encountered, and subsequently coped with inaccuracies of clustering functions. instead of using clusters as abstract states directly, @xcite learned probabilistic automata over clusters. while successful applications of the clustering hypothesis might imply its soundness, the validity of the hypothesis still remains questioned. for example, already in early work @xcite warned against methods that rely on state-space discretization (clustering) due to the inherent information loss. also, @xcite noticed problems with the clustering approach. since validation and verification of rnns should not be based on anecdotal evidence, we return to this open question and empirically examine the soundness of the clustering hypothesis. more precisely, first, we train rnns to recognize formal languages with known and minimal ground-truth automaton representations. then, we process data with the rnn to investigate the following research questions: are an rnn's hidden-state vectors linearly separable (rq1)? is the clustering hypothesis assumed for rnns valid (rq2)? does the level of the chomsky hierarchy affect clustering (rq3)? we approach these questions by simulating validation data on trained rnns to extract visited hidden state vectors. at the same time, we track the unique automaton state corresponding to each rnn state. then, we partition the sampled rnn states using multiple clustering functions and we train linear multiclass classifiers to classify rnn states to automaton states. linear classifiers use known ground-truth states, therefore they establish an upper bound for the precision of clustering with linear cluster boundaries. hence, rq1 can be seen as a prerequisite for some clustering techniques. to answer rq2, we analyze the correspondence between derived clusters and automata states and assign an ambiguity score to each clustering configuration. ideally, each cluster (or a set of clusters) should correspond to a unique state in the respective ground-truth automaton. an overview of this process can be seen in fig. 1 . for the first two research questions, we focus on regular languages. regular languages provide a good basis for analysis, but many practical applications, such as natural language processing require more expressiveness. therefore, for rq3 we move one layer up in the chomsky hierarchy and analyze the clustering hypothesis on a subset of context-free languages that can be modeled with deterministic pushdown automata. our contributions can be summarized as: (1) analyses of 1950 trained rnns w.r.t. separability of their state space, (2) computation and analysis of clusters over the hidden-state vectors, (3) and a framework containing all presented functionalities developed with aalpy @xcite , pytorch @xcite , and scikit-learn @xcite . to the best of our knowledge, this constitutes the first detailed empirical evaluation of the "clustering hypothesis". structure. in sect. 2 we discuss related work followed by preliminaries in sect. 3. sect. 4 discusses our research questions and presents techniques and accuracy metrics that we use in sect. 5 for an empirical evaluation of the clustering hypothesis. sect. 6 concludes the paper and discusses future work. so far we presented related work that, in some form or another, assumes or relies on the clustering hypothesis. the connections between formal languages and rnn were studied in other contexts, such as extraction of models from rnns @xcite @xcite , formal reasoning about the expressive power of rnns and transformers @xcite @xcite , adapting an rnn's architecture and training so that the rnn implicitly learns the model of its behaviour @xcite , among others. ## preliminaries a deterministic finite automaton (dfa) over alphabet σ is a tuple @xmath0, σ, q 0 , δ, f ), where q is a finite set of states, q 0 ∈ q is the initial state, δ : q × σ → q is the transition function, f ⊆ q are the final states. we extend the transition function as usual to arbitrary-length sequences @xmath1, i.e., δ(q, ϵ) = q and δ(q, e • s ′ ) = δ(δ(q, e), s ′ ), where ϵ is the empty sequence, @xmath2, s ′ ∈ σ * . a word @xmath3, w) ∈ f . all accepted words form a regular language. moore machines extend dfas by producing an output from a discrete output alphabet o in every state defined by a function λ : @xmath4. a deterministic pushdown automaton (pda) is a 7-tuple (q, σ, γ, δ, q 0 , z, f ) where q is a finite set of locations, σ is a finite input alphabet, γ is a finite stack alphabet, δ : q × σ × γ * → q × γ * is the transition function, q 0 ∈ q is the initial location, @xmath5, and f ⊂ q is the set of accepting locations. the state of a pda is a pair (q, γ) ∈ q × γ * , where q is a location and γ is a stack of symbols from γ. as in dfas, we extend δ to sequences w where δ(q 0 , z, w) = (q, γ) is the state reached after processing w. recurrent neural networks (rnns). in this paper, we examine standard implementations of elman rnns @xcite (with relu and tanh activation functions), lstms @xcite , and grus @xcite . we view an rnn as a pair of functions (r, o), where r : r h × r @xmath6. we use a one-hot encoding for discrete inputs from an alphabet of size m. for simplicity, we also use this view for lstms by analyzing the state space spanned by the concatenation of the hidden state h t and the cell state c t of lstms. the output function o : r @xmath7. we train rnns on sequences sampled from languages defined by dfas, moore machines, and pdas. for dfas and pdas, we have @xmath8, false}, where true denotes acceptance of the sequence processed so far. for moore machines, we have @xmath9, where o is an output alphabet and o maps to the last output produced by the corresponding moore machine. ## method this section presents the basis for the analysis of the "clustering hypothesis", including research questions and accuracy metrics. ## evaluation next, we present the experimental setup and empirical results related to our research questions. the code required to reproduce all experiments can be online foot_0 . the appendix includes numerical data from plots and additional experiments. all experiments were conducted on a laptop with an intel ® core™i7-11800h cpu, nvidia 3050 ti moblie gpu32 gb ram, and took ∼40h. ## conclusion and future work we revisited and empirically analyzed the hypothesis that an rnn's hidden-state vectors tend to form clusters. our analysis examines the clustering hypothesis for rnns trained to recognize formal languages. this provided us with a ground truth enabling a comparison of the identified clusters with the original finite-state semantics that underlie the learned concept. additionally, we examined the (linear) separability of hidden-state vectors into regions corresponding to automata states. we observed that the hidden-state vectors of rnns trained to recognize regular languages can often be (piecewise linearly) separated when considering regular languages. considering unsupervised clustering, the regions identified by classi-fiers may contain multiple clusters and clusters may span across decision boundaries. restricted to regular languages, we show that it is possible to compute clustering functions that correlate with automata states. for example, clusterings obtained by k-means with large k overall achieved high accuracy and perfect accuracy in 58% of the first set of experiments. this drastically changes when considering deterministic context-free languages, where the k-means with a large k achieved perfect clustering in only 2.6% of the cases. this is a strong indication that the clustering hypothesis alone should not be used as a basis for abstraction in the analysis of rnns. future work. with rnn verification being our ultimate goal, we will investigate ways to mitigate imprecisions and errors resulting from imperfect clustering. a stochastic interpretation of rnns and stochastic automata learning over clusters seems promising @xcite . further analysis of factors affecting the clustering is also important, like the effect of different optimizers or overtraining. finally, we will investigate how to adapt the training and rnn architecture such that clusters are likely to form, enabling explainability-by-design. acknowledgments. this work has been supported by the "university sal labs" initiative of silicon austria labs (sal) and its austrian partner universities for applied fundamental research for electronic based systems. in addition, this work has been partially supported by the wwtf project ict22-023. limitations. to the best of our knowledge, our empirical analysis has two potential limitations: a) statistical significance of results, and b) dependence of our findings on the quality of clustering metric introduced in sect. 4.2. regarding a), we applied exploratory data analysis to find trends in the data from a total of 1950 trained rnns over 74 (59 regular languages and 15 context-free) formal languages. these networks include different architectures of various sizes, and for each trained network, we conduct experiments that contain multiple parameterizations of clustering algorithms. we examined selected findings through statistical tests, where we found statistically significant support for mean shift computing clusters with low ambiguity and a statistically significant correlation between ambiguity and accuracy of rnns trained on regular languages. in cases, where trends were very clear, we did not perform statistical tests like for the high ambiguity results involving context-free languages. regarding b), we believe that our entropy-based metric for the clustering quality reflects the quality of clustering in the scope of the presented research questions, that is, it encodes the correspondence of identified clusters to states. we further compared it to nmi, and the reason why nmi is not suited as a measure of clustering quality in our research context, is that might penalize perfect, but nonminimal, correspondence of clusters to states. our experiments were performed on formal languages where the ground truth model against which we can compare rnns performance is known and accessible. however, the existence of such a model cannot be generally assumed for nlp tasks.