VC 維度與均勻大數法則（VC dimension and uniform laws of large numbers）

VC 維度回答了統計學習核心的問題：何時某個量的經驗平均不僅對一個固定函數、而是對整個函數類「同時均勻地」收斂到其真均值？這種均勻收斂正是從資料學習成為可能的原因——它保證使訓練誤差最小的假設也具有近乎最小的真誤差——而 Vapnik-Chervonenkis 維度是控制它何時成立及收斂多快的組合參數。

固定一個取 {0,1} 值的函數類 F（或幾何上一族集合）。對一個有限點樣本，若 F 能實現這 m 個點之 2^m 種可能標記中的每一種，則該類「打散」該樣本。F 的 VC 維度是 F 所能打散的最大樣本之大小——超過此斷點，F 便無法再實現所有標記。組合上的奇蹟，即 Sauer-Shelah 引理，是：一旦 VC 維度為有限的 d，F 在任何 m 個點上能產生的相異標記數只「多項式地」增長，如 O(m^d)，而非如 2^m 那樣指數增長。這個多項式增長正是馴服「對先驗無限類取聯集界」者。把它與對稱化步驟（將經驗過程與「幽靈樣本」比較並注入隨機 Rademacher 符號）及集中不等式（對上確界用 McDiarmid、對對稱化過程用 Hoeffding）結合，即得 VC 不等式：以至少 1 - delta 的機率，sup（在 f in F 上）|f 的經驗均值 - f 的真均值| <= C sqrt((d log(m/d) + log(1/delta)) / m)。由於此界對所有 f 均勻成立，它是一個「均勻」大數法則；上確界幾乎必然收斂到 0 的類稱為 Glivenko-Cantelli 類，而有限 VC 維度是典範的充分條件。

這是機器學習中泛化的理論基礎：它解釋了為何在 m 個樣本上訓練的低複雜度類之模型會泛化，並把樣本複雜度定在 m ~ d / eps^2 以學到精度 eps。誠實的提醒對實務要緊。VC 維度是最壞情形、與「分布無關」的量——它對最壞可能的資料分布界定均勻收斂，故對良性資料可能極度悲觀，而資料相關的複雜度量（Rademacher 複雜度，恰是上面的鏈接量）往往給出緊得多的界。經典形式的 VC 理論是針對二元分類；實值損失需要胖打散維度或偽維度。且有限 VC 維度是充分的，但速率 sqrt(d/m) 是最壞情形——基於間隔與局部化的分析能勝過它。最深刻的現代提醒：非常大的模型（深度網路）可能具有巨大或無窮的 VC 維度卻仍泛化良好，故 VC 維度並非泛化的全貌，只是其中一塊嚴格且具歷史奠基性的拼圖。