Observation Tree Approach: Active Learning Relying on Testing
Observation Tree Approach: Active Learning Relying on Testing
复制标题
观察树法：依靠测试的主动学习
DOI：
10.1093/comjnl/bxz056
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
K. Bogdanov
中科院分区：
文献类型：
--
作者：
Michal Soucha;K. Bogdanov
有限状态机（FSM）的主动学习和测试的对应关系已经知道了一段时间，但是，它没有被用于学习。我们提出了一个新的框架称为观察树的方法，允许使用测试理论，以提高主动学习的性能。三个新的学习算法，实现观察树方法的改进。在最低限度的适当教师提供反例的情况下，它们的性能优于标准学习算法，例如L* 算法。此外，他们还可以显着减少对教师的依赖，使用额外的状态的假设，这是在FSM的测试中建立良好的。这是非常有帮助的，因为如果一个人学习一个黑盒子的模型，比如一个只能通过网络访问的系统，那么老师就不必在场。
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.