Training individually fair machine learning algorithms via distributionally robust optimization

Patent metadata

Field	Value
Publication number	US-2022318639-A1
Application number	US-202117213167-A
Country	US
Kind code	A1
Filing date	Mar 25, 2021
Priority date	Mar 25, 2021
Publication date	Oct 6, 2022
Grant date	—

Abstract

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.

First claim

What is claimed is:

1 . A method comprising:
obtaining a first data set, a second data set, and a machine learning model; constructing a sensitive subspace of the first data set that defines a fair metric for distance among elements of the first data set; fairly training the machine learning model on the first data set using a distributionally robust optimization approach based on the fair metric; producing an individually fair set of labels by applying the fairly trained machine learning model to the second data set; and allocating a resource according to the individually fair set of labels.

2 . The method of claim 1 , wherein fairly training the machine learning model comprises:
defining a cost matrix C for the model; entering an iterative loop; in the loop:
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;
assigning a distribution for inputs and outputs of the model, based on the solution to the optimization problem;
fitting a base learner to pseudo-residuals of a loss function of the model, based on the distribution for inputs and outputs of the model; and
updating a candidate classifier of the model, based on the loss function;
repeating the loop until a final iteration produces a finally updated candidate nclassifier; and returning the finally updated candidate classifier as the fairly trained model.

3 . The 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 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 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 fair metric.

6 . The 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, being an 1-Wasserstein distance between distributions Q on and P on 0 , ε being a budget for distance.

7 . The method of claim 1 , wherein fairly training the machine learning model on the first data set comprises using a regularization approach based on the fair metric.

8 . The 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′ of x to each x t ′ of x′, within constraints λ such that distance between x and x′ is minimized;
updating the constraints λ using a gradient descent technique, setting λ no less than zero; and
updating weights θ of the machine learning model using a gradient descent technique;
exiting the loop when the updated weights θ converge to produce the fairly trained machine learning model; and returning the fully trained machine learning model.

9 . The method of claim 8 , wherein the fair regularizer R(h) is defined as

R
⁡
(
h
)

=
Δ

{

sup

Π
∈

Δ
⁡
(

𝒳
×
𝒳

)

𝔼
Π

[

dy
⁡
(

h
⁡
(
x
)

,

h
⁡
(

x
′

)

)

]

subject
⁢

to

Assignees

• IBM
• Univ Michigan

Inventors

• Upadhyay Sohini
• Yurochkin Mikhail
• Mukherjee Debarghya
• Sun Yuekai
• Bower Amanda Ruth Garcia
• Eftekhari Seyed Hamid
• Vargo Alexander
• Zhang Fan

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06F18/214

  Generating training patterns; Bootstrap methods, e.g. bagging or boosting · CPC title

• G06N3/047

  Probabilistic or stochastic networks · CPC title

• G06F18/22

  Matching criteria, e.g. proximity measures · CPC title

• G06N5/01 Primary

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title