机器学习的主要目的是为了从数据中抓取有效信息，而隐私的目的是想要隐藏掉信息（防止个人信息泄露等）。两者看起来有冲突，但是当我们挖掘敏感信息的时候，我们需要平衡这两者之间的关系（保护个人隐私不被泄露的同时抓取到有效信息，从而训练得到一个performance比较好的算法）。所以一个比较常见的方法就是当我们从数据中抓取信息的时候，尽可能的去抓取整个population中比较general的特征，同时保证不透露任何individual的隐私信息。但是往往匿名化数据仍然无法保护个人隐私被泄露。比如说，如果当攻击者掌握了一些其他的泄露信息时，他可以通过合并重叠数据得到他想要的信息。或者通过query多次结果的差异，找到他想要的信息。因此，有人提出，可以把具有相同特征的sample合并成一个group，当整个group中sample数量达到一定程度，可以公开这个group的信息来防止敏感信息被泄露。但是即使这样，攻击者还是可以得到他想要的信息。
比如说，
假设在一个数据库中，包含四个人的地址和收入信息，如果使用“3个匿名”规则：如果有3个人住在同一个城市，他们的城市和收入信息可以被公开）。假设现在攻击者知道了两个人在数据库中的地址是洛杉矶，另外一个人的地址在纽约，所以如果没有任何数据发布，攻击者可以推断出第四个人不住在洛杉矶。
所以通过只释放合并信息的方法并不能防止隐私信息不被泄露。
所以Dwork提出了差分隐私(Differential Privacy)的概念，简单来说就是通过使用随机噪声来确保query公开可见信息的结果并不会因为个体的变化而变化。（有一点类似model stability的感觉，比如我拿走任意一条数据或者增加新的数据并不会对整个model的performance带来很大变化）
比较常见的有三种关于差分隐私的数学定义
Definition 1: a mechanism
is a random function that takes a dataset
as input, and outputs a random variable
.
这个定义的意思就是对结果加一个随机噪声（Gaussian noise或者Laplacian noise都可以）
Definition 2: the distance of two datasets,
, denotes the minimum number of sample changes that are required to change
.
这个定义了用来表示从数据集
变成数据集
的最小的数据变化量。举一个简单的例子，如果两个数据集
和
最多只相差一条数据，那么
. 我们又把这样的pair (D, D') 叫做邻近数据集（dataset neighbours，不知道是不是这么翻译的）。
Definition 3: a mechanism
)-differential privacy for two non-negative numbers
and
iff for all neighbours
of
定义3就是由Dwork提出的差分隐私的default定义了，通过加入随机噪声，输出一个结果的概率分布(that's the reason we use probability on both sides)。定义中的表示，当对于数据集和它的任意邻近数据集（表示每一条数据都需要满足），这个机制的结果变化超过
因数的概率（其实就是把不等式右边第二项移到左边）。所以
代表了这个机制的confidence（值越小越confident），
则表示了隐私保护的标准（值越小，标准越严格，所以又叫做privacy budget）。简而言之，就是当
和
越小的时候，两个probability就越相近，因此隐私保护的就越好。
当我们选择的时候，我们要注意，当数据集中有n个samples时，
必须要小于1/n。因为显而易见，这个机制可以满足
-differential privacy，但是如果当
的值偏大时，这个机制有很高的概率会导致隐私泄漏。对于这个数据集中的每一条数据，都有
概率会被release出来，因为release每一条不同的数据都是独立的，所以相当于这个机制可以release了
个sample。所以为了防止这样的泄露，
必须要小于1/n.
通常，当的时候，我们又把这个叫做
-differential privacy. 当
的时候，
-differential privacy仍然有
的几率会导致信息泄露，但是当
的时候，就表示，泄露的概率为0，也就是说这个隐私保护不是概率性的，所以
-differential privacy的定义要远强于
-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
