Evaluating the Interpretability of the Knowledge Compilation Map: Communicating Logical Statements Effectively

Serena Booth, Christian Muise, Julie ShahIJCAI 2019 · DOI

Introduction

In the field of Artificial Intelligence, Knowledge Compilation (KC) is a vital process used to translate complex logical theories into specific "target" formats. These formats are optimized to allow computers to process information rapidly for tasks such as diagnosis, state estimation, or planning. While researchers have established a comprehensive "KC Map" to determine which formats are most computationally efficient, a significant gap remains: we lack a corresponding map for human interpretability.

Historically, the AI community has operated under the assumption that Disjunctive Normal Form (DNF)—a series of "OR" statements containing "AND" statements—is the gold standard for human readability. This paper challenges that conventional wisdom through a controlled user study, investigating how structural properties and domain complexity influence human comprehension.

Methods and Experimental Design

The authors conducted a "human-grounded" user study involving 25 participants to evaluate interpretability across several logical languages, including DNF, Conjunctive Normal Form (CNF), and Decomposable Negation Normal Form (d-DNNF).

A comparison of different logical representations used in the study, including DNF, CNF, Inverted Negation, and d-DNNF.

To isolate the effects of logical structure from cognitive load, the study employed three distinct task domains:

  1. Highway Driving: Focused on spatial reasoning (e.g., "a vehicle is to my left").
  2. Emergency Triage: Required evaluating mathematical inequalities based on medical procedures (e.g., respiratory rate and pulse).
  3. Chopsticks Game: Involved arithmetic and tracking game states.

Instead of presenting raw Boolean algebra, the researchers translated the logic into natural language bulleted lists. They utilized Generalized Linear Mixed Models (GLMM) to analyze the results, accounting for individual participant differences while isolating the impact of specific logical properties.

An example of the data presented to participants in the Emergency Triage domain, requiring them to evaluate logical conditions against patient vitals.

Key Insights: The DNF Myth and the Cognitive Cost of Negation

The study's findings suggest that the structural properties typically prioritized for machine tractability do not always align with human cognitive strengths.

The DNF Myth

Contrary to expectations, DNF was not significantly more interpretable than other compiled forms. This indicates that AI researchers may have more flexibility in choosing representation languages for human-AI interaction than previously assumed. The "shape" of the logic was often secondary to the context in which it was presented.

Domain Complexity

The domain context proved to be a stronger predictor of performance than the logical structure itself. Participants struggled significantly more with the arithmetic-heavy Chopsticks domain than the spatial Highway domain, regardless of whether the logic was presented in DNF or CNF. This suggests that the cognitive effort required to process the underlying variables can overwhelm the benefits of an "optimal" logical form.

The Problem with Negation

A critical finding was that humans are particularly poor at processing negated logical connectives, such as "neither of A or B" (the NOR connective). Participants described these as counterintuitive and difficult to track. The study found that pushing negations down to individual variables (e.g., "A is false AND B is false") significantly improved comprehension compared to using inverted connectives.

Results and Conclusion

The quantitative analysis revealed high overall accuracy (92.6%), but a notable drop when inverted connectives were introduced ($p = 0.046$). While larger formulas naturally increased the time spent on tasks ($p < 0.001$), they did not necessarily decrease accuracy, provided the logic remained modular or "decomposable."

In conclusion, this research demonstrates that machine tractability does not equate to human tractability. For AI systems to communicate effectively with humans, designers must prioritize the elimination of negated connectives and account for the inherent complexity of the task domain, rather than simply relying on traditional formats like DNF. Future work may explore visual representations, such as circuit diagrams, and the potential for "lossy" compression to provide shorter, more manageable explanations for complex logic.

Summary updated

BibTeX
@inproceedings{booth2019evaluating,
  author = {Serena Booth and Christian Muise and Julie Shah},
  title = {{Evaluating the Interpretability of the Knowledge Compilation Map: Communicating Logical Statements Effectively}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/804},
}
Figure