本地差分隐私

本地差分隐私#

学习目标

阅读本章后，您将能够：

定义差分隐私的本地模型，并比较本地模型与中心模型的异同
定义和实现随机应答和一元编码机制
描述这些机制的准确性影响，以及本地模型的挑战

截至目前，我们只考虑了差分隐私的中心模型（Central Model）。在中心模型中，原始敏感数据被汇总到单个数据集中。在这种场景下，我们假定分析者是恶意的，但存在一个可信任的数据管理者，由它持有数据集并能正确执行分析者指定的差分隐私机制。

这种设定通常是不现实的。在很多情况下，数据管理者和分析者是同一个人，且实际上不存在一个可信第三方，能由它持有数据集并执行差分隐私机制。事实上，往往是我们不信任的组织来收集我们最敏感的数据。这样的组织显然无法成为可信数据管理者。

中心差分隐私模型的一种替代方案是差分隐私本地模型（Local Model）。在本地模型中，数据在离开数据主体控制之前就已经满足差分隐私。例如，在将数据发送给数据管理者之前，用户就在自己的设备上为自己的数据添加噪声。在本地模型中，数据管理者不需要是可信的，因为他们收集的是已经满足差分隐私的数据。

因此，相比于中心模型，本地模型有着巨大的优势：数据主体不需要相信除他们自己以外的任何人。这一优势使得本地模型在实际系统中有着广泛的应用，包括谷歌和苹果都部署了基于本地模型的差分隐私应用。

不幸的是，本地模型也有明显的缺点：在相同的隐私消耗量下，对于相同的问询，本地模型问询结果的准确性通常比中心模型低几个数量级。这种巨大的准确性损失意味着只有较少类型的问询适用于本地差分隐私。即便如此，只有当数据量较大（即参与者数量较多时）时，差分隐私本地模型分析结果的准确率才可以满足实际要求。

本章，我们将学习两种本地差分隐私机制。第一种是随机应答（Randomized Response），第二种是一元编码（Unary Encoding）。

随机应答#

随机应答 [16]是一种本地差分隐私机制，S. L. Warner在其1965年的论文中首次提出了这一机制。当时，该技术提出的目的是允许用户可以用错误的回复来应答调研中的敏感问题，且学者们当初也没有意识到这是一种差分隐私机制（此后40年内，学者们都尚未提出差分隐私的概念）。在提出差分隐私的概念后，统计学家们才意识到随机应答技术已经满足了差分隐私的定义。

Dwork和Roth提出了一种随机应答变种机制。在此机制中，数据主体按下述方法用”是”或”不是”来回答一个问题：

掷一枚硬币
如果硬币正面向上，如实回答问题
如果硬币反面向上，再掷一枚硬币
如果第二枚硬币也是正面向上，回答”是”；否则，回答”否”

该算法的随机性来自两次硬币的抛掷结果。正如其他差分隐私算法一样，硬币抛掷结果的随机性为真实结果引入了不确定性，而这种不确定性正是差分隐私机制可以提供隐私保护的根本原因。

事实证明，该随机应答算法满足\(\epsilon\)-差分隐私，其中\(\epsilon = \log(3) = 1.09\)。

让我们来实现这个算法，并用其回答一个简单的”是或否”问题：”你的职业是’销售’吗？”我们可以在Python中使用np.random.randint(0, 2)函数模拟硬币抛掷过程。此函数的输出仅可能是0或1。

def rand_resp_sales(response):
    truthful_response = response == 'Sales'
    
    # 第一次抛掷硬币
    if np.random.randint(0, 2) == 0:
        # 如实回答
        return truthful_response
    else:
        # （用第二次硬币抛掷结果）随机应答
        return np.random.randint(0, 2) == 0

让我们来询问200名从事销售工作的人，请他们使用随机应答算法回答此问题，看看结果如何。

pd.Series([rand_resp_sales('Sales') for i in range(200)]).value_counts()

True     150
False     50
dtype: int64

可以看到，我们可以得到答案为”是”和”否”的人数，但”是”的数量远多于”否”的数量。与我们学过的算法类似，此输出结果也展示出了差分隐私算法的两个性质：算法引入一定的不确定性来实现隐私保护，但算法的输出结果仍然释放出足够的信号，帮助我们推断出人口相关信息。

让我们试试在实际数据上做同样的实验。我们从一直使用的美国人口数据集中获取所有个体的职业信息。我们要问询的问题是”你的职业是’销售’吗？”，并对每个职业的回复结果进行编码。在实际部署的系统中，我们不会集中收集真实数据。相对地，每个回复者会在本地执行rand_resp_sales（随机应答销售职业）函数，并把随机应答结果提交给数据管理者。在实验中，我们在现有的数据集上执行rand_resp_sales函数。

responses = [rand_resp_sales(r) for r in adult['Occupation']]

pd.Series(responses).value_counts()

False    22453
True     10108
dtype: int64

这次，我们得到的”否”数量比”是”数量更多。稍加思考，就会发现这是一个合理的统计结果，因为数据集中大多数参与者的职位都不是销售。

现在的关键问题是：我们如何根据这些回复，估计出数据集中销售人员的真实人数呢？”是”的数量并不能很好地估计销售人员数量：

len(adult[adult['Occupation'] == 'Sales'])

这并不奇怪，因为很多”是”都来自于算法中的随机硬币抛掷结果。

为了估计销售人员的正确人数，我们需要分析随机应答算法的随机性，估计出有多少”是”来自实际销售人员，以及有多少”是”来自随机硬币抛掷结果。我们知道：

每个响应者随机回复的概率为\(\frac{1}{2}\)
每个随机回复中”是”的概率为\(\frac{1}{2}\)

因此，响应者随机回复（而不是因为他们真的是销售人员才回复）”是”的概率为\(\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}\)。这意味着我们得到的回复中有四分之一是假的”是”。

responses = [rand_resp_sales(r) for r in adult['Occupation']]

# 我们估计出有1/4的"是"回复完全来自于硬币的随机抛掷结果
# 这些都是假的"是"
fake_yeses = len(responses)/4

# 回复为"是"的总人数
num_yeses = np.sum([1 if r else 0 for r in responses])

# 真实"是"的人数等于回复为"是"的总人数减去假"是"的人数
true_yeses = num_yeses - fake_yeses

另一个我们需要考虑的因素是，虽然有一半受访者是随机应答的，但在这些随机应答的响应者中，部分响应者实际上可能也是销售人员。随机应答响应者中有多少是销售人员呢？我们得不到相关数据，因为他们的应答是完全随机的！

但是，因为我们（根据第一次硬币抛掷结果）把受访者随机分为了”真实”和”随机”两组，我们期望两组的销售人员数量基本一致。因此，如果我们能估计出”真实”组的销售人员数量，那么我们可以将该人数翻倍，进而得到销售人员总数。

# 用true_yesses估计"真实"组中回答"是"的人数
# 我们把人数翻倍，估计出回复为"是"的总人数
rr_result = true_yeses*2
rr_result

3573.5

得到的人数和销售人员的真实人数有多接近呢？让我们来比较一下！

true_result = np.sum(adult['Occupation'] == 'Sales')
true_result

pct_error(true_result, rr_result)

2.095890410958904

当总人数相对比较大时，（例如，本例的总人数超过了3000），我们通常可以使用此方法得到一个错误率”可接受”的统计结果。此例子中的错误率低于5%。如果我们的目标是统计最受欢迎的职位，这个方法可以帮助我们得到较为准确的结果。然而，统计结果的错误率会随着总人数的降低而快速增大。

此外，随机应答的准确率和中心模型拉普拉斯机制的准确率相比要差出几个数量级。让我们使用此例子比较一下这两种机制：

pct_error(true_result, laplace_mech(true_result, 1, 1))

0.05374880006242514

即使我们中心模型中的\(\epsilon\)值略低于随机应答的\(\epsilon\)，中心模型的误差也仅约为0.01%，远小于本地模型。

确实存在效果更好的本地模型算法。然而，本地模型存在天生的限制条件：必须在提交数据前增加噪声。这意味着本地模型算法的准确率总是比最好的中心模型算法准确率低。

一元编码#

随机应答允许我们基于本地差分隐私回答”是或否”的问题。如何实现直方图问询呢？

学者们已经提出了多种不同的算法，来解决本地差分隐私的直方图问询问题。Wang等人 [17]在2017年的论文中总结了一些优化方法。这里，我们介绍其中最简单的一个方法：一元编码。该方法是谷歌RAPPOR系统 [15]的基础算法（谷歌RAPPOR系统对基础算法作了大量的修改，使算法支持更大的标签数量、支持随时间推移的多次应答）。

我们首先需要定义应答域，即直方图包含的标签。下述例子中，我们想要知道各个职业的从业者人数，因此应答域是所有职位所构成的集合。

domain = adult['Occupation'].dropna().unique()
domain

array(['Adm-clerical', 'Exec-managerial', 'Handlers-cleaners',
       'Prof-specialty', 'Other-service', 'Sales', 'Craft-repair',
       'Transport-moving', 'Farming-fishing', 'Machine-op-inspct',
       'Tech-support', 'Protective-serv', 'Armed-Forces',
       'Priv-house-serv'], dtype=object)

我们将定义三个函数，这三个函数共同实现了一元编码机制：

encode（编码），编码应答值
perturb（扰动），扰动编码后的应答值
aggregate（聚合），根据扰动应答值重构最终结果

该技术的名称来源于所用的编码方法：如果应答域大小为\(k\)，我们将每个应答值编码为长度为\(k\)的比特向量。除了应答者的职位所对应的比特值为1以外，所有其他位置的编码均为0。机器学习领域称这种表示方法”独热编码”（One-hot Encoding）。

举例来说，’销售’是应答域中的第6个元素，因此’销售’职位的编码是第6个比特为1、其余比特值均为0的向量。

def encode(response):
    return [1 if d == response else 0 for d in domain]

encode('Sales')

[0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0]

我们接下来要用perturb函数翻转应答向量中的各个比特值，从而满足差分隐私。翻转一个比特值的概率由\(p\)和\(q\)这两个参数共同决定。这两个参数也决定了隐私参数\(\epsilon\)的值（我们稍后将看到具体的计算公式）。

\[\begin{split} \mathsf{Pr}[B'[i] = 1] = \left\{ \begin{array}{ll} p\;\;\;\text{if}\;B[i] = 1 \\ q\;\;\;\text{if}\;B[i] = 0\\ \end{array} \right. \end{split}\]

def perturb(encoded_response):
    return [perturb_bit(b) for b in encoded_response]

def perturb_bit(bit):
    p = .75
    q = .25

    sample = np.random.random()
    if bit == 1:
        if sample <= p:
            return 1
        else:
            return 0
    elif bit == 0:
        if sample <= q:
            return 1
        else: 
            return 0

perturb(encode('Sales'))

[0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0]

我们可以根据\(p\)和\(q\)计算出隐私参数\(\epsilon\)。如果\(p=.75\)，\(q=.25\)，则计算得到的\(\epsilon\)略高于2。

(38)#\[\begin{align} \epsilon = \log{\left(\frac{p (1-q)}{(1-p) q}\right)} \end{align}\]

def unary_epsilon(p, q):
    return np.log((p*(1-q)) / ((1-p)*q))

unary_epsilon(.75, .25)

2.1972245773362196

最后一步是聚合。如果我们没有对应答值进行过任何扰动，我们可以简单地对所有得到的应答向量逐比特相加，得到应答域中每个元素的计数结果：

counts = np.sum([encode(r) for r in adult['Occupation']], axis=0)
list(zip(domain, counts))

[('Adm-clerical', 3770),
 ('Exec-managerial', 4066),
 ('Handlers-cleaners', 1370),
 ('Prof-specialty', 4140),
 ('Other-service', 3295),
 ('Sales', 3650),
 ('Craft-repair', 4099),
 ('Transport-moving', 1597),
 ('Farming-fishing', 994),
 ('Machine-op-inspct', 2002),
 ('Tech-support', 928),
 ('Protective-serv', 649),
 ('Armed-Forces', 9),
 ('Priv-house-serv', 149)]

但是，正如我们在随机应答中所看到的，翻转比特值产生的”假”应答值将使我们得到难以解释的统计结果。如果我们把扰动后的应答向量逐比特相加，得到的所有计数结果都是错误的：

counts = np.sum([perturb(encode(r)) for r in adult['Occupation']], axis=0)
list(zip(domain, counts))

[('Adm-clerical', 10152),
 ('Exec-managerial', 10225),
 ('Handlers-cleaners', 8812),
 ('Prof-specialty', 10254),
 ('Other-service', 9711),
 ('Sales', 10013),
 ('Craft-repair', 10140),
 ('Transport-moving', 8934),
 ('Farming-fishing', 8588),
 ('Machine-op-inspct', 9165),
 ('Tech-support', 8557),
 ('Protective-serv', 8427),
 ('Armed-Forces', 8277),
 ('Priv-house-serv', 8204)]

一元编码算法的聚合步骤需要考虑每个标签的”假”应答数量。此步骤以\(p\)、\(q\)，以及应答数量\(n\)为输入，得到聚合结果：

(39)#\[\begin{align} A[i] = \frac{\sum_j B'_j[i] - n q}{p - q} \end{align}\]

def aggregate(responses):
    p = .75
    q = .25
    
    sums = np.sum(responses, axis=0)
    n = len(responses)
    
    return [(v - n*q) / (p-q) for v in sums]  

responses = [perturb(encode(r)) for r in adult['Occupation']]
counts = aggregate(responses)
list(zip(domain, counts))

[('Adm-clerical', 3857.5),
 ('Exec-managerial', 4083.5),
 ('Handlers-cleaners', 1327.5),
 ('Prof-specialty', 4361.5),
 ('Other-service', 3511.5),
 ('Sales', 3843.5),
 ('Craft-repair', 3943.5),
 ('Transport-moving', 1751.5),
 ('Farming-fishing', 833.5),
 ('Machine-op-inspct', 2055.5),
 ('Tech-support', 965.5),
 ('Protective-serv', 699.5),
 ('Armed-Forces', 77.5),
 ('Priv-house-serv', 79.5)]

正如我们在随机应答中所看到的，一元编码机制得到的统计结果也比较准确，我们可以得到应答域中各个标签的粗略排序结果（至少可以统计出最受欢迎的职位是什么）。即便如此，一元编码机制的准确率要比中心模型拉普拉斯机制的准确率低几个数量级。

学者们已经提出了其他在本地模型下实现直方图问询的方法。之前链接给出的论文具体介绍了这些方法。这些方法可以在一定程度上提高准确率，但这些方法都必须保证本地模型下每个样本需独立满足差分隐私。这一基本限制条件使得即便使用最复杂的技术，本地模型机制的准确率也无法达到中心模型机制的准确率。

本地差分隐私

目录

本地差分隐私#

随机应答#

一元编码#