Analyzing robustness of Angluin’s \(L^*\) algorithm in presence of noise. (English) Zbl 07872346
Summary: 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.
MSC:
| 68-XX | Computer science |
References:
| [1] | L. Ye et al Vol. 20:1 |
| [2] | Kousar Aslam, Loek Cleophas, Ramon Schiffelers, and Mark van den Brand. Interface protocol inference to aid understanding legacy software components. Softw. Syst. Model., 19(6):1519-1540, nov 2020. doi:10.1007/s10270-020-00809-2. · doi:10.1007/s10270-020-00809-2 |
| [3] | Dana Angluin and Philip D. Laird. Learning from noisy examples. Mach. Learn., 2(4):343-370, 1987. doi:10.1023/A:1022873112823. · doi:10.1023/A:1022873112823 |
| [4] | Dana Angluin. Learning regular sets from queries and counterexamples. Inf. Comput., 75(2):87-106, 1987. doi:10.1016/0890-5401(87)90052-6. · Zbl 0636.68112 · doi:10.1016/0890-5401(87)90052-6 |
| [5] | Nader H. Bshouty, Nadav Eiron, and Eyal Kushilevitz. PAC learning with nasty noise. Theoretical Computer Science, 288(2):255-275, 2002. Algorithmic Learning Theory. doi: 10.1016/S0304-3975(01)00403-0. · Zbl 1061.68081 · doi:10.1016/S0304-3975(01)00403-0 |
| [6] | A. W. Biermann and J. A. Feldman. On the synthesis of finite-state machines from samples of their behavior. IEEE Trans. Comput., 21(6):592-597, jun 1972. doi:10.1109/TC.1972.5009015. 22:22 L. Ye et al Vol. 20:1 · Zbl 0243.94039 · doi:10.1109/TC.1972.5009015 |
| [7] | Alan W. Biermann and Jerome A. Feldman. A survey of results in grammatical inference. In S. Watanabe, editor, Frontiers of Pattern Recognition, pages 31-54. Academic Press, New York, 1972. doi:10.1016/B978-0-12-737140-5.50007-5. · Zbl 0255.68025 · doi:10.1016/B978-0-12-737140-5.50007-5 |
| [8] | Benedikt Bollig, Peter Habermehl, Carsten Kern, and Martin Leucker. Angluin-style learning of nfa. In Proceedings of the 21st International Joint Conference on Artificial Intelligence, IJCAI’09, page 1004-1009. Morgan Kaufmann Publishers Inc., 2009. doi:10.5555/1661445.1661605. · doi:10.5555/1661445.1661605 |
| [9] | Alexander Clark and Rémi Eyraud. Polynomial identification in the limit of substitutable context-free languages. Journal of Machine Learning Research, 8:1725-1745, dec 2007. doi: 10.5555/1314498.1314556. · Zbl 1222.68093 · doi:10.5555/1314498.1314556 |
| [10] | Christos G. Cassandras and Stephane Lafortune. Introduction to Discrete Event Systems. Springer Publishing Company, Incorporated, 2010. doi:10.1007/978-0-387-68612-7. · Zbl 1165.93001 · doi:10.1007/978-0-387-68612-7 |
| [11] | Alexander Clark. Distributional learning of some context-free languages with a minimally adequate teacher. In Grammatical Inference: Theoretical Results and Applications, ICGI’10, page 24-37. Springer-Verlag, 2010. doi:10.5555/1886263.1886269. · Zbl 1291.68188 · doi:10.5555/1886263.1886269 |
| [12] | Scott E. Decatur. Pac learning with constant-partition classification noise and applications to decision tree induction. In Proceedings of the Fourteenth International Conference on Machine Learning, ICML ’97, page 83-91, San Francisco, CA, USA, 1997. Morgan Kaufmann Publishers Inc. [FBLJ + 21] Daniel Furelos-Blanco, Mark Law, Anders Jonsson, Krysia Broda, and Alessandra Russo. Induction and exploitation of subgoal automata for reinforcement learning. J. Artif. Int. Res., 70:1031-1116, may 2021. doi:10.1613/jair.1.12372. · Zbl 1512.68275 · doi:10.1613/jair.1.12372 |
| [13] | Paul Fiterau-Brostean and Falk Howar. Learning-based testing the sliding window behavior of TCP implementations. In Laure Petrucci, Cristina Seceleanu, and Ana Cavalcanti, editors, Critical Systems: Formal Methods and Automated Verification -FMICS-AVoCS 2017, Turin, Italy, September 18-20, 2017, Proceedings, volume 10471 of Lecture Notes in Computer Science, pages 185-200. Springer, 2017. doi:10.1007/978-3-319-67113-0_12. · doi:10.1007/978-3-319-67113-0_12 |
| [14] | Paul Fiterau-Brostean, Ramon Janssen, and Frits W. Vaandrager. Combining model learning and model checking to analyze TCP implementations. In Swarat Chaudhuri and Azadeh Farzan, editors, 28th International Conference on Computer Aided Verification, CAV 2016, Toronto, ON, Canada, July 17-23, 2016, Part II, volume 9780 of Lecture Notes in Computer Science, pages 454-471. Springer, 2016. doi:10.1007/978-3-319-41540-6_25. [FLP + 17] Paul Fiterau-Brostean, Toon Lenaerts, Erik Poll, Joeri de Ruiter, Frits W. Vaandrager, and Patrick Verleg. Model learning and model checking of SSH implementations. In Hakan Erdogmus and Klaus Havelund, editors, Proceedings of the 24th ACM SIGSOFT International SPIN Symposium on Model Checking of Software, Santa Barbara, CA, USA, July 10-14, 2017, pages 142-151. ACM, 2017. doi:10.1145/3092282.3092289. · doi:10.1145/3092282.3092289 |
| [15] | E Mark Gold. Complexity of automaton identification from given data. Information and Control, 37(3):302 -320, 1978. doi:10.1016/S0019-9958(78)90562-4. · Zbl 0376.68041 · doi:10.1016/S0019-9958(78)90562-4 |
| [16] | HIS + 12] Falk Howar, Malte Isberner, Bernhard Steffen, Oliver Bauer, and Bengt Jonsson. Inferring semantic interfaces of data structures. In Tiziana Margaria and Bernhard Steffen, editors, ISoLA 2012, Heraklion, Crete, Greece, October 15-18, 2012, Part I, volume 7609 of Lecture Notes in Computer Science, pages 554-571. Springer, 2012. doi:10.1007/978-3-642-34026-0_41. · doi:10.1007/978-3-642-34026-0_41 |
| [17] | Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. doi:10.2307/2282952. · Zbl 0127.10602 · doi:10.2307/2282952 |
| [18] | Natasha Yogananda Jeppu, Thomas Melham, Daniel Kroening, and John O’Leary. Learning concise models from long execution traces. In Proceedings of the 57th ACM/EDAC/IEEE Design Automation Conference, DAC ’20. IEEE Press, 2020. doi:10.5555/3437539.3437631. · doi:10.5555/3437539.3437631 |
| [19] | Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. J. ACM, 45(6):983-1006, 1998. doi:10.1145/293347.293351. · Zbl 1065.68605 · doi:10.1145/293347.293351 |
| [20] | Michael J. Kearns and Umesh V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994. doi:10.7551/mitpress/3897.001.0001. · doi:10.7551/mitpress/3897.001.0001 |
| [21] | Oded Maler and Amir Pnueli. On the learnability of infinitary regular sets. In Proceedings of the Fourth Annual Workshop on Computational Learning Theory, COLT ’91, page 128-138. Morgan Kaufmann Publishers Inc., 1991. doi:10.5555/114836.114848. · doi:10.5555/114836.114848 |
| [22] | Franz Mayr and Sergio Yovine. Regular inference on artificial neural networks. In Andreas Holzinger, Peter Kieseberg, A Min Tjoa, and Edgar R. Weippl, editors, Proceedings of Interna-tional Cross-Domain Conference for Machine Learning and Knowledge Extraction, CD-MAKE 2018, Hamburg, Germany, August 27-30, 2018, volume 11015 of Lecture Notes in Computer Science, pages 350-369. Springer, 2018. doi:10.1007/978-3-319-99740-7_25. · doi:10.1007/978-3-319-99740-7_25 |
| [23] | J. R. Quinlan. The effect of noise on concept learning. In Machine Learning, An Artificial Intelligence Approach Volume II, chapter 6, pages 149-166. Morgan Kaufmann, 1986. |
| [24] | R. L. Rivest and R. E. Schapire. Inference of finite automata using homing sequences. In Proceedings of the twenty-first annual ACM symposium on Theory of computing, STOC ’89, page 411-420. Association for Computing Machinery, 1989. doi:10.1145/73007.73047. · doi:10.1145/73007.73047 |
| [25] | Muzammil Shahbaz and Roland Groz. Inferring mealy machines. In Proceedings of the 2nd World Congress on Formal Methods, FM ’09, page 207-222. Springer-Verlag, 2009. doi:10. 1007/978-3-642-05089-3_14. · doi:10.1007/978-3-642-05089-3_14 |
| [26] | Robert H. Sloan. Four types of noise in data for pac learning. Inf. Process. Lett., 54(3):157-162, may 1995. doi:10.1016/0020-0190(95)00016-6. · Zbl 1004.68539 · doi:10.1016/0020-0190(95)00016-6 |
| [27] | Ray J. Solomonoff. A formal theory of inductive inference. Inf. Control., 7(1, 2):1-22, 224-254, 1964. doi:10.1016/S0019-9958(64)90223-2. · doi:10.1016/S0019-9958(64)90223-2 |
| [28] | Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134-1142, 1984. doi: 10.1145/1968.1972. · Zbl 0587.68077 · doi:10.1145/1968.1972 |
| [29] | Wil M. P. van der Aalst. Process mining. CACM, 55(8):76-83, 2012. doi:10.1145/2240236. 2240257. · doi:10.1145/2240236.2240257 |
| [30] | Gail Weiss, Yoav Goldberg, and Eran Yahav. Extracting automata from recurrent neural networks using queries and counterexamples. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80, pages 5247-5256. PMLR, 10-15 Jul 2018. doi:10.48550/arXiv.1711.09576. · doi:10.48550/arXiv.1711.09576 |
| [31] | R. M. Wharton. Approximate language identification. Information and Control, 26(3):236 -255, 1974. doi:10.1016/S0019-9958(74)91369-2. · Zbl 0309.68063 · doi:10.1016/S0019-9958(74)91369-2 |
| [32] | Ryo Yoshinaka and Alexander Clark. Polynomial time learning of some multiple context-free languages with a minimally adequate teacher. In Proceedings of the 15th and 16th International Conference on Formal Grammar, FG’10/FG’11, page 192-207, Berlin, Heidelberg, 2010. Springer-Verlag. doi:10.1007/978-3-642-32024-8_13. · Zbl 1370.68151 · doi:10.1007/978-3-642-32024-8_13 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
