動機
一個假設類即使包含無窮多個規則,在任一有限樣本上的表現也可能只有有限種。實數軸上的閾值便是例子:切分點可以有無窮多個位置,但對 個有序輸入只會產生 種標籤模式。泛化證明可以統計這些模式,而不必逐一統計所有假設。困難在於,統計模式所用的樣本本身是隨機的,而且學習器是在看到標籤之後才選擇假設。
增長函數衡量給定大小的樣本上最多可能出現多少種模式;VC 維數衡量多大的集合能夠實現所有模式。Sauer–Shelah 定理把有限 VC 維數轉化為多項式增長界。隨後需要另一個概率論證,才能從計數得到同時成立的誤差保證。單靠計數或訓練擬合都不能保證總體表現:數據還必須滿足所述抽樣假設。
定義
定義 2.1.1
(跡、增長函數與打散)
設 為非空可測空間, 是由可測函數 組成的非空類。對有限集合 ,其跡為
若 ,稱 被打散。VC 維數 是被打散的有限集合的最大大小;若不存在有限上界,則維數為無窮。定義增長函數
輸入元組可以重複點;重複不會增加模式數。大小為 的集合被打散,當且僅當全部 種模式都能實現。有限 VC 維數為 意味著存在被打散的 點集合,但沒有被打散的 點集合。被打散集合的每個子集也被打散:將子集上的任意標籤擴展到較大集合即可。 時,非空 打散空集。
跡取決於輸入,而不是觀測標籤。兩個假設即使在其他地方不同,只要在這些輸入上相同,就只貢獻一個模式。反過來,無窮假設類不一定有無窮 VC 維數。即使 有限,定義仍允許樣本點重複,這符合有放回抽樣。
定義 2.1.2
(總體誤差與經驗誤差)
令 為有標籤對 的任意分布,其中 。對 定義
其中 獨立地從 抽取。分布可以有標籤噪聲,不必由 中某個目標實現。一致收斂在同一個高概率事件上同時控制每個 的 ,因此也涵蓋觀察樣本後選擇的假設。
以下概率證明假設 可數,使相關上確界及所選的見證假設可測,無需引入額外的經驗過程工具。組合定理本身不需要可數性。很多不可數類在適當可測性條件下也有相應概率結論;這些條件並非自動成立,此處不作證明。
定理/命題
定理 2.1.3
(Sauer–Shelah 增長界)
若 的 VC 維數為有限的 ,則對每個整數 ,
其中 時取 。特別地,固定 時,模式數至多按 的 次多項式增長,而不是按 增長。
定理 2.1.4
(通過幽靈樣本得到一致誤差界)
設 如上可數且其成員可測, 包含 個從任意 獨立同分布抽取的有標籤樣本。若 且 ,則
右邊可能大於一,此時不等式雖成立卻沒有實際資訊。結合 Sauer–Shelah 定理可得可數有限 VC 類的無分布假設界;無需假設標籤沒有噪聲。
對置信參數 及 VC 維數 ,定義
這裏對數為自然對數。由於 ,定理適用:以至少 的概率,所有 同時滿足 。這是一個明確的誤差證書,不聲稱其常數或特殊模型下的速率總是最優。
即使不用更精細的二項式估計,增長界也能顯示收斂速度。把一個 點集合中至多含 個元素的子集按遞增次序列出,並用零補成長度 。這是到 的單射,因此 。由此
固定 和 時,右邊趨於零。這裏關於 的對數因子屬於這個特定的界,不能證明更強的定理也必須含有它。若半徑大於一,結論仍成立,但不會改善誤差不超過一的平凡界。
證明思路
證明
(組合遞推式)
固定 個互異點,把一個跡看成這些點的子集。從每個跡中刪去最後一個點。令 為刪點後得到的子集族,令 為同時有「包含最後一點」和「不包含最後一點」兩種原始延伸的子集族。 中每個成員有一種或兩種原始延伸,所以
的 VC 維數至多為 ,因為它打散的任何子集原本也被 打散。若 非空,其 VC 維數至多為 :若 打散剩餘點中的 個點,那麼這 點的每種標籤都由 中某個跡實現。該跡對被刪點有兩種延伸,因而 會打散這 點及被刪點,與 的定義矛盾。
歸納命題適用於 點集合上的任意有限子集族,只要求 VC 維數至多為 ,不局限於原類的跡。空族的大小為零,顯然滿足此界。對 同時歸納: 時,若有兩個不同跡,它們必在某點不同,從而打散該單點,故至多有一個跡; 時初等界 恰為完整二項式和。其餘情況下,歸納假設及 Pascal 恆等式給出
重複樣本點只會減少不同模式的數量,因此同一界適用於 中的元組。
證明
(從第二個樣本到一致界)
令 是同樣大小、獨立的「幽靈」樣本。對固定的 ,幽靈經驗誤差的期望為 ,方差至多為 。Chebyshev 不等式給出
若 上存在壞假設滿足 ,按固定的 枚舉選出第一個。給定 後,獨立幽靈樣本以至少二分之一的概率使該假設的經驗誤差與真實誤差相差至多 。三角不等式隨即給出 。所以
為估計右邊,將 和 的第 個樣本配對,獨立地以二分之一概率交換每對中的兩個成員。交換性保證總體聯合分布不變。給定交換前的 個有標籤樣本,最多出現 種預測模式。合併樣本的標籤也已固定,因此每個預測模式確定一個誤差差值向量。對於固定模式,兩個經驗誤差之差是獨立、均值為零且位於 的帶符號項的平均。Hoeffding 不等式說明其絕對值超過 的概率至多為 。對所有模式使用並集界,再對配對數據取平均,就得到定理和前面的係數四。
計數是在給定合併輸入之後進行的,但早於選擇違反界的模式。正因如此,對有限個樣本模式取並集界可以控制從可數、甚至無窮類中依賴數據作出的選擇。幽靈樣本僅是證明工具;學習器不需要實際獲取其標籤。
證明透視
兩個不同的歸約
Sauer–Shelah 定理是確定性的:它控制固定輸入上的標籤模式數量。對稱化是概率性的:獨立幽靈數據和隨機成對交換將真實誤差轉化成有限多個隨機經驗比較。增長函數只在計數步驟進入論證。分清兩步可以避免錯誤地認為 VC 維數小就能保證某個具體訓練樣本一定有代表性。
一致假設的快速率界
雙側偏差界在 的尺度上控制經驗誤差與總體風險的差。對在樣本上完全不犯錯的假設,下述上界的指數因子是 ,但還乘以增長函數。有限 VC 維使該因子至多多項式增長,從而最終得到更快的速率。證明使用幽靈樣本與獨立交換。
本節取 ,即上面定義 時所用的帶標籤分布。記 為經驗誤差;對 、 和 使用相同記號。
定理 2.1.5
(一致假設的快速率界)
設 是非空可數的可測分類器類, 是帶標籤樣例上的任意分布, 且 。若 ,則
定理並不假設可實現性;它對每個 都估計一個事件的概率。可實現性只在之後起作用:若固定的 滿足 ,它幾乎必然與樣本一致,因此一致假設幾乎必然存在。
證明
(幽靈樣本、交換與 Chernoff 界)
已知不等式(乘法型 Chernoff). 設 是獨立 Bernoulli 變量之和,,且 。則 。
幽靈樣本。 取與 獨立的 。記定理中的事件為 ;記 為「存在 使 且 」。
枚舉 。在 上,令 為第一個滿足 且 的 。由於 可數,這個首個見證是 的可測函數。
給定 ,計數 是 個獨立 Bernoulli 變量之和。這裏 ,所以 。令 ,則 且 。由 Chernoff 不等式,
最後一步用到 。因此在 上 。這個事件包含於 。對 取平均得 ,即損失一個因子 。
交換。 寫 、。取相互獨立的均勻比特 ,並令它們與 獨立。當 時交換 與 ,得到 。由於 獨立同分布, 與 同分布。因此 等於 上同一事件的概率。
現在以交換前匯總的數據 為條件。每個 給出誤差向量 : 當且僅當 在 上出錯, 當且僅當 在 上出錯。該向量由 在這 個點上的標籤決定,所以至多出現 種;重複的點只會減少種數。
固定一個向量。
- 若某個 有 ,則無論 取何值,總有一個錯誤落入 ,故 不可能成立。
- 否則,設恰有一個錯誤的配對數為 。幽靈一側至多有 個錯誤,所以事件要求 。事件還要求這 對都把出錯的成員送到 ,其概率為 。
對所有向量作並集界,條件概率至多為 。再對匯總數據取平均, 滿足同樣的界。由於 ,結合幽靈樣本一步的結論即完成證明。
說明
為何需要幽靈樣本. 在 上表現相同的假設可以有不同的風險,因為 依賴整個 。所以只在 上計數行為模式不足以得到這裏的統一風險界,而直接對無限的 使用無權並集界可能沒有資訊。幽靈樣本把 換成 。這個量只依賴 個點,正是 所計數的對象。
界可能大於 1. 當 較小時,該界沒有資訊量。
樣本量. 設 且 。Sauer–Shelah 引理給出 。在同時滿足 的前提下,只需 。這是隱式的充分樣本量不等式:增長項關於 為對數,而指數因子依賴 。若 且 非空,則 ;此時使用原界,要求 且 。在可實現情況下,一致輸出就以至少 的概率滿足 。這些是充分界,不是匹配的下界,也不是高效算法。
例題 2.1.6
(快速率界下的閾值類)
在 上取 ,其中 ,此類可數。在 個不同點上,閾值標籤由排序後位於 及其右側的點數決定。有理數稠密,所以 種情形都能出現,於是 。
取 ,。此時 ,界為
這是充分而非最優的結論;小得多的 也可以。
快速檢查
(對同一類與 ,證明 使界小於 。)
先檢查 的條件,再計算 。
解答 · 答案
條件成立:。又 ,,故界為 。因此在可實現情形下,一致輸出的風險以至少 的概率不超過 。
例題
例題 2.1.7
(閾值:無窮規則與線性增長的模式)
令 ,定義域為 。任意單點都能標為零或一;但若 ,標籤 不可能出現,所以 。對 個互異有序輸入,可以在每個相鄰間隙以及兩個端點外側選擇有理切分點,因此 。本例中 Sauer–Shelah 界精確達到。此類雖無限,卻滿足可數性限制。實數參數閾值有相同的有限跡,但可數類的概率定理不能自動推廣到該類:需要額外的可測性或單獨的逼近論證,尤其當輸入分布有原子時。
例題 2.1.8
(數值證書及其代價)
對上述閾值,。當 、 時,明確的一致誤差半徑為
因此定理保證以至少 的概率,所有閾值的誤差偏差均小於約 。這個界為通用結論,可能較保守;它同時涉及每個閾值,不是對某個擬合模型實際誤差的估計。
例題 2.1.9
(經驗風險最小化如何利用這一事件)
固定非空可數 的枚舉,令 為該枚舉中第一個經驗誤差最小者。最小值確實存在,因為經驗誤差屬於有限集合 ;這一平局處理規則也保證選擇可測。在每個偏差都不超過 的事件上,對每個 ,
取下確界得 。最小真實風險不一定被某個假設達到。保證中包含類的逼近誤差 ,不假設類中存在完美分類器。
反例模式
訓練準確不代表泛化準確
取 ,兩點等概率,且標籤在 為 、在 為 。恆等於一的假設有真實誤差 。若 個輸入恰好全部為 ,這一事件的概率為 ,則它的經驗誤差為零。高概率定理可以控制不具代表性的樣本出現的頻率,卻不會說這種樣本不可能出現。
常見錯誤
常見錯誤
(將 VC 維數與假設個數混淆)
VC 維數為一並不意味著類中只有一個規則;它意味著至少一個點能被打散,但沒有一對點能被打散。增長函數統計有限樣本上可區分的標籤模式;若不同假設在該樣本上相同,只算一種模式。
常見錯誤
(擬合後套用固定假設的界)
對預先選定的一個 成立的集中不等式,不能直接用於觀察同一樣本後選出的假設。一致定理構造一個同時控制所有假設的事件,此時才可以代入擬合出的假設。使用概率結論前,須檢查獨立同分布及可測性條件。
總結
打散衡量哪些標籤模式可以實現;Sauer–Shelah 遞推控制最大模式數。幽靈樣本、隨機交換和集中不等式將計數轉化為同時成立的偏差保證。即使標籤含噪聲,經驗風險最小化也可以用這一事件將擬合風險與類中可達到的最佳風險比較。
練習
快速檢查
(定義域有 個互異點, 包含所有二元函數。求 ,以及 時的 。)
數一數 個互異點上的模式。
解答 · 答案
整個定義域被打散,且不存在更大的子集,因此 。當 ,選取 個互異點,全部 種模式都出現;模式數也不可能更多,故 。
快速檢查
(對 上的 ,求 並與 比較。)
數一數六個有序輸入的切分位置。
解答 · 答案
六個互異有序輸入的每個切分位置對應一種模式;重複輸入不會產生額外切分,所以 ,遠小於 。界 在此達到。
快速檢查
(假設一致收斂事件的半徑為 ,某經驗風險最小化解的經驗誤差為 。給出其真實誤差上界,並另外給出相對於 的界。)
一個界直接用該事件,另一個界與每個 比較。
解答 · 答案
一致事件給出 ;經驗最小化論證給出 。這是兩個不同結論,均未確定未知的最佳風險。
快速檢查
(非空定義域上的假設類只包含兩個常值分類器。求其 VC 維數及 時的增長函數,並驗證 Sauer–Shelah 不等式。)
哪些由互異點組成的集合能被打散?
解答 · 答案
一個點可以標為零或一,所以維數至少為一。常值分類器不能給兩個互異點不同標籤;若定義域只有一個點,也沒有更大子集,故維數仍為一。每個 均只有全零和全一兩種跡,因此 。