動機
分類器可以完全擬合訓練樣本,卻在未見過的數據上頻繁出錯。分析差距之前,我們必須說明樣本如何產生、錯誤如何衡量,以及保證中的概率針對甚麼隨機性。PAC 學習要求算法以高概率輸出近似正確的假設,並不保證每一個可能樣本都會成功。
本節討論可實現的二分類模型:標籤由假設類中的目標函數產生,樣本獨立地來自一個固定但未知的分布。樣本數量足夠並不自動意味著能高效找到所需假設;統計與計算是兩個不同問題。
定義
定義 1.1.1
(風險與 PAC 保證)
令 為可測實例空間, 為可測函數組成的假設類, 為概率分布,目標為 ,且 。獨立同分布樣本 的經驗誤差和總體風險為
可實現 PAC 學習要求:對每個 、 和 ,輸出的 以至少 的概率滿足 。概率針對訓練樣本和算法內部隨機性。高效 PAC 學習還要求運行時間在相關參數中有適當的多項式界。
經驗誤差為零的假設稱為與樣本一致。一致只約束觀察到的點;概率為零的點即使標籤不同,也不增加總體風險。
定義 1.1.2
(打散與 VC 維數)
若有限集合 的每一種二元標記都能由某個 實現,則稱 打散 。VC 維數是被打散的有限集合的最大大小;若能打散任意大的有限集合,則維數為無窮。存在一個大小為 的被打散集合就足夠,並不要求所有大小為 的集合都被打散。
概念視角組合
打散即標記模式的計數
對有限集合 ,令 為 在 上能實現的標記模式的集合。則 被打散當且僅當 ,即 。多個假設可以產生同一個模式,所以 。因此有限類只能打散滿足 的集合,由此得 。這是把同一概念看作模式的計數,而不是逐個標記地檢查。
定理/命題
定理 1.1.3
(有限類的一致學習界)
設 有限,算法總返回 中與可實現的獨立同分布樣本一致的假設。如果
則輸出的風險至多為 的概率至少是 。
定理 1.1.4
(可數類的奧卡姆界)
對可數假設類賦予正權重 ,滿足 ,且權重在觀察樣本前固定。以至少 的概率,每個與樣本一致的假設同時滿足
可以給描述較短的假設較大權重;在一致的條件下,這給出較小的風險上界。
證明思路
證明
(壞假設必須避開所有樣本錯誤)
固定一個 的假設。每個樣本落入其錯誤區域的概率大於 ;獨立性給出它仍然一致的概率至多為 。對所有假設使用並集界,存在壞的一致假設的概率至多為 。因此在剩餘事件上,算法即使看過樣本才選擇假設,其一致輸出仍有風險至多 。可實現性確保至少存在一致的目標假設。
對於加權結論,令 。當 時, 一致但風險大於 的概率至多為 ;當 時結論自動成立。對所有假設求和,失敗概率至多為 。不同假設的失敗事件不必相互獨立。
證明透視
為甚麼界適用於依賴數據的選擇
先固定一個壞假設:獨立性控制它避開所有樣本錯誤的概率。然後在學習器選出輸出之前,對所有假設取並集界。在所得成功事件上,每個一致候選都準確,所以保證也適用於觀察樣本後選出的輸出。
以下獨立的四點例子使證明更具體。輸入從 {a,b,c,d} 獨立均勻抽取,目標為 0000,固定假設類為 {0000,0001,0011}。抽取兩次、,並選取一致假設中序號最大者時,十六個有序樣本中有四個會選出壞假設。改變選取規則,可比較特定學習器失敗的事件與「存在任何壞的一致假設」的事件。樣本量界是分布無關的充分條件;這個精確計數只適用於所述均勻分布。
例題
例題 1.1.5
(有限假設類)
若 、、,定理給出的充分樣本數為
這是對所有符合模型的分布有效的充分界,並非每個具體問題所需的精確閾值。計數證明也沒有給出尋找一致假設的算法運行時間。
例題 1.1.6
(實數軸上的閾值)
令 ,其中 。任意一個點可以被標為零或一,所以能被打散。對於 ,標記 無法由閾值實現,因此 VC 維數為一。這個類是無窮的,不能直接把無窮代入有限類的樣本界。
例題 1.1.7
(實數軸上的區間)
取所有有界閉區間的示性函數,並加入空集對應的假設。兩個不同點的四種標記都可實現:選取只含其中一點、包含兩點的區間,或選空集。三個有序點的標記 不可能由區間實現,所以 VC 維數是二。即使不加入空假設,也可選取與有限集合不相交的有界區間來實現全零標記。
下面的互動圖列出固定樣本在閾值類與區間類下的每一種標記,並為每種標記給出可配合的假設或有序反例,讓兩個 VC 維數可逐一模式核對。
常見錯誤
常見錯誤
(只檢驗一個集合,而非所有集合)
要證明 ,只需給出一個大小為 的被打散集合。要證明 ,則必須排除所有大小為 的集合;找到一個沒有被打散的集合並不能說明任何問題。例如令 , 由在 處取值為零的四個函數組成。集合 沒有被打散,因為沒有假設在 處給出標籤 ;但 被打散,所以 。
常見錯誤
(訓練誤差、總體誤差和概率)
經驗誤差為零不代表總體誤差為零。 控制抽到使保證失敗的訓練樣本的概率; 控制成功事件上的總體誤差。二者均不是某一次固定測試預測出錯的概率。
反例模式
權重之和超過一
假設有人對每個假設取 來使用奧卡姆(Occam)界。取 、 為均勻分布、目標 ,以及 ,其中 是單點 的示性函數。則每個 都有 ,而權重之和為 。取 ,所聲稱的界是 ;當 時等於 。但七次抽樣至多包含七個不同的點,所以必有某個點 未被抽到;此時 與樣本一致,而它的風險是 。所聲稱的事件「每個一致假設的風險都至多為 」因此概率為 ,而不是至少 。換用合法的權重 ,界為 ,與實際情形相符。條件 正是對假設取並集界所需要的。
無分布假設的保證仍有模型條件:樣本必須獨立地來自同一個固定分布,且標籤由 中的目標產生。不能不加修改地把結論用於相依樣本、分布變化或任意標籤噪聲。
總結
一致性與有限假設類通過並集界給出樣本保證;加權計數將論證推廣到可數類。VC 維數衡量類能實現的標記模式,對無窮類也有意義。統計可學習性與計算效率應分別分析。
練習
快速檢查
(若 、、,求有限類定理給出的充分整數樣本數。)
計算 並向上取整。
解答 · 答案
,向上取整得到充分樣本數 。
快速檢查
(若有限定義域有 個點, 包含定義域上的所有二元函數,求 VC 維數並解釋。)
整個定義域是否被打散?有沒有更大的子集?
解答 · 答案
整個定義域被打散,因為全部 種標記均在類中。定義域沒有更大的子集,因此維數恰為 。
快速檢查
(某一致假設的權重為 ,樣本量為 ,。寫出它的加權風險上界。)
此時 。
解答 · 答案
在同時成立的高概率事件上,。該事件對每個一致假設成立,包括看過樣本後選擇的假設。
快速檢查
(利用模式計數的描述,說明只有五個假設的類不能打散任何三點集合。)
比較 與 。
解答 · 答案
對任何三點集合 ,限制 中每個假設至多給出一個模式,所以 。八種標記不可能全部出現,因此 不被打散。