Selected from ArXiv by Bo-Jian Hou, Zhi-Hua Zhou, Compiled by The Heart of Machine, Siyuan, Xiao Kun.

Beyond numerical calculations, do you really know what’s going on inside a neural network? We’ve always understood that depth models depend on the flow of computation inside them, but we still don’t know whether they have physical or semantic meaning. Especially in recurrent neural networks, we just know that at each time step it’s extracting current semantic information from previous memory, but when it comes to how and what, we can’t do anything about it. In this paper, Zhou Zhihua and other researchers from Nanjing University try to explore the internal mechanism of RNN by using finite state machines. This model with physical significance can show the internal process of RNN and help us to see what RNN does on the ground.

The main task of Structure learning is to deal with structured output, and it does not predict a value for each independent sample like a classification problem. The structures in question can be graphs, sequences, trees, vectors, etc. Generally, machine learning algorithms used for structured output include various probability graph models, perceptron and SVM. In the past decades, structured learning has been widely used in target tracking, target location, semantic parsing and other tasks, and many problems such as multi-label learning and clustering are also strongly related to structured learning.

Generally speaking, structured learning uses structured annotations as supervisory information, and uses corresponding algorithms to predict these structured information to achieve excellent performance. However, as machine learning algorithms become more complex, their interpretability, by which I mean how to understand the internal mechanisms or processes of the learning process, becomes more and more important. In this paper, Zhou Zhihua and other researchers focus on deep learning models and explore how to learn the structure of these models to improve the interpretability of models.

Exploring the interpretability of deep learning models is often difficult, but there are solutions for specific types of deep learning models such as RNN. As the main component of deep neural networks, recurrent neural networks (RNN) are widely used in various sequence data tasks, especially those variants with gating mechanisms, such as MGU with one gate, GRU with two gates and LSTM with three gates.

In addition to the familiar RNN, there is another tool that can capture sequence data, namely Finite State Automaton/FSA. FSA consists of finite states and transitions between states, which will transition from one state to another in response to external sequence input. The FSA conversion process is somewhat similar to RNN in that they are input elements in a sequence received one by one and passed between the corresponding states. Unlike RNN, FSA’s internal mechanisms are easier to explain because we can more easily simulate its processes. In addition, FSA transitions between states have physical significance, whereas RNN only has numerical significance.

These characteristics of FSA led Zhou Zhihua’s team to explore learning an FSA model from RNN and using the natural interpretability of FSA to understand the internal mechanism of RNN. Therefore, Zhou Zhihua and other researchers adopted FSA as the interpretable structure they sought. In addition, this study differs from previous explorations of structured learning. While previous methods focused on structured prediction or classification results, this article focuses on the output structure of the middle hidden layer, so as to better understand the internal mechanism of RNN.

In order to learn FSA from RNN, and to use FSA to explain the internal mechanisms of RNN, we need to know how to learn FSA and explain exactly what is in RNN. As for how to learn FSA, the researchers found that non-gated classical RNN hiding state tends to construct some clusters. However, there are still some important unresolved issues, one of which is that we do not know whether the tendency to construct clusters is also present in gated RNN. Efficiency also needs to be considered, since gated RNN variants are often used in large data sets. To explain specifically what is in RNN, researchers analyzed the role of gating mechanism in LSTM, GRU and MGU models, especially the number and influence of gates in different gated RNN. Since transitions between states in FSA have physical meaning, we can infer semantic meaning from the FSA transitions corresponding to RNN.

In this paper, Zhou Zhihua et al. tried to learn FSA from RNN. They first verified that in addition to classical RNN without gating, the hidden state of other gated RNN variants also had natural cluster attributes. Then they proposed two methods, one is the efficient clustering method K-means ++. Another method is proposed based on the phenomenon that if the hidden states in the same sequence are similar, they are also similar in the geometric space. This method is named k-means-x. The researchers then learned FSA by designing five necessary elements: the alphabet, a set of states, an initial set of states, a set of receiving states, and state transitions. They eventually applied these methods to simulated and real data.

For the artificial simulation data, the researchers first show that we can understand the FSA learned during operation. They then show the relationship between accuracy and the number of clusters, and show that a gating mechanism is necessary for a gated RNN, and that the fewer gates the better. This partly explains why only one gated MGU is to some extent superior to the other gated RNN.

As for the real data of emotion analysis, the researcher found that behind the numerical calculation, the hidden state of RNN does have the ability to distinguish semantic differences. Because in the corresponding FSA, the words that lead to the positive/negative output do indeed do some positive or negative understanding of human emotion.

Learning with Interpretable Structure from RNN



Address: arxiv.org/pdf/1810.10…

Abstract: In structured learning, output is usually a structure that can be used as supervisory information to obtain good performance. Considering that the interpretability of deep learning has received more and more attention in recent years, it would be helpful if we could learn explicable structures from deep learning models. In this paper, we focus on recurrent neural networks (RNN), whose internal mechanisms are still not well understood. We find that finite state machines (FSA) that process sequence data have more explicable internal mechanisms and can be learned from RNN as explicable structures. We propose two different clustering methods to learn FSA from RNN. We start with a graph of the FSA to demonstrate its interpretability. From the FSA perspective, we analyze how the performance of RNN is affected by the number of gates and the semantic meaning behind the numerical hidden state transitions. Our results show that RNNS with simple gated structures such as minimum Gated unit (MGU) perform better, and that transformations in FSA can yield specific classification results associated with corresponding words, a process that is understandable to humans.

The method of this paper

In this section, we introduce the intuitive sources and methodological frameworks for proposing methods. We represent the hidden state of RNN as a vector or a point. So when multiple sequences are entered into RNN, a large number of hidden state points accumulate, and they tend to form clusters. To verify this conclusion, we show the distribution of hidden state points on MGU, SRU, GRU and LSTM, as shown in Figure 1 (a) to (d).

Figure 1: Dimensionality of hidden state points is reduced into two dimensions by t-SNE method. It can be seen that hidden state points tend to form clusters.

Figure 2 shows the overall framework. We first train RNN on the training data set, then perform clustering on all the hidden states H of the validation data V, and finally learn an FSA of V. Once we have the FSA, we can use it to test unlabeled data or draw diagrams directly. For the first step of retraining the RNN, we use the same strategy as [ZWZZ16], ignoring the details here. We’ll cover hidden state clustering and FSA learning steps in more detail later (see article).

Figure 2: Frame display of the proposed algorithm. The yellow circle represents the hidden state, represented by h_T, where T is the time step. “A” is the loop unit that receives input X_T and h_T-1 and outputs h_t. The double circle of structured FSA is the accept state. Overall, the framework consists of three steps: training RN your model, clustering hidden states, and exporting structured FSA.

The complete FSA learning process from RNN is shown in Algorithm 1. We call this method LISOR and show two different clustering algorithms. Those based on K-means ++ are called “lisor-k” and those based on k-means-x are called “Lisor-x”. Both LisOR-k and Lisor-X can learn well-generalized FSA from RNN by taking advantage of the clustering tendencies that make up the hidden state points.

The experimental results

In this part, we conducted experiments on both artificial and real tasks and visualized FSA learned from the corresponding RNN model. In addition, in two tasks, we discussed how we interpreted the RNN model from FSA and demonstrated the accuracy of classification using the learned FSA.

The first human task is to identify the sequence “0110” (task “0110”) in a sequence of length 4 containing only 0s and 1s. This is a simple task involving only 16 different cases. We included 1000 instances in the training set and repeated instances to improve accuracy. We learned FSA using a 0-1 sequence of length 4 with all possible values and no duplicates, and randomly generated 100 instances to test.

The second human task is to determine whether a sequence contains three consecutive zeros (task “000”). There is no limit on the length of the sequence, so the task has infinite instance space and is more difficult than task “0110”. We randomly generate 3000 0-1 training instances whose length is randomly determined. We also generated 500 validation instances and 500 test instances.

Table 2: The number of clusters (N_c) when the FSA accuracy of task “0110” learned from the four RNN reaches 1.0 for the first time based on lisOR-k and Lisor-x methods respectively. Note that the smaller these values are, the more efficient and interpretable they are. The RNN models trained in different experiments were initialized with different parameters.

As shown in Table 2, we can see that the average number of FSA clusters learned from the MGU always achieves accuracy of 1.0 with the smallest number of clusters. A cluster number of 65 means that FSA accuracy will not reach 1.0 until n_C is 64. The minimum number of clusters per trial and the average minimum number of clusters are shown in bold.

Table 3: Number of clusters (n_c) based on LISOR-k and Lisor-x methods when FSA learned from the four RNNZHOs first reached 0.7 accuracy in task “000”. Note that the smaller these values are, the more efficient and interpretable they are.

Figure 3: FSA structure diagram learned from training four RNNS in task “0110”. The number of clusters k is determined by the number of clusters when the FSA reaches accuracy 1.0 for the first time. Routes for 0110 are shown in red. Note that figure (d) consists of four nodes independent of the main section. This is because we have abandoned the smaller frequency conversion when typing a symbol to learn a deterministic FSA.

Figure 4: FSA structure diagram learned when training four RNNS in task “000”. The number of clusters k is determined by the number of clusters when FSA reaches 0.7 accuracy for the first time.



Figure 7: FSA learned by MGU trained on emotion analysis task. Here the FSA is compressed and the words between the same two states in the same direction are grouped into the same speech class. For example, the words in “Word class 0-1” all represent transitions from state 0 to state 1.

Table 5: The words that transition from state 0 are called acceptable state (i.e. state 1 containing positive movie reviews), and most of them are positive. The numbers in brackets here indicate the FSA number from which the word came.

Table 4: Accuracy rate of emotion classification task when the number of clusters is 2.