会员服务
线性的 · CC · 学成 · 样例 · 近似 ·
2021 年 2 月 1 日
The Complexity of Learning Linear Temporal Formulas from Examples
翻译：实例中学习线性时间公式的复杂性
Nathanaël Fijalkow,Guillaume Lagarde
Nathanaël Fijalkow,Guillaume Lagarde

In this paper we initiate the study of the computational complexity of learning linear temporal logic (LTL) formulas from examples. We construct approximation algorithms for fragments of LTL and prove hardness results; in particular we obtain tight bounds for approximation of the fragment containing only the next operator and conjunctions, and prove NP-completeness results for many fragments.


翻译：在本文中,我们开始研究从实例中学习线性时间逻辑(LTL)公式的计算复杂性。我们为LTL的碎片构建近似算法,并证明其硬性效果;特别是,我们获得了仅包含下一个操作员和连接的碎片近似近距离的严格限制,并证明了许多碎片的NP完整性结果。
0
下载
关闭预览

相关内容

哥伦比亚大学最新《机器学习》课程，Fall-B 2020 (Machine Learning)
专知会员服务
39+阅读 · 2020年11月3日
【KDD2020】动态图的拉普拉斯变换点检测，Laplacian Change Point Detection for Dynamic Graphs
【KDD2020】动态图的拉普拉斯变换点检测，Laplacian Change Point Detection for Dynamic Graphs
专知会员服务
38+阅读 · 2020年7月3日
因果图，Causal Graphs，52页ppt
因果图，Causal Graphs，52页ppt
专知会员服务
249+阅读 · 2020年4月19日
【阿里巴巴-CVPR2020】频域学习，Learning in the Frequency Domain
【阿里巴巴-CVPR2020】频域学习，Learning in the Frequency Domain
专知会员服务
29+阅读 · 2020年3月14日
【新书：机器学习简介】《A Concise Introduction to Machine Learning》by A.C. Faul (CRC 2019)
【新书：机器学习简介】《A Concise Introduction to Machine Learning》by A.C. Faul (CRC 2019)
专知会员服务
77+阅读 · 2020年2月8日
TensorFlow深度学习，从线性回归到强化学习的深度学习（TensorFlow for Deep Learning From Linear Regression to Reinforcement Learning），附页256页pdf
TensorFlow深度学习，从线性回归到强化学习的深度学习（TensorFlow for Deep Learning From Linear Regression to Reinforcement Learning），附页256页pdf
专知会员服务
46+阅读 · 2020年1月1日
【电子书】机器学习实战（Machine Learning in Action），附PDF
【电子书】机器学习实战（Machine Learning in Action），附PDF
专知会员服务
128+阅读 · 2019年11月25日
【课程】普林斯顿大学19年春季学期《机器学习优化》课程讲义
【课程】普林斯顿大学19年春季学期《机器学习优化》课程讲义
专知会员服务
85+阅读 · 2019年10月29日
2019年机器学习框架回顾
2019年机器学习框架回顾
专知会员服务
36+阅读 · 2019年10月11日
【新书】Python编程基础，669页pdf
【新书】Python编程基础，669页pdf
专知会员服务
195+阅读 · 2019年10月10日
局部学习的特征选择：Local-Learning-Based Feature Selection
局部学习的特征选择：Local-Learning-Based Feature Selection
我爱读PAMI
14+阅读 · 2019年9月20日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Imitation - Reinforcement Learning
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
激活函数初学者指南
激活函数初学者指南
论智
6+阅读 · 2018年5月15日
Reinforcement Learning: An Introduction 2018第二版 500页
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
12+阅读 · 2018年4月27日
Machine Learning：十大机器学习算法
Machine Learning：十大机器学习算法
开源中国
21+阅读 · 2018年3月1日
强化学习 cartpole_a3c
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
Arxiv
0+阅读 · 2021年3月25日
Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
Arxiv
0+阅读 · 2021年3月24日
The Gradient Convergence Bound of Federated Multi-Agent Reinforcement Learning with Efficient Communication
Arxiv
0+阅读 · 2021年3月24日
Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance
Arxiv
0+阅读 · 2021年3月23日
Explicit and recursive estimates of the Lambert W function
Arxiv
0+阅读 · 2021年3月22日
The Causal Learning of Retail Delinquency
Arxiv
14+阅读 · 2020年12月17日
A Tour of Reinforcement Learning: The View from Continuous Control
Arxiv
6+阅读 · 2018年6月25日
Logically-Constrained Reinforcement Learning
Arxiv
5+阅读 · 2018年4月22日
Feature-Based Aggregation and Deep Reinforcement Learning: A Survey and Some New Implementations
Arxiv
9+阅读 · 2018年4月22日
Safety-aware Adaptive Reinforcement Learning with Applications to Brushbot Navigation
Arxiv
4+阅读 · 2018年1月29日
VIP会员
文章信息
前往arXiv
下载PDF
相关主题
线性的
CC
学成
样例
近似
相关VIP内容
哥伦比亚大学最新《机器学习》课程，Fall-B 2020 (Machine Learning)
专知会员服务
39+阅读 · 2020年11月3日
【KDD2020】动态图的拉普拉斯变换点检测，Laplacian Change Point Detection for Dynamic Graphs
【KDD2020】动态图的拉普拉斯变换点检测，Laplacian Change Point Detection for Dynamic Graphs
专知会员服务
38+阅读 · 2020年7月3日
因果图，Causal Graphs，52页ppt
因果图，Causal Graphs，52页ppt
专知会员服务
249+阅读 · 2020年4月19日
【阿里巴巴-CVPR2020】频域学习，Learning in the Frequency Domain
【阿里巴巴-CVPR2020】频域学习，Learning in the Frequency Domain
专知会员服务
29+阅读 · 2020年3月14日
【新书：机器学习简介】《A Concise Introduction to Machine Learning》by A.C. Faul (CRC 2019)
【新书：机器学习简介】《A Concise Introduction to Machine Learning》by A.C. Faul (CRC 2019)
专知会员服务
77+阅读 · 2020年2月8日
TensorFlow深度学习，从线性回归到强化学习的深度学习（TensorFlow for Deep Learning From Linear Regression to Reinforcement Learning），附页256页pdf
TensorFlow深度学习，从线性回归到强化学习的深度学习（TensorFlow for Deep Learning From Linear Regression to Reinforcement Learning），附页256页pdf
专知会员服务
46+阅读 · 2020年1月1日
【电子书】机器学习实战（Machine Learning in Action），附PDF
【电子书】机器学习实战（Machine Learning in Action），附PDF
专知会员服务
128+阅读 · 2019年11月25日
【课程】普林斯顿大学19年春季学期《机器学习优化》课程讲义
【课程】普林斯顿大学19年春季学期《机器学习优化》课程讲义
专知会员服务
85+阅读 · 2019年10月29日
2019年机器学习框架回顾
2019年机器学习框架回顾
专知会员服务
36+阅读 · 2019年10月11日
【新书】Python编程基础，669页pdf
【新书】Python编程基础，669页pdf
专知会员服务
195+阅读 · 2019年10月10日
热门VIP内容
相关资讯
局部学习的特征选择：Local-Learning-Based Feature Selection
局部学习的特征选择：Local-Learning-Based Feature Selection
我爱读PAMI
14+阅读 · 2019年9月20日
Hierarchically Structured Meta-learning
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
Disentangled的假设的探讨
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Imitation - Reinforcement Learning
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
激活函数初学者指南
激活函数初学者指南
论智
6+阅读 · 2018年5月15日
Reinforcement Learning: An Introduction 2018第二版 500页
Reinforcement Learning: An Introduction 2018第二版 500页
CreateAMind
12+阅读 · 2018年4月27日
Machine Learning：十大机器学习算法
Machine Learning：十大机器学习算法
开源中国
21+阅读 · 2018年3月1日
强化学习 cartpole_a3c
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
相关论文
Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning
Arxiv
0+阅读 · 2021年3月25日
Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity
Arxiv
0+阅读 · 2021年3月24日
The Gradient Convergence Bound of Federated Multi-Agent Reinforcement Learning with Efficient Communication
Arxiv
0+阅读 · 2021年3月24日
Nonlinear Two-Time-Scale Stochastic Approximation: Convergence and Finite-Time Performance
Arxiv
0+阅读 · 2021年3月23日
Explicit and recursive estimates of the Lambert W function
Arxiv
0+阅读 · 2021年3月22日
The Causal Learning of Retail Delinquency
Arxiv
14+阅读 · 2020年12月17日
A Tour of Reinforcement Learning: The View from Continuous Control
Arxiv
6+阅读 · 2018年6月25日
Logically-Constrained Reinforcement Learning
Arxiv
5+阅读 · 2018年4月22日
Feature-Based Aggregation and Deep Reinforcement Learning: A Survey and Some New Implementations
Arxiv
9+阅读 · 2018年4月22日
Safety-aware Adaptive Reinforcement Learning with Applications to Brushbot Navigation
Arxiv
4+阅读 · 2018年1月29日
Top
微信扫码咨询专知VIP会员
Top