Ch6.敏感度

之前在拉普拉斯机制中有提到.
拉普拉斯机制: $F(x) = f(x) + Lap(\frac{s}{\epsilon})$.
$f(x)$ 是确定性的问询函数, $s$ 是 $f$ 的敏感度.

给定一个映射函数 $f: \mathcal{D} \rightarrow \mathbb{R}$. 将数据集 $\mathcal{D}$映射为实数 $\mathbb{R}$.
$f$ 的全局敏感度 (Global Sensitivity) 为:

$d(x,x')$ 表示两个数据集 $x$ 和 $x'$ 的距离 (Distance).
若距离 $\leq 1$, 说明两个数据集是临近集 (Neighbor).
??? 之前说的临近数据集的之间仅有一个个体的数据不同.

全局敏感度限制了两个数据集相差的最大值, GS 的定义与具体问询的数据集无关.

??? GS 与数据集无关, 也就是对任意一对临近集, 他们输出的最大差值都是 GS.

6.1 距离

对于按行存储的数据集, 距离即有多少行数据的不同.

度量方法使用 对称差 (Symmetric Difference):

通过对一个数据集进行增减一条数据, 可以获得相邻数据集.
但若修改某一条数据, 会得到的一个距离为 2 的数据集.

• 无界差分隐私 Unbounded Differential Privacy

  数据集中个体数量不固定, 可通过动态增加/减少个体, 来得到相邻数据集.

• 有界差分隐私 Bounded Differential Privacy

  数据集中个体数量固定, 修改单行数据, 即可得到相邻数据集.

6.2 计算敏感度

6.2.1 计数问询

问询满足属性的数据有多少行.

SQL 中的 COUNT 算子.

# 数据集中有多少人?
adult.shape[0]

# 受教育年数超过10年的有多少人?
adult[adult['Education-Num'] > 10].shape[0]

# 受教育年数小于或等于10年的有多少人?
adult[adult['Education-Num'] <= 10].shape[0]

# 名字叫Joe Near的有多少人?
adult[adult['Name'] == 'Joe Near'].shape[0]

计数问询的敏感度总为 1.

• 增加一行数据, 最多会使输出结果增加 1, 也就是刚好新增的这行数据满足了查询的条件, 也可能输出保持不变.
• 删除一行数据, 最多会使输出结果减少 1.

6.2.2 求和问询

问询特定属性的数据的求和值.

SQL 中的 SUM 算子.

# 受教育年数超过10年的人, 其年龄总和是多少?
adult[adult['Education-Num'] > 10]['Age'].sum()

求和问询的敏感度和计数问询不同, 敏感度需要设置一个问询的属性值合理上界, 但实际中总会产生与设置的上界发生冲突的数据.

在求和的属性值不存在上下界时, 求和问询具有 无界敏感度.
在求和的属性值存在上下界时, 求和问询的敏感度为 上下界的差.

6.2.3 均值问询

问询特定属性的数据的平均值.

SQL 中的 AVG 算子.

# 受教育年数超过10年的人, 其平均年龄是多少?
adult[adult['Education-Num'] > 10]['Age'].mean()

应用差分隐私在均值问询的方法: 均值问询 = $\frac{求和问询}{计数问询}$. 根据串行组合性, 总的隐私消耗量就为 求和问询 和 计数问询 的和.

6.3 裁剪

拉普拉斯机制无法直接应用于无界敏感度问询.

??? 因为不知道敏感度是多少, 也就无法计算增加噪声.

通过 裁剪 (Clip) 转换成等价的 有界敏感度问询.

??? 也就是人为设置一个相对合理的上下界. 所以裁剪最大的难点就是找到合理的上下界.

确定上下界要注意

• 裁剪导致的信息损失 与 满足 DP 所需噪声 的权衡.

  裁剪的上下界越接近, 敏感度 (上下界的差) 越小, 所需噪声 ($Lap(\frac{s}{\epsilon})$) 越小.

• 尽可能保留数据集的所有信息.

确定上下界的方法

1. 查看数据, 确定边界
   通过观察数据的分布, 比如直方图, 就能很清晰的观察到数据的大致分布, 进而设置一个合适的边界.

   这个方法不满足差分隐私, 边界本身也会泄露一些信息.

2. 逐渐扩大边界, 直至问询输出不再变化
   不断扩大边界的同时, 进行问询. 当问询结果逐渐趋于平稳, 则可以确定一个合适边界.