PaperlayerView exact revision on arXiv

Source-linked AI summary

Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples

Gail Weiss, Yoav Goldberg, Eran Yahav

arXiv:1711.09576v4cs.LGcs.FL

TL;DR

The paper addresses the difficulty of extracting understandable automata from RNNs whose learned behavior may be unclear or overly coarse under fixed partitions. It combines exact learning with adaptive abstraction, achieving small, accurate DFAs for networks corresponding to succinct automata while exposing cases where the network behavior is too complex.

  • Problem

    The paper asks how to extract a DFA observably equivalent to a trained RNN when the network’s learned language and internal behavior are unclear.

  • Method

    The method uses the RNN as an exact-learning teacher for L*, comparing proposed DFAs with abstractions and refining partitions only when concrete inputs justify refinement.

  • Results

    For networks corresponding to succinct automata, the method generally extracts small DFAs with over 99% accuracy with respect to the networks in seconds or tens of seconds.

  • Takeaways & Limitations

    Counterexamples can reveal incorrect patterns and adversarial inputs that trained RNNs learned without awareness, including deviations from intended languages.

  • Takeaways & Limitations

    Some networks exhibit behavior too complicated for a small DFA, and convergence between an abstraction and L* DFA does not guarantee equivalence with the RNN.

Abstract

from arXiv · show

We present a novel algorithm that uses exact learning and abstraction to extract a deterministic finite automaton describing the state dynamics of a given trained RNN. We do this using Angluin's L* algorithm as a learner and the trained RNN as an oracle. Our technique efficiently extracts accurate automata from trained RNNs, even when the state vectors are large and require fine differentiation.

1. Introduction

The paper seeks deterministic finite automata that are observably equivalent to trained RNN-acceptors, using exact learning with the RNN as teacher. Its abstraction-based equivalence procedure returns reliable counterexamples or justified refinements and exposes network deviations from intended languages.

  • Motivation: RNNs process arbitrary-length sequences through timestep-wise state vectors, whose classifications define an RNN-acceptor.The classifier is trained alongside the recurrent network.
  • Motivation: The goal is to extract a DFA that classifies sequences observably equivalently to a trained RNN, although exact language equality is more difficult.
  • Exact Learning: Exact learning uses membership and equivalence queries, with counterexamples returned when a hypothesis disagrees with the teacher.
  • Our Approach: The RNN answers membership queries directly, while finite abstraction and L* jointly handle equivalence queries through counterexamples and abstraction refinements.
  • Contributions: The approach guarantees no incorrect counterexamples or unnecessary refinements, yielding no false negatives.
  • Contributions: Experiments on simple and complicated languages show descriptive automata where previous approaches fail, including counterexamples that reveal deviations from target languages.

2. Related Work

Earlier extraction methods partition the continuous RNN state space before exploration, creating scalability and parameter-selection problems. Their fixed partitions cannot recognize or correct overly coarse behavior during extraction.

  • Existing Approaches: Previous approaches explore partitioned RNN state spaces using BFS or transition sampling, differing mainly in how they define the partition.
  • Quantization: Equal-interval quantization suffers from state-space explosion and does not scale from networks with eight hidden values to modern networks with hundreds or thousands.
  • Clustering: Unsupervised clustering depends strongly on the chosen cluster count and on how reachable network states are sampled.
  • Limitations: Fixed partitioning offers no mechanism to detect or overcome overly coarse behavior, so methods are rerun with different parameters and the best DFA is selected heuristically.
  • Future Direction: Existing techniques treat all RNN dimensions as one state, leaving fast and slow internal-state distinctions as a possible future direction.

3. Background

The background formalizes RNN-acceptors as recurrent state-transition and classification functions, then describes abstraction-based DFA extraction and L* learning from query-answering teachers.

  • RNN Acceptors: An RNN applies gR recursively to input vectors, mapping a state vector and input to the next state; a binary acceptor adds fR to classify states.
  • Network Abstraction: Network abstraction maps continuous states into partitions and extracts a DFA by exploring partition transitions from the initial network state.
  • The L* Algorithm: L* learns a DFA from a teacher answering membership queries and equivalence queries, returning counterexamples when a proposed DFA is rejected.

4. Learning Automata from RNNs using L*

The method turns a trained RNN into an L* teacher and answers equivalence queries by comparing proposed DFAs with progressively refined network abstractions. Time or size limits allow returning the latest DFA when convergence is impractical, but abstraction convergence alone does not prove RNN equivalence.

  • Membership Queries: The RNN classifier answers membership queries directly by checking whether each word is accepted or rejected.
  • Equivalence Queries: For an equivalence query, the proposed DFA is compared with an abstraction AR,p, and any disagreement is evaluated by the RNN.
  • Equivalence Queries: The RNN evaluation turns a disagreement into either a counterexample for L* or a partition refinement followed by renewed comparison.
  • Practical Limits: Practical time or size limits return the last L* DFA when convergence may take a long time or produce more than 30,000 states.
  • Practical Limits: Convergence between the proposed DFA and abstraction does not guarantee equivalence between the DFA and the original RNN.

5. Notations

The paper formalizes automata and RNN-acceptors through state transitions, recursive sequence processing, and word classifications. It also explains the shorthand used to compare their classifications.

  • Automaton and Classification Function: A deterministic automaton A consists of an alphabet, states, an initial state, accepting states, and a transition function.Its recursive transition function maps a state and sequence to the state reached after processing that sequence.
  • Binary RNN-acceptor: An RNN applies its transition function recursively over input sequences, producing continuous network states after each prefix.The notation ĝ_R captures this recursive application from any R-state over a sequence.
  • Binary RNN-acceptor: An RNN-acceptor can be viewed as a deterministic state machine whose state space may be infinite.This interpretation motivates extracting a finite automaton that matches the network’s sequence classifications.
  • Shorthand: Returning the final abstraction instead of counterexamples may produce less accurate automata because it lacks L*’s separating suffix strings.The paper therefore emphasizes counterexample-driven refinement during equivalence checking.
  • Shorthand: The shorthand f_A(w) and f_R(w) denotes the classification assigned to word w after processing it from each system’s initial state.This notation supports direct comparison between automaton and RNN classifications.

6. Answering Equivalence Queries

The equivalence procedure traverses a proposed DFA and an RNN abstraction in parallel, validates disagreements against the RNN, and either returns genuine counterexamples or refines the abstraction. Its guarantees ensure that extracted states and refinements are justified by concrete network behavior.

  • 6.1. Overview: The procedure searches for disagreements between a proposed DFA and the RNN abstraction, then checks each candidate word’s true classification in the RNN.A disagreement with the RNN becomes a counterexample; otherwise the partitioning is refined and exploration restarts.
  • 6.1. Overview: Every returned counterexample is guaranteed to satisfy f_A(w) ≠ f_R(w), so the procedure produces no false negatives.This guarantee follows from validating proposed disagreements against the RNN before returning them.
  • 6.1. Overview: Every final A-state and every partition refinement is justified by concrete input to the network.Consequently, extracted DFA complexity reflects network complexity rather than uncorrected overly fine partitioning.
  • 6.2. Conflicts: Parallel exploration detects classification conflicts when the abstraction and RNN disagree, and clustering conflicts when one A-state is associated with multiple disagreeing L-states.The traversal checks both conflict types while associating abstract states with L* states.
  • 6.3. Conflict Resolution and Counterexample Generation: For clustering conflicts, differentiating suffixes expose disagreement between paths, after which the RNN determines whether to return a counterexample or refine the partition.The method tests relevant path extensions against the RNN and prioritizes returning a genuine counterexample over refinement.
  • 6.3. Conflict Resolution and Counterexample Generation: Shortest available counterexamples are returned because experiments found that long counterexamples could inflate the DFA without generalizing well.This choice is an empirical design decision aimed at avoiding unnecessary automaton growth.

7. Abstraction and Refinement

The abstraction begins with a partition of the RNN state space and refines it when equivalence checking exposes insufficient separation. SVM-based refinement adds states conservatively, while safeguards reduce premature termination from overly coarse initial abstractions.

  • 7. Abstraction and Refinement: The method starts from an initial partitioning and refines it using an RNN-state h and comparison set H.The refinement seeks to generalize the information in h and H without invoking excessive refinements.
  • 7. Abstraction and Refinement: Each refinement increases the number of A-states by exactly one, and the method is unaffected by the length of the R-states.This gives the abstraction a conservative growth pattern even for large state vectors.
  • 7.1. Initial Partitioning: The initial partition maps every R-state to one abstract state, keeping the starting abstraction as small as possible.A separate aggressive first refinement is used because the coarse initialization can otherwise accept small but incorrect DFAs.
  • 7.2. Support-Vector based Refinement: SVM refinement uses an RBF-kernel classifier to separate h from H and represents successive splits as a decision tree whose leaves are A-states.The RBF kernel provides nonlinear partitioning, while the max-margin property allocates a region around h.
  • 7.2. Support-Vector based Refinement: If an SVM fails to separate all required states, the method still separates at least one state from h and can refine further during later exploration.This may violate the strongest refinement condition but does not prevent the method from seeking counterexamples to equivalence.
  • 7.3. Initial Refinement: Two safeguards against premature termination are shortest accepting and rejecting samples plus an aggressive first refinement.The samples prevent termination on a single-state automaton, while the first refinement generates a manageable number of A-states.
  • 7.3.1. Initial Refinement: The initial refinement splits along dimensions with the largest gaps, with d user-controlled and values around 7–10 generally providing a strong starting partition.The resulting decision tree focuses on dimensions showing the greatest deviation between the state being split and comparison states.

8. Experimental Results

Experiments show that query-driven extraction recovers small, accurate DFAs from regular-language RNNs and exposes deviations that random sampling can miss. Its effectiveness is strongest when the network itself admits a succinct automaton, while poorly generalized or highly complex behavior can cause large automata and timeouts.

  • Regular languages: The method correctly extracted the seven Tomita target grammars from GRUs in under 2 seconds, despite one network reaching 99.94% dev accuracy.Each GRU had two layers and hidden size 100; the other six reached 100% dev accuracy.
  • Regular languages: Across randomly generated 10-state regular languages, extracted DFAs were small and highly accurate even on sequences of length 1000.Each table row summarizes three experiments, with nine random DFAs generated, trained, and extracted overall.
  • Comparison with other extraction methods: Compared with quantization, the method produced small accurate DFAs within 30 seconds, whereas quantization often exceeded 60,000 states and had near-zero coverage at length 1000.Quantized automata could still reach 99+% accuracy on covered sequences, potentially because large quantization assigned separate states to explored RNN states.
  • Method behavior: The extraction maintains a complete DFA that continuously improves, enabling it to return useful small approximations without parameter tuning when succinct representations exist.The experiments used initial refinement depth 10, and no parameter tuning was required.
  • Counterexamples: Shortest counterexamples prevented automata blow-up and revealed adversarial inputs that random sampling failed to find, including unbalanced parentheses accepted by a seemingly perfect network.The parentheses network appeared perfect on more than 44,000 training samples, yet the method found a misclassification.
  • Failure cases and limitations: For email and other poorly generalized networks, the method exposed misclassified examples but could produce large or nonrepresentative DFAs and time out during refinement.An email network with 100% train and test accuracy yielded counterexamples quickly; a 134-state proposal had nearly random train accuracy before timeout.
  • Failure cases and limitations: The results caution that strong train- or test-set performance may coexist with brittle RNN generalization and should therefore be interpreted with extreme caution.The method also found simple misclassified examples in many RNN-acceptors with 100% train and test accuracy on large test sets.

9. Conclusions

The method extracts DFAs from RNNs through exact learning without assumptions about internal architecture or hidden-state size. It can reveal learned behaviors, including inaccuracies, while producing compact and accurate approximations quickly.

  • The technique applies to any RNN architecture, including LSTM and GRU models, because it makes no assumptions about internal configuration.
  • The method is unaffected by hidden state-size and requires little parameter tuning or prior information beyond the input alphabet and two labeled examples.
  • The extraction is guaranteed not to produce a DFA more complicated than the language represented by the RNN.
  • Counterexamples can expose incorrect patterns learned by the network without the researchers’ awareness.
  • For networks representable by succinct automata, extraction generally yields small DFAs with over 99% accuracy against the network in seconds or tens of seconds.Existing approaches often require orders of magnitude more time and may return DFAs with tens of thousands of states.

A. Angluin’s L* Algorithm

Angluin’s L* algorithm learns a DFA by maintaining an observation table, refining it through membership queries, and testing consistent hypotheses with equivalence queries. Counterexamples trigger further refinement until the hypothesis matches the teacher.

  • Membership queries fill T by asking the teacher whether strings belong to the target language.
  • L* learns an unknown regular language over alphabet Σ and outputs a DFA accepting that language.
  • The algorithm maintains observation table (S, E, T), where S contains state-reaching words, E contains distinguishing experiments, and T records membership outcomes.
  • When the table is closed and consistent, L* constructs a hypothesis automaton and submits an equivalence query.A disagreement produces a counterexample for subsequent refinement.
  • The learner begins with the empty word and checks state-reaching prefixes and letter continuations for classification consistency.

B.1. Random Regular Languages

The experiments evaluate extraction on random regular languages and more complex sequence languages using GRU and LSTM networks. The method often recovers target behavior, while counterexamples expose cases where highly accurate networks learned more complex or incorrect concepts.

  • Random Regular Languages: The random-language experiments used 2-layer GRU and LSTM networks, 30-second extraction limits, and three networks per parameter combination.
  • Random Regular Languages: 36 of 54 random-language experiments reached equivalence with a regular language identical to the network’s target language.One LSTM extraction reached equivalence too easily with a two-state automaton that poorly matched the network.
  • Random Regular Languages: A-priori quantization with level 2 did not complete within 50 seconds on these networks.Larger hidden sizes slowed transition computation, causing less state-space exploration and smaller partial DFAs within the time limit.
  • COUNTING: For balanced parentheses, L* generated automata for increasing nesting depths before finding a counterexample showing that the GRU had not generalized correctly.The extracted automaton was almost, but not quite, correct for the intended language.
  • COUNTING: The 31-letter-language network reached 100% train and test accuracy, yet accepted aca11, which was outside its target language.
Loading 1711.09576v4…