Sparse and Faithful Explanations Without Sparse Models

Abstract

Even if a model is not globally sparse, it is possible for decisions made by that model to be accurately and faithfully described by a small number of features. For example, an application for a large loan might be denied to someone because they have no credit history, which overwhelms any evidence of their creditworthiness. In this paper, we introduce the Sparse Explanation Value (SEV), a new way to measure sparsity in machine learning models. In the loan denial example above, the SEV is 1 because only one factor is needed to explain why the loan was denied. SEV is a measure of \textit{decision sparsity} rather than overall model sparsity, and we can show that many machine learning models -- even if they are not sparse -- actually have low decision sparsity as measured by SEV. SEV is defined using moves over a hypercube with a predefined population commons (reference), allowing SEV to be defined consistently across model classes, with movement restrictions that reflect real-world constraints. Moreover, by allowing flexibility in this reference, and by considering how distances along the hypercube translate into distances in feature space, we can derive sparse and meaningful explanations for different types of function classes and propose three possible approaches: cluster-based SEV, SEV with flexible references and tree-based SEV. Ultimately, we propose algorithms aimed at reducing SEV without compromising model accuracy, thereby offering sparse yet fully faithful explanations, even in the absence of globally sparse models.