Linear Adversarial Concept Erasure

Introduction

This paper studies concept erasure, the removal of information from a given vector representation, such as those that are derived from neural language models (Melamud et al., 2016; Peters et al., 2018; Howard and Ruder, 2018; Devlin et al., 2019).

In this work, we focus on the case where the function $r(\cdot)$ is linear—in other words, we aim to identify and remove a linear concept subspace from the representation, preventing any linear predictor from recovering the concept. By restricting ourselves to the linear case, we obtain a tractable solution while also enjoying the increased interpretability of linear methods.

Linear concept removal was pioneered by Bolukbasi et al. (2016), who used principal component analysis to identify a linear gender bias subspace. Gonen and Goldberg (2019) demonstrate that the method of Bolukbasi et al. (2016) does not exhaustively remove bias. Another linear concept removal technique is iterative nullspace projection (INLP; Ravfogel et al., 2020). INLP learns the linear bias subspace by first training a classifier on a task that operationalizes the concept (e.g., binary gender prediction) and then isolating the concept subspace using the classifier’s learned weights.

We introduce a principled framework for linear concept erasure in the form of a linear minimax game (von Neumann and Morgenstern, 1947). In many cases, we find that this minimax formulation offers superior performance to previously proposed methods, e.g., INLP. Moreover, because the game is linear, we still retain an interpretable concept space. Given this framework, we are able to derive a closed-form solution to the minimax problem in several cases, such as linear regression and Rayleigh quotient maximization. Further, we develop a convex relaxation, Relaxed Linear Adversarial Concept Erasure (R-LACE), that allows us to find a good solution in practice for the case of classification, e.g., logistic regression. In the empirical portion of the paper, we experiment with removing information predictive of binary gender, and find our minimax formulation effective in mitigating bias in both uncontexualized, e.g., GloVe, and contextualized, e.g., BERT, representations.See § B.1 for a discussion in related ethical considerations.

Linear Minimax Games

This section focuses on the mathematical preliminaries necessary to develop linear adversarial concept removal. Specifically, we formulate the problem as a minimax game between a predictor that aims to predict a quantity that operationalizes the concept that tries to hinder the prediction by projecting the input embeddings to a subspace of predefined dimensionality. By constraining the adversarial intervention to a linear projection, we maintain the advantages of linear methods—interpretability and transparency—while directly optimizing an expressive objective that aims to prevent any linear model from predicting the concept of interest.

We briefly overview generalized linear modeling (Nelder and Wedderburn, 1972) as a unified framework that encompasses many different linear models. e.g., linear regression and logistic regression.

We consider the problem where we are given a dataset ${\mathcal{D}}=\{(y_{n},\boldsymbol{x}_{n})\}_{n=1}^{N}$ of $N$ response–representation pairs, where the response variables $y_{n}$ represent the information to be neutralized (e.g., binary gender).

We seek to minimize 1 with respect to ${\boldsymbol{\theta}}$ in order to learn a good predictor of $y_{n}$ from $\boldsymbol{x}_{n}$.

2 The Linear Bias Subspace Hypothesis

Basic linear algebra tells us that the operation ${{\footnotesize\textsf{proj}}_{B_{\perp}}}$ is represented by an orthogonal projection matrix, i.e., there is a symmetric matrix $P$ such that $P^{2}=P$ and ${{\footnotesize\textsf{proj}}_{B_{\perp}}}(\boldsymbol{x}_{m})=P\boldsymbol{x}_{m}$. This means that ${{\footnotesize\textsf{null}}}(P)$ is our bias subspace and ${{\footnotesize\textsf{range}}}(P)$ is its orthogonal complement, i.e., the space without the bias subspace. Intuitively, an orthogonal projection matrix onto a subspace maps a vector to its closest neighbor on the subspace. In our case, the projection maps a vector to the closest vector in the subspace that excludes the bias subspace.

3 Linear Minimax Games

We are now in a position to define a linear minimax game that adversarially identifies and removes a linear bias subspace. Following Ravfogel et al. (2020), we search for an orthogonal projection matrix $P$ that projects onto $B_{\perp}$, i.e., the orthogonal complement of the bias subspace $B$. We define $\mathcal{P}_{k}$ as the set of all $D\times D$ orthogonal projection matrices that neutralize a rank $k$ subspace. More formally, we have that

where $I_{k}$ denotes the $k\times k$ identity matrix and $I_{D}$ denotes the $D\times D$ identity matrix. The matrix $P$ neutralizes the $k$-dimensional subspace $B=\texttt{span}(W)$.

We define a minimax game between $P\in\mathcal{P}_{k}$ and ${\boldsymbol{\theta}}$:

where $k$—the dimensionality of the neutralized subspace—is an hyperparamter.One should choose the smallest $k$ that maximizes the loss, so as to minimize the damage to the representations. Note that 4 is a special case of the general adversarial training algorithm (Goodfellow et al., 2014), but where the adversary is constrained to interact with the input only via an orthogonal projection matrix of rank at most $k$. This constraint enables us to derive principled solutions, while minimally changing the input.Note that an orthogonal projection of a point onto a subspace gives the closest point on that subspace.

We now spell out several instantiations of common linear models within the framework of adversarial generalized linear modeling: (i) linear regression, (ii) partial least squares regression, and (iii) logistic regression.

Solving the Linear Minimax Game

We begin with the case of linear regression (Example 1). We show that there exists an optimal solution to 5 in the following proposition, proved in § B.3.

The equilibrium point of the objective below

is achieved when $P=I-\frac{X^{\top}\boldsymbol{y}\boldsymbol{y}X}{\boldsymbol{y}^{\top}XX^{\top}\boldsymbol{y}}$. At this point, the objective is equal to the variance of $\boldsymbol{y}$.

Note that the optimal direction for linear regression, $X^{\top}\boldsymbol{y}$, is the covariance between the input and the target. As the regression target is one dimensional, the covariance is a single vector. Since linear regression aims to explain the covariance, once this single direction is neutralized, the input becomes completely uninformative with respect to $\boldsymbol{y}$.

2 Rayleigh Quotient Maximization

We now turn to partial least squares regression (Wold, 1973) as a representative of a special class of objectives, which also include canonical correlation analysis (Hotelling and Pabst, 1936) and other problems. The loss function described in Example 2 is not convex due to the constraint that the parameters have unit norm. However, we can still efficiently minimize the objective making use of basic results in linear algebra. We term losses of the type in 6 Rayleigh quotient losses because they may be formulated as a Rayleigh quotient (Horn and Johnson, 2012).

We now state a general lemma about minimax games in the form of a Rayleigh quotient. This lemma allows us to show that Example 2 can be solved exactly.

where the constraint enforces that $P$ is an orthogonal projection matrix of rank $k$, has the solution

Moreover, the value of 10 is $\lambda_{k+1}$.

The PLS objective 6 has an equilibrium point where ${\boldsymbol{\theta}}$ and $P$ are given by 11 and 12.

The adversarial PLS objective Example 2 is scale invariant. Thus, it can be equivalently expressed as

The above is in the form 10 if we take $A=X^{\top}\boldsymbol{y}\boldsymbol{y}^{\top}X$. ∎

3 Classification

We now turn to the case of logistic regression. In this case, we are not able to identify a closed-form solution, so we propose a practical convex relaxation of the problem that can be solved with iterative methods. Note that while our exposition focuses on logistic regression, any other convex loss, e.g., hinge loss, may be substituted in.

In the general case, minimax problems are difficult to optimize. However, one special case that is generally well-behaved is that of convex–concave game, i.e., where the outer optimization problem is concave and the inner is convex (Kneser, 1952; Tuy, 2004).

4 R-LACE : A Convex Relaxation

In this section, we describe Relaxed Linear Adversarial Concept Erasure (R-LACE), an effective method to solve the objective 4 for classification problems. To overcome the non-convex nature of the problem, we propose to relax $\mathcal{P}_{k}$ to its convex hull:

In the case of a rank-constrained orthogonal projection matrix, the convex hull is called the Fantope (Boyd and Vandenberghe, 2014):

We solve the relaxed objective 18 with alternate minimization and maximization over ${\boldsymbol{\theta}}$ and $P$, respectively. Concretely, we alternate between: (a) holding $P$ fixed taking an unconstrained gradient step over ${\boldsymbol{\theta}}$ towards minimizing the objective; (b) holding ${\boldsymbol{\theta}}$ fixed and taking an unconstrained gradient step towards maximizing the objective; (c) adhering to the constraint by projecting $P$ onto the Fantope, using the algorithm given by Vu et al. (2013). See § B.4 for more details on the optimization procedure and Alg. 1 for a pseudocode of the complete algorithm.

Relation to INLP

The method constructs the linear bias subspace $B$ iteratively by finding directions ${\boldsymbol{\theta}}$ that minimize 4 and neutralizing them by projecting the representation to their nullspace. This iterative process is aimed to eliminate from the representation space any features that are used by predictors trained to recover the concept of interest (e.g. linear gender classifiers). Concretely, INLP initializes $P_{0}=I$, and on the $i^{\text{th}}$ iteration, it performs the following two steps:

Calculate the projection matrix that neutralizes the direction ${\boldsymbol{\theta}}_{i}$: $P_{i+1}\leftarrow P_{i}\left(I-\frac{{\boldsymbol{\theta}}_{i}{\boldsymbol{\theta}}_{i}^{\top}}{{\boldsymbol{\theta}}_{i}^{\top}{\boldsymbol{\theta}}_{i}}\right)$.

After $k$ iterations, it returns the projection matrix $P_{k}$ (of rank $D-k$) and the basis vectors $B$ of the bias subspace $\texttt{span}({\boldsymbol{\theta}}_{1},\dots,{\boldsymbol{\theta}}_{k})$. Neutralizing the concept subspace is realized by $X\leftarrow XP$, which decreases the rank of $X$ by $k$. In other words, instead of solving the minimax game in 4, INLP solves the inner minimization problem, and iteratively uses the solution to update the projection matrix $P$. See Ravfogel et al. (2020) for more details.

1 Linear Regression

The optimal solution we derived for the regression Proposition 3.1 case is generally different than the INLP solution; this implies that INLP does not identify a minimal-rank bias subspace: while it is guaranteed to eventually damage the ability to perform regression, it may remove an unnecessarily large number of dimensions.

INLP does not identify the minimal set of directions needed to be neutralized in order to maximize the MSE loss.

The first iteration of INLP will first identify the best regressor, given by ${({X}^{\top}X)}^{-1}X^{\top}\boldsymbol{y}$. This direction is generally different than the optimal direction $X^{\top}\boldsymbol{y}$ given in Proposition 3.1. ∎

2 Rayleigh quotient losses

In contrast to the regression case, we prove that for Rayleigh quotient losses, the INLP algorithm does converge to an optimal solution to the minimax problem.

INLP optimally identifies the set of directions that maximizes Rayleigh quotient losses.

The two steps 11 and 12 of the optimal solution are identical to the two INLP steps 1 and 2. Rayleigh maximization problems are solved via SVD, which can be performed iteratively, similarly to INLP (Wold, 1966). ∎

3 Classification

In § 5, we empirically demonstrate that INLP is also not optimal for classification: in all experiments we were able to identify a single-dimensional subspace whose removal completely neutralized the concept, while INLP requires more than one direction.

Experiments

In this section, we apply R-LACE on classification-based binary gender removal problems in the context of bias mitigation. We consider two bias mitigation tasks: mitigating gender associations in static word representations (§5.1) and increasing fairness in deep, contextualized classification (§5.2). Additionally, we qualitatively demonstrate the impact of the method on the input space by linearly removing different concepts from images (§5.3).

We replicate the experiment performed by Gonen and Goldberg (2019) and Ravfogel et al. (2020) on bias mitigation in static embeddings. Our bias mitigation target is the uncased version of the GloVe word vectors (Pennington et al., 2014), and we use the training and test data of Ravfogel et al. (2020), where each word vector is annotated with the bias of the corresponding words (male-biased or female-biased). We run Alg. 1 to neutralize this gender information. See § B.5 for more details on our experimental setting. We perform 5 runs of R-LACE and INLP with random initializations and report mean and standard deviations. In § B.10 we demonstrate that our method identifies a matrix which is close to a proper projection matrix.

Initially, a linear SVM classifier can recover the gender label of a word with perfect accuracy. This accuracy drastically drops after Alg. 1: for all the different values of $k$ (the dimensionality of the neutralized subspace) we examined, post-projection accuracy drops to almost $50\%$ (a random accuracy, Fig. 2). This suggests that for the GloVe bias mitigation task, there exists a 1-dimensional subspace whose removal neutralizes all linearly-present concept information. INLP, in contrast, does not reach majority-accuracy even after the removal of a $20$-dimensional subspace. Thus, INLP decreases the rank of the input matrix (Fig. 2) more than Alg. 1, and removes more features. We also examined the PCA-based approach of Bolukbasi et al. (2016), where the subspace neutralized is defined by the first $k$ principle components of the subspace spanned by the difference vectors between gendered words.We used the following pairs, taken from Bolukbasi et al. (2016): (woman, man), (girl, boy), (she, he), (mother, father), (daughter, son), (gal, guy), (female, male), (her, his), (herself, himself), (mary, john). However, for all $k\in\{1,\dots,10\}$ the method did not significantly influence gender prediction accuracy post-projection.

In Ravfogel et al. (2020) it was shown that high-dimensional representation space tends to be (approximately) linearly separable by multiple orthogonal linear classifiers. This led Ravfogel et al. (2020) to the hypothesis that multiple directions are needed in order to fully capture the gender concept. Our results, in contrast, show that there is a $1$-dimensional subspace whose neutralization exhaustively removes the gender concept.

Importantly, as expected with a linear information removal method, non-linear classifiers are still able to recover gender: both RBF-SVM and a ReLU MLP with 1 hidden layer of size 128 predict gender with above 90% accuracy. We repeat the recommendation of Ravfogel et al. (2020): when using linear-removal methods, one should be careful to only feed the result to linear classifiers (such as the last layer of a neural network).

How does R-LACE influence the geometry of representation space? We perform PCA of the GloVe representations, and color the points by gender, both on the original representations, and after 1-rank gender-removal projection. As can be seen in Fig. 1, the original representation space is clustered by gender, and this clustering significantly decreases post-projection. See § B.7 for a quantitative analysis of this effect.

Caliskan et al. (2017) introduced the Word Embedding Association Test (WEAT), a measure for the association of similarity between male and female related words and stereotypically gender-biased professions. The test examines, for example, whether a group of words denoting STEM professions is more similar, in average, to male names than to female ones. We measure the association between Female and Male names and (1) career and family-related terms; (2) Art and Mathematics words; (3) Artistic and Scientific Fields. We report the test statistic, WEAT’s $d$ (see Caliskan et al. (2017) for more details), and the $p$-values after rank-$1$ projections in Tab. 1. R-LACE is most effective in decreasing biased associations to nearly nonsignificant $p$-values.

Does R-LACE damage the semantic content of the embeddings? We run SimLex-999 (Hill et al., 2015), a test that measures the quality of the embedding space by comparing word similarity in that space to a human notion of similarity. The test is composed of pairs of words, and we calculate the Pearson correlation between the cosine similarity before and after projection, and the similarity score that humans gave to each pair. Similarly to Ravfogel et al. (2020), we find no significant influence on correlation to human judgement, from 0.399 for the original vectors, to 0.392 after rank-1 projection and 0.395 after 1 iteration of INLP. See § B.8 for the neighbors of randomly-chosen words before and after R-LACE.

2 Deep Classification

We proceed to evaluate the impact of R-LACE on deep classifiers with a focus on the fairness of the resulting classifiers. De-Arteaga et al. (2019) released a large dataset of short biographies collected from the web annotated for both binary gender and profession. We embed each biography with the [CLS] representation in the last layer of BERT, run Alg. 1 to remove gender information from the [CLS] , and then evaluate the performance of the model, after the intervention, on the main task of profession prediction.

We consider several deep profession classifiers:

A multiclass logistic regression profession classifier over the frozen representations of pre-trained BERT (BERT-frozen);

A pretrained BERT model finetuned to the profession classification task (BERT-finetuned);

A pretrained BERT model finetuned to the profession classification task, trained adversarially for gender removal with the gradient-reversal layer method of Ganin and Lempitsky (2015) (BERT-adv). We consider (1) a linear adversray (2) an MLP adversary with 1-hidden-layer of size 300 and ReLU activations.

We run Alg. 1 on the representations of BERT-frozen and BERT-finetuned , while BERT-adv is the commonly used way to remove concepts, and is used as a baseline. We report the results of 5 runs with random initializations. Before running Alg. 1, we reduce the dimensionality of the representations to 300 using PCA. We finetune the linear profession-classification head following the projection. See § B.6 for more details on our experimental setting.

3 Erasing Concepts in Image Data

Our empirical focus is concept removal in textual data. Visual data, however, has the advantage of being able to clearly inspect the influence of R-LACE on the input. To qualitatively assess this effect, we use face images from the CelebsA dataset (Yang et al., 2015), which is composed of faces annotated with different concepts, such as “sunglasses” and “smile”. We downscaled all data to 50 over 50 grey-scale images, flatten them to 2,500-dimensional vectors, and run our method on the raw pixels (aiming to prevent a linear classifier to classify, for instance, whether a person has sunglasses based on the pixels of their image).Modern vision architecture relies on deep models. We focus on linear classification in order to see the direct effect on the input. Extending it for deep architectures is left to future work. We experimented with the following concepts: “glasses”, “smile”, “mustache”, “beard”, “bald” and “hat”.

See Fig. 4 and § B.9 for randomly-sampled outputs. In all cases, a rank-$1$ linear projection is enough to remove the ability to classify attributes (classification accuracy of less than 1% above majority accuracy). The intervention changed the images by focusing on the features one would expect to be associated with the concepts of interest; for example, adding “pseudo sun-glasses” to all images (for “glasses”) and blurring the facial features around the mouth (for “smile”).In contrast to regular style transfer, we prevent classification of the concept. At times (e.g. the “glasses” case), we converged on a solution which always enforces the concept on the image; but this need not generally be the case. Since the intervention is constrained to be a projection, it is limited in expressivity, and it often zeros-out pixels to simulate a concept of interest, such as sunglasses. These results suggest that very simple style transfer of images does not always necessitate deep architectures, such as Style GAN (Karras et al., 2019).

Related Work

Concept removal is predominantly based on adversarial approaches (Goodfellow et al., 2014), which were extensively applied to bias mitigation problems (Ganin and Lempitsky, 2015; Edwards and Storkey, 2016; Chen et al., 2018; Xie et al., 2017; Zhang et al., 2018; Wang et al., 2021). However, those methods are notoriously unstable, and were shown by Elazar and Goldberg (2018) to be non-exhaustive: residual bias often still remains after apparent convergence. Linear information removal method was pioneered by Bolukbasi et al. (2016), who used PCA to identify “gender subspace” spanned by a few presupposed “gender directions”. Following the criticism of Gonen and Goldberg (2019), several works have proposed alternative linear formulations (He et al., 2020; Dev and Phillips, 2019; Ravfogel et al., 2020; Dev et al., 2021; Kaneko and Bollegala, 2021).

Concurrent to this work, spectral removal of information (a special case of the Rayleigh-quotient loss, § 2) was studied in Shao et al. (2022), who projected out the directions that explain most of the covariance between the representations and the protected attribute, and also proposed a kernalization of the Rayleigh-quotient objective. Closest to our work are Sadeghi et al. (2019) and Sadeghi and Boddeti (2021), who studied a different linear adversarial formulation and quantified the inherent trade-offs between information removal and main-task performance. Their analysis is focused on the special case of linear regression, and they considered a general linear adversary (which is not constrained to an orthogonal projection – making it more expressive, but less interpetable). Finally, Haghighatkhah et al. (2021) provide a thorough theoretical analysis of the problem of preventing classification through an orthogonal projection, and provide a constructive proof for optimality against SVM adversaries.

Beyond bias mitigation, concept subspaces have been used as an interpretability tool (Kim et al., 2018), for causal analysis of NNs (Elazar et al., 2021; Ravfogel et al., 2021), and for studying the geometry of their representations (Celikkanat et al., 2020; Gonen et al., 2020; Hernandez and Andreas, 2021). Our linear concept removal objective is different from subspace clustering (Parsons et al., 2004), as we focus on hindering the ability to linearly classify the concept, and do not assume that the data lives in a linear or any low-dimensional subspace.

Conclusion

We have formulated the task of erasing concepts from the representation space as a constrained version of a general minimax game. In the constrained game, the adversary is limited to a fixed-rank orthogonal projection. This constrained formulation allows us to derive closed-form solutions to this problems for certain objectives, and propose a convex relaxation which works well in practice for others. We empirically show that the relaxed optimization recovers a single dimensional subspace whose removal is enough to mitigate linearly-present gender concepts.

The method proposed in this work protects against linear adversaries. Effectively removing non-linear information while maintaing the advantages of the constrained, linear approach remains an open challenge.

Acknowledgements

We thank Marius Mosbach, Yanai Elazar, Josef Valvoda and Tiago Pimentel for fruitful discussions. This project received funding from the Europoean Research Council (ERC) under the Europoean Union’s Horizon 2020 research and innovation programme, grant agreement No. 802774 (iEXTRACT). Ryan Cotterell acknowledges Google for support from the Research Scholar Program.

References

Appendix A Pseudocode

Appendix B Appendices

The empirical experiments in this work involve the removal of binary gender information from a pre-trained representation. Beyond the fact that gender a non-binary concept, this task may have real-world applications, in particular such that relate to fairness. We would thus like remind the readers to take the results with a grain of salt and be extra careful when attempting to deploy methods such as the one discussed here. Regardless of any proofs, care should be taken to measure the effectiveness of the approach in the context in which it is to be deployed, considering, among other things, the exact data to be used, the exact fairness metrics under consideration, the overall application, and so on. We urge practitioners not to regard this method as a “solution” to the problem of bias in neural models, but rather as a preliminary research effort towards mitigating certain aspects of the problem. Unavoidably, we make use a limited set of datasets in our experiments, and they do not reflect all the subtle and implicit ways in which gender bias is manifested. As such, it is likely that different forms of bias still exist in the representations following the application of our method. We hope that followup works would illuminate some of these shortcomings.

Furthermore, our method targets a very specific technical definition of bias, quantified by the ability to linearly predict the sensitive information. The method is not expected to be robust to nonlinear adversaries, or generally other ways to quantify bias.

B.2 Rayleigh-quotient

In this appendix, we provide a derivation of the equilibrium point of the linear adversarial game for objectives that can be cast as Rayleigh quotient maximization (§ 3.2). We prove that these objective, the optimal projection of rank $k$ neutralizes the subsapce spanned by the $k$-best ${\boldsymbol{\theta}}_{1},\dots,{\boldsymbol{\theta}}_{k}$ — i.e., the first $k$ directions that maximize the Rayleigh quotient.

We first argue for an upper bound on the objective. For any orthogonal projection matrix $P_{0}$ of rank $k$, we have

which is true when ${\boldsymbol{\theta}}^{\star}=\boldsymbol{v}_{k+1}$ and $P^{\star}=I-\sum_{d=1}^{D-k}\boldsymbol{v}_{d}\boldsymbol{v}_{d}^{\top}$.

This is true as $\textsf{null}\left(P\right)=\texttt{span}\left(\{\boldsymbol{v}_{1},\ldots,\boldsymbol{v}_{k}\}\right)$ which zeros out the elements of the collection that achieve the highest values of the objective in this collection, i.e. $\{\boldsymbol{v}_{1},\ldots,\boldsymbol{v}_{k}\}$. Plugging in $P^{\star}$, we get ${\boldsymbol{\theta}}^{\star}=\boldsymbol{v}_{k+1}$ and the value of the objective is $\lambda_{k+1}$.

Given that we have upper and lower bounded the problem with $\lambda_{k+1}$, we conclude the solution is as stated in the theorem. ∎

B.3 Linear Regression

In this appendix, we provide a derivation of the equilibrium point of the linear adversarial game in the linear regression case (§ 3.1). We show that the optimal projection is of rank 1, and that it neutralizes the covariance direction $X\boldsymbol{y}$. See 3.1

Let $P=I-\frac{\boldsymbol{v}\boldsymbol{v}^{\top}}{\boldsymbol{v}^{\top}\boldsymbol{v}}$ be an arbitrary orthogonal projection matrix, where span($\boldsymbol{v})$ is the rank-1 concept subspace that is neutralized. For every choice of $\boldsymbol{v}$, the optimal ${\boldsymbol{\theta}}$ is ${\boldsymbol{\theta}}={({(XP)}^{\top}XP)}^{-1}X^{\top}y={(PX^{\top}XP)}^{-1}PX^{\top}\boldsymbol{y}:=CX^{\top}\boldsymbol{y}$, where $C$ is the inverse (or pseudoinverse) matrix. Consider the choice $\boldsymbol{v}:=X^{\top}\boldsymbol{y}$. For this choice, the objective is evaluated to $\frac{1}{2}{||\boldsymbol{y}-XP{(PX^{\top}XPw)}^{-1}PX^{\top}\boldsymbol{y}||}^{2}$. Since, by definition, $P$ projects to the nullspace of $X^{\top}\boldsymbol{y}$, we have $PX^{\top}\boldsymbol{y}=\vec{0}$ and the objective is then evaluated to $\frac{1}{2}{||\boldsymbol{y}||}^{2}$. Thus, the objective is the variance of $\boldsymbol{y}$, regardless or the value of ${\boldsymbol{\theta}}$. Note also that the adversary cannot improve over this choice for $P$, since regardless of the choice of $P$, the predictor can always choose ${\boldsymbol{\theta}}=\vec{0}$ and get an objective value of $Var(\boldsymbol{y})$ – so this is an upper bound for the objective.

B.4 Optimizing the Relaxed Objective

In this appendix, we describe the optimization of the relaxed objective § 3.4.

To optimize the relaxed objective 18, we perform alternate minimization and maximization over ${\boldsymbol{\theta}}$ and $P$, respectively. ${\boldsymbol{\theta}}$ is updated with a regular gradient descent:

While $P$ is updated with projected gradient ascent:

where $\alpha_{t}$ is the learning rate, and $\Pi_{\mathcal{F}_{k}}$ is the projection to the Fantope, given in Vu et al. (2013). The following lemma describes how to calculate that projection:

Let $\mathcal{F}_{k}$ be the $k$-dimensional fantope; see 17, and let $P=\sum_{d=1}^{D}\lambda_{d}\boldsymbol{v}_{d}\boldsymbol{v}_{d}^{\top}$ be the eigendecomposition of $P$ where $\lambda_{d}$ is $P$’s $d$th eigenvalue and $\boldsymbol{v}_{d}$ is its corresponding eigenvector. The projection of $P$ onto the fantope is given by $\Pi_{\mathcal{F}_{k}}(P)=\sum_{d=1}^{D}\lambda_{d}^{+}(\gamma)\cdot\boldsymbol{v}_{d}\boldsymbol{v}_{d}^{\top}$, where $\lambda_{d}^{+}(\gamma)=\min\left(\max(\lambda_{d}-\gamma,0),1\right)$ and $\gamma$ satisfies the equation $\sum_{d=1}^{D}\lambda_{d}^{+}(\gamma)=k$.

The lemma specifies that finding the projection entails performing an eigendecomposition of $P$ and finding $\gamma$ that satisfies a set of monotonous, piece-wise linear equations. Since we can easily find $\gamma$ where $\sum_{d=1}^{D}\lambda_{d}^{+}(\gamma)>k$ and $\gamma$ where $\sum_{d=1}^{D}\lambda_{d}^{+}(\gamma)<k$, we can solve the system of equations using the bisection method.

Upon termination of the optimization process, we perform spectral decomposition of $P$, and return a projection matrix to the space spanned by the first $D-k$ eigenvectors (to ensure a proper orthogonal projection matrix that neutralizes a rank-$k$ subspace). The process is summarized in Alg. 1. The matrix $P$ can then be used to mitigate bias in the dataset $X$ by projecting $X\leftarrow XP$.

Concave–convex adversarial problems have a unique Nash equilibrium under mild conditions (Pang and Razaviyayn, 2016), and there is a rich literature on efficient solution to these problems. However, Even for the concave–convex case, alternate optimization–as we employ–is not guaranteed to find that equilibrium, and is prone to problems such as rotational behavior (Nouiehed et al., 2019). Indeed, in our experiments, we witness such behavior: the objective does not converge smoothly. However, in all cases, when we run the algorithm for enough iterations and continuously evaluate the projection $P$ by fixing it, training ${\boldsymbol{\theta}}$ to convergence and evaluating it on the development set, we converge to an optimal $P$ (in the sense of ${\boldsymbol{\theta}}$ achieving majority-accuracy) at certain point. We then terminate the optimization and take that optimal $P$. Because of these positive results we opted for using vanilla alternate optimization, although more sophisticated algorithms, that do guarantee convergence to the equilibrium point, have also been developed for convex–concave games (Wang and Li (2020); Yoon and Ryu (2021), inter alia).

B.5 Experimental Setting: Static Word Vectors

In this appendix, we describe the experimental setting in the static word vectors experiments § 5.1.

We conduct experiments on 300-dimensional uncased GloVe vectors. Following (Ravfogel et al., 2020), to approximate the gender labels for the vocabulary, we project all vectors on the $\overrightarrow{he}-\overrightarrow{she}$ direction, and take the $7,500$ most male-biased and female-biased words. Note that unlike (Bolukbasi et al., 2016), we use the $\overrightarrow{he}-\overrightarrow{she}$ direction only to induce approximate gender labels, but then proceed to measure the bias in various ways, that go beyond neutralizing just the $\overrightarrow{he}-\overrightarrow{she}$ direction.

We use the same train–dev–test split of Ravfogel et al. (2020), but discard the gender-neutral words (i.e., we cast the problem as a binary classification). We end up with a training set, evaluation set and test set of sizes 7,350, 3,150 and 4,500, respectively.

We run Alg. 1 for 50,000 iterations with the cross entropy loss, alternating between an update to the adversary and to the classifier after each iteration ($T=50,000,M=1$ in Alg. 1).

The inner optimization problem entailed in the Fantope projection operation is solved with the bisection method. We train with a simple SGD, with a learning rate of $0.005$, chosen by experimenting with the development set. We use a batch size of 128. After each 1000 batches, we freeze the adversary, train the classifier to convergence, and record its loss. Finally, we return the adversary which yielded the highest classification loss. In test time, we evaluate the ability to predict gender using logistic regression classifiers trained in Sklearn. For the dimensionality of the neutralized subspace, we experiment with the values $k=1\dots 20$ for INLP and R-LACE.̇ We perform 5 runs and report mean $\pm$ standard deviation.

B.6 Experimental Setting: Deep Classifiers

In this appendix, we describe the experimental setting in the deep classification experiments § 3.3.

We use the same train–dev–test split of the biographies dataset used by Ravfogel et al. (2020), resulting in training, evaluation and test sets of sizes 255,710, 39,369, and 98,344, respectively. We reduce the dimensionality of the representations to 300 using PCA, and for efficiency reasons, we run Alg. 1 on the first 100,000 training examples only (but test on all the test data).

We run Alg. 1 with a simple SGD optimization, with a learning rate of $0.005$ and a weight decay of $1e^{-4}$, chosen by experimenting with the development set. We use a batch size of 256, and again choose the adversary which yielded highest classification loss. For the dimensionality of the neutralized subspace, we run R-LACE and INLP with $k=1\dots 100$. We perform 5 runs of the entire experimental pipeline (classifier training, INLP and R-LACE ) and report mean $\pm$ standard deviation.

We experiment with several deep profession classifiers, as detailed in § 3.3. For BERT-frozen, we use the HuggingFace implementation (Wolf et al., 2020). For BERT-finetuned we finetune the pre-trained BERT on the profession classification task, using a SGD optimizer with a learning rate of $0.0005$, weight decay of $1e^{-6}$ and momentum of 0.9. We train for 30,000 batches of size 10 and choose the model which achieved lowest loss on the development set. For BERT-adv, we perform the same training procedure, but add an additional classification head which is trained to predict gender, and whose gradient is reversed (Ganin and Lempitsky, 2015). This procedure should create an encoder which generates hidden representations which are predictive of the main task, but are not predictive of gender. The adversary always converged to a low gender classification accuracy (below $55\%$), which is commonly interpreted as a success of the removal process.

We formally describe the fairness measures used in § 5.2.

The TPR-GAP is tightly related to the notion of fairness by equal opportunity (Hardt et al., 2016): a fair binary classifier is expected to show similar success in predicting the task label $\boldsymbol{y}$ for the two populations, when conditioned on the true class. Formally, let $Z$ is a random variable denoting binary protected attribute, $z$ and $z^{\prime}$ denote its two values, and let $Y$ denote a random variable describing the main-task label, and similarly let $\widehat{Y}$ be a random variable denoting the model’s prediction on the main task (e.g. profession). TPR between a main-task label $y$ and a protected group $z$, and the gap in the TPR, are defined as follows (De-Arteaga et al., 2019):

We also consider the root-mean square of $GAP_{z,y}^{TPR}$ over all main-class labels, to get a single per-gender bias score:

where $C$ is the set of all labels (in our case, professions).

B.7 V-Measure

To quantify the effect of our intervention on the GloVe representation sapce in § 5.1, we perform $K$-means clustering with different values of $K$, and use $V-$measure (Rosenberg and Hirschberg, 2007) to quantify the association between cluster identity and the gender labels, after a projection that removes rank-$1$ subspace. The results are presented in Fig. 5. $V$-measure for the original representations is 1.0, indicating a very high alignment between cluster identity and gender label. The score drastically drops after a rank-$1$ relaxed projection, while INLP projection and the PCA-based method of (Bolukbasi et al., 2016) have a smaller effect.

B.8 Influence on Neighbors in Embedding Space

In § 5.1, we showed that the SimLex999 test does not find evidence to damage that our intervention causes to the GloVe embedding space. To qualitatively demonstrate this, we provide in Tab. 3 the closest-neighbors to 15 randomly-sampled words from the vocabulary, before and after our intervention.

B.9 Additional results on the CelebsA dataset

We present here randomly-sampled outputs for the 6 concepts we experimented with: “glasses”, “smile”, “mustache”, “beard”, “bald” and “hat” (Experiment § 5.3).

B.10 Relaxation Quality

To what extent the optimization of the relaxed objective 18 results in a matrix $P$ that is a valid a rank-$k$ orthogonal projection matrix? recall that orthogonal projection matrix have binary eigenvalues: all eigenvalues are either zeros or ones, and their sum is the rank of the matrix. In Fig. 12, we present the eigenvalues spectrum of $P$ when we run Alg. 1 with $k=6$ on the static word-embeddings dataset (§ 5.1). We find that the top $6$ eigenvalues are indeed close to 1, and the rest are close to 0—suggesting the approximation is tight: the resulting matrix is close to a valid rank-$k$ orthogonal projection matrix.