Learning Fair Representations for Kernel Models
Zilong Tan Samuel Yeom Matt Fredrikson Ameet Talwalkar


Quiescent galaxies at z ≳ 2.5: observations vs. models
    Giacomo Girelli
    December 30, 2023
======================================================




Fair representations are a powerful tool for satisfying fairness goals such as statistical parity and equality of opportunity in learned models. 
Existing techniques for learning these representations are typically model-agnostic, as they pre-process the original data such that the output satisfies some fairness criterion, and can be used with arbitrary learning methods.
In contrast, we demonstrate the promise of learning a model-aware fair representation, focusing on kernel-based models.
We leverage the classical sufficient dimension reduction (SDR) framework to construct representations as subspaces of the reproducing kernel Hilbert space (RKHS), whose member functions are guaranteed to satisfy a given fairness criterion.
Our method supports several fairness criteria, continuous and discrete data, and multiple protected attributes.
We also characterize the fairness-accuracy trade-off with a parameter that relates to the principal angles between subspaces of the RKHS.
Finally, we apply our approach to obtain the first fair Gaussian process (FGP) prior for fair Bayesian learning, and show that it is competitive with, and in some cases outperforms, state-of-the-art methods on real data.




§ INTRODUCTION



Fairness has emerged as a key issue in machine learning as the learned models are increasingly used in areas such as hiring <cit.>, healthcare <cit.>, and criminal justice <cit.>.
In particular, the models' predictions should not lead to decisions that discriminate on the basis of a legally protected attribute, such as race or gender.
Among the proposals to address this issue, a growing body of work focuses on learning fair representations of data for downstream modeling <cit.>.
Most of these approaches are model-agnostic, which provides flexibility when working with the learned representations but comes at the cost of potentially suboptimal results in terms of both fairness and accuracy.

In this work, we present a novel approach for fair representation learning that takes into account the target hypothesis space of models that will be learned from the representation.
Specifically, we show how to leverage information about the reproducing kernel Hilbert space (RKHS) to learn a fair representation for kernel-based models with provable fairness and accuracy guarantees.

Our approach builds on the sufficient dimension reduction (SDR) framework <cit.>, which is used to compute a low-dimensional projection of the feature vector X that captures all information related to the response Y. Our key insight is that we can instead perform SDR with respect to the protected attributes S, and then take the orthogonal complement of the resulting projection to obtain a fair subspace of the RKHS that captures information in X unrelated to S. We show that functions in the fair subspace will be independent of S under mild conditions (<ref>), and we leverage this fact to prove that our approach can guarantee several popular definitions of fairness, namely statistical parity <cit.>, proxy nondiscrimination <cit.>, equality of opportunity <cit.>, and equalized odds <cit.>. Moreover, our approach is compatible with both classification and regression, as well as in settings where there are multiple, possibly continuous protected attributes.

Because a fair model might have a lower-than-desired accuracy in practice, we further generalize our approach to consider this trade-off. In particular, we apply SDR to compute a predictive subspace of the RKHS that captures sufficient information in the feature vector X related to the response Y.  We then define a third model subspace of the RKHS, which is bounded between the fair and predictive subspaces by a specified principal angle <cit.>. In contrast to recent regularization- and constraint-based trade-offs <cit.>, we provide precise characterizations of how the specified angle affects the fairness and accuracy of any model in this subspace.

Finally, we apply our method to obtain, to the best of our knowledge, the first fair Gaussian process (FGP) prior for constructing fair models in the Bayesian setting. Sample paths 
of the FGP will be functions in the chosen model subspace, and hence satisfy the specified fairness conditions. 
We identify the covariance kernel of the FGP that corresponds to the chosen model subspace by using the duality between a Gaussian process and its RKHS <cit.>. Our experiments 
show that the FGP achieves both rigorous fairness properties and improved accuracy compared to prior methods.



  
Outline
The remainder of the paper is organized as follows. In Section <ref>, we introduce an SDR-induced fair representation and show that it satisfies several existing fairness criteria. In Section <ref>, we present an algorithm for computing the proposed fair representation that attains a specified fairness-accuracy trade-off. We provide theoretical analysis that characterizes this trade-off as well as generalization performance. In Section <ref>, we demonstrate the application of the fair representation to GPs, and Section <ref> reports empirical results of the fair GP on several real-life datasets.




  
Additional Related Work


Much of the prior work on fair representation learning optimizes only for statistical parity <cit.> or individual fairness <cit.>. Learned Adversarially Fair and Transferable Representations (LAFTR) <cit.> provides additional support for equality of opportunity and equalized odds by taking into account the model loss while learning the fair representation. The authors prove bounds for statistical parity and equalized odds, but it should be noted that these bounds depend on the optimal adversary, which may not be available in non-convex settings. Our approach supports a broader set of fairness criteria (see <ref>), and we characterize the generalization performance in terms of both fairness and accuracy.

Provably fair kernel learning has been recently studied by <cit.> and <cit.>. Both approaches primarily target equality of opportunity in the setting of a single protected attribute. As previously noted, we address a more general setting. <cit.> also study fair kernel methods, but they only remove linear correlation between the input features X and the protected attribute S; by contrast, we can remove general statistical associations between X and S.

Bayesian formulations of fairness have been studied by <cit.> and <cit.>, who take into account the uncertainty in model parameters. <cit.> propose Bayesian versions of the balance <cit.> and calibration criteria <cit.> based on decision-theoretic risk formulations. <cit.> introduce a differential fairness criterion inspired by the definition of differential privacy in the setting of multiple protected attributes. Unlike these works, we do not propose new fairness criteria, instead focusing on several widely used criteria as described in <ref>.

Much previous research on learning rules with explicit fairness constraints or objectives <cit.> includes empirical studies on the fairness-accuracy trade-off, reporting that classifiers trained in this way outperform those trained on model-agnostic fair representations. Our proposed fair representations are not model-agnostic, and our performance is competitive if not better in some cases than that of those learning methods. <cit.> provide a theoretical analysis of the trade-off, providing information-theoretic bounds on accuracy in terms of the correlation between the target and protected attributes, as well as a regularization parameter analogous to the principal angle between subspaces used to set the trade-off in our work. In contrast, we provide insight into how the trade-off impacts generalization performance. 

Another approach to fair classification uses randomized post-processing of the classifier's predictions to ensure group fairness criteria. <cit.> propose such a procedure for ensuring equalized odds on binary classifiers. <cit.> argue that this approach can be suboptimal, and propose an alternative scheme: first learn a classifier with constraints to approximate fairness, and subsequently post-process its predictions to reduce discrimination. These approaches are orthogonal to fair representation learning, and do not consider either regression or multiple protected attributes.





§ USING SDR TO FORMULATE FAIRNESS




We begin by introducing some notation. We write  for the feature space and 𝒮 for the space of protected attributes. In addition, X ∈, S ∈𝒮, and Y ∈ denote the random variables for the feature vector, protected attributes, and label/response, respectively. We write accordingly {(x_i,s_i,y_i) ∈𝒳×𝒮×}_i=1^n for the training data of n examples.

The fair subspace is chosen as a vector space such that the projection of X onto the fair subspace does not contain information about S while retaining the residual information of X. We then use the projection as the fair representation. In the next subsection, we present an SDR-based method, i.e., <ref>, for finding a fair subspace. In <ref>, we show that the fair subspace based representation satisfies several existing fairness criteria.




 §.§ SDR-Induced Fair Representations



First consider the simple case where = ^p and 𝒮 =, including both the categorical and continuous cases. The goal is to obtain a basis of the fair subspace of dimension d ≤ p represented by the columns of C∈^p× d. A salient challenge in finding the fair subspace arises as the link between S and X is unknown. To address this issue, the key insight we use is that C can be obtained from an SDR subspace of X with respect to S. Next, we briefly recall the definition of the SDR subspace as well as its assumption <cit.>. Then, we provide the construction of C in <ref>.

An m-dimensional vector space is called an SDR subspace of X with respect to S if the projection of X onto the subspace captures the statistical dependency of S on X. The proposed SDR-induced fair representation relies on a kernel version of the following SDR assumption.


There exists a function f_S: ^m×^l → and a matrix B∈^p × m such that

    S = f_S(B^⊤ X,ϵ_S)   or  
        X  S |B^⊤ X,

where ϵ_S is a random variable independent of X.

The column span of B is known as the SDR subspace. It is worth pointing out that the condition (<ref>) is always satisfied since there is a one-to-one correspondence between B^⊤ X and X whenever B is square non-singular. The condition (<ref>) states that the projection B^⊤ X captures all information in X about S or more. The goal is thus to recover an SDR subspace with the lowest dimension. Under mild conditions on X, this recovery is guaranteed without requiring the knowledge of f_S <cit.>.

The SDR-induced fair representation is given by the projection onto the fair subspace X^'C^⊤ X, where C is defined as in <ref>. Note that the proposition does not make assumptions about the underlying link function f_S. Its proof adapts techniques used in  as well as the properties of elliptically contoured distributions, and is provided in <ref>. 



Suppose that |S| < ∞ and |X_i  S| < ∞ for i=1,⋯,p. Let the columns of C form a basis of the nullspace of (X) B. If condition (<ref>) holds and X follows an elliptically contoured distribution, then (C^⊤ X,S) = 0.


The class of elliptically contoured distributions contains the normal distribution. In the case where X^' and S are jointly multivariate normal, the lack of correlation guaranteed by <ref> implies X'  S. We remark that the multivariate normal requirement of the pair (X^',S) is reasonable for high-dimensional X, as most low-dimensional projections of high-dimensional data are nearly normal under mild conditions <cit.>. Moreover, the high-dimensional condition holds for kernel models where input data is mapped to potentially infinite-dimensional feature space.



  
Extensions to Multivariate S and RKHS
Our approach incorporates two generalizations of the linear SDR condition (<ref>). First, the condition (<ref>) does not apply to the setting with multiple protected attributes. This is handled by replacing (<ref>) with the joint conditions S_i = f_S_i(B^⊤ X,ϵ_S_i) for each protected attribute S_i <cit.>. Second, S can depend on nonlinear structures of X, and hence the linear condition (<ref>) may not yield a low-rank B. In that case, the resulting fair subspace C^⊤ X may be too low-dimensional for accurately predicting Y. To address this issue, we use the RKHS counterpart of condition (<ref>). 

Denote by ℋ_κ an RKHS of functions f: 𝒳↦ generated by kernel κ(·,·). In the RKHS setting with training points x_1, …, x_n, X is replaced by the feature function κ(·,X), and B_i will instead be functions in ℋ_κ expressed as B_i = ∑_j=1^n W_jiκ(·,x_j) for some W∈^n× m by the representer theorem <cit.>. Thus, condition (<ref>) in the RKHS setting reads

    S = f_S(κ(X,X)W_1,⋯,κ(X,X)W_m, ϵ_S)

with κ(X,X) (κ(X,x_1),…,κ(X,x_n)). Similarly, we also adapt <ref> to the RKHS setting with C_i replaced by ∑_j=1^n Q_jiκ(·,x_j) for some Q∈^n× r. This yields the corresponding fair subspace 
    {∑_j=1^n Q_j1κ(·,x_j),…,∑_j=1^n Q_jrκ(·,x_j)},

and the fair representation X^' = κ(X,X)Q of X. 




  
Kernel Misspecification
In the RKHS setting, <ref> states that the fair representation X^' does not contain information about S. However, this does not necessarily imply that X^' is predictive in terms of Y. For example, one can trivially satisfy (<ref>) by letting W be the identity matrix. Then, the corresponding fair representation  will be the constant 0, which is trivially independent of X. Thus, in order for the fair representation to be predictive, κ(·,·) and W should be chosen such that (<ref>) holds for a small m.

We note that a misspecified kernel affects the predictive power, but not fairness, of the fair representation as long as (<ref>) holds. Kernel misspecification can be detected in practice because the resulting model based on X^' would give a large prediction error. The problem of finding appropriate W and m will be discussed in <ref>.



 §.§ Fairness as Statistical Independence



In this section, we formulate several common fairness criteria in terms of the statistical independence X^' S, where X^' is the projection of X onto the fair subspace described in <ref>. Let h(·) denote the model and let = h(X^') be the model output. This paper focuses on the following fairness criteria:



  * Statistical parity (SP), also called demographic parity, is one of the simplest notions of fairness and requires model predictions to be independent of the protected attributes, i.e., S. This follows from X'  S since  is a function of X'.

  * Proxy nondiscrimination <cit.> goes further than statistical parity in that it considers all components of the model rather than just its output. For example, a component c of a linear model h(X) = β^⊤ X has the output _c∑_i=1^p c_i β_i X_i for c_i ∈[0,1].
The strictest version of proxy nondiscrimination requires _c S for all component c.
This follows from X'  S since _c is a function of X'.

  * Equalized Odds, Equality of Opportunity: In the binary classification setting where Y ∈, the equalized odds (EO) condition <cit.> is defined as the conditional independence S | Y. Compared to statistical parity, one advantage of equalized odds is that it admits the perfect model = Y. Equality of opportunity (EOP) <cit.> is a relaxation of equalized odds, requiring only that S | Y=1. To attain EOP, we can apply (<ref>) to only the individuals with Y=1, and use the resulting X^' as input features. Similarly, we can achieve EO by restricting (<ref>) to individuals with Y=1 to obtain B_Y=1 and to individuals with Y=0 to obtain B_Y=0. Then, we compute X^' by taking the union of SDR subspaces [B_Y=1B_Y=0] as the B in <ref>.


We conclude the discussion by pointing out that our approach does not support accuracy parity <cit.>, which requires ( = Y)  S, or the calibration condition Y  S | <cit.>. This is because, without further assumptions on the model, a fair representation alone cannot preclude a constant model. If  is a constant, to satisfy accuracy parity and calibration we would need some independence condition between Y and S, which does not in general hold. Thus, it could be interesting future work to further identify additional conditions on the model needed to support the other fairness definitions.




§ COMPUTING THE HYPOTHESIS SPACE




We now describe how to compute the fair subspace as well as the model subspace in which every function attains a desired fairness-accuracy trade-off. The construction is presented analytically in (<ref>), and we provide generalization bounds in <ref> and (<ref>) for the deviation between an optimal fair or predictive model in the RKHS and the model obtained from the model subspace on unseen data. The pseudo-code and all proofs are provided in the appendix.



  
Problem Setup
Recall that a kernel-based learning problem is typically formulated as the following optimization under Tikhonov regularization <cit.>:

    min_f ∈ℋ_κ L(f,{(x_i,y_i)}_i=1^n) + R(f_ℋ_κ),

where L is a convex loss, R is a monotonically increasing regularization function, and {(x_i, y_i)}_i=1^n is the set of training points. While ℋ_κ is infinite dimensional, the well-known representer theorem <cit.> states that the solution f_⋆ for (<ref>) is in a data-dependent finite-dimensional subspace of ℋ_κ:

    ℋ_κ,n{∑_i=1^n a_i κ(·,x_i)  | {a_i}_i=1^n ⊂}.


Our goal is to obtain a subset of functions in ℋ_κ,n that meets the fairness criteria described in <ref>. This subset will be the fair subspace (<ref>) of ℋ_κ,n.



 §.§ Learning the Fair and Predictive Subspaces



Both the predictive subspace 𝒢 and the fair subspace ℱ of ℋ_κ can be estimated using a standard SDR estimator for the RKHS. Specifically, the predictive subspace 𝒢 is given by the SDR subspace with respect to Y. Similarly, the fair subspace ℱ given by (<ref>) is obtained by first computing the SDR subspace with respect to S and then using <ref> to obtain Q.




Since 𝒢 and ℱ are subspaces of ℋ_κ,n, we write 𝒢 = {ϕA_1,⋯,ϕA_d} and ℱ = {ϕQ_1,⋯,ϕQ_r}  with r = n - m and ϕ(κ(·,x_1),⋯,κ(·,x_n)).  Our goal is thus to compute A and Q, the latter of which requires the SDR subspace specified by W. Next we briefly review the estimation of A; W is obtained similarly with respect to S. In the following, we assume without loss of generality that d + m ≤ n.



  
Estimating the SDR Subspace
The estimate of A is given by the eigenvectors of the following generalized eigenvalue decomposition <cit.>:

    Γ_nKA_i = τ_i (Δ + n ηI_n) A_i,

where Γ_n I_n - 1_n1_n^⊤/n, K represents the kernel matrix with K_ijκ(x_i,x_j), η > 0 is a regularization parameter, and Δ is a matrix to be discussed shortly. For simplicity, (<ref>) assumes that the data tuples (x_i,s_i,y_i) are sorted by y_i, either in ascending or descending order. To obtain Δ, one first partitions the data into slices {(x_1,s_1,y_1),⋯,(x_n_1,s_n_1,y_n_1)}, {(x_n_1 + 1,s_n_1+1,y_n_1+1),⋯,(x_n_1+n_2,s_n_1+n_2,y_n_1+n_2)}, and so forth, where n_i denotes the size of the i-th slice. Then, set Δ = diag(Γ_n_i)K where diag(Γ_n_i) is the block-diagonal matrix with diagonal blocks Γ_n_i. The overall computational complexity for estimating A is O(n^2 d).

Another relevant problem is to decide the dimensions of 𝒢 and ℱ, i.e., the values of m and d. When y_i (resp. the entries of s_i) is categorical with N categories, at most N-1 linearly independent directions are needed. This gives an upper bound for d (resp. m). In both the categorical and continuous cases, one can use the methods proposed by <cit.> and <cit.>. For example, <cit.> introduced an eigenvalue-based sequential test for the true SDR subspace dimension d_⋆. Based on the test, <cit.> provided a lower bound for the eigenvalue τ_d_⋆. We use the lower bound to select the SDR dimension d. In particular, we choose the largest dimension d such that τ_d satisfies the lower bound.



  
Estimating the Fair Subspace
Given W, we invoke <ref> to compute the fair subspace ℱ which is described by Q. In the RKHS setting, the covariance matrix (X) in <ref> is replaced by the covariance operator (κ(·,X)) on ℋ_κ. Let ⊗ denote the tensor product and let μ_X 𝔼_X [κ(·,X)], the empirical estimator of (κ(·,X)), be written
𝔼_X [(κ(·,X) - μ_X) ⊗(κ(·,X) - μ_X)] ≈1/nϕΓ_n ⊗ϕΓ_n.
<ref> states that for all i ∈[m] and j ∈[r], Q satisfies

    <ϕW_i, (1/nϕΓ_n ⊗ϕΓ_n) ϕQ_j>
    = 1/nW_i^⊤KΓ_n KQ_j
    = 0.

Thus, the columns of Q are given by a basis of the nullspace of W^⊤KΓ_n K.

A subtlety in estimating the fair subspace for EO and EOP, as described in <ref>, is that only a subset of the training data with certain value of Y is used. In this case, W and Q both will have a reduced number of rows. This is not an issue as the fair subspace is still a subspace of ℋ_κ,n, and the pseudo-code in <ref> shows how to handle this case.




 §.§ Controlling the Trade-off between Accuracy and Fairness


We now describe a fairness-accuracy trade-off specified by the maximum principal angle between two subspaces of ℋ_κ,n. Recall that the i-th principal angle θ_i between ℱ and 𝒢 is defined as <cit.>:

    cosθ_i max_f_i∈ℱ, f_i≤ 1
    ∀ j<i: <f_i,f_j> = 0max_g_i∈𝒢, g_i≤ 1
    ∀ j<i: <g_i,g_j> = 0<f_i,g_i>.

If the largest principal angle max_i θ_i equals 0, ℱ and 𝒢 coincide. Based on this idea, we consider constructing the hypothesis class of the model as a subspace ℳ of ℋ_κ,n such that the largest principal angle between ℳ and ℱ is small. Intuitively, functions in ℳ would then be approximately fair.

More formally, our goal is to enforce the distance between ℳ and ℱ as measured by the largest principal angle to be no greater than a given threshold. This is equivalent to requiring the cosine of the largest principal angle to be no less than a parameter 0 ≤ϵ≤ 1 specified by the user. Recall that the cosines of principal angles are the singular values of the projection of an orthonormal basis of one subspace onto an orthonormal basis of the other <cit.>. A direct method for finding an ℳ that satisfies the principal angle constraint is by reversing the well-known Wedin's bound for the perturbation of singular subspaces <cit.>. However, a limitation that inherits from the bound is the dependency on the eigengap. Therefore, we instead consider a simple construction of ℳ given by:

    ℳ{a_i e_i + b_i u_i}_i=1^d

for some orthonormal set of functions {e_i}_i=1^r in ℱ and orthonormal set of functions {u_j}_j=1^d in 𝒢. With careful choices of a_i, b_j, as well as the orthonormal sets, we show that the above hypothesis class satisfies the principal angle constraint as well as several desirable properties. 

First, we compute an orthonormal basis for ℱ and 𝒢 by performing the eigenvalue decompositions
Q^⊤KQM = MΛ and A^⊤KAT = TΩ. The columns of M and T are eigenvectors, while Λ and Ω are diagonal containing the corresponding eigenvalues, i.e., λ_i = Λ_ii and ω_i Ω_ii. It is easy to see that ℱ and 𝒢 have the following orthonormal bases:

    ℱ{λ_i^-1/2ϕQM_i}_i=1^r,   𝒢{ω_i^-1/2ϕAT_i}_i=1^d.



Using the orthonormal bases (<ref>), <ref> gives the hypothesis space ℳ for the model which is bounded between the fair RKHS ℱ and the predictive RKHS 𝒢 through ϵ specifying the cosine of the largest principal angle between ℳ and ℱ.


Let Λ^-1/2M^⊤Q^⊤KATΩ^-1/2 = UΣV^⊤ be the thin singular value decomposition with singular values σ_i Σ_ii, and let the hypothesis class of the model be

    ℳ = {ϕ[
         (γ_i - ρ_i σ_i) QMΛ^-1/2U_i +
         ρ_i ATΩ^-1/2V_i
         ]
         }_i=1^d

with
     γ_i max{σ_i,ϵ},
     and ρ_i √(1-γ_i^2/1-σ_i^2) if σ_i < 1 and ρ_i  0 if σ_i = 1 for i=1,2,⋯,d.
Denote by σ_minmin_i σ_i and let 𝒫_ℱ, 𝒫_𝒢, and 𝒫_ℳ be the orthogonal projection operators onto the fair RKHS ℱ, predictive RKHS 𝒢, and the model RKHS ℳ, respectively. Then, the following operator norms hold:

    𝒫_ℱ - 𝒫_ℳ   = √(1 - max{ϵ^2,σ_min^2})
    𝒫_𝒢 - 𝒫_ℳ   = max{0, ϵ√(1-σ_min^2) - σ_min√(1-ϵ^2)}.



For the case where ϵ = 1, the basis of (<ref>) are linear combinations of the orthonormal basis of ℱ in (<ref>), and hence ℳ⊂ℱ. Additionally, it can be verified that 𝒫_ℱ - 𝒫_ℳ = 0 from (<ref>), and (<ref>) becomes 𝒫_𝒢 - 𝒫_ℳ = √(1-σ_min^2) which is the sine of the largest principal angle between ℱ and 𝒢 as desired. Similarly, if we set ϵ=0 we get ℳ = 𝒢.

The key utility of <ref> involves bounding the difference between the model obtained using ℳ and an optimal fair (or predictive) model. In particular,
<ref> shows that ℳ contains a function which approximates the optimal fair model f_fair∈ℋ_κ. Let δ_x f  f(x) be the evaluation functional.
Then, for any x∈𝒳:

    | (𝒫_ℳ f_fair)(x) - f_fair(x)|
       = δ_x(𝒫_ℳ f_fair) - δ_x f_fair
       ≤δ_x𝒫_ℳ f_fair - f_fair
       = δ_x𝒫_ℳ f_fair - 𝒫_ℱ f_fair + 𝒫_ℱ f_fair - f_fair
       ≤δ_x(
         𝒫_ℳ - 𝒫_ℱf_fair + 𝒫_ℱ f_fair - f_fair).

Here, δ_x and f_fair are bounded from the property of the RKHS, and the last norm in (<ref>) converges in probability to zero at rate O_P(n^-1/4) by the consistency of ℱ and 𝒢 <cit.>. Together with (<ref>), (<ref>) sheds light on the impact of ϵ on the generalization of the fairness criteria; similar arguments can be made for an optimal predictive model.




§ APPLICATION TO FAIR GPS




In this section, we demonstrate the utility of our approach by constructing a fair Gaussian process (FGP) which can be used to develop a class of fair models under the Bayesian framework <cit.>. In particular, the FGP specifies a prior over functions in ℳ that satisfy the fairness criteria discussed in <ref>.

Recall that a GP {f(x): x ∈𝒳} is specified by a mean function and a covariance function. The covariance function characterizes the class of functions, i.e., the curves of f(·), the GP can realize. The FGP is a GP equipped with a covariance function that ensures that any sample path f(x) is fair. To obtain the covariance function, we use the integral representation of GPs <cit.>:

    f(x) = ∫_𝒳κ(x,z) ν(z) d μ(z),

where ν: 𝒳×Ω↦ℝ is another GP on a probability space (Ω,ℱ,P) and μ is the measure on 𝒳. Clearly, f(·) given by (<ref>) is a GP. Without loss of generality, we assume the GP has mean zero, then the covariance function (f(x), f(z)) is written 

    ∫_𝒳∫_𝒳κ_ν(s,t) κ(x,s) κ(z,t) d μ(s) d μ(t),

where κ_ν(·,·) is the covariance function of the GP ν(·). A key property of (<ref>) we use to construct the FGP is that functions in the form of (<ref>) are contained in the RKHS generated by kernel κ(·,·) <cit.>. By replacing κ(·,·) in (<ref>) with the reproducing kernel of ℳ, we obtain the desired FGP which inherits the fairness as well as accuracy guarantees of ℳ. It is worth noting that the representation ℳ in (<ref>) can be computed independent of data. This can be done using a likelihood for SDR subspaces <cit.>.

In practice, we use a sample version of the FGP for improved computational efficiency. Consider the sample average of (<ref>) given by

    f_n(x) 1/n∑_i=1^n ν(x_i) κ_ℳ(x,x_i),

which converges in probability to (<ref>) at rate O_p(n^-1/2) by the central limit theorem for Hilbert spaces <cit.>. The covariance function of the sample FGP has two parameters, namely the covariance function κ_ν(·,·) of ν(·) and the reproducing kernel κ_ℳ(·,·) of the RKHS ℳ. 

Finally, we give a reparameterization to simplify the sample FGP. Let ϕE_i represent the i-th basis function of (<ref>), and denote by Π(z) (κ(z,X) - 11_n^⊤K/n)E, where K is the kernel matrix of κ as defined in (<ref>). The sample FGP can be rewritten as

    f_n(·) ∼𝒢 𝒫(0,
    Π(·)ΛΠ(·)^⊤),

where the covariance function has only a single hyperparameter, a positive definite matrix Λ. Now, it is straightforward to choose  Λ as to maximizes the marginal likelihood while training the FGP (<ref>).




§ EXPERIMENTS





We present experiments on five real datasets to: (1) demonstrate the efficacy of our approach in mitigating discrimination while maintaining prediction accuracy; (2) characterize the empirical behavior of the algorithms developed in <ref>; and (3) highlight the ability of our method to handle multiple, possibly continuous, protected attributes.

We adapt the experimental setup, including the processed datasets, code, as well as configurations, used in prior work <cit.> to compare the proposed FGP[The datasets and our Matlab implementation of the FGP are available at <https://github.com/ZilongTan/fgp>.] against several approaches: a standard GP trained on an adversarially-fair representation <cit.> (LAFTR-GP), fairness-constrained ERM <cit.>, both the linear (Linear-FERM) and nonlinear (FERM) variants, and non-convex fair regression <cit.> (NCFR) which supports settings with multiple protected attributes. We also report the results of a standard GP with no fairness objective.

We measure fairness conditions empirically using the absolute correlation coefficient, as it can be generalized to the regression setting. Specifically, we compute the population |(,S)| as the SP risk score, |(,S)| on individuals with Y=1 for EOP, and EO is given by the maximum absolute correlation on individuals with Y=1 and Y=0. All scores are calculated on holdout test data. For the experiments, we do not consider proxy non-discrimination as it relies on certain model structures, and is not comparable to our chosen baselines. Finally, for the baseline methods we use the code published online by their respective authors, and for the GPs we use a linear mean and a radial basis covariance.



 §.§ Fair Classification


 


 

A primary goal of our approach is to enforce a specified fairness criterion with minimal loss in accuracy. We evaluate how each of the fairness conditions are satisfied empirically on two standard datasets: the Adult income dataset <cit.>, and the Compas recidivism risk score data <cit.>. We illustrate how the fairness score and prediction error react to various choices of the fairness-accuracy tradeoff ϵ. For both datasets, we use gender as the single protected attribute.

<ref> compares different methods for achieving each fairness goal (column). First, observe that Linear-FERM and FERM do not meet SP on both datasets. This is because Linear-FERM and FERM only target EOP. Also note that the accuracy of our approach tends to converge to that of standard GP, which is expected as setting the trade-off ϵ = 0 in (<ref>) yields this model. Some baselines attain the the best fairness, e.g., LAFTR-GP delivers the lowest EO on Compas, at the cost of accuracy. However, overall our approach generally achieves greater accuracy for a given level of fairness.



 §.§ Fair Regression with Multiple Protected Attributes


We consider a regression setting with two protected attributes. For this evaluation, we use three real datasets with continuous target values, namely the UCI Communities and Crime <cit.>, the National Longitudinal Survey of Youth (NLSY) <cit.>
and the Law School Admissions Council <cit.> datasets.
The protected attribute pairs (s_1,s_2) used for these datasets are respectively (race, origin), (gender, age), and (race, age).

Note that NCFR is the only baseline that handles multiple protected attributes. In addition, EO and EOP are defined in the context of binary classification, so they are not suitable in this regression experiment. We use the root mean squared error (RMSE) to measure the prediction error.

<ref> depicts the prediction error as well as SP for each protected attribute. As stricter fairness conditions are enforced, the RMSE climbs. Across these datasets, our approach achieves consistently improved accuracy. Interestingly, the curves correspond to our approach are generally steeper than the curves of NCFR, suggesting more effective fairness-accuracy trade-offs.









§ CONCLUSIONS


We have presented a novel and theoretically principled method for learning fair representations for kernel models, which also enables users to systemically navigate the fairness-accuracy trade-off.  We apply our approach to obtain a fair Gaussian process, demonstrating competitive empirical performance on several datasets relative to state-of-the-art methods. Our work hinges on the idea of learning a model-aware representation, along with the key insight that several popular fairness notations can be reformulated as sufficient dimension reduction (SDR) problems. Future work involves supporting additional fairness notions like calibration and accuracy parity through additional model assumptions, developing more scalable algorithms using randomized approximations, and generalizing the strategy of learning model-aware representations to other model classes.



§ ACKNOWLEDGEMENTS


This work was supported in part by DARPA FA875017C0141, the National Science Foundation grants IIS1705121, IIS1838017, CNS1704845, an Okawa Grant, a Google Faculty Award, an Amazon Web Services Award, a JP Morgan A.I. Research Faculty Award, and a Carnegie Bosch Institute Research Award. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of DARPA, the National Science Foundation, or any other funding agency.



§ APPENDIX




 §.§ Proofs




First, we use a property of elliptically contoured distributions <cit.> to obtain

    [C^⊤ X|B^⊤ X] 
    	   = a + (C^⊤ X,B^⊤ X)^-1(B^⊤ X)[B^⊤ X - (B^⊤ X)]
       = a + C^⊤(X) B(B^⊤(X) B)^-1B^⊤(X -  X)

for some constant a. From condition (<ref>) and the law of total covariance, 
    (S,C^⊤ X) 
           = (f_S(B^⊤ X, ϵ_S),C^⊤ X) 
       = 𝔼[(f_S(B^⊤ X, ϵ_S),C^⊤ X|B^⊤ X, ϵ_S)] +
       =[𝔼(f_S(B^⊤ X, ϵ_S)|B^⊤ X, ϵ_S),𝔼(C^⊤ X|B^⊤ X, ϵ_S)]
       = (f_S(B^⊤ X, ϵ_S), 𝔼(C^⊤ X|B^⊤ X))
       = (f_S(B^⊤ X, ϵ_S),X)
        B(B^⊤(X) B)^-1B^⊤(X) C.

Thus, we have (S,C^⊤ X) = 0 if B^⊤(X) C = 0 which implies that the columns of C lie in the nullspace of (X) B.




We first show that the basis (<ref>) of the classifier hypothesis RKHS is orthonormal, and then compute the canonical angles using the basis (<ref>) and an orthonormal basis of ℱ. Denote by ξ_i (γ_i - ρ_i σ_i) QMΛ^-1/2U_i + ρ_i ATΩ^-1/2V_i the i-th basis function in (<ref>), we have

    <ξ_i, ξ_j>
            = (γ_i - ρ_i σ_i)(γ_j - ρ_j σ_j) U_i^⊤U_j
         + ρ_i ρ_j V_i^⊤V_j + 2ρ_iσ_i(γ_i - ρ_i σ_i) 1_i=j
       = [(γ_i - ρ_i σ_i)^2 + ρ_i^2 + 2ρ_iσ_i(γ_i - ρ_i σ_i)] 1_i=j
       = 1_i=j,

where the first equality follows from the orthonormal basis (<ref>). This shows that (<ref>) is an orthonormal basis. Using the orthonormal basis {ψ_i ϕQMΛ_i^-1/2}_i=1^r of ℱ, we can use the SVD to compute the canonical angles (see e.g., Algorithm 6.4.3 in <cit.>) as

    [ξ_1,⋯,ξ_d]^⊤[ψ_1,⋯,ψ_r] 
        = diag(γ_i - ρ_i σ_i) U^⊤
         + diag(ρ_i) ΣU^⊤
        = I_d diag(γ_i) U^⊤.

Here, diag(d_i) denotes the diagonal matrix with diagonal elements d_i. Note that the last term in (<ref>) is the (thin) SVD, and the singular values γ_i are the canonical angles between ℳ and ℱ. Finally, we relate the canonical angles to the operator norm in (<ref>). Recall that the orthogonal projector can be expressed as the tensor product 𝒫_ℱ = ∑_i=1^r ψ_i ⊗ψ_i, and 𝒫_ℱ h = ∑_i=1^r <h,ψ_i> ψ_i. We have

    𝒫_ℱ - 𝒫_ℳ   = (𝒫_ℱ + 𝒫_ℱ)(𝒫_ℱ - 𝒫_ℳ)(𝒫_ℳ + 𝒫_ℳ)
       = 𝒫_ℱ𝒫_ℳ - 𝒫_ℱ𝒫_ℳ
       = sup_h∈ℋ_κ,nh≤ 1(𝒫_ℱ𝒫_ℳ h  + 𝒫_ℱ𝒫_ℳ h),

where ℱ and ℳ represent respectively the orthogonal complements of ℱ and ℳ. It can be shown that 𝒫_ℱ𝒫_ℳ and 𝒫_ℱ𝒫_ℳ have the same nonzero singular values which are the sines of the principal angles between ℱ and ℳ (see e.g., p.249 of ). From (<ref>), these principal angles are arccos(γ_i). Thus, we obtain 𝒫_ℱ - 𝒫_ℳ = √(1-min_iγ_i^2). To obtain (<ref>), one can simply apply the trigonometric identity of sines yielding 

    𝒫_𝒢 - 𝒫_ℳ
        = γ_min√(1 - σ_min^2) - σ_min√(1-γ_min^2)
        = max{0, ϵ√(1-σ_min^2) - σ_min√(1-ϵ^2)},

where we denote by γ_minmin_i γ_i.





 §.§ Implementation



<ref> gives the Matlab-style pseudo-code for our approach which can handle multiple protected attributes. This algorithm use the SDR procedure described in <ref> to compute the desired model representation with a specified trade-off ϵ.






plainnat


