QPM: Discrete Optimization for Globally Interpretable Image Classification

Authors: Thomas Norrenbrock, Timo Kaiser, Sovan Biswas, Ramesh Manuvinakurike, Bodo Rosenhahn
Primary area: interpretability and explainable AI
Keywords: explainable AI, Global Interpretability, Sparse Representations, Compactness, Local Interpretability, Image Classification, Discrete Optimization

Abstract:
Understanding the classifications of deep neural networks, e.g. used in safety-critical situations, is becoming increasingly important. While recent models can locally explain a single decision, to provide a faithful global explanation about an accurate model’s general behavior is a more challenging open task. Towards that goal, we introduce the Quadratic Programming Enhanced Model (QPM), which learns globally interpretable class representations. QPM represents every class with a binary assignment of very few, typically 5, features, that are also assigned to other classes, ensuring easily comparable contrastive class representations. This compact binary assignment is found using discrete optimization based on predefined similarity measures and interpretability constraints. The resulting optimal assignment is used to fine-tune the diverse features, so that each of them becomes the shared general concept between the assigned classes. Extensive evaluations show that QPM delivers unprecedented global interpretability across small and large-scale datasets while setting the state of the art for the accuracy of interpretable models.

Decision: accept (poster)
Reviewer scores: 6, 6, 8

Reviews and discussion:
<thread>
creation date:
1730655962958

thread_type:
official_review

<thread_object>
creator: reviewer_gmvn

<content>
summary:
With the rise of AI in several high-risk areas such as autonomous driving and medical diagnosis, being able to interpret the decisions of deep neural networks is paramount for safety. The authors focus on providing faithful global explanations as opposed to the simpler task of giving local explanations. This is achieved via their Quadratic Programming Enhanced Model (QPM) via learning interpretable class representations using only 5 features and binary assignment. This simple decision logic makes interpreting classifications feasible by humans. The authors optimize for this representation and predictive power using discrete optimization on diverse pretrained features. They evaluate their method on a variety of datasets and achieve competitive accuracy and interpretability compared to popular interpretability methods. The authors show qualitative results of their model’s interpretability and quantitative for metrics on complexity, spatial diversity, class-indepence of features, contrastiveness of features, and their structural grounding to human given concepts.

strengths:
- Global explanations are simple and easy for humans to interpret. Weights from features are binary and only positive. Each class only has 5 features (in most experiments).
- Robustness and generalizability of their method is given based on evaluation on a variety of datasets and models
- Good use of discrete optimization and constraints to select diverse, localized, and predictive features from a pre trained set of features. Clever relaxation of constraints for feasible optimization while maintaining accuracy and interpretability.
- Ability for concepts/features to be used for predicting multiple classes.
- Competitive or SOTA accuracy and interpretability compared to other popular methods. Qualitative results show the ease of interpretability of their method.
- Ablation experiments show effectiveness of $Z_B$ and $Z_R$ objectives.

weaknesses:
Minor:
- Writing can be unclear at times:
  - L282: Are you keeping the entries that are being clipped? Between 0 and epsilon.
  - L127-129: This sentence is unclear. How does the balanced binary assignment cause general binary concepts?
  - L372-273: You say you omit measuring the grounding of features, but provide results…Do you mean that you don’t focus on it since you only do this for CUB & TravelingBird due to lack of part annotations in other datasets?

Worth noting:
- While your method doesn’t use negative reasoning, which makes it more simple, it is a restriction/limitation.
- Your method’s performance isn’t that much above Q-SENN, but you mention the computation limitation on Q-SENN. A comparative analysis, such as a table, that shows the speed of training differences between methods would be desirable.

questions:
- You provide misclassifications of your model in the Appendix in figure 10, but not the explanation for the classification visually. I think being able to understand the misclassification from your method’s explanation is important to your method’s strength. Could you show the explanation visualization for several misclassified samples? I think image (j) would be interesting plus images from other datasets.
- See weaknesses for other questions.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730685663377

thread_type:
official_review

<thread_object>
creator: reviewer_x2rh

<content>
summary:
To develop inherently interpretable image classification, the authors propose to use a set of five diverse features for each class to perform classification. Specifically, the proposed method leverages discrete quadratic programming to extract the features that are distinct, contrastive, and generalizable across similar classes from pretrained vision models, e.g., ResNet-50. The paper provides extensive empirical results on prediction accuracy and interpretability metrics.

strengths:
1. The idea is intuitive and easy to understand.
2. The paper is well-organized and easy to follow.
3. Different from most interpretable models, the proposed method didn’t compromise too much on the prediction accuracy.

weaknesses:
1. Although the proposed method can provide five different heatmaps to explain the prediction of a class, the semantic meanings of these explanations are subjective. This is different from Concept Bottleneck Models (CBMs) and Testing with Concept Activation Vectors (TCAV) that can provide human-understandable concept explanations with semantic meanings. Although the authors propose structural grounding that uses dense annotations of bird parts from the CUB dataset to interpret some of the heatmaps, the concept coverage might be restrictive and cannot reflect what the model has learned.
2. The choice of five features per class might be arbitrary. Some classes might be more complicated than others, while some classes could be very simple. Would it be better to use a different or dynamic number of concepts for each class? This is actually related to the Weakness 1 above. The restricted number of five concepts makes the model learn polysemantic features, which means it might represent different concepts within a single feature. This can make the interpretation of the functionality of the features even harder. For example, as shown in Fig. 12, the green feature can highlight bird beaks on one image and wings on the other image. This might defeat the purpose of making the model more interpretable.
3. The proposed method highly relies on the quality of extracted features from the pretrained models, whereas they are not designed to be explainable. Since the base models are normally trained, they can also extract biased features which would significantly affect the performance of the proposed model.
4. Experiments using standard metrics for explanations are missing, such as the explanation fidelity using the deletion/insertion method [1]. The proposed contrastiveness metric cannot fully reflect the explanation quality in terms of faithfulness. The authors propose Scale-Invariant-Diversity@5 (SID@5), however, the proposed method cannot achieve the best or second-best performance on the three datasets.

[1] Petsiuk, V. "Rise: Randomized Input Sampling for Explanation of black-box models." BMVC 2018.

questions:
See Weakness for details.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730728961690

thread_type:
official_review

<thread_object>
creator: reviewer_vzlv

<content>
summary:
The paper introduces the Quadratic Programming Enhanced Model (QPM), an approach for globally interpretable image classification. Unlike traditional models that primarily focus on local explanations, QPM achieves a compact, interpretable global representation of each class by assigning only a few features, typically five, per class through discrete optimization. This binary feature assignment ensures contrastive and general class representations, which allows for clear, globally understandable explanations. The model sets a new benchmark in both interpretability and accuracy for compact, interpretable models across small and large datasets, including ImageNet-1K. The approach shows robust performance by using optimally selected features that enhance global interpretability and structural grounding while maintaining high classification accuracy.

strengths:
- The paper studies global  an important question in explainable machine learning, providing global interpretation through user defined features.

- The paper motivation is well justified, well-written and easy to understand.

- The results show that QPM achieves superior performance in structure grounding, which signifies that QPM’s learned class representations align with human-understandable features. This is very crucial in explainable machine learning.

weaknesses:
- The paper operates on only a few features, which is fine for natural images. However, I think in more complex domain applications such as medical imaging, more features might be required. How would more features affect the model’s optimization of feature selection in terms of time and accuracy?

- On that note, the paper lacks experiments related to high-stake domain applications such as healthcare, autonomous driving, etc.

- In QPM, Pearson correlation serves as a fundamental similarity measure that aids in identifying which features are most relevant to each class. By focusing on linear relationships, it allows the model to assign interpretable, contrastive, and compact features to classes. However, because it overlooks non-linear relationships, it may not capture all nuances in complex datasets, potentially impacting accuracy in applications where non-linear patterns are significant. Could the author elaborate on this matter?

- QPM demonstrates inferior performance on SID@5, Class-Independence, and Contrastiveness compared to state-of-the-art models, suggesting that its compact binary feature assignment strategy, while beneficial for interpretability, may limit the model's ability to capture diverse, independent, and highly contrastive feature representations across classes. This trade-off reflects QPM's focus on simplicity and interpretability at the expense of some nuanced, dataset-specific feature diversity.

questions:
- Presentation-wise, I think it is better to explicitly show what the features are in human language for the figures, so that it is more friendly to the readers.

- Structure ground is only evaluated on CUB-2011, and the authors also explained why. How much effort would it take to achieve the evaluation metric on a larger dataset, such as ImageNet?

- How long is the optimization of “4 hours for fine-grained datasets, and roughly 11 hours for ImageNet”? Are these times better than previous methods?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731947688866

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Intermediate Revised Manuscript Uploaded

comment:
We thank all reviewers for their valuable and highly constructive feedback. We further appreciate the feedback of a well written manuscript, an intuitive idea, the clever relaxation of constraints, the good accuracy, and following an important goal of global interpretability. \
We respond to all weaknesses / questions separately and want to stress that the proposed additions will improve the overall quality and readability of our manuscript.  \
We uploaded an intermediate version of the paper, as we followed Reviewer GMvn’s suggestion to add more visualizations. Therefore, we also added tables and figures containing results that are referenced in our comments. When referencing parts of the paper, we try to be clear, whether it is in the initial or revised version. References to the revised version will be accompanied by “new”, and else the initial pdf is meant to maintain the references in the comments. \
The changes compared to the initial version are:
* **New Figures 11-14**: Following Reviewer GMvn’s suggestion, we added further example visualizations of our explanations. Fig. 11 contains all the GradCAM visualizations of Fig. 10, showing that QPM consistently localizes on the dog. As QPM enables more in-depth analysis, Fig. 12 and 13 are concerned with Fig.10j, visualizing the features of the predicted Greater Swiss Mountain Dog and the annotated Rottweiler class on class examples and Fig. 10j. Given the class examples and their features, the classification of the presumably falsely labeled image as Greater Swiss Mountain Dog is expected. Fig. 14 then contains exemplary test classifications of the model explained in Fig. 4. As expected by its global explanation, it does not identify a Bronzed Cowbird if the red eye is not visible enough.
* **New Appendix F, Figure 15 and Table 6**: Following questions from Reviewers vzLV and GMvn, we added Results on the runtime of our method with respect to the number of features, as inquired by Reviewer  vzLV and a general comparison and discussion of it. 
* **New Table 7, Figure 16 and Appendix G**: We added an Ablation study on the impact of enforcing exactly $n_{wc}$ features per class as opposed to on average, following remarks from Reviewers x2rh and GMvn. The ablation study shows that while being beneficial for interpretability, a balanced assignment also improves accuracy. We further show that the features do indeed become less general during unbalanced fine-tuning in Figure 16.
* **New Figure 17**: The added figure shows the sparsities of the probed models in the above ablation study. It visualizes that Q-SENN learns very unevenly sparse representations. This might explain why SID@5 can be better for it than for QPM, as the top 5 features explain the entire reasoning of QPM, and typically only part of Q-SENNs.
* **New Figure 18 and Appendix H**: In Response to the question regarding polysemantic features, brought up by Reviewer x2rh and also relevant to questions brought up by the other reviewers, we added a discussion of the topic and Figure 18 as anecdotal evidence for the presence of globally polysemantic, but locally monosemantic features. We want to emphasize that the notion of locality used here, is enabled through QPMs interpretable structure.
* **New Table 8**: We added Results on Diversity@5 to the appendix to demonstrate its insufficiency for PIP-Net. As remarked by  Reviewers  vzLV and x2rh, QPM does not perform best in the preferable metric SID@5, so this table can be further context that the relative diversity is  metric dependent, as QPM learns the most diverse features according to  Diversity@5. However, we want to emphasize that a value of around 90% in either of these metrics indicates very localized features and that higher values can also indicate errors, like the class-detectors of PIP-Net. 
* **New Table 9 and Appendix I**: In response to the question from Reviewer vzLV, we evaluated Structural Grounding using the similarities in a CLIP Language Space.
* **New Table 10 and Appendix J**: In response to the question from Reviewer vzLV, we compared  AUROC, as alternative highly non-linear assignment criterion, with our linear correlation, showing slight but clear improvements when using the proposed correlation.
* **New Appendix K**: We started the Limitations and Future Work section and included a discussion regarding insertion / deletion metrics for evaluating saliency maps , following remarks of Reviewer x2rh. 

Notably, we have not changed the main paper yet. Except for the changes we concretely propose, we will of course refer to all content added to the appendix where suitable in the main paper.  Similarly, the text in the appendix, e.g. in E, is not yet updated with references to the added figures. Finally, the Limitations and Future Work section is not finished yet.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732741565146

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Final Revised Manuscript Uploaded

comment:
We thank all reviewers for their valuable and highly constructive feedback which led to an improved manuscript. We further appreciate the feedback of a well written manuscript, an intuitive idea, the clever relaxation of constraints, the good accuracy, and following an important goal of global interpretability. \
We have now uploaded the revised version, in which we believe we included the results of our discussion. \
The total changes compared to the initial version are:
* All changes described in the comment "Intermediate Revised Manuscript Uploaded"

* **New Appendix K**: We completed the Limitations and Future Work section. It includes:
  * A discussion of high-stakes applications as a valuable avenue for future work, following remarks by Reviewer vzLV.
  * A discussion of negative reasoning as limitation to the QP in its current form, following the comment by Reviewer GMvn.
  * A discussion of polysemantic features and their alignment as current challenge and avenue for future work.
  * A discussion regarding insertion / deletion metrics for evaluating saliency maps, following remarks of Reviewer x2rh.
* **New Lines 153-154**: We added a clarifying sentence to the related work to indicate that our method also profits off of post-hoc alignment methods, following a comment by Reviewer x2rh. This is also discussed in new appendix K.
* **New Lines 125-127**: We clarified the phrasing following the comment from Reviewer GMvn.
* **New Lines 527-529**: We added references to the added ablations
* **New Lines 483-485**: We added references to the added analyses
* **New Line 456**: We added a reference to results on div@5
* **New Line 473**: We reference the runtime analysis in appendix F.
* **Rephrased 4.3, Lines 473-485**: This section is slightly rephrased to put more emphasis on QPM as the only model that excels in all metrics, PIP-Net and glmsaga's weaknesses, and to include references to the appendix where suitable.
* We extended Appendix E to also discuss the new figures 11-14.
* In order to reference the content added to the appendix, we slightly shrank Figure 2 by removing whitespace between the feature images.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes a method to make image classification interpretable by using a binary assignment of a few features for each class. The method starts with pre-trained network and then imposes these constraints through a quadratic programming framework. This results in a globally interpretable model. Reviewers liked the interpretable framework and that the accuracy did not drop much. Most reviewers also said that the paper was well written and read well. Some of the weakness the reviewers pointed were with using a very few set of features across all classes and perhaps the base model being  normally trained might pose restrictions. The rebuttal seem to address these issues. Overall, the ratings are in favor of acceptance to ICLR.