发帖
雷达卡
摘要翻译：
在n节点上的贝叶斯网络中，基于记分的结构发现的最快精确算法运行在2nno(1)的时间和空间上。这些算法的使用范围最多仅限于25个节点左右的网络，主要是由于空间的要求。在这里，我们研究了寻找最优网络结构的时空权衡。在空间很小的情况下，我们应用Gurevich-Shelah递推--最初针对哈密顿路径问题提出的--在空间2SNO(1)中，对于任意s=n/2,n/4,n/8,得到时间22n-SNO(1)。...；我们假定每个结点的结点由一个常数限定。对于更实际的设置与适度的空间，我们提出了一个新的方案。在空间2n(3/4)pnO(1)中，对于任意p=0,1,，得到运行时间2n(3/2)pnO(1)。..,N/2；只要indegrees最多为0.238N，这些界限就会存在。此外，后一种方案允许比以前的算法更容易和有效的并行化。我们还从经验上探讨了所提出的技术的潜力。
---
英文标题：
《Exact Structure Discovery in Bayesian Networks with Less Space》
---
作者：
Pekka Parviainen, Mikko Koivisto
---
最新提交年份：
2012
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science 计算机科学
二级分类：Data Structures and Algorithms 数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
---
英文摘要：
The fastest known exact algorithms for scorebased structure discovery in Bayesian networks on n nodes run in time and space 2nnO(1). The usage of these algorithms is limited to networks on at most around 25 nodes mainly due to the space requirement. Here, we study space-time tradeoffs for finding an optimal network structure. When little space is available, we apply the Gurevich-Shelah recurrence-originally proposed for the Hamiltonian path problem-and obtain time 22n-snO(1) in space 2snO(1) for any s = n/2, n/4, n/8, . . .; we assume the indegree of each node is bounded by a constant. For the more practical setting with moderate amounts of space, we present a novel scheme. It yields running time 2n(3/2)pnO(1) in space 2n(3/4)pnO(1) for any p = 0, 1, . . ., n/2; these bounds hold as long as the indegrees are at most 0.238n. Furthermore, the latter scheme allows easy and efficient parallelization beyond previous algorithms. We also explore empirically the potential of the presented techniques.
---
PDF链接：
https://arxiv.org/pdf/1205.2620
京公网安备 11010802022788号
