REVIEW 2 cited by
Efficient Explanations for Knowledge Compilation Languages
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
read the original abstract
Knowledge compilation (KC) languages find a growing number of practical uses, including in Constraint Programming (CP) and in Machine Learning (ML). In most applications, one natural question is how to explain the decisions made by models represented by a KC language. This paper shows that for many of the best known KC languages, well-known classes of explanations can be computed in polynomial time. These classes include deterministic decomposable negation normal form (d-DNNF), and so any KC language that is strictly less succinct than d-DNNF. Furthermore, the paper also investigates the conditions under which polynomial time computation of explanations can be extended to KC languages more succinct than d-DNNF.
Forward citations
Cited by 2 Pith papers
-
A Distributed Framework for Compiling and Reasoning with d-DNNF
A Cube-and-Conquer framework compiles CNF formulas into a virtual d-DNNF distributed across workers, enabling counting, direct access, and uniform sampling under conditioning.
-
Feature Relevancy, Necessity and Usefulness: Complexity and Algorithms
A feature is 'useful' if flipping its value can change a model's output; the paper proves this matches the logical notions of relevant and necessary features and analyzes the cost of computing them.
Discussion (0). Continue with ORCID to comment.