AL123 人文社科会员免费专区文学 2024-03-18

动手学差分隐私_【美】约瑟夫·P. 尼尔；希肯·亚比雅_AZW3_MOBI_EPUB_PDF_电子书（无页码）_【美】约瑟夫·P. 尼尔；希肯·亚比雅

内容节选

第6章敏感度学习目标阅读本章后，你将能够： ·定义敏感度。 ·找到计数问询的敏感度。 ·找到求和问询的敏感度。 ·将均值问询分解为计数问询和求和问询。 ·使用裁剪技术限制求和问询的敏感度上界。我们在讲解拉普拉斯机制时曾提到，使问询满足差分隐私所需的噪声量取决于问询的敏感度。简单来说，函数的敏感度反映了函数输入发生变化时对应输出的变化程度。回想一下，拉普拉斯机制定义了下述机制F(x)：其中f(x)是确定性函数（即问询函数），ϵ是隐私参数，而s就是f的敏感度。给定一个将数据集（D）映射为实数的函数f:D→R，f的全局敏感度（global sensitivity）定义如下：其中d(x,x′)表示两个数据集x和x′之间的距离（distance）。如果两个数据集之间的距离小于等于1，我们称这两个数据集是邻近集（neighbor）。数据集的距离定义会对隐私定义带来很大的影响。我们稍后将讨论如何度量数据集之间的距离。全局敏感度的定义告诉我们，对于任意两个邻近数据集x和x′，函数f(x)和f(x′)的输出最多相差GS(f)。此敏感度的定义与具体问询的数据集无关（对于任意两个邻近集x和x′都成立），因此我们把这一敏感度度量方法称为“全局”敏感度。另一种敏感度度量方法将其中一个数据集固定为被问询的数据集，对应的敏感度称为局部敏感度（local sensitivity）。我们将在稍后的章节中具体讨论局部敏感度。现在，当提到“敏感度”时，我们均指全局敏感度。 6.1 距离可以用很多不同的方法来度量前面提到的距离d(x,x′)。直观来看，如果两个数据集中只有一个个体的数据不一样，则这两个数据集之间的距离应该等于1（即这两个数据集是邻近集）。很容易在某些场景下用数学语言定义距离度量方法（例如，在美国人口普查场景中，每个个体都只贡献一条自己的数据）。但在另一些场景下（如位置轨迹、社交网络、时序数据等场景），用数学语言定义距离度量方法颇具挑战。对于按行存储的数据集，通常会把距离定义为有多少行数据值不相同。当每一行仅包含单一个体的数据时，这种距离度量方法一般都是合理的。如果用数学语言描述，这种距离度量方法可以由两个数据集的对称差（symmetric difference）所定义：这个特殊定义有几个有趣且重要的含义： ·如果x′是通过向x添加一行来构造的，则d(x,x′)=1。 ·如果x′是通过从x删除一行来构造的，则d(x,x′)=1。 ·如果x′是通过在x修改一行来构造的，则d(x,x′)=2。换句话说，添加或删除一行数据可以生成邻近数据集，修改一行数据则生成距离为2的数据集。这种对距离的特殊定义通常称为无界差分隐私（unbounded differential privacy）。也有一些其他的距离定义。例如，有界差分隐私（bounded differential privacy）认为修改数据集中的单行数据即可构成邻近数据集。现在，我们主要采用对称差邻近数据集的数学定义。我们将在稍后的章节中讨论替代定义。 6.2 计算敏感度我们如何确定特定函数的敏感度呢？对于实数域上的一些简单函数，答案是显而易见的。 ·f(x)=x的全局敏感度是1，因为x变化1，f(x)变化为1。 ·f(x)=x+x的全局敏感度是2，因为x变化1，f(x)变化为2。 ·f(x)=5* x的全局敏感度是5，因为x变化1，f(x)变化为5。 ·f(x)=x*x的全局敏感度是无界的，因为f(x)的变化取决于x的值。对于将数据集映射到实数的函数，我们都采用类似的分析方法。下面我们将考虑3个常见的数据库聚合问询函数——计数问询、求和问询和均值问询。 6.2.1 计数问询计数问询（利用SQL中的COUNT算子）计算数据集中满足特定属性的行数。一般来说，计数问询的敏感度总等于1。这是因为向数据集中添加一行数据最多会使问询的输出结果增加1，即当新增行满足特定属性时，计数结果加1。反之，当新增行不满足特定属性时，计数结果不变（删除行可能使计数结果减1）。例子：“数据集中有多少人？”（敏感度：1，计算总行数。）例子：“受教育年数超过10年的有多少人？”（敏感度：1，根据属性计算行数。）例子：“受教育年数小于或等于10年的有多少人？”（敏感度：1，根据属性计算行数。）例子：“名字叫Joe Near的有多少人？”（敏感度：1，根据属性计算行数。） 6.2.2 求和问询求和问询（利用SQL中的SUM算子）计算数据集行中的属性值（attribute value）总和。例子：“受教育年数超过10年的人，其年龄总和是多少？” 计算求和问询的敏感度不像计数问询那么简单。向数据集添加一行新数据会使样例问询增加一个新个体的年龄。这意味着问询的敏感度取决于我们添加的具体数据是什么。我......