On the Computational Intelligibility of Boolean Classifiers
This work addresses the problem of making AI models more interpretable for researchers and practitioners, though it is incremental as it builds on existing XAI query frameworks.
The paper investigates the computational intelligibility of Boolean classifiers, such as decision trees and DNF formulae, by analyzing their ability to answer XAI queries in polynomial time, revealing that all 9 queries are tractable for decision trees but none are for other families like DNF formulae and neural networks.
In this paper, we investigate the computational intelligibility of Boolean classifiers, characterized by their ability to answer XAI queries in polynomial time. The classifiers under consideration are decision trees, DNF formulae, decision lists, decision rules, tree ensembles, and Boolean neural nets. Using 9 XAI queries, including both explanation queries and verification queries, we show the existence of large intelligibility gap between the families of classifiers. On the one hand, all the 9 XAI queries are tractable for decision trees. On the other hand, none of them is tractable for DNF formulae, decision lists, random forests, boosted decision trees, Boolean multilayer perceptrons, and binarized neural networks.