{'fraction_non_alphanumeric': 0.03445892322265175, 'fraction_numerical': 0.009805176518778321, 'mean_word_length': 4.829279212057902, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Towards Fair Classifiers Without Sensitive Attributes: Exploring Biases in Related Features

Despite the rapid development and great success of machine learning models, extensive studies have exposed their disadvantage of inheriting latent discrimination and societal bias from the training data. This phenomenon hinders their adoption on high-stake applications. Thus, many efforts have been taken for developing fair machine learning models. Most of them require that sensitive attributes are available during training to learn fair models. However, in many real-world applications, it is usually infeasible to obtain the sensitive attributes due to privacy or legal issues, which challenges existing fair-ensuring strategies. Though the sensitive attribute of each data sample is unknown, we observe that there are usually some non-sensitive features in the training data that are highly correlated with sensitive attributes, which can be used to alleviate the bias. Therefore, in this paper, we study a novel problem of exploring features that are highly correlated with sensitive attributes for learning fair and accurate classifiers. We theoretically show that by minimizing the correlation between these related features and model prediction, we can learn a fair classifier. Based on this motivation, we propose a novel framework which simultaneously uses these related features for accurate prediction and enforces fairness. In addition, the model can dynamically adjust the regularization weight of each related feature to balance its contribution on model classification and fairness. Experimental results on real-world datasets demonstrate the effectiveness of the proposed model for learning fair models with high classification accuracy.


INTRODUCTION
With the great improvement in performance, modern machine learning models are becoming increasingly popular and are widely used in decision-making systems such as medical diagnosis [2] and credit scoring [8]. Despite their great successes, extensive studies [13,26,34] have revealed that training data may include patterns of previous discrimination and societal bias. Machine learning models trained on such data can inherit the bias on sensitive attributes such as ages, genders, skin color, and regions [3,9,15]. For example, a study found strong unfairness exists in a Criminal Prediction system used to assess a criminal defendant's likelihood of becoming a recidivist [17]. The system shows a strong bias towards people with color, tending to predict them as recidivist even when they are not. Thus, hidden biases in a machine learning model could cause severe fairness problems, which raises concerns on their real-world applications, especially in high-stake scenarios.
Various efforts [11,18,28,35] have been taken to address the fairness issue of current machine learning models. For example, [11,19] pre-process the data to remove discrimination in training. [9,35] design special regularization terms to ensure that the prediction output is insensitive w.r.t sensitive attributes. And [15,27] postprocess prediction results on instances of unfair classes. Despite their superior performance, all the aforementioned approaches require that sensitive attributes are available for removing bias. However, for many real-world applications, it is difficult to obtain sensitive attributes of each data sample due to various reasons such as privacy and legal issues, or difficulties in data collection [5,21].
Tackling fairness issue without sensitive attributes available is challenging as we lack supervision to preprocess the training data, regularize the model or post-process the predictions. There are only very few initial efforts on learning fair classifiers without sensitive attributes [5,21,33]. Yan et al. [33] use a clustering algorithm to form pseudo groups to approximate real protected groups. Lahoti et al. [21] propose to use an auxiliary module to find computationally-identifiable regions where model under-performs, and optimize this worst-case performance. However, these works are often found to be ineffective in achieving fairness with demographics [21]. In addition, the groups or regions found by these approaches may not be related to the sensitive attribute we want to be fair with. For example, we might want the model to be fair on gender; while the clustering algorithm gives groups of race. Thus, more efforts need to be taken to address the important and challenging problem of learning fair models without sensitive attributes.
Though the sensitive attribute of each data sample is unknown, we observe that there are usually some non-sensitive features in the training data that are highly correlated with sensitive attributes, which can be used to alleviate the bias. Previous works [5,17] observed that unfairness persists even when sensitive attributes are not used as input, which indicate that biases are embedded in some non-sensitive features used for training models. These non-sensitive features are highly correlated with sensitive attributes, which makes the model biased. We call such features as Related Features. These correlations arise from various reasons, such as biases in data collection, or interplay of an underlying physiological difference with socially determined role perception [4]. For example, Vogel and Porter [30] find that there exist striking differences in age distributions across racial/ethnic groups in US prisons. The Hispanic and black populations have a larger portion of individuals at younger ages, hence age is correlated with race in this field. In practice, common sense and prior domain knowledge can help to identify the related features given that we want to have a fair model on certain sensitive attributes. In addition, for different sensitive attribute such as race or gender, we can specify different sets of related features. With these related features identified, we would be able to alleviate the fairness issue. One straightforward way is to discard related features for training a fair model. However, it will also discard important information for classification. Thus, though promising, it remains an open question of how to effectively utilize related features to learn fair models with high classification accuracy. Therefore, in this paper, we study a novel problem of exploring related features for learning fair and accurate classifiers without sensitive attributes. In essence, we are faced with three challenges: (i) how to utilize these related features to achieve fairness; (ii) how to achieve an optimal trade-off between accuracy and fairness; (iii) when given related feature sets contains misidentified features or are incomplete, how to adjust the usage of them. In an attempt to solve these challenges, we propose a novel framework Fairness with Related Features (FairRF). Instead of simply discarding related features, the basic idea of FairRF is to use the related features as both features for training the classifier and as pseudo sensitive attributes to regularize the behavior of it, which help to learn fair and accurate classifiers. We theoretically show that regularizing the model using related features can achieve fairness on sensitive attribute. Furthermore, to balance the classification accuracy and model fairness, and cope with the case when identified related attributes are inaccurate and noisy, FairRF can automatically learn the importance weight of each related feature for regularization in the model. The main contributions of the paper are as follows: • We study a novel problem of exploring related features to learn fair classifiers without sensitive attributes; • We theoretically show that by adopting related features to regularize the model, we can learn fairer classifier; • We propose a novel framework FairRF which can simultaneously utilize the related features to learn fair classifiers and adjust the importance weights of each related feature; and • We conduct extensive experiments on real-world datasets to demonstrate the effectiveness of the proposed method for fair classifiers with high classification accuracy.

RELATED WORK
To address the concerns of fairness in machine learning models, a number of fairness approaches are proposed. They can be generally split into three categories: (i) individual fairness [9,20,22,36], which requires the model to give similar prediction to similar individuals; (ii) group fairness [9,15,39], which aims to treat the groups with different protected sensitive attributes equally; (iii) Max-Min fairness [16,21,38], which tries to maximize the minimum expected utility across groups. We focus on group fairness in this work. Extensive works have been conducted to for group fairnessaware machine learning [3,9,15,21,23,36,39]. Based on the stage of applying fairness in training, these algorithms can be generally split into three categories: pre-processing approaches [19,32,39], inprocessing approaches [35,37], and post-processing approaches [15,27]. Pre-processing approaches modify the training data to reduce the historical discrimination in the dataset. For instance, the bias could be eliminated by correcting labels [18,39], revising attributes [11,19], generating non-discriminatory data [28,32], and obtaining fair representations [3,6,10,23,24,36]. In-processing approaches revise the training of the state-of-the-art models to achieve fairness. More specifically, they apply fairness constraints or design a objective function considering the fairness of predictions [9,35,37]. Finally, the post-processing approaches directly change the predictive labels of trained models to obtain fair predictions [15,27].
Despite their ability in alleviating the bias issues, aforementioned methods generally require the sensitive attributes of each data sample available to achieve fairness; while for many real-world applications, it is difficult to collect sensitive attributes of subjects due to various reasons such as privacy issues, legal problems and regulatory restrictions. The lacking of sensitive attributes of training data challenges the aforementioned methods [3]. Investigating fair models without sensitive attributes is important and challenging, and it is still in its early stage. There are only a few works on this direction [16,21,33]. One branch of approaches [16,21] investigates fairness without demographics via solving a Max-Min problem. For instance, Lahoti et al. [21] proposes adversarial reweighted learning that leverages the notion of computationally-identifiable errors to achieve Rawlsian Max-Min fairness without sensitive attributes. However, these methods are only effective for achieving Max-Min fairness. The other branch [7,33] addresses this missing sensitive attribute scenario via providing pseudo group splits. For instance, Yan et al. [33] pre-processes the data via clustering and uses obtained groups as the proxy. However, the conformity between obtained groups from these approaches and real protected groups are highly dependent on data distribution. The proposed FairRF is inherently different from the aforementioned approaches: (i) We study a novel problem of exploring features that are highly related to the unseen sensitive ones for learning fair and accurate classifiers. Obtaining these features requires just a little prior domain knowledge, and it prevents the difficulty and instability of previous approaches in detecting protected groups [21,33]; and (ii) We theoretically show that by regularizing the model prediction with the related features that are highly corrected with sensitive attributes, we can learn a fair model w.r.t the sensitive attribute. In addition, our experimental results show that the given related feature set can be incomplete or noisy.
Throughout this paper, matrices are written as boldface capital letters and vectors are denoted as boldface lowercase letters. For an arbitrary matrix M ∈ R × , denotes the ( , )-th entry of M while m and m mean the -th row and -th column of M, respectively. Capital letters in calligraphic math font such as P are used to denote sets or cost function.
Let X ∈ R × be the data matrix with each row x ∈ R 1× as an -dimensional data instance. We use F = { 1 , . . . , } to denote the features and x 1 , . . . , x are the corresponding feature vectors, where x is the -th column of X. Let y ∈ R be the label vector, where the -th element of y, i.e., , is the label of x . Following existing work on fair machine learning models [21], we focus on binary classification problem, i.e., ∈ {0, 1}. Given X and y, we aim to train a fair classifier with good classification performance.
Extensive studies [17,21] have revealed that historical data may include previous discrimination and societal bias on sensitive attribute such as ages, genders, skin color, and regions. Though sensitive attributes are not used as features, i.e., ∉ F , a subset of none-sensitive features F ∈ F are highly correlated with sensitive attributes, making machine learning models trained on such data inherit the bias. For example, in dataset containing US criminal records [17], racial information is taken as sensitive. Although it is unseen, trained model could still be unfair as distribution of racial groups population may be leaked from the distribution of ages [30].
In many real-world applications, sensitive attributes of data samples are unavailable due to various reasons such as difficulty in data collection, security or privacy issues. It challenges existing fair machine leaning approaches that require sensitive attributes of data samples for fair models. Though sensitive attribute of each data sample is unknown, since the bias is caused by the subset of features F that are highly correlated with , F can provide alternative supervision to learn fair models. Therefore, we aim to explore the utilization of F to help learn more fair model meanwhile maintain high classification performance. The problem is defined as: Problem Definition Given the data matrix X ∈ R × , with corresponding labels y ∈ R , and a predefined feature subset F ∈ F , where each ∈ F called related feature which highly correlates with the unobserved protected attribute , e.g., race or gender, learn a classifier that maintains high accuracy and is fair on .
Note that we assume F ∈ F is given from domain knowledge or experts. In practice, F can be incomplete and noisy. We design FairRF that is able to re-weight each ∈ F , so that it has the potential of remaining effective, as shown in experiments.

PRELIMINARY THEORETICAL ANALYSIS
In this paper, we adopt Pearson correlation coefficient to measure the correlation between two variables, defined as below: Definition 1 (Pearson Correlation Coefficient). Pearson correlation coefficient measures the linear correlation between two random variables and as: where is the mean and is the standard deviation of .
Next, we will show a theorem on the propagation property of Pearson correlation coefficient, which justifies our motivation of using F to regularize model predictions in the case of absent . Below, we first present a rule depicting the relation of three included angles in space, which is the basis of our proof. Lemma 1. Given a unit sphere centered at origin , , and are three points on the surface of the sphere. Assume that the angle = 1 and the angle = 2 , then the cosine value of angle is within: Proof. From Spherical law of cosines [12], we can know that: where ′ corresponds to the angle opposites in spherical triangle . As all angles are in the scale [0, ], we can directly induce: which completes the proof. □ Next, we will show the relationship between Pearson correlation coefficient and cosine similarity of two variables. Lemma 2. Given two random variables , , Pearson correlation coefficient between them can be calculated as the cosine distance between x ′ and y ′ , where x ′ is an infinite-length vector constructed by sampling z-score value of , i.e., ′ = − and is the -th sample. Similarly, ′ = − .
Proof. This can be easily proven by re-writing the form of Pearson correlation coefficient as: which completes the proof. □ With these preparations, we can now turn to our main theorem: Proof. The proof can be developed via the following steps: (1) Cosine similarity between x ′ and y ′ shows the cosine value of included angle between them. Hence, based on Lemma 2, we can learn that the cosine of angle between x ′ and y ′ is ( ) and that of angle between y ′ and z ′ is ( ) from the given correlation coefficients.  Basing on theorem 1, we can show how the constraint of correlation scale is propagated from F to in Theorem 2, which theoretically proves our idea. Theorem 2. Let and represent an input feature and sensitive attribute, respectively. Letˆdenotes the variable of model's prediction. Assume that is highly correlated with , i.e., , is larger than a positive constant . If the model is trained to make ,ˆn ear 0, i,e, . Theorem 2 can be easily proved based on Theorem 1. From it, we can see that when ≈ 1 and ≈ 0, ,ˆw ould also approximate 0. In this way, the prediction would be insensitive towards , achieving fairness w.r.t sensitive attribute .
We can extend Theorem 2 to the case of utilizing multiple related features simultaneously.
where is the smallest value in { 1 , 2 , ..., }. Note that this range is usually not tight, and high divergence within F would often restrict the range of ,ˆm ore.

METHODOLOGY
In this section, we present the details of the proposed framework FairRF. The basic idea is using the regularization on correlated features F as the surrogate fairness objective. With the motivation theoretically justified in Sec 4, an illustration of FairRF is shown in Figure 1. It is composed of three parts: (i) a base classifier (·) which predicts its labelˆgiven data sample x ; (ii) a covariance regularizer which constrains correlation between F andˆto achieve fairness; and (iii) an importance learning module which adjusts importance score of each related feature ∈ F . Next, we introduce each component in detail.

Base Classifier
The proposed FairRF is flexible to use various classifiers as backbone such as neural networks, logistic regression and SVM. Without loss of generality, we use (·) to denote the base classifier, where is the set of parameters of the base classifier. Following existing work on fairness [21], we consider binary classification. We leave the extension to multi-class classification as future work. For a data sample x , the predicted probability of x having label 1 iŝ Then the binary cross entropy loss for training the classifier (·) can be written as where ∈ {0, 1} is the label of x . Generally, the well trained model is good at classification. However, as shown in previous studies [3,39], the obtained model could make unfair predictions because spurious correlation may exist in the training data between sensitive attributes and labels due to societal bias. Though various efforts have been taken to mitigate the bias [9,15,35], most of them require knowing the sensitive attributes. With the sensitive attributes unknown, to learn fair models, we propose to regularize the predictions using the related features F that are highly correlated with , which will be introduced next.

Exploring Related Features for Fairness
If the sensitive attribute of each data sample x is known, we can adopt to achieve fairness of the classification model by making the prediction independent of the sensitive attributes [9,35]. Let s ∈ R ×1 be the sensitive attribute vector with the -th element of s, i.e., , as the sensitive attribute of x . Similarly, letŷ ∈ R ×1 be the predictions with the -th element being the prediction for x . Following the design in [7,35], the pursuit of non-dependence between predictionˆand sensitive attribute s can be achieved through minimizing the correlation score between them, which can be mathematically written as: where andˆare the mean of s andŷ, respectively. Note that we set constraints directly on the correlation score instead of correlation coefficient, but it can be seen from Eq.1 that it only differs from correlation coefficient by a constant multiplier s ·ˆ. Constraining the scale of this regularization term, s andˆwould be encouraged to have no statistical correlation with each other. However, as sensitive attribute s is unavailable in our problem, directly adopting the above regularization is impossible. Fortunately, from Theorem 2, we can see that if we have a set of non-sensitive features F , with each feature ∈ F , i.e., x , having high correlation with s, then reducing the correlation between x withŷ can indirectly reduce the correlation between s andŷ, which helps to achieve fairness, even though s is unknown. Hence, in FairRF, we apply correlation regularization on each feature ∈ F , in the purpose of making trained model fair towards . Without loss of generality, let the set of features in F be { 1 , . . . , }, where 1 ≤ < . The regularization term is written as where is the weight for regularizing correlation coefficient between x andŷ. R (x ,ŷ) is given as where is the mean of x . Generally, if the correlation between x and s is large, we would prefer large to enforce R (x ,ŷ) to be close to 0, which can better reduce the correlation between s andŷ, resulting in a more fair classifier. If the correlation between x and s is not that large, a small is preferred because under such case, making R (x ,ŷ) close to 0 doesn't help much in making s andŷ independent, but may instead introduce large noise in label prediction. Domain knowledge would be helpful in setting .

Learning Importance of Related Features
One limitation of this approach is the requirement of pre-defined . This information provides prior knowledge and is important for the success of the proposed proxy regularization. However, in real-world applications, it is difficult to get accurate values, and F could be inaccurate. In addition, is also important in balancing the contribution of in model prediction and fairness. Larger will result in the independence between x andŷ, making contributes little in model prediction. Hence, in this section, we propose to learn , allowing the model to automatically adjust its value. Specifically, before learning, each related weight is initialized to a pre-defined value 0 , which serves as an inaccurate estimation of its importance. Then, during training, the value of will be optimized along with model parameters iteratively. As no other information is available, we update by minimizing the total regularization loss, based on the intuition that an ideal surrogate correlation regularization should be achieved without causing significant performance drop. We limit the range of as [0, 1], and the full optimization objective function can be written as follows: (11) where sets the weights of regularization term, and is the set of parameters of the classifier.
Eq.(11) can lead to a trivial solution, i.e., to minimize the cost function, it tends to set corresponding to the smallest R (x ,ŷ) to 1 and others to 0. To alleviate this issue, we add ∥ ∥ 2 2 to penalize being close to 1. Thus, The final objective function of FairRF is where is used to control the contribution of ∥ ∥ 2 2 .

OPTIMIZATION ALGORITHM
The objective function in Eq.(12) is constrained optimization, which is difficult to be optimized directly. We take the alternating direction optimization [14] strategy to update and iteratively. The basic idea is to update one variable with the other one fixed at each step, which can ease the optimization process. Next, we give the details.
Update . To optimize , we fix and remove terms that are irrelevant to , which arrives at This is a non-constrained cost function, and we can directly apply gradient descent to learn . UPDATE . Then, given at the current step, can be obtained through solving the following optimization problem: It is a convex primal problem, and strong duality holds as it follows Slater's condition. For simplicity of notation, we use R to represent R (x ,ŷ). Then, we can solve this problem using Karush-Kuhn-Tucker(KKT) [25] conditions as: In the above equation, and are Lagrange multipliers. From the stationary condition, we can get: Eliminating using complementary slackness, we have: From this condition, we know that = max{0, }. Since =1 = 1, can be computed via solving the following equation: Solving the above equation can be done as follows: we first rank R in descending order as R ′ , i.e., R ′ −1 ≥ R ′ . Assume that is within Then, we have it is a valid solution; otherwise, it is invalid. We do this for every interval and find . With learned, we can calculate as: Training Algorithm. With the updating rules above, the full pipeline of the training algorithm for FairRF can be summarized in Algorithm 1 in the supplementary material.
In this section, we conduct experiments to evaluate the effectiveness of the proposed FairRF in terms of both fairness and classification performance when sensitive attributes are unavailable. In particular, we aim to answer the following research questions: • RQ1 Can the proposed FairRF achieve fairness without sensitive attributes while maintain high accuracy? • RQ2 How would FairRF perform when the provided F contains misidentified related features or is incomplete? • RQ3 How would different choices of hyper-parameters influence the performance of FairRF?
• ADULT 1 : It contains 45, 221 records of personal yearly income, with binary label indicating if the yearly salary is over or under $50 . Gender is considered as sensitive attribute. and we select age, relation and marital status as F . For this dataset, we use race, year and residence as F .
We make the train:eval:test splits as 5 : 2 : 3. Note that for all three datasets, features in F are selected following existing analysis or prior domain knowledge. For example, in COMPAS, biases towards race have been found to exist in score and decile text [17]. The correlation between race and gender is also from reports by U.S. Bureau of Justice Statistics(BJS). Since race is the sensitive attribute of the dataset, we include score, decile text and gender in F .

Baselines.
To evaluate the effectiveness of FairRF, we first compare it with the vanilla model and sensitive-attribute-aware model, which can be treated as the lower and upper bound of our model's performance: • Vanilla model: It directly uses the base classifier without any regularization terms. It is used to show the performance without fairness-assuring algorithm taken. • ConstrainS: In this baseline, we assume that the sensitive attribute of each data sample is known. We add the correlation regularization between sensitive attribute vector s and model outputŷ, i.e., R (s,ŷ). It sets a reference point for the performance of the proposed framework. Note that for all the other baselines and our model, s is unknown.
We also include following representative approaches in fair learning without sensitive attributes as baselines:   Note that the fairness formulation of ARL is different from the group fairness we focus on. ARL [21] is inefficient in obtaining demographic fairness by design, which is also verified by our experiments. Although not working on the same fairness definition, we still include it as one baseline for completeness of the experiment.

Configurations.
For KSMOTE, we directly use the code provided by [33]. For all other approaches, we implement a multi-layer perceptron (MLP) network with three layers as the backbone classifier. The two hidden dimensions are 64 and 32. Adam optimizer is adopted to train the model, with initial learning rate as 0.001.

Evaluation Metrics.
To measure the fairness, following existing work on fair models [29,33], we adopt two widely used evaluation metrics, i.e., equal opportunity and demographic parity, which are defined as follows: Equal Opportunity [26] Equal opportunity requires that the probability of positive instances with arbitrary protected attributes , being assigned to a positive outcome are equal: whereˆis the output of model , representing the probability of being predicted as positive. In the experiments, we report difference in equal opportunity(Δ ): Demographic Parity [26] Demographic parity requires the behavior of prediction model to be fair on different sensitive groups. Concretely, it requires that the positive rate across sensitive attributes are equal: Similarly, in the experiment, we report the difference in demographic parity(Δ ): Equal opportunity and demographic parity measure the fairness from different perspectives. Equal opportunity requires similar performance across protected groups, while demographic parity is more focused on fair demographics. The smaller Δ and Δ are, the more fair a model is. Furthermore, to measure the classification performance, accuracy (ACC) is also reported.

Classification Performance Comparison
To answer RQ1, we fix the base classifier as MLP and conduct classification on all three datasets. For all the baselines, the hyperparameters are tuned via grid search on the validation dataset. In particular, for FairRF, is set to 0.5 on ADULT, 0.8 on COMPAS, and 1.0 on LSAC. is set as 0.15 for COMPAS and 0.3 for other two datasets. More details on the hyperparameters sensitivity will be discussed in Sec 7.5. Each experiment is conducted 5 times and the average performance in terms of accuracy, Δ and Δ with standard deviation are reported in Table 1, Table 2 and Table 3. From the tables, we make the following observations: • Constraining related features can help the model to perform fairer on sensitive groups. For example, compared with vanilla approach in which no fair-learning techniques are applied, FairRF shows a clear improvement w.r.t Equal Opportunity and Demographic Parity across all three datasets; • FairRF improves the fairness without causing significant performance drop, and works stably. No pre-computed clusters are required, and it does not involve training an adversarial model, hence FairRF can get results with less deviation compared to ARL and KSMOTE; • Compared with baselines without sensitive attribute, FairRF is effective for both two fairness metrics; while other approaches such as ARL is able to improve on "equal opportunity", but the performance would drop w.r.t "demographic parity". This is because FairRF is able to learn to balance the fairness and accuracy.

Impact of the Quality of F on FairRF
In this section, we conduct experiment to investigate the impact of the quality of F on the performance of FairRF to answer RQ2. In particular, we consider the following variants of FairRF: • Random: We randomly select five sets of F with the same number of attributes as FairRF. Average results are reported. We use it to show the influence of prior knowledge. • Fix-: The same is adopted for all related features, and its value is not automatically updated during training. Selected related features are exactly the same as those chosen in FairRF. • Top-1: It uses only the most-effective related features. We test all candidates and select the one that achieves highest performance when used as related feature, and report its performance. • ConstrainAll: It includes all features in F , i.e., all features are treated as related features. This is used to show if noisy features are included or no prior knowledge about related feature is given, FairRF can still work. We also learn for this variant. • Noisy: Its contains features randomly sampled from both F and non-related attributes. In implementation, we randomly replace one attribute in F with non-related ones.
For all these baselines, hyper-parameters are found via grid search, and experiments are conducted for 5 times randomly. From Table 4 and 5, we can make following observations: •   Table 6: Examples of learned on a set of selected related attributes. ·, represents its correlation with class label, and ·, is the correlation with sensitive attributes .

Parameter Sensitivity Analysis
In this subsection, we analyze the sensitivity of FairRF on hyperparameters and . controls the importance of coefficient regularization term, and can adjust the distribution of learned . We vary as {0.2, 0.25, 0.3, 0.35, 0.4} and as {0.4, 0.5, 0.6, 0.7, 0.8}. Other settings are the same as FairRF. This experiment is performed on ADULT, with results shown in Figure 2. From the figure, we can observe that: (i) Larger will achieve fairer predictions, but may also cause severe drop in accuracy when it is larger than some thresholds; (ii) Generally, smaller requires larger to achieve fairness. Small allows learned to be sparse. As a result, a large portion of coefficient regularization term could be enforced on lessdiscriminative attributes that are less-related at the same time; and (iii) encourages learned to be uniform, resulting a faster drop in accuracy when goes large. These observations could help to find suitable hyper-parameter choices in other applications.

Case Study on
In this subsection, we conduct case studies to analyze the behavior of FairRF in learning , i.e., the weights of related attributes. Specifically, we calculate the ground-truth correlation between the sensitive attribute and others are computed, and a set of attributes with varying range of correlation coefficient magnitudes are selected as F . and are set using grid search to make sure that fairness is obtained without significant drop in accuracy.We report the distribution of learned . Results on ADULT and COMPAS are shown in Table 6. From the result, we can observe • FairRF tends to assign higher weight to features that have high correlation with but small correlation with . For example, the correlation of "Duration" with label is 0.02 and with is 0.30, FairRF assigns 0.52 to the feature. This is because such features have little effect on model accuracy but introduce a lot of bias. Assigning a large weight can help achieve fairness with marginal affects on performance; • On the contrary, when a feature has high correlation with , FairRF tends to assign smaller number to even if the correlation of the feature with is large. For example, FairRF assigns 0 to "Relation". This is because when a feature has high correlation with label, it is important for model prediction. A large weight on fairness regularizer will significantly reduce the accuracy.
These observations further demonstrate that by learning , FairRF can balance the accuracy and fairness.

Flexibility of FairRF to Various Backbones
In the above experiment, we fix the base classifier as MLP. In this section, we investigate if FairRF can also benefit various classifiers to achieve fairness while maintaining high accuracy when the sensitive attributes are unknown. Specifically, we also adopt two other widely-used classifiers as the base classifiers of FairRF, i.e., Linear Regression (LR) and Support Vector Machine (SVM). The details of experimental setting and results are given in Supplementary Material. For both models, we find that FairRF only scarifies a little bit of accuracy while significantly improves the fairness. For example, by adding FairRF to LR , Δ drops by 58.5% while the accuracy only drops by 2%.

CONCLUSION
In this paper, we study a novel and challenging problem of exploring related features for learning fair and accurate classifiers without knowing the sensitive attribute of each data sample. We propose a new framework FairRF which utilizes the related features as pseudo sensitive attribute to regularize the model prediction. Our theoretical analysis shows that if the related features are highly correlated with the sensitive attribute, by minimizing the correlation between the related features and model's prediction, we can learn a fair classifier with respect to the sensitive attribute. Since we lack the prior knowledge of the importance of each related feature, we design a mechanism for the model to automatically learn the importance weight of each feature to trade-off their contribution on classification accuracy and fairness. Experiments on real-world datasets show that the proposed approach is able to achieve more fair performance compared to existing approaches while maintain high classification accuracy when no sensitive attributes are known. if Require learning weight then 10: Obtain R for each related feature x ; 11: Calculate and based on Eq.(18) to Eq.(21); 12: end if 13: end while 14: return Trained classifier .

A TRAINING ALGORITHM
With the updating rules introduced in Section 6, the full pipeline of the training algorithm for FairRF can be summarized in Algorithm 1. Before adding the regularization, we first pre-train the model to converge at a good start point in line 3 in order to prevent correlation constraint from providing noisy signals. Then, from line 5 to line 13, we fine-tune the model to be fair w.r.t related features. If not refining related weights, will stay fixed. Otherwise, it will be updated iteratively with parameter , as shown from line 9 to 12.

B IMPLEMENTATION ON DIFFERENT BASE MODEL
In the experiments of main paper, we fix the base classifier as MLP.
In this section, we present the incorporation of FairRF into various machine learning models to achieve fairness while maintain high accuracy when the sensitive attributes are unknown. Specifically, in addition to MLP, we also adopt two other widely-used classifiers as the base classifiers of FairRF, i.e., Linear Regression (LR) and Support Vector Machine (SVM). We implement both of them in a gradient-based manner. so that parameters can be optimized alternatively with the regularization term on related features, as in Algorithm 1. Concretely, we tune the hyperparameters on the validation set. is fixed to 0.4, and is set to 0.4 and 0.6 for LR and SVM, respectively. Adam optimizer is adopted to train them, with the initial learning rate as 0.001. Each experiment is conducted for 5 times, and average results on ADULT and COMPAS are reported in Table 7 and 8, respectively.
From the table, we observe that • Compared with the base classifiers, integrating FairRF makes the accuracy drops a little bit, which is in consistent with observations in other work on fair models [33] as the fairness regularizer usually drops the accuracy. However, the accuracy decrease is marginal. For example, for LR, the accuracy only drops by 2%, which shows that we are still able to maintain high accuracy; • Though the accuracy drops a little bit, the fairness in terms of Δ and Δ on three models improves significantly, even though the sensitive attributes are not observed. For instance, for LR, with the FairRF framework, Δ drops by 58.5% while the accuracy only drops by 2%. In other words, we scarify a little bit of accuracy while significantly improves the fairness. These observations show that FairRF can benefit various machine learning models to achieve fairness while maintaining high accuracy when the sensitive attributes are unknown