Abstract
Recurrent Neural Networks (RNNs) have achieved tremendous success in sequential data processing. However, it is quite challenging to interpret and verify RNNs' behaviors directly. To this end, many efforts have been made to extract finite automata from RNNs. Existing approaches such as exact learning are effective in extracting finite-state models to characterize the state dynamics of RNNs for formal languages, but are limited in the scalability to process natural languages. Compositional approaches that are scalable to natural languages fall short in extraction precision. In this paper, we identify the transition sparsity problem that heavily impacts the extraction precision. To address this problem, we propose a transition rule extraction approach, which is scalable to natural language processing models and effective in improving extraction precision. Specifically, we propose an empirical method to complement the missing rules in the transition diagram. In addition, we further adjust the transition matrices to enhance the context-aware ability of the extracted weighted finite automaton (WFA). Finally, we propose two data augmentation tactics to track more dynamic behaviors of the target RNN. Experiments on two popular natural language datasets show that our method can extract WFA from RNN for natural language processing with better precision than existing approaches.
Introduction
Recurrent Neural Networks (RNNs) and Long Short-Term Memory (LSTM) networks are the standard for processing sequential data in natural language processing (NLP). Despite their performance, they remain "black boxes." Their internal gate controls and high-dimensional state vectors make it nearly impossible to verify why they make specific decisions or to guarantee their safety in critical applications.
To bridge this gap, researchers have sought to extract Finite Automata—mathematical models with discrete states and clear transition rules—to serve as interpretable maps of RNN behavior. However, extracting these models for natural language is difficult due to the massive vocabularies involved and the inherent complexity of human language. This paper presents a novel approach to extracting Weighted Finite Automata (WFA) that addresses these scalability and precision challenges.
The Challenge: Transition Sparsity
Existing extraction methods often struggle with scalability or precision. A primary obstacle identified in this research is the transition sparsity problem. Because human language follows Zipf’s law—where a few words are common and most are rare—an RNN may never encounter certain word-state combinations during training.
In the CogComp QC dataset, for example, the median word appears so infrequently that most of its transition matrix rows would be empty in a standard extraction. This creates "holes" in the logic of the extracted model, leading to poor performance when the WFA encounters unfamiliar word-state pairs. Furthermore, simple automata often lack the "memory" required to track long-term dependencies that RNNs handle via internal gates.
Proposed Methodology
To address these issues, we propose a compositional extraction scheme that transforms an RNN into a WFA through four key innovations:
1. State Abstraction via k-means
We record the RNN's internal probabilistic outputs and cluster them using $k$-means. Each cluster center represents a discrete "abstract state" in the WFA. Unlike previous methods that treated states as arbitrary identifiers, our approach treats the center of a cluster as the state's semantic "meaning."
2. Complementing Missing Rows
To solve transition sparsity, we introduce an empirical method to fill "missing rows" in the transition diagram. When the WFA encounters a word-state pair it has not seen before, it identifies semantically similar states based on Euclidean distance. It then borrows the transition logic from these neighbors, weighted by a "reference rate" ($\beta$).
3. Context-Aware Enhancement
To better mimic the long-term memory of an LSTM, we adjust the transition matrices using a "static probability" ($\alpha$). By mixing the Identity Matrix ($I$) into the transition matrices, we ensure that information from previous steps vanishes exponentially rather than instantly. This allows the discrete WFA to track context more effectively.
4. Data Augmentation
To capture a broader range of the RNN's dynamic behaviors, we employ two data augmentation tactics: Synonym Replacement and Dropout (replacing words with an <unk> token). These tactics "poke" the RNN to see how it behaves in rare or noisy scenarios, providing a more robust dataset for extraction.
Experimental Evaluation
We evaluated our method on two popular NLP benchmarks:
- CogComp QC (Question Classification): News titles labeled with topics such as "Location" or "Entity."
- Jigsaw Toxic Comment Dataset: Wikipedia talk page edits labeled as "toxic" or "non-toxic."
Our primary metric was the Consistency Rate (CR), which measures how often the extracted WFA makes the exact same prediction as the original RNN.
Key Results
- Precision Improvements: On the QC dataset, the consistency rate jumped from 60% (using standard uniform filling) to 84% using our full suite of enhancements.
- High Consistency: On the Jigsaw dataset, we achieved a 94% consistency rate, demonstrating that the WFA can highly accurately mimic the target RNN.
- Efficiency: Despite the complexity of calculating semantic distances, the process is highly efficient. For the QC dataset, extraction and evaluation took only 81 seconds.
Conclusion
By addressing the transition sparsity problem through semantic state-mapping and context-aware adjustments, we have developed a scalable method for extracting interpretable WFAs from RNNs. While the method is highly effective at mimicking RNN behavior, future work will focus on using these WFAs for formal verification—proving that an RNN will not produce toxic output under specific conditions—and extending the framework to other architectures like Transformers.
Summary updated