Source-linked AI summary
FAHT: An Adaptive Fairness-aware Decision Tree Classifier
Wenbin Zhang, Eirini Ntoutsi
TL;DR
Automated decision systems can reproduce discrimination from biased historical data, while existing fairness methods often overlook evolving stream populations. The paper introduces FAHT, a fairness-aware extension of Hoeffding Trees using fair information gain for online classification. Experiments show lower discrimination with moderate or comparable predictive performance over streams.
Problem
Existing fairness-aware learning methods generally treat discrimination as static despite data streams whose populations and distributions evolve over time.
Method
FAHT extends Hoeffding Trees with a fair information gain splitting criterion that jointly considers predictive information and fairness.
Results
FAHT consistently reduces discrimination while maintaining fairly comparable accuracy, including discrimination decreases of 27.89% and 53.22% with accuracy reductions of 2.48% and 8.20% on Adult and Census, respectively.
Takeaways & Limitations
Fairness-aware induction can support fair predictions while allowing model adaptation to evolving stream distributions.
Takeaways & Limitations
The evaluation assumes fully supervised prequential learning with labels becoming available shortly after each instance arrives, and binary sensitive and class attributes.
Abstract
from arXiv · showhide
Automated data-driven decision-making systems are ubiquitous across a wide spread of online as well as offline services. These systems, depend on sophisticated learning algorithms and available data, to optimize the service function for decision support assistance. However, there is a growing concern about the accountability and fairness of the employed models by the fact that often the available historic data is intrinsically discriminatory, i.e., the proportion of members sharing one or more sensitive attributes is higher than the proportion in the population as a whole when receiving positive classification, which leads to a lack of fairness in decision support system. A number of fairness-aware learning methods have been proposed to handle this concern. However, these methods tackle fairness as a static problem and do not take the evolution of the underlying stream population into consideration. In this paper, we introduce a learning mechanism to design a fair classifier for online stream based decision-making. Our learning model, FAHT (Fairness-Aware Hoeffding Tree), is an extension of the well-known Hoeffding Tree algorithm for decision tree induction over streams, that also accounts for fairness. Our experiments show that our algorithm is able to deal with discrimination in streaming environments, while maintaining a moderate predictive performance over the stream.
1 Introduction
Automated decisions raise fairness and accountability concerns because historical data can encode discrimination, while existing fairness methods largely treat the problem as static. The paper introduces a stream-oriented fairness-aware classifier to adapt to evolving populations.
- Historical data can encode discrimination into predictive models even when the underlying algorithm is not explicitly discriminatory.Ignoring sensitive attributes does not prevent indirect discrimination when other features correlate with them.
- Existing fairness-aware approaches generally assume a static population, although streaming data distributions can change over time.The paper argues that fairness-aware learning for streams must adapt to the underlying distribution.
- FAHT extends Hoeffding Trees with a fairness-aware stream classifier designed to address discrimination while maintaining predictive performance.The proposed work is presented as the first to address discrimination in data stream classification.
- The paper contributes a fair information gain criterion, an adaptive online learner, and experiments examining predictive performance, fairness, and tree structure.The fair splitting criterion jointly considers information and fairness gains.
2 Basic Notions
The paper defines a supervised stream setting in which instances are tested before their labels arrive for training, and formalizes fairness through sensitive groups and statistical parity. Discrimination is assessed by comparing benefit rates between deprived and favored communities.
- The stream learner predicts each arriving instance before using its subsequently revealed label for model updates, an evaluation known as prequential testing.This is also called first-test-then-train evaluation.
- The fairness setting assumes binary sensitive and class attributes, producing deprived-rejected, deprived-granted, favored-rejected, and favored-granted communities.Gender and benefit approval are used as the running example for the sensitive and class attributes.
- Statistical parity evaluates whether the probability of receiving a benefit is equal for deprived and favored communities.It can be measured on the original dataset or on classifier predictions.
- The discrimination score compares granted-benefit rates for favored and deprived communities.A higher rejection rate for the deprived community indicates potential discrimination.
3 Related Work
Related work addresses fairness through data preprocessing, algorithmic modification, or post-processing, while stream learning focuses on adapting to changing distributions. The paper combines these directions by building a fairness-aware method on Hoeffding Trees.
- 3 Related Work: Fairness-aware learning methods are commonly organized into pre-processing, in-processing, and post-processing approaches.These categories respectively modify data, learning algorithms, or resulting decision regions.
- 3.1 Fairness-aware Learning: Pre-processing changes training data to balance communities but cannot guarantee fairness and may not remove discrimination introduced by the learning algorithm.Massaging is one example that swaps selected class labels to restore balance.
- 3.1 Fairness-aware Learning: In-processing modifies the learner to account for fairness, including decision-tree splitting criteria that incorporate discrimination.The paper distinguishes its fairness gain based on split-induced discrimination from prior entropy-based criteria.
- 3.2 Stream Classification: Post-processing adjusts learned decision regions or tree leaves, but transferring such methods to streams is difficult because leaves can change under concept drift.Stream methods must also adapt incrementally to changing joint data distributions and manage historical information.
- 3.2 Stream Classification: The proposed approach combines algorithm-level fairness with online stream learning by building on the Hoeffding Tree classifier.Hoeffding Trees are presented as a widely used decision-tree model for data streams.
4 Fairness-Aware Hoeffding Tree Classifier
FAHT extends Hoeffding Trees for streaming fairness by combining predictive and discrimination-aware split evaluation while preserving online adaptation. The design adds fairness-aware statistics and pruning mechanisms so tree induction can jointly target accuracy and fairness.
- Fairness-aware extension: Unlike original Hoeffding Trees, which optimize predictive performance through information gain alone, FAHT incorporates fairness into online splitting decisions.The original approach can therefore induce an unfair tree over the course of a stream.
- Fairness-aware extension: FAHT extends Hoeffding Trees with a splitting criterion that jointly evaluates classification and discrimination gains.The method also maintains node statistics needed to compute this criterion during stream processing.
- Fairness gain: Fairness gain measures discrimination reduction from splitting, paralleling information gain while evaluating split merit from the fairness perspective.It compares discrimination before splitting with aggregated discrimination across the resulting partitions.
- Fair information gain: Fair information gain combines information gain and fairness gain into one objective, making tree construction both accuracy- and fairness-driven.When fairness gain is zero, the criterion reduces to information gain; multiplication is preferred because the metrics may be incomparable in scale and it favors discrimination-reducing splits.
- Refinements: FAHT adapts Hoeffding-tree pre-pruning by comparing candidate splits against a null nonsplitting option using fair information gain.The null option represents the current class distribution and current discrimination level.
- Refinements: FAHT augments streaming sufficient statistics with discrimination-related information for discrete and numeric attributes, while retaining the original tree's efficient one-pass setting.Numeric attributes update distribution statistics by sensitive-attribute value and class, and potential thresholds are evaluated for binary splits.
5 Experiments
The experiments evaluate FAHT against accuracy- and fairness-oriented baselines on streaming datasets, measuring predictive accuracy, statistical parity, tree structure, and stream adaptation. FAHT reduces discrimination while retaining comparable accuracy and produces more conservative tree structures than HT.
- 5.2 Accuracy vs. Fairness: FAHT’s fair information gain criterion jointly evaluates information and fairness, controlling discrimination propagation during incremental stream learning.The experiments assess accuracy and statistical parity using prequential evaluation, predicting each incoming instance before updating the model.
- 5.2 Accuracy vs. Fairness: FAHT decreases discrimination by 27.89% on Adult and 53.22% on Census, while reducing accuracy by 2.48% and 8.20%, respectively.The comparison is against HT, with Kamiran’s method showing little numerical difference from HT; the anti-discrimination capability is statistically significant in Table 2.
- 5.2 Accuracy vs. Fairness: FAHT consistently lowers discrimination with comparable accuracy across alternative stream-adaptation strategies.With window size 1000, FAHT gives the best discrimination reduction, whereas HT gives the worst fairness result; HT nevertheless provides better prediction performance.
- 5.3 Structural Effects on the Tree Construction: FAHT selects attributes differently from HT, favoring age over capital-gain because age balances predictive information with reduced encoding of historical discrimination.The analysis uses Pearson correlations among attributes, sensitive attributes, predicted decision boundaries, and actual decision boundaries.
- 5.3 Structural Effects on the Tree Construction: FAHT produces shorter trees than HT because its fair information gain criterion is more restrictive than ordinary information gain.The authors characterize FAHT’s induction as more conservative and link this property to improved interpretability; Figure 2 reports model complexity over the stream.
6 Conclusion
The proposed fairness-aware stream classifier maintains moderate predictive performance with low discrimination as data distributions evolve. It achieves this by incorporating discrimination awareness into induction through a fair information gain splitting criterion.
- The approach maintains moderate predictive performance with low discrimination scores over the stream while adapting to evolving data distributions.
- Fair information gain incorporates discrimination awareness into model induction to support fair predictions during stream adaptation.
- Future work will extend the approach to ensemble learning with different window models and learner complexities.
- The authors also plan to investigate semantic similarities and differences between FAHT and Hoeffding Tree induced models.