為甚麼無限函數族需要新的計數方法
一個連續參數便可代表無窮多個預測函數,例如 ,其中 。上一節對有限清單的聯集界不能直接代入 :所得概率界沒有用。不過,數值接近的常數預測通常有接近的損失。我們可以先用有限網格近似整個參數族,只在網格點上支付集中不等式的代價,再估計近似誤差。
這是一個具體的容量控制方法,依賴有界參數盒以及對損失的一致 Lipschitz 條件。高維時它可能給出很弱的界;不能僅憑參數數目就斷言任意神經網絡具有同樣的泛化保證。
定義與定理
定義 10.2.1
(有界且一致 Lipschitz 的損失族)
設 與新的觀測 同分布且相互獨立,。對每個 ,其中 、 為正整數,設損失 可測且屬於 ,。假設存在確定的 ,使每個 和任意 都滿足
定義總體風險 及經驗風險 。
上述條件使兩個風險函數均為 -Lipschitz,因而連續;盒子內可數稠密子集上的上確界已等於整個盒子上的上確界,所以以下隨機上確界可測。
網格網逐個座標構造。
引理 10.2.2
(參數盒的網格網)
對 令 。所有座標都屬於 的點組成網格 ,共有 點,而每個 都有網格點 使 。
證明
(座標等距分割)
把每個座標區間等分成 段,取全部端點。相鄰端點距離 ,整個網格 恰有 點。任意 都有網格鄰點 ,滿足 。此網格在抽樣之前確定。
有了網格網,集中不等式只需在其 個點上付出代價。
定理 10.2.3
(從參數網格得到一致界)
選取 與 ,令 、,並定義
以至少 的概率,同時對所有參數有
若可測的、允許依賴數據的 滿足 ,其中 ,則在同一事件上
由於風險在緊盒子上連續,兩個下確界實際上都能取到。證明也可先與任意參數比較,再取下確界。概率指的是樣本的隨機性,而不是在事件建立之後對參數的隨機選擇。
證明:先覆蓋,再選擇
證明
(先對網格用聯集界,再作 Lipschitz 轉移)
對固定網格點,上一節的有界均值集中界給出
對 個點使用聯集界,得到至少 的概率下所有網格誤差均不超過 。不同網格點的損失使用同一批樣本,無須彼此獨立。
在這個事件上,對任意參數用三角不等式和兩個 Lipschitz 界:
一個 用於移動總體風險,另一個用於移動經驗風險。同一個網格事件覆蓋所有參數,包括看過數據之後選出的參數。
對任意比較參數 ,依次使用一致界、近似最小化和一致界:
取下確界即得第二個結論。
證明透視
為何網格必須先固定,每個 Lr 從何而來
論證有嚴格的次序。網格 在抽樣之前選定,所以 是固定數,對 個固定點使用聯集界才合法。其後一切都是確定性的:在同一個網格事件上,由 轉移到 不涉及任何概率,因此對每個 同時成立,包括依賴數據的 。
轉移付出兩次 ,理由各不相同。移動總體風險時,對新的 平均 Lipschitz 界;移動經驗風險時,則在樣本點上使用它。兩者都只因該界對每個 成立而成立;兩者都與網格相配,因為 Lipschitz 條件與覆蓋使用同一個 距離。半徑 於是在最後的界中出現兩次:在 中及在 之內,這正是下面要考察的取捨。
它比較的是盒內最佳風險;如果理想預測函數不在這個族內,族內最佳風險與理想風險之差還要作為單獨的近似誤差加入。
例題:連續的常數預測
例題 10.2.4
(有界區間上的絕對損失)
設 幾乎處處成立,考慮所有常數預測 ,損失 屬於 。反三角不等式給出 ,故 、。取 、、,則網格有 點,且
因此任一精確經驗最小化解,以至少 的概率,其風險不超過最佳常數風險加約 。截斷到該區間的樣本中位數是這樣的解。這個分布無關的界是充分保證,並非說實際超額風險等於該數。
縮小 會降低近似項 ,卻增加 和集中項。固定 時取 ,所得界隨 趨於零。然而 ,大維度可能使界很弱。利用函數結構或數據分布的更精細覆蓋有可能改進結果,但需要另外證明。
例題 10.2.5
(選擇網格半徑)
保留絕對損失族,、;因 ,有 。下表列出 、 及四捨五入後的 。
每往下一行,近似項縮小十倍,而 只經 增長。界由 改善至 ,之後反而變差:在 ,多出的網格點在 上付出的代價超過在 上節省的。任何 都給出有效的界;選擇只影響它有多大資訊量。
例題 10.2.6
(邊界情況:十維中達到同樣精度)
設 、、、,則每個座標有 個網格值,。要使 ,定理要求 。當 ,此值為 ,所以 已足夠。當 ,,要求變成 。維數只經 以對數形式出現,但這個對數隨 線性增長,充分樣本數增大約 倍。
條件與反例
定理的每個假設都排除一種具體的失敗。
反例模式
單有有界損失不能控制不受限制的函數族
斷言:若每個損失都在 內,則經驗最小化解的總體風險接近最佳風險。設 在 上均勻分布、,允許所有從 到 的可測預測函數,並使用平方損失。對任意有限樣本,取函數在樣本輸入處為零、其他地方為一;其經驗風險為零,而總體風險為一。恆零函數的兩種風險均為零。所以經驗最小化解可能泛化很差;損失有界本身無法控制不受限制的函數族。此例不滿足上面的有限維一致 Lipschitz 參數條件。
常見錯誤
(只在已觀測樣本上檢查 Lipschitz 界)
Lipschitz 常數必須對所有觀測值一致成立,不能僅在已觀測樣本上成立。證明把總體風險 移到網格時,是對新的觀測 平均該界;只在 上驗證的界,對 在其他位置的取值毫無說明,而上面反例中的函數正是在那些位置不為零。
常見錯誤
(看過數據之後才選擇函數族)
訓練誤差小本身並不能保證總體誤差小。也不能看過同一批數據之後選擇函數族,再假裝該族事先固定。如果隨機函數族由獨立的訓練數據產生,且同樣的確定性界對每個實現都成立,可以先對訓練數據條件化。
常見錯誤
(把界用於無界的平方損失)
沒有額外假設或另一種集中工具,保證不涵蓋無界平方損失。只限制參數並不足夠:若 無界,即使 ,損失 仍然無界,第二題正說明這一點。
練習
快速檢查
(取 、、,求 和 。再令 、、,寫出一致誤差界的精確值。)
解答 · 答案
,。所求界為 ,其中 。它有效,但大於損失在 時最大可能的誤差一,說明正確的界也可能沒有實際區分力。
快速檢查
(設 、,平方損失 。求適用的 和 ;解釋若 無界,為何只限制 不能給出同一個 。)
解答
,故可取 。並且
所以可取 。若 無界,即使 ,平方損失也可任意大;不能以 使用有界損失集中界。
快速檢查
(在一致事件上,若族內最佳風險為 、,算法的經驗目標距下確界不超過 ,求總體風險上界。若理想風險為 ,分解所得超額風險界。)
解答 · 答案
總體風險至多 。相對理想風險,超額風險界為 :族的近似誤差為 ,一致估計貢獻 ,優化貢獻 。
快速檢查
(若 ,定理對族內風險說明甚麼?此時是否必須支付全部 個網格點的代價?)
解答 · 答案
的逐點條件意味著所有參數在每個 上給出相同損失,所以所有總體風險和經驗風險都相同。一個點就覆蓋整個族,直接對一個函數應用集中界便可避免多餘的 因子;定理使用較大網格仍然正確,只是偏鬆。