Short Boolean Formulas as Explanations in Practice
This work addresses the need for human-interpretable explanations in data analysis, though it is incremental as it builds on existing methods with a focus on practical application.
The paper tackles the problem of generating interpretable explanations for data using short Boolean formulas, providing quantitative bounds for expected error and demonstrating on three datasets that limiting formula length reduces overfitting while maintaining reasonable accuracy.
We investigate explainability via short Boolean formulas in the data model based on unary relations. As an explanation of length k, we take a Boolean formula of length k that minimizes the error with respect to the target attribute to be explained. We first provide novel quantitative bounds for the expected error in this scenario. We then also demonstrate how the setting works in practice by studying three concrete data sets. In each case, we calculate explanation formulas of different lengths using an encoding in Answer Set Programming. The most accurate formulas we obtain achieve errors similar to other methods on the same data sets. However, due to overfitting, these formulas are not necessarily ideal explanations, so we use cross validation to identify a suitable length for explanations. By limiting to shorter formulas, we obtain explanations that avoid overfitting but are still reasonably accurate and also, importantly, human interpretable.