Linear temporal logic (LTL) is a specification language for finite sequences (called traces) widely used in program verification, motion planning in robotics, process mining, and many other areas. We consider the problem of learning LTL formulas for classifying traces; despite a growing interest of the research community, existing solutions suffer from two limitations: they do not scale beyond small formulas, and they may exhaust computational resources without returning any result. We introduce a new algorithm addressing both issues: our algorithm is able to construct formulas an order of magnitude larger than previous methods, and it is anytime, meaning that it in most cases successfully outputs a formula, albeit possibly not of minimal size. We evaluate the performances of our algorithm using an open source implementation against publicly available benchmarks.


翻译:线性时间逻辑(LTL)是程序核查、机器人运动规划、工艺采矿和其他许多领域广泛使用的限定序列(所谓痕量)的具体说明语言。我们考虑了学习LTL公式对痕量进行分类的问题;尽管研究界越来越感兴趣,但现有解决方案存在两个局限性:它们的规模不超出小公式,它们可能耗尽计算资源而不产生任何结果。我们引入了一个新的算法,处理这两个问题:我们的算法能够构建比以往方法大得多的层次的公式,而且随时可以,这意味着它在大多数情况下成功地输出出一种公式,尽管可能不是最小的公式。我们用开放源执行来对照公开的基准来评估我们的算法的绩效。

0
下载
关闭预览

相关内容

专知会员服务
52+阅读 · 2020年9月7日
【CIKM2020】神经逻辑推理,Neural Logic Reasoning
专知会员服务
49+阅读 · 2020年8月25日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2021年12月3日
A Survey of Deep Learning for Scientific Discovery
Arxiv
29+阅读 · 2020年3月26日
Advances and Open Problems in Federated Learning
Arxiv
18+阅读 · 2019年12月10日
Arxiv
6+阅读 · 2019年11月14日
A Comprehensive Survey on Transfer Learning
Arxiv
121+阅读 · 2019年11月7日
Risk-Aware Active Inverse Reinforcement Learning
Arxiv
7+阅读 · 2019年1月8日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
vae 相关论文 表示学习 1
CreateAMind
12+阅读 · 2018年9月6日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【学习】(Python)SVM数据分类
机器学习研究会
6+阅读 · 2017年10月15日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
相关论文
Arxiv
0+阅读 · 2021年12月3日
A Survey of Deep Learning for Scientific Discovery
Arxiv
29+阅读 · 2020年3月26日
Advances and Open Problems in Federated Learning
Arxiv
18+阅读 · 2019年12月10日
Arxiv
6+阅读 · 2019年11月14日
A Comprehensive Survey on Transfer Learning
Arxiv
121+阅读 · 2019年11月7日
Risk-Aware Active Inverse Reinforcement Learning
Arxiv
7+阅读 · 2019年1月8日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Top
微信扫码咨询专知VIP会员