×

Infinite probability computation by cyclic explanation graphs. (English) Zbl 1302.68054

Summary: 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.

MSC:

68N17 Logic programming
68Q42 Grammars and rewriting systems
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)

Software:

PRISM; XSB; OPTYap
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] DOI: 10.1145/356827.356829 · doi:10.1145/356827.356829
[2] Theory and Practice of Logic Programming (TPLP) 8 pp 81– (2008) · Zbl 1128.68018 · doi:10.1017/S147106840700316X
[3] Proceedings of the 3rd International Conference on Logic Programming (ICLP’86) pp 84– (1986)
[4] DOI: 10.1017/S1471068411000524 · Zbl 06049750 · doi:10.1017/S1471068411000524
[5] Matrix Analysis and Applied Linear Algebra (2000)
[6] Computational Linguistics 17 pp 315– (1991)
[7] Foundations of Statistical Natural Language Processing (1999) · Zbl 0951.68158
[8] Proceedings of the 12th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’06) pp 441– (2006)
[9] Proceedings of the 5th International Conference on Parsing Technologies (IWPT-97) pp 147– (1997)
[10] DOI: 10.1017/S1471068412000245 · Zbl 1260.68062 · doi:10.1017/S1471068412000245
[11] DOI: 10.1007/978-3-642-22110-1 · Zbl 1220.68006 · doi:10.1007/978-3-642-22110-1
[12] Journal of ACM 56 pp 1– (2009)
[13] Proceedings of the 1st Conference on Computational Logic (CL’00) pp 269– (2000)
[14] Proceedings of the International Workshop on Wearable and Implantable Body Sensor Networks pp 242– (2007)
[15] Computational Linguistics 21 pp 165– (1995)
[16] Technical Communications of the 28th International Conference on Logic Programming (ICLP’12) pp 348– (2012)
[17] DOI: 10.1007/978-3-540-78652-8 · Zbl 1132.68007 · doi:10.1007/978-3-540-78652-8
[18] Journal of Artificial Intelligence Research 15 pp 391– (2001)
[19] DOI: 10.1007/s10844-008-0062-7 · Zbl 05348896 · doi:10.1007/s10844-008-0062-7
[20] DOI: 10.1017/S1471068404002030 · Zbl 1093.68021 · doi:10.1017/S1471068404002030
[21] DOI: 10.1017/S147106841100010X · Zbl 1218.68169 · doi:10.1017/S147106841100010X
[22] DOI: 10.1145/131295.131299 · doi:10.1145/131295.131299
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.