跳到正文
arXiv cs.AI· Rajarshi Roy, Xiaowei Huang·· 4 小时前AI 评分33

通过区分查询主动学习时序规约:基于 LTLf 的框架提出

Active Learning of Temporal Specifications through Distinguishing Queries

AI 导读

一篇 arXiv 论文提出面向 LTLf 的主动学习框架,教师只需标注轨迹并回答自然语言问题,学习者通过枚举版本空间生成区分候选公式的轨迹。理论方面证明了与观测样例的一致性、有界假设类内的可识别性与 PAC 保证。

正文 · 原文

View PDF HTML (experimental)

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