Year: 2022

Abstract:
We propose to identify directions invariant to a given classifier so that these directions can be controlled in tasks such as style transfer. While orthogonal decomposition is directly identifiable when the given classifier is linear, we formally define a notion of orthogonality in the non-linear case. We also provide a surprisingly simple method for constructing the orthogonal classifier (a classifier utilizing directions other than those of the given classifier). Empirically, we present three use cases where controlling orthogonal variation is important: style transfer, domain adaptation, and fairness. The orthogonal classifier enables desired style transfer when domains vary in multiple aspects, improves domain adaptation with label shifts and mitigates the unfairness as a predictor. The code is available at https://github.com/Newbeeer/orthogonal_classifier.

heading: 1 INTRODUCTION
text: Many machine learning applications require explicit control of directions that are orthogonal to a predefined one. For example, to ensure fairness, we can learn a classifier that is orthogonal to sensitive attributes such as gender or race (Zemel et al., 2013; Madras et al., 2018). Similar, if we transfer images from one style to another, content other than style should remain untouched. Therefore images before and after transfer should align in directions orthogonal to style. Common to these problems is the task of finding an orthogonal classifier. Given any principal classifier operating on the basis of principal variables, our goal is to find a classifier, termed orthogonal classifier, that predicts the label on the basis of orthogonal variables, defined formally later.
The notion of orthogonality is clear in the linear case. Consider a joint distribution PXY over X ∈ Rd and binary label Y . Suppose the label distribution is Bernoulli, i.e., PY = B(Y ; 0.5) and class-conditional distributions are Gaussian, PX ∣Y =y = N (X;µy, σ2yI), where the means and variances depend on the label. If the principal classifier is linear, w1 = Pr(Y = 1∣θ⊺1x), any classifier w2, in the setW2 = {Pr(Y = 1∣θ⊺2x) ∣ θ⊺1θ2 = 0}, is considered orthogonal to w1. Thus the two classifiers w1,w2, with orthogonal decision boundaries (Fig. 1) focus on distinct but complementary attributes for predicting the same label.
Finding the orthogonal classifier is no longer straightforward in the non-linear case. To rigorously define what we mean by the orthogonal classifier, we first introduce the notion of mutually orthogonal random variables that correspond to (conditinally) independent latent variables mapped to observations through a diffeomorphism (or bijection if discrete). Each r.v. is predictive of the label but represents complementary information. Indeed, we show that the orthogonal random variable maximizes the conditional mutual information with the label given the principal counterpart, subject to an independence constraint that ensures complementarity.
Our search for the orthogonal classifier can be framed as follows: given a principal classifier w1 using some unknown principal r.v. for prediction, how do we find its orthogonal classifier w2 relying solely on orthogonal random variables? The solution to this problem, which we call classifier orthogonalization, turns out to be surprisingly simple. In addition to the principal classifier, we assume access to a full classifier wx that predicts the same label based on all the available information, implicitly relying on both principal and orthogonal latent variables. The full classifier can be trained normally, absent of constraints1. We can then effectively “subtract” the contribution of w1 from the full classifier to obtain the orthogonal classifier w2 which we denote as w2 = wx ∖w1. The advantage of this construction is that
1The full classifier may fail to depend on all the features, e.g., due to simplicity bias (Shah et al., 2020).
we do not need to explicitly identify the underlying orthogonal variables. It suffices to operate only on the level of classifier predictions.
We provide several use cases for the orthogonal classifier, either as a predictor or as a discriminator. As a predictor, the orthogonal classifier predictions are invariant to the principal sensitive r.v., thus ensuring fairness. As a discriminator, the orthogonal classifier enforces a partial alignment of distributions, allowing changes in the principal direction. We demonstrate the value of such discriminators in 1) controlled style transfer where the source and target domains differ in multiple aspects, but we only wish to align domain A’s style to domain B, leaving other aspects intact; 2) domain adaptation with label shift where we align feature distributions between the source and target domains, allowing shifts in label proportions. Our results show that the simple method is on par with the state-of-the-art methods in each task.

heading: 2 NOTATIONS AND DEFINITION
text: Symbols. We use the uppercase to denote random variable (e.g., data X , label Y ), the lowercase to denote the corresponding samples and the calligraphic letter to denote the sample spaces of r.v., e.g., data sample space X . We focus on the setting where label space Y is discrete, i.e., Y = {1,⋯,C}, and denote the C − 1 dimensional probability simplex as ∆C . A classifier w ∶ X →∆C is a mapping from sample space to the simplex. Its y-th dimension w(x)y denotes the predicted probability of label y for sample x. Distributions. For random variables A,B, we use the notation pA, pA∣B , pAB to denote the marginal/conditional/joint distribution, i.e., pA(a) = p(A = a), pA∣B(a∣b) = p(A = a∣B = b),pAB(a, b) = p(A = a,B = b). Sometimes, for simplicity, we may ignore the subscript if there is no ambiguity, e.g., p(a∣b) is an abbreviation for pA∣B(a∣b). We begin by defining the notion of an orthogonal random variable. We consider continuous X,Z1, Z2 and assume their supports are manifolds diffeomorphic to the Euclidean space. The probability density functions (PDF) are in C1. Given a joint distribution pXY , we define the orthogonal random variable as follows:
Definition 1 (Orthogonal random variables). We say Z1 and Z2 are orthogonal random variables w.r.t pXY if they satisfy the following properties:
(i) There exists a diffeomorphism f ∶ Z1 ×Z2 → X such that f(Z1, Z2) =X .
(ii) Z1 and Z2 are statistically independent given Y , i.e., Z1 ⊥ Z2∣Y .
The orthogonality relation is symmetric by definition. Note that the orthogonal pair perfectly reconstructs the observations via the diffeomorphism f ; as random variables they are also sampled independently from class conditional distributions p(Z1∣Y ) and p(Z2∣Y ). For example, we can regard foreground objects and background scenes in natural images as being mutually orthogonal random variables.
Remark. The definition of orthogonality can be similarly developed for discrete variables and discretecontinuous mixtures. For discrete variables, for example, we can replace the requirement of diffeomorphism with bijection.
Since the diffeomorphism f is invertible, we can use z1 ∶ X → Z1 and z2 ∶ X → Z2 to denote the two parts of the inverse mapping so that Z1 = z1(X) and Z2 = z2(X). Note that, for a given joint distribution pXY , the decomposition into orthogonal random variables is not unique. There are multiple pairs of random variables that represent valid mutually orthogonal latents of the data. We can further justify our definition of orthogonality from an information theoretic perspective by showing that the choice of z2 attains the maximum of the following constrained optimization problem. Proposition 1. Suppose the orthogonal r.v. of z1(X) w.r.t pXY exists and is denoted as z2(X). Then z(X) = z2(X) is a maximizer of I(z(X);Y ∣z1(X)) subject to I(z(X); z1(X)∣Y ) = 0.
We defer the proof to Appendix B.1. Proposition 1 shows that the orthogonal random variable maximizes the additional information about the label we can obtain from X while remaining conditionally independent of the principal random variable. This ensures complementary in predicting the label.

heading: 3 CONSTRUCTING THE ORTHOGONAL CLASSIFIER
text: Let Z1 = z1(X) and Z2 = z2(X) be mutually orthogonal random variables w.r.t pXY . We call Z1 the principal variable and Z2 the orthogonal variable. In this section, we describe how we can construct the Bayes optimal classifier operating on features Z2 from the Bayes optimal classifier relying on Z1. We formally refer to the classifiers of interests as: (1) principal classifier w1(x)y = p(Y = y∣Z1 = z1(x)); (2) orthogonal classifier w2(x)y = p(Y = y∣Z2 = z2(x)); (3) full classifier wx(x)y = p(Y = y∣X = x).

heading: 3.1 CLASSIFIER ORTHOGONALIZATION
text: Our key idea relies on the bijection between the density ratio and the Bayes optimal classifier (Sugiyama et al., 2012). Specifically, the ratio of densities pX ∣Y (x∣i) and pX ∣Y (x∣j), assigned to an arbitrary point x, can be represented by the Bayes optimal classifier w(x)i = Pr(Y = i∣x) as
pX∣Y (x∣i) pX∣Y (x∣j) = pY (j)w(x)i pY (i)w(x)j .
Similar, the principal classifier w1 gives us associated density ratios of class-conditional distributions over Z1. For any i, j ∈ Y , we have
pZ1 ∣Y (z1(x)∣i) pZ1 ∣Y (z1(x)∣j) = pY (j)w1(x)i pY (i)w1(x)j . These can be combined to obtain
density ratios of class-conditional distribution pZ2∣Y and subsequently calculate the orthogonal classifier w2. We additionally rely on the fact that the diffeomorphism f permits us to change variables between x and z1, z2: pX ∣Y (x∣i) = pZ1∣Y (z1∣i) ∗ pZ2∣Y (z2∣i) ∗ volJf(z1, z2), where volJf is volume of the Jacobian (Berger et al., 1987) of the diffeomorphism mapping. Taken together,
pZ2∣Y (z2∣i) pZ2∣Y (z2∣j) = pZ1∣Y (z1∣i) ∗ pZ2∣Y (z2∣i) ∗ volJf(z1, z2) pZ1∣Y (z1∣j) ∗ pZ2∣Y (z2∣j) ∗ volJf(z1, z2) / pZ1∣Y (z1∣i) pZ1∣Y (z1∣j) = wx(x)i wx(x)j / w1(x)i w1(x)j (1)
Note that since the diffeomorphism f is shared with all classes, the Jacobian is the same for all labelconditioned distributions on Z1, Z2. Hence the Jacobian volume terms cancel each other in the above equation. We can then finally work backwards from the density ratios of pZ2∣Y to the orthogonal classifier:
Pr(Y = i∣Z2 = z2(x)) = Pr(Y = i) wx(x)i w1(x)i /∑ j (Pr(Y = j)wx(x)j w1(x)j ) (2)
We call this procedure classifier orthogonalization since it adjusts the full classifier wx to be orthogonal to the principal classifier w1. The validity of this procedure requires overlapping supports of the classconditional distributions, which ensures the classifier outputs wx(x)i,w1(x)i to remain non-zero for all x ∈ X , i ∈ Y . Empirically, we usually have access to a dataset D = {(xt, yt)}nt=1 with n iid samples from the joint distribution pXY . To obtain the orthogonal classifier, we need to first train the full classifier ŵx based on the dataset D. We can then follow the classifier orthogonalization to get an empirical orthogonal classifier, denoted as w2 = ŵx ∖w1. We use symbol ∖ to emphasize that the orthogonal classifier uses complementary information relative to z1. Algorithm 1 summarizes the construction of the orthogonal classifier.
Generalization bound. Since wx is trained on a finite dataset, we consider the generalization bound of the constructed orthogonal classifier. We denote the population risk as R(w) = −EpXY (x,y) [logw(x)y] and the empirical risk as R̂(w) = − 1∣D∣ ∑(xi,yi)∈D logw(xi)yi . For a function familyW whose elements map X to the simplex ∆C , we define ŵx = infwx∈W R̂(wx),w∗x = infwx∈W R(wx). We further denote the Rademacher complexity of function familyW with sample size ∣D∣ as R∣D∣(W).
Algorithm 1 Classifier Orthogonalization Input: principal classifier w1, dataset D. Train an empirical full classifier ŵx on D by empirical risk minimization. Construct an orthogonal classifier ŵx ∖w1 via classifier orthogonalization (Eq. (2)). return the empirical orthogonal classifier ŵ2 = ŵx ∖w1
Theorem 1. Assume py is uniform distribution, ∀wx ∈W takes values in (m,1 −m)C with m ∈ (0, 12), and 1/pX ∣Y (x∣y) ∈ (0, γ) ⊂ (0,+∞) holds for ∀x ∈ X , y ∈ Y . Then for any δ ∈ (0,1) with probability at least 1 − δ, we have:
∣R(ŵx ∖w1) −R(w∗x ∖w1)∣ ≤ (1 + γ) ⎛ ⎜ ⎝ 2R∣D∣(W) + 2 log 1 m
¿ ÁÁÀ2 log 1 δ
∣D∣ ⎞ ⎟ ⎠
Theorem 1 shows that the population risk of the empirical orthogonal classifier in Algorithm 1 would be close to the optimal risk if the maximum value of the reciprocal of class-conditioned distributions 1/pX ∣Y (x∣y) and the Rademacher term are small. Typically, the Rademacher complexity term satisfies R∣D∣(W) = O(∣D∣− 1 2 ) (Bartlett & Mendelson, 2001; Gao & Zhou, 2016). We note that the empirical full classifier may fail in specific ways that are harmful for our purposes. For example, the classifier may not rely on all the key features due to simplicity bias as demonstrated by (Shah et al., 2020). There are several ways that this effect can be mitigated, including Ross et al. (2020); Teney et al. (2021).

heading: 3.2 ALTERNATIVE METHOD: IMPORTANCE SAMPLING
text: An alternative way to get the orthogonal classifier is via importance sampling. For each sample point (x, y), we construct its importance φ(x, y) ∶= pZ1(z1(x))
pZ1 ∣Y (z1(x)∣y) . Via Bayes’ rule, the importance φ(x, y) can
be calculated from the principal classifier by φ(x, y) = pY (y) w1(x)y . We define the importance sampling (IS) objective as LIS(w) ∶= Ex,y∼pXY [φ(x, y) logw(x)y]. It can be shown that the orthogonal classifier w2 maximizes the IS objective, i.e., w2 = arg maxLIS. However, the importance sampling method has an Achilles’ heel: variance. A few bad samples with large weights can drastically deviate the estimation, which is problematic for mini-batch learning in practice. We provide an analysis of the variance of the IS objective. It shows the variance increases with the divergences between Z1’s marginal and its label-conditioned marginals, {Df(pZ1 ∣∣pZ1∣Y =y)}Cy=1 even when the learned classifier w is approaching the optimal classifier, i.e., w ≈ w2. Let L̂nIS(w) ∶= 1n ∑ n t=1 φ(xt, yt) logw(xt)yt be the empirical IS objective estimated with n iid samples. Clearly, Var(L̂nIS(w)) = 1nVar(L̂1IS(w)). While Var(L̂1IS(w)) at w = w2 is the following,
Var(L̂1IS(w2)) = EY [(Df(pZ1 ∣∣pZ1∣Y =y) + 1)EZ2∣Y =y log 2 pY ∣Z2(y∣z2)] −L(w2)2
where Df is the Pearson χ2-divergence. The expression indicates that the variance grows linearly with the expected divergence. In contrast, the divergences have little effect when training the empirical full classifier in classifier orthogonalization. We provide further experimental results in section 4.1.2 to demonstrate that classifier orthogonalization has better stability than the IS objective with increasing divergences and learning rates.

heading: 4 ORTHOGONAL CLASSIFIER FOR CONTROLLED STYLE TRANSFER
text: In style transfer, we have two domains A,B with distributions PXY ,QXY . We use binary label Y to indicate the domain of data X (0 for domain A, 1 for domain B). Assume Z1 and Z2 are mutually orthogonal variables w.r.t both PXY and QXY . The goal is to conduct controlled style transfer between the two domains. By controlled style transfer, we mean transferring domain A’s data to domain B only via making changes on partial latent (Z1) while not touching the other latent (Z2). Mathematically, we aim to transfer the latent distribution from PZ1PZ2 to QZ1PZ2 . This task cannot be achieved by traditional style transfer algorithms such as CycleGAN (Zhu et al., 2017), since they directly transfer data distributions from PX to QX , or equivalently from the perspective of latent distributions, from PZ1PZ2 to QZ1QZ2 . Below we show that the orthogonal classifier wx ∖w1 enables such controlled style transfer. Our strategy is to plug the orthogonal classifier into the objective of CycleGAN. The original CycleGAN objective defines a min-max game between two generators/discriminator pairs GAB/DAB and
GBA/DBA. GAB transforms the images from domainA to domainB. We use P̃ to denote the generative distribution, i.e., GAB(X) ∼ P̃ for X ∼ P . Similarly, Q̃ denotes the generative distribution of generator GBA. The minimax game of CycleGAN is given by
min GAB ,GBA max DAB ,DBA
LABGAN(GAB ,DAB) +LBAGAN(GBA,DBA) +Lcyc(GAB ,GBA) (3)
where GAN losses LABGAN,LBAGAN minimize the divergence between the generative distributions and the targets, and the cycle consistency loss Lcyc is used to regularize the generators (Zhu et al., 2017). Concretely, the GAN loss LABGAN is defined as follows,
LABGAN(GAB ,DAB) ∶= Ex∼Q[logDAB(x)] +Ex∼P̃ [log(1 −DAB(x))] Now we tilt the GAN losses in CycleGAN objective to guide the generators to perform controlled transfer. Specially, we replace LABGAN in Eq. (3) with the orthogonal GAN loss LABOGAN when updating the generator GAB :
LABOGAN(GAB ,DAB) ∶= Ex∼P̃ [log(1 − φ(DAB(x), r(x)))]
where φ(DAB(x), r(x)) = DAB(x)r(x)(1−DAB(x))+DAB(x)r(x) and r(x) = wx∖w1(x)0 wx∖w1(x)1 . Consider an extreme case where we allow the model to change all latents, i.e., z1(x) = x. As a result, LOGAN degenerates to the original LGAN since wx ∖ w1 ≡ 12 and φ(DAB(x), r(x)) ≡ DAB(x). The other orthogonal GAN loss LBAOGAN can be similarly derived. For a given generator GAB , the discriminator’s optimum is achieved at D∗AB(x) = Q(x)/(P̃ (x) +Q(x)). Assuming the discriminator is always trained to be optimal, the generator GAB can be viewed as optimizing the following virtual objective: LABOGAN(GAB) ∶= LABOGAN(GAB ,D∗AB) = Ex∼P̃ log P̃ (x) P̃ (x)+Q(x)r(x) . The optimal generator in the new objective satisfies the following property.
Proposition 2. The global minimum of LABOGAN(GAB) is achieved if and only if P̃Z1,Z2(z1, z2) = QZ1(z1)PZ2(z2).
We defer the proof to Appendix B.4. The proposition states that the new objective LABOGAN converts the original global minimum QZ1QZ2 in LABGAN to the desired one QZ1PZ2 . The symmetric statement holds for LBAOGAN(GBA).

heading: 4.1 EXPERIMENTS

heading: 4.1.1 SETUP
text: Datasets. (a) CMNIST: We construct C(olors)MNIST dataset based on MNIST digits (LeCun & Cortes, 2005). CMNIST has two domains and 60000 images with size (3,28,28). The majority of the images in each domain will have a digit color and a background color correspond to the domain: domain A ↔ “red digit/green background” and domain B↔ “blue digit/brown background”. We define two bias degrees λd, λb to control the probability of the images having domain-associated colors, e.g., for an image in domain A, with λd probability, its digit is set to be red; otherwise, its digit color is randomly red or blue. The background colors are determined similarly with parameter λb. In our experiments,
Table 1: CMNIST
Z1 acc. Z2 acc.
Vanilla 90.2 14.3 wx ∖w1 (MLDG) 94.9 91.1 wx ∖w1 (TRM) 89.2 96.2 wx ∖w1 (Fish) 93.9 98.0 IS (Oracle) 90.0 100 wx ∖w1 (Oracle) 94.9 100
Table 2: CelebA-GH
Z1 acc. Z2 acc. FID ↓ Vanilla 88.4 16.8 38.5 wx ∖w1 (MLDG) 90.9 53.0 46.2 wx ∖w1 (TRM) 92.2 56.5 39.8 wx ∖w1 (Fish) 88.8 42.9 43.4 IS (Oracle) 89.1 40.6 44.3 wx ∖w1 (Oracle) 93.7 57.4 39.7
we set λd = 0.9 and λb = 0.8. Our goal is to transfer the digit color (Z1) while leaving the background color (Z2) invariant. (b) CelebA-GH: We construct the CelebA-G(ender)H(air) dataset based on the gender and hair color attributes in CelebA (Liu et al., 2015). CelebA-GH consists of 110919 images resized to (3,128,128). In CelebA-GH, domain A is non-blond-haired males, and the domain B is blond-haired females. Our goal is to transfer the facial characteristic of gender (Z1) while keeping the hair color (Z2) intact.
Models. We compare variants of orthogonal classifiers to the vanilla CycleGAN (Vanilla) and the importance sampling objective (IS). We consider two ways of obtaining the w1 classifier: (a) Oracle: The principal classifier w1 is trained on an oracle dataset where Z1 is the only discriminative direction, e.g., setting bias degrees λd = 0.9 and λb = 0 in CMNIST such that only digit colors vary across domains. (b) Domain generalization: Domain generalization algorithms aim to learn the prediction mechanism that is invariant across environments and thus generalizable to unseen environments (Blanchard et al., 2011; Arjovsky et al., 2019). The variability of environments is considered as nuisance variation. We construct environments such that only Y ∣Z1 is invariant. We defer details of the environments to Appendix E.1. We use three domain generalization algorithms, Fish (Shi et al., 2021), TRM (Xu & Jaakkola, 2021) and MLDG (Li et al., 2018), to obtain w1. We indicate different approaches by the parentheses after wx ∖w1 and IS, e.g., wx ∖w1 (Oracle) is the orthogonal classifier with w1 trained on Oracle datasets. Metric. We use three metrics for quantitative evaluation: 1) Z1 accuracy: the success rate of transferring an image’s latent z1 from domain A to domain B; 2) Z2 accuracy: percentage of transferred images whose latents z2 are unchanged; 3) FID scores: a standard metric of image quality (Heusel et al., 2017). We only report FID scores on the CelebA-GH dataset since it is not common to compute FID on MNIST images. Z1, Z2 accuracies are measured by two oracle classifiers that output an image’s latents z1 and z2 (Appendix E.1.3).
For more details of datasets, models and training procedure, please refer to Appendix E.

heading: 4.1.2 RESULTS
text: Comparison to IS. In section 3.2, we demonstrate that IS suffers from high variance when the divergences of the marginal and the label-conditioned latent distributions are large. We provide further empirical evidence that our classifier orthogonalization method is more robust than IS. Fig. 2(a) shows that the test loss of IS increases dramatically with the divergences. Fig. 2(b) displays that IS’s test loss grows rapidly when enlarging learning rate, which corroborates the observation that gradient variances are more detrimental to the model’s generalization with larger learning rates (Wang et al., 2013). In contrast, the test loss of wx ∖w1 remains stable with varying divergences and learning rates. In Fig. 2(c), we visualize the histograms of predicted probabilities of wx ∖ w1 (light color) and IS (dark color). We observe that the predicted probabilities of wx ∖ w1 better concentrates around the ground-truth probabilities (red lines).
Main result. As shown in Table 1 and 2, adding an orthogonal classifier to the vanilla CycleGAN significantly improves its z2 accuracy (from 14 to 90+ in CMNIST, from 16 to 40+ in CelebA-GH) while incurring a slight loss of the image quality. We observe that the oracle version of orthogonal classifier (wx ∖w1 (Oracle)) achieves best z2 accuracy on both datasets. In addition, class orthogonalization is compatible with domain generalization algorithms when the prediction mechanism Z1∣Y is invariant across collected environments.
In Fig. 3, we visualize the transferred samples from domain A. We observe that vanilla CycleGAN models change the background colors/hair colors along with digit colors/facial characteristics in CMNIST and CelebA. In contrast, orthogonal classifiers better preserve the orthogonal aspects Z2 in the input images. We also provide visualizations for domain B in Appendix C.

heading: 5 ORTHOGONAL CLASSIFIER FOR DOMAIN ADAPTATION
text: In unsupervised domain adaptation, we have two domains, source and target with data distribution ps, pt. Each sample comes with three variables, data X , task label Y and domain label U . We assume U is uniformly distributed in {0 (source), 1 (target)}. The task label is only accessible in the source domain. Consider learning a model h = g ○ f that is the composite of the encoder f ∶ X → Z and the predictor g ∶ Z → Y . A common practice of domain adaptation is to match the two domain’s feature distributions ps(f(X)), pt(f(X)) via domain adversarial training (Ganin & Lempitsky, 2015; Long et al., 2018; Shu et al., 2018). The encoder f is optimized to extract useful feature for the predictor while simultaneously bridging the domain gap via the following domain adversarial objective:
min f max D L(f,D) ∶= Ex∼ps[logD(f(x))] +Ex∼pt[log(1 −D(f(x)))] (4)
where discriminator D ∶ Z → [0,1] distinguishes features from two domains. The equilibrium of the objective is achieved when the encoder perfectly aligns the two domain, i.e., ps(f(x)) = pt(f(x)). We highlight that such equilibrium is not desirable when the target domain has shifted label distribution (Azizzadenesheli et al., 2019; des Combes et al., 2020). Instead, when the label shift appears, it is more preferred to align the conditioned feature distribution,i.e., ps(f(x)∣y) = pt(f(x)∣y),∀y ∈ Y . Now we show that our classifier orthogonalization technique can be applied to the discriminator for making it “orthogonal to” the task label. Specifically, consider the original discriminator as full classifier wx, i.e., for a given f , wx(x)0 = arg maxD L(f,D) = ps(f(x)) ps(f(x))+pt(f(x)) . We then construct the principle classifier w1 that discriminates the domain purely via the task label Y , i.e., w1(x)0 = Pr(U = 0∣Y = y(x)). Note that here we assume the task label Y can be determined by the data X , i.e., Y = y(X). We focus on the case that Y is discrete so w1 could be directly computed via frequency count. We propose to train the encoder f with the orthogonalized discriminator wx ∖w1,
min f L(f, (wx ∖w1)(⋅)0) = Ex∼ps[log(wx ∖w1)(x)0] +Ex∼pt[log(1 − (wx ∖w1)(x)0)] (5)
Proposition 3. Suppose there exists random variable Z2 = z2(X) orthogonal to y(X) = Y w.r.t p(f(X), U). Then f achieves global optimum if and only if it aligns all label-conditioned feature distributions, i.e., ps(f(x)∣y) = pt(f(x)∣y),∀y ∈ Y .
Note that in practice, we have no access to the target domain label prior pt(Y ) and the label y(x) for target domain data x ∼ pt. Thus we use the pseudo label ŷ as a surrogate to construct the principle classifier, where ŷ(x) = arg maxy h(x)y is generated by our model h.

heading: 5.1 EXPERIMENTS
text: Models. We take a well-known domain adaptation algorithm VADA (Shu et al., 2018) as our baseline. VADA is based on domain adversarial training and combined with virtual adversarial training and entropy regularization. We show that utilizing orthogonal classifier can improve its robustness to label shift. We compare it with two improvements: (1) VADA+wx∖w1 which is our method that plugs in the orthogonal classifier as a discriminator in VADA; (2) VADA+IW: We tailor the SOTA method for label shifted domain adaptation, importance-weighted domain adaptation (des Combes et al., 2020), and apply it to VADA. We also incorporate two recent domain adaptation algorithms for images— CyCADA (Hoffman et al., 2018) and ADDA (Tzeng et al., 2017)—into comparisons.
Setup. We focus on visual domain adaptation and directly borrow the datasets, architectures and domain setups from Shu et al. (2018). To add label shift between domains, we control the label distribution in the two domains. For source domain, we sub-sample 70% data points from the first half of the classes and 30% from the second half. We reverse the sub-sampling ratios on the target domain. The label distribution remains the same across the target domain train and test set. Please see Appendix E.2 for more details.
Results. Table 3 reports the test accuracy on seven domain adaptation tasks. We observe that VADA+wx∖ w1 improves over VADA across all tasks and outperforms VADA+IW on five out of seven tasks. We find VADA+IW performs worse than VADA in two tasks, MNIST→SVHN and MNIST→MNIST-M. Our hypothesis is that the domain gap is large between these datasets, hindering the estimation of importance weight. Hence, VADA-IW is unable to adapt the label shift appropriately. In addition, the results show that VADA+wx ∖w1 outperforms ADDA on six out of seven tasks.

heading: 6 ORTHOGONAL CLASSIFIER FOR FAIRNESS
text: We are given a dataset D = {(xt, yt, ut)}nt=1 that is sampled iid from the distribution pXY U , which contains the observations x ∈ X , the sensitive attributes u ∈ U and the labels y ∈ Y . Our goal is to learn a classifier that is accurate w.r.t y and fair w.r.t u. We frame the fairness problem as finding the orthogonal classifier of an “totally unfair” classifier w1 that only uses the sensitive attributes u for prediction. We can directly get the unfair classifier w1 from the dataset statistics, i.e., w1(x)y = p(Y = y∣U = u(x)). Below we show that the orthogonal classifier of unfair classifier meets equalized odds, one metric for fairness evaluation. Proposition 4. If the orthogonal random variable of U = u(X) w.r.t pXY exists, then the orthogonal classifier wx ∖w1 satisfies the criterion of equalized odds.
We emphasize that, unlike existing algorithms for learning fairness classifier, our method does not require additional training. We obtain a fair classifier via orthogonalizing an existing model wx which is simply the vanilla model trained by ERM on the dataset D.

heading: 6.1 EXPERIMENTS
text: Setup. We experiment on the UCI Adult dataset, which has gender as the sensitive attribute and the UCI German credit dataset, which has age as the sensitive attribute (Zemel et al., 2013; Madras et al., 2018; Song et al., 2019). We compare the orthogonal classifier wx ∖w1 to three baselines: LAFTR (Madras et al., 2018), which proposes adversarial objective functions that upper bounds the unfairness metrics; L-MIFR (Song et al., 2019), which uses mutual information objectives to control the expressivenessfairness trade-off; ReBias (Bahng et al., 2020), which minimizes the Hilbert-Schmidt Independence Criterion between the model representations and biased representations; as well as the Vanilla (wx) trained by ERM. We employ two fairness metrics – demographic parity distance (∆DP) and equalized odds distance (∆EO) – defined in Madras et al. (2018). We denote the penalty coefficient of the adversarial or de-biasing objective as γ, whose values govern a trade-off between prediction accuracy and fairness, in all baselines. We borrow experiment configurations, such as CNN architecture, from Song et al. (2019). Please refer to Appendix E.3 for more details.
Results. Tables 4, 5 report the test accuracy, ∆DP and ∆EO on Adults and German datasets. We observe that the orthogonal classifier decreases the unfairness degree of the Vanilla model and has competitive performances to existing baselines. Especially in the German dataset, compared to LAFTR, our method
has the same ∆EO but better ∆DP and test accuracy. It is surprising that our method outperforms LAFTR, even though it is not specially designed for fairness. Further, our method has benefit of being training-free, which allows it to be applied to improve any off-the-shelf classifier’s fairness without additional training.
Table 4: Accuracy v.s. Fairness (Adults)
Acc.↑ ∆DP ↓ ∆EO ↓ Vanilla 84.5 0.19 0.20
LAFTR (γ = 0.1) 84.2 0.14 0.09 LAFTR (γ = 0.5) 84.0 0.12 0.07 L-MIFR (γ = 0.05) 81.6 0.04 0.15 L-MIFR (γ = 0.1) 82.0 0.06 0.16 ReBias (γ = 100) 84.3 0.15 0.11 ReBias (γ = 50) 84.4 0.17 0.16 wx ∖w1 81.6 0.12 0.12
Table 5: Accuracy v.s. Fairness (German)
Acc.↑ ∆DP ↓ ∆EO ↓ Vanilla 76.0 0.19 0.33
LAFTR (γ = 0.1) 73.0 0.11 0.17 LAFTR (γ = 0.5) 72.7 0.11 0.19 L-MIFR (γ = 0.1) 75.8 0.10 0.21 L-MIFR (γ = 0.05) 75.6 0.08 0.18 ReBias (γ = 100) 73.0 0.07 0.17 ReBias (γ = 50) 75.0 0.10 0.20 wx ∖w1 75.4 0.09 0.18

heading: 7 RELATED WORKS
text: Disentangled representation learning Similar to orthogonal random variables, disentangled representations are also based on specific notions of feature independence. For example, Higgins et al. (2018) defines disentangled representations via equivalence and independence of group transformations, Kim & Mnih (2018) relates disentanglement to distribution factorization, and Shu et al. (2020) characterizes disentanglement through generator consistency and a notion of restrictiveness. Our work differs in two key respects. First, most definitions of disentanglement rely primarily on the bijection between latents and inputs (Shu et al., 2020) absent labels. In contrast, our orthogonal features must be conditionally independent given labels. Further, in our work orthogonal features remain implicit and they are used discriminatively in predictors. Several approaches aim to learn disentangled representations in an unsupervised manner (Chen et al., 2016; Higgins et al., 2017; Chen et al., 2018). However, Locatello et al. (2019) argues that unsupervised disentangled representation learning is impossible without a proper inductive bias.
Model de-biasing A line of works focuses on preventing model replying on the dataset biases. Bahng et al. (2020) learns the de-biased representation by imposing HSIC penalty with biased representation, and Nam et al. (2020) trains an unbiased model by up-weighting the high loss samples in the biased model. Li et al. (2021) de-bias training data through data augmentation. However, these works lack theoretical definition for the de-biased model in general cases and often require explicit dataset biases.
Density ratio estimation using a classifier Using a binary classifier for estimating the density ratio (Sugiyama et al., 2012) enjoys widespread attention in machine learning. The density ratio estimated by classifier has been applied to Monte Carlo inference (Grover et al., 2019; Azadi et al., 2019), class imbalance (Byrd & Lipton, 2019) and domain adaptation (Azizzadenesheli et al., 2019).
Learning a set of diverse classifiers Another line of work related to ours is learning a collection of diverse classifiers through imposing penalties that relate to input gradients. Diversity here means that the classifiers rely on different sets of features. To encourage such diversity, Ross et al. (2018; 2020) propose a notion of local independence, which uses cosine similarity between input gradients of classifiers as the regularizer, while in Teney et al. (2021) the regularizer pertains to dot products. Ross et al. (2017) sequentially trains multiple classifiers to obtain qualitatively different decision boundaries. We defer more discussions of the advantages of classifier orthogonalization over existing methods to Appendix F.

heading: 8 CONCLUSION
text: We consider finding a discriminative direction that is orthogonal to a given principal classifier. The solution in the linear case is straightforward but does not generalize to the non-linear case. We define and investigate orthogonal random variables, and propose a simple but effective algorithm (classifier orthogonalization) to construct the orthogonal classifier with both theoretical and empirical support. Empirically, we demonstrate that the orthogonal classifier enables controlled style transfer, improves existing alignment methods for domain adaptation, and has a lower degree of unfairness.

heading: ACKNOWLEDGEMENTS
text: The work was partially supported by an MIT-DSTA Singapore project and by an MIT-IBM Grand Challenge grant. YX was partially supported by the HDTV Grand Alliance Fellowship. We would like to thank the anonymous reviewers for their valuable feedback.

heading: A MORE PROPERTIES OF ORTHOGONAL RANDOM VARIABLE
text: In this section we demonstrate the properties of orthogonal random variables. We also discuss the existence and uniqueness of orthogonal classifier when given the principal classifier. Below we list some useful properties of orthogonal random variables. Proposition 5. Let Z1 and Z2 be any mutually orthogonal w.r.t PXY , then we have
(i) Invariance: For any diffeomorphism g, g(Z1) and g(Z2) are also mutually orthogonal.
(ii) Distribution-free: Z1, Z2 are mutually orthogonal w.r.t PX′Y if and only if there exists a diffeomorphism mapping between X and X ′.
(iii) Existence: Suppose the label-conditioned distributions py ∈ C1, supp(py) = X ,∀y ∈ Y . For z1 ∈ C1 and z1(X ) is diffeomorphism to Euclidean space, then ∀i ∈ Y , there exists a diffeomorphism mapping (z1(X), z2,i(X)) such that z1(X) ⊥ z2,i(X)∣Y = i. Further if there exists diffeomorphism mappings between z2,is, then the orthogonal r.v. of z1(X) exists.
In the following theorem, we justify the validity of the classifier orthogonalization when z1(x) satisfies some regularity conditions. Theorem 2. Suppose w1(x)i = p(Y = i∣z1(x)). If the label-condition distributions pys, and z1 satisfy the conditions in Proposition 5.(iii), then wx ∖w1 is the unique orthogonal classifier of w1.
Note that our construction of wx ∖w1 does not require the exact expression of z1(X), its orthogonal r.v or data generation process. The theorem states that the orthogonal classifier constructed by classifier orthogonalization is the Bayesian classifier for any orthogonal random variables of z1(X).

heading: B PROOFS

heading: B.1 PROOF FOR PROPOSITION 1
text: Proposition 1. Suppose the orthogonal r.v. of z1(X) w.r.t pXY exists and is denoted as z2(X). Then z(X) = z2(X) is a maximizer of I(z(X);Y ∣z1(X)) subject to I(z(X); z1(X)∣Y ) = 0.
Proof. For any function z, by chain rule we have I(z1(X), z2(X);Y ) = I(z1(X);Y ) + I(z2(X);Y ∣z1(X)) and I(z1(X), z(X);Y ) = I(z1(X);Y )+ I(z(X);Y ∣z1(X)). Further, the definition of the orthogonal r.v. ensures that there exists a differmorphism f between X and z1(X), z2(X), which implies I(z1(X), z(f(z1(X), z2(X)));Y ) = I(z1(X), z(X);Y ). Hence by data processing inequality we have:
I(z1(X), z2(X);Y ) ≥ I(z1(X), z(f(z1(X), z2(X)));Y ) = I(z1(X), z(X);Y ) ⇔ I(z1(X);Y ) + I(z2(X);Y ∣z1(X)) ≥ I(z1(X);Y ) + I(z(X);Y ∣z1(X))
⇔ I(z2(X);Y ∣z1(X)) ≥ I(z(X);Y ∣z1(X))
The above inequality shows that z = z2 maximize the mutual information I(z(X);Y ∣z1(X)). Further, by definition of the orthogonal r.v., z = z2 is independent of z1 conditioned on Y , i.e. z(X) ⊥ z1(X)∣Y which is equivalent to I(z(X); z1(X)∣Y ) = 0.

heading: B.2 PROOF FOR THEOREM 1
text: Theorem 1. Assume py is uniform distribution, ∀wx ∈W takes values in (m,1 −m)C with m ∈ (0, 12), and 1/pX ∣Y (x∣y) ∈ (0, γ) ⊂ (0,+∞) holds for ∀x ∈ X , y ∈ Y . Then for any δ ∈ (0,1) with probability at least 1 − δ, we have:
∣R(ŵx ∖w1) −R(w∗x ∖w1)∣ ≤ (1 + γ) ⎛ ⎜ ⎝ 2R∣D∣(W) + 2 log 1 m
¿ ÁÁÀ2 log 1 δ
∣D∣ ⎞ ⎟ ⎠
Proof. Denote the empirical risk of w as
R̂(w) = R̂(w) = − 1∣D∣ ∑(xi,yi)∈D logw(xi)yi
and the population risk as
R(w) = −Ep(x,y) [logw(x)y]
Step 1: bounding excess risk ∣R(ŵx) −R(w∗x)∣. By the classical result in theorem 8 in Bartlett & Mendelson (2001), we know that for any w ∈ W , δ ∈ (0,1), since − logw(x)y ∈ (0, log 1m), with probability at least 1 − δ,
∣R̂(w) −R(w)∣ = ∣ 1 n
n
∑ i=1
log(w(xi))yi −Ep[log(w(x)y)]∣ ≤ 2Rn(W) + 2 log 1
m
√ 2 log 1
δ
n
Since ŵx = infwx∈W R̂(wx),w∗x = infwx∈W R(wx), and ∣R̂(ŵx) − R(ŵx)∣ ≤ 2Rn(W) + 2 log 1
m √ 2 log 2δ n , ∣R̂(w∗x) −R(w∗x)∣ ≤ 2Rn(W) + 2 log 1m √ 2 log 1δ n , we have
∣R(ŵx) −R(w∗x)∣ ≤ 2Rn(W) + 2 log 1
m
√ 2 log 1
δ
n (6)
Step 2: bounding ∣R(ŵx ∖w1) −R(w∗x ∖w1)∣ by ∣R(ŵx) −R(w∗x)∣.
R(w ∖w1) = −Ep(x,y) ⎡⎢⎢⎢⎢⎢⎣ log w(x)y w1(x)y ∑y′ w(x)y′ w1(x)y′ ⎤⎥⎥⎥⎥⎥⎦ = R(w) +Ep(x,y) ⎡⎢⎢⎢⎢⎣ logw1(x)y∑ y′ w(x)y′ w1(x)y′ ⎤⎥⎥⎥⎥⎦
Then we have:
∣R(ŵx ∖w1) −R(w∗x ∖w1)∣
≤ ∣R(ŵx) −R(w∗x)∣ + RRRRRRRRRRRR Ep(x,y) ⎡⎢⎢⎢⎢⎣ logw1(x)y∑ y′ ŵx(x)y′ w1(x)y′ ⎤⎥⎥⎥⎥⎦ −Ep(x,y) ⎡⎢⎢⎢⎢⎣ logw1(x)y∑ y′ w∗x(x)y′ w1(x)y′ ⎤⎥⎥⎥⎥⎦ RRRRRRRRRRRR = ∣R(ŵx) −R(w∗x)∣ + RRRRRRRRRRRRRR Ep(x,y) ⎡⎢⎢⎢⎢⎢⎣ log ∑y′ ŵx(x)y′ w1(x)y′ ∑y′ w∗x(x)y′ w1(x)y′ ⎤⎥⎥⎥⎥⎥⎦ RRRRRRRRRRRRRR
≤ ∣R(ŵx) −R(w∗x)∣ +max ⎛ ⎜ ⎝ RRRRRRRRRRRRRR Ep(x,y) ⎡⎢⎢⎢⎢⎢⎣ log max y′ ŵx(x)y′ w1(x)y′ w∗x(x)y′ w1(x)y′ ⎤⎥⎥⎥⎥⎥⎦ RRRRRRRRRRRRRR , RRRRRRRRRRRRRR Ep(x,y) ⎡⎢⎢⎢⎢⎢⎣ log min y′ ŵx(x)y′ w1(x)y′ w∗x(x)y′ w1(x)y′ ⎤⎥⎥⎥⎥⎥⎦ RRRRRRRRRRRRRR ⎞ ⎟ ⎠
We define the ratio r(x, y) = ŵx(x)y w∗x(x)y . We define y(x) ∶= arg miny r(x, y), ȳ(x) ∶= arg maxy r(x, y). We have r(x, y(x)) ≤ ∑y′ ŵx(x)y′ /w1(x)y′∑y′ w∗x(x)y′ /w1(x)y′ ≤ r(x, ȳ(x)). Let assume 1 p(y∣x) ≤ γ for all x, y. For any function y′ ∶ X → Y , we have the following bound, where we have importance weight φ(x, y) ∶= 1 p(y∣x) if y = y′(x) otherwise 0, ∣Ex log r(x, y′(x))∣ = ∣Ex,yφ(x, y) log r(x, y)∣ ≤ γ∣Ex,y log r(x, y)∣ = γ∣R(ŵx) −R(w∗x))∣
As a result, we have
∣E log ∑y ′ ŵx(x)y′/w1(x)y′
∑y′ w∗x(x)y′/w1(x)y′ ∣ ≤ max (∣E log r(x, y(x))∣, ∣E log r(x, ȳ(x))∣) ≤ γ∣R(ŵx) −R(w∗x)∣
Thus
∣R(ŵx ∖w1) −R(w∗x ∖w1)∣ ≤ ∣R(ŵx) −R(w∗x)∣
+max ⎛ ⎜ ⎝ RRRRRRRRRRRRRR Ep(x,y) ⎡⎢⎢⎢⎢⎢⎣ log max y′ ŵx(x)y′ w1(x)y′ w∗x(x)y′ w1(x)y′ ⎤⎥⎥⎥⎥⎥⎦ RRRRRRRRRRRRRR , RRRRRRRRRRRRRR Ep(x,y) ⎡⎢⎢⎢⎢⎢⎣ log min y′ ŵx(x)y′ w1(x)y′ w∗x(x)y′ w1(x)y′ ⎤⎥⎥⎥⎥⎥⎦ RRRRRRRRRRRRRR ⎞ ⎟ ⎠ ≤ (1 + γ)∣R(ŵx) −R(w∗x)∣ (7)
Combining Eq. (6) and Eq. (7), we know that with probability 1 − δ, we have:
∣R(ŵx ∖w1) −R(w∗x ∖w1)∣ ≤ (1 + γ) ⎛ ⎜ ⎝ 2Rn(W) + 2 log 1 m
√ 2 log 1
δ
n ⎞ ⎟ ⎠

heading: B.3 PROOF FOR PROPOSITION 5 AND THEOREM 2
text: Proposition 5. Let Z1 and Z2 be any mutually orthogonal w.r.t PXY , then we have
(i) Invariance: For any diffeomorphism g, g(Z1) and g(Z2) are also mutually orthogonal.
(ii) Distribution-free: Z1, Z2 are mutually orthogonal w.r.t PX′Y if and only if there exists a diffeomorphism mapping between X and X ′.
(iii) Existence: Suppose the label-conditioned distributions py ∈ C1, supp(py) = X ,∀y ∈ Y . For z1 ∈ C1 and z1(X ) is diffeomorphism to Euclidean space, then ∀i ∈ Y , there exists a diffeomorphism mapping (z1(X), z2,i(X)) such that z1(X) ⊥ z2,i(X)∣Y = i. Further if there exists diffeomorphism mappings between z2,is, then the orthogonal r.v. of z1(X) exists.
Proof. (i) Since Z1 and Z2 are independent, the independence also holds for g(Z1) and g(Z2). In addition, we construct the diffeomorphism between (g(Z1), g(Z2)) and X as f̂(g(Z1), g(Z2)) = f(g−1(g(Z1)), g−1(g(Z2))) =X . Apparently f(g−1(Z1), g−1(Z2)) is a diffeomorphism.
(ii) We denote the diffeomorphism between X ′ and X as f̂ . Then the diffeomorphism mapping between (Z1, Z2) and X is f̂ ○ f . Thus Z1, Z2 are mutually orthogonal w.r.t X ′. (iii) We will use a constructive proof.
Step 1: Denote dim(X ) = d,dim(z1(X )) = k, then we can prove that the manifold[z1(X ),Rd−k] is diffeomorphism of X . We denote the diffeomorphism as f , and denote f(x) = [z1(x), t(x)] where z1 ∶ X → z1(X ), t ∶ X → Rd−k. Step 2: For X ∣Y = y, let Fj(t(x)j ∣ t(x)1,⋯, t(x)j−1, z1(x),1) ∶ R → [0,1], j ∈ {1, . . . , d − k} be the CDF corresponding to the distribution of t(x)j ∣ t(X)1 = t(x)1,⋯, t(X)j−1 = t(x)j−1, z1(X) = z1(x), Y = y.
h(t(x); z1(x))1 = F1(t(x)1 ∣ z1(x), y) h(t(x); z1(x))i = Fi(t(x)i ∣ t(x)1,⋯, t(x)i−1, z1(x),1), i ∈ {2, . . . , d}
The conditions p ∈ C1, p(x) > 0,∀x ∈ X ensure that the PDF of f(X) is also in C1 and takes values in (0,∞). Thus the above CDFs are all diffeomorphism mapping. By the inverse CDF theorem, for any z1(x), h(t(X); z1(X) = z1(x)) is a uniform distribution in (0,1)d−k. Hence the random variable defined by the mapping h, i.e., z2,y(X) = h(t(X); z1(X)), is independent of z1(X) given Y = 1.
In addition, by the construction of z2,y(x) we know that there exists a diffeomorphism f̂ between (z1(X ), t(X )) and (z1(X ), z2,y(X )) such that f̂(z1(X), t(X)) = (z1(X), z2,y(X)). Then f−1 ○ f̂−1(z1(X), z2,y(X)) =X is also a diffeomorphsim mapping. Step 3: From the condition we know that for every y ∈ Y , there exists a diffeomorphism function my such thatmy○z2,y(x) = z2,1(x). Apparently ∀y,my○z2,y(X) ⊥ z2,1(X)∣Y = y by z2,y(X) ⊥ z1(X)∣Y = y. Further, (z1, z2,1) is a diffeomorphism. Hence z2,1(X) is the orthogonal r.v. of z1(X) w.r.t PXY .
Theorem 2. Suppose w1(x)i = p(Y = i∣z1(x)). If the label-condition distributions pys, and z1 satisfy the conditions in Proposition 5.(iii), then wx ∖w1 is the unique orthogonal classifier of w1.
Proof. By the existence property in Proposition 5, we know that for X , there exists a orthogonal r.v. of z1(X) and denote it as z2(X1). By the proposition we know that there exists a common diffeomorphism f mapping (z1(X ∣y), z2(X ∣y)) to X ∣y, ∀y ∈ Y .
Further, by change of variables and the definition of orthogonal r.v., we have pi,2(z2) pj,2(z2) = pi,1(z1)pi,2(z2)volJf (z1,z2) pj,1(z1)pj,2(z2)volJf (z1,z2)/ pi,1(z1) pj,1(z1) = pi(x) pj(x)/ pi,1(z1) pj,1(z1) = wx(x)i wx(x)j / w1(x)i w1(x)j . Thus via the bijection of classifier and density ratios we know that wx ∖w1(x)i = p(Y = i∣z2(x)).

heading: B.4 PROOF FOR PROPOSITION 2
text: Proposition 2. The global minimum of LABOGAN(GAB) is achieved if and only if P̃Z1,Z2(z1, z2) = QZ1(z1)PZ2(z2).
Proof. By definition, r(x) = w2(x) 1−w2(x) = P (z2(x)) Q(z2(x)) . Thus we can reformulate the criterion L AB OGAN as the following:
LABOGAN(GAB) = Ex∼P̃ log P̃ (x)
P̃ (x) +Q(x)r(x)
= Ez1,z2∼P̃ log P̃ (z1, z2)
P̃ (z1, z2) +Q(z1)Q(z2)P (z2)Q(z2)
≥ − logEz1,z2∼P̃ [ P̃ (z1, z2) +Q(z1)P (z2)
P̃ (z1, z2) ] = − log 2
where we get the lower bound by Jensen’s inequality. The equality holds when P̃ (z1, z2) = Q(z1)P (z2).

heading: B.5 PROOF FOR PROPOSITION 3
text: Proposition 3. Suppose there exists random variable Z2 = z2(X) orthogonal to y(X) = Y w.r.t p(f(X), U). Then f achieves global optimum if and only if it aligns all label-conditioned feature distributions, i.e., ps(f(x)∣y) = pt(f(x)∣y),∀y ∈ Y .
Proof. By definition, optimal classifier wx(x)0 = ps(f(x))ps(f(x))+pt(f(x)) , principle classifier w1(x)0 = ps(y(x)) ps(y(x))+pt(y(x)) . By the definition of orthogonal r.v., (Y,U) and f(X) have a bijection between them. It suggests, conditioned on Y , the supports of f(X)∣Y = y is non-overlapped for different y in both domains ps and pt. It means if ps(f(x)∣y) > 0 then ∀y′ ≠ y, ps(f(x)∣y′) = 0. Thus the orthogonal classifier wx ∖w1 satisfies: (wx ∖w1)(x)0 = ps(f(x)) ps(y(x)) /(ps(f(x)) ps(y(x)) + pt(f(x)) pt(y(x)) )
= ∑y ′ ps(f(x)∣y′)ps(y′) ps(y(x)) / (∑y ′ ps(f(x)∣y′)ps(y′) ps(y(x)) + ∑y ′ pt(f(x)∣y′)pt(y′) pt(y(x)) )
= ps(f(x)∣y(x))ps(y(x)) ps(y(x)) / (ps(f(x)∣y(x))ps(y(x)) ps(y(x)) + pt(f(x)∣y(x))pt(y(x)) pt(y(x)) )
= ps(f(x)∣y(x)) ps(f(x)∣y(x)) + pt(f(x)∣y(x))
Thus the objective in Eq. (5) can be reformulated as, L(f, (wx ∖w1)(⋅)0)
=Ex∼ps[log ps(f(x)∣y(x))
ps(f(x)∣y(x)) + pt(f(x)∣y(x)) ] +Ex∼pt[log pt(f(x)∣y(x)) ps(f(x)∣y(x)) + pt(f(x)∣y(x)) ]
=Ey∼psEx∼ps(x∣y)[− log ps(f(x)∣y) + pt(f(x)∣y)
ps(f(x)∣y) ] +Ey∼ptEx∼pt(x∣y)[− log ps(f(x)∣y) + pt(f(x)∣y) pt(f(x)∣y) ]
≥ −Ey∼ps [logEx∼ps(x∣y)[ ps(f(x)∣y) + pt(f(x)∣y)
ps(f(x)∣y) ]] −Ey∼pt [logEx∼pt(x∣y)[ ps(f(x)∣y) + pt(f(x)∣y) pt(f(x)∣y) ]]
= − 2 log 2.
The lower-bound holds due to Jensen’s inequality. The equality is achieved if and only if ps(f(x)∣y) pt(f(x)∣y) is invariant to x, for all y, i.e., ∀y ∈ Y, ps(f(x)∣y) = pt(f(x)∣y).

heading: B.6 PROOF FOR PROPOSITION 4
text: Proposition 4. If the orthogonal random variable of U = u(X) w.r.t pXY exists, then the orthogonal classifier wx ∖w1 satisfies the criterion of equalized odds.
Proof. We denote the orthogonal random variables as z2(X), and wx ∖ w1(x) = Pr[y∣z2(x)]. Since z2(X) ⊥ U ∣Y , we know that wx ∖ w1(X) ⊥ U ∣Y . Hence the prediction of the classifier wx ∖ w1 is conditional independent of sensitive attribute U on the ground-truth label Y , which meets the equalized odds metric.

heading: C EXTRA SAMPLES

heading: D EXTRA EXPERIMENTS
text: D.1 STYLE TRANSFER
We show transferred samples for both domains in Fig. 4 on CMNIST and CelebA-GH.

heading: D.2 STYLE TRANSFER ON CELEBA
text: Unlike the split in CelebA-GH dataset, domain A is males, and domain B is females. The two domains together form the full CelebA (Liu et al., 2015) with 202599 images. Note that there exists large imbalance of hair colors within the male group, with only around 2% males having blond hair. Table 6 reports the Z1/Z2 accuracies and FID scores on the full CelebA datasets. We find that our method improves the style transfer on the original CelebA dataset, especially the Z2 accuracy. It shows that our method can help style transfer in real-world datasets with multiple varying factors.

heading: E EXTRA EXPERIMENT DETAILS

heading: E.1 STYLE TRANSFER

heading: E.1.1 DATASET DETAILS
text: We randomly sampled two digits colors and two background colors for CMNIST. For CelebA-GH, we extract two subsets—male with non-blond hair and female with blond hair—by the attributes provided in CelebA dataset. For all datasets, we use 0.8/0.2 proportions to split the train/test set.
For CelebA dataset, following the implementation of Zhu et al. (2017) (https://github.com/ junyanz/CycleGAN), we use 128-layer UNet as the generator and the discriminator in PatchGAN. For CMNIST dataset, we use a 6-layer CNN as the generator and a 5-layer CNN as the discriminator. We adopt Adam with learning rate 2e-4 as the optimizer and batch size 128/32 for CMNIST/CelebA.

heading: E.1.2 DETAILS OF MODELS
text: We craft datasets for training the oracle w1(x) = Pr(Y ∣z1(x)). For CMNIST, oracle dataset has bias degrees 0.9/0. For CelebA-GH, oracle dataset has {male, female} as classes and the hair colors under each class are balanced.
For each dataset, we construct two environments to train the domain generalization models. For CMNIST, the two environments are datasets with bias degrees 0.9/0.4 and 0.9/0.8. For CelebA-GH, the two environments consist of different groups of equal size: one is {non-blond-haired males, blond-haired females} and the other is {non-blond-haired males, blond-haired females, non-blond-haired females, blond-haired males}. Note that the facial characteristic of gender (Z1) is the invariant prediction mechanism across environments, instead of the hair color.
E.1.3 EVALUATION FOR Z1/Z2 ACCURACY
To evaluate the accuracies on Z1, Z2 latents, we train two oracle classifiers w∗1(x) = Pr(Y ∣z1(x)),w∗2(x) = Pr(Y ∣z2(x)) on two designed datasets. Specifically, w1/w2 are trained on datasets D1/D2 with Z1/Z2 as the only discriminative direction. For CMNIST, D1 is the dataset with bias degrees 0.9/0 and D2 is the dataset with bias degrees 0/0.8. For CelebA-GH, D1 is the dataset with {male, female} as classes and the hair colors under each class are balanced. D2 is the dataset with {blond hair, non-blond hair} as classes and the males/females under each class are balanced. The Z1 accuracy on dataset D for transfer model G is:
Z1 accuracy = 1
∣D∣ ∑x∈D I(arg max y w∗1(x) /= arg max y w∗1(G(x)))
And Z2 accuracy is:
Z1 accuracy = 1
∣D∣ ∑x∈D I(arg max y w∗2(x) = arg max y w∗2(G(x)))
where I is the indicator function. Z1 accuracy measures the success rate of transferring the Z1 and Z2 accuracy measures the success rate of keeping Z2 aspects unchanged.

heading: E.2 DOMAIN ADAPTATION
text: The full names for the seven datasets are MNIST, MNIST-M, SVHN, GTSRB, SYN-DIGITS (DIGITS), SYN-SIGNS (SIGNS), CIFAR-10 (CIFAR) and STL-10 (STL). We sub-sample each dataset by the designated imbalance ratio to construct the pairs.
We use the 18-layer neural network in Shu et al. (2018) with pre-process via instance-normalization. Following Shu et al. (2018), smaller CNN is used for digits (MNIST, MNIST-M, SVHN, DIGITS) and traffic signs (SIGNS, GTSRB) and larger CNN is used for CIFAR-10 and STL-10. We use the Adam optimizer and hyper-parameters in Appendix B in Shu et al. (2018) except for MNIST →MNIST-M, where we find that setting λs = 1, λd = 1e − 1 largely improves the VADA performance over label shifts. Furthermore, we set λd = 1e − 2, i.e., the default value suggested by Shu et al. (2018), to enable adversarial feature alignment.

heading: E.3 FAIRNESS
text: The two datasets are: the UCI Adult dataset2 which has gender as the sensitive attribute; the UCI German credit dataset3 which has age as the sensitive attribute. We borrow the encoder, decoder and the final fc layer from Song et al. (2019). For fair comparison, we use the same encoder+fc layer as the function familyW of our classifier since our method do not need decoder for reconstruction. We use Adam with learning rate 1e-3 as the optimizer, and a batch size of 64.
The original ReBias method trains a set of biased models to learn the de-biased representations (Bahng et al., 2020), such as designing CNNs with small receptive fields to capture the texture bias. However, in the fairness experiments, the bias is explicitly given, i.e., the sensitive attribute. For fair comparison, we set the HSIC between the sensitive attribute and the representations as the de-bias regularizer.

heading: F LEARNING A DIVERSE SET OF CLASSIFIERS
text: In this section we discuss the difference and advantages of the classifier orthogonalization, compared to methods that learn a diverse set of classifiers. We also provide a counter-example to show that the orthogonal input gradient does not lead to a pair of orthogonal classifiers. We show that orthogonal classifiers might not in optimal solution set of minimizing input gradient penalty.
The goals of learning diverse classifiers include interpretability (Ross et al., 2017), overcoming simplicity bias (Teney et al., 2021), improving ensemble performance (Ross et al., 2020), and recovering confounding decision rules (Ross et al., 2018). There is a direct trade-off between diversity and accuracy and this is controlled by the regularization parameter. In contrast, in our work, given the principal classifier, our method directly constructs a classifier that uses only the orthogonal variables for prediction. There is no trade-off to set in this sense. We also focus on novel applications of controlling the orthogonal directions, such as style transfer, domain adaptation and fairness. Further, our notion of orthogonality is defined via latent orthogonal variables that relate to inputs via a diffeomorphism (Definition 1) as opposed to directly in the input space. Although learning diverse classifiers through input gradient penalties is efficient, it does not guarantee orthogonality in the sense we define it. We provide an illustrative counter-example in Appendix F, where the input space is not disentangled nor has orthogonal input gradients but corresponds to a pair of orthogonal classifiers in our sense. We also prove that, given the principal classifier, minimizing the loss by introducing an input gradient penalty would not necessarily lead to an orthogonal classifier.
We note that one clear limitation of our classifier orthogonalization procedure is that we need access to the full classifier. Learning this full classifier can be impacted by simplicity bias (Shah et al., 2020) that could prevent it from relying on all the relevant features. We can address this limitation by leveraging previous efforts (Ross et al., 2020; Teney et al., 2021) to mitigate simplicity bias when training the full classifier.

heading: F.1 RELATIONSHIP TO ORTHOGONAL INPUT GRADIENTS
text: The orthogonality constraints on input gradients demonstrate good performance in learning a set of diverse classifiers (Ross et al., 2017; 2018; 2020; Teney et al., 2021). They typically use the dot product of input gradients between pairs of classifiers as the regularizer. We highlight that when facing the latent orthogonal random variables, the orthogonal gradient constraints on input space no longer guarantees to learn the orthogonal classifier. We demonstrate it on a simple non-linear example below.
Consider a binary classification problem with the following data generating process. Label Y is uniformly distributions in {−1,1}. Conditioned on the label, we have two independent k-dimensional latents
2https://archive.ics.uci.edu/ml/datasets/adult 3https://archive.ics.uci.edu/ml/datasets/Statlog+%28German+Credit+Data%29
Z1, Z2 such that Z1∣Y = y ∼ N (yµ1, Ik), Z2∣Y = y ∼ N (yµ2, Ik). µ1 ∈ Rk, µ2 ∈ Rm are the means of the latent variables, and k > m. The data X is generated from latents via the following
diffeomorphism X = ⎛ ⎝ g(Z1 − ( Z2 0(k−m) )) Z2 ⎞ ⎠ where g is an arbitrary non-linear diffeomorphism on Rk. We can see that Z1, Z2 are mutually orthogonal w.r.t the distribution pXY . Now consider the Bayes optimal classifiers w1,w2 using variable Z1, Z2. We have w1(x) = pY ∣Z1(1∣z1) = σ(2µT1 z1) and w2(x) = pY ∣Z2(1∣z2) = σ(2µT2 z2) , where σ is the sigmoid function. Apparently, they are a pair of orthogonal classifiers. Besides, we denote the classifier based on the first m dimensions in z1 for prediction as w3, i.e., w3(x) = pY ∣(Z1)∶m(1∣(z1)∶m) = σ(2(µ1)T∶m(z1)∶m). Given the principal classifier w1, we consider using the loss function in Ross et al. (2018; 2020) to learn the orthogonal classifier of w1, by adding a input gradient penalty term to the standard classification loss:
Lw1(w) = Lc(w) + λE[cos2(∇xw1(x),∇xw(x))] Lc is the expected cross-entropy loss, cos is the cosine-similarity and λ is the hyper-parameter for the gradient penalty term (Ross et al., 2018; 2020). Below we show that (1) the orthogonal classifier w2 does not necessarily satisfy E[cos2(∇xw1(x),∇xw2(x))] = 0. (2) the orthogonal classifier w2 is not necessarily the minimizer of Lw1(w). Proposition 6. For the above (Z1, Z2), their corresponding Bayes classifiers w1,w2 satisfy E[∇xw1(x)T∇xw2(x)] = 0 if and only if (µ1)T∶mµ2 = 0.
Proof. Let X1 = g(Z1 − ( Z2 0(k−m) )), X2 = Z2 are the two components of X . Note that z1 = g−1(x1) + ( x20(k−m)). By chain rule, the input gradient of w1 is
∇xw1(x) = dz1 dx ∇z1 Pr(Y = 1∣Z1 = z1(x))
= (∇x1g −1(x1)
Im×k ) (k+m)×k
e−2µ T 1 z1(x)
(1 + e−2µT1 z1(x))2 ⋅ 2µ1
where Im×k is the submatrix of Ik×k. Similarly we get∇xw2(x) = ( 0
Im×m ) (k+m)×m
e−2µ T 2 z2(x)
(1+e−2µ T 2 z2(x))2
⋅2µ2.
Together, the dot product between input gradients is
∇xw1(x)T∇xw2(x) = 2e−2µ T 1 z1(x)µT1 (1 + e−2µT1 z1(x))2 (∇x1g −1(x1) Im×k ) T (k+m)×k ( 0 Im×m ) (k+m)×m 2e−2µ T 2 z2(x)µ2 (1 + e−2µT2 z2(x))2
= 4e −2µT1 z1(x)−2µ T 2 z2(x)(µ1)T∶mµ2
(1 + e−2µT1 z1(x))2(1 + e−2µT2 z2(x))2
Since 4e −2µT1 z1(x)−2µ T 2 z2(x)
(1+e−2µ T 1 z1(x))2(1+e−2µ T 2 z2(x))2
> 0, E[∇xw1(x)T∇xw2(x)] if and only if (µ1)T∶mµ2 = 0.
Proposition 6 first shows that the expected input gradient product of the two Bayes classifiers of underlying latents is non-zero, unless the linear decision boundaries on z1, z2 are orthogonal. Hence, given the principal classifier w1, the expected dot product of input gradients between w1 and its orthogonal classifier w2 does not have to be zero. Proposition 7. The orthogonal classifer w2 does not minimize Lw1(w) if (µ1)∶m = µ2 and µT1 ∇x1g−1(x1)T∇x1g−1(x1)k×m(µ1)∶m < 0. Particularly, we show that Lw1(w3) < Lw1(w2) in this case.
Proof. Let w3(x) = pY ∣(Z1)∶m(1∣(z1)∶m). The input gradient of w3(x) is
∇xw3(x) = (∇xw1(x))∶m = dz1 dx ∇(z1)∶m Pr(Y = 1∣(Z1)∶m = (z1(x))∶m)
= ((∇x1g −1(x1))k×m Im×m ) (k+m)×m
e−2(µ1) T ∶mz1(x)∶m
(1 + e−2(µ1)T∶mz1(x)∶m)2 ⋅ 2(µ1)∶m
When (µ1)∶m = µ2, the dot-product between ∇xw3(x),∇xw1(x) is
∇xw1(x)T∇xw3(x) = 2e−2µ T 1 z1(x)µT1 (1 + e−2µT1 z1(x))2 (∇x1g −1(x1) Im×k ) T (k+m)×k
((∇x1g −1(x1))k×m Im×m ) (k+m)×m
e−2(µ1) T ∶mz1(x)∶m
(1 + e−2(µ1)T∶mz1(x)∶m)2 ⋅ 2(µ1)∶m
= 4e −2µT1 z1(x)−2(µ1) T ∶mz1(x)∶m
(1 + e−2µT1 z1(x))2(1 + e−2(µ1)T∶mz1(x)∶m)2 (∥ µ2 ∥22 +µT1 ∇x1g−1(x1)T∇x1g−1(x1)k×m(µ1)∶m)
When (µ1)∶m = µ2, we know that z1(x), z2(x) are equally predictive of the label and thus Lc(w3) = Lc(w2). Note that if µT1 ∇x1g−1(x1)T∇x1g−1(x1)k×m(µ1)∶m < 0, we have E[cos2(∇xw1(x),∇xw2(x))] > E[cos2(∇xw1(x),∇xw3(x))]:
E[cos2(∇xw1(x),∇xw2(x))]
= E ⎡⎢⎢⎢⎢⎢⎢⎢⎢⎣ ⎛ ⎜⎜⎜⎜ ⎝ ∥ µ2 ∥22 ∥ (∇x1g −1(x1) I ) (k+m)×k µ1 ∥2∥ ( 0 I ) (k+m)×m µ2 ∥2 ⎞ ⎟⎟⎟⎟ ⎠ 2⎤⎥⎥⎥⎥⎥⎥⎥⎥⎦
> E ⎡⎢⎢⎢⎢⎢⎢⎢⎢⎣ ⎛ ⎜⎜⎜⎜ ⎝
(∥ µ2 ∥22 +µT1 ∇x1g−1(x1)T (∇x1g−1(x1))k×mµ2)
∥ (∇x1g −1(x1) I
) (k+m)×k
µ1 ∥2∥ (∇x1g −1(x1)
Im×k ) (k+m)×k µ2 ∥2
⎞ ⎟⎟⎟⎟ ⎠ 2⎤⎥⎥⎥⎥⎥⎥⎥⎥⎦ = E[cos2(∇xw1(x),∇xw3(x))]
The strict inequality holds by µT1 ∇x1g−1(x1)T∇x1g−1(x1)k×m(µ1)∶m < 0
(∇x1g −1(x1)
Im×k ) (k+m)×k
µ2 ∥2 =∥ (∇x1g −1(x1) 0
) (k+m)×k
µ2 + ( 0
Im×k ) (k+m)×k µ2 ∥2
= (∥ (∇x1g −1(x1) 0
) (k+m)×k
µ2 ∥22 + ∥ ( 0
Im×k ) (k+m)×k
µ2 ∥22) 1 2
≥∥ ( 0 Im×k ) (k+m)×k µ2 ∥2
To verify that µT1 ∇x1g−1(x1)T∇x1g−1(x1)k×m(µ1)∶m < 0 does exist, pick k = 3,m = 2, g−1(x) = ⎛ ⎝ 2 −3 3 1 −1 5 1 −1 1 ⎞ ⎠ x, and µ1 = ⎛ ⎝ 1 1 1 ⎞ ⎠ . We have µT1 ∇x1g−1(x1)T∇x1g−1(x1)k×m(µ1)∶m = −2 in this case.
Together, we have Lw1(w3) < Lw1(w2).
Proposition 7 shows that the orthogonal classifier w2 is not the minimizer of the loss with input gradient penalty. The results above also hold for un-normalized version of input gradient penalty in Teney et al. (2021) by similar analysis.

Review summaries:
- The paper introduces the notion of "orthogonal classifiers": classifiers that rely on orthogonal variables. It starts with the simple linear case, and adds a definition that also applies to the non-linear case. - The paper proposes two methods to identify a classifier orthogonal to a given one. - It then describes 3 use cases: style transfer, domain adaptation, and fairness. 

The paper presents classifier orthogonalization technique that works for non-linear classifiers. The idea is to find a method that orthogonalizes the full classifier w.r.t. the principal classifier so that the resulting classifier is statistically orthogonal to principal classifier. The algorithm turns out to be very simple, only requiring access to the full classifier $P(Y|x)$ and the principal classifier $P(Y|z(x))$, where $z$ is a control variable you want to orthogonalize against. The paper also discusses an alternative method of classifier orthogonalization using importance sampling.   The effectiveness of the proposed classifier orthogonalization technique has been demonstrated through 3 applications: controlled style transfer, domain adaptation, and classifier fairness. For controlled style transfer, authors modified the CycleGAN's generator update step by orthogonalizing discriminator w.r.t. the controlled style variable. For domain adaptation, they modified VADA, an adversarial domain adaptation approach, by orthogonalizing discriminator based on the label-based principal classifier, so that discriminator wouldn't discriminate the domain based on the frequency count of labels from each domain. For fairness, full classifier is orthogonalized by the sensitive attribute classifier.