Submodular Pick

The algorithm maximizes a submodular set function that balances coverage (explaining important features across the dataset) with diversity (avoiding redundant explanations). A set function is submodular if adding an element to a smaller set provides more marginal gain than adding it to a larger set—a property that naturally models diminishing returns in explanation value. The objective is formalized as:

codeCopy
max_{|S| ≤ k} Σ_{i∈V} max_{j∈S} w_{ij}

where V is the set of all instances, S is the selected subset of size k, and w_{ij} represents the importance weight of feature i in the explanation of instance j. This formulation ensures each selected explanation contributes unique, non-overlapping information about the model's decision boundaries.

Since exact optimization of submodular functions is NP-hard, Submodular Pick employs a greedy forward selection algorithm with provable approximation guarantees. The algorithm iteratively selects the instance whose explanation maximizes the marginal gain in the objective function:

• Initialization: Start with an empty selected set and compute the importance weight matrix W where each row corresponds to a feature and each column to an instance
• Iterative Selection: At each step, add the instance that covers the most high-importance features not already covered by previously selected explanations
• Termination: Stop when the budget B (desired number of explanations) is reached

This greedy approach achieves a (1 - 1/e) ≈ 63% approximation of the optimal solution, a theoretical guarantee derived from the seminal work of Nemhauser, Wolsey, and Fisher on submodular maximization.

The foundation of Submodular Pick is the importance weight matrix, which encodes the significance of each feature for every instance in the dataset. Construction involves:

• Local Explanation Generation: Run LIME (or any instance-level explainer) on a representative sample of instances to obtain feature importance vectors
• Global Aggregation: For each feature j across all instances i, compute a composite importance score that reflects how critical that feature is to the model's behavior globally
• Weight Normalization: Scale weights to ensure features that are important for many instances receive appropriate emphasis without dominating the selection

The resulting matrix W ∈ R^{d × n} (where d is the number of features and n is the number of instances) serves as the input to the submodular optimization, enabling the algorithm to reason about both local and global feature importance simultaneously.

Submodular Pick explicitly manages the tension between two competing goals:

• Coverage: Ensuring the selected explanations collectively account for all features that the model considers important across the entire dataset. High coverage means no critical feature is left unexplained.
• Diversity: Preventing the selection of explanations that highlight the same features repeatedly. Diverse selections expose different aspects of the model's reasoning.

The submodular objective naturally encodes this trade-off because the marginal gain of selecting an instance decreases as its important features are already covered by previously chosen explanations. This property ensures the algorithm automatically shifts from prioritizing coverage (early selections) to enforcing diversity (later selections) as the budget is filled.

The primary use case for Submodular Pick is enabling efficient human auditing of black-box models under strict time constraints. A compliance officer or ML engineer can only review a limited number of explanations—typically 5 to 20—before cognitive fatigue sets in. Submodular Pick ensures this budget is optimally allocated:

• Non-Redundancy Guarantee: No two selected explanations will be dominated by the same features, maximizing the information gained per review
• Global Representativeness: The selected set provides a faithful summary of model behavior across different regions of the input space, not just a single cluster
• Audit Trail Completeness: For regulatory compliance under frameworks like the EU AI Act, the selected explanations serve as evidence that the model's decision logic has been systematically examined

This transforms local explanation methods from debugging tools for individual predictions into comprehensive model auditing instruments.

Submodular Pick generalizes the concept of prototype selection—choosing representative examples from a dataset—to the domain of model explanations. Unlike traditional prototype methods that select based on data distribution alone, Submodular Pick selects based on explanation content:

• Explanation-Aware Selection: Instances are chosen not because they are typical data points, but because their explanations reveal distinct aspects of the model's decision function
• Facility Location Connection: The objective function is mathematically equivalent to the facility location problem in operations research, where facilities (selected explanations) are placed to maximize coverage of demand points (important features)
• Determinantal Point Processes: An alternative probabilistic approach that also models diversity, but Submodular Pick provides deterministic guarantees and is computationally more efficient for large-scale applications

This connection to established optimization frameworks provides theoretical rigor and enables the use of mature algorithmic tooling.

A mathematical framework for maximizing a set function that exhibits diminishing returns. Adding an element to a smaller set provides more marginal gain than adding it to a larger set. SP leverages this property to greedily select explanations that maximize coverage while minimizing redundancy, achieving a solution within a provable (1 - 1/e) approximation bound of the optimal set.

An interpretable model trained to approximate the predictions of a black-box model over the entire input space, not just locally. SP bridges local and global interpretability by selecting a representative subset of local explanations that collectively serve as a non-redundant global summary, allowing human reviewers to understand overall model behavior without examining every instance.

The objective function SP maximizes to ensure selected explanations cover the most important features across the dataset. It balances two criteria:

• Importance Weight: Aggregate feature importance scores from LIME explanations
• Diversity Penalty: Redundancy reduction via pairwise similarity of selected instances This prevents selecting multiple explanations that highlight the same features repeatedly.

The algorithmic core of SP that iteratively builds a representative set under a user-specified budget B (number of explanations to show). At each step, it selects the instance that maximizes the marginal gain in coverage relative to the already-chosen set. This greedy approach is computationally efficient and theoretically sound due to the submodular, monotone nature of the coverage function.

The primary output of SP: a curated collection of individual LIME explanations that are both representative and diverse. Unlike random sampling, SP ensures each selected explanation illustrates a distinct aspect of model behavior. This prevents 'explanation fatigue' where a reviewer sees many similar justifications and misses critical failure modes or biases present in the model.

SP explicitly balances the aggregate importance of selected features against the diversity of the explanation set. A pure importance-maximizing selection would pick only high-confidence predictions with similar features, while pure diversity might select outliers. SP's submodular objective formalizes this trade-off, ensuring the final set captures both common decision patterns and rare but critical edge cases.