Active Learning 框架从轨迹标注中学习 LTLf 时序规约
Active Learning of Temporal Specifications through Distinguishing Queries
写 LTLf 公式很痛苦,这篇论文让 learner 只靠轨迹标注加自然语言提示就能猜出目标公式,36 个测试目标全部识别成功。做形式化验证或监控的朋友可以看看,比以往 SAT-based 的学法更快也更好交互。
一篇 arXiv 论文提出针对 LTLf(有限轨迹线性时序逻辑)的主动学习框架,用于自动推导验证与监控所需的时序规约。与传统方法要求 teacher 回答等价查询并构造反例不同,该框架中 teacher 只需标注轨迹并回答自然语言问题,降低了交互门槛。
技术上,learner 维护一个枚举式版本空间(version space)存放候选公式,主动生成能区分候选公式的轨迹,并利用 teacher 的提示(hints)对候选排序或收缩搜索范围。论文证明了一致性、有界假设类内带查询次数上界的可识别性,以及最终假设的 PAC 保证。
实验在 36 个目标(含 4 个标准环境中的目标)上进行:learner 比较全部候选时能识别每个目标,在 10 条初始轨迹之外平均仅需不到 7 次查询;正确提示最多减少 16% 的查询量和五分之一的候选数,错误提示用于排序也不会阻止识别。枚举式版本空间在所有目标规模上都快于以往基于 SAT 的学习方法。
Active Learning of Temporal Specifications through Distinguishing Queries
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.
This report is categorized under AITOP's "Papers" desk. Within our cross-regional analytical framework, it directly maps to AI developer toolchains, coding agents, and engineering workflows. Key entities and technical topics under continuous tracking include LTLf, formal verification, active learning, temporal logic.
Source attribution: curated from arXiv cs.AI (@Rajarshi Roy, Xiaowei Huang).