Research map / Learning theory and algorithms / Prediction and decision losses

Extracting PAC Decision Trees from Black Box Binary Classifiers: The Gender Bias Study Case on BERT-based Language Models

AAAI 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Optimal decision tree learning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extracts decision trees with PAC guarantees from black-box binary classifiers (BERT/RoBERTa pronoun predictors) via a TrePAC-style algorithm, and uses them to reveal occupational gender bias.

Problem

Surrogate decision trees extracted from black-box models lack theoretical guarantees on fidelity to the original model; the paper asks how PAC guarantees can be provided for such extracted trees in binary classification.

Approach

Derives a PAC sample-size bound for finite hypothesis spaces allowing up to k training misclassifications, and adapts the TrePAC tree-induction algorithm (membership queries, binary entropy splits, PAC-derived sample size and node budget) to extract decision trees from BERT-based models with PAC fidelity guarantees.

Key results

• Extracted PAC decision trees from all four BERT-based models have training error below the epsilon=0.2 bound (e.g., RoBERTa-base 0.020, BERT-large-cased 0.002 at n=10, k=10).
• Extracted trees reproduce occupational gender bias: 'nurse' maps to female in 0.50 of extracted rules, with industrialist, footballer and boxer mapping to male.
• Tree extraction time is negligible (about 0.0007 s), while querying the models takes roughly 85 to 510 seconds (per Appendix Table 5 totals up to about 1700 s).

Measured effects reported in the paper

Surprising findings

• RoBERTa-base and RoBERTa-large yield higher training errors than BERT models, suggesting larger-corpus models need more internal nodes.

Limitations

• Models are not binary classifiers; pronoun prediction (she/he) is treated as binary, excluding 'they'.
• Evaluated on a single template-based case study with 360 sentences and 22 binary features.
• Sample-size bounds are for finite hypothesis spaces and require sizing the hypothesis space by n^|F|.

Experimental setup

Datasets: template-generated sentences (360 sentences from 5 birth periods, 9 locations, 8 occupations)

Benchmarks: template-generated occupational gender bias sentences

Metrics: training error true error misclassified examples querying time

Baselines: Horn-algorithm rule extraction (Blum et al. 2023 case study)

Builds on: TrePAC Trepan PAC learning Angluin Horn algorithm

Closest papers by meaning

• Decision Trees with Short Explainable Rules (NeurIPS 2022 · similarity 0.84)
• Generative Model for Decision Trees (AAAI 2024 · similarity 0.83)
• Multistage Defer Trees for Hybrid Interpretability: If at First You Can't Succeed, Tree Again (NeurIPS 2026 · similarity 0.83)
• Symbolic Regression Enhanced Decision Trees for Classification Tasks (AAAI 2024 · similarity 0.83)
• Debiasing Algorithm through Model Adaptation (ICLR 2024 · similarity 0.82)
• Trust Regions for Explanations via Black-Box Probabilistic Certification (ICML 2024 · similarity 0.81)