寫在前面：這是我看到的第一篇發(fā)在《science》上的文章，將近年來比較火的差分隱私用在解決過機器學習中的過擬合上，效果很棒。這是15年的文章，現(xiàn)在已經(jīng)17年了，網(wǎng)上居然沒有中文翻譯，我就粗略的翻譯一下給后來者有個參考。這里面有個很重要的名詞holdout，因為不好翻譯我就沒翻譯，大概意思是，將原始數(shù)據(jù)或分為兩部分，一部分做訓練集，剩下小部分作為用來驗證準確率的holdout集，兩個集合內(nèi)容不交叉，這樣驗證出來的結(jié)果更真實。以下是翻譯全文：

可重用的holdout：保護自適應(yīng)數(shù)據(jù)分析中的正確性

摘要：統(tǒng)計數(shù)據(jù)分析的錯誤應(yīng)用是科學研究中造成虛假發(fā)現(xiàn)的常見原因。確保從數(shù)據(jù)中得出的推論的有效性的現(xiàn)有方法是，在數(shù)據(jù)被檢查之前執(zhí)行一個固定的程序?qū)?shù)據(jù)進行選擇。然而，在通常的做法中，數(shù)據(jù)分析是一個本質(zhì)上適應(yīng)性的過程，在數(shù)據(jù)探尋的基礎(chǔ)上生成新的分析，以及以前對相同數(shù)據(jù)的分析結(jié)果。作為一個應(yīng)用，我們展示了如何安全地重用holdout集多次來驗證自適應(yīng)選擇的分析結(jié)果。

在整個科學界，越來越多的人認識到，在發(fā)表的研究中，統(tǒng)計學意義的聲稱往往是無效的。對這個問題的理解和提出解決辦法上，已經(jīng)做了大量的努力，主要集中在多重假設(shè)檢驗中控制虛假發(fā)現(xiàn)率的統(tǒng)計方法。然而，這個工作本身的統(tǒng)計學概念假設(shè)，在數(shù)據(jù)收集之前有一個固定的程序去選擇對數(shù)據(jù)進行選擇。相反，科學研究中的數(shù)據(jù)分析實踐是一個自適應(yīng)過程，新的分析是建立在數(shù)據(jù)探尋和以前對相同數(shù)據(jù)的分析之上的。

現(xiàn)在已經(jīng)很好地理解了，將分析調(diào)整到數(shù)據(jù)中會導致隱式多重比較問題，這一問題在標準統(tǒng)計程序的報告顯著性水平或現(xiàn)有的控制錯誤發(fā)現(xiàn)率的技術(shù)中沒有得到。這個問題，在某些情況下，被稱為“p值篡改”或“研究者的自由度”，是研究結(jié)果常常出錯的一種最主要的解釋。

傳統(tǒng)的自適應(yīng)性觀點使我們有必要明確地考慮所有可能的分析方法，為自適應(yīng)分析提供有效保證。雖然這種方法在簡單的研究中可能是可行的，但它在技術(shù)上具有挑戰(zhàn)性，在更復雜的分析中往往不切實際。統(tǒng)計學家開發(fā)了許多技術(shù)來解決常見的自適應(yīng)數(shù)據(jù)分析的特殊情況。大多數(shù)這些方法都集中在單輪適應(yīng)性上，例如可變選擇，然后根據(jù)選定的變量進行回歸，或者選擇模型后進行測試，并針對特定的推理程序進行優(yōu)化（文獻太廣泛，無法充分覆蓋這里，但參見文獻5中的章節(jié)7作為一個入口）。還有一個程序，用于在一個連續(xù)的設(shè)置中控制錯誤發(fā)現(xiàn)，其中測試逐個到達。然而，這些結(jié)果完全取決于所有測試保持其統(tǒng)計特性，盡管是順序選擇的——這種假設(shè)在復雜的自適應(yīng)分析中往往難以證明。

一種避免適應(yīng)性問題的方法是預注冊；也就是說，提前定義整個數(shù)據(jù)分析協(xié)議，從而迫使分析不適用。最近有一個公開信[9]，有超過80個簽署者要求科學預注冊。雖然這樣做是安全的，但是這個建議對于研究人員來說可能是沉重的，可能會限制他或她能夠執(zhí)行的分析方式[4]。結(jié)果，這種方法在實踐中很少被使用。用于避免這種類型的問題的更流行的方法是在holdout集合上驗證數(shù)據(jù)相關(guān)假設(shè)或統(tǒng)計信息。數(shù)據(jù)分析師首先將數(shù)據(jù)樣本隨機分為訓練數(shù)據(jù)和保留數(shù)據(jù)。分析人員與訓練集進行交互以獲得感興趣的數(shù)據(jù)統(tǒng)計量：例如，某些特征之間的相關(guān)度或預測模型的準確性。然后通過計算其在holdout集上的值來驗證統(tǒng)計量。由于holdout是獨立地從相同的數(shù)據(jù)分布中抽取的，因此可以安全地使用標準統(tǒng)計推理程序。

這種基本方法的一個主要缺點是，一般來說，holdout集不能重復使用。如果分析人員使用驗證結(jié)果來選擇其他數(shù)據(jù)統(tǒng)計量，該統(tǒng)計信息不再與holdout集獨立，并且進一步使用holdout進行驗證可能導致不正確的統(tǒng)計推斷。為了保持統(tǒng)計學有效性，目前唯一的安全方法是收集新數(shù)據(jù)去刷新holdout。但這種保守的方法成本很高，因此經(jīng)常被濫用，從而導致holdout過擬合。

在這項工作中，我們描述了一種通用的方法，連同一個具體的實例化來重新使用holdout集，同時保留了新鮮數(shù)據(jù)的統(tǒng)計學上的保證。分析者可以不受約束地訪問訓練數(shù)據(jù)集，但只能通過一種算法（或者說是機制）訪問holdout集，這種算法允許分析者驗證holdout的統(tǒng)計信息。通過這種機制，分析人員可以自由的挖掘（訓練）數(shù)據(jù)，生成和計算出統(tǒng)計信息，在holdout上驗證這些統(tǒng)計信息，并重復此過程，也能與其它使用相同holdout的分析者分享這些輸出信息。

我們的可重用的holdout方法背后的關(guān)鍵思想來自于差分隱私保護[13]。大致來說，差別隱私確保分析出的結(jié)果出現(xiàn)的概率基本上不變，這是通過修改數(shù)據(jù)集中單個元素做到的。這種情況通常被稱為穩(wěn)定性保證。一個重要的方法（line of work）確定了學習算法的穩(wěn)定性與其泛化能力之間的聯(lián)系[14-16]。已經(jīng)可以知道的是，穩(wěn)定性對于泛化是必要的和充分的。不幸的是，在這些以前的工作中考慮的穩(wěn)定性概念并沒有這么理解，運行多個穩(wěn)定的算法順序和自適應(yīng)，可能會導致一個程序是不穩(wěn)定的。差分隱私比以前研究的穩(wěn)定性概念更強大，特別是擁有強大的適應(yīng)性組合保證。

簡而言之，可重用的抵抗機制很簡單：通過差分隱私機制訪問holdout。直覺是，如果我們可以從宏觀上去了解一個數(shù)據(jù)集，同時盡可能的降低單個數(shù)據(jù)元素對整體的影響，那么我們可以控制信息的泄露，從而防止過度擬合。更具體地說，我們引入了一個關(guān)于控制過擬合的最大信息的新概念，并且可以使用差異隱私來限制（概述，參見[17]的第1節(jié)）。我們提出了一個稱為Thresholdout的可重用holdout的實現(xiàn)，并表明它可以驗證大量的自適應(yīng)選擇統(tǒng)計。然后，我們在合成的數(shù)據(jù)上使用了一個簡單的分類算法，來說明Thresholdout的性能。當我們單純的重用holdout時會過擬合，但使用可重用holdout時就不會過擬合。

我們在標準集上操作時：給分析者一個具有n個樣本的數(shù)據(jù)集S = (x1, x2, …, xn)，這n個樣本隨機地獨立地從未知分布P中提取，P在可能的數(shù)據(jù)點的離散域X上。盡管我們的方法的應(yīng)用場景更為廣泛，我們在此關(guān)注于驗證統(tǒng)計信息方面，這些統(tǒng)計信息可以表示為任意函數(shù)f的平均值，f：X -> [0, 1]在數(shù)據(jù)集ES上，ES[f] = 1/n∑f(xi)（更多細節(jié)請見[17]的1.1）。這種統(tǒng)計信息被用于估計f在一個樣本上的期望值，該樣本從分布P[f] =Ex~P[f(x)]上隨機提取。數(shù)據(jù)分析中各種數(shù)量的interest可以表達為P上函數(shù)f期望值Ex~P[f(x)]。樣本中包括真實的均值和個別屬性的矩，屬性之間的相關(guān)度和預測模型的泛化誤差。此外，對這些期望的足夠精確估計足以進行模型選擇和評估。

數(shù)據(jù)集S被隨機劃分為訓練集和holdout（分別用St和Sh表示），分析者可以自由的使用訓練集，并生成函數(shù)f來估計P的期望。分析者僅能通過Thresholdout得到Sh。Thresholdout將訓練集和holdout作為輸入，對分析者使用的所有函數(shù)，都對P上每個函數(shù)的期望提供統(tǒng)計上的有效估計。具體來說，對于一個足夠大的holdout，Theresholdout以1 -β的概率保證分析者提供的每個函數(shù)f：X -> [0, 1]都會返回一個值vf，|vf – P[f]|≤t，分析者可以設(shè)置誤差t和置信度β的值。概率空間覆蓋了St和Sh中數(shù)據(jù)元素的隨機選擇以及由機制所引入的自由度。我們強調(diào)的是，對于真實分布的估計是保證精確的，即使當函數(shù)是由分析人員順序和自適應(yīng)地生成的，直到大量函數(shù)。我們的算法可以等價地看作是，在自適應(yīng)選擇的線性泛函序列上產(chǎn)生保守的置信區(qū)間（關(guān)于與置信區(qū)間的正式連接的部分，見[17]第4節(jié)）。

對于給定的函數(shù)f，該算法首先檢查f在St和Sh的均值（ESt[f]和ESh[f]）的差是不是低于一個確定的閾值T +η，T是一個固定的值，比如說0.01，η是標準差小于T的拉普拉斯噪聲變量，by a small factor such as 4（拉普拉斯分布是一個對稱的指數(shù)分布，添加拉普拉斯噪聲是差分隱私中的一個基本步驟[13]）。如果差值在閾值之內(nèi)，算法返回ESt[f]；這意味著，f的值來源于訓練集。如果差值超過了閾值，算法返回holdout的平均值加上拉普拉斯噪聲，就是ESh[f] +ξ（ξ是拉普拉斯分布的隨機變量）。

盡管這個東西很簡單，但是Thresholdout令人驚訝的強的保證。通俗的說，這個保證是指對于任何固定的準確度參數(shù)t，Thresholdout都能繼續(xù)驗證訓練集上的估計值，直到函數(shù)請求的總數(shù)達到Sh的大小的指數(shù)大，或者驗證失敗的函數(shù)（這意味著Sh和St的均值的差超過噪聲的閾值）總數(shù)達到Sh的大小的平方。我們給出的保證因此可以解釋為：Thresholdout可以檢測到的在訓練集上過擬合（或者誤發(fā)現(xiàn)）的函數(shù)的數(shù)量是平方級的，并且是由于自適應(yīng)產(chǎn)生的；此外Thresholdout為這些函數(shù)的期望提供一個正確的估計。在[17]中的第二部分，我們描述了Thresholdout實現(xiàn)上的具體細節(jié)，并給出形式化的保證。

我們在合成數(shù)據(jù)集上描述了一個簡單的實驗，闡述了在標準holdout集上重用的危險性，并給出了這些問題在我們的可重用holdout集上的解決方法。該實驗的設(shè)計靈感來源于Freedman經(jīng)典實驗，它證明了在相同數(shù)據(jù)上進行變量選擇和回歸的危險[18]。由于對結(jié)果的有效性產(chǎn)生驚人的強烈影響，所以實驗通常被稱為“Freedman悖論”。

在我們的實驗中，分析者想要通過一般的策略建立分類器。首先，分析者找到一個與類別標簽相關(guān)的單個屬性的集合。然后將相關(guān)變量聚合成一個高精度的模型（例如使用Boosting或者Bagging方法）。更正式地說，分析者給出大小為2n的d維標記數(shù)據(jù)集S，并將其隨機分成大小相同的分成訓練集St和holdout集Sh。我們使用元組（x, y）標記S中的元素，x是d維向量，y是對應(yīng)的標簽，y∈{-1, 1}。分析者希望選擇的變量被包含在分類器中。對于被選擇的變量的數(shù)量k的值，分析者選擇與標簽具有最大絕對相關(guān)度的k個變量。然而，分析者帶著標簽在holdout上驗證相關(guān)度，僅使用那些相關(guān)度與訓練集上的相關(guān)度在符號上相符合的變量，且兩個相關(guān)度都在絕對值上大于閾值。然后，分析人員使用所選變量的相關(guān)符號，在所選變量上創(chuàng)建一個簡單的線性閾值分類器。最后在holdout上測試分類器的準確度。分析者所使用的算法的具體細節(jié)見[17]的第三部分。

在我們的第一個實驗中，每個屬性都從N(0,1)正態(tài)分布中獨立地提取，隨機地均勻地選擇類別標簽y∈{-1, 1}，使數(shù)據(jù)點和標簽之間不相關(guān)。我們令n=10000，d=10000，改變變量的數(shù)量k的值。在該方案中沒有分類器能真正達到50%的準確率。不過，在k=500的時候，重用一個標準的holdout結(jié)果，在訓練集和holdout集上都達到了63±0.4%以上的準確率。100次獨立實驗的結(jié)果的均值和標準差繪制在圖1A中，同時包含了分類器在新數(shù)據(jù)上的準確率，新數(shù)據(jù)的大小為n，從桐鄉(xiāng)的分布中提取。然后我們在可重用holdout集上執(zhí)行同樣的分類算法。Thresholdout中的T=0.04，t=0.01，這就解釋了當holdout集上的準確率在訓練集準確率的0.04以內(nèi)時，不使用Thresholdout的分類器的準確度只到0.04。Thresholdout防止了算法在holdout上過擬合，并給出了分類器準確率的有效估計。在圖1B中，我們繪制了Thresholdout報告的分類器的準確率。在圖S2中我們繪制了給出的分類器在holdout集上的真實準確率。

在第二個實驗中，類別標簽與一些變量相關(guān)。先前，標簽已經(jīng)隨機地從{1, -1}中選取，除了有20個屬性從N(y*0.06,1)中選取之外（y是類別標簽），其他屬性都從N(0,1)中選取。我們在這些數(shù)據(jù)上執(zhí)行同樣的算法，同樣使用標準holdout和Thresholdout，實驗結(jié)果繪制在圖2中。我們的實驗說明了，在使用了可重用holdout后，在不降低分類器準確率的情況下防止了過擬合。

我們的實驗里，使用標準holdout時會發(fā)生過擬合的原因是分析者在使用holdout測量完單個屬性的相關(guān)度之后重用了holdout。我們首先注意到，無論交叉驗證還是自舉（bootstrap）都不能解決這個問題。如果我們使用這些方法中的任一種來驗證相關(guān)性，則由于使用相同的數(shù)據(jù)進行訓練和驗證（使用最終的分類器），過度擬合仍然會出現(xiàn)。我們根據(jù)實驗的具體問題，完全可以推薦其他解決方案。事實上，統(tǒng)計文獻中有相當多的使用了固定兩步過程的方法去解決，其中第一步是變量選擇（具體例子參見[5]）。我們的實驗表明，即使這樣簡單和標準地去處理，我們的方法也避免了誤發(fā)現(xiàn)，不需要使用專門的步驟，當然，它的擴展可以更廣泛。更重要的是，可重用holdout給分析者提供了一種一般性的條理化的方法去執(zhí)行更多的驗證步驟，此前唯一安全的方法每當一個函數(shù)依賴于先前的結(jié)果時刷新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).