A Novel Regularization Approach to Fair ML

A much-cited work that shares some similarity with that of the present paper is that of [17], later extended by for instance [20].

In [17], the usual least-squares estimate is modified by imposing an upper bound on the coefficient of determination $R^{2}$ in the prediction of $Y$ by (a scalar) $S$. Closed-form expressions are derived, and a kernelized form is considered as well. In this paper, we focus on the approach of [20], which builds on that of [17].

Those two papers develop a kind of 2-stage least squares method, which we now describe in terms relevant to the present work. We use different notation, make previously-implicit assumptions explicit, and apply a bit more rigor, but the method is the same. As noted, all quantities here are population values, not sample statistics.

The basic assumption (BA) amounts to $(Y,X,S)$ having a multivariate Gaussian distribution, with $Y$ scalar and $X$ being a vector of length $p$. For convenience, assume here that $S$ is scalar. All variables are assumed centered. The essence of the algorithm is as follows.

One first applies a linear model in regressing $X$ on $S$,

where $\gamma$ is a length-$p$ coefficient vector. BA implies the linearity.

This yields residuals

Note that $U$ is a vector of length $p$.

$Y$ is then regressed on $S$ and $U$, which again by BA is linear:

where $\alpha$ is a scalar and $\beta$ is a vector of length $p$.

Residuals and regressors are uncorrelated, i.e. have 0 covariance (in general, not just in linear or multivariate normal settings). So, from (3), we have that $U$ is uncorrelated with $S$. In general 0 correlation does not imply independence. but again under BA, uncorrelatedness does imply independence. This yields

and, by the Tower Property [16],

In other words, we have enabled $S$-free predictions of $Y$ by $U$, i.e. (1). The residuals $U$ form our new features, replacing $X$.

This technically solves the fairness problem, since $S$ and $U$ are independent. However, there are some major concerns:

• (a)

  The BA holds only rarely if ever in practical use.

• (b)

  The above methodology, while achieving fairness, does so at a significant cost in terms of our ability to predict $Y$. This methodology, in removing all vestige of correlation to $S$, may weaken some variables in $X$ that are helpful in predicting $Y$. In other words, this methodology may go too far toward the Fairness end of the Fairness-Utility Tradeoff.

The authors in [17] were most concerned about (b) above. They thus modified their formulation of the problem to allow some correlation between $S$ and $\widehat{Y}$, the predicted value of $Y$. They then formulate and solve an optimization problem that finds the best predictor, subject to a user-specified bound on the coefficient of determination, $R^{2}$, in predicting $S$ from $X$. The smaller the bound, the fairer the predictions, but the weaker the predictive ability. Their method is thus an approach to the Fairness/Utility Tradeoff.

The later paper [20] extends this approach, using a ridge penalty. This has the advantage of simplicity. Specifically, they choose $\widehat{\alpha}$ and $\widehat{\beta}$ to be

where $\lambda$ is a regularizing hyperparameter.

If this produces a coefficient of determination at or below the desired level, these are the final estimated regression coefficients. Otherwise, an update formula is applied.

Thus [20] finds a simpler, nearly-closed form extension of [17]. And they find in an empirical study that their method has superior performance in the Fairness-Utility Tradeoff:

We compare our approach with the regression model from Komiyama et al. (2018), which implements a provably-optimal linear regression model, and with the fair models from Zafar et al. (2019). We evaluate these approaches empirically on six different data sets, and we find that our proposal provides better goodness of fit and better predictive accuracy for the same level of fairness.

Note carefully the difference between EDF and [20] (and [17]):

• •

  EDF allows limited but explicit involvement of the specific features in $C$ in predicting $Y$.

• •

  EDF completely excludes $S$, thus complying with European Union regulations [6]. [20] and [17] go much further, allowing limited involvement of $S$ (even in the prediction stage), thus possibly out of compliance with legal requirements in some jurisdictions.

As noted earlier, we aim for simplicity, with the measure of fairness consisting of a single number if possible. This makes the measure easier to understand by nontechnical consumers of the analysis, say a jury in litigation, and is more amenable to graphical display. Our goal here is thus to retain the correlation concept (as in [20]), but in a modified setting.

Specifically, we will use the correlation between modified versions of $\widehat{Y}$ and $S$, denoted by $T$ and $W$. They are defined as follows:

• •

  If $Y$ is continuous, set $T=\widehat{Y}$. If instead $Y$ is a one-hot variable, set $T=P(Y=1~{}|~{}X)$.

• •

  If $S$ is continuous, set $W=S$. If instead $S$ is a one-hot variable, set $W=P(S=1~{}|~{}X)$.

Our fairness measure is then constructed by calculating $\rho^{2}(T,W)$ for each component of $S$.

In other words, we have arranged things so that in all cases we are correlating two continuous quantities. One then reports $\rho^{2}(T,W)$, estimated from our dataset. The reason for squaring is that squared correlation is well known to be the proportion of variance of one variable explained by another (as in the use of the coefficient of determination in [17] and [20]).

For categorical $S$, a squared correlation is reported for each category, e.g. for each race if $S$ represents race.

We assume that the ML method being used provides us with the estimated value of $E(Y~{}|~{}X)$ in the cases of both numeric and categorical $Y$; in the latter case, this is a vector of probabilities, one for each category. The estimated means and probabilities come naturally from ML methods such as linear/generalized linear models, tree-based models, and neural networks. For others, e.g. support vector machines, one can use probability calibration techniques [13].

Our only real asumption is linearity, i.e. that

for some constant vector $\beta$ of length $p$. The predictors in $X$ can be continuous, discrete, categorical etc. Since we are not performing statistical inference, assumptions such as homoscedasticity are not needed.

We then generalize the classic ridge regression problem to finding

where the diagonal matrix ${D}=diag(d_{1},...,d_{p})$ is a hyperparameter. We will want $d_{i}=0$ if the $i^{th}$ feature is not in $C$, while within $C$, features that we wish to deweight more heavily will have larger $d_{i}$. (In order for $D$ to be invertible, we will temporarily assume $d_{i}$ is positive but small for elements of $X$ not in $C$.)

Now with the change of variables $\widetilde{b}={D}b$ and $\widetilde{\mathbb{X}}=\mathbb{X}{D}^{-1}$, (10) becomes

with $\lambda=1$.

Equation (11) is then in the standard ridge regression form, and has the closed-form solution

Mapping back to $b$ and $\mathbb{X}$, we have

Substituting $\mathbb{I}={D}{{D}}^{-1}$ in (13), and using the identity $T^{-1}S^{-1}=(ST)^{-1}$, the above simplifies to

and then, with $D={{D}}^{-1}{DD}$, we have

We originally assumed $d_{i}>0$, but due to the fact that (15) is continuous in the $d_{i}$, we can take the limit as $d_{i}\rightarrow 0$, showing that 0 values are valid. We now drop that assumption.

In other words, we can achieve our goal—deweighting only in $C$, and in fact with different weightings within $C$ if we wish—via a simple generalization of ridge regression.⁶⁶6In a different context, see also [24]. We can assign a different $d_{i}$ value to each feature in $C$, according to our assessment (whether it be ad hoc, formal correlation etc.) of its impact on $S$. We then set $d_{i}=0$ for features not in $C$.

Note again that the diagonal matrix $D$ is a hyperparameter, a set of $|C|$ quantities $d_{i}$ controlling the relative weights we wish to place within $C$. We then set our deweighting parameters $\delta_{i}=d_{i}^{2}$.

Applying the well-known dual problem in this context, minimizing (10), the above is equivalent to choosing $b$ as

where $\gamma$ is also a hyperparameter.

One computational trick in ridge regression is to add certain artificial data points, as follows.

Add $p$ rows to the feature design matrix, which in our case means

Add $p$ 0s to $\mathbb{Y}$:

Then compute the linear model coefficients as usual,

Since

and

(19) gives us (15), our desired ridge estimator. We then can use ordinary linear model software on the new data (17) and (18).

In the case of the generalized linear model, here taken to be logistic, the situation is more complicated.

Regularization in general linear models is often implemented by penalizing the length of the coefficient vector in maximizing the likelihood function [10]. Also, [15] uses conjugate gradient for solving for the coefficient vector. In the EDF setting, such approaches might be taken in conjunction with a penalty term involving $||Db||^{2}$ as above.

As a simpler approach, one might add artificial rows to the design matrix, as in Section 5.2. We are currently investigating the efficacy of this ad hoc approach.

Which features should go into the $C$ deweighting set? These are features that predict $S$ well. The analyst may rely on domain expertise here, or use any of the plethora of feature engineering methods that have been developed in the ML field. In some of the experiments reported later, we turned to FOCI, a model-free method for choosing features to predict a specified outcome variable [2].

The deweighting parameters can be chosen by cross-validation, finding the best predictive ability for $Y$ for a given desired level for the fairness measure $\rho^{2}$. But if $C$ consists of more than one variable, each with a different deweighting parameter, we must do a grid search. Our software standardizes the features, which puts the various deweighting parameters on the same scale, and the analyst may thus opt to use the same parameter value for each variable in $C$. The search then becomes one-dimensional. Note that even in that case, EDF differs from other shrinkage approaches to fair ML, since there is no shrinkage associated with features outside $C$.

Our examples below are only exploratory, illustrating the use of EDF for a few values of the deweighting parameters; no attempt is made to optimize.

Let us start with a dataset derived from the 2000 US census, consisting of salaries for programmers and engineers in California’s Silicon Valley.⁷⁷7This is the pef data in the R regtools package. Census data is often used to investigate biases of various kinds. Let’s see if we can predict income without gender bias.

Even though the dataset is restricted to programmers and engineers, it’s well known that there is a quite a variation between different job types within that tech field. One might suspect that the variation is gendered, and indeed it is. Here is a comparison between men and women among the six occupations, showing the gender breakdown across occupatioms:

Men and women do seem to work in substantially different occupations. A man was 3 times as likely as a woman to be in occupation 141, for instance.

Moreover, those occupations vary widely in mean wages:

So, the occupation variable is a prime candidate for inclusion in $C$.

Thus, $Y$ will be income, $S$ will be gender, and we’ll take $C$ to be occupation. Here are the Mean Absolute Prediction Errors and correlations between predicted $Y$ and gender, based on results of 500 runs, i.e. 500 random holdout sets:⁸⁸8The default holdout size was used, 1000. The dataset has 20090 rows.

Now, remember the goal here. We know that occupation is related to gender, and want to avoid using the latter, so we hope to use occupation only “somewhat” in predicting income, in the spirit of the Fairness-Utility Tradeoff. Did we achieve that goal here?

We see the anticipated effect for occupation: Squared correlation between $S$ and predicted $Y$ decreases as $D_{i}^{2}$ increases, with only a slight deterioriation in predictive accuracy in the last settings, and with predictive accuracy actually improving in the first few settings—as anticipated in Section 7. Further reductions in $\rho^{2}$ might be possible by expanding $C$ to include more variables.

The authors of [20] have made available software for their method (and others), in the fairml package. Below are the results of running their function frrm() on the census data.⁹⁹9The package also contains implementations of the methods of [17] and [25], but since [20] found their method to work better, we will not compare to the other two. The ‘unfairness’ parameter, which takes on values in [0,1], corresponds to their ridge restriction; smaller values place more stringent restriction on $||\alpha||$ in (4), i.e. are fairer. We set their $\lambda$ parameter to 0.2.

The mean absolute prediction errors here are somewhat smaller than those of EDF. But the squared correlations between predicted $Y$ and probabilities of $S$ (here, the probabilities of being female, the sensitive attribute) are larger than those of EDF. In fact, the correlation seemed to be constant, and no value of the fairness parameter succeeded in bringing the squared correlation below 0.20. Further investigation is needed.

This is easy to do for both linear and several other standard ML methods:

• •

  Random forests: In considering whether to split a tree node, set the probability of choosing variables in $C$ to be lower than for the other variables in $X$. The R package ranger [23] sets variable weights in this manner (in general, of course, not specific to our fair-ML context here).

• •

  k-nearest neighbors (k-NN): In defining the distance metric, place smaller weight on the coordinates corresponding to $C$, as allowed in [8] (again, not specific to the fair-ML context).

• •

  Support vector machines: Apply an $\ell_{2}$ constraint on the portion of the vector $w$ of hyperplane coefficients corresponding to $C$. This could be implemented using, for instance, the weight-feature SVM method of [22] (once again, a feature not originally motivated by fairness).

As noted, in each of the above cases, the deweighting of features has traditionally been aimed at improving prediction accuracy. Here we repurpose the deweighting for improving fairness in ML.