Learning Weighted Automata from Recurrent Neural Networks using Hidden-State Partitioning

Recurrent neural networks (RNNs) are able to learn complex sequential behaviours, but their hidden-state representations make them difficult to interpret. This paper presents a new method for learning Weighted Finite Automata (WFAs) from RNNs. The method works within the standard $L^{\ast }$ active learning framework, where the main challenge is in comparing a hypothesised WFA with an RNN. The key novelty lies in how this comparison is realised, thereby answering equivalence queries. This is achieved through a partitioning of the RNN hidden-state space that is iteratively refined until each partition has been sufficiently explored and has small relative variance. The partitioning guides the search for counterexamples between the RNN and the learned WFA and provides a practical criterion for terminating the algorithm when no significant discrepancy is identified. Theoretical guarantees on the correctness and termination of the extraction procedure are provided under appropriate conditions. An empirical comparison of the approach with existing methods for WFA extraction from RNNs is given, and the experiments show that the proposed method efficiently extracts compact WFAs with high fidelity to the underlying RNN while generally achieving substantially lower extraction times than existing approaches.