Bayesian networks are probabilistic graphical models with a wide range of application areas including gene regulatory networks inference, risk analysis and image processing. Learning the structure of a Bayesian network (BNSL) from discrete data is known to be an NP-hard task with a superexponential search space of directed acyclic graphs. In this work, we propose a new polynomial time algorithm for discovering a subset of all possible cluster cuts, a greedy algorithm for approximately solving the resulting linear program, and a generalised arc consistency algorithm for the acyclicity constraint. We embed these in the constraint programmingbased branch-and-bound solver CPBayes and show that, despite being suboptimal, they improve performance by orders of magnitude. The resulting solver also compares favourably with GOBNILP, a state-of-the-art solver for the BNSL problem which solves an NP-hard problem to discover each cut and solves the linear program exactly.


翻译:Bayesian 网络是概率化的图形模型,应用领域广泛,包括基因监管网络的推断、风险分析和图像处理。从离散数据中学习Bayesian 网络(BNSL)的结构,已知是一项难以完成的任务,其搜索空间超能,有定向环形图。在这项工作中,我们提出一种新的多米时间算法,以发现所有可能的集束切除子集,一种贪婪算法,以大致解决由此产生的线性程序,以及一种通用的周期性制约弧一致性算法。我们将这些算法嵌入基于约束性编程的分支和约束求解器 CPBayes 中,并表明尽管它们不是最理想的,但它们的性能按数量级提高。由此产生的求解器也优于GOBNILP, GONILP是解决BNSL问题的最先进的解算器,它解决了NP-硬的问题,以便发现每一个切断并精确解决线性程序。

0
下载
关闭预览

相关内容

因果图,Causal Graphs,52页ppt
专知会员服务
238+阅读 · 2020年4月19日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
54+阅读 · 2019年10月17日
【新书】Python编程基础,669页pdf
专知会员服务
186+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年8月25日
Arxiv
10+阅读 · 2021年2月18日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Arxiv
7+阅读 · 2019年6月20日
Arxiv
17+阅读 · 2019年3月28日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
24+阅读 · 2019年5月18日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
carla 学习笔记
CreateAMind
9+阅读 · 2018年2月7日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员