樣本壓縮界

如果一個學習者能丟掉幾乎全部的訓練資料，卻仍能從一個倖存的小子集精確重建出完全相同的假設，那麼這個假設就不可能太複雜——它實際上被那幾個保留下來的樣本所概括。樣本壓縮把這件事轉化為泛化保證：你為了重建預測器而需要保留的樣本越少，它就泛化得越好。壓縮是簡單性的證人。

一個大小為 k 的壓縮方案，把任意訓練集映射到至多 k 個樣本的子集（壓縮集）外加可能的少量旁位元，使得對該子集套用一個固定的重建函數，便能重現學習者的假設。由於從 m 個樣本中挑出保留樣本至多有約 m 的 k 次方種方式，「計數加聯集界」的論證便對一致方案給出約「k log m 加上 log 一除以 delta，再全部除以 m」的泛化誤差，不可知情形則有一個平方根版本——完全不涉及 VC 維度或任何假設類別容量。支撐向量機的支撐向量正是壓縮集的原型。

樣本壓縮是通往泛化一條截然不同的路徑——是組合式、與演算法相關的，而非以類別為本——而一個深刻結果顯示它在威力上本質等價於 VC 理論：每個 VC 維度為 d 的類別都容許一個大小約為 d 的壓縮方案，解決了一個長年懸而未決的問題。它直接解釋了最近鄰與 SVM 的泛化，並支撐集合式與字典式方法。提醒是：這些界要求重建只依賴壓縮集，因此它們適用於某種特定的演算法結構，而非任意學習者。