DROPS

Document

DOI: 10.4230/LIPIcs.ICLP.2012.348

Tabling for infinite probability computation

Authors: Taisuke Sato and Philipp Meyer

Published in: LIPIcs, Volume 17, Technical Communications of the 28th International Conference on Logic Programming (ICLP'12) (2012)

Abstract

Tabling in logic programming has been used to eliminate redundant computation and also to stop infinite loop. In this paper we add the third usage of tabling, i.e. to make infinite computation possible for probabilistic logic programs. Using PRISM, a logic-based probabilistic modeling language with a tabling mechanism, we generalize prefix probability computation for PCFGs to probabilistic logic programs. Given a top-goal, we search for all SLD proofs by tabled search regardless of whether they contain loop or not. We then convert them 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 generalized approach to prefix probability computation through tabling opens a way to logic-based probabilistic modeling of cyclic dependencies.

Cite as

Taisuke Sato and Philipp Meyer. Tabling for infinite probability computation. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 17, pp. 348-358, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{sato_et_al:LIPIcs.ICLP.2012.348,
  author =	{Sato, Taisuke and Meyer, Philipp},
  title =	{{Tabling for infinite probability computation}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{348--358},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Dovier, Agostino and Santos Costa, V{\'\i}tor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2012.348},
  URN =		{urn:nbn:de:0030-drops-36355},
  doi =		{10.4230/LIPIcs.ICLP.2012.348},
  annote =	{Keywords: probability, tabling, PRISM}
}

Search Results

Documents authored by Meyer, Philipp

Tabling for infinite probability computation

Abstract

Cite as

Thanks for your feedback!

Could not send message