Weighted Automata Extraction and Explanation of Recurrent Neural Networks for Natural Language Tasks

Zeming Wei, Xiyue Zhang, Yihao Zhang, Meng Sun

Abstract

Recurrent Neural Networks (RNNs) have achieved tremendous success in processing sequential data, yet understanding and analyzing their behaviours remains a significant challenge. To this end, many efforts have been made to extract finite automata from RNNs, which are more amenable for analysis and explanation. However, existing approaches like exact learning and compositional approaches for model extraction have limitations in either scalability or precision. In this paper, we propose a novel framework of Weighted Finite Automata (WFA) extraction and explanation to tackle the limitations for natural language tasks. First, to address the transition sparsity and context loss problems we identified in WFA extraction for natural language tasks, we propose an empirical method to complement missing rules in the transition diagram, and adjust transition matrices to enhance the context-awareness of the WFA. We also propose two data augmentation tactics to track more dynamic behaviours of RNN, which further allows us to improve the extraction precision. Based on the extracted model, we propose an explanation method for RNNs including a word embedding method -- Transition Matrix Embeddings (TME) and TME-based task oriented explanation for the target RNN. Our evaluation demonstrates the advantage of our method in extraction precision than existing approaches, and the effectiveness of TME-based explanation method in applications to pretraining and adversarial example generation.

Introduction

Recurrent Neural Networks (RNNs) are fundamental to processing sequential data, yet their internal "gate" logic and hidden state dynamics are notoriously difficult to interpret. While researchers have previously attempted to extract human-readable models like finite automata from RNNs, these methods often struggle with the massive vocabularies and complex dependencies inherent in natural language processing (NLP).

Two primary hurdles exist for NLP model extraction:

  1. Transition Sparsity: The vast vocabulary of natural language means most words appear rarely in training data, leading to "missing rows" in extracted transition matrices.
  2. Context Loss: RNNs, particularly LSTMs, are designed for long-term context. Simple automata often lose this "memory" during abstraction, resulting in poor precision.

This paper introduces a robust framework to bridge this gap by refining Weighted Finite Automata (WFA) extraction and introducing a novel embedding technique to explain RNN behavior.

Methodology

The proposed framework utilizes a compositional approach where the RNN's hidden state vectors are clustered into a finite set of "abstract states" using the k-means algorithm. To address precision and sparsity issues, the authors introduced three key innovations:

  • Empirical Rule Complement: To handle missing transitions, the method uses the semantic distance between abstract states to estimate transitions, weighted by a "reference rate" ($\beta$).
  • Context-Awareness Enhancement: A "static probability" ($\alpha$) is introduced, allowing the WFA to remain in its current state with some probability, mimicking how LSTMs preserve information.
  • Data Augmentation: Synonym replacement and "dropout" (replacing words with <unk>) are used during extraction to force the RNN to reveal more of its internal transition logic.
Overview of the proposed WFA extraction framework, illustrating the pipeline from data augmentation and RNN execution to transition matrix refinement and final WFA extraction.

The resulting transition matrices are flattened into vectors called Transition Matrix Embeddings (TME). Unlike standard embeddings like Word2Vec, TMEs represent how a word specifically affects the model's state for a given task. The framework was evaluated on the CogComp QC (Question Classification) and Jigsaw Toxic Comment datasets.

Results and Discussion

The evaluation demonstrates significant improvements in both model fidelity and practical application:

  • Higher Fidelity: The "Consistency Rate" (agreement between WFA and RNN) reached 84% on the QC dataset and 94% on the Toxic dataset, significantly outperforming baseline extraction methods.
  • Task-Oriented Semantics: TMEs reveal that RNNs group words based on their functional role in a task. For instance, an RNN trained on a health vs. sports classifier treats "exercise" and "sports" differently despite their general semantic similarity.
  • Adversarial Robustness: TME-guided adversarial attacks were roughly 2x more effective than those using GloVe on the QC dataset, highlighting the method's ability to identify influential words.
  • Faster Convergence: Initializing new RNNs with TMEs led to faster training and higher accuracy compared to random or GloVe-based initialization.

Conclusion

While the framework provides a powerful tool for RNN interpretation, limitations remain regarding clustering sensitivity and the computational overhead of k-means on high-dimensional states. Future work may involve refining the selection of the number of clusters ($K$) and extending data augmentation tactics beyond NLP-specific methods. Nonetheless, this approach offers a significant step toward making complex sequential models more transparent and explainable.

Summary updated

Abstract

Recurrent Neural Networks (RNNs) have achieved tremendous success in processing sequential data, yet understanding and analyzing their behaviours remains a significant challenge. To this end, many efforts have been made to extract finite automata from RNNs, which are more amenable for analysis and explanation. However, existing approaches like exact learning and compositional approaches for model extraction have limitations in either scalability or precision. In this paper, we propose a novel framework of Weighted Finite Automata (WFA) extraction and explanation to tackle the limitations for natural language tasks. First, to address the transition sparsity and context loss problems we identified in WFA extraction for natural language tasks, we propose an empirical method to complement missing rules in the transition diagram, and adjust transition matrices to enhance the context-awareness of the WFA. We also propose two data augmentation tactics to track more dynamic behaviours of RNN, which further allows us to improve the extraction precision. Based on the extracted model, we propose an explanation method for RNNs including a word embedding method -- Transition Matrix Embeddings (TME) and TME-based task oriented explanation for the target RNN. Our evaluation demonstrates the advantage of our method in extraction precision than existing approaches, and the effectiveness of TME-based explanation method in applications to pretraining and adversarial example generation.
BibTeX
@article{wei2024weighted,
  author = {Zeming Wei and Xiyue Zhang and Yihao Zhang and Meng Sun},
  title = {{Weighted Automata Extraction and Explanation of Recurrent Neural Networks for Natural Language Tasks}},
  journal = {J. Log. Algebraic Methods Program.},
  year = {2024},
  url = {https://openreview.net/forum?id=Cpc0zwqfQs},
}
Figure