{ "cells": [ { "cell_type": "markdown", "id": "6b9078e7", "metadata": {}, "source": [ "# Exponential mechanism DP\n", "\n", "By [Armaan Bhojwani](https://armaanb.net) under [Praneeth Vepakomma](https://praneeth.mit.edu/)\n", "\n", "This notebook features the following differentially private operations on a finite set:\n", "- Exponential mechanism\n", " - Choice\n", "\n", "### Dependencies\n", "- tqdm\n", "- matplotlib\n", "\n", "### Status\n", "- Complete\n", "\n", "### References\n", "- https://programming-dp.com/ch9.html" ] }, { "cell_type": "markdown", "id": "f961bc8f", "metadata": {}, "source": [ "## Choosing the best country to hold a conference in\n", "You are tasked with hosting a conference on nuclear disarmarment in, ideally, the country with the most nuclear weapons. The catch is you can't reveal which country has the most nukes. In this example, the input database is a 2x196 table with 196 countries in the first column and a triangularly distributed number of theoretical nukes in the second." ] }, { "cell_type": "markdown", "id": "84841604", "metadata": {}, "source": [ "### Parameters\n", "\n", "Epsilon is the privacy-accuracy trade-off\n", "\n", "Sensitivity is 1 as we are essentially performing a max query on the privatized probabilities we create" ] }, { "cell_type": "code", "execution_count": 1, "id": "c18e3ee5", "metadata": {}, "outputs": [], "source": [ "# Privacy\n", "epsilon = 5\n", "sensitivity = 1\n", "\n", "# Data\n", "nukes_low = 0 # Minimum number of nukes a country can have\n", "nukes_high = 10000 # Maximum number of nukes a country can have\n", "\n", "# Analysis\n", "max_epsilon = 10 # Largest epsilon value to test\n", "epsilon_step = 0.25 # Step size between epsilons\n", "num_samples = 20000 # Number of times to run lim x->inf functions" ] }, { "cell_type": "markdown", "id": "38fc1651", "metadata": {}, "source": [ "### Build the dataset" ] }, { "cell_type": "code", "execution_count": 2, "id": "bb8b815b", "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Top 25 countries with the most nukes (non-private):\n", " 1: ('Czech Republic', 9547)\n", " 2: ('Dominica', 9377)\n", " 3: ('Brunei', 9323)\n", " 4: ('Andorra', 8885)\n", " 5: ('Saint Vincent and the Grenadines', 8851)\n", " 6: ('Bangladesh', 8603)\n", " 7: ('Djibouti', 8437)\n", " 8: ('Bhutan', 8131)\n", " 9: ('Dominican Republic', 8119)\n", "10: ('Japan', 8048)\n", "11: ('Malta', 7912)\n", "12: ('Lebanon', 7905)\n", "13: ('Bulgaria', 7903)\n", "14: ('Slovakia', 7850)\n", "15: ('Belgium', 7694)\n", "16: ('Honduras', 7677)\n", "17: ('Cuba', 7598)\n", "18: ('Saudi Arabia', 7534)\n", "19: ('Equatorial Guinea', 7496)\n", "20: ('United States of America', 7461)\n", "21: ('New Zealand', 7398)\n", "22: ('Turkmenistan', 7396)\n", "23: ('Pakistan', 7348)\n", "24: ('Somalia', 7288)\n", "25: ('Monaco', 7267)\n" ] } ], "source": [ "import numpy as np\n", "\n", "rng = np.random.default_rng()\n", "\n", "countries = np.loadtxt(\"./Data/countries.txt\", dtype='str')\n", "countries = [y.replace('_', ' ') for y in countries]\n", "nukes_avg = (nukes_low + nukes_high) / 2\n", "nukes = rng.triangular(nukes_low,\n", " nukes_avg,\n", " nukes_high,\n", " size=np.shape(countries))\n", "nukes = [round(y) for y in nukes]\n", "\n", "x = list(zip(countries, nukes))\n", "x.sort(key=lambda tup: tup[1], reverse=True)\n", "\n", "print(\"Top 25 countries with the most nukes (non-private):\")\n", "for i, y in enumerate(x[:25]):\n", " print(f\"{1 + i:2}: {y}\")" ] }, { "cell_type": "markdown", "id": "22e2bf56", "metadata": {}, "source": [ "### Apply exponential model" ] }, { "cell_type": "code", "execution_count": 3, "id": "58ba906b", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Using epsilon 5, the algorithm chose Turkmenistan, which is the number 22 best choice.\n" ] } ], "source": [ "def exponential_mech(nukes, nukes_high, epsilon):\n", " # Create list of privatized probabilities for each country\n", " nukesX = [4 * i / nukes_high for i in nukes]\n", " nukesX = [np.exp(epsilon * i / (2 * sensitivity)) for i in nukesX]\n", " nukesProb = nukesX / np.linalg.norm(nukesX, ord=1)\n", "\n", " # Pick a country according to the privatized probabilities\n", " choice = rng.choice(countries, 1, p=nukesProb)[0]\n", " place = [y[0] for y in x].index(choice) + 1\n", " \n", " return choice, place\n", "\n", "choice, place = exponential_mech(nukes, nukes_high, epsilon)\n", "\n", "print(f\"Using epsilon {epsilon}, the algorithm chose {choice}, which is the \" +\n", " f\"number {place} best choice.\")" ] }, { "cell_type": "markdown", "id": "3f0a0af7", "metadata": {}, "source": [ "### Analysis" ] }, { "cell_type": "code", "execution_count": 4, "id": "e09e3c58", "metadata": {}, "outputs": [ { "data": { "application/vnd.jupyter.widget-view+json": { "model_id": "0fe00cb9502543f59894a5c989feddde", "version_major": 2, "version_minor": 0 }, "text/plain": [ " 0%| | 0/39 [00:00" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import matplotlib.pyplot as plt\n", "\n", "plt.plot(epsilons, data)\n", "plt.xlabel(\"Epsilon\")\n", "plt.ylabel(\"Mean distance from ideal choice\")\n", "plt.title(\"Effect of epsilon on privacy\")\n", "plt.show()" ] } ], "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.7" } }, "nbformat": 4, "nbformat_minor": 5 }