“两种符号使最高分恰为 $\max t P {S t}\phi t P\phi t \ge0$。监视器按指数机制选择候选索引,权重是 $\exp(m\varepsilon u(t,s)/2)$…”
形式陈述
设
取
它满足纯$\varepsilon$-差分隐私。这里改变的是数据
隐私与效用各怎样证明
记
令
对任意
直觉
候选可以是课程时段、分类器或一棵树,没有必要先把输出编码成一个有距离意义的实数再加噪声。机制只要求能评价候选质量,并限制一个人的记录对每个评分的影响。
温度降低,也就是增大
例子与边界
三个候选的完整计算
某项匿名投票有三个公开候选
最优候选仍可能落选。实际期望效用为
若把“数据库中出现过的候选”直接作为
有限集合条件的用途
对连续候选也可相对于固定基准测度定义指数密度,但归一化积分必须有限,效用保证还要比较近最优区域的测度。不能把有限集合公式中的
推论与应用
若目标是最小化经验损失,可设
显式有限集的实现可先减去最大 log-weight,再求指数并归一化,避免数值溢出。在指数、算术与离散采样采用单位成本原语的模型下,若计算一次效用用时
参考资料
- McSherry 与 Talwar,“Mechanism Design via Differential Privacy”,FOCS 2007,指数机制的原始论文。
- Dwork 与 Roth,《The Algorithmic Foundations of Differential Privacy》§3.4,Theorems 3.10–3.11。