论文下载地址：http://cseweb.ucsd.edu/~kamalika/pubs/survey.pdf
相关会议视频：https://youtu.be/qH-jUfzoeXA

私营公司、政府单位、医院等机构在日常生活中积累了大量关于客户、消费者、患者的数字个人信息。这些信息大多是私人或敏感的。未来的一个关键技术挑战是如何系统或处理技术，在保证数据和个人信息隐私和安全的前提下，从这些大规模数据中提取信息。个了公共健康，个人经常自愿分享数据，但他们希望自己的身份或参与的事实不会被泄露。近年来，解决这些挑战的隐私模型和隐私保护。本文将介绍差异化隐私机器学习和信号处理的相关进展。

隐私保护的定义和模型很多，最近Fung等人[1]的研究比较了几种不同的方法。这些模型大多被证明对合成攻击无效。合成攻击是攻击者通过观察算法的输出来确认个人信息[2]。例如，攻击者可以使用可用的公共记录，如投票调查[3]。定义隐私不是一件简单的事情。隐私、秘密和安全在不同的场景中有不同的含义。越来越明显的是，个人身份和数据之间没有真正的分离——与个人相关的数据模式本身是唯一可识别的。
差异隐私[4]是一种基于密码的隐私定义，近年来在机器学习和数据挖掘领域得到了显著的关注。对于差异隐私有一些不同的定义[5]-[7]，但对于本研究，差异隐私通过参数$?$为了衡量隐私风险，这个参数限制了两个数据集中输出结果中(私有)算法的对数，而这两个数据库中只有一个个人数据是不同的。$?$在相对较小的时候，无论个人数据是否集中在数据集中，攻击者对算法输出的观察结果都是相似的。还有其他关于隐私文献差异的研究；特别是，Dwork和Smith[8]研究包括大量的早期理论工作。差异化隐私的隐私保证本质上是统计的，不同于密码学[9]或信息论[10]的隐私保证。
发布过滤数据等官方统计数据中存在的问题，促进了差分隐私的初步工作。另一种不同的方法是交互查询模型：用户向数据库管理员提出查询，然后管理员提供类似的答案。近似值是为了保护个人数据的隐私。通过这两种不同的设置，各个文献扩展到更复杂的数据处理算法，比如实时信号处理[11]-[13]，分类[14]-[16]，降维[17]-[18]，和拍卖设计[19]。
在这些应用程序中，关键挑战是估计隐私限制在算法效果或性能上的影响。隐私和实用性是相反的；一个完整的隐私算法不会发布任何东西。尽管如此，如果可用的数据集包含大量的个人信息，那么隐私保证$?$、实用性和数据点数量(样本量)$n$两者之间有平衡。总的来说，这个平衡依赖于数据集的性质，比如它的维度、值域或者稀疏度。在不同的应用领域，如何测量实用性是不同的。例如，对于统计估计，我们可以使用均方差错（MSE）对于分类，我们可以测量预期的损失。通过计算每个数据集可以达到的隐私和准确性等级，可以提供一种在同一任务上比较不同差异的隐私算法的方法。
虽然差异化隐私的理论正在经历显著的发展，但这里有大量的有大量的遗留工作。其实很多理论都是针对离散数据发展起来的，从实现差分隐私算法[20]到理论基础[21]，连续数据带来了很多挑战。在本教程中，我们将重点关注在连续数据上操作差异隐私的统计方法和算法。我们将介绍统计估计、分类程序、降维技术和信号处理技术。
隐私理论与离散数据不同。例如，在离散数据上学习分类器很容易。如果可能的分类器或假设数量有限或数据离散，则当数据点n随假设集或数据域的大小呈对数增加时，可以学习最佳分类器[22][23]：在$[0,1{]}^d$范围内的数据、样本量$n$一定和维度$d$线性相关性。另一方面，当数据允许连续和类别时许是无限的，无分布统计学习是不可能的[24]：我们既不知道数据分布的先验知识，$n$也依赖于数据分布。因此在样本需求上没有形式化的上界。这甚至适用于简单的类,如学习阈值和线性分类器：在缺乏隐私约束的条件下,我们可以选择一个n,这样我们对于任何的数据分布都可以学习真正的假说，但为了学习具有差分隐私的真正的假说，必须选择n作为数据的分布函数。
        信号处理的技术有可能很好的扩展连续型数据的差分隐私算法。我们集中注意力在连续型数据意味着我们将不讨论在离散型差分隐私上的许多调查主题。特别的，我们将不讨论某些方面的进展，比如说为差分隐私设计的软件系统[25]-[27]、计算直方图和列联表的算法[28][29]，或者是大量隐私保护的数据的发布工作（这些能在最近的工作中找到[18][30]）。

        在数据集$D=(x_1,x_2...,x_n)$中有$n$条记录，其中$x_i$是$R^d$中的向量，对应于一条数据。$d$维向量对应于不同的特征。我们假设这些特征的值域被正则化为$||x||\le 1$，其中$||\cdot ||$是欧几里德范式。尽管在这次研究中我们集中注意力在连续型数据上，目前存在大量的关于离散型数据的差分隐私文献。

        差分隐私旨在为敏感数据的计算过程提供保障，它具有许多特性，使得成为一种有吸引力的隐私量化方法。隐私通过确保使用下面的承诺进行随机化来保证的：如果在数据库中任何记录的参与（对应于一个个体）不会显著修改输出的可能性，我们认为这个算法是差分隐私的。这个定义有许多特点：它可以抵抗其他隐私模型容易受到的攻击[2]，它限制了每个人的隐私风险，并且随着个人数据在多个计算中被使用，它可以优雅地降级。

        一个算法$A_{priv}(\cdot )$在集合$T$中提供$ϵ$-差分隐私，需要对于所有的可测量的$S⊑T$和所有的差一个简单记录的数据集$D$和$D^{{}^{\prime }}$都满足：

它提供$(ϵ,\delta )$-差分隐私需要对所有的$S⊑T$和所有的相差一个记录的数据集$D$和$D^{{}^{\prime }}$都满足：

        这里我们假设在数据集$D$中的每个条目都对应一个个体。隐私参数是$ϵ$和$\delta$，较小的参数可以保证隐私[4][21]。第二个隐私保证是很弱的[31]，当$\delta =0$是就是第一个。差分隐私的变体，比如$(1,ϵ,\delta )$-不可区分性[7]和$\delta$-可能性隐私[32]，在文献中也被考虑过；为了我们的目的，我们集中注意力在最受欢迎的变体上。
        差分隐私算法有两个重要的特征。首先，如果$v$是一个$ϵ$-差分隐私算法$A_{priv}$的输出，那么对于输出的任意函数$g(v)$而言都保证是$ϵ$-差分隐私。那是因为输出的后续处理不改变隐私保证，同时后续处理也不使用原始数据。第二个关键特征是数据上的多次计算如何影响隐私保证。如果我们在${ϵ}_1$和${ϵ}_2$的隐私保证下在数据集上运行算法$A_{priv}^{(1)}$和算法$A_{priv}^{(2)}$，那么$(A_{priv}^{(1)},A_{priv}^{(2)})$就能保证最大隐私风险为${ϵ}_1+{ϵ}_2$的差分隐私。如果我们允许$(ϵ,\delta )$-差分隐私的话，也许能获得更好的保证[33]。

        对于一个给定的算法或者函数$A_{nonpriv}$，有许多通用的方法来生成满足其中一个隐私定义的近似算法$A_{priv}$。这些方法展示在FIG1 中。这些方法以不同的方式引入了隐私保护的随机性，但大多涉及在原算法$A_{nonpriv}$的某些步骤中加入噪声。我们描述了以下四种获取差分隐私的关键方法。

        假如我们想要提供我们的身体传感器数据给第三方。最容易保证差分隐私的方式是把噪音添加到数据本身上。如果$x$是真实的d维向量，一个差分隐私版本的x是：

其中Z是一个随机的d维向量，服从：

        通过对集合$D$中的每个向量$x_i$添加添加噪音，我们能够保证生成的数据集$\hat{D}=\widehat{x_1},...,\widehat{x_n}$是和$d$近似$ϵ$差分隐私。在标量环境下这对应于添加$Laplace$分布的噪音。这不是唯一的保证差分隐私的分布，特别的，对于输出上的给定实用程序，在提供差分隐私的同时最大化实用程序的噪声分布可能具有不同的形状。

        假设现在我们希望计算人群中每个传感读数的平均值。在这种情况下，我们想要的算法$A_{nonpriv}$简单的计算一个数据的函数$fD)$，我们能够通过像$f(D)$上添加噪音来获得差分隐私。我们需要添加的噪音量依赖于函数$f$对于输入变化的敏感度。全局敏感度是仅仅一个记录不同的所有数据集$D$和$D^{{}^{\prime }}$之间最大的差异：

其中$||\cdot ||$是欧几里德范式。我们能够计算一个$f$的差分隐私近似：

其中$Z$是d维向量，服从分布：

        例如，为了计算平均向量$f(D)=(1/2){\sum }_{i=1}^n{x}_i$，敏感度$S(f)=2/n$。这是（全局）敏感度方法[4]，并且有许多变体来处理其他的更宽松的敏感度概念。例如，平滑敏感方法[34]在给定的数据集$D$上，通过添加噪音获得一个只有在最坏情况下有较大$S(f)$的函数$f$，让它作为敏感度的平滑版本函数。

        假如我们想要使用活动中的k次心率读数来发表一个活动后病人的心率预测。给定一个早已开源的线性预测$P_{}$