Observation Tree Approach: Active Learning Relying on Testing. (3rd July 2019)

• Record Type: Journal Article
• Authors: Soucha, Michal; Bogdanov, Kirill
• Is Part Of: Computer journal. Volume 63:Number 9(2020)
• Page Start: 1298
• Page End: 1310
• Publication Date: 2019-07-03
• Subjects: model inference -- active learning -- finite-state machine -- automata inference -- observation tree -- software testing; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxz056
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: The correspondence of active learning and testing of finite-state machines (FSMs) has been known for a while; however, it was not utilized in the learning. We propose a new framework called the observation tree approach that allows one to use the testing theory to improve the performance of active learning. The improvement is demonstrated on three novel learning algorithms that implement the observation tree approach. They outperform the standard learning algorithms, such as the L* algorithm, in the setting where a minimally adequate teacher provides counterexamples. Moreover, they can also significantly reduce the dependency on the teacher using the assumption of extra states that is well-established in the testing of FSMs. This is immensely helpful as a teacher does not have to be available if one learns a model of a black box, such as a system only accessible via a network.