LUCID: Exposing Algorithmic Bias through Inverse Design

Artificial intelligence (AI) systems are used in decision-making processes throughout all aspects of human life, ranging from detecting child abuse, determining access to education or healthcare, and granting loans (Amrit et al., 2017; Ledford, 2019; Makhlouf, Zhioua, and Palamidessi, 2021). However, it is by now a well-established fact that algorithms can be biased and lead to discrimination against already disadvantaged population groups (Barocas and Selbst, 2016; Buolamwini and Gebru, 2018; Chouldechova and Roth, 2018; Whittaker et al., 2018). The sources of such biases are multiple and include problem specification, historical bias, unrepresentative data, biased measurement methods, or choice of objective function (Barocas, Hardt, and Narayanan, 2019; Fazelpour and Danks, 2021; Lee and Singh, 2021b; Suresh and Guttag, 2021).

Recent efforts to identify algorithmic discrimination often focus on the statistical properties of a model’s output. The standard approach is to translate philosophical or political notions of group fairness into a statistical metric Makhlouf, Zhioua, and Palamidessi (2021). The model’s output can then be analysed with respect to the chosen notion of group fairness and the model is judged to be “fair” or “unfair”. There are several widely recognised issues with output-based fairness evaluations of this kind. First, there often is substantial philosophical disagreement as to what ought to be considered a “fair” outcome distribution Binns (2018); Gallie (2019). The now infamous controversy about the alleged racism of the COMPAS recidivism risk algorithm boiled down to such a disagreement. In this case, the two fairness measures under debate were accuracy equality and equalised odds with respect to race. Second, different notions of group fairness are incompatible with each other, except for highly special cases Kleinberg, Mullainathan, and Raghavan (2016). Third, the computation of fairness metrics depends on a benchmark data set, which is often also used to evaluate the model on other metrics such as accuracy. The metrics do not assess the model’s fairness towards the whole population after deployment Northcutt, Athalye, and Mueller (2021). Fourth, work on group fairness usually relies on the evaluation of a limited number of prescribed protected attributes, running the risk of missing discrimination either against people who are at the intersection of different groups or against groups that do not share a protected characteristic (Binns, 2020; Crenshaw, 1990; Wachter and Mittelstadt, 2019). Finally, focussing exclusively on output distributions to determine fairness is only one part of the story. In everyday life and when stakes are high, the output of a given decision is not the only thing one typically cares about. We are also interested in how the decision came about, e.g. why I wasn’t granted the loan I applied for or why I didn’t receive the job I interviewed for AIHLEG (2019); Wachter, Mittelstadt, and Russell (2017). Understanding the reasoning behind a decision is not just relevant from a moral point of view, it is equally important within a legal context. Disparate treatment and direct discrimination both aim at addressing cases in which similarly situated individuals are not treated alike on grounds of a legally protected characteristic. In these cases, it becomes relevant both that such individuals were treated differently and why they were treated differently. Output-based fairness evaluations cannot address these issues as they do not take into account the internal logic of the model in question.

We present a method (called LUCID, for Locating Unfairness through Canonical Inverse Design), complementary to output-based fairness evaluations, that takes into account a model’s internal logic. In particular, we introduce the notion of a “canonical set” that allows us to evaluate the fairness of a model’s decision-making processes (see Fig. 1). Through gradient-based inverse design, we generate a canonical input, which can be thought of as the desired input given a preferred output for a trained model. The canonical set then emerges from repeatedly interrogating the model’s decision-making process by generating canonical inputs. By revealing information about the model’s mechanisms, the canonical set provides insights into how the model reaches certain decisions, e.g., what features play a crucial role in the model’s decision-making process. To locate unfairness in the model’s logic, we inspect the distribution of a protected demographic feature within the canonical set. This approach aligns with the increasing focus on equality of treatment beyond equality of outcome.

In contrast to traditional fairness evaluations, LUCID does not require a specific fairness metric, a ground truth, or a benchmark data set. We show that LUCID can be applied to any differentiable model. As an illustration, we evaluate binary classifiers trained on the UCI Adult Dua and Graff (2017) and COMPAS Angwin et al. (2016) data sets. We find that analyzing the canonical set exposes several unethical biases, which interestingly differ from those found by traditional group fairness metrics. By looking into the algorithm’s internal workings, the canonical sets are a valuable addition when evaluating algorithmic fairness.

While, technically, many countries have anti-discrimination laws in place that are designed to protect people from discriminatory harms Barocas, Hardt, and Narayanan (2017); European Commission (2018), there are often considerable practical difficulties associated with the very detection of algorithmic discrimination. The first problem is that those subject to unfair treatment (e.g., the rejected job applicant) often lack the epistemic resources needed to identify instances of discrimination Milano et al. (2021); Selbst and Barocas (2018). The second problem is that access to data sets by third parties is often limited due to intellectual property and privacy rights. Finally, the third problem relates to the frequent opaqueness of the algorithmic decision-making process itself. LUCID mainly addresses the second and third problems.

LUCID lies at the intersection of fairness and interpretability in algorithmic decision-making. There is a strong interaction between these fields, and their connections Meng et al. (2022) and trade-offs Kleinberg and Mullainathan (2019) are part of ongoing research. The most widespread group of methods to gauge fair decision-making translate philosophical or political notions of group fairness into mathematical statements on the model’s output Makhlouf, Zhioua, and Palamidessi (2021). The number of this kind of fairness metrics has grown over the past years, accounting for at least $19$ definitions Barocas, Hardt, and Narayanan (2019); Hardt, Price, and Srebro (2016); Zafar et al. (2017). Furthermore, most prominent open-source fairness toolkits rely on these statistical output metrics Lee and Singh (2021a).

Over the past few years, much work has been done on post hoc interpretability methods, especially in the computer vision literature Das and Rad (2020). The most prominent examples are feature importance estimation methods that help understand which features have a high impact on the output of a model by giving a score to each input. While the feature importance estimation methods differ in various ways, they can be broadly categorized into perturbation- and gradient-based explanations Agarwal et al. (2021).

SHAP Lundberg and Lee (2017) is an example of the former as it constructs local explanations of decision-making algorithms by using perturbations of individual samples. However, the resulting explanations are found to be unreliable, especially in the context of fairness Slack et al. (2020); Balagopalan et al. (2022). Moreover, the standard implementation method does not account for feature dependence whereas many other implementations are computationally very expensive Gohel, Singh, and Mohanty (2021). Nevertheless, perturbation-based methods are often used in combination with statistical fairness metrics Datta, Sen, and Zick (2016). Thereby, this interpretable fairness analysis inherits the obstacles from the output metrics, namely philosophical disagreements Binns (2018); Gallie (2019), statistical incompatibilities Kleinberg, Mullainathan, and Raghavan (2016), the absence of universal ground truth, and the selection of a benchmark data set Northcutt, Athalye, and Mueller (2021) and a limited number of prescribed protected attributes (Binns, 2020).

The Integrated Gradients Sundararajan, Taly, and Yan (2017) method is an example of gradient-based explanations. The gradients of the outputs of individual samples with respect to their inputs are used to construct local explanations. Importantly, the gradients can also be used to construct global explanations by generating an input with the highest activation and certainty for a specific output starting from random noise Simonyan, Vedaldi, and Zisserman (2014). One of the first implementations of this method, called DeepDream, was developed at Google Mordvintsev, Olah, and Tyka (2015) in $2015$. The resulting input images illustrate which elements are essential to get the preferred output. For example, when generating input images that optimize the output “dog,” the results are images with many dog legs, ears, and noses, merged in an unnatural, almost psychedelic way. The resulting images are therefore called “dreams.”

Since then, the technique to determine hidden parameters of a complex system through inverse design has been used in several other research fields, including physics, computer science, engineering, and biotechnology Ferruz and Höcker (2022); Forte et al. (2022); Lenaerts, Pinson, and Ginis (2021); Ren, Padilla, and Malof (2020). We show that LUCID builds upon these methods as the canonical sets are the result of repeatedly applying inverse design to generate canonical inputs, thereby revealing the internal logic of a trained model.

Conventional neural networks use gradient descent to improve their workings by taking advantage of their mathematical structure, which can be differentiated straightforwardly Nielsen (2015). All the layers in a model can be optimized through gradient descent, including the input values. Indeed, the input vector can be seen as a special layer of the model. With LUCID, we use this property to create a canonical input for a preferred output. In other words, starting from a random input vector one can construct the ideal input of a trained model through gradient descent on the input layer, keeping the weights and biases fixed.

This gradient-based inverse design has been extensively used in the computer vision literature Mordvintsev, Olah, and Tyka (2015); Simonyan, Vedaldi, and Zisserman (2014); Sundararajan, Taly, and Yan (2017), but there is a key difference in our application to tabular data. For images, canonical inputs are interpretable individually and difficult to aggregate, whereas for tabular data we have the opposite scenario. In addition, due to the stochastic nature of randomly generated vectors, there is little information in the canonical version of a single input vector. Therefore, we generate a canonical set which results from repeatedly interrogating the model’s decision-making process by generating canonical inputs, revealing its internal workings. To locate unfairness in the model’s logic, we inspect the distribution of a protected demographic feature within the canonical set, and compare it to the initial random distribution. This approach aligns with the increasing focus on equality of treatment beyond equality of outcome, as this requires interpretability, which builds and supports trust, and contributes to procedural fairness.

In Algorithm 1, we show an implementation of LUCID and detail how a canonical set can be generated for a differentiable model by updating a random input vector via gradient descent on the input layer. First, we generate an extensive set of randomly initialized input vectors where the features are sampled from a uniform distribution. Then, these randomly initialized input vectors are transformed into canonical inputs through inverse design. The transformations are the result of minimizing the loss between the model predictions and the preferred output (e.g., a loan is granted). Afterwards, the canonical set is analyzed to learn about the internal workings of the model and evaluated if the model is insensitive to protected attributes.

We evaluate LUCID on the UCI Adult Dua and Graff (2017) and COMPAS Angwin et al. (2016) data sets. The task of UCI Adult is to predict if a person earns more or less than $\$50,000$ per year. The preferred outcome is that a person earns more. We focus on the legally protected featured encoded in the UCI Adult data set as “sex,” “race,” “native country,” “marital status,” and “relationship.” For COMPAS, the task is to predict if a person will commit recidivism in the next two years. The preferred outcome is that a person is predicted to not commit recidivism and can thus be released on bail. The legally protected features in the COMPAS data set are “race,” and “sex.” The models for both tasks are binary fully-connected neural network classifiers. The classifiers consist of hidden layers with ReLU activation functions and a softmax output layer. The number of nodes and layers is decided by the accuracy on the test set. We choose for this rather simple and small architecture as the point of this experiment is not to achieve state–of–the–art performance, but to demonstrate the capabilities of LUCID and compare it with output–based fairness metrics. Note that the computational complexity of LUCID depends on the model, and the number of epochs and inputs.

To locate the unfairness in the classifier trained on the UCI Adult data set, we assess the distributions of the protected features “sex,” “race,” “marital status,” and “relationship” in the canonical set (see Fig. 4). We see that the “race” feature keeps its initial uniform distribution, and “Sex,” “marital status,” and “relationship” do not after the canonical inverse design. This indicates a preference of the model for certain values of these features. Additionally, three numerical features are analyzed: “age,” “education level,” and “hours per week.” All three distributions shift to larger values to achieve a positive output. In the canonical set for the classifier trained on the COMPAS data set both the “race,” and “sex” feature do not keep their initial uniform distribution after the canonical inverse design (see Fig. 5). This indicates that women and Asian people are treated preferentially.

We compare the results of LUCID with two well–known traditional output-based notions of assessing fairness based on group membership: Statistical Parity and Equal Opportunity  Makhlouf, Zhioua, and Palamidessi (2021). Statistical Parity holds when all subpopulations have an equal Positivity Rate (PR). This means that the same proportion of each subpopulation receives a positive output. Equal Opportunity holds when all subpopulations have an equal True Positive Rate (TPR). This implies that for each subpopulation the same rate of people who should receive a favorable output also receive this output.

In Table 1, we show the PR and the TPR of the respective subpopulations of the four protected features for the UCI Adult data set. We see that none of the protected features adheres to either Demographic Parity or Equal Opportunity within an acceptable error margin. Interestingly, these biases differ from those found with LUCID. For example, for the “race” feature, the two fairness metrics indicate that the categories “White” and “American Indian Eskimo” have better rates and, therefore, a benefit. However, with LUCID, we do not find a preferred “race” category. The statistical metrics also find a bias in the “martial status” and “relationship” features. For “relationship,” the highest value of the two rates corresponds to the most preferred category in the canonical set. However, the second-highest value differs. The traditional metrics indicate “Husband” while the canonical set indicates “Not in family.” For the “Marital status” feature the highest and the second-highest values are exchanged, i.e., “Married” and “Military spouse.” In Table 2, we present the PR and the TPR of the respective subpopulations of the two protected features for the COMPAS data set. Overall, the results of these fairness metrics are similar to the results of LUCID.

While LUCID confirms the results of the fairness metrics on the COMPAS data set, there is not always a one-to-one match on the UCI Adult data set. These differences may be the result of several distinct properties of both data sets. First, the UCI Adult data set contains a lot more variables which can encode the information embedded in the protected features. These “proxy” variables may be used by the model to make certain decisions that result in discriminatory outputs. Second, the output-based fairness metrics focus on the outcome, i.e., whether or not the output probability is above or below a certain threshold. In contrast, LUCID is an input-based analysis that aligns with the increasing focus on equality of treatment. The canonical inputs maximize the model’s preferred output. LUCID thus looks for the inputs which do not simply lie above the threshold, but which are strongly preferred by the model. Finally, a lot of categories in the protected features do not contain a lot of data points (e.g., “Military spouse” in the UCI Adult data set). The PR and TPR of these categories are not statistically relevant, and therefore the results may differ from LUCID. Even, in the case that the results are similar, LUCID provides a sanity check and may detect potential overfitting on these few data points. Note that the statistical metrics can only be evaluated using a ground truth and do not consider the internal dynamics of the model.

To ensure that algorithms are used for the benefit of society and not against it, they should be accessible for transparent evaluation. Above all because decision-making algorithms can create, propagate, support, and automate bias in decision-making processes. Therefore, assessing whether the internal logic of algorithms is “fair” is essential to mitigate these biased algorithms, and promoting equality of treatment.

We introduce LUCID which generates a trained model’s canonical set through gradient-based inverse design. We show that this set provides meaningful information about the treatment of protected features by analyzing if it is balanced with respect to said features. By unleashing the technique on two models, trained on the UCI Adult and COMPAS data sets respectively, we find that analyzing the canonical set exposes several biases of which some interestingly differ from those found in traditional output analyses.

LUCID is a useful addition to the toolbox of algorithmic fairness evaluation, as it can be implemented without access to the training data set or the output, and explains the internal workings of the algorithm while locating the unfairness. Further research includes applying it on other types of models such as decision trees, determining potential clustering of inputs in the canonical set, and performing a dynamical analysis to examine which features adjust faster than others.