VC 維統計可能的標籤模式,但本身並不告訴我們如何找到分類器。座標軸平行盒子提供一個易於實現的算法和初等的分布無關證明。關鍵思想是幾何的:如果學習器漏掉了大量正樣本概率,那麼目標盒的某個大量邊界區域必定沒有被樣本命中。
模型與學習器
固定整數 。未知目標盒為 ,所有端點有限且 。從 上任意分布 獨立抽取 個樣本 ,標籤無噪聲:。不假設分布有密度,也不排除原子。盒 的總體錯誤率為
定義 1.3.1
(最緊外包盒)
若至少觀察到一個正樣本,就輸出包含所有正樣本的最小閉座標軸平行盒子:
若沒有正樣本,則輸出空集。
因此假設類包含空集。在實數比較模型中,該規則使用 次座標比較及 個端點儲存;位複雜度取決於輸入編碼。
引理 1.3.2
(沒有假陽性與一致性)
在無噪聲模型下,對每份樣本都有 。因此 包含每個觀察到的正樣本,並且不含任何觀察到的負樣本,即與樣本一致。
證明
(最小值與最大值留在目標之內)
每個正樣本都在 中。每個座標上的最小值和最大值都在對應目標區間內,所以 ; 為空時也成立。因此所有觀察到的正樣本都在 中,所有觀察到的負樣本在 外,也必在 外。
學習器可能產生假陰性,但沒有假陽性。與樣本一致的盒未必等於目標盒。
含原子時的邊界帶
定理 1.3.3
(盒的分布無關樣本界)
設 。若
則 。保證適用於每個分布 和上述每個目標盒;對數為自然對數。
證明
(邊界帶與並集界)
令 ,。若 ,由於學習器沒有假陽性,每份樣本都滿足 。否則 。對每個座標 ,選擇閾值 ,使
即使有原子,這些閾值也存在。例如,令 為滿足 的 的下確界;因為 、目標座標有界,且 使定義集合非空,所以下確界有限。右連續性給出第一個不等式;對每個 有 ,令 並用從下連續性得第二個。對 使用同樣論證得到上閾值。閾值不必分割原子,各不等式也不必取等。
將 個事件 與 稱為邊界帶。若樣本命中每條帶,則至少有一個正樣本,故 非空。每個座標都存在不大於 的正樣本和不小於 的正樣本。因此,被 漏掉的目標正點必對某個 滿足 或 。由 (3) 和並集界,其概率至多為 ;由於 ,這就是全部分類風險。即使 ,這個論證仍成立。
每條帶的概率至少為 ,所以 次獨立抽樣漏掉某條固定帶的概率至多為 。對 條帶使用並集界,得到
各帶可以重疊,漏掉它們的事件也不必獨立。獨立性用於控制多次抽樣漏掉一條固定帶的概率。
證明透視
為甚麼同時使用非嚴格與嚴格不等式?
非嚴格邊界帶有足夠概率被抽中,即使閾值處有原子也如此。一旦樣本命中該帶,這一側只有嚴格越過閾值的點可能被漏掉;這些嚴格尾部的概率至多為 。我們不需要將原子切成指定概率質量。
例子與兩個誤區
例題 1.3.4
(一份誤導性樣本)
在二維空間中,令 均勻分布於 四點,目標為 。假設 且觀察到的兩個正樣本是 和 。輸出為退化盒 ,它符合樣本,卻漏掉另外兩點,風險為 。這樣的樣本具有正概率;PAC 保證控制誤導性樣本發生的頻率,並不聲稱它不可能發生。
例題 1.3.5
(三維的一次運行及其樣本量)
令 ,觀察到正樣本 、、。逐座標取最小值和最大值,得 。對 、,不等式 (2) 要求 ,所以 即可。如果樣本中沒有任何正樣本,輸出就是空集,其風險等於 。在 (2) 成立時,除非 (此時風險本來就小於 ),這種情況發生的概率至多為 。
例題 1.3.6
(稀少的正樣本:低於閾值的情形)
令 、、,所以 ,並設只有 的質量落在 內。由於 ,證明在第一步就結束:無論樣本如何,即使輸出為空集,也有 ,因為學習器沒有假陽性。這種情況不需要任何樣本量條件。
常見錯誤
(期望學習器重建邊界)
該學習器不能從任意 中精確識別目標。若 集中於原點,則所有包含原點的目標盒產生相同帶標籤數據;它們的邊界可以不同,而只要在原點一致,任何盒的風險都為零。PAC 錯誤依賴分布,並不是幾何邊界重建。
常見錯誤
(以為每條帶的概率恰好等於 )
若分布有密度,可以選取閾值使帶的概率恰好為 。有原子時一般做不到:閾值處的單個原子可以帶有大於 的質量。這就是 (3) 對帶使用非嚴格不等式、對尾部使用嚴格不等式,而不要求等號的原因。
證明同時使用了無噪聲標籤,下面的例子具體說明樣本界對標籤噪聲並不穩健。
反例模式
標籤噪聲破壞沒有假陽性的不變量
取 、, 在 處質量為 ,在 處質量為 。設在 處的每個樣本以概率 獨立地被誤標為正,而 處的標籤正確。取 ,不等式 (2) 要求 ,故取 。每次抽樣得到 處的噪聲正樣本的概率為 ,所以樣本以概率 含有這樣的點。此時 包含 ,而 在 之外,相對真實目標的風險至少為 。所聲稱的失敗概率 被大幅超出。證明所依賴的正是不變量 ;任意標籤噪聲需要不同的分析。
練習與解答
快速檢查
(若 中的正樣本為 和 ,返回甚麼盒?)
逐座標取最小值和最大值。
解答 · 答案
第一個座標為 ,第二個座標為 ,所以盒為 。
快速檢查
(取 、、,給出 (2) 的充分整數樣本數。)
計算 ,其中 。
解答 · 答案
,所以 即可。
快速檢查
(在本模型下,為甚麼負訓練樣本不可能落入返回的盒?)
比較返回的盒與目標盒。
解答 · 答案
返回的盒包含於 ,而每個負點在 外。
快速檢查
(在 (3) 中存在原子時,為甚麼下邊界帶的非嚴格不等式不能與嚴格尾部不等式互換?)
想像一個恰好位於閾值處的原子。
解答 · 答案
閾值處可能有正質量:包含該原子可能是使邊界帶質量至少為 所必需的,而排除該原子才能使尾部質量至多為 。例如,若閾值 處原子質量為 且下方沒有正質量,則非嚴格帶質量為 ,嚴格尾部質量為零。不必取原子的任意一部分。