為甚麼要數模式,而不是參數?
參數網格通過比較附近的參數控制無限函數族,但需要度量和一致利普希茨(Lipschitz)條件。有時不同參數在所有觀測點上給出的預測完全相同;反過來,一個描述看似簡單的函數族也可能記住全部樣本。我們需要衡量樣本上的函數行為,而不是只數參數名稱。
隨機符號提供一種檢驗:為每個觀測獨立地賦予公平的正負號,問函數族能在多大程度上跟隨這些人為雜訊。豐富的函數族可以追隨較多雜訊,受限制的函數族則不行。這裏直接衡量的是損失函數族;預測函數族的界不能不經論證就當作損失族的界。
設定與隨機符號度量
設 獨立同分布,公共分布為 ,。設 是非空、可數的可測函數族,每個函數取值於 。記
定義 10.3.1
(經驗與期望拉德馬赫複雜度)
令 為相互獨立的公平正負號,且與樣本獨立。經驗拉德馬赫(Rademacher)複雜度是條件期望
上確界允許在看到隨機符號後選擇 ;否則每個固定函數的帶符號和的期望均為零。可數性保證下文的上確界可測。即使函數族不含零函數,複雜度仍非負:上確界不小於任一固定函數的帶符號和,而後者的期望為零。
定理 10.3.2
(單側一致泛化界)
對 ,以下事件關於樣本的概率至少為 :
因此,同一事件上,任何由數據決定的可測選擇 的總體風險 至多是經驗風險 加上右端。這裏的複雜度還對樣本取了期望,並非僅是觀察到的經驗複雜度。
證明:影子樣本與集中不等式
證明
(先對稱化,再用有界差分)
引入與原樣本獨立、同分布的影子樣本 。對固定原樣本,。把期望移到上確界之外只會增加表達式,因此
每一對 的兩項可交換,而且各對獨立。因此按獨立公平符號交換各對兩項,不改變聯合分布。引入符號,再應用 ,得到
兩個上確界可以選取不同函數,所以這裏得到的是不等式。最後一步使用符號分布的對稱性。
令 。更換一個觀測使每個 的變化不超過 ,故 的變化也不超過 。有界差分不等式給出 。其證明也解釋了條件:逐個揭示觀測,形成 的 Doob 鞅;給定過去,每個鞅增量的條件均值為零,且位於長度不超過 的區間內。Hoeffding 引理將其條件指數矩控制在 。將各步相乘並用 Markov 不等式,得到 ;取最優 得所述尾界。取 並結合影子樣本估計,即證定理。
證明透視
三個步驟,各自消除一個障礙
影子樣本把未知的 換成獨立副本的經驗平均。這一步唯一的不等式,是把期望移到上確界之外。
接著可以插入隨機符號而不改變任何東西,因為每對 可交換,而各對之間相互獨立;獨立同分布假設正是在這裏用到。拆開上確界得到兩個拉德馬赫複雜度,係數二就來自這次拆分;它有所損失,因為兩個上確界可以選取不同函數。
圍繞其均值的集中只用到取值範圍 ,經由大小為 的差分;有界性在這裏進入。可數性只用於使上確界可測。界以期望複雜度 表述,因為對稱化控制的是 ,而不是 本身。
這只是單側界。對 也應用定理,再用聯集界,可得雙側誤差界,根號中的對數改為 。兩族複雜度相同,因為額外常數項的帶符號和期望為零,且符號反轉不改變分布。若雙側一致誤差為 ,而近似經驗最小化滿足 ,則 :先與任意 比較,再取下確界。
從樣本模式得到界
引理 10.3.3
(模式計數界)
假設在固定樣本上,取值向量 至多有 個不同值,則
證明
(對有限個模式取指數矩)
把這些向量記為 。對任意 ,由 Jensen 不等式、指數最大值界和 ,
當 時優化 並除以 ;當 時,帶符號和的期望恰為零。如果同一個確定的 對每個樣本有效,取樣本期望後也得到 的上界。這個簡便估計可能大於一,也不一定緊;當 相對 較小時才有用。
證明透視
為甚麼只有模式的數目重要
函數類只透過它的 個值向量出現,所以上確界變成有限多個和的最大值;正因如此,才可用軟最大值上界 。接著 Jensen 不等式把對符號的期望移入對數之內。符號的獨立性把每個指數矩分解為 ,而範圍 把它界於 。選取 使兩項平衡。若以 代替 ,便得到更精細的 。
例題 10.3.4
(閾值損失只有少量樣本模式)
令 為實隨機變量,,其中 取有理數。這是無限但可數的函數族。將任意 個觀測排序,移動閾值只會按排序依次加入觀測,因此最多出現 個不同取值向量;相同觀測值可能使數量更少。於是
的概率至少為 。當 、 時,右端約為 。它是與分布無關的充分保證,不是觀測誤差,也不是最緊的閾值過程不等式。
例題 10.3.5
(兩點上的兩個函數:精確計算)
令 , 在樣本上的取值向量為 與 。則 、,帶符號的上確界是 。在四個等可能的符號對上,它分別為 ,平均為 。除以 得 。 的模式計數界給出 ,大三倍以上。這個界有效,但 很小時,對符號向量精確取平均可以緊得多。
例題 10.3.6
(邊界情況:只有一個觀測)
對閾值族及 ,把有理數 放在 之下或之上,每個觀測都容許模式 與 。當 ,上確界為 ;當 ,上確界為 ,由模式 達到。因此對每個樣本 ,而 。定理於是把 界定為 ,對每個 都大於 。取值於 的損失,其差距永不超過 ,所以這個界正確卻毫無資訊;模式估計 亦然。有用的保證需要 相對 很小。
一個會記住樣本的函數族
取值有界與可數性本身並不能使複雜度變小。
反例模式
差距不會縮小的可數有界函數族
斷言:對取值於 的可數函數族,一致差距隨 增大而趨於零。令 為 上的均勻分布, 為有理端點開區間的有限並的指示函數族。它可數。對任意有限樣本和任意 ,可用有限多個這樣的區間覆蓋樣本點,並使總長度小於 。相應函數滿足 、,故 。實際上,只要樣本點互異,就可在標記為一的點附近選擇足夠小的區間,實現任意二元標記。因此,有界損失和可數性本身並不能保證有用的一致界:該族的複雜度不趨於零。函數族在抽樣前固定的條件也很重要;若使用同一數據選擇函數族,需要另作分析。
常見錯誤
常見錯誤
(先選函數,後看符號)
若把上確界換成一個固定的 , 的期望為零,每個函數族的複雜度都會變成零。定義容許 依賴符號向量;正因如此,它才量度函數族擬合雜訊的能力。
常見錯誤
(以觀測到的複雜度代替期望複雜度)
定理以 表述。把它換成在觀測樣本上計算的 ,需要對 再作集中論證,並會改變常數;本節沒有證明這一步。對每個樣本都成立的確定性模式計數可避開這個問題,閾值例子正是如此。
常見錯誤
(把預測函數族的界轉用於損失族)
計算是在損失函數本身進行的。預測函數族的複雜度界,不會自動成為複合後損失族的界;這種轉移需要另外論證損失如何依賴預測。
練習
快速檢查
(函數族只含 。計算其經驗拉德馬赫複雜度,並解釋為甚麼結果不是一。)
解答 · 答案
它等於 。上確界只有一個候選函數,公平符號在期望中抵消;損失值一並不是帶符號相關本身。
快速檢查
(某二值函數族在任何大小為 的樣本上最多產生 16 種模式。利用模式估計給出期望拉德馬赫複雜度的數值上界。)
解答 · 答案
上界為 。由於對每個樣本均成立,取期望後仍成立。
快速檢查
(在上述閾值族中,觀察樣本後選擇經驗閾值。解釋為何同時成立的定理適用,並指出仍須核對的一個條件。)
解答 · 答案
同一事件同時控制每個有理閾值,因此控制使用數據選擇的閾值。選擇必須可測且屬於固定的可數函數族;不能據此擅自擴大成依賴同一數據的其他函數族。
快速檢查
(對區間有限並的記憶函數族,計算互異的 個樣本點上的經驗複雜度。為甚麼它不趨於零?)
解答 · 答案
對每組符號,該族都能實現恰在正號點上為一的指示函數,因此最大的帶符號和等於正號數量。經驗複雜度為 ,對任意互異樣本都與 無關。這個可數區間族足夠豐富,可以記住隨機符號。