動機
樣本平均即使無偏,波動仍可能太大,無法支援可靠決策。基本的方差界只回答關於這種波動的一個問題。如果每次觀測都落在已知的有界區間內,便能利用這項更強的資訊,得到隨樣本數指數下降的概率界。這在預測程序比較多個候選時尤其重要:逐個候選各有保證,不代表看過分數後挑出的贏家也自動受到同樣保護。
假設用同一組訓練數據建立六十四個候選預測函數,再用另一組驗證數據比較它們的損失。在檢視驗證標籤之前,條件於訓練結果,候選構成一份固定清單;驗證結果則是隨機的。我們需要一個足夠強的結論,使它在選出表現最好的候選後仍然成立。有用的事件是:每個候選的驗證分數都同時接近其總體風險。
「偏差」也有兩個容易混淆的意思。它可以指函數族無法表示真實目標,也可以指訓練所得預測函數的平均偏離真實目標。兩者相關,但並不相同。本節會推導有限族的風險比較,以及偏差與方差分解,並逐一交代涉及的隨機性和損失。以下沒有任何定理宣稱:只因個別預測有界,任意的網絡函數族便已在統計上受控。
定義
設 為相互獨立的實值隨機變量,有共同均值 ,且每個都幾乎必然落在 內,其中 已知。這裏同分布足夠但不是必要條件。記 。集中不等式控制這個隨機平均偏離其均值達指定幅度的概率。
定義 10.1.1
(總體風險與驗證風險)
對預測規則 ,定義總體風險及驗證風險為
驗證觀測獨立同分布,並獨立於產生候選清單 的程序,其中 。每個候選的損失都落在 內,其中 是確定的上界。所有有限族的結論也可以改為條件於獨立訓練數據來理解。它們不要求不同候選在同一觀測上的損失相互獨立。
定義 10.1.2
(近似經驗最小化函數)
近似經驗最小化函數 屬於該清單,並滿足 ,其中 。這個容許量衡量驗證準則未完全優化的程度,不包括利用驗證標籤構造清單以外的新候選所造成的相依性。
定義 10.1.3
(訓練平均預測函數)
在平方誤差預測中,記 。設隨機訓練數據 獨立於新的測試對 , 為擬合所得函數。其訓練平均預測為 。假設以下所需的聯合二階矩有限;條件均值及函數均在輸入概率為零的集合以外理解。
定理 / 命題
定理 10.1.4
(獨立有界平均具有指數集中界)
在上述有界及獨立假設下,對每個 ,
因此,當 時,以至少 的概率,固定清單的所有成員同時滿足
在同一事件上,。若概率上界大於一,總可以改用一。
定理 10.1.5
(訓練隨機性分成平方偏差與方差)
設 ,且訓練數據與測試數據獨立。則
三項分別是條件雜訊、訓練平均預測函數的平方偏差,以及跨訓練樣本的變動。此恆等式不表示任何特定訓練程序會使其中一項最小。
證明思路
證明
(指數矩與 Markov 不等式)
先證明推動第一個定理的指數矩事實。若 ,令 。有界性容許對每個實數 在期望內微分。二階導數是 在指數傾斜概率律下的方差。在任何支撐於這個區間的概率律下,方差至多為 :由不等式 得到方差上界 ,其最大值正是所述數值。由於 ,把二階導數的上界積分兩次,得到
對正的 ,使用 Markov 不等式,並以獨立性把各觀測的上界相乘,得到上尾概率界 。使它最小的值是 。對負方向的偏差作同樣論證,再把兩個概率相加,便證得雙邊不等式,不需要正態近似或估計的標準差。
證明透視
為甚麼一個方差界能控制所有指數矩
決定性的觀察是:方差界 對 上的每個概率分布都成立,所以能同時用於每個指數傾斜後的分布;有界性只在這裏使用。 的這個一致上界,連同 ,積分後給出對數矩的二次上界 。獨立性只用來把 個矩界相乘。接著選取自由參數 使 Markov 界最小,從而得到指數中的因子 。單有有限方差只在 處控制 ,不能沿整個傾斜控制它。
證明
(對固定清單使用聯集界)
先對一個固定候選的驗證損失應用該不等式,再對全部 個候選使用聯集界。任何候選違反容許差距的概率至多為 。選取定理中的容許值,便使這個概率至多為 。一旦所有候選同時受控,所選指標可以依賴每一個驗證結果:同一事件已經涵蓋該指標。證明需要的是觀測獨立,而不是模型獨立。
在這個事件上,把選定規則與清單中任一成員比較:由總體風險轉到驗證風險,付出 ;利用近似最小化,付出 ;再回到總體風險,又付出 。對比較對象取最小值,便得到風險不等式。相對於理想風險 ,差 是另一項近似誤差。因此表示能力、統計比較和不完美擬合各自貢獻不同的量。
若候選因以較早的樣本訓練而是隨機的,先條件於整個該樣本。對每份實現的候選清單,獨立驗證數據上的失敗概率至多為同一選定水平。把這個條件概率對訓練隨機性取平均,界仍然成立。因此各候選共用一組訓練數據在這裏無害;但容許驗證標籤改變產生候選的程序,則是另一回事。獨立樣本提供了證明所需的分隔。
證明透視
獨立性在哪裏用到,在哪裏沒有用到
獨立性只在指數矩一步用到一次:驗證觀測相互獨立,總和的矩母函數才可分解為乘積。對候選函數則毫無假設,它們在同一觀測上的損失可以高度相關。聯集界完全不需要獨立性;它把 個失敗事件當作互不相交,代價是因子 。
不明顯之處在於量詞的次序。對每個固定指標 成立的界,對看過分數後才選出的隨機指標毫無說明;而對所有 同時成立的事件,包含最終選出的任何指標。在看驗證標籤之前固定清單,正是使 成為固定數的假設;自適應搜尋則須把 換成它可能產生的全部函數。風險不等式中的 記錄了在總體風險與驗證風險之間來回跨越兩次。
證明
(先條件於訓練樣本)
對第二個定理,先條件於 ,對新的測試對應用條件均值的風險恆等式。再寫 。對訓練數據取平均時,因 ,交叉項消失。平方可積性保證乘積及交換平均次序合法。這個證明也說明,為何依賴訓練數據的測試反應不能簡單地當作新的雜訊。
這個分解比較隨機訓練預測函數的期望風險與其訓練平均函數的風險:前者比後者多出整合後的訓練方差。但這不代表平均函數可以直接取得:要精確計算它,須對所有可能訓練集的分布取平均。把多個擬合預測函數取平均有時能近似這個想法,但能消除多少變動取決於它們之間的相關性。恆等式本身並不假設實際得到的一批擬合預測函數相互獨立。
例題詳解
例題 10.1.6
(利用有界範圍估計比例)
對獨立的 Bernoulli 觀測,區間長度為一。要使樣本比例絕對誤差至少 的概率不超過 ,只需要求 。向上取整得 738 個觀測。先前只用方差的不等式給出保守的一致要求 2000。較強的結論使用了有界性,但它仍是充分條件,而非必要樣本數。兩項計算都不能在檢視一個樣本後證明其實際誤差。
例題 10.1.7
(在六十四個獨立訓練的候選中選擇)
設驗證損失落在 ,,,。則 。精確的經驗選擇,其總體風險在概率至少 的事件上,至多為最佳候選風險加約 。若容許優化誤差 ,該超額上界增至約 。
候選可共享訓練觀測、特徵或架構。只要整份清單在接觸獨立驗證標籤之前已經固定,這並不影響上述條件論證。相反,看過這些標籤後反覆發明新的候選,會改變受控的清單。有效的分析必須把這個較大的選擇程序納入,或保留另一個獨立樣本。
例題 10.1.8
(有偏估計可能有較低預測風險)
設反應為成功概率 的 Bernoulli 變量,從 個獨立訓練反應擬合常數預測。考慮 ,其中 固定。它相對於 的平方偏差為 ,訓練方差為 。新反應的風險再加上不可消除的雜訊 。
當 、 時,樣本平均的估計誤差為 。取 ,平方偏差為 、方差為 ,合計 。因此新反應的預測風險分別為 及 。在這個分布下,有偏規則較好。然而當 時,樣本平均完全準確,同一有偏規則的估計誤差卻是 。這只是一個比較,並非普遍支持收縮。
常見錯誤
有限方差不代表有界範圍,所以不能據此使用剛證明的指數界。罕見而極大的損失可以有有限方差,同時違反任何設想中較小的確定範圍。證明在方差一步使用了有界性,方差假設不能取代它。
反例模式
有限方差不能給出有界區間的指數
斷言:對方差為 的獨立觀測,把 換成 (具相同方差的兩點分布之寬度平方)後不等式仍成立。取 ,令 以各 的概率取 或 ,其餘取 。則 、,而 。斷言在 給出 ,約 ,遠小於實際概率。若用正確區間 ,定理給出 ,雖平凡但正確。指數部分只含方差的界需要本節沒有證明的額外假設。
常見錯誤
(只限制預測而不限制反應)
對平方損失,若反應及每個預測都限制在 內,便得到有效範圍 。若反應仍然無界,只限制預測並不能限制平方損失。
常見錯誤
(只計算自適應搜尋最後留下的模型)
有限清單與按驗證標籤擬合的函數類是不同的對象。只計算最後的少數模型,沒有計入自適應搜尋中檢視過的每一種可能。同樣,在這個論證中,訓練分數不能代替獨立的驗證分數。證明的目標是:對一個獨立於評估樣本而固定的函數族,得到同時成立的事件。
函數類的有限網,或 Rademacher 複雜度,取代對固定清單的聯集。
自然延伸的下一個問題
對無限函數類,甚麼取代 M 的對數?
函數類的有限網,或 Rademacher 複雜度,取代對固定清單的聯集。
聯集界付出 的代價,對有無限多個成員的參數族毫無用處。若損失對有界集合中的參數 Lipschitz 連續,該集合的有限網便可充當清單,代價是一個離散化誤差。另一種做法是透過函數類的 Rademacher 複雜度,估計整個類別上最大偏差的期望。本章其後的筆記會發展這兩條路線。
常見錯誤
(把近似誤差與平方偏差混為一談)
偏差與方差的說法必須指明估計量及其隨機性。近似誤差關乎函數族中可得的最佳函數;平方偏差關乎某個特定訓練程序所產生的平均函數。即使函數族包含真實目標,該程序仍可能引入偏差。擴大函數族可能降低族內最佳誤差,同時增加擬合規則的變動。
總結
已知有界性把平均誤差的控制加強為指數概率不等式。有限聯集界使保證在固定清單中選擇後仍然成立。所得的風險比較分開族內最佳風險、估計容許量與擬合容許量。對平方損失,再對獨立訓練樣本取平均,可進一步分開條件雜訊、平方偏差與訓練方差。每個結論都取決於其所述的數據切分及概率模型。
練習
快速檢查
(十六個獨立於驗證而固定的候選,其損失都在 內。按定理, 須多大才能以至少 的概率保證所有風險差距同時不超過 ?給出精確的對數式及一個整數。)
解答 · 答案
解 得 。這約為 ,所以 1615 個觀測足夠。有界性及獨立驗證的假設是這個計算不可缺少的前提。
快速檢查
(對 的 Bernoulli 訓練數據,比較 與 的平方估計誤差。這個逐點比較能否找出對每個 都最好的估計量?)
解答 · 答案
在 處兩個規則都無偏。它們的估計誤差分別為 及 ,所以較小的 在這個比較中較好。在 處,樣本平均誤差為零,而任何 都有正的平方偏差。因此在單一分布上的結論,不能給出對所有 Bernoulli 分布的一致支配。
快速檢查
(設 ,且每個候選預測都在 內。求平方損失的有效上界 。若候選清單的最佳風險比理想風險高 ,一致差距容許量為 ,擬合容許量為 ,求所得的超額風險界。)
解答 · 答案
反應與預測之差的絕對值最大為五,所以 有效;損失非負。在同時成立的事件上,相對於理想風險的超額風險至多為 。比對稱共同界捷徑更精細的範圍是合法的,因為它直接由所述反應及預測區間得出。
快速檢查
(解釋為何零訓練誤差不會觸發有限清單定理。給出一個具體分布,以及一個訓練誤差為零、但總體平方風險為一的訓練相依函數。)
解答 · 答案
令 在 上均勻分布,。對有限的已實現訓練輸入集,定義預測函數在這些點上為零、其他位置為一。它可測,訓練損失為零,而總體風險為一,因為新的連續輸入命中該有限集的概率為零。這個預測函數由被評估的觀測構造,所有可能的這類函數所成的集合,也不是定理中那份獨立固定的有限清單。