Efficient Computation of Shap Explanation Scores for Neural Network Classifiers via Knowledge Compilation

SHAP explanations are computationally expensive: The paper confirms that calculating SHAP scores—a popular method for explaining AI decisions—is "in general intractable" when using black-box classifiers like neural networks, meaning current approaches can be prohibitively slow or resource-intensive.

A new technical solution enables faster explanations: By converting binary neural networks into Boolean circuits using knowledge compilation techniques, the researchers demonstrate that SHAP scores can be computed much more efficiently, with experiments showing "huge" performance gains compared to existing methods.

This advance makes explainability more practical: Faster SHAP computation means organizations can more realistically explain their neural network decisions in real-world applications, supporting the goal of making AI systems more transparent and accountable to users and regulators.

The approach works specifically with binary neural networks: The method applies to neural networks with binary inputs/outputs, which limits its immediate applicability but represents an important step toward making explanation techniques feasible for broader classes of neural networks.

Knowledge compilation bridges AI and explainability: The paper demonstrates that logic-based techniques from symbolic AI can be leveraged to solve practical problems in modern deep learning, suggesting that hybrid approaches combining different AI methodologies may be valuable for responsible AI development.