[toc]
# Adversarial Training
# Fairness through Explanation
# FairPrune
## Problem
Given a dataset $D=\{x_i,y_i,c_i\},\ i\in1,...,N$
* $x_i$: Input image
* $y_i$: Class label
* $c_i$: Sensitive attribute

, and a pre-trained classification model $f_\theta(\cdot)$ with parameters $\theta$ that maps the input $x_i$ to the final prediction $\hat{y}_i=f_\theta(x_i)$.
Our goal is to reduce the discrimination in $f_\theta(\cdot)$ with respect to the sensitive attribute $c$ by only modifying some of the parameters in $f_\theta(\cdot)$ without further finetuning.
## Saliency
Given the pre-trained model $f_\theta$ and its objective function $E$, the change of the objective function after pruning parameters $\Theta$ can be approximated by Taylor series
$$
\Delta E=E(D|\Theta=0)-E(D)=-\sum_ig_i\theta_i+\frac{1}{2}\sum_ih_{ii}\theta_i^2+\frac{1}{2}\sum_{i\not=j}h_{ij}\theta_i\theta_j+O(||\Theta||^3)=\frac{1}{2}\sum_ih_{ii}\theta_i^2
$$
* $g_i=\frac{\partial E}{\partial\theta_i}$: The gradient of $E$ with respect to $\theta_i$, which is close to $0$ because we assume the pre-tained model has converged and the objective function is at its local minimum.
* $h_{ii}$: The elemetn at row $i$ and column $i$ of second derivate Hessian matrix $H$.
* $\frac{1}{2}h_{ii}\theta_i^2$: The saliency of $\theta_i$ which represents the increase of error after pruning this parameter.

The approximation assumes that $\Delta E$ caued by pruning serveral parameters is the sum of $\Delta E$ caued by pruning each parameter individually, so the third term is neglected.
By pruning parameters with low saliency for the privileged group and high saliency for the unprivileged group, the accuracy difference can be reduced.
## Method
For example, $c_i=0$ represents unprivileged samples and $c_i=1$ represents privileged samples.
To identify those parameters to prune, formulate a multi-objective optimization problem
$$
min\Delta E_{c=0}(\Theta)\\
max\Delta E_{c=1}(\Theta)
$$
* $\Delta E_{c=0}(\Theta)$ and $\Delta E_{c=1}(\Theta)$: The error changes of unprivileged group $c=0$ and privileged group $c=1$ after pruning parameters $\Theta$, repectively.

To solve this problem, the formula can be transformed into a single objective as
$$
\begin{aligned}
&min_{\Theta}J=\Delta E_{c=0}(\Theta)-\beta\Delta E_{c=1}(\Theta)=\sum_is_i\\
&s_i=(\frac{1}{2}h_{ii}^{(0)}\theta_i^2)-\beta(\frac{1}{2}h_{ii}^{(1)}\theta_i^2)=\frac{1}{2}\theta_m^2(h_{ii}^{(0)}-\beta h_{ii}^{(1)})
\end{aligned}
$$
* $\beta$: A hyper-parameter controlling the trade-off between minimizing $\Delta E_{c=0}$ and maximizing $\Delta E_{c=1}$.
* $\theta_i$: The parameter of the model and can be treated as a contant.
* $s_i$: The saliecy of parameter $\theta_i$ for achieving the fairness objective, where a smaller value represents a larger benefit when we prune it since a small $s_i$ contributes to minimizing the objective $J$.
* $h^{(c)},c\in\{0,1\}$: The Hessian element of $\theta_i$ for group $c$.
## Procedure
Repeat until the taget fairness metric is achieved
1. Step 1: Sample mini-batches $\{B^{(0)}\}$ and $\{B^{(1)}\}$ from the unprivileged group and privileged group, respectively.
2. Step 2: For each pair of mini-batches $(B^{(0)},B^{(1)})$, compute the second derivatives $h_{ii}$ for each parameter, and compute parameter salience $s_i$.
3. Step 3: After several mini-batches, average teh saliecy of each parameter over the mini-batches. Remove $p\%$ parameters with the smallest saliency.

**References**
[FairPrune: Achieving Fairness Through Pruning for Dermatological Disease Diagnosis](https://arxiv.org/pdf/2203.02110.pdf)