统计视角下的差分隐私：Differential Privacy from a Statistic View

2022 年 2 月 10 日 PaperWeekly

©作者 | 李轩宇

单位 | 中国科学院大学博士生

研究方向 | 机器学习

统计视角下的差分隐私

最近在学习统计领域内的差分隐私，一个人只是读论文看资料难免会在细节上有些疏漏，遂决定整理总结自己所看的一些经典或者优秀的论文，把它们做成读书笔记，既巩固自己的知识，也可以服务想要快速了解差分隐私的同学。如果有什么错误或者不严谨，还请多多指教。

差分隐私的概念最早是由 Dwork 在 2006 年的一篇论文中提出来的，Dwork 是一位计算机科学家，在提出 Differential Privacy 的时候也有很多计算机 domain 的考量，但是由于最终的定义是要引入概率的视角，所以在统计的领域内也有学者对这个话题进行研究。而作为一个统计的学生，也应当更多的站在统计的视角去看隐私保护这个 topic，所以我读的文章基本都是在统计的杂志上发表的。

在写文章的时候，我也会把计算机的术语全部转换到统计的语言里。

1.1 背景 Setting

考量这样的一个场景，有一个数据库，它存储了包括你在内一个班 n 个人的家庭年收入信息，这 n 个数据总体记为 D，并且提供数据总体的统计量查询服务，之所以要这样做而不是直接提供所有个人数据是为了保护个人的信息隐私。

你是个转学生，在你来到这个班级之后恰好又离开了一位学生。

而刚在你来之前，那时候的数据总体也有 n 个人的信息，不过相比于现在的 D，有一位同学和你是分别不属于对方的数据集的。

在你来之前，曾有人查询过数据库的平均值统计量，在你来后，他为了更新信息，再次查询了你们班的平均值统计量得到了，通过两次查询的结果相减，他会得到你和离开同学的家庭收入差，也就是，如果他还知道那位同学的家庭收入信息，那么你的收入信息便遭到了泄露。

1.2 隐私保护方案

那么在这个时候，就需要有一种手段，使得对两个有一个个体差异的数据集，查询关于总体的统计量时不会造成个体信息的泄露，不过，绝对的隐私保护（也就是说完全不泄露任何隐私）最后只能带来无法提供任何信息的查询结果。

所以解决方案就变成了在一定的隐私权限下，如何发布统计量使得个人信息最少程

度被泄露。

在引入正式的定义之前，我想先介绍一篇很早的有关统计学家研究保护隐私的文章。

1.3 历史方案

在 1965 年的时候，JASA 上刊登了 Warner 的一篇如何收集可以保护数据隐私的工作，作者指出，在调查中总是存在回避型误差 Invasive Bias，原因是有些问题涉及个人隐私，被访者可能由于安全考虑会错填回答，比如调查高中生是否吸烟。

那么 Warner 的做法就是提供被访者一个指针，它有 p 的概率指向是，有 1-p 的概率指向否，在一个受访者接受敏感问题的回答的时候，他首先需要拨动指针，然后再不告诉调查者指针的指向情况下，回答指针的随机预测是否符合自己的情况就可以了。

该方法之所以可以有效保护隐私是因为就算调查者知道指针的指向概率，只要这个 p 不等于 0 或者 1，我们无法从他的回答中肯定他的真实情况，比如 p 为 0.9，他回答了符合情况，我们也不能肯定是否他的回答一定是‘是’，因为还是有 0.1 的可能指针是指向了否，而他的情况是'否'的，但是我们知道他大概率是'是'，从而可以利用这个信息进行进一步的统计推断，值得注意的是，在 p 为 0.5 的时候，此时收集到的信息将没有任何意义。

Warner 开创性的提出了该方法，也在论文中证明了改方法收集到的数据的统计性质。

从本质上，Warner 的方法其实是在给一个 0、1 变量添加噪声，Warner考虑了一个 01 分布的随机变量的情况，事实上也很容易将其推广到连续变量之上。至此，一个最 intuitive 的差分隐私保护方法已然呈现在我们眼前，就是要将原本 deterministic 的查询结果添加一个随机化的噪声，这样哪怕知道了噪声的分布，也无法确切知道个体的信息，从而达到保护作用。

对于个体的信息发布，该方法已然可以保护隐私，事实上，这种针对个体数据直接发布的保护方法称为 local privacy，而要将它推广到多个个体组成的总体也是不难的，这就是差分隐私的保护机制中最常用的方法——添加随机噪声，下面可以引出 Differential Privacy 的正式概念：

1.4 Differential Privacy

对一个统计量 M，我们定义其具有限度的差分隐私保护机制如下：

对任意相差一个个体的两个数据集、，以及任何的都有

考虑特殊情况，此时称 M 具有限度的差分隐私保护机制。

1.5 统计推断视角下的隐私保护机制

在 Larry Wasserman 与合作者 Shuheng Zhou 2010 年发表于 JASA 上的论文中，他们指出，隐私保护的定义事实上等价于一个假设检验的检验力度（power)。

▲ 定理

从差分隐私到假设检验以及Neyman-Pearson引理

在开始证明这个定理前，先简要的引入必要的数理统计知识。

2.1 数理统计

2.2 假设检验以及检验水平

我们知道假设检验的 setting 是，我们拿到了一批数据（比如说是一维的特征，n 个样本），我们想要知道 X 的分布，这时候会提供两个假设以及，分别代表原假设（Null Hypothesis）以及备择假设（Alternative Hypothesis），分别代表两种分布以及，我们的目的是给出一种判别准则，来对属于哪一个分布做一个判断，一般的，我们记为拒绝原假设选择备择假设，记为接受原假设，如此一来，由于 X 是随机的，所以相应的，也是随机的，是一个服从 0 1 分布的随机变量，具体的例子可以在任何一本数理统计书中找到，这里我们只是做一个抽象的总结。

检验水平便可以由下面的方式定义：

若对服从分布的，我们有，则称一个检验统计量检验水平为。

2.3 统计效力（test power）

在假设检验中，我们有两种可能发生的错误：

一种是服从时我们错误的拒绝了，这种错误被称为第一类错误，第一类错误发生的概率为。

一种是服从时我们错误的接受了，该错误被称为第二种错误，第二类错误发生的概率为。

在假设检验中，我们的目的是尽可能做出正确的推断，这需要我们选择一个好的检验方法，也就是检验统计量，但如何衡量检验统计量的好坏呢。

直觉上，一个好的检验方法两种类型的错误概率都很小，但是，可以证明，我们无法让两种错误概率同时变小，所以我们合理比较不同检验统计方法好坏的方法便是在固定第一类错误的前提下，尽可能的减小第二类错误的概率。这就引入了统计效力。

统计效力的定义为在服从的分布，且检验水平为的时候，我们拒绝原假设的概率，即当的时候，下式的概率：。

可见，统计效力是与的取值有关的，在固定了的情况下，统计效力越高，则检验统计量越好。

2.4 Neyman-Pearson 引理

现如今本科数理统计课本里的绝大多数知识都是来自于 Fisher, Neyman 以及 Pearson 父子四大天王在 20 世纪初开创统计学时的工作。现在要介绍的这个引理也是由其中的两位大牛做出的工作。

考虑为的原假设，而为的备择假设。我们可以用来表示第一类和第二类错误的概率。

令，分别为以及的概率密度函数，我们定义如下的 Neyman-Pearson 检验：

Neyman-Pearson 引理证明了该 Neyman-Pearson 检验是最好的检验函数（在同等检验水平下，检验效力最高），而且有下面的不等式：

2.4.1 Proof of Neyman-Pearson Lemma

另外，如果要寻找在给定检验水平下的最优检验统计量，我们需要选取合适的 c 使得的第一类错误概率等于。

2.5 从统计效力看差分隐私

2.6 Setting

现在有了上述的引理和知识，我们可以对原来的定理进行阐述。

P 是 X 的数据分布，是一个隐私保护的生成机制，Z 是由该机制生成的查询统计量。

也就是说是一个有关于的分布，那么我们要检验的原假设和备择假设就是以及。

该定理说明：在差分隐私机制服从限度的差分隐私保护限度时，我们关于这个假设的水平的假设检验统计效力不超过。

事实上，由于之前所说是一个有关于的分布，所以该假设其实是关于分布的假设。

现在我们可以利用上面所补充的知识，对该定理进行证明：

2.7 Proof of Theory

w.l.o.g（不失一般性）令

记

其中，可以理解为一个区间或者 Borel 集，由 Neyman-Pearson 引理，在检验水平为的情况下，我们用该引理找到最好的检验统计量：

我们选取合适的 c，使得这里需要将 M 理解为一个概率密度；
当的时候，我们拒绝原假设。

我们回忆一下差分隐私的定义：

对一个统计量，我们定义其具有限度的差分隐私保护机制如果：

对任意相差一个个体的两个数据集、，以及任何的都有

在这里，就是，其中，所以应用定义，我们有

因此，此时的统计效力为

由此我们证明了相较于原论文更为一般的形式的差分隐私的假设检验等价形式（当然这个推广很 trivial）。

想要理解这个定理，不妨这样看：当都比较小，甚至为 0 的时候，统计效力几乎甚至直接等于检验水平，此时，如果我们每次不管数据长什么样而是直接以检验水平的概率拒绝原假设，那么此时的统计效力也是基本等于我们利用了数据得到的最好的检验的统计效力的，因此，这说明此时我们没有什么好的检验方法，因为最好的方法也和我们不看数据乱猜差不多。换句话说，当隐私保护的力度很大的时候，假设检验的困难很大。

2.8 结语

至此，我们通过该定理完成了从差分隐私到假设检验的顺利过渡，在此之后便可以进一步深入，去探索在统计的框架内差分隐私的发展。

Gaussian Differential Privacy (f-DP) - 定义以及基本性质

3.1 前言

在上文中，我介绍了差分隐私的基本概念以及其与统计学中的假设检验的联系，而接下来我想写写最近读的苏炜杰老师在 2019 年与其合作者 Jinshuo Dong 和 Aaron Roth 在此基础上更进一步的工作，该工作于 2021 年发表在Jrrsb上，YouTube 上可以查到 rss 公布的 paper discussion 视频，这篇文章一共约 30 页，内容涵盖众多，所以我想分两节来对这篇文章的内容进行介绍，当然，太过详细的述说就不免失去了我写这篇读书笔记的意义了，所以我会尽量精简的对该文章进行说明与介绍，希望可以使得读者对文章的主要思想有所了解，感兴趣的话去阅读原文就更好啦。

在第一节中，我打算先介绍 Gaussian Differential Privacy 这篇文章给出的新定义以及该定义所具备的基础性质，而在第二节中，我会给出该定义所具备的更多超越其他隐私度量的优良性质。

3.2 定义

3.2.1 基于假设检验的视角看差分隐私

前面的笔记已经证明，满足的差分隐私保护机制是可以推导出任意两个相邻数据集（相差一个单一个体）的假设检验效力函数上界的，那么该文章的想法很 intuitive，为什么不直接用任意两个相邻数据集的假设检验难度来定义差分隐私呢？那么首先，我们需要给出假设检验难度的一个衡量。

3.2.2 Trade-off 函数

trade-off 的意思就是两个事物有某种权衡，此消彼长。

该函数用简单的语言来理解就是在第一类错误固定为 x 的时候，将第二类错误的误差下确界作为 y。

可以证明的是，一个定义域和值域都在 01 区间的函数如果拥有凸性，连续性，单调下降以及被 1-x 上 bound 的性质的话，等价于该函数就是一个 Trade-off 函数。

3.2.4 特殊的trade-off函数 -- Gaussian Differential Privacy

前面说过，trade-off 函数是由两个分布检验难度得到的，那么有没有比较特殊的 trade-off 函数呢？也就是说有没有特殊的两个分布，他们的 trade-off 函数具有非常重要的地位呢？

这里解释一下什么叫做’地位‘，在一个数学体系中，如果一个东西非常常见，可以与这个体系中的其他概念产生广泛的联系，那么称这个东西的地位很高。比如说在离散型随机变量的分布中，01 分布是最重要的，因为所有的离散型随机变量都可以表示成它的线性组合。在连续型随机变量中，正态分布是最重要的，因为中心极限定理的存在，所有的随机变量都可以用一定的方式逼近它。

这篇文章指出，对于这样一类由两个正态分布所得到的 trade-off 函数，它具有非常重要的地位。当然这就涉及到第二篇读书笔记要讲的东西了，我们这里先暂且承认这件事。作者给出了该 trade-of f函数的显式表达。

▲ 显式表达

可以看到该 trade-off 函数只有一个参数

至此，终于出现了该文章的标题所说的术语- guassian differential privacy 的定义了：

我们称一个统计量 M 满足 -GDP，当且仅当

对所有的相邻数据集和成立。

3.3 性质

3.3.1 对称性

对称性其实很容易用直觉感受，因为 trade-off 函数的两个数据集是可以互换位置的，所以最后得出的下界一定是一个对称的函数。

3.3.2 与 -DP 的关系

我们定义一类特殊的 trade-off 函数族：

如下图实线所示

那么可以证明如下性质

▲ 关系

也就是说，其实差分隐私保护机制是一种特殊形式的 f-DP 机制。

3.3.3 后处理以及信息充分性（Post-Processing and the Informativeness)

后处理性质是 dwork 提出来的 -DP 的优良性质，直观上，如果我们发布了一个具有某种隐私保护程度的统计量，那么如果这个统计量被一个函数（可以是随机的）处理后，新统计量的隐私保护程度不应该比原来的统计量隐私保护程度低。同样的 f-DP 也是具备该性质的，数学语言表述如下：

后处理性质：

定义为一个随机化的映射，将统计量映射到一个新统计量，则如果M满足，则也是满足的。

3.3.4 Primal-Dual：f-DP与 -DP的相互转换

3.3.4.1 Primal-Dual

Primal-Dual 在凸分析中是一个重要的话题，学过凸分析的话就会接触这个内容，感兴趣的话可以自行翻阅相关书籍讲义，在这里我们不对优化中的 Primal-Dual 进行过多介绍，简单来说，duality 就是对一个原问题（比如说最优化问题）找到一个对偶问题，二者的最值有一定的关系，在某些情况下是相等的，所以 duality可以说是找到一个问题的另一种视角。

在这篇文章中，作者引用 Primal-Dual 这个术语是想类比 f-DP 与 -DP 之间的关系。具体来说，将 f-DP 视为原始问题，将一组 -DP 视为对偶问题。

3.3.4.2 Dual to Primal

也就是说从 -DP到 f-DP：

记 I 为指标集，则一个统计量对所有都满足 -DP 等价于该统计量是如下定义的 f-DP：。

3.3.4.3 Primal to Dual

反过来也是可以的，假如一个统计量是 f-DP 的，那么等价于它对所有的是满足的。

其中，，是的共轭函数，具体的，

。

3.4 结语

至此我们完成了 f-DP 基本定义以及基础性质的介绍，我们也知道了标题中的 Gaussian Differential Privacy 的具体含义，而且可以看到 f-DP 与 -DP 也是有诸多关系的，这在后面的优良性质推导中会起到重要作用，在接下来的笔记中，我会对 f-DP 所具备的超越其他隐私定义（比如 renyi-DP， -DP）的地方进行阐述。

Gaussian Differential Privacy - 中心地位及优良性质

我介绍了由苏炜杰老师及合作者所提出来的 f-DP 和 GDP 的定义和基本性质，在这篇文章中，我会先简要介绍当然包括经典的 -DP 定义在内的差分隐私定义，然后聚焦于 GDP 优于其他隐私刻画方式的优良性质，介绍其在复合情形下的隐私保护的优良刻画性质。

4.1 f-DP 与 -DP 的简单比较

由于 f-DP 使用函数来对隐私机制进行量化，相比于只使用两个参数的隐私保护机制，函数的无限参数使得 f-DP 可以对隐私的度量更加准确。

在举例子之前，这里要给出在 -DP 的框架下保护隐私的具体方式。

第一节中说到在目前的研究中，针对一个统计量，普遍采用的保护隐私的方法是在发布该统计量之前，对其添加一定量的随机噪声，下面的定理就给出了如何对一个统计量添加噪声，使得最后释放的统计量是满足 -DP 的：

定义1 敏感度（Sensitivity)

对一个统计量，我们定义该统计量的敏感度为：

也就是说敏感度反应了两个相邻数据集统计量的最大差异值。

定理1 添加 Laplace 噪声的 -DP

对一个统计量，

，其中 L 是拉普拉斯分布，则是符合 -DP 的统计量。

定理2 添加 Gauss 噪声的 -DP（Dwork 的经典定理）

对一个统计量，

，其中 N 是正态分布，则是符合 -DP 的统计量。

分析：从参数的外观上，不难发现，第一个定理的参数还算比较自然，但第二个定理的参数就非常不自然，事实上，这是由于第二个定理的证明应用到一些尾概率不等式，而且放缩并不是那么严格和苛刻的，所以这里加入的噪声其实是比较‘大’的，换句话说，在达到要求的 -DP 的前提下，是可以加入比该定理方差更小的正态分布噪声的，那么具体最精确能加多少呢？后续的文献 [9] 中对该问题进行了探讨，篇幅问题，这里只列出结论：

定理3 添加 Gauss 噪声的 -DP 解析解

对一个统计量，，其中 N 是正态分布，则是符合 -DP 的统计量只需要：

，其中，就是，这里方便起见做此简化。

光是看这些，可能会觉得头疼，但是接下来，在 f-DP 的框架下，我们可以直观的看到这三个定理给出的 trade-off 曲线对比。

这里借用 [8] 苏炜杰老师在 Online Discussion 的图：

▲ Laplace 机制和 Gauss 机制的 Trade-off 函数

从第一张图的示意可以看出，在添加 Laplace 噪声的时候，其 trade-off 函数正好能和某个函数相切，所以定理 1 的结果不算难看，左图的蓝色曲线就是 Laplace 噪声后的 trade-off 函数，但到了 gauss 噪声的时候，在两个端点（0，1）和（1，0）处的斜率都是坐标轴方向，所以不可能得到形式的 DP 机制，但是如果允许截距的存在，则就可以被函数相切了。在右边的图中，刚好相切的蓝线就是由定理 3 的解析解所表示的，如果使用定理 2，则最终的线其实是在图中蓝线之上的。

4.2 其他差分隐私刻画方式

Concentrated Differential Privacy

需要用到一些次高斯和 Divergence 的知识，由于篇幅问题，给出原论文 [11] 供查阅。

R´enyi differential privacy

R´enyi Divergence 是一种特殊的Divergence:

对两个概率分布 P 和 Q，order 为的 R´enyi Divergence 定义为：

称一个统计量具有 R´enyi-DP 当且仅当对任意相邻的数据集和：

Truncated concentrated differential privacy

Concentrated Differential Privacy 的推广，篇幅原因这里只给出原文献 [12]。

4.3 复合隐私保护

Setting

复合隐私保护考虑数据分析者对同一个数据集多次进行分析的情况，这其中的问题在于如何衡量在多次在保护隐私地查询（释放统计量）后，一个数据集隐私保护力度的变化情况。我们称这种情况为复合后的差分隐私。

首先，对这种情况进行严格的数学定义：

记为数据集，令为释放的第一个统计量，为释放的第二个统计量，依次定义，我们定义这 n 个统计量的复合为：

为了后续结论，现在定义两个 trade-off 函数的张量积为：

则对一个复合的统计量，其 f-DP 有如下定理：

令对满足 -DP，则 n 次复合统计量是满足 -DP 的。

一般来说，两个 trade-off 函数的张量积的解析表达是复杂的。

但下面的定理表明了 GDP 的优良复合性质：

n 次 -GDP 的复合统计量是符合 -GDP 的。

不过，这还没有奠定 GD P在 f-DP 中的核心地位，如下的中心极限定理表明了 GDP 的核心地位。

（我们先给出形式，然后解释其中的符号含义）

令为一列 trade-off 函数，对，，当的时候：

则我们有如下的中心极限定理：

对所有的成立。

现在来解释其中涉及的两个符号：

这个定理说明：当每次的隐私保护力度都很小的时候，最终的隐私保护力度会趋于一个 GDP，这也对应着在随机变量中的中心极限定理。

相比于其他隐私刻画的复合优越性

从之前的结论可以看出，在单次的隐私保护下，由于 f-DP 拥有更灵活的参数，所以最终的刻画是十分精准的，而在复合隐私保护的情况下，这种精确性也是更为明显的，这里我们还是举例 -DP（因为好画图直观说明）。

下图红线表明的是在 10 次 -DP 复合后的 trade-off 函数曲线，而蓝线则为使用上述中心极限定理得到的逼近曲线。虚线表示用 -DP 所能达到的最好刻画。

从蓝线和红线的贴近，我们可以看到中心极限定理的强大：它便于粗略计算而且效果很好。

从红线和虚线的空隙，我们可以看到 f-DP 在刻画复合隐私保护时的精准。

当然，如果我们改变 -DP 中的进行刻画的话是会有不一样的效果的，但是此时也还是会和真实 trade-off 函数有不小的距离。

4.4 总结

在这一节中，我们简介了一些现有的差分隐私保护机制，介绍了具体的添加噪声的算法，最后介绍了复合差分隐私的概念以及 GDP 在复合查分隐私里的重要性。

参考文献

[1] https://www.ece.rutgers.edu/~asarwate/nips2017/

[2] Wasserman, L., & Zhou, S. (2010). A statistical framework for differential privacy. Journal of the American Statistical Association, 105(489), 375–389. https://doi.org/10.1198/jasa.2009.tm08651

[3] Warner, S. L. (1965). Randomized Response: A Survey Technique for Eliminating Evasive Answer Bias. Journal of the American Statistical Association, 60(309), 63–69. https://doi.org/10.1080/01621459.1965.10480775

[4] Dong, J., Roth, A., & Su, W. J. (2021). Gaussian differential privacy. Journal of the Royal Statistical Society. Series B: Statistical Methodology. https://doi.org/10.1111/rssb.12455

[5] https://www.youtube.com/watch?v=QbMxd0dTexo

[6] Hiriart-Urruty, Jean-Baptiste, and Claude Lemaréchal. Fundamentals of convex analysis. Springer Science & Business Media, 2004.

[7] Dong, J., Roth, A., & Su, W. J. (2021). Gaussian differential privacy. Journal of the Royal Statistical Society. Series B: Statistical Methodology. https://doi.org/10.1111/rssb.12455

[8] https://www.youtube.com/watch?v=QbMxd0dTexo

[9] Balle B, Wang Y X. Improving the gaussian mechanism for differential privacy: Analytical calibration and optimal denoising[C]//International Conference on Machine Learning. PMLR, 2018: 394-403.

[10] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Computing, 40(3):793–826, 2011.

[11] Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint arXiv:1603.01887, 2016.

[12] Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 74–86. ACM, 2018.

特别鸣谢

感谢 TCCI 天桥脑科学研究院对于 PaperWeekly 的支持。TCCI 关注大脑探知、大脑功能和大脑健康。

更多阅读