Incremental Algorithms for Approximate Compilation

Abstract

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 draw-back is that S can be exponentially larger than the size of the original function. To address this issue, we propose an incre-mental, approximate compilation technique that guarantees a sound and space-bounded compilation for weighted boolean functions, at the expense of query completeness. In particu-lar, our approach selectively compiles all solutions exceeding a particular threshold, given a range of weighting functions, without having to perform inference over the full solution-space. 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 com-pilation, while losing relatively little query completeness.