幾何分類器可以有無限多個可能的邊界,VC 維卻仍然有限。問題不在於有多少條邊界,而在於它們能對有限多個點作出多少獨立的標記。需要兩個互補的論證:構造一個能實現所有標記的集合,再證明任何更大的集合都不能有這個性質。
以下 為整數,定義域是 。
定義 2.2.1
(打散與 VC 維)
如果某個分類器類能實現有限集合上每一種二元標記,就說它打散該集合。該類的 VC 維是使得存在 個互異點的集合被打散的最大整數 ;若任意大的有限集合都能被打散,則為 。
被打散集合的每個子集也被打散:先將子集的標記任意擴展到整個集合即可。因此,排除某一大小的打散集合,也就排除了所有更大的大小。座標和閾值均為實數,下文的幾何集合都包含邊界。
仿射半空間
考慮
我們允許 ,因此包含恆為零和恆為一的分類器。偏移量 使邊界能夠移動,而不必通過原點。
定理 2.2.2
(仿射半空間的 VC 維為 )
對於上述類,。
證明
(仿射分數的構造與仿射相關)
下界。 點 仿射無關。對於任意指定的符號 ,取 和 。那麼仿射分數在原點恰為 ,在 處恰為 。因此它以嚴格遠離零的分數實現所需標記。全部 種標記都能實現。
上界。 任取 個互異點 。它們的增廣向量 線性相關。因此存在不全為零的實係數,滿足
這些係數中既有正數也有負數。將 的點標為 1, 的點標為 0;係數為零的點可任意標記。若某個仿射半空間實現了該標記,其分數 在正係數點滿足 ,在負係數點滿足 。因此
嚴格不等式來自至少一個負係數與嚴格為負的分數相乘。但仿射相關給出 ,矛盾。因此任何 個點都不可能被打散。結合下界即證明定理。
證明透視
邊界約定為何重要
證明沒有假定所有帶標籤點的分數都被嚴格分開。由於邊界點標為 1,一個候選實現只保證正標籤側 、負標籤側 。單憑負係數項便能迫使加權和嚴格為正。因此不必假設點處於一般位置,也處理了邊界情況。
例題 2.2.3
(平面上的三個點)
平面上的原點和兩個座標單位向量能實現全部八種標記。若原點標為 0、 標為 1、 標為 0,取 、:三個分數為 。定理說明,無論排列如何,平面上任意四個點都不能被仿射半空間打散。
例題 2.2.4
(由仿射相關取出不可實現的標記)
取平面上的四個點 。取 ,則 ,且 。正係數在 和 ,所以證明將它們標為 1,並將 標為 0。假設分數 實現了這個標記,則 、、、。後兩式相加得 ,前兩式相加得 ,矛盾。這就是熟悉的異或標記,也說明加權和 正是被迫為正的量。
概念視角幾何
仿射相關就是兩個相交的凸包
令 。仿射相關式表示兩個點 與 重合,也就是正、負兩組點的凸包有一個公共點。仿射分數不可能在其中一個凸包上 ,而在另一個凸包上 。在正方形的例子裏,這個公共點是 。
例題 2.2.5
(係數為零與共線的點)
取四個點 。係數 滿足 ,且 。點 的係數為零,所以它的標記可以任意,在論證中不起作用。證明將 和 標為 1, 標為 0,這正是共線模式 1、0、1:中間的分數 ,不可能為負。同一個相關式也說明上面證明透視中所講邊界約定的重要性,因為 可以等於零。
反例模式
維數結論並不是關於每個集合的結論
平面上一條直線上按順序排列的三個點,不能被仿射半空間標記為 1、0、1。中間點的分數是兩個端點分數的凸組合,所以若兩個端點均非負,中間分數也非負。平面中的 VC 維仍為 3,因為存在可以打散的非共線三點集。下界只需存在一個可打散集合。
座標軸平行盒子
令 由有界閉盒子的指示函數組成,其中
不同座標中的界可以分別選擇,但每個正點必須同時滿足所有座標約束。該結論不需要把空盒子作為額外假設加入類中。
定理 2.2.6
(座標軸平行盒子的 VC 維為 2d)
當 時,。
證明
(極端點與嚴格極值)
下界。 考慮 個點 。對每個座標 ,若 要標為正,取 ,否則取 。若 要標為正,取 ,否則取 。每個區間都包含零,因此其他座標不會限制 。所選端點恰好包含標為 1 的點。即使全零標記也可由 實現。
上界。 假設有 個互異點被打散。對每個點 ,選擇一個包含其他所有點但排除 的盒子。 的某個座標必定在盒子之外。若它低於該座標的下端點, 便是全體點在該座標上的嚴格最小值;若高於上端點,它便是嚴格最大值。每個座標至多有一個嚴格最小點和一個嚴格最大點,因此至多 個點能充當這樣的極值點。 個點卻每個都必須是極值點,矛盾。
這個論證也適用於座標值相同的情況:如果一個點被排除而其他點都被包含,它在某個座標上必須是嚴格極值。相同座標不能在該座標上提供所需的證據。
例題 2.2.7
(被矩形打散的四個點)
在二維中,四個點 和 能被打散。若只包含 和 ,使用 。其餘兩點落在外面。即使四條邊界座標都是實數,平面上的五個點也不可能被座標軸平行矩形打散。
例題 2.2.8
(一維情形與不能被排除的點)
當 時,盒子就是閉區間,定理給出 。點 被打散: 選中兩者, 只選中 , 只選中 , 一個也不選。對三個點 ,中間點既不是嚴格最小也不是嚴格最大,所以沒有區間能包含 和 而排除 。標記 1、0、1 不可能實現,這與 時的上界論證一致。
常見錯誤
(丟掉偏移量)
若去掉偏移量,類 的 VC 維是 ,而不是 。當 時,它包含 、 的指示函數和恆為一的函數。單個點 能被打散,兩個點則不能:對點 ,標記 需要 且 ;對 ,標記 需要 且 。定理中多出的一維正是由偏移量 帶來的。
常見錯誤
(把座標相同當作極值證據)
在盒子的上界論證中,被排除而其他點都被包含的點,必須在某個座標上是嚴格最小或嚴格最大。座標相同不算數。在平面上,令 ,其他點為 。在第一個座標上 嚴格處於 與 之間,在第二個座標上嚴格處於 與 之間,所以任何包含其餘四點的盒子都包含 。這個 永遠不能被排除;同樣的推理也說明,嚴格性正是證明至多只有 個證據點的依據。
容量與學習結論
定理統計有限集合上可能出現的標記;它沒有給出具體的高效學習算法或精確樣本量。VC 泛化結果還要結合獨立抽樣、置信度及學習規則等假設。單憑可調參數的數量也不能代替打散證明:類的定義、定義域和允許的邊界都很重要。
練習與解答
快速檢查
(給出 ,使 在 處分別標為 1、0、1。)
由原點處的分數決定 。
解答 · 答案
取 、,分數為 。
快速檢查
(為甚麼實數線上按順序排列的三個點不能被閉區間打散?)
哪一種標記不可能實現?
解答 · 答案
包含兩個端點的區間也包含中間點,所以無法實現標記 1、0、1。
快速檢查
(對平面上的四個點 ,給出一個恰好選中 和 的盒子。)
分別限定每個座標。
解答 · 答案
。
快速檢查
(VC 維為 是否意味著仿射半空間能打散每個由 個點組成的集合?)
回想定義:只要求存在一個被打散的集合。
解答 · 答案
不是。定義只要求存在一個該大小的被打散集合;例如平面上共線的三個點,就不能按順序實現 1、0、1。