Datensatz

Zusammenfassung

Angluin's L* algorithm learns the minimal (complete) deterministic finite
automaton (DFA) of a regular language using membership and equivalence queries.
Its probabilistic approximatively correct (PAC) version substitutes an
equivalence query by a large enough set of random membership queries to get a
high level confidence to the answer. Thus it can be applied to any kind of
(also non-regular) device and may be viewed as an algorithm for synthesizing an
automaton abstracting the behavior of the device based on observations. Here we
are interested on how Angluin's PAC learning algorithm behaves for devices
which are obtained from a DFA by introducing some noise. More precisely we
study whether Angluin's algorithm reduces the noise and produces a DFA closer
to the original one than the noisy device. We propose several ways to introduce
the noise: (1) the noisy device inverts the classification of words w.r.t. the
DFA with a small probability, (2) the noisy device modifies with a small
probability the letters of the word before asking its classification w.r.t. the
DFA, and (3) the noisy device combines the classification of a word w.r.t. the
DFA and its classification w.r.t. a counter automaton. Our experiments were
performed on several hundred DFAs.
Our main contributions, bluntly stated, consist in showing that: (1)
Angluin's algorithm behaves well whenever the noisy device is produced by a
random process, (2) but poorly with a structured noise, and, that (3) almost
surely randomness yields systems with non-recursively enumerable languages.