Superhuman Fairness

Group fairness measures are primarily defined by confusion matrix statistics (based on labels $y_{i}\in\{0,1\}$ and decisions/predictions $\hat{y}_{i}\in\{0,1\}$ produced from inputs ${\bf x}_{i}\in\mathbb{R}^{M}$) for examples belonging to different protected groups (e.g., $a_{i}\in\{0,1\}$).

We focus on three prevalent fairness properties in this paper:

• •

  Demographic Parity (DP) (Calders et al., 2009) requires equal positive rates across protected groups:

  $$\mathrm{P}(\hat{Y}=1|A=1)=\mathrm{P}(\hat{Y}=1|A=0);$$

• •

  Equalized Odds (EqOdds) (Hardt et al., 2016) requires equal true positive rates and false positive rates across groups, i.e.,

  $$\mathrm{P}(\hat{Y}\!=\!1|Y\!=\!y,A\!=\!1)=\mathrm{P}(\hat{Y}\!=\!1|Y\!=\!y,A\!=\!0),\;\;y\in\{0,1\};$$

• •

  Predictive Rate Parity (PRP) (Chouldechova, 2017) requires equal positive predictive value ($\hat{y}=1$) and negative predictive value ($\hat{y}=0$) across groups:

  $$\mathrm{P}(Y\!=\!1|A\!=\!1,\hat{Y}\!=\!\hat{y})=\mathrm{P}(Y\!=\!1|A\!=\!0,\hat{Y}\!=\!\hat{y}),\;\;\hat{y}\in\{0,1\}.$$

Violations of these fairness properties can be measured as differences:

Numerous fair classification algorithms have been developed over the past few years, with most targeting one fairness metric (Hardt et al., 2016). With some exceptions (Blum & Stangl, 2019), predictive performance and fairness are typically competing objectives in supervised machine learning approaches. Thus, though satisfying many fairness properties simultaneously may be naïvely appealing, doing so often significantly degrades predictive performance or even creates infeasibility (Kleinberg et al., 2016).

Given this, many approaches seek to choose parameters $\mathbf{\bm{\theta}}$ for (probabilistic) classifier $\mathbb{P}_{\mathbf{\bm{\theta}}}$ that balance the competing predictive performance and fairness objectives (Kamishima et al., 2012; Hardt et al., 2016; Menon & Williamson, 2018; Celis et al., 2019; Martinez et al., 2020; Rezaei et al., 2020). Recently, Hsu et al. (2022) proposed a novel optimization framework to satisfy three conflicting fairness metrics (demographic parity, equalized odds, and predictive rate parity) to the best extent possible:

Preference elicitation (Chen & Pu, 2004) is one natural approach to identifying desirable performance-fairness trade-offs. Preference elicitation methods typically query users for their pairwise preference on a sequence of pairs of options to identify their utilities for different characteristics of the options. This approach has been extended and applied to fairness metric elicitation (Hiranandani et al., 2020), allowing efficient learning of linear (e.g., Eq. (4)) and non-linear metrics from finite and noisy preference feedback.

Imitation learning (Osa et al., 2018) is a type of supervised machine learning that seeks to produce a general-use policy $\hat{\pi}$ based on demonstrated trajectories of states and actions, $\tilde{\xi}=\left(\tilde{s}_{1},\tilde{a}_{1},\tilde{s_{2}},\ldots,\tilde{s}_{T}\right)$. Inverse reinforcement learning methods (Abbeel & Ng, 2004; Ziebart et al., 2008) seek to rationalize the demonstrated trajectories as the result of (near-) optimal policies on an estimated cost or reward function. Feature matching (Abbeel & Ng, 2004) plays a key role in these methods, guaranteeing if the expected feature counts match, the estimated policy $\hat{\pi}$ will have an expected cost under the demonstrator’s unknown fixed cost function weights $\tilde{w}\in\mathbb{R}^{K}$ equal to the average of the demonstrated trajectories:

where $f_{k}(\xi)=\sum_{s_{t}\in\xi}f_{k}\left(s_{t}\right)$.

Syed & Schapire (2007) seeks to outperform the set of demonstrations when the signs of the unknown cost function are known, $\tilde{w}_{k}\geq 0$, by making the inequality,

strict for at least one feature. Subdominance minimization (Ziebart et al., 2022) seeks to produce trajectories that outperform each demonstration by a margin:

under the same assumption of known cost weight signs. However, since this is often infeasible, the approach instead minimizes the subdominance, which measures the $\alpha$-weighted violation of this inequality:

where $[f(x)]_{+}\triangleq\max(f(x),0)$ is the hinge function and the per-feature margin has been reparameterized as $\alpha_{k}^{-1}$. Previous work (Ziebart et al., 2022) has employed subdominance minimization in conjunction with inverse optimal control:

learning the cost function parameters ${\bf w}$ for the optimal trajectory $\xi^{*}({\bf w})$ that minimizes subdominance. One contribution of this paper is extending subdominance minimization to the more flexible prediction models needed for fairness-aware classification that are not directly conditioned on cost features or performance/fairness metrics.

We consider reference decisions $\tilde{\mathbf{\bm{y}}}=\{\tilde{y}_{j}\}_{j=1}^{\text{M}}$ that are drawn from a human decision-maker or baseline method $\tilde{\mathbb{P}}$, on a set of M items, $\mathbf{\bm{X}}_{\text{M}\times\text{L}}=\{\mathbf{\bm{x}}_{j}\}_{j=1}^{\text{M}}$, where L is the number of attributes in each of $M$ items $\mathbf{\bm{x}}_{j}$. Group membership attributes $a_{m}$ from vector $\mathbf{\bm{a}}$ indicate to which group item $m$ belongs.

The predictive performance and fairness of decisions $\hat{\mathbf{\bm{y}}}$ for each item are assessed based on ground truth $\mathbf{\bm{y}}$ and group membership $\bf{a}$ using a set of predictive loss and unfairness measures $\{f_{k}(\hat{\mathbf{\bm{y}}},\mathbf{\bm{y}},\mathbf{\bm{a}})\}$.

If strict Pareto dominance is required to be $\gamma$-superhuman, which is often effectively true for continuous domains, then by definition, at most $(1-\gamma)\%$ of human decision makers could be $\gamma$-superhuman. However, far fewer than $(1-\gamma)$ may be $\gamma-$superhuman if pairs of human decisions do not Pareto dominate one another in either direction (i.e., neither $\bm{f}\left(\tilde{\bf y},{\bf y},{\bf a}\right)\preceq\bm{f}\left(\tilde{\bf y}^{\prime},{\bf y},{\bf a}\right)$ nor $\bm{f}\left(\tilde{\bf y}^{\prime},{\bf y},{\bf a}\right)\preceq\bm{f}\left(\tilde{\bf y},{\bf y},{\bf a}\right)$ for pairs of human decisions $\tilde{\bf y}$ and $\tilde{\bf y}^{\prime}$). From this perspective, any decisions with $\gamma-$superhuman performance more than $(1-\gamma)\%$ of the time exceed the performance limit for the distribution of human demonstrators.

Unfortunately, directly maximizing $\gamma$ is difficult in part due to the discontinuity of Pareto dominance ($\preceq$). The subdominance (Ziebart et al., 2022) serves as a convex upper bound for non-dominance in each metric $\{f_{k}\}$ and on $1-\gamma$ in aggregate:

Given $N$ vectors of reference decisions as demonstrations, $\tilde{\mathbfcal{Y}}=\{\tilde{\mathbf{\bm{y}}}_{i}\}_{i=1}^{\text{N}}$, the subdominance for decision vector $\hat{\bf y}$ with respect to the set of demonstrations is¹¹1For notational simplicity, we assume all demonstrated decisions $\tilde{\mathbf{\bm{y}}}\in\tilde{\mathbfcal{Y}}$ correspond to the same $M$ items represented in $\mathbf{\bm{X}}$. Generalization to unique $\mathbf{\bm{X}}$ for each demonstration is straightforward.

where $\hat{\mathbf{\bm{y}}}_{i}$ is the predictions produced by our model for the set of items $\mathbf{\bm{X}}_{i}$, and $\hat{\mathbfcal{Y}}$ is the set of these prediction sets, $\hat{\mathbfcal{Y}}=\{\hat{\mathbf{\bm{y}}}_{i}\}_{i=1}^{\text{N}}$. The subdominance is illustrated by Figure 2. Following concepts from support vector machines (Cortes & Vapnik, 1995), reference decisions $\tilde{\mathbf{\bm{y}}}$ that actively constrain the predictions $\hat{\mathbf{\bm{y}}}$ in a particular feature dimension, k, are referred to as support vectors and denoted as:

We consider probabilistic predictors $\mathbb{P}_{\theta}:\mathcal{X}^{M}\rightarrow\Delta_{\mathcal{Y}^{M}}$ that make structured predictions over the set of items in the most general case, but can also be simplified to make conditionally independent decisions for each item.

Hinge loss slopes $\mathbf{\bm{\alpha}}\triangleq\{\alpha_{k}\}_{k=1}^{\text{K}}$ are also learned from the data during training. For subdominance of $k_{\text{th}}$ feature, $\alpha_{k}$ indicates the degree of sensitivity to how much the algorithm fails to sufficiently outperform demonstrations in that feature. When $\alpha_{k}$ value is higher, the algorithm chooses that feature to minimize subdominance. In our setting, features are loss/violation metrics defined to measure the performance/fairness of a set of reference decisions.

We use the subgradient of subdominance with respect to $\mathbf{\bm{\theta}}$ and $\mathbf{\bm{\alpha}}$ to update these variables iteratively, and after convergence, the best learned weights $\mathbf{\bm{\theta}}^{*}$ are used in the final model $\hat{\mathbb{P}}_{\mathbf{\bm{\theta^{*}}}}$. A commonly used model like logistic regression can be used for $\hat{\mathbb{P}}_{\mathbf{\bm{\theta}}}$.

Using gradient descent, we update the model weights $\mathbf{\bm{\theta}}$ using an approximation of the gradient based on a set of sampled predictions $\hat{\mathbf{\bm{y}}}\in\hat{\mathbfcal{Y}}$ from the model $\hat{\mathbb{P}}_{\mathbf{\bm{\theta}}}$:

We show the steps required for the training of our model in Algorithm 1. Reference decisions $\{\tilde{\mathbf{\bm{y}}}_{i}\}_{i=1}^{\text{N}}$ from a human decision-maker or baseline method $\tilde{\mathbb{P}}$ are provided as input to the algorithm.   $\mathbf{\bm{\theta}}$ is set to an initial value. In each iteration of the algorithm, we first sample a set of model predictions $\{\hat{\mathbf{\bm{y}}}_{i}\}_{i=1}^{\text{N}}$ from $\hat{\mathbb{P}}_{\mathbf{\bm{\theta}}}(.|\mathbf{\bm{X}}_{i})$ for the matching items used for reference decisions $\{\tilde{\mathbf{\bm{y}}}_{i}\}_{i=1}^{\text{N}}$. We then find the new $\mathbf{\bm{\theta}}$ (and $\mathbf{\bm{\alpha}}$) based on the algorithms discussed in Theorem 3.3.

With a small effort, we extend the generalization bounds based on support vectors developed for inverse optimal control subdominance minimization (Ziebart et al., 2022).

This generalization bound requires overfitting to the training data so that the $\hat{\mathbb{P}}_{\mathbf{\bm{\theta}}}$ has restricted support (i.e., $\hat{\mathbb{P}}_{\mathbf{\bm{\theta}}}(\hat{\mathbf{\bm{y}}}|\mathbf{\bm{X}})=0$ for many $\hat{\mathbf{\bm{y}}}$) or becomes deterministic.

To emulate human decision-making with various levels of noise, we add noise to the ground truth data of benchmark fairness datasets and apply fair learning methods over repeated randomized dataset splits. We describe this process in detail in the following section.

We use a logistic regression model $\mathbb{P}_{\mathbf{\bm{\theta}}_{0}}$ with first-order moments feature function, $\phi(y,\mathbf{x})=[x_{1}y,x_{2}y,\dots x_{m}y]^{\top}$, and weights $\mathbf{\bm{\theta}}$ applied independently on each item as our decision model. During the training process, we update the model parameter $\mathbf{\bm{\theta}}$ to reduce subdominance.

After training each model, e.g., obtaining the best model weight $\mathbf{\bm{\theta}}^{*}$ from the training data (train-sh) for superhuman, we evaluate each on unseen test data (test-sh). We employ hard predictions (i.e., the most probable label) using our approach at time time rather than randomly sampling.