差分隐私 - Differential Privacy [1. 定义]

机器学习的主要目的是为了从数据中抓取有效信息，而隐私的目的是想要隐藏掉信息（防止个人信息泄露等）。两者看起来有冲突，但是当我们挖掘敏感信息的时候，我们需要平衡这两者之间的关系（保护个人隐私不被泄露的同时抓取到有效信息，从而训练得到一个performance比较好的算法）。所以一个比较常见的方法就是当我们从数据中抓取信息的时候，尽可能的去抓取整个population中比较general的特征，同时保证不透露任何individual的隐私信息。但是往往匿名化数据仍然无法保护个人隐私被泄露。比如说，如果当攻击者掌握了一些其他的泄露信息时，他可以通过合并重叠数据得到他想要的信息。或者通过query多次结果的差异，找到他想要的信息。因此，有人提出，可以把具有相同特征的sample合并成一个group，当整个group中sample数量达到一定程度，可以公开这个group的信息来防止敏感信息被泄露。但是即使这样，攻击者还是可以得到他想要的信息。

比如说，

假设在一个数据库中，包含四个人的地址和收入信息，如果使用“3个匿名”规则：如果有3个人住在同一个城市，他们的城市和收入信息可以被公开）。假设现在攻击者知道了两个人在数据库中的地址是洛杉矶，另外一个人的地址在纽约，所以如果没有任何数据发布，攻击者可以推断出第四个人不住在洛杉矶。
所以通过只释放合并信息的方法并不能防止隐私信息不被泄露。

所以Dwork提出了差分隐私(Differential Privacy)的概念，简单来说就是通过使用随机噪声来确保query公开可见信息的结果并不会因为个体的变化而变化。（有一点类似model stability的感觉，比如我拿走任意一条数据或者增加新的数据并不会对整个model的performance带来很大变化）

比较常见的有三种关于差分隐私的数学定义

Definition 1: a mechanism $\tilde f$ is a random function that takes a dataset $D$ as input, and outputs a random variable $\tilde f(D)$ .

这个定义的意思就是对结果加一个随机噪声（Gaussian noise或者Laplacian noise都可以）

Definition 2: the distance of two datasets, $d(D,D')$ , denotes the minimum number of sample changes that are required to change $D$ into $D'$ .

这个定义了用 $d(D,D')$ 来表示从数据集 $D$ 变成数据集 $D'$ 的最小的数据变化量。举一个简单的例子，如果两个数据集 $D$ 和 $D'$ 最多只相差一条数据，那么 $d(D,D') = 1$ . 我们又把这样的pair (D, D') 叫做邻近数据集（dataset neighbours，不知道是不是这么翻译的）。

Definition 3: a mechanism $\tilde f$ satisfies ( $\epsilon,\delta$ )-differential privacy for two non-negative numbers $\epsilon$ and $\delta$ iff for all neighbours $d(D,D')$ = 1, and all subset $S$ of $\tilde f$ 's range, as long as the following probabilities are well-defined, there holds
$P(\tilde f(D) \in S) \le \delta + e^\epsilon P(\tilde f(D') \in S)$

定义3就是由Dwork提出的差分隐私的default定义了，通过加入随机噪声，输出一个结果的概率分布(that's the reason we use probability on both sides)。定义中的 $\delta$ 表示，当对于数据集和它的任意邻近数据集（表示每一条数据都需要满足），这个机制的结果变化超过 $e^\epsilon$ 因数的概率（其实就是把不等式右边第二项移到左边）。所以 $\delta$ 代表了这个机制的confidence（值越小越confident）， $\epsilon$ 则表示了隐私保护的标准（值越小，标准越严格，所以又叫做privacy budget）。简而言之，就是当 $\delta$ 和 $\epsilon$ 越小的时候，两个probability就越相近，因此隐私保护的就越好。

当我们选择 $\delta$ 的时候，我们要注意，当数据集中有n个samples时， $\delta$ 必须要小于1/n。因为显而易见，这个机制可以满足 $(0,\delta )$ -differential privacy，但是如果当 $\delta$ 的值偏大时，这个机制有很高的概率会导致隐私泄漏。对于这个数据集中的每一条数据，都有 $\delta$ 概率会被release出来，因为release每一条不同的数据都是独立的，所以相当于这个机制可以release了 $n \delta$ 个sample。所以为了防止这样的泄露， $\delta$ 必须要小于1/n.

通常，当 $\delta=0$ 的时候，我们又把这个叫做 $\epsilon$ -differential privacy. 当 $\delta > 0$ 的时候， $(\epsilon,\delta)$ -differential privacy仍然有 $\delta$ 的几率会导致信息泄露，但是当 $\delta = 0$ 的时候，就表示，泄露的概率为0，也就是说这个隐私保护不是概率性的，所以 $\epsilon$ -differential privacy的定义要远强于 $(\epsilon,\delta)$ -differential privacy。

Reference:
[1]. Ji, Zhanglong, Lipton, Zachary C., Elkan, Charles, Differential Privacy and Machine Learning: a Survey and Review.
[2]. Cynthia Dwork, Differential Privacy: A Survey of Results

差分隐私 - Differential Privacy [1. 定义]

推荐阅读更多精彩内容