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

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

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

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

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

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

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

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

在這項(xiàng)工作中蹄梢，我們描述了一種通用的方法，連同一個(gè)具體的實(shí)例化來重新使用holdout集富俄，同時(shí)保留了新鮮數(shù)據(jù)的統(tǒng)計(jì)學(xué)上的保證禁炒。分析者可以不受約束地訪問訓(xùn)練數(shù)據(jù)集，但只能通過一種算法（或者說是機(jī)制）訪問holdout集霍比，這種算法允許分析者驗(yàn)證holdout的統(tǒng)計(jì)信息幕袱。通過這種機(jī)制，分析人員可以自由的挖掘（訓(xùn)練）數(shù)據(jù)悠瞬，生成和計(jì)算出統(tǒng)計(jì)信息们豌，在holdout上驗(yàn)證這些統(tǒng)計(jì)信息，并重復(fù)此過程浅妆，也能與其它使用相同holdout的分析者分享這些輸出信息望迎。

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

簡(jiǎn)而言之玻淑，可重用的抵抗機(jī)制很簡(jiǎn)單：通過差分隱私機(jī)制訪問holdout。直覺是呀伙，如果我們可以從宏觀上去了解一個(gè)數(shù)據(jù)集补履，同時(shí)盡可能的降低單個(gè)數(shù)據(jù)元素對(duì)整體的影響，那么我們可以控制信息的泄露剿另，從而防止過度擬合箫锤。更具體地說贬蛙，我們引入了一個(gè)關(guān)于控制過擬合的最大信息的新概念，并且可以使用差異隱私來限制（概述谚攒，參見[17]的第1節(jié)）阳准。我們提出了一個(gè)稱為Thresholdout的可重用holdout的實(shí)現(xiàn)，并表明它可以驗(yàn)證大量的自適應(yīng)選擇統(tǒng)計(jì)馏臭。然后野蝇，我們?cè)诤铣傻臄?shù)據(jù)上使用了一個(gè)簡(jiǎn)單的分類算法，來說明Thresholdout的性能括儒。當(dāng)我們單純的重用holdout時(shí)會(huì)過擬合绕沈，但使用可重用holdout時(shí)就不會(huì)過擬合。

我們?cè)跇?biāo)準(zhǔn)集上操作時(shí)：給分析者一個(gè)具有n個(gè)樣本的數(shù)據(jù)集S = (x1, x2, …, xn)帮寻，這n個(gè)樣本隨機(jī)地獨(dú)立地從未知分布P中提取乍狐，P在可能的數(shù)據(jù)點(diǎn)的離散域X上。盡管我們的方法的應(yīng)用場(chǎng)景更為廣泛固逗，我們?cè)诖岁P(guān)注于驗(yàn)證統(tǒng)計(jì)信息方面澜躺，這些統(tǒng)計(jì)信息可以表示為任意函數(shù)f的平均值，f：X -> [0, 1]在數(shù)據(jù)集ES上抒蚜，ES[f] = 1/n∑f(xi)（更多細(xì)節(jié)請(qǐng)見[17]的1.1）掘鄙。這種統(tǒng)計(jì)信息被用于估計(jì)f在一個(gè)樣本上的期望值，該樣本從分布P[f] =Ex~P[f(x)]上隨機(jī)提取嗡髓。數(shù)據(jù)分析中各種數(shù)量的interest可以表達(dá)為P上函數(shù)f期望值Ex~P[f(x)]操漠。樣本中包括真實(shí)的均值和個(gè)別屬性的矩，屬性之間的相關(guān)度和預(yù)測(cè)模型的泛化誤差饿这。此外浊伙，對(duì)這些期望的足夠精確估計(jì)足以進(jìn)行模型選擇和評(píng)估。

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

對(duì)于給定的函數(shù)f，該算法首先檢查f在St和Sh的均值（ESt[f]和ESh[f]）的差是不是低于一個(gè)確定的閾值T +η挥萌，T是一個(gè)固定的值绰姻，比如說0.01，η是標(biāo)準(zhǔn)差小于T的拉普拉斯噪聲變量引瀑，by a small factor such as 4（拉普拉斯分布是一個(gè)對(duì)稱的指數(shù)分布狂芋，添加拉普拉斯噪聲是差分隱私中的一個(gè)基本步驟[13]）。如果差值在閾值之內(nèi)憨栽，算法返回ESt[f]帜矾；這意味著，f的值來源于訓(xùn)練集屑柔。如果差值超過了閾值屡萤，算法返回holdout的平均值加上拉普拉斯噪聲，就是ESh[f] +ξ（ξ是拉普拉斯分布的隨機(jī)變量）掸宛。

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

我們?cè)诤铣蓴?shù)據(jù)集上描述了一個(gè)簡(jiǎn)單的實(shí)驗(yàn)，闡述了在標(biāo)準(zhǔn)holdout集上重用的危險(xiǎn)性是晨，并給出了這些問題在我們的可重用holdout集上的解決方法肚菠。該實(shí)驗(yàn)的設(shè)計(jì)靈感來源于Freedman經(jīng)典實(shí)驗(yàn)，它證明了在相同數(shù)據(jù)上進(jìn)行變量選擇和回歸的危險(xiǎn)[18]罩缴。由于對(duì)結(jié)果的有效性產(chǎn)生驚人的強(qiáng)烈影響蚊逢，所以實(shí)驗(yàn)通常被稱為“Freedman悖論”层扶。

在我們的實(shí)驗(yàn)中，分析者想要通過一般的策略建立分類器烙荷。首先镜会，分析者找到一個(gè)與類別標(biāo)簽相關(guān)的單個(gè)屬性的集合。然后將相關(guān)變量聚合成一個(gè)高精度的模型（例如使用Boosting或者Bagging方法）终抽。更正式地說戳表，分析者給出大小為2n的d維標(biāo)記數(shù)據(jù)集S，并將其隨機(jī)分成大小相同的分成訓(xùn)練集St和holdout集Sh昼伴。我們使用元組（x, y）標(biāo)記S中的元素匾旭，x是d維向量，y是對(duì)應(yīng)的標(biāo)簽圃郊，y∈{-1, 1}价涝。分析者希望選擇的變量被包含在分類器中。對(duì)于被選擇的變量的數(shù)量k的值持舆，分析者選擇與標(biāo)簽具有最大絕對(duì)相關(guān)度的k個(gè)變量色瘩。然而，分析者帶著標(biāo)簽在holdout上驗(yàn)證相關(guān)度逸寓，僅使用那些相關(guān)度與訓(xùn)練集上的相關(guān)度在符號(hào)上相符合的變量居兆，且兩個(gè)相關(guān)度都在絕對(duì)值上大于閾值。然后竹伸，分析人員使用所選變量的相關(guān)符號(hào)史辙，在所選變量上創(chuàng)建一個(gè)簡(jiǎn)單的線性閾值分類器。最后在holdout上測(cè)試分類器的準(zhǔn)確度佩伤。分析者所使用的算法的具體細(xì)節(jié)見[17]的第三部分聊倔。

在我們的第一個(gè)實(shí)驗(yàn)中，每個(gè)屬性都從N(0,1)正態(tài)分布中獨(dú)立地提取生巡，隨機(jī)地均勻地選擇類別標(biāo)簽y∈{-1, 1}耙蔑，使數(shù)據(jù)點(diǎn)和標(biāo)簽之間不相關(guān)。我們令n=10000孤荣，d=10000甸陌，改變變量的數(shù)量k的值。在該方案中沒有分類器能真正達(dá)到50%的準(zhǔn)確率盐股。不過钱豁，在k=500的時(shí)候，重用一個(gè)標(biāo)準(zhǔn)的holdout結(jié)果疯汁，在訓(xùn)練集和holdout集上都達(dá)到了63±0.4%以上的準(zhǔn)確率牲尺。100次獨(dú)立實(shí)驗(yàn)的結(jié)果的均值和標(biāo)準(zhǔn)差繪制在圖1A中，同時(shí)包含了分類器在新數(shù)據(jù)上的準(zhǔn)確率，新數(shù)據(jù)的大小為n谤碳，從桐鄉(xiāng)的分布中提取溃卡。然后我們?cè)诳芍赜胔oldout集上執(zhí)行同樣的分類算法。Thresholdout中的T=0.04蜒简，t=0.01瘸羡，這就解釋了當(dāng)holdout集上的準(zhǔn)確率在訓(xùn)練集準(zhǔn)確率的0.04以內(nèi)時(shí)，不使用Thresholdout的分類器的準(zhǔn)確度只到0.04搓茬。Thresholdout防止了算法在holdout上過擬合犹赖，并給出了分類器準(zhǔn)確率的有效估計(jì)。在圖1B中卷仑，我們繪制了Thresholdout報(bào)告的分類器的準(zhǔn)確率峻村。在圖S2中我們繪制了給出的分類器在holdout集上的真實(shí)準(zhǔn)確率。

在第二個(gè)實(shí)驗(yàn)中系枪，類別標(biāo)簽與一些變量相關(guān)雀哨。先前磕谅，標(biāo)簽已經(jīng)隨機(jī)地從{1, -1}中選取私爷，除了有20個(gè)屬性從N(y*0.06,1)中選取之外（y是類別標(biāo)簽），其他屬性都從N(0,1)中選取膊夹。我們?cè)谶@些數(shù)據(jù)上執(zhí)行同樣的算法衬浑，同樣使用標(biāo)準(zhǔn)holdout和Thresholdout，實(shí)驗(yàn)結(jié)果繪制在圖2中放刨。我們的實(shí)驗(yàn)說明了工秩，在使用了可重用holdout后，在不降低分類器準(zhǔn)確率的情況下防止了過擬合进统。

我們的實(shí)驗(yàn)里助币，使用標(biāo)準(zhǔn)holdout時(shí)會(huì)發(fā)生過擬合的原因是分析者在使用holdout測(cè)量完單個(gè)屬性的相關(guān)度之后重用了holdout。我們首先注意到螟碎，無論交叉驗(yàn)證還是自舉（bootstrap）都不能解決這個(gè)問題眉菱。如果我們使用這些方法中的任一種來驗(yàn)證相關(guān)性，則由于使用相同的數(shù)據(jù)進(jìn)行訓(xùn)練和驗(yàn)證（使用最終的分類器）掉分，過度擬合仍然會(huì)出現(xiàn)俭缓。我們根據(jù)實(shí)驗(yàn)的具體問題，完全可以推薦其他解決方案酥郭。事實(shí)上华坦，統(tǒng)計(jì)文獻(xiàn)中有相當(dāng)多的使用了固定兩步過程的方法去解決，其中第一步是變量選擇（具體例子參見[5]）不从。我們的實(shí)驗(yàn)表明惜姐，即使這樣簡(jiǎn)單和標(biāo)準(zhǔn)地去處理，我們的方法也避免了誤發(fā)現(xiàn)椿息，不需要使用專門的步驟载弄，當(dāng)然耘拇，它的擴(kuò)展可以更廣泛。更重要的是宇攻，可重用holdout給分析者提供了一種一般性的條理化的方法去執(zhí)行更多的驗(yàn)證步驟惫叛，此前唯一安全的方法每當(dāng)一個(gè)函數(shù)依賴于先前的結(jié)果時(shí)刷新holdout集。

參考文獻(xiàn)

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).