TL;DR — Extends Angluin's L* algorithm from boolean DFAs to weighted automata. Given a black-box that assigns weights to strings, the algorithm learns a minimal deterministic weighted automaton using membership queries and equivalence queries with counterexamples.
The Problem
Angluin's L* algorithm is a classic result: it can learn any regular language (represented as a DFA) by asking two types of questions—membership queries ("is this string in the language?") and equivalence queries ("is my current hypothesis correct? if not, give me a counterexample"). The algorithm is elegant, efficient, and guaranteed to converge.
But many real systems don't just classify strings as accept/reject. They produce continuous outputs: probabilities, scores, confidence values. A recurrent neural network doesn't just say "yes" or "no"—it assigns a real-valued weight to each input string. How do you learn a compact automaton that captures this weighted behavior?
The challenge is to generalize L* from the boolean world (0/1) to the weighted world (real numbers), while preserving its key properties: polynomial query complexity, guaranteed convergence, and minimality of the learned automaton.
The Key Idea
The core of L* is the observation table—a matrix whose rows are string prefixes, columns are string suffixes, and entries are boolean (does the concatenation belong to the language?). The algorithm grows this table until it is closed and consistent, then extracts a DFA.
The weighted generalization replaces boolean entries with real-valued weights: the entry for row s and column e is the weight that the target function assigns to the string s · e. But this introduces complications:
- Approximate equivalence: Exact equality of real numbers is fragile. Two rows are considered "equivalent" if their weight vectors are close enough (within a tolerance).
- No simple consistency check: In boolean L*, consistency means equal prefixes must produce equal extensions. In the weighted case, the relationship involves linear algebra over the weight vectors.
- Counterexample processing: When an equivalence query returns a counterexample, the algorithm must decompose it to find where the hypothesis diverges from the target, then add new rows or columns to the table.
The key insight is that the observation table can be viewed through the lens of linear algebra: rows of the table span a vector space, and the rank of this space determines the number of states in the minimal weighted automaton.
Interactive Demo
Weighted L* Algorithm Explorer
Explore how the weighted L* algorithm learns a deterministic weighted automaton from a black-box target. Use the guided walkthrough or query the target yourself.
Observation Table
Hypothesis Automaton
The hidden target automaton assigns weights to strings over the alphabet {a, b}. Query it to discover its behavior, then check if you can guess its structure.
Membership Query
Equivalence Check
Query Log
How It Works
The Observation Table
The observation table T(S, E) is indexed by a set of prefixes S (rows) and suffixes E (columns). Each entry T(s, e) contains the weight assigned by the target function to the concatenation s · e. This is obtained through membership queries.
In the boolean case, each row is a binary vector. In the weighted case, each row is a real-valued vector. The table also includes rows for S · Σ (each prefix extended by one symbol), which are used to check closure.
Closure and Consistency
The table is closed when every row in S · Σ is (approximately) a linear combination of the rows in S. In the boolean case this simplifies to: every extension row matches some existing row. In the weighted case, we need approximate linear dependence.
When the table is closed, we can extract a hypothesis weighted automaton: each distinct row vector in S becomes a state, and transitions are determined by the linear relationships between rows.
Approximate Equivalence
Since we deal with real numbers, exact comparisons are replaced with approximate ones. Two row vectors are considered equivalent if their difference is within a tolerance parameter ε. This tolerance must be chosen carefully: too large and the algorithm conflates distinct states; too small and floating-point noise creates spurious states.
Results
Key result: The weighted L* algorithm successfully extracts interpretable weighted automata from trained RNNs. By treating the RNN as a black box and querying it, the algorithm produces a minimal deterministic weighted automaton that approximates the RNN's behavior, making the learned computation transparent and analyzable.
- The algorithm is polynomial in the number of states of the target automaton and the length of the longest counterexample.
- Applied to RNNs trained on weighted languages, the extracted automata faithfully capture the network's learned computation.
- The extracted automata are minimal—they have the fewest states possible for any equivalent deterministic weighted automaton.
- This provides a principled way to interpret what an RNN has learned: instead of examining opaque weight matrices, we get a clean automaton with labeled states and weighted transitions.