Programs as Black-Box Explanations

Sameer Singh, Marco Túlio Ribeiro, Carlos GuestrinarXiv 2016 · arXiv

Introduction

As machine learning models grow in complexity, their internal logic becomes increasingly opaque. While deep neural networks and ensemble methods like Random Forests offer high predictive accuracy, they often function as "black boxes," making it difficult for users to understand the rationale behind specific decisions. This lack of transparency is particularly problematic in high-stakes domains such as finance and healthcare. This paper proposes a novel framework that uses computer programs as a "universal language" for local explanations, effectively "decompiling" complex model behavior into human-readable code.

Methodology: Program Synthesis as Optimization

The authors frame the task of explaining a model's local behavior as a program synthesis problem. The process involves three primary stages:

  1. Local Perturbation: To explain a specific prediction for an input $x$, the system generates a set of random perturbations around that point and records the black-box model’s responses.
  2. Domain-Specific Language (DSL): The explanations are restricted to a simple but expressive DSL. This language includes boolean constants, logical operators (and, or, not), arithmetic (+, -, *), and if-then-else structures.
  3. Optimization via Simulated Annealing: The search for the optimal explanation is treated as an optimization problem. The goal is to find a program $p$ that minimizes a loss function (fidelity to the black box) while maintaining low program complexity (interpretability). The authors use simulated annealing to "mutate" program trees until an optimal balance is reached.
The framework treats programs as a unified representation, capable of expressing logic that ranges from simple decision trees to complex arithmetic.

Programs as a Universal Language

A key insight of this work is that programs are a superset of many existing explanation representations. A decision tree, a set of rules, or a linear model can all be expressed as a program. This flexibility allows the framework to navigate the tradeoff between expressivity and interpretability more effectively than methods restricted to a single representation type. Furthermore, by using code, the method leverages the existing "literacy" of technical users who are already accustomed to reading and writing logic in this format.

Experimental Evaluation

The framework was evaluated using the UCI Adult and Hospital Readmission datasets. The goal was to explain predictions from various black-box models, including Random Forests and Linear Models.

Local explanations for the Adult dataset show how complex ensemble models can be reduced to intuitive "if-then" logic involving key features like marriage status and capital gains.

The results demonstrated that the induced programs could successfully capture the primary drivers of a model's decision. For instance, in the Adult dataset, the generated code highlighted "Capital Gain" and "Marriage status" as critical features, even when the underlying Random Forest utilized hundreds of trees. Moreover, the programs were often more compact than the original model structures, significantly enhancing human readability without sacrificing local fidelity.

Limitations and Future Work

While promising, the current approach has several limitations. The search process using simulated annealing is computationally intensive and may not scale well as the DSL becomes more complex. Future work may explore differentiable program induction to improve search efficiency. Additionally, the current DSL lacks advanced features like loops and variables. Finally, while the programs appear interpretable, formal human-subject studies are needed to quantify the actual impact on user trust and decision-making.

Summary updated

Abstract

Recent work in model-agnostic explanations of black-box machine learning has demonstrated that interpretability of complex models does not have to come at the cost of accuracy or model flexibility. However, it is not clear what kind of explanations, such as linear models, decision trees, and rule lists, are the appropriate family to consider, and different tasks and models may benefit from different kinds of explanations. Instead of picking a single family of representations, in this work we propose to use "programs" as model-agnostic explanations. We show that small programs can be expressive yet intuitive as explanations, and generalize over a number of existing interpretable families. We propose a prototype program induction method based on simulated annealing that approximates the local behavior of black-box classifiers around a specific prediction using random perturbations. Finally, we present preliminary application on small datasets and show that the generated explanations are intuitive and accurate for a number of classifiers.
BibTeX
@misc{singh2016programs,
  author = {Sameer Singh and Marco Túlio Ribeiro and Carlos Guestrin},
  title = {{Programs as Black-Box Explanations}},
  year = {2016},
  eprint = {1611.07579},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1611.07579},
}
Figure