论文标题
近似知识汇编的下限
Lower Bounds for Approximate Knowledge Compilation
论文作者
论文摘要
知识汇编研究不同表示语言的简洁性与效率之间的权衡。对于许多语言，在表示规模上有很强的下限，但是最近的工作表明，对于某些语言，可以使用近似汇编绕过这些界限。这个想法是编译可以控制错误数量的知识的近似。我们专注于确定性分解的否定形式（D-DNNF）中的电路，这是一种适用于概率推理等上下文中的汇编语言，因为它支持有效的模型计数和概率推断。此外，有一些已知的D-DNNF尺寸下限，通过放松到近似值，可以避免。在本文中，我们正式化了两个近似概念：弱近似值，这些近似是在决策图文献和强近似中进行了研究的，这已在最近的算法结果中使用。然后，我们显示了通过D-DNNF近似的下限，并补充了文献的积极结果。
Knowledge compilation studies the trade-off between succinctness and efficiency of different representation languages. For many languages, there are known strong lower bounds on the representation size, but recent work shows that, for some languages, one can bypass these bounds using approximate compilation. The idea is to compile an approximation of the knowledge for which the number of errors can be controlled. We focus on circuits in deterministic decomposable negation normal form (d-DNNF), a compilation language suitable in contexts such as probabilistic reasoning, as it supports efficient model counting and probabilistic inference. Moreover, there are known size lower bounds for d-DNNF which by relaxing to approximation one might be able to avoid. In this paper we formalize two notions of approximation: weak approximation which has been studied before in the decision diagram literature and strong approximation which has been used in recent algorithmic results. We then show lower bounds for approximation by d-DNNF, complementing the positive results from the literature.
