在差分隐私中，为什么需要消耗隐私预算？ 第1页

另一个答主解释得很清晰，他是从减预算的角度。我就从另一个角度说下自己的理解。

隐私预算ε衡量的是隐私保护程度，ε越小，说明对隐私保护程度越高。

假如第一次查询时满足ε-DP，即每次查询的隐私预算是ε，对隐私保护程度是80%（只是直观的表示），也就是说攻击者只能得到20%有效的信息。

继续第二次查询，攻击者再次得到20%有效的信息，如果从两次得到的有效信息中他能判断出25%真实的信息，这时说明隐私的保护程度只有75%，也就是说保护程度下降了，ε会增大。

……以此继续查询，ε会继续增大，这说明到很多次查询后就没有隐私了（？

这当然是个可怕的事情，所以要设置一个ε的最大值，到达这个值后就不允许再查询，或者就完全随机，不能再给出任何有效信息了。

我所说的这个角度就相当于我设定今天最多只能用10元（好惨），第一次用了1元，第二次又用了一元，所花的钱一直累加直到10元就不能再用。

消耗隐私预算的角度就相当于，第一次用了1元，还剩9元，第二次用完还剩8元，计算的是剩余的钱，每花一笔就要消耗所剩的钱。

具体算法如何消耗，或者说ε在多次查询后是如何变大的就要涉及组合机制问题了。

组合机制其实就是解释n次独立同分布的查询后，ε以什么机制增大，是线性还是非线性？这类问题

在DP中，为了保护隐私，我们采用的是添加噪声的方式（当然，添加噪声不是唯一的方式），通常来说，为了保证数据的可用性，所添加的噪声有这样一个特性：噪声的期望是0。比如最经典的拉普拉斯机制，我们通过敏感度设置的是Laplace的方差，添加的噪声实际上是 ，其中 是Laplace分布的位置参数和尺度参数。

这就意味着，如果噪声是独立同分布的，那么我对多个噪声求平均，就在一定程度上可以使得噪声的值更接近0。在DP中，噪声接近0就意味着隐私保护程度的下降。

在理解消耗隐私预算之前，我举一个采用RR（Random Response）的例子，RR也有人叫Coin Flipping，严格来说这是Local Differential Privacy中的概念。假设你是数据收集的对象，有一个1bit数据保护表示你是否抽烟（暂定你的数据 ，并且我作为数据收集者是不知道这个 的）。以下是我们的数据收集协议：

1. 数据收集者规定概率
2. 用户以概率 发送真实值（ ），以概率 发送非真实值（ ）

根据DP的定义，其中有：

也就是说这个协议的隐私保护程度为 。那问题来了，如果根据这个协议，我问你两次呢？我们知道在问你两次的情况下，你的输出可能是 ，这时候我们想知道隐私保护程度是多少呢？

所以我们这时候的保护程度是 了。那么为什么 会变大（ ）呢？本质上来说，这是因为所引入噪声是独立同分布的。如果可以一直查询下去，我们可以以任意的精度反推出x是0还是1。比如，在这个例子中，我问了你一百次，其中有65次你回答1，有35次你回答0，那么显然，用户的数据就是1了（不是说没可能是0，而是我们有很大很大的把握说是1）。

那么我们怎么避免对数据集查询的人（就称其为攻击者吧）依据这个原理反推出数据呢？一种傻瓜式的操作是这样：

假设我根据我机制的设计，单个查询的隐私保护程度为 ，然后我总的允许用户推断出的隐私保护程度为 ，那也就意味着我允许用户一共进行10次查询。所以，我认为分配给这个查询者的隐私预算为 ，然后这个用户每次进行一个查询，我就给他扣掉1。

这个过程有点像对查询者的信任程度，每一次查询，查询者就有可能以一定的概率反推出数据，所以其信任程度就降低了，一旦到达了我允许的总的privacy budget，就意味着查询者再查询下去的话，我的数据就可能以我所不能忍受的精度反推出来。

实际上，作为数据的拥有者，其关心的不是怎么去扣查询者的privacy budget，其关心的是查询者经过 次查询之后，总的privacy-preserving level是多少。限制查询次数，就是保证总的privacy-preserving level还是那么多。

说到这里大概已经能解释为什么每次查询之后隐私预算要扣掉一部分了。其实还有个更值得深究的部分：隐私预算怎么扣？直接暴力地减一下吗？

其实，减一下是合理的。这是因为组合性质，组合性质是这么说的：

假设机制 是 DP的，机制 是 DP的，那么 就是 DP的。

刚才我们说了，数据拥有着关心的是总的privacy preserving level，利用组合性质去线性地扣是一种合理的方式。那么是不是只能这样呢？当然不是的，因为前面说到了一个噪声是独立同分布的，这一点是否一定需要满足呢？这可能是个open question了。如果用户第 次查询的结果所添加的噪声不是和前 次查询的噪声不是独立同分布的呢？直接扣当然可以（因为组合性质说的实际上是privacy leakage的上限），但是不一定是最好的。

举个LDP下最基本的例子，依然以你是否抽烟为例。当我第一次查询了你是否抽烟之后，得到了一个结果。然后我第二次查询你是否抽烟，这时候所添加的噪声难道还需要和第一次的噪声是独立同分布的吗？不一定的。我们设想这样一个机制，第一次查询，用random response给出一个结果，第k次查询，直接给出第k-1次查询的结果。

这个时候，我们知道，无论攻击者查询多少次，其只会得到同样的结果，呢么这种情况下，我们就没有必要去把privacy budget扣掉了，因为攻击者后面的查询结果完全反推不出什么东西。这个例子比较极端，因为往往查询没有这么简单。

回答到这里结束了，欢迎关注公众号《差分隐私》。