指数机制#

学习目标

阅读本章后，您将能够：

  • 定义、实现并应用指数机制和报告噪声最大值机制

  • 描述实际中应用指数机制所面临的挑战

  • 描述指数机制和报告噪声最大值机制的优势

截至目前，我们已学习的基本机制（拉普拉斯机制和高斯机制）针对的都是数值型回复，只需直接在回复的数值结果上增加噪声即可。如果我们想返回一个准确结果（即不能直接在结果上增加噪声），同时还要保证回复过程满足差分隐私，该怎么办呢？一种解决方法是使用指数机制（Exponential Mechanism）[12]。此机制可以从备选回复集合中选出”最佳”回复的同时，保证回复过程满足差分隐私。分析者需要定义一个备选回复集合。同时，分析者需要指定一个评分函数（Scoring Function），此评分函数输出备选回复集合中每个回复的分数。分数最高的回复就是最佳回复。指数机制通过返回分数近似最大的回复来实现差分隐私保护。换言之，为了使回复过程满足差分隐私，指数机制返回结果所对应的分数可能不是备选回复集合中分数最高的那个结果。

指数机制满足\(\epsilon\)-差分隐私：

  1. 分析者选择一个备选回复集合\(\mathcal{R}\)

  2. 分析者指定一个全局敏感度为\(\Delta u\)的评分函数\(u : \mathcal{D} \times \mathcal{R} \rightarrow \mathbb{R}\)

  3. 指数机制输出\(r \in \mathcal{R}\)，各个回复的输出概率与下述表达式成正比：

(30)#\[\begin{align} \exp \Big(\frac{\epsilon u(x, r)}{2 \Delta u} \Big) \end{align}\]

和我们之前学习过的机制（如拉普拉斯机制）相比，指数机制最大的不同点在于其总会输出集合\(\mathcal{R}\)中的一个元素。当必须从一个有限集合中选择输出结果，或不能直接在结果上增加噪声时，指数机制就会变得非常有用。例如，假设我们要为一个大型会议敲定一个日期。为此，我们获得了每个参会者的日程表。我们想选择一个与尽可能少的参会者有时间冲突的日期来举办会议，同时想通过差分隐私为所有参会者的日程信息提供隐私保护。在这个场景下，在举办日期上增加噪声没有太大意义，增加噪声可能会使日期从星期五变成星期六，使冲突参会者的数量显著增加。应用指数机制就可以完美解决此类问题：既不需要在日期上增加噪声，又可以实现差分隐私。

指数机制的有趣之处在于：

  • 无论\(\mathcal{R}\)中包含多少个备选输出，指数机制的隐私消耗量仍然为\(\epsilon\)。我们后续将详细讨论这一点。

  • 无论\(\mathcal{R}\)是有限集合还是无限集合，均可应用指数机制。但如果\(\mathcal{R}\)是无限集合，则我们会面临一个非常有挑战的问题：如何构造一个实际可用的实现方法，其可以遵循适当的概率分布从无限集合中采样得到输出结果。

  • 指数机制代表了\(\epsilon\)-差分隐私的”基本机制”：通过选择适当的评分函数\(u\)，所有其他的\(\epsilon\)-差分隐私机制都可以用指数机制定义。

有限集合的指数机制#

options = adult['Marital Status'].unique()

def score(data, option):
    return data.value_counts()[option]/1000

score(adult['Marital Status'], 'Never-married')

10.683

def exponential(x, R, u, sensitivity, epsilon):
    # 计算R中每个回复的分数
    scores = [u(x, r) for r in R]
    
    # 根据分数计算每个回复的输出概率
    probabilities = [np.exp(epsilon * score / (2 * sensitivity)) for score in scores]
    
    # 对概率进行归一化处理，使概率和等于1
    probabilities = probabilities / np.linalg.norm(probabilities, ord=1)

    # 根据概率分布选择回复结果
    return np.random.choice(R, 1, p=probabilities)[0]

exponential(adult['Marital Status'], options, score, 1, 1)

'Married-civ-spouse'

r = [exponential(adult['Marital Status'], options, score, 1, 1) for i in range(200)]
pd.Series(r).value_counts()

Married-civ-spouse    183
Never-married          17
dtype: int64

报告噪声最大值#

我们能用拉普拉斯机制实现指数机制吗？当\(\mathcal{R}\)为有限集合时，指数机制的基本思想是使从集合中选择元素的过程满足差分隐私。我们可以应用拉普拉斯机制给出此基本思想的一种朴素实现方法：

  1. 对于每个\(r \in \mathcal{R}\)，计算噪声分数\(u(x, r) + \mathsf{Lap}\left(\frac{\Delta u}{\epsilon}\right)\)

  2. 输出噪声分数最大的元素\(r \in \mathcal{R}\)

因为评分函数\(u\)在\(x\)下的敏感度为\(\Delta u\)，所以步骤1中的每次”问询”都满足\(\epsilon\)-差分隐私。因此，如果\(\mathcal{R}\)包含\(n\)个元素，根据串行组合性，上述算法满足\(n\epsilon\)-差分隐私。

然而，如果我们使用指数机制，则总隐私消耗量将只有\(\epsilon\)！为什么指数机制效果如此之好？原因是指数机制泄露的信息更少。

对于上述定义的拉普拉斯机制实现方法，我们的隐私消耗量分析过程是非常严苛的。实际上，步骤1中计算整个集合噪声分数的过程满足\(n\epsilon\)-差分隐私，因此我们可以发布得到的所有噪声分数。我们应用后处理性得到步骤2的输出满足\(n\epsilon\)-差分隐私。

与之相比，指数机制仅发布最大噪声分数所对应的元素，但不发布最大噪声分数本身，也不会发布其他元素的噪声分数。

上述定义的算法通常被称为报告噪声最大值（Report Noisy Max）算法。实际上，因为此算法只发布最大噪声分数所对应的回复，所以无论集合\(\mathcal{R}\)包含多少个备选回复，此算法都满足\(\epsilon\)-差分隐私。可以在Dwork和Roth论文 [13]的断言3.9中找到相应的证明。

输出噪声最大值算法的实现方法非常简单，而且很容易看出，此算法得到的回复结果与之前我们实现的有限集合指数机制非常相似。

def report_noisy_max(x, R, u, sensitivity, epsilon):
    # 计算R中每个回复的分数
    scores = [u(x, r) for r in R]

    # 为每个分数增加噪声
    noisy_scores = [laplace_mech(score, sensitivity, epsilon) for score in scores]

    # 找到最大分数对应的回复索引号
    max_idx = np.argmax(noisy_scores)
    
    # 返回此索引号对应的回复
    return R[max_idx]

report_noisy_max(adult['Marital Status'], options, score, 1, 1)

'Married-civ-spouse'

r = [report_noisy_max(adult['Marital Status'], options, score, 1, 1) for i in range(200)]
pd.Series(r).value_counts()

Married-civ-spouse    194
Never-married           6
dtype: int64

因此，当\(\mathcal{R}\)为有限集合时，可以用报告噪声最大值机制代替指数机制。但如果\(\mathcal{R}\)为无限集合呢？我们无法简单地为无限集合中每一个元素对应的分数增加拉普拉斯噪声。当\(\mathcal{R}\)为无限集合时，我们不得不使用指数机制。

然而，在实际应用中，在无限集合上应用指数机制通常是极具挑战的，甚至是不可能的。尽管可以很容易写出无限集合下指数机制定义的概率密度函数，但一般来说对应的高效采样算法是不存在的。因此，很多理论论文会应用指数机制证明”存在”满足某些特定性质的差分隐私算法，但多数算法在实际中都是不可用的。

指数机制是差分隐私的基本机制#

我们已经知道，无法使用拉普拉斯机制与串行组合性来实现指数机制，这是因为当使用拉普拉斯机制与串行组合性时，我们可以得到差分隐私保护的所有噪声分数，但我们想实现的差分隐私算法不需要发布这些噪声分数。那么，反过来又如何呢？我们可以应用指数机制实现拉普拉斯机制吗？事实证明，这是可以做到的！

考虑一个敏感度为\(\Delta q\)的问询函数\(q(x) : \mathcal{D} \rightarrow \mathbb{R}\)。我们可以在真实回复值上增加拉普拉斯噪声\(F(x) = q(x) + \mathsf{Lap}(\Delta q / \epsilon)\)，以得到满足\(\epsilon\)-差分隐私的回复结果。差分隐私回复\(q\)的概率密度函数为：

(31)#\[\begin{align} \mathsf{Pr}[F(x) = r] =& \frac{1}{2b} \exp\Big(- \frac{\lvert r - \mu \rvert}{b}\Big)\\ =& \frac{\epsilon}{2 \Delta q} \exp\Big(- \frac{\epsilon \lvert r - q(x) \rvert}{\Delta q}\Big) \end{align}\]

考虑一下，当我们将指数机制的评分函数设置为\(u(x, r) = -2 \lvert q(x) - r \rvert\)时会发生什么？指数机制的定义告诉我们，每个回复值的采样概率应该与下述表达式成正比：

(32)#\[\begin{align} \mathsf{Pr}[F(x) = r] =&\; \exp \Big(\frac{\epsilon u(x, r)}{2 \Delta u} \Big)\\ &= \exp \Big(\frac{\epsilon (-2 \lvert q(x) - r \rvert)}{2 \Delta q} \Big)\\ &= \exp \Big(- \frac{\epsilon \lvert r - q(x) \rvert}{\Delta q} \Big)\\ \end{align}\]

因此，可以应用指数机制实现拉普拉斯机制，并得到相同的概率分布（两个概率分布可能会相差一个常数因子，这是因为指数机制的通用分析结论不一定在所有情况下都是紧致的）。

指数机制非常具有普适性。一般情况下，通过精心选择评分函数\(u\)，我们可以用指数机制重定义任何\(\epsilon\)-差分隐私机制。只要我们可以分析出该评分函数的敏感度，我们就可以轻松证明相应机制满足差分隐私。

另一方面，指数机制之所以具有普适性，是因为其通用分析方法得到的隐私消耗量边界可能会更宽松一些（就像前面给出的拉普拉斯例子那样）。此外，用指数机制定义的差分隐私机制一般都比较难实现。指数机制通常用于证明理论下界（即证明差分隐私算法的存在性）。在实际中，一般会使用一些其他的算法来复现指数机制（如前面描述的输出噪声最大值例子）。