Encoding CNFs to Empower Component Analysis

摘要

Recent algorithms for model counting and compilation work by decomposing a CNF into syntactically independent components through variable splitting, and then solving the components recursively and independently. In this paper, we observe that syntactic component analysis can miss decomposition opportunities because the syntax may hide existing semantic independence, leading to unnecessary variable splitting. Moreover, we show that by applying a limited resolution strategy to the CNF prior to inference, one can transform the CNF to syntactically reveal such semantic independence. We describe a general resolution strategy for this purpose, and a more specific one that utilizes problem-specific structure. We apply our proposed techniques to CNF encodings of Bayesian networks, which can be used to answer probabilistic queries through weighted model counting and/or knowledge compilation. Experimental results demonstrate that our proposed techniques can have a large effect on the efficiency of inference, reducing time and space requirements significantly, and allowing inference to be performed on many CNFs that exhausted resources previously.