Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay Joao Marques-Silva

In contrast, we show that the computation of one PI-explanation for an NBC can be achieved in log-linear time, and that the same result also applies to the more general class of linear classifiers. Furthermore, we show that the enumeration of PI-explanations can be obtained with polynomial delay.