Group imbalance usually caused by insuficient or unrepresentative data collection procedures, is among the main reasons for the emergence of representation bias in datasets. Representation bias can exist with respect to diferent groups of one or more protected attributes and might lead to prejudicial and discriminatory outcomes toward certain groups of individuals; in case if a learning model is trained on such biased data. In this paper, we propose MASC a data augmentation approach based on afinity clustering of existing data in similar datasets. An arbitrary target dataset utilizes protected group instances of other neighboring datasets that locate in the same cluster, in order to balance out the cardinality of its nonprotected and protected groups. To form clusters where datasets can share instances for protected-group augmentation, an afinity clustering pipeline is developed based on an afinity matrix. The formation of the afinity matrix relies on computing the discrepancy of distributions between each pair of datasets and translating these discrepancies into a symmetric pairwise similarity matrix. Furthermore, a non-parametric spectral clustering is applied to the afinity matrix and the corresponding datasets are categorized into an optimal number of clusters automatically. We perform a step-by-step experiment as a demo of our method to both show the procedure of the proposed data augmentation method and also to evaluate and discuss its performance. In addition, a comparison to other data augmentation methods before and after the augmentations are provided as well as model evaluation performance analysis of each of the competitors compared to our method. In our experiments, bias is measured in a non-binary protected attribute setup w.r.t. racial groups distribution for two separate minority groups in comparison with the majority group before and after debiasing. Empirical results imply that our method of augmenting dataset biases using real (genuine) data from similar contexts can efectively debias the target datasets comparably to existing data augmentation strategies.
Recent years have brought extraordinary advances in the field of Artificial Intelligence (AI) such
that now AI-based technologies replace humans at many critical decision points, such as who
will get a loan [
One of the leading causes of unfair automated decisions in many real-world scenarios is due to unrepresentative, insuficient, or biased data fed to the learning algorithm [ 4]. Consequently, such biases can lead to certain discriminatory and prejudicial decisions harming sensitive groups e.g. racial/gender minorities in practice. To overcome this issue, in this paper, we propose a mechanism for Minority Augmentation of biased datasets coming from separate but similar sources of data (described in the same feature space) through a Spectral Clustering scheme (MASC). The method proposes a way to augment underrepresented minority groups of an arbitrary task (hereafter we use the terms dataset and task interchangeably) by increasing their instances from a subset of contextually similar datasets that belong to the same cluster. Our proposed method performs an afinity clustering based on distribution discrepancy (that is used as a distance measure) among tasks to group similar tasks into a pre-defined number of clusters. Within each cluster, any member dataset can use instances shared by neighboring (mutually most similar) tasks to augment their underrepresented groups as compensation for group cardinality diference (that leads to representation and imbalance bias) according to a protected attribute.
Our main contributions can be summarized as follows: • A new data augmentation framework for data debiasing towards statistical balancing between non-protected and protected group(s) based on most similar neighbors. • Utilizing distribution shift metrics to quantify pairwise discrepancy between diferent datasets/ joint distributions • A spectral clustering framework to group similar datasets based on the discrepancy between the joint distribution of these datastes. • Clustering into an optimal number of clusters using a graph theoretic heuristic, known as ”Eigen-gap or Spectral-gap“ to avoid parameter selection and thus avoid any additional bias in the pipeline.
are presented in Section 2. In Section 3, we present the proposed data augmentation pipeline. Experimental evaluation results are provided in Section 4, including an intuitive example of applying the proposed method. Finally, Section 5 concludes this work, discusses its limitations and points out to future directions.
In this section, the necessary theoretical background and a brief literature review of these necessary notions are discussed.
Distribution shift [ 5] is a broad topic studying how test data can difer from training data and how would such diferences afect model performance. There are several possible causes for dataset shift, out of which two are deemed to be the most important reasons: Sample selection bias and non-stationary environments according to [6]. The motivation for referring to notions of data distribution shift in our paper is to utilize measures of distribution shift that provide practical tools as well as rich theoretical backgrounds that enable us to quantify similarity (and/or distance) among pairs of datasets that we will later use for data debiasing. Next, we look at formal definitions and diferent types of distribution shifts.
If we consider a dataset ( , ) to be a set of independent and identically distributed (...) set of instances drawn randomly from an unknown continuous probability density function, then a classification problem is defined by a joint distribution ( , ) of features a.k.a. covariates and target variables [6]. According to the Bayesian Decision Theory [7], a classification can be described either by the prior probabilities of the classes ( ) and the class conditional probability density functions ( | ) covariate probabilities ( ) distribution ( , ) for all classes = 1, … ,
where c is the number of classes or by the and conditional probability density functions ( | ) . Thus the joint can be decomposed in both following forms: ( ) ( | )
( ) ( | ) = , ( | ) =
∑ =1 ( ) ( | )
( ) ( ) ( | ) where ( ) =
∑ =1 ( ) ( | )
and similarly ( ) = classification problems respectively. The two forms of problem formulation will be formalized as → and →
(pronounced as Y given X ) respectively in the rest of this paper.
The literature on distribution shift detection and adaptive learning domain indicates that there in ( | ) and ( | ) are three types of distribution shifts [ 8, 9]: ( ) target labels ( | ) known as “virtual shifts”. 1. Covariate shift appears only in →
problems when the probability of input features changes, but the decision boundary defining the relationship between covariates and remains the same. In other words, the distribution of the input changes, but the conditional probability of a label given an input remains the same. These shifts are 2. Prior probability or target shift appears only in → problems when the probability of target labels ( ) changes but ( | )
remains the same. For example, consider the case when the output distribution changes but for a given output, the input distribution stays the same. type → → 3. Concept drift basically can appear in both types of problems namely in problems of where the probability of ( | )
changes between train and test data or in problems where ( | )
changes. Concept drift happens when the input distribution remains the same between the two datasets but the conditional distribution of the output given an input changes. In other words, the decision boundary defining the relationship between covariates and labels changes.
We are interested in measuring distribution discrepancy between two datasets ∈ ℝ× , and ∈ ℝ×
defined over the same feature space of features and having an arbitrary size of input samples. Discrepancy between two datasets can be due to diferences in their feature and label distributions, so the conditional probability of labels given an input can remain the same. Since our goal is to develop a method to cluster similar distributions to enable us to augment a test dataset and also for the sake of maintaining the generality of the problem, we assume we don’t have access to target labels and thus do not use prior probability information for shift quantification. As a result, we only use covariate distribution similarities. Moreover, we assume the similarity of the attribute space between diferent tasks; meaning that all the datasets have the same number of feature with the same range of values.
Leibler (KL for short) distance [10]. KL has nice theoretical properties, but it is not considered a metric as it is not symmetric ( (P, Q) ≠ (
sets and respectively) and it does not satisfy the triangle inequality [8]. A modified version of KL-divergence which belongs to a symmetrized sub-category of KL-divergence is the JensenShannon divergence [11] which is a metric but still, as with all measures based on KL-divergence, it is sensitive to the sample size and requires both datasets to have the same cardinality.
Maximum Mean Discrepancy (MMD for short) [12]. It is a multi-variate non-parametric statistic calculating the maximum deviation in the expectation of a function evaluated on each of the random variables, taken over a reproducing kernel Hilbert space (RKHS). MMD can equivalently be written as the L2-norm of the diference between distribution mean feature embeddings in the RKHS. In contrast to KL-Divergence, MMD is not sensitive to the number of instances and can be highly scalable to any arbitrary number of instances for each of the distributions depending on the kernel function employed for its calculation.
( , ) = ‖ − ‖ℋ 2
Where is the kernel mean of estimated using (( )) = is kernel mean of assuming ∶
→ ℋ to be a feature map embedding to the embedding Hilbert space ℋ. Then Eq. 1 can be substituted as: 1 ∑=1 ( ) and similarly ( , ) = ‖ ∑ ( ) −
∑ ( ) ‖ 1 =1 1 =1 2 ℋ
The inner product (indicated by ⟨ • ⟩ ) of feature means of ∼ and ∼ can be written in terms of the kernel function such that:
ℋ ⟨ ( ( )), ( ( )) ⟩ = , [ ⟨ ( ), ( )⟩ ] = , [ ( , ( , ) = ∑ ∑ ( , ) − 2
∑ ∑ ( , ) +
1 ( − 1) ≠ ∑ ∑ ( , ) (1) (2) (3) (4) (5) Substituting Eq. 3 into Eq. 1 we can rewrite it such that: ( , ) = [ ( , ) ] − 2 , [ ( , ) ] + [ ( , ) ]
. 1 ℋ
method is described in 4 steps. A procedural overview of each of these steps of the proposed data augmentation method is provided in Algorithm 1. Before approaching these steps with details, an overall overview of the process is discussed in the following.
Assume having number of biased datasets = { 1 ∪ 2 ∪…∪ } according to diferent tasks.
or be from civil registration ofices in diferent cities (or states) and many other similar cases.
Input: — Set of all tasks; Output: ̂ — Minority-augmented (debiased) target task — Index of target task ; ▷ = ⋃ , ∈ {1, … , } ⇒ ⊂ 2 3 4 5 6 7 8 9 1 for ← 0 to do for ← 0 to do (, ) ← ( if ≠ then else end end
, ) ; ( , ) ← (− ‖ − ‖ ) ;
2 ( , ) ← 0 ; 10 end 11 ← − : where , ← 12 ← Σ ; 13 ← [ 2 − 1, 3 − 2, … , − −1 ];
∑
=1 , ; 15 ∈ ℝ× ← [ 1, … , ] =∧ min ;
1… ⋮ ⋮ ⋮ ⋮ 16 ← ( )
; 18 for ← 1 to do
| | ← ; 19 20 end 21 ← 22 if > then 23 25 24 else 26 end ̂ ← ∪ ̂ ← ; ( 1, … , ); ( − ) ⋃ =1 (); =1
▷ = | | ▷ Pairwise MMD: Eq. 5 ▷ Gaussian Kernel: Eq. 6
▷ Zeros on diagonals ▷ Graph Laplacian: Sec 3.2
▷ SVD: Eq 7 ▷ Eigengap vector: Eq 8 ▷ Top eigenvectors: Eq. 9 ▷ Cardinality of majority group ▷ Augment ⊆ in the c-th cluster 14 (optimal number of clusters): apply eigen-gap technique on , is the index of largest gap; ▷ = ( ) = { 1 ∪ … ∪ }, ≤ : Eq. 10 17 ← { 1 ∪ … ∪ }, ≤ & ∈ { 1, … , } ; ▷ Where | | = ∑
=1 = : Eq. 11 ▷ Subgroup cardinality of = , ∑ =1 = : Eq. 12 such that in each cluster, tasks can share their instances. This way, an arbitrary dataset ⊂ that is biased by over-representing a majority1 group w.r.t. a protected attribute, can borrow instances of minority group(s) from its neighboring tasks and construct an augmented unbiased training set. For the clustering procedure, a spectral clustering algorithm is utilized that can identify the optimal number of clusters automatically based on an Eigen-gap or Spectral-gap heuristic introduced in [13]. In order to perform the clustering step, initially we need to construct an afinity matrix from the pairwise distances that we obtain by metric.
each pair of datasets ⊂ and ⊂ using Eq. 5. The distances are then transformed into a symmetric matrix of pairwise distances
∈ ℝ× such that the diagonal of the matrix is all zeros.
Radial Basis Function a.k.a. Gaussian Kernel [13, 14]: ( , ) = { 0,
2 (− ‖ − ‖ ) , if ≠
otherwise = [ 2 − 1, 3 − 2, … , − −1 ] where , is the k-th sorted eigenvalue in ascending order. Note that, if ( − −1 ) implies the largest diference i.e. eigengap according to Eq. 8, then index k is the optimal number of clusters. where and are two entries of the distance matrix . Eq. 6 results in a weighted undirected symmetric afinity matrix with zero diagonal elements with weights being Gaussian functions of the pairwise distances.
In order to perform spectral clustering on the afinity matrix, we need to calculate the unnormalized graph Laplacian [13] = − where , = ∑
=1 , is the diagonal degree matrix of the afinity matrix . Graph Laplacian is key to spectral clustering; its eigenvalues and eigenvectors reveal many properties about the structure of a graph.
According to the ”Perturbation Theory“, an optimal number of clusters k for a dataset can be given through the eigengap identification of eigenvalues of the graph Laplacian, which is the largest diference between eigenvalues [ 15, 16]. Thus, computing the eigenvalues of the Laplacian matrix and finding it’s biggest gap can discover the optimal number of clusters. This way, one can avoid the dificult and tricky decision of the cluster number parameter. Thus, similar to the instructions in step 5 of [17] we perform a ”Singular Value Decomposition (SVD)“ to calculate the eigenvalues of the Laplacian matrix :
= Σ where ,
are unitary matrices called left and right singular matrices, respectively containing eigenvectors corresponding to eigenvalues in Σ. Next, we create an eigengap vector using the eigenvalues from Σ in Eq. 7 as follows: ⋮ ⋮ ⋮ ⋮ = [ 1, … , ] =∧ m1…in
After obtaining
k, the desired number of clusters in Section 3.2, there is one more step to finally be able to partition the afinity matrix. In this step, we find the top k eigenvectors to the top k smallest eigenvalues of the Laplacian, stack them as columns of a new matrix ∈ ℝ× 1, … , according such that: (6) (7) (8) (9) where =∧ stands for the term ”Corresponding to“. Then, a k-means clustering [18] is performed on the rows of matrix which is equivalent to a clustering of the r datasets: = ( ) = { 1 ∪ 2 ∪ … ∪ } and ≤ ≡ and ≡ sign represents the equivalence of its operands. Note that, in practice, spectral clustering is often followed by another clustering algorithm such as k-means to finalize the clustering task. The main property of spectral clustering is to transform the representations of the data points of into the indicator space in which the cluster characteristics become more prominent and passes much more processed/meaningful information to the next step clustering algorithm. (10) (11) (12) (13)
Now that the set of input tasks/datasets is clustered into partitions according to Eq. 10, the data augmentation process for minority group(s) can be fulfilled. If cluster consists of datasets: = { 1 ∪ … ∪ }
where ≤ & ∈ { 1, … , } Initially, we create a pool of instances in the cluster by collecting all the instances from each dataset belonging to the cluster. The number of instances in this cluster | | = , (where | • | denotes cardinality) can be written as a sum of the number of instances belonging to each of the protected groups ∑
=1 = . Given a protected attribute = { 1, … , } with groups and knowing | | = , the augmentation process for task ⊂ is a very straightforward process based on protected groups cardinality. We calculate the cardinality of each group corresponding to the number of instances belonging to that group such that:
| | = for i ∈ { 1, … , } where ∑
=1 = . Next, we identify the biggest group and indicate it as the majority/nonprotected group through a procedure like ( 1, … , ) = . Ideally, the intention would be to balance every minority subgroup to have a cardinality as big as the majority group , so that | ̂ | = . Thus, every protected group needs to be augmented by a diference of − .
However, it is only the case if the pool of shared protected group instances includes this number of instances otherwise we augment by as many instances as there exist in the shared pool. Thus, the augmented version of dataset has the following number of instances depending on the number of shared instances: ̂ ← ⎧ ∪ ⎨ ⎩ ( − ) ⋃ =1 () if > otherwise syntax complication. where
= { | = }. Note that, and are substituted by and respectively, to avoid
experimental results on a number of real-world datasets are analyzed. The organization of this section is as follows: First, details of the datasets employed are presented. Next, the evaluation measures used in the experiments and also methods used for comparisons are described. Finally, the experimental results and discussions on them are provided.
To evaluate MASC’s performance in addressing group imbalance and representation bias, we used the recently released US Census datasets [19], which comprise a reconstruction of the popular Adult dataset [20]. These datasets provide a suitable benchmark with 52 datasets representing diferent states, efectively capturing the problem of group imbalance between states with varying numbers of instances but similar feature spaces.
The datasets [19] include census information on demographics, economics, and working status of US citizens. Spanning over 20 years, they allow research on temporal and spatial distribution shifts and incorporate various sources of statistical bias. As already mentioned in Section 2.2, in this study we assume that the conditional probability of labels given specific inputs remains constant. Therefore, we focus on the latest release, specifically the year 2019 (till the date of submission), and examine the spatial context to explore the connection between covariate shifts and bias.
The feature space consists of 286 features, with only 10 deemed relevant [19]. The target
variable, Income Value, is transformed into a binary vector to predict whether an individual earns
an income of more than 50k: ∈ {≤ 50 , > 50 } , the positive class being ‶ > 50 ″. We
selected “Race” as the protected attribute due to the challenge it poses compared to gender or age,
given the highly imbalanced distribution of racial groups across states. The “Race” attribute has
9 categories, but due to a very small representation of seven of these categories which usually
comprise less than 1% of the instances in the dataset, we aggregate them to a bigger group called
“Other”. Thus, the categories in our experiments are aggregated into 3 groups: White, Black,
and Other. Categorical features are transformed into numerical features and all the features are
normalized by standard scaling using their mean ( ) and standard deviation ( ) values such that
each = ( − )/ is a standard representation of its and lies within the range [
distribution, class imbalance ratio, name abbreviation conventions, and other details. The table summarizes information for 5 out of 51 datasets. The intuition behind this specific selection of states will be addressed in detail in Section 4.4. The datasets exhibit significant racial bias, with the White group representing the majority (also referred to as non-protected) in all 5 datasets.
In this paper, we adopt five measures in total. We use accuracy [
( = 1 | = 0 ) − ( = 1 | = 1 ) Since we consider two protected groups of ”Black“ and ”Other “ in our experiments, the results are calculated for each of the measures twice; for each of the two protected groups against the non-protected group of ”White“. So in our analysis ∈ { 0, 1 , 2 } . SP takes values in the range ∈ (−1, 1)
with 0 as the best possible value implying zero bias.
The measure Equalized Odds (Eq.Odds for short) calculates the diference in prediction errors between the protected and non-protected groups for both classes as | | + | | where stands for ”False Negative Rates“ and
stands for ”False Positive Rates“ that are also known as Equal Opportunity and Predictive Equality respectively. The measures the diference of the probability of subjects from both the protected and non-protected groups that belong to the positive class to have a negative predictive value and similarly, the calculates the diference of the probability of subjects from both the protected and non-protected groups that belong to the negative class to have a positive predictive value. So, the Eq.Odds is formulated as follows: which basically calculates the ratio of the probability of being a member of the protected group having positive outcomes to the probability of the non-protected group with positive outcomes.
The measure statistical parity (SP for short) also computes a quite similar value, where it reflects the mentioned change as a diference instead of a ratio: (14) (15) (16) (17) (18) . = | ( =̂ 0| = 1, = ) − (
=̂ 0| = 1, = /) | ( =̂ 1| = 0, = ) − ( =̂ 1| = 0, = /) | + | where ̂is the predicted label, Y is the actual label and ∈ = { , , } is the protected attribute.
and
is [
essentially calculates group imbalance or the proportion of instances belonging to each of the protected groups or the non-protected group w.r.t. the total number of instances in the dataset. Similar to the definition of protected attribute and its member groups in Section 3.4, the group distribution ratio for a protected group is obtained as follows: = ( | = ) = | | | | = ∑ =1 where the denominator of the fraction in Eq. 18, is the sum of the cardinality of all subgroups of task or the total number of its instances ∑ =1 = . Clearly, the cumulative probability of all subgroups ∑ ( | = ) is = 1. Thus, a dataset is group balanced w.r.t. a protected attribute subgroup in the dataset is given by group distribution ratio would be subgroups
∗ = 1/3.
if Eq. 18 is proportionately equal for each subgroup. In other words, the optimal balance for each same number of instances. As a result, for a protected attribute with two subgroups, the optimal ∗ = 1/(∑=1 ) which implies balanced groups with the ∗ = 1/2 and similarly for a protected attribute with three In order to compare the results of our MASC augmentation method, we compare it with 4 diferent competitors including the original shape of untouched datasets along with three other strategies. Specifically, we use a variation of
group over-sampling instead of minority class augmenting, and similarly we use a variation of RUS [24], as a random group under-sampling. In addition, we also introduce a natural geographical neighborhood augmentation by concatenating datasets within their local clusters of geographical neighbors based on the formal region categorization as in [25]. All the augmentation methods are also analyzed by feeding their outputs to a Logistic Regression classifier (LR for short).
protected group distribution of the protected attribute such that: for SMOTE we over-sample both minority groups until their cardinality is as large as the majority group. For the RUS method, we under-sample the majority group and the bigger minority group until they contain as few samples as the smallest minority group.
The forthcoming experiments in this section are conducted in order to compare the initial dataset biases of the original datasets before and after the proposed data augmentation and also in comparison with the three other augmentation strategies, respectively as mentioned in section 4.3 based on the introduced measures in Section 4.2. Following that, we also compare predictive performance and fairness of a LR classifier on the diferent augmentation strategies to see how would each of the augmentation methods afect model performance 2 . Meanwhile, to get an intuition about the step-wise procedure of the proposed MASC method, a demonstration of implementation on the aforementioned US-Census datasets, following the steps in Section 3 is illustrated before discussing performance results. 4.4.1. A Demo implementation Initially, an afinity matrix according to steps 1-9 of Algorithm 1 is generated. Following that, based on instructions in lines 11-12 of Algorithm 1, initially a graph Laplacian and afterward its SVD decomposition are calculated from the afinity matrix, in order to obtain eigenvalues of the Laplacian and find the spectral eigengap as in steps 13-14. According to the spectral graph theory [26], in an ultimately well-shaped problem, one can observe that there exists an ideal case of k completely disconnected components which constitute a block diagonal Laplacian matrix that has k zero eigenvalues and corresponding k eigenvectors of ones. In this extreme case, the (k+1)-th eigenvector which is non-zero, has a strict gap. This gap identifies the optimal number of connected components that can be clustered as highly similar objects. The eigengap heuristic is an advanced guide to avoid parameter selection, although our problem as well as the majority of real-world problems do not produce such a well-formed block diagonal Laplacian. In Figure 1a the first ten eigenvalues and the major eigengap are demonstrated. It depicts that our datasets can be semi-optimally clustered into five categories.
2The source code of the proposed MASC and the comparisons can be found at: Github/SiamakGhodsi/MASC (a) The largest eigen-gap
(b) States data clustering shown as a 5-nn graph for legibility
4.4.2. Results The MASC is applied to all the input datasets and augments each task based on the cluster that they belong to and therefore the neighborhood instances that they share. Since the method indicates 5 clusters as depicted in Figure 1b, for the sake of readability we evaluate the results for 5 of the datasets, each chosen from one of the clusters. Namely, the states are; Montana (MT), Mississippi (MS), North-Dakota (ND), Colorado (CO), and Maryland (MD). The selection of states within each cluster is based on diversity; we chose states from western and more central regions to northern and east-most states that allow comparing population texture of diferent regions of the US according to [25].
In Figure 2a the GR values according to the distribution of each of the original datasets is shown. Comparing them to distributions in Figure 2b which is the results obtained by our method, the performance of our method in reducing the group diferences is inferable. The proposed method borrows similar instances for each minority group from similar states and balances exactly perfectly four of the states and to a very good extent also the Colorado state. In Colorado’s case, the number of minority group instances borrowed from other states in the cluster is not enough to equalize the representation of minority groups, but still decreases the worst imbalance in the original dataset in terms of diference between GR-values of Maj-min1 from 87.98% − 2.56% ≈ 85% to 49.16% − 26.13% ≈ 23% and reduces the 85% diference to 23%.
Table 2 summarizes the evaluation of the five datasets based on previously introduced measures DI, SP, GR (refer to Section 4.2 for details) comparing the results of original states with (a) (b)
MASC, Geographical-neighborhood grouping, the SMOTE, and the RUS methods. Note that the Geographical-neighborhood augmentation is abbreviated as Geo-nei in the table. The Maj, Min1, and Min2 notations correspond to Majority (White) and two minority groups (Black and Other ), respectively. It is empirically shown in the table that the results of the MASC, alleviate group imbalance to a good extent for all the datasets according to the GR column and subsequently achieve good DI and SP rates compared to the original datasets. Moreover, in comparison to Geonei, our method performs better for all the states except for the Min1 group in the Colorado state and still achieves much better balances for the protected groups but only the class distribution is slightly worse. Compared to SMOTE and RUS, our method performs comparably well in terms of GR-values but w.r.t. DI and SP metrics, the method reports slightly worse results that is because our method only balances out group distributions and doesn’t take into account the distribution of target-class. However, in model performance, our method outperforms the SMOTE and RUS for all the states w.r.t. accuracy and eq.odds metrics that we will see in the followings. Also, there are some technical issues/limitations that may arise using the SMOTE and RUS methods which will be discussed more detail in Section 4.5.
and tested on the corresponding are illustrated. Note that, there are two legends where the ifrst one represents the three augmentations (including our method MASC) that are based on real (genuine) data and the other represents synthetic augmentation methods. In Figure 3a the Eq.Odds values are shown where we can see the purple bar, representing our method MASC gets the best results for three states Montana, Mississippi, and North-Dakota as well as standing in the third best for two other states Colorado, and Maryland. Interesting observation comparing to results in Table 2 where SMOTE and RUS had better DI and SP results, it is observed that in model performance analysis, along with Geographical neighbors our method outperforms the SMOTE and RUS in all the states (Except for Mississippi where Geographical neighbors augmentations stands slighly worse than RUS) for both the metrics, accuracy and eq.odds. In Figure 3b where the accuracy results are compared, again the same situation is observed where MASC outperforms RUS and SMOTE and has the best accuracy in four of the states Montana, North-Dakota, Colorado, and Maryland and also stands in the third best for Mississippi.
From an analytical perspective although our method MASC seems to stand statistically comparable to or lower than the SMOTE and RUS in terms of DI and SP in Table 2, but it outperforms both these methods in model performance results reported in Figure 3. The reason for the former is because in our experiments, we implement a version of SMOTE and RUS that statistically (a) Equalized odds of each method on each of the five states (b) Accuracy of each method on each of the five states augment protected groups, but still w.r.t. model performance measures, their augmentation is not comparable to real-world (genuine) data augmentations (e.g. MASC and Geographical neighbors). In that case, in Figure 3a and Figure 3b it is observed that MASC and Geographical neighbors (except for one case) outperform in all cases the two synthetic augmentations and once more we can highlight the importance/diference of real-world (genuine) data augmentation compared to synthetic/generated data.
group imbalance augmentation. Starting with RUS: looking at Figure 2a only 0.36%, 1.35% of the population belong to the minority group1 (Black) of the states Montana and North-Dakota, respectively. For the cleaned dataset it is no more than 20, and 60 instances each. So, with such a small number of instances, it is very unlikely for any learning algorithm to produce reliable predictions while being imposed to test data. This was also observed in Figure 3b where the Eq.Odds results of the RUS method always report one because it basically predicts all the undersampled data to belong to the majority class. Subsequently, this lack of reliable performance might even get worse in cases where learning parameters are applied to out-of-distribution (OOD) data. An example of OOD is training on the augmented data (in our experiments are 2019 US-Census dataset) and then applying the model for future data, e.g. 2020, and later data of the same state. This is left as an open question to interested readers to test and analyze the results. Furthermore, another question is: what about inter-sectional groups when there is imbalance also w.r.t. more than one attribute; for example how would SMOTE and RUS perform if gender and ethnicity are studied simultaneously? For example, if only exists one instance of coloured-skin females within the 20 samples in Montana dataset, the algorithm will only learn to infer one class label among these group of instances which could lead to highly unreliable and deficient predictions on test data.
In case of SMOTE, it over-samples the minority group of 20 or 60 instances to generate hundreds of times more data. So, these synthetically generated data are only specifically applicable to this application because they need to be very carefully tailored for the application. This may describe the worse performance in Accuracy and Eq.Odds despite balancing the groups in training data perfectly (GR, DI, and SP measures) in the experiments. One of the limitations of SMOTEing is data types. How would it work with categorical data? One has to define a multi-valued vector of features and statistically over-sample the outnumbered categories while they are encoded numerically which results in severe performance deterioration because of much larger search space. However, our method is easily adaptable to categorical or other data types.
We would like to also highlight once again that in this study we only study the 2019 data so that conditions 2 and 3 of Section 2.1 do not apply to our analysis. In future works, it can be studied also where the distribution of target class (condition 2) or when the decision boundary changes (condition 3) which can happen when analyzing diferent historical records for each state, e.g. comparing the 2014-2019 data of each state. Also it is worth mentioning that there is a lack of similar datasets especially from the European countries that can be provided for research which can open up space for more studies in this direction.
In this paper, we propose a spectral clustering-based methodology to tackle data representation and protected-attribute group-imbalance biases. The motivation for developing this pipeline is to utilize contextually similar but separate datasets coming from similar sources, to augment one another in order to provide unbiased or less biased training sets using shared instances from contextually similar neighboring datasets. Our MASC approach identifies an optimal number of clusters based on inherent similarities of the input tasks and clusters them according to a robust and scalable MMD two-sampled test. Furthermore, it categorizes similar tasks based on their pairwise distribution discrepancies in a kernel-based afinity space. Experimental results on New Adult datasets reveal the promising performance of the proposed MASC in dataset debiasing and superior performance in improving predictive and fairness of learning models trained using the augmented training sets obtained by it. Moreover, it is preferable over synthetic data augmentation methods such as SMOTE and RUS since it augments based on genuine (real) existing data in contrary to the synthetic ones which are usually used under many ethical concerns. In future work, we will study the efect of normalized spectral clustering on the size and shape of clusters produced. We also encourage to extend our analysis to temporal aspects of the datasets by assuming change in the conditional probability of outcomes ( | ) in → problems for each year of the input datasets. Another interesting study would be to compare our method and the Geo-neib with a version of the SMOTE and RUS for multi-class imbalance or regression problems where the targets are multi-class or continuous.
This work has received funding from the European Union’s Horizon 2020 research and innovation programme under Marie Sklodowska-Curie Actions (grant agreement number 860630) for the project ‘’NoBIAS - Artificial Intelligence without Bias’’. This work reflects only the authors’ views and the European Research Executive Agency (REA) is not responsible for any use that may be made of the information it contains. [4] D. Pessach, E. Shmueli, A review on fairness in machine learning, ACM Comput. Surv. 55 (2023) 51:1–51:44. [5] J. Quinonero-Candela, M. Sugiyama, A. Schwaighofer, N. D. Lawrence, Dataset shift in machine learning, Mit Press, 2008. [6] J. G. Moreno-Torres, T. Raeder, R. Alaíz-Rodríguez, N. V. Chawla, F. Herrera, A unifying view on dataset shift in classification, Pattern Recognit. 45 (2012) 521–530. [7] R. O. Duda, P. E. Hart, D. G. Stork, Pattern classification, 2nd Edition, Wiley, 2001. [8] I. Goldenberg, G. I. Webb, Survey of distance measures for quantifying concept drift and shift in numeric data, Knowl. Inf. Syst. 60 (2019) 591–615. [9] J. Lu, A. Liu, F. Dong, F. Gu, J. Gama, G. Zhang, Learning under concept drift: A review,
IEEE Trans. Knowl. Data Eng. 31 (2019) 2346–2363. [10] Y. Zhang, W. Liu, Z. Chen, K. Li, J. Wang, On the properties of kullback-leibler divergence between gaussians, CoRR abs/2102.05485 (2021). [11] J. Deasy, N. Simidjievski, P. Lió, Constraining variational inference with geometric jensenshannon divergence, in: H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, H. Lin (Eds.), Advances in Neural Information Processing Systems, volume 33, Curran Associates, Inc., 2020, pp. 10647–10658. [12] A. Gretton, K. M. Borgwardt, M. J. Rasch, B. Schölkopf, A. J. Smola, A kernel two-sample test, J. Mach. Learn. Res. 13 (2012) 723–773. [13] U. von Luxburg, A tutorial on spectral clustering, Stat. Comput. 17 (2007) 395–416. [14] S. Jayasumana, R. I. Hartley, M. Salzmann, H. Li, M. T. Harandi, Kernel methods on riemannian manifolds with gaussian RBF kernels, IEEE Trans. Pattern Anal. Mach. Intell. 37 (2015) 2464–2477. [15] A. V. Little, M. Maggioni, J. M. Murphy, Path-based spectral clustering: Guarantees, robustness to outliers, and fast algorithms, J. Mach. Learn. Res. 21 (2020) 6:1–6:66. [16] Y. Nataliani, M. Yang, Powered gaussian kernel spectral clustering, Neural Comput. Appl.
31 (2019) 557–572. [17] T. J. Park, K. J. Han, M. Kumar, S. Narayanan, Auto-tuning spectral clustering for speaker diarization using normalized maximum eigengap, IEEE Signal Process. Lett. 27 (2020) 381–385. [18] A. Likas, N. Vlassis, J. J. Verbeek, The global k-means clustering algorithm, Pattern Recognit.
36 (2003) 451–461. [19] F. Ding, M. Hardt, J. Miller, L. Schmidt, Retiring adult: New datasets for fair machine learning, in: NeurIPS, 2021, pp. 6478–6490. [20] D. Dua, C. Graf, UCI machine learning repository, 2017. URL: http://archive.ics.uci.edu/ml. [21] M. Feldman, S. A. Friedler, J. Moeller, C. Scheidegger, S. Venkatasubramanian, Certifying and removing disparate impact, in: KDD, ACM, 2015, pp. 259–268. [22] A. Castelnovo, R. Crupi, G. Greco, D. Regoli, The zoo of fairness metrics in machine learning,
CoRR abs/2106.00467 (2021). [23] A. Fernández, S. García, F. Herrera, N. V. Chawla, SMOTE for learning from imbalanced data: Progress and challenges, marking the 15-year anniversary, J. Artif. Intell. Res. 61 (2018) 863–905. [24] S. Mishra, Handling imbalanced data: Smote vs. random undersampling, Int. Res. J. Eng.
Technol 4 (2017) 317–320. [25] J. K. Summers, L. M. Smith, L. C. Harwell, J. L. Case, C. M. Wade, K. R. Straub, H. M. Smith,
doi:10.3390/su6063915. [26] G. W. Stewart, J.-g. Sun, Matrix perturbation theory, Academic press, 1990.