Probably Approximately Correct
Valiant 的問題（1984）
Leslie Valiant 提出了一個看似簡單的問題：機器學習意味著什麼？不是「它能否記憶？」也不是「它能否完美預測？」而是：它能否從有限樣本中，以高機率、近似良好的方式，在多項式時間內學習？
這個框架讓他於 2010 年獲得圖靈獎，並奠定了計算學習理論的基礎。
兩個旋鈕
ε (epsilon) — 誤差容忍度。 近似正確表示誤差 ≤ ε。ε 越小，學習條件越嚴格。
δ (delta) — 信心參數。 可能正確表示成功機率 ≥ 1 − δ。δ 越小，所需的信心越高。
定義
若存在某演算法，使得對於任意資料分布 D 與任意目標概念 c ∈ C，給定從 D 抽取並由 c 標記的 m 個樣本，該演算法回傳的假設 h 滿足：
P[error(h) ≤ ε] ≥ 1 − δ
且 m 為 1/ε、1/δ 與概念大小的多項式函數，則概念類 C 稱為 PAC-learnable。
In English: feed it enough examples & it gets close enough often enough, & 'enough' doesn't blow up exponentially.
有限假設空間的樣本複雜度
若我們的假設空間 H 包含有限個候選假設，經典分析給出：
m ≥ (1/ε)(ln|H| + ln(1/δ))
將上述公式視為預算：ε 減半時所需樣本數加倍；δ 減半時僅增加常數；|H| 加倍時僅增加 ln(2) 個樣本——對數規模，成長極為溫和。
假設類別的樣本大小計算
某個垃圾郵件過濾器從 |H| = 1,000,000 個候選規則集中選擇。我們希望錯誤率 ε ≤ 0.05，且信心水準 1 − δ = 0.99（亦即 δ = 0.01）。
粉碎與 VC 維度
當假設空間變無限大
當 |H| = ∞ 時，m ≥ (1/ε)(ln|H| + ln(1/δ)) 的界限便失效。大多數實用的假設類別（ℝᵈ 中的線性分類器、決策樹、神經網路）都包含無限多個候選假設。Vapnik 與 Chervonenkis 於 1971 年左右提出更豐富的複雜度量度：VC 維度。
粉碎（Shattering）
若假設類別 H 能產生某 n 個點的所有可能標記（即 2ⁿ 種二分法），則稱 H 粉碎 該集合。ℝ² 中的線性分類器可粉碎任意三個處於一般位置的點：對於這三個點的 8 種可能的 +/− 標記，總存在一條直線能正確分隔。
但線性分類器在 ℝ² 中 無法 粉碎排列成 XOR 組態的 4 個點。沒有任何一條直線能將對角線上的點對與反對角線上的點對分開。
VC 維度
VC(H) = H 能粉碎某個 n 點集合的最大 n 值。 對於二維線性分類器：VC = 3。對於二維軸對齊矩形：VC = 4。對於具有 W 個權重的神經網路：VC ≤ O(W² log W)（Bartlett & Anthony 1999）。
使用 VC 維度的樣本複雜度
將 PAC 界中的 ln|H| 以 VC 維度 d 取代：
m = O((d/ε) log(1/ε) + (1/ε) log(1/δ)) [BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE SECTION/STEP]
VC 維度可視為無限假設類的「有效複雜度」。低 VC 維度的假設類只需少量樣本即可泛化；高 VC 維度的假設類則需要更多資料。 [BLOCK_TYPE SECTION/STEP]
VC 維度作為有效假設數量 [BLOCK_TYPE SECTION/STEP]
一個神經網路有 W = 10⁹ 個權重。根據 Bartlett-Anthony 界，VC ≤ O(W² log W)。近似 VC ≈ W² log₂ W。 [BLOCK_TYPE SECTION/STEP]
Dropping Realizability, Posteriors over Hypotheses
Two Important Generalizations
Classical PAC assumes our target concept c lives inside our hypothesis class H. Real data carries noise, mislabels, & concepts our class cannot represent. Two extensions handle this.
不可知 PAC
捨棄 c ∈ H 的假設。現在我們要與 最佳假說 h* = argmin_{h ∈ H} risk(h) 競爭。界限的形式改變：不再追求接近完美，而是追求接近 H 內的最佳可能。
不可知界限：P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ，樣本複雜度 m = O(1/ε² × (VC(H) + log(1/δ)))。注意分母是 ε² 而非 ε：不可知學習需要更多樣本才能達到相同精確度。
PAC-Bayes（McAllester 1999）
從選擇單一假說轉為選擇假說的分布。先有先驗分布 P，觀察資料後得到後驗分布 Q。PAC-Bayes 界限 Q 下的期望風險：
𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]
KL(Q‖P) 衡量我們的後驗分布相對於先驗分布移動了多遠。兩種解釋如下：
1. 壓縮觀點。 當後驗分布接近其先驗分布（KL 較小）時，泛化效果良好——較小的資訊成本對應較小的泛化差距。
2. 貝氏觀點。 強先驗加上微弱的資料更新會產生緊密的界；弱先驗加上大量的資料更新則會產生較寬鬆的界。
為什麼 PAC-Bayes 很重要。 經驗 PAC-Bayes 界（Catoni 2007、Dziugaite & Roy 2017）為真實神經網路提供了數值上有意義的泛化保證，而傳統 PAC 界在此情境下往往失效。它們仍是我們對過參數化模型泛化能力最嚴謹的理論工具。
Reading a PAC-Bayes Bound
假設我們用 n = 50,000 個標記樣本訓練一個網路。訓練後，我們的權重後驗 Q 相對於高斯先驗 P 的 KL(Q‖P) = 200 nats。Q 下的經驗風險為 0.10。設定 δ = 0.05。
Overparameterization & Double Descent
古典 PAC 預測的災難
古典 PAC 預測：參數數量多於樣本數 = 災難性過擬合。在訓練資料上完美學習，在測試資料上隨機泛化。VC 界限預測只會死背而不學習。
現代神經網路的參數數量經常是訓練樣本的 10 倍到 1000 倍，卻仍能泛化。這在古典理論下不該發生，但它就是發生了。
我們被教過的 U 型曲線
古典偏差-變異：隨著模型容量增加，訓練誤差單調下降；測試誤差先下降（欠擬合減少），達到最小值後再上升（過擬合）。VC 理論預測的 U 形曲線。
實際發生什麼 — 雙重下降
Belkin 等人（2019）顯示，測試誤差在達到插值閾值（容量 = 樣本數）之前遵循古典 U 形曲線，超過該閾值後測試誤差再次下降。大量過參數化的模型泛化能力比「剛好足夠大」的模型更好。
為什麼古典 PAC 理論無法解釋此現象
1. 無分佈假設過於悲觀。 真實資料具有結構（低內在維度、流形幾何）。PAC 界限適用於最壞情況的分佈；真實分佈則利用了 SGD 也能利用的結構。
2. 隱式正則化。 在過參數化網路中，SGD 會找到最小範數或最小複雜度的內插解，而非任意解。古典理論假設最壞情況的經驗風險最小化器；實際演算法則選擇良性解。
3. 假設類別定義錯誤。 SGD 實際探索的有效假設類別遠小於名義上的權重空間。PAC-Bayes 後驗能捕捉此現象；VC 維度則無法。
現代理論研究（Bartlett, Long, Lugosi, Tsigler 2020 關於良性過擬合；Nakkiran et al 2020 關於雙重下降）正在建立後 PAC 泛化理論，以解釋我們所處的過參數化情境。
診斷古典 PAC 的失效
某研究團隊在 100,000 個標記樣本上訓練一個 10 億參數的網路。古典 PAC 預測其泛化界是空泛的，但實測測試準確率卻達到 95%。
Kaplan、Chinchilla 與自動化通用智慧的規模化 [BLOCK_TYPE SECTION/STEP]
從界限到經驗規模法則
[BLOCK_TYPE SECTION/STEP]古典 PAC 從理論上預測資料集大小，但結果通常為空。經驗規模法則從觀察中預測資料集大小，且實際有效。它們已取代 PAC，成為大型模型的實用規模化工具。 [BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE SECTION/STEP]
Kaplan et al (2020)
損失遵循參數 N、資料集 token 數 D 與運算量 C 的冪律關係：
L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC
將參數數量加倍會使損失下降固定的乘積因子。將資料量加倍也會使損失下降另一個固定的乘積因子。這些指數（αN、αD、αC）可用來衡量並預測跨許多數量級的前沿行為。
Hoffmann et al 2022 (Chinchilla)
Chinchilla 顯示 Kaplan 的指數過度偏重參數相對於資料。計算最優訓練大致需要 20 tokens per parameter：
D_opt ≈ 20 × N
GPT-3（175B 參數）在約 300B tokens 上訓練——依 Chinchilla 計算嚴重訓練不足。一個計算最優的 175B 參數模型需要約 3.5 兆 tokens。
The Data Wall
擴展我們的參數量需要按比例擴展 token 量。公開網路爬取可產生約 10¹³ 個有用的 token。一個假設的 10¹⁵ 參數自動化通用智慧模型將需要約 2×10¹⁶ 個 token——比現有網路資料多出三個數量級。
這就是我們的資料牆。 擴展定律預測，我們在遇到算力短缺之前，就會先遇到語料短缺。合成資料、多模態語料（影片、音訊、感測器串流）以及來自環境的強化學習（RL-from-environment）都旨在突破這道限制。
古典 PAC 理論（錯誤地）告訴我們需要 10²¹ 個樣本。擴展定律（根據現實校準）告訴我們需要 2×10¹⁶ 個樣本。這兩個數字都超過了現有文本量。目前前沿工作正致力於彌補這一差距。
估算自動化通用智慧語料庫
假設一家前沿實驗室提出一個 10¹⁴ 參數模型，並聲稱它將達到自動化通用智慧。我們想根據 Chinchilla 規則來估算其訓練語料庫的大小。
從理論界限到生產環境量測
停止計算界限；開始量測它們
古典 PAC 界限通常過於寬鬆。PAC-Bayes 界限在難以驗證的假設下可能較緊。實務上的替代方案是：在真實分佈上經驗性地量測 ε，並隨著系統運行持續更新。
想法 1 — 將覆蓋率視為經驗 PAC
一個 make coverage 目標會將 N 個保留問題送入你的查詢系統，並測量兩項比率：
- cache_hit_rate — 系統找到已知答案的比例
- i_dont_know_rate — 系統誠實拒答的比例
每次測量 = 一次 Bernoulli 試驗。根據觀察到的計數，計算真實比率的 Wilson 信賴區間。例如：N = 1000 筆查詢，觀察到的 i_dont_know_rate = 0.20 → 95% CI ≈ [0.177, 0.226]。上限 0.226 與 PAC 中的 ε 在 δ = 0.05 時的作用完全相同，但它是從真實資料與真實分佈推導而來，而非最壞情況的理論分析。 [BLOCK_TYPE production_audit/audit_content]
[BLOCK_TYPE production_audit/audit_content]
古典 PAC 詞彙同樣適用（ε、δ、confidence）。所使用的數學工具不同（二項式集中不等式 vs. VC 理論）。由於真實分佈具有可利用的結構，因此能得到更緊的結果。 [BLOCK_TYPE production_audit/audit_content]
[BLOCK_TYPE production_audit/audit_content]
想法 2 — 透過 Falsification Events 進行 PAC-Bayes 審核
[BLOCK_TYPE production_audit/audit_content]將每次 falsification（系統答案明顯錯誤）視為更新真實錯誤率 ε 後驗分佈的證據： [BLOCK_TYPE production_audit/audit_content]
[BLOCK_TYPE production_audit/audit_content]
1. Prior: ε ~ Beta(α₀, β₀)。選擇較弱的先驗，例如 Beta(1, 1) = 均勻分佈。
2. 每個查詢 都會產生一個 Bernoulli 結果：被篡改（1）或未被篡改（0）。
3. 在 n 次查詢中出現 k 次篡改後的後驗分佈： Beta(α₀ + k, β₀ + n − k)。
4. 後驗均值： (α₀ + k) / (α₀ + β₀ + n) → 當 n → ∞ 時趨近於實證篡改率。
5. ε 的 95% 可信區間 會隨 1/√n 而收窄。
這帶來什麼好處
- 來自實際部署的真實世界 ε₀ 估計，而非最壞情況理論
- 隨時有效的警示：當後驗可信區間跨越合約閾值時，立即通知負責人
- 單調置信：觀察到的查詢越多 → 置信區間越窄 → 保證越強
相關技術：帶線上重新校準的共形預測（Vovk）、序貫概率比檢定（Wald）、線上 PAC-Bayes（Haddouche & Guedj 2022）。同屬一類，但數學機制不同。
計算偽造事件的 Beta 後驗
我們的團隊對生產查詢系統進行覆蓋率稽核。先驗真實錯誤率 ε 為 Beta(1, 1)（均勻分布）。在 200 筆保留查詢中，觀察到 8 次偽造。