# Fair Representations by Compression

Xavier Gitiaux, Huzefa Rangwala

###### Abstract

Organizations that collect and sell data face increasing scrutiny for the
discriminatory use of data. We propose a novel unsupervised approach to
transform data into a compressed binary representation independent of
sensitive attributes. We show that in an information bottleneck framework, a
parsimonious representation should filter out information related to sensitive
attributes if they are provided directly to the decoder. Empirical results
show that the proposed method, FBC, achieves state-of-the-art accuracy-
fairness trade-off. Explicit control of the entropy of the representation bit
stream allows the user to move smoothly and simultaneously along both rate-
distortion and rate-fairness curves.

##  1 Introduction

A growing body of evidence has questioned the fairness of machine learning
algorithms across a wide range of applications, including judicial decisions
(ProPublica 2016), face recognition (Buolamwini and Gebru 2018), degree
completion (Gardner, Brooks, and Baker 2019) or medical treatment (Pfohl et
al. 2019). Of particular concerns are potential discriminatory uses of data on
the basis of racial or ethnic origin, political opinion, religion, or gender.

Therefore, organizations that collect and sell data are increasingly liable if
future downstream uses of the data are biased against protected demographic
groups. One of their challenges is to anticipate and control how the data will
be processed by downstream users. Unsupervised fair representation learning
approaches (Madras et al. (2018), Zemel et al. (2013), Gitiaux and Rangwala
(2020), Moyer et al. (2018)) offers a flexible fairness solution to this
challenge. A typical architecture in fair representation learning includes an
encoder that maps the data into a representation and a decoder that
reconstructs the data from its representation. The objective of the
architecture is to extract from a data $X$ the underlying latent factors $Z$
that correlate with unobserved and potentially diverse task labels, while
remaining independent of sensitive factors $S$.

This paper asks whether an encoder that filters out information redundancies
could generate fair representations. Intuitively, if sensitive attributes $S$
are direct inputs to the decoder, an encoder that aims for conciseness would
not waste code length to encode information related to $S$ in the latent
factors $Z$. We show that in an information bottleneck framework (Tishby,
Pereira, and Bialek 2000), this intuition is theoretically founded:
constraining the information flowing from the data $X$ to the representation
$Z$ forces the encoder to control the dependencies between sensitive
attributes $S$ and representations $Z$. _It is sufficient to constraint the
mutual information $I(Z,X)$ between $Z$ and $X$ in order to minimize the
mutual information $I(Z,S)$ between $Z$ and $S$._

Therefore, instead of directly penalizing $I(Z,S)$, we recast fair
representation learning as a rate distortion problem that controls explicitly
the bit rate $I(Z,X)$ encoded in the latent factors $Z$. We model the
representation $Z$ as a binary bit stream, which allows us to monitor the bit
rate more effectively than floating point representations that may maintain
redundant bit patterns. We estimate the entropy of the code $Z$ with an
auxiliary auto-regressive network that predicts each bit in the latent code
$Z$ conditional on previous bits in the code. One advantage of the method is
that the auxiliary network collaborates with the encoder to minimize the
cross-entropy of the code.

Empirically, we demonstrate that the resulting method, Fairness by Binary
Compression (henceforth, FBC) is competitive with state-of-the art methods in
fair representation learning. Our contributions are as follows:

  1. 1.

We show that controlling for the mutual information $I(Z,X)$ is an effective
way to remove dependencies between sensitive attributes and latent factors
$Z$, while preserving in $Z$, the information useful for downstream tasks.

  2. 2.

We find that compressing the data into a binary code as in FBC generates a
better accuracy-fairness trade-off than limiting the information channel
capacity by adding noise (as in variants of $\beta$-VAE, (Higgins et al.
2017)).

  3. 3.

We show that increasing the value of the coefficient on the bit rate
constraint $I(Z,X)$ in our information bottleneck framework allows to move
smoothly along both rate-distortion and rate-fairness curves.

Related work. The machine learning literature increasingly explores how
algorithms can adversely impact protected demographic groups (e.g individuals
self-identified as Female or African-American) (see Chouldechova and Roth
(2018) for a review). Research questions revolve around how to define fairness
(Dwork et al. (2012)), how to enforce fairness in standard classification
algorithms (e.g. Agarwal et al. (2018), Kim, Reingold, and Rothblum (2018),
Kearns et al. (2018)) or audit a black box classifier for its fairness (e.g
Feldman et al. (2015), Gitiaux and Rangwala (2019)).

This paper relates to recent efforts towards transforming data into fair and
general purpose representations that are not tailored to a pre-specified
specific downstream task. Many contributions use a supervised setting where
the downstream task label is known while training the encoder-decoder
architecture (e.g Madras et al. (2018), Edwards and Storkey (2015), Moyer et
al. (2018) Song et al. (2018) or Jaiswal et al. (2019)). However, Zemel et al.
(2013), Gitiaux and Rangwala (2020) and Locatello et al. (2019) argue that in
practice, an organization that collects data cannot anticipate what the
downstream use of the data will be. In this unsupervised setting, the
literature has focused on penalizing approximations of the mutual information
between representations and sensitive attributes: maximum mean discrepancy
penalty (Gretton et al. (2012)) for deterministic (Li, Swersky, and Zemel
(2014)) or variational (Louizos et al. (2015)) autoencoders (see Table 1);
cross-entropy of an adversarial auditor that predicts sensitive attributes
from the representations (Madras et al. (2018), Edwards and Storkey (2015),
Zhang, Lemoine, and Mitchell (2018) or Xu et al. (2018)).

Methods | Fairness by controlling: | Examples
---|---|---
| $I(Z,S)$ | $I(Z,X)$ |
Adversarial | Minimizing auditor’s | ✗ |  Madras et al. (2018), Edwards and Storkey (2015),
| cross-entropy |  | Creager et al. (2019)
MMD | Mimizing maximum | ✗ |  Li, Swersky, and Zemel (2014), Louizos et al. (2015)
| mean discrepancy |  |
$\beta-$ VAE | ✗ | Noisy $Z$ |  Higgins et al. (2017), This paper
FBC | ✗ | Binary $Z$ | This paper
Table 1: Methods in unsupervised fair representation learning organized by
whether the fairness properties of the learned representations is obtained by
minimizing the mutual information between sensitive attributes $S$ and
representations $Z$; or by minimizing the mutual information between data $X$
and representations $Z$; and whether $Z$ is modelled as a binary bit stream or
is convolved with Gaussian noise.

Our approach contrasts with existing work since it does not control directly
for the leakage between sensitive attributes and representations. FBC obtains
fair representations only by controlling its bit rate. In a supervised
setting, Jaiswal et al. (2019) show that nuisance factors can be removed from
a representation by over-compressing it. We extend their insights to
unsupervised settings and show the superiority of bit stream representations
over noisy ones to remove nuisance factors. Our insights could offer an
effective alternative to methods that learn representations invariant to
nuisance factors (e.g. (Achille and Soatto 2018), (Jaiswal et al. 2020),
(Jaiswal et al. 2018)).

Our paper borrows soft-quantization techniques when backpropagating through
the model (Agustsson et al. 2017) and hard quantization techniques during the
forward pass (Mentzer et al. 2018). We find that in our fair representation
setting, explicit control of the bit rate of the representation leads to
better accuracy-fairness trade-off than floating point counterpart. We
estimate the entropy of the code as in Mentzer et al. (2018) by computing the
distribution $P(Z)$ of $Z$ as an auto-regressive product of conditional
distributions, and by modeling the auto-regressive structure with a PixelCNN
architecture (Oord, Kalchbrenner, and Kavukcuoglu (2016), Van den Oord et al.
(2016)).

##  2 Fair Information Bottleneck

Consider a population of individuals represented by features
$X\in\mathcal{X}\subset[0,1]^{d_{x}}$ and sensitive attributes in
$S\in\mathcal{S}\subset\\{0,1\\}^{d_{s}}$, where $d_{x}$ is the dimension of
the feature space and $d_{s}$ is the dimension of the sensitive attributes
space. In this paper, we do not restrict ourselves to binary sensitive
attributes and we allow $d_{s}>1$. The objective of fair representation
learning is to map the features space $\mathcal{X}$ into a $m-$dimensional
representation space $\mathcal{Z}\subset[0,1]^{m}$, such that (i) $Z$
maximizes the information related to $X$, but (ii) minimizes the information
related to sensitive attributes $S$. We can express this as

$\max_{Z}I(X,\\{Z,S\\})-\gamma I(Z,S)$ (1)

where $I(X,S)$ and $I(X,\\{Z,S\\})$ denote the mutual information between $Z$
and $S$ and between $X$ and $(Z,S)$, respectively; and $\gamma\geq 0$ controls
the fairness penalty $I(Z,S)$.

Existing methods focus on solving directly the problem (1) by approximating
the mutual information $I(Z,S)$ between $Z$ and $S$ via the cross-entropy of
an adversarial auditor that predicts $S$ from $Z$ (Madras et al. (2018),
Edwards and Storkey (2015), Gitiaux and Rangwala (2020)) or via the maximum
mean discrepancy between $Z$ and $S$ (Louizos et al. (2015)).

In this paper, we instead reduce the fair representation learning program (1)
to an information bottleneck problem that consists of encoding $X$ into a
parsimonious code $Z$, while ensuring that this code $Z$ along with a side
channel $S$ allows a good reconstruction of $X$. The mutual information
between $X$ and $S$ can be written as

$\begin{split}I(Z,S)&\overset{(a)}{=}I(Z,\\{X,S\\})-I(Z,X|S)\\\
&\overset{(b)}{=}I(Z,X)+I(Z,S|X)-I(Z,X|S)\\\
&\overset{(c)}{=}I(Z,X)-I(Z,X|S)\\\
&\overset{(d)}{=}I(Z,X)-I(X,\\{Z,S\\})+I(X,S).\end{split}$

where $(a)$, $(b)$ and $(d)$ use the chain rule for mutual information; and,
$(c)$ uses the fact that $Z$ is only encoded from $X$, so $H(Z|X,S)=H(Z|X)$
and $I(Z,S|X)=H(Z|X)-H(Z|X,S)=0$. Since the mutual information between $X$ and
$S$ does not depend on the code $Z$, the fair representation learning (1) is
equivalent to the following fair information bottleneck:

$\max\limits_{Z}(1+\gamma)I(X,\\{Z,S\\})-\gamma I(Z,X).$ (2)

Intuitively, compressing information about $X$ forces the code $Z$ to avoid
information redundancy, particularly redundancy related to the sensitive
attribute $S$, since the decoder has direct access to $S$. Note that there is
no explicit constraint in (2) to impose independence between $Z$ and $S$.

If the representation $Z$ is obtained by a deterministic function of the data
$X$, once $X$ is known, $Z$ is known and $H(Z|X)=0$. Therefore, the mutual
information $I(Z,X)$ is equal to the entropy $H(Z)$ of the representation $Z$.
Since the entropy of the data $X$ does not depend on the representation $Z$,
we can replace $I(X,\\{Z,S\\})=H(X)-H(X|Z,S)$ by $E_{z,s,x}\log(P(x|z,s)$ in
the information bottleneck (2) and solve for:

$\min\limits_{Z}E_{x,z,s}[-\log(P(X|Z,S)]+\beta H(Z),$ (3)

where $\beta=\gamma/(\gamma+1)$. Therefore, the fair representation problem,
in its information bottleneck interpretation, can be recast as a rate-
distortion trade-off. A lossy compression of the data into a representation
$Z$ forces the independence between sensitive attribute and representation but
increases the distortion cost measured by the negative log-likelihood of the
reconstructed data $E_{x,z,s}[-\log(P(X|Z,S)]$. The parameter $\beta$ in
equation (3) controls the competitive objectives of low distortion and
fairness-by-compression: the larger $\beta$, the fewer the dependencies
between $Z$ and $S$.

##  3 Proposed Method

There are two avenues to control for $I(Z,X)$ in the information bottleneck
(2) (see Figure 1): (i) adding noise to $Z$ to control the capacity of the
information channel between $X$ and $Z$; or, (ii) storing $Z$ as a bit stream
whose entropy is explicitly controlled.

The noisy avenue (i) is a variant of variational autoencoders, so called
$\beta-$VAE (Higgins et al. 2017), that models the posterior distribution
$P(Z|X)$ of $Z$ as Gaussian distributions (see Figure 1(a)). The channel
capacity and thus the mutual information between $X$ and $Z$ is constrained by
minimizing the Kullback divergence between these posterior distributions and
an isotropic Gaussian prior (Braithwaite and Kleijn (2018)). In the context of
fair representation learning, (Louizos et al. 2015) and (Creager et al. 2019)
use variants of $\beta-$VAE, but do not focus on how limiting the channel
capacity $I(Z,X)$ could lead to fair representations. Instead, they add
further constraints on $I(Z,S)$.

$\mathbf{X}$Encoder
$F(\mathbf{X})$$\mu,\sigma$$Z\sim\mathcal{N}(\mu,\sigma^{2})$$\mathbf{Z}$Decoder
$G(\mathbf{Z},\mathbf{S})$$S$ (a) $\beta-$VAE

$\mathbf{X}$Encoder $F(\mathbf{X})$$\mathbf{e}$Binarizer
$B(e)$$\mathbf{Z}$Decoder $G(\mathbf{Z},\mathbf{S})$$S$ (b) FBC

Figure 1: Unsupervised methods to obtain fair representations $z$ by
compression. Variables are: features $X$; sensitive attribute $S$;
representation $Z$. $\beta-$VAE generates noisy representations with mean
$\mu$ and variance $\sigma^{2}$. FBC generates binary representations.

We implement the binary avenue with a method –FBC (see Figure 1(b)) – that
consists of an encoder $F:\mathcal{X}\rightarrow\mathbb{R}^{m}$, a binarizer
$B:\mathbb{R}^{m}\rightarrow\\{0,1\\}^{m}$ and a decoder
$G:\\{0,1\\}^{m}\times\mathcal{S}\rightarrow\mathcal{X}$. The encoder $F$ maps
each data point $x$ into a latent variable $e=F(x)$. The binarizer $B$
binarizes the latent variable $e$ into a bit stream $z$ of length $m$. The
decoder $G$ reconstructs a data point $\hat{x}=G(z,s)$ from the bitstream $z$
and the sensitive attribute $s$. We model encoder and decoder as neural
networks whose architecture varies with the type of data at hand.

The binarization layer controls explicitly the bit allowance of the learned
representation and thus forces the encoder to strip redundancies – including
sensitive attributes. Binarization is a two step process: (i) mapping the
latent variable $e$ into $[0,1]^{m}$; (ii) converting real values into 0-1
bit. We achieve the first step by applying a neural network layer with an
activation function $\overline{z}=(\tanh(e)+1)/2$. We achieve the second step
by rounding $\overline{z}$ to the closest integer $0$ or $1$. One issue with
this approach is that the resulting binarizer $B$ is not differentiable with
respect to $\overline{z}$. To sidestep the issue, we follow Mentzer et al.
(2018) or Theis et al. (2017) and rely on soft binarization during backward
passes through the neural network. Formally, during a backward pass we replace
$z$ by a soft-binary variable $\dot{z}$:

$\dot{z}=\frac{exp(-\sigma||\overline{z}-1||_{2}^{2})}{exp(-\sigma||\overline{z}-1||_{2}^{2})+exp(-\sigma||\overline{z}||_{2}^{2})},$

where $\sigma$ is an hyperparameter that controls the soft-binarization.
During the forward pass, we use the binary variable $z$ instead of its soft-
binary counterpart $\dot{z}$ to control the bitrate of the binary
representation $Z$ 111In Pytorch, the binarizer returns
$(z-\dot{z}).detach()+\dot{z}$..

To estimate the entropy $H(z)$, we factorize the distribution $P(z)$ over
$\\{0,1\\}^{m}$ by writing $z=(z_{1},...,z_{m})$ (Mentzer et al. (2018)) and
by computing $P(z)$ as the product of conditional distributions:

$P(z)=\displaystyle\prod_{i=1}^{m}p(z_{i}|z_{i-1},z_{i-2},...,z_{1})\triangleq\displaystyle\prod_{i=1}^{m}p(z_{i}|z_{.<i}),$
(4)

where $z_{.<i}=(z_{1},z_{2},...,z_{i-1})$. The order of the bits $z_{1}$, …,
$z_{m}$ is arbitrary, but consistent across all data points. We model $P$ with
a neural network $Q$ that predicts the value of each bit $z_{i}$ given the
previous values $z_{i-1},z_{i-2},...,z_{1}$. With the factorization (4), the
entropy $H(z)$ is given by

$\begin{split}H(z)&=E_{z}\left[\displaystyle\sum_{i=1}^{m}-\log(Q(z_{i}|z_{.<i}))\right]-KL(P||Q)\\\
&\leq CE(P,Q),\end{split}$ (5)

where $CE(P,Q)$ is the cross entropy between $P$ and $Q$. Therefore,
minimizing the cross-entropy loss of the neural network $Q$ minimizes an upper
bound of the entropy of the code $z$. The encoder $F$ and the entropy
estimator $Q$ cooperate. The lower the cross-entropy of $Q$ is, the lower is
the estimate of the bit rate $H(z)$. Therefore, the encoder has incentives to
make the bit stream easy to predict for the neural network $Q$. Designing a
powerful predictor for the bit stream $z$ does not necessary complicate the
loss landscape, unlike what could happen with adversarial methods (Berard et
al. (2019)).

Since the prediction of $Q$ for the $i^{th}$ bit depends on the values of the
previous bits $z_{i-1}$, …, $z_{1}$, the factorization of $P(z)$ imposes a
causality relation, where the $(i+1)^{th}$, …, $m^{th}$ bits should not
influence the prediction for $z_{i}$. We could enforce this causality
constraint by using an iterative method that would first compute
$P(z_{2}|z_{1})$, then $P(z_{3}|z_{1},z_{2})$,…, and lastly,
$P(z_{m}|z_{1},...,z_{m-1})$. However, it will require $O(m)$ operations that
cannot be parallelized. Instead, we follow Mentzer et al. (2018) and enforce
the causality constraint by using an architecture for $Q$ similar to PixelCNN
(Van den Oord et al. (2016), Oord, Kalchbrenner, and Kavukcuoglu (2016)). We
model $z$ as a $2D$ $\sqrt{m}\times\sqrt{m}$ matrix and convolve it with one-
zero masks, which are equal to one only from their leftmost/top position to
the center of the filter. Intuitively, the $i^{th}$ output from this
convolution depends only on the bits located to the left and above the bit
$z_{i}$. The advantage of using a PixelCNN structure, as noted in Mentzer et
al. (2018), is to enforce the causality constraint and compute
$P(z_{i}|z_{.<i})$ for all bits $z_{i}$ in parallel, instead of computing
$P(z_{i}|z_{.<i})$ sequentially from $i=1$ to $i=m$.

##  4 Experiments

Figure 2: Pareto Front for fair representation learning approaches for
DSprites and three benchmark datasets. This shows an accuracy-fairness trade-
off by comparing the accuracy $A_{s}$ of auditors that predict sensitive
attributes $S$ from representations $Z$ to the accuracy of predicting a task
label $Y$ from $Z$. The dashed horizontal line represents the chance level of
predicting $Y$. The dashed vertical line represents the chance level of
predicting $S$. Ranges of $x-$ and $y-$ axes varies across datasets.

###  4.1 Comparative Methods

The objective of this experimental section is to demonstrate that Fairness by
Binary Compression – FBC – can achieve state-of-the art performance compared
to four benchmarks in fair representations learning: $\beta$-VAE, Adv, MMD and
VFAE.

  1. (i)

$\beta$-VAE (Higgins et al. (2017)) solves the information bottleneck by
variational inference and generates fair representations by adding Gaussian
noise which upper-bounds the mutual information between $Z$ and $X$;

  2. (ii)

MMD ((Li, Swersky, and Zemel 2014)) uses a deterministic auto-encoder and
enforces fairness by minimizing the maximum mean discrepancy ((Gretton et al.
2012)) between the distribution of latent factors $Z$ conditioned on sensitive
attributes $S$;

  3. (iii)

VFAE (Louizos et al. (2015)) extends $\beta$-VAE by adding a maximum mean
discrepancy penalty;

  4. (iv)

Adv (Edwards and Storkey (2015)) uses a deterministic auto-encoder as for MMD,
but enforces the fairness constraint by maximizing the cross-entropy of an
adversarial auditor that predicts sensitive attributes $S$ from
representations $Z$.

Although FBC shares the deterministic nature of Adv and MMD, it is more
closely related to $\beta-$VAE, since $\beta-$VAE obtains fairness without
explicit constraint on the mutual information of $I(Z,S)$. The main difference
between our approach FBC and $\beta-$VAE is that FBC controls the entropy of a
binary coding of the data, while $\beta-$VAE generates noisy representations
and approximates the mutual information $I(Z,X)$ with the Kullback divergence
between $Q(z|x)$ and a Gaussian prior $P(z)$. Note that the use of a vanilla
$\beta-$VAE in a fairness context is novel: only its cousin VFAE with an
additional MMD penalty has been proposed as a fair representation method.

Both FBC and $\beta-$VAE attempt to obtain fairness by controlling $I(Z,X)$.
However, $\beta-$VAE assumes further that the prior distribution of the
representation is an isotropic Gaussian. FBC does not require such a strong
assumption and could still work well even if the data is not generated from a
factorized distribution. $\beta-$VAE is meant to compress and factorize. The
main result from this paper is that compression is sufficient to learn fair
representations and thus, disentanglement might be too restrictive. For
problems where factorization could be hard to achieve in an unsupervised
setting (Locatello et al. 2018), we would expect FBC to outperform
$\beta-$VAE.

###  4.2 Experimental Protocol

The overall experimental procedure consists of:

  1. (i)

Training an encoder-decoder architecture $(F,B,G)$ along with an estimator of
the code entropy $Q$;

  2. (ii)

Freezing its parameters;

  3. (iii)

Training an auditing network $Aud:\mathcal{Z}\rightarrow\mathcal{S}$ that
predicts sensitive attributes from $Z$.

  4. (iv)

Training a task network $T:\mathcal{Z}\rightarrow\mathcal{Y}$ that predicts a
task label $Y$ from $Z$.

The encoder-decoder does not access the task labels during training: our
representation learning approach is unsupervised with respect to downstream
task labels. Datasets are split into a training set used to trained the
encoder-decoder architecture; two test sets, one to train both task and
auditing networks on samples not seen by the encoder-decoder; one to evaluate
their respective performances.

Pareto fronts. To compare systematically performances across methods, we rely
on Pareto fronts that estimates the maximum information that can be attained
by a method for a given level of fairness. We approximate information content
as the accuracy $A_{y}$ of the task network $T$ when predicting the downstream
label $Y$. The larger $A_{y}$, the more useful is the learned representation
for downstream task labels.

We measure how much a representation $Z$ leaks information related to
sensitive attributes $S$ by the best accuracy $A_{s}$ among a set of auditing
classifiers $Aud:\mathcal{Z}\rightarrow\mathcal{S}$ that predict $S$ from $Z$.
The intuition is that if the distributions $p(Z|S=s)$ of $Z$ conditioned on
$S$ do not depend on $s$, the accuracy of any classifier predicting $S$ from
$Z$ would remain near chance level. In the binary case
$\mathcal{S}=\\{0,1\\}$, comparing $A_{s}$ to chance level accuracy is a
statistical test of independence with good theoretical properties (Lopez-Paz
and Oquab (2016)). If the sensitive classes are furthermore balanced
($P(S=0)=P(S=1)$) and the task labels are binary ($\mathcal{Y}=\\{0,1\\}$),
$A_{s}$ estimates the worst demographic disparity that can be obtained by a
downstream task classifier $T$ that uses $Z$ as an input (Gitiaux and Rangwala
(2020)). In the general case $S=\\{0,1\\}^{d_{s}}$, the lower $A_{s}$ compared
to chance level, the more independent $Z$ and $S$ are.

Figure 3: Rate distortion/fairness curves. Each dot corresponds to one
simulation of FBC. Distortion is measured as the $l2$ loss between
reconstructed and observed data.

Rate distortion curves. To demonstrate further our theoretical insights from
section 2, we study both rate-distortion and rate-fairness curves of
compressing methods FBC and $\beta-$VAE.

The rate-distortion function $RD(D)$ of an encoder-decoder is measured as the
minimum bitrate (in nats) necessary for the distortion
$E_{x,z,s}[-\log(p(X|Z,S)]$ to be less than $D$ (Tishby, Pereira, and Bialek
(2000)):

$RD(D)=\min I(Z,X)\mbox{ s.t. }E_{x,z,s}[-\log(p(X|Z,S)]\leq D.$ (6)

We introduce a new concept, rate-fairness function $RF(\Delta)$, and define it
as the maximum bit rate allowed for the accuracy $A_{s}$ of the auditing
classifier to remain less than $\Delta$

$RF(\Delta)=\max I(Z,X)\mbox{ s.t. }A_{s}\leq\Delta.$ (7)

The rate-fairness function captures the maximum information $Z$ can contain
while keeping $A_{s}$ under a given threshold. To obtain both rate-distortion
and rate-fairness curves for either our binary compression –FBC – or
variational –$\beta$-VAE and VFAE – approaches , we vary the value of the
parameter $\beta$ controlling the rate-distortion trade-off and for each value
of $\beta$, we train the model $50$ times with different seeds. For our binary
compression method, FBC, the bit rate is approximated by the cross-entropy of
the entropy estimator $Q$ in (5); for variational-based methods, the bit rate
is approximated by the Kullback divergence between $Q(z|x)$ and a Gaussian
prior. In both cases, the approximation is an upper bound to the true bit-rate
(in nats) of $Z$. We estimate the distortion generated by the encoder-decoder
procedure as the $l_{2}$ loss between reconstructed data
$\widehat{X}=G(B(F(X)))$ and observed data $X$.

Robustness to Fairness Metrics. The fair information bottleneck (1) aims at
controlling the flow of information between $Z$ and $S$. (McNamara, Ong, and
Williamson 2017) show that minimizing $I(Z,S)$ minimizes an upper bound of the
demographic disparity $\Delta(T)$ of a task network $T$ that predicts a binary
task label $Y$ from $Z$, where demographic parity $\Delta(T)$ is defined as

$\Delta(T)=\displaystyle\sum_{s\in\mathcal{S}}|P(T(x)=1|S=s)-P(T(x)=1|S\neq
s)|.$ (8)

Moreover, the fair information bottleneck (1) is solved without a prior
knowledge of specific downstream task labels $Y$. Therefore, (1) is not
designed to control for fairness criteria that rely on labels $Y$ (e.g.
equality of odds or opportunites, (Hardt et al. 2016)) or on a specific
classifier (e.g. individual fairness, (Dwork et al. 2012)), unless downstream
task labels are orthogonal to sensitive attributes conditional on features
$X$: $Y\perp S|X$. In practice, we explore whether empirically FBC can
generate representations that exhibit for a given task network $T$, low
differences in false positive rates $\Delta FPR(T)$ with

$\begin{split}\Delta
FPR(T)&\triangleq\displaystyle\sum_{s\in\mathcal{S}}|P(T(x)=1|Y=0,S=s)\\\
&-P(T(x)=1|Y=0,S\neq s)|\end{split}$ (9)

Figure 4: Effect of $\beta$. This shows the effect of increasing the
coefficient $\beta$ for the code entropy in (3) on the bit rate and the
auditor’s accuracy $A_{s}$ of representations generated by FBC. Changes in
$\beta$ allows to move smoothly along the rate-fairness curve.

###  4.3 Datasets

First, we apply our experimental protocol to a synthetic dataset – DSprites
Unfair, 222https://github.com/deepmind/dsprites-dataset/ – that contains $64$
by $64$ black and white images of various shapes (heart, square, circle).
Images in the DSprites dataset are constructed from six independent factors of
variation: color (black or white); shape (square, heart, ellipse), scales (6
values), orientation (40 angles in $[0,2\pi]$); x- and y- positions (32 values
each). We modify the sampling to generate a source of potential unfairness and
use as sensitive attribute a variable that encodes the quadrant of the circle
the orientation angle belongs to.

Then, we extend our experimental protocol to three benchmark datasets in fair
machine learning: Adults, Compas and Heritage. The Adults dataset
333https://archive.ics.uci.edu/ml/datasets/adult contains $49K$ individuals
and includes information on $10$ features related to professional occupation,
education attainment, race, capital gains, hours worked and marital status.
Sensitive attributes is made of $10$ categories that intersect gender and race
to which individuals self-identify to. The downstream task label $Y$
correspond to whether an individual earns more than $50K$ per year.

The Compas data 444https://github.com/propublica/compas-analysis/ contains
$7K$ individuals with information related to their criminal history,
misdemeanors, gender, age and race. Sensitive attributes intersect self-
reported race and gender and result in four categories. The downstream task
label $Y$ assesses whether an individual presents a high risk of recidivism.

The Health Heritage dataset 555https://foreverdata.org/1015/index.html
contains $220K$ individuals with $66$ features related to age, clinical
diagnoses and procedure, lab results, drug prescriptions and claims payment
aggregated over $3$ years. Sensitive attributes are $18$ categories that
intersect the gender which individuals self-identify to and their reported
age. The downstream task label $Y$ relates to whether an individual has a
positive Charlson comorbidity Index.

##  5 Results and Discussion

###  5.1 Pareto Fronts

Figure 2 shows the Pareto fronts across five comparative methods for the
DSprites and real-world datasets, respectively. Across all dataset, the higher
and more leftward the Pareto front, the higher is the task accuracy $A_{y}$
for a given auditor accuracy $A_{s}$ and the better is the accuracy-fairness
trade-off. From these Pareto fronts, we can draw three conclusions.

First, on all datasets, controlling for the mutual information between $Z$ and
$X$ – as in FBC and $\beta-$VAE – is sufficient to reduce the accuracy $A_{s}$
of the auditor $Aud$. This result is consistent with our theoretical
observation that minimizing proxies for the information rate $I(Z,X)$ is
sufficient to minimize $I(Z,S)$, provided that a side-channel provides the
sensitive attributes $S$ to the decoder.

Second, in the $(A_{s},A_{y})-$ plan, our method, FBC achieves either similar
(Adults, Heritage) or better (DSprites, Compas) accuracy-fairness trade-off
than the variational method $\beta-$VAE that controls $I(Z,X)$ by adding noise
to the information channel between $X$ and $Z$. Across all experiments, the
Pareto fronts obtained from FBC are at least as upward and leftward as for
$\beta-$VAE. This is consistent with our intuition that FBC may outperform
$\beta-$VAE in situations where disentanglement of the data into factorized
representation is difficult (see (Locatello et al. 2018) for DSprites).

Third, FBC is a method that appears to be more consistently state-of-the-art
in terms of performances compared to existing methods. . FBC offers a better
accuracy-fairness trade-off for Compas and DSprites than MMD, VFAE and Adv and
is competitive for Adults and Heritage. This is true although Adv, VFAE and
MMD control directly the mutual information between $Z$ and $S$, while FBC
controls only $I(Z,X)$. The adversarial methods do not manage to generate
representations with low $A_{s}$ for the DSprites dataset, possibly because in
this higher dimensional problem, the optimization gets stuck in local minima
where the adversary has no predictive power, regardless of the encoded
representation.

###  5.2 Rate-distortion and Rate-fairness

Figure 5: Differences in false positive rates and demographic disparity of
downstream task networks. This shows pareto fronts for Adults and Compas as in
2, but using $\Delta$ ((8)) $\Delta FPR$ ( (9)) as a fairness criteria. Shaded
areas show the area between the $25-th$ and $75-th$ quantiles of the pareto
front. Figure 6: Adults – t-SNE visualizations colored with gender ($S$) and
income level ($Y$) of the representations obtained by FBC for different values
of the parameter $\beta$ controlling the compression rate of FBC.

Figure 3 confirms that for FBC, a lower bit rate estimated by the cross
entropy $CE(p,q)$ corresponds to a lower accuracy for the auditing classifier
$Aud$. Both rate-distortion $(R,D)$ and rate-fairness $(R,\Delta)$ curves show
the same monotonic behavior: as distortion moves up along the rate-distortion
curves, lack of fairness as measured by $A_{s}$ moves down. However, for real-
word datasets, particularly for Adults and Compas, we observe more variance in
the auditor accuracy’s $A_{s}$ given a representation bit rate. We attribute
this higher variance to a smaller sample size – $617$ for Compas and $3,256$
for Adult on the test set.

Figure 4 shows that controlling for the level of compression by increasing the
value of $\beta$ in (3) allows moving smoothly along the rate-fairness curve.
This is true whether the mutual information $I(Z,X)$ between data and
representation is controlled by the bitstream entropy as in FBC (Figure 4) or
by adding a noisy channel as in $\beta-$VAE (see results in appendix).
However, binary compression allows a tighter control of the fairness of the
representation $Z$ than variational-based methods since in Figure 2, for a
given auditor’s accuracy $A_{s}$, FBC allows the downstream classifier to
achieve a higher accuracy $A_{y}$ while predicting $Y$ from $Z$.

###  5.3 Other Fairness Metrics

Figure 5 extends the pareto fronts of Figure 2 to additional fairness
criteria. It plots the median accuracy obtained by task network $T$ against
its differences in false positive rates $\Delta FPR$ and its demographic
disparity $\Delta$.

First, all the methods tested – Adv, $\beta-$VAE and FBC – generate an
accuracy/fairness trade-off by reducing differences of false positive rates
and demographic disparity at the cost of a lower downstream accuracy. Figure 5
illustrates a fairness transfer, where general purpose fair representations
can offer some guarantees against some fairness criteria that the auto-encoder
is not trained to minimize. This transfer is all the more remarkable for
differences in false positive rates that rely on downstream task labels $Y$
that were not accessed by the auto-encoder during its training.

Second, for a given value of $\Delta FPR$n or $\Delta$, FBC reaches higher
task accuracy $A_{y}$ than $\beta-$VAE and is competitive with Adv for low
values of $\Delta FPR$ and $\Delta$.

###  5.4 Representation Embeddings

Figure 6 shows the $t-SNE$ visualizations (Maaten and Hinton (2008)) of the
representations generated by FBC for different values of the parameter $\beta$
that controls the rate-distortion trade-off in (3) for the Adults dataset.
Without control of the representation bit rate – $\beta=0$ – the $t-SNE$ plot
show a cluster of Females that are isolated from males and thus, are easily
detected by an auditor that predicts $S$ from $Z$.

With enough compression – $\beta=0.35$ – the representation not only looks
more parsimonious, but also does not separate Females from Males as much as
without compression ($\beta=0$). In the embeddings space, Females plots are
either within clusters of Males or on the edges of these clusters. Moreover,
the $t-SNE$ visualizations separate individuals by income level regardless of
the compression level, which confirms that the representations generated by
FBC are useful for classification tasks that predict income level from $Z$.
$t-SNE$ plots for Compas and Heritage are in the technical appendix.

To quantitatively assess the local homogeneity of the sensitive attribute in
the embedding space (Figure 6, top), we compute the average distance of
females to their top-10 male neighbors and normalize it by the average
distance between all individuals. We find that our homogeneity measure
decreases by $30\%$ when compressing the data (from left to right plot). But,
a similar measure of homogeneity for outcomes (bottom row) decreases only by
$8\%$. This result confirms the visual perception that compression decreases
the local homogeneity of sensitive attributes more than the homogeneity of
downstream task labels.

##  6 Conclusion

This paper introduces a new method – Fairness by Binary Compression (FBC) – to
map data into a latent space, while guaranteeing that the latent variables are
independent of sensitive attributes. Our method is motivated by the
observation that in an information bottleneck framework, controlling for the
mutual information between representation and data is sufficient to remove
unwanted factors, provided that these unwanted factors are direct inputs to
the decoder.

Our empirical findings confirm our theoretical intuition: FBC offers a state-
of-the-art accuracy-fairness trade-off across four benchmark datasets.
Moreover, we observe that encoding the representation into a binary stream
allows a tighter control of the fairness-accuracy trade-off than limiting the
information channel capacity by adding noise. Our results suggest further
research into encoder-decoder whose architecture allows a tighter control of
the representation’s bit rate and thus, of its fairness.

## Acknowledgments

This work is supported by the National Science Foundation grant No. 1937950.

## References

  * Achille and Soatto (2018) Achille, A.; and Soatto, S. 2018.  Emergence of Invariance and Disentanglement in Deep Representations.  _Journal of Machine Learning Research_ 19(50): 1–34.  URL http://jmlr.org/papers/v19/17-646.html.
  * Agarwal et al. (2018) Agarwal, A.; Beygelzimer, A.; Dudík, M.; Langford, J.; and Wallach, H. 2018\.  A reductions approach to fair classification.  _arXiv preprint arXiv:1803.02453_ .
  * Agustsson et al. (2017) Agustsson, E.; Mentzer, F.; Tschannen, M.; Cavigelli, L.; Timofte, R.; Benini, L.; and Gool, L. V. 2017.  Soft-to-hard vector quantization for end-to-end learning compressible representations.  In _Advances in Neural Information Processing Systems_ , 1141–1151.
  * Berard et al. (2019) Berard, H.; Gidel, G.; Almahairi, A.; Vincent, P.; and Lacoste-Julien, S. 2019.  A closer look at the optimization landscapes of generative adversarial networks.  _arXiv preprint arXiv:1906.04848_ .
  * Braithwaite and Kleijn (2018) Braithwaite, D. T.; and Kleijn, W. B. 2018.  Bounded information rate variational autoencoders.  _arXiv preprint arXiv:1807.07306_ .
  * Buolamwini and Gebru (2018) Buolamwini, J.; and Gebru, T. 2018.  Gender Shades: Intersectional Accuracy Disparities in Commercial Gender Classification.  In Friedler, S. A.; and Wilson, C., eds., _Proceedings of the 1st Conference on Fairness, Accountability and Transparency_ , volume 81 of _Proceedings of Machine Learning Research_ , 77–91. New York, NY, USA: PMLR.  URL http://proceedings.mlr.press/v81/buolamwini18a.html.
  * Chouldechova and Roth (2018) Chouldechova, A.; and Roth, A. 2018.  The frontiers of fairness in machine learning.  _arXiv preprint arXiv:1810.08810_ .
  * Creager et al. (2019) Creager, E.; Madras, D.; Jacobsen, J.-H.; Weis, M. A.; Swersky, K.; Pitassi, T.; and Zemel, R. 2019.  Flexibly fair representation learning by disentanglement.  _arXiv preprint arXiv:1906.02589_ .
  * Dwork et al. (2012) Dwork, C.; Hardt, M.; Pitassi, T.; Reingold, O.; and Zemel, R. 2012.  Fairness through awareness.  In _Proceedings of the 3rd innovations in theoretical computer science conference_ , 214–226. ACM.
  * Edwards and Storkey (2015) Edwards, H.; and Storkey, A. 2015.  Censoring Representations with an Adversary.  _arXiv preprint arXiv:1511.05897_ .
  * Feldman et al. (2015) Feldman, M.; Friedler, S. A.; Moeller, J.; Scheidegger, C.; and Venkatasubramanian, S. 2015.  Certifying and removing disparate impact.  In _Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 259–268. ACM.
  * Gardner, Brooks, and Baker (2019) Gardner, J.; Brooks, C.; and Baker, R. 2019.  Evaluating the Fairness of Predictive Student Models Through Slicing Analysis.  In _Proceedings of the 9th International Conference on Learning Analytics & Knowledge_, 225–234. ACM.
  * Gitiaux and Rangwala (2019) Gitiaux, X.; and Rangwala, H. 2019.  mdfa: Multi-Differential Fairness Auditor for Black Box Classifiers.  In _IJCAI_.
  * Gitiaux and Rangwala (2020) Gitiaux, X.; and Rangwala, H. 2020.  Learning Smooth and Fair Representations.  _arXiv preprint arXiv:2006.08788_ .
  * Gretton et al. (2012) Gretton, A.; Borgwardt, K. M.; Rasch, M. J.; Schölkopf, B.; and Smola, A. 2012\.  A kernel two-sample test.  _Journal of Machine Learning Research_ 13(Mar): 723–773.
  * Hardt et al. (2016) Hardt, M.; Price, E.; Price, E.; and Srebro, N. 2016.  Equality of Opportunity in Supervised Learning.  In Lee, D.; Sugiyama, M.; Luxburg, U.; Guyon, I.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 29. Curran Associates, Inc.  URL https://proceedings.neurips.cc/paper/2016/file/9d2682367c3935defcb1f9e247a97c0d-Paper.pdf.
  * Higgins et al. (2017) Higgins, I.; Matthey, L.; Pal, A.; Burgess, C.; Glorot, X.; Botvinick, M.; Mohamed, S.; and Lerchner, A. 2017.  beta-VAE: Learning Basic Visual Concepts with a Constrained Variational Framework.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_. OpenReview.net.  URL https://openreview.net/forum?id=Sy2fzU9gl.
  * Jaiswal et al. (2019) Jaiswal, A.; Brekelmans, R.; Moyer, D.; Steeg, G. V.; AbdAlmageed, W.; and Natarajan, P. 2019.  Discovery and Separation of Features for Invariant Representation Learning.  _arXiv preprint arXiv:1912.00646_ .
  * Jaiswal et al. (2020) Jaiswal, A.; Moyer, D.; Ver Steeg, G.; AbdAlmageed, W.; and Natarajan, P. 2020.  Invariant Representations through Adversarial Forgetting.  In _AAAI_ , 4272–4279.
  * Jaiswal et al. (2018) Jaiswal, A.; Wu, R. Y.; Abd-Almageed, W.; and Natarajan, P. 2018.  Unsupervised Adversarial Invariance.  In Bengio, S.; Wallach, H.; Larochelle, H.; Grauman, K.; Cesa-Bianchi, N.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 31. Curran Associates, Inc.  URL https://proceedings.neurips.cc/paper/2018/file/03e7ef47cee6fa4ae7567394b99912b7-Paper.pdf.
  * Kearns et al. (2018) Kearns, M.; Neel, S.; Roth, A.; and Wu, Z. S. 2018.  Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness.  In _International Conference on Machine Learning_ , 2569–2577.
  * Kim, Reingold, and Rothblum (2018) Kim, M. P.; Reingold, O.; and Rothblum, G. N. 2018.  Fairness Through Computationally-Bounded Awareness.  _arXiv preprint arXiv:1803.03239_ .
  * Li, Swersky, and Zemel (2014) Li, Y.; Swersky, K.; and Zemel, R. 2014.  Learning unbiased features.  _arXiv preprint arXiv:1412.5244_ .
  * Locatello et al. (2019) Locatello, F.; Abbati, G.; Rainforth, T.; Bauer, S.; Schölkopf, B.; and Bachem, O. 2019.  On the fairness of disentangled representations.  In _Advances in Neural Information Processing Systems_ , 14584–14597.
  * Locatello et al. (2018) Locatello, F.; Bauer, S.; Lucic, M.; Rätsch, G.; Gelly, S.; Schölkopf, B.; and Bachem, O. 2018.  Challenging common assumptions in the unsupervised learning of disentangled representations.  _arXiv preprint arXiv:1811.12359_ .
  * Lopez-Paz and Oquab (2016) Lopez-Paz, D.; and Oquab, M. 2016.  Revisiting classifier two-sample tests.  _arXiv preprint arXiv:1610.06545_ .
  * Louizos et al. (2015) Louizos, C.; Swersky, K.; Li, Y.; Welling, M.; and Zemel, R. 2015.  The variational fair autoencoder.  _arXiv preprint arXiv:1511.00830_ .
  * Maaten and Hinton (2008) Maaten, L. v. d.; and Hinton, G. 2008.  Visualizing data using t-SNE.  _Journal of machine learning research_ 9(Nov): 2579–2605.
  * Madras et al. (2018) Madras, D.; Creager, E.; Pitassi, T.; and Zemel, R. 2018.  Learning Adversarially Fair and Transferable Representations.  In Dy, J.; and Krause, A., eds., _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , 3384–3393. Stockholmsmässan, Stockholm Sweden: PMLR.  URL http://proceedings.mlr.press/v80/madras18a.html.
  * McNamara, Ong, and Williamson (2017) McNamara, D.; Ong, C. S.; and Williamson, R. C. 2017.  Provably fair representations.  _arXiv preprint arXiv:1710.04394_ .
  * Mentzer et al. (2018) Mentzer, F.; Agustsson, E.; Tschannen, M.; Timofte, R.; and Van Gool, L. 2018.  Conditional Probability Models for Deep Image Compression.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Moyer et al. (2018) Moyer, D.; Gao, S.; Brekelmans, R.; Galstyan, A.; and Ver Steeg, G. 2018.  Invariant representations without adversarial training.  In _Advances in Neural Information Processing Systems_ , 9084–9093.
  * Oord, Kalchbrenner, and Kavukcuoglu (2016) Oord, A. v. d.; Kalchbrenner, N.; and Kavukcuoglu, K. 2016.  Pixel recurrent neural networks.  _arXiv preprint arXiv:1601.06759_ .
  * Pfohl et al. (2019) Pfohl, S.; Marafino, B.; Coulet, A.; Rodriguez, F.; Palaniappan, L.; and Shah, N. H. 2019.  Creating Fair Models of Atherosclerotic Cardiovascular Disease Risk.  In _Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society_ , 271–278. ACM.
  * ProPublica (2016) ProPublica. 2016.  How We Analyzed the COMPAS Recidivism Algorithm.  _ProPublica_ .
  * Song et al. (2018) Song, J.; Kalluri, P.; Grover, A.; Zhao, S.; and Ermon, S. 2018.  Learning controllable fair representations.  _arXiv preprint arXiv:1812.04218_ .
  * Theis et al. (2017) Theis, L.; Shi, W.; Cunningham, A.; and Huszár, F. 2017.  Lossy image compression with compressive autoencoders.  _arXiv preprint arXiv:1703.00395_ .
  * Tishby, Pereira, and Bialek (2000) Tishby, N.; Pereira, F. C.; and Bialek, W. 2000.  The information bottleneck method.  _arXiv preprint physics/0004057_ .
  * Van den Oord et al. (2016) Van den Oord, A.; Kalchbrenner, N.; Espeholt, L.; Vinyals, O.; Graves, A.; et al. 2016.  Conditional image generation with pixelcnn decoders.  In _Advances in neural information processing systems_ , 4790–4798.
  * Xu et al. (2018) Xu, D.; Yuan, S.; Zhang, L.; and Wu, X. 2018.  Fairgan: Fairness-aware generative adversarial networks.  In _2018 IEEE International Conference on Big Data (Big Data)_ , 570–575. IEEE.
  * Zemel et al. (2013) Zemel, R.; Wu, Y.; Swersky, K.; Pitassi, T.; and Dwork, C. 2013.  Learning fair representations.  In _International Conference on Machine Learning_ , 325–333.
  * Zhang, Lemoine, and Mitchell (2018) Zhang, B. H.; Lemoine, B.; and Mitchell, M. 2018.  Mitigating unwanted biases with adversarial learning.  In _Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society_ , 335–340.