{ "cells": [ { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "# Getting Started\n", "\n", "This notebook is an introduction to programming in the OpenDP Library. \n", "\n", "Before we get started, the notebook [A Framework to Understand DP](programming-framework/a-framework-to-understand-dp.ipynb) provides useful background. \n", "It explains\n", "\n", "* basic terminology like _sensitivity_ and _epsilon_\n", "* the [OpenDP Programming Framework](programming-framework/index.rst)\n", "* how we define _transformations_, _measurements_, _stability_ and _privacy_" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "--------\n", "\n", "Any constructors that have not completed the proof-writing and vetting process may still be accessed if you opt-in to \"contrib\".\n", "Please contact us if you are interested in proof-writing. Thank you!" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "import opendp.prelude as dp\n", "dp.enable_features(\"contrib\")" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "## The Laplace Mechanism\n", "The Laplace mechanism is a ubiquitous algorithm in the DP ecosystem that is typically used to privatize an aggregate, like a sum or mean.\n", "\n", "An instance of the Laplace mechanism is captured by a _measurement_ containing the following five elements:\n", "\n", "> 1. We first define the **function** $f(\\cdot)$, that applies the Laplace mechanism to some argument $x$. This function simply samples from the Laplace distribution centered at $x$, with a fixed noise scale.\n", "> \n", "> $$f(x) = Laplace(\\mu=x, b=scale)$$\n", ">\n", "> 2. Importantly, $f(\\cdot)$ is only well-defined for any finite float input. This set of permitted inputs is described by the **input domain** `atom_domain(T=f64)`.\n", "> \n", "> 3. The Laplace mechanism has a privacy guarantee in terms of epsilon. \n", "> This guarantee is represented by a **privacy map**, a function that computes the privacy loss $\\epsilon$ for any choice of sensitivity $\\Delta$.\n", "> \n", "> $$map(\\Delta) = \\Delta / scale \\le \\epsilon$$\n", "> \n", "> 4. This map only promises that the privacy loss will be at most $\\epsilon$ if inputs from any two neighboring datasets may differ by no more than some quantity $\\Delta$ under the absolute distance **input metric** `absolute_distance(T=f64)`.\n", "> \n", "> 5. We similarly describe units on the output ($\\epsilon$) via the **output measure** `max_divergence(T=f64)`.\n", "\n", "\n", "\n", "The OpenDP Library consists of _constructor functions_ that can be called with simple arguments and always return valid measurements.\n", "The `make_base_laplace` constructor function returns the equivalent of the Laplace measurement described above.\n", "Since it returns a measurement, you can find it under `dp.m`:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# call the constructor to produce the measurement `base_lap`\n", "base_lap = dp.m.make_base_laplace(\n", " dp.atom_domain(T=float), \n", " dp.absolute_distance(T=float), \n", " scale=5.\n", ")" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "The supporting elements on this transformation match those described above:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "input domain: AtomDomain(T=f64)\n", "input metric: AbsoluteDistance(f64)\n", "output measure: MaxDivergence(f64)\n" ] } ], "source": [ "print(\"input domain: \", base_lap.input_domain)\n", "print(\"input metric: \", base_lap.input_metric)\n", "print(\"output measure:\", base_lap.output_measure)" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "We now invoke the measurement on some aggregate `0.`, to sample $Laplace(\\mu=0., scale=5.)$ noise:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "noisy aggregate: -3.462086040297409\n" ] } ], "source": [ "aggregate = 0.\n", "print(\"noisy aggregate:\", base_lap(aggregate))" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "If we are using `base_lap` on its own, we must know the sensitivity of `aggregate` (i.e. how much the aggregate can differ on two adjacent datasets) to determine epsilon.\n", "In this case, we know `base_lap` has an absolute distance input metric, so the sensitivity should represent the greatest possible absolute distance between aggregates on adjacent datasets." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "epsilon: 2.0\n" ] } ], "source": [ "absolute_distance = 10.\n", "print(\"epsilon:\", base_lap.map(d_in=absolute_distance))" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "This tells us that when the sensitivity is `10`, and the noise scale is `5`, the epsilon consumption of a release is `2`." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "## Transformation Example: Sum\n", "\n", "We package computations with bounded stability into _transformations_.\n", "\n", "A transformation that computes the sum of a vector dataset contains a very similar set of six elements:\n", "\n", "> 1. We first define the **function** $f(\\cdot)$, that computes the sum of some argument $x$.\n", "> \n", "> $$f(x) = \\sum x_i$$\n", "> \n", "> 2. $f(\\cdot)$ is only well-defined for any vector input of a specific type. Each element must be bounded between some lower bound `L` and upper bound `U`. Thus the **input domain** is of type `vector_domain(atom_domain(T=f64))` with elements restricted between `L` and `U`.\n", "> \n", "> 3. The **output domain** consists of any single finite `f64` scalar: `atom_domain(T=f64)`.\n", "> \n", "> 4. The sum transformation has a stability guarantee in terms of sensitivity. \n", "> This guarantee is represented by a **stability map**, which is a function that computes the stability $d_{out}$ for any choice of dataset distance $d_{in}$. In this case $d_{out}$ is in terms of the sensitivity.\n", "> \n", "> $$map(d_{in}) = d_{in} \\cdot \\max(|L|, U) \\le d_{out}$$\n", "> \n", "> 5. This map only promises a sensitivity of $d_{out}$ under the assumption that neighboring datasets differ by no more than some quantity $d_{in}$ under the symmetric distance **input metric** `symmetric_distance()`.\n", "> \n", "> 6. The sensitivity is computed with respect to the absolute distance. This gives units to the output ($d_{out}$) via the **output metric** `absolute_distance(T=f64)`. \n", "\n", "`make_sum` constructs the equivalent of the sum transformation described above.\n", "It is important to note that since the bounds are float, the resulting transformation is calibrated to work for floating-point numbers.\n", "You will need to be careful and intentional about the types you use.\n", "Since it returns a transformation, you can find it under `dp.t`:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [], "source": [ "# call the constructor to produce the transformation `bounded_sum`\n", "# notice that `make_sum` expects an input domain consisting of bounded data:\n", "input_domain = dp.vector_domain(dp.atom_domain(bounds=(0., 5.)))\n", "bounded_sum = dp.t.make_sum(input_domain, dp.symmetric_distance())" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "According to the documentation, this transformation expects a vector of data with non-null elements bounded between `0.` and `5.`. \n", "We now invoke the transformation on some mock dataset that satisfies this constraint.\n", "Remember that since this component is a transformation, and not a measurement, the resulting output is not differentially private." ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10.1" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# under the condition that the input data is a member of the input domain...\n", "bounded_mock_dataset = [1.3, 3.8, 0., 5.]\n", "# ...the exact sum is:\n", "bounded_sum(bounded_mock_dataset)" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "It can help to understand a simple example of how a stability map works,\n", "but going forward you don't need to understand why the maps give the numbers they give in order to use the library.\n", "\n", "\n", "The stability argument for this transformation's advertised sensitivity goes roughly as follows:\n", "\n", "> If the input data consists of numbers bounded between 0. and 5., \n", "> then the addition or removal of any one row can influence the sum by $max(|0.|, 5.)$. \n", "> In addition, if one individual may contribute up to k rows, \n", "> then the sensitivity should further be multiplied by k.\n", "\n", "In practice, the calculated sensitivity may be larger under certain conditions to account for the inexactness of arithmetic on finite data types." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10.00000004656613" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# under the condition that one individual may contribute up to 2 records to `bounded_mock_dataset`...\n", "max_contributions = 2\n", "# ...then the sensitivity, expressed in terms of the absolute distance, is:\n", "bounded_sum.map(d_in=max_contributions)" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "As we would expect, the sensitivity is roughly `2 * max(|0.|, 5.)`." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "## Transformation Example: Clamp\n", "\n", "The sum transformation has an input domain of vectors with bounded elements. \n", "We now construct a transformation that clamps/clips each element to a given set of bounds.\n", "\n", "Instead of listing the components of a clamp transformation as I've done above, going forward you can check the `**Supporting Elements**` section of the relevant API documentation entry:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Help on function make_clamp in module opendp.transformations:\n", "\n", "make_clamp(input_domain: opendp.mod.Domain, input_metric: opendp.mod.Metric, bounds: Tuple[Any, Any]) -> opendp.mod.Transformation\n", " Make a Transformation that clamps numeric data in `Vec` to `bounds`.\n", " \n", " If datum is less than lower, let datum be lower.\n", " If datum is greater than upper, let datum be upper.\n", " \n", " [make_clamp in Rust documentation.](https://docs.rs/opendp/latest/opendp/transformations/fn.make_clamp.html)\n", " \n", " **Supporting Elements:**\n", " \n", " * Input Domain: `VectorDomain>`\n", " * Output Domain: `VectorDomain>`\n", " * Input Metric: `M`\n", " * Output Metric: `M`\n", " \n", " **Proof Definition:**\n", " \n", " [(Proof Document)](https://docs.opendp.org/en/latest/proofs/rust/src/transformations/clamp/make_clamp.pdf)\n", " \n", " :param input_domain: Domain of input data.\n", " :type input_domain: Domain\n", " :param input_metric: Metric on input domain.\n", " :type input_metric: Metric\n", " :param bounds: Tuple of inclusive lower and upper bounds.\n", " :type bounds: Tuple[Any, Any]\n", " :rtype: Transformation\n", " :raises TypeError: if an argument's type differs from the expected type\n", " :raises UnknownTypeException: if a type argument fails to parse\n", " :raises OpenDPException: packaged error from the core OpenDP library\n", "\n" ] } ], "source": [ "help(dp.t.make_clamp)" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "Documentation for specific types may be found behind the following links:\n", "\n", "* [metrics](https://docs.rs/opendp/latest/opendp/metrics/index.html)\n", "* [measures](https://docs.rs/opendp/latest/opendp/measures/index.html)\n", "* [domains](https://docs.rs/opendp/latest/opendp/domains/index.html)" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1.3, 5.0, 0.0, 5.0]" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "input_domain = dp.vector_domain(dp.atom_domain(T=float))\n", "input_metric = dp.symmetric_distance()\n", "\n", "# call the constructor to produce the transformation `clamp`\n", "clamp = dp.t.make_clamp(input_domain, input_metric, bounds=(0., 5.))\n", "\n", "# `clamp` expects vectors of non-null, unbounded elements\n", "mock_dataset = [1.3, 7.8, -2.5, 7.0]\n", "# `clamp` emits data that is suitable for `bounded_sum`\n", "clamp(mock_dataset)" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "According to the API documentation, the input and output metric is set by the user.\n", "We passed in a symmetric distance metric.\n", "Therefore, the stability map accepts a dataset distance describing the maximum number of contributions an individual may make, and emits the same.\n", "\n", "The stability argument for the clamp transformation is very simple:\n", "\n", "> If an individual may influence at most k records in a dataset,\n", "> then after clamping each element, \n", "> an individual may still influence at most k records in a dataset." ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "2" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# dataset distance in... dataset distance out\n", "clamp.map(max_contributions)" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "## Chaining\n", "\n", "The OpenDP library supports chaining a transformation with a transformation to produce a compound transformation, \n", "or a transformation with a measurement to produce a compound measurement.\n", "\n", "When any two compatible computations are chained, all six components of each primitive are used to construct the new primitive.\n", "\n", "A measurement produced from chaining a transformation with a measurement contains the same set of six elements as in previous examples:\n", "\n", "\n", "> 1. A **function** $f(\\cdot)$. When you chain, the output domain of the transformation must match the input domain of the measurement.\n", "> \n", "> $$f(x) = measurement(transformation(x))$$\n", "> \n", "> 2. The **input domain** from the transformation.\n", "> \n", "> 3. The **output domain** from the measurement.\n", "> \n", "> 4. A **privacy_map** $map(\\cdot)$. When you chain, the output metric of the transformation must match the input metric of the measurement.\n", "> \n", "> $$map(d_{in}) = measurement.map(transformation.map(d_{in}))$$\n", "> \n", "> 5. The **input metric** from the transformation.\n", "> \n", "> 6. The **output measure** from the measurement.\n", "\n", "A similar logic is used when chaining a transformation with a transformation.\n", "\n", "We know that the\n", "\n", "* output domain of `bounded_sum` matches the input domain of `base_lap`, and the\n", "* output metric of `bounded_sum` matches the input metric of `base_lap`.\n", "\n", "The same holds for `clamp` and `bounded_sum`.\n", "Therefore, we can chain all of these primitives to form a new compound measurement:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "DP sum: 18.552569770564993\n", "epsilon: 2.000000009313226\n" ] } ], "source": [ "dp_sum = clamp >> bounded_sum >> base_lap\n", "\n", "# compute the DP sum of a dataset of bounded elements\n", "print(\"DP sum:\", dp_sum(mock_dataset))\n", "\n", "# evaluate the privacy loss of the dp_sum, when an individual can contribute at most 2 records\n", "print(\"epsilon:\", dp_sum.map(d_in=max_contributions))" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "## Retrospective\n", "\n", "Now that you have a more thorough understanding of what's going on, we can breeze through an entire release:" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "epsilon: 2.000000009313226\n", "DP sum release: -5.612579341340162\n" ] } ], "source": [ "# establish public info\n", "max_contributions = 2\n", "bounds = (0., 5.)\n", "\n", "# construct the measurement\n", "dp_sum = (\n", " dp.t.make_clamp(dp.vector_domain(dp.atom_domain(T=float)), dp.symmetric_distance(), bounds) >> \n", " dp.t.make_sum(dp.vector_domain(dp.atom_domain(bounds=bounds)), dp.symmetric_distance()) >> \n", " dp.m.make_laplace(dp.atom_domain(T=float), dp.absolute_distance(T=float), 5.)\n", ")\n", "\n", "# evaluate the privacy expenditure and make a DP release\n", "mock_dataset = [0.7, -0.3, 1., -1.]\n", "print(\"epsilon:\", dp_sum.map(max_contributions))\n", "print(\"DP sum release:\", dp_sum(mock_dataset))" ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "## Partial Constructors\n", "\n", "You may notice some redundancy in the code for `dp_sum` above: The output domain of a transformation will always match the input of its successor. We can make this shorter by using `then_*` constructors: These are paired with `make_*` constructors, but delay application of the `input_domain` and `input_metric` arguments. We can rewrite `dp_sum` in an equivalent but more concise form:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "dp_sum = (\n", " (input_domain, input_metric) >>\n", " dp.t.then_clamp((0., 5.)) >>\n", " dp.t.then_sum() >>\n", " dp.m.then_laplace(5.)\n", ")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You'll notice that the start of the chain is special: We provide a tuple to specify the `input_domain` and `input_metric` for `then_clamp`." ] }, { "attachments": {}, "cell_type": "markdown", "metadata": {}, "source": [ "\n", "The next major sections of the documentation each cover a module where you can find constructors:\n", "\n", "* `opendp.transformations`\n", "* `opendp.measurements`\n", "* `opendp.combinators`\n" ] } ], "metadata": { "kernelspec": { "display_name": "psi", "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.11.3" }, "orig_nbformat": 4, "vscode": { "interpreter": { "hash": "3220da548452ac41acb293d0d6efded0f046fab635503eb911c05f743e930f34" } } }, "nbformat": 4, "nbformat_minor": 2 }