對樣本的簡短解釋
分類器可能僅因為假設類足夠靈活而擬合樣本。另一種可能是:它能從樣本的一小部分重構出來。如果是這樣,大部分觀測值並非指定該分類器所必需,可以用來檢驗由保留觀測值確定的假設。這個想法即使在整個假設類無限時,也能導出泛化界。
保留哪些觀測值是在看到數據後決定的,因此不能自動把它們視為隨機訓練集、把其餘部分視為獨立測試集。證明必須考慮所有可能保留的指標和所有可能的附加消息。對數據依賴的壓縮,這種計數是主要的數學代價。
精確的壓縮模型
設 是帶標籤樣本 上的分布,從 獨立同分布地抽取 。對分類器 ,記 。假設重構規則產生的所有分類器均可測,且下文使用的選擇、損失和風險事件可測。
定義 4.1.1
(帶附加資訊的壓縮方案)
確定性的壓縮過程選擇至多含 個位置的子集 ,以及恰好 個附加資訊比特。固定的確定性重構規則只接收按指標遞增排列的所選帶標籤樣本及這 個比特,返回分類器 ;它不接收其餘觀測值。附加字符串可以依賴整個樣本,所以證明要計入全部 種可能。如果不需要附加資訊,取 。
假設對於 ,最終重構出的分類器以概率一與全部 個樣本一致。例如,在可實現的採樣模型中,為該模型構造的壓縮方案可以保證這一點。定理並不聲稱每個分布或假設類都存在這樣的方案。樣本值允許重複:選擇針對位置,二項式計數針對位置而不是不同的數值。
壓縮界
定理 4.1.2
(有限附加資訊下的一致壓縮)
設 和 為整數。在上述模型中,對每個 ,以至少 的概率,重構分類器滿足
對數均為自然對數。此界可能大於一,此時結論仍正確,但不提供有效資訊。
概念視角組合
這個界在計算描述的數目
一個描述是一個配對:至多 個位置的集合,加上一個 比特字符串。這樣的描述共有 個,所以界可寫成 。取 、,得 ,;若 ,界為 。
證明
(計算每個可能的保留集合與附加字符串)
對 ,固定一個大小為 的位置集合 和一個特定的 比特附加字符串。對這些位置的樣本取條件後,重構規則得到一個固定分類器 ;其餘 個樣本仍是來自 的獨立抽樣。如果 ,則所有剩餘樣本都與 一致的條件概率至多為
此界一致適用於保留樣本的各種取值。大小為 的指標集合有 種,附加字符串有 種。對所有 、指標集合和字符串使用並集界,故「存在某個此類重構,其真實誤差大於 且與所有未保留樣本一致」的概率至多為
實際壓縮器可以用整個樣本選擇指標和附加比特;其輸出仍在上述計數之中。全樣本一致性保證它與未保留樣本一致。將最後的表達式設為 ,在所得閾值小於一時得到結論;若閾值至少為一,則風險至多為一,結論立即成立。
證明透視
為甚麼可以計算依賴數據的選擇
獨立性假設只用在一處:對一個固定的指標集合和附加字符串,給定所選值後,其餘 個樣本仍是來自 的獨立抽樣,由此得到因子 。實際選擇不必獨立於這些其餘樣本。關鍵的一步,是先對所有可能的選擇與字符串使用並集界,再問壓縮器實際選了哪一種。一致性假設使論證完結:無論實際產生哪個重構,它都屬於被計數的、與全部未保留樣本一致的那些之一。出現的是 而不是 ,因為保留的樣本可以免費擬合,所以只需考慮最壞情形 。若省去這一計數,就會把依賴數據的留出集誤當作事先固定的集合。
例題 4.1.3
(代入壓縮界)
、、、 時,指標集合數為 。界為
這是充分的高概率界,不是某次運行的精確風險。指標集合之和是證明中的代價:重構規則實際接收的是保留樣本和比特,而不是所有可能集合的單獨描述。樣本小時同一公式說明不了多少。取 、、、,指標集合數為 ,界為 ,大於一:結論仍正確,但無法由它得出風險的任何資訊。
保留兩個樣本的閾值方案
命題 4.1.4
(閾值類可壓縮為兩個樣本和兩個比特)
設分類器為實數上的 以及兩個常值分類器,並假設 可由此類實現:其中某個 滿足 。則幾乎必然地,樣本具有 、 的壓縮方案,其重構與全部 個樣本一致。因此 時上面的定理適用。
證明
(最大負點與最小正點)
每個有限樣本都幾乎必然與 一致。若兩類標籤都出現,選最大的觀測負樣本點 和最小的觀測正樣本點 ;若同一個極值出現在多個位置,選擇最小指標。與 一致蘊含 :若 ,每個負點都小於 ,每個正點都大於或等於 。取 重構 。每個觀測負點至多為 ,每個觀測正點至少為 ,故重構結果一致。
若標籤全為零,則不保留點,重構常零分類器;若標籤全為一,則重構常一分類器。兩個固定附加比特足以區分這些情形和混合情形。這裏並不聲稱它是最省的編碼。雖然閾值有無限多個,定理仍適用於壓縮後的重構。若同時出現兩種標籤卻次序顛倒,樣本便不與此類一致,因此不能悄悄刪去一致性假設。
例題 4.1.5
(由六個帶標籤點重構閾值)
取樣本 、、、、、,位置為 至 。最大負點是位置 1 的 。最小正點是 ,出現在位置 3 和 6;規則取最小指標,即位置 3。保留的一對是 和 ,附加字符串記錄兩種標籤都出現。重構為 。三個負點 、、 都小於 ,三個正點 、、 都大於它,所以 一致。重複的值說明為甚麼計數針對位置:兩個 是不同的位置,只保留其中一個。
例題 4.1.6
(只有一種標籤的邊界情形)
設全部 個標籤都是零,點為 。方案不保留任何樣本,即 ,附加字符串說明出現的是全零情形。重構為常零分類器,與四個樣本都一致。當 、、 時,界為 ,沒有意義,因為 太小。計數仍然涵蓋這種情形:實際壓縮器選了 ,它屬於被計數的 。
反例模式
空描述不能暗中使用樣本資訊
令 上的分布為均勻分布,所有真實標籤為零。考慮這樣一個規則:看過樣本後,在每個觀測過的點輸出零,在每個未觀測過的點輸出一。它的經驗誤差為零,但至少有 個定義域點未被觀察,故真實誤差至少為 。若稱其描述為「保留零個樣本、零個比特」,就無效:重構需要完整的觀測點列表。資訊被隱藏在計數之外時,不能應用 的壓縮界。
定理能說明甚麼,不能說明甚麼
定理控制一致重構假設的總體誤差。它不要求目標屬於有限類,也不計數所有可能分類器的基數。但它要求樣本獨立、重構規則固定、保留規模和附加資訊有界,以及樣本一致性。壓縮過程可能在統計上有意義,但尋找或重構它在計算上不可行;運行時間必須另行分析。
對於有噪聲或不可實現的數據,全一致的重構可能不存在。不能直接刪去一致性假設並保留相同證明:未保留觀測值不再全部與重構假設一致。允許訓練誤差的界使用不同的尾概率估計,並必須計入如何選擇這些錯誤。
常見錯誤
(忘記附加比特使計數相乘)
假設分析閾值方案時當作不需要附加資訊。對 、、,得到 ,比正確的 小。附加字符串在三種情形(混合、全零、全一)中作選擇,並集界必須對全部 個字符串求和,這裏貢獻 。重構規則在保留樣本之外讀取的任何內容,都要計入 。
常見錯誤
(把保留樣本當作普通訓練集)
寫成「用 個保留點訓練,用其餘 個測試」,容易讓人想到普通的訓練與測試劃分。保留點是看過全部 個樣本後才選的,所以其餘 個對實際選出的子集並不是獨立測試集。獨立性只在固定指標集合的條件下成立,這正是證明要為每一個可能的集合付出代價的原因。
練習與解答
快速檢查
(若 、,允許保留零個或一個樣本,有多少種指標子集?如果還允許 個附加比特,並集界中的計數如何改變?)
分別數大小為 0 和 1 的子集,再數附加字符串。
解答 · 答案
共有 個子集。三個比特允許 個附加字符串,因此並集計數乘以八。
快速檢查
(一個含兩種標籤且一致的閾值樣本,其最大負點為 、最小正點為 。給出一個重構閾值,並解釋為何沒有樣本點被誤分類。)
用中點規則。
解答 · 答案
取 。由最大負點和最小正點的定義,所有負點不大於 ,所有正點不小於 ,故 正確標記全部樣本。
快速檢查
(某過程聲稱 、,但重構讀取了整個樣本。定理證明的哪一步失效?)
想一想:保留樣本和比特固定後,甚麼被固定了。
解答 · 答案
給定零個保留樣本後,分類器仍由其餘全部觀測值計算,因而並未固定且不獨立。於是不能應用固定假設下的概率 。
快速檢查
(對固定 和置信水平 ,解釋為甚麼當 時所示界趨於零。不要求精確漸近常數。)
用 的冪界住指標集合之和。
解答 · 答案
當 時,指標集合之和至多為 ,故其對數至多按 的對數增長,而分母 線性增長。比值趨於零。