Infinite probability computation by cyclic explanation graphs
Infinite probability computation by cyclic explanation graphs
复制标题
DOI：
10.1017/s1471068413000562
复制
发表时间：
2013-09
影响因子：
1.4
通讯作者：
Taisuke Sato;Philipp J. Meyer
中科院分区：
文献类型：
--
作者：
Taisuke Sato;Philipp J. Meyer
摘要 逻辑编程中的制表被用来消除冗余计算并阻止无限循环。在本文中，我们研究了制表的另一种可能性，即计算概率逻辑程序的概率的无限和。使用 PRISM（一种具有制表机制的基于逻辑的概率建模语言），我们将概率上下文无关语法（PCFG）的前缀概率计算推广到概率逻辑程序。给定一个最高目标，我们用表格搜索所有证明，并获得一个压缩它们的解释图，并且可能是循环的。然后，我们将解释图转换为一组线性概率方程，并通过矩阵运算求解它们。该解决方案为我们提供了最高目标的概率，其本质上是概率的无限和。我们通过表格进行前缀概率计算的通用方法不仅允许处理非概率上下文无关语法（例如概率左角语法），而且具有诸如计划识别和概率模型检查之类的应用，并且使得计算描述循环关系的概率模型的概率成为可能。
Abstract Tabling in logic programming has been used to eliminate redundant computation and also to stop infinite loop. In this paper we investigate another possibility of tabling, i.e. to compute an infinite sum of probabilities for probabilistic logic programs. Using PRISM, a logic-based probabilistic modeling language with a tabling mechanism, we generalize prefix probability computation for probabilistic context-free grammars (PCFGs) to probabilistic logic programs. Given a top-goal, we search for all proofs with tabling and obtain an explanation graph which compresses them and may be cyclic. We then convert the explanation graph to a set of linear probability equations and solve them by matrix operation. The solution gives us the probability of the top-goal, which, in nature, is an infinite sum of probabilities. Our general approach to prefix probability computation through tabling not only allows to deal with non-probabilistic context-free grammars such as probabilistic left-corner grammars but has applications such as plan recognition and probabilistic model checking and makes it possible to compute probability for probabilistic models describing cyclic relations.