Metrics and Algorithms for Locally Fair and Accurate Classifications using Ensembles

The idea of model ensembles is to train multiple models and select or combine the best of these models [16]. Hereby, the optimization goal typically is the improvement of the accuracy of predictions [8, 17, 20]. Combining the outputs of several models has proven to be preferable compared to single-model systems. By combining the results of several models, model ensembles can, for example, reduce the risk of choosing a model that performs poorly, which reduces the overall risk of a bad decision, or overcome complex decision borders that may not be able to be implemented by a chosen model because they lie outside the functional space of the model. The same rationale underlies fair model ensembles (discussed further below), which set an additional optimization focus on increasing fairness.

As already described in the introduction, the term fairness in machine learning commonly refers to the fact that models must not discriminate against people because of bias(es). Based on various laws, social definitions and understood meanings, different measures to quantify fairness have been defined [13, 15, 21]. They can be broadly classified into two categories. A group of metrics for individual fairness (or equality or equality of treatment) focuses on providing equal treatment to equal people [10]. However, we will focus on the second notion of fairness: group fairness. It is also known as equality of outcome or equity. Here, groups with different preconditions are treated differently, so that in the end everyone, despite their differences, has the same opportunities. This is intended to overcome social inequalities and offer equal opportunity to different groups [10].

Based on these fairness metrics, methods have been developed which allow the development of individual fair models using fair data, new machine learning algorithms, or techniques for modifying existing models [11, 13, 15].

While there is now a visible body of research on measuring fairness and learning single fair models, only few works leverage multiple models in order to achieve fairness, thereby bringing the advantages of using model ensembles to the the realm of improving fairness.

Calders and Verwer [3] create fair naive Bayes model ensembles. To this end, they split the dataset according to the favored and discriminated groups and learn a naive Bayes model on each subset with the intention to classify independently of a given sensitive attribute. An overall naive Bayes model chooses the decision of either model depending on the group of incoming data tuples to be classified. While this approach yields fairer models, it is specialized to and does not extend beyond naive Bayes models.

Dwork et al. [9] combine multiple machine learning classifiers to improve group fairness. They provide different versions of their algorithm, where the models are either learned on the different subgroups as in [3] or on larger data subsets in order to prevent accuracy loss. Their approach uses a joint loss metric that optimizes for both accuracy and fairness in order to assess which model should be used for which group of the dataset. While this approach does consider both accuracy and fairness at group level using any type of classifier, it may suffer from local unfairness.

Dynamic classifier selection [5] selects one classifier during runtime for each new sample which has to be classified. This is based on the rationale of model ensembles that not every classifier is an expert in all local regions of the feature space. Usually, for each new sample the local region is first identified, for example using \(k\)-nearest-neighbors (kNN). Then, the quality of available classifiers is determined and the best one(s) are selected. Dynamic ensemble selection is similar, it merely selects ensembles instead of classifiers. One example is the Dynamic Classifier Selection by Local Accuracy (DCS-LA) algorithm by Woods et al. [19]. First, it uses kNN to identify the local region. Then, local accuracy of classifiers is evaluated as percentage of correctly classified samples in the local region. Alternatively, it uses local class accuracy, which is the accuracy of classifiers in the local regions with respect to the class the classifiers assign to the new sample. Only the most accurate classifier is then used to classify the unknown sample.

As illustrated in Fig. 2a, the problem with locally unjust decisions is that while existing solutions (reviewed in Sect. 2) are optimized to make globally fair and accurate decisions, there are still local regions where data points of different groups are treated unfairly. To address this problem, the decision should be optimized so that the optimal (i.e. fair and accurate) decision can be made at a local level. Our emphasis in this paper is on group fairness, i.e., equal opportunities between groups.

Formally, we consider as given a labeled dataset \(D\), a similarity metric \(s\), a positive integer \(k\) indicating a local region sample size, an optimization metric \(af\) combining fairness and accuracy, and a set of machine learning models (classifiers) \(M\) for the same classification task. Furthermore, \(D\) can be partitioned into groups \(G\), for which equal opportunity is relevant. We further assume a new test sample \(t\) that belongs to one of the groups \(G\). Then, we define our goal of locally fair and accurate classification as a classification task that classifies \(t\) using a model \(m\in M\) with the best performance according to the \(af\) metric in the local region of \(D\) around \(t\). This local region includes the \(k\) items in \(D\) most similar to \(t\) according to \(s\).

To address the problem defined above, we combine the rationales underlying both fair and dynamic model ensembles described in Sect. 2 into a new framework for fair and dynamic model ensembles. The main components of this framework are visualized in Fig. 3. We distinguish between an offline phase (bottom part), where suited model ensembles are trained and selected, and an online phase (upper part), where a previously unseen test sample \(t\) is classified by dynamically selecting the model ensemble most appropriate for \(t\).

Offline phase. The first step of the offline phase, named model training, is a step common to model ensemble approaches. Here, using training data taken from the labeled dataset \(D\), a diverse set of classifiers is trained. Given that we target both fair and accurate decisions, model training can benefit from using different subsets of data based on the different groups \(G\) present in \(D\), which has for instance been proposed for fair model ensembles (see Sect. 2). We denote the set of classifiers resulting from model training considering different groups \(G\) as \(M=\{(m_{1},g_{1}),(m_{2},g_{2}),\ldots,(m_{n},g_{n})\}\), where each \(m_{i}\) is a model and \(g_{i}\) identifies the group it is trained for. Among these classifiers, not all may be suited to make both fair and accurate decisions. Also, too many classifiers to be considered during the online phase (further discussed below) can be computationally prohibitive. Therefore, during model pruning, the framework assesses all model combinations or ensembles possible with the classifiers in \(M\) that use exactly one classifier per group \(g_{i}\). Assessment is done with respect to the global performance metric \(af\) that considers both accuracy and fairness. Only the best classifier combinations are retained after model pruning, resulting in the model candidates MC = {[((m₁₁, g₁) …, (m_1n, g_n)], …, [((m_e1, g₁) …, (m_en, g_n)]}, a set of model ensembles (in square brackets) s.t. for each ensemble, \(g_{i}\neq g_{j}\) when \(i\neq j\) and \(n=|G|\).

Online phase. When a new test sample \(t\) is to be classified, the framework determines the local region \(t\) belongs to as part of local region determination. To this end, it performs a kNN search of \(t\) on each \(g_{i}\), where \(g_{i}\) is a group in \(G=\{g_{i},\ldots,g_{n}\}\). The framework specifically selects an equal number of members similar to \(t\) of each group, to have a locally balanced data region with respect to the different groups. Then, for this particular region, dynamic ensemble selection assesses which ensemble \(E\in MC\) achieves the best local performance with respect to \(af\). Intuitively, this dynamically selects the optimal model ensemble comprising a dedicated model for each group for the region most relevant to \(t\). With this approach, our framework combines previous techniques separately devised for fair and dynamic model ensembles. The identification of the locally best model is performed according to dynamic model ensemble techniques using fair model ensemble metrics. Therefore the classifiers are tested on the local region of the test sample using an \(af\) metric. Finally, the best classifier \(m_{ct}\) such that \((m_{ct},g_{t})\in E\) and \(g_{t}\) corresponds to the group \(t\) belongs to is used in the final step of locally fair classification to classify \(t\).

As mentioned before, the set of classifiers should be diverse in order to benefit from combining them to model ensembles. To this end, we vary both the set of machine learning techniques used to train classifiers as well as the data from \(D\) that are considered for training.

In principle, any machine learning technique suited for classification tasks can be considered as a candidate technique. In our evaluation, we will resort to simple techniques, e.g., decision trees, logistic regression, or nonlinear support vector machines [12].

Concerning the data, following previous research on fair model ensembles [3, 9], we consider splitting the input dataset \(D\) on pre-defined sub-datasets that correspond to the different groups for which we aim to achieve group fairness (e.g., we divide by sex (male, female) and race (white, others) in our experiments which creates four subgroups). This effectively partitions \(D\) into \(G=\{g_{1},\ldots,g_{n}\}\), assuming \(n\) distinct groups. Then, models are trained separately for the different partitions. Different training datasets have the advantage of learning different models that exhibit their strengths in certain areas of the feature space. However, as shown in Calders et al [3], splitting up the input dataset does not necessarily improve the quality of the results. In addition, complex decision borders between the two groups, which originate from different behavioral patterns, can be better modeled, thus increasing accuracy [9].

As a result, similar to [3, 9], we obtain classifiers that are “specialized” on some group. More precisely, in this variant, we obtain \(M=\{(m_{1},g_{1}),\ldots,(m_{k},g_{n})\}\) where each \((m_{i},g_{j})\) associates a classifier \(m_{i}\) to a group \(g_{j}\). For any two \((m_{i},g_{j}),(m_{i^{{}^{\prime}}},g_{j^{{}^{\prime}}})\), it holds that \(m_{i}\neq m_{i^{{}^{\prime}}}\), and \(g_{j},g_{j^{{}^{\prime}}}\in G\), but it is possible that \(g_{j}=g_{j^{{}^{\prime}}}\).

On the downside, splitting the data as described above can lead to a too small dataset to train on, which often results in loss of accuracy for the classifiers. Hence, we further consider the option of training models on the complete dataset \(D\) rather than on individual partitions of \(G\). In this setting, we have \(M=\{(m_{1},g_{D}),\ldots(m_{n},g_{D})\}\), where \(g_{D}=D\).

To distinguish the two variants for implementing model training described above in FALCES, we will append a suffix SBT (for Split Before Training) for the first option, while absence of this suffix indicates training is performed on the full training dataset.

In the offline phase, the number of classifiers can already be reduced based on their global performance in order to improve the efficiency of the online phase later. Indeed, the less classifiers need to be considered in the online phase, the faster the classification of a new test item is. As we shall see in the evaluation (Sect. 6.8), this has only little impact on making locally fair and accurate decisions, while runtime may improve significantly. In this section, we first present metrics we consider for model pruning, to then describe how these are used for model pruning.

Moving on to the online phase, the task is to classify a new tuple \(t\) in a locally accurate and fair manner. Our framework defines locality relying on a similarity measure \(s\) and considers retrieving the \(k\) most similar tuples to \(t\) in \(D\).

The approach for retrieving the most similar tuples depends on the types of data we are dealing with. We now discuss different types of data and present the corresponding algorithms to retrieve the \(k\) most similar tuples.

Based on the \(|G|\cdot k\) tuples defining the local region for a given test sample \(t\), dynamic ensemble selection identifies the ensemble \(E=[(m_{c_{1}},g_{1}),\ldots,(m_{c_{p}},g_{p})]\in MC\) that achieves the best local performance. To this end, FALCES follows previous research on dynamic model ensembles [19] and combines these techniques with the \(af\) metric. More precisely, using as input \(MC\), we evaluate all model combinations based on \(af\) when they classify the \(|G|\cdot k\) nearest neighbors of \(t\). The combination \(E\) with the lowest \(af\)-score is retained.

Note that through previous model pruning during the offline phase, the above example needed only to consider 2 instead of 25 classifier combinations. In addition to reducing the number of comparisons, we further reduce the complexity of an individual combination assessment, because the computation of classification predictions for all sets of classifiers and all local \(|G|\cdot k\) tuples can be quite time consuming. That is, FALCES precomputes all classification predictions for all tuples in \(D\) using all models in \(M\). This allows dynamic ensemble selection to simply look up the necessary predictions instead of repeatedly computing them by applying the classifier for each test sample during the online phase.

Finally, the classifier of the previously identified model ensemble \(E\) that achieved best local performance with respect to the \(af\) metric and that is associated to the same group as \(t\) is used to classify \(t\).

This section summarizes which different algorithm variants and baseline solutions we compare in our evaluation. We further discuss datasets and metrics we use for benchmarking.

Compared algorithms. We have presented different variants of FALCES, depending on whether or not the training data is split before training and whether or not model pruning is applied. In addition, we compare to the state-of-the-art algorithms. More precisely, we consider the algorithms summarized in Table 2 for each experiment. Additionally, we also want to evaluate the performance of the algorithm variants using the runtime-efficient framework adaptation described in Sect. 5 and compare it with the original FALCES variants. We evaluate the different fairness metrics for these algorithms as well as vary the \(\lambda\) value of the \(af\) metrics used. Furthermore we want to see what influence changing the \(k\)-value for the kNN algorithm has on the overall results. When not mentioned otherwise, we set \(k=15\) as the default value. The reasoning for choosing this value has been based on some prior testing, which showed across the datasets considered that a \(k\)-value of 15 provides promising results, while still having an acceptable runtime.

Datasets and ML models. We use both synthetic and real benchmark data in our evaluation.

We developed a synthetic data generator in order to control different types and degrees of bias in order to study how the different algorithms are affected by these. The generated datasets use numerical values, hence the kNN algorithm can be directly used on the datasets. It generates labeled data for two groups and a binary classification task and allows to control (i) the group balance, (ii) the degree of social bias, and (iii) implicit bias. Group balance describes the percentage group \(g_{1}\) represents in the full dataset (\(g_{2}\) implicitly making up the remainder of the dataset), which can be very unbalanced (e.g., only 10% of the training data belong to \(g_{1}\)) or perfectly balanced at \(50\%\). Social bias refers to bias directly related to the protected attribute defining a group (e.g., gender in our example), reflected by different probabilities for a positive label in the different groups (e.g., women have a lower probability for a positive label than men). Such bias is sometimes also called historical bias, because it reflects direct discrimination of a group in a dataset that commonly labels data based on historical decisions. In our experiments, a social bias of 0 means probabilities are equal for both groups (no discrimination), 0.1 if the probability for \(g_{1}\) differs by 0.1, and so on. Implicit bias is present in a dataset when, even though groups are not directly discriminated, their label depends on an unfavorable attribute value that occurs more frequently in the protected group, i.e., that is correlated to the protected group. Note that both examples from the press mentioned in the introduction are likely linked to such implicit bias. Similarly to social bias, we vary implicit bias from 0 (none) in increments of 0.1. The generated data in all cases consist of approximately 13,000 tuples. Table 3 summarizes the configurations we used for testing. When not mentioned otherwise, the values are set to the default values highlighted in bold.

We chose the Adult Data Set [7], a census income dataset with data from 1994, which is a commonly used dataset in multiple machine learning experiments. This dataset consists of approximately 49,000 tuples and contains various variables, including a binary salary value of yearly income with the threshold of 50 K$, which is our label in the experiments. We chose the attribute “sex” with values “male” and “female” as a sensitive attribute, as well as a combination of the attribute “sex” with the attribute “race” with values “white” and “others”, where we grouped together all other races, because all other races make up \(\approx 10\%\) of the dataset. The dataset got preprocessed in such a way that our implemented kNN algorithm could work properly in order to have a better runtime.

Each dataset (synthetic and real) is split randomly such that 50% of the dataset serve as training data for model training, 35% for validation to determine emsembles, and 15% for testing the quality of predictions in the online phase.

To get a diverse set of classifiers, we train five different classifiers on our datasets: (i) Decision Tree, (ii) Logistic Regression, (iii) Softmax Regression, (iv) Linear Support Vector Machine, and (v) Nonlinear Support Vector Machine [12]. Given that we have two groups, this results in ten classifiers when we split before training, and five when training on the full dataset.

Metrics. Given that we aim for a good compromise of accuracy and fairness, we use metrics to assess the different algorithms in these two dimensions. We use the well known accuracy-metric commonly used to evaluate machine learning techniques. For fairness, we distinguish between global and local fairness. To study global fairness, we use the “unfairness part” of the metric given by Eq. 2 (setting \(\lambda=0\)), to which we refer to as global bias (lower values are better).

To measure local bias, we define a local region bias metric, which we call local region discrimination (LRD): where \(R_{t_{i},g_{j}}\) is the local data region of \(t_{i}\) comprising the kNN of \(t_{i}\) in group \(g_{j}\). In this metric the probability of a positive predicted label of each group in the local region is measured against the average probability of a positive predicted label amongst all points in the local region. In this way, the metric reflects the average local fairness.

Table 4 depicts a brief overview over the different parameters used and evaluated in our experiments. Using the experimental setup described in this section, we now discuss results we obtained.

We first present results we obtained when using different algorithms on our synthetic dataset in terms of accuracy, global bias, and local bias. The metric used for the Decouple and FALCES algorithms in the following results is the \(\hat{L}_{\text{mean}}\) metric described in Eq. 2.

As a first baseline, we start with a “clean” dataset with no social or implicit bias, and see if changes in group balance have an impact on our three metrics. Essentially, we expect only a marginal effect on accuracy and a low global and local bias, because the input data are a priori unbiased. This is confirmed by the results depicted in Fig. 5. Note that instead of plotting absolute accuracy for all methods, we plot the deviation algorithms have in accuracy from the accuracy reached by DCS-LA, reported as percentage points. DCS-LA is not considering bias and optimizes solely for accuracy, which is between 0.76 and 0.79 for DCS-LA over the whole range of considered group balance. The ordinate reporting percentage points, a deviation of -1 means that an algorithm reaches for instance 0.77 instead of 0.78 reached by DCS-LA.

In Fig. 5, we observe that all algorithms perform similarly, i.e., for all algorithms, there is some very small fluctuation in accuracy and global bias remains low. For local bias, while being generally low as well, we observe that it steadily increases with increasing imbalance, reaching a relative increase of up to 64% from the balanced case (0.5) to the highest imbalance (at 0.1, where only 10% of the dataset concern one group).

Next, we perform the same analysis again, but this time with an additional social bias of 0.3 introduced to \(g_{1}\). The results are summarized in Fig. 6. With the introduction of social bias, we observe that deviations in accuracy become more pronounced, in particular for the two variants of the Decouple algorithm. Least affected in terms of accuracy is FALCESSBTPFA, actually having comparable or better accuracy than DCS-LA. For both local and global bias, we see that all FALCES variants consistently outperform both Decouple variants and DCS-LA. Also, compared to the previous experiment without social bias, the field has overall shifted upwards. This shows that we cannot fully counter bias originally present in the dataset, but FALCES is best in reducing it while maintaining high accuracy.

Our next analysis focuses on the impact different degrees of social bias have on the overall performance, assuming balanced groups without additional implicit bias. Fig. 7 reports our results. For accuracy, we observe that all methods fluctuate, but the degradation in accuracy (typically less than 2 percentage points) is tolerable. Our approaches are more robust to social bias than the state-of-the-art Decouple variants, the PFA variants generally being closest to the accuracy reached by DCS-LA. For both local and global bias, a clear upward trend is visible with increasing social bias, showing that the more bias in the input data, the more bias the ensemble generates. However, the gradient of our approaches is less steep and consistently below the baseline methods. This means that the more social bias in the data, the more effective our approaches are in countering the bias to optimize (local) group fairness compared to the state-of-the-art. FALCES-SBT is best in terms of global and local bias, but FALCES-SBT-PFA has similar performance and thus presents a good compromise in datasets with mainly social bias.

We perform a similar analysis for implicit bias in the source data, again assuming a balance of groups (balance = 0.5) and setting social bias to 0. Fig. 8 visualizes the results of this set of experiments. Our first observation is that implicit bias impacts all metrics more than the previously considered social bias. As before, in terms of variations in accuracy, these are strongest for the Decouple variants, whereas the PFA variants of our algorithm outperform FALCES and FALCES-SBT. However, looking at both local and global bias, our algorithms without model pruning typically perform better than their counterpart with PFA. The reason for this is that model pruning during the offline phase can prune classifiers that would, during the online phase, be better compared to those retained after model pruning. Nevertheless, in general, our methods outperform the state of the art for a wide range of implicit bias configurations.

We validate our findings on artificial data on the real-world dataset as well. Given that it includes two sensitive attributes (sex and race), we study accuracy, global bias, and local bias when just one attribute is used to form groups (resulting in two groups) and when two attributes are used (resulting in 4 groups). Fig. 9 shows the average results of multiple tests for global and local bias. Results on accuracy confirm that all algorithms perform similarly, it consistently ranges between 0.790 (Decouple) and 0.799 (DCS-LA). As before, we observe that FALCES variants typically are comparable or outperform the three baseline algorithms, both in terms of global and local fairness. With the increasing number of sensitive attributes, we observe that the bias increases for all methods.

In conclusion, we see that our methods improve on the state of the art by offering a better accuracy-fairness compromise than the state of the art Decouple approach (considering global fairness) and the difference in accuracy compared to DCS-LA is typically tolerable. Our methods are also the most robust to different types and degrees of bias (we studied group balance, social bias, and implicit bias). An added benefit is that our methods inherently consider local fairness as well, and our evaluation of local fairness shows that the classifications performed using our algorithms get us closer to equal opportunity for different predefined groups.

In Sect. 4.2, we have presented multiple alternative metrics for \(af\), used both during model pruning in the offline phase and dynamic classifier selection in the online phase. All experiments so far have used our metric \(\hat{L}_{\text{mean}}\) (Eq. 2). The next series of experiments investigates how different metrics potentially impact the result. For the sake of consistency and to compare the different metrics, we still use the same methodology (mean difference) to calculate the global bias and the LRD metric to calculate the local bias.

First, we want to compare the results of the state-of-the-art metric of Eq. 1 as SOA, with our metric \(\hat{L}_{\text{mean}}\), since it is an extended version of the SOA metric. As a reminder, our extension aims at countering the effect on fairness in presence of unbalanced groups. Therefore, we focus our study on evaluating both the global and local bias for different configurations of group balance. As before, accuracy is comparable across all approaches, whether we use SOA or \(\hat{L}_{\text{mean}}\). Fig. 10 reports our results on global bias and local bias comparing the results of both approaches. For better readability, we omit the results of Deocuple, Decouple-SBT and DCS-LA, as their relative performance to the other approaches being analogous to our previous discussion. The dotted lines represent the results when using the state-of-the-art metric, while the results using the \(\hat{L}_{\text{mean}}\) metric are presented in solid lines. For both global bias and local bias, we see that FALCES variants without model pruning (FALCES and FALCES-SBT) are comparable when using SOA or \(\hat{L}_{\text{mean}}\). The effect of using a different metric only becomes apparent when model pruning is active. Overall, we see that \(\hat{L}_{\text{mean}}\) closes the “bias gap” between FALCES variants with model pruning (FALCES-PFA and FALCES-SBT-PFA) and those without. This allows our methods to consistently exhibit low bias, especially in comparison to state-of-the-art algorithms like Decouple. This behavior can be explained by the fact the \(af\) is used by model pruning where group imbalance can cause the pruning of otherwise good classifier combinations. Note that the use of \(af\) during the online-phase is not sensitive to the choice of the two metrics, because it ensures class balance in the local region by selecting \(k\) members of each group to form a region. Consequently, FALCES and FALCESSBT are not significantly affected by the choice of metric.

Furthermore we want to explore the effects when using other fairness metrics, like \(\hat{L}_{\text{impact}^{*}}\) or \(\hat{L}_{\text{elift}^{*}}\) as described in Eq. 3 and Eq. 4 respectively. Due to the nature of ratio metrics in comparison to difference metrics, when using values within the range of \([0,1]\), the output generated by the ratio metric is greater than the output generated by the difference metric. Since the fairness part of \(\hat{L}_{\text{impact}^{*}}\) and \(\hat{L}_{\text{elift}^{*}}\) will generate values higher than the \(\hat{L}_{\text{mean}}\) metric, we want to evaluate these metrics when varying the bias value of the dataset. The expectation is that a higher bias in the dataset results in a bigger improvement by our algorithm variants when using one of the two ratio metrics. Here we also want to measure the influence of these metrics on the accuracy value, since this is expected to decline. The results are depicted in Fig. 11 and Fig. 12. The results show, that although our FALCES algorithms still outperform the DCS-LA and Decouple algorithms, the gap of global and local bias is more narrow. Contrary to our expectations, the bias is not further decreased compared to the \(\hat{L}_{\text{mean}}\) metric results. In general the global and local bias is even higher than when we used the \(\hat{L}_{\text{mean}}\) metric. The difference between both ratio metrics \(\hat{L}_{\text{impact}^{*}}\) and \(\hat{L}_{\text{elift}^{*}}\) is very small as expected, since both metrics are similar to each other. Also the assumption about the influence on the overall accuracy is invalidated within this experiment. The overall accuracy values of the predictions are similar to the ones using the difference metric for the fairness part, hence metric \(\hat{L}_{\text{mean}}\). However, the conclusion that the FALCES algorithms reduce further bias compared to the state-of-the-art Decouple approach still persists when using other \(af\) metrics.

All experiments so far have used the default \(\lambda\) value of \(\lambda=0.5\), which means that both parts, accuracy and fairness, are valued the same. We want to test how the overall results change when different \(\lambda\) values are used, ranging from \(\lambda=0\) (ignoring the accuracy part) to \(\lambda=1\) (ignoring the fairness part) with steps of 0.1. The evaluation has been made for the \(\hat{L}_{\text{mean}}\) and \(\hat{L}_{\text{impact}^{*}}\) metrics. We omit the evaluation for the \(\hat{L}_{\text{elift}^{*}}\) metric as they are analogous to the results of the \(\hat{L}_{\text{impact}^{*}}\) metric. Fig. 13 and Fig. 14 show the results.

The DCS-LA algorithm does not have the same result in each computation, which could be the result of randomly choosing the classifier if multiple classifiers perform equally well. Overall the results show, as expected, that for a low \(\lambda\) value, the bias tends to be lower for our algorithms, but also worsen the overall accuracy. For a higher \(\lambda\) value, the accuracy gets better, but the bias becomes higher at the same time. For the experiments we conducted, a \(\lambda\) value between 0.3 and 0.5 seems to be optimal when using the \(\hat{L}_{\text{mean}}\) metric, while for the \(\hat{L}_{\text{impact}^{*}}\) metric a \(\lambda\) value between 0.3 and 0.6 seem to provide similar results. Surprisingly, when using the \(\hat{L}_{\text{impact}^{*}}\) metric, the FALCES-PFA algorithm seems to perform badly, while the FALCES-SBT-PFA algorithm overall performs the best considering local bias and accuracy, and also performs similar to the FALCES-SBT algorithm when considering global bias and accuracy. Also our FALCES algorithms have some different results compared to the DCS-LA algorithm, although it behaves similarily for \(\lambda=1\). However, since we consider the kNN of each group nonetheless within FALCES, we take into account more sample points overall within the validation dataset compared to the DCS-LA algorithm.

Another experiment we conduct in this paper is about the influences of different \(k\)-values for the kNN algorithms. A positive aspect of a high \(k\)-value is that multiple points are considered, hence the effect of a single point is lower. However this could also result in a problem, since if the \(k\)-value is too high, points might be considered as close which are not necessarily similar to the current point considered. Also we are taking into account the kNN of each group for the FALCES algorithms, so if the \(k\)-value is 20 and we have, e.g., 4 sensitive groups, we use 80 points to decide which model combination is best suited for the current point. The results are shown in Fig. 15.

The results of this experiment are unexpected as the accuracy results are the lowest for \(k=10\). Apart from that the results seem to be quite stable, especially for the local bias value. The downside of having a small \(k\)-value is that not many points are considered in order to find the locally best machine combination for a specific sample. On the other hand, choosing a high \(k\)-value could risk that points are considered as being similar to the current tuple, although they might vary a lot. Especially when dealing with a lot of different groups, one group might only have very few samples. If a high \(k\)-value is chosen it would mean that a high proportion of this group is considered. E.g. we set \(k=100\) and the underlying dataset consists of 6 different groups, whereas there is one small group consisting of only 300 tuples. In this case 1/3 of the group would be considered as being similar to the currently considered tuple, although in reality a high number of these tuples might be totally different.

In Sect. 4.3 we mention that a preprocessed dataset is needed to perform the more runtime-efficient kNN algorithm. Additionally, it is also mentioned that not only the runtime might suffer if a no preprocessed data is used, but that also the qualitative results might take a hit. Therefore we conduct an experiment about the influence of using preprocessed data. In Fig. 16 we see the results of the experiment using the same data as the experiment in Fig. 7. The difference is that this time we do not use pre-processed values, hence we only have a distance of 1 or 0 of an attribute between two points. We use distance 0 if the attribute value is the same and 1 otherwise. The influence on the runtime is shown in Sect. 6.8. However, for the LRD metric in the evaluation we still use the original kNN algorithm.

As expected, the results are worse if the data is not preprocessed. However, the degree of the impact is higher than initially expected. Especially the variants without pruning model combinations perform worse in both aspects, accuracy and bias, compared to the Decouple, and even the DCS-LA algorithm. Also the FALCES variants with model pruning are providing similar results as the Decouple algorithms. This indicates that the FALCES algorithms should be used on preprocessed datasets.

The last experiment we conduct is comparing the algorithms implementing the new runtime-efficient framework adaptation described in Sect. 5 with the other FALCES algorithms. We chose \(k=10\) for the kNN algorithm within the prediction dataset. The accuracy value is similar in both experiments and is therefore not depicted here. The results are depicted in Fig. 17. These were similar to the results when varying the implicit bias or using the other metrics. The FALCES algorithms using this new adaptation have added “‑NEW” to their name in this graph and are depicted as solid lines. The comparison of the runtime is provided in Sect. 6.8.

Expectedly, the bias of the results slightly increase using this new approach. However the difference is mostly marginal. In situations where the runtime is important, it might be useful to use the runtime-efficient adaptation, since the tradeoff in terms of bias is rather low.

Furthermore we want to evaluate the runtime-efficient framework adaptation on the real-world dataset as well. Fig. 18 depicts the results in comparison to the standard FALCES algorithms for the dataset with both, 2 sensitive groups and 4 sensitive groups. The results of the standard FALCES algorithms slightly deviate from the ones shown in Fig. 9, since that figure shows the average of multiple runs. On the real-world dataset with 2 sensitive groups the FALCES algorithms using the framework adaptation even have less global bias for most of the variants. However, this can not be confirmed for the dataset with 4 sensitive groups. In general the bias value is very similar in both strategies.

We also evaluate the efficiency of our approach in its online phase. In particular, we study the effect of model pruning in the offline phase on the online performance, as well as the effect of other proposed FALCES strategies. To this end, we run the four variants of FALCES and measure the average runtime to perform online classification on a tuple for which we want a prediction. Compared to our originally published paper [14] we provide a more extensive runtime evaluation in this enhanced version. Due to a different hardware, as well as some minor changes within the code, the overall runtime in this paper also deviates compared to the original paper. For Fig. 19a–e the evaluation has been conducted on the synthetic dataset with 30% of social bias, while for Fig. 19f the evaluation has been done on the real-world dataset.

We report results in Fig. 19a on our synthetic dataset with 30% social bias, on which we can vary the number of groups (either 2 or 4), given two sensitive attributes. In any configuration, we see that model pruning during the offline phase improves the average runtime to classify a test tuple during the online phase. While this improvement is moderate when limiting to two groups, the difference increases as the number of groups increases. This can be explained based on the fact that for two groups and five models trained per group, we have 25 combinations to consider during the online phase when none are previously pruned. This exponentially increases with the number of groups, e.g., for 4 groups, \(5^{4}=625\) combinations need to be tested. The runtime gap is increasing with the numbers of model combinations considered. Surprisingly the SBT variants also outperform the other algorithms in terms of runtime by quite a margin. This could be due to a slightly different implementation strategy adapted for this variant.

The FALCES algorithms implementing the runtime-efficient framework adaptation defined in Sect. 5 show a big runtime improvement compared to the standard FALCES algorithms, as depicted in Fig. 19b. Taking into consideration the results of Fig. 17 that showed that the overall bias is only slightly increased for the framework adaptation with our settings, and in some cases even performs a little bit better, using this strategy seems very promising.

Fig. 19c depicts the runtime results of our standard algorithm compared to the runtime, if the data are not preprocessed properly and do not conform to a specific format. As expected the runtime increases significantly, since the optimized kNN algorithm cannot be used. Combining it with the results of Fig. 16 which showed that if the data are not preprocessed, FALCES does not reduce the bias compared to the state-of-the-art algorithms, which proves that preprocessed data are of utter importance for our FALCES algorithms, both in terms of runtime as well as quality of the results.

The \(k\)-value chosen has also an influence on the overall runtime as it can be seen in Fig. 19d. In this experiment, the runtime with 2 kNN compared to 5 kNN is tripled for the algorithms where the data are not split before the training phase. However, for the SBT variants, the runtime difference is surprisingly rather small. An explanation could be that due to splitting up the dataset beforehand, finding and accessing the kNN can be performed faster, while the amount of model combinations considered is still the same.

Fig. 19e depicts the impact of having sorted indices for the validation dataset. This shows that the runtime can be further improved using this strategy, while having no effect on the overall quality of the results.

Fig. 19f shows the effect on the runtime on the real-world dataset with 4 sensitive groups, when comparing the original FALCES algorithms with their runtime-efficient framework adaptations described in Sect. 5, combined with having sorted indices within the validation dataset.

The results of the detailed experiment discussion can be summarized as follows.

While FALCES typically provided good results, which variant to choose depends on several factors.

Overall, FALCES-SBT-PFA-NEW is a promising algorithm, when the runtime is an important factor and FALCES-SBT or FALCES-SBT-NEW, if the goal is solely to reduce bias.