写在前面：这是我看到的第一篇发在《science》上的文章，将近年来比较火的差分隐私用在解决过机器学习中的过拟合上，效果很棒。这是15年的文章，现在已经17年了，网上居然没有中文翻译，我就粗略的翻译一下给后来者有个参考。这里面有个很重要的名词holdout，因为不好翻译我就没翻译，大概意思是，将原始数据或分为两部分，一部分做训练集，剩下小部分作为用来验证准确率的holdout集，两个集合内容不交叉，这样验证出来的结果更真实。以下是翻译全文：

可重用的holdout：保护自适应数据分析中的正确性

摘要：统计数据分析的错误应用是科学研究中造成虚假发现的常见原因。确保从数据中得出的推论的有效性的现有方法是，在数据被检查之前执行一个固定的程序对数据进行选择。然而，在通常的做法中，数据分析是一个本质上适应性的过程，在数据探寻的基础上生成新的分析，以及以前对相同数据的分析结果。作为一个应用，我们展示了如何安全地重用holdout集多次来验证自适应选择的分析结果。

在整个科学界，越来越多的人认识到，在发表的研究中，统计学意义的声称往往是无效的。对这个问题的理解和提出解决办法上，已经做了大量的努力，主要集中在多重假设检验中控制虚假发现率的统计方法。然而，这个工作本身的统计学概念假设，在数据收集之前有一个固定的程序去选择对数据进行选择。相反，科学研究中的数据分析实践是一个自适应过程，新的分析是建立在数据探寻和以前对相同数据的分析之上的。

现在已经很好地理解了，将分析调整到数据中会导致隐式多重比较问题，这一问题在标准统计程序的报告显著性水平或现有的控制错误发现率的技术中没有得到。这个问题，在某些情况下，被称为“p值篡改”或“研究者的自由度”，是研究结果常常出错的一种最主要的解释。

传统的自适应性观点使我们有必要明确地考虑所有可能的分析方法，为自适应分析提供有效保证。虽然这种方法在简单的研究中可能是可行的，但它在技术上具有挑战性，在更复杂的分析中往往不切实际。统计学家开发了许多技术来解决常见的自适应数据分析的特殊情况。大多数这些方法都集中在单轮适应性上，例如可变选择，然后根据选定的变量进行回归，或者选择模型后进行测试，并针对特定的推理程序进行优化（文献太广泛，无法充分覆盖这里，但参见文献5中的章节7作为一个入口）。还有一个程序，用于在一个连续的设置中控制错误发现，其中测试逐个到达。然而，这些结果完全取决于所有测试保持其统计特性，尽管是顺序选择的——这种假设在复杂的自适应分析中往往难以证明。

一种避免适应性问题的方法是预注册；也就是说，提前定义整个数据分析协议，从而迫使分析不适用。最近有一个公开信[9]，有超过80个签署者要求科学预注册。虽然这样做是安全的，但是这个建议对于研究人员来说可能是沉重的，可能会限制他或她能够执行的分析方式[4]。结果，这种方法在实践中很少被使用。用于避免这种类型的问题的更流行的方法是在holdout集合上验证数据相关假设或统计信息。数据分析师首先将数据样本随机分为训练数据和保留数据。分析人员与训练集进行交互以获得感兴趣的数据统计量：例如，某些特征之间的相关度或预测模型的准确性。然后通过计算其在holdout集上的值来验证统计量。由于holdout是独立地从相同的数据分布中抽取的，因此可以安全地使用标准统计推理程序。

这种基本方法的一个主要缺点是，一般来说，holdout集不能重复使用。如果分析人员使用验证结果来选择其他数据统计量，该统计信息不再与holdout集独立，并且进一步使用holdout进行验证可能导致不正确的统计推断。为了保持统计学有效性，目前唯一的安全方法是收集新数据去刷新holdout。但这种保守的方法成本很高，因此经常被滥用，从而导致holdout过拟合。

在这项工作中，我们描述了一种通用的方法，连同一个具体的实例化来重新使用holdout集，同时保留了新鲜数据的统计学上的保证。分析者可以不受约束地访问训练数据集，但只能通过一种算法（或者说是机制）访问holdout集，这种算法允许分析者验证holdout的统计信息。通过这种机制，分析人员可以自由的挖掘（训练）数据，生成和计算出统计信息，在holdout上验证这些统计信息，并重复此过程，也能与其它使用相同holdout的分析者分享这些输出信息。

我们的可重用的holdout方法背后的关键思想来自于差分隐私保护[13]。大致来说，差别隐私确保分析出的结果出现的概率基本上不变，这是通过修改数据集中单个元素做到的。这种情况通常被称为稳定性保证。一个重要的方法（line of work）确定了学习算法的稳定性与其泛化能力之间的联系[14-16]。已经可以知道的是，稳定性对于泛化是必要的和充分的。不幸的是，在这些以前的工作中考虑的稳定性概念并没有这么理解，运行多个稳定的算法顺序和自适应，可能会导致一个程序是不稳定的。差分隐私比以前研究的稳定性概念更强大，特别是拥有强大的适应性组合保证。

简而言之，可重用的抵抗机制很简单：通过差分隐私机制访问holdout。直觉是，如果我们可以从宏观上去了解一个数据集，同时尽可能的降低单个数据元素对整体的影响，那么我们可以控制信息的泄露，从而防止过度拟合。更具体地说，我们引入了一个关于控制过拟合的最大信息的新概念，并且可以使用差异隐私来限制（概述，参见[17]的第1节）。我们提出了一个称为Thresholdout的可重用holdout的实现，并表明它可以验证大量的自适应选择统计。然后，我们在合成的数据上使用了一个简单的分类算法，来说明Thresholdout的性能。当我们单纯的重用holdout时会过拟合，但使用可重用holdout时就不会过拟合。

我们在标准集上操作时：给分析者一个具有n个样本的数据集S = (x1, x2, …, xn)，这n个样本随机地独立地从未知分布P中提取，P在可能的数据点的离散域X上。尽管我们的方法的应用场景更为广泛，我们在此关注于验证统计信息方面，这些统计信息可以表示为任意函数f的平均值，f：X -> [0, 1]在数据集ES上，ES[f] = 1/n∑f(xi)（更多细节请见[17]的1.1）。这种统计信息被用于估计f在一个样本上的期望值，该样本从分布P[f] =Ex~P[f(x)]上随机提取。数据分析中各种数量的interest可以表达为P上函数f期望值Ex~P[f(x)]。样本中包括真实的均值和个别属性的矩，属性之间的相关度和预测模型的泛化误差。此外，对这些期望的足够精确估计足以进行模型选择和评估。

数据集S被随机划分为训练集和holdout（分别用St和Sh表示），分析者可以自由的使用训练集，并生成函数f来估计P的期望。分析者仅能通过Thresholdout得到Sh。Thresholdout将训练集和holdout作为输入，对分析者使用的所有函数，都对P上每个函数的期望提供统计上的有效估计。具体来说，对于一个足够大的holdout，Theresholdout以1 -β的概率保证分析者提供的每个函数f：X -> [0, 1]都会返回一个值vf，|vf – P[f]|≤t，分析者可以设置误差t和置信度β的值。概率空间覆盖了St和Sh中数据元素的随机选择以及由机制所引入的自由度。我们强调的是，对于真实分布的估计是保证精确的，即使当函数是由分析人员顺序和自适应地生成的，直到大量函数。我们的算法可以等价地看作是，在自适应选择的线性泛函序列上产生保守的置信区间（关于与置信区间的正式连接的部分，见[17]第4节）。

对于给定的函数f，该算法首先检查f在St和Sh的均值（ESt[f]和ESh[f]）的差是不是低于一个确定的阈值T +η，T是一个固定的值，比如说0.01，η是标准差小于T的拉普拉斯噪声变量，by a small factor such as 4（拉普拉斯分布是一个对称的指数分布，添加拉普拉斯噪声是差分隐私中的一个基本步骤[13]）。如果差值在阈值之内，算法返回ESt[f]；这意味着，f的值来源于训练集。如果差值超过了阈值，算法返回holdout的平均值加上拉普拉斯噪声，就是ESh[f] +ξ（ξ是拉普拉斯分布的随机变量）。

尽管这个东西很简单，但是Thresholdout令人惊讶的强的保证。通俗的说，这个保证是指对于任何固定的准确度参数t，Thresholdout都能继续验证训练集上的估计值，直到函数请求的总数达到Sh的大小的指数大，或者验证失败的函数（这意味着Sh和St的均值的差超过噪声的阈值）总数达到Sh的大小的平方。我们给出的保证因此可以解释为：Thresholdout可以检测到的在训练集上过拟合（或者误发现）的函数的数量是平方级的，并且是由于自适应产生的；此外Thresholdout为这些函数的期望提供一个正确的估计。在[17]中的第二部分，我们描述了Thresholdout实现上的具体细节，并给出形式化的保证。

我们在合成数据集上描述了一个简单的实验，阐述了在标准holdout集上重用的危险性，并给出了这些问题在我们的可重用holdout集上的解决方法。该实验的设计灵感来源于Freedman经典实验，它证明了在相同数据上进行变量选择和回归的危险[18]。由于对结果的有效性产生惊人的强烈影响，所以实验通常被称为“Freedman悖论”。

在我们的实验中，分析者想要通过一般的策略建立分类器。首先，分析者找到一个与类别标签相关的单个属性的集合。然后将相关变量聚合成一个高精度的模型（例如使用Boosting或者Bagging方法）。更正式地说，分析者给出大小为2n的d维标记数据集S，并将其随机分成大小相同的分成训练集St和holdout集Sh。我们使用元组（x, y）标记S中的元素，x是d维向量，y是对应的标签，y∈{-1, 1}。分析者希望选择的变量被包含在分类器中。对于被选择的变量的数量k的值，分析者选择与标签具有最大绝对相关度的k个变量。然而，分析者带着标签在holdout上验证相关度，仅使用那些相关度与训练集上的相关度在符号上相符合的变量，且两个相关度都在绝对值上大于阈值。然后，分析人员使用所选变量的相关符号，在所选变量上创建一个简单的线性阈值分类器。最后在holdout上测试分类器的准确度。分析者所使用的算法的具体细节见[17]的第三部分。

在我们的第一个实验中，每个属性都从N(0,1)正态分布中独立地提取，随机地均匀地选择类别标签y∈{-1, 1}，使数据点和标签之间不相关。我们令n=10000，d=10000，改变变量的数量k的值。在该方案中没有分类器能真正达到50%的准确率。不过，在k=500的时候，重用一个标准的holdout结果，在训练集和holdout集上都达到了63±0.4%以上的准确率。100次独立实验的结果的均值和标准差绘制在图1A中，同时包含了分类器在新数据上的准确率，新数据的大小为n，从桐乡的分布中提取。然后我们在可重用holdout集上执行同样的分类算法。Thresholdout中的T=0.04，t=0.01，这就解释了当holdout集上的准确率在训练集准确率的0.04以内时，不使用Thresholdout的分类器的准确度只到0.04。Thresholdout防止了算法在holdout上过拟合，并给出了分类器准确率的有效估计。在图1B中，我们绘制了Thresholdout报告的分类器的准确率。在图S2中我们绘制了给出的分类器在holdout集上的真实准确率。

在第二个实验中，类别标签与一些变量相关。先前，标签已经随机地从{1, -1}中选取，除了有20个属性从N(y*0.06,1)中选取之外（y是类别标签），其他属性都从N(0,1)中选取。我们在这些数据上执行同样的算法，同样使用标准holdout和Thresholdout，实验结果绘制在图2中。我们的实验说明了，在使用了可重用holdout后，在不降低分类器准确率的情况下防止了过拟合。

我们的实验里，使用标准holdout时会发生过拟合的原因是分析者在使用holdout测量完单个属性的相关度之后重用了holdout。我们首先注意到，无论交叉验证还是自举（bootstrap）都不能解决这个问题。如果我们使用这些方法中的任一种来验证相关性，则由于使用相同的数据进行训练和验证（使用最终的分类器），过度拟合仍然会出现。我们根据实验的具体问题，完全可以推荐其他解决方案。事实上，统计文献中有相当多的使用了固定两步过程的方法去解决，其中第一步是变量选择（具体例子参见[5]）。我们的实验表明，即使这样简单和标准地去处理，我们的方法也避免了误发现，不需要使用专门的步骤，当然，它的扩展可以更广泛。更重要的是，可重用holdout给分析者提供了一种一般性的条理化的方法去执行更多的验证步骤，此前唯一安全的方法每当一个函数依赖于先前的结果时刷新holdout集。

参考文献

1. Y. Benjamini, Y. Hochberg, J. R. Stat.Soc. B 57, 289–300(1995).

2. J. P. A. Ioannidis, PLOS Med. 2, e124(2005).

3. J. P. Simmons, L. D. Nelson, U.Simonsohn, Psychol. Sci. 22, 1359–1366 (2011).

4. A. Gelman, E. Loken, Am. Stat. 102, 460(2014).

5. T. Hastie, R. Tibshirani, J. H.Friedman, The Elements of Statistical Learning: Data Mining, Inference, andPrediction (Springer Series in Statistics, Springer, New York, ed. 2, 2009).

6. D. Foster, R. Stine, J. R. Stat. Soc. B70, 429–444 (2008).

7. E. Aharoni, H. Neuvirth, S. Rosset,IEEE/ACM Trans. Comput. Biol. Bioinform. 8, 1431–1437 (2011).

8. A. Javanmard, A. Montanari, On online control of falsediscovery rate. http://arxiv.org/abs/1502.06197 (2015).

9. C. Chambers, M. Munafo, “Trust inscience would be improved by study pre-registration,” Guardian US, 5 June 2013;  www.theguardian.com/science/blog/2013/jun/05/trust-in-science-study-pre-registration.

10. J. Reunanen, J. Mach. Learn. Res. 3,1371–1382 (2003).

11. R. B. Rao, G. Fung, in Proceedings ofthe SIAM International Conference on Data Mining 2008 (Society for Industrialand Applied Mathematics, Philadelphia, PA, 2008), pp. 588–596.

12. G. C. Cawley, N. L. C. Talbot, J. Mach.Learn. Res. 11, 2079–2107 (2010).

13. C. Dwork, F. McSherry, K. Nissim, A.Smith, in Theory of Cryptography (Lecture Notes in Computer Science Series, Springer,Berlin, 2006), pp. 265–284.

14. O. Bousquet, A. Elisseeff, J. Mach.Learn. Res. 2, 499–526 (2002). 15. T. Poggio, R. Rifkin, S. Mukherjee, P.Niyogi, Nature 428, 419–422 (2004).

16. S. Shalev-Shwartz, O. Shamir, N.Srebro, K. Sridharan, J. Mach. Learn. Res. 11, 2635–2670 (2010).

17. Supplementary materials are availableon Science Online.

18. D. A. Freedman, Am. Stat. 37, 152–155(1983).