為甚麼計算模式而不是模型?
一個很大的分類器族,在特定樣本上仍可能只有少數不同表現。例如在實數線上移動閾值雖然得到無窮多個函數,但在 個不同的有序點上只有 個標記序列。泛化分析需要理解模型在觀察點上能產生多少種錯誤模式,而不是只數參數值。我們用有限集合上的限制來表達這一點。
定義 17.1.1
(打散與增長函數)
設 是從 到 的非空函數族。若有限集 上每個函數 都是某個 成員的限制,便稱 被打散。VC 維數是被打散集合大小的最大值;若不存在有限上界,則維數為無窮。定義 為所有由 個不同輸入構成的集合上,不同限制個數的最大值,並令 。若定義域少於 點,則取大小至多為 的集合。重複點不會增加模式數。
某個集合不能被打散,不代表另一個同樣大小的集合也不能。要確立維數,既要展示達到該大小的集合,也要排除所有更大的集合。訓練數據的標記無須可由這個函數族完全實現。
組合定理
定理 17.1.2
(Sauer–Shelah 界)
若 的 VC 維數有限且等於 ,則對每個整數 ,
其中 時令 。當 時,這比平凡界 更好;固定 時,它隨 多項式增長。
證明
(刪去一點後作歸納)
將標記一的點看成子集。只須證明:若 點集 的子集族 不打散任何 點集,則 。對 歸納,並同時對所有 進行, 顯然。取 ,令 ,定義
令 ,。按原子集是否含 計數,得 。若 打散某集合, 也打散它,故 維數至多 。若 打散 中的 點集 ,對 上每個標記模式, 的兩種標記都能實現,於是 打散 ,矛盾。因此 時, 維數至多 ;當 時,同一論證說明 為空,計數貢獻為零。分別使用歸納假設及 Pascal 恆等式,得到
故斷言成立,定理亦隨之成立。
證明透視
為甚麼交集少一個維數?
證明包含一個計數恆等式和一個結構觀察。恆等式 只是記帳: 上有兩種延伸的模式在聯集中計一次,在交集中再計一次。結構觀察才是不明顯的一步。交集中的每個模式都能以被移除點的兩種標記實現。若交集已提供其餘 點上的所有模式,多出的選擇便會打散 點。聯集只記錄哪些模式可行;交集記錄哪些模式有兩種延伸。
假設「沒有 點集被打散」用了兩次,層次不同:對 直接使用;對 則經延伸論證使用,並降為 。所以歸納必須同時對所有 進行。論證以 Pascal 恆等式 收口,它把兩個和逐項配對。
從計數到學習保證
設 為正整數, 獨立同分佈,,定義 及 。以下另外假設 有限且分類器可測,從而不必處理無窮函數族上確界的可測性。上述計數引理本身無須函數族有限。
定理 17.1.3
(有限分類器族的 VC 一致界)
若 且 ,則
因此若 最小化 中的經驗錯誤,在上式事件以外有 。若右邊概率界大於一,可以改用一。
證明
(幽靈樣本、隨機交換與對模式的聯合界)
取一個獨立、大小同為 的幽靈樣本,其經驗錯誤記為 。若上確界超過 ,按有限函數族的固定次序選一個見證分類器。給定原樣本後,它在幽靈樣本上的均值方差至多 ;Chebyshev 不等式給出它與真實錯誤相差至多 的概率至少為 。因此原事件概率至多為以下事件概率的兩倍:存在 使 。
對每一對位置的兩個觀察值,以概率二分之一獨立交換;聯合分佈不變。給定所有 個觀察值後,一個預測模式決定一個錯誤模式,而預測模式至多 個;重複輸入只會減少個數。對固定模式,交換後差值是 ,其中獨立符號 等概率取正負一,而固定數 。Hoeffding 不等式表明其絕對值超過 的概率至多為 。對模式用聯合界,再乘幽靈樣本步驟的二,便得所需概率界。
在該事件以外,令 為有限族中的真實風險最小者,則
這裏無須假設訓練錯誤為零。
例子與反例
例題 17.1.4
(實數線上的閾值)
令 ,。在單點兩側選閾值可實現兩種標記;兩個有序點卻不能取得 ,所以 VC 維數為一。對 個不同的有序點,正標記形成後綴,而且 個後綴全部可實現。因此 ,恰好等於 。對任何有限的閾值選集,前述條件下的學習界為 。
例題 17.1.5
(區間可以打散兩點)
考慮把閉區間內標為正、其餘標為負的分類器。任選兩個不同點,選擇不含兩點、只含其中一點或同時包含兩點的區間,便能實現四種模式。三個有序點不能取 :包含兩端點的區間必包含中點。所以 。論證用的是區間的幾何性質,而不只是端點參數的個數。
例題 17.1.6
(界何時開始有內容,以及 的情況)
對有限閾值族取 、。此時 ,且 ,所以界為 。以至少 的概率,每個經驗錯誤與其風險相差至多 ,經驗最小者與類內最佳閾值相差至多 。對照下面練習中的 ,同一公式會大於一。
另一極端是 :沒有任何單點被打散,所以全部成員在每個輸入上都一致, 只有一個函數,。定理給出 ,而對單一固定分類器用 Hoeffding 不等式則給出 。幽靈樣本的論證並不追求最佳常數。
反例模式
參數個數本身不是 VC 維數證明
無窮定義域的所有子集構成的分類器族打散每個有限集,故 VC 維數無窮。可是它在任何固定的 點樣本上仍只有有限多個限制,即 個。因此每個樣本上的模式數有限,並不足以推出定理所需的多項式增長。類似地,只有低維參數化而沒有參數如何產生分類器的假設,也不能直接推得 VC 界。
維數陳述有兩半,量詞並不相同;計算 VC 維數時的錯誤大多來自把兩者混淆。
常見錯誤
(用一個不好的配置來界住維數)
要證明 ,展示一個被打散的 點集便足夠;要證明 ,則必須說明每個 點集都不能被打散。對區間而言,任何兩個不同點都得到全部四種模式,而每三個有序點都缺少 ;兩半合起來才得到 。只說明某一個 點集不能被打散,並不證明任何上界:平面上的半平面不能給三個共線點標記 ,因為半平面是凸集;但不共線的三點可被打散,所以半平面的 VC 維數至少為三。
常見錯誤
(在 點而非 點上數模式)
對稱化一步同時固定原樣本與幽靈樣本,所以聯合界遍及 點上的模式。這個證明不容許把 寫成 。對閾值而言,這會把 換成 ;對較大的 ,兩個計數之比可以接近 。
練習與解答
快速檢查
(若 只有恆零及恆一分類器,求其 VC 維數及 時的增長函數,假設定義域至少有 點。)
解答 · 答案
一點可打散,但兩點只有 及 。故 , 時 ,而 。
快速檢查
(四點上的分類器族 VC 維數至多一,Sauer–Shelah 允許多少個模式?給出達到此數的例子。)
解答 · 答案
至多 個。空集與四個單點集達到此數;任意兩點同時標正的模式不存在,所以沒有一對被打散。
快速檢查
(對有限閾值族,取 、,不經四捨五入寫出概率界。)
解答 · 答案
,界為 ,大於一。它雖然正確但沒有資訊;使用概率至多一更好。
快速檢查
(經驗錯誤最小者的訓練錯誤為零,定理是否保證真實錯誤為零?)
解答 · 答案
不保證。一致事件上只能推出 ;事件以外甚至沒有這個結論。例如分類器可能錯分一個有正概率但沒有在樣本中出現的區域。