Active Learning of Temporal Specifications through Distinguishing Queries
Organizations: University of Liverpool
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.
Figures & tables
| Type | Level 1 question | Level 2 question | Patterns in |
|---|---|---|---|
| Undesired behaviour | Does anything happen that should not happen? | Which event should not happen, and when? | , , |
| Missing behaviour | Is something required missing? | Which event is missing, and when is it required? | , , |
| Ordering | Do any events happen in the wrong order? | Which events, and in what order? | , , , , , |
| Completion | Is any task left unfinished? | Which task, and what would complete it? | , , , |
| Repetition | Does anything happen too often or not often enough? | Which event, and how should its repetition change? |
| Free traces , | |
|---|---|
| Size 2 | , |
| Size 3 | , , |
| Size 5 | , , , , , , |
| Size 6 | , , , |
| Size 7 | , , , |
| Environments | |
| Free traces | Environments | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Top- | Exhaustive | Top- | Exhaustive | |||||||||
| Order of rivals | Succ. | Exact | MQ | Succ. | MQ | Eq. | Succ. | Exact | MQ | Succ. | MQ | Eq. |
| Enumeration | 92 | 77 | 15.5 | 100 | 16.2 | 14.2 | 40 | 20 | 8.7 | 80 | 12.5 | 310 |
| Semantic (closest) | 64 | 56 | 13.5 | 100 | 15.9 | 20.1 | 40 | 20 | 8.6 | 80 | 12.2 | 310 |
| Semantic (farthest) | 100 | 85 | 16.1 | 100 | 16.1 | 11.9 | 41 | 20 | 9.5 | 80 | 12.5 | 308 |
| Split | 100 | 85 | 15.7 | 100 | 15.7 | 11.8 | 64 | 25 | 10.6 | 80 | 12.4 | 296 |
| Free traces | Environments | |||||||
|---|---|---|---|---|---|---|---|---|
| MQ | Time | Max | Cand. | MQ | Time | |||
| 2 | 10 | 10.6 (10–13) | 0.01 | 0.03 | 0.2 | 20 | 8.7 (5–11) | 0.02 |
| 3 | 15 | 11.4 (10–13) | 0.01 | 0.02 | 1.0 | 10 | 10.5 (7–13) | 0.02 |
| 5 | 35 | 15.7 (10–20) | 0.10 | 0.11 | 55.8 | 45 | 14.0 (9–21) | 0.19 |
| 6 | 20 | 18.6 (14–22) | 1.07 | 1.32 | 536 | 5 | 18.4 (17–19) | 1.02 |
| 7 | 20 | 20.9 (13–32) | 7.94 | 10.70 | 3,944 | – | – | – |
| Progr. | MONA | SAT | |||||
| Time | Mem. | Time | Mem. | Time | Mem. | ||
| 2 | 3 | 0.83 | 281 | 0.78 | 281 | 0.89 | 315 |
| 3 | 4 | 0.79 | 281 | 0.80 | 281 | 0.98 | 316 |
| 5 | 6 | 0.87 | 290 | 0.97 | 290 | 1.63 | 356 |
| 6 | 7 | 1.81 | 350 | 1.98 | 352 | 3.03 | 415 |
| 7 | 8 | 8.82 | 702 | 9.92 | 728 | 22.35 | 486 |
| Free traces | Environments | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Succ. | Exhaustive | Succ. | Exhaustive | |||||||
| Hints | Top- | Exh. | MQ | Cand. | Time | Top- | Exh. | MQ | Cand. | Time |
| None | 92/100 | 100/100 | 16.2 | 916 | 1.83 | 40/80 | 80/80 | 12.5 | 57 | 0.18 |
| Level 1, ranking | 95/100 | 100/100 | 16.0 | 916 | 1.84 | 64/80 | 80/80 | 12.4 | 57 | 0.20 |
| Level 1, pruning | 94/100 | 100/100 | 14.6 | 710 | 1.56 | 54/80 | 80/80 | 10.5 | 46 | 0.12 |
| None † | 66/70 | 70/70 | 16.0 | 964 | 1.94 | 25/55 | 55/55 | 13.7 | 77 | 0.23 |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| Environment | States | Targets |
|---|---|---|
| Office world | 108 | 7 |
| Taxi | 101 | 3 |
| DoorKey | 62 | 4 |
| DoorKey | 154 | 2 |
Active Learning
Active learning selects the examples, labels, features, or experiments most useful for improving a model under limited budgets.
See all 322 papers