TL;DR
This paper introduces "Themis," a novel testing framework for automatically detecting and quantifying causal discrimination in software. Themis goes beyond existing methods by focusing on causality rather than just correlation, revealing that even state-of-the-art "fairness-aware" algorithms can still exhibit significant discrimination.
What Problem Does This Paper Address?
As software increasingly makes critical decisions in areas like criminal justice, finance, and healthcare, ensuring fairness and preventing discrimination is paramount. While many systems aim to avoid bias, evidence suggests that discrimination still creeps in. Existing methods for detecting this bias often rely on correlations or statistical disparities, which can miss subtle, causal forms of discrimination. The authors argue that a more robust approach is needed to measure how and why software discriminates, especially in complex, real-world systems.
Methods
The core contribution is Themis, a testing-based approach for measuring software discrimination. Key aspects include:
- Causal Discrimination Definition: The authors define discrimination not just as statistical disparity but as a causal relationship. A system is causally fair with respect to a characteristic if changing that characteristic never alters the output. This is a stronger definition than correlation-based measures.
- Automated Test Generation: Themis automatically generates test suites to measure discrimination. This is a significant departure from prior work that often required manual test creation.
- No Oracle Required: Themis doesn't need a pre-defined "correct" output (an oracle). The fairness itself serves as the oracle: if changing a sensitive input characteristic changes the output, discrimination is detected.
- Optimizations: To handle the combinatorial explosion of test cases, Themis employs:
- Test Caching: Reusing results of previously executed tests.
- Adaptive, Confidence-Driven Sampling: Intelligently selecting test cases and stopping when a desired confidence and error margin are met.
- Sound Pruning: Leveraging monotonicity properties of discrimination scores to eliminate large portions of the search space for discriminating characteristics.
Datasets
The evaluation uses two well-established financial datasets:
- Adult Dataset (Census Income Dataset): Contains demographic and financial data for ~45K individuals, used for predicting income.
- Statlog German Credit Dataset: Contains credit data for 1000 individuals, used for predicting creditworthiness ("good" or "bad").
These datasets are commonly used in fairness research, and the authors note their suitability for evaluating discrimination based on characteristics like race and gender.
Key Insights and Ideas
- Causality is Key: Focusing on causal discrimination reveals issues missed by purely statistical approaches. A system might appear fair on average but still discriminate heavily for specific subgroups.
- "Fairness-Aware" Algorithms Aren't Always Fair: Surprisingly, even algorithms explicitly designed to avoid discrimination often fail to do so, sometimes discriminating against a large percentage of inputs. This highlights the difficulty of achieving true fairness.
- Discrimination is Pervasive: The study found discrimination in a significant number of tested software instances, including those from prior work aiming for fairness.
- Themis is Efficient: The pruning optimization significantly reduces the number of test cases required, making fairness testing more practical.
- More Discrimination = More Efficient Testing: Themis becomes more efficient on systems that exhibit more discrimination, as pruning becomes more effective.
Key Results
- Themis effectively discovered software discrimination in 20 evaluated software systems.
- State-of-the-art techniques for removing discrimination from algorithms failed in many situations, sometimes discriminating against as much as 98% of an input subdomain.
- Themis's optimizations (caching, sampling, pruning) were effective in producing efficient test suites.
- Pruning reduced test suite sizes by an average factor of 2,849x for group discrimination and 148x for causal discrimination.
- In one instance (B census), the causal discrimination score for gender was over 21x higher than the group score (11.27% vs. 0.52%), demonstrating the value of causal testing.
- Another instance (F census) showed a causal discrimination score of 98.1% against country and race.
Limitations and Future Work
- Categorical Assumption: The formal definitions currently assume categorical input and output characteristics. While binning can handle continuous variables, extending the definitions directly is a future direction.
- Operational Profiles: The paper mentions using operational profiles for apparent discrimination but notes that the confidence of these measurements is limited by the representativeness of the profile.
- Combinatorial Testing: The authors suggest that integrating advanced combinatorial testing techniques could further improve Themis's efficiency.
- Broader Applicability: While evaluated on financial systems, the authors believe Themis is applicable to a broader range of domains where software makes discriminatory decisions.
Summary updated