06 - Local Differential Privacy via Randomized Response.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from math import e\n",
    "from random import choice\n",
    "\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Imagine we are asked to participate in a survey that will use randomized response as a way to gaurantee plausible deniability. We want to first determine what our personal threshhold (loss function) is to participating. We can imagine that one or more of the questions we will be asked are sensitive. Here are a few examples:\n",
    "\n",
    "- Have you knowingly consumed illegal drugs in the past month? \n",
    "- Have you tested positive for Covid in the past 6 months?\n",
    "- Have you ever lied to your boss?\n",
    "\n",
    "Answering yes (or, arguably, no) to any of these responses would be considered quite sensitive in terms of personal privacy. We will take yes as the most sensitive response and say that if you toss a coin and it turns up heads (1), that you tell the truth in your response. If it turns up tails, you toss the coin again and you report No (0) if it comes up tails and Yes (1) if it comes up heads.  \n",
    "\n",
    "Let's take a look at how this mechanism ensures differential privacy!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "outcomes = [0, 1]\n",
    "our_true_response = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "coin_flip = choice(outcomes)\n",
    "print (\"Initial coin flip is %s\" % coin_flip)\n",
    "if coin_flip == 0:\n",
    "    second_coin_flip = choice(outcomes)\n",
    "    print(\"Second coin flip is %s\" % second_coin_flip)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def flip_coin(outcomes, our_response=1):\n",
    "    coin_flip = choice(outcomes)\n",
    "    if coin_flip == 1:\n",
    "        return our_response\n",
    "    second_coin_flip = choice(outcomes)\n",
    "    return second_coin_flip"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def randomized_response(outcomes, num_trails=100):\n",
    "    return [flip_coin(outcomes) for x in range(num_trails)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "results = randomized_response(outcomes)\n",
    "Counter(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.bar(Counter(results).keys(), Counter(results).values(), tick_label=['Yes', 'No'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can see here the benefit of plausible deniability. Even though 100 of us would have answered yes, we see that there is always some proportion of no responses due to the randomized response mechanism. This protects all of us by allowing us culpable deniability. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So for us personally, this aligns well with looking at our own probability distribution w.r.t the sensitive questions. If our true answer is yes we have:\n",
    "\n",
    "P[A(Yes)=Yes]=0.75, P[A(Yes)=No]=0.25\n",
    "\n",
    "75% chance of saying Yes, 25% chance of saying No.\n",
    "\n",
    "\n",
    "If our true answer is no we have:\n",
    "\n",
    "P[A(No)=Yes]=0.25, P[A(No)=No]=0.75\n",
    "\n",
    "This difference shows a sensitivity of 3x (.25 * 3 = .75), which means our probability should be bounded by 3 in differential privacy, which would mean\n",
    "\n",
    "e^epsilon = 3\n",
    "\n",
    "Making epsilon ≃ 1.1 if we are using (ɛ, 0)-differential privacy :) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "e**1.1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = np.linspace(0,3,10000)\n",
    "y = np.power(e,x)\n",
    "\n",
    "fig,ax= plt.subplots()\n",
    "plt.style.use('ggplot')\n",
    "ax.plot(x,y);\n",
    "ax.set_title('e^epsilon')\n",
    "ax.set_xlabel('epsilon')\n",
    "ax.set_ylabel('probability bound');"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, it also tells the researcher that there are quite a lot of true Yeses, due to the ratio of the outcomes above. Due to our epsilon bounds, we can say that the researcher can increase their probability of learning something about us by 3x with successive queries via this mechanism. Of course, we also have the power of large numbers in our favor here, meaning the researcher being able to link our exact response to us is quite rare and would require a targeted attack (or several). \n",
    "\n",
    "Now, how does the researcher learn from the survey? They would need to de-noise the data as best possible which means thinking about the biases they introduced with the differentially private mechanism.\n",
    "\n",
    "How the researcher might try to de-noise the data is as follows."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we will create some data where there is more initial variety in the responses! Feel free to modify below to try out different underlying distributions!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "underlying_dist = np.random.choice([0, 1], size=100, p=[.2, .8])\n",
    "\n",
    "def randomized_response(outcomes):\n",
    "    return [flip_coin(outcomes, our_response=x) for x in underlying_dist]\n",
    "results = randomized_response(outcomes)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Counter(underlying_dist)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Counter(results)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def denoise_data(survey_results):\n",
    "    results = Counter(survey_results)\n",
    "    # We want to first figure out our guess of # of possible random responses per Yes, No answer\n",
    "    num_random_responses = len(survey_results)*0.5 / len(results)\n",
    "    denoised = {'Yes': 0, 'No':0, 'Unaccounted':0}\n",
    "    for outcome, num_responses in results.items():\n",
    "        if outcome == 0: \n",
    "            outcome = 'No'\n",
    "        else:\n",
    "            outcome = 'Yes'\n",
    "        # if the number of responses for this answer is more than we expect, we could try to subtrack the random responses (naive and crude!)\n",
    "        if num_responses > num_random_responses:\n",
    "            denoised[outcome] = num_responses - num_random_responses\n",
    "        elif outcome == 1: # oops, we have too many Yes answers because our distribution is skewed\n",
    "            denoised[outcome] = 0\n",
    "            denoised['Unaccounted'] = num_random_responses - num_responses\n",
    "        else: # or too many No!\n",
    "            denoised[outcome] = 1 \n",
    "            denoised['Unaccounted'] = num_random_responses - num_responses\n",
    "    return denoised"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "results = denoise_data(randomized_response(outcomes))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "plt.bar(Counter(results).keys(), Counter(results).values(), \n",
    "        tick_label=['Yes', 'No', 'Unaccounted'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And one way to interpret this would be that we could guess that a large percent of the population had a true answer of Yes. This is of course quite inaccurate compared to our knowledge that 100% of the population said yes, but it is a step in the right direction! Thus, we see both the accuracy limits and results of our randomized response! :)\n",
    "\n",
    "\n",
    "### Challenge\n",
    "\n",
    "How can we modify the functions above to show how it might work on different underlying distributions? (i.e. if 75% of the population would answer yes, or if 50% would answer yes?). What changes with the results and the accuracy? \n",
    "\n",
    "\n",
    "### Additional Challenge\n",
    "\n",
    "If you were a researcher trained in Bayesian statistics, could you use a prior here that would allow you to have a more accurate takeaway from the response? (Or from future responses?). Asked in another way, what information have we learned from our initial survey that could inform future surveys by using an appropriate probability distribution function?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Recommended Reading\n",
    "\n",
    "- Ted on Privacy's Blog Series on Differential Privacy! https://desfontain.es/privacy/friendly-intro-to-differential-privacy.html"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.13"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}