Interpreting Neural Network Judgments via Minimal, Stable, and Symbolic Corrections

Xin Zhang, Armando Solar-Lezama, Rishabh Singh

Abstract

We present a new algorithm to generate minimal, stable, and symbolic corrections to an input that will cause a neural network with ReLU activations to change its output. We argue that such a correction is a useful way to provide feedback to a user when the network's output is different from a desired output. Our algorithm generates such a correction by solving a series of linear constraint satisfaction problems. The technique is evaluated on three neural network models: one predicting whether an applicant will pay a mortgage, one predicting whether a first-order theorem can be proved efficiently by a solver using certain heuristics, and the final one judging whether a drawing is an accurate rendition of a canonical drawing of a cat.

What Problem Does This Paper Address?

Deep learning models are notoriously "black boxes." While researchers have developed methods to explain their decisions—such as saliency maps that highlight important input features—these explanations are rarely actionable.

If a neural network denies a mortgage application, knowing that the "debt-to-income ratio" was a highly weighted feature is only mildly helpful. What a user really needs to know is: "How much do I need to change my debt-to-income ratio to get approved?"

The authors focus on "judgment problems"—asymmetric binary decisions where a user needs a path from a negative judgment to a positive one. The challenge is finding a correction that is:

  1. Minimal: The smallest change possible.
  2. Stable: Not just a single point, but a robust neighborhood where the answer remains positive.
  3. Symbolic: Described by clear rules (e.g., "DTI between 20% and 30%") rather than an opaque vector.

Methods

The authors' tool, POLARIS, exploits the piecewise linear property of ReLU activations. The algorithm works in three main stages:

  • Finding an Initial Seed: It uses a modified gradient method to find the nearest single point that flips the network's output.
  • Expanding the Region: The algorithm identifies the linear region (activation pattern) the seed point belongs to and uses a worklist algorithm to find adjacent linear regions that also result in a positive judgment.
  • Inferring Symbolic Constraints: Finally, it fits a simple geometric shape (like a box or a simplex) inside this collection of successful regions. This shape is translated into a set of linear constraints—the "symbolic correction."
Visualizing symbolic corrections across three domains: (a) Mortgage Underwriting, (b) Theorem Proving, and (c) Drawing Recognition. The red 'x' represents the original rejected input, while the blue polygon defines the stable region of successful correction.

Datasets and Evaluation

The researchers evaluated POLARIS on three distinct models:

  1. Mortgage Underwriting: Trained on 34 million loan applications from Fannie Mae (21 features).
  2. Theorem Proving: Predicts if a first-order theorem can be solved efficiently (51 features).
  3. Drawing Recognition: Trained on the Google "QuickDraw" dataset to judge cat sketches (512 features).

Key Insights

  • Actionability over Attribution: The core shift is moving from "attribution" (what did the model look at?) to "recourse" (what can I change?).
  • Stability is Safety: By requiring the correction to be a region with volume, the system ensures that if a user follows the advice but misses the exact target slightly, they are still likely to get the desired outcome.
  • The ReLU Advantage: The paper uses the piecewise linearity of ReLUs to make the problem mathematically tractable through linear programming (LP) solved via the Gurobi optimizer.

Key Results

POLARIS successfully generated stable symbolic corrections for 85% of mortgage cases, 81% of theorem-proving cases, and 75% of drawing cases. For mortgage applications, the average correction suggested concrete changes like decreasing the debt-to-income ratio by 19.5%.

Distribution of running times for generating corrections in the Drawing Recognition task, with an average of 781 seconds.

The algorithm found corrections in about 12 minutes on average. Interestingly, the bottleneck was not the LP math (which took <2% of the time), but the overhead of creating the LP instances in Python.

Limitations and Future Work

The algorithm is "sound" (guaranteed to work) but not necessarily "optimal" (it might not find the absolute smallest correction). Future work includes scaling to deeper state-of-the-art models and extending the method to non-ReLU activations (like Sigmoid or Tanh) through linear approximations.

Summary updated

Abstract

We present a new algorithm to generate minimal, stable, and symbolic corrections to an input that will cause a neural network with ReLU activations to change its output. We argue that such a correction is a useful way to provide feedback to a user when the network's output is different from a desired output. Our algorithm generates such a correction by solving a series of linear constraint satisfaction problems. The technique is evaluated on three neural network models: one predicting whether an applicant will pay a mortgage, one predicting whether a first-order theorem can be proved efficiently by a solver using certain heuristics, and the final one judging whether a drawing is an accurate rendition of a canonical drawing of a cat.
BibTeX
@inproceedings{zhang2018interpreting,
  author = {Xin Zhang and Armando Solar-Lezama and Rishabh Singh},
  title = {{Interpreting Neural Network Judgments via Minimal, Stable, and Symbolic Corrections}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=SybNnPb_br},
}
Figure