Fairness (machine learning)

In machine learning, a given algorithm is said to be fair, or to have fairness, if its results are independent of given variables, especially those considered sensitive, such as the traits of individuals which should not correlate with the outcome (i.e. gender, ethnicity, sexual orientation, disability, etc.).
Context.
Research about fairness in machine learning is a relatively recent topic. Most of the articles about it have been written in the last three years. Some of the most important facts in this topic are the following:
Controversies.
The algorithms used for assuring fairness are still being improved. However, the main progress in this area is that some big corporations are realizing the impact that reducing algorithmic bias could have on society.
An example of the controversial use of an algorithm is the way that Facebook allocates news articles to users, which some people have complained can introduce political bias. 
Before elections, some candidates have tried to use Facebook for campaigning purposes, which can become a hotly disputed area.
Transparency of algorithms.
Many people have complained that algorithms often cannot be inspected, to ensure that they are operating fairly, which cannot disadvantage some users.
But many commercial companies prefer to not reveal the details of the algorithms that they use, as they frequently state that it could assist rival companies to benefit from their technologies.
Implications.
If an algorithm is not operating properly the effects on people can be significant and long-lasting, such as regarding education or employment opportunities, and access to financial credit services.
International standards.
Because algorithms are constantly changing and are often proprietary, there are few recognised standards for their construction or operation.
Eventually, algorithms may become more highly regulated, but currently, there is little public oversight for them.
Fairness criteria in classification problems.
In classification problems, an algorithm learns a function to predict a discrete characteristic formula_1, the target variable, from known characteristics formula_2. We model formula_3 as a discrete random variable which encodes some characteristics contained or implicitly encoded in formula_2 that we consider as sensitive characteristics (gender, ethnicity, sexual orientation, etc.). We finally denote by formula_5 the prediction of the classifier.
Now let us define three main criteria to evaluate if a given classifier is fair, that is if its predictions are not influenced by some of these sensitive variables.
Independence.
We say the random variables formula_6 satisfy independence if the sensitive characteristics formula_3 are statistically independent to the prediction formula_5, and we write formula_9.
We can also express this notion with the following formula:
formula_10
This means that the probability of being classified by the algorithm in each of the groups is equal for two individuals with different sensitive characteristics.
Yet another equivalent expression for independence can be given using the concept of mutual information between random variables, defined as
formula_11
In this formula, formula_12 of the random variable. Then formula_13 satisfy independence if formula_14.
A possible relaxation of the independence nce definition include introducing a positive slack formula_15 and is given by the formula:
formula_16
Finally, another possible relaxation is to require formula_17.
Separation.
We say the random variables formula_18 satisfy separation if the sensitive characteristics formula_3 are statistically independent to the prediction formula_5 given the target value formula_1, and we write formula_22.
We can also express this notion with the following formula:
formula_23
This means that the probability of being classified by the algorithm in each of the groups is equal for two individuals with different sensitive characteristics given that they actually belong in the same group (have the same target variable).
Another equivalent expression, in the case of a binary target rate, is that the true positive rate and the false positive rate are equal (and therefore the false negative rate and the true negative rate are equal) for every value of the sensitive characteristics:
formula_24
formula_25
Finally, another possible relaxation of the given definitions is to allow the value for the difference between rates to be a positive number lower than a given slack formula_15, rather than equal to zero.
Sufficiency.
We say the random variables formula_18 satisfy sufficiency if the sensitive characteristics formula_3 are statistically independent to the target value formula_1 given the prediction formula_5, and we write formula_31.
We can also express this notion with the following formula:
formula_32
This means that the probability of actually being in each of the groups is equal for two individuals with different sensitive characteristics given that they were predicted to belong to the same group.
Relationships between definitions.
Finally, we sum up some of the main results that relate the three definitions given above:
Metrics.
Most statistical measures of fairness rely on different metrics, so we will start by defining them. When working with a binary classifier, both the predicted and the actual classes can take two values: positive and negative. Now let us start explaining the different possible relations between predicted and actual outcome:
These relations can be easily represented with a confusion matrix, a table that describes the accuracy of a classification model. In this matrix, columns and rows represent instances of the predicted and the actual cases, respectively.
By using these relations, we can define multiple metrics which can be later used to measure the fairness of an algorithm:
formula_43
formula_44
formula_45
formula_46
formula_47
formula_48
formula_49
formula_50
Other fairness criteria.
The following criteria can be understood as measures of the three definitions given in the first section, or relaxation of them. In the table to the right, we can see the relationships between them.
To define these measures specifically, we will divide them into three big groups as done in Verma et al.: definitions based on a predicted outcome, on predicted and actual outcomes, and definitions based on predicted probabilities and the actual outcome.
We will be working with a binary classifier and the following notation: formula_51 refers to the score given by the classifier, which is the probability of a certain subject to be in the positive or the negative class.formula_5 represents the final classification predicted by the algorithm, and its value is usually derived from formula_51, for example will be positive when formula_51 is above a certain threshold.formula_1 represents the actual outcome, that is, the real classification of the individual and, finally, formula_3 denotes the sensitive attributes of the subjects.
Definitions based on predicted outcome.
The definitions in this section focus on a predicted outcome formula_5 for various distributions of subjects. They are the simplest and most intuitive notions of fairness.
formula_58
formula_59
Definitions based on predicted and actual outcomes.
These definitions not only considers the predicted outcome formula_5 but also compare it to the actual outcome formula_1.
formula_62
formula_63
formula_64
formula_65
formula_66
formula_67
formula_68
formula_69
formula_70
formula_71
Definitions based on predicted probabilities and actual outcome.
These definitions are based in the actual outcome formula_1 and the predicted probability score formula_51.
formula_75
formula_78
formula_81
formula_84
Algorithms.
Fairness can be applied to machine learning algorithms in three different ways: data preprocessing, optimization during software training, or post-processing results of the algorithm.
Preprocessing.
Usually, the classifier is not the only problem; the dataset is also biased. The discrimination of a dataset formula_85 with respect to the group formula_86 can be defined as follows:
formula_87
That is, an approximation to the difference between the probabilities of belonging in the positive class given that the subject has a protected characteristic different from formula_88 and equal to formula_88.
Algorithms correcting bias at preprocessing remove information about dataset variables which might result in unfair decisions, while trying to alter as little as possible. This is not as simple as just removing the sensitive variable, because other attributes can be correlated to the protected one.
A way to do this is to map each individual in the initial dataset to an intermediate representation in which it is impossible to identify whether it belongs to a particular protected group while maintaining as much information as possible. Then, the new representation of the data is adjusted to get the maximum accuracy in the algorithm.
This way, individuals are mapped into a new multivariable representation where the probability of any member of a protected group to be mapped to a certain value in the new representation is the same as the probability of an individual which doesn't belong to the protected group. Then, this representation is used to obtain the prediction for the individual, instead of the initial data. As the intermediate representation is constructed giving the same probability to individuals inside or outside the protected group, this attribute is hidden to the classificator.
An example is explained in Zemel et al. where a multinomial random variable is used as an intermediate representation. In the process, the system is encouraged to preserve all information except that which can lead to biased decisions, and to obtain a prediction as accurate as possible.
On the one hand, this procedure has the advantage that the preprocessed data can be used for any machine learning task. Furthermore, the classifier does not need to be modified, as the correction is applied to the dataset before processing. On the other hand, the other methods obtain better results in accuracy and fairness.
Reweighing.
Reweighing is an example of a preprocessing algorithm. The idea is to assign a weight to each dataset point such that the weighted discrimination is 0 with respect to the designated group.
If the dataset formula_85 was unbiased the sensitive variable formula_3 and the target variable formula_1 would be statistically independent and the probability of the joint distribution would be the product of the probabilities as follows:
formula_93
In reality, however, the dataset is not unbiased and the variables are not statistically independent so the observed probability is:
formula_94
To compensate for the bias, the software adds a weight, lower for favored objects and higher for unfavored objects. For each formula_95 we get:
formula_96
When we have for each formula_2 a weight associated formula_98 we compute the weighted discrimination with respect to group formula_86 as follows:
formula_100
It can be shown that after reweighting this weighted discrimination is 0.
Optimization at training time.
Another approach is to correct the bias at training time. This can be done by adding constraints to the optimization objective of the algorithm. These constraints force the algorithm to improve fairness, by keeping the same rates of certain measures for the protected group and the rest of individuals. For example, we can add to the objective of the algorithm the condition that the false positive rate is the same for individuals in the protected group and the ones outside the protected group.
The main measures used in this approach are false positive rate, false negative rate, and overall misclassification rate. It is possible to add just one or several of these constraints to the objective of the algorithm. Note that the equality of false negative rates implies the equality of true positive rates so this implies the equality of opportunity. After adding the restrictions to the problem it may turn intractable, so a relaxation on them may be needed.
This technique obtains good results in improving fairness while keeping high accuracy and lets the programmer choose the fairness measures to improve. However, each machine learning task may need a different method to be applied and the code in the classifier needs to be modified, which is not always possible.
Adversarial debiasing.
We train two classifiers at the same time through some gradient-based method (f.e.: gradient descent). The first one, the "predictor" tries to accomplish the task of predicting formula_1, the target variable, given formula_2, the input, by modifying its weights formula_103 to minimize some loss function formula_104. The second one, the "adversary" tries to accomplish the task of predicting formula_3, the sensitive variable, given formula_106 by modifying its weights formula_107 to minimize some loss function formula_108.
An important point here is that, in order to propagate correctly, formula_106 above must refer to the raw output of the classifier, not the discrete prediction; for example, with an artificial neural network and a classification problem, formula_106 could refer to the output of the softmax layer.
Then we update formula_107 to minimize formula_112 at each training step according to the gradient formula_113 and we modify formula_103 according to the expression:
formula_115
where formula_116 is a tuneable hyperparameter that can vary at each time step.
The intuitive idea is that we want the "predictor" to try to minimize formula_117 (therefore the term formula_118) while, at the same time, maximize formula_112 (therefore the term formula_120), so that the "adversary" fails at predicting the sensitive variable from formula_106.
The term formula_122 prevents the "predictor" from moving in a direction that helps the "adversary" decrease its loss function.
It can be shown that training a "predictor" classification model with this algorithm improves demographic parity with respect to training it without the "adversary".
Postprocessing.
The final method tries to correct the results of a classifier to achieve fairness. In this method, we have a classifier that returns a score for each individual and we need to do a binary prediction for them. High scores are likely to get a positive outcome, while low scores are likely to get a negative one, but we can adjust the threshold to determine when to answer yes as desired. Note that variations in the threshold value affect the trade-off between the rates for true positives and true negatives.
If the score function is fair in the sense that it is independent of the protected attribute, then any choice of the threshold will also be fair, but classifiers of this type tend to be biased, so a different threshold may be required for each protected group to achieve fairness. A way to do this is plotting the true positive rate against the false negative rate at various threshold settings (this is called ROC curve) and find a threshold where the rates for the protected group and other individuals are equal.
The advantages of postprocessing include that the technique can be applied after any classifiers, without modifying it, and has a good performance in fairness measures. The cons are the need to access to the protected attribute in test time and the lack of choice in the balance between accuracy and fairness.
Reject Option based Classification.
Given a classifier let formula_123 be the probability computed by the classifiers as the probability that the instance formula_2 belongs to the positive class +. When formula_123 is close to 1 or to 0, the instance formula_2 is specified with high degree of certainty to belong to class + or - respectively. However, when formula_123 is closer to 0.5 the classification is more unclear.
We say formula_2 is a "rejected instance" if formula_129 with a certain formula_130 such that formula_131.
The algorithm of "ROC" consists on classifying the non-rejected instances following the rule above and the rejected instances as follows: if the instance is an example of a deprived group (formula_132) then label it as positive, otherwise, label it as negative.
We can optimize different measures of discrimination (link) as functions of formula_130 to find the optimal formula_130 for each problem and avoid becoming discriminatory against the privileged group.