Knowledge compilation algorithms transform a probabilistic logic program into a circuit representation that permits efficient proba- bility computation. Knowledge compilation underlies algorithms for ex- act probabilistic inference and parameter learning in several languages, including ProbLog, PRISM, and LPADs. Developing such algorithms involves a choice, of which circuit language to target, and which compi- lation algorithm to use. Historically, Binary Decision Diagrams (BDDs) have been a popular target language, whereas recently, deterministic- Decomposable Negation Normal Form (d-DNNF) circuits were shown to outperform BDDs on these tasks. We investigate the use of a new language, called Sentential Decision Diagrams (SDDs), for inference in probabilistic logic programs. SDDs combine desirable properties of BDDs and d-DNNFs. Like BDDs, they support bottom-up compilation and cir- cuit minimization, yet they are a more general and flexible representa- tion. Our preliminary experiments show that compilation to SDD yields smaller circuits and more scalable inference, outperforming the state of the art in ProbLog inference.

@inproceedings{VlasselaerPLP14,
  author = "Vlasselaer, Jonas and Renkens, Joris and Van den Broeck, Guy and De Raedt, Luc",
  title = "Compiling probabilistic logic programs into sentential decision diagrams",
  booktitle = "Workshop on Probabilistic Logic Programming (PLP)",
  location="Vienna, Austria",
  month = Jul,
  year = "2014",
  url = "http://starai.cs.ucla.edu/papers/VlasselaerPLP14.pdf",
  keywords   = {workshop}
}