Towards interpretable AI with quantum annealing feature selection

1. Problem Statement

Deep Learning (DL) models, particularly Convolutional Neural Networks (CNNs), are widely used in critical applications but often function as "black boxes." While Explainable AI (XAI) techniques like Grad-CAM and Grad-CAM++ exist to visualize which image regions influence predictions, they suffer from significant limitations:

• Aggregation: They combine contributions from all feature maps (FMs) into a single saliency map, failing to disentangle the specific roles of individual FMs.
• Redundancy: They do not filter out redundant or correlated representations, making it difficult to understand the specific learned patterns driving a decision.
• Combinatorial Complexity: Selecting the optimal subset of FMs to explain a prediction is a combinatorial optimization problem that scales exponentially ($2^N$) with the number of features, making it computationally intractable for classical exhaustive search.

The authors propose that Feature Selection (FS) applied to internal learned representations (rather than raw input pixels) is a powerful but underutilized tool for XAI. However, solving this FS problem efficiently requires a new approach.

2. Methodology

The paper proposes a novel Quantum Annealing (QA) based approach to select the most relevant and non-redundant feature maps for a given image prediction.

A. Feature Map Filtering

1. Gradient Analysis: The authors compute the global average pooling of the gradients with respect to the final convolutional layer's feature maps ($f^{(a)}_{ij}$).
   $$\alpha_a = \frac{1}{H_f W_f} \sum_{i,j} \frac{\partial z}{\partial f^{(a)}_{ij}}$$
   where $\alpha_a$ represents the importance of feature map $a$.
2. Positive Selection: Only feature maps with a positive gradient contribution ($\alpha_a > 0$) are retained, as these confirm the predicted class. This creates a filtered set $\{\tilde{f}\}$.

B. QUBO Formulation

The selection problem is encoded into a Quadratic Unconstrained Binary Optimization (QUBO) problem (or equivalently, an Ising model).

• Variables: Binary variables (qubits) represent the inclusion ($1$) or exclusion ($0$) of each filtered feature map.
• Objective Function (Hamiltonian): The goal is to maximize the importance of selected maps while minimizing redundancy (geometric similarity).
  $$\hat{H}_{QUBO} = (1 - \beta) \frac{1}{2} \sum_{p,q} J_{pq} \hat{n}_p \hat{n}_q + \beta \sum_{p} h_p \hat{n}_p$$
  • Linear Term ($h_p$): Represents the normalized importance of feature map $p$ (derived from $\alpha_p$).
  • Quadratic Term ($J_{pq}$): Represents the absolute cosine similarity between feature maps $p$ and $q$. High similarity implies redundancy; the term penalizes selecting both.
  • Hyperparameter ($\beta$): Controls the trade-off between selecting high-importance features and minimizing redundancy.

C. Quantum Annealing Protocol

• Initialization: The system starts in a superposition of all possible feature subsets (ground state of a driver Hamiltonian $\hat{H}_D = -\sum \hat{\sigma}_x$).
• Evolution: The system evolves via a time-dependent Hamiltonian $\hat{H}(s) = A(s)\hat{H}_D + B(s)\hat{H}_{QUBO}$, where $s$ goes from 0 to 1.
• Sampling: The final state is sampled to obtain a bit-string representing the optimal subset of feature maps. This subset constitutes the "explanation map."

3. Key Contributions

1. Novel XAI Framework: The first application of Quantum Annealing specifically for selecting internal feature maps (latent representations) of CNNs, rather than input pixels.
2. Disentanglement: Unlike Grad-CAM which aggregates all maps, this method isolates a sparse, non-redundant subset of FMs, providing a clearer view of the specific patterns the model uses.
3. Physics-Driven Analysis: The authors analyze the computational behavior of the algorithm using quantum physics metrics, such as the minimum energy gap ($\Delta_{min}$) and fidelity, to explain why the method works and its scalability limits.
4. Hybrid Approach: The work demonstrates how NISQ (Noisy Intermediate-Scale Quantum) concepts can be simulated to solve high-dimensional FS problems that are difficult for classical heuristics.

4. Results

The method was evaluated on the STL-10 dataset using a ResNet-18 architecture.

• Class Disentanglement:
  • The authors generated class-class correlation maps using the Bhattacharyya coefficient.
  • The QA-based method (with $N_f=16$) showed significantly better disentanglement (more diagonal matrix) compared to the full ResNet-18 model, indicating that selected FMs are more specific to individual classes.
• Quantitative Performance (Average Drop %):
  • Metric: The "Average Drop %" measures how much the model's confidence drops when pixels not in the explanation map are masked. A lower drop indicates a better explanation (the map contains the critical information).
  • Findings: The QA-fGradCAM method achieved a lower Average Drop % (better performance) than both Grad-CAM and Grad-CAM++ across most classes when using a reduced feature set ($N_f=16$).
  • Scalability Note: When scaling to the full ResNet-18 ($N_f=512$) using Simulated Annealing (SA), performance degraded. The authors attribute this to the difficulty of finding the global minimum in larger QUBO instances and the aggressive suppression of features by the redundancy term without careful tuning of $\beta$.
• Physical Analysis:
  • Energy Gap: The minimum energy gap ($\Delta_{min}$) was found to be relatively large (around $10^{-1}$), suggesting the problem landscape is not the "hardest" instance of the Sherrington-Kirkpatrick model and is tractable.
  • Fidelity: For annealing times $\tau > 50$, the algorithm achieved high fidelity (convergence to the ground state), confirming the robustness of the protocol.

5. Significance and Conclusion

• Interpretability: The method enhances the transparency of DL models by identifying the specific, non-redundant filters responsible for a decision, moving beyond coarse heatmaps.
• Quantum Advantage Potential: While current hardware is limited, the study proves that formulating XAI as a QUBO problem allows for the exploration of exponentially large solution spaces efficiently. It suggests that future quantum hardware could solve these interpretability problems faster and more accurately than classical heuristics.
• Future Directions: The authors suggest that tuning the hyperparameter $\beta$ and potentially adding cardinality constraints could further improve results. The framework is agnostic and could be applied to other architectures (e.g., Vision Transformers) or generative models.

In summary, this paper bridges the gap between Quantum Computing and Explainable AI, demonstrating that quantum annealing can effectively solve the combinatorial problem of feature selection in deep networks, leading to more distinct, reliable, and interpretable model explanations.