DP-Differential Privacy概念介绍

• 我们希望的是在保证数据可用的前提下，尽可能少地泄露隐私
• 我们希望我们对数据的查询“几乎”得不到你的信息。也就是说，你在这个数据库中和你不在这个数据库中两种情况下我对数据库的查询得到的结果“几乎”一样，我们就更倾向于你的隐私得到了保护。也就是说我们希望：、
  你在不在数据库中，我得到的结果都是差不多的
• 既然在数据库中和不在数据库中结果都一样了，那肯定就意味着数据可用性为0了。所以“几乎”二字很重要，“几乎”的程度也就表示着隐私保护的力度。

相邻数据集的概念

• **如果两个数据集只相差一条记录，那么这两个数据集是“相邻数据集”。**在这基础上，如果对于相邻数据集的查询结果相近，那么那相差的一条记录的隐私就得到了保护。
  
• 有一个自然而然的问题就是，得到了多大程度的保护，直观上我们有：

如果对相邻数据集的查询结果越像，那么隐私保护力度越大

差分隐私的概念

如果对于任何一个可能查询结果，机制M对于任何相邻数据集的查询结果都不可区分，那么就说机制M是满足差分隐私机制的。epsilon称为隐私预算（budget）。通常而言，budget越小，隐私保护程度越高，数据可用性越差。（这里的delta可以忽略不看）

exp()是高等数学里以自然常数e为底的指数函数。

上述定义的两点体会

• （x, y）是无序的，我们用概率比值来衡量他们的相似程度
• 相邻数据集意味着对每一条记录都提供保护

根据这个定义，研究者就可以对数据集进行分析，而保证任何一个数据集中的个体的隐私都不会被泄露
那么如何理解该定义？首先需要知道什么是M以及为何M的输出是概率性的

问题1 - 查询不应该是确定性的吗？为何会有概率？】
在当前的很多隐私保护模型中，查询结果确实是确定性的。差分隐私机制引入的“随机化”就是通过将确定的输出以概率的方式呈现（可以理解为，以一定概率说假话）。

问题2 - 将确定性的结果概率化难道不会导致不精确吗？

• 这需要回到数据分析的目的：数据可用性
• 在大数据环境下，我们关心的是数据集中数据呈现出来的性质，规律等，而非单一个体的性状。
• 要保障个人的隐私，必然会导致数据分析中引入误差。
• 我们希望控制误差，差分隐私实际上也正是隐私保护程度和数据可用性之间的权衡
• 下图两条曲线，两条曲线之间有差值，两条曲线的差值是sensitivity
  

应用

• DP只是一个定义，最初的DP甚至只是一种对隐私保护的一种至高目标，如何设计出满足DP机制的随机化算法M才是研究人员最关心的问题。
• 如何设计机制M，先不给出，仅仅先给出一个案例

案例研究 - 如何通过抽样统计人群中抽烟人数的比例？

• 对于被调查者，是不希望直接回答自己抽烟与否的，因为在一定程度上，抽烟是一种和个人隐私紧密相关的问题。

只需要通过一枚硬币，就可以以差分隐私的方式解决这个问题。这个方法叫做Coin Flipping：
（1）扔一枚硬币，如果正面朝上，老实回答自己是否抽烟
（2）如果反面朝上，则重复扔一枚硬币，如果正面朝上就回答“抽烟”，反面朝上就回答“不抽烟”。

数据有效性（Utility）

• 首先我们来看这个机制是否可以解决问题，我们用Pa表示被调查者抽烟的概率（即我们想获得的结果，用Pb表示我们收集到的抽烟人数的比例，则根据上面的过程有：

   					Pb = 0.5Pa + 0.25
  

因此 ：Pa=2Pb-0.5

所以根据统计的Pb可以估计出Pa，这个估计人群吸烟比例的方法是正确的（假设有足够多的样本）。

隐私性

• 数据有效性是对数据整体而言的特性，而隐私就更涉及到和个人有关。
• 理想情况下，最好的隐私保护策略就是随机回答，但是随机回答会导致数据完全没有真实性。
• 我们看一下CoinFlipping的过程，首先有：

S=[‘抽烟’, ‘不抽烟’]
因此我们可以计算出

P['抽烟' | '抽烟'] = 0.75

P['抽烟' | '不抽烟'] = 0.25

P['不抽烟' | '不抽烟'] = 0.75

P['不抽烟' | '抽烟'] = 0.25

P(a∣b)是条件概率公式，其中P(a|b)表示事件b已经发生的情况下，事件a发生的概率。
公式为： P(a|b) = P(ab)/P(b)

• 那么我们自然而然就计算出了epsilon=ln 3，所以我们说Coin Flipping 机制是提供了ln 3-DP的。
• 直观感觉上来说，Coin Flipping是比较能保护隐私的，因为即使某人回答抽烟，我们只能得到他很可能抽烟（保证数据有效性），而无法确定（隐私性）。

待续
上面提到的一个应用仅仅针对二值回答才有效，**如何对一般性的查询设计出一个满足差分隐私的随机化查询机制M呢？**在DP的定义一出来之后，不就便广受研究人员的关心。