Preventing Discriminatory Decision-making in Evolving Data Streams

In continuous data streams, the status of minority and majority classes can evolve. In other words, a class currently identified as a minority may turn into the majority class, or vice versa  (Wang et al., 2013). Additionally, approaches focusing solely on fairness in recent outcomes (i.e., in the immediate future) are inadequate in combating discrimination over time. Although individual instances of discrimination may seem minor when evaluated alone, they can accumulate and result in substantial bias in the long term. Hence, monitoring the subgroup distribution in the data stream over time is vital for both the efficiency and fairness of the model. However, the primary challenge faced by $FS^{2}$ is its inability to consistently monitor data to address both concept drift and fairness concerns. In streaming machine learning, we assume the data stream to be infinite. Firstly, no memory can physically store infinite data; secondly, this would be against the stream paradigm approach. Therefore, storing every new sample in memory is impossible until the data stream ends.

To address this problem, we employ a different approach from previous non-stationary studies  (Chen et al., 2012; Gomes et al., 2017). $FS^{2}$ employs ADWIN  (Bifet and Gavaldà, 2007) to detect changes in both accuracy and fairness, reflecting both concept and fairness drifts. In other words, drift is detected when either fairness or the data distribution evolves. Specifically, we will use ADWIN to save the most recently seen samples and apply the synthesis algorithm (explained below in Section 5.2.2) using the samples stored in ADWIN. ADWIN maintains a variable-length window of recently seen items and can automatically detect and adapt the window size to the current rate of change in the data. As shown in Equation  4, ADWIN employs a threshold known as $\delta$ (i.e., performance threshold and fairness threshold) to configure the error to have two levels automatically. These levels are known as the warning level and the change level.

We identify the warning level by multiplying $\delta$ by 10, and $\delta$ itself helps determine the change level. Since $\delta$ is in the denominator, multiplying it by 10 will result in a lower value than the one obtained by using $\delta$ alone. Therefore, we will reach the warning level before the change level and can detect changes early to take appropriate action. The width of the window at any given moment is represented by $n$.

ADWIN monitors the error that occurs over the data in the window. If the error reaches a threshold of the warning level, ADWIN assumes that either a concept drift or fairness drift is starting to occur, and it starts collecting new samples in a new window. If the error exceeds the change level, ADWIN assumes either a concept drift or a fairness drift has occurred, and it substitutes the old window with the new one.

Here we propose a new strategy for synthesizing fair data to address the challenges posed by class balancing and its impact on model fairness. Our proposed approach eliminates the in-class and between-class imbalance in the oversampling part. Unlike traditional class balancing techniques such as SMOTE, our method identifies the true minority classes in the dataset (see Figure 2), and adds fairness constraints to the generation process for synthetic samples. At a high level, rather than directly running SMOTE, our approach first determines similar samples via clustering, then filters the clusters using silhouette score to ensure a good clustering. Finally, it uses SMOTE within each cluster to generate synthetic minority samples. Notably, our approach not only enhances the fairness of the balancing method but also preserves the accuracy of the prediction. Below we discuss our approach in detail.

First, we use a clustering algorithm to identify homogeneous subgroups of feature similarity in the feature space. In our experiments, we use the KNN algorithm. Note that any clustering algorithm can be applied, but different clustering algorithms may have different clustering results and time complexity. By partitioning the dataset according to the selected number of clustering families $M$, samples with similarities in the feature space will be classified into the same clusters. We will measure the quality of clustering by silhouette analysis. The silhouette score measures how similar an object is to its own cluster compared to others, and the value is between [$-1$, $1$]. A value of $1$ indicates perfect separation, and a value of $-1$ suggests that the object is in the wrong cluster. Values between $0$ and $1$ show the degree of separation, with values closer to $1$ indicating a stronger separation.

After determining the optimal number of clusters $M$, the algorithm performs filtering detection for each cluster. The algorithm will calculate the silhouette score of each sample and then remove samples with the lowest 20% silhouette score from the dataset. The intuition for this is as follows. Let’s imagine a realistic data distribution situation where a sample of a minority group exists near the cluster boundaries. In this case, we can assume that SMOTE selects the minority group sample near the clustering boundary as the template. Then the simulated data generated based on this sample will also be close to the clustering boundary. In addition, there is a risk that the generated simulated data are even closer to the clustering boundary than the original data. This increases the number of samples near the cluster boundaries, thus blurring the boundaries between different clusters, making it difficult to separate these samples in the feature space and a higher probability of being assigned to incorrect clusters. As a result, new instances generated based on these samples may further increase the distribution bias.

After the filtering is complete, the algorithm checks each cluster. Specifically, the algorithm detects the proportion of minority class samples in each cluster to determine its synthetic weight, which is directly related to the proportion of minority samples in the cluster. If the percentage of minority samples in a cluster is higher, the more representative the cluster is for minority samples. In other words, clusters with a high percentage of minority class samples are assigned higher synthetic weights. For each cluster, the synthetic weight is calculated according to Equation  5:

where $N_{i}$ is the number of minority class samples in each cluster, $N_{Total}$ is the total number of minority class samples, and $W_{i}$ is the synthetic weight of cluster $i$. The sum of all weights is one, and the number of samples selected for each cluster is calculated according to Equation 6:

where $N_{num}$ is the total number of samples to be synthesized. After calculating the number of samples selected for each cluster, the model will randomly select samples in the clusters, and a new minority sample is generated according to the SMOTE (Chawla et al., 2002) generation algorithm based on the k-nearest neighbors of the minority samples.

The algorithm for $FS^{2}$ is outlined in Algorithm 1 using pseudocode.

The $FS^{2}$ algorithm utilizes two sliding windows of samples, $W$ and $W_{label}$ (line 1). $W$ contains all samples related to the current concept. $W_{label}$ is an array indicating whether the corresponding samples in $W$ belong to the privileged favorable subgroup, privileged unfavorable subgroup, unprivileged favorable subgroup, or unprivileged unfavorable subgroup. The $FS^{2}$ algorithm utilizes nine counters (lines 2-4): $C_{0}$, $C_{1}$, $C_{2}$ and $C_{3}$ are used to count the number of instances in each subgroup, while $\overline{C_{0}}$, $\overline{C_{1}}$, $\overline{C_{2}}$ and $\overline{C_{3}}$ count the number of instances of different subgroups generated by the synthesis algorithm, respectively. The $C_{gen}$ counter for each sample $d_{i}$ in the sliding window $W$ keeps track of the number of times $d_{i}$ is used to generate synthetic samples.

$FS^{2}$ tracks instances of different classes. As we mention above, after new samples are continuously collected, the number of samples of different classes in $W$ can deviate significantly. In this case, the representation of different subgroups in $W$ may change, $FS^{2}$ will synthesize new samples to balance the representation of different subgroups. In line 5, the variable $adwin$ is a change detector that ensures the two windows ($W$, $W_{label}$) remain consistent with any concept drift by using the class value of the incoming sample. $adwin$ is used later for adapting the model to concept and/or fairness drift as needed. In line 6 the variables $balR,fairR$ are initialized to 0.

For each new instance $d_{i}$ (line 7), we first train the pipeline learner $l$ using the new sample (line 8). After this process, the new sample $d_{i}$ is saved in the sliding window $W$ (line 9). On line 10, the function $updateWindows$ adds a new bit into $W_{label}$ depending on the new sample’s class label $Y$ (i.e., 0 if $Y$ = 0). On line 11, the function $updateCounters$ increments the relative counter $C_{0}$, $C_{1}$, $C_{2}$, or $C_{3}$ depending on the sample’s class label $Y$ and sensitive attribute $S$.

After that, the $adwin$ is updated with the sensitive attribute $S$ and class value $Y$ of the incoming sample $d_{i}$ (line 12) and the $checkDrift$ function uses $adwin$ to check for any concept or fairness drift (line 13). The function adapts by reducing $W$ in accordance with the window maintained by $adwin$ to the occurrence of concept drift or fairness drift. Additionally, it updates $W_{label}$ and the counters $C_{0}$, $C_{1}$, $C_{2}$ and $C_{3}$ based on this reduction. Furthermore, if the instances removed from $W$ have been used to create synthetic samples, the function also updates the counter of instances generated for that class ($\overline{C_{0}}$, $\overline{C_{1}}$, $\overline{C_{2}}$ or $\overline{C_{3}}$). Line 14 determines the actual representation of each subgroup and then saves the associated window and counters into $W_{syn}$, $C_{syn}$, $\overline{C_{syn}}$.

Then we evaluate whether the instances in $W_{synthetic}$ satisfy or surpass the hyperparameter $minSize$ set by the user (line 15). $minSize$ denotes the minimum number of data samples already seen before rebalancing can occur. For example, if $minSize=5$, that means we must have seen at least 5 data samples before rebalancing can occur. If both criteria are met, the rebalancing stage begins. If not, the algorithm waits for another data sample to arrive. The imbalance ratio between the number of minority and majority instances is calculated according to Equation  1, and Equation 2 is used to compute the statistical parity difference. The results are stored in $balR$ and $fairR$, respectively (line 16).

Now we present the rebalancing part of the algorithm. If $balR$ is less than $p_{1}$ it means that $W$ is unbalanced, and if $fairR$ is less than the hyperparameter $f_{1}$, then $W$ is unfair. Therefore, new synthetic samples $\hat{d}_{i}$ are generated using the function $FairGenerate$ until $W$ is fair and balanced (line 18). In other words, the condition to stop synthesizing samples is that $balR$ equals $p_{1}$ and $fairR$ equals $f_{1}$, As described in the previous section, our method of generating samples will be fairer than the SMOTE.

Before generating new data points, $FS^{2}$ will calculate the number of instances introduced for each batch subgroup. Then it will cluster the instances in sliding window $W$, identify similar individuals through the feature space, filter the boundary samples, and calculate the synthetic weights for the different clusters. $FS^{2}$ will randomly select samples in each cluster to synthesize new instances $d_{i}$ and update the counter $S_{gen}$ until the synthesis number of that cluster is reached. In addition, to avoid overfitting, we will keep the one-time principle, meaning that a sample will be used only once to synthesize instances during the rebalancing phase. The algorithm violates the one-time principle only in one case: when the number of synthesized instances needed to rebalance $W$ is larger than the number of samples. Only in this case will the function reuse the same samples multiple times during the same rebalancing phase. Finally, we will use the new synthesized instances $d_{i}$ to train the learner $l$ (line 19) and calculate the new $balR$ and $fairR$ (line 21).

$FS^{2}$ is a meta-strategy that solves class imbalance and cumulative discriminatory results in data streams. In particular, we have integrated the Adaptive Hoeffding Trees (AHT) (Bifet and Gavalda, 2009) classifier. AHT is a stream-based decision tree induction algorithm that ensures the tree’s adaptation to changes in the underlying data distribution by updating the tree with new instances from the stream and replacing underperforming sub-trees. Therefore, for the online setting, AHT is superior to the majority of other classifiers. $FS^{2}$ can be pipelined with any data stream classifier.

We compare the performance-fairness metric of our proposed method ($FS^{2}$) against the four baselines. The results are demonstrated in Table  2, the darker hue of red denotes the best model performance followed by a lighter red/ pink shade that signifies the second-best performance. $FS^{2}$ performed the best in 12 of the 16 performance-fairness evaluations. It was a close second (with a margin of 1-3%) in the remaining 4 measurements.

In the BNK dataset, $FS^{2}$ achieved a maximum Balanced Accuracy of 81%, surpassing the powerful C-SMOTE. The cumulative EOD and SPD were the best for $FS^{2}$ with a 0.02 and 0.01 score respectively, while its recall score of 0.78 was the second highest. $FS^{2}$ outperformed these models on the GMSC dataset in terms of Balanced Accuracy, Cumulative EOD and SPD with respective scores of 0.83, 0.01 and 0.01. It was second in terms of Recall with a score of 0.78. Similarly, for the NYPD dataset $FS^{2}$ surpassed all four baseline methods as it got the best score for all the fairness-performance metrics i.e. Balanced Accuracy (0.68), Recall (0.54), Cumulative SPD (0.06) and Cumulative EOD (0.03). For the SYN dataset, $FS^{2}$ performed fairly well–it was the second best in terms of Balanced Accuracy and Recall. But it outshined in terms of the fairness metrics as it scored a cumulative SPD (0.04) and OPD (0.06).

To summarize, $FS^{2}$ demonstrates superior performance compared to other methods in terms of both accuracy and fairness.

With the proposed FBU, we can now evaluate the trade-off between fairness and performance based on one single illustrative metric. Figure 4 shows the overall results. As we can see, $FS^{2}$ achieves a good or win-win trade-off (i.e., it beats the trade-off baseline constructed by FBU) in most cases, i.e., 79% of the time.

In comparison, the corresponding percentages for FATH, OSBoost, FABBOO, and C-SMOTE were 32%, 25%, 58%, 31%, respectively. In addition, $FS^{2}$ has significantly fewer lose-lose trade-off cases (just 1%) than other existing methods. For example, FATH has a lose-lose trade-off rate of 15%, 15 times higher than that of $FS^{2}$. Overall, $FS^{2}$ achieves the best trade-off, and it is a significant improvement over all existing methods. The obtained results in Figure 4 are also consistent with the results in Table 2, but are presented in a unified manner that is easy to interpret, verifying the theoretical design of FBU.

In this section, we analyze the effect of varying decay factor settings on model fairness and performance in the presence of diverse data flow variations. i) Fixed Class-imbalance: In this situation the class ratio is fixed over the data stream. We noted that low decay factor values negatively impact model performance, with Recall dropping below 60% for decay factor $\textless$ 0.4. However, for decay factor $\geq$ 0.5, Balanced Accuracy and Recall were not significantly impacted. Furthermore, the model’s capacity to alleviate unfair outcomes was unchanged for all decay factor values. ii) Increasing and decreasing class imbalance: we observed a steady rise in Recall as the decay factor increased. iii) Fluctuating Class-imbalance: low values of decay factor decrease the performance as in previous cases, while high values also hurt the minority class. In this case, the positive class alternates between minority and majority. High decay factor values allow the model to consider a greater amount of history, leading to class imbalance weights assigned by $FS^{2}$ not being adjusted to recent changes. Overall, the value of the decay factor directly affects the performance of $FS^{2}$. Low values of the decay factor produce fluctuating class imbalance weights that decrease the model’s performance, and in some cases, values close to 1 are also not appropriate.

We tracked the variation of the model performance on the simulated dataset using FBU, and the results are shown in Figure 6. Our approach (the orange curve, towards the top of the graph) is designed for streaming data, and we do observe that the model has the capability to adapt and regain its performance after a concept drift takes place (the curve goes down and then goes up). And since we can handle fairness drifts, we observe that our model can adapt to both fairness drift and conceptual drift. For example, C-SMOTE has a significant decrease in the overall performance of the model because of the lack of detection of fairness drift. At the same time, the intuition and validity of FBU are well represented. Before BFU, we would need to show the changes in performance and fairness separately, and it would be difficult to analyze the specific impact tradeoff between them. FBU makes this analysis far simpler.

In our study, we evaluated the impact of various window sizes on our method, specifically using window sizes of 500, 1000, 2000, 5000, and 10000. For predictive performance, we present results on Balanced Accuracy, and for fairness we report CumSPD. As Figure 7 shows, we observe that when the window size surpasses 2000, Balanced Accuracy and CumSPD remain constant. This is due to the occurrence of concept drift, the large sliding window (window size ¿ 2000) is not able to discard outdated instances from before the concept drift, while the smaller window (size = 500 or 1000) is able to accommodate the newer instances after concept drift and discards the older ones. Generally, smaller window settings yield more fair results, but at the cost of decreased prediction performance. Conversely, excessively large window settings can impede the model’s ability to adjust decision boundaries during concept drift, thus negatively affecting model fairness.