Real-world decision-making systems are often subject to uncertainties that have to be resolved through observational data. Therefore, we are frequently confronted with combinatorial optimization problems of which the objective function is unknown and thus has to be debunked using empirical evidence. In contrast to the common practice that relies on a learning-and-optimization strategy, we consider the regression between combinatorial spaces, aiming to infer high-quality optimization solutions from samples of input-solution pairs -- without the need to learn the objective function. Our main deliverable is a universal solver that is able to handle abstract undetermined stochastic combinatorial optimization problems. For learning foundations, we present learning-error analysis under the PAC-Bayesian framework using a new margin-based analysis. In empirical studies, we demonstrate our design using proof-of-concept experiments, and compare it with other methods that are potentially applicable. Overall, we obtain highly encouraging experimental results for several classic combinatorial problems on both synthetic and real-world datasets.


翻译:现实决策系统往往受到不确定性的影响,这些不确定性必须通过观测数据加以解决。因此,我们经常面临组合优化问题,其目标功能未知,因此必须利用经验证据予以解析。与依赖学习和优化战略的常见做法不同,我们考虑组合空间之间的回归,目的是从投入-溶液组合样本中推断出高质量的优化解决方案 -- -- 无需学习客观功能。我们的主要交付品是一个能够处理抽象的未确定的随机组合优化问题的通用求解器。对于学习基础,我们在PAC-Bayesian框架下采用新的边际分析,在PAC-Bayesian框架下提出学习-传感器分析。在经验研究中,我们展示了我们使用验证概念实验的设计,并将它与其他可能适用的方法进行比较。总体而言,我们对合成和真实世界数据集的若干经典组合问题取得了非常令人鼓舞的实验结果。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【2020新书】概率机器学习,附212页pdf与slides
专知会员服务
108+阅读 · 2020年11月12日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年9月17日
Arxiv
0+阅读 · 2021年9月15日
Imitation by Predicting Observations
Arxiv
4+阅读 · 2021年7月8日
VIP会员
相关资讯
强化学习三篇论文 避免遗忘等
CreateAMind
19+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
19篇ICML2019论文摘录选读!
专知
28+阅读 · 2019年4月28日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
spinningup.openai 强化学习资源完整
CreateAMind
6+阅读 · 2018年12月17日
【SIGIR2018】五篇对抗训练文章
专知
12+阅读 · 2018年7月9日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习族谱
CreateAMind
26+阅读 · 2017年8月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员