Fairness-aware machine learning seeks to maximise utility in generating predictions while avoiding unfair discrimination based on sensitive attributes such as race, sex, religion, etc. An important line of work in this field is enforcing fairness during the training step of a classifier. A simple yet effective binary classification algorithm that follows this strategy is two-naive-Bayes (2NB), which enforces statistical parity requiring that the groups comprising the dataset receive positive labels with the same likelihood. In this paper, we generalise this algorithm into N-naive-Bayes (NNB) to eliminate the simplification of assuming only two sensitive groups in the data and instead apply it to an arbitrary number of groups. We propose an extension of the original algorithm's statistical parity constraint and the post-processing routine that enforces statistical independence of the label and the single sensitive attribute. Then, we investigate its application on data with multiple sensitive features and propose a new constraint and post-processing routine to enforce differential fairness, an extension of established group-fairness constraints focused on intersectionalities. We empirically demonstrate the effectiveness of the NNB algorithm on US Census datasets and compare its accuracy and debiasing performance, as measured by disparate impact and DF-ϵ score, with similar group-fairness algorithms. Finally, we lay out important considerations users should be aware of before incorporating this algorithm into their application, and direct them to further reading on the pros, cons, and ethical implications of using statistical parity as a fairness criterion.
Today, countless machine learning-based systems are in use that autonomously make decisions or aid human decisionmakers in applications that significantly impact individuals’ lives. This has made it vital to develop ways of ensuring these models are trustworthy, ethical, and fair. The ifeld of fairness-aware machine learning is centered on enhancing the fairness, explainability, and auditability of ML models. A goal many research works in this field share is to maximise utility in generating predictions while avoiding discrimination against people based on specific sensitive attributes, such as race, sex, religion, nationality, etc.
Researchers have devised many formalisations to try and
capture intuitive notions of fairness, each with different
priorities and limitations. We summarise the ones we will
men___________________________________
In T. Kido, K. Takadama (Eds.), Proceedings of the AAAI 2022 Spring Symposium
“How Fair is Fair? Achieving Wellbeing AI”, Stanford University, Palo Alto, California,
USA, March 21–23, 2022. Copyright © 2022 for this paper by its authors. Use permitted
under Creative Commons License Attribution 4.0 International (CC BY 4.0).
tion here in Table 1. Traditionally, the proposed notions have
been classified into two categories. The simplest and most
well-studied, group fairness, is based on defining distinct
protected groups in the given data. Then, for each of these
groups, a user-selected statistical constraint must be
satisifed. This has notable disadvantages: It requires groups to be
treated fairly in aggregate, but this guarantee does not
necessarily extend to individuals
An orthogonal notion to group fairness is individual
fairness. Put simply, this notion requires that ”similar
individuals be treated similarly”
Alternative models of fairness have been proposed to
address the disadvantages of the two traditional definitions.
One model is causal fairness, which examines the unfair
causal effect the sensitive attribute value may have on the
prediction made by an algorithm
A similar model is statistical parity subgroup fairness
(SF), which focuses on mitigating intersectional bias by
applying group fairness to the case of infinitely many, very
small subgroups
Despite the lack of consensus on any universal notion of
fairness, research has proceeded using the existing models.
A major line of work in the development of fair learning
algorithms is enforcing fairness during the training step of a
classifier
A recent publication exploring the arguments for and
against statistical parity
This opens the question of how 2NB can be applied to data with multiple, overlapping sensitive attributes while avoiding oversimplification. The 2NB algorithm is applicable to a wide range of tasks and its effectiveness, even in comparison to more complex algorithms, has been demonstrated (Kamishima et al. 2013; Friedler et al. 2019). At the same time, its’ design is sufficiently elegant and intuitive to be approachable to practitioners across many disciplines - an important advantage. Thus, extending the algorithm to cover more use cases will be the focus of this work.
This paper seeks to build upon Calders and Verwer’s work by exploring the following: • We adapt the original 2NB structure and balancing routine to support multiple, polyvalent (categorical) sensitive features. • We use this new property of the algorithm to apply it to differential fairness. • To support the above, we examine the extended algorithm’s performance on real-world US Census data. • Finally, we lay out important considerations users should be aware of before using this algorithm. We draw upon the literature to lay out the pros, cons, and ethical implications of using statistical parity as a fairness criterion.
of groups should be 1 or greater than p%.
Naive Bayes Naive Bayes is a probabilistic data mining
and classification algorithm. In spite of its relative
simplicity, it has been shown to be very competent in real-world
applications that require classification or class probability
estimation and ranking1. Various strategies have been explored
for improving the algorithm’s performance by weakening its
conditional independence assumption. These include
structure extension, attribute weighting, etc. These techniques
focus on maximising accuracy or averaged conditional log
likelihood (Jiang 2011). Calders and Verwer’s proposal of
composing multiple naive Bayes models instead aims to
enforce independence of predictions with respect to a binary
sensitive feature, thus satisfying the statistical parity
constraint between the two groups
A more recent proposal, differential fairness (DF),
extends existing group fairness concepts to protect subgroups
defined by intersections of and by individual sensitive
attributes. The original papers by (Foulds et al. 2020) and
1Recent, novel applications include
(Friedler, Scheidegger, and Venkatasubramanian 2016)
introduce the concept of distinct worldviews which influence
how we pursue fairness. One of them is that We’re All Equal
(WAE) i.e. there is no association between the construct (the
latent feature that is truly relevant for the prediction) and the
sensitive attribute. The orthogonal worldview is that What
You See Is What You Get, wherein the observed labels are
accurate reflections of the construct. In
2
The proposed N-naive-Bayes algorithm is a supervised binary classifier that allows the enforcement of a statistical fairness constraint in its predictions. Given an (ideally large) training set of labelled instances, the algorithm partitions the data based on sensitive attribute value and trains a separate naive Bayes sub-estimator on each of the sub-sets. This is an extension of the original two-naive-Bayes structure, where exactly two sub-estimators are trained. The next step of the training stage is for the conditional probabilities P (Y |S) to be empirically estimated from the training set. Where Ns is the number of instances that belong to group s, and Ny,s the number of instances of that group that have label y, the empirical conditional probability2 is given as:
P (y|s) =
Ny,s + α Ns + 2 ∗ α (1)
Finally, the algorithm modifies the joint distribution P (Y, S) to enforce the given fairness constraint. Then, the 2Equation (1) gives a smoothed empirical probability, where the constant α is the parameter of a symmetric Dirichlet prior with concentration parameter 2 ∗ α, since a binary label is assumed. ifnal predicted class probabilities, for a sample xs (where x is the feature vector excluding the sensitive feature s), is: P (y|xs) = P (x|y) ∗ P (s|y) ∗ P (y) = Cs(x) ∗ P (s|y) ∗ P (y) = Cs(x) ∗ P (s ∩ y) (2) (3) (4) Where Cs is the the sub-estimator for sensitive group s ∈ S.
To satisfy the statistical parity constraint, the original 2NB
algorithm runs a heuristic post-processing routine that
iteratively adjusts the conditional probabilities P (Y |S) of the
groups in the direction of making them equal. During its
execution, this probability-balancing routine alternates
between reducing N (Y = 1, S = 1) and increasing N (Y =
1, S = 0) depending on the number of positive labels
outputted by the model at each iteration. This is to try and keep
the resultant marginal distribution of Y stable. Once
balancing is complete, the value of P (S|Y ) can be induced from
Ny,s similar to (1). The first contribution of this paper is to
extend this routine to suit the polyvalent definition of
statistical parity we will use:
Definition 1. Statistical (Conditional) Parity for Polyvalent
S
For predicted binary labels yˆ and polyvalent sensitive feature S, statistical (conditional) parity requires 3: P (yˆ = 1|s) = P (yˆ = 1|s′) ∀ s, s′ ∈ S (5)
We modify the probability-balancing routine to subtract and add probability to the group with the highest (max) and lowest (min) current P (Y = 1|s) respectively. These probabilities are re-computed with each iteration, and the max and min groups re-selected. Further, we introduce the constraint that only groups designated by the user as privileged can receive a reduction in their likelihood of getting a positive label 4. This is to avoid making any assumptions about which groups it would be appropriate to demote positive instances of. It allows the balancing routine to terminate immediately if it over-corrects, or if the data is such that P (yˆ = 1|snp) > P (yˆ = 1|sp) to begin with, as is the case in the well-known UCI Adult dataset, for example. This gives us the final form of our statistical parity criterion: Definition 2. Statistical Parity Criterion for NNB: For predicted binary labels yˆ and sensitive feature S: P (yˆ = 1|sp) = P (yˆ = 1|snp) ∀ (sp, snp) ∈ Sp × Snp (6) Where Sp and Snp are the sub-sets of all privileged and nonprivileged sub-groups of S respectively.
We adapt the above definition into a score that the algorithm can minimise: disc = max P (yˆ = 1|sp) − min P (yˆ = 1|snp) (7) 3The cited definition requires this to hold for all values of yˆ, however for a binary label it is sufficient to check yˆ = 1. 4A similar constraint is explored by (Zafar et al. 2017). Algorithm 1: Pseudocode for a probability-balancing routine to enforce statistical parity 1: Calculate the parity score, disc, of the predicted classes by the current model and store smax, smin 2: while disc > disc0 do 3: Let numpos be the number of positive samples by the current model 4: if numpos < the number of positive samples in the training set then 5: N (y = 1, smin) + = ∆ ∗ N (y = 0, smin) 6: N (y = 0, smin) − = ∆ ∗ N (y = 0, smin) 7: else 8: N (y = 1, smax) + = ∆ ∗ N (y = 1, smax) 9: N (y = 0, smax) − = ∆ ∗ N (y = 1, smax) 10: end if 11: If any N (y, s) is now negative, rollback the changes and terminate 12: Recalculate P (Y |S), disc, smax, smin 13: end while
Note that the above criterion can easily be relaxed to apply the four-fifths rule for removing disparate impact (or its more general form, the p% rule (Zafar et al. 2017)) instead of perfect statistical parity. For the purposes of this paper, however, we explore the effect of statistical parity in its base form.
We also note the definition of disparate impact we use in the evaluation stage:
Disparate Impact (Mean) for Polyvalent S: 1
X
P (yˆ = 1|snp) |Sp × Snp| (sp,snp) P (yˆ = 1|sp)
Algorithm 1 describes the extended probability balancing heuristic for enforcing parity. The values of sp, snp in the parity criterion (Equation 7) are referred to as smax and smin respectively. At each iteration, the routine determines these groups and adjusts their conditional probabilities. A further modification from the original is that the proportion by which the probabilities are adjusted with each iteration is now proportional to the size of the group itself, instead of the size of the opposite group. In experiments, this yields a great performance improvement, especially where the distribution of samples over S is very imbalanced.
An alternative measure of fairness we explore is differential fairness, as given in (Foulds et al. 2020).
Definition 4. A classifier is ϵ-differentially fair if: e−ϵ ≤
P (yˆ|s) ϵ
P (yˆ|s′) ≤ e ∀ s, s′ ∈ S, yˆ ∈ Y
The (smoothed) empirical differential fairness score, from the empirical counts in the data, assuming a binary label, is: eϵ− ≤
N (yˆ, s) + α N (s) + β
N (s′) + β ϵ N (yˆ, s′) + α ≤ e ∀ s, s′ ∈ S, yˆ ∈ Y (8) (9)
This is used in experiments to estimate the value of ϵ (the ϵ-score) from the predicted labels on the dataset 5. In experiments we set β = 2 ∗ α and substitute with the observed conditional probability estimates from the dataset. An additional measure given in (Foulds et al. 2020) to assess fairness from the standpoint of intersectionality is differential fairness bias amplification. This measure gives an indication of how much a black-box classifier increases the unfairness over the original data (Foulds et al. 2020; Zhao et al. 2017). Definition 5. Differential Fairness Bias Amplification
A classifier C satisfies (ϵ 2 − ϵ 1)-DF bias amplification w.r.t. dataset D if C is ϵ 2-DF fair and D is ϵ 1-DF fair.
To adjust the joint distribution P (Y, S) to minimise satisfy DF-fairness and minimise the ϵ-score, we propose a new heuristic probability-balancing routine and associated discrimination score. The distinction from the balancing routine given in Algorithm 1 is that this focuses on outputting a narrower range of probabilities, while still avoiding negatively impacting groups that are designated as nonprivileged. To form the new discrimination score, we apply the principle of separating privileged and non-privileged sub-groups of S from the previous section to the ϵ-score definition: e−ϵ
≤ Snp:
P (yˆ = 1|snp) ϵ
P (yˆ = 1|sp) ≤ e ∀ (sp, snp) ∈ Sp × Snp (10) We then express this restricted ϵ-score as the maximum of two ratios: eϵ = max(ρ d, ρ u), where for (sp, snp) ∈ Sp × ρ d = max P (yˆ = 1|snp) , ρ u = max P (yˆ = 1|sp) P (yˆ = 1|sp)
P (yˆ = 1|snp) (11)
The execution of the proposed balancing routine is determined by these ratios. If ρ d is greater, then the nonprivileged sub-group with smallest probability at that iteration receives an increase in probability. If ρ u is greater, then the privileged group with highest probability receives a decrease in probability. These conditions can be expected to alternate as the conditional probabilities P (Y |S) converge. Iteration continues until ρ d is close to zero. The smax and smin groups are determined as in the previous section.
This routine disregards the number of positive labels the
model produces, while Algorithm 1 attempts to keep that
number close to the number of positive labels in the
training data. This allows it to avoid situations where a single,
non-privileged sub-group with small probability would
require the probabilities of the privileged groups to be reduced
significantly. In such cases, other non-privileged sub-groups
might maintain much higher probabilities, therefore giving
a poor ϵ-score. An further difference is the proportion by
5Note that this definition produces noisier estimates for
subgroups with fewer members.
Finally, note that all the above probability-balancing
routines (including Calders and Verwer’s original one) are
based around the assumption that the distribution of labels
over the sensitive feature(s) in the training set is reflective of
the test setting. This assumption is not unique to this model
(see
3
We implement NNB in Python within the scikit-Learn framework, using Gaussian naive Bayes as the subestimator. We then evaluate its performance in two experiments.
For both experiments, we use real-world data from the US
Census Bureau6.
The details of which features are included in each task and
what filtering takes place can be found in the paper
surveys/acs/microdata/documentation.html 7https://github.com/zykls/folktables indicated after its name, e.g. Income-Race-Sex is the Income task using race and sex as the sensitive features. To best capture intersectional fairness when using multiple sensitive features, we follow the approach from (Foulds et al. 2020) and define each group s as a tuple of the sub-groups of each sensitive feature that each sample belongs to. First Experiment This experiment compares NNB’s performance with other algorithms. The comparison includes ”vanilla” models as baselines for performance, and several group-fairness-aware algorithms that have a similar focus to NNB - ensuring non-discrimination across protected groups by optimising metrics such as statistical parity or disparate impact. Specifically, we consider the following: • GaussianNB, DecisionTree, LR, SVM: scikitLearn’s Gaussian naive Bayes, Decision Trees, Logistic Regression, and SVM. • Feldman-DT, Feldman-NB: A pre-processing algorithm that aims to remove disparate impact. It equalises the marginal distributions of the subsets of each attribute with each sensitive value (Feldman et al. 2015). The resulting ”repaired” data is then used to train scikit-Learn classifiers - Decision Trees (DT) and Gaussian naive Bayes (NB). • Kamishima: An in-processing method that introduces a regularisation term to logistic regression to enforce independence of labels from the sensitive feature (Kamishima et al. 2012). • ZafarAccuracy, ZafarFairness: An inprocessing algorithm that applies fairness constraints to convex margin-based classifiers (Zafar et al. 2017) . Specifically, we test two variations of a modified logistic regression classifier: The first maximises accuracy subject to fairness (disparate impact) constraints, while the latter prioritises removing disparate impact. • 2NB: Calders and Verwer’s original algorithm, using the same GaussianNB sub-estimator as NNB. • NNB-Parity, NNB-DF: N-naive-Bayes tuned to satisfy statistical parity using Algorithm 1, and DF-parity using Algorithm 2.
For the comparison we use the benchmark provided by (Friedler et al. 2019). The fairness-aware algorithms are tuned via grid-search to optimise accuracy. The performance of the algorithms is then measured over ten random train-test splits of the data.
Second Experiment This experiment demonstrates how NNB performs in finer detail. We consider GaussianNB, NNB-Parity, and NNB-DF as before, and we further include 2NB, the original two-naive-Bayes algorithm implemented identically to NNB. Finally, we include Perfect as a secondary baseline, to illustrate the scores that would be achieved by a perfect classifier.
To evaluate the performance of the above algorithms, we note the mean and variance of the following measures over 10 random train-test splits: accuracy, AUC, disparate impact score (mean of the DI between all privileged and nonprivileged groups), statistical parity score (as defined in 2), DF-ϵ (as defined in 4), DF-bias amplification score (as deifned in 5). We also compare the resultant distribution of labels over groups of S on a single random train-test split.
First Experiment Figure 1 gives the accuracy vs. the disparate impact and DF-ϵ scores on the Income-Race and Income-Race-Sex tasks. Figure 2 shows the same for Employment-Race and Employment-Race-Sex. It can be seen that on Income-Race, NNB results in a higher DI score than 2NB and has often over-favoured non-privileged groups causing a score > 1. Its accuracy is on-par with 2NB and the baseline naive Bayes, DT, and LR models. Feldman’s algorithm with Decision Trees results similar disparate impact score in some splits, but lower accuracy. The same is true for the DF-ϵ score on this task. On Income-Race-Sex, NNB-DF beats out all other algorithms in achieving DI ∼ 1, however NNB-Parity has higher accuracy than both NNB-DF and naive Bayes. NNB-DF is also the most successful at minimising the ϵ-score for this task, though again this comes at the cost of lower accuracy than the baseline model.
On Employment-Race all naive Bayes models achieve similar accuracy, while DT and LR-based models rank higher, and SVM the highest. The same can be observed for Employment-Race-Sex, and for both tasks NNB-DF again gives the ϵ-scores closest to zero.
Second Experiment Table 2 gives the scores achieved on the Income-Race task, and Table 3 gives the same Employment-Race-Sex. On Income-Race, both NNB models gave an improved parity score compared to the perfect classifier and GaussianNB. NNB and 2NB also gave improved disparate impact scores over the baseline models, but 2NB under-corrected while the NNB models gave a score > 1 indicating they favoured the non-privileged groups over the privileged group.
NNB-Parity and NNB-DF gave similar disparate impact scores, but the former gave higher accuracy while the latter produced a narrower range of positive label proportions, and thus better parity, ϵ, and DF-bias amplification scores. The evident accuracy trade-off is more pronounced in the latter task, with NNB-Parity achieving an accuracy of 0.7445 ± 0.00, and NNB-DF achieving 0.7199 ± 0.00. On Employment-Race-Sex, NNB-DF outperformed NNB-Parity on all scores. This was also the case for Employment-Race, where both models had similar accuracy but NNB-DF displayed less over-correction in its disparate impact score (1.0336 ± 0.0001 versus 1.2760 ± 0.0002), in addition to the expected improvement in ϵ-score (0.1068 ± 0.001 versus 0.3434 ± 0.0001). This suggests the DF balancing routine is better suited for the Employment task than the parity-based routine.
4
In this work we presented an extension of the two-naiveBayes algorithm, adapting it to suit datasets with multiple, polyvalent sensitive features. We applied the proposed N-naive-Bayes structure to intersectionality and differential fairness by giving an alternative probability-balancing routine. Our experiments on real-world datasets yielded favourable results and demonstrated the effectiveness and the differences between the parity and DF-based approaches.
We conclude by laying out key considerations users
should take into account before using N-naive-Bayes:
Statistical Parity as a Fairness Criterion Statistical
parity stands opposed to the (aggregate) accuracy of a classifier,
except in degenerate cases where the data is already fair, so
it is recommended that a balance between the two is pursued
We recommend further reading on the advantages and
disadvantages of group fairness in general
Users should always consider the implications of
estimating probability distributions for each group separately (as
is done at the beginning of the training stage), as well as
the mechanism behind any post-facto probability tuning they
decide on. Further, users should understand the implications
of affirmative action, its downstream effects, and ensure it
is appropriate to their application. As a starting point for
further reading, see
Finally, the explicit choice of sensitive features to
consider when enforcing statistical parity is a simplification of
the real world and should be done carefully. One should
consider the ontology behind observed values in the dataset:
race, for example, has varying definitions, each of which
comes with its own assumptions. Further, identifying groups
in the data using a set of observable qualities, whatever those
may be, also carries implicit assumptions about how all the
factors involved interact with each other and the validity of
decomposing them into discrete features
Feng, X.; Li, S.; Yuan, C.; Zeng, P.; and Sun, Y. 2018. Prediction of Slope Stability using Naive Bayes Classifier. KSCE Journal of Civil Engineering, 22(3): 941–950. Foulds, J. R.; Islam, R.; Keya, K. N.; and Pan, S. 2020. An Intersectional Definition of Fairness. In 2020 IEEE 36th International Conference on Data Engineering (ICDE), 1918– 1921. Dallas, Texas, USA: IEEE.
Friedler, S. A.; Scheidegger, C.; and Venkatasubramanian, S. 2016. On the (im)possibility of fairness. CoRR, abs/1609.07236: 16.
Friedler, S. A.; Scheidegger, C.; Venkatasubramanian, S.; Choudhary, S.; Hamilton, E. P.; and Roth, D. 2019. A Comparative Study of Fairness-Enhancing Interventions in Machine Learning. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* ’19, 329–338. New York, NY, USA: Association for Computing Machinery. ISBN 9781450361255.
Hardt, M.; Price, E.; and Srebro, N. 2016. Equality of Opportunity in Supervised Learning. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, 3323–3331. Red Hook, NY, USA: Curran Associates Inc. ISBN 9781510838819.
Heidari, H.; Loi, M.; Gummadi, K. P.; and Krause, A. 2019. A Moral Framework for Understanding Fair ML through Economic Models of Equality of Opportunity. In Proceedings of the Conference on Fairness, Accountability, and Transparency, FAT* ’19, 181–190. New York, NY, USA: Association for Computing Machinery. ISBN 9781450361255.
Hertweck, C.; Heitz, C.; and Loi, M. 2021. On the Moral Justification of Statistical Parity. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’21, 747–757. New York, NY, USA: Association for Computing Machinery. ISBN 9781450383097. Jiang, L. 2011. Random one-dependence estimators. Pattern Recognition Letters, 32(3): 532–539.
Kalev, A.; Dobbin, F.; and Kelly, E. 2006. Best Practices or Best Guesses? Assessing the Efficacy of Corporate Affirmative Action and Diversity Policies. American Sociological Review, 71(4): 589–617.
Kamishima, T.; Akaho, S.; Asoh, H.; and Sakuma, J. 2012. Fairness-Aware Classifier with Prejudice Remover Regularizer. In Flach, P. A.; De Bie, T.; and Cristianini, N., eds., Machine Learning and Knowledge Discovery in Databases, 35– 50. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN 978-3-642-33486-3. Yeom, S.; and Tschantz, M. C. 2021. Avoiding Disparity Amplification under Different Worldviews. In Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’21, 273–283. New York, NY, USA: Association for Computing Machinery. ISBN 9781450383097.
Zafar, M. B.; Valera, I.; Rogriguez, M. G.; and Gummadi, K. P. 2017. Fairness Constraints: Mechanisms for Fair Classification. In Singh, A.; and Zhu, J., eds., Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, 962–970. Ft. Lauderdale, FL, USA: PMLR. Zhao, J.; Wang, T.; Yatskar, M.; Ordonez, V.; and Chang, K. 2017. Men Also Like Shopping: Reducing Gender Bias Amplification using Corpus-level Constraints. CoRR, abs/1707.09457.