Weighted automata extraction and explanation of recurrent neural networks for natural language tasks

Zeming Wei, Xiyue Zhang, Yihao Zhang, Meng Sun

Recurrent Neural Networks (RNNs) are the workhorses of sequential data, but their internal "gate" logic and hidden state dynamics are notoriously difficult to interpret. While researchers have previously tried to extract simpler, human-readable models like finite automata from RNNs, these methods often crumble when faced with the massive vocabularies and complex dependencies of natural language.

A new paper by Wei et al., titled "Weighted Automata Extraction and Explanation of Recurrent Neural Networks for Natural Language Tasks," introduces a robust framework to bridge this gap. By refining how we extract Weighted Finite Automata (WFA) and introducing a novel embedding technique, the authors provide a clearer lens into how RNNs actually "think" about text.

TL;DR

The authors propose a novel framework to extract precise Weighted Finite Automata (WFA) from RNNs by addressing the "transition sparsity" and "context loss" common in natural language tasks. They introduce Transition Matrix Embeddings (TME), a task-oriented word embedding that outperforms traditional methods like GloVe in explaining model decisions and generating adversarial examples.

What Problem Does This Paper Address?

Understanding RNNs usually involves looking at "surrogate models"—simpler abstractions like finite automata that represent states and transitions. However, two major hurdles exist for NLP:

  1. Transition Sparsity: In natural language, the "alphabet" (vocabulary) is huge. Most words appear rarely in training data, leading to "missing rows" in the extracted transition matrices. If a word wasn't seen in a specific state during extraction, the automaton doesn't know what to do.
  2. Context Loss: RNNs (especially LSTMs) are designed to remember long-term context. Simple automata often lose this "memory" during the abstraction process, leading to poor precision.

Existing extraction methods either don't scale to large vocabularies (exact learning) or lack the precision needed for complex language tasks (compositional approaches).

Methods

The researchers use 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 fix the precision issues, they introduced three key innovations:

  • Empirical Rule Complement: To handle missing transitions (sparsity), they don't just fill them with zeros. Instead, they use the semantic distance between abstract states to "guess" the transition, weighted by a "reference rate" ($\beta$).
  • Context-Awareness Enhancement: They introduce a "static probability" ($\alpha$) that allows the WFA to remain in its current state with some probability. This mathematically mimics the way LSTMs preserve information over time.
  • Data Augmentation: They use synonym replacement and "dropout" (replacing words with <unk>) during the extraction phase to force the RNN to reveal more of its internal transition logic.

Finally, they flatten the resulting transition matrices into vectors called Transition Matrix Embeddings (TME). Unlike standard embeddings (like Word2Vec), TMEs represent how a word specifically affects the state of the model for a given task.

Datasets

The authors evaluated their framework on two popular NLP benchmarks:

  1. CogComp QC (Question Classification): 20,000 training samples across seven categories (e.g., Sport, Business, Sci_tech).
  2. Jigsaw Toxic Comment Dataset: A large-scale dataset for binary classification (toxic vs. non-toxic) of Wikipedia talk page edits.

Key Insights and Ideas

  • Task-Oriented Semantics: TMEs reveal that RNNs group words based on their functional role in a task rather than just dictionary definitions. For example, "exercise" and "sports" might be synonyms in general language, but an RNN trained on a health vs. sports classifier treats them very differently.
  • Collaborative vs. Adversarial Pairs: The authors define "Collaborative Pairs" (words with different meanings that trigger the same RNN behavior) and "Adversarial Pairs" (synonyms that trigger wildly different RNN behaviors). Identifying these pairs helps pinpoint where a model is vulnerable or biased.
  • Zipf’s Law is a Barrier: The authors use Zipf’s law to prove mathematically why "missing rows" are inevitable in NLP automata extraction, justifying the need for their empirical filling methods.

Key Results

  • Higher Fidelity: The "Consistency Rate" (how often the WFA and RNN agree) reached 84% on the QC dataset and 94% on the Toxic dataset, significantly outperforming baseline extraction methods (which hovered around 60-86%).
  • Faster Convergence: Using TMEs to initialize a new RNN's word embeddings led to much faster training and higher accuracy compared to random initialization or even pre-trained GloVe embeddings.
  • Superior Adversarial Attacks: Using TME to identify influential words allowed the authors to generate adversarial examples with a much higher Attack Success Rate (ASR). On the QC dataset, TME-guided attacks were roughly 2x more effective than those using GloVe.

Limitations and Future Work

While the framework is powerful, the authors note a few areas for growth:

  • Clustering Sensitivity: The precision of the WFA is still dependent on the number of clusters ($K$) chosen for state abstraction. While their method is more robust than others, finding the "optimal" $K$ remains an empirical challenge.
  • Generalization: While the authors argue the method can be applied to other RNN types (beyond LSTMs), the data augmentation tactics (like synonym replacement) are specific to NLP and would need to be redesigned for domains like time-series forecasting or signal processing.
  • Computational Overhead: Although the complexity is linear relative to dataset size, the k-means clustering on high-dimensional hidden states can still be resource-intensive for extremely large models.

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},
}

Loading related content...

Figure