Optimized Pre-Processing for Discrimination Prevention
Non-discrimination is a recognized objective in algorithmic decision making. In this paper, we introduce a novel probabilistic formulation of data pre-processing for reducing discrimination. We propose a convex optimization for learning a data transformation with three goals: controlling discrimination, limiting distortion in individual data samples, and preserving utility. We characterize the impact of limited sample size in accomplishing this objective. Two instances of the proposed optimization are applied to datasets, including one on real-world criminal recidivism. Results show that discrimination can be greatly reduced at a small cost in classification accuracy.
This paper presents a constrained optimization framework to address (ethically/socially sensitive) discrimination in a classification setting. Such discrimination can occur in machine learning because (1) the training data was obtained from an unfair world and reflects that unfairness, (2) the algorithm trained on the data may introduce biases or unfairness even if there are no issues in the training data, or (3) the output is used in a discriminatory fashion. The present paper falls in the category of preprocessing, meaning it attempts to address unfairness coming from (1) by transforming the data to reduce or eliminate its discriminatory aspects.
As notation, D represents one or more variables of a sensitive nature for which we wish to reduce discrimination, such as race or sex, X represents other predictors, and Y the outcome variable for (binary) classification. Existing literature on fairness and discrimination contains a variety of formal definitions of (un)fairness. Two such definitions are used here, (I) dependence of the predicted outcome \hat Y on D should be low, and (II) similar individuals should receive similar predicted outcomes. These two criteria form the constraints of the optimization problem posed in this paper, and the objective is to minimize a probability distance measure between the joint distribution of the transformed data and the joint distribution of the original data. The paper gives conditions under which the optimization problem is (quasi)convex, and proves a result bounding errors resulting from misspecification of the prior distribution of the data. The utility of the method is demonstrated empirically on two datasets and shown to be competitive with the most similar existing method of Zemel et al. (2013). 
One important limitation of this paper is the assumption that the joint distribution of the data is known. Proposition 2 is a good attempt at addressing this limitation. However, there may be subtle issues related to fairness encoded in the joint distribution which are only hinted at in the Supplementary Material in Figures 2-4. For example, what does it mean for two individuals with different values of D to be similar otherwise? Are there important aspects of similarity not captured in the available data--i.e. confounding variables? These questions are fundamental limitations of individual fairness (IF), and while I may have objections to (IF) I recognize it has been accepted in previous literature and is not a novel proposal of the present work. However, even accepting (IF) without objections, Proposition 2 appears only to address the other two aspects of the optimization problem, and does not address the effect of prior distribution misspecification on (IF). If this could be changed it would strengthen the paper. Some acknowledgement of the subtlety in defining fairness--issues concerning the relations between D and other variables in X, and the implications of those relations on Y, which are addressed fairly implicitly in (IF)--would also strengthen the exposition. See, for example, Johnson et al. "Impartial Predictive Modeling: Ensuring Fairness in Arbitrary Models," or Kusner et al. "Counterfactual Fairness."
Another limitation of the present work is the large amount of calibration or tuning parameters involved. There are tolerances for each constraint, and the potentially contradictory nature of the two kinds of constraints (discrimination vs distortion) is not acknowledged except in the Supplementary Materials where Figure 1 shows some constraint tolerances may be infeasible. Addressing this in the main text and giving conditions (perhaps in the Supplementary Materials) under which the optimization problem is feasible would also strengthen the paper.
Finally, the choice of the distortion metric is both a subtle issue where the fundamental goal of fairness is entirely implicit--a limitation of (IF)--and a potentially high dimensional calibration problem. The metric can be customized on a per-application basis using domain and expert knowledge, which is both a limitation and a strength. How should this be done so the resulting definition of (IF) is sensible? Are there any guidelines or default choices, or references to other works addressing this? Figure 2 is rather uninformative since neither the present method nor its competitor have been tuned. The comparison is (probably) fair, but the reader is left wondering what the best performance of either method might look like, and whether one strictly dominates the other.
* Quality
The paper is well supported by theoretical analysis and empirical experiments, especially when the Supplementary Materials are included. The work is fairly complete, though as mentioned above it is both a strength and a weakness that there is much tuning and other specifics of the implementation that need to be determined on a case by case basis. It could be improved by giving some discussion of guidelines, principles, or references to other work explaining how tuning can be done, and some acknowledgement that the meaning of fairness may change dramatically depending on that tuning.
* Clarity
The paper is well organized and explained. It could be improved by some acknowledgement that there are a number of other (competing, often contradictory) definitions of fairness, and that the two appearing as constraints in the present work can in fact be contradictory in such a way that the optimization problem may be infeasible for some values of the tuning parameters.
* Originality
The most closely related work of Zemel et al. (2013) is referenced, the present paper explains how it is different, and gives comparisons in simulations. It could be improved by making these comparisons more systematic with respect to the tuning of each method--i.e. compare the best performance of each.
* Significance
The broad problem addressed here is of the utmost importance. I believe the popularity of (IF) and modularity of using preprocessing to address fairness means the present paper is likely to be used or built upon.