2010 Leslie Valiant —— PAC 學習：把「學習」變成定理#

「機器能從例子中學到概念嗎？哲學家爭了三百年。Valiant 1984 年問了一個工程師的問題：多少個例子才夠？ 答案是一條公式。」

案件檔案#

前因#

1980s，神經網路與專家系統（1994 案）都號稱「學習」， 但學習沒有理論：多少樣本？誤差何界？哪類概念 根本學不會？Valiant 1984 論文《A Theory of the Learnable》回答。

線索與推理#

線索一：PAC 的定義（Probably Approximately Correct）#

學習演算法 A 對概念類 C 是 (ε, δ)-PAC 可學習 ⟺
  對任意目標 c ∈ C、任意分佈 D、任意 ε, δ > 0：
  以 1−δ 的機率，A 輸出的假設 h 滿足
    error_D(h, c) ≤ ε
  樣本數 m = O((1/ε)(log|C| + log(1/δ)))   （一致界版）

三個關鍵寬容：機率地（可失敗 δ）、近似地 （可誤差 ε）、分佈相關地（只求對真實世界的 D 好）。 學習從神秘主義變成取樣統計。

線索二：計數複雜度 #P（1979）#

Valiant 定義 #P：計數版本的 NP。

#SAT：有多少組滿足指派？（不是「有沒有」）
#P-完全的實務震驚：數矩陣積和式（permanent）是 #P 完全的，
  但行列式（determinant）卻是簡單的 O(n³)
  ——一字之差、天壤之別（他用此聯結隨機化：
     permanent 可用隨機近似，FPRAS）

線索三：evolvability（2007–09）#

Valiant 的晚年野心：把演化也納入 PAC 框架—— 「物種是透過受限制的學習演算法（突變+選擇）學習其 生態位」。計算理論 × 演化生物學的橋樑。

線索四：平行計算#

Valiant 亦提出 BSP（Bulk Synchronous Parallel）模型 （1990）：並行計算的抽象成本模型（p 處理器、g 網路 延遲、l 同步開銷）——MapReduce 時代前先立好尺規。

理論評析#

PAC 的偵探學要義：把「概念」建模為集合、把「經驗」 建模為取樣、把「學會」建模為泛化界。其後裔：

VC 維（Vapnik–Chervonenkis）→ SVM 的泛化界
Rademacher 複雜度 → 現代統計學習
PAC-Bayes → 深度學習泛化理論（2018 案的理論武器）

「需要多少資料」自此可以先算後學——資料科學的 理論憲法。

後果#

• 機器學習課程的理論骨架（Mitchell 教科書第 2 章）。

• P 讓「計數也是一種難度」進入演算法課綱；#

  FPRAS 思想影響近似計數與隨機化證明。

關聯案件#

→ 1985-Richard-Karp與NP完全問題的證明、2011-Judea-Pearl與因果推理、2018-Bengio-Hinton-LeCun與深度神經網路