Difference between revisions of "Fairness Without Demographics in Repeated Loss Minimization"

From statwiki
Jump to: navigation, search
(Disparity Amplification)
(Empirical Risk Minimization)
Line 38: Line 38:
\theta^{(t)} = arg min_{\theta \in \Theta} \sum_i \ell(\theta; Z_i^{(t)}
\theta^{(t)} = arg min_{\theta \in \Theta} \sum_i \ell(\theta; Z_i^{(t)})

Revision as of 13:04, 22 October 2018

This page contains the summary of the paper "Fairness Without Demographics in Repeated Loss Minimization" by Hashimoto, T. B., Srivastava, M., Namkoong, H., & Liang, P. which was published at the International Conference of Machine Learning (ICML) in 2018. In the following, an

Overview of the Paper


Usually, machine learning models aim to minimize their average loss in order to achieve high overall accuracy. While this works well for the majority, minority groups suffer high error rates because they contribute less data to the model. This phenomenon is known as representation disparity and has been observed in many models that, for instance, recognize faces, or identify language. This disparity even increases as minority users suffer higher error rates, and therefore, are less likely to use the system in the future. This retention of users from minority groups from the system shrinks these groups further, and provide less data to the system. With less data the disparity becomes even worse - a phenomenon referred to as disparity amplification.

In this paper, Hashimoto et al. first show that empirical risk minimization (ERM) does not control the loss of minority groups, and thus causes representation disparity even if the model has been fair before. Second, the researchers try to mitigate representation disparity and its amplification by proposing the use of distributionally robust optimization (DRO). Indeed Hashimoto et al. are able to show that DRO can bound the loss for minority groups and is fair on models that ERM turns unfair.


Hashimoto et al. follow the difference principle to achieve and measure fairness. It is defined as the maximization of the welfare of the worst-off group rather than the whole group (cf. utilitarianism).

Representation Disparity

If a user makes a query [math]Z \sim P[/math], the model [math]\theta \in \Theta[/math] makes a prediction, and the user experiences loss [math]\ell (\theta; Z)[/math]. The expected loss of of a model [math]\theta[/math] is denoted as the risk [math]\mathcal{R}(\theta) = \mathbb{E}_{Z \sim P} [\ell (\theta; Z)] [/math]. While the queries (i.e. provide data to the model) are made by users from [math]K[/math] latent groups such that [math]Z \sim P := \sum_{k \in [k]} \alpha_kP_k[/math], neither the actual population proportions [math]\{\alpha_k\}[/math] nor the group distributions [math]\{P_k\}[/math] are known. Therefore, Hashimoto et al.'s goal is to control the worst-case risk over all groups [math]K[/math]:

\begin{align} \mathcal{R}_{max}(\theta) := \underset{k \in [k]}{max} \mathcal{R}_k(\theta), \qquad \mathcal{R}_k(\theta) := \mathbb{E}_{P_k} [\ell (\theta; Z)] \end{align}

We say there is high representation disparity if the expected loss of the model [math]\mathcal{R}(\theta)[/math] is low, but the worst-case risk [math]\mathcal{R}_{max}(\theta)[/math] of one group is high. That is why Hashimot et al. try to minimize [math]\mathcal{R}_{max}(\theta)[/math] in the following.

Disparity Amplification

Representation disparity can amplify as time passes and loss gets minimized. Specifically, over [math]t = 1, 2, ..., T[/math] minimization rounds the group proportions [math]\alpha_k^{(t)}[/math] vary dependent on past losses. At each round the expected number of users [math]\lambda_k^{(t+1)}[/math] from group [math]k[/math] is determined by

\begin{align} \lambda_k^{(t+1)} := \lambda_k^{(t)} \nu(\mathcal{R}_k(\theta^{(t)})) + b_k \end{align}

where [math]\lambda_k^{(t)} \nu(\mathcal{R}_k(\theta^{(t)}))[/math] describes the fraction of retained users from the previous optimization and [math]b_k[/math] is the number of new users of group [math]k[/math]. To put simply, the number of expected users of a group depend on the number of new users of that group, and the fraction of users that continue to use the system from the previous optimization step. Without the knowledge of population proportions [math]\alpha_k^{(t)}[/math], the new user rate [math]b_k[/math], and the retention function [math]\nu[/math] in practice it is hard, however, to control the worst-case risk over all time periods [math]\mathcal{R}_{max}^T[/math] for all groups.

Empirical Risk Minimization

Since the aforementioned variables are unknown in practice, the standard approach to fit a sequence of models [math]\theta^{(t)}[/math] is to empirically approximate them. Using ERM, for instance, the optimal model is approached by minimizing the loss of the model:

\begin{align} \theta^{(t)} = arg min_{\theta \in \Theta} \sum_i \ell(\theta; Z_i^{(t)}) \end{align}

Distributonally Robust Optimization (DRO)

At this point our goal is to minimize the worst-case group risk over a single time-step [math]\mathcal{R}_{max} (\theta^{(t)}) [/math]. As previously mentioned, this is difficult to do because neither the population proportions [math]\{\alpha_k\} [/math] nor group distributions [math]\{P_k\} [/math] are known. Therefore, Hashimoto et al. developed an optimization technique that is robust "against all directions around the data generating distribution". This refers to the notion that DRO is robust to any group distribution [math]P_k [/math] whose loss other optimization techniques such as ERM might try to optimize. To create this distributionally robustness, the optimizations risk function [math]\mathcal{R}_{dro} [/math] has to "up-weigh" data [math]Z[/math] that cause high loss [math]\ell(\theta, Z)[/math]. In other words, the risk function has to over-represent mixture components (i.e. group distributions [math]\{P_k\} [/math]) in relation to their original mixture weights (i.e. the population proportions [math]\{\alpha_k\} [/math]) for groups that suffer high loss.

To do this we need to consider the worst-case loss (i.e. the highest risk) over all perturbations [math]P_k [/math] around [math]P[/math] within a certain limit. This limit is described by the [math]\chi^2[/math]-divergence (i.e. the distance, roughly speaking) between probability distributions. For two distributions [math]P[/math] and [math]Q[/math] the divergence is defined as [math]D_{\chi^2} (P || Q):= \int (\frac{dP}{dQ} - 1)^2[/math]. With the help of the [math]\chi^2[/math]-divergence, Hashimoto et al. define the chi-squared ball [math]\mathcal{B}(P,r)[/math] around the probability distribution P. This ball is defined so that [math]\mathcal{B}(P,r) := \{Q \ll P : D_{\chi^2} (Q || P) \leq r \}[/math]. It is exactly this ball that gives us the opportunity to consider the worst-case loss (i.e. the highest risk) over all perturbations [math]P_k [/math] that lie inside the ball (i.e. within reasonable range) around the probability distribution [math]P[/math]. This loss is given by

\begin{align} \mathcal{R}_{dro}(\theta, r) := \underset{Q \in \mathcal{B}(P,r)}{sup} \mathbb{E}_Q [\ell(\theta;Z)] \end{align}

which for [math]P:= \sum_{k \in [K]} \alpha_k P_k[/math] for all models [math]\theta \in \Theta[/math] where [math]r_k := (1/a_k -1)^2[/math] bounds the risk [math]\mathcal{R}_k(\theta) \leq \mathcal{R}_{dro} (\theta; r_k)[/math] for each group with risk [math]\mathcal{R}_k(\theta)[/math]. Furthermore, if we specify a lower bound on the group proportions [math]\alpha_{min} \leq min_{k \in [K]} \alpha_k[/math], and define [math]r_{max} := (1/\alpha_{min} -1)^2[/math], the worst-case risk [math]\mathcal{R}_{max} (\theta) [/math] can be controlled by [math]\mathcal{R}_{dro} (\theta; r_{max}) [/math] by forming an upper bound that can be minimized.

Optimization of DRO

To minimize [math]\mathcal{R}_{dro}(\theta, r) := \underset{Q \in \mathcal{B}(P,r)}{sup} \mathbb{E}_Q [\ell(\theta;Z)][/math] Hashimoto et al. look at the dual of this maximization problem (i.e. every maximization problem can become transformed into a minimization problem and vice-versa). This dual is given by the minimization problem

\begin{align} \mathcal{R}_{dro}(\theta, r) = \underset{\eta \in \mathbb{R}}{inf} \left\{ F(\theta; \eta):= C\left(\mathbb{E}_P \left[ [\ell(\theta;Z) - \eta]_+^2 \right] \right)^\frac{1}{2} + \eta \right\} \end{align}

with [math]C = (2(1/a_{min} - 1)^2 + 1)^{1/2}[/math]. [math]\eta[/math] describes the dual variable (i.e. the variable that appears in creating the dual). Since [math]F(\theta; \eta)[/math] involves an expectation [math]\mathbb{E}_P[/math] over the data generating distribution [math]P[/math], [math]F(\theta; \eta)[/math] can be directly minimized. For convex losses [math]\ell(\theta;Z)[/math], [math]F(\theta; \eta)[/math] is convex, and can be minimized by performing a binary search over [math]\eta[/math]. In their paper, Hashimoto et al. further show that optimizing [math]\mathcal{R}_{dro}(\theta, r_{max})[/math] at each time step controls the future worst-case risk [math]\mathcal{R}_{max} (\theta) [/math], and therefore retention rates. That means if the initial group proportions satisfy [math]\alpha_k^{(0)} \geq a_{min}[/math], and [math]\mathcal{R}_{dro}(\theta, r_{max})[/math] is optimized for every time step (and therefore [math]\mathcal{R}_{max} (\theta) [/math] is minimized), [math]\mathcal{R}_{max}^T (\theta) [/math] over all time steps is controlled. In other words, optimizing [math]\mathcal{R}_{dro}(\theta, r_{max})[/math] every time step is enough to avoid disparity amplification.