Learning Deterministic Finite Automata from Confidence Oracles
Wilson Wu
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 $\Sigma$; the
oracle maps a string $x\in\Sigma^*$ 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.