TL;DR
This paper introduces a novel method for extracting decision trees from complex "black box" AI models, providing theoretical guarantees of accuracy using the Probably Approximately Correct (PAC) framework. They demonstrate this by uncovering occupational gender bias in BERT-based language models, offering a more interpretable view of these biases.
What Problem Does This Paper Address?
Explaining the decisions of complex AI models, especially deep neural networks, is a major challenge in Explainable AI (XAI). Decision trees are highly interpretable, but they often lack the predictive power of neural networks. A common approach is to extract decision trees as "surrogate" models to approximate the behavior of black box models. However, a critical gap exists: current methods lack theoretical guarantees on how accurately these extracted trees represent the original model's behavior. This makes it difficult to trust the explanations provided. The authors aim to bridge this gap by introducing PAC guarantees for decision tree extraction, allowing for a more rigorous assessment of their fidelity. They apply this to a specific, socially relevant problem: uncovering gender bias in BERT-based language models.
Methods
The core contribution is the adaptation of the Probably Approximately Correct (PAC) learning framework to provide theoretical guarantees for decision tree extraction. The authors define formal notions of fidelity and relate them to PAC guarantees. They adapt a decision tree algorithm, inspired by the TopDown algorithm and the TREPAC algorithm, to incorporate PAC guarantees. This involves calculating the necessary sample size for learning based on the desired accuracy ($\epsilon$), confidence ($\delta$), and the number of allowed misclassifications ($k$). They focus on binary classification and use a membership oracle (MQC) to query the black box model for classifications, which is a standard technique in PAC learning.
Datasets
The paper uses BERT-based language models (BERT-base-cased, BERT-large-cased, RoBERTa-base, and RoBERTa-large) as the "black box" models. The experiments are based on a study case by Blum et al. (2023) which involves creating sentences using templates that combine birth period, location, and occupation features. These sentences are then used to probe the language models for pronoun prediction ('she' or 'he'), effectively creating a binary classification task. No new datasets were introduced; existing language models and a specific experimental setup were utilized.
Key Insights and Ideas
- PAC Guarantees for Decision Tree Extraction: The most significant insight is the formalization of PAC guarantees for decision trees extracted from black box models. This moves beyond empirical validation to theoretical assurance of fidelity.
- Bridging Interpretability and Accuracy: The work demonstrates that it's possible to achieve a balance between the interpretability of decision trees and the predictive power of complex models by providing theoretical bounds on their approximation.
- Decision Trees as a Lens for Bias: Extracting decision trees from language models reveals specific features and decision rules that contribute to occupational gender bias, making these biases more visually understandable and actionable.
- Feasibility of PAC for Real-World Models: The experiments show that the PAC framework is practically feasible for complex models like BERT, even when dealing with the inherent noise and approximations involved.
Key Results
- The proposed method successfully extracts decision trees from BERT-based language models with PAC guarantees.
- The experiments confirm previous findings of occupational gender bias in these models, consistent with the study by Blum et al. (2023).
- The decision tree format enhances the visualization of which occupations are most impacted by social bias, with "nurse" being identified as the most biased occupation towards female.
- The training error of the extracted decision trees was consistently below the chosen upper bound ($\epsilon = 0.2$), validating Theorem 8.
- The number of misclassified training examples decreases as the tree size increases, and appropriate tree sizes can be chosen to ensure the number of misclassified examples is at most $k$.
Limitations and Future Work
- Binary Classification Focus: The current work focuses on binary classification. Extending the PAC framework to multi-class classification would be a valuable future direction.
- Computational Cost: While the time for running the TREPAC algorithm itself was negligible, generating training data by querying BERT-based models could take significant time (85-510 seconds per experiment).
- Sampling Strategy: The paper suggests exploring sampling strategies that better satisfy the constraints of decision tree leaves, similar to techniques used in Trepan, to improve the PAC analysis.
- Adaptation for Complex PAC: Adapting the PAC framework for scenarios where randomly selecting examples that satisfy leaves changes the sample space is noted as a complex but promising area for future research.
Summary updated