你的假設類有多大？容量度量

為何數假設的個數會失敗

有限類的界向你收取 log|H|。但平面上所有線性分隔器構成的類是無限的，於是 log|H| 無限大、界變得空洞——然而線性分隔器顯然能學習。解套之道在於：在任何有限的 m 點樣本上，一個無限類只能產生有限多種不同的標記方式。兩個在全部 m 點上都一致的假設，從資料的角度看是無法區分的，因此真正該重要的，不是存在多少個假設，而是它們在 m 點上展現出多少種行為。

這才是「有效大小」的正確概念，也是本篇每一個容量度量的根基。我們把對函數的粗略計數，換成一種度量：這個類別能多富表達性地切割資料——也就是操作意義下的模型容量（capacity）。有三種度量把這件事形式化，從最組合性的到最具資料適應性的。

VC 維度：組合式的答案

VC（Vapnik–Chervonenkis）維度以「打散」（shattering）來度量容量。若對 k 個點貼上 + 或 − 的全部 2^k 種標記方式，每一種都有 H 中某個假設能恰好實現，則稱這 k 個點被 H 打散。VC 維度就是 H 能打散的最大點集之大小。d 維中的線性分隔器 VC 維度為 d + 1；直線上的閾值函數 VC 維度為 1；而正弦族 sin(θx) 雖只有單一參數，VC 維度卻無限大——這是一記鮮明的警告：參數個數不等於容量。

其中的魔法是 Sauer–Shelah 引理：一旦樣本量超過 VC 維度 d，一個類別能產生的不同標記方式之個數只會以多項式成長（約 m^d），而非 2^m。把這個多項式增長函數代入原本 log|H| 的位置，一致收斂機器便能再次運轉——此時泛化落差的階為 sqrt(d·log(m) / m)。類別是無限的，但其有效對數大小是 d·log(m)，而可學習性則由「VC 維度是否有限」所支配。

\Pi_{\mathcal{H}}(m)\;\le\;\sum_{i=0}^{d}\binom{m}{i}\;\le\;\left(\frac{e\,m}{d}\right)^{d}

Sauer–Shelah 引理：当样本量超过 VC 维数 d 后，可实现的标注数只随 m 多项式增长，而不是 2^m。

覆蓋數：以解析度衡量容量

對於實值類別——回歸、間隔、核機器——「打散」過於粗糙。覆蓋數（covering numbers）以幾何方式度量容量：固定一個解析度 ε，問你在某個選定的度量下需要多少個 ε-球才能覆蓋整個類別，使類中每個函數都落在某個球心的 ε 之內。這個數目的對數即「度量熵」（metric entropy）。在每個尺度下都能用少量球覆蓋的類別很小；需要指數多個球的類別則很豐富。

覆蓋數是經驗過程理論的通用貨幣。它連結到 VC 維度（一個 VC 類其覆蓋數對 1/ε 呈多項式），它支撐「鏈結」（chaining）論證——Dudley 積分把各尺度的對數覆蓋數加總起來，遠比單一聯集界更緊地約束過程的上確界——它也是平滑性假設進入學習速率的途徑。日後當你看到某個 β-平滑函數類的速率形如 m^(−β/(2β+d))，它正是出自覆蓋數的計算。

\hat{\mathfrak{R}}_{S}(\mathcal{H})\;\le\;\inf_{\alpha\ge 0}\left(4\alpha+\frac{12}{\sqrt{m}}\int_{\alpha}^{\infty}\sqrt{\log N(\varepsilon,\mathcal{H},L_2)}\;d\varepsilon\right)

Dudley 熵积分：链式论证将每个分辨率 ε 下的覆盖数转化为 Rademacher 复杂度的上界。

Rademacher 複雜度：讓資料發言

三者之中最銳利的是 Rademacher 複雜度。取你實際的樣本，為每個點隨機附上一個 ±1 的符號，然後問這個類別能與這純噪聲相關到何種程度：Rademacher 複雜度就是 H 中某函數與隨機符號所能達到的最佳相關之期望值。能擬合隨機標記的類別其複雜度高、終將過擬合；無法擬合的類別其複雜度低、能夠泛化。它是對過擬合潛能的一種直接、依賴於資料的測量——你甚至能從你訓練所用的那份樣本上估計它。

\hat{\mathfrak{R}}_{S}(\mathcal{H})=\mathbb{E}_{\sigma}\!\left[\sup_{h\in\mathcal{H}}\frac{1}{m}\sum_{i=1}^{m}\sigma_i\,h(x_i)\right],\quad \sigma_i\in\{-1,+1\}

经验 Rademacher 复杂度：在你自己的样本上，假设类与随机 ±1 符号能对齐到何种程度。

Rademacher 複雜度之所以主導全局，是因為其他度量都約束它：它絕不大於以 VC 為基礎的估計，且 Dudley 鏈結能透過覆蓋數來約束它。關鍵是它會適應分佈——若你的資料落在某個良性的低維結構上，即使 VC 維度極大，經驗 Rademacher 複雜度仍然很小。這是第一個緊到有時能與現實吻合的度量，而第 4 篇的局部化版本會把它磨得更銳利。

# empirical Rademacher complexity (Monte Carlo estimate)
#   sigma_i ~ uniform({+1,-1});  S = sample of m points
R_hat = E_sigma[  sup_{h in H}  (1/m) * sum_i sigma_i * h(x_i)  ]
# gen. gap  <=  2 * R_hat  +  sqrt( log(1/delta) / (2m) )

若 H 能與隨機符號對齊，它就能擬合噪聲——也就會過擬合。

從容量到選擇：結構風險最小化

容量度量的作用不止於約束某個固定的類別——它們還讓你能選擇一個。結構風險最小化（SRM）把你的假設安排成一座複雜度遞增、層層巢套的階梯，然後最小化「經驗風險加上一個源自各層容量的複雜度懲罰」。你是在明確地最佳化偏差—變異權衡（bias–variance tradeoff）：低層欠擬合（偏差高）、高層過擬合（變異高），而懲罰項把你導向「真實風險之界最小」的那一層。

SRM 是你訓練過的每一個正則化目標的理論祖先，而最大化間隔的支援向量機（SVM）是它最著名的實例：SVM 不去懲罰參數個數，而是控制一個「隨間隔增大而縮小」的容量——這正是通往第 4 篇間隔理論的橋樑。