ACM通信

研究突出了

无罪数据重用

作者:辛西娅·德沃克，维塔利·费尔德曼，莫里茨·哈特，托尼安·皮塔西，奥马尔·莱因戈尔德，亚伦·罗斯
ACM通信，2017年4月，第60卷第4期，86-93页
10.1145 / 3051088
评论

现有的确保从数据中得出的推论有效性的方法假设执行一个固定的过程，在检查数据之前选择该过程。然而，数据分析的实践本质上是一个互动和自适应的过程:在看到之前的结果后提出新的分析和假设，在获得的结果的基础上调整参数，数据集的共享和重用。

在这项工作中，我们对如何保证统计推断在自适应数据分析中的有效性进行了原则性的研究。我们展示了基于隐私保护数据分析中开发的技术来解决适应性挑战的新方法。

作为我们技术的一个应用，我们给出了一种简单实用的方法，用于重用抵制集(或测试集)来验证由在训练集上操作的学习算法自适应生成的假设的准确性。

回到顶部

1.引言:问题及其重要性

从发现新粒子和临床研究到选举结果预测和信用评分评估，科学研究和工业应用严重依赖统计数据分析。统计数据分析的目标是使分析人员能够通过分析过程生成的数据样本来发现过程或现象的属性。幸运的是，数据样本反映了产生它们的过程的许多特性:如果吸烟增加了肺癌的风险，那么我们应该期望在医疗记录样本中看到吸烟和肺癌之间的相关性。然而，数据也会表现出来自数据采样过程中的随机性的特质，而不会说明产生它们的过程。如果我们从该过程中重新采样新数据，这些特质就会消失。从这些特性中梳理出流程的真正属性是非常困难且容易出错的任务。由这种错误引起的问题可能代价高昂，并促使人们更广泛地关注研究结果的可重复性，尤其是在医学研究领域。¹⁸

统计学家早就建立了许多方法来衡量对分析结果的信心，其中最著名的就是这些方法P-值和置信区间。这些概念允许分析人员表达这样一种可能性(在随机抽样的情况下)，即分析的结果只是一种特性，并不适用于数据的真实分布。因此，当这个概率足够小时，结果可以被宣布具有统计学意义。保证有一个置信区间或P-value提供一个关键的警告;但是，它们仅适用于在没有检查应用该程序的数据的情况下选择分析程序的情况。

当分析人员执行多个分析，但只报告最有利的结果(例如，得到最低的结果)时，这种保证就会发生简单而众所周知的滥用P值)。它有很多名字，包括多重比较问题，多重测试，P-黑客攻击和数据挖掘。报告指出，由于这种选择性的结果，报告的分析依赖于数据P-value是不正确的，结论通常无效。许多技术，最著名的是错误发现率控制，^3.已开发用于处理多重比较，当要执行的分析集在收集数据之前就已经知道。与此同时，数据分析的实践远远超出了从固定的分析集合中挑选最佳结果的范围。数据探索激发假设生成;一个测试的结果决定接下来执行哪些分析;对大型语料库的一次研究决定了对同一语料库的下一次研究。总之，数据分析在实践中本质上是一种自适应的过程。

尽管在自适应分析中重用数据非常有用，但它会极大地增加虚假发现的风险。分析中的适应性选择可能导致在分析师收到不同的数据样本时执行的程序数量呈指数增长。换句话说，根据数据进行分析会导致一个隐式的、潜在的非常大的多重比较问题，被Gelman和Loken恰当地称为“分叉路径的花园”。¹⁴

虽然通常不理解这些术语，“弗里德曼悖论”是一个优雅的示范，自适应分析对结论有效性的强大影响。¹³在弗里德曼的模拟中，一个方程是拟合的，变量有一个不重要的t-统计数据被删除，方程被重新调整为这个新的自适应选择的变量子集，其著名的误导结果是:当因变量和解释变量之间的关系不存在时，这个过程会过度拟合，并错误地声明重要的关系。在Aschwanden的在线文章中可以找到一个关于线性回归分析结果的变量选择的极好的交互式演示。¹

虽然我们前面的讨论主要涉及统计的应用;自适应数据分析在机器学习中也面临着类似的挑战。机器学习的一个重要目标是获得一个具有良好泛化能力的预测模型，即该模型对数据的准确性能够代表其对由相同过程生成的未来数据的准确性。事实上，大量的理论和实证研究被开发出来，以确保在各种各样的设置中普遍化。在理论工作中，通常假设学习算法操作在一个新采样的数据集上。实际上，一个数据集被随机分成两个(有时更多)部分:训练集和测试集(或坚持集)。训练集用于学习预测器，抵制集用于估计预测器的真实准确性。因为预测器是独立于抵制数据集的，这样的估计是真实预测精度的有效估计。

然而，在实践中，坚持数据集很少只使用一次。超参数调优是一个经常自适应重用抵制集的突出例子。类似地，机器学习竞赛(如著名的ImageNet竞赛)中的抵制集通常会被多次自适应重用。其他示例包括使用坚持集进行变量选择、生成基本学习器(在聚合技术中，如增强和套袋)、检查停止条件和循环分析器决策。众所周知，这样的重用会导致对抵制集的过拟合(例如，参考文献。^7，22)．

文献认识到风险，并在自适应数据分析的一些特殊情况下提出解决方案。它们中的大多数都解决了单轮自适应问题，如变量选择之后是对所选变量的回归，或者模型选择之后是测试，并针对特定的推理过程进行了优化(参见参考文献中的第7章)。¹⁷概述)。然而，据我们所知，目前还没有一项工作给出了一种通用的方法，可以在不限制所执行过程类型的情况下，解决多轮自适应数据重用的风险。我们描述了这样一种方法，它基于隐私保护数据分析的技术，以及一个我们称为的具体应用程序可重用的抵抗。

回到顶部

2.我们的方法和结果^一个

让我们建立一些简单的术语。我们将一个数据点表示为某个宇宙的一个元素数据集由n数据点。数据生成过程产生数据集上的概率分布。我们将关注最常被研究的设置，在这种设置中，数据集的每个点都是随机抽取的，独立于某个未知分布P在．例如，数据集可能包含的健康信息和习惯n个体，分析人员试图了解影响个体随机抽取的人群的医疗状况。

我们认为自适应分析是一个过程，在这个过程中分析师希望提出一系列的问题查询在给定的数据集上。在这里，查询可以指某些统计过程、学习算法、预处理步骤或数据的任何其他检查的执行。关键是，在问完第一个问题之后t查询时，分析人员可以使用这些查询的结果来选择在步骤中执行的查询t+ 1。虽然我们的方法可以应用于非常一般的查询定义，但为了简单起见，我们首先关注估计函数平均值的查询：[0,1]在未知分布上P或P［] =E_{x ~ p}［（x)]。估计需要是正确的，直到一些相加误差通常被称为宽容有高概率的。这样的查询允许分析人员了解人口的各种基本统计数据，例如，超过6英尺的人口占总人口的比例。更一般地说，它们允许分析师估计单个属性的真实均值和矩，属性之间的相关性和任何预测模型的准确性。这样的查询称为统计在经过充分研究的统计查询模型的背景下¹⁹在统计学中也被研究过线性统计泛。众所周知，许多标准数据分析可以通过访问统计查询来执行，而不是直接访问数据(参见参考文献)。^4，19例子)。

即使在这个相对简单的设置中，有多少自适应选择的统计查询可以使用正确回答的问题n从样本中提取I.I.D.P以前没有检查过。为每个自适应选择的查询使用新样本的保守方法要求n随查询的数量线性扩展m。我们观察到，在通过样本的确切经验平均值来估计期望的标准方法中，这种糟糕的依赖性是固有的。“弗里德曼悖论”直接暗示了这一点。¹³我们在参考文献中描述了另外一个简单的例子。⁹这种情况与非适应性的情况形成鲜明对比例子足以回答这个问题米使用经验平均值的公差查询。

我们演示了可以使用在的上下文中开发的技术来解决这个问题微分隐私，这是为保护隐私的数据分析量身定制的隐私定义。粗略地说，差异隐私确保了通过修改任何单个数据集元素观察到分析结果的概率“基本不变”(概率分布覆盖算法引入的随机性)。

差异私有数据分析的核心观点是，可以了解数据集的统计属性，同时控制关于任何数据集元素的信息披露量。我们的方法基于自适应数据重用问题的相同观点:如果向分析人员透露的数据信息量有限，则可以防止分析人员对数据进行过拟合。为了确保信息泄漏受到限制，算法需要控制分析师对数据的访问。通过引入两个随机变量之间最大信息的概念，我们证明了这一观点可以形式化。这个概念允许我们限定一个因子，通过这个因子，算法在这个数据集上的输出可以减少数据集的不确定性。我们将在3.1节中更详细地描述它。

我们的主要技术成果是广泛的传输定理表明任何以不同的私人方式进行的分析都必须得出一般化到基本分布的结论。这一定理使我们能够利用差分隐私的丰富结果，并对自适应数据分析中保证泛化的问题得到相应的结果。我们将在第3节详细描述这个一般定理。

我们的定理的一个直接推论是，值得注意的是，近似解是可能的指数增长很多自适应选择的统计查询(在数据集的大小上)n)．同样地，这减少了样品的复杂性回答米查询从线性在查询的数量polylog-arithmic，几乎匹配非自适应选择查询所必需的依赖性。

定理1。有一个算法，给定一个至少n n的数据集₀，可以回答任意m个自适应选择的统计查询，使每个答案在高概率下都是正确的，直到公差，其中

在这个绑定对数|中应该将|大致视为维的域。例如，如果底层域是= {0,1}^d的所有可能向量的集合d-boolean属性，然后记录|| =d。

不幸的是，这种用于回答查询的算法计算效率不高(它的运行时间与数据宇宙的大小|成线性关系)|,指数在数据的维度上)。尽管如此，我们证明了通过使用一个简单而实用的算法，用独立噪声扰动每个查询的答案，可以对naïve基于经验均值的方法进行二次改进。

定理2。存在一种计算效率高的算法，用于回答m个自适应选择的统计查询，这样，在给定一个至少n n的数据集的情况下，答案有很高的概率是正确的，直到公差₀:

我们的研究结果自然提出了一个问题:是否存在一种有效的算法，可以回答指数数量的自适应选择的查询。这个问题已经在参考文献中得到了解决。^16，25谁证明了在标准的密码假设下，没有算法可以改进我们的简单算法所达到的上界:任何算法可以回答超过n²自适应选择的统计查询必须具有log |的运行时间指数|。

这个下界意味着，能够回答任意和自适应选择的查询的指数数量的实际算法不太可能存在。然而，我们表明，有一种替代方法可以应用我们的技术，有效地回答指数级数量的查询。在这个应用程序中，分析人员将数据集分为一个训练集和一个拒绝集。然后，分析人员可以对训练数据集执行任何分析，但只能通过对我们的可重用的抵抗算法。可重用的抵制算法允许分析师根据抵制集验证她的模型和统计数据。更正式地说，分析人员可以选择任何函数：[0,1]。的经验均值在训练集上的评价接近于真实的期望P［，换句话说没有对训练集过拟合，则可重用拒绝确认没有过拟合(但不提供额外信息)。否则，算法返回的估计值P［的统计查询．

我们描述一个可重用拒绝的特定实例，称为Thresholdout．查询的数量Thresholdout能不能回答在抵制集的大小上是指数级的n只要分析者(对训练集)过拟合的次数最多是二次元n。的分析Thresholdout是基于差分隐私的已知技术和我们的转移定理。在第4节中，我们将描述Thresholdout及其详细的保证。的性质Thresholdout对合成数据使用一种简单的分类算法。该算法产生的分类器在以标准方式重用抵制集时对数据进行过拟合，但在使用我们的可重用抵制集时不进行过拟合。

在裁判,¹⁰我们描述了基于描述长度的自适应查询验证结果的附加算法。我们对这一简单而经典的技术的应用不同于其标准的泛化应用。它带来的算法保证是那些通过差别隐私实现的算法无法比拟的。

2.1.相关工作

在理论机器学习中，确保经验估计推广到底层分布的经典方法是基于算法输出的函数集的各种复杂性概念，最著名的是Vapnik-Chervonenkis (VC)维(参见参考文献)。²³参考教科书介绍)。如果有一个足够大的数据样本，可以保证在某一类具有有限复杂度的函数中对所有函数进行泛化，那么数据分析师是自适应还是非自适应地选择该类中的函数就无关紧要了。相反，我们的目标是证明泛化边界没有对分析人员可以从中选择查询函数的类做出任何假设。在这种情况下，适应性设置与非适应性设置是非常不同的。

重要而相关的工作^6，20.，24在稳定学习算法和它的泛化能力。稳定性是一种衡量由学习算法输出的函数的误差受其输入数据集变化的影响程度的指标。众所周知，某些稳定性概念对于泛化是必要和充分的。²⁴不幸的是，在这些先前的工作中考虑的稳定性概念并没有在这样的意义上构成:按顺序和自适应地运行多个稳定算法可能会导致一个不稳定的过程。差分隐私比这些先前研究过的稳定性概念更强，而且特别享有强大的构成保证。这为建立复杂的算法提供了一种微积分，这些算法满足足够的稳定性保证，可以进行泛化。因此，我们的工作可以解释为，在多步骤自适应分析设置中，差异隐私起着稳定的作用。

为各种数据分析任务设计差异私有算法的工作非常多，我们在应用程序中利用了其中一些算法(参见参考文献)。⁸参阅简短调查和参考资料。¹²阅读一本关于不同隐私的教科书)。

对于输出假设的差分隐私算法，差分隐私意味着替换(或删除)输入数据集中某个元素的假设的稳定性，这被称为民间传说。长期以来，人们都知道这种稳定性意味着泛化在期望(例如,裁判。²⁴)．我们的技术可以被看作是对这种观察的实质性加强:从期望到高概率边界(这对回答许多查询至关重要)，从纯粹到近似差分隐私(这对我们改进的高效算法至关重要)，以及超出假设的预期误差。

以我们的工作为基础，布卢姆和哈特⁵展示了如何在机器学习竞赛中重用拒绝集以保持精确的排行榜，该竞赛允许参赛者在竞赛过程中提交自适应选择的模型(如由Kaggle Inc.组织的那些模型)。

最后，在最近的后续工作中，Bassily等人。²定量地加强泛化和近似差分隐私之间的联系，并将其扩展到更一般的低灵敏度查询类。他们的结果导致了保证泛化所需要的样本数量的界限，使我们的定理改进了一个因子．

回到顶部

3.差别隐私与泛化

我们的结果依赖于我们在差异隐私和泛化之间建立的紧密联系。在较高的水平上，我们证明了如果米是差分私有算法吗?那么它在随机数据集上输出的函数的经验平均值将接近函数的真实期望，在数据集的选择和的随机性上有很高的概率米．更正式地说，用于数据集年代= (x₁……x_n)和一个函数的经验平均值．我们表示一个随机选择的数据集Pⁿ通过年代．独立随机变量和的标准Chernoff-Hoeffding浓度不等式意味着对于任何固定函数，经验平均数_年代［强烈地集中在它的期望周围P［］．然而，这种说法不再正确，如果是否允许依赖年代(例如，如果我们自适应地选择函数，使用先前的估计年代)．然而，对于一个由差分私有输出的假设米在年代(用＝米（年代)，我们证明了这一点_年代［接近于P［的高概率。在正式陈述之前，我们回顾了差异隐私的定义。¹¹

定义3。定义域为X的随机算法Mⁿis(，)-区别私有if for所有O范围(米）对于所有对数据集S, S＇Xⁿ在单一元素上不同的:

其中概率空间是除以算法m抛硬币的次数，当= 0有时被称为纯差分隐私，在这种情况下，我们可以简单地说M是-差分隐私。

我们得到的纯微分隐私的浓度边界几乎与标准Chernoff-Hoeffding浓度不等式给出的浓度边界一样强。

定理4。设M是一个-差分私有算法，它从到输出函数[0,1]。对于一个随机变量年代按P分布ⁿ我们让= M(年代)．然后

对于一类重要的低灵敏度函数，这种说法也适用得更广泛。这些是数据集的函数灵敏度满足:|f（年代）f（年代|用于所有数据集年代,年代ⁿ在单一元素上的差异。注意范围为[0,1]的任何函数的经验平均值在规模较大的数据集上的灵敏度n是1/n．

我们将在3.1节概述这一结果的证明思路。(也可得到类似的浓度结果。，)-差分私有算法，尽管它不是很强大，需要一个本质上不同的和更复杂的证明。我们在这种情况下的结果(参见参考文献。⁹)最近已被Bassily等人使用一种新的证明技术加强并推广到低灵敏度查询。²

定理4表明|P［] -_年代［|保持高概率是由差分私有算法生成的吗米．这看起来可能与我们在应用程序中需要的不同，因为在应用程序中查询是由任意(可能是对抗性的)自适应分析器生成的，而我们只能控制查询回答算法。这种联系来自于差别隐私的一个关键属性，即后处理保证:任何可以被描述为(可能是随机化的)差分私有算法输出的后处理的算法本身就是差分私有的(例如，Ref。¹²)．因此，尽管我们不知道一个任意的分析师是如何自适应地生成她的查询的，但我们知道，如果她拥有的唯一访问年代是通过差分私有算法，那么她产生查询函数的方法就必须是差分私有的年代．因此，在不丧失一般性的情况下，我们可以将查询回答算法和分析师视为单算法米，即给定一个随机数据集年代并返回差异私有输出查询＝米（年代)．

我们还注意到，定理4中的界限给出了查询的每个单独答案的正确概率，这意味着错误概率是针对每个查询的，而不是同时针对所有查询的。我们在定理1和定理2中陈述的边界对所有的都具有高概率米查询，为了从本节的边界中获取它们，我们应用联合边界。

为了得到一个回答自适应选择的统计查询的算法，我们现在所缺少的只是一个满足以下两个条件的算法:

1. 该算法可以回答每一个查询使用一个值，即close(直到error)的经验平均数在数据集上。
2. 该算法是差分私有的。

为数据集上函数的平均值的大量查询提供准确答案的问题，一直是不同隐私文献中密集研究的主题。这样的查询通常称为(分数)计算查询或线性查询在这种情况下。这允许我们通过使用各种已知的差分私有算法来回答计数查询，从而获得统计查询回答算法。具体来说，我们的定理1依赖于Ref中的算法。¹⁵它使用乘权更新算法来回答查询。我们的定理2依赖于基本的拉普拉斯噪声机制和微分的强复合性质。

在得到的算法中，应该被视为限制经验误差，应该被看作是泛化误差和=+作为总误差的边界。注意，使用经验平均数的标准方法具有最佳的经验误差= 0。然而，事实并非如此-区别于任何私有并且，正如我们前面指出的，不提供任何对泛化误差的保证。在另一端，一个用一个常数回答查询的算法，独立于数据，有最佳的泛化误差，但可怕的经验误差。用于回答计数查询的差分私有算法允许我们显式地权衡经验误差与泛化误差得到总误差的强界。

3.1.Max-information

直观地说，一种方法是保证函数由算法输出米泛化是为了保证函数不过度依赖输入数据集年代．我们证明，这种直觉可以通过概念捕获max-information我们介绍。

定义5。让X而且Y是联合分布的随机变量。之间的max-informationX而且Y,表示我（X;Y)，是k的最小值，使得对于的支持度中的每一个xX而在…的支持下Y我们有公关(X= x|Y= y) 2^k·公关(X= x］．

根据贝叶斯法则我（X;Y）＝我（Y;X)．在我们的用法中(X, Y)将是一个联合发行(年代，)在(dataset, function)对上。数据集年代是从分布中得出的Pⁿ对应于n取身份证的点P．随机变量表示分析人员生成的函数，而与之交互年代通过我们的机制。重要的是，分析人员可以在观察同一数据集上其他函数的计算之后，得出函数年代．现在对于每一个可能的函数在我们关联了一组“坏”数据集R（)．我们以后选择R（)表示经验值_年代［与真正的价值相差甚远P［),也就是说,overfits来年代．最大信息给出了一个概率的界限年代落在R（)．

定理6。k＝我（年代,),公关年代R（) 2^k·马克斯公关(年代R（)]。

首先对事件进行分解，接下来的证明就很容易了年代R（)事件,年代R（) &＝对所有．也就是说,

自

我们可以应用max-information的定义，得到Pr[年代R（) |＝) 2^k公关(年代R（)]。将这个界限代回到分解中得到预期的结果:

我们的定理在随机变量的意义上是完全通用的在函数上不需要支持吗也可以在其他离散域中取值。例如，这样的输出可以是用于后续监督学习任务的一组数据特征。对于我们的主应用程序表示一个函数，我们表示经验估计误差大于as的数据集

根据Hoeffding界，我们知道最大值公关(年代R（(2)经验值²n)．这就得出了以下直接的推论。

推论7。如果我_；（年代,)日志₂e·²n,那么公关(年代R（exp (-))²n)．

要应用这个推论，我们所需要做的就是证明纯粹的差别隐私意味着在最大信息上有一个足够强的界限我（年代,)．

定理8。设M是一个-差分私有算法。让年代为M的n元输入数据集上的任意随机变量，令Y对应的输出分布Y= (年代)．然后我（年代;Y）日志₂e·n。

这个定理的证明是通过观察任意两个数据集得出的年代而且年代最多有不同之处n元素。因此，应用差别隐私的保障n乘以，我们得到每一个y，

因为一定存在一个数据集y这样的公关(Y= y|年代= S ')公关(Y= y我们可以得出结论，对于每一个年代和每一个y它认为Pr[Y= y|年代=年代］eⁿ公关(Y= y］．这将产生所需的边界我（年代;Y）＝我（Y;年代）日志₂e·n。

由定理8和推论7，我们可以看出²-在与数据集的整个交互过程中的差异隐私严格控制了对手可以选择一个过于适合数据集的函数的概率。这比定理4中的要求-差分隐私的要求要差一些。在裁判,¹⁰我们证明，对于由I.I.D.样本组成的数据集，通过考虑一个简单的max-information松弛(称为近似max-information)，可以证明差分私有算法的max-information的强界。有趣的是，不难看出，输出描述长度较短(以位为单位)的算法也具有较低的近似最大信息。因此近似最大信息统一了通过(纯)差分隐私和描述长度获得的泛化边界。此外，近似最大信息的组合性质意味着可以很容易地获得自适应算法序列的泛化保证，其中一些算法序列是差分私有的，而另一些算法的输出描述长度较短。

回到顶部

4.可重用的抵抗

在本节中，我们将描述我们的框架的一个实际应用程序，它提供了一种多次安全地重用拒绝集的方法。在这个应用程序中，分析人员将数据集分为一个训练集和一个拒绝集。这种方法的一个优点是，数据分析师可以完全、不受限制地访问训练集，并可以以任何她想要的方式使用它。只能通过可重用的坚持算法访问坚持集。该算法的目标是验证在训练集上执行的分析结果。

我们描述一个可重用拒绝的特定实例，称为Thresholdout，它验证统计查询的值，并基于来自差异隐私的“稀疏向量”技术(例如，参考文献第3章)。¹²)．具体来说，对于每个函数：[0,1]，该算法检查的经验平均值是否在训练集上是接近真实均值的(在一定限度内)。如果值很接近，算法就不会向分析人员提供任何额外的信息。只有在过拟合的训练集，算法提供的真实期望的有效估计．结果是，对于分析师提出的所有查询，她对真实期望有正确的估计——要么我们的算法证明来自训练集的估计是近似正确的，要么它使用坚持集提供了正确的估计。对算法的分析表明，所需要的样本数量Thresholdout只要过度拟合训练集(并且必须使用保留集来回答)的查询总数不是太大，它只对数据分析师提出的查询总数有对数依赖性。因此，这种简单和计算效率高的算法可以潜在地回答一个指数(在n)查询的数目。

更正式,Thresholdout是否可以访问训练数据集年代_t数据集和坚持年代_h预算限制B。它允许对表单进行任何查询：[0,1]，其目标是提供的估计值P［］．为实现这一目标，算法给出了一个估计值_年代h［，以防止分析人员生成的函数与抵制集过拟合。换句话说，反应Thresholdout都是为了确保，极有可能，_年代h［接近于P［的估计_年代h［给出了对真实期望的估计P［］．给定一个函数，Thresholdout首先检查平均值之间的差值在训练现场年代_t(或_年代t［])和坚持集上的平均值年代_h(或_年代h［])低于某个阈值T+。在这里,T是一个固定的数字，如0.01，是一个拉普拉斯噪声变量，其标准差需要根据所需的保证选择。如果差值低于阈值，则算法返回_年代t［］．如果差值高于阈值，则算法返回_年代h［) +为另一个拉普拉斯噪声变量．每次差异超过“过拟合”预算的阈值B减1。一旦它耗尽，Thresholdout停止回答查询。在图1的伪代码Thresholdout．

我们现在声明形式化的泛化保证了的整个执行Thresholdout享受。它们是基于参考文献第3章给出的“稀疏向量”技术的隐私保证。¹²以及差分隐私的泛化性质。对于纯粹的微分隐私，我们依赖定理4，对于(，)-差分隐私我们使用Ref中的绑定。²¹

定理9。让,> 0和m B> 0。我们组T= 3/4而且= / (96 ln (4米/))。让年代表示从分布P和S中绘制的大小为n的坚持数据集_t任何额外的数据集都要结束。考虑一个被赋予访问S的算法_t自适应选择函数₁……_米而互动Thresholdout哪个是给定的数据集年代,年代_t值，B, t，对于每一个i［米),让一个_我表示的答案Thresholdout在函数_我：[0,1]。此外，对于每一个i［米),我们定义过拟合的计数器

然后

当n n₀为

注意在上的界n,这个术语是否等于(在一个常数因子以内)需要回答的样本数量m发生不带着宽容和自信选择问题．更进一步，这个界限允许米指数大:在n只要Bsubquadratically生长在n(即,Bn^2摄氏度为一个常数c> 0)。

我们注意到，同样的方法也适用于低灵敏度查询类。在裁判,¹⁰我们还给出了该算法的一个无可比拟的版本，其保证来自描述长度参数，而不是来自差异隐私。该变体的优点是它的使用不局限于低灵敏度查询。

4.1.演示实验

我们描述了一个关于合成数据的简单实验，它说明了重用标准拒接集的危险，以及如何通过我们的可重用拒接来解决这个问题。在我们的实验中，分析人员希望通过以下通用策略来构建一个分类器。首先，分析人员找到一组与类标签相关的单一属性。然后，分析人员将相关变量聚集到一个精度更高的单一模型中(例如，使用boost或bagging方法)。更正式地说，分析师会得到一个d-维标记数据集年代大小2n然后随机分成一个训练集年代_t还有一组顽固不化的年代_h相同的大小。的元素年代通过元组(x, y),x是一个d维向量和y{1,1}是对应的类标签。分析师希望选择要包含在她的分类器中的变量。对于不同值的变量数量进行选择k,她选择k变量与标签的绝对相关性最大。然而，她验证了抵制集上的相关性(用标签)，并只使用那些相关性在符号上与训练集上的相关性一致的变量，并且这两个相关性在绝对值上都大于某个阈值。然后，她只使用所选变量的相关性符号，在所选变量上创建一个简单的线性阈值分类器。最后一个测试评估分类器在训练集和保留集上的分类精度。

在实验中，我们使用的实现Thresholdout这与我们在理论上分析的算法有些不同图1)．具体来说，我们把参数设为T= 0.04,= 0.01。这低于证明所需的值(并且不打算直接应用)，但足以防止在我们的实验中过拟合。其次，我们使用高斯噪声而不是拉普拉斯噪声，因为它具有更强的集中特性(在许多差分隐私应用中，基于高斯噪声的机制具有类似的理论保证，但我们的不是这样)。

标签和数据之间没有相关性。在我们的第一个实验中，每个属性都独立于正态分布N(0,1)，我们选择类标签y{1,1}是一致随机的，因此数据点与其标签之间没有相关性。我们选择n= 10000,d= 10,000，并改变所选变量的数量k．在这种情况下，任何分类器都不能达到50%以上的真实准确率。尽管如此，重用一个标准拒绝结果报告的准确性超过63%k训练集和抵制集上均为= 500(误差的标准差小于0.5%)。从100次独立的实验执行中得到的结果的平均值和标准差绘制在图2这也包括分类器在另一个大小的新数据集上的准确性n从相同的分布中抽取。然后，我们使用可重用拒绝执行相同的算法。该算法Thresholdout调用了T= 0.04,= 0.01解释为什么分类器报告的准确性Thresholdout如果坚持值集上的精度与训练集上的精度相差0.04，则误差可达0.04。Thresholdout防止算法过拟合到保留集，并给出分类器精度的有效估计。

标签和一些变量之间的高度相关性。在我们的第二个实验中，类标签与一些变量相关。和前面一样，标签是从{1,1}中随机选择的，每个属性都是从其中绘制的N(0,1)除了从其中提取的20个属性N（y·0.06,1)其中y是类标签。我们对这些数据执行相同的算法，包括标准抵制和Thresholdout把结果画出来图3．实验结果表明，在使用可重用保留条件的情况下，该算法在避免过拟合的同时，仍能找到较好的分类器。这说明了可重用延迟同时防止过拟合，并允许发现真正的统计模式。

致谢

我们要感谢S. Arora、M.F. Balcan、A. Blum、D. Foster、M. Kearns、J. Kleinberg、A. Rakhlin、P. Rigollet、W. Su和J. Ullman对这项工作的启发性讨论。我们还要感谢伯克利的西蒙斯理论计算机科学研究所，在那里完成了部分研究。这项工作由阿尔弗雷德·斯隆基金会和美国国家科学基金会资助CNS 1253345。

回到顶部

回到顶部

回到顶部

回到顶部

回到顶部

数字图书馆是由计算机协会出版的。版权所有©2017 ACM, Inc.

---

没有发现记录