Phá vỡ & Kích thước VC

Khi Không Gian Giả Thuyết Trở Nên Vô Hạn

Giới hạn m ≥ (1/ε)(ln|H| + ln(1/δ)) bị phá vỡ khi |H| = ∞. Hầu hết các lớp giả thuyết hữu ích (bộ phân loại tuyến tính trong ℝᵈ, cây quyết định, mạng nơ-ron) đều chứa vô số ứng viên. Vapnik & Chervonenkis đã giải quyết vấn đề này vào khoảng năm 1971 bằng một thước đo độ phức tạp phong phú hơn: VC dimension.

Shattering

Một lớp giả thuyết H shatters một tập hợp n điểm nếu H có thể tạo ra mọi nhãn có thể có của n điểm đó (tất cả 2ⁿ nhãn nhị phân). Các bộ phân loại tuyến tính trong ℝ² có thể shatter bất kỳ 3 điểm nào ở vị trí tổng quát: với mỗi một trong 8 cách gán nhãn +/− có thể có của 3 điểm đó, luôn tồn tại một đường thẳng phân tách chúng chính xác.

Nhưng các bộ phân loại tuyến tính trong ℝ² không thể shatter 4 điểm được sắp xếp theo cấu hình XOR. Không có đường thẳng nào tách cặp đường chéo khỏi cặp đường chéo phụ.

VC Dimension

VC(H) = số n lớn nhất sao cho H có thể shatter một tập hợp n điểm. Đối với bộ phân loại tuyến tính 2D: VC = 3. Đối với hình chữ nhật trục song song trong 2D: VC = 4. Đối với mạng nơ-ron có W trọng số: VC ≤ O(W² log W) (Bartlett & Anthony 1999).

Độ phức tạp mẫu với VC Dimension

Thay thế ln|H| trong giới hạn PAC của chúng ta bằng VC dimension d:

m = O((d/ε) log(1/ε) + (1/ε) log(1/δ))

VC dimension đóng vai trò là 'độ phức tạp hiệu quả' của một lớp vô hạn. Một lớp giả thuyết có VC dimension thấp có thể tổng quát hóa từ ít mẫu; một lớp có VC dimension cao đòi hỏi nhiều dữ liệu hơn.

VC Dimension như Số lượng Giả thuyết Hiệu quả

Một mạng nơ-ron có W = 10⁹ trọng số. Theo bất đẳng thức Bartlett-Anthony, VC ≤ O(W² log W). Xấp xỉ VC ≈ W² log₂ W.

Bỏ giả định Realizability, Phân phối hậu nghiệm trên các giả thuyết

Hai Mở rộng Quan trọng

PAC cổ điển giả định khái niệm mục tiêu c nằm trong lớp giả thuyết H của chúng ta. Dữ liệu thực mang nhiễu, nhãn sai và các khái niệm mà lớp giả thuyết không thể biểu diễn. Hai mở rộng xử lý vấn đề này.

Agnostic PAC

Bỏ giả định c ∈ H. Bây giờ ta cạnh tranh với giả thuyết tốt nhất trong lớp h* = argmin_{h ∈ H} risk(h). Hình dạng của bound thay đổi: thay vì tiến gần đến hoàn hảo, ta chỉ cần tiến gần đến mức tốt nhất có thể trong H.

Bound Agnostic: P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ với độ phức tạp mẫu m = O(1/ε² × (VC(H) + log(1/δ))). Lưu ý ε² thay vì ε ở mẫu số: học agnostic cần nhiều mẫu hơn để đạt cùng độ chính xác.

PAC-Bayes (McAllester 1999)

Chuyển từ việc chọn một giả thuyết duy nhất sang chọn một phân phối trên các giả thuyết. Bắt đầu với prior P. Quan sát dữ liệu. Suy ra posterior Q. PAC-Bayes bound rủi ro kỳ vọng dưới Q:

𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]

KL(Q‖P) đo lường mức độ posterior của chúng ta đã dịch chuyển xa khỏi prior. Có hai cách diễn giải:

1. Quan điểm nén (Compression view). Một posterior gần với prior (KL nhỏ) sẽ tổng quát hóa tốt — chi phí thông tin nhỏ = khoảng cách tổng quát hóa nhỏ.

2. Quan điểm Bayesian. Prior mạnh + cập nhật dữ liệu yếu = biên chặt; prior yếu + cập nhật dữ liệu mạnh = biên lỏng hơn.

Tại sao PAC-Bayes quan trọng. Các biên PAC-Bayes thực nghiệm (Catoni 2007, Dziugaite & Roy 2017) cung cấp các đảm bảo tổng quát hóa có ý nghĩa số học cho các mạng nơ-ron thực tế, nơi các biên PAC cổ điển trở nên vô nghĩa. Chúng vẫn là công cụ lý thuyết chặt chẽ nhất của chúng ta về tổng quát hóa trong mô hình quá tham số hóa.

Đọc một PAC-Bayes Bound

Giả sử chúng ta huấn luyện một mạng trên n = 50.000 ví dụ có nhãn. Sau khi huấn luyện, posterior Q của chúng ta trên các trọng số có KL(Q‖P) = 200 nats so với prior Gaussian P. Rủi ro thực nghiệm dưới Q là 0,10. Đặt δ = 0,05.

Overparameterization & Double Descent

Dự đoán thảm họa của PAC cổ điển

PAC cổ điển dự đoán: số lượng tham số lớn hơn số mẫu huấn luyện = overfitting thảm khốc. Học thuộc lòng hoàn hảo trên dữ liệu huấn luyện, nhưng khái quát ngẫu nhiên trên dữ liệu kiểm tra. Giới hạn VC dự đoán việc ghi nhớ mà không có học thực sự.

Các mạng nơ-ron hiện đại thường có số lượng tham số nhiều gấp 10× đến 1000× so với số mẫu huấn luyện nhưng vẫn khái quát tốt. Điều này không nên xảy ra theo lý thuyết cổ điển. Nhưng nó vẫn xảy ra.

Đường cong chữ U mà chúng ta đã được dạy

Classical bias-variance: khi dung lượng mô hình tăng, lỗi huấn luyện giảm đơn điệu; lỗi kiểm tra trước tiên giảm (bớt underfit), đạt cực tiểu, sau đó tăng (overfit). Đường cong hình chữ U được dự đoán bởi lý thuyết VC.

Điều Thực Sự Xảy Ra — Double Descent

Belkin et al (2019) chỉ ra rằng lỗi kiểm tra tuân theo đường cong chữ U cổ điển cho đến ngưỡng nội suy (dung lượng = #mẫu), sau đó GIẢM TIẾP sau ngưỡng đó. Các mô hình tham số hóa quá mức tổng quát tốt hơn so với các mô hình chỉ đủ lớn.

Tại Sao PAC Cổ Điển Bỏ Lỡ Điều Này

1. Giả định không phụ thuộc phân phối quá bi quan. Dữ liệu thực có cấu trúc (chiều nội tại thấp, hình học đa tạp). Các giới hạn PAC đúng với phân phối trường hợp xấu nhất; các phân phối thực khai thác cấu trúc mà SGD cũng khai thác.

2. Regular hóa ngầm. SGD trên mạng quá tham số hóa tìm nghiệm nội suy có chuẩn tối thiểu hoặc độ phức tạp tối thiểu, không phải nghiệm tùy ý. Lý thuyết cổ điển giả định nghiệm rủi ro thực nghiệm tối thiểu theo trường hợp xấu nhất; thuật toán thực tế chọn nghiệm “lành tính”.

3. Định nghĩa lớp giả thuyết sai. Lớp giả thuyết hiệu quả mà SGD khám phá nhỏ hơn rất nhiều so với không gian trọng số danh nghĩa. Hậu nghiệm PAC-Bayes nắm bắt được điều này; chiều VC thì không.

Các công trình lý thuyết hiện đại (Bartlett, Long, Lugosi, Tsigler 2020 về overfitting lành tính; Nakkiran et al 2020 về double descent) đang xây dựng lý thuyết tổng quát hóa hậu-PAC, phù hợp với chế độ quá tham số hóa của chúng ta.

Chẩn đoán sự thất bại của PAC cổ điển

Một nhóm nghiên cứu huấn luyện mạng 1 tỷ tham số trên 100.000 mẫu có nhãn. PAC cổ điển dự đoán các chặn vô nghĩa. Thực nghiệm cho thấy độ chính xác kiểm tra đạt 95%.

Kaplan, Chinchilla, & Định cỡ Trí tuệ Tổng quát Tự động [BLOCK_TYPE SECTION/STEP]

Từ Các Giới hạn đến Định luật Scaling Thực nghiệm

PAC cổ điển dự đoán kích thước tập dữ liệu về mặt lý thuyết và cho kết quả trống rỗng. Định luật scaling thực nghiệm dự đoán kích thước tập dữ liệu từ quan sát và thực sự hoạt động. Chúng đã thay thế PAC như công cụ định cỡ thực tế cho các mô hình lớn. [BLOCK_TYPE SECTION/STEP]

[BLOCK_TYPE SECTION/STEP]

Kaplan et al (2020)

Mất mát tuân theo quy luật lũy thừa theo số tham số N, số token dữ liệu D, và lượng tính toán C:

L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC

Nhân đôi số tham số sẽ làm giảm mất mát theo một hệ số nhân cố định. Nhân đôi dữ liệu cũng làm giảm mất mát theo một hệ số cố định khác. Các số mũ (αN, αD, αC) đo lường và dự đoán hành vi biên giới qua nhiều bậc độ lớn.

Hoffmann et al 2022 (Chinchilla)

Chinchilla cho thấy các hệ số của Kaplan đã đánh giá quá cao tham số so với dữ liệu. Huấn luyện tối ưu theo compute đòi hỏi khoảng 20 token cho mỗi tham số:

D_opt ≈ 20 × N

GPT-3 (175B tham số) được huấn luyện trên ~300B token — bị thiếu huấn luyện nghiêm trọng theo tính toán Chinchilla. Một mô hình 175B tham số tối ưu theo compute cần ~3,5 nghìn tỷ token.

The Data Wall

Việc mở rộng số lượng tham số đòi hỏi mở rộng số lượng token theo tỷ lệ tương ứng. Dữ liệu thu thập từ web công khai chỉ mang lại khoảng ~10¹³ token hữu ích. Một hệ thống trí tuệ tổng quát tự động giả định với 10¹⁵ tham số sẽ cần khoảng ~2×10¹⁶ token — lớn hơn ba bậc so với lượng dữ liệu web hiện có.

Đây là bức tường dữ liệu của chúng ta. Các định luật mở rộng dự đoán chúng ta sẽ gặp thiếu hụt kho ngữ liệu trước khi gặp thiếu hụt năng lực tính toán. Dữ liệu tổng hợp, kho ngữ liệu đa phương thức (video, âm thanh, luồng cảm biến) và học tăng cường từ môi trường đều nhằm vượt qua giới hạn này.

Lý thuyết PAC cổ điển (không chính xác) cho rằng chúng ta cần 10²¹ mẫu. Các định luật mở rộng (đã được hiệu chỉnh theo thực tế) cho thấy chúng ta cần 2×10¹⁶ mẫu. Cả hai con số đều vượt quá lượng văn bản hiện có. Công việc tiên phong hiện nay tập trung vào việc thu hẹp khoảng cách này.

Ước lượng Kho ngữ liệu cho Trí tuệ Tổng quát Tự động

Giả sử một phòng thí nghiệm tiên phong đề xuất mô hình 10¹⁴ tham số và tuyên bố nó sẽ đạt được trí tuệ tổng quát tự động. Chúng ta muốn xác định kích thước kho huấn luyện theo quy tắc Chinchilla.

Từ Lý Thuyết Giới Hạn đến Đo Lường Thực Tế

Dừng Tính Toán Giới Hạn; Bắt Đầu Đo Lường Chúng

Các giới hạn PAC cổ điển trở nên vô nghĩa. Giới hạn PAC-Bayes chặt chẽ nhưng dựa trên các giả định khó kiểm chứng. Giải pháp thực tế: đo lường ε thực nghiệm trên phân phối thực tế của bạn và cập nhật nó khi hệ thống hoạt động.

Ý tưởng 1 — Tạo Coverage như Empirical PAC

Mục tiêu make coverage chạy N câu hỏi đã tách ra qua hệ thống truy vấn của bạn và đo hai tỷ lệ:

- cache_hit_rate — tỷ lệ hệ thống của bạn tìm được câu trả lời đã biết

- i_dont_know_rate — tỷ lệ hệ thống của bạn thành thật từ chối trả lời

Mỗi phép đo = một phép thử Bernoulli. Từ số đếm quan sát được, tính khoảng tin cậy Wilson cho tỷ lệ thực. Ví dụ: N = 1000 truy vấn, i_dont_know_rate quan sát = 0.20 → 95% CI ≈ [0.177, 0.226]. Giới hạn trên 0.226 hoạt động chính xác như ε PAC tại δ = 0.05, được suy ra từ dữ liệu thực trên phân phối thực thay vì phân tích lý thuyết worst-case.

Từ vựng PAC cổ điển áp dụng (ε, δ, độ tin cậy). Cơ chế khác nhau (nồng độ nhị thức so với lý thuyết VC). Kết quả chặt chẽ hơn vì các phân phối thực mang cấu trúc có thể khai thác.

Ý tưởng 2 — Kiểm toán PAC-Bayes qua các Sự kiện Bác bỏ

Coi mỗi lần bác bỏ (câu trả lời của hệ thống rõ ràng sai) là bằng chứng cập nhật posterior cho tỷ lệ lỗi thực ε:

1. Prior: ε ~ Beta(α₀, β₀). Chọn prior yếu, ví dụ Beta(1, 1) = phân phối đều.

2. Mỗi truy vấn tạo ra một kết quả Bernoulli: bị làm giả (1) hoặc được giữ (0).

3. Hậu nghiệm sau k lần làm giả trong n truy vấn: Beta(α₀ + k, β₀ + n − k).

4. Giá trị trung bình hậu nghiệm: (α₀ + k) / (α₀ + β₀ + n) → tỷ lệ làm giả thực nghiệm khi n → ∞.

5. Khoảng tin cậy 95% trên ε thu hẹp theo 1/√n.

Những gì điều này mang lại cho chúng ta

- Ước lượng ε₀ thực tế từ triển khai thực tế, không phải lý thuyết trường hợp xấu nhất

- Báo động anytime-valid: khi khoảng tin cậy hậu nghiệm vượt ngưỡng hợp đồng, gọi người phụ trách [BLOCK_TYPE production_audit/audit_content]

- Độ tin cậy đơn điệu: càng nhiều truy vấn quan sát → CI càng hẹp → đảm bảo càng mạnh [BLOCK_TYPE production_audit/audit_content]

[BLOCK_TYPE production_audit/audit_content]

Các kỹ thuật họ hàng: conformal prediction với recalibration online (Vovk), sequential probability ratio tests (Wald), online PAC-Bayes (Haddouche & Guedj 2022). Cùng họ, khác công cụ toán học.

Tính hậu nghiệm Beta cho các falsification

Nhóm chúng ta đang chạy coverage audit trên hệ thống truy vấn production. Prior cho tỷ lệ lỗi thật ε: Beta(1, 1) (đều). Sau 200 truy vấn held-out chúng ta quan sát được 8 falsification.