Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Lifted message passing for satisfiability

: Hadiji, F.; Kersting, K.; Ahmadi, B.

Kersting, K. ; American Association for Artificial Intelligence -AAAI-:
Statistical relational artificial intelligence : Papers from the 2010 AAAI Workshop; Collocated with AAAI-10; July 12, 2010, Atlanta, Georgia, USA
Menlo Park: AAAI Press, 2010 (Technical report - American Association for Artificial Intelligence WS-10-06)
ISBN: 978-1-577-35472-7
AAAI Conference on Artificial Intelligence <24, 2010, Atlanta>
Fraunhofer IAIS ()

Unifying logical and probabilistic reasoning is a longstanding goal of AI. While recent work in lifted belief propagation, handling whole sets of indistinguishable objects together, are promising steps towards achieving this goal that even scale to realistic domains, they are not tailored towards solving combinatorial problems such as determining the satisfiability of Boolean formulas. Recent results, however, show that certain other message passing algorithms, namely, survey propagation, are remarkably successful at solving such problems. In this paper, we propose the first lifted variants of survey propagation and its simpler version warning propagation. Our initial experimental results indicate that they are faster than using lifted belief propagation to determine the satisfiability of Boolean formulas.