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

Xin Zhang, Armando Solar-Lezama, Rishabh Singh

Deep learning models are notoriously opaque, often acting as "black boxes" that provide decisions without actionable explanations. While researchers have developed techniques like saliency maps to highlight important input features, these methods rarely tell a user how to change an unfavorable outcome.

This paper introduces POLARIS, an algorithm designed to make neural network decisions actionable. By calculating the smallest, most robust changes needed to flip a "negative" outcome to a "positive" one, POLARIS provides users with specific guidance on how to achieve their desired result.

The Need for Actionable Recourse

The authors focus on judgment problems—binary decisions such as loan approvals, college admissions, or parole hearings. In these scenarios, users typically only seek explanations when they receive a negative outcome (e.g., a rejection). A useful explanation in these cases must be actionable. Instead of simply stating, "Your debt was the reason for rejection," a better system would advise, "If your debt-to-income ratio were 10% lower, you would have been approved."

To be practically useful, these suggested corrections must meet three criteria:

  1. Minimal: The required change should be as small as possible to minimize the burden on the user.
  2. Stable: The correction shouldn't point to a "knife-edge" boundary. It must be surrounded by a neighborhood of other positive outcomes so that tiny, realistic variations don't accidentally flip the result back to a rejection.
  3. Symbolic: Instead of providing a single, rigid data point, the explanation should offer a range or relationship (e.g., "Maintain a Debt-to-Income ratio between 20% and 25%").

The POLARIS Algorithm

The core contribution of the paper is the POLARIS algorithm, which exploits the mathematical properties of networks using ReLU (Rectified Linear Unit) activations. Because ReLU networks are piecewise linear functions, their entire input space is partitioned into distinct regions where the network behaves like a simple linear equation.

POLARIS navigates this geometry through four main steps:

  1. Initial Correction: It uses a modified gradient-based method (akin to generating adversarial examples) to find a single point that successfully flips the network's output.
  2. Region Identification: It determines the specific "linear region" this point occupies by analyzing which neurons are activated.
  3. Region Growing: Using a worklist algorithm and Linear Programming (LP) solvers (like Gurobi), it explores adjacent linear regions that also yield a positive judgment.
  4. Symbolic Inference: Finally, it fits a simple geometric shape—such as a box or a simplex (triangle)—inside these verified positive regions. This shape represents the "symbolic correction," providing a set of linear constraints guaranteed to produce the desired output.

Applications and Visualizing Corrections

The authors evaluated POLARIS across three distinct domains, demonstrating its versatility:

  1. Mortgage Underwriting: Predicting loan defaults based on a Fannie Mae dataset (21 features).
  2. Solver Performance Prediction: Predicting if a first-order theorem prover will succeed based on theorem characteristics (51 features).
  3. Drawing Tutoring: Judging whether a user's sketch accurately depicts a canonical cat drawing (512 coordinate features).
Symbolic corrections generated by POLARIS across three domains: Mortgage Underwriting, Solver Performance, and Drawing Tutoring. The red 'x' marks the original rejected input, and the blue shapes represent the stable, symbolic regions of positive outcomes.

As seen in the figure above, POLARIS identifies a stable geometric region (like the blue triangles for the mortgage and solver datasets, or the blue bounding boxes for the drawing coordinates) rather than just a single point. This ensures the user has a robust target to aim for.

Key Insights and Results

By treating the neural network as a collection of linear constraints, the authors successfully turn an interpretability problem into a formal verification and optimization problem. This shifts the focus of AI explainability from attribution (who is to blame?) to recourse (what can I do about it?).

  • Effectiveness: POLARIS successfully found stable symbolic corrections for 85% of the mortgage cases, 81% of the solver cases, and 75% of the drawing cases.
  • Actionability: The corrections were practically meaningful. In the mortgage domain, an average correction suggested decreasing the Debt-to-Income (DTI) ratio by 19.5% or increasing the interest rate by 3%.
  • Efficiency: The algorithm took an average of 12 minutes to find a correction. While slower than a standard forward pass, the actual LP solving time was less than 2% of the total time, with the rest attributed to Python overhead.
  • Complexity: In the drawing task, POLARIS handled corrections involving up to 20 features simultaneously, proving it can scale beyond simple 2D problems.

Limitations and Future Directions

While POLARIS offers a robust framework for recourse, it has limitations. The evaluation was conducted on relatively small networks (e.g., 5 layers, 1000 ReLUs). Scaling the LP-based region growing to massive, ImageNet-scale models would be computationally prohibitive due to the sheer number of linear regions. Additionally, the method currently relies strictly on the piecewise linearity of ReLUs, meaning networks with Sigmoid or Tanh activations would require linear approximations. Finally, for extremely high-dimensional inputs like full-resolution images, "symbolic" corrections (like boxes in pixel space) may become less intuitively understandable for human users.

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