Source-linked AI summary
Interpreting Blackbox Models via Model Extraction
Osbert Bastani, Carolyn Kim, Hamsa Bastani
TL;DR
Machine-learning models used in consequential decisions can contain defects that are difficult to diagnose without interpretable views. This paper extracts global decision-tree explanations from blackbox models using active sampling, finding substantially higher fidelity than baselines and equal-or-greater interpretability in a user study. The resulting interpretations expose issues such as non-causal diabetes-risk patterns and symmetry violations in cart-pole control.
Problem
Consequential machine-learning applications need interpretable views because deployed models can exhibit causal, fairness, and distribution-shift defects.
Method
The paper extracts global decision-tree explanations from blackbox models by actively sampling inputs, labeling them with the model, and fitting an approximating tree.
Results
The extracted trees are substantially more accurate relative to the complex model than several baselines and equally or more interpretable in a user study.
Takeaways & Limitations
The interpretations reveal actionable model issues, including a physician-validated non-causal diabetes-risk pattern and cart-pole policy symmetry violations.
Takeaways & Limitations
Cart-pole policies may not generalize well when the initial cart position or pole-falling direction changes substantially.
Abstract
from arXiv · showhide
Interpretability has become incredibly important as machine learning is increasingly used to inform consequential decisions. We propose to construct global explanations of complex, blackbox models in the form of a decision tree approximating the original model---as long as the decision tree is a good approximation, then it mirrors the computation performed by the blackbox model. We devise a novel algorithm for extracting decision tree explanations that actively samples new training points to avoid overfitting. We evaluate our algorithm on a random forest to predict diabetes risk and a learned controller for cart-pole. Compared to several baselines, our decision trees are both substantially more accurate and equally or more interpretable based on a user study. Finally, we describe several insights provided by our interpretations, including a causal issue validated by a physician.
1. Introduction
The paper targets defects in consequential machine-learning applications by extracting interpretable global explanations of blackbox models. Its active-sampling decision trees aim to preserve model fidelity while supporting diagnosis and user understanding.
- Motivation: Interpretability can help data scientists diagnose defects in deployed machine-learning models.The motivating defects include causal confusion, unfairness, and covariate shift.
- Approach: Global explanations approximate a complex model with an interpretable model that can mirror its computation when approximation quality is good.Unlike local explanations, this approach provides a single model-level view for inspecting the complex model.
- Approach: The extraction method actively samples new inputs and labels them with the blackbox model to reduce overfitting when learning decision trees.The paper uses decision trees because they are both nonparametric and highly structured.
- Evaluation: The evaluation covers a diabetes-risk random forest and a cart-pole control policy, comparing extracted trees with several baselines.The paper evaluates both fidelity and interpretability, including a user study with machine-learning graduate students.
- Related work: Prior extraction work learns decision trees using rejection sampling, whereas this paper directly targets paths needing additional data through active sampling.The comparison positions active sampling as the paper’s methodological distinction from related model-compression approaches.
2. Problem Formulation
The task is to learn a decision tree that approximates a blackbox classifier from training data and blackbox queries. Performance is evaluated by agreement with the blackbox on held-out inputs, with extensions to categorical features and regression.
- Decision trees: A decision tree is a binary tree whose internal nodes apply axis-aligned constraints and whose leaves return labels.For an internal node, inputs satisfying the constraint follow one child and all others follow the other child.
- Decision trees: Each node’s path is represented by a conjunction of the constraints encountered from the root to that node.This path constraint determines the feasible inputs associated with the node.
- Problem: The goal is to learn a decision tree T that approximates a blackbox function f using a training set and blackbox access.The blackbox is queried to obtain outputs for selected inputs.
- Setting: The primary formulation uses d-dimensional real inputs X = R^d and classification outputs Y = [m].The approach is stated to generalize to categorical input dimensions and regression outputs.
- Evaluation: Classification performance is measured by accuracy relative to f on a held-out test set.Binary classification additionally uses F1 score, while regression uses mean-squared error.
3. Decision Tree Extraction Algorithm
The extraction algorithm estimates an exact greedy decision tree by sampling from the input distribution within each leaf’s feasible region. It uses axis-aligned splits, Gini-based gains, and theoretical convergence under regularity and uniqueness assumptions.
- Sampling: The algorithm estimates an input distribution from training data, then actively samples inputs satisfying each leaf’s path constraints and labels them with the blackbox.The distribution is modeled as a mixture of axis-aligned Gaussians fitted using EM.
- Exact greedy tree: The exact greedy tree starts with the majority label under P and repeatedly splits leaves using axis-aligned constraints.Each split replaces a leaf with an internal node and two labeled children.
- Split selection: The algorithm selects leaf expansions by gain based on weighted Gini impurity and stops early when the best gain is zero.The gain determines which candidate leaf and split should be chosen next.
- Estimated tree: For estimated trees, split and label quantities are computed from n i.i.d. samples drawn conditionally within each leaf’s path region.Additional samples are used to select which leaf to expand.
- Constraint handling: Redundant path constraints are discarded, and mutually exclusive bounds make a region unsatisfiable with zero gain.The simplified representation keeps at most one lower and one upper inequality per feature.
- Theoretical guarantees: Under continuous, bounded, bounded-domain input density and unique maximizers, the estimated tree converges to the exact greedy tree as n approaches infinity.The paper defines convergence using an epsilon-approximation notion for complete trees.
4. Evaluation
Across diabetes-risk and cart-pole benchmarks, the extracted decision trees achieved higher fidelity than several baselines while remaining interpretable to users. The interpretations also exposed provider variation, potentially non-causal diabetes-risk patterns, and non-monotone age dependence.
- Fidelity: Our decision trees outperformed CART and born-again trees across tree sizes, with active sampling reducing overfitting in larger trees.Born-again trees struggled to generate new training points at deeper levels because they used rejection sampling.
- Fidelity: Our size-31 decision trees substantially outperformed rule-list and decision-set baselines, while decision-set learning did not scale to the diabetes-risk benchmark.For cart-pole, feature binning gave the tree a four-dimensional input versus 28 dimensions for the competing models, which may have reduced overfitting.
- Interpretability: On four diabetes-risk questions, all decision-tree answers matched the blackbox model, compared with three matching answers for the rule list.The questions assessed predictions and counterfactuals against the blackbox model.
- Diabetes-risk insights: The interpretations revealed provider-specific diagnosis patterns, including different frequencies of hyperlipidemia codes and impaired fasting glucose across providers.These covariate shifts can help data scientists adapt existing models to new providers.
- Diabetes-risk insights: The diabetes-risk tree exposed a likely non-causal low-risk pattern linked to prior doctor visits, and captured non-monotone age dependence that relative influence scores cannot represent.A physician reported no known diabetes-risk relationship for the relevant diagnoses and suggested prior visits and interventions as a plausible explanation.
5. Conclusion
The paper interprets blackbox models by extracting decision trees and identifies future work in richer input distributions and deeper use of extracted-tree insights.
- The approach interprets blackbox models through extracted decision trees.
- Future work includes model extraction with more expressive input distributions.
- Another future direction is developing new ways to gain insight from extracted decision trees.
A. Proofs of Main Results
This section introduces the proof of Theorem 3.4 without providing substantive proof details in the supplied passage.
- The section states that it gives a proof of Theorem 3.4.
A.1. Proof Overview
The proof overview argues that the estimated tree converges toward the exact greedy tree by aligning node structure, routed-point distributions, and labels as sample size grows.
- As sample size increases, the estimated tree’s internal and leaf parameters should converge to those of the exact tree.
- The proof quantifies tree error as the probability that an input is routed to the wrong leaf node.
- A mapping φ pairs each node in the exact tree with the node at the corresponding position in the estimated tree.
- The main lemma states that the routed-point distributions for corresponding nodes converge in L1 distance in probability.
- The overview frames the result as a high-probability convergence guarantee for the extracted tree.
A.2. Proof of Main Theorem
The theorem proof establishes correct leaf labels and then combines this with corresponding-node distribution convergence to bound the probability that the estimated and exact trees disagree.
- The proof proceeds in two steps: establish correct leaf labels, then bound whole-tree disagreement using Lemma A.1.
- For each corresponding leaf, the estimated label equals the exact label with probability approaching one as sample size increases.
- The proof rewrites leaf-label selection in terms of routed-point distributions and uses the unique maximizer assumption for the exact tree.
- Hoeffding’s inequality and a union bound control empirical label estimates across possible labels.
- A union bound over leaves combines distribution and label guarantees to show that tree disagreement is at most ϵ with probability at least 1 −δ.
- The proof concludes by applying Lemma A.1 and the preceding bounds to obtain the theorem.
A.3. Proof of Main Lemma
The proof shows that estimated tree parameters converge to those of the exact greedy tree, so corresponding inputs are routed and labeled consistently. In one dimension, the key step is proving convergence of split thresholds using uniform gain convergence and a gap around the population maximizer.
- The proof proceeds by induction on the structure of the exact tree, transferring parent-node correspondence to each child.
- In the one-dimensional case X = R, internal-node feature indices coincide automatically, so the proof reduces to showing t converges to t∗.The general case is described as a straightforward extension requiring additional bookkeeping.
- The proof separates threshold convergence into gain-function convergence and stability of maximizers under a sufficiently small uniform gain-function difference.
- Continuity and bounded support of G∗ imply an (ϵ′, δ′) gap, while the Gini-based gain function satisfies these regularity conditions.
- An (ϵ, δ)-gapped gain function has a unique maximizer and remains at least δ below its maximum outside an ϵ-neighborhood.
B. Proof of Technical Lemmas
This section introduces the technical lemmas needed for the proofs of the main convergence results.
- The technical lemmas support the proofs of Lemma A.1 and Theorem 3.4.
B.1. Proof of Convergence of the Gain Function
The technical analysis proves that the empirical gain function converges uniformly to its population counterpart. It combines error decomposition, concentration bounds, and regularity of the population gain function.
- B.1. Proof of Convergence of the Gain Function: The proof establishes uniform convergence of the estimated gain function G to the exact gain function G∗ as n →∞.
- B.1. Proof of Convergence of the Gain Function: The gain functions for the exact and estimated greedy trees are defined using Gini impurity.
- B.1. Proof of Convergence of the Gain Function: The analysis handles zero-gain cases by defining H∗(t) and H(t) as zero when their corresponding gain is zero.
- B.1. Proof of Convergence of the Gain Function: The first term is controlled by partitioning R into √n intervals with equal probability mass and bounding the number of samples in each interval.
- B.1. Proof of Convergence of the Gain Function: The proof decomposes ∥g −g∗∥∞ into three terms and shows each can be made arbitrarily small with high probability for sufficiently large n.
- B.1. Proof of Convergence of the Gain Function: Hoeffding’s inequality and union bounds control empirical deviations across intervals and candidate thresholds.
- B.1. Proof of Convergence of the Gain Function: The population gain function G∗ is continuous and has bounded support, providing the regularity conditions used in the convergence argument.
C. User Study Interface
The user study interface tests whether participants can understand decision-tree, rule-list, and decision-set interpretations across diabetes-risk and cart-pole tasks. Questions are designed around model structure rather than outside knowledge.
- Study design: Questions are adapted to each interpretation so every item has one correct answer, and model order is randomized within study parts.
- Study design: The study presents four models and asks participants questions whose answers depend only on each model’s structure.
- Study design: Participants are instructed to answer quickly, skip questions taking longer than about two minutes, and treat trained-model structure as the sole basis for responses.
- Predicting diabetes risk: Five diabetes-risk questions test interpretation of predictions and feature dependencies for a decision tree and a rule list.
- Predicting diabetes risk: The diabetes questions examine age, cholesterol, medications, diagnoses, smoking, and the additional information required for risk assessment.
- Predicting diabetes risk: A rule list is presented as a one-sided decision tree composed of sequential if-then-else statements.
- Cart-pole controller: The cart-pole section asks users to inspect actions, dependence on cart position, and left-to-right symmetry in decision-tree and decision-set controllers.
- Cart-pole controller: Decision sets are equivalent to rule lists but use a different training algorithm, implicit else clauses, and topmost-rule priority.