Nowadays, machine learning algorithms play increasingly more important roles in decision-making for a broad spectrum of applications, such as applicant screening in job markets, credit risk analysis, and recommendation systems. However, recent studies (Barocas and Selbst 2016;Buolamwini and Gebru 2018;Dressel and Farid 2018) have discovered that machine learning algorithms tend to make discriminatory decisions. For example, a dataset may contain records of physicians most of whom are male. As a result, a job screening algorithm trained on this dataset may unfairly predict if a person is suitable for a physician position based on their gender, instead of education background or professional experience. Obviously, such favorable prediction for male applicants is unfair to female applicants.
Formally, the algorithmic fairness issue refers to the phenomenon that machine learning algorithms make discriminatory decisions across different demographic subgroups and give favorable predictions for some particular subgroups. Intuitively, discriminatory decisions are associated with some demographic features contained in the data, such as age, gender, and race. These features are referred to as sensitive features. Ideally, a fair model should be able to make decisions independent of sensitive features. Towards this end, different fairness notions (Pedreshi, Ruggieri, and Turini 2008;Dwork et al. 2011;Hardt, Price, and Srebro 2016; Chouldechova and Roth 2020) have been proposed. Among them, Demographic Parity (DP) (Pedreshi, Ruggieri, and Turini 2008) and Equalized Opportunity (EOp) (Hardt, Price, and Srebro 2016) are two of the most widely-used definitions. DP requires a model's decision to be independent of sensitive features, achieving a population-level fairness (Edwards and Storkey 2015; Madras et al. 2018;Creager et al. 2019). However, Dwork et al. (2011) showed that such population level fairness does not necessarily guarantee fairness in all label groups. To address this limitation, Hardt, Price, and Srebro (2016) proposed to take label information into consideration and defined EOp and its stronger version Equalized Odds (EO). Specifically, EOp requires the decision to be independent of sensitive features conditionally in the label group receiving an favorable outcome (Hardt, Price, and Srebro 2016). Examples of favorable outcomes include "being admitted to a position" in job screening, and "approval of credit card application". For brevity, we refer to the label group in which each individual receives the favorable outcome as the advantaged group. With a more restrictive fairness definition, EO further requires that the decision is independent of sensitive features in each label group, including not only the advantaged group but also the groups receiving other outcomes.
Some methods have been proposed based on the aforementioned fairness definitions. However, they are focused only on scenarios where each instance is associated with a single target label (Hardt, Price, and Srebro 2016;Woodworth et al. 2017;Zafar et al. 2017). In many real-world applications, multiple labels need to be predicted for an instance. For example, in job screening, an applicant may apply for multiple positions, and the admission decision of each position is a target label of the applicant. Similarly, undergraduates usually submit applications to multiple programs when applying to graduate schools, and thus associate themselves with multiple target labels of admission. Scenarios where each instance is associated with more than one target labels are termed as multi-label classification (Zhang and Zhou 2014). Obviously, fairness concerns also exist in multi-label classification scenarios. One straightforward approach toward fairness in a multi-label scenario is to decompose multi-label classification into multiple binary classification tasks, each of which judges whether a label is associated with an instance or not, and then apply existing fairness metric separately on each binary classification task (Zhang et al. 2018). However, this naive approach ignores one unique property of multi-label classification, i.e., the correlations among labels. Again, take job screening as an example. Applicants usually apply for positions with similar requirements of skill sets and experiences at the same time, and thus the application outcomes (labels) are correlated. Ignoring such correlations among labels would lead to unsatisfactory classification and let alone fairness results. On the other hand, existing multi-label classification methods consider the correlations among labels but cannot enforce fairness in the predictions.
Therefore, it is critical to define fairness directly in the context of multi-label classification. Unfortunately, we did not find existing work along this direction. This motivates us to study this problem. In a multi-label scenario, since different target labels usually occur together, it is more natural to treat their combinations as an advantaged outcome (label). For example, the advantaged group in the job screening example with two possible positions can be the applicants who "received offers of position A and position B". Note that this definition allows us to define more general and complex advantaged groups by specifying more than one favorable labels and requires fairness on all of them.
In practice, the discussed fairness objective is usually achieved by incorporating some fairness notions into optimization (Mohler et al. 2018;Scutari, Panero, and Proissl 2021). Such an optimization is non-trivial when tackling fairness issue based on this extended concept of advantaged group in multi-label classification, where collected data is usually not evenly distributed among different labels (Dekel and Shamir 2010). When few instances are in the advantaged group (i.e., the group that has the favorable label), it may introduce unreliable fairness constraints into optimization and degrade the fairness performance. In this work, we show that the aforementioned optimization challenges can be alleviated by utilizing information sharing among labels. Intuitively, we group data with different but similar labels to alleviate data shortage issue, and then enable an EOp-like framework to incorporate fairness constraints on advantaged groups.This will be formalized in Section . We refer to our framework as Similarity s-induced Fairness (s γ -SimFair), highlighting the crucial requirement of a similarity measure between different labels in the data grouping step.
The proposed framework s γ -SimFair is principled in the sense that it unifies DP and EOp, bringing the flexibility of leveraging a population level fairness or fairness on some particular label groups (e.g., the advantaged group) per desires. The DP and EOp are two extreme cases of s γ -SimFair. When treating all labels as equally similar and ignoring their differences, we end up with one label group of data, in which s γ -SimFair becomes DP. On the contrary, if two labels are similar only if they are the same, then each label group involves only one label, in which s γ -SimFair becomes EOp. Moreover, s γ -SimFair is able to enforce a restrictive fairness notion on the advantaged group even when data is inadequate by utilizing information from other similar label groups.
Our main contributions are summarized below.
• To the best of our knowledge, we are the first to investigate fairness in a multi-label classification setting. We extend DP and EOp to the multi-label classification setting, and recognize the challenge of achieving EOp based on both theoretical and empirical studies.
• To handle the recognized challenge, we propose a novel framework, namely s γ -SimFair, to achieve the fairness objective for multi-label classification even when imbalanced label distributions exist. We further support the proposed framework with rigorous theoretical analysis.
• The comprehensive experiments show that the proposed framework s γ -SimFair is able to achieve competitive and even better performance in term of DP and EOp compared to that of directly incorporating DP and EOp into optimization respectively.
Most existing fairness definitions fall into two categories: group fairness (Pedreshi, Ruggieri, and Turini 2008;Dwork et al. 2011;Hardt, Price, and Srebro 2016;Chouldechova and Roth 2020) and individual fairness (Dwork et al. 2011).
Group fairness requires that the probability of being assigned to a group by a model is independent of sensitive features such as gender, age and race. For example, Demographic Parity (DP) requires that the prediction is independent of sensitive features, while Equalized Odds (EO) and Equalized Opportunity (EOp) require that the prediction is conditionally independent of sensitive features in each or some label group. When labels are binary, this is equivalent to requiring an equality of true and false positive rates across different demographic subgroups. Modifications of DP and EO (EOp) have also been studied. For example, in Pleiss et al. (2017), a relaxed condition is required by replacing EO with some calibration. Individual fairness, on the other hand, requires that a model treats similar individuals similarly (Dwork et al. 2011). In this work we focus on group fairness.
In order to correct the unfairness of models, many methods have also been proposed, which can be classified into one of the following three categories: pre-processing biased datasets, in-processing models during training, and post-processing the outputs of models. In-processing is usually the most effective way to intervene an unfair model (Petersen et al. 2021), which can be done by penalizing unfair predictions directly (Mohler et al. 2018;Scutari, Panero, and Proissl 2021), or by disentangling some intermediate representations (on which final predictions are made) from sensitive features (Locatello et al. 2019;Creager et al. 2019). Nevertheless, penalty-based methods are still good and effective starting points to mitigate unfairness (Mary, Calauzenes, and El Karoui 2019;Kamishima et al. 2012).
Multi-label classification is a general family of classification tasks where each instance is associated with multiple target labels. This task has very broad applications (El Kafrawy, Mausad, and Esmail 2015), such as recommendation systems (Zheng, Mobasher, and Burke 2014;Zhang et al. 2020), multi-object detection (Gong et al. 2019;Zhao et al. 2020), and text classification (Yang et al. 2009;Nam et al. 2014).
Methods for multi-label classification can be grouped into two categories (Zhang and Zhou 2014;Tsoumakas, Katakis, and Vlahavas 2006): problem transformation and algorithm adaptation. Problem transformation tackles multi-label classification by transforming the task into other well-defined tasks. One possible transformation is binary relevance (Boutell et al. 2004), which ignores all dependencies among different targets and predicts each target separately. Classifier chain, the other extreme case, learns the joint distribution of different labels by applying the chain rule of probability (Read et al. 2011). In summary, these problem transformation multi-label classification tasks into other well-established learning problems and adopt existing methods to solve them (Tsoumakas and Vlahavas 2007;Fürnkranz et al. 2008). Algorithm adaptation, on the other hand, modify existing algorithms such as kNN (Zhang and Zhou 2007) and decision tree (Clare and King 2001) to model multi-label data directly. We refer readers to Zhang and Zhou (2014); Tsoumakas, Katakis, and Vlahavas (2006) for more details.
Deep learning has advanced multi-label classification as well (Liu et al. 2021). Recently, Chen, Xue, and Gomes (2018); Bai, Kong, and Gomes (2020) revisited the Multivariate Probit (MP) model (Chib and Greenberg 1998) with the equipment of deep learning tools. MP model assumes that the joint distribution of labels is controlled by a multivariate Gaussian random variable, and the probability of a label is determined by the cumulative density function (CDF) at the value of this Gaussian variable. The correlations in the Gaussian variable allows the model to capture pairwise dependencies in a multi-label setting. Chen, Xue, and Gomes (2018) parameterized the MP model with a deep neural network resulting in the deep Multivariate Probit model (DMVP), and Bai, Kong, and Gomes (2020) proposed to combine DMVP and variational autoencoder (Kingma and Welling 2014) to obtain better performance.
In this section, we propose s γ -SimFair, a flexible framework to unify Demographic Parity (DP) and Equalized Opportunity (EOp). We start with deriving DP and EOp in multi-label scenarios. Then we provide a systematic study on the challenges of estimating EOp in multi-label scenarios. We propose s γ -SimFair based on the these studies to achieve the fairness objective even when imbalanced label distributions exist.
Notations Throughout this paper, we use bold capital letters (e.g., X) to denote matrices, bold lowercase letters (e.g., x) to denote (column) vectors, and calligraphic letters (e.g., X ) to denote spaces. Finally, capital P denotes a probability and lowercase p denotes a distribution. We summarize notations used in this paper in appendixfoot_1 for better readability.
Consider a dataset that contains N samples D = {(x (i) , a (i) , y (i) )} N i=1 . Without loss of generality, we assume each sample is associated with M non-sensitive features x (i) ∈ X = R M , a K-way scalar sensitive feature a (i) ∈ A = {1, . . . , K} where K is the number of demographic subgroups (e.g., K = 2 if gender is the sensitive feature that takes female and male), and L binary labels y (i) ∈ Y = {0, 1} L . We further assume N samples are drawn from an unknown underlying distribution p over space (X × A × Y), and use (x, a, y) ∼ p to denote a random sample. To avoid ambiguity, for y = (y 1 , . . . , y L ), we call y a label, and y l ∈ {0, 1} the l-th target, where y l = 1 indicates the presence of l-th target. We use h : X → Y to denote a multi-label classifier that predicts label based on non-sensitive features. Under these settings, L = 1 corresponds to single-label classification, and L > 1 corresponds to multi-label classification.
In particular, a classifier first predicts ỹ = g(x), the probability of the presence of L targets given x. Then l-th target prediction is given by ŷl = 1(ỹ l ≥ 0.5) elementwisely, in which f denotes this elementwise thresholding function. This family of classifiers is capable of capturing dependencies between different targets by predicting ỹ given x jointly as shown in Chen, Xue, and Gomes (2018); Bai, Kong, and Gomes (2020).
DP and EOp Condition In this section, we establish DP and EOp condition in multi-label scenarios. For classifier h = f • g : X → Y and random sample (x, a, y) ∼ p, h is fair in terms of (1) DP if ŷ ⊥ a; and (2) EOp if ŷ ⊥ a | y adv , where y adv ∈ Y denotes some advantaged label where only favorable outcomes (e.g., "received offer" in the job screening example) present. In essence, DP requires predictions to be independent with sensitive variables, and EOp requires conditional independence to hold on label y adv . As assumed, prediction ŷ depends on predicted probability ỹ elmentwisely, therefore distribution of ŷ is fully parameterized by ỹ. Proposition 0.1 gives a condition for DP and EOp to hold in multilabel classification. Proposition 0.1 (DP and EOp condition for multi-label classifier). For a multi-label classifier that takes the form h = f • g, where ỹ = g(x) is the predicted probability and ŷ = f (ỹ) is computed elementwisely, DP and EOp hold if for any k ∈ A
Proof. See appendix.
Remark 1. Proposition 0.1 indicates that on multi-label data where labels are correlated, for classifier h, we can still evaluate its fairness performances in the same way as evaluating traditional single label classifiers by comparing the averaged predicted probability on different subgroups. Moreover, we can construct estimations with finite samples
Estimation Challenge of EOp In multi-label scenarios, a long-tailed phenomenon, i.e., most labels only associate with few samples (Dekel and Shamir 2010), brings additional challenges for EOp estimation. Without sufficient samples, EOp is barely able to construct reliable estimates for fairness and correspondingly may not achieve fairness objective in an in-processing framework on such datasets. Mathematically, the challenge of estimating EOp stems from terms 2) and (3). When these summations are close to 0, the two estimates are unstable or even undefined. More formally, the conditional expectation in eqn ( 1) is This implies
Henceforth, eqn ( 1) is equivalent to
for ∀ k ∈ A. If 1(y = y adv ) = 1 happens with low probability, i.e., few samples are from label group y adv , EOp is difficult and even impossible to estimate from eqn (2) and (3) directly.
Similarity s-Induced Fairness (s γ -SimFair) For any random sample (x, a, y), fairness of its prediction is always taken in consideration, but as the affinity of y to y adv decreases, it will be down-weighted when estimating fairness violations with respect to y adv . Definition 1 (s γ -SimFair). Given a similarity function s :
Same as DP and EOp, terms involved in eqn ( 7) can be estimated with
In this paper, we adopt the Jaccard score to define similarity s. In essence, we use the cardinality ratio between the intersection and union of pair (y, y ) to measure their similarity, then apply some monotonic transformation for scaling. Formally, for y ∈ Y with y l = 1 represents the presence of the l-th target, we denote cate(y) = {l : y l = 1, l = 1, . . . , L}, i.e., the collection of indices of present targets, and define Jac(y,
where γ is a scaling parameter. It is worth mentioning that the choice of s is not unique and can be task-or data-specific.
One key characteristic of s γ -SimFair is that it can be seen as an unification of DP and EOp, as formalized by Proposition 0.2 and 0.3. Proposition 0.2 (DP and EOp are special cases of s γ -SimFair). Consider s γ -SimFair defined in eqn (7), if similarity s is a constant function s(y, y ) = c for some c, then s γ -SimFair implies DP; if s is an indicator function s(y, y ) = 1(y = y ), then s γ -SimFair implies EOp.
Proof. See appendix.
Proposition 0.3 (s γ -SimFair helps achieve DP and EOp). For any multi-label classifier h satisfying s γ -SimFair, its violation of DP will be arbitrarily small if γ is sufficiently small; and its violation of EOp will be arbitrarily small if γ is sufficiently large. More generally, its violation of DP is arbitrarily close to its violation of s γ -SimFair for sufficiently small γ, and its violation of EOp is arbitrarily close to its violation of s γ -SimFair for sufficiently large γ.
Proof. See appendix.
Remark 2. Proposition 0.2 reveals the connection between s γ -SimFair and DP (EOp). Proposition 0.3 further shows that s γ -SimFair condition indeed helps achieve DP and EOp, establishing a theoretical foundation of borrowing information from similar labels.
Datasets Due to the lack of existing work in fairness-aware multi-label classification, we transform two tabular datasets that are ubiquitous in fairness literature into multi-label settings. Towards this goal, we select some features and treat them as additional targets. To help focus on the challenge brought by multi-label, we use binary sensitive features, but as defined in eqn (3), our methods can easily generalize to where more complicated sensitive features are usedfoot_2 .
• Adult (Kohavi 1996) is a widely-used fairness dataset from UCI repository that contains 48,842 samples. Original Adult dataset contains 112 features and a binary label income level, which denotes whether an individual's yearly income is greater than $50K dollars or not. We further use workclass and occupation as two other targets. In terms of sensitive features, we follow Reddy et al. (2021) and binarize age into 25-44 years old and else. This allows us to construct two balanced demographic subgroups. • Credit (Yeh and Lien 2009) is another popular fairness dataset from UCI repository. It contains 30,000 samples, each sample is associated with 24 features and a binary label indicates the existence of default payments. We treat education level as an additional target, and use gender as the sensitive feature.
Baselines We compare MPVAE h trained with proposed s γ -SimFair regularizer with three baseline methods: ( 1 macro-averaged F1 (macro-F1), and example-averaged F1 (example-F1) as defined below
.
These metrics compute either F1-score over the label matrix or averaged F1-score over targets or samples. Implementation Details For s γ -SimFair, we use γ = 1, 5, 10 to illustrate when it approximates DP or EOp. We also vary λ, the coefficient of fairness loss sγ (y,y adv ) (h), from 1 to 5000 to study the trade-off between fairness and accuracy (in terms of micro-, macro-, and example-F1). We randomly choose 70% data for training and 30% for testing. Other hyperparameters for MPVAE training such as batch size, epochs, and learning rates are fixed throughout all experiments. A full list of hyperparameters used in this paper is provided in appendix.
We first evaluate how well s γ -SimFair can approximate DP and EOp to answer RQ1. To do so, we train a MPVAE without any regularizers for 20 epochs on Adult and Credit datasets and evaluate how it violates DP and EOp. We choose the largest label group (i.e., the label that appears most frequent) as the advantaged group. This allows us to construct a reliable estimate of EOp, which could be used as the ground truth.
Figure 2 shows how fairness violations estimated by s γ -SimFair change under different γ, with DP and EOp marked on the left and right y-axis. From the figure, the starting points of s γ -SimFair curves at γ = 0.1 locate close to DP, and the ending points at γ = 10 are close to EOp; these observations justify the effectiveness of s γ -SimFair in approximating DP and EOp, consistent with theoretical analysis.
Next, we study the robustness of three estimators by varying the numbers of samples in the advantaged group to different levels and evaluating how estimates of DP and EOp change. Results summarized in Table 1 are averaged over 10 independent replications. Empirically, EOp estimator degrades drastically as the size of observed advantaged group decreases. s γ -SimFair with large γ(= 5), in contrary, produces more stable EOp estimates when EOp estimator fails. In terms of DP, both its own and s γ -SimFair estimator produce similarly stable results, which is reasonable as we only decrease the size of the advantaged group.
After showing that s γ -SimFair can approximate DP and EOp well, we evaluate how well it can help achieve DP and EOp.
We start with reporting fairness violations of MPVAE trained with DP, EOp, and s γ -SimFair regularizers. On each dataset, two potential advantaged groups are considered. The first group is the largest label group as in the last subsection, and the second group is chosen to be a small label group but we can still estimate EOp on the test set. For Adult dataset, since it has more labels, we choose the 18-th largest label group, which is the smallest one that has more than 100 test samples from the advantaged group out of 152 possible labels. For Credit dataset, we choose the 9-th largest, this group has at least 10 test samples from the advantaged label out of 13 possible labels. Throughout experiments, we fix λ = 10 and run 10 replications to smooth out randomness.
Table 2 shows resultant DP and EOp achieved by different methods. In all experiments, s γ -SimFair performs competitive to DP regularizer and better than EOp regularizer in terms of minimizing these metrics as objectives. Notably, when the advantaged group is small, the vanilla EOp regularizer mitigates EOp violation poorly, but s γ -SimFair still reduces it significantly. Moreover, s γ -SimFair maintains a better DP-EOp balance, even they are known to be incompatible (Barocas, Hardt, and Narayanan 2017). For example, s 1 -SF regularzier helps achieve better DP and EOp simultaneously than a DP regularizer on the largest label group on Adult dataset. We interpret this observation as a byproduct of the biased estimation given by s γ -SimFair. As s γ -SimFair is biased towards DP (EOp) when estimating EOp (DP), such bias implicitly considers the other metric and hence strikes a batter balance. These results clearly establish the power of s γ -SimFair in minimizing DP and EOp.
To better reveal the limitation of EOp regularizer, we further evaluate how fair a model can be achieved by the use of different methods. To do so, we choose a large λ = 5000. Note that such large λ, will be shown shortly, significantly impedes accuracy. Here we sacrifice all accuracy to check We run 3 replications on top 18 largest label groups in Adult dataset and top 9 largest label groups in Credit dataset as advantaged group separately 3 . Figure 3 shows resultant DP and EOp achieved by different methods. Compared to EOp regularizer, which performs the worst on all labels, s γ -SimFair is much more stable. In extreme cases, s γ -SimFair, as a good approximation of EOp, also encounter failure ultimately, but it is much more robust.
We end up this section with a study on the tradeoff between fairness and accuracy on the two label groups from the previous section. Hyperparameter λ varies from 1 to 5000 and results are averaged over 10 replications. Due to the page limit, 3 As described above, these groups have sufficient test samples to check violations. regularizer is unstable and ineffective when the advantaged group is small, s γ -SimFair, in contrast, preserves similar tradeoff trend as DP on both large and small label groups.
we only report EOp-accuracy tradeoffs on Credit dataset in Figure 4 here and defer other figures to appendix. Nevertheless, conclusions drawn here apply to all experiments. Overall, micro-and example-F1 are much more robust to fairness requirement than macro-F1. On Credit dataset, they are even improved slightly when a small fairness regularization is added. We hypothesize that fairness regularization indirectly adds smooth conditions and penalizes unstable predictions. s γ -SimFair has similar tradeoff patterns compared with the DP regularizer and does not encounter instability as EOp regularizer does. In addition, on small label groups where EOp regularizer fails, its s γ -SimFair approximation succeeds in achieving low EOp violation, and performs one of the best in handling tradeoffs.
In this paper, We study the important problem of enforcing fairness on multi-label classification. Given the ubiquitous imbalanced issue with respect to label groups, we propose s γ -SimFair, an effective framework that helps achieve existing group fairness metric: DP and EOp. We first establish a formal extension of DP and EOp condition to multi-label scenarios, then prove that (extended) DP and EOp can be exactly expressed by s γ -SimFair, and can be approximated arbitrarily well. Experiments on two real-world datasets echos with theoretical analysis and reveals limitations of EOp regularizer. s γ -SimFair, in contrary, shows strong robustness against the challenges EOp regularizer cannot overcome.
s γ -SimFair is a general tool. The concept and technique derived in this paper can apply to multi-class classification as well, so long as a proper similarity function can be defined in the label space Y. In the future, we plan to further conduct theoretical analysis on s γ -SimFair regularizer and convergence, and apply s γ -SimFair in a post-processing framework.
The Thirty-Seventh AAAI Conference on Artificial Intelligence
https://arxiv.org/abs/2302.09683
See appendix for experiments where a multi-class sensitive feature race is considered.