Fair Decision-making Under Uncertainty

While machine learning increasingly permeate facets of life, significant concerns on the unfair and discriminatory manner of ML-based systems have been voiced and observed [15]. The machine learning community has responded by proposing a growing body of fairness notions to measure the level of discrimination along with a number of approaches to mitigate bias in order to provide fairness-aware decision-making systems [16].

The broad set of existing mathematical formulations of fairness can be typically divided into two main families, individual fairness and group fairness, based on whether they evaluate fairness at the individual level or the group level, respectively [17]. The former definitions aim to ensure that similarly situated individuals are treated similarly. The seminal work is the notion proposed by Dwork et al. [11], which requires similarly situated individuals to receive similar probability distributions over class labels to prevent unequal treatments. One of the prerequisites of this line of work is the demanding of a task-specific similarity metric that is suitable to measure how similar two individuals are depending on the task at hand. In practice, however, such a proper similarity metric cannot be trivially specified or it is even not possible to do so. Take the individuals with censorship as an example, a proper similarity metric is hard to be specified unless disregard the censored information which is of great importance and cannot simply be ignored. The lack of task-specific similarity metric has therefore been a major obstacle for the wider adoption of individual fairness [18].

On the other hand, group fairness notations normally first specify a set of subgroups defined by sensitive attributes (e.g., race or gender), then preserve fairness by asking for group level approximate parity of some statistic over class labels either predicted or actual. For example, statistical or demographic parity, the representative formulation belonging to this category, measures whether the desired outcomes are equally distributed across different demographic groups [19]. Compared to the dependence of predicted class label of statistical parity, equalized odds [20], another representative notation, further depends on the actual class label by considering the true classification difference between different subgroup.

Although many fairness notions exist, most of them, as previously discussed, formulate fairness depend on class label either actual or predicted, thus limiting their applicability in censoring settings which is prevalent in real-world applications. Keya et al. [21] directly extend the existing fairness notions to the application with censoring problems, which is the single relevant effort to the best of our knowledge. However, their definitions exclude the censoring information when measuring discrimination, which could introduce substantial bias, as censored information might be of importance and cannot simply be ignored [22]. In addition, a similarity metric, as one of the vital components, is required to be specified with the Euclidean distance employed in their study, which could lead to inappropriate similarity evaluation due to censorship as well as the potential distinct semantic meanings of different attributes [23]. Our proposed fairness notions alleviate such limitations by explicitly involving censoring information and is free of similarity metric specification.

The fairness definitions above could be directly used or slightly modified as a constraint or a regularizer to enforce fairness, leading to three categories of mechanisms to guarantee fairness: i) pre-processing approaches, ii) in-processing approaches and ii) post-processing approaches, depending on the intervention occurs at the input/data layer, the algorithm design or the output/results of the model, respectively.

The first strategy, pre-processing approaches, deals with bias in the input/data level. The underlying assumption is that in order to learn a fair classifier, the training data should be discrimination-free. Therefore, the methods in this category, try to “correct” the data to ensure fairness in the representation of different communities. This comprises a popular category of methods as it is model-agnostic and therefore, can be employed by any classifier. For instance, massaging [24] changes the data distribution by re-labeling some of the instances in order to neutralize discriminatory effects. The instance to be altered are those close to the decision boundary, which is provided by a ranker. The method is applicable to binary classification problems, so the re-labeling is actually label swap. Massaging might result in reverse discrimination, i.e., communities that were favored are now discriminated. In [25] an extension of massaging is proposed that also deals with the problem of reverse discrimination. Reweighting [26], on the other hand, assigns different weights to the different communities, e.g., the deprived community will receive a higher score comparing to the favored community. However, the underlying assumption of such type of approaches does not necessarily hold as inherit bias could still persist due to proxies/correlations between features.

The second category, in-processing techniques, directly modifies the learning algorithm to ensure that it will produce non-discriminating results. Typically, these methods are algorithm-specific. As an example, the fairness gain, reflected by the reduction in discrimination, is incorporated into the splitting criterion for fair tree induction [27]. This model was later extended as an ensemble approach offering additional adaptability and flexibility of fairness [28]. In [29], the Mann Whitney U statistic, a rank-based non-parametric independence test, is leveraged to measure the correlations between class label and sensitive attribute, then further reformulates it as a new non-convex optimization problem to mitigate the inherent bias of the data. The common assumption hold by these methods is the certainty on the class label. On the contrary, research on fairness under uncertainty has still been limited due to the significant technical challenges when addressing unfairness and censoring distribution simultaneously [21]. Our work seeks to fill this gap by jointly addressing bias reduction and censoring management.

The last category, post-processing solutions, “corrects” the results of a model by modifying its decision regions to ensure a fairer representation of different communities. For example, in [30], the prediction thresholds are adjusted to decrease discrimination while minimizing the effect on predictive accuracy whereas in [31], the authors shift the decision boundary of the deprived group to work against discrimination. In this category, one could also place method for building human-interpretable models [32]. We emphasize that transferring such techniques to censoring settings is not straightforward as the decision boundaries could be censored themselves due to the censored distributions in censoring settings.

The critical challenge of the main outcome under assessment could be unknown for a portion of the study group, deemed censoring, hinders the use of many methods of analysis. This motivates the study of survival analysis to address the problems of partially survival information access from the study cohort [14, 33, 34].

With the ubiquitous of censored data, survival analysis has gained its popularity in applications beyond its originated medical domain ranging from customer analytics and actuaries to predictive maintenance in mechanical operations [35, 36, 37]. Among the various methods proposed for modeling censored data, the Cox proportional hazards model (CPH) [38] is the most commonly used in which the multiplicative relation between the risk, as expressed by the hazard function and covariates is described. Under the assumption of proportional hazards, deep neural networks have recently also been employed to better encode the nonlinearity of censored data [39, 40]. In contrast, another line of effort is the tree based methods [41, 42], particularity random forests due to its superior capabilities in handling nonlinear effect of variables and is free of restrictive assumptions such as proportional hazards [43, 36]. A comprehensive literature survey covering recent censored data modeling effort is provided in [44].

Amid the popularity of survival models, same as other ML approaches, care must be taken to ensure the fairness of these models. Our work situates in this under-explored research direction to tackle fairness in the presence of censoring. Our in-processing approach incorporates a fair splitting criterion that explicitly considers censoring information into the algorithm design to guide an accuracy-driven and fairness-oriented learning procedure. Relevantly, the Cox model is modified to ensure fair risk predictions in [21]. Three key differences are that our model: i) does not necessitate a distance metric to be specified for the wide adoption of our method, ii) explicitly includes survival information and survival time to mitigate bias in the censoring settings, and iii) is free of hyperparameter tuning to decrease the computational requirements in practice.

The presence of censorship in data limits the applicability of commonly used fairness definitions introduced in the existing fairness-aware studies. To fill this gap, we introduce two fairness metrics specifically account for model unfairness in the present of censorship to help with practitioners and policy makers arriving to fair decisions.

Concordance imparity. Motivated by the previously discussed ProPublica investigation on clinical prediction models [8], we first propose the concordance imparity (CI) to measure whether the model under consideration has systematically underperformed on certain population. Formally, we define the CI, mathematically represent as $C_{\triangle}$, as the largest deviation of discriminative abilities across different demographic groups of the model:

Specifically, CI first considers individual level pairwise comparison between model prediction and actual outcomes, i.e., Equation (5) and (6), then measures, at the group level, i.e., Equation (4) and (5), whether the discriminative ability of the model is fairly distributed across groups. The lower the concordance imparity score the fairer the model. Note that different from the previous definitions [21], the survival time and censorship information are explicitly involved in CI to avoid important information loss and introducing substantial bias.

Fair calibration. The concordance imparity depends on the risk score to measure the distinct discriminative capabilities on different demographic groups of the model. Here, we further introduce fair calibration (FC) to evaluate probability values based prediction disparate. In contrast to the risk score based prediction disparate, which is meaningful within the context of other patients’ risk scores, probability values are labels for individual patients with semantic content, thus providing stakeholders and practitioners with an additional navigation for fair decisions.

In practice, FC starts with sorting the predicted probabilities at a specific time $t$ condition on surviving to $t$, i.e., $S(t|x)$, for each individual demographic group as defined by $G$. Within each demographic group, the sorted predicted probabilities are further group into deciles, i.e., $D=10$ number of bins. Suppose there are 100 individuals for one certain demographic group, i.e., $G=g$; each bin would contain 10 individuals belong to this demographic group with their predicted probabilities in ascending order, so are other demographic groups. The final outcome of FC, denoted $C_{\parallel}$, is then evaluated as:

The $L_{g}(S(t|x))$ follows a $\chi^{2}_{B-1}$ distribution, and the model is fair calibrated on the condition that all p-value pertaining to each subgroup pass the test, i.e., a p-value greater than 0.05; otherwise, the model’s predicted probability is deemed to be biased against those being underperformed, i.e., the model’s predicted probabilities only agree with favored communities’ observed event rates or frequencies of the outcome. Note that the same as concordance imparity, fair calibration explicitly involves survival time and censoring information so as to quantify unfairness in the presence of uncertainty effectively.

Random forests construct an array of base learners to increase predictive ability. It has also been extended to handle censored data, and enjoys the merits of automatically addressing the difficulties of restrictive parametric assumptions of other approaches and is capable of modeling nonlinear interactions [44]. However, existing survival random forests aim to optimize for predictive performance and does not take fairness, which we desire to add, into consideration [43]. To alleviate this limitation, we propose Survival Universal Random Forests (SURF) to jointly consider fair data encoding and discrimination reduction for fair forests induction by: i) introducing a new accuracy-driven and fairness-oriented splitting criterion to select the potential fair splitting candidates in the presence of censorship, ii) illustrating the way to enable the construction of the new fair random forests under censorship (c.f. Section IV-C).

In the absence of censorship, the information gain and Gini impurity are normally used to measure the certainty on class labels during the induction of the tree for classification performance [50]. When censorship is present, which brings uncertainty on the class labels, the survival difference between splitting nodes can be instead used to measure the impurity. To explicitly involve survival time and censoring information, we use the logrank test [51] to distinguish the survival difference, denoted $S_{\triangle}$, between different groups:

We then propose a new fair splitting criterion that takes both predictive performance and fairness into consideration. We define the conjunctive criterion Universal Survival Difference (USD), denoted $S_{\vee}$, as:

Intuitively, USD jointly considers the predictive performance by maximizing the internode-wise overall survival difference, i.e., a large value of the minuend, as well as unfairness reduction by minimizing the intranode-wise survival difference among different demographic subgroups, i.e., the smaller subtrahend value, thus motivating fair split by giving priority to splitting candidates that ensures predictive performance while preventing from systematically underperforming on certain population simultaneously. The use of $log$ form in USD is for smoothing. In addition, such a combination of multiple factors is also advantageous when factors are not in the same scale which means one can be dominated by the other.

This fair splitting criterion explicitly considers survival time and censorship information now gives us a means to induce fair decision trees in the presence of censorship, and thus build Random Forests under uncertainty. We emphasize that this approach to promote fair splitting has no tunable parameters as given. This is to retain the desirable property of decision trees in that they often “just work” [50].

With the tailored fair splitting criterion specifically accounts for censoring, we now introduce a corresponding learning algorithm, Survival Universal Random Forests (SURF), following the general idea of random forests to generate tailored forecasts while providing fair risk predictions. The pseudocode of SURF is illustrated in Algorithm 1.

The algorithm specifically works as follows: for each ensemble member of SURF, a bootstrap sample from the censored and discriminated dataset $X$ is first selected where $X^{(i)}$ denotes the $i$th bootstrap (line 1-2). When growing the ensemble member, the candidate splitting attributes at each node are restricted to some randomly selected subset of the whole feature space to decrease the correlation between trees in the ensemble (line 4). From fairness point of view, the randomness introduced by such restriction also limits the biased correlation inherited in the data. Line 5 then performs the splitting test related calculation based on the newly proposed USD to maximize the survival difference of all demographic groups rather than certain population. When the best splitting attribute in the subset has been selected, line 6 splits the node, causing each ensemble learner to grow. As selecting which feature to split is the most computationally expensive aspect of decision tree construction, narrowing the set of features further decreases the computational requirements of SURF. SURF is in full size when all terminal nodes of each base learner, e.g, $SURF_{i}$, contain less than $d_{0}>0$ unique event of interest (line 3).

With SURF being inducted, it is ready for fair risk predictions. SURF predicts the risk as the cumulative hazard function $H(t|x)$ to have a direct interpretation of the expected number of events, and it is the intermediate function between hazard and survival functions for direct derivation when needed. Formally, the risk score is estimated by the Nelson-Aalen estimator [52] as:

Armed with the previously introduced fairness notions and debiasing algorithm explicitly considering survival time and censoring information, quantifying and guaranteeing unfairness in the presence of censorship becomes feasible. In addition, it is also of practitioners and policy makers’ interests to have an insight into the fairness-performance. However, due to censorship, existing fairness theoretical analyses are not applicable to understand the interplay between fairness and censorship. Here, we further provide a versatile geometric formalism to study fairness under uncertainty.

To this end, we formulate the fairness diagnostic as a fairness with uncertainty confusion tensor encoding the information needed to study the fair discriminative ability, i.e., concordance imparity, of the model, which provides a general perspective for understanding unfairness under uncertainty. In specific, the fairness with uncertainty confusion tensor is the stack of confusion matrices for the sensitive attribute $G$, as shown in Table I. For simplicity, we assume that $G$ is a binary attribute, i.e., $G\in\{0,1\}$.

Let us denote the elements of fairness with uncertainty confusion tensor as ${N}_{G}^{a}$, ${N}_{G}^{b}$, ${N}_{G}^{c}$ and ${N}_{G}^{d}$ as well as ${M}_{G}^{a}$, ${M}_{G}^{b}$, ${M}_{G}^{c}$ and ${M}_{G}^{d}$ (abbreviations in align with Equation 6), each element with subscripts indicating the value of $G$. We further denote $P_{G}={M}_{G}^{a}+{M}_{G}^{b}+{M}_{G}^{c}+{M}_{G}^{d}$, $I_{G}={N}_{G}^{a}+{N}_{G}^{b}+{N}_{G}^{c}+{N}_{G}^{d}$ and $C_{G}={M}_{G}^{b}+{M}_{G}^{c}$ be the number of pairwise individuals in each group $G\in\{0,1\}$ pertaining permissible, impermissible and concordant pairs, respectively. Assume $P_{G}$, $I_{G}$ and $C_{G}$ are known constants. Unraveling the fairness with uncertainty confusion tensor, we can formulate concordance imparity as:

We show below that how fair/unfair the model could appear in the presence of censorship, i.e., how censorship could affect fairness notion calculation, based on “floor” outcome and “ceiling” outcome possible.

Let us first consider the “floor” outcome– all impermissible pairs, e.g., $I_{G}$, become permissible with all censored individuals experience immediate event of interest, i.e., $\delta$ becomes 1 for those individuals with $\delta=0$ and their censored time $t$ now becomes the actual event time. Under this floor circumstance the CI becomes:

• •

  Sub-scenario 1: $\frac{C_{0}}{P_{0}}=\frac{I_{0}^{con}}{I_{0}}$ and $\frac{C_{1}}{P_{1}}=\frac{I_{1}^{con}}{I_{1}}$.

  In this case, $\lfloor C_{\triangle}\rfloor=\left|\frac{C_{0}+\frac{C_{0}*I_{0}}{P_{0}}}{P_{0}+I_{0}}-\frac{C_{1}+\frac{C_{1}*I_{1}}{P_{1}}}{P_{1}+I_{1}}\right|=\left|\frac{C_{0}(1+\frac{I_{0}}{P_{0}})}{P_{0}+I_{0}}-\frac{C_{1}(1+\frac{I_{1}}{P_{1}})}{P_{1}+I_{1}}\right|=\left|\frac{C_{0}(1+\frac{I_{0}}{P_{0}})}{P_{0}(1+\frac{I_{0}}{P_{0}})}-\frac{C_{1}(1+\frac{I_{1}}{P_{1}})}{P_{1}(1+\frac{I_{1}}{P_{1}})}\right|=\\ ~{}\left|\frac{C_{0}}{P_{0}}-\frac{C_{1}}{P_{1}}\right|$

  That is to say CI stays unchanged in this case. In practice, this suggests that the independence of model prediction with censorship. Practitioners and stakeholders can therefore interpret the level of unfairness of the model under consideration with more confidence.

• •

  Sub-scenario 2: $\frac{C_{0}}{P_{0}}=0$ and $\frac{C_{1}}{P_{1}}=1$.

  In this case, the uncertainty affect the fairness calculation the most and could lead to the most deviated CI score from the original CI score in the presence of censorship. Sufficient care must be taken to ensure the extra unfairness possible as the result of the censorship when deploying social sensitive applications.

• •

  Sub-scenario 3: $\frac{C_{0}}{P_{0}}=0$ and $\frac{C_{1}}{P_{1}}=0$.

  In contrast to the sub-scenario 2, the uncertainty, in this case, does affect the fairness calculation but uniform in direction. Practitioners and stakeholders can have this in mind considering real-world’s socially sensitive impacts.

• •

  Sub-scenario 4: assume certain distribution with $\frac{C_{0}}{P_{0}}$ and $\frac{C_{1}}{P_{1}}$, for example the binomial distribution.

  The assumed distribution on censorship in conjunction with existing CI score in the presence of censorship can therefore provide additional confidence interval with respect to the range of the CI score in the presence of censorship.

In contrast to the previous “floor” outcome, the second “ceiling” outcome also presents all impermissible pairs become permissible but all censored individuals now have an infinite event time of interest instead, i.e., $\delta$ also becomes 1 for those individuals with $\delta$ = 0 but their censored time $t$ becomes infinite instead. Under this floor circumstance the concordant elements of $\lceil C_{\triangle}\rceil$ change to the other way around, i.e., $N_{0}^{con}=N_{0}^{a}+N_{0}^{d}$ and $N_{1}^{con}=N_{1}^{a}+N_{1}^{d}$ with all previously impermissible pairs, e.g., $I_{G}$, become permissible as well. In addition, the censorship of longer survival time also makes difference and should be considered to form the new uncertainty tensor. Other than these, the previous discussion on “floor” outcome still applies and can be analyzed similarly to help the practical application deployment.

We validate our proposed SURF on three real-world censored datasets with socially sensitive concerns and diverse characteristics¹¹1The code and data are publicly available at
https://github.com/vanbanTruong/censoredFairness. Table II provides a summary description of them. Note that survival time and censoring information are explicitly included in our study to specifically account for censorship.

The ROSSI dataset pertains to persons convicted then released from Maryland state prisons, who were followed up for one year after release [53]. Among the total of 432 released convicts engaging in an experimental treatment, half of them were given financial aid and the rest of them did not receive aid. The task is then to predict the reoffending risk score of convicted criminals as described by 9 features, including the sensitive attribute “race” with black being the deprived group and other being the favored group.

The landmark algorithmic unfairness COMPAS dataset has a similar learning task but is considerably larger with 10,325 convicts from Broward County [54]. The COMPAS dataset consists of 14 features with “race” being the sensitive attribute and the African American defining the deprived group in contrast to other as the favored group. The COMPAS dataset also shares a similar 73% censored rate with the ROSSI dataset.

The KKBOX dataset is created from the WSDM-KKBOX’s Churn Prediction Challenge 2017 [55]. Specially, the task is to predict a user’s risk score of canceling his/her streaming music subscription from KKBOX. Compared with the previous two datasets, this is the largest number dataset we experiment with along with a lower censored rate of 34.7%. The total 2,814,735 users are described using the same 18 features developed by the winning Kaggle team, and gender is used as the sensitive attribute with female being the sensitive value.

We compare our method with the representative survival models and recent survival models with fairness constraints based on a set of typical survival analysis evaluation metrics as well as our proposed fairness notions considering censorship measuring their fair risk prediction capabilities.

Evaluation Metrics. In addition to the proposed fairness measures considering censorship (c.f. Section IV-A), in our evaluation we also report the following widely used survival analysis evaluation metrics: i) the C-index, which is an accuracy measure equals to the area under ROC curve (AUC) in the absence of censorship [56], ii) the Brier score in measuring the mean squared error between the probability estimations assigned to possible outcomes and the actual outcome [57], iii) the Time-dependent AUC, which is a function of time testing the discriminative capability of a model when distinguishing individuals experienced the event of interest from those have not experienced till time $t$ [58]. Among them, while the model with a lower Brier score is desired, the higher C-index and Time-dependent AUC scores, the better.

Comparison Methods. The proposed SURF is designed to address highly underexplored discrimination in the presence of censorship. To evaluate its design, we consider baselines from the following four perspectives: i) two recent proportional hazards assumption based fair survival models IDCPH and GDCPH [21], which are the only works for fair survival analysis problem to the best of our knowledge (note that only the most competitive ones are discussed among different variants proposed therein), ii) the mostly widely used CPH for survival analysis [38], iii) the state of the art random forests on survival analysis RSF [43] and deep neural network based DeepSurv [39] as additional baselines. Other competing fairness methods are not considered as none of them is capable of addressing fairness in the presence of censoring.

We present both quantitative and qualitative experiment results that illustrate and confirm the utility of SURF in making fair decisions under uncertainty.

Fair risk predictions. A set of fairness metrics in the presence of censorship and survival analysis evaluations are tested on different models with the 5-fold cross validation results summarized in Table III.

As can be seen clearly our new SURF dominates all other baselines in terms of minimizing discrimination while maintaining a competitive predictive performance, which verifies the necessity of its debiasing design while accounting for censorship. On the other hand, the lack of consideration for survival time and censoring information as well as task-specific similarity metric among individuals result in the inferior performances of other baselines, although they are proposed for fairness in censoring settings. This also verifies our previous discussion that fairness in the presence of censorship cannot be trivially solved by a simple combination of existing techniques.

As p-values are not intended to be ranked, the fair calibration cannot rank models besides suggesting whether one model is calibrated across different demographic communities. We therefore further visualize the predicted probabilities against the true probability observed by KM to qualitatively evaluate the fairness of such predictions, as shown in Figure 1. Note that for space constraint, only the fair calibration plots for deprived community is presented. As we can see, the dark bars, are roughly the same height as the red ones, suggesting SURF’s predicted probabilities are representative of the deprived community’s true probabilities.

In addition, we also perform an ablation study, testing whether the debiasing component of SURF worked to benefit the improved performance of the deprived group. To this end, we further break down the predictive performance by the sensitive value that defines the deprived community and favored community and with and without our fairness constraints (e.g., SURF and SURF-). The predictive performance confusion matrix are shown in Table IV. As one can see, SURF attends to the deprived community with improved predictive ability and characterization, which verifies its anti-discrimination capability. In addition, the improved overall predictive performance also shows the merit of such anti-discrimination design for fair risk predictions as a whole.

Time Complexity. We illustrate and analyze the time complexity of our proposed SURF against other baseline methods, as shown in Figure 2, where the y-axis is the logarithm of the runtime in seconds for ROSSI dataset and minutes for the other two datasets. As one can see, SURF enjoys the merit of computational efficiency as it follows the idea of tree based method to decrease the computational requirements in practice, while the other baseline IDCPH becomes computational expensive, thus limiting its applicability.