发布时间:2023-09-01 17:00
目录
1.前言(如何实现差分隐私)
2.指数机制
3.指数机制满足ε-差分隐私定义
差分隐私是通过随机化的方式来干扰正常的查询,或是对数据集做一些处理. 那么最常规的干扰查询/处理数据的手法,就是加噪音。
一般情况下,数据库的查询可分为两类:数值查询和非数值查询。
1.数值查询:小明的高数考了多少分?
2.非数值查询:小明分最高的是哪一门课?
应对这两种查询,分别有拉普拉斯机制和指数机制。
对于非数值查询,需要用指数机制来干扰
在拉普拉斯机制中,我们首先对数据库进行查询,然后在查询结果之上添加一定的噪声使其满足差分隐私的要求。因此,返回的数据通常只是“接近准确”的。那么差分隐私能否允许我们得到真实的结果(实用程序)呢?在这种情况下,指数机制应运而生。
综上:指数机制适用于回答具有任意实用程序和任意非数字范围查询
指数机制是为我们希望选择“最佳”响应的情况而设计的,但直接在计算数量上添加噪声可能完全破坏其价值。例如在拍卖中设定价格,其目标是最大化收益,如果在最优价格上添加少量正噪声(为了保护投标的隐私)可能会大大减少由此产生的收入。为了理解接下来我们举个例子:
假设我们有最够充足的南瓜,想要卖给Alice,Bob,Charlie。他们每个人出价每个南瓜1元或者2元,我们想要定下价格,让我们受益最大。假设我们有一个出价的数据表:
如果我们定价为1元,这个价格在每个人的预算内,那我们能够获得3元(1+1+1);如果我们定价2元,那只有Charlie能买得起,那我们能够获得2元。我们用效用函数(utility function)描述以上信息:
效用函数的值取决于出价表和定价。如果我们想最大化效用,我们应该定价1元。
但是这个定价可能会暴露隐私,假如我们知道Alice比较穷,只出得起1元,Charlie比较富,能出2元,但是不知道Bob的出价情况。但是通过最大化的收益和定价就能推断出Bob的出价。指数机制就能够保证出价者的隐私。
效用函数:
效用函数 :
效用函数的映射关系为:数据库 不同情况 (类比上面的price) 效用得分 (类比上面utility)
在上面的例子,查询 是“南瓜的单价是多少?”,可能的定价 是 ,效用得分是收益,对于出价数据库,,
效用函数的全局敏感度和局部敏感度:
效用函数 的全局敏感度:
对于任意的数据库D和D'效用得分差距的上限,也就是对于所有相邻数据集,某一数据库 ,其相对拥有最大的效用函数值a,某一数据库 其相对拥有最小的效用函数值b,则效用函数 的全局敏感度 = a-b
效用函数 的局部敏感度:
对于一个已知的数据库,我们要对运用指数机制进行差分隐私保护。那么对于数据库和任意与相邻的数据库效用得分差距的上限,也就是数据库的最大效用函数值a和最小效用函数值b,某一与相邻的数据库 有最大效用函数值c, 某一与相邻的数据库有最小效用函数值d,则效用函数 的局部敏感度为|a-d|和|b-c|中的较大值
指数机制:
设随机化算法输入为数据集,输出为一个实体对象,为可用性函数,为函数的敏感度,若以正比于的概率从输入中选择并输出,则算法是满足 - 差分隐私的
直接的说就是,以更高的概率选择效用得分更高的输出
应用案例:
假设某基地正在举办一场体育比赛,可以选择的项目有{足球,排球,篮球,网球}四个项目,参与者们对这些项目进行投票,现在要确定一个项目是的整个决策过程满足 - 差分隐私,以每个选项的得票数量作为可用性函数,在给定隐私预算情况下,可以计算选择各个项目的输出概率:
上述案例中,当=0时,提供完全的隐私保护但数据可用性为0,随着大,选择出期望结果的可能性也越大。