Skip to Main content Skip to Navigation
Conference papers

Lower Bounds for Approximate Knowledge Compilation

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-02976041
Contributor : Stefan Mengel Connect in order to contact the contributor
Submitted on : Friday, October 23, 2020 - 11:09:12 AM
Last modification on : Wednesday, October 20, 2021 - 9:58:20 AM

Links full text

Identifiers

Collections

Citation

Alexis de Colnet, Stefan Mengel. Lower Bounds for Approximate Knowledge Compilation. Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence , Jul 2020, Yokohama, Japan. pp.1834-1840, ⟨10.24963/ijcai.2020/254⟩. ⟨hal-02976041⟩

Share

Metrics

Record views

105