從經驗風險最小化到保證：PAC 框架

我們想約束的那道落差

統計學習理論始於一個令人不安的事實：在已見資料上把誤差降到最低，本身幾乎無法說明在未見資料上的誤差。我們稱前者為「經驗風險」（empirical risk），後者為「真實風險」（true / population risk），而整門學問就是研究兩者之間的落差。當你執行經驗風險最小化（ERM）時，你是在賭「小的經驗風險會轉移為小的真實風險」——這個賭注有時安全，有時致命，而理論會告訴你是哪一種。

R(h)=\mathbb{E}_{(x,y)\sim\mathcal{D}}\big[\ell(h(x),y)\big],\qquad \hat{R}_S(h)=\frac{1}{m}\sum_{i=1}^{m}\ell(h(x_i),y_i)

真实风险是在分布上的期望损失，经验风险是其在样本上的平均——我们要约束的正是两者之间的差距。

落差之所以不會自動消失，關鍵在於「選擇」。若你在看到資料之前就固定了單一預測器，大數法則早已保證它的訓練誤差會收斂到真實誤差。但 ERM 並不事先固定預測器——它挑選在這份特定樣本上表現最好的那一個，而正是這個挑選動作，可能讓訓練誤差成為一個討好你的謊言。掌控泛化（generalization）意味著掌控「依資料挑選出來的假設」的誤差。

嚴謹陳述的 PAC 模型

由 Valiant 提出的 PAC（可能近似正確，probably approximately correct）框架把這個賭注講精確了。固定一個假設類 H 與一個損失。我們說某演算法能學會 H，若對每一個資料分佈，只要樣本夠多，它回傳的假設其真實風險都落在最佳可達值的 ε 之內（近似正確），且這件事在隨機樣本上以至少 1 − δ 的機率成立（可能）。兩個旋鈕——ε 控準度、δ 控信心——並承諾所需樣本數會隨你收緊任一者而以受控的方式成長。

\Pr_{S\sim\mathcal{D}^m}\!\Big[\,R\big(A(S)\big)\le \min_{h\in H} R(h)+\varepsilon\,\Big]\ge 1-\delta

不可知 PAC 条件：以至少 1−δ 的概率，学习器的风险与类中最优假设相差不超过 ε。

早期文獻在一個假設上分道揚鑣。在「可實現」（realizable）設定下，H 中存在某個假設達到零真實風險——目標真的落在你的類別內。但真實問題很少這麼配合，因此現代的預設是不可知學習（agnostic learning）：對真相不作任何假設，只要求能與 H 之內最佳的假設競爭。基準從「零誤差」轉為「H 所能達到的最小誤差」，而你的保證則是針對「超出這個下限的超額風險」。

陳明 H、損失，以及你假設的是可實現還是不可知設定。
固定目標準度 ε 與信心 1 − δ。
提問：需要多少樣本 m，才能讓 ERM 的超額風險以 ≥ 1 − δ 的機率 ≤ ε？
這個最小的 m，作為 ε、δ 與 H 的函數，就是樣本複雜度。

先一個假設，再有限多個

先從單一固定假設 h 開始。它的經驗風險是若干獨立有界隨機變數的平均，因此一個集中不等式（concentration inequality）——最簡單情形是 Hoeffding 不等式——告訴我們：這個平均不太可能偏離其期望太遠。具體而言，經驗風險與真實風險相差超過 ε 的機率，會以 exp(−2mε²) 的速度衰減。單一假設很容易；大數法則替你完成了工作。

現在讓 H 為有限類，含 |H| 個假設。ERM 可能輸出其中任何一個，因此我們必須同時掌控全部。聯集界（union bound）把失敗機率乘上 |H|：某個假設出現大風險落差的機率，至多是 |H|·exp(−2mε²)。令它等於 δ 並求解，你便得到第一個真正的樣本複雜度界——m 約為 (1/ε²)(log|H| + log(1/δ))。H 的容量只透過 log|H| 進入；豐富度是以對數來付費的。

\Pr\!\Big[\,\sup_{h\in H}\big|R(h)-\hat{R}_S(h)\big|>\varepsilon\,\Big]\le 2\,|H|\,e^{-2m\varepsilon^2}

对每个假设应用 Hoeffding 界，再通过联合界乘以 |H|，即可控制有限类上的最坏情形偏差。

# finite-class agnostic bound (sketch)
#   with prob >= 1 - delta, for all h in H:
#   risk(h)  <=  emp_risk(h)  +  sqrt( ( log|H| + log(1/delta) ) / (2 m) )
m_needed = ceil( (log(len(H)) + log(1/delta)) / (2 * eps**2) )

一致性偏差以 1/sqrt(m) 收縮；log|H| 是「挑選」的代價。

一致收斂與這個界的含義

上面的模式正是整個領域的核心工具：一致收斂（uniform convergence）。我們約束的不是單一假設的落差，而是所有假設同時的落差，如此一來，無論 ERM 恰好挑中哪一個都自動被涵蓋。一旦一致收斂在 ε 水準上成立，ERM 輸出的真實風險就落在 H 中最佳值的 2ε 之內——準度來自於掌控「由 H 索引的經驗過程之上確界」。

把這條樣本複雜度式子當成工程規格來讀。1/ε² 表示：把容忍誤差減半，資料量要變四倍——準度很貴。log(1/δ) 表示：信心很便宜——從 90% 提升到 99.9% 的信心，只把資料量乘上一個小常數。而 log|H| 是你的第一個容量度量：它對有限類有效，卻對我們真正使用的無限類（線性分隔器、神經網路）爆炸——而這正是下一篇要跨越的懸崖。

R(h)\le \hat{R}_S(h)+\sqrt{\frac{\log|H|+\log(2/\delta)}{2m}}\quad\text{for all } h\in H

一致收敛保证：真实风险至多为经验风险加上一个以 1/√m 衰减的项，其中 log|H| 是选择假设的代价。