We address the problem of extracting an automaton from a trained recurrent neural network (RNN). We present a novel algorithm that uses exact learning and abstract interpretation to perform efficient extraction of a minimal automaton describing the state dynamics of a given RNN. We use Angluin's L* algorithm as a learner and the given RNN as an oracle, employing abstract interpretation of the RNN for answering equivalence queries. Our technique allows automaton-extraction from the RNN while avoiding state explosion, even when the state vectors are large and fine differentiation is required between RNN states. We experiment with automata extraction from multi-layer GRU and LSTM based RNNs, with state-vector dimensions and underlying automata and alphabet sizes which are significantly larger than in previous automata-extraction work. In some cases, the underlying target language can be described with a succinct automata, yet the extracted automata is large and complex. These are cases in which the RNN failed to learn the intended generalization, and our extraction procedure highlights words which are misclassified by the seemingly "perfect" RNN.

本文提出了一种新算法，利用精确学习和抽象来提取描述给定训练RNN状态动态的确定性有限自动机，使用Angluin的L*算法作为学习器和训练RNN作为oracle，即使状态向量较大且需要进行精细区分，该技术也可以高效地从训练RNN中提取准确的自动机。

使用查询和反例从递归神经网络中提取自动机