```javascript
%%javascript
MathJax.Hub.Config({
    TeX: { equationNumbers: { autoNumber: "AMS" } }
});
```


    <IPython.core.display.Javascript object>


# 03. Differential Privacy

[Differential privacy](https://www.microsoft.com/en-us/research/publication/differential-privacy/) is a popular mechanism to quantitatively assess the privacy loss of a given probabilistic query schema or data transformation method. The fundamental equation of differntial privacy is given as

$$ 
\begin{equation}
    \mathrm{Pr}[\mathcal{K}(D_1) \in S] \le exp(\epsilon) \times \mathrm{Pr}[\mathcal{K}(D_2) \in S] \label{eq:dp}
\end{equation}
$$

Here, $\mathrm{Pr}[\mathcal{K}(D_1) \in S]$ is the probability of a
randomized function $\mathcal{K}$ to yield one of values in the $S$ when evaluating
it on a given dataset $D_1$. The right side is identical to the left except
that the function is now evaluated on a dataset $D_2$ that differs from $D_1$
in at most one element. And finally, $\epsilon$ is a parameter that describes
how much information is leaked (or generated) by the function.

Sounds pretty abstract, so let's work out a simple example: Let's assume we want to build a differentially private dataset from the adult data that we've looked at in part 02. The goal here is to protect an adversary from gaining too much information about the sensitive attribute (income > 50k or not) when adding that person's data to the dataset. With differential privacy, we look at the state of the dataset before and after a person was added and quantify the privacy loss as given by equation ($\ref{eq:dp}$). The scheme we're evaluating here is a so-called **randomized response method**, which works as follows:

* With probability $1-p$, we add a person's true attribute value to the database.
* With probability $p$ we choose a random boolean (0/1) value from a distribution returning $0$ with probability $k$ and $1$ with probability $1-k$ and add that value to the database instead.

Using this scheme, an attacker cannot know with certainty if the real attribute value of the person or a random one was added to the database. This protects the privacy of the person but of course it also adds noise to the database, making it more difficult to use for legitimate users as well.

In practice, we therefore always need to weigh privacy against utility when employing differential privacy. In this notebook, we will calculate the $\epsilon$ and other relevant parameters for our scheme above and see how we can use this differentially private data to make predictions about the income distribution of the people in our dataset.

#### Calculating $\epsilon$

In our differentially private scheme, the probability of adding the true attribute value to the database is $1-p$. The probability of adding a random value is therefore $p$ and the probability of that value being $0$ is $k$. So how can we relate this to eq. (\ref{eq:dp})? Well, we can set $D_1$ and $D_2$ as the versions of our database **before** and **after** adding the person's data to it. Let's say that before adding the person's data there are $n$ $1$'s in the database. We can then use a query $\mathcal{K}$ that returns the number of 1's in the database and choose our result set as $S = \{n\}$. Before adding the person to the database, $\mathcal{K}(D_1)=n$ with certainty, hence $\mathrm{Pr}(\mathcal{K}(D_1))=1$. After adding the person's data, the probability that the query result is still $n$ can be calculated as follows, depending on the person's attribute value:

* If a persons's attribute value is $0$, the probability that $\mathcal{K}$ is unchanged after adding the data to the database is given as $1-p+p\cdot k$.
* If a person's attribute value is $1$, the probability that $\mathcal{K}$ is unchanged after adding the data to the database is given as $p\cdot k$.

We therefore have the two equations

$$
\begin{eqnarray}
\mathrm{Pr}[\mathcal{K}(D_1) \in S | x_i=1] & = & 1 \le \exp{\epsilon}\cdot \mathrm{Pr}[\mathcal{K}(D_2) \in S | x_i=1] = \exp{\epsilon}\cdot p \cdot k \\
\mathrm{Pr}[\mathcal{K}(D_1) \in S | x_i=0] & = & 1 \le \exp{\epsilon}\cdot \mathrm{Pr}[\mathcal{K}(D_2) \in S | x_i=0] = \exp{\epsilon}\cdot (1-p+p \cdot k) \\
\end{eqnarray}
$$

This yields

$$
\begin{eqnarray}
 \epsilon & \ge & -\ln{\left(p \cdot k\right)} \\
 \epsilon & \ge & -\ln{\left(1-p+p\cdot k\right)} \\
\end{eqnarray}
$$

Since we're interested in an upper bound for $\epsilon$ and since $-\ln{\left(1-p+p\cdot k\right)} \le -\ln{p\cdot k}$, we obtain

$$
\begin{equation}
\epsilon = -\ln{\left(p\cdot k\right)}
\end{equation}
$$

## Exercise

**Write a function that returns the value of epsilon for a given $p$ and $k$.**


```python
# %load "../solutions/differential-privacy/epsilon.py"

def epsilon(p, k):
    """
    :param p: The probability of returning a random value instead of the true one
    :param k: The probability of returning 1 when generating a random value
    :returns: The epsilon for the given values of p, k
    """
```

## Exercise

** Plot $\epsilon$ for various values of $p$ and $k$.**

## Exercise: Different Scheme

Let's assume we propose the following anonymization scheme for our dataset:

* With probability $1-p$, we add a person's true attribute value to the database
* With probability $p$, we do not add anything to the database

Can you calculate the $\epsilon$ of this scheme? Which scheme do you prefer, and why? Does this scheme always provide "plausible deniability"?


```python
%load "../solutions/differential-privacy/different-scheme.md"
```

## What does this tell us?

Calculating the $\epsilon$ is great, but what does it actually tell us about the privacy loss or risk for our use case? Let's assume an adversary want to learn about the real value of a person's attribute. If she knows the model used for generating the data, she could then use Bayesian reasoning to calculate the probability of a person's attribute being $1$ given the observed difference in the database, which we call $\Delta$. Using Bayes theorem we can calculate this as (for $\Delta = 1$ here)

$$
\begin{equation}
    P(x_i=1 | \Delta = 1) = P(\Delta = 1| x_i = 1)\cdot \frac{P(x_i=1)}{P(\Delta=0)}
\end{equation}
$$

For our scheme, we know that 

$$
\begin{equation}
    P(\Delta = 1 | x_i = \mathrm{1}) = (1-p) + p\cdot(1-k) = 1-pk
\end{equation}
$$

and

$$
\begin{equation}
    P(\Delta = 1) = (1-p)\cdot P(x_i = \mathrm{1}) + p\cdot(1-k)
\end{equation}
$$

so we obtain

$$
\begin{equation}
    P(x_i=1 | \Delta = 1) = \frac{(1-pk)\cdot P(x_i = \mathrm{1})}{(1-p)\cdot P(x_i = \mathrm{1})+p\cdot(1-k)}
\end{equation}
$$

Let's see how this relates to $\epsilon$!

## Exercise

**Write a function that calculates thecondition probability as given in eq. (4).**


```python
# %load "../solutions/differential-privacy/conditional-prob.py"

def p_cond(p, k, p_1):
    """
    :param   p: The probability of returning a random value instead of the true one
    :param   k: The probability of returning 1 when generating a random value
    :param p_1: The probability of a person to have an attribute value x_i=1
    """
```

## Exercise

** Choose a given k (e.g. 0.5) as well as a value for P(x_i=yes) and plot the conditional probability from eq. (4) as a function of p.**

# Implementing It

Now that we have a feeling for our scheme we can implement it! For that, we load the "adult census" data from the k-anonymity case study again.


```python
import pandas as pd

names = (
    'age',
    'workclass', #Private, Self-emp-not-inc, Self-emp-inc, Federal-gov, Local-gov, State-gov, Without-pay, Never-worked.
    'fnlwgt', # "weight" of that person in the dataset (i.e. how many people does that person represent) -> https://www.kansascityfed.org/research/datamuseum/cps/coreinfo/keyconcepts/weights
    'education',
    'education-num',
    'marital-status',
    'occupation',
    'relationship',
    'race',
    'sex',
    'capital-gain',
    'capital-loss',
    'hours-per-week',
    'native-country',
    'income',
)
categorical = set((
    'workclass',
    'education',
    'marital-status',
    'occupation',
    'relationship',
    'sex',
    'native-country',
    'race',
    'income',
))
df = pd.read_csv("../data/k-anonymity/adult.all.txt", sep=", ", header=None, names=names, index_col=False, engine='python');# We load the data using Pandas
```

## Exercise

**Implement a function that processes a new value according to the differentially private scheme discussed above.**


```python
# %load "../solutions/differential-privacy/process-value.py"

import random

def process_value(value, p, k):
    """
    :param value: The value to apply the differentially private scheme to.
    :param     p: The probability of returning a random value instead of the true one
    :param     k: The probability of returning 1 when generating a random value
    :    returns: A new, differentially private value
    """
```

## Exercise

**Now apply this method to the "income" column of the adult dataset to obtain a differentially private dataset.**


```python
# %load "../solutions/differential-privacy/apply.py"

import numpy as np

p = 0.8
k = 0.4

df['income_binary'] = np.where(df['income'] == '<=50k', 0, 1)
df['income_dp'] = 0

# ...
```

# Working With Differentially Private Data

After collecting the differentially private data, we want of course to make use of it! For example, we might want to estimate the probability of a person having an income > 50T\$ based on the data we've collected, which we assume is [Bernoulli distributed](https://en.wikipedia.org/wiki/Bernoulli_distribution) with a probability $p_{1}$. Now, when adding up the data from $n$ persons, the resulting value is [binomially distributed](https://en.wikipedia.org/wiki/Bernoulli_distribution). The mean of this distribution is given as $\mathrm{E}_{1} = n\cdot p_{1}$ and the variance as $\mathrm{Var}_1 = n\cdot p_1 \cdot (1-p_1)$. A consistent and unbiased estimator of $\mathrm{E}_1$ is $\hat{\mathrm{E}}_{1} = \sum_i x_{1}^i$, which then gives an estimate for $p_{1}$ of $\hat{p}_{1} = \hat{\mathrm{E}}_1/n$.

Now, if we apply the differential privacy mechanism to our dataset, the probability of obtaining a $1$ will change to $p_{1,dp} = (1-p)\cdot p_{1}+p\cdot(1-k)$. Therefore, an unbiased and consistent estimator of $p_1$ based on $p_{1,dp}$ is given as
$$
\begin{equation}
\hat{p}_1 = \frac{\hat{p}_{1,dp}-p\cdot(1-k)}{1-p}
\end{equation}
$$

As before, $\hat{p}_{1,dp}=\sum_i x_{1,dp}^i/n$. Note that this naive estimator can return a negative probability, which can be avoided by using a more suitable method like a maximum likelihood estimator.

## Exercise

**Write an estimator for $\hat{p}_1$ based on a differentially private dataset with parameters $p$ and $k$..**


```python
# %load "../solutions/differential-privacy/p-1.py"

def p_1_estimator(p_1dp, p, k):
    """
    :param p_1dp: The empirical probability of x_i=1 of our DP dataset.
    :param     p: The p value of our DP scheme.
    :param     k: The k value of our DP scheme.
    :    returns: An estimate of p_1 of our DP dataset.
    """
```

## Exercise

**Apply the estimator to the differentially private dataset created above to generate an estimate of $p_1$.**


```python
# %load "../solutions/differential-privacy/estimate-p1.py"

p_1_hat = ...
```

## Exercise

**Write a function that estimates the variance of $\hat{p}_{1}$ and calculate its value for the case above.**

Hint: The variance of $\hat{p}_1$ can be estimated as $$\hat{\mathrm{Var}}_1 = \frac{\hat{\mathrm{Var}}_{1,dp}}{(1-p)^2} = \frac{\hat{p}_{1,dp}\cdot(1-\hat{p}_{1,dp})}{(1-p)^2\cdot n}$$


```python
# %load "../solutions/differential-privacy/estimate-var.py"

def var_1_estimator(p_1dp, n, p, k):
    """
    :param p_1dp: The empirical probability of x_i=1 of our DP dataset.
    :param     n: The number of samples in our dataset.
    :param     p: The p value of our DP scheme.
    :param     k: The k value of our DP scheme.
    :    returns: An estimate of the variance of our DP dataset.
    """

var_1_hat = var_1_estimator(p_1dp, len(df), p, k)
var_1_hat
```




    0.00012764584739878977



## Exercise

** Repeat the data generation process $N$ (e.g. 500) times. For each resulting dataset, estimate $\hat{p}_1$ and store the value in a list, so that we can plot it later.**


```python
# %load "../solutions/differential-privacy/repeat-dp.py"

p_1_hats = []

for j in range(500):
    
    # ...
    
    p_1_hats.append(p_1_hat)

p_1_hats = np.array(p_1_hats)
```


```python
# We then compare these estimates to the expected distribution (via central limit theorem: a normal distribution
# with expectation p_1 and variance var_1_hat)

import matplotlib.pylab as pl

pl.hist(p_1_hats, density=True)

gauss = lambda x, mu, var: 1/np.sqrt(2*np.pi*var)*np.exp(-(x-mu)**2/(2*var))

p_1_hat = p_1_hats.mean()

x = np.linspace(0.1, 0.3, 1000)

pl.plot(x, gauss(x, p_1_hat, var_1_hat));
```

# Summary

That's it! As you can see, applying a differential privacy mechanism to your data is not so difficult, you have to take into account the added noise though, which will make your estimates less precise.

0e45600f0a72266d0b8ddddf9193ec2cdf2d7228
ipynb
Jupyter Notebook
notebooks/03 - Differential Privacy.ipynb
graingert/data-privacy-for-data-scientists
df36f1bc926c1aadab3d475df2b4417df2643712
MIT
2018-07-19T12:14:24.000Z
2020-06-30T23:37:42.000Z
notebooks/03 - Differential Privacy.ipynb
graingert/data-privacy-for-data-scientists
df36f1bc926c1aadab3d475df2b4417df2643712
MIT
2018-07-29T10:33:39.000Z
2020-03-30T21:38:01.000Z
notebooks/03 - Differential Privacy.ipynb
graingert/data-privacy-for-data-scientists
df36f1bc926c1aadab3d475df2b4417df2643712
MIT
2018-07-24T12:41:29.000Z
2020-04-15T21:19:19.000Z
Qwen/Qwen-72B
1. YES
2. YES