Fairness in the Eyes of the Data: Certifying Machine-Learning Models

Introduction

Machine learning systems are increasingly being used to inform and influence decisions about people, leading to algorithmic outcomes that have powerful personal and societal consequences. For instance, decisions such as (i) is an individual likely to commit another crime?(Angwin et al., 2016); or (ii) is an individual likely to default on a loan?(Waddell, 2016) are made using algorithmic predictions. This can be concerning given the many documented cases of models amplifying bias and discrimination from the training data (Buolamwini and Gebru, 2018; Kleinberg et al., 2017; Corbett-Davies et al., 2017; Tatman and Kasten, 2017). To address this formally, a line of recent works considers fairness in classification by proposing notions of fairness based on similarity measures and formalizing variants of this notion that provide guarantees against discrimination (Dwork et al., 2012; Hébert-Johnson et al., 2018; Kearns et al., 2018; Kim et al., 2019).

One common scenario in which such a discrimination could potentially happen is a setting with a client and a server. The server classifies queries by a client in an automated way using a machine learning model generated by it. On the other hand, the client wants to make sure its queries are treated fairly and its sensitive data is conserved. If the model itself is not a secret, then a client can potentially run tests (such as the ones implied by the references above) on the model to establish its purported fairness without exposing its data. Making a model public, however, is not always in the interest of the server, since it has invested resources such as expertise, data and computation time for the training – and therefore often wants the model to remain proprietary. Moreover, sharing models may in some cases raise security or privacy concerns. It therefore may be deemed appropriate or necessary to outsource any such test to a semi-trusted third party such as a government entity, which would inspect a model and certify its fairness. This raises our first question:

Question 1: Can we design a framework for verifying the fairness of models, giving guarantees to clients while being practically realizable and keeping the model secret from the clients?

Having such a third party relieves the client from testing fairness, but actually just shifts responsibility to someone who might be more qualified to make a judgement about the model. To minimize the necessary trust between the model owner and the third party, such a test would still be restricted to a black-box scenario. In addition, constructing such a test for establishing fairness guarantees can be difficult on its own. Given that the sources and amount of data is limited, it might be that the third party can only use data in the fairness test that the model owner is familiar with. This might enable the model owner to design an unfair model which successfully passes the examination by the third party.

Question 2: Can we design a black-box fairness test that gives guarantees even if the test set is (partially) known?

Here, by a black-box test we mean that a test should only query the model $M$ on different inputs but should not make any assumptions about the actual model parameters.

In this work, we answer both questions affirmatively. We design an architecture for certifying fairness via verification in machine learning models using three (or more) participants, the model owner (or “server”) $\mathcal{S}$, the client $\mathcal{C}$ and a trusted third party $\mathcal{R}$ (also called “regulator”). Our architecture uses techniques from cryptography to construct secure protocols for

An interactive test between $\mathcal{S}$ and $\mathcal{R}$ allowing to verify with high probability that a model $M$ provided by $\mathcal{S}$ is fair with respect to a set of pre-defined groups. While ensuring that $\mathcal{R}$ does not learn $M$. This test considers scenarios where $\mathcal{S}$ is or is not aware of the test data. $\mathcal{R}$ is not involved in the training of $M$, it only performs certification.

An interactive computation between $\mathcal{S}$ and $\mathcal{C}$ which computes a prediction $\hat{y}=M(x)$ from an input $x$ and a model $M$. The interactive computation neither leaks $M$ to $\mathcal{C}$ nor $x$ to $\mathcal{S}$, and yet makes sure that the model that was used in the prediction has been certified by $\mathcal{R}$ beforehand.

Our work provides fairness tests necessary for these protocols that have black-box to the model and uses existing highly efficient cryptographic primitives to implement the tests securely. While we motivate the underlying ideas of these tests on an intuitive level and give formal arguments for their soundness, we also provide experimental evidence that the hypotheses that make our tests possible are viable. Since secure and privacy-preserving computation of models, for both training and inference, is a very active research area (e.g. Mohassel and Zhang (2017); Juvekar et al. (2018); Riazi et al. (2018); Kumar et al. (2019); van der Maaten and Hannun (2020); Guo et al. (2020)), the performance of the current solutions in this field is continuously improving. As our work assumes the existence of secure protocols for inference, and investigates how to add fairness on top of these in a generic way that is independent of the underlying training algorithm, our approach will benefit in practicality from any independent progress that is made in this direction.

Related work

Fairness in algorithms was first investigated by Friedman and Nissenbaum (1996). Since then, further research into data as a source of unfairness in ML decisions has been done (Kay et al., 2015; Caliskan et al., 2017). Baluta et al. (2019) showed how to verify properties of a DNN (fairness among them). In their work they encode the network into Conjunctive Normal Forms and then test if it will likely fulfill certain logical constraints. In comparison, our approach is independent of the concrete model parameters and architecture.

Several statistical measures of unfairness, and fairness criteria are studied by Feldman et al. (2015); Zemel et al. (2013). These and subsequent works achieve statistical notions of fairness through post-processing the training data, and/or by enforcing constraints at training time. Our work differs from this line of research in that we want to guarantee fairness which is enforced obliviously of the training process. Dwork et al. (2012) shows that statistical notions of fairness are inadequate, while Corbett-Davies et al. (2017) established that model calibration does not rule out unfair decisions. These results emphasize that fairness is nuanced, complicated, application-specific, and can depend on legal and social contexts. In this work, we answer the orthogonal question of designing a fairness test for any machine learning model, given an accepted fairness definition.

Most relevant prior work to ours is the study by Kilbertus et al. (2018). In this research the authors suggest to use cryptographic primatives for fairness certification, fair model training, and model decision verification. However, this study was mainly focused on certifying a model via fair training. Additionally it did not provide analysis and guarantees for model fairness certification. Our study focuses on certifying fairness via verification of any existing machine learning models, regardless of the training process. Since the framework is oblivious to the training process, multiple fairness definitions can be certified post-training, even if the training process did not take them into account. We analyze our framework from both theoretical and practical points of view while providing guarantees based on the number of samples available in the test set. We also explore a different scenario where these samples are known to $\mathcal{S}$ during model training, which makes the certification harder.

Preliminaries

Let $\mathcal{X}$ be the set of possible inputs, $\mathcal{G}$ be a finite set of groups that are relevant for fairness (e.g., ethnic groups) and $\mathcal{Y}$ be a finite set of labels. We suppose $\mathcal{X}\times\mathcal{G}\times\mathcal{Y}$ is drawn from a probability space $\Omega$ with an unknown distribution $\mathcal{D}$. Let $M$ be a trained model for a classification task of $\mathcal{D}$, we denote $M(x)$ for classification of input $x\in\mathcal{X}$.

The goal of training a model $M$ is usually to achieve low error on unseen data. In addition, when dealing with model fairness, we also take into account a measurement with respect to $\mathcal{G}$. While there are plenty of fairness measurements (Verma and Rubin, 2018), here we focus on group risk and likelihood based definitions, specifically: overall risk equality (ORE), equalized odds (EO) and demographic parity (DP). First, we define the conditional risk and likelihood respectively:

where $m_{g}$ is the number of samples in $T$ from group $g$.

We define a metric called the fairness gap to be the maximal margin between any two groups (and labels). Formally, we use three well-known measurements:

Likewise, the empirical fairness gap (EFG) is defined using the empirical approximation of each measurement respectively.

Lastly, we call model $M$ $\epsilon$-fair on $(\mathcal{G},\mathcal{D})$ with respect to a fairness measurement, if its fairness gap is smaller than $\epsilon$ with confidence $1-\delta$, which is similar to PAC-style fairness (Rothblum and Yona, 2018). A model $M$ is then called $\epsilon$-fair on $(\mathcal{G},\mathcal{D})$ under the ORE metric if:

Plugging-in the fairness gap metric for EO and DP yields the corresponding $\epsilon$-fairness definitions.

Cryptographic Primitives

We now describe the cryptographic primitives that are necessary to implement the proposed framework in more detail: Signatures, Collision-Resistant Hash Functions and Secure Computation.

Collision-Resistant Hashing. We will use a Collision-Resistant Hash Function $H_{k}:\{0,1\}^{n}\times\{0,1\}^{2n}\rightarrow\{0,1\}^{n}$, which is an efficiently computable function such that it is hard for any polynomial-time algorithm (in $n$) that is given a random $k$ to come up with $x_{1},x_{2}$ such that $H_{k}(x_{1})=H_{k}(x_{2})$. In practice, one uses e.g. SHA-3 to implement $H_{k}$ for a $k$ that is fixed in advance. Since the input length of SHA-3 is fixed, in order to hash longer messages, one can apply $H_{k}$ recursively using a Merkle Tree (see Figure 1). For such a Merkle Tree it can be proven that if $H_{k}$ is collision-resistant then $\hat{H}_{k}$ is too.

Secure Computation. We further let parties perform computations on shared data such that the computation does not reveal their inputs, for purposes as mentioned in the next Section.

Secure Computation can be imagined as the existence of a “trusted third party” $\mathcal{F}_{\mathtt{SC}}$ which performs a computational task for certain parties. $\mathcal{F}_{\mathtt{SC}}$ would receive the inputs from both participants, do the computation, and send the output to the participants. The task of this party is outlined in Figure 2. As is common in the secure computation literature, this description assumes that the computation is done by a circuit $K$. Participant $\mathcal{P}_{1}$ provides to the trusted party its input $x_{1}$, while participant $\mathcal{P}_{2}$ provides its input $x_{2}$. The trusted party computes $K(x_{1},x_{2})$ and sends its outputs to the respective participants. By this definition this “idealized box” $\mathcal{F}_{\mathtt{SC}}$ achieves the desired privacy objective.

Such a trusted third party $\mathcal{F}_{\mathtt{SC}}$ as described in Figure 2 does not necessarily exist in the real world, but it can be emulated using cryptographic tools as a protocol consisting of two (or more) entities sending messages to each other over a network. Guarantees in these protocols can be given if at least one of the participants is acting honestly throughout the process.

The two most popular approaches for implementing Figure 2 are based on cryptographic paradigms called Fully Homomorphic Encryption (FHE) and Secure Multiparty Computation (MPC). For comparison, current FHE schemes are constrained by their demand for computational power and they at best can evaluate a few hundred AND-gates of the circuit $K$ per second. MPC on the other hand, which has a higher demand in terms of communication, can achieve a much better throughput. In particular, there exist MPC schemes that are tailored at efficiently implementing the function $M(\cdot)$ A recent framework for privacy preserving machine learning using MPC built on PyTorch: CrypTen (FacebookResearch, 2019). (Barak et al., 2019; Damgård et al., 2019).

The Framework

We present our framework from a broad overview, and leave most of the implementation details to later sections. There we describe two interactive tests to verify fairness and more wholesome view on the cryptographic aspects. For now we focus on the general flow and interaction between the different participants we previously described. We also make their roles more explicit and describe the security guarantees that are given to each of them as well as the trust relations. Note that we discuss our framework with respect to three participants but it can easily be generalized to any larger number. In particular, it allows for a large number of regulators $\{\mathcal{R}_{i}\}_{i=1}^{k}$ that a client $\mathcal{C}$ can choose from or even perform the regulators role by itself.

The Server $\mathcal{S}$ initially generates the model $M$. Its main objective is to keep $M$ secret. He may try to use an unfair model towards $\mathcal{R}$ or $\mathcal{C}$.

The Client $\mathcal{C}$ has a private input $x$ and wishes to obtain $\hat{y}\leftarrow M(x)$, where the server provides $M$. The objective of $\mathcal{C}$ is to ensure that $M$ is fair while keeping $x$ private.

The third participant is the Regulator $\mathcal{R}$ who should neither learn $M$ nor $x$ or $y$. After $\mathcal{S}$ proves the fairness of model $M$, $\mathcal{R}$ outputs certificate $\mathtt{cert}_{M}$ for the model to attest its validity. $\mathtt{cert}_{M}$ is tied to another certificate $\mathcal{R}$ issued, $\mathtt{cert}_{ID}$, which serves as the identity of $\mathcal{R}$. When $\mathtt{cert}_{M}$ is shown to $\mathcal{C}$ it can verify that indeed $\mathcal{R}$ certified the model using $\mathtt{cert}_{ID}$. In addition, $\mathcal{R}$ has access to the sample set $T$ in order to check fairness, which is possibly known to $\mathcal{S}$.

In terms of modeling security we assume that $\mathcal{S}$ will try by any means to get an unfair model certified, use an unfair model to a client or learn $\mathcal{C}$’s input. In particular, $\mathcal{S}$ may actively deviate from any specified program or protocol in any way. On the other side, we consider that $\mathcal{C}$ and $\mathcal{R}$ would follow the protocol but may try to learn information about $\mathcal{S}$’s model in the process. In more cryptographic terms we consider a malicious $\mathcal{S}$ while $\mathcal{C}$ and $\mathcal{R}$ are semi-honest. We further assume that either party is computationally polynomially time-bounded.

The certificates $\mathtt{cert}_{ID},\mathtt{cert}_{M}$ are implemented using a digital signature scheme and a collision-resistant hash function. Roughly, $\mathtt{cert}_{ID}$ is a public verification key that is tied to the identity of $\mathcal{R}$, and $\mathtt{cert}_{M}$ is a signature on a compressed version of the model that is computed using a collision-resistant hash function. Here, a cryptographic signature ensures that only $\mathcal{R}$ could issue $\mathtt{cert}_{M}$, while the hash function forces $\mathcal{S}$ to use the same model with $\mathcal{C}$ that he used when obtaining $\mathtt{cert}_{M}$.

At the beginning of the protocol, $\mathcal{R}$ generates its public certificate $\mathtt{cert}_{ID}$ and makes it available. $\mathcal{S}$ and $\mathcal{R}$ then interact to generate the model certificate $\mathtt{cert}_{M}$ for model $M$. In the process $\mathcal{R}$ is allowed to query $M$ an arbitrary number of times to ensure fairness. To perform an inference by $\mathcal{S}$ and $\mathcal{C}$, both first agree on a regulator certificate $\mathtt{cert}_{ID}$ that they will use. Then, $\mathcal{C}$ obtains an output $\hat{y}$ based on its input $x$ and on a model $M^{\prime}$ providedHere we write $M^{\prime}$ to denote that technically a malicious $\mathcal{S}$ could try to perform the inference with whatever model $M^{\prime}$ it wants. The job of the inference algorithm is then to enforce that $M^{\prime}=M$ for some previously certified $M$. by $\mathcal{S}$. Here, $\mathcal{C}$ only accepts $\hat{y}$ if $M^{\prime}$ is certified by the regulator behind $\mathtt{cert}_{ID}$ for fairness. $\mathcal{C}$ does not learn anything about $M^{\prime}$, besides $\hat{y}$. Fig. 3 describes the aforementioned process schematically.

Both the inference on $M$ and the verification of $\mathtt{cert}_{M}$ that are necessary in Fig. 3 could be done easily if $\mathcal{S},\mathcal{R}$ and $\mathcal{C}$ would have access to a “trusted third party” $\mathcal{F}_{\mathtt{SC}}$ which performs the computational task for them. That trusted third party would receive inputs from participants, do the computation, and send the output back to them. In our case, $\mathcal{F}_{\mathtt{SC}}$ would receive all secret input from the participants and send $\mathtt{cert}_{M}$ to $\mathcal{S}$ after verifying $M$ is fair. $\mathcal{F}_{\mathtt{SC}}$ can also send $M(x)$ to $\mathcal{C}$ if model $M^{\prime}$ is certified in that manner. As mentioned in the previous section, such a ”trusted third party” can be emulated using cryptographic protocols for Secure Computation. The use of cryptography guarantees that the protocol is secure against a malicious $\mathcal{S}$ or semi-honest $\mathcal{C},\mathcal{R}$.

Verifying Fairness Interactively

We now turn to introduce two interactive tests which allow $\mathcal{R}$ to determine if a model $M$ is $\epsilon$-fair:

The model $M$ is queried using a sample set $T$ which is unknown to $\mathcal{S}$. We show that fairness guarantees about $M$ can be made given by the empirical fairness gap (EFG) and a lower-bound on the minimal size of the set $T$ with respect to each group $g\in\mathcal{G}$.

Both of the aforementioned tests are independent of the representation of $M$, make no requirement on its training algorithm and only require access to $M(\cdot)$ for different inputs. All claims below are based on $\epsilon$-fairness with confidence $1-\delta$ under the ORE fairness metric, however these can be modified to other group-based fairness definitions.

The simpler case is when the model $M$ is queried using an i.i.d sample set $T$ which is unknown to $\mathcal{S}$. This setup is rather standard in machine learning, as verification using i.i.d samples can be achieved via classic concentration bounds from PAC learning (Valiant, 1984; Vapnik, 2006). We apply similar bounds to assess the minimum number of samples needed for fairness verification.

The following states the conditions which guarantee that a model is $\epsilon$-fair with a confidence $1-\delta$.

A model $M$ is $\epsilon$-fair with confidence $1-\delta$ if:

for $T=\{(x_{1},g_{1},y_{1}),...,(x_{m},g_{m},y_{m})\}\sim\mathcal{D}^{m}$, where $m_{g}$, as in Eq. $(\ref{eq:emp_group_risk})$, denotes the number of occurrences of $g$ in $T$.

DP and EO can be achieved by using the corresponding EFG definition and minimizing over $\mathcal{G}\times\mathcal{Y}$, counting $m_{g}$ and $m_{g,y}$ respectively in (3). The full proof of the above claim can be found in the supplementary materials.

Verifying Fairness using Augmented Data.

The disadvantage of the aforementioned test is that all test data $T$ must be hidden so that the model generator $\mathcal{S}$ cannot use it to adapt $M$ accordingly. In other settings, we would like to test for fairness using public data, which can be known to $\mathcal{S}$. This setting is realistic in many scenarios. For example, if labelled data is costly, getting unique labelled data for a test will be difficult for $\mathcal{R}$.

A straightforward argument against this approach is once the data is publicly available, $T$ is not chosen independently of $M$. Thus, a malicious $\mathcal{S}$ can create an unfair model that memorizes the set $T$ and responds fairly on it, so that it passes the test outlined above. To counter such dishonest training, we need a method to alter the existing samples and force some sort of generalization abilities. We therefore define the notion of an augmentor. An augmentor applies random augmentations to the input which alter the sample but still preserves its label and group with high probability. Here we use it to generate new samples for querying that with high probability were not seen during model training. This is a necessary but not sufficient condition in order to ensure a valid test for $M$. For example, consider an augmentor that only alters the first few pixels of the image. A model that simply ignores those pixels can still overfit on the rest of the image and pass any test.

Hence, we suggest to use a set of randomized augmentation functions to reduce memorization capabilities of an adversary. For this, the assumption is that $\epsilon$-fair models behave differently from unfair models when queried against the samples augmented by the augmentor. Then, this different behavior can be leveraged to expose the unfair nature of certain models. Our approach follows this assumption to construct a querying test set in the same fashion of the test that was previously defined.

More specifically, define an algorithm augmentor $\mathtt{aug}:\mathcal{X}\times\mathcal{G}\times\{0,1\}^{\tau}\to\mathcal{X}$ that gets as input a random string and a sample and outputs a new augmented sample. The label and group of the new sample should be the same as the original sample with high probability.

We re-define the conditional risk to be on an augmented sample from $\mathcal{D}$. Formally:

As mentioned before, there is no guarantee that samples augmented by $\mathtt{aug}$ yield better results than $T$ itself. We need an additional assumption on the behavior of fair and unfair models when shown augmented samples from $\mathtt{aug}$, thus we call a class of models $\mathcal{M}$ detectable if it fulfills that assumption.

1 allows us to build an interactive test and to empirically find parameters $\epsilon,\alpha,m$ and an augmentor for which it appears to be true. The intuition behind 1 is that in order to cheat the test, M is required to behave differently on the augmented data than on the new unobserved samples. In practice, augmentations are commonly used to improve robustness and generalization, thus M is less likely to be able to generalize on a large set of them without the risk of exposing its unfair nature, as $\mathtt{aug}$ challenges its generalization capabilities. The parameterization yields a non-trivial angle both for breaking our overall construction and for improving it.

Notice, the above definition does not imply that all $\epsilon$-fair models have this property, and some fair models will not be discovered due to that. Empirically, we observed that such models can efficiently be detected and we demonstrate that in the experimental section. Additionally, we observe that the output of $\mathtt{aug}$ is not required to be indistinguishable from a new sample from $\mathcal{D}$. In particular the definition does not rule out that $\mathcal{A}$ is aware of the possible augmentations.

In other words, we can certify $\epsilon$-fairness of a model with high confidence assuming $(\epsilon,\alpha,\mathtt{aug})$-detectable fairness. The proof is in the supplementary materials.

Implementing the Framework

We describe how to implement the framework from previous sections using the interactive tests and guarantees from 1. While the implementation is described at a high level, it is easy to instantiate each of the components based on existing cryptographic tools and the experimental results in the Experiments section.

Consider a design of an interactive test based on the set $T=\{(x_{1},g_{1},y_{1}),...,(x_{m},g_{m},y_{m})$ and parameters $\delta,\epsilon$ as follows:

The regulator $\mathcal{R}$ computes the minimal $m_{g}$ fulfilling Eq. 3 by assuming $EFG=0$. If $T$ does not contain enough samples from each group, then $\mathcal{R}$ aborts. If $\mathcal{R}$ does not abort, it tells $\mathcal{S}$ the total number of inputs $m$ that will be checked.

$\mathcal{R}$ and $\mathcal{S}$ run a secure computation of a functionality $\mathcal{F}_{\mathtt{Check}}$ which is described below. $\mathcal{S}$ inputs $M$ into $\mathcal{F}_{\mathtt{Check}}$ while $\mathcal{R}$ inputs $(\{(x_{i},g_{i},y_{i})\}_{i\in[m]})$. The functionality $\mathcal{F}_{\mathtt{Check}}$ consists of the following steps:

Compute $\hat{y}_{i}\leftarrow M(x_{i})$ for all $i\in[m]$.

For all $i\in[m]$, compute a bit $b_{i}$ as 1 if $\hat{y}_{i}=y_{i}$ and 0 otherwise.

Evaluate Eq. (3) of 1 (checking $\epsilon$-fairness). Output $1$ if the statement holds and otherwise.

Based on the statement of 1 it follows that $\mathcal{F}_{\mathtt{Check}}$ will output $1$ if and only if the model $M$ provided by $\mathcal{S}$ is $\epsilon$-fair with confidence $1-\delta$.

The secure computation of $\mathcal{F}_{\mathtt{Check}}$ implements the functionality as a Binary circuit $K$ that is evaluated on secret inputs. We examine the size of this circuit in a following section under Efficiency.

If $\mathcal{R}$ instead wishes to use public and augmented data as for Theorem 2 then this will only work assuming that $M$ is $(\epsilon,\alpha)$-detectable as defined in Definition 1. In such a setting $\mathcal{R}$ would now create a test set $T^{\prime}$ from $T$ locally using an augmentor $\mathtt{aug}$ and then follow the exact same path as for the public data (albeit with different constants).

Algorithms

We now describe how to use the circuit $K$ from the previous section to implement the framework. The overall approach is as follows: Initially, $\mathcal{R}$ generates a signature key pair and distributes the verification key to all other participants. Then $\mathcal{R}$ and $\mathcal{S}$ run a secure computation which runs the interactive test and computes a Merkle tree hash $\hat{H}_{k}(M)$ of the model $M$. If the test finds that the model is fair, then $\mathcal{R}$ signs ($\hat{H}_{k}(M),\epsilon,\delta$, fairness definition string) and sends the signature to $\mathcal{S}$. By signing $\epsilon,\delta$ and a fairness definition string we allow multiple fairness definitions and hyperparameters to be certified.

Later, whenever $\mathcal{S}$ and $\mathcal{C}$ run a certified inference for $\epsilon,\delta$ and a fairness definition, then in addition to running a secure computation of $M(x)$, the functionality will also recompute the hash $\hat{H}_{k}(\cdot)$ of the model provided by $\mathcal{S}$ and output it to $\mathcal{C}$, while $\mathcal{S}$ sends the signature on the model to $\mathcal{C}$. $\mathcal{C}$ can then locally check if $\mathcal{R}$ originally issued the signature on the hash for those hyperparameters and fairness definition, given the public verification key of $\mathcal{R}$. The overall protocols are outlined in Figure 4.

Security

We provide a sketch of the argument about the security of $\pi_{\mathtt{Framework}}$. This must naturally stay on a high level, since we did not make the security properties of the framework formal.

First, we note that $\pi_{\mathtt{Framework}}$ leaks to $\mathcal{R}$ and $\mathcal{C}$ the Merkle-tree hash $h$ of the model. But since it can be assumed that $M$ has high entropy and the implementation of $H_{k}$ is a cryptographic hash function, the leakage of $h$ should be tolerable.It is possible in principle to reduce this leakage by computing $\mathcal{R}$’s signature of $h$, and the signature verification by $\mathcal{C}$, in a secure computation, but this will considerably increase the overhead. In the other direction, if we are willing to leak some more information then the circuit $K$ can be modified to output to $\mathcal{R}$ whether $M$ successfully classified each input $x_{i}$ and let $\mathcal{R}$ compute the $\epsilon$-fairness of the model locally. This will simplify the secure computation at the cost of leaking more data to $\mathcal{R}$.

That being said, we base our security argument on statements about the security of the building blocks that are used, which can be instantiated using well-known cryptographic constructions:

The functionality $\mathcal{F}_{\mathtt{SC}}$ can be implemented using a secure protocol. As mentioned above this can be done using secure two-party or multi-party computation (MPC).

There exist secure signature and hashing schemes.

Efficiency

We now estimate the efficiency of implementing our framework using $\pi_{\mathtt{Framework}}$. We first claim that it only makes sense to run our framework in settings where the ML inference is done using a secure computation: If the inference is not computed using a secure computation, then one option is for the client to learn the model and run by itself a check for fairness, or send the model to another party and ask it to do this check. Another option is that the client simply hands over its input to the model owner, but this would require prohibitively expensive zero-knowledge proofs, to be computed at the owner side, to attest to fairness of the output without revealing anything about the model.

Therefore, given that inference is done via secure computation, the parties must incur the cost of running a secure computation of the inference, and the efficiency of the framework should be measured by the additional overhead that is added on top of the secure inference.

The main computational tasks that are run by $\pi_{\mathtt{Framework}}$ are as follows:

The Certification phase runs $m$ instances of a secure computation of inference and in addition computes a hash of the model and checks the accuracy of the output.

The Inference phase runs a single secure computation of the inference and in addition computes a hash of the model.

The Certification phase is a one-time event, and therefore its overhead is less critical. Theorem 1 shows that the number of samples $m_{g}$ per group should be $m=\frac{2}{(EFG-\epsilon)^{2}}\ln\frac{2|G|}{\delta^{2}}$. Setting for example $EFG=0.05,\epsilon=0.1,\delta=0.2$ and considering $|G|=100$ groups, we get that $m_{g}\approx 6800$, which does not seem to be too far off from existing training set sizes.

As for the cost of computing $M(\cdot)$, current secure computation implementations for this task only hide the weights of a DNN but reveal the actual network structure and activation functions. We assume that our secure computation will also only hide the weights as this seems to be a standard assumption. Therefore, we ask what is the additional cost of hashing this data over the default cost of using the weights in the computation of the model.

There is a lot of current work on lightweight hashing schemes for usage in zero-knowledge proofs, and it is reasonable to expect that a lot of improvements in this area will be made in the near future. As a baseline, we consider the Keccak-F function, which is the basis of the SHA3 standard. That function takes a 1600 bit input and can be implemented by a Boolean circuit of 38,400 AND gates (see Abril et al. ([n.d.])), i.e. 24 AND gates per input bit. If we use a Merkle tree then the total number of hashes is twice the number of input blocksWe can improve on that by having the circuit output to $\mathcal{C}$ the results of the first layer of the Merkle tree, and have $\mathcal{C}$ locally compute the rest of the tree. For this to work, we will on the other hand have to add random values to each input block to avoid lookup table-based attacks on preimages of $H_{k}$.. Therefore, the total cost is about 48 AND gates per input bit.

Now, with regards to the secure evaluation of the model (not considering special MPC implementations for secure inferenceThis analysis neglects recent works such as e.g. (Barak et al., 2019) that apply to special types of networks only. We believe that the accuracy of the networks such as MobileNets that are used in (Barak et al., 2019) is too low to be of use for fairness testing. ), let us consider a setting where the weights have 32 bit fixed-point values. The cost per each weight (when used in DNN inference) must be at least that of multiplying the weight with either an input or output of a hidden layer and adding all these products together (neglecting the cost of the activation function). Multiplying the weight with a 32 bit value costs $185$ ANDs per input bit, while adding up the result would only require $6$ ANDs per input bit (see (Abril et al., [n.d.])), and we therefore take the assumption that the total cost of the secure computation is $191$ AND gates per bit of the weights (neglecting the activation function). Therefore the fairness verification increases the cost of inference in this model by only about $25\%$. While using optimized implementations for inference will make the additional overhead from hashing larger, we can in practice lower the cost of hashing drastically by exploiting special properties of $\mathcal{F}_{\mathtt{SC}}$ which allow the use of homomorphic commitments. We leave such specialized hashing techniques as interesting future work.

Experiments

We provide empirical evidence to demonstrate that the assumptions made for the fairness tests are meaningful.

We used six different datasets from various domains: visual (UTKFaces (Zhang et al., 2017), LFW (Huang et al., 2007), Colored-MNIST (Arjovsky et al., 2019), and a subset of CelebAWe annotated 8,500 celebrities out of 10,177 in the dataset for ethnicity using Amazon Mechanical Turk. Three turkers annotated three images of each of the 8,500 celebrities, resulting in 177,683 images. The annotations can be downloaded from www.github.com/will/be/published/. (Liu et al., 2015)), tabular (Adult Income (Kohavi, 1996)) and spoken (TIMIT (Garofolo et al., 1993)). The datasets vary in size and disparity of minority groups and as such some can be used to create fair or unfair models based on their empirical fairness gap (EFG). We demonstrate the variety of our datasets and detail the preprocess in supplementary materials.

In the following setup, we assume that $\mathcal{R}$ possesses a subset of secret samples to be used to certify a model $M$ for fairness and accuracy. Naturally, we split the data into a training and test subset. Setting $\epsilon$-fair and $\delta$-confidence thresholds, we can certify whether a model is fair using the conditions in 1. A bottleneck of these conditions is our dependency on the size of the sample set. Datasets with bigger sample set allow us to certify more (fair) models, while we were not able to certify a (fair) model if the sample set was too small, even if it is indeed truly fair under the chosen fairness metric.

We performed our test on the mentioned datasets with $\delta=0.05$ and $\epsilon\in\{0.05,0.075,0.1\}$. For some tasks this gap and confidence level might be intolerable, but for others, such as gender prediction of a face image, which is the task set for UTKFace, LFW and CelebA, it is better than the existing empirical gaps between ethnicity groups of well-known service providers’ models (Buolamwini and Gebru, 2018).

The test results for ORE are shown in Figure 5. As shown, out of the six datasets only C-MNIST and CelebA produced fair models during our training for $\epsilon=0.05$, while UTKFace has a fair model for $\epsilon=0.075$. LFW, Adult Income and TIMIT datasets are all below the threshold of all tests, either due to sample size or a large EFG. Therefore, we focus on the first three datasets as they are the only ones to pass any of our tests. Note that by adjusting the allowed bias, $\epsilon$, we can certify the other datasets. For example, the minority group in LFW has only 559 samples. With its current empirical gap, $EFG=0.049$, choosing $\epsilon=0.2$ would suffice to certify the LFW model.

To further evaluate the setup, we trained the same models with a tainted batch sampler. The sampler showed less samples from the smallest minority group-label pair $(g_{1},y_{1})$ in each batch in order to generate a synthetic sample disparity. We denoted these models as Bias in Fig. 5 and Table 1. The taint resulted in an almost as accurate model with a much larger EFG, suggesting they are less fair. For EO, only CelebA had enough samples to certify a model for $\epsilon=0.05$. It requires at least twice as many samples (since we count $m_{g,y}$ instead of $m_{g}$). We find it interesting as it implies the amount of data should be a consideration even for which definition of fairness is practical to choose. We detail the results for EO and DP metrics in the supplementary materials. Results for bias C-MNIST does not appear in Figure 5 since its performance is significantly worse.

Augmented Public Data Setup.

In this setup, all the data used in the test is known to all participants. With that in mind, we show a potential augmentor for datasets of images and demonstrate empirically that unfair models cannot pass our test as both accurate and fair. Even though the training set is the same as the test set, the key difference is that $\mathcal{S}$ fixes $M$ before we apply our augmentor to the dataset with new randomness. This generates diverse enough samples, for which models that are fair and generalize well on augmented samples pass the test, while models which are either unfair or bad at generalization fail the test. Our augmentations include rotation, cropping, blanked pixels (Zhong et al., 2017) and added Gaussian noise. Each augmentation was set to be invoked at a certain probability threshold which was chosen randomly. The augmented images should keep the same label and group as the original image to the human eye. By doing so, we hope to generate varied data that cannot be easily reversed or overfitted on.

We tested our three image datasets using the ORE metric, the results are in Table 1. We used the same method to generate fair and unfair models as in the private data section, except that during training we used the augmentor per sample to generate a new augmented sample each time. When we trained the models on the original dataset, the models were not able to generalize on the augmented data.

The results show that there exists a margin in EFG between the fair and unfair models on UTKFace, C-MNIST and CelebA, while the margin is different between datasets, potentially due to their varying size and different complexities of the tasks. This suggests the existence of some $\alpha$ per dataset, based on 1, but we were not able to pinpoint the exact $\alpha$. We conducted further attempts to characterize $\alpha$ in supplementary materials.

Attacks Against Public Fairness Tests.

As we assume that our test works without knowledge of the concrete model, our scheme might be susceptible to an indirect attack on our augmentor. For example, if the model could distinguish between the public data available and a new sample, it could try and behave fairly during the test, but unfairly when an actual new sample is shown. To mimic such an attack, we tested on UTKFace whether it is easy to fool our test using a simple $k$-nearest neighbour algorithm (kNN) or an out-of-distribution detection technique , ODIN (Liang et al., 2017), on top of a fair classifier to identify the augmented samples. For a fixed threshold distance from our augmented dataset, we switch to the unfair model and otherwise output the class identified by the kNN. For the ODIN attack, we create a threshold to detect out-of-distribution samples to switch to the unfair classifier. Ideally these attacks use a fair classifier to pass the test as fair when needed, while future new samples (being “far enough” in threshold terms) invoke the unfair model as predictor. We gave the kNN augmented samples of the test as referenced neighbors and plotted the accuracy and EFG by the threshold distance for $k=1$ in Fig. 6a-b (larger $k$ had worse results). In order to have a similar EFG to the fair model, it has to suffer a drop in accuracy; from 91.44% to 81.9%.

In the other attack, we tuned ODIN’s hyperparameters, taking the values which had at least 95% success rate identifying test samples and had the best results at detecting new samples as out-of-distribution. Further details on tuning are listed in the supplementary materials. We plotted the train and test detection rate as out-of-distribution by threshold in Fig. 6c. As can be seen, the sets are detected at similar rates, and are nearly indistinguishable. This resulted in a similar fair or unfair behavior depending on the chosen threshold.

These experiments suggest that these types of attacks are not a good approach to attack the proposed verification test, as this hybrid models cannot pass as both fair and accurate enough for practical applications.

Discussion & Future Work

We present an interactive test to verify fairness of any machine learning model using cryptographic tools. The interactive test ensures $\mathcal{R}$ does not learn $M$, $x$ does not leak to $\mathcal{S}$, and $M$ does not leak to $\mathcal{C}$, yet it verifies the model was used during inference has been certified by $\mathcal{R}$. We experimented with two scenarios where the test data is either public or private. We provide analysis and guarantees for the test data, as well as rigorously define the relation between the empirical fairness gap to the sample set sizes.

Moreover, from our guarantees and experiments we noticed not all fairness definitions are created equally, some are harder to verify and require a much larger volumes of data, i.e. EO requires at least twice as many samples as ORE. This leaves room for consideration on what practical definition should we aim for with respect to limited resources or what compromise needs to be made in terms of fairness gap and certainty ($\epsilon$ and $\delta$).

For future work we would like to further explore the public data scenario. Specifically, to characterize the detectable fairness hyper-parameter $\alpha$ and its relation to other parameters like the sample set size $T$, the amount of randomness used per augmentation, etc. Additionally, we would like to explore whether these parameters can be estimated in advance, without having to conduct experiments on a dataset. Results suggest that this is a challenge on its own. Moreover, as we are dealing with large models we also require to hash the model inside secure computation. This step has substantial cost, and it is an open question if it could be made more efficient in practice using different ideas than ours. Lastly, the proposed method is focused on group-based fairness definitions, exploring other fairness definitions is also an interesting research direction.

References

Appendix A Claims Proofs

Using Hoeffding’s concentration bound for any $g\in G$:

Given that the good event holds then, by applying the triangle inequality twice, for any $g_{0},g_{1}\in\mathcal{G}$ we have:

proof

Appendix B Experiments Details

UTKFace (Zhang et al., 2017) is a dataset of face images with attribute annotation for age, ethnicity (called race and annotated as black, asian, white or other), and gender (male or female). We focused on gender prediction as a task across two ethnicity groups black and white and discarded all other samples, so we were left with 14,604 samples, which we split equally to train and test sets. The dataset consists of 70% white and 30% black, 53% male and 47% female.

MNIST is originally a dataset of hand-written digits from 0 to 9. The dataset is used to predict the digit in the image without additional annotations, hence there are 10 classes across the dataset without any allocation of groups. We changed the task to a binary classification and synthetically generated two fairness groups of digits based on MNIST data. Therefore, we assign the label 0 to the digits 0-4 and the label 1 to the digits 5-9. We randomly colored half of the dataset’s digits in red as was done in (Arjovsky et al., 2019), resulting in 50% red digits and 50% white digits – these were the fairness groups. We called this dataset C(olored)-MNIST.

LFW (Huang et al., 2007) is a dataset of face images with attributes annotation (Kumar et al., 2009). Using the “Black” attribute we divided the data into two groups, while using “Male” as a binary label.

CelebA (Liu et al., 2015) is a face recognition dataset consisting of more than 10,000 different celebrities with gender labelling. We annotated 8,500 celebrities out of 10,177 in the dataset for ethnicity using Amazon Mechanical Turk. Three turks annotated three images of each of the 8,500 celebrities, resulting in 177,683 images classified as either Asian, African, Caucasian or OtherThe annotations can be downloaded from https://github.com/ShaharKSegal/CelebA_Samples. During our experiments we merged all but the Caucasian group to produce a large dataset to showcase our setup, having over 30,000 samples for the minority group.

Adult Income (Kohavi, 1996) is a tabular features dataset with a label for low/high income. We used the gender feature as group affiliation and income for labels. During the preprocessing all numeric features were normalized, while categorical features were transformed into one-hot vectors in order to be used later by DNN models.

TIMIT (Garofolo et al., 1993) is a voice recognition dataset with dialects and gender annotation. We used the different dialects as groups and gender of speaker as label. To have more samples per dialect, we merged dialects which have much in common and are considered similar, namely we merge New England with New York City and Northern with North Midland, while discarding the rest.

Private and Public Data Setup Full Results

The full results for overall risk equality, equalized odds and demographic parity in the private setup can be found in Table 2. In the public setup We’ve also experimented with cutting the UTKFace dataset in half, to see how it affects the margin and $\alpha$. We include results for the LFW dataset. Since we could not generate a fair model in LFW, we have no reference or evidence of margin, but empirically the EFG seems high suggesting the augmentation would work on it as well. The public setup results are in Table 4.

ODIN Tuning

We tuned ODIN’s 3 hyperparameters - T temperature, $\epsilon$ perturbation and $\delta$ threshold. We did so in a similar fashion of its original paper (Liang et al., 2017). We chose T from among $\{1,10,100,1000\}$, $\epsilon$ from 30 evenly spaced numbers between 0 and 0.01 and took those which yielded the best results for any $\delta\in$. We note that the hyperparameter tuning had little effect, as most of the values chosen performed very similarly.

Testing with unknown margin

In certain scenarios it might be hard to determine $\alpha$ necessary for the fairness test in advance. For example, UTKFace in the augmented public data setup has a different fairness gap than the one seen when private data is used, and the fairness gap is influenced by the sample set size. To further investigate the nature of our augmentation under the assumption that the gap is unknown, we tested the models under an increasingly larger degree of augmentation (frequency that each augmentation is invoked) for each sample. The changes in accuracy and fairness gap are presented in Table 5. The accuracy decreases as we increase the augmentation degree, which fits the idea that it might be hard to generalize on the augmented data. Hence, more augmentation yields less accuracy. The fairness gap, on the other hand, had inconclusive results: increasing the augmentation degree had little or no effect on CelebA dataset, while it greatly varied on UTKFace between fair and unfair models.