SOInter: A Novel Deep Energy Based Interpretation Method for Explaining Structured Output Models

S. Fatemeh Seyyedsalehi, Mahdieh Soleymani, Hamid R. Rabiee

TL;DR

SOInter is a novel interpretation method designed specifically for "structured output" models—where output variables are interconnected, like in image segmentation or multi-label classification. By using a deep energy-based training process, it identifies critical input features more accurately and efficiently than standard tools like LIME or SHAP, which often ignore these complex output dependencies.

What Problem Does This Paper Address?

Most explainable AI (XAI) tools treat model outputs as independent islands. However, in many real-world tasks, outputs are highly correlated. For example, in image segmentation, the classification of one pixel is strongly related to its neighbors. In multi-label text tagging, the tag "Machine Learning" is likely to appear alongside "Artificial Intelligence."

Existing methods like LIME or SHAP can struggle with these structured output models because a feature might influence a target output indirectly through its relationship with other output variables. If an interpreter ignores these structural dependencies, it may fail to identify the true "why" behind a model's decision. Furthermore, many current methods are computationally expensive, requiring hundreds of model passes for a single explanation.

Methods

The authors introduce SOInter (Structured Output Interpreter), which treats the target model as a black box. The core innovation is the use of an Energy Block to capture the internal logic of the structured model.

  1. The Energy Block ($E_{sb}$): This is a deep neural network trained to mimic the black box. It learns an "energy function" where low energy indicates a high compatibility between a specific input and a set of outputs. Crucially, it captures the correlations between output variables.
  2. The Interpreter ($IN_t$): A separate network that takes an input and produces a "k-hot" vector, selecting the $k$ most important features for a specific target output. It uses the Gumbel-Softmax trick to make this selection process differentiable, allowing for end-to-end training.
  3. Energy-Based Training: The interpreter is trained using a loss function that compares energy levels. It asks: "If I only show the model these $k$ features, does the energy stay low for the original predicted output, even when accounting for how other outputs might change?"

This approach allows the interpreter to be trained globally across the entire input space, rather than searching for features sample-by-sample.

Datasets

The authors evaluated SOInter across three distinct types of data:

  • Synthetic Datasets: Custom-built linear and non-linear energy functions where the ground-truth important features were known, allowing for precise accuracy measurements.
  • Multi-label Text Datasets: Bibtex (tagging bookmarks), Enron (email categorization), and IMDB (movie genres).
  • Image Segmentation: The Weizmann-horses dataset, where the task is to explain why specific pixels were classified as part of a horse.

Key Insights and Ideas

  • Structure Matters: Incorporating output correlations significantly improves explanation quality. The authors compared SOInter to a version that ignores structure (SOInter-1), and the full version consistently performed better.
  • Indirect Influence: SOInter can identify features that affect a target output through a "computational path" involving other outputs—something independent interpreters often miss.
  • Global Training, Local Explanation: Unlike LIME or SHAP, which are "local" (they run a new optimization for every single sample), SOInter is trained once globally. This makes it extremely fast at inference time.
  • Scalability: Because it's a trained function, the time it takes to generate an explanation remains constant even as the number of input features grows, whereas LIME and SHAP's costs explode.

Key Results

SOInter demonstrated superior performance across several metrics:

  • Accuracy & Median Rank: On synthetic data, SOInter achieved higher accuracy in matching ground-truth features and a better "median rank" (placing true features at the top of the importance list) compared to LIME, Kernel-SHAP, and L2X.
Accuracy comparisons for different target outputs. SOInter (purple line) consistently maintains higher accuracy as the number of features increases.
Median rank results. SOInter (purple) stays closest to the ideal rank (2.5), showing it is more robust to increasing input dimensions than competitors.
  • Text Classification: On the Bibtex and Enron datasets, SOInter achieved higher "post-hoc F1" scores, meaning the features it selected were more effective at reconstructing the black-box's original predictions.
  • Efficiency: For 10,000 samples, SOInter was orders of magnitude faster than LIME and SHAP, maintaining a constant processing time regardless of input size.

Limitations and Future Work

The authors identify a few areas for improvement:

  • Zero-Masking Artifacts: Like many perturbation-based methods, SOInter "removes" features by setting them to zero. This can sometimes confuse the black-box model if zero has a specific semantic meaning in the data.
  • Feature Granularity: Currently, the model selects individual features (like single pixels). The authors suggest extending it to detect "coarse conceptual elements" (like shapes or textures) for more human-readable explanations.
  • Memory Footprint: Because SOInter requires deploying two neural networks (the interpreter and the energy block), it uses more memory than simpler analytical methods.

Summary updated

Abstract

We propose a novel interpretation technique to explain the behavior of structured output models, which learn mappings between an input vector to a set of output variables simultaneously. Because of the complex relationship between the computational path of output variables in structured models, a feature can affect the value of output through other ones. We focus on one of the outputs as the target and try to find the most important features utilized by the structured model to decide on the target in each locality of the input space. In this paper, we assume an arbitrary structured output model is available as a black box and argue how considering the correlations between output variables can improve the explanation performance. The goal is to train a function as an interpreter for the target output variable over the input space. We introduce an energy-based training process for the interpreter function, which effectively considers the structural information incorporated into the model to be explained. The effectiveness of the proposed method is confirmed using a variety of simulated and real data sets.
BibTeX
@misc{seyyedsalehi2022sointer,
  author = {S. Fatemeh Seyyedsalehi and Mahdieh Soleymani and Hamid R. Rabiee},
  title = {{SOInter: A Novel Deep Energy Based Interpretation Method for Explaining Structured Output Models}},
  year = {2022},
  eprint = {2202.09914},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2202.09914},
}
Figure