Disparate Conditional Prediction in Multiclass Classifiers
Authors: Sivan Sabato
Eran Treister
Elad Yom-Tov
Venue: ICML 2025 poster (2025)
Keywords: fairness
optimization
multiclass
auditing
Primary area: social_aspects->fairness
TL;DR: We propose new optimization procedures for auditing the deviation from equalized odds fairness in multiclass classifiers.

Abstract: We propose methods for auditing multiclass classifiers for fairness under multiclass equalized odds, by estimating the deviation from equalized odds when the classifier is not completely fair. We generalize to multiclass classifiers the measure of Disparate Conditional Prediction (DCP), originally suggested by Sabato & Yom-Tov (2020) for binary classifiers. DCP is defined as the fraction of the population for which the classifier predicts with conditional prediction probabilities that differ from the closest common baseline. We provide new local-optimization methods for estimating the multiclass DCP under two different regimes, one in which the conditional confusion matrices for each protected sub-population are known, and one in which these cannot be estimated, for instance, because the classifier is inaccessible or
because good-quality individual-level data is not available. These methods can be used to detect classifiers that likely treat a significant fraction of the population unfairly. Experiments demonstrate the accuracy of the methods. The code for the experiments is provided as supplementary material.

Disparate Conditional Prediction in Multiclass Classifiers
Sivan Sabato 12
Eran Treister?
Elad Yom-Tov
Abstract
able, due to inherent limitations of the distribution (Pleiss et al., 2017; Kleinberg et al., 2017; Menon & Williamson, 2018: Wang et al., 2024), as well as practical constraints. It is thus necessary be able quantify the deviation from faimess of given classifier. In addition, often the classifier is proprietary (Dastin, 2022; Grandinetti, 2023) and thus is not directly accessible for auditing, In other cases, individual-level data that is required for auditing is missing or insufficient. For instance, a health insurance com- pany may use a proprietary classifier to decide on coverage or on premium rates (Kafuria, 2022). Sabato & Yom-Tov (2020) showed that for binary classifiers, it is possible to provide fairness auditing without individual- data, us- ing only population-leve information on the frequencies of positive predictions and of true positive labels in each sub- population, where a sub-population the group of individ- uals who have the same value of the protected attribute(s). They considered fairness in the sense of equalized odds (Hardt et al., 2016), which defines a binary classifier as fair if its false positive rate and its false negative rate are each the same across all sub- sub-populations. They proposed to quan- tify the deviation from equalized odds using a measure that we will henceforth call Disparate Conditional Prediction (DCP). DCP the fraction of the population for which the classifier predicts with conditional prediction probabilities that differ from the closest common baseline.
We propose methods for auditing multiclass classi- fiers for fairness under multiclass equalized odds, by estimating the deviation from equalized odds when the classifier is not completely fair. We generalize to multiclass classifiers the measure of Disparate Conditional Prediction (DCP), origi- nally suggested by Sabato & Yom-Tov (2020) for binary classifiers. DCP is defined as the fraction of the population for which the classifier predicts with conditional prediction probabilities that dif- fer from the closest common baseline. We provide new localloptimization methods for estimating the multiclass DCPunder two different regimes, one in which the conditional confusion matrices for each protected sub-population are known, and one in which these cannot be estimated, for in- stance, because the classifier is inaccessible because good-quality individual-level data is not available. These methods can be used to detect classifiers that likely treat a significant fraction of the population unfairly. Experiments demonstrate the accuracy of the methods. Code is provided at https:: //g thub. com/s s vansabate/ DCPmulticlass
The faimess notion of equalized odds was originally stud- ied for binary classifiers. However, interest in fairness for multiclass classifiers has gained traction in recent years (see, e.g. Alghamdi et al., 2022; Rouzot et al., 2022; Wang et al., 2024). In multiclass scenarios, the multiclass equalized odds criterion measures any differences in conditional prediction probabilities between sub- nub-populations. This includes not only the difference in the rate of correct predictions as in the binary case, but also the types of prediction mistakes. For instance, if a patient's 's heart attack is misdiagnosed as an anxiety attack (which may mean the patient is denied care), this is significantly different than being misdiagnosed as a stroke (which may lead delayed care). If some sub- populations ineur more of certain type of misdiagnosis error, this could indicate bias in diagnosis, well as lead to undesired differences in treatment.
1. Introduction
Faimess of classifiers is a crucial property in many real-life scenarios (see, e-g., Caton & Haas, 2024). In particular, auditing classifiers for fairness is essential in wide range of applications and has been studied in many works (e.g., Saleiro et al., 2018; Angwin et al., 2022; Taskesen et al., 2021; Cherian & Candès, 2024).
While it is desirable that a classifier accurately satisfies the required fairness criterion, this is in many cases not achiev-
DDepartment of Computing and Software, McMaster Uni- versity; Canada CIFAR AI Chair, Vector Institute 'Department of Computer Science, Ben-Gurion University of the Negev e "Department of Computer Science, Bar- Blan University. Corre- spondence to: Sivan Sabato <sabatos memaster.ca>.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
In this work, we study the auditing of multiclass classi- fiers for deviation from multiclass equalized odds, using

---

Disparate Conditional Prediction in Multiclass Classifiers
natural generalization of DCP. DCP is different from other commonly used measures of deviation from equal- ized odds, such as the difference ratio of equalized odds (e.g., Alghandi et al., 2022; Wang et al., 2024), in that it has a consistent interpretable meaning as a fraction of the population, regardless of the number of protected attribute values, the number of classes, or the degree of class imbal- ance. Thus, DCP is useful for interpretably auditing and comparing classifiers. This is contrasted with the standard use of differences or ratios, which produces undesirable artifacts, such as discounting differences in rare labels, lack of normalization or boundedness, and lack of differentiation between classifiers with different degrees of bias. The quan- tifiable interpretation of the DCP measure ensures that it does not suffer from similar issues.
procedures provide useful estimates. These estimates can be used to identify classifiers that behave differently on different protected sub-populations.
Paper structure. Section 2 discusses related work. Pre- liminaries are provided in Section 3. In Section 4, we present the DCP measure and extend it to multiclass clas- sifiers. Section 5 provides methods for calculating upper and lower bounds for DCP for multiclass classifiers when the conditional confusion matrices for all sub-populations are known. In Section 6, consider the case where these matrices are unknown, using only population-level frequen- cies. Experiments are reported in Section 7. We conclude in Section 8. Some technical details are deferred to appendices.
It was shown in Sabato & Yom-Tov (2020) that the DCP of given binary classifier can be calculated efficiently using the confusion matrices of this classifier in each cotppopulation. When the confusion matrices are not available as discussed above, there exists an efficient procedure for deriving a lower bound on the value of DCP given population-level frequencies. This lower bound can be used to identify classi- fiers that treat high fraction of the population unfairly, with- out direct access to the classifier. In the case of multiclass classifiers, efficient procedures for calculating DCP are un- known, as this may be computationally intractable. Thus, we propose procedures to upper-bound and lower-bound the DCP of a multiclass classifier, given the conditional confusion matrices of the classifier for each noppoouuatiion, as well as given only population-level frequencies.
2. Related Work
Fairnsss for multiclass classification has been gaining inter- est in recent years. Denis et al. (2024) studied multiclass fairness with demographic parity. Alghamdi et al. (2022) use model projection for multiclass equalized odds. Putzel & Lee (2022) propose post-processing techniques for obtain- ing fairness in multiclass classification for various faireess notions. Rouzot et al. (2022) propose fairness scoring sys- tems for multiclass classification. Wang et al. (2024) study the fundamental limits of faimnss in multiclass classifiers, under several faimess notions, including equalized odds.
Sabato & Yom-Tov (2020) studied estimating the (un)fairness of a classifier, a crucial task in many appli- cations (Bellamy et al., 2019). They proposed the new DCP measure for binary classifiers, showed that it is easy to cal- culate using the confusion matrices for each sub-population. and provided methods for lower-bounding this measure in the absence of individual label data, using population-level frequencies. Several other works have studied fairness audit- ing in the absence of individual information about protected attributes (e.g., Awasthi et al., 2021; Fabris et al., 2023; Cor- nacchia al., 2023). Fairness auditing has also been studied in specific applications, including tax auditing algorithms (Black et al., 2022), visual systems (Goyal et al., 2022), and candidate rankings (Roth et al., 2022).
The upper bounds are obtained using local minimization procedures. The minimization problems are constrained, non-smooth and non-convex, and their objective functions have regions with large gradients, which is challenging nu- merically. As it is known that non-smooth functions are challenging for gradient-basee based algorithms,, we first handle the non-smoothness, caused by maximum term over sev- eral concave functions, by splitting the functions into their smooth parts, and adding more constraints to the existing ones to account for that. Then, we replace the concave func- tions in the constraints with linear approximations, and the minimization is obtained via sequential solutions of standard linear programming (LP) problems, which have available and rather efficient solution routines (Hall al., 2023). The LP solvers efficiently handle the constrained minimization at each step, even when the constraint matrices include large numbers because of the large gradients. As the problem is highly non-convex, the sequential minimization reaches local minima.
Many works use some relaxation of equalized odds to al- low learning or studying near-fair classifiers. However, there is not a single agreed-upon relaxation, in the binary or the multiclass case. For instance, Donini et al. (2018); Jung et al. (2021); Xue (2023); Wang et al. (2024) use a difference- based formulation, while Calmon et al. (2017) and Alghamdi et al. (2022) use ratio-based one. In Xue (2023), the sum of the differences is used, while in Wang et al. (2024), the maximum is used. In this work, we study a natural extension to of the interpretable DCP measure of Sabato & Yom-Tov (2020) to multiclass classification.
We report experiments on several data sets, showing that the gap between the upper and lower bounds, for both scenarios, are usually quite small, indicating that the optimization
2

---

Disparate Conditional Prediction in Multiclass Classifiers
Our work partly falls within the realm of fairness auditing using only aggregate statistics, without assuming access to the classifier. The challenge of auditing faimess using limited information has received significant attention in recent years, as evident, for example, in (Pinzón et al., 2024; Wang et al., 2021). Our work is unique, in that is the first, to our knowledge, to address the multiclass setting.
The set of matrices whose rows are in the simplex over ) is
A Akkk == (X == By definition, the classifier C satisfies the following:
| Vy ) (1 Jeey E Ax).
Va E A it holds that M2 E Aaxk and M To = Pa. (1)
The faimess notion of equalized odds (Hardt al., 2016),
originally defined for binary classification, was later gen- eralized to multiclass classifiers. We use the term-by-term multiclass equalized odds criterion (Putzel & Lee, 2022; Al- ghamdi et al., 2022), which requires that for each y. 1 E V, Og = p = 5 Y = y, = a] is the same across all a E A. Equivalently, all the matrices in MA are the same, Note that the same definitions can be used also for relaxed multiclass equalized odds criteria, such as those that dis- tinguish sensitive and insensitive labels (see, e.g. Rouzot et al., 2022). This can be achieved by mapping Y condi- tioned Y = y to a smaller set of predicted labels, where the mapping can depend on y, and then recalculating the distribution properties provided above. All the methods and results below are valid for the resulting transformation.
3. Preliminaries
We consider a multiclass classification problem with l pos- sible labels, in which each individual in the population has a true label in the label set y = (1....,k}. .k]. Fairness is considered with respect to some protected attribute, such as race, state of residence or age. A value of the attribute, which can be multi-valued, is assigned each individual. If there is more than one protected attribute, it can be sub- stituted for a single attribute which is the Cartesian product of all protected attributes. A nub-population is the subset of the population that includes all the individuals with the same value of the protected attribute.
The object of study is an existing classifier, denote it C, which maps each individual from the population to pre- dicted label, which may be different from its true label. We do not make any assumptions about the way the classifier is generated or the classification model. For a given C, denote by 'D the uniform distribution over the population of the triplets of true label, predicted label, and protected attribute value of individuals. A random triplet drawn according to D is denoted by (Y, Y, A), where Y E y' is the true label of the individual, Y E > is the label predicted by C for this individual, and A E A is the individual's protected attribute value, where A is the set of possible values. Denote the probability of an event E according to D by P[E].
4. The DCP Measure for Multiclass Classifiers
Recall that the distribution D is determined by the given classifier C. Denote the conditional distribution of D given the attribute value A a, and the true label Y y by Dy The binary DCP measure is based on modeling each Dy as mixture of two conditional distributions: a global baseline distribution, which is the same for all sub-populations and represents the baseline behavior, and a local nuisance dis- tribution, which can be different for each a and represents the deviation from this baseline. For a E A, y E y, let ny E j0, 1] be the probability conditioned on A= a, Y = y that Y is drawn according to the nuisance distribution. DCP(C) is defined as the fraction of the population for which the local nuisance conditional distributions are used by the classifier instead of the global baseline distribution. Since the baseline conditional distribution is unobserved, it is taken to be the one that results in the minimal possible DCP. Formally, for given classifier with the distribution D, and letting na = (nk)nE,,
We define the following notation for properties of D: The frequency of each sub-population in the distribution is wa := PIA- a]: The vector of frequencies is w (wa)eEd- The proportion of true label y E y in sub- population a E A is n²- == PlY = y A = a): The vector of these proportions is To := (m The proportion of predicted label y E y by classifier C in sub-populee tobpulpulttion a E is P == P| = y A = al: The vector of these proportions is p. == (P vey. The entries in the confusion matrix of the classifier on sub- aub-population a E A are = y, a).
DCP(C)= = min {ma aEA
Wa T a na: Σ
(2)
denoted by Vy, 5 Y, 0. == PI = Throughout this work, the value of a conditional probability expression in which the probability of the condition is zero is treated as zero Denote the confusion matrix of on a sub- population a by M. := (a2"), v.ee.. Denote the indexed set of all such confusion matrices by MA == [Ma]aeAA
where the minimum taken over {NaAaEA that are consis- tent with D; that is, such that there exist baseline distribu- tion D and nuisance distributions {N hue V.EA such that for each y E V,a E A, DV = (1 - n D2 + No If the classifier satisfies cqualized odds, then the distributions Dy are the same for all a E A, in which case the decomposition holds by setting ng = 0 for all y E V, a E A and setting the baseline distribution for y to Dy for an arbitrary a. This
Denote row y in M, by ag- := (a gey.
Denote the k-simplex by A& = (v E RR 1 ||vl]1 = 1}.
3

---

Disparate Conditional Prediction in Multiclass Classifiers
where og = (oi Joey.
Proof. In an analog to the derivation in Sabato & Yom- Tov (2020), it is easy to see that for given baseline distribution with rates {ags) J..Ey..
05-
62
0. b v8 (1 11-17 (-nn))) + 22 nM
60
0.
where 22 is the conditional probability of predicting 9 given true label y, under the nuisance distribution Agg From Eq. (2), it follows that the optimal solution for w2 mini- mizes ny subject to
(a) a ++ (a,a,) b)
1.0
68-
0 49
Vg E y s.t. v2 + qb
v9
0
0.6
V
0
0.4
Vy E y E A, nā 20, 0,
622
Va E A, (v ..... vuth E A
02
0.4
0.6
0.8
If a = og for all ÿ E V then clearly ny = 0. Otherwise, the first constraint requires v a + (a ab 3/m% Summing over ÿ. this implies Egey SR Σ EgE ag Vb + (Ejey 0g ESEy "0") >/ng = 1. Thus, the last constraint can be replaced by U E [0, 1] for all ø E y. Since the derivative of the RHS of the first constraint is never zero, the minimizer of no is obtained when one of the other con- straints holds. That is, with an assignment of a = 1 for some o, ú. y such that ag a or vēy 0 for some a. 9 y such that ug < ag follows that there is some ① E y such that
(b) 6 + vj(a b)
Figure 1: The function 17(a, b).
gives DCP(C)- = 0, as expected. Sabato Yom-Tov (2020)
show that for binary classifiers, where D 10.
DCP(C)- = DCP(MA, w. T)
(3)
Σ min vEY 101-1) E10,11 aEA
Wa Dua 1 a (0(()))),
(11-))
where MA is determined by C, w, are the population properties, and without subscripts denotes the function:
99 - 0
%b
a ag
and n/
1
ab
Vb
o
<<< a (a, b) = 1 (1 b)/(1 a) > 0 0
1 b/a
or
(4)
2
b= ==0 a
29 <
29 and n %
99
abb
%
17 is illustrated in Figure 1. In the minimization in Eq. (3), og =(1-)) represent conditional prediction rates for the base- line distribution. More generally, we denote the conditional probability of predicting ý given true label y under the base- line distribution by ab Sabato & Yom-Tov (2020) observe that since a + n1a, b) is piecewise concave on the intervals [0, bj and [b, 1] (see Figure 1), it suffices to minimize each of the terms in Eq. (3) over ab v(1-y) {aaJaEA (0, 1}.
Moreover, for all i V, if og
>
%
vú then 7o 2 1
1-a 0
1 1-a
and if ag < ag then 1aa 2
follows that
v0
T = max max BEY
max 7((g" vb
a
vÿ
a
v9
BEy
We first provide formulation of DCP(MA, w, TT) for mul- ticlass classifiers.
Eq. (5) thus follows.
Theorem 4.1. For multiclass classification, Eq. (2) implies
It is easy to verify that Eq. (5) is equivalent to Eq. (3) for binary classifiers, since for ) = (0. 1}. /. = 1 - 1-000 9(1-)) and the same for ab. and 17(a, b) -,,1,1-b)
DCP(C)= DCP (M, W)
(5)
min Σ yEy
Σ
Wany max v9 DEy
o²)),
For simplicity of notation, we henceforth treat w and π as fixed and write DCP( In the multiclass case,
aga
a
4

---

Disparate Conditional Prediction in Multiclass Classifiers
(C)(MA) is the solution of non-convex constrained min- imization problem. In the next section, provide methods for calculating a lower bound and an upper bound for this quantity.
Algorithm 1 Local minimization of DCP, via sequential
linear programming
Input: (²) H, w, maxiter, Output: The local minimizer ax
Note that in practice, some cases, the properties of the distribution D for would be estimated from a limited data set and so may deviate from the true properties for D. However, since DCP is interpretable as fraction of the population, any inaccuracy in the estimation of 'D would map to at most the same amount of inaccuracy in DCP.
for ( = 0 to maxlter do
Define the LP approximation of Eq. (9) by computing
M, M2, and v.
Define â as the minimizer of the LP in Eq. (11).
Set ( a μ( (²)),, where / is obtained
using line search to ensure a reduction in Eq. (8). If ||e]| < stop.
end for return the last iterate (()
5. Bounding the DCP of Multiclass Classifier
We propose methods for calculating a lower bound and an upper bound for DCP(MA). The lower bound is simple analytical formula. For y E V, define a = {OE)REA and
identity matrix of dimensions d x d by la. Our objective in Eq. (5) and its constraints, is thus given by:
DCP = min Σ EDE
Wa na max r/ vb 2 (6)
Minimize aERk
Σ Wa max hag))
(8)
xE)
aEd
s.t.
a (a, 1x) =
Then DCP(MA) = Ewey DCP, (a)) A lower bound on DCP, y can be derived follows:
To solve the problem, we observe that its structure resem- bles a linear program (LP). That is, the objective is given by an inner product, and the constraints are linear. The only difference between an LP and Eq. (8) is the maximum term over the v) values inside the inner product. Hence, to solve Eq. (8), we apply the sequential linear program- ming approach (Nocedal & Wright, 2006), which iteratively approximates Eq. (8) as a linear program and solves it.
DCP, (a2) agED:
min
Σ aeA
Wax max (/ a.
NEY
min
Wn maxin(a av)
1]
BEy
min
max
Wa - 20 a
og [0 DEy
aEA
max min
Wa Wa Q8.
SE s=[0,1]
First, we replace the maximum terms in the objective with another variable vector c and additional constraints, follow- ing Charalambous Conn (1978):
Due to the piecewise concavity of a naa, b) on [0, b) and [6, 1]. it suffices to minimize each of the terms in Eq. (3) over E (0.1} U (a
Minimize &ERt ,eEk14
(w,c)
MEEA. Thus.
s.t.
0 05 1k) 1
DCP(MA) >
max Σ
min
Σ
Warkn(z
DEY
ZE (0.11)). (o )ACA aEA
yEy
n(ag, ha.)) ) S Ca. Vÿ E A.
This lower bound can be calculated in time (((A(22).
This problem is equivalent to Eq. (8), but has maximum operation. However, now have non-linear constraints, thus violating the definition of an LP. To correct this, we use local approximation of r (around an iterate (x using the Taylor series. Note that the function a + 17(a, b) is piece- wise concave, non-negative, and smooth at (0, 1) except at b, where is minimized and equals zero. Therefore, we do not expect the maximum over in the objective Eq. (8) to fall on the discontinuity of 1) at b. except for extreme cases. Hence, using linear approximation we expect to get good local approximation of r7).
To upper bound DC)(MA), we propose local iterative optimization approach on the objective function in Eq. (6), which is constrained, non-smooth, and non-convex. One can randomly initialize using feasible solution. However, we propose a more tailored approach the end of this section.
Our optimization approach utilizes sequential LP solu- tions, and is as follows. Given y y, denote the matrix H E R A|xk to include the entries ht.y = oy9. Note that the rows of H are in the simplex Ap. The vector W E [o, A| includes the entries W1 == w. The opti- mization variables are denoted by the vector a == ag E R Denote the all-one vector of dimension by 1 and the
The sequential linear programming approach calculates the new iterate (a. (I+1), c((+1)) (++1))c(t+1)) by solving an I.P problem an
5

---

Disparate Conditional Prediction in Multiclass Classifiers
approximation of Eq. (9) around (o cl That is, given an iterate (a c(t) we first approximate 1 by linear
the objective function into account. We propose instead greedy approach, in which the entries in the baseline confusion matrix are optimized label-by-label, using the fact that the binary problem is easy to minimize. In the first iteration, all labels except for one are treated as the same label, and optimal confusion matrix values for the first labels are calculated. In each further iteration, one additional label is separated, and the assignment for this label is optimized given the assignments of the previous labels. This approach is possible because DCP is monotonic under the merging of labels. The full derivation and procedure are provided in Appendix C. Our experiments in Section 7 demonstrate that this method is superior to the averaging approach.
Taylor series in its first argument:
7(a+t,))-n(0) On(a,,) b)
aze (1-b)
b,
< b
da
(1aa2
b.
We now locally approximate Eq. (9) around an iterate a (1)
via the following LP problem:
Minimize OER" ,EERAA
(w
(10)
S.L.
0sa,el,
(a, 1x) 1
6. Best-case DCP without Confusion Matrices
Va + Ja(a - (1)) s 1xCa, Va E A,
We next consider the case of classifier for which the con- fusion matrices for each sub-population are not available, either because the classifier is not accessible for testing or because individual-level ground-truth data is missing or insufficient. In this case, we assume, as in Sabato & Yom- Tov (2020), access only to the frequencies of true and pre- dicted labels in each cotb-ppulation, but not the conditional probabilities. Formally, we do not have M, for the given classifier C. We only have access to the population-level frequencies (w, { (T Pa)
where Va E R$ is a vector with the coordinates (Va)g ha.)) for all ÿ E [k), and Jn E R is a diagonal Jacobian matrix s.t (Ja)gg =
nlag (1)
ov(a (t) shass Bringing this 8a
into a canonical form with a variable a (1) + yields
Minimize aER* CER*M
(w,c) c)
(11)
s.t.
S a (a, 1x) 1,
If C is fair under multiclass equalized odds, then all the matrices in MA must be identical. Thus, from Eq. (I), there exists a single confusion matrix M E ARx such that Va A, M π. = Pa. If such a matrix does not exist and the input frequencies are accurate, then C does not satisfy the multiclass equalized odds criterion. Nonetheless, given (w, ( Pa) JaEA) for C, we would like to find the best- case value of DCP for C, denoted mi D.P. Formally,
M,c + M2a - M2a + v v O,
where M1 := :- ||A @ lx. M2 = J2; Jujl is the stacking of all diagonal Jacobian matrices on top of each other, and v : [vi;-..; V/Ai is the stacking of vectors. Eq. (11) is an LP in a canonical form, which is solved itera- tively. Note that M, and M2 are highly sparse, which can be exploited to easily solve large instances of the problem. The resulting local optimization algorithm is given in Alg. 1.
mi nnnDC(((w, (TT Pa) = min((CP(MA) Va E A, A.M. E M. n. = p...
(12)
A note on usage. By definition, the function ry in Eq. (4) is continuous in the open section (0, 1)², but at the boundaries, it is easy to see that 17(0, 0) = O, while lims-+0 7765, 0)- Furthermore, the derivatíves of 1) when its first argument is close to 0 or 1 can be very large, causing numerical difficul- ties in the LP solvers. Thus, to avoid numerical instability, we make sure that all entries of H are in [e, 1 - c| (where we used & = 10-5) by replacing any value outside these boundaries by the relevant boundary value and renormal- izing. Note that since the input values in H are calculated in practice based on finite data sets, values in H are al- ready noisy representations of the true population values, and so slightly changing them does not negatively affect the correctness of the method.
Sabato & Yom-Tov (2020) show that minDCP can be cal- culated exactly for binary classifiers. In the multiclass case, we are not aware of an efficient algorithm for cal- culating the exact value of minDCP. Instead, vide below mocal-minimization algorithm for (M,( under the constraints on MA. which results in an upper bound for mi DCP. This, combined with a lower bound on minDCP, provides a limited range of possible values of minDCP for the given classifier C.
pro-
To calculate the lower bound, observe that
DCP(MA) = Σ min oFE
Σ wary max r(ag" ".)) sEy
nEy
aEA
Finding an initializing assignment A natural guess for an initializing assignment a ()) is the weighted average of the confusion matrices in MA- However, this does not take
min Bey a E
W WaTyn(a 2y ".
(13)
a
6

---

Disparate Conditional Prediction in Multiclass Classifiers
Each of the terms in the RHS is of the same form the terms in the definition of DCP for binary classification. The RHS is a constrained minimization problem that can be solved using the same methodology as in Sabato & Yom- Tov (2020), providing a lower bound for mi n nDP.
Kestaa
tyloud
Uneer
We now turn to the local optimization algorithm for minDCP. We use a sequential linear programming ap- proach, similarly our solution Eq. (8) in Section 5. First, we extend the notation of Eq. (8) explicitly denote the value of y E )): The matrix H E RRAAi is defined such that hig = a The vector w E [0, (| includes the entries wa == = The optimization variables are denoted by the vectors a == a E R We replace the maximum terms in the problem Eq. (5) with the vectors c² E RR similarly to the transformation from Eq. (8) to Eq. (9). The variables for the optimization problem are the collection of the vectors and matrices
Figure 2: The linear approximation of nn(a, b) using the split to 7/1 and 7/2 around ouy = 0.35, for fixed b 0.25.
it as the maximum between the two smooth functions:
(a, b) max (m b), m2(a,)))
(16)
1-b This where m (a. b) = 1- _ and 12 b) = = T-a"
split is an alternative formulation to the definition of nj in Eq. (4), only now the singularity point is replaced with a maximum, and can be treated in the same way we treat the maximization over all terms involving r using sequential LP. Figure 2 shows the independent linearization of the two terms after the split and the piece-wise linear approximation of the non-smooth function in our objective. Overall, the solution of the Eq. (15) is obtained after the split using sequential LP. More details are given in Appendix D.
x (a', H c'', ax, H c²*)"
(14)
which amount to x² + k2. |A| + k |A|| scalar unknowns in total. We get the following new problem, which is equivalent to the problem defined in Eq. (5), including its constraints:
Minimize (a"), (aH)).HP))ee)) }.fey
Σ (W ,"))
(15)
s.t.
0 S a² $1
Vy E [A:], Vy E [k],
0 S HD 11
7. Experiments
0 c. 1
Ay E [k],
We report experiments demonstrating the performance of the methods proposed above, for the case of known as well as unknown confusion matrices (Section 7.1 and Section 7.2), respectively. We show that in most cases, the ratio between the lower bound and the upper bound, in both types of experiments, is close to 1, indicating that the methods pro- duce fairly accurate estimates. Code is provided at https: //github. com/ s
(a",1) =1
Ay [k:]
Hº1, = =1 Vy E [k],
Σ T و = pd vg E [kt] a E [[A]].
naa Ny S c% Vy.u E [k]. a E [[A]],
Note that the objective in Eq. (15) is linear, and its con- straints are linear as well, except the bottom ones involving 70. similarly to Eq. (9). Also note that all of the linear constraints are separable y, except for the last one, which introduces coupling between the HD of different y's.
7.1. Bounding the DCP with Known Confusion Matrices
We report the results of calculating upper bound and lower bound on the DCP(MA) of multiclass classifier given MA. As discussed above, if the confusion matrices in MA are known up to some accuracy of DD then (M)(MM) will have at least the same accuracy, as a direct result of its definition as a fraction of the population.
To solve the problem we again use the sequential linear pro- gramming approach, as the structure of the problem again resembles a linear program. Given the t-th iterate (+) for all the variables defined in Eq. (14), we first approximate r) by a linear Taylor series, this time in both of its arguments, since now both are optimized. The function 17 b) is linear which
in 6, hence the Taylor series is exact with respect is appealing for approach. However, minimizing the objective with respect to both 1." and og leads to the mini- mal non-smooth points of 17. These points are the singularity points (see Fig. 1), where is not approximated well by a linear function. This results in a slow convergence of the sequential I.P algorithm, To solve this, we split 1) and define
We compared our proposed local-optimization approach for calculating an upper bound, described in Section 5, to other approaches for finding feasible low-value assignment for Eq. (5). We tested the following alternatives: (1) Average: the weighted average of the sub- populaation confusion ma- trices; (2) Greedy: the greedy initialization procedure pro- posed in Section 5: (3) Average+I.M and (4) Greedy+L.M
7

---

Disparate Conditional Prediction in Multiclass Classifiers
initializing with the corresponding method, then running the local optimization procedure. Our results below show that our approach, Greedy+LM, has the best performance. We also report the ratio between the best upper bound and the lower bound, calculated according to Eq. (7). A ratio close to indicates that in this case, the two bounds are tight.
Table I: DCP with known confusion matrices, decision trees; US Census (top), Natality (bottom). For US Census, cach row corresponds to different classifier. Its error is indicated in the "Error" column. "Lower bound" is the lower bound calculated for DCP using our method. The upper bounds are the values obtained by each of the compared methods for minimizing the DCP objective. "Best ratio" indicates the ratio between the best (lowest) upper bound and the lower bound. A ratio of indicates that the bounds are both tight. For Natality, all the rows report the same classifier, and cach row calculates DCP with respect to a different protected attribute.
For these experiments, we selected data sets on individuals, which are mostly categorical, and which include several multi-valued attributes that can be used as predicted label and as protected attribute. First, we used the US Census data set (Dua & Graff, 2019) to generate multiclass classi- fiers to predict each of the individual attributes that have between 3 and 10 values. The protected attribute was the state of work. We tested our methods with three different types of classifiers: decision tree and a nearest neighbor classifier, using standard Matlab libraries, as well a classi- fier based on a standard fully connected neural network. The latter used two layers of size 64 and 32 neurons, with ReLU activation. The network was implemented in PyTorch, and trained with the Adam W optimizer, with a learning rate of 0.001, and batch size of 256, for 4 epochs.
Lahels
Emorr
Upper Bounds
Best
Bound
Average
Greedy
Average-LM
Gre
Ratio
11.74%
5.35%
27.19%
B.6176
14.07%
7.65%
1.42
5.71%
4.35%
42.17%
5.92%
$2.39%
5.28%
1.21
3.96%
3.24%
13.63%
5.07%
16.95%
3.25%
1.00
5.15%
4.24%
39.0556
5.40%
14.32%
4.25%
1.00
3.36%
2.63%
48.0455
5.2015
5.49%%
3811%
1.44
1.85%
1.83%
6456666
8.2255
17.85%
1.85%
1.00
1.96%
1.967%
51 8655
7.88%
13.31%
1.96%
1,00
2.027%
2.28%
48.501
6.5756
10.50%
2.28%
14.00%
1.57%
26, 85%
6.17%
13.13%
6,10%
1.31
3.91%
1.48%
27.555
8.1255
1.86%
1.49%
5.619E
2.06%
7.14%
43.00156
6.61%%
3.91%
1.50
11.83%%
4.57%
25.28%6
34-40%
22.18%
8.28%
1.81
0.57%%
0. 0.86%
21 21.96%
24.85%
9.55%
0.86%
1.00
22.61%
8 29%
841.555
32.035%
38.20%
23.61% %
2.85
21.54%
6.03%
86.1756
12.50%
6.8455
6.17%
1:23
Protected
Lower
Upper Bounds
Best
Table as well as Table and Table in Appendix A, list the DCP lower bound calculated for each of these classifiers given their confusion matrices, the upper bound obtained by each of the tested upper bound methods, and the ratio between the smallest upper bound and the lower bound. In some of the experiments, the lower bound is equal to the upper bound, giving the exact value of the DCP of this classifier. In all of the experiments except for single case, our proposed approach provides the tightest upper bound. The ratio between the upper bound and the lower bound ranges from 1.00 to 2.85, and is close to 1.00 in most cases, showing that for these classifiers, the DCP can be estimated quite well. In most cases, the DCP for decision tree classifiers obtained better accuracy ratios.
Attribute
Bound
Average
Greedy
Average+LLM
Greedy-LM
Ratio
Attendant
1.91%
14.30%
2.34%
2.10%
2.08%
Father Race
0.92%
19.75%
1.50%%
1.322%
1.28%
1.40
Mother Race
0.63%
13-43%
1.31%
1.14%
1.12%
1.71
Payer
1.71%
21.15%
1.96%
1.97%
1.89 %
1.09
lower bound is between 1.00 and 1.58, showing that here too, DCP is estimated to high accuracy.
7.2. Bounding minDCP without Confusion Matrices
In the second set of experiments, we used only the population-level frequencies (w, ( paa)) to esti- mate minDCP.. We ran the local optimization procedure provided in Section 6 to find an upper bound on mi minDCP, and compared this result to the lower bound Eq. (13), to provide a range of possible values for minDCP. This range can indicate whether the population-level frequencies point to a possible, or definite, large deviation from multiclass equalized odds, as measured by the DCP.
Second, we used data about births in the United States (CDC, 2017), which provides detailed information about each birth that occurred during 2017. The data set includes approxi- mately 3.8 million data points and 50 attributes. Using only attributes that are known before the labor, we generated three classifiers that attempt to predict the type of labor out of the five possible options (e.g., spontaneous, Cesarean): a decision tree (error 30.8%), a k-Nearest Neighbor classifier, where & was set to 9 using parameter tuning (error 24.6%), and a 2-layer neural network (error 22.43%). This allows studying a high-error regime for the estimation of DCP. We estimated the DCP of each classifier, with respect to different protected attributes. Table (bottom), and Table 4, Table 6 in Appendix A, report the DCP lower bound and upper bounds relative to each of these protected attributes. Here too, our proposed approach provides the tightest up- per bounds. The ratio between the upper bound and the
First, we calculated the local minimizer of minDCP for the same two labeled data sets that were tested in Section 7.1, this time without access to the confusion matrices. We then compared the obtained value to the actual ranges of DCP that were calculated using the confusion matrices in Section 7.1. Table 2 provides results for the US Census data set and the Natality data set. In all but single case the local optimizer of minDCP was lower than the true DCP range of the classifier, showing that this value is indeed a relevant best-case value for DCP with unknown confusion matrices.
Next, we report two experiments for which we do not have ground truth labels to compare to, to demonstrate how this
8

---

Disparate Conditional Prediction in Multiclass Classifiers
Table 2: Comparing the output of the mi minDCP local optimizer (LO) to the DCP range calculated for US Census classifiers (top) and Natality (hottom). The ranges are derived from the results of
UK elections
10%
Table 1, Table and Table
2%
US Census
Decision tree
Nearest Neighbor
Lahels
m1 DDnDCP LO
true DCP
m1=DCP 10
true DCP
2.47%
5.30%
7.63%
3.16%
6.56%
9.77%
1.11%
4.35%
5.28%
2.86%
6.15%
9.87%
1 1.20%%
3.24%
3.25%
3.01%
6.82%
9.55%
0.84%
4.24%%
4.25%
2.79%
6.16%
8.81%
0.98%
2.63%
3.81%
2.83%
7.15%
9.05%
1.13%
1.85%6
2.82%
6.03%
9.08%
1920
1030
1940
1980
1950
1970
-250
1920
2000
2010
2000
1.11%
1.96%
3.02%
6.50%
8.50%
eledton your
0.68%
2.28%
2.82%
7.14%
9.47%
3
1 1.90%%
4.57%
6. 6,10
2.40%
6.24%
7.01%
Figure 3: Calculated value minDCP for each election year in the UK elections dataset, where the value is reported for the classifier that attempts to predict this year's election
1.07%
1.8%%
1.49%
4.29%
10.81%
5
2 0.08%
2.06%
3.915
6.08%
8. 86%
10.74%6
3.13%
4.57%
8.28%
3,29%
10.7456
5.99%
9.50%
18.22%
result using the results of the previous election.
5.62%
88%
21.25%
0.32%
0.88%
6.41%
10. 100%
20.58%
4.05%
8.29%
23.615%
5.9776
7.89% 20.45%
2.38%
5.08%
6.1555
4.31%
7.91%
14.00%
Natality
Decision
N-Nearest Neighbors
from equalized odds, even when there are many classes, protected attribute values, or highly imbalanced data sets.
Protected Artriatee
mf DDPP 1.O
muc DCP
mi M1+1CCPI1 1.O
truc DCP
Altendant
0.73%
199%
2.08%
0.74%
1.80%
1.82%
Futher Race
0.20%
0.92%
1. 1.28%
0.92%
1.17%
1.18%
Mother Rovy
0.12%
0.65%
1.12%
0.14%
0.61%
0.62%
Pager
0.05%
1.74%
1.80%
0.50%
1.78%
1.76%
Impact Statement
This paper studies the auditing of classifiers for fairness in the sense of multiclass equalized odds. Identifying classi- fiers that may violate faimess criteria is an important task that can help advance societal desiderata. Nonetheless, such use must always consider the suitability of the fairness cri- terion to the specific classification task. In addition, in some cases the methods that propose may provide loose bounds for the studied criterion. These cases can be iden- tified by observing a large gap between the upper bound and the lower bound. In such cases, care must be taken when making operative decisions based on the results of the methods.
method can be used for studying various empirical ques- tions. In the first experiment, used data about the general elections in the UK from 1918 to 2019 (Watson et al., 2020). We studied the changes in voting patterns between elections by studying the m nDCP value of a hypothetical classifier that would predict the vote of individuals in one general election to be the same as their vote in the previous general elections (ignoring the change in population between elec- tions). We studied DCP when the protected attribute was the geographic region of the voters, as reported in the data set. A high DCP value of such a classifier would indicate a possibly large difference between voting pattern changes across regions. Figure 3 shows the value of min minDCP by election year, revealing clear differences between different periods of the last century.' The full results are reported in Table 9 in the appendix. In Appendix B, we report additional experiment, on a US education data set.
Acknowledgements
We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number RGPIN-2024-05977]. Re- sources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vec- tor Institute; see attps:://eectorinss.ttttteet pa partnershi httchhippccurreeee wwwreenttparteeeeeeeeeeeteeeeeee was supported by the Israeli Council for Higher Education (CHE) via the Data Science Research Center at Ben-Gurion University.
8. Conclusion
In this work, we provided a definition and bounding meth- ods for the DCP measure for multiclass classifiers. This provides a new tool for auditing fairness in multiclass clas- sification. Because DCP is interpretable as fraction of the population, the estimation methods that we proposed can be used to provide clear evaluation of classifiers' deviation
This work
References
'Noe the spike in Figure 3 for Oct. 1974 elections; they were unusual as they were held in the same year the previous elections, and resulted a significant political change (Roe-Crines, 2021).
Alghamdi, W., Hsu, H., Jeong, H.,, Wang, H., Michalak, P., Asoodeh, S., and Calmon, F. Beyond adult and compas:

---

Disparate Conditional Prediction in Multiclass Classifiers
Fair multi-class prediction via information projection. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Informa- tion Processing Systems, volume 35, pp. 38747-38760. Curran Associates, Inc., 2022.
Dastin, J. Amazon scraps secret ai recruiting tool that showed bias against women. In Ethics of data and ana- lytics, pp. 296-299. Auerbach Publications, 2022.
Denis, C., Elie, R., Hebiri, M., and Hu, Fairness guaran- tees in multi- classification with demographic parity, Journal of Machine Learning Research, 25(130):1 2024.
Angwin, J., Larson, J., Mattu, S., and Kirchner, L. Ma- chine bias. In Ethics of data and analytics, pp. 254-264. Auerbach Publications, 2022.
Donini, M., Oneto, I.., Ben-David, S., Shawe- Taylor, S., and Pontil, M. Empirical risk minimization under fairness constraints. In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Advances in Neural Information Processing Systems 31, pp. 2791-2801. Curran Associates, Inc., 2018.
Awasthi, P., Beutel, A., Kleindessner, M., Morgenstem, J., and Wang. X. Evaluating fairness of machine learning models under uncertain and incomplete information. In Proceedings of the 2021 ACM conference on fairness, accountabiliry, and transparency. pp. 206-210 214, 2021.
N., and Garnett, R. (eds.),
Bellamy, R. K., Dey, K., Hind, M., Hoffman, S. C., Houde, S., Kannan, K., Lohia, P., Martino, J., Mehta, S., Mo- jsilović, A., et al. Al fairness 360: An extensible toolkit for detecting and mitigating algorithmic bias. IBM Jour- nal of Research and Development, 63(4/5):4-1, 2019.
Dua, D. and Graff, C. UCI machine learning repository, 2019. URL
ics www.uci..... edu. m1.
Fabris, A., Esuli, A., Moreo, A., and Sebastiani, F. Mea- suring fairness under unawareness of sensitive attributes: A quantification-bass approach. Journal of Artificial Intelligence Research, 76:1117-11881 2023.
Black, E., Elzayn, H., Chouldechova, A., Goldin, J., and
Ho, D. Algorithmic fairness and vertical equity: Income fairness with irs tax audit models. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAceT '22, pp. 1479-1503, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978 1450393522.
Goyal, P., Soriano, A. R., Hazirbas, C., Sagun, L., and Usunier, N. Fairness indicators for systematic assess- ments of visual feature extractors. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT '22, pp. 70-88, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450393522.
Calmon, F., Wei, D., Vinzamuri, B., Natesan Ramamurthy, K., and Varshney, K. R. Optimized pre-processing for discrimination prevention. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30, pp. 3992-4001. Curran Asso- ciates, Inc., 2017.
Grandinetti, J. Examining embedded apparatuses of ai in facebook and tiktok. Al & Society, pp. 1-14, 2023.
Hall, J., Galabova, I., Gottwald, L., and Feldmeier, M. Highs-higs performance software for linear optimization, 2023.
Caton, S. and Haas, C. Fairness in machine learning: A survey. ACM Computing Surveys, 56(7):1-38, 2024.
Hardt, M., Price, E., and Srebro, N. Equality of opportunity in supervised learning. In Advances in neural information processing systems, pp. 3315 33233, 2016.
CDC.
United states natality public use file, 2017. URL https://ftp.cr cdc. gov/pb//
Health httpp//aaaaaiittee//////aaaaaaae
Jung, S., Lee, D., Park, T., and Moon, T. Fair feature distillation for visual recognition. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 12115-12124, 2021.
Charalambous, C. and Conn, A. An efficient method to solve the minimax problem directly. SIAM Journal on Numerical Analysis, 15()):122-187, 1978.
Kafuria, A. D. A predictice model for health insurance premium rates using machine learning algorithms. PhD thesis, University of Rwanda, 2022.
Cherian, J. J. and Candès, E. J. Statistical inference for fairness auditing. Journal of Machine Learning Research, 25(149):1-49, 2024.
Kiessling, D., Zanelli, A., Nurkanovie, A., Gillis, J., Diehl, M., Zeilinger, M., Pipeleers, G., and Swevers, J. A feasi- ble sequential linear programming algorithm with appli- cation to time-optimal path planning problems. In 2022 IEEE 61st Conference on Decision and Control (CDC), pp. 1196-1 1003. IEEF, 2022.
Cornacchia, G., Anelli, V. W., Biancofiore, G. M., Narducci, F., Pomo, C., Ragone, A., and Di Sciascio, E. Auditing fairness under unawareness through counterfactual rea- soning. Information Processing & Management, 60(2):
103224, 2023.
10

---

Disparate Conditional Prediction in Multiclass Classifiers
Kleinberg, J., Mullainathan, S., and Raghavan, M. Inher- trade-offs in the fair determination of risk scores. In 8th Innovations in Theoretical Computer Science Con- ference (ITCS 2017). Schloss Dagstuhl- Seatuull-LeiibiizZZennnun fuer Informatik, 2017.
USDA Economic Research Service. Highest level of edu- cational attainment, 2021. URL hwtpt:tttt://ttc /data ers. usda gov/reports aspx?ID-1753
Wang. H., He, L.,, Gao, R., and Calmon, F. Aleatoric and epistemic discrimination: Fundamental limits of faireess interventions. Advances Neural Information Process- ing Systems, 36, 2024.
Menon, A. K. and Williamson, R. C. The cost of fairness in binary classification. In Conference on Fairness, Ac- countability and Transparency, pp. 107-118, 2018.
Wang. J., Liu, Y., and Levy, C. Fair classification with group- dependent label noise. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, pp. 526-536. 2021.
Nocedal, J. and Wright, S. Numerical optimization. Springer Science & Business Media, 2006.
Pinzón, C., Palamidessi, C., Piantanida, P., and Valencia, On the incompatibility accuracy and equal opportunity. Machine Learning, 1355):2455-2434, 2024.
Watson, C., Uberoi, E., and Loft, P. General elec- tion results from 1918 to 2019, 2020. URL
https: httes://oommonsllrrrryyrerr.l.lt uk/ http://earrchbrriiiiigg//o-----
Pleiss, G., Raghavan, M., Wu, F., Kleinberg, J., and Wein- berger, K. Q. On fairness and calibration. In Advances in Neural Information Processing Systems, pp. 5680-5689, 2017.
Xue, Group adaboost with fairness constraint. In Pro- ceedings of the 2023 SIAM International Conference on Data Mining (SDM), pp. 865-873. SIAM, 2023.
Putzel, P. and Lee, S. Blackbox post-processing for multi- class fairness. arXiv preprint arXiv:2201.0446/ 2022.
Roe-Crines, A. S. Who Governs? The General Election Defeats of 1974, pp. 355-375. Springer International Publishing, Cham, 2021.
Roth, J., Saint-Jacques, G., and Yu, Y. An outcome test of discrimination for ranked lists. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT 22, pp. 350-356, New York, NY, USA. 2022, Association for Computing Machinery. ISBN 9781450393522.
Rouzot, J., Ferry, J., and Huguet, M.-J. Learning optimal fair scoring systems for multi-class classification. In 2022 IEEE 34th International Conference on Tools with Artificial Intelligence (ICTAI), pp. 197-204. IEEE, 2022.
Sabato, S. and Yom-Tov, E. Bounding the fairness and accuracy of classifiers from population statisties. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th In- ternational Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8325. PMLR, 13-18 Jul 2020.
Saleiro, P., Kuester, B., Hinkson, L.., London, J., Stevens, A. Anisfeld, A., Rodolfa, K. T., and Ghani, Ae- quitas: A bias and faimess audit toolkit. arXiv preprint arXiv:1811.05577 2018
Taskesen, B., Blanchet, J., Kuhn, D., and Nguyen, V. A statistical test for probabilistic fairness. In Proceedings of the 2021 ACM conference on fairness, accountabiliry, and transparency, pp. 648 665., 2021.

---

Disparate Conditional Prediction in Multiclass Classifiers
A. Deferred Experiment Results
Table --ble below provide remaining result the experiments which are described Section 7.
Table 3: Bounding the DCP for multiclass classifiers with known confusion matrices; US Census data set with nearest neighbor classifiers. Table columns as Table 1.
# Error
Lower Bound
Upper Bounds
Best Ratio
Labels
Average
Greedy
Average+LLM
Greedy +LM
3
27.71%
6.56%
19.71%
10.64%
10.80%
9.77
1.49
3
28.71%
6.13%
19.00%
11.66%
10.67%
9.87
1.61
3
26.22%
6.82%
18.44%
10.46%
11.82%
9.59%
1.41
3
24.61%
6.16%
19.54%
10.05%
11.23%
8.81%
1.43
3
24.24%
7.15%
20.04%
10.44%
12.04%
9.05%
1.27
3
23.52%
6.93%
20.42%
10.00%
11.97%
9.08% %
1.31
3
23.43%
6.56%
19.15%
8.91%
11.10%
8.59
1.31
3
23.46%
7.14%
20.01%
10.95%
12.08%
9.47 %
1.33
3
19.45%
5.24%
23.24%
8.80%
9.98%
7.01%
1.34
27.22%
5.61%
39.16%
11.24%
18.47%
9.12%
1.63
13.87%
7.53%
64.62%
13.32%
14.62%
10.81 %
1.43
5
17.54%
8.86%
59.21%
11.83%
29.39%
10.74%
1.21
5
48.57%
9.50%
41.93%
22.14%
28.16%
18.22%
1.92
5
54.92%
8.88%
36.77%
24.23%
24.88%
21.25%
2.39
6
50.47%
10.10%
48.96%
25.51%
33.19%
20.58%
2.04
8
42.67%
7.89%
69.92%
30.60%
47.78%
20.45%
2.59
9
39.56%
7.91%
99.27%
16.90%
17.99%
14.09%
1.78
Table 4: Bounding the DCP for multiclass classifiers with known confusion matrices; Natality data with k-Nearest- Neighbor classifier. Table columns in Table 1.
Test
Lower Bound
Upper Bounds
Best Ratio
Average
Greedy
Average LLM
Greedy+LMM
Attendant
1.80%
28.53%
1.82%
1.82%
1.82%
1.01
Father Race
1.17%
46.54%
1.20%
1.18%
1.18%
1.01
Mother Race
0.61%
21.47%
0.69%
0.62 %
0.62 %
1.02
Payer
1.73%
54.61%
1.79%
1.76%
1.75% %
1.01
12

---

Disparate Conditional Prediction in Multiclass Classifiers
Table 5: Bounding the DCP for multiclass classifiers with known confusion matrices; US Census data set with the neural network-based classifiers. Table columns as in Table 1.
# Labels
Error
Lower Bound
Upper Bounds
Best Ratio
Average
Greedy
Average+LM
Greedy+LM
12.76%
2.36%
20.19%
3.46%
3.04%
3.03 %
1.28
12. 12%
1.43%
23.16%
2.06%
2.75%
1.84 %
1.28
8.95%
1.27%
18.89%
2.05%
1.75%
1.75%
1.38
8.96%
1.52%
16.63%
1.94%
1.83%
1.77% %
1.16
6.04%
2.42%
22.88%
3.52%
2.96%
2.96 %
1.22
8.26%
0.86%
34.80%
3.53%
2.24%
2.24%
2.60
3
13.31%
0.01%
68.05%
27.12%
0.01%
0.02%
2.45
3
8.07%
0.63%
24.58%
1.41%
0.79%
0.78%
1.23
10.39%
1.53%
40.93%
1.56%
2.06%
1.56 %
1.02
4.08%
0.93%
41.29%
4.07%
2.51%
2.17% %
2.33
4.09%
0.78%
69.65%
12.97%
1.89%
0.99 %
1.28
5.40%
2.44%
66.73%
41.57%
3.18%
2.53%
1.04
17.48%
3.55%
46.89%
4.35%
4.24%
4.05 %
1.14
5
21.35%
6.02%
64.82%
8.01%
8.86%
7.67% %
1.27
17.76%
2.49%
66.61%
6.01%
4.30%
3.67 %
1.47
26.69% 8
2.64%
68.10%
14.22%
5.66%
4.28%
1.62
18.19%
2.95%
80.76%
3.13%
4.15%
3.12%
1.06
Table 6: Bounding the DCP for multiclass classifiers with known confusion matrices; Natality data set with the neural network classifier. Table columns as in Table 1.
Protected Attribute
Lower Bound
Upper Bounds
Best Ratio
Average
Greedy
Average+LM
Greedy+LM
Attendant
1.03%
26.25 25.25%
1.05%
1.04%
1.04%
1.01
Father Race
0.67%
50.53%
0.73%
0.67% %
0.67 %
1.01
Mother Race
0.58%
13.25%
0.58%
0.58 %
0.58
1.01
Payer
1.21%
55.86%
1.21%
1.21
1.21
1.00
13

---

Disparate Conditional Prediction in Multiclass Classifiers
Table 7: Comparing the output of the minDCP local optimizer (LO) to the DCP range calculated for US Census classifiers for the neural network classifiers. The ranges are derived from Table
US Census
Neural Network
Labels
minDCP LO
true DCP
3
0.97%
2.36% - -3.03%
3
0.63%
1.43% 1.84%
3
0.68%
1.27% 1.75%
3
0.53%
1.52% 1.77%
3
1.23%
2.42% 2.96%
3
0.56%
0.86%
2.24%
3
0.01%
0.01%
3
0.26%
0.63% 0.78%
3
0.90%
1.53% - 1.56%
4
0.47%
0.93% 2.17%
5
0.70%
0.78% 0.99%
5
1.36%
2.44% 2.53%
5
1.09%
3.55% -4055%
5
3.16%
6.02% -7.67%
6
0.80%
2.49% 3.67%
8 1.77%
2.64% 4.28%
1.63% 9
2.95% 3312%%
Table 8: Comparing the output of the minDCP local optimizer (LO) to the DCP range calculated for the Natality data set for the neural network classifier. The ranges are derived from Table
Natality
Neural Network
Protected Attribute
minDCP L.O
true DCP
Attendant
0.15%
1.03% 1.04%
Father Race
0.24%
0.67%
Mother Race
0.10%
0.58%
Payer
0.13%
1.21%
14

---

Disparate Conditional Prediction in Multiclass Classifiers
Table 9: Calculated minDCP local optimizers for the UK elections data. In each line, the election data from the listed baseline year was used to predict the vote in the listed prediction year.
Election years
Baseline
Prediction
# protected attribute values
minDCP LO
1918
1922
12
6.36%
1922
1923
13
8.57%
1923
1924
13
3.26%
1924
1929
13
4.92%
1929
1931
13
5.14%
1931
1935
13
3.11%
1935
1945
13
5.69%
1945
1950
12
4.75%
1950
1951
12
3.79%
1951
1955
12
5.54%
1955
1959
12
2.40%
1959
1964
12
2.16%
1964
1966
12
1.37%
1966
1970
12
1.32%
1970
1974 (Feb)
12
2.69%
1974 (Feb)
1974 (Oct)
12
6.28%
1974 (Oct)
1979
3.67%
1979
1983
11
3.23%
1983
1987
12
1.43%
1987
1992
12
4.21%
1992
1997
11
5.25%
1997
2001
12
5.25%
2001
2005
12
4.83%
2005
2010
12
5.26%
2010
2015
3.96%
2015
2017
12
5.54%
2017
2019
11
5.24%
15

---

Disparate Conditional Prediction in Multiclass Classifiers
B. An Additional Experiment
In this experiment, we studied a data set on US education (USDA Economic Research Service, 2021), which provides the percentage of various levels of education attainment (e.g., high school, college) in each US state in each decade. Here too, we calculated minDCP for a hypothesized classifier that predicts the education level to be distributed the same in each state in each decade. The protected attribute as set to be the state. Table 10 provides our results. Here, we found significant differences in the DCP of change patterns in different decades, indicating fairly constant behavior of this measure of divergence between states. This type of analysis can be used for exploratory research on social questions.
Table 10: Calculated mi n nDCP upper bounds for the US education data
Year
Baseline
Predicted
minDCP upper bound
1970
1980
2.38%
1980
1990
2.94%
1990
2000
2.22%
2000
2015-2019
2.32%
C. The Greedy Initialization Procedure
We provide here the full details of the greedy initialization procedure presented in Section 5.
Let f := (fylwey, where fg y + y, be label mappings conditioned on the true label y, which can map some predicted labels to the same transformed label. For given classifier C with distribution D, let C(f] be hypothetical classifier that predicts fy whenever the true label is y and C' would predict ÿ. For a given distribution P over (Y, Y, A), let P[f] be the distribution of (Y) A). Then, D[f] is the distribution determined by C[f). is easy to see that (CP(C I DCP(C). This is because the equality DV = (1-nğ) over n for C f] can never result in solution of a higher value than minimizing for C. We use this observation devise an iterative greedy optimization procedure.
/ ) DV N implies that also [X[ = (1- (1-n))D"(i [[
Thus, minimizing
For E [K- 1]. let f; := (fry)eyy be an indexed set of label mappings, fu, y + y, defined as follows. Let y/ be the é'th label in y that is different from y. Denote 3%- = {y. "i......... y.). Note that Vx-1 = y For E [k - 2]. define (J) = j- T[j E 2/ y T[ & Dil. Note that ft,y can be calculated from the image of fi-1.y- Hence, C [f]] is refinement of 1. In addition, fx-1, is the identity. Thus, the following monotonicity property holds:
DCP(C(A)) < DCP(C(()) .... DCP(C((:-1)) DCP((C).
Moreover, DCP(fi) can be calculated exactly as in case of binary classification, since the range of fi includes only y and y1. Based on these observations, we define a greedy procedure for calculating an assignment for ag to initialize the minimization in Eq. (5).
Let a² [i] be row y of the confusion matrices of D[r.]. Then coordinatesj jEV:- of [g are the same as those of a k-1 390 We have
and coordinate ys has the value a.y: Σ}=
11) = (ax s DCP, (a)l)) ... -D)) (a))
The greedy procedure first calculates assignment for [ [1] that obtains the value of DCP MCCyy(a/a (1)) This is binary problem, which can be solved exactly following Sabato & Yom-Tov (2020). Then, at each iteration i + 1 for i E [k [42),, 2). a local minimum ag ( + 1] for DCP, [ + +1] is calculated by constraining of + 1] to have the same coordinates as af on V and minimizing over ob ,,8 can be solved exactly, as follows.
ub: 30-+1 such that their sum is equal to coordinate in ag [i] This minimization
Denote the value of coordinate y; a by = 1- -EEE v0 Minimizing the objective of DCP, (a + 1)) subject
16

---

Disparate Conditional Prediction in Multiclass Classifiers
to the constraints resulting from og
[i] is equivalent solving the following problem:
Minimize 9 :
Σ
WaTT
max
moxxmaxn((e "a"" 7,(0p 1ii-1 (ag
DED;
aEA
s.t.
0
y9:
and ag + %b"
v3++1 7.
Letting va == maXgeMi-1 7/ vy
agd) this is equivalent to
Minimize vuL E(0,>] aEA
Σ
my max n/ag" vn aaa ",)))<l -ogg og (ga++1))
Similarly to the case of binary classification, this objective is one me-dimensional, and concave in each of the intervals defined by the inflection points of the instances and the values for which any two of the expressions in the maximum are equal. Denote this set of points by M... Then the objective above is minimized by one of the values in the following set: M. U (aa2 JoE JOEAA U {āe ( AAEA U {0, 7}. Repeating this procedure until iteration = k - 1, we obtain an assignment for ag which can be used to calculate an upper bound for DCP,(a')
Since the ordering of the labels in the greedy procedure is arbitrary, it is possible to attempt several different orderings and select the one that obtains the smallest DCP value. In our experiments, we tried 10 random orderings in each upper bound calculation.
D. More Details on the Local Optimization Procedure
Here we provide more details on the minimization of Eq. (15). Given the split in Eq. (16), the last constraint in Eq. (15) becomes
nla a.j) S c/ m (a ( 5 cg
(a(a y a. S c2
and now the constraints does not include singularity points, and can be locally approximated by two linear functions, one for M and one for 722 (see Figure 2). Explicitly, the Taylor approximation of mı. for i = 1, are given by:
8m: tn +
On cb
(1(a + ea, + tb) R (n(aab) b)
da
ab
where
8m
b
Bm
Oma 80
(1-b) (I-a)
and
Ona 8h
80
8b
T-a'
Given the first order Taylor approximations above, form the LP approximation of Eq. (15) around an iterate ((() {ā", HP, 20 eny as follows:
Minimize (a (a*),(H*),,(() ((ee)
Σ Ww c
(17)
s.t. 0 S a 1
Vy E [k],
0 0 HD <
Ay E [k],
chc <
Ay E [k],
(a", 1x) 1
Vy E [k).
H11, = 1,4
Ay E [k)]
Σ un 0.
pd
vg E [k)) a E [|AA]].
Th (a g. h2 +
am
(a a
an ab
(h RM cll. Vy [k), E [|]], i 1,2,
Ba
Eq. (17) is an LP problem which is solved at each iteration by an LP solver, for which we use the sci scipy- py opt imi ze library. In addition to the box constraints of [0, 1] for all variables, it includes 2 2 k- |A| + k equality constraints, and 2 12? [A] inequality constraints. It can be seen that the number of inequality constraints is rather high, and as a result, so is the computational complexity of the algorithm if run as is. However, many of these constraints are not active in the solution, and any case we limit the step size of our algorithm. Hence, we can ease the difficulty of the I.P problem by
17

---

Disparate Conditional Prediction in Multiclass Classifiers
both limiting the search space of the LP solver, and removing the inequality constraints that seem be inactive in the solution. To this end, remove the inequality constraints where () z: Fag)) -1, we expect these not to be active the solution. Furthermore, we use maximum step size so that || - o a < T. and H HH < where || 2o
is the maximum norm. This condition is trivially incorporated in the box constraints Eq. (17). Finally, given the LP approximation above, the solver of Eq. (15) follows the same lines as Alg. 1.
As in Section 6, numerical instabilities arise when a is too close 0 or Thus, here as well we restrict these values be in the segment [e, e]. this time as optimization variables through the box constraints. Also, we update the values ph be pd kc) k k + guarantee solution for Eq. (15) after updating the box constraints for a
Convergence of Algorithm Our problem contains the non-linear functions 7, which are approximated by linear functions. For general non-linear programming problem, sequential linear programming (SLP) methods converge linearly if all functions are smooth. That is because they do not use Hessian information, and their whole purpose is to handle the constraints efficiently (determine who is active and who is not). If one uses Hessian information, we get sequential quadratic programming (SQP) and the convergence asymptotically quadratic once the active set of constraints is identified, similar Newton's 's method (Nocedal & Wright, 2006). For an SLP method like in Algorithm to have smooth constraints, and for that we use the split of presented in Eq. (16) and detailed above. Furthermore, limit the size of the steps to be of size at most т. This approach is called a Trust Region method, and is commonly used with sequential quadratic or linear programming methods. The method was analyzed in (Kiessling et al., 2022) for a case that is similar to ours, where the objective of the constrained problem is linear, like in Eq. (9) and Eq. (15). It is shown that the convergence of the SLP method is linear, and the rate depends on the radius the trust region method (T, in our case). In Figure we show the convergence of our method for solving Eq. (15) for convex 17, so that the problem convex and the solutions that are obtained by the method using all trust regions are equivalent. Specifically, to demonstrate the convergence we used
converge linearly, we first need also
aa -ba ab (1 a1- -1 -1-b)(1 - (1
b <
Meonver (a, b)
b > a, b a,
(18)
instead of Eq. (4), and got the plots in Figure 4 for various maximal step sizes T, for solving Eq. (15) for the labor dataset. Here, the plots show that the method is slower as T is smaller, since the algorithm is constrained to be slower. However, in some cases, the inner LP solution can result a stagnate direction, and then decreasing T as shown in (Kiessling et al., 2022) can mitigate this. our original problem, 7 and the whole problem are non-convex, hence the algorithm can converge to different local minimum for each value of r. For the problems reported in this paper, we used r = 0.2 which seemed to work best, and decreased when the LP solver failed to converge.
max, 0lop-0.2
stap-d 25
025
20
Darution
Figure 4: The convergence of Algorithm for different trust region (maximal step size) parameters т.
18


Reviews:
[{"review_id": "n6r6Kx6oeN", "reviewer": "Reviewer_XH1z", "summary": "This work extends disparate conditional prediction, which measures the deviation from equalized odds, to multiclass classification problems. As the confusion matrices are not available, the authors derived the lower bound and the upper bound of the DCP of a multiclass classifier. The upper bounds are obtained using a local minimization procedure. To overcome the non-smoothness, the functions are split into locally linear parts, and the solutions are obtained by a combination of sequential solutions of standard linear programming problems.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful review and comments. Please find below our responses to your comments and questions. \n\n**Comment**: There is no proof for the theoretical claims.\n\n**Reply**: All theoretical claims are proved, either in the body of the paper or in the appendix. If there are any theoretical claims for which you believe proofs are missing, we would be grateful if you could point them out to us.\n\n**Comment**: In the experiments, only decision trees and nearest neighbor classifiers are examined. However, researchers would expect more complicated models, such as SVM and neural networks.\n\n**Reply**: The types of classifiers were chosen to be suitable for the low-dimensional categorical data-sets that we are reporting. Since our methods only use the prediction rates of each label in the output classifier, the complexity of the models does not have any effect on the usage of our methods. In addition, if a classifier is 100% accurate in its predictions, then the equalized odds criterion holds trivially, in which case the DCP would be zero. We appreciate the suggestion to extend our experiments - we will add experiments in which the classifiers are generated by SVMs and neural networks to the final version of the paper. \n\n**Comment**: originality and novel contributions\n\n**Reply**: While we build on a previous work, which defined binary DCP, the definitions and methods in that previous work are not applicable to multiclass classifiers, since they heavily rely on the binary nature of the problem. The calculation of the extension of DCP to the multiclass setting is challenging, and all of our methods for bounding the DCP are completely novel. As we discuss in the paper, the computational problems that arise in the multiclass case are not trivial and cannot be solved efficiently by out-of-the-box solvers. For instance, we use a combination of sequential linear programming with a function split to handle the non-smoothness. In addition, we handle instabilities encountered by the LP solvers when they deal with extremely high derivatives imposed by the $\\eta$ function. Thus, our contributions are novel and original. \n\n**Question**: What does the nuisance distribution mean in Section 4? And what is its insight on real world data?\n\n**Reply**: The nuisance distribution represents the deviation of the classifier's conditional probabilities on each sub-population from the baseline conditional probabilities. This is a modeling construct that was used to derive the DCP measure in the previous work that we build upon. In this paper, we extend this to the multiclass case. In real-world data, a nuisance distribution with a higher mixture parameter ($\\eta_a^y$) indicates that a larger part of the population is classified with conditional probabilities that deviate from the baseline conditional probabilities, thus indicating that the classifier is less fair.\n\n**Question**: What is the convergence rate of the proposed Algorithm 1?\n\n**Reply**: Our problem contains the non-linear $\\eta$ functions, which are approximated by linear functions. For a general non-linear programming problem, sequential linear programming (SLP) methods converge linearly if all functions are smooth. That is because they do not use Hessian information, and their whole purpose is to handle the constraints efficiently (determine who is active and who is not). If one uses Hessian information, we get sequential quadratic programming (SQP) and the convergence is asymptotically quadratic once the active set of constraints is identified, similar to Newton’s method [1]. For Algorithm 1 to converge linearly, we first need to have smooth constraints, and for that we use the split of $\\eta$ presented in Equation (16) and detailed in Appendix D. Furthermore, we also limit the size of the steps to be of size at most $\\tau$, as detailed in Appendix D. This approach is called a Trust Region method, and is commonly used with sequential quadratic or linear programming methods. The method was analyzed in [2] for a case that is similar to ours, where the objective of the constrained problem is linear, like in Eq. (9) and Eq. (15). It is shown that the convergence of the SLP method is linear, and the rate depends on the radius of the trust region method ($\\tau$, in our case). We will add this discussion to the final version of the paper, including plots demonstrating the convergence rate for different choices of $\\tau$ in our problems.  \n\n[1] Nocedal J, Wright SJ, editors. Numerical optimization. New York, NY: Springer New York; 1999.\n\n[2] Kiessling D, Zanelli A, Nurkanović A, Gillis J, Diehl M, Zeilinger M, Pipeleers G, Swevers J. A feasible sequential linear programming algorithm with application to time-optimal path planning problems. In 2022 IEEE 61st Conference on Decision and Control (CDC) 2022 Dec 6 (pp. 1196-1203). IEEE.", "claims_and_evidence": "The claims made in the submission are clearly supported by theoretical analysis on the lower bound and the upper bound.", "methods_and_evaluation_criteria": "The proposed methods look seamlessly reasonable.", "theoretical_claims": "There is no proof for the theoretical claims.", "experimental_designs_or_analyses": "In the experiments, only decision tree and nearest neighbor classifiers are examined. However, researchers would expect more complicated models, such as SVM and neural networks.", "relation_to_broader_scientific_literature": "The contribution of this paper is related to audit the fairness of multiclass classifiers.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "- The core contribution of this paper builds upon the criteria established by Sabato & Yom-Tov (2020), which raises questions about its originality and novel contributions.\n- The approach to determining lower and upper bounds demonstrates sound optimization approach to addressing the problem.\n- The experiments are only evaluated on simple tree-based and nearest neighbor models.", "other_comments_or_suggestions": "The paper is clearly written. I did not find any typo.", "questions_for_authors": "- What does the nuisance distribution mean in Section 4? And what is its insight on real world data?\n- What is the convergence rate of the proposed Algorithm 1?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "83xMc7fL0S", "reviewer": "Reviewer_PiSi", "summary": "This paper provides methods to bound the unfairness of multiclass classifiers. In particular, they extend the Disparate Conditional Prediction (DCP) metric from prior work to the multiclass setting. The DCP measure for a classifier quantifies the fraction of the population for whom the classifier's prediction distribution (conditional on the group and true outcome) differs from that of an equalized odds fair classifier. The paper shows how this metric can be generalized to the multiclass setting and forward methods to bound the DCP of any classifier with and without access to the group-conditional confusion matrices. They demonstrate the efficacy of this approach over multiple datasets, with the proposed evaluation approach achieving the sharpest bounds on the DCP of decision trees and kNNs trained on the datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful review and comments. Please find below our response to your comments and questions. \n\n**Question 1**: What are the limitations of the other metrics in multiclass settings?\n\n**Reply**: Standard unfairness measures (see the Related Work section) have several disadvantages that are overcome by DCP. While these were discussed in the work that suggested binary DCP, we will add a relevant discussion to the paper, to highlight these issues and make the paper self-contained. The disadvantages include the following:\n\n- Measures based on differences discount differences that are small in value, although they could be meaningful in terms of fairness. This is especially problematic when there is class imbalance. For instance, if the probability of predicting a certain label is 0.1 in one sub-population and 0.2 in another, this would be identified as significantly more unfair than if the probabilities are 0.001 and 0.002, respectively. However, when this label is very rare to begin with (such as in cancer diagnosis), these differences could indicate meaningful unfairness. Previous measures that try to correct this, such as ratio-based measures, suffer from other issues, such as a lack of boundedness and difficulty achieving normalization that retains the meaning of the measure. The DCP measure does not have these issues, since it always identifies the fraction of the population that is affected by the disparate classification probabilities, which is inherently normalized and meaningful, regardless of class imbalance.\n\n- Most previous works only consider cases with two sub-populations. Standard extensions to multiple sub-populations maximize over pairwise comparisons between sub-populations. However, this disproportionally penalizes classifiers in which a single sub-population is treated unfairly, in comparison to classifiers in which several sub-populations are treated unfairly, since both types of classifiers would be deemed to have the same amount of unfairness. The DCP measure uses an optimal common baseline and sums over all sub-population differences from the baseline, thus properly differentiating between classifiers of significantly different fairness levels. \n\n- The lack of quantifiable interpretability of the measures proposed in the literature implies that they are not guaranteed to have a consistent interpretation of unfairness across all possible classifiers and confusion matrices. While we have listed above several specific issues, trying to solve these issues by fixing the measure in an ad-hoc manner leads to other issues, and so forth. The quantifiable interpretability of DCP ensures that the value of the measure is meaningful in all possible scenarios, and that this meaning is consistent, so that one can also compare the value of the measure for different classifiers and obtain meaningful conclusions.\n\n**Question 2**: What's the purpose of the experiments on UK election patterns and US education data and what does the DCP quantification mean in these settings?\n\n**Reply**: \nThe experiments are intended to demonstrate how our approach can be used in diverse settings. Specifically, as discussed on page 8 of the paper, our analysis of the UK election dataset shows how political scientists could identify regional variability in voting patterns using the DCP measure. In the education dataset, our goal was to test whether educational attainment progressed more (or less) in some states compared to others. In this case, consider the scenario where authorities do not publish their achievements (or lack thereof) in disadvantaged areas, and only publish aggregate information. The DCP measure can help uncover such cases. \n\n**Question 3**: Regarding the gap between the upper bounds from Greedy and Greedy+LM methods, what's the reason for the change in this gap across #labels?\n\n**Reply**: This is indeed an interesting question. We conjecture that the greedy approach is less tight when there are more labels, because it relies on iterative solutions for a binary version of the problem. When the number of labels is larger, there are exponentially more possible combinations, and so we believe this leads to the greedy initialization being more likely to follow a sub-optimal iterative path. \n\n**Comment**: [On election patterns] it seems to me that any such inference can only be made when the classifier is fairly accurate. \n\nIn the election experiment, the classifier predicts by assuming no changes in voting patterns between consecutive elections. Thus, we do not expect the classifier to always be accurate. On the contrary, its inaccuracy and unfairness are the objects of study, as they reveal changing voting patterns, and a variability of changes between regions, as measured by the DCP.\n\n**Comment**: Difficulty of interpreting Tables and a Figure.\n\n**Reply**: Thank you for the comment, we will improve the readability of these in the final version of the paper.", "claims_and_evidence": "The main claim of the paper is that DCP is a useful metric for assessing the fairness of multiclass classifiers and can be evaluated effectively using the proposed methodology. Both claims seem well-justified. \n\nFor the former claim (on the usefulness of DCP), the introduction does a good job of motivating the necessity of a DCP-based method for multiclass classifier audits. However, there seems to be heavy reliance on prior works for this motivation (e.g.,  Sabato & Yom-Tov for DCP and  Wang et al. for limitations of other metrics in the multiclass setting). I would encourage the authors to expand the discussion/examples on the limitations of prior methods for multiclass classifier audit and the usefulness of DCP to make the paper more self-contained. \n\nI am also curious if any of the limitations of the other metrics in multiclass setting can be demonstrated within the paper itself. For example, in the setting where one has access to the group confusion matrices, ${M_a}$, one can trivially construct quantify unfairness as $max_{a_1, a_2} || M_{a_1} - M_{a_2}||_F$, where $||\\cdot||_F$ denotes the Frobenius norm. Its unclear whether the the main issue with this (and other prior ways of quantifying fairness for multiclass settings) is interpretabality of the metric or if they have fail to capture some crucial aspects of unfairness.", "methods_and_evaluation_criteria": "The methods used to estimate DCP in the multiclass setting are well-described and look correct.\n\nFor the empirical analysis, most of the datasets used also make sense. However, I don't completely understand the purpose of the experiments on UK election patterns at the end of Section 7 and on US education data in the appendix. Specifically, it's unclear what the DCP criteria would imply in this case. The paper claims that a \"high DCP value of such a classifier would indicate a possibly large difference between voting pattern changes across regions\". However, it seems to me that any such inference can only be made when the classifier is fairly accurate and it's unclear if that's true in this case.", "theoretical_claims": "No theoretical claims.", "experimental_designs_or_analyses": "The experimental design seems sound. However, Table 1, Table 2, and Figure 3 are quite difficult to read and interpret in their current form. I would encourage adding a more detailed caption and labels as well as increasing the font size of all tables and plots in the main body.", "relation_to_broader_scientific_literature": "The paper adds to the literature on fairness audits methods. Specifically, it focuses on how to perform accurate fairness audits for multiclass classifiers. To do so, it employs the DCP measure from the prior work of Sabato & Yom-Tov (2020) and generalizes it to the multiclass setting. \n\nTo my knowledge, prior work on fairness hasn't focused much on interpretable extensions to multiclass settings. And the trivial extensions from binary to multiclass setting that first come to mind are of the type that I stated in the earlier section (using matrix norms), which may be easier to compute but not necessarily easy to interpret. In that sense, I like the formulation proposed in the paper and can it see being broadly relevant for audits of other unfair human/automated decision processes as well.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "I found the Greedy initialization technique interesting. Table 1 shows that in some cases (e.g., when #labels=3) Greedy initialization alone leads to significant improvement in the upper bound, and running LM leads to a small improvement beyond that. In other cases (e.g., when #labels=8, 9), there is a larger gap between Greedy and Greedy+LM. I am curious if this is related to the number of labels or if its some artifact of how the greedy initialization is done.", "other_comments_or_suggestions": "No other comments", "questions_for_authors": "1. What are the limitations of the other metrics in multiclass setting and can these limitations be clearly demonstrated within the paper itself (e.g., using the datasets used for empirical analysis)?\n\n2. What's the purpose of the experiments on UK election patterns and US education data and what does the DCP quantification mean in these settings?\n\n3. Regarding the gap between the upper bounds from Greedy and Greedy+LM methods, what's the reason for the change in this gap across #labels? It seems this gap is smaller when #labels is small, but not sure if that trend will hold across datasets.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UiSj0BQpSn", "reviewer": "Reviewer_1f59", "summary": "The authors proposed a multi label extension of the framework developed by Sabato & Yom-Tov (thats only binary) that allows to compute bounds on fairness metrics only using population level quantities. \n\nDcp is determined by the matrix, and the proportions and a function of conditional prediction rates and such that there is an efficient way on computing it, the authors then derive a multiclass version of DCP. Then the authors compute an analytical lower bound on the DCP and then a procedure to upper bound the multiclass version of the DCP. This procedure is a loop of LPs which can be solver efficiently. Finally the authors present a way to compute a bound on the DCP with out the need of having all the conditional proportions (the per class matrix), in particular there is no access to the classifier, just to its population level frequencies.\n\nWeakness \n- The writing of the paper is confusing. The derivation of the multiclass DCP should be a theroem. Also the metric DCP lacks motivation.\n\nStrengths\n-  The authors propose an efficient algorithm to compute bounds on DCP.\n- The algorithms can be computed efficiently", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful review and comments. Please find below our response to your comments and questions. \n\n**Comment**: The derivation of the multiclass DCP should be a theorem.\n\n**Reply**: Thank you for the suggestion. We will add a formal theorem statement for the derivation of DCP. \n\n**Comment**: the metric DCP lacks motivation.\n\n**Reply**: The main motivation of the DCP, as discussed in the Introduction, is that it has a consistent interpretable meaning as a fraction of the population, regardless of the number of protected attribute values, the number of classes, or the degree of class imbalance. Thus, DCP is useful for interpretably auditing and comparing classifiers. We will add a discussion of the disadvantages of other previously suggested measures, to highlight the issues that are overcome by the use of DCP. These include the following:\n\n- Measures based on differences discount differences that are small in value, although they could be meaningful in terms of fairness. This is especially problematic when there is class imbalance. For instance, if the probability of predicting a certain label is 0.1 in one sub-population and 0.2 in another, this would be identified as significantly more unfair than if the probabilities are 0.001 and 0.002, respectively. However, when this label is very rare to begin with (such as in cancer diagnosis), these differences could indicate meaningful unfairness. Previous measures that try to correct this, such as ratio-based measures, suffer from other issues, such as lack of boundedness and difficulty achieving normalization that retains the meaning of the measure. The DCP measure does not have these issues, since it always identifies the fraction of the population that is affected by the disparate classification probabilities, which is inherently normalized and meaningful, regardless of class imbalance.\n\n- Most previous works only consider cases with two sub-populations. Standard extensions to multiple sub-populations maximize over pairwise comparisons between sub-populations. However, this disproportionally penalizes classifiers in which a single sub-population is treated unfairly, in comparison to classifiers in which several sub-populations are treated unfairly, since both types of classifiers would be deemed to have the same amount of unfairness. The DCP measure uses an optimal common baseline and sums over all sub-population differences from the baseline, thus properly differentiating between classifiers of significantly different fairness levels. \n\n- The lack of quantifiable interpretability of the measures proposed in the literature implies that they are not guaranteed to have a consistent interpretation of unfairness across all possible classifiers and confusion matrices. While we have listed above several specific issues, trying to solve these issues by fixing the measure in an ad-hoc manner leads to other issues, and so forth. The quantifiable interpretability of DCP ensures that the value of the measure is meaningful in all possible scenarios, and that this meaning is consistent, so that one can also compare the value of the measure for different classifiers and obtain meaningful conclusions.", "claims_and_evidence": "Yes, the experiments and proved are correct and relevant.", "methods_and_evaluation_criteria": "They do, but the DCP is not propperly motivated", "theoretical_claims": "Refer to summary", "experimental_designs_or_analyses": "Refer to summary", "relation_to_broader_scientific_literature": "I am somehow familiar with the fairness literature but not with the main work the authors cite (Sabato and Yom-tov)", "essential_references_not_discussed": "Refer to summary", "other_strengths_and_weaknesses": "Refer to summary", "other_comments_or_suggestions": "...", "questions_for_authors": "No questions for the authors.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GJehyeBL1t", "reviewer": "Reviewer_PQXZ", "summary": "This paper introduced the measure of Disparate Conditional Prediction (DCP) to multi-class classifiers based on equalized odds. They provided optimization methods for scenarios with and without the access to confusion matrices and justified the algorithm efficacy by using decision trees and NN models on three datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your helpful review and comments. Please find below our response to your comments and questions. \n\n**Comment**: The results comparisons are among different strategies or with the true DCP. It would be better to simply declare this is the best choice if there are not any feasible baselines.\n\n**Reply**: We have included different strategies for ablation purposes, as we believe it strengthens the justification of our use of the chosen strategies.\n\n**Comment**: Maybe more fairness audit research should be discussed to better position this work.\n\n**Reply**: Our work falls within the realm of fairness auditing using only aggregate statistics, without assuming access to the classifier. This is in contrast with many other works, which require access to the classifier and the ability to query it. The challenge of auditing fairness using limited information has received significant attention in recent years, as evident, for example, in [1] & [2]. Our work is unique, in that it is the first, to our knowledge, to address the multiclass setting.\n\nThe state of fairness audit research is discussed in the first three paragraphs of the Introduction, and in the second paragraph of the Related Work section. We will expand the discussion on recent works on fairness auditing with limited information in the final version of the paper.\n\n[1] Pinzón, Carlos, Catuscia Palamidessi, Pablo Piantanida, and Frank Valencia. \"On the incompatibility of accuracy and equal opportunity.\" Machine Learning 113, no. 5 (2024): 2405-2434.\n\n[2] Jialu Wang, Yang Liu, and Caleb Levy. Fair classification with group-dependent label noise. In Proc. of the 2021 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’21, page 526–536, New York, NY, USA, 2021b. Association for Computing Machinery.\n\n\n**Comment**: What we are expected to see or understand through Figure 1. \n\n**Reply**: Figure 1 provides a visualization of the function $\\eta$, demonstrating that it is piecewise concave. We will refer to the figure when discussing the function's properties and explain the visualization.\n\n**Comment**: Above Eq. 2 we see $\\eta$’s definition, while it takes two input variables in Eq. 4.\n\n**Reply**: Above and in Eq. 2, we use $\\eta_a^y$, which is a scalar, and $\\eta_a$, which is a vector of scalars. $\\eta$ without superscripts or subscripts is a function that takes two arguments. We will clarify this in the final version.\n\n**Numbered Comment 1**: In Eq. 4, both w and $\\pi$ are not dependent on the classifier according to their definitions in section 3, but they are said determined by C below Eq. 3.\n\n**Reply**: Thank you for the comment. Indeed this is a typo, since only $M_A$ is determined by C. We will fix this in the final paper. \n\n**Numbered Comment 2**: Eq. 2 executes addition group by group, then will it lead to a trivial solution? \n\n**Reply**: As our analysis below Eq (2) shows, the solution is not trivial, because of the constraint that the values of $\\eta_a^y$ must be consistent with the distribution D. \n\n**Question 1**: Equalized odds emphasizes true and false positive rates, which are well-interpreted in binary classification. It would be helpful if the authors could provide some examples illustrating the significance of equalized odds in multi-class scenarios.\n\n**Reply**: In multiclass scenarios, the multiclass equalized odds criterion measures any differences in conditional prediction probabilities between sub-populations. This includes not only the difference in the rate of correct predictions as in the binary case, but also the types of prediction mistakes. For instance, if a patient's heart attack is misdiagnosed as an anxiety attack (which may mean the patient is denied care), this is significantly different than being misdiagnosed as a stroke (which may lead to delayed care). If some sub-populations incur more of a certain type of misdiagnosis error, this could indicate bias in diagnosis, as well as lead to undesired differences in treatment.  This is one example of the importance of the multiclass equalized odds criterion. We will add a discussion with additional examples to the final version of the paper.\n\n**Question 2**: I understand this work currently focuses on auditing a trained classifier. But I am curious have you considered integrating the proposed DCP into a in-processing fairness method? \n\n**Reply**: We agree that this is an important question, and we intend to study it in future work.", "claims_and_evidence": "DCP is extended to multi-class scenarios, and I think the claims are well evidenced in the paper.", "methods_and_evaluation_criteria": "The proposed DCP measure looks good, and some standard datasets are applied.", "theoretical_claims": "I read through the theoretical analyses but was unable to verify their correctness.", "experimental_designs_or_analyses": "The results comparisons are among different strategies or with the true DCP. It would better to simply declare this is the best choice if there is not any feasible baselines.", "relation_to_broader_scientific_literature": "I am unsure whether this topic holds significant importance in fairness research today. Maybe more fairness audit research should be discussed to better position this work.", "essential_references_not_discussed": "This work is based on Sabato&Yom-Tov (2020) and I think the most related works are included in the paper.", "other_strengths_and_weaknesses": "Strengths: The proposed DCP for multi-class scenarios is well presented, and I believe some readers in the fairness community will find this work interesting. Although I may not fully grasp every detail, I find the paper to be of good quality.\n\nWeaknesses:\n1. Some figures are presented without further explanation. For example, what we are expected to see or understand through Figure 1. The authors should not just simply refer to it (line 146).\n2. Some notations are not easy to understand. For example, above Eq. 2 we see \\eta’s definition, while it takes two input variables in Eq. 4I found this part confusing when reading here.", "other_comments_or_suggestions": "1. In Eq. 4, both w and \\pi are not dependent on the classifier according to their definitions in section 3, but they are said determined by C below Eq. 3.\n2. Eq. 2 executes addition group by group, then will it lead to a trivial solution?", "questions_for_authors": "1. Equalized odds emphasizes true and false positive rates, which are well-interpreted in binary classification. It would be helpful if the authors could provide some examples illustrating the significance of equalized odds in multi-class scenarios.\n2. I understand this work currently focuses on auditing a trained classifier. But I am curious have you considered integrating the proposed DCP into a in-processing fairness method? What is the challenge of doing so?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper develops methods for auditing multiclass classifiers for equalized odds. A key contribution is generalizing Disparate Conditional Prediction (DCP) to multiclass prediction tasks. The authors develop methods for upper and lower bounding DCP.

The reviewers were unanimous in recommending acceptance. They found the paper well-written, well-motivated, and that the generalization of DCP to multiclass predictions is of interest to the community studying fairness in machine learning. I agree with this assessment, and recommend acceptance.
Decision: Accept (poster)