Training individually fair machine learning algorithms via distributionally robust optimization
Obtain a first data set, a second data set, and a machine learning model. Construct a sensitive subspace of the first data set that defines a fair metric for distance among elements of the first data set. Fairly train the machine learning model on the first data set using a distributionally robust optimization approach based on the fair metric. Produce an individually fair set of labels by applying the fairly trained machine learning model to the second data set. Allocate a resource according to the individually fair set of labels.
1 . A computer-implemented method comprising:
obtaining a first data set, a second data set, and a machine learning model;
constructing a subspace of the first data set that defines a metric for distance among elements of the first data set, wherein the metric ignores protected attributes in measuring a difference between samples to allow for free movement in a corresponding space;
training the machine learning model on the first data set using a distributionally robust optimization approach based on the metric, wherein the distributionally robust optimization approach includes a regularization approach based on the metric and
wherein the training of the machine learning model comprises defining an iteration of a loss matrix R, finding a solution to an optimization problem by executing a linear program on the iteration of the loss matrix, and assigning a distribution for inputs and outputs of the machine learning model, based on the solution to the optimization problem;
producing an individually fair set of labels by applying the trained machine learning model to the second data set; and
allocating a resource according to the individually fair set of labels.
2 . The computer-implemented method of claim 1 , wherein training of the machine learning model further comprises:
defining a cost matrix C for the machine learning model;
entering an iterative loop;
in the loop:
fitting a base learner to pseudo-residuals of a loss function of the machine learning model, based on the distribution for inputs and outputs of the machine learning model; and
updating a candidate classifier of the machine learning model, based on the loss function;
repeating the loop until a final iteration produces a finally updated candidate classifier; and
returning the finally updated candidate classifier as the trained model.
3 . The computer-implemented method of claim 2 , wherein updating the candidate classifier comprises applying a gradient boosted descent algorithm to a decision tree of the model.
4 . The computer-implemented method of claim 2 , wherein the loss matrix R is defined as
R i,j = ( h ,( x i ,y j )),
being the loss, h being the score of input x i , y j being the output of the machine learning model for input x j .
5 . The computer-implemented method of claim 2 , wherein a cost function c of the cost matrix is defined as
c (( x 1 ,y 1 ),( x 2 ,y 2 ))= d x 2 ( x 1 ,x 2 )+∞·1 {y 1 ≠y 2 } .
x being inputs to the machine learning model, y being outputs from the machine learning model, d x 2 being the square of a distance function on the metric.
6 . The computer-implemented method of claim 2 , wherein the robust loss function L(f) of the model is defined as
L
(
f
)
=
sup
Q
:
(
Q
,
P
n
)
≤
ε
𝔼
Q
[
(
f
,
ℨ
)
]
,
Q being an expected value on the distribution Q of counterfactual inputs that are as close as possible to the actual inputs P while having different scores, W being an I-Wasserstein distance between distributions Q on and P on 0 , ϵ being a budget for distance.
7 . A computer-implemented method comprising:
obtaining a first data set, a second data set, and a machine learning model;
constructing a subspace of the first data set that defines a metric for distance among elements of the first data set, wherein the metric ignores protected attributes in measuring a difference between samples to allow for free movement in a corresponding space;
training the machine learning model on the first data set using a distributionally robust optimization approach based on the metric, wherein the distributionally robust optimization approach includes a regularization approach based on the metric, wherein the regularization approach comprises updating constraints λ using a first gradient descent technique, setting λ no less than zero and updating weights θ of the machine learning model using a second gradient descent technique;
producing an individually fair set of labels by applying the trained machine learning model to the second data set; and
allocating a resource according to the individually fair set of labels.
8 . The computer-implemented method of claim 7 , wherein the regularization approach comprises:
defining a fair regularizer for the machine learning model as the solution of an optimization problem;
entering a conditional loop that continues until convergence of a stochastic algorithm for solving the optimization problem;
in the loop:
sampling a mini-batch from the first data set x and from a corresponding first label set;
generating counterfactual data x′ by maximizing a difference in score from each x t of x to each x t ′ of x □ ′, within the constraints λ such that distance between x and x′ is minimized;
exiting the loop when the updated weights θ converge to produce the trained machine learning model; and
returning the fully trained machine learning model, wherein the updating the constraints λ and the updating the weights θ are performed within the loop.
9 . The computer-implemented method of claim 8 , wherein the fair regularizer R(h) is defined as
R
(
h
)
=
△
{
sup
Π
∈
Δ
(
𝒳
×
𝒳
)
𝔼
Π
[
dy
(
h
(
x
)
,
h
(
x
′
)
)
]
subject
to
𝔼
Π
[
dx
(
x
,
x
′
)
]
≤
ε
Π
(
·
,
𝒳
)
=
P
X
}
,
h(X) being the score of inputs x, Π being a solution to an optimization problem that produces a marginal distribution P of inputs x such that expected value Π of difference in outputs is maximized on data distribution Π, ϵ being a budget for distance.
10 . The computer-implemented method of claim 8 , wherein the dual of the fair regularizer R(h) is defined as
R ( h )=inf λ≥0 {λϵ+ P x [r λ ( h,x )]},
r λ ( h,x ) sup x′∈z,22 {dy ( h ( x ), h ( x ′))−λ dx ( x,x ′)},
P x being an expected value on distribution P x , d y being distance between scores for inputs x, x′.
11 . The computer-implemented method of claim 10 , wherein the constraints λ are updated based on the gradient of the dual of the fair regularizer with respect to λ.
12 . The computer-implemented method of claim 10 , wherein the weights θ are updated based on the gradient of the loss function plus the gradient of the dual of the fair regularizer with respect to θ.
13 . A computer-implemented method comprising:
obtaining a list of objects;
obtaining a machine learning model that is partly trained for ranking the list of objects in response to a given query;
constructing a subspace of the list of objects that defines a metric for distance among the objects, wherein the metric ignores protected attributes in measuring a difference between samples to allow for free movement in a corresponding space;
obtaining a set of queries on the list of objects;
defining a regularizer for the machine learning model as the solution of an optimization problem;
solving the optimization problem according to a stochastic algorithm;
producing an individually fair ranking of the list of objects, using the trained machine learning model in response to a received query; and
allocating resources according to the individually fair ranking, wherein the stochastic algorithm comprises entering a conditional loop that continues until convergence of the stochastic algorithm for solving the optimization problem;
in the loop:
sampling a mini-batch from the set of queries q;
generating a set of counterfactual queries q t ′ by minimizing distance on the metric between each q t of the set of queries and each q t ′ of the set of counterfactual queries, while maximizing difference between a score of each item in q t and a corresponding score of each item in q t ′;
updating constraints λ on the distance between q t and q t ′ according to a first gradient descent technique on the gradient of the dual of the regularizer; and
updating weights θ of the machine learning model according to a second gradient descent technique on the sum of the loss function and the gradient of the dual of the regularizer; and
exiting the loop when the updated weights θ converge to produce a trained machine learning model for ranking a list.
14 . The computer-implemented method of claim 13 , wherein the dual of the regularizer R(h) is
(π)=inf λ≥0 {λϵ+ q˜Q [r λ (π, q )]}, where
r λ (π, q )=sup q′∈ { (π(⋅| q ),π(⋅| q ′))−λ ( q,q ′)},
wherein q is an expected value on distribution q and d is a metric on query distribution .