通过区分查询主动学习时序规约:基于 LTLf 的框架提出
Active Learning of Temporal Specifications through Distinguishing Queries
AI 导读
一篇 arXiv 论文提出面向 LTLf 的主动学习框架,教师只需标注轨迹并回答自然语言问题,学习者通过枚举版本空间生成区分候选公式的轨迹。理论方面证明了与观测样例的一致性、有界假设类内的可识别性与 PAC 保证。
正文 · 原文
Abstract:Temporal specifications are essential for verification and monitoring, yet writing formulas that capture the intended behaviour is difficult. Active learning derives such specifications through interaction between a learner and a teacher, but remains underexplored for temporal logics. Existing approaches require the teacher to answer equivalence queries and to construct counterexamples, and they often rely on SAT-based learning procedures that restart the search after each new example. We present an active-learning framework for LTLf in which the teacher only labels traces and answers natural-language questions about the intended behaviour. The learner maintains an enumerated version space of candidate formulas, generates traces that distinguish candidates, and uses the teacher's hints to rank candidates or to restrict the search. We prove consistency with the observed examples, identification within bounded hypothesis classes with a bound on the number of queries, and a PAC guarantee for the final hypothesis. In experiments with a simulated teacher on 36 targets, including targets in four standard environments, the learner identifies every target when it compares all rivals, with fewer than seven queries beyond an initial sample of ten traces on average. Correct hints reduce the number of queries by up to 16% and the number of generated candidates by a fifth, and hints used for ranking never prevent identification, even when incorrect. Our enumeration-based version space is faster than the SAT-based approach of previous learners at every target size.
| Subjects: | Logic in Computer Science (cs.LO); Artificial Intelligence (cs.AI) |
| Cite as: | arXiv:2611.17866 [cs.LO] |
| (or arXiv:2611.17866v1 [cs.LO] for this version) | |
| https://doi.org/10.48550/arXiv.2611.17866 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Rajarshi Roy [view email]
[v1]
Fri, 13 Nov 2026 07:55:29 UTC (126 KB)
来源:arXiv cs.AI · arxiv.org