发帖
雷达卡
摘要翻译：
概率数据库在不确定数据的管理和理解中起着至关重要的作用。然而，将概率纳入不完备数据库的语义提出了许多挑战，迫使系统牺牲建模能力、可伸缩性或限制它们关闭的关系代数公式类。我们提出了一种替代方法，其中底层关系数据库总是表示单个世界，外部因素图编码可能世界的分布；然后利用马尔可夫链蒙特卡罗(MCMC)推理将这种不确定性恢复到所需的保真度水平。我们的方法允许对概率数据库上的任意查询进行有效的评估，这些数据库具有任意依赖关系，这些依赖关系由结构在推理过程中发生变化的图形模型表示。MCMC采样通过假设对可能的世界进行{\em修改}而不是从头开始生成整个世界来提高效率。然后，查询将在变化的世界的部分上运行，避免了在每个采样的世界上运行完整查询的繁重成本。这项工作的一个重要创新是将MCMC采样和物化视图维护技术联系起来：我们发现，使用视图维护技术比单纯地查询每个采样世界要快几个数量级。我们还演示了我们的系统通过聚合回答关系查询的能力，并通过使用并行化演示了额外的可伸缩性。
---
英文标题：
《Scalable Probabilistic Databases with Factor Graphs and MCMC》
---
作者：
Michael Wick, Andrew McCallum, Gerome Miklau
---
最新提交年份：
2010
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Databases 数据库
分类描述：Covers database management, datamining, and data processing. Roughly includes material in ACM Subject Classes E.2, E.5, H.0, H.2, and J.1.
涵盖数据库管理、数据挖掘和数据处理。大致包括ACM学科类E.2、E.5、H.0、H.2和J.1中的材料。
--
一级分类：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中的材料。
--
---
英文摘要：
Probabilistic databases play a crucial role in the management and understanding of uncertain data. However, incorporating probabilities into the semantics of incomplete databases has posed many challenges, forcing systems to sacrifice modeling power, scalability, or restrict the class of relational algebra formula under which they are closed. We propose an alternative approach where the underlying relational database always represents a single world, and an external factor graph encodes a distribution over possible worlds; Markov chain Monte Carlo (MCMC) inference is then used to recover this uncertainty to a desired level of fidelity. Our approach allows the efficient evaluation of arbitrary queries over probabilistic databases with arbitrary dependencies expressed by graphical models with structure that changes during inference. MCMC sampling provides efficiency by hypothesizing {\em modifications} to possible worlds rather than generating entire worlds from scratch. Queries are then run over the portions of the world that change, avoiding the onerous cost of running full queries over each sampled world. A significant innovation of this work is the connection between MCMC sampling and materialized view maintenance techniques: we find empirically that using view maintenance techniques is several orders of magnitude faster than naively querying each sampled world. We also demonstrate our system's ability to answer relational queries with aggregation, and demonstrate additional scalability through the use of parallelization.
---
PDF链接：
https://arxiv.org/pdf/1005.1934
京公网安备 11010802022788号
