Stability of Data Transformations

A transformation is a computation that maps a dataset to another dataset, or maps a dataset to an aggregate. Consider a transformation that squares each element ina dataset: $f\left(x\right)=x^2$. Then given the dataset $X=\{1,2,3\}$, the transformed data is:

$f\left(X\right)=\{1,4,9\}$

This transformation operates on each row independently and returns a transformed dataset with the same number of rows. Such a transformation is called a row-by-row transformation. Such row-by-row transformations are rather common; you will find them useful as you learn more about DP.

The mean is another example of a transformation - one that maps a dataset to value computed from an aggregate of the data. Taking the same dataset, we can compute

$\mu \left(X\right)=\frac{1+2+3}{3}=2$

In this case, the result of the transformation is a single value, not a dataset. This single value takes the data in aggregate and returns a value that describes a property of the dataset. We’ll generally refer to such transformations as aggregators.

In this chapter, we are interested in transformations with bounded stability. Stability is a property of a transformation that guarantees that similar inputs map to similar outputs. If a transformation maps similar inputs to similar outputs, then we say it is stable.

You might be wondering what we mean by similar here - great question. Mathematically speaking, you will always want to be precise with your notions of similarity and closeness. Much like you say a release is "$ϵ$-private,” you will also say that a transformation $T$ is "$c$-stable.” Relative to the absolute distance, this means that whenever $|u-v|\le d_{in}$, then it is also true that $|T\left(u\right)-T\left(v\right)|\le c·d_{in}$. In other words, inputs that are within $d_{in}$ distance from each other will result in outputs which are no further apart than $c·d_{in}$ from each other.

Stability may already feel familiar to you, because stability is a generalization of sensitivity. Recall the definition of sensitivity from the previous chapter:

Recall that $A\sim B$ requires that A and B are similar; the distance between them is bounded. The sensitivity is a form of stability - it guarantees that, when any two input datasets A and B are similar, the outputs are similar.

import opendp.prelude as dp
input_space = dp.vector_domain(dp.atom_domain(T=float)), dp.symmetric_distance()

clip_trans = input_space >> dp.t.then_clamp((0., 10.))

mock_dataset = np.random.normal(0., scale=10.)
transformed_dataset = clip_trans(data)

Example: DP Analysis of Income Data

Suppose you have a dataset of individuals and their annual incomes. The least amount they can be paid per year is $0, but it is unclear what the maximum is. For this reason, your data is on the domain $[0,\infty )$.

In this case, you would need to use outside domain knowledge to estimate a good maximum given the dataset. If you set it very high, you are almost guaranteed to not cut off any of the values, but your sensitivity will suffer. Conversely, if the maximum is set too low, then you will clip too many values and lose utility in your final statistic.

import numpy as np
import opendp.prelude as dp

def release_dp_mean(bounds, contributions, epsilon):
    context = dp.Context.compositor(
        data=data,
        privacy_unit=dp.unit_of(contributions=contributions),
        privacy_loss=dp.loss_of(epsilon=epsilon),
        split_evenly_over=2
    )

    numerator = context.query().clamp(bounds).sum().laplace().release()
    denominator = context.query().count().laplace().release()
    return numerator / denominator

pr = []
true_mean = sum(data) / len(data)
print(f"True mean: {true_mean}
")

print("Mean	Utility")
for upper in [50., 75., 90., 100.]:
    clipped_dp_mean = release_dp_mean((0., upper), contributions=1, epsilon=1.)
    utility = abs(clipped_dp_mean - true_mean)
    print(f"{clipped_dp_mean}	{utility}")

Categorical Data Transformations

Categorical data is, as its name suggests, data that be divided into different categories.

In this case, you can aggregate the vehicles by the column “Vehicle Type” and generate a count: 2 cars, 2 trucks, 1 motorcycle. The possible categories (car, truck, motorcycle) are also known as the keys.

When dealing with categorical data, the set of keys might be entirely known or only partially known. In some cases, the set of keys is clear and well known. For example, consider a census survey. If there is a question related to citizenship status, there are only two possible keys: citizen or non-citizen. If a data analyst decides to create a histogram of citizenship status, the data analyst will query the number of individuals whose status is “citizen” and the number of individuals whose status is “non-citizen.”

The data analyst does not know how many individuals are in each category, so they will query the count of citizens and the count of non-citizen individuals. In this query, an individual belongs to either the category “citizen” or “non-citizen”, so all neighboring databases will have the same set of categories.

Next, consider an illustrative example where a data analyst queries citizenship status statistics from a database:

The data analyst queries the count of individuals with Citizenship Status == Citizen and the count of individuals where Citizenship Status == non-Citizen. These two queries represent the citizenship status histogram. In this case, adding or subtracting individuals from this database will not change the key set in the histogram, since the only two options are “citizen” and “non-citizen.”

If the analyst builds a histogram of citizenship counts from this table, it will appear like so:

Figure 4-1. Histogram of citizenship status (non-private)

This dataset contains an example of a categorical variable with a known key set. Because the key set is known, the set of keys is consistent over all possible neighboring databases. There is no third possible key that can be introduced here - the category is binary. If the data analyst wants to release a differentially-private histogram of citizenship statuses of individuals in a database, they can use a differentially private count query on the database. Because the keys are known, the DP count query will provide a differentially private data release.

Recall from chapter 3 that DP has the parallel composition property: this means that performing a $ϵ$-DP operation on different (non-overlapping) parts of a dataset is still $ϵ$-DP. Further, the total $ϵ$ does not increase with the number of subsets. Using this definition, we can apply a DP count function to each bin in the histogram, adding noise separately to each bin.

An example of a DP count with noise addition could look like this:

Figure 4-2. Histogram of citizenship status (private)

Note that the counts are close to the true values of 7 and 3.

Adding or subtracting individuals from this database will not affect the key set, since there are only two fixed options. The possible key set always remains the same independently of the individuals in the dataset.

When categorical variables have a wider variety of possible categories, you may encounter a scenario in which the key set of the categorical variable is unknown. Consider an example where a data analyst is building a histogram from the same dataset, but this time based on job titles. The job titles are self-reported by the individuals, meaning that the set of possible job titles is not known ahead of time.

Suppose the data analyst decides to make a GROUP BY query, getting the counts of individuals for each job title:

Figure 4-3. Histogram of job titles (non-private)

And the differentially private version of the histogram is

Figure 4-4. Histogram of job titles (private)

Now, suppose that Elionore Gillbard requests that her data be redacted from the database. The new database without Elionore Gillbard is a neighboring database. The new histogram produced by the data analyst will look like so:

[[histogram_of_job_titles_of_a_neighboring database]] .Histogram of job titles of a neighboring database (non-private) image::images/ch4_fig4.png["query database without Barb"]

Applying differential privacy to the counts will result in the following histogram

Figure 4-5. Histogram of job titles of a database (private) .

When comparing the histogram from Figure 4-4 with the histogram from Figure 4-6, it is easy to notice that there is a privacy violation happening in the data release. Both histograms should be differentially private, and yet they are leaking information. Based on a quick inspection, you can infer that the job title of the person who left the database is “Actor.”

To overcome this issue, the data analyst should pre-define the key set before making the analysis. In the case of the job titles variable, the data analyst can create a set of job titles based on their previous knowledge of possible answers to the question of “what is your job title?” In addition to the job titles that the data analyst includes in the pre-defined set, the data analyst can define a category “other” that will include new job titles and outliers.

Now let’s understand how the pre-defined key set is defined and used to make differetially private queries to categorical data in the following example.

Example: Histogram Queries

Let’s consider the database described in Table 4-4. To query a differentially private histogram of job title, the data analyst will:

• Define the key set of the categories in the histogram based on previous information

• Count the number of individuals in each of the pre-defined categories

The data analyst starts by defining the following job titles categories as the key set for the data analysis:

• Accountant

• Teacher

• Engineer

• Other

The histogram maps the job titles Accountant, Teacher, and Engineer to equivalent categories in the key set, while the job titles Actor and Medical Doctor are mapped to the category Other. The non-private histogram of job counts appears like so:

Figure 4-6. Histogram of job titles with a pre-defined key set

The private histogram has a very similar appearance, with noise added to the counts using a Laplace mechanism with $ϵ=1$:

Figure 4-7. Histogram of job titles with a pre-defined key set.

Notice that with this configuration, any individual, with any job title, can be added or deleted from the database without resulting in privacy violations. In contrast to the previous example, any unexpected job title will simply be mapped to Other.

Suppose Marta James, an architect, is added to the database:

Table 4-4. Job title associated with each user in the data

First Name	Last Name	Budget	Job Title	Citizenship Status
Caryl	Baptie	$898,031.59	Accountant	Citizen
Moyra	Leverson	$847,791.81	Teacher	non-Citizen
Elinore	Gillbard	$729,605.84	Actor	Citizen
Farleigh	Crampton	$9,742,235.31	Engineer	Citizen
Sebastien	Marples	$3,677,589.94	Teacher	non-Citizen
Baxy	Doohan	$1,044,044.63	Medical Doctor	Citizen
Henrie	Whawell	$4,670,377.71	Accountant	Citizen
Dorothy	Drummer	$2,641,401.28	Teacher	Citizen
Meaghan	Clinnick	$989,042.50	Accountant	non-Citizen
Tildy	Gutans	$5,986,640.99	Engineer	Citizen
Marta	James	$9,480,446,38	Architect	non-Citizen

The pre-defined key set prevents the new histogram configuration from adding a job title Architect in the histogram, and potentially leaking the addition of Marta to the dataset.

Summary

Exercises

1. Identify the following transformations as either aggregates or general transformations. If they are not aggregates, specify their range. Construct a limitation on their input so that the stability is defined.

   1. f(x, min, max) = x if x in [min, max]

   2. $f\left(x\right)=\frac{1}{\left|x\right|}{\sum }_{i}x$

   3. $f\left(x\right)=x^2$

   4. $f\left(\overrightarrow{x}\right)=A\overrightarrow{x}$ where $A=\left.\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 1& 0\end{array}\right)$

2. Generate an array of 1000 random floats using a library like NumPy.

   1. Calculate the mean of the data

   2. Calculate the 5th and 95th percentiles for the data

   3. Clip these values

   4. Recompute the mean - how has it changed?

   5. Repeat c and d with trimming

3. Prove that DP observes parallel composition