SDS-2.x, Scalable Data Engineering Science

%md

###### by [Christoffer Långström](https://www.linkedin.com/in/christoffer-l%C3%A5ngstr%C3%B6m-7a460514b/)

This is part 3 of the in a series of notebooks discussing different aspects on privacy preserving methods in data science. 

Differential privacy, originally proposed by Cynthia Dwork et. al (2006) treats the problem of privacy from the perspective that simply being included in a data set is a risk. The solution proposed through diffential privacy is to make it so that a data set that contains a certain individual is not meaningfully differentiable from the same data set with that person removed. 

The proposal was to make it so that a random algorithm could be considered epsilon diff. private if the distribution of the estimator does not "change much" with the inclusion/exclusion of any particular individual, with epsilon being the "privacy factor" that quantifies to what extent the distributions differ. See below for more details. 

The advantage of this approach is that we can now quantify the degree of privacy of a random algorithm, and start to develop methods that enforce a desired level of privacy in an algorithm. Further, there is research being done (Duchi et. al) on *local* differential privacy, where the true data is kept hidden from even the data scientist working on it, by applying differentially private mechanisms to the data, before any statistics is computed. The type of privacy preserving mechanism that is applied depends on the application, where min/max optimal estimators are found for several canonical statistical problems. 

### Links:

* Introduction to DP in the context of network protocols:  
[Diffential Privacy at IETF104 by Amelia Andersdotter and Christoffer Långström](https://www.youtube.com/watch?v=PlSX-o36Wus&feature=youtu.be&t=3809)

* Locally private statistical procedures:  
[Minimax Optimal Procedures for Locally Private Estimation](https://arxiv.org/abs/1604.02390)

* Original DP paper:  
[Cynthia Dwork et. al](http://people.csail.mit.edu/asmith/PS/sensitivity-tcc-final.pdf)

def frameIt( u:String, h:Int ) : String = {
      """<iframe 
 src=""""+ u+""""
 width="95%" height="""" + h + """"
 sandbox>
  <p>
    <a href="http://spark.apache.org/docs/latest/index.html">
      Fallback link for browsers that, unlikely, don't support frames
    </a>
  </p>
</iframe>"""
}

displayHTML(frameIt("https://en.wikipedia.org/wiki/Differential_privacy#Definition_of_ε-differential_privacy",350))

%md 
One of the first suggested approaches to enforcing e-differential privacy was by introducing "noise" to the ouput of estimators. This approach works as thus: For a dataset *X*, compute the statistic *T(X)*, generate some noise *W*, return *T(X) + W* as the result. If *W* is symmetric noise, and chosen in such a way that it does not greatly distort the data, the goal is to achieve reasonably good estimates that cannot be meaningfully reversed engineered to 
reveal information on the people included in the data set. 

####The Laplace Mechanism

This approach to adding noisy data involves adding samples from a standard laplace distribution, with the scale parameter chosen depending on the sensitivity of the data and the desired privacy level. The laplace distribution is a symmetric "double exponential" distribution with slim tails and a sharp center, here taken to be at the origin. The algorithm for applying laplace noise to a data set is as follows:

Let *D* be a data set and *T* a statistic to be computed, and *epsilon* the desired degree of privacy. 
* Compute the sensitivity \\( \Delta(T(D)) \\) of the statistic T to changes in the data set D
* Generate noise W = \\( Laplace(\Delta(T(D))/ \epsilon) \\)
* Compute & return the result \\( T'(D) = T(D) + W \\)

The statistic *T'* is now an \\( \epsilon \\)- differentially private version of *T*, as defined above. 

##### Some notes: 
* For small values of  \\( \epsilon \\) (i.e high degrees of privacy) significant levels of noise is added and so the values of *T'* will exhibit large variance for repeated queries and may provide unaccetably poor performance in most applications. 

* This approach only protects against information being divulged from the output of T by an adversiarl party, the data still needs to be stored safely by a trusted holder. This is the problem adressed by local DP, discussed below.  

%md
<img src="http://i.imgur.com/eMoJkND.png" alt="drawing" width="500"/>


#### Read More in the paper:
[Additive Noise Models in Deep Learning](https://arxiv.org/abs/1607.00133)

%md

This approach, as suggested by Duchi, Jordan, et. al, is based on privatizing the data before any statistics are computed, effectively meaning that the data is hidden even from the data scientist. Their suggestion is to apply a differentially private mechanism to the data and provide such mechanisms for some canonical problems. 



####Add more details

%md 
#### Experiment setup: 
As an example application, [Duchi et. al](https://arxiv.org/abs/1604.02390) considers the problem of estimating means of drug use related hospitalizations. In the original problem, they have records of hospitalization of the form (drugs, year, # of hospitalizations) where the number of hospitalizations denotes how many people that year where admitted and used a certain drug. Many of the admitted individuals used several drugs, as the number of drugs were vastly larger than the number of admittances. We will use this information to generate a data set of measurements of the form  \\( X_i \in {0,1}^d \\) representing one admission; a component *j* is 1 if the patient used drug *j* and 0 else. The usage frequency will be uniformly distributed over the samples generated, with only the constraint 
that the total number of admittances using drug *j* matches a preset number. This means that if there were *n* patients and *k* of them used drug *j* then \\( X_ij = 1 \\) with probability *k/n*. 


#### Methods: 
We have N = 1000 measurements of \\( X_i \in {0,1}^d \\) for *d = 27*, with a preset vector of admittance frequency. The problem is to estimate the mean of this population, \\( \theta = E(X) \\) and we will use three different approaches: 
* Non-private estimation
* Min/Max optimal local privacy mechanism
* Local Laplace Noise 

Non-private estimation is simply the sample mean of the raw data, which is the "gold standard" of estimates that private methods are necesserally worse than. The min/max locally private mechanism consists of generating a new sample from the raw data which is sequentially dependent, in such a way that the new sample is differntially private and min/max optimal w.r.t to an arbitray loss function. This can be compared by the theoretical lower bound obtained in the paper. Lastly, one can compare this to a "naive" local privacy mechanism of adding *laplace(epsilon/d)* distributed noise to the data before estimation. Each method is analyzed through the l-infinity norm of the deviation from the full sample mean, as a function of the sample size.