Learning Deterministic Finite Automata from Confidence Oracles
This work addresses a specific challenge in formal language learning for researchers in theoretical computer science, representing an incremental advancement by adapting existing learning methods to handle confidence-based oracles.
The paper tackles the problem of learning a deterministic finite automaton (DFA) from a confidence oracle that provides scores indicating confidence about string membership in a target language, aiming to produce a DFA that accurately reflects the oracle's high-confidence predictions.
We discuss the problem of learning a deterministic finite automaton (DFA) from a confidence oracle. That is, we are given access to an oracle $Q$ with incomplete knowledge of some target language $L$ over an alphabet $Σ$; the oracle maps a string $x\inΣ^*$ to a score in the interval $[-1,1]$ indicating its confidence that the string is in the language. The interpretation is that the sign of the score signifies whether $x\in L$, while the magnitude $|Q(x)|$ represents the oracle's confidence. Our goal is to learn a DFA representation of the oracle that preserves the information that it is confident in. The learned DFA should closely match the oracle wherever it is highly confident, but it need not do this when the oracle is less sure of itself.