{
"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": 146,
"metadata": {},
"outputs": [],
"source": [
"from opendp.mod import enable_features\n",
"enable_features(\"contrib\")"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"## The Laplace Mechanism\n",
"The Laplace mechanism is a ubiquitous algorithm in the DP community that is 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 six 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** (denoted `AllDomain`).\n",
">\n",
"> 3. The set of possible outputs is described by the **output domain** (also `AllDomain`).\n",
"> \n",
"> 4. 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 <= \\epsilon$$\n",
"> \n",
"> 5. This map only holds if the same aggregation applied to any two neighboring datasets may differ by no more than some quantity $\\Delta$ under the absolute distance **input metric** (`AbsoluteDistance`).\n",
"> \n",
"> 6. We similarly describe units on the output ($\\epsilon$) via the **output measure** (`MaxDivergence`).\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."
]
},
{
"cell_type": "code",
"execution_count": 147,
"metadata": {},
"outputs": [],
"source": [
"from opendp.measurements import make_base_laplace\n",
"\n",
"# call the constructor to produce the measurement `base_lap`\n",
"base_lap = make_base_laplace(scale=5.)"
]
},
{
"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": 148,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"noisy aggregate: -9.028542355622688\n"
]
}
],
"source": [
"aggregate = 0.\n",
"print(\"noisy aggregate:\", base_lap(aggregate))"
]
},
{
"attachments": {},
"cell_type": "markdown",
"metadata": {},
"source": [
"We must know the sensitivity of `aggregate` 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": 149,
"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 `VectorDomain>` and contains `L` and `U`.\n",
"> \n",
"> 3. The **output domain** consists of any single finite `f64` scalar: `AllDomain`.\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} * max(|L|, U) <= d_{out}$$\n",
"> \n",
"> 5. This map only holds if neighboring datasets differ by no more than some quantity $d_{in}$ under the symmetric distance **input metric** (`SymmetricDistance`).\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** (`AbsoluteDistance`). \n",
"\n",
"`make_bounded_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."
]
},
{
"cell_type": "code",
"execution_count": 150,
"metadata": {},
"outputs": [],
"source": [
"from opendp.transformations import make_bounded_sum\n",
"\n",
"# call the constructor to produce the transformation `bounded_sum`\n",
"bounded_sum = make_bounded_sum(bounds=(0., 5.))"
]
},
{
"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": 151,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10.1"
]
},
"execution_count": 151,
"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 finite data types."
]
},
{
"cell_type": "code",
"execution_count": 152,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"10.00000004656613"
]
},
"execution_count": 152,
"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": 153,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Help on function make_clamp in module opendp.transformations:\n",
"\n",
"make_clamp(bounds: Tuple[Any, Any], TA: Union[ForwardRef('RuntimeType'), _GenericAlias, str, Type[Union[List, Tuple, int, float, str, bool]], tuple] = None) -> 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: `SymmetricDistance`\n",
" * Output Metric: `SymmetricDistance`\n",
" \n",
" :param bounds: Tuple of inclusive lower and upper bounds.\n",
" :type bounds: Tuple[Any, Any]\n",
" :param TA: Atomic Type\n",
" :type TA: :py:ref:`RuntimeTypeDescriptor`\n",
" :rtype: Transformation\n",
" :raises TypeError: if an argument's type differs from the expected type\n",
" :raises UnknownTypeError: if a type argument fails to parse\n",
" :raises OpenDPException: packaged error from the core OpenDP library\n",
"\n"
]
}
],
"source": [
"from opendp.transformations import make_clamp\n",
"help(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": 154,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[1.3, 5.0, 0.0, 5.0]"
]
},
"execution_count": 154,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# call the constructor to produce the transformation `clamp`\n",
"clamp = make_clamp(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 `SymmetricDistance`.\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": 155,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"2"
]
},
"execution_count": 155,
"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": 156,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"DP sum: 13.705564590232404\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": 157,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"epsilon: 2.000000009313226\n",
"DP sum release: 5.988716324791998\n"
]
}
],
"source": [
"from opendp.transformations import *\n",
"from opendp.measurements import *\n",
"\n",
"# establish public info\n",
"max_contributions = 2\n",
"bounds = (0., 5.)\n",
"\n",
"# construct the measurement\n",
"dp_sum = make_clamp(bounds) >> make_bounded_sum(bounds) >> make_base_laplace(5.)\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": [
"\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.8.13 (default, Mar 16 2022, 20:38:07) \n[Clang 13.0.0 (clang-1300.0.29.30)]"
},
"orig_nbformat": 4,
"vscode": {
"interpreter": {
"hash": "3220da548452ac41acb293d0d6efded0f046fab635503eb911c05f743e930f34"
}
}
},
"nbformat": 4,
"nbformat_minor": 2
}