局部差分隐私实现的广义随机响应

Question

我的任务是实现本地（非交互式）差异隐私机制。我正在处理一个庞大的人口普查数据数据库。唯一敏感的属性是“子女数”，它是一个从0到13的数值。在

我决定采用广义随机响应机制，因为它似乎是最直观的方法。这个机制被描述为here和{a2}。在

在将每个值加载到一个数组中之后（暂时忽略其他属性），我执行如下扰动。在

d = 14 # values may range from 0 to 13

eps = 1 # epsilon level of privacy

p = (math.exp(eps)/(math.exp(eps)+d-1))
q = 1/(math.exp(eps)+d-1)

p_dataset = []

for row in dataset:
    coin = random.random()
    if coin <= p:
        p_dataset.append(row)
    else:
        p_dataset.append(random.randint(0,13))

除非我误解了这个定义，否则我相信这将保证p峎u数据集上的epsilon差异隐私。在

但是，我很难理解聚合器必须如何解释这个数据集。在上面的presentation之后，我尝试实现一个方法来估计回答特定值的个人数量。在

^{pr2}$

我不知道我是否正确地实现了所描述的方法，因为我不完全理解它在做什么，也找不到一个清晰的定义。在

不管怎样，我使用这个方法来估计数据集中的epsilon值从1到14回答每个值的个人总数，然后将其与实际值进行比较。结果如下（请原谅格式化）。在

如您所见，epsilon值较低时，数据集的实用程序会受到很大影响。此外，当多次执行时，即使是小量epsilon值，估计值的偏差也相对较小。在

例如，当估计回答0的参与者数量时，使用epsilon为1，所有的估计值似乎都集中在1600左右，估计值之间的最大距离是100。考虑到这个查询的实际值是5969，我认为我可能实现了错误的东西。在

这是广义随机响应机制的预期行为，还是我在实现中犯了错误？在

Answer 1

我认为当得到错误答案时，我们不能直接使用p_dataset.append(random.randint(0,13))，因为它包含真答案