Incremental Algorithms for Approximate Compilation

Compilation is an important approach to a range of inference problems, since it enables linear-time inference in the size S of the compiled representation. However, the main drawback is that S can be exponentially larger than the size of the original function. To address this issue, we propose an incremental, approximate compilation technique that guarantees a sound and space-bounded compilation for weighted boolean functions, at the expense of query completeness. In particular, our approach selectively compiles all solutions exceeding a particular threshold, given a range of weighting functions, without having to perform inference over the full solutionspace. We describe incremental, approximate algorithms for the prime implicant and DNNF compilation languages, and provide empirical evidence that these algorithms enable space reductions of several orders-of-magnitude over the full compilation, while losing relatively little query completeness.

Authors

• Alberto Venturini Gregory Provan

Keywords

No keywords are indexed for this paper.