一句话：实验分析 Angluin L* 的噪声鲁棒性：随机噪声下表现良好、结构化噪声下较差，并证明随机过程几乎必然产生非递归可枚举语言。
Angluin L* 算法用成员查询和等价查询学习正则语言的最小 DFA；其 PAC 版本用大量随机成员查询替代等价查询，可为任意设备合成自动机抽象。本文研究该 PAC 算法在设备含噪时能否降噪并逼近原始 DFA。作者提出四类噪声：小概率翻转词分类、小概率扰动字母、混合 DFA 与计数器自动机分类，以及由两个包含关系 DFA 随机生成。实验表明：随机噪声下算法表现良好，结构化噪声下较差，且能消除正则指定的病态行为。理论上证明随机性几乎必然导致非递归可枚举语言。
Angluin's L$^*$ algorithm learns the minimal deterministic finite automaton (DFA) of a regular language using membership and equivalence queries. Its probabilistic approximatively correct (PAC) version substitutes an equivalence query by numerous random membership queries to get a high level confidence to the answer. Thus it can be applied to any kind of 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, (3) the noisy device combines the classification of a word w.r.t. the DFA and its classification w.r.t. a counter automaton, and (4) the noisy DFA is obtained by a random process from two DFA such that the language of the first one is included in the second one. Then when a word is accepted (resp. rejected) by the first (resp. second) one, it is also accepted (resp. rejected) and in the remaining cases, it is accepted with probability 0.5. Our main experimental contributions 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) is able to eliminate pathological behaviours specified in a regular way. Theoretically, we show that randomness almost surely yields systems with non-recursively enumerable languages.
@article{paperbot2769,
title = {Analyzing Robustness of Angluin's L$^*$ Algorithm in Presence of Noise},
author = {Lina Ye and Igor Khmelnitsky and Serge Haddad and Benoît Barbot and Benedikt Bollig and Martin Leucker and Daniel Neider and Rajarshi Roy},
journal = {Logical Methods in Computer Science},
volume = {Volume 20, Issue 1},
year = {2024},
doi = {10.46298/lmcs-20(1:22)2024}
}