Fairness-aware Model-agnostic Positive and Unlabeled Learning

Positive and Unlabeled Learning is a variant of the classical classification setup where the training data consists of only positive and unlabeled (PU) examples. It fits within the long-standing interest in developing learning algorithms that do not require fully supervised data. The PU data can originate from two scenarios. One is called the single-training-set scenario (Elkan and Noto, 2008) where the data come from one single training set; the other is called the case-control scenario (Ward et al., 2009) where the data come from two independently drawn datasets, one with all positive examples and one with all unlabeled examples. The single-training-set scenario has received substantially more attention in the literature (Bekker and Davis, 2020). Most PUL methods can be divided into the following three categories. Two-step techniques (He et al., 2018; Ienco and Pensa, 2016) first identify reliable negative examples and then conduct classical classification. Biased learning (Shao et al., 2015; Hsieh et al., 2015; Claesen et al., 2015) considers PU data as fully labeled data with class label noise for the negative class. Class prior incorporation (Elkan and Noto, 2008; Kiryo et al., 2018; du Plessis et al., 2014) modifies standard learning methods using the class prior and learns weights for all examples. However, none of the existing work in PUL explores the fairness issue. As shown in our experiments (Subsection 5.2), current PUL methods exhibit unfairness against subgroups, which will result in potential discrimination in real-world applications.

The existing studies on fairness in classification have focused on two key issues: how to formalize the fairness metric in classification, and how to design efficient algorithms that strike a desirable trade-off between classification performance and fairness. To seek equality between different populations, a number of works have been proposed to control group fairness. Equal Opportunity (Hardt et al., 2016) requires the same true positive rates among groups and Equalized Odds (Berk et al., 2018) simultaneously considers false positive rates. Equalizing Disincentives (Feldman et al., 2015) requires the difference of two metrics to be equal across the groups. Using these metrics, a variety of fairness-aware algorithms in classification have been proposed under different learning settings. (Zafar et al., 2017; Hardt et al., 2016; Zemel et al., 2013; Agarwal et al., 2018; Song et al., 2019) focused on the supervised learning setting where the learning algorithms have access to the class labels of all training examples. Since they highly rely on supervised data, even if we adjust their decision boundary with a standard PUL technique, the unlabeled data still cannot contribute to algorithmic fairness explicitly. In a more realistic scenario where both labeled and unlabeled examples are given, (Bird et al., 2020) devised a linear transformation pre-processing technique to remove the underlying discrimination. (Zhang et al., 2020) incorporated the fairness constraint into the original training process. (Chzhen et al., 2019) post-processed the output conditional probability to improve fairness by recalibration with the unlabeled data. Although these methods do not rely on labeled data as much as the fully supervised methods, both positive and negative labeled samples are necessary for their algorithms. The most related work to us is (Chzhen et al., 2019) where they limit the fairness criterion to Equal Opportunity. However, the unlabeled examples can only be used to estimate the fairness threshold in their method. How to properly use the positive-only and unlabeled data in fair classification is still under-explored. In this paper, we instead explore how to make the best use of PU data to boost both classification performance and algorithmic fairness.

As stated before, the unlabeled samples in PUL mainly come from the following two sources: (1) It is truly a negative example; (2) It is a positive example, but simply was not selected by the labeling mechanism. In order to enable learning with PU data, it is necessary (Bekker and Davis, 2020) to make assumptions about either the labeling mechanism, the class distributions in the data, or both. We base our work on the most frequently used assumption (Lee and Liu, 2003) in PUL:

Under this assumption, the set of labeled examples are i.i.d. samples from the positive distribution. The label frequency $c$ plays an important role in the single-training-set scenario (Elkan and Noto, 2008) we consider here. Define the regression function $f(X,S):=\mathbb{P}(L=1\mid X,S)$, i.e., the probability of an example $(X,S)$ being labeled. Then we have the following lemma regarding the constant $c$:

The proof can be found in Appendix A. This lemma shows how we can obtain the probability of an example being positive from $f$. Next, we further incorporate fairness into the classification problem and show how to get the optimal fair classifier theoretically and empirically.

To obtain the optimal fair classifier, we study the following problem:

For EO, $\mathcal{Y}=\{0,1\}$. When $y=1$, the constraint requires the same true positive rates (TPR), that is $TPR^{(1)}=TPR^{(0)}$, where we use the superscript to identify the sensitive attribute $S$. Similarly, when $y=0$, the constraint requires the same false positive rates (FPR), that is $FPR^{(1)}=FPR^{(0)}$. For EOP, $\mathcal{Y}=\{1\}$ and it only requires $TPR^{(1)}=TPR^{(0)}$. In our later derivation, we will focus on EO while discussing how our results can easily accommodate EOP.

Using the misclassification risk $\mathcal{R}(g)=\mathbb{P}(g\neq Y)$ and based on Lemma 1, we can solve problem (1) and get the following result:

Here, $\lambda_{1}$ is the Lagrange multiplier for the same TPR constraint, and $\lambda_{2}$ is for the same FPR constraint. Since $g(X,S)\in\{0,1\}$, we can rewrite the Lagrange function of Problem (1) into expressions of $g(X,S)$ and then get the above equations. The detailed derivation is shown in Appendix B. Note that by incorporating $c$ explicitly, our designed minimizer can boost performance and meanwhile reduce discrimination for PU data.

With Lemma 2, the problem of finding the optimal fair classifier in PUL is equivalent to obtaining the optimal value of $\boldsymbol{\lambda}$ in Equation (2). To do this, we introduce an assumption on the regression function $\mathbb{P}(Y=1\mid X,S)$, i.e., the probability of an example $(X,S)$ being positive. For notation simplicity, we abbreviate it as $p^{+}_{X,S}$.

This Assumption requires that the random variable $p^{+}_{X,s}$ does not have atoms for each $s\in\{0,1\}$. This is proved achievable by many distributions (Yan et al., 2018; Sadinle et al., 2019; Denis and Hebiri, 2020). Based on this assumption, we introduce the optimal $\lambda^{*}$:

Based on the theoretical optimal classifier in Equations (2) and (3), we are now ready to introduce the proposed FairPUL framework for empirically estimating the optimal fair classifier. Given an existing classifier, FairPUL will modify its output for PUL data while reducing unfairness, and output the fair version of the classifier with a low misclassification risk. In the next subsections, any notation (e.g., $c$) with a hat denotes its estimated counterpart (e.g., $\hat{c}$).

In the PUL setting, the training data consists of two parts, the labeled (positive) data set $D_{L}$ and the unlabeled data set $D_{U}$. A classifier $\hat{f}$ can be constructed to estimate the probability of an example being labeled by treating $D_{L}$ as positive examples and $D_{U}$ as negative ones. Let $V$ be the validation set that is drawn from the overall distribution in the same manner as the training set and $P$ be the subset of examples in $V$ that are labeled (and positive). We can estimate the label frequency $c$ as follows:

where $n_{P}$ is the cardinality of $P$. If $\hat{f}$ is trained well enough, $\hat{f}(x,s)$ provides a precise estimate of labeling probability. Since every example in $P$ is positive, we have $\hat{f}(x,s)\approx c$ based on Total Probability Theorem and SCAR assumption. Although this ideal case hardly holds in practice, the average estimation is a good choice for estimating the label frequency $c$ with low variance.

Since the ideal $\boldsymbol{\lambda}^{*}$ should satisfy Equations (3), we minimize the difference between its two sides. Based on the rule of conditional probability, this is equivalent to minimizing unfairness defined as follows:

We can get their empirical versions by substituting all the unknown terms with their empirical estimators:

Then we can obtain the estimator of $\boldsymbol{\lambda}^{*}$ as:

where $\hat{\Delta}$ can be either $\hat{\Delta}_{EO}$ or $\hat{\Delta}_{EOP}$ to satisfy EO or EOP respectively. $\hat{g}^{*}_{\boldsymbol{\lambda}}$ is the estimated optimal fair classifier defined in a similar way as Equation (2) by replacing all the unknown terms with their empirical estimators.:

We adopt the Simulated Annealing strategy to search for the optimal $\hat{\boldsymbol{\lambda}}$.

Alg. 1 summarizes our proposed FairPUL framework. It takes the training and validation sets as well as a base model $\hat{f}$ as input, and outputs a fairness-aware classifier with a low misclassification risk. The base regressor $\hat{f}$ is trained with $D_{L}$ and $D_{U}$. It can be any classifier that outputs the conditional probability of an example being labeled. First, an estimator of $c$ can be learned on the validation set with $\hat{f}$ in Step 1. Then we use Simulated Annealing to search for the best $\hat{\lambda}$ to minimize unfairness for PUL data in Step 2 and 3. We finally compute the empirical optimal fair classifier accordingly in Step 4.

Consistency is a desired property for a classifier in asymptotic theory. It guarantees that with the increase in the amount of data, the estimation will converge to the true value. In this subsection, we show that the proposed framework FairPUL is consistent, that is, it asymptotically satisfies the fairness criterion and its risk converges to the one of the theoretical optimal fair classifier.

First of all, following (Chzhen et al., 2019), we make the following realistic assumptions on the estimator of $p^{+}_{X,S}$:

The first part of the assumption requires the estimator to be consistent in $l_{1}$ norm. This can be achieved by a variety of estimations for different regression functions as shown in the literature (Devroye, 1978; Audibert et al., 2007; Van de Geer et al., 2008). The second part means that $\mathbb{E}_{X|S=s}[\hat{p}^{+}_{X,S}]$ is lower bounded by a certain positive term which vanishes as $n_{U}$ and $n_{L}$ go to infinity. This can be easily achieved by slightly modifying any existing consistent estimator. The last part is similar to Assumption 2.

Based on these realistic assumptions on $p^{+}_{X,S}$, next we establish the statistical consistency of FairPUL.

In this section, we compare the post-processing FairPUL with the in-processing method proposed by (Agarwal et al., 2018) and the pre-processing method in (Bird et al., 2020). The in-processing method is introduced in Section 5.2. The pre-processing method is a widely-used technique which transforms the non-sensitive features to remove their correlation with the sensitive feature while retaining as much information as possible. We report the average results of 10 independent runs on COMPAS data set under labeling rates of 1.0 and 0.9 in Table 2. Results on German can be found in Appendix F. In the fully labeled setting, the in-processing and pre-processing methods sacrifice much classification performance for better fairness. FairPUL achieves a good balance instead. Under labeling rate 90%, FairPUL significantly outperforms all the baselines in both metrics. Compared with the in-processing method, FairPUL only needs black-box access to the predictions and sensitive attribute information without requiring access to the actual algorithms and ML models. While the pre-processing method only needs to transform the data set before the actual model takes effect, it leads to classifiers that still exhibit substantial unfairness in practice. So our proposed FairPUL is more flexible and also effective in fairness-aware PUL.